7.3. Network-Malware Dynamic Game

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

7.3. Network-Malware Dynamic Game

7.3.1. Formulation

Following the setup described in Section 7.2, consider a system with two players

N

$N$

(network) and

M

$M$

(malware), specified by a system of

n

$n$

differential equations [146, P.83]:

\dot{x} (t) = f (t, x (t), u^{N} (t), u^{M} (t)) t \in [t_{0}, T]

$\dot{x} (t) = f (t, x (t), u^{N} (t), u^{M} (t)) t \in [t_{0}, T]$

, where

u^{N} (t) \in U^{N} \subset R^{m}

$u^{N} (t) \in U^{N} \subset R^{m}$

, and

u^{M} (t) \in U^{M} \subset R^{s}

$u^{M} (t) \in U^{M} \subset R^{s}$

, and the initial condition

x (t_{0}) = x_{0}

$x (t_{0}) = x_{0}$

, and a damage function (the functional)

J (u^{N}, u^{M}) = g (x (T)) + \int_{t_{0}}^{T} h (x, u^{N}, u^{M}, t) d t

$J (u^{N}, u^{M}) = g (x (T)) + \int_{t_{0}}^{T} h (x, u^{N}, u^{M}, t) d t$

, where

x (t)

$x (t)$

is the

n

$n$

-dimensional state vector. Player

N

$N$

seeks to minimize

J

$J$

by choosing the

m

$m$

dimensional control function

u^{N} (\cdot)

$u^{N} (\cdot)$

, and player

M

$M$

seeks to maximize

J

$J$

by choosing the

s

$s$

-dimensional control function

u^{M} (\cdot)

$u^{M} (\cdot)$

. The game is therefore referred to as a dynamic two-player zero-sum game. The players’ payoffs and the set of strategies available to them are called rules of the game. Both players know the rules of the game and each player knows that its opponent knows the rule and ad infinitum.³ As we mentioned in the Introduction to this chapter, we consider open-loop strategies, that is, the controls only depend on time (and not on the state, or the previous history). This is appropriate in the context of the security in networks, as the instantaneous state of the network (exact fraction of the nodes of each type) is impossible (or very costly) to follow, for both of the players.

In our context, (7.1) provides the

f (\cdot)

$f (\cdot)$

functions, the initial conditions are provided by (7.1), (7.3) provides the

g (\cdot), h (\cdot)

$g (\cdot), h (\cdot)$

functions, (7.4a), (7.4b) provide

U^{N}, U^{M}

$U^{N}, U^{M}$

. Also, we have

n = 3, m = 2

$n = 3, m = 2$

s = 1

$s = 1$

. Note that the

f (\cdot), h (\cdot)

$f (\cdot), h (\cdot)$

functions in our context depend on time

t

$t$

only implicitly, that is through the state and control functions. Also, the formulation does not capture any other constraints on the state functions, and in our context it does not need to either, owing to Lemma 7.1.

We now consider the values of the game. The lower value denoted by

V_{*}

$V_{*}$

is the overall damage when the minimizing player (

N

$N$

) is given the upper-hand, i.e. selects its strategy after learning its opponent’s strategy. Mathematically,

V_{*} = {max}_{u^{M}} {min}_{u^{N}} J (u^{N}, u^{M})

$V_{*} = {max}_{u^{M}} {min}_{u^{N}} J (u^{N}, u^{M})$

. Conversely, the upper value of the game

V^{*}

$V^{*}$

is defined as

V^{*} = {min}_{u^{N}} {max}_{u^{M}} J (u^{N}, u^{M})

$V^{*} = {min}_{u^{N}} {max}_{u^{M}} J (u^{N}, u^{M})$

Thus,

V_{*}

$V_{*}$

(

V^{*}

$V^{*}$

, respectively) is the maximum (minimum, respectively) damage that the malware (network, respectively) can inflict (incur, respectively) if the other player has the upper-hand. Hence,

V_{*} \leq V^{*}

$V_{*} \leq V^{*}$

. A pair of strategies

(u^{N *}, u^{M *})

$(u^{N *}, u^{M *})$

is called a saddle-point if

J (u^{N *}, u^{M}) \leq J (u^{N *}, u^{M *}) = V \leq J (u^{N}, u^{M *})

$J (u^{N *}, u^{M}) \leq J (u^{N *}, u^{M *}) = V \leq J (u^{N}, u^{M *})$

for any strategy

u^{N}

$u^{N}$

of the network and

u^{M}

$u^{M}$

of the malware, and then

V

$V$

is the value of the game, and

V = V_{*} = V^{*}

$V = V_{*} = V^{*}$

Thus, if the network selects its saddle-point strategy

u^{N *}

$u^{N *}$

, irrespective of the strategy of the malware, the damage it incurs is at most

V

$V$

, which is also the minimum damage that the malware can inflict if it has the upper-hand. Thus, the network’s saddle-point strategy is also its robust strategy, in the sense, that it minimizes the maximum possible damage it can incur. Conversely, the malware’s saddle-point strategy is also its robust strategy, since it maximizes the minimum possible damage it can inflict. Also, the network’s and the malware’s saddle-point strategies are their respective best responses to the other’s robust strategy. We prove the existence of saddle-point pair in the next theorem.

