Transcript A Game Theoretical Approach to Communication Security

Budhaditya Pyne
BEE-IV
Roll No: 000910801081
Jadavpur University









What is Game Theory?
A Brief History of Game Theory
Game Theory Basics with a suitable example
An Interesting Analogy with Communication
Systems
Non-Cooperative Game Theory in Wireless
Communications Research
Coalitional Game Theory in Wireless Networks
Research
Game Theory in Routing and Congestion Control
Game Theory in Network Security
Scope of Further Research
Game Theory in Communication
Systems
/ 341
Game Theory in Communication
Systems
/ 342
“…Game Theory is designed to address situations in which the
outcome of a person’s decision depends not just on how they choose
among several options, but also on the choices made by the people
they are interacting with…”
“… Game theory is the study of the ways in which strategic
interactions among economic (rational) agents produce outcomes with
respect to the preferences (or utilities) of those agents ….”
Game Theory in Communication
Systems
/ 343
•
•
•
•
•
•
•
Cournot (1838), Bertrand (1883): Economics
J. von Neumann, O. Morgenstern (1944)
•
“Theory of Games and Economic Behavior”
•
Existence of mixed strategy in 2-player game
O. Morgenstern 19021977
J. Nash (1950): Nash Equilibrium
• (Nobel Prize in Economic Sciences 1994)
Selten (1965): Subgame Perfect Equilibrium
Harsani (1967-68): Bayesian (Incomplete Information) Games
The 80’s
• Nuclear disarmament negotiations
• Game Theory for Security (Burke)
von Neumann 19031957
More recently:
• Auction modeling, mechanism design
• Routing, Congestion Control, Channel Access
• Network Economics
• Network Security
• Biology
Game Theory in Communication
Systems
John F. Nash
/ 344

GAME = (P,A,U)
◦ Players (P1; … ; PN): Finite number (N≥2) of
decision makers.
◦ Action sets (A1; … ;AN): player Pi has a
nonempty set Ai of actions.
◦ Payoff functions ui : A1x … xAN: R; i =
1;….;N
-
materialize players’ preference,
- take a possible action profile and assign to it a real number (von Neumann-Morgenstern).
Game Theory in Communication
Systems
/ 345





Cooperative and Non-Cooperative
Symmetric and Asymmetric
Zero-Sum and Non-Zero Sum
Simultaneous and Sequential
Static and Dynamic
Game Theory in Communication
Systems
/ 346
Game Theory in Communication
Systems
/ 347

1.
2.

1.
2.
What should Prisoner A do to minimize his
maximum punishment when:
Prisoner B confesses?
Prisoner B stays quiet?
What should Prisoner B do to minimize his
maximum punishment when:
Prisoner A confesses?
Prisoner A stays quiet?
Game Theory in Communication
Systems
/ 348
Game Theory in Communication
Systems
/ 349


Routing, Congestion Control and Channel
Access
Network Security
Game Theory in Communication
Systems
/ 34
10

How do we apply an abstract Mathematical
Tool like Game Theory in something as
realistic like Communication Systems?
Game Theory in Communication
Systems
/ 34
11


Communication Networks consists of several
nodes which have to take decisions regarding
several aspects like packet switching, packet
forwarding, etc.
These nodes are considered as the players.
Utility functions are often chosen to
correspond to achieved connection rate or
similar technical metrics.
Game Theory in Communication
Systems
/ 34
12
Game Theory in Communication
Systems
13


Various studies have analyzed radio
resource management problems in 802.11
WLAN networks.
In such random access studies, researchers
have considered selfish nodes, who try to
maximize their own utility (throughput)
only, and control their channel access
probabilities to maximize their utilities.
Game Theory in Communication
Systems
/ 34
14


1.
2.
Power control refers to the process through which
mobiles in CDMA cellular settings adjust their
transmission powers so that they do not create
unnecessary interference to other mobiles, trying,
nevertheless, to achieve the required Quality of
Service.
Power Control may be:
Centralized
Distributed
Game Theory in Communication
Systems
/ 34
15


In such distributed settings, the mobiles
can be considered to be selfish agents
(players) who try to maximize their utilities
(often modeled as corresponding
throughputs).
Game theory is considered to be a powerful
tool to study such scenarios.
Game Theory in Communication
Systems
/ 34
16



Coalitional game theory is a branch of game
theory that deals with cooperative behavior.
By cooperating, the players can strengthen
their position in a given game as well as
improve their utilities.
Coalitional game theory proves to be a
powerful tool for modeling cooperative
behavior in many wireless networking
applications such as cognitive radio
networks, wireless system, physical layer
security, virtual MIMO.
Game Theory in Communication
Systems
/ 34
17


