Contents
Andrew Clark, Quanyan Zhu, Radha Poovendran, and Tamer Başar. 2012. Deceptive routing in relay networks. In Decision and Game Theory for Security. Springer, 171–185. 1. Introduction 2. Related Work 3. Model and Preliminaries 4. Game Formulation and Equilibria 5. Simulation Results 6. Conclusion 7. References
Keywords – Game Theory, Stackelberg Equilibrium, Routing Algorithms, Jamming and Security, Relay Networks
방해 공격(jamming attacks)에 대한 물리적 계층과 MAC 계층 방어 메커니즘은, 종종 공격 후의 처리량 delay와 loss에 본질적으로 반응함
section 1: 소개
section 2: 방해 공격과 방어에 대한 관련 작업 검토
section 3: 시스템과 적 모델 소개
section 4: 각 플레이어에 대한 게임 공식화 및 솔루션 알고리즘
section 5: 시뮬레이션 결과 제시
section 6: 논문 마무리
1. Introduction
무선 네트워크는 많은 군사 및 상업 애플리케이션에서 중요한 역할을 한다.
그러나 개방형 무선 매체는 그러한 네트워크를 적들이 노드 근처에서 간섭 신호를 방송하여 들어오는 패킷이 올바르게 디코딩되는 것을 방지하는 방해 공격(jamming attacks)에 취약하게 만든다.
Jamming attacks가 특히 해로운 경우
- 적이 노드에서 사용하는 physical 또는 MAC layer 프로토콜의 약점을 악용(exploit)할 때
- 멀티 홉 네트워크의 중간 relay nodes를 대상으로 end-to-end-throughput(처리량)을 줄일 때
jamming에 대한 defense mechanisms
- based on 물리적 계층 기술
- beamforming, 확산 스펙트럼, 지향성 안테나, 채널 서핑과 같은 MAC 계층 프로토콜 등
멀티 홉 라우팅이 사용될 때, source nodes는 jamming으로 인해
- 높은 패킷 손실이 발생하는 경로의 유량(flow rate)을 줄일 수 있음
- 낮은 패킷 손실이 발생하는 경로의 속도(rate)를 증가시킬 수 있음
When multi-hop routing is used, the source nodes can also decrease the flow rate on paths that experience high packet-loss due to jamming, while increasing the rate on routes experiencing lower packet-loss [10].
2. Related Work
분류 | 상세 |
목표 | 멀티 홉 무선 네트워크의 방해에 대한 사전 예방적 방어 메커니즘 연구 – 분리된 라우팅 경로를 따라서 무작위로 더미 패킷이 생성됨 – 이 패킷으로 기만적인 네트워크 흐름을 구성하여 방해함 In this paper, we study a proactive defense mechanism against jamming for multi-hop wireless networks, in which one or more network sources introduce a deceptive network flow, consisting of randomly generated dummy packets, along a disjoint routing path. |
제약사항 | 1) deceptive packets은 real packets과 동일한 링크를 통과하여 혼잡(congestion)과 지연(delay)을 증가시킬 것 2) 각 source node는 패킷 생성, 암호화, 전송할 수 있는 용량이 제한적 – 이 부족한 용량은 real/fake 흐름으로 나누어야 함 3) fake packets이 적의 능력과 목표에 대한 정보를 활용하는 최적의 전략에 따라 도입되지 않는다면, 속임수는 real nodes의 처리량을 높이는 데에 효과가 없을 수 있음 + 혼잡 증가로 비생산적일 수 있음 |
게임모델 | Stackelberg equilibrium에서 속임수 전략을 얻기 위해 2단계 게임 모델을 사용함 |
게임단계 | 소스와 재밍 공격을 가하는 적 사이의 2단계 게임 기반으로 프레임워크 설정 1) 소스는 real/deceptive flow 할당을 선택하기 위해 noncooperative game 수행 2) 적은 각 소스의 total flow 할당을 관찰, 처리량 감소를 극대화하기 위해 그에 따라 jamming strategy 선택 |
연구방법 | two types of source behavior 1) selfish source: 다른 소스에 의해 실행된 지연을 무시 → own throughput을 극대화 2) altruistic source: 소스의 유량을 선택할 때 다른 소스의 지연을 고려 각 경우에 대한 게임 평형을 도출 평형을 기반으로 각 소스에서 real/deceptive flows를 할당하기 위한 효율적인 알고리즘 제공 (through a simulation study) |
중점사항 | 방해에 대한 반응이 아닌, given set of network flows에 대한 방해의 영향을 정량화하는데 초점 |
결과 | 기만적인 흐름을 도입하여 방해 공격을 저지 → 적에게 자원 낭비 → 유효한 패킷이 막히지 않도록 함 1) added deceptive flows: 네트워크 혼잡과 지연을 증가시킬 수 있음 2) effect of the deceptive flow: 다른 소스의 흐름 할당에 따라 달라짐, 소스 간의 결합을 초래함 – 적에 의해 막힌 기만적인 흐름을 도입 → 적: 그 흐름을 목표로 삼는 자원이 부족함 → 소스는 자신의 처리량을 할당, 인근 소스의 처리량도 개선 |
3. Model and Preliminaries
Fig.1. Illustration of the network model with two source nodes \(s_1\) and \(s_2\), which transmit data to destination \(t_1\) and \(t_2\), respectively, via the relay network consisting of five relay nodes \(r_1, r_2, ··· , r_5\).
4. Game Formulation and Equilibria
적과 네트워크 소스 간의 상호작용
1) 유속과 라우팅 토폴로지 관찰
2) 방해 전략을 선택하는 적의 행동 설명
3) 유량 \(x_f\)을 결정하는 소스의 행동에 대한 논의
4.1 Game Formulation
deceptive jamming game은 두 단계로 구성되어 있음
첫 번째 단계에서, 각 소스 \(s_i\)는 실제 및 기만적인 흐름 \(x_i^R\)과 \(x_i^D\)를 동시에 선택함
두 번째 단계에서, 적들은 모든 \(f \in \mathrm{F}\)에 대한 유량 \(x_f\)을 관찰하고 방해 속도 \(p_f\) 선택
f가 소스 \(s_i\)의 실제 흐름일 때 \(p_f\) ≔ \(p_i^R\)을 사용하며,
\(p_i^D\)는 소스 \(s_i\)와의 기만적인 흐름을 방해할 확률
적의 목표는 최적화 문제에 대한 해결책인 최적화 방어 전략 \(p_f^{*}, f \in \mathrm{F}_A\)을 찾는 것
\(\displaystyle maximize_{p_f, f \in F_A} \sum_{f \in F_A}U_A(p_f, x_f)\)
\(s.t. \sum_{f \in F_A} c_f p_f \leq J\)
상수 J: 적의 총 전력 예산, Section 4.3에서 분석을 위해 \(U_A(p_f, x_f) = p_f x_f\)을 선택함
각 소스 \(s_i\)에서 목표는 유틸리티 함수 \(U_i(x_i^R, x_i^D, x_{-i})\)를 최적화 (\(x_{-i}\): 다른 소스의 유속)
→ 실제 패킷의 지연을 제한하면서 자체 처리량을 극대화하여 유틸리티 기능으로 이어짐
Fig. 2. Illustration of two-stage games and Stackelberg equilibrium is used as solution concept (a) Selfish source nodes: each source first decides on deceptive and real flows in a noncooperative way. (b) Cooperative source nodes: source nodes jointly optimize their data rates to achieve the best total utility. The attacker A sniffs the traffic of the network after source nodes decide on their data rates, and launches a jamming attack by choosing the power levels to affect the flows within its range of influence.
(a) Selfish source nodes: 비협조적인 방식으로 deceptive and real flows을 결정
(b) Cooperative source nodes: 소스 노드는 best total utility를 달성하기 위해, 데이터 속도를 공동으로 최적화함
공격자 A는 소스 노드가 데이터 속도를 결정한 후, 네트워크 트래픽을 sniffing하여, 영향 범위 내 흐름에 영향을 미칠 레벨을 선택하여 방해 공격을 시작함
별도의 경로에 기만적인 흐름을 도입하면,
달성된 처리량↑, 소스의 오류율↓, 혼잡↑, 나머지 소스가 경험하는 지연↑
4.2 Equilibrium Concepts
Definition 1 (Stackelberg Equilibrium).
게임의 평형 개념은 각 플레이어가 사용할 수 있는 정보의 양에 달려 있다.
소스와 적 사이의 게임을 위해, 적들은 재밍 전략 \(p_1^R, p_1^D, … ,\)을 선택하기 전 소스 속도 \(x_1^R, x_1^D, … ,\) 의 소스 행동을 관찰
따라서 상대방은 소스의 행동을 관찰한 후 최적화 문제 (3)에 따라 재밍 전략 \(p_f^{*}\)를 선택할 것
5. Simulation Results
Matlab 시뮬레이션 연구를 통해 제안된 접근 방식을 설명
네 개의 소스, 네 개의 릴레이, 그리고 하나의 목적지가 있는 네트워크를 고려한다.(각 소스의 용량은 1)
모든 네트워크 링크는 동등한 용량을 가지고 있다.
6. Conclusion
속임수를 통해 공격을 완화하는 문제 연구
각 소스가 잘못된 트래픽 흐름을 생성 → 공격자가 기만적인 흐름을 목표로 하는 자원을 소비 → 실제 패킷이 방해를 피할 수 있도록 하는 방어 메커니즘을 고려
source와 jammer 사이의 two-stage game으로 deceptive jamming을 formulated함
1) source는 처리량(throughput)을 최대화하고 지연(delay)을 최소화하기 위해 real and deceptive flow를 동시에 선택
2) 공격자는 real and deceptive flow를 관찰하고 각 흐름의 분수로 대표되는 jamming strategy 선택
공격자의 최적 전략에 대한 closed-form expression을 도출
: 기만적인 흐름을 표적으로 삼는 데 사용될 적의 방해 자원 부분, 속임수 사용으로 인한 실제 흐름의 추가 처리량
For the sources, 두 가지 경우에 대한 pure-strategy Stackelberg equilibria의 존재를 증명함
① 각 source가 자체 유틸리티 (selfish users)를 최대화하기 위해 흐름을 할당하는 경우
② 각 소스가 유속 (altruistic users)을 선택할 때 다른 소스의 혼잡을 통합하는 경우
두 경우 모두에 대한 평형을 계산하기 위한 알고리즘 제안
처리량을 극대화하고 지연을 최소화하기 위해 각 source에서 real and deceptive flows을 할당하는 효율적인 방법 제안
시뮬레이션 연구를 통한 접근 방식 결과: 이타적인 행동(altruistic behavior)이 출처의 전반적인 유용성을 향상시킴
향후 작업에서, selfish source behavior으로 인한 효율성의 손실을 분석하고, 속임수의 가치를 정량화하기 위한 지표 개발
출처가 적의 유틸리티 기능과 비용에 관한 불완전한 정보를 가지고 있는 경우를 연구할 것
7. References
- Andrew Clark, Quanyan Zhu, Radha Poovendran, and Tamer Başar. 2012. Deceptive routing in relay networks. In Decision and Game Theory for Security. Springer, 171–185.