Theorem 7.1

The dynamic game defined above has a saddle-point pair of strategies.

Proof

This theorem directly follows from Theorem 2 in page 91 of [146]. The necessary conditions of the theorem are readily satisfied in our game. Namely,

(i) the system function

f (t, x, u^{N}, u^{M})

$f (t, x, u^{N}, u^{M})$

in this game is continuous in states and controls and is moreover bounded. Note that this is sufficient for the condition in page 83 of [146] to hold;

(ii) the instantaneous pay-off function

h (t, x, u^{N}, u^{M})

$h (t, x, u^{N}, u^{M})$

and the terminal pay-off function

g (x (T))

$g (x (T))$

are continuous in the states and controls (page 84 of [146]);

(iii) the system function

f (t, x, u^{N}, u^{M})

$f (t, x, u^{N}, u^{M})$

is linear in controls. The set defining controls are convex sets, and the instantaneous pay-off function

h (t, x, u^{N}, u^{M})

$h (t, x, u^{N}, u^{M})$

is linear in controls (page 91 of [146]). □

7.3.2. A Framework for Computation of the Saddle-point Strategies

Since the set of deterministic strategies of each player is uncountably infinite, the saddle-point strategies and the value of the game cannot be computed using convex or linear programming. We now present a framework for numerical computation of the saddle-point strategies.

Define the Hamiltonian for a given policy pair

(u^{N}, u^{M})

$(u^{N}, u^{M})$

in an arbitrary two-person dynamic game as

H (u^{N}, u^{M}) = 〈 λ, f (x, u^{N}, u^{M}, t) 〉 + h (x, u^{N}, u^{M}, t)

$H (u^{N}, u^{M}) = 〈 λ, f (x, u^{N}, u^{M}, t) 〉 + h (x, u^{N}, u^{M}, t)$

, where the state functions

x (\cdot)

$x (\cdot)$

are those that correspond to the strategy pair

(u^{N}, u^{M})

$(u^{N}, u^{M})$

, and

λ

$λ$

, the costate (or adjoint) functions, are continuous and piecewise differentiable functions of time that satisfy the following system of differential equations wherever the controls

(u^{N}, u^{M})

$(u^{N}, u^{M})$

are continuous:

\dot{λ} = - \frac{\partial}{\partial x} H (x, λ, t)

$\dot{λ} = - \frac{\partial}{\partial x} H (x, λ, t)$

, and the final value (transversality) condition

λ (T) = \frac{\partial (g (x))}{\partial (x)} ∣_{x = x (T)}

$λ (T) = \frac{\partial (g (x))}{\partial (x)} ∣_{x = x (T)}$

. In our context,

$H (u^{M}, u^{N}) = κ_{I} I + κ_{D} D + u^{N_{i}} R_{0} - κ_{r} u^{N_{r}} + (λ_{I} - λ_{S}) β_{0} u^{N_{r}} I S - λ_{S} β_{1} R_{0} u^{N_{i}} S - λ_{I} β_{2} R_{0} u^{N_{i}} I + (λ_{D} - λ_{I}) u^{M} I,$ $H (u^{M}, u^{N}) = κ_{I} I + κ_{D} D + u^{N_{i}} R_{0} - κ_{r} u^{N_{r}} + (λ_{I} - λ_{S}) β_{0} u^{N_{r}} I S - λ_{S} β_{1} R_{0} u^{N_{i}} S - λ_{I} β_{2} R_{0} u^{N_{i}} I + (λ_{D} - λ_{I}) u^{M} I,$

where again the state functions

(S (\cdot), I (\cdot), D (\cdot))

$(S (\cdot), I (\cdot), D (\cdot))$

are obtained from (7.1) with

(u^{N} (\cdot), u^{M} (\cdot))

$(u^{N} (\cdot), u^{M} (\cdot))$

as the control functions, and the costate functions

(λ_{S} (\cdot), λ_{I} (\cdot), λ_{D} (\cdot))

$(λ_{S} (\cdot), λ_{I} (\cdot), λ_{D} (\cdot))$

are obtained from the following system of differential equations (with

u^{N} (\cdot), u^{M} (\cdot)

$u^{N} (\cdot), u^{M} (\cdot)$

as the control functions) with the final conditions,

${\dot{λ}}_{S} = - \frac{\partial H}{\partial S} = - (λ_{I} - λ_{S}) β_{0} u^{N_{r}} I + λ_{S} β_{1} R_{0} u^{N_{i}}, λ_{S} (T) = 0,$ ${\dot{λ}}_{S} = - \frac{\partial H}{\partial S} = - (λ_{I} - λ_{S}) β_{0} u^{N_{r}} I + λ_{S} β_{1} R_{0} u^{N_{i}}, λ_{S} (T) = 0,$

(7.5a)