It’s a non-cooperative game where the goal
of each user is to maximize it’s own
bandwidth by selecting its path.
First, the existence of the Nash
Equilibrium(NE) is determined because at
NE no user has the incentive to change its
routing strategy.
Game Theory in Communication
Systems
/ 34
18




It is investigated how the selfish behavior
of the users may affect the performance of
the network as a whole.
A concept of observed available bandwidth
is introduced on each link which allows a
user to find a path with maximum
bandwidth under max-min fair congestion
control.
A game-based algorithm is formulated to
compute the Nash Equilibrium (NE).
It is seen that by following the natural
game course the network converges to an
NE.
Game Theory in Communication
Systems
/ 34
19

Routing games
◦ users determine
network routes
◦ multi-path routing
and traffic splitting
is possible
◦ users’ data rates are
given and must be
routed
 Congestion games
 users determine their
data rate
 network routes are
given (single path)
Game Theory in Communication
Systems
/ 34
20
Game Theory in Communication
Systems
/ 34
21
Hacktivists
Hackers
Foreign Governments
Terrorists, Criminal Groups
Disgruntled Insiders
Game Theory in Communication
Systems
/ 34
22
Traditional Security Solutions
Attack
Defender:
strategy 1
strategy 2
…..
Defense
Example: Security
Remote Attack
A mathematical problem!
 Solution tool: Game Theory
Attacker
strategy 1
strategy 2
…..
Predict players’ strategies, Build defense mechanisms, Compute cost of security,
Understand attacker’s behavior, etc…
Game Theory also helps:
E.g.: Rate of Port Scanning
Trust
Incentives
IDS Tuning
Externalities
Machine Intelligence
Game Theory in Communication
Systems
/ 34
23
Key Concepts
Forwarding has an energy cost of c
(c<< 1)
Successfully delivered packet: reward of 1
If Green drops and Blue forwards: (1,-c)
If Green forwards and Blue drops: (-c,1)
If both forward: (1-c,1-c)
If both drop: (0,0)
Each player is trying to selfishly maximize it’s net gain.
What can we predict?
Game Theory in Communication
Systems
/ 34
24
Key Concepts
Game:
Players: Green, Blue
Actions: Forward (F), Drop (D)
Payoffs: (1-c,1-c), (0,0), (-c,1), (1,-c)
Matrix representation:
Actions of Green
Actions of Blue
Reward of Green
Reward of Blue
Game Theory in Communication
Systems
/ 34
25
John F. Nash
(1928)
Nash equilibrium:
“…a solution concept of a game involving two or more players, in which no
player has anything to gain by changing his own strategy unilaterally…”
Game Theory in Communication
Systems
/ 34
26
Intruder
Game
Alice
p
X
Y
Bob
Z
1-p
Normal traffic
Intelligent
Virus
Trudy
a
Virus
Xn
b
Detection
If Xn > l => Alarm
Availability
Attack
Game Theory in Communication
Systems
/ 34
27
Scenario:
Source
(Alice)
M
What if it is
possible that:
Network
M’  M
User
(Bob)
Intruder
(Trudy)
Encryption is not always practical ….
Formulation: Game between Intruder and User
Game Theory in Communication
Systems
/ 34
28
Trudy
Bob
Alice
Y
Z
• Strategies (mixed i.e. randomized)
• Trudy: (p0,p1),
Bob: (q0,q1)
• Payoffs:
• One shot, simultaneous choice game
• Nash Equilibrium?
Game Theory in Communication
Systems
/ 34
29
Alice
X
p
Trudy
Y
Bob
Z
1-p
Pay: V
Game Theory in Communication
Systems
/ 34
30
Scenario
Normal traffic
a
Virus
b
Xn
Detection
If Xn > l => Alarm, ….
Assume a known
Virus: choose b to maximize infection cost
Detection system: choose l to minimize cost of
infection + clean up
Game Theory in Communication
Systems
/ 34
31
Scenario
Normal traffic
a
Virus
b
Xn
Detection
If Xn > l => Alarm, ….
2.4
l0=10
l0=15
2
Virus Gain: Linear
Smart virus designer picks
very large b, so that the
cost is always high ….
Regardless of l!
l0=5
2.2
1.8
1.6
1.4
1.2
Game Theory
in Communication
1
0
10
20
30
40
Systems
b
50
l (/sec)
60
70
80
90
/10034
32
Modified Scenario
Normal traffic
a Xn
Virus
b
Detection
If Xn > l => Alarm
•Detector: buffer traffic and test threshold
• Xn < l  process
• If Xn > l  Flush & Alarm
•Game between Virus (b) and Detector (l)
Game Theory in Communication
Systems
/ 34
33
Tree-Link
Game:
Game Theory in Communication
Systems
/ 34
34




