Maximum-reliability network interdiction

Network interdiction models are used to model a how a “defender” should best react to the presence of an “attacker” on a network.  In contrast to other network interdiction models, shortest-path network interdiction considers an attacker who is attempting to maximize their probability of reaching a given sink node from a given source node.  The attacker has a probability of traversing each arc safely.  The defender is able to “interdict” a subset of these arcs (within the confines of a budget) by placing sensors on them, thereby reducing the attacker’s probability of safely traversing that arc.

This network interdiction model can be seen as a bilevel game.  As the defender, we attempt to minimize the attacker’s maximum-reliability path through the network.  Many of the models are obtained by beginning with this min-max formulation and consolidating it into something more workable.

Here’s a picture to visualize what is happening.  As defenders, we choose first the arcs on which to place sensors.  Afterwards, the attacker will note our decision and take the “best” (maximum-reliability) path through the network.

nip_example

On the picture, the red dashes represent sensors.  The blue path represents the attacker’s maximum-reliability path through the network.

Let’s build a model!  We’ll need to define a few things first.

  • G=(N,A): our directed network
  • AD\subseteq A: arcs on which we can place sensor
  • R: interdiction budget
  • r_{ij}: cost of placing a sensor on arc (i,j)\in AD
  • p_{ij}: probability of attacker traversing arc (i,j)\in A undetected
  • q_{ij}: probability of attacker traversing arc (i,j)\in AD undetected when a sensor is present
  • \psi_j: value of maximum-reliability path from j to t with no sensors installed
  • s\in N: the attacker’s starting point
  • t\in N: the attacker’s goal

For our data to make sense, we must have 0\leq q_{ij} < p_{ij} \leq 1.

Great!  We’ll now add a few variables.

  • \pi_i: probability of attacker making it from node i\in N to node t undetected
  • x_{ij}: whether or not we place a sensor on arc (i,j)\in AD

If \pi_i is defined as above, we surely want \pi_t=1.  It only makes sense that if the attacker is present at the ending goal, they will make it to their goal with probability \pi_t = 1.

Furthermore, we want $\pi_i$ to take on specific values based on our values of x_{ij}.  Specifically, if we do interdict arc (i,j)\in AD, we want to enforce \pi_i\geq q_{ij}\pi_j.  If we do not interdict arc (i,j)\in AD, we want to enforce \pi_i\geq p_{ij}\pi_j.  Our objective will be to minimize \pi_s.  This will ensure that \pi_i is calculated to the attacker’s best path from i to t.

Now let’s examine the model.

\min \pi_s \\    \phantom{XXX} \pi_i - p_{ij} \pi_j \geq 0, \phantom{-(p_{ij}-q_{ij})\psi_j x_{ij}1} (i,j) \in A \setminus AD \\    \phantom{XXX}\pi_i - p_{ij}\pi_j \geq -(p_{ij}-q_{ij})\psi_j x_{ij}, \phantom{01} (i,j)\in AD \\    \phantom{XXX} \pi_i - q_{ij}\pi_j \geq 0, \phantom{-(p_{ij}-q_{ij})\psi_j x_{ij} 1}(i,j) \in AD \\    \phantom{XXX} \pi_t = 1 \\    \phantom{XXX} \displaystyle\sum_{(i,j) \in A} r_{ij} x_{ij} \leq R

Remember when we wanted to enforce certain conditions on \pi_i depending on our choices of x_{ij} for (i,j)\in AD?  Let’s see if those hold!

Let x_{ij}=0.  By the second constraint, we have \pi_i \geq p_{ij}\pi_j, as desired.  We also want to ensure the third constraint is dominated by this constraint; that is, it has no bearing on the model.  Because p_{ij} > q_{ij} we have \pi_i \geq p_{ij} \pi_j \implies \pi_i \geq q_{ij} \pi_j.  This proves the third constraint is dominated by the second.

Now, let x_{ij}=1.  By the third constraint, we have \pi_i \geq q_{ij}\pi_j, which is again what we want.  We will also ensure the second constraint is dominated by this constraint.  Because (p_{ij}-q_{ij})>0 and \pi_j\leq \psi_j, we have \pi\geq q_{ij}\pi_j \implies \pi_i \geq -(p_{ij}-q_{ij})\pi_j + p_{ij}\pi_j \implies \pi_i \geq -(p_{ij} - q_{ij}) \psi_j + p_{ij} \pi_j.  Thus, the second constraint is indeed dominated by the third.

In a few weeks, we’ll be taking a closer look at the stochastic case of the maximum-reliability network problem, in which the attacker’s starting and ending points are unknown.

Anyways, back to watching The Bachelor finale.  I’m totally only watching because my wife is. #TeamLauren

Cormican, Kelly J., David P. Morton, and R. Kevin Wood. “Stochastic network interdiction.” Operations Research 46.2 (1998): 184-197.

Advertisements

2 thoughts on “Maximum-reliability network interdiction

    1. We make a ton of assumptions about the knowledge of information. As defenders, we know with certainty the probabilities associated with each arc. We also assume that the attacker will know which arcs we interdict, and that the attacker will respond to our choices optimally. The former of these is plausible, though the latter is highly unlikely.

      The beauty of the above formulation is that it considers the worst-case scenario. When we as defenders assume the interdictor knows our choices, we place a firm bound on the attacker’s maximum-reliability path. It’s more likely that the attacker will operate suboptimally and will be even less likely to traverse the network safely. We win either way!

      Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s