${\dot{λ}}_{I} = - \frac{\partial H}{\partial I} = - κ_{I} - (λ_{I} - λ_{S}) β_{0} u^{N_{r}} S + λ_{I} β_{2} u^{N_{i}} R_{0} - (λ_{D} - λ_{I}) u^{M}, λ_{I} (T) = 0,$ ${\dot{λ}}_{I} = - \frac{\partial H}{\partial I} = - κ_{I} - (λ_{I} - λ_{S}) β_{0} u^{N_{r}} S + λ_{I} β_{2} u^{N_{i}} R_{0} - (λ_{D} - λ_{I}) u^{M}, λ_{I} (T) = 0,$

(7.5b)

${\dot{λ}}_{D} = - \frac{\partial H}{\partial D} = - κ_{D}, λ_{D} (T) = K_{D} .$ ${\dot{λ}}_{D} = - \frac{\partial H}{\partial D} = - κ_{D}, λ_{D} (T) = K_{D} .$

(7.5c)

Then, following [146, P.31], a necessary condition for the pair

(u^{N}, u^{M})

$(u^{N}, u^{M})$

to be a saddle-point strategy pair is that for all

t \in [0, T]

$t \in [0, T]$

$(u^{N}, u^{M}) \in arg min_{{\tilde{u}}^{N}} max_{{\tilde{u}}^{M}} H ({\tilde{u}}^{N}, {\tilde{u}}^{M}) and$ $(u^{N}, u^{M}) \in arg min_{{\tilde{u}}^{N}} max_{{\tilde{u}}^{M}} H ({\tilde{u}}^{N}, {\tilde{u}}^{M}) and$

(7.6a)

$(u^{N}, u^{M}) \in arg max_{{\tilde{u}}^{M}} min_{{\tilde{u}}^{N}} H ({\tilde{u}}^{N}, {\tilde{u}}^{M}) .$ $(u^{N}, u^{M}) \in arg max_{{\tilde{u}}^{M}} min_{{\tilde{u}}^{N}} H ({\tilde{u}}^{N}, {\tilde{u}}^{M}) .$

(7.6b)

Henceforth, we denote the saddle-point strategy pair as

(u^{N} (\cdot), u^{M} (\cdot))

$(u^{N} (\cdot), u^{M} (\cdot))$

, and

(S (\cdot), I (\cdot), D (\cdot))

$(S (\cdot), I (\cdot), D (\cdot))$

(λ_{S} (\cdot), λ_{I} (\cdot), λ_{D} (\cdot))

$(λ_{S} (\cdot), λ_{I} (\cdot), λ_{D} (\cdot))$

as the corresponding state and costate functions and

H

$H$

as the corresponding Hamiltonian. We now express

(u^{N} (\cdot), u^{M} (\cdot))

$(u^{N} (\cdot), u^{M} (\cdot))$

in terms of

(S (\cdot), I (\cdot), D (\cdot)), (λ_{S} (\cdot), λ_{I} (\cdot), λ_{D} (\cdot))

$(S (\cdot), I (\cdot), D (\cdot)), (λ_{S} (\cdot), λ_{I} (\cdot), λ_{D} (\cdot))$

using necessary conditions (7.6). Define

ψ^{N_{r}} : = (λ_{I} - λ_{S}) β_{0} I S - κ_{r}

$ψ^{N_{r}} : = (λ_{I} - λ_{S}) β_{0} I S - κ_{r}$

, and

ψ^{N_{i}} : = R_{0} - λ_{S} β_{1} R_{0} S - λ_{I} β_{2} R_{0} I

$ψ^{N_{i}} : = R_{0} - λ_{S} β_{1} R_{0} S - λ_{I} β_{2} R_{0} I$

, and

ψ^{M} : = (λ_{D} - λ_{I}) I

$ψ^{M} : = (λ_{D} - λ_{I}) I$

. Now, the Hamiltonian can be written as

$H = κ_{I} I + κ_{D} D + ψ^{N_{r}} u^{N_{r}} + ψ^{N_{i}} u^{N_{i}} + ψ^{M} u^{M} .$ $H = κ_{I} I + κ_{D} D + ψ^{N_{r}} u^{N_{r}} + ψ^{N_{i}} u^{N_{i}} + ψ^{M} u^{M} .$

(7.7)

Thus, the Hamiltonian is a separable function of different components of the defense controls

(u^{N_{r}} (\cdot), u^{N_{i}} (\cdot))

$(u^{N_{r}} (\cdot), u^{N_{i}} (\cdot))$

and the attack control

u^{M} (\cdot)

$u^{M} (\cdot)$

, that is, each of these appears in different terms in the right-hand side of the above characterization. Now, from the necessary conditions in (7.6) subject to the control constraints in (7.4), the saddle-point strategies are derived as

$u^{N_{r}} = u_{min}^{N_{r}} if ψ^{N_{r}} > 0 and u^{N_{r}} = u_{norm}^{N_{r}} if ψ^{N_{r}} < 0,$ $u^{N_{r}} = u_{min}^{N_{r}} if ψ^{N_{r}} > 0 and u^{N_{r}} = u_{norm}^{N_{r}} if ψ^{N_{r}} < 0,$

(7.8)