Consider a tree with € links and n nodes. Let Ƭ
be the set of spanning trees.
To get all the nodes connected in a cycle-free
way, the Network Manager/Defender chooses a
spanning tree TϵƬ of the network
The attacker simultaneously chooses a link eϵ€
to attack
The attacker wins if the attacked link belongs
to the chosen spanning tree; the Defender wins
elsewise
Game Theory in Communication
Systems
/ 34
35

Game( modeled as a one-shot 2 player game)
◦ Graph = (nodes V, links E, spanning trees T)
 Defender:
Example:
chooses T T
 Attacker:
chooses e E (+ “No Attack”)
◦ Rewards
 Defender:
 Attacker:
-1eT
1eT - µe (µe cost of attacking e)
– Defender : choose a distribution a on T,
Defender: 0
-1
Attacker: 1- µµ21
to minimize the
expected attack loss
--Attacker: Choose a distribution b on E,
gain
to maximize the attack
Game Theory in Communication
Systems
/ 34
36
Assume: zero attack cost µe=0
Graph
Most vulnerable links
a)
1/2
Chance
1/2
b)
1/2
1/7
c)
1/7
Game Theory in Communication
Systems
1/7
1/7
1/7
1/7
1/7
Chance
4/7>1/2
/ 34
37
(G)=1
(G)=1/2
(G)=4/7
• Definition 1&2: For any nonempty subset E Ε
3
1
2
7
5
4
6
E={1,4,5}
|T  E|=2
M(E) =1
1.
M(E) = min{| TE|, TТ}
(minimum number of links E has in common with any spanning tree)
2.
Vulnerability of E
(E) = 1/3
(E) = M(E)/|E|
(minimum fraction of links E has in common with any spanning tree)
• Definition 3: A nonempty subset C Ε is said to be critical if
(C) = maxE Ε((E))
(C has maximum vulnerability)
vulnerability of graph ((G)) := vulnerability of critical subset
Game
Theory in critical
Communicationsubset
Defender: choose trees that minimally
cross
Systems
/ 34
38
Theorem 1:There exists a Nash Equilibrium where
• Attacker attacks only the links of a critical set C, with equal probabilities
• Defender chooses only spanning trees that have a minimal intersection
with C, and have equal likelihood of using each link of C, no larger than that
of using any link not in C. [Such a choice is possible.]
There exists a polynomial algorithm to find C [Cunningham 1982]
Theorem generalizes to a large class of games.
Game Theory in Communication
Systems
/ 34
39
Edge-Connectivity is not always the right
metric!
If ν ≤ 0:Attacker: “No Attack”
Defender can invest to make µ high
Deter attacker from attacking
• Need to randomize choice of tree
Network
Design
Additional link
ν= 3/4
Network in b) is more vulnerable than network in c)
ν= 2/3
a)
ν= 3/5
b)
c)
2/3 > 3/5
Game Theory in Communication
Systems
/ 34
40
Game Theory helps for a better understanding
of the Security problem!
Intruder and Intelligent Virus Games:
• Most aggressive attackers are not the most dangerous ones
• Mechanisms to deter attackers from attacking
Availability Games
◦ Critical set
 Vulnerability ((G)): a metric more refined than edgeconnectivity
 Analyzing NE helps determine most vulnerable subset of
links
 Importance in topology design
 Polynomial-time algorithm to compute critical set
◦ Generalization
 Set of resources for mission critical task
 Most vulnerable subset of resources.
Game Theory in Communication
Systems
/ 34
41

A certain number of issues
◦ Costs model
 Not based on solid ground
Game Theory for Airport Security
◦ Mixed strategy equilibrium
 How to interpret it?
ARMOR (LAX)
Airports create security systems
and terrorists seek out breaches.
◦ Nash equilibrium computation
 In general difficult to compute
Placing checkpoint
Game Theory in Communication
Systems
Allocate canine units
/ 34
42
•
Repeated versions of the games
– More realistic models
– Applications: Attack Graphs
•
Collaborative Security
– Team of Attackers vs Team of Defenders
– Trust and Security
– Role of Information
•
Security of Cloud Computing
– Are you willing to give away your information?
•
Policing the Internet
– Who is responsible for security flaws?
Game Theory in Communication
Systems
/ 34
43
Game Theory in Communication
Systems
/ 34
44