6.3. Worm’s Optimal Control

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

6.3. Worm’s Optimal Control

Let

$((S, I, D), ν)$

be an optimal solution. Let the Hamiltonian

$H$

, and costate or adjoint functions

$λ_{S} (t)$

$λ_{I} (t)$

, and

$λ_{D} (t)$

, and a scalar

$λ_{0} \geq 0$

be defined as the following:

$H : = λ_{0} f (I) + (λ_{I} - λ_{S}) β I S - λ_{S} Q (S, I) S - λ_{I} B (S, I) I + (λ_{D} - λ_{I}) ν I,$

(6.4)

$\begin{matrix} {\dot{λ}}_{S} & = - \frac{\partial H}{\partial S} = - (λ_{I} - λ_{S}) β I + λ_{S} Q (S, I) + λ_{S} Q_{S} (S, I) S, \\ {\dot{λ}}_{I} & = - \frac{\partial H}{\partial I} = - λ_{0} f^{'} - (λ_{I} - λ_{S}) β S + λ_{I} B (S, I) + λ_{I} B_{I} (S, I) I - (λ_{D} - λ_{I}) ν, \\ {\dot{λ}}_{D} & = - \frac{\partial H}{\partial D} = 0 \end{matrix}$

(6.5)

along with the transversality (final) conditions,

$λ_{S} (T) = 0, λ_{I} (T) = 0, λ_{D} (T) = λ_{0} κ .$

(6.6a)

Then according to Pontryagin’s maximum principle with terminal constraints— [70, P.111 theorem 3.14] —there exist continuous and piecewise continuously differentiable costate functions

$λ_{S}$

$λ_{I}$

, and

$λ_{D}$

, and a constant

$λ_{0} \geq 0$

that at every point

$t \in [0 \dots T]$

where

$ν (\cdot)$

is continuous, satisfy (6.5) and transversality conditions (6.6), and we have

$\vec{λ} ≢ \vec{0},$

(6.7a)

$ν \in arg max_{(\underline{ν}) \in Ω} H (\vec{λ}, (S, I, D), \underline{ν}) .$

(6.7b)

First, we argue that

$λ_{0}$

has to be strictly positive. This is because if

$λ_{0} = 0$

, then the system of ODE in (6.5) becomes a homogeneous ODE with the final conditions of

$λ_{S} (T) = λ_{I} (T) = λ_{D} (T) = 0$

. However, this ODE has the unique solution of

$\vec{λ} \equiv \vec{0}$

, which contradicts (6.7a). Hence, combined with the property that

$λ_{0} \geq 0$

, we have

$λ_{0} > 0$

Define the switching function

$φ$

as follows:

$φ : = (λ_{D} - λ_{I}) I$

(6.8)

which is a continuous and piecewise continuously differential function of time and referring to (6.6) has the following final value:

$φ (T) = λ_{0} κ I (T) > 0 .$

(6.9)

The positivity comes from the facts

$λ_{0} > 0$

$κ > 0$

, and

$I > 0$

according to Lemma 6.1. Introduction of

$φ$

allows us to rewrite the Hamiltonian in (6.4) as follows:

$H = λ_{0} f (I) + (λ_{I} - λ_{S}) β I S - λ_{S} Q (S, I) S - λ_{I} B (S, I) I + φ ν .$

(6.10)

According to PMP in (6.7b), we have

$H (S, I, D, ν, λ_{S}, λ_{I}, λ_{D}) \geq H (S, I, D, \underline{ν}, λ_{S}, λ_{I}, λ_{D}) \forall \underline{ν} \in [0, 1] .$

(6.11)

Hence, the optimal

$ν$

satisfies

$φ ν \geq φ \underline{ν}$

, for all

$\underline{ν} \in [0, 1]$

. Thus, to find the optimal controller, one needs to maximize the linear function

$φ ν$

over the admissible set

$ν \in [0, 1]$

, which yields

$ν = {\begin{matrix} 0, & φ < 0, \\ 1, & φ > 0, \end{matrix}$

(6.12)

hence the name switching function. An immediate observation of the above relation is the following important property:

$φ ν \geq 0 .$

(6.13)

Also note that according to (6.9),

$φ (T) > 0$

and thus by continuity of

$φ$

and following (6.12),

$ν = 1$

over an interval of nonzero length toward the end of

$(0 \dots T)$

interval which extends until time

$T$

6.3.1. Structure of the Maximum Damage Attack

Whether in practice the worm can indeed inflict the maximum damages developed in this section depends on implementability of the optimal strategies. Specifically, if the optimal policies that inflict the maximum damage are complex to execute, then the worm may not be able to perform them since they are limited by the capabilities of their resource constrained hosts as well. Inauspiciously though, we show that optimal attack strategies follow simple structures (Theorem 6.1) which make them conducive to implementation. Fig. 6.2 provides visualization of the theorem. Note that in the left figure, the patching only immunizes the susceptible nodes (

$Q (S, I) \equiv 0.2$

but

$B (S, I) \equiv 0$

), while in the right figure, patching can equally immunize the susceptible and clean and immunize the infective nodes (

$Q (S, I) = B (S, I) \equiv 0.2$

Fig. 6.2 — FIGURE 6.2 Evaluation of the optimal controller and the corresponding states as functions of time. The parameters are time horizon: $T = 10$ , initial infection fraction: $I_{0} = 0.1$ , contact rate: $β = 0.9$ , instantaneous reward rate of infection for the malware: $f (I) = 0.1 I$ , reward per each killed node: $κ = 1$ . Also, we have taken $Q (S, I) \equiv 0.2$ , and $B (S, I) \equiv 0$ in the left and $B (S, I) \equiv 0.2$ in the right figures. That is, in the left figure, patches can only immunize the susceptible nodes but in the right figure, the same patch can successfully remove the infection, if any, and immunize the node against future infection. We can see that when patching can recover the infective nodes too (right figure), then the malware starts the killing phase earlier. This makes sense as deferring the killing in the hope of finding a new susceptible is now much riskier.

Recall that one of the basic tradeoff/s decisions that the attacker was dynamically faced with was the best timing to kill an infective node. Specifically, should an attacker kill a node as soon as it is infected so as to have claimed a casualty and secured a large damage on the network but losing the chance to further the spread? Or should it wait in anticipation of contacting new susceptible nodes and extend the contagion but at the risk of being detected and removed by the defender before it gets to destroy the host. Is the tradeoff broken by choosing an intermediate probability of killing the host? Theorem 6.1 states not.

Theorem 6.1

Consider an optimal solution

$ν$

that maximizes the worm’s damage function in(6.3)subject to the control constraint of

$ν (t) \in [0, 1]$

for all

$t \in [0, T]$

. Then

$ν (t)$

has the following structure:

$\exists t_{1} \in [0 \dots T)$

such that

$ν (t) = 0$

for

$0 < t < t_{1}$

and

$ν (t) = 1$

for

$t_{1} < t < T$

In words, an optimal

$ν (\cdot)$

is of bang-bang form, that is, it possesses only two possible values

$1$

and

$0$

, and switches abruptly between them. It has at most one such jump, which necessarily culminates at

$1$

. Thus, the theorem says that although killing a node early on would ensure a partial damage, the overall damage is more if this decision is deferred until toward the end of the attacking period despite the risk of recovery of the infective nodes by the system. Specifically, at the start of the outbreak, the number of susceptible nodes is high and infective nodes can be used to further propagate the infection. As time passes by, the level of susceptible nodes drops due to both spread of infection and immunization effort by the system. At a certain threshold, the risk of recovery of the infective nodes in the remaining time outweighs the potential benefit by spreading the infection. At this point, whose exact value depends on the parameters of the case, the malware starts killing the nodes with maximum possible rate. This will ensure that infective nodes are maximally used for spread of the infection and for attacker’s malicious activities.

In summary, Theorem 6.1 provides the optimal attack as follows: initially, the effort of the malware is focused on spreading the worm and amassing infective nodes without killing any. Subsequently, the reverse course of action is taken: at a threshold time, the amassed infected nodes are slaughtered at the highest rate which lasts till the end of the interval.

Note that the optimal killing policy (

$ν$

) will be completely specified by the (only possible) jump points (trigger epoch). Given the flexibility provided by software-driven devices, the infective nodes can subsequently execute these strategies without coordinating any further among themselves or with any central entity. The transition time can be determined by solving a system of differential equations, as described in the previous sections. Such systems can be solved very fast due to the existence of efficient numerical algorithms for solving differential equations, and the computation time is constant in that it does not depend on the number of nodes

$N$

. Note also that our algorithms do not require any local or global information as time progresses and only the initial information is sufficient to determine the decision of infective nodes for the entire interval.

Fig. 6.3 shows the effect of increasing the patching rates

$Q$

and

$B$

on the trigger epoch. We observe that increasing the patching rate generally decreases the jump time. Intuitively, in a system with a large recovery rate, both the susceptible and infective nodes recover rapidly. Hence, the worm should start killing them earlier in order to not lose too many nodes in the competition with the network administrator to the pool of recovered. Note also that the starting time of the killing is sensitive to the value of recovery rate when the patching can impact both infective as well as susceptible nodes (

$B = Q$

). This is because when

$B \equiv 0$

, once a node is infected, then it will not be recovered by the system and is safely in the tally of the worm, but when

$B > 0$

, the worm is in competition with the system and excessively deferring the killing is ever more risky if the speed of recovery of the victims is increased.

Fig. 6.3 — FIGURE 6.3 The jump (up) point of optimal $ν$ , i.e. the starting time of the slaughter period, for different values of the patching and rates. For both curves, we have taken the recovery rate of the susceptible nodes, i.e. $Q (S, I)$ as $γ$ , and the recovery rate of the infective nodes, i.e. $B (S, I)$ , once as zero and once as the same as $Q (S, I)$ where $γ$ is varied from $0.02$ to $0.7$ with steps of $0.02$ . The rest of the parameters are $f (I) = 0.1 I$ , $κ = 1$ , $T = 10$ , $β = 0.9$ , and $I_{0} = 0.1$ . Note that when $B (S, I) \equiv γ$ , then for $γ \geq 0.6$ , the malware starts killing the infective nodes from time zero.

In the next section, we provide the proof of the theorem.

6.3.2. Proof of Theorem 6.1

We first obtain some useful properties of the Hamiltonian and system states.

Lemma 6.2

$H = constant > 0$

Proof

First, the system is autonomous, i.e. the Hamiltonian and the control region do not have any explicit dependence on the independent variable

$t$

. Hence ([138, P.236]),

$H (S (t), I (t), D (t), ν (t), λ_{S} (t), λ_{I} (t), λ_{D} (t)) \equiv constant .$

(6.14)

Therefore, from (6.10),

$H = H (T) = λ_{0} f (I (T)) + λ_{0} κ ν (T) I (T) .$

(6.15)

We showed (after (6.7)) that

$λ_{0} > 0$

, and following Lemma 6.1,

$I (T) > 0$

; also

$ν (T) = 1 > 0$

, as we argued after (6.12). Hence,

$H (T) > 0$

. □

The second observation is that

$I$

satisfies the following condition:

Lemma 6.3

$(f^{'} (I) I - f (I)) \geq 0$

for all

$t \in [0 \dots T]$

Proof

By Lemma 6.1,

$I$

and

$S$

are nonnegative. Define

$ξ (I) = f^{'} (I) I - f (I)$

. Since

$f (0) = 0$

, we have

$ξ (0) = 0$

. Also,

$\frac{d}{d I} ξ (I) = ξ^{'} = {f^{'}}^{'} (I) I + f^{'} (I) - f^{'} (I) = {f^{'}}^{'} (I) I .$

Following Lemma 6.1 and properties of

$f$

, we observe that

$ξ^{'} \geq 0$

for all

$t \in [0 \dots T]$

. Thus, since

$ξ (0) = 0$

$ξ (I) = f^{'} (I) - f (I) I \geq 0$

for all

$t \in [0 \dots T]$

. □

We will also use the following key lemma in the sequel.

Lemma 6.4

For all

$t \in (0 \dots T)$

, we have

$λ_{S} \geq 0$

and

$(λ_{I} - λ_{S}) > 0$

Proof

Step-1. Following (6.6),

$λ_{I} (T) = (λ_{I} (T) - λ_{S} (T)) = 0$

and from (6.5) and (6.6),

$({\dot{λ}}_{I} (T) - {\dot{λ}}_{S} (T)) = - λ_{0} f^{'} (I (T)) - κ ν (T)$

, which is strictly negative. Thus, there exists an

$ϵ_{1} > 0$

such that on the interval of

$(T - ϵ_{1} \dots T)$

, we have

$(λ_{I} - λ_{S}) > 0$

. Also recall from (6.6) that

$λ_{S} (T) = 0$

Step-2. Proof by contradiction. Let

$t^{*}$

be defined as follows:

$t^{*} : = inf_{0 \leq t \leq T} {t ∣ λ_{S} (t) \geq 0 and (λ_{I} (t) - λ_{S} (t)) > 0 on the interval (t \dots T)} .$

$t^{*} = 0$

then we are done. Suppose

$t^{*} > 0$

. According to the continuity of

$λ_{S}$

and

$λ_{I}$

, and following step-1, we must have

$λ_{I} (t^{*}) - λ_{S} (t^{*}) = 0 OR λ_{S} (t^{*}) = 0 .$

• Case 1:

$λ_{I} (t^{*}) - λ_{S} (t^{*}) = 0$

. From (6.5) and continuity of

$λ_{S}$

$λ_{S} (t^{*}) \geq 0$

. We have

$[\frac{d}{d t} (λ_{I} - λ_{S})] (t^{* +}) = [\frac{d}{d t} (λ_{I} - λ_{S})] (t^{* -}) = - λ_{0} f^{'} + λ_{I} (B + B_{I} I) - \frac{φ}{I} ν - λ_{S} (Q + Q_{S} S) [∵] = - λ_{0} f^{'} + λ_{I} (B + B_{I} I) - \frac{φ}{I} ν - λ_{S} (Q + Q_{S} S) - \frac{H}{I} + λ_{0} \frac{f}{I} - \frac{λ_{S} Q S}{I} - λ_{I} B + \frac{φ}{I} ν [∵ (6.10)] = \frac{λ_{0}}{I} [f - f^{'} I] + λ_{I} B_{I} I - λ_{S} (Q + Q_{S} S) - \frac{λ_{S} Q S}{I} - \frac{H}{I} .$

(6.16)

From Lemma 6.3,

$[f - f^{'} I] \leq 0$

, and following the properties of

$B$

and

$Q$

, we have

$B_{I} \leq 0$

and

$Q, (Q + Q_{S} S) \geq 0$

. Also in this case,

$λ_{I} (t^{*}) = λ_{S} (t^{*})$

and

$λ_{S} (t^{*}) \geq 0$

(by assumption of the case). Now following Lemmas 6.1 and 6.2, and Eq. (6.16), we observe that

$[\frac{d}{d t} (λ_{I} - λ_{S})] (t^{* +}) = [\frac{d}{d t} (λ_{I} - λ_{S})] (t^{* -}) < 0$

. According to Property 6.1, this is a contradiction. Thus, case 1 could not occur.

• Case 2:

$λ_{I} (t^{*}) - λ_{S} (t^{*}) > 0$

, and

$λ_{S} (t^{*}) = 0$

, and

$\forall δ > 0$

, there exists

$t_{1} \in (t^{*} - δ \dots t^{*})$

such that

$λ_{S} (t_{1}) < 0$

. From continuity of

$λ_{S}$

and

$λ_{I}$

$\exists ϵ > 0$

such that on

$(t^{*} - ϵ \dots t^{*})$

$λ_{I} - λ_{S} > 0$

, and hence according to (6.5) and Lemma 6.1, wherever

$ν$

is continuous,

${\dot{λ}}_{S} \leq λ_{S} (Q + Q_{S} S)$

. Now consider a

$δ < ϵ$

, and define

$\hat{t}$

to be the point which has the lowest value of

$λ_{S}$

on the interval of

$[t^{*} - δ \dots t^{*}]$

. According to the assumption of case 2,

$λ_{S} (\hat{t})$

is strictly negative. Thus,

${\dot{λ}}_{S} ({\hat{t}}^{+}) \leq [λ_{S} (Q + Q_{S} S)] ∣_{t = \hat{t}} < 0$

. This, along with continuity of

$λ_{S}$

, imply that in the right neighborhood of

$\hat{t}$

$λ_{S}$

has lower values than

$λ_{S} (\hat{t})$

. This contradicts the definition of

$\hat{t}$

Therefore, none of the two cases could occur, which is a contradiction with the existence of

$t^{*}$

. The lemma hence follows by contradiction. □

We are now ready to proceed to the proof of the theorem.

6.3.3. Proof of Theorem 6.1: Optimal Rate of Killing

Proof

To establish the statement of the theorem, we will show that the switching function

$φ$

is equal to zero on at most one time epoch. The theorem subsequently follows from the relation between

$φ$

and

$ν$

given by (6.12).

Let us begin by studying two simple real analysis properties.

Property 6.1

Let

$f (t)$

be a continuous and piecewise continuously differentiable function of

$t$

. Assume

$f (t_{0}) > L$

. Now if

$f (t_{1}) = L$

for the first time before

$t_{0}$

, i.e.

$f (t_{1}) = L$

and

$f (t) > L$

for all

$t \in (t_{1} \dots t_{0}]$

, then

$\dot{f} (t_{1}^{+}) \geq 0$

.⁹

Property 6.2

Let

$f (t)$

be a continuous and piecewise continuously differentiable function of

$t$

. Assume

$t_{1}$

and

$t_{2}$

to be its two consecutive

$L$

-crossing points, that is,

$f (t_{1}) = f (t_{2}) = L$

and

$f (t) \neq L$

for all

$t_{1} < t < t_{2}$

. Now if

$\dot{f} (t_{1}^{+}) \neq 0$

and

$\dot{f} (t_{2}^{-}) \neq 0$

, then

$\dot{f} (t_{1}^{+})$

and

$\dot{f} (t_{2}^{-})$

must have opposite signs.

Now, we proceed with the proof of the theorem. Let us calculate the time derivative of the

$φ$

function wherever

$ν$

is continuous,

$\dot{φ} = ({\dot{λ}}_{D} - {\dot{λ}}_{I}) I + \dot{I} \frac{φ}{I} [∵] = (λ_{0} f^{'} + (λ_{I} - λ_{S}) β S - λ_{I} (B + B_{I} I) + (λ_{D} - λ_{I}) ν) I + \dot{I} \frac{φ}{I} [∵] = λ_{0} f^{'} I + (λ_{I} - λ_{S}) β I S - λ_{I} (B + B_{I} I) I + φ ν + \dot{I} \frac{φ}{I} + (H - λ_{0} f - (λ_{I} - λ_{S}) β I S + λ_{S} Q S + λ_{I} B I - φ ν) [∵] = H + λ_{S} Q S + λ_{0} (f^{'} I - f) - λ_{I} B_{I} I^{2} + \dot{I} \frac{φ}{I} .$