$u^{N_{i}} = 0 if ψ^{N_{i}} > 0 and u^{N_{i}} = 1 if ψ^{N_{i}} < 0,$ $u^{N_{i}} = 0 if ψ^{N_{i}} > 0 and u^{N_{i}} = 1 if ψ^{N_{i}} < 0,$

(7.9)

$u^{M} = u_{max}^{M} if ψ^{M} > 0 and u^{M} = 0 if ψ^{M} < 0 .$ $u^{M} = u_{max}^{M} if ψ^{M} > 0 and u^{M} = 0 if ψ^{M} < 0 .$

(7.10)

Since

ψ^{N_{r}}, ψ^{N_{i}}, ψ^{M}

$ψ^{N_{r}}, ψ^{N_{i}}, ψ^{M}$

are uniquely specified once the state and the costate functions are known, the above relations express the saddle-point strategies in terms of the state and costate functions. The strategies

u^{N_{r}} (\cdot), u^{N_{i}} (\cdot), u^{M} (\cdot)

$u^{N_{r}} (\cdot), u^{N_{i}} (\cdot), u^{M} (\cdot)$

can be substituted by the above characterizations in (7.1) and (7.5), resulting in a system of

s i x

$s i x$

differential equations involving only the state and the costate functions. Using standard numerical methods for solving differential equations, this system can be solved (very fast) using initial and final conditions (7.1) and (7.5). The state and costate functions obtained as solutions will now provide the

ψ^{N_{r}}, ψ^{N_{i}}, ψ^{M}

$ψ^{N_{r}}, ψ^{N_{i}}, ψ^{M}$

functions, and thereby the saddle-point strategies via (7.8)–(7.10). The resulting set of differential equations is nonlinear and a closed-form solution is unknown. However, as we will show in the next section, using novel techniques, even without access to the closed-form solution, we can establish the type of behavior that the saddle-point strategies exhibit.

7.3.3. Structural Properties of Saddle-point Defense Strategy

We establish that the saddle-point defense strategy has a simple threshold-based structure that ought to facilitate its implementation in a localized manner in resource constrained wireless devices. Specifically, we prove the following.

Theorem 7.2

For the saddle-point defense strategy

u^{N} (\cdot) = (u^{N_{r}} (\cdot), u^{N_{i}} (\cdot))

$u^{N} (\cdot) = (u^{N_{r}} (\cdot), u^{N_{i}} (\cdot))$

, there exists times

t_{1}

$t_{1}$

t_{2}

$t_{2}$

0 \leq t_{1} < T

$0 \leq t_{1} < T$

0 \leq t_{2} < T

$0 \leq t_{2} < T$

such that

•

u^{N_{r}} (t) = u_{\min}^{N_{r}}

$u^{N_{r}} (t) = u_{\min}^{N_{r}}$

for

0 < t < t_{1}

$0 < t < t_{1}$

, and

u^{N_{r}} (t) = u_{norm}^{N_{r}}

$u^{N_{r}} (t) = u_{norm}^{N_{r}}$

for

t_{1} < t < T

$t_{1} < t < T$

;

•

u^{N_{i}} (t) = 1

$u^{N_{i}} (t) = 1$

for

0 < t < t_{2}

$0 < t < t_{2}$

, and

u^{N_{i}} (t) = 0

$u^{N_{i}} (t) = 0$

for

t_{2} < t < T

$t_{2} < t < T$

The overall strategy therefore has the following three phases: In the initial aggressive defense phase, i.e. during

(0, min (t_{1}, t_{2}))

$(0, min (t_{1}, t_{2}))$

, the susceptibles select the minimum possible reception rate, and the dispatchers transmit the patches whenever they are in contact with any other node. Thus, the quarantining is the most stringent, and the recovery most rapid during this phase. Then, in the interim watchful phase, i.e. during

(min (t_{1}, t_{2}), max (t_{1}, t_{2}))

$(min (t_{1}, t_{2}), max (t_{1}, t_{2}))$

, one of the defense controls subsides while the other continues as before. Finally, in the terminal relaxed phase, i.e. in

(max (t_{1}, t_{2}), T)

$(max (t_{1}, t_{2}), T)$

, both defense controls subside, that is, the susceptibles select their normal reception rate and the dispatchers do not transmit the patches. Thus, the QoS in data traffic is back to its normal value and the resource consumption overhead due to patch transmission ends.

Note that the defense strategy always chooses either the maximum or the minimum values of the parameters except possibly at

t_{1}, t_{2}

$t_{1}, t_{2}$

. Such strategies are referred to as bang-bang in the control literature. The durations of the phases (i.e. the values of the threshold times

t_{1}, t_{2}

$t_{1}, t_{2}$

) and which defense subsides in the interim watchful period depend on the damage coefficients

κ_{I}, κ_{D}, K_{D}, κ_{r}, κ_{i}

$κ_{I}, κ_{D}, K_{D}, κ_{r}, κ_{i}$

. We will shed more light on the latter in Theorem 7.3 later. But first, we conclude this subsection by proving Theorem 7.2.

Proof

The continuity and piecewise differentiability of

ψ^{N_{r}} (\cdot), ψ^{N_{i}} (\cdot)

