Single Core Node

Problem description of PPSD model.

Given:
1. Network topology
2. Total budget of the defender
3. The probability that a node will be compromised is a function of its budget
allocation.
Objective:
To minimize the maximized compromise probability of the network
Subject to:
1. Budget constraint of the defender
To determine:
1. The budget allocated to each node by the defender
2. Which nodes will be attacked by the attacker
3. Which routing path will be chosen to reach the core node
Given Parameters
Notation / Description
B / Total budget of the defender
N / The index set of nodes in the network
w / The O-D pair (s, t)
Pw / The index set of candidate paths for O-D pair w
/ The indicator function, which is 1 if node i is on path p, and 0 otherwise, where
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;
bi / The budget allocated to protect node i;.
Pi(bi) / The probability of node i being compromised by an attack;.

Multiple Core Nodes

Given:

1. Network topology

2. Total budget of the defender

3. The probability that a node will be compromised is a function of its budget

allocation.

Objective:

To minimize the maximized compromise probability of the network

Subject to:

1. Budget constraint of the defender

To determine:

1. The budget allocated to each node by the defender

2. Which nodes will be attacked by the attacker

3. Which minimum costtree will be chosen to reach those multiple core nodes.

Given Parameters
Notation / Description
B / Total budget of the defender
N / The index set of nodes in the network
W / The set of all O-D pairs, where the origin is the node where intelligent attacker locates, and the destinations are the given multiple core nodes.
Pw / The index set of all candidate paths for O-D pairsw
/ The indicator function, which returns 1 if node iis on path p; 0 otherwise, where .
s / The node where the attacker locates, .
INi’ / The set of nodes with an incoming link to node i’, where .
INs / The set of nodes with an incoming link to node s.
h / The number of hops from s to the farthest core node in the network.
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;
bi / The budget allocated to protect node i;.
Pi(bi) / The probability of node i being compromised by an attack;.

Problem formulation

Objective function
Subject to
/ (1.1) / Total defense budget constraint.
/ / (1.2) / Require the budget allocated to each node should be between zero and the total budget B.
/ / (1.3) / Each node could be attacked.
/ (1.4) / The h and the cardinality are the legitimate lower bounds of the number of nodes on the attack tree.
/ / (1.5) / Requires that the union of the selected paths for those multiple core nodes forms a tree.
/ / (1.6) / Requires the number of selected node with an incoming link to node i’ is 1 or 0.
/ (1.7) / Requires no selected node with a link to root s.
/ / (1.8) / Jointly enforces that exactly one path is chosen between the given O-D pair.
/ / (1.9)

Problem reformulation

Objective function
Subject to
* / / (2.1) / Requires that the selected tree should be a minimal cost tree.
/ (2.2)
/ / (2.3)
/ / (2.4)
/ (2.5)
* / / (2.6)
/ / (2.7)
/ (2.8)
/ / (2.9)
/ / (2.10)

Lagrangean Relaxation

Subject to
/ (3.1)
/ / (3.2)
/ / (3.3)
/ (3.4)
/ / (3.5)
/ (3.6)
/ / (3.7)
/ / (3.8)

Subproblem 1.1 (related to decision variable xp)

Subject to
/ / (3.7)
/ / (3.8)

Subproblem 1.2 (related to decision variable yi, bi)

/ (3.1)
/ / (3.2)
/ / (3.3)
/ (3.4)
/ / (3.5)
/ (3.6)