Transcript Document

Near Optimal Budget
Allocation of Single
Core Node Attack
Presented by Erion Lin,
Graduate Student of
Department of Information
Management,
National Taiwan University
Outline
Introduction
 Motivation
 Problem Description
 Model Description
 Testing Environment
 Some Interesting Findings

Introduction
Introduction

Along the trend, much researchers pay
ever-increasing attention to the
survivability, and purpose many
architectures about that, including of
quantitatively and qualitatively analytical
models.
Introduction (Cont’d)
However, they focus on the random failure
of the survivability. Recent years, hacker’s
malicious attack would be the most
dangerous threat in the world.
 According to FBI’s survey, more than 500
billion U.S. dollars of loss results from
hacker’s malicious attack.

Introduction (Cont’d)

Therefore, we pose a model to evaluate
the intelligent attack cost, and maximize it.
Motivation
Motivation

The defender wants to stop the hacker to
attack the network due to its high attack
cost.
Problem Description
Problem Description

The attacker will try to find a shortest path
to minimize the total necessary attack
power (cost) for compromising the target
of attack, while the defender will try to
maximize the attacker’s total necessary
attack power through different budget
allocation on each node.
Problem Description (Cont’d)
Hack may go that way
S
T
Hack may go this way
Problem Assumptions



The attacker is on node s.
Only one node (node t, the most
important node) is the target of attack,
and all the others are not.
A node i is subject to attack only if a path
exists from node s to node i where all the
intermediate nodes on the path have
been compromised (they can be viewed
as the hop sites for attacking the target).
Problem Assumptions (Cont’d)
If attack power or more is applied to node
i, then the node is compromised.
 The topology is complete information
between the attacker and the defender.
 The attacker is smart enough that he/she
can always find the best strategy to meet
the objective.

Problem Assumptions (Cont’d)
The defender has total budget constraint.
 No link attacks are considered.
 No random failures are considered.
 The source node s and the destination
node t can’t consume any budget.

Model
Given Parameters
Notation
Description
B
Total budget owned by the defender
N
The index set of all nodes in the network
W
The O-D pair (s, t)
Pw
The index set of all candidate paths for
O-D pair w, w W
The indicator function which is 1 if node i
is on path p and 0 otherwise
 pi
Decision Variables
Notation
Description
yi
1 if node i is compromised, and 0 otherwise
xp
1 if path p is selected as the attack path and 0
otherwise
the budget allocated to protect node i, i  N
bi
aˆi (bi ) the attack power applied to the budget of node
i, i  N
Problem Formulation
Objective: max min  aˆ (b )  x 
bi
Subject to
xp
iN
i
i
pPw
b  B
iN
x
pPw
p
iN
1
x p  0 or 1
pi
IP 1
1.1
i
0  bi  B
p
1.2
1.3
 p  Pw
1.4
Problem Reformulation
Objective:min   y b
bi
Subject to
iN
i i
IP 2
 yibi    pibi
 p  Pw
2.1
x
iN
2.2
iN
pPw
x
pPw
iN
p
pi
p
1
 yi
2.3
x p  0 or 1
x 
iN
p
pi
yi  0 or 1
 p  Pw
| N | 1
2.4
2.5
iN
2.6
Problem Reformulation (Cont’d)
Subject to
b  B
iN
2.7
i
0  bi  B
iN
2.8
Lagrangian Relaxation
Optimization Problem
Z D (u1, u 2 , u3 , u 4 )  min   yibi   u1p  ( yi   pi )bi   ui2 (  x p pi  yi )  u3 ( bi  B)
LR
Subject to
 xp  1
LR 1
iN
pPw
p pw
iN
iN
pPw
iN
x p  0 or 1
 p  Pw
LR 2
yi  0 or 1
iN
LR 3
x 
iN
p
pi
| N | 1
0  bi  B
LR 4
iN
LR 5
Subproblem 1
(Related Decision Variable x p)
Objective Function
Z sub1 (u 2 )  min 
bi
iN
2
u
 i x p pi
pPw
Sub 1
Subject to
x
pPw
p
1
x p  0 or 1
x 
iN
p
pi
| N | 1
Sub 1.1
 p  Pw
Sub 1.2
Sub 1.3
Subproblem 2
(Related Decision Variable
y、
i bi )
Objective Function
Z sub 2 (u1 , u 2 , u 3 )  min   yibi 
bi
 min   yibi 
bi
 min
bi
iN

p pw
iN
 u
p pw
iN
1
p
 u ( y 
p pw
1
p
iN
i
pi
)bi   ui2 yi  u 3 ( bi  B)
iN
( yi   pi )bi   ui2 yi  u 3  bi  u 3 B
iN
iN
1
3
2
3
u
(
y


)
b

u
b

y
(
u

b
)

u
 p i pi i  i  i i i B
iN
iN
iN
Sub 2
iN
Subject to
yi  0 or 1
iN
0  bi  B
iN
Sub 2.1
Sub 2.2
Subproblem 2 Cont’d
(Related Decision Variable
Objective Function
Z sub 2' (u1 , u 2 , u 3 )  min
1
3
2
u
(
y


)
b

u
b

y
(
u
 p i pi i i i i  bi ) Sub 2’
p pw
Subject to
Sub 2.1’
yi  0 or 1
0  bi  B
yi  0, 
yi  1,
Sub 2.2’
1
3
3
u

b

u
b

(
u

 p pi i i
p pw
1
p
y、
i bi)
1
u
 p pi )bi
p pw
1
3
2
u
(1


)
b

u
b

(
u

b
)

(
u
(1


)

u

1)
b

u

 p pi
pi i
i
i
i
i
p pw
3
2
i
p pw
Testing Environment
Testing Environment

Nodes
 As

large as possible
Topology
 Grid
Network
 Random Network
 Scale-Free Network
Some Interesting
Findings
Some Interesting Findings─
Scale-Free Network
Scale-Free Network With 2 Degrees
300
100 nodes
200
200 nodes
100
300 nodes
400 nodes
0
500 nodes
0
10
20
30
40
50
60
Some Interesting Findings─
Scale-Free Network (Cont’d)
Scale-Free Network With 2 Degrees (Log Data)
0
0
-1
0.5
1
1.5
2
100 nodes
200 nodes
300 nodes
-2
400 nodes
500 nodes
-3
Some Interesting Findings─
Scale-Free Network (Cont’d)
n degrees with 500 nodes
400
1 degree
300
2 degrees
200
3 degrees
4 degrees
100
5 degrees
0
0
20
40
60
80
100
120
Some Interesting Findings─
Scale-Free Network (Cont’d)
n degrees with 500 nodes (Log Data)
0
-0.5 0
0.5
1
1.5
2
2.5
1 degree
-1
2 degrees
-1.5
3 degrees
-2
4 degrees
-2.5
5 degrees
-3
Some Interesting Findings─
Random Network
Random Network With n Nodes
100
80
100 nodes
60
200 nodes
40
300 nodes
20
400 nodes
0
0
2
4
6
8
10
12
Some Interesting Findings─
Random Network (Cont’d)
Random Network With n Nodes (Percentage Data)
0.25
0.2
100 nodes
0.15
200 nodes
0.1
300 nodes
0.05
400 nodes
0
0
2
4
6
8
10
12
Thanks for Your
Attention