$ψ^{N_{r}} (\cdot), ψ^{N_{i}} (\cdot)$

follow from those of the costate functions. From the final conditions on the costate functions, i.e. (7.5),

ψ^{N_{r}} (T) = - κ_{r} < 0

$ψ^{N_{r}} (T) = - κ_{r} < 0$

ψ^{N_{i}} (T) = R_{0} > 0

$ψ^{N_{i}} (T) = R_{0} > 0$

. We show that

ψ^{N_{r}} (\cdot)

$ψ^{N_{r}} (\cdot)$

(

ψ^{N_{i}} (\cdot)

$ψ^{N_{i}} (\cdot)$

, respectively) is a strictly decreasing (increasing, respectively) function of time. Thus, each has at most one zero-crossing point in

(0, T)

$(0, T)$

; denote these as

t_{1}, t_{2}

$t_{1}, t_{2}$

. If

ψ^{N_{r}}

$ψ^{N_{r}}$

(

ψ^{N_{i}}

$ψ^{N_{i}}$

, respectively) has no zero-crossing point in

(0, T)

$(0, T)$

t_{1} = 0

$t_{1} = 0$

(

t_{2} = 0

$t_{2} = 0$

, respectively). Thus, from the continuity of the

ψ (\cdot)

$ψ (\cdot)$

functions, and from their terminal values, (i)

ψ^{N_{r}} (\cdot)

$ψ^{N_{r}} (\cdot)$

is negative in

(t_{1}, T)

$(t_{1}, T)$

and positive in

(0, t_{1})

$(0, t_{1})$

and (ii)

ψ^{N_{i}} (\cdot)

$ψ^{N_{i}} (\cdot)$

is positive in

(t_{2}, T)

$(t_{2}, T)$

and negative in

(0, t_{2})

$(0, t_{2})$

. The theorem follows from (7.8) and (7.9). We prove the strict monotonicity of

ψ^{N_{r}} (\cdot)

$ψ^{N_{r}} (\cdot)$

ψ^{N_{i}} (\cdot)

$ψ^{N_{i}} (\cdot)$

, using the following.

Lemma 7.2

λ_{S} > 0

$λ_{S} > 0$

and

λ_{I} > λ_{S}

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

λ_{D} \geq 0 \forall t, 0 < t < T

$λ_{D} \geq 0 \forall t, 0 < t < T$

The lemma is intuitive since the shadow prices (i.e. costate variables) associated with the susceptibles and dead nodes ought to be positive, and also the shadow price associated with the infectives ought to be at least as high as that associated with susceptibles. However, as we will see next, the proof requires detailed analysis of the state and costate differential equations (7.1) and (7.5), respectively, and is less direct.

Proof

Since

λ_{D} (T) = K_{D} \geq 0

$λ_{D} (T) = K_{D} \geq 0$

(from (7.5)), and

\frac{d}{d t} λ_{D} \leq 0

$\frac{d}{d t} λ_{D} \leq 0$

λ_{D} \geq 0

$λ_{D} \geq 0$

. Now, for the rest, we argue in two steps.

Step 1:

λ_{S} (T) = 0

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

and

λ_{I} (T) = K_{I} = 0

$λ_{I} (T) = K_{I} = 0$

, also

{\dot{λ}}_{I} (T) - {\dot{λ}}_{S} (T) = {\dot{λ}}_{I} (T) = - κ_{I} - K_{D} u^{M} (T) < 0

${\dot{λ}}_{I} (T) - {\dot{λ}}_{S} (T) = {\dot{λ}}_{I} (T) = - κ_{I} - K_{D} u^{M} (T) < 0$

. Therefore,

\exists ϵ > 0

$\exists ϵ > 0$

such that on

(T - ϵ \dots T)

$(T - ϵ \dots T)$

we have

λ_{S} > 0

$λ_{S} > 0$

and

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

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

Step 2: Proof by contradiction. Let

τ

$τ$

be such that

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

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

(τ \dots T)

$(τ \dots T)$

and

λ_{S} (τ) = 0

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

λ_{I} (τ) = λ_{S} (τ)

$λ_{I} (τ) = λ_{S} (τ)$

. From the continuity of the costate functions,

(λ_{I} (τ) - λ_{S} (τ)) \geq 0

$(λ_{I} (τ) - λ_{S} (τ)) \geq 0$

and

λ_{S} (τ) \geq 0

$λ_{S} (τ) \geq 0$

We first prove that

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

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

. Suppose not. Then,

λ_{I} (τ) = λ_{S} (τ)

$λ_{I} (τ) = λ_{S} (τ)$

. Thus,

{\dot{λ}}_{I} (τ) - {\dot{λ}}_{S} (τ) =

${\dot{λ}}_{I} (τ) - {\dot{λ}}_{S} (τ) =$

- κ_{I} + λ_{I} β_{2} u^{N_{i}} - (λ_{D} - λ_{I}) u^{M} - λ_{S} β_{1} u^{N_{i}} =

$- κ_{I} + λ_{I} β_{2} u^{N_{i}} - (λ_{D} - λ_{I}) u^{M} - λ_{S} β_{1} u^{N_{i}} =$

- κ_{I} - λ_{S} u^{N_{i}} (β_{1} - β_{2}) - (λ_{D} - λ_{I}) u^{M}

$- κ_{I} - λ_{S} u^{N_{i}} (β_{1} - β_{2}) - (λ_{D} - λ_{I}) u^{M}$

. Here, (i) the first term is strictly negative,⁴ (ii) the second term is negative because

λ_{S} (τ) \geq 0

$λ_{S} (τ) \geq 0$

and

β_{2} \leq β_{1}

$β_{2} \leq β_{1}$

, and (iii) the third term is negative because of (7.10). Thus,

{\dot{λ}}_{I} (τ) - {\dot{λ}}_{S} (τ) > 0

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

. But, then both

λ_{I} (τ) = λ_{S} (τ)

$λ_{I} (τ) = λ_{S} (τ)$

, and

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

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

(τ \dots T)

$(τ \dots T)$

cannot happen. Thus,

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

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

Now, suppose

λ_{S} (τ) = 0

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

{\dot{λ}}_{S} (τ) = - (λ_{I} - λ_{S}) β_{0} u^{N_{r}} I ∣_{τ} < 0

${\dot{λ}}_{S} (τ) = - (λ_{I} - λ_{S}) β_{0} u^{N_{r}} I ∣_{τ} < 0$

. The last inequality follows since

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

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

β_{0} > 0

$β_{0} > 0$

u^{N_{r}} \geq u_{\min}^{N_{r}} > 0

$u^{N_{r}} \geq u_{\min}^{N_{r}} > 0$

and

I (τ) > 0

$I (τ) > 0$

(Lemma 7.1). This again contradicts the assumptions that

λ_{S} (τ) = 0

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

and

λ_{S} > 0

$λ_{S} > 0$

(τ \dots T)

$(τ \dots T)$

. Thus,

λ_{S} (τ) \neq 0

$λ_{S} (τ) \neq 0$

, and hence

λ_{S} (τ) > 0

$λ_{S} (τ) > 0$

. □

Strict monotonicity of $ψ^{N_{r}} (\cdot)$ $ψ^{N_{r}} (\cdot)$

We show that

{\dot{ψ}}^{N_{r}} (t)

${\dot{ψ}}^{N_{r}} (t)$

is strictly negative at all

t \in (0, T)

$t \in (0, T)$

⁵

${\dot{ψ}}^{N_{r}} = \frac{\partial}{\partial t} ψ^{N_{r}} = ({\dot{λ}}_{I} - {\dot{λ}}_{S}) β_{0} I S + (λ_{I} - λ_{S}) β_{0} \dot{I} S + (λ_{I} - λ_{S}) β_{0} I \dot{S}$ ${\dot{ψ}}^{N_{r}} = \frac{\partial}{\partial t} ψ^{N_{r}} = ({\dot{λ}}_{I} - {\dot{λ}}_{S}) β_{0} I S + (λ_{I} - λ_{S}) β_{0} \dot{I} S + (λ_{I} - λ_{S}) β_{0} I \dot{S}$

which after replacement and simplification yields

$\frac{{\dot{ψ}}^{N r}}{β_{0} I S} = - κ_{I} - (λ_{D} - λ_{S}) u^{M} - β_{1} λ_{I} u^{N_{i}} + β_{2} λ_{S} u^{N_{i}}$ $\frac{{\dot{ψ}}^{N r}}{β_{0} I S} = - κ_{I} - (λ_{D} - λ_{S}) u^{M} - β_{1} λ_{I} u^{N_{i}} + β_{2} λ_{S} u^{N_{i}}$

$= - κ_{I} - (λ_{D} - λ_{I}) u^{M} - (λ_{I} - λ_{S}) u^{M} - (β_{1} - β_{2}) λ_{I} u^{N_{i}} - (λ_{I} - λ_{S}) β_{2} u^{N_{i}} .$ $= - κ_{I} - (λ_{D} - λ_{I}) u^{M} - (λ_{I} - λ_{S}) u^{M} - (β_{1} - β_{2}) λ_{I} u^{N_{i}} - (λ_{I} - λ_{S}) β_{2} u^{N_{i}} .$

From (7.10), Lemma 7.2 and since

κ_{I} > 0

$κ_{I} > 0$

β_{1} \geq β_{2}

$β_{1} \geq β_{2}$

u^{M} (t) \geq 0, u^{N_{i}} (t) \geq 0

$u^{M} (t) \geq 0, u^{N_{i}} (t) \geq 0$

at all

t

$t$

, the right-hand side is negative. The result follows since

β_{0} > 0

$β_{0} > 0$

and

S (t) > 0, I (t) > 0

$S (t) > 0, I (t) > 0$

at all

t

$t$

(Lemma 7.1).

Strict monotonicity of $ψ^{N_{i}} (\cdot)$ $ψ^{N_{i}} (\cdot)$

${\dot{ψ}}^{N_{i}} = \frac{\partial}{\partial t} ψ^{N_{i}} = ({\dot{λ}}_{I} - {\dot{λ}}_{S}) β_{0} I S + (λ_{I} - λ_{S}) β_{0} \dot{I} S + (λ_{I} - λ_{S}) β_{0} I \dot{S}$ ${\dot{ψ}}^{N_{i}} = \frac{\partial}{\partial t} ψ^{N_{i}} = ({\dot{λ}}_{I} - {\dot{λ}}_{S}) β_{0} I S + (λ_{I} - λ_{S}) β_{0} \dot{I} S + (λ_{I} - λ_{S}) β_{0} I \dot{S}$

$\Rightarrow \frac{{\dot{ψ}}^{N_{i}}}{β_{0} I} = κ_{I} β_{2} + β_{2} u^{M} λ_{D} + β_{0} β_{1} S u^{N_{r}} (λ_{I} - λ_{S}) .$ $\Rightarrow \frac{{\dot{ψ}}^{N_{i}}}{β_{0} I} = κ_{I} β_{2} + β_{2} u^{M} λ_{D} + β_{0} β_{1} S u^{N_{r}} (λ_{I} - λ_{S}) .$

The R.H.S is positive from Lemma 7.2 and since

κ_{I} > 0, β_{0} > 0

$κ_{I} > 0, β_{0} > 0$

. Thus,

{\dot{ψ}}^{N_{i}} > 0

${\dot{ψ}}^{N_{i}} > 0$

since

β_{0} > 0

$β_{0} > 0$

and

I (t) > 0

$I (t) > 0$

at all

t

$t$

(Lemma 7.1). □

In the next theorem, we show that under a sufficient condition, the quarantining period (by reduction of communication rates) ends before the immunization/healing effort is stopped. This is in accordance with our intuition that the primary use of quarantining is buying time for the recovery process in the network.

Theorem 7.3

Let

t_{1}

$t_{1}$

and

t_{2}

$t_{2}$

be as defined inTheorem 7.2. If

κ_{r} \geq \frac{β_{0} S_{0}}{β_{2}}

$κ_{r} \geq \frac{β_{0} S_{0}}{β_{2}}$

, then either

t_{2} = 0

$t_{2} = 0$

t_{1} < t_{2}

$t_{1} < t_{2}$

Note that the condition of the theorem is quite intuitive. For instance, if

β_{2} = β_{0}

$β_{2} = β_{0}$

, this condition is satisfied when

κ_{r} \geq 1

$κ_{r} \geq 1$

. Recall that the coefficients of the costs were rescaled so that the coefficient of the cost of patching is normalized. Thus, this means when the instantaneous cost of per unit reduction of commutation rates (quarantining) is no less than per unit patching. The other parameters in

κ_{r} \geq \frac{β_{2} S_{0}}{β_{0}}

$κ_{r} \geq \frac{β_{2} S_{0}}{β_{0}}$

refer to the cases of relatively small initial susceptible pool, and a relatively fast healing rate.

Proof

Recall from the proof of Theorem 7.2 that

ψ^{N_{r}} (t)

$ψ^{N_{r}} (t)$

and

ψ^{N_{i}} (t)

$ψ^{N_{i}} (t)$

each have at most one zero-crossing point and

ψ^{N_{r}} (t)

$ψ^{N_{r}} (t)$

terminates in a negative, and

ψ^{N_{i}} (t)

$ψ^{N_{i}} (t)$

terminates in a positive value at

T

$T$

. Now we show that at a potential zero-crossing point of

ψ^{N_{r}} (t)

$ψ^{N_{r}} (t)$

ψ^{N_{i}} (t)

$ψ^{N_{i}} (t)$

is strictly negative.

$ψ^{N_{r}} = (λ_{I} - λ_{S}) β_{0} I S - κ_{r} = 0 \Rightarrow λ_{I} = \frac{κ_{r}}{β_{0} I S} + λ_{S}, then,$ $ψ^{N_{r}} = (λ_{I} - λ_{S}) β_{0} I S - κ_{r} = 0 \Rightarrow λ_{I} = \frac{κ_{r}}{β_{0} I S} + λ_{S}, then,$

$ψ^{N_{i}} = R_{0} - λ_{S} β_{1} R_{0} S - λ_{I} β_{2} R_{0} I = R_{0} - λ_{S} β_{1} R_{0} S - β_{2} R_{0} I (\frac{κ_{r}}{β_{0} I S} + λ_{S}) = R_{0} (1 - \frac{β_{2}}{β_{0}} \frac{κ_{r}}{S}) - λ_{S} β_{1} R_{0} S - λ_{S} β_{2} R_{0} I .$ $ψ^{N_{i}} = R_{0} - λ_{S} β_{1} R_{0} S - λ_{I} β_{2} R_{0} I = R_{0} - λ_{S} β_{1} R_{0} S - β_{2} R_{0} I (\frac{κ_{r}}{β_{0} I S} + λ_{S}) = R_{0} (1 - \frac{β_{2}}{β_{0}} \frac{κ_{r}}{S}) - λ_{S} β_{1} R_{0} S - λ_{S} β_{2} R_{0} I .$

According to Lemmas 7.1 and 7.2, the last two terms are strictly negative. The first term is negative following the condition of the theorem (i.e.

κ_{r} \geq \frac{β_{2} S_{0}}{β_{0}}

$κ_{r} \geq \frac{β_{2} S_{0}}{β_{0}}$

) and the fact that

S

$S$

is a nonincreasing function of time. Similarly, one can show that given

κ_{r} \geq \frac{β_{2} S_{0}}{β_{0}}

$κ_{r} \geq \frac{β_{2} S_{0}}{β_{0}}$

, then at a potential zero-crossing point of

ψ^{N_{i}} (t)

$ψ^{N_{i}} (t)$

ψ^{N_{r}} (t) > 0

$ψ^{N_{r}} (t) > 0$

. The theorem follows from the continuity of

ψ^{N_{i}} (t)

$ψ^{N_{i}} (t)$

and

ψ^{N_{r}} (t)

$ψ^{N_{r}} (t)$

and by referring to (7.8) and (7.9). □

Note that the case of

t_{2} = 0

$t_{2} = 0$

occurs when

ψ^{N_{i}}

$ψ^{N_{i}}$

does not have a zero-crossing point and is hence non-negative throughout

[0, T]

$[0, T]$

. In this case, the immunization/healing effort is never launched.

7.3.4. Structure of the Saddle-point Attack Strategy

The saddle-point attack has a simple first-amass, then slaughter structure in the special case that the worm benefits from killing only through the final tally of the dead (i.e.

κ_{D} = 0

$κ_{D} = 0$

), and the patches can only immunize the susceptibles, but cannot heal the infectives (i.e.

β_{2} = 0

$β_{2} = 0$

). Specifically, we have the following.

Theorem 7.4

When

β_{2} = κ_{D} = 0

$β_{2} = κ_{D} = 0$

, for the saddle-point attack strategy

u^{M} (\cdot)

$u^{M} (\cdot)$

, there exists a time

t_{3}

$t_{3}$

0 \leq t_{3} < T

$0 \leq t_{3} < T$

such that

u^{M} (t) = 0

$u^{M} (t) = 0$

for

0 < t < t_{3}

$0 < t < t_{3}$

, and

u^{M} (t) = u_{\max}^{M}

$u^{M} (t) = u_{\max}^{M}$

for

t_{3} < t < T

$t_{3} < t < T$

Thus, the worm does not kill any infective during the initial amass period of

(0, t_{1})

$(0, t_{1})$

when it uses them to spread the infection; it slaughters them at the maximum rate subsequently. The intuition behind this structure is as follows. Once the worm infects a host, it never loses it to the recovery process, and thus, since it benefits from killing a host only because this enhances the final tally of the dead, it ought to kill hosts toward the end and utilize them before. The proof follows.

Proof

Note that

ψ^{M} (T) = K_{I} I (T) > 0

$ψ^{M} (T) = K_{I} I (T) > 0$

(because of Lemma 7.1). Thus, as in the proof of Theorem 7.2, the result follows if we can show that

ψ^{M} (t)

$ψ^{M} (t)$

crosses zero at most once. We establish this slightly differently: we show that

{\dot{ψ}}^{M}

${\dot{ψ}}^{M}$

is strictly positive at its zero-crossing point (as opposed to showing it for all

t

$t$

). But this is also sufficient to conclude

ψ^{M}

$ψ^{M}$

has at most one zero-crossing point,

$\begin{matrix} {\dot{ψ}}^{M} & = I ({\dot{λ}}_{D} - {\dot{λ}}_{I}) + \dot{I} ψ^{M} \\ = κ_{I} - κ_{D} + u^{M} (λ_{D} - λ_{I}) - β_{2} λ_{I} u^{N_{i}} + S β_{0} u^{N_{r}} (λ_{I} - λ_{S}) + \dot{I} ψ^{M} . \end{matrix}$ $\begin{matrix} {\dot{ψ}}^{M} & = I ({\dot{λ}}_{D} - {\dot{λ}}_{I}) + \dot{I} ψ^{M} \\ = κ_{I} - κ_{D} + u^{M} (λ_{D} - λ_{I}) - β_{2} λ_{I} u^{N_{i}} + S β_{0} u^{N_{r}} (λ_{I} - λ_{S}) + \dot{I} ψ^{M} . \end{matrix}$

At a zero-crossing point of

ψ^{M}

$ψ^{M}$

, the last term vanishes. Also,

κ_{D} = β_{2} = 0

$κ_{D} = β_{2} = 0$

. The third and fifth terms are non-negative because of (7.10) and Lemma 7.2, respectively. The result now follows since

κ_{I} > 0

$κ_{I} > 0$

. □

The saddle-point attack strategy may however be more involved when either

β_{2} > 0

$β_{2} > 0$

κ_{D} > 0

$κ_{D} > 0$

. For example, Fig. 7.2 depicts the saddle-point strategies and the state evolution in an example scenario where

κ_{D} = 13, β_{2} = 4.47

$κ_{D} = 13, β_{2} = 4.47$

. The malware starts killing the nodes from the beginning, but then it stops the killing and infects the newly accessible susceptible nodes, boosting the fraction of the infective and toward the end, starts to kill them all again.