# Seeking Best-Balanced Patch-Injecting Strategies through Optimal Control Approach

Authors: Kaifan Huang; Pengdeng Li; Lu-Xing Yang; Xiaofan Yang; Yuan Yan Tang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

To restrain escalating computer viruses, new virus patches must be constantly injected into networks. In this scenario, the patch-developing cost should be balanced against the negative impact of virus. This article focuses on seeking best-balanced patch-injecting strategies. First, based on a novel virus-patch interactive model, the original problem is reduced to an optimal control problem, in which (a) each admissible control stands for a feasible patch-injecting strategy and (b) the objective functional measures the balance of a feasible patch-injecting strategy. Second, the solvability of the optimal control problem is proved, and the optimality system for solving the problem is derived. Next, a few best-balanced patch-injecting strategies are presented by solving the corresponding optimality systems. Finally, the effects of some factors on the best balance of a patch-injecting strategy are examined. Our results will be helpful in defending against virus attacks in a cost-effective way.


---

## Body

## 1. Introduction

Computer networks bring huge convenience to our work and life [1, 2]. Meanwhile, digital viruses can propagate rapidly through computer networks, posing a severe threat to human society. For example, Wanna Decryptor, the notorious ransomware, has recently swept across the globe, leading to massive computer paralysis [3]. Consequently, the problem of how to mitigate the negative impact of computer virus in a cost-effective way has long been a hotspot of research in the field of cyber security [4].To restrain evolving computer viruses, new virus patches must be constantly injected into networks. In this scenario, there is an obvious conflict between the patch-developing cost and the impact of virus; reducing the former would increase the latter, whereas mitigating the latter would enhance the former. Therefore, the patch-developing cost should be balanced against the impact of virus. We refer to a dynamic patch-injecting strategy that achieves the best balance between the two aspects as a best-balanced patch-injecting strategy, and we refer to the problem of seeking best-balanced patch-injecting strategies as thevirus-patch tradeoff (VPT) problem. Solving the VPT problem would be helpful in defending against virus attacks in a cost-effective way.This article addresses the VPT problem. First, based on a novel virus-patch interactive model, the original problem is reduced to an optimal control problem which we refer to as the VPT control problem, in which (a) each admissible control stands for a feasible patch-injecting strategy and (b) the objective functional measures the balance of a feasible patch-injecting strategy. Second, the solvability of the VPT control problem is shown, and the optimality system for solving the VPT control problem is derived. Next, a few best-balanced patch-injecting strategies are given by solving the corresponding optimality systems. Finally, the effects of some factors on the best balance of a patch-injecting strategy are examined.The remaining materials are organized in this fashion: Section2 reviews the related work. Sections 3 and 4 establish and solve the VPT control problem, respectively. Section 5 illustrates how to solve the VPT control problem, and Section 6 examines the effects of some factors on the best balance. This work is summarized by Section 7.


## 2. Related Work

In order to solve the VPT problem, the expected total loss of all network users resulting from a patch-injecting strategy must be estimated [5, 6]. As this quantity relies on the expected network states at all times, we need to characterize the evolutionary process of the expected network state. The resulting evolutionary model is essentially a propagation model that captures the interactive propagation of viruses and patches [7, 8]. In the available literature, propagation models of this kind are referred to as Susceptible-Infected-Patched-Susceptible (SIPS) models.Compartmental propagation models are propagation models in which all nodes of the same state are classified as a class, with the goal of understanding the evolutionary trend of the size or fraction of each class [9]. Compartmental models are suited to capturing propagation phenomena occurring on homogeneously mixed networks but fail to characterize propagation phenomena occurring on highly heterogeneous networks. The compartmental SIPS models proposed in [10–13] take patch forwarding into account but leave patch injection out of consideration. Very recently, [14] proposed a compartmental SIPS model with static patch-injecting mechanism and thereby assessed the effectiveness of patch injection.Node-level propagation models are propagation models in which each node is regarded as a separate class, with the goal of gaining insight into the evolutionary trend of the expected network state [15, 16]. One striking advantage of node-level propagation models is that they can accurately characterize propagation phenomena occurring on arbitrary networks. With the progress of wireless and mobile communication technologies, most existing computer networks admit an irregular topology [17–19]. As a result, a number of node-level computer virus propagation models have been advised [20–25]. In particular, [26] introduced a node-level SIPS model with no patch injection. Recently, [27] proposed a node-level SIPS model with dynamic patch-injecting mechanism and thereby addressed a problem that is something like the VPT problem through differential game approach. In our opinion, this work has two weaknesses: (i) It is assumed that the network defender is aware of the total attack budget of all relevant cyber malefactors. However, in practice the budget is usually unknown to the defender. (ii) It is assumed that new patches can be injected into any network node. Due to the limited network bandwidth, in practice new patches are typically injected into a small subset of nodes and then forwarded to the unpatched nodes [28].Optimal control theory [29, 30] provides a powerful tool for studying the problem of how to contain the prevalence of computer virus in a cost-effective way [31–35]. In view of the defects of the research approach used in [27], in this paper we deal with the VPT problem through optimal control approach. For this purpose, we propose a novel node-level SIPS model with dynamic patch-injecting mechanism, where new patches can be injected into only a small subset of nodes. Thereby, we accurately estimate the expected total loss of all network users. On this basis, we reduce the VPT problem to an optimal control problem and then solve the problem by means of optimal control theory. Our optimal control model is promising, because, by collecting and analyzing the relevant actual data, the model parameters can be estimated quite accurately.


## 3. The Modeling of the VPT Problem

This section is devoted to the modeling of the VPT problem. First, we introduce basic terms and notations. Second, we establish a node-level SIPS model. Finally, we model the VPT problem as an optimal control problem.


### 3.1. Terms and Notations

Consider a computer network withN nodes labeled v1 through vN. Let G=(V,E) denote the topology of the network, i.e., V={v1,v2,…,vN}, and each edge stands for a communication link between the two endpoints. Let A=aijN×N denote the adjacency matrix of G, i.e, aij=1 or 0 according as {vi,vj}∈E or not. Suppose new computer viruses can be injected into any node of the network and can propagate over the network, and suppose new virus patches can be injected into only the node subset U={v1,v2,…,vM} of the network and can be forwarded to other nodes through the network.Consider the finite time horizon[0,T]. Assume each and every node of the network is in one of three possible states:susceptible,infected, andpatched. Susceptible nodes are nodes that are not infected with any virus but have not received the newest patch. This implies these nodes are vulnerable to new viruses. Infected nodes are nodes that are infected with some virus. Patched nodes are nodes that are not infected with any virus and have received the newest patch. This implies that these nodes possess temporary immunity to new viruses. Let Xi(t)=0, 1, and 2 denote that the node vi is susceptible, infected, and patched at time t, respectively. Then the state of the network at time t can be characterized by the vector(1)Xt=X1t,…,XNt.Let Si(t), Ii(t), and Pi(t) denote the probabilities of the node vi being susceptible, infected, and patched at time t, respectively.(2)Sit=PrXit=0,Iit=PrXit=1,Pit=PrXit=2.Since Si(t)=1-Ii(t)-Pi(t), the expected state of the network at time t can be characterized by the vector(3)Et=I1t,…,INt,P1t,…,PNt.


### 3.2. A Virus-Patch Interactive Model

In order to establish a virus-patch interactive model, we introduce a set of assumptions as follows.(A1)
Due to virus injection, each susceptible node gets infected at the average rateβI which we refer to as thevirus injection rate.(A2)
Due to virus propagation, the susceptible nodevi gets infected at time t at the average rate βP∑j=1NaijIj(t), where βP is a constant which we refer to as thevirus propagation rate.(A3)
Due to patch injection, each unpatched node inU gets patched at time t at the average rate γI(t) which we refer to as thepatch injection rate at time t.(A4)
Due to patch forwarding, the unpatched nodevi∈V-U gets patched at time t at the average rate γP∑j=1NaijPj(t), where γP is a constant which we refer to as thepatch forwarding rate.(A5)
Due to appearance of new viruses, each patched node becomes susceptible at the average rateδ which we refer to as thepatch failure rate.Remark 1.
The virus injection rate, the virus propagation rate, the patch forwarding rate, and the patch failure rate can be estimated accurately by collecting and analyzing the relevant historical data. All patch injection rates are under control of the network defender.Figure1 shows the above assumptions schematically.Figure 1
Diagram of the assumptions (A1)-(A5).
(a)
v i ∈ U (b)
v i ∈ V - UBased on the above assumptions, the expected network state evolves over time according to the following differential dynamical system:(4)dIitdt=βI+βP∑j=1NaijIjt1-Iit-Pit-γItIit,0≤t≤T,vi∈U,dPitdt=γIt1-Pit-δPit,0≤t≤T,vi∈U,dIitdt=βI+βP∑j=1NaijIjt1-Iit-Pit-γPIit∑j=1NaijPjt,0≤t≤T,vi∈V-U,dPitdt=γP1-Pit∑j=1NaijPjt-δPit,0≤t≤T,vi∈V-U,E0=E0. This is a novel SIPS model, which can be written in matrix-vector notation as(5)dEtdt=FEt,γIt,0≤t≤T,E0=E0.


### 3.3. The Modeling of the VPT Problem

The functionγI defined by γI(t), t∈[0,T], is under control of the network defender. We refer to the function as apatch-injecting strategy. Let L[0,T] denote the set of all Lebesgue integrable functions defined on the interval [0,T] [36]. Henceforth, we assume the set of all allowable patch-injecting strategies is(6)Γ=γI∈L0,T∣γI_≤γIt≤γI¯,0≤t≤T. We refer to γI_ as theminimum allowable patch injection rate,γI¯ as themaximum allowable patch injection rate.LetC(t) denote the cost per unit time at time t for patch developing. Obviously, C(t) is increasing with γI(t). In this paper we simply assume that C(t) is linearly proportional to γI(t). That is, C(t)=cγI(t), where c is a constant which we refer to as thecost coefficient. As a result, the total patch-developing cost is ∫0TcγI(t)dt units.Remark 2.
In practice,C(t) may be dependent on γI(t) in a more complex way. For example, C(t) may be proportional to the square of γI(t). That is, C(t)=cγI2(t), where c is a constant. If this is the case, the total patch-developing cost would be ∫0TcγI2(t)dt units. The exact form in which C(t) depends on γI(t) is yet to be determined through analysis of massive actual data. Nevertheless, our research approach can easily be applied to any other dependence relationship.On the other hand, we assume that the average loss per unit time caused by the infected nodevi is wi unit. Then, the expected total loss of all network users is ∫0T∑i=1NwiIi(t)dt units. Let w=(w1,…,wN). Therefore, we get a measure of the balance of a patch-injecting strategy γI as follows.(7)JγI=∫0TcγItdt+∫0T∑i=1NwiIitdt.By combining the above discussions, the VPT problem is reduced to the following optimal control problem:(8)MinimizeγI∈ΓJγI=∫0TcγItdt+∫0T∑i=1NwiIitdtsubjecttodEtdt=FEt,γIt,0≤t≤T,E0=E0.We refer to the optimal control problem as theVPT control problem. In this problem, each admissible control stands for a feasible patch-injecting strategy, and the objective functional measures the balance of a feasible patch-injecting strategy. Each instance of the VPT control problem is given by the 11-tuple(9)M=G∣U,βI,βP,γP,δ,γI_,γI¯,c,w,T,E0.


## 3.1. Terms and Notations

Consider a computer network withN nodes labeled v1 through vN. Let G=(V,E) denote the topology of the network, i.e., V={v1,v2,…,vN}, and each edge stands for a communication link between the two endpoints. Let A=aijN×N denote the adjacency matrix of G, i.e, aij=1 or 0 according as {vi,vj}∈E or not. Suppose new computer viruses can be injected into any node of the network and can propagate over the network, and suppose new virus patches can be injected into only the node subset U={v1,v2,…,vM} of the network and can be forwarded to other nodes through the network.Consider the finite time horizon[0,T]. Assume each and every node of the network is in one of three possible states:susceptible,infected, andpatched. Susceptible nodes are nodes that are not infected with any virus but have not received the newest patch. This implies these nodes are vulnerable to new viruses. Infected nodes are nodes that are infected with some virus. Patched nodes are nodes that are not infected with any virus and have received the newest patch. This implies that these nodes possess temporary immunity to new viruses. Let Xi(t)=0, 1, and 2 denote that the node vi is susceptible, infected, and patched at time t, respectively. Then the state of the network at time t can be characterized by the vector(1)Xt=X1t,…,XNt.Let Si(t), Ii(t), and Pi(t) denote the probabilities of the node vi being susceptible, infected, and patched at time t, respectively.(2)Sit=PrXit=0,Iit=PrXit=1,Pit=PrXit=2.Since Si(t)=1-Ii(t)-Pi(t), the expected state of the network at time t can be characterized by the vector(3)Et=I1t,…,INt,P1t,…,PNt.


## 3.2. A Virus-Patch Interactive Model

In order to establish a virus-patch interactive model, we introduce a set of assumptions as follows.(A1)
Due to virus injection, each susceptible node gets infected at the average rateβI which we refer to as thevirus injection rate.(A2)
Due to virus propagation, the susceptible nodevi gets infected at time t at the average rate βP∑j=1NaijIj(t), where βP is a constant which we refer to as thevirus propagation rate.(A3)
Due to patch injection, each unpatched node inU gets patched at time t at the average rate γI(t) which we refer to as thepatch injection rate at time t.(A4)
Due to patch forwarding, the unpatched nodevi∈V-U gets patched at time t at the average rate γP∑j=1NaijPj(t), where γP is a constant which we refer to as thepatch forwarding rate.(A5)
Due to appearance of new viruses, each patched node becomes susceptible at the average rateδ which we refer to as thepatch failure rate.Remark 1.
The virus injection rate, the virus propagation rate, the patch forwarding rate, and the patch failure rate can be estimated accurately by collecting and analyzing the relevant historical data. All patch injection rates are under control of the network defender.Figure1 shows the above assumptions schematically.Figure 1
Diagram of the assumptions (A1)-(A5).
(a)
v i ∈ U (b)
v i ∈ V - UBased on the above assumptions, the expected network state evolves over time according to the following differential dynamical system:(4)dIitdt=βI+βP∑j=1NaijIjt1-Iit-Pit-γItIit,0≤t≤T,vi∈U,dPitdt=γIt1-Pit-δPit,0≤t≤T,vi∈U,dIitdt=βI+βP∑j=1NaijIjt1-Iit-Pit-γPIit∑j=1NaijPjt,0≤t≤T,vi∈V-U,dPitdt=γP1-Pit∑j=1NaijPjt-δPit,0≤t≤T,vi∈V-U,E0=E0. This is a novel SIPS model, which can be written in matrix-vector notation as(5)dEtdt=FEt,γIt,0≤t≤T,E0=E0.


## 3.3. The Modeling of the VPT Problem

The functionγI defined by γI(t), t∈[0,T], is under control of the network defender. We refer to the function as apatch-injecting strategy. Let L[0,T] denote the set of all Lebesgue integrable functions defined on the interval [0,T] [36]. Henceforth, we assume the set of all allowable patch-injecting strategies is(6)Γ=γI∈L0,T∣γI_≤γIt≤γI¯,0≤t≤T. We refer to γI_ as theminimum allowable patch injection rate,γI¯ as themaximum allowable patch injection rate.LetC(t) denote the cost per unit time at time t for patch developing. Obviously, C(t) is increasing with γI(t). In this paper we simply assume that C(t) is linearly proportional to γI(t). That is, C(t)=cγI(t), where c is a constant which we refer to as thecost coefficient. As a result, the total patch-developing cost is ∫0TcγI(t)dt units.Remark 2.
In practice,C(t) may be dependent on γI(t) in a more complex way. For example, C(t) may be proportional to the square of γI(t). That is, C(t)=cγI2(t), where c is a constant. If this is the case, the total patch-developing cost would be ∫0TcγI2(t)dt units. The exact form in which C(t) depends on γI(t) is yet to be determined through analysis of massive actual data. Nevertheless, our research approach can easily be applied to any other dependence relationship.On the other hand, we assume that the average loss per unit time caused by the infected nodevi is wi unit. Then, the expected total loss of all network users is ∫0T∑i=1NwiIi(t)dt units. Let w=(w1,…,wN). Therefore, we get a measure of the balance of a patch-injecting strategy γI as follows.(7)JγI=∫0TcγItdt+∫0T∑i=1NwiIitdt.By combining the above discussions, the VPT problem is reduced to the following optimal control problem:(8)MinimizeγI∈ΓJγI=∫0TcγItdt+∫0T∑i=1NwiIitdtsubjecttodEtdt=FEt,γIt,0≤t≤T,E0=E0.We refer to the optimal control problem as theVPT control problem. In this problem, each admissible control stands for a feasible patch-injecting strategy, and the objective functional measures the balance of a feasible patch-injecting strategy. Each instance of the VPT control problem is given by the 11-tuple(9)M=G∣U,βI,βP,γP,δ,γI_,γI¯,c,w,T,E0.


## 4. Theoretical Study of the VPT Control Problem

This section is dedicated to the theoretical study of the VPT control problem. First, we show that the problem is solvable. Second, we present a method for solving this problem.


### 4.1. Solvability

LetL(E,γ)=cγI+∑i=1N‍wiIi. We have the following lemma [30].Lemma 3.
The VPT game problem (8) admits an optimal control if the following five conditions are met.(C1)
Γ is closed and convex.(C2)
There isγI∈Γ such that the differential system dE(t)/dt=F(E(t),γI(t))(0≤t≤T) is solvable.(C3)
F(E,γI) is bounded by a linear function in E.(C4)
L(E,γI) is concave on Γ.(C5)
L(E,γI)≥c1γIρ+c2 for some ρ>1, c1>0 and c2.The solvability of the VPT control problem is guaranteed by the following theorem.Theorem 4.
The VPT control problem (8) admits an optimal control.Proof.
(a) LetγI be a limit point of Γ. Then there is a sequence of points in Γ, denoted γI(1),γI(2),…, that approaches γI. As L[0,T] is complete [36], we get that γI∈L[0,T]. As γI_≤γI=limn→∞γI(n)≤γI¯, we get that γI∈Γ. So, Γ is closed. (b) Let γI(1),γI(2)∈Γ, 0<α<1. γI=αγI(1)+(1-α)γI(2). As L[0,T] is a real vector space [36], we have γI∈L[0,T]. As γI_≤γI≤γI¯, we get that γI∈Γ. So, Γ is convex. (c) As F(E,γI¯) is continuously differentiable, it follows from Continuation Theorem for Differential Systems [37] that the differential system dE(t)/dt=F(E(t),γI¯)(0≤t≤T) is solvable. (d) Obviously, for vi∈U,(10)-γI¯Ii≤βI+βP∑j=1NaijIj1-Ii-Pi-γIIi≤βI+βP∑j=1NaijIj,-δPi≤γI1-Pi-δPi≤γI¯-δPi, for vi∈V-U,(11)-γP∑j=1NaijPj≤βI+βP∑j=1NaijIj1-Ii-Pi-γPIi∑j=1NaijPj≤βI+βP∑j=1NaijIj,-δPi≤γP1-Pi∑j=1NaijPj-δPi≤γP∑j=1NaijPj. (e) Let γI(1),γI(2)∈Γ, 0<α<1. As(12)LE,αγI1+1-αγI2=αLE,γI1+1-αLE,γI2, we get that L(E,γI) is convex with respect to γI. (f) Obviously, L(E,γI)≥cγI≥c/γI¯γI2. Hence, the five conditions in Lemma 3 are met. By Lemma 3, the VPT control problem admits an optimal control.
This theorem implies that the VPT problem admits a best-balanced patch-injecting strategy.


### 4.2. The Optimality System

According to optimal control theory [29], when the solvability of an optimal control problem is guaranteed, we may solve the problem by solving the optimality system associated with the problem. Now, let us derive the optimality system associated with the VPT control problem (8). The associated Hamiltonian is(13)HE,γI,p=cγI+∑i=1NwiIi+∑i=1MμiγI1-Pi-δPi+∑i=M+1NμiγP1-Pi∑j=1NaijPj-δPi+∑i=1MλiβI+βP∑j=1NaijIj1-Ii-Pi-γIIi+∑i=M+1NλiβI+βP∑j=1NaijIj1-Ii-Pi-γPIi∑j=1NaijPj,where p=p(t)=(λ1(t),…,λN(t),μ1(t),…,μN(t))(0≤t≤T) is the adjoint.The following result is a necessary condition for the optimal control of the VPT control problem.Theorem 5.
SupposeγI is an optimal control for the VPT control problem (8). Let E be the solution to the differential system (5). Then there exists p with p(T)=0 such that(14)dλitdt=-wi+λitβI+βP∑j=1NaijIjt+γIt-βP∑j=1Naijλjt1-Ijt-Pjt,0≤t≤T,vi∈U,dλitdt=-wi+λitβI+βP∑j=1NaijIjt+γP∑j=1NaijPjt-βP∑j=1Naijλjt1-Ijt-Pjt,0≤t≤T,vi∈V-U,dμitdt=μitδ+γIt+λitβI+βP∑j=1NaijIjt+γP∑j=M+1NaijIjtλjt+1-Pjtμjt,0≤t≤T,vi∈U,dμitdt=μitδ+γP∑j=1NaijPjt+λitβI+βP∑j=1NaijIjt+γP∑j=M+1NaijIjtλjt+1-Pjtμjt,0≤t≤T,vi∈V-U,γIt=γI_ifc+∑i=1Mμit1-Pit>∑i=1MIitλit,γI¯ifc+∑i=1Mμit1-Pit<∑i=1MIitλit,0≤t≤T.Proof.
According to Pontryagin Minimum Principle [29], there exists p such that(15)dλitdt=-∂HEt,γIt,pt∂Ii,dμitdt=-∂HEt,γIt,pt∂Pi,t∈0,T,1≤i≤N. Thus, the first 2N equations in the system (14) follow by direct calculations. As the terminal cost is unspecified and the final state is free, the transversality condition p(T)=0 holds true. Again by Pontryagin Minimum Principle, we have(16)γIt∈arg⁡minγI∗∈Γ⁡HEt,γI∗t,pt,0≤t≤T. The last equation in the system (14) follows by direct calculations.
The optimality system associated with the VPT control problem (8) consists of the system (5), the system (14), and p(T)=0. In practice, we may apply the well-known Forward-Backward Euler Scheme [38] to solve the optimality system.


## 4.1. Solvability

LetL(E,γ)=cγI+∑i=1N‍wiIi. We have the following lemma [30].Lemma 3.
The VPT game problem (8) admits an optimal control if the following five conditions are met.(C1)
Γ is closed and convex.(C2)
There isγI∈Γ such that the differential system dE(t)/dt=F(E(t),γI(t))(0≤t≤T) is solvable.(C3)
F(E,γI) is bounded by a linear function in E.(C4)
L(E,γI) is concave on Γ.(C5)
L(E,γI)≥c1γIρ+c2 for some ρ>1, c1>0 and c2.The solvability of the VPT control problem is guaranteed by the following theorem.Theorem 4.
The VPT control problem (8) admits an optimal control.Proof.
(a) LetγI be a limit point of Γ. Then there is a sequence of points in Γ, denoted γI(1),γI(2),…, that approaches γI. As L[0,T] is complete [36], we get that γI∈L[0,T]. As γI_≤γI=limn→∞γI(n)≤γI¯, we get that γI∈Γ. So, Γ is closed. (b) Let γI(1),γI(2)∈Γ, 0<α<1. γI=αγI(1)+(1-α)γI(2). As L[0,T] is a real vector space [36], we have γI∈L[0,T]. As γI_≤γI≤γI¯, we get that γI∈Γ. So, Γ is convex. (c) As F(E,γI¯) is continuously differentiable, it follows from Continuation Theorem for Differential Systems [37] that the differential system dE(t)/dt=F(E(t),γI¯)(0≤t≤T) is solvable. (d) Obviously, for vi∈U,(10)-γI¯Ii≤βI+βP∑j=1NaijIj1-Ii-Pi-γIIi≤βI+βP∑j=1NaijIj,-δPi≤γI1-Pi-δPi≤γI¯-δPi, for vi∈V-U,(11)-γP∑j=1NaijPj≤βI+βP∑j=1NaijIj1-Ii-Pi-γPIi∑j=1NaijPj≤βI+βP∑j=1NaijIj,-δPi≤γP1-Pi∑j=1NaijPj-δPi≤γP∑j=1NaijPj. (e) Let γI(1),γI(2)∈Γ, 0<α<1. As(12)LE,αγI1+1-αγI2=αLE,γI1+1-αLE,γI2, we get that L(E,γI) is convex with respect to γI. (f) Obviously, L(E,γI)≥cγI≥c/γI¯γI2. Hence, the five conditions in Lemma 3 are met. By Lemma 3, the VPT control problem admits an optimal control.
This theorem implies that the VPT problem admits a best-balanced patch-injecting strategy.


## 4.2. The Optimality System

According to optimal control theory [29], when the solvability of an optimal control problem is guaranteed, we may solve the problem by solving the optimality system associated with the problem. Now, let us derive the optimality system associated with the VPT control problem (8). The associated Hamiltonian is(13)HE,γI,p=cγI+∑i=1NwiIi+∑i=1MμiγI1-Pi-δPi+∑i=M+1NμiγP1-Pi∑j=1NaijPj-δPi+∑i=1MλiβI+βP∑j=1NaijIj1-Ii-Pi-γIIi+∑i=M+1NλiβI+βP∑j=1NaijIj1-Ii-Pi-γPIi∑j=1NaijPj,where p=p(t)=(λ1(t),…,λN(t),μ1(t),…,μN(t))(0≤t≤T) is the adjoint.The following result is a necessary condition for the optimal control of the VPT control problem.Theorem 5.
SupposeγI is an optimal control for the VPT control problem (8). Let E be the solution to the differential system (5). Then there exists p with p(T)=0 such that(14)dλitdt=-wi+λitβI+βP∑j=1NaijIjt+γIt-βP∑j=1Naijλjt1-Ijt-Pjt,0≤t≤T,vi∈U,dλitdt=-wi+λitβI+βP∑j=1NaijIjt+γP∑j=1NaijPjt-βP∑j=1Naijλjt1-Ijt-Pjt,0≤t≤T,vi∈V-U,dμitdt=μitδ+γIt+λitβI+βP∑j=1NaijIjt+γP∑j=M+1NaijIjtλjt+1-Pjtμjt,0≤t≤T,vi∈U,dμitdt=μitδ+γP∑j=1NaijPjt+λitβI+βP∑j=1NaijIjt+γP∑j=M+1NaijIjtλjt+1-Pjtμjt,0≤t≤T,vi∈V-U,γIt=γI_ifc+∑i=1Mμit1-Pit>∑i=1MIitλit,γI¯ifc+∑i=1Mμit1-Pit<∑i=1MIitλit,0≤t≤T.Proof.
According to Pontryagin Minimum Principle [29], there exists p such that(15)dλitdt=-∂HEt,γIt,pt∂Ii,dμitdt=-∂HEt,γIt,pt∂Pi,t∈0,T,1≤i≤N. Thus, the first 2N equations in the system (14) follow by direct calculations. As the terminal cost is unspecified and the final state is free, the transversality condition p(T)=0 holds true. Again by Pontryagin Minimum Principle, we have(16)γIt∈arg⁡minγI∗∈Γ⁡HEt,γI∗t,pt,0≤t≤T. The last equation in the system (14) follows by direct calculations.
The optimality system associated with the VPT control problem (8) consists of the system (5), the system (14), and p(T)=0. In practice, we may apply the well-known Forward-Backward Euler Scheme [38] to solve the optimality system.


## 5. Examples of Best-Balanced Patch-Injecting Strategy

In this section, we present a few best-balanced patch-injecting strategies by solving the corresponding instances of the VPT control problem. For comparative purpose, for the VPT control problem (8) and the admissible control γI, we define the cumulative balance function as(17)JγI,t=∫0tcγIsds+∫0t∑i=1NwiIisds,0≤t≤T.Obviously, J(γI,T)=J(γI). For convenience, let 1 denote an all-one row vector with appropriate number of dimensions.Small-world networks are networks with small diameter and high clustering coefficient [39]. By invoking Pajek [40], the well-known social network analysis software, we get a synthetic small-world network GSW, which is plotted in Figure 2, where the patch injection subset USW consists of the red nodes.Figure 2
A synthetic small-world networkGSW, where USW consists of the red nodes.Example 1.
Consider the following instance of the VPT control problem:(18)GSW∣USW,0.1,0.4,0.4,0.1,0.2,0.8,1,1,20,0.1×1. By solving the corresponding optimality system, we get an optimal control, which is depicted in Figure 3(a). Figure 3(b) plots the cumulative balance functions for the optimal control and three static controls, from which it is seen that the optimal control is superior to these static controls in terms of the balance.Figure 3
Results in Example1: (a) an optimal control; (b) a comparison between the optimal control and three static controls.
(a) (b)Scale-free networks are networks with power-law degree distribution [41]. Again by invoking Pajek, we get a synthetic scale-free network GSF, which is portrayed in Figure 4, where the patch injection subset USF consists of the red nodes.Figure 4
A synthetic scale-free networkGSF, where USF consists of the red nodes.Example 2.
Consider the following instance of the VPT control problem:(19)GSF∣USF,0.1,0.4,0.4,0.1,0.2,0.8,1,1,20,0.1×1. By solving the corresponding optimality system, we get an optimal control, which is exhibited in Figure 5(a). Figure 5(b) plots the cumulative balance functions for the optimal control and three static controls, from which it is seen that the optimal control outperforms these static controls in terms of the balance.Figure 5
Results in Example2: (a) an optimal control; (b) a comparison between the optimal control and three static controls.
(a) (b)Figure6 exhibits a real-world email network GEM, which comes from [42]. Here, the patch injection subset UEM consists of the red nodes.Figure 6
An email networkGEM, where UEM consists of the red nodes.Example 3.
Consider the following instance of the VPT control problem:(20)GEM∣UEM,0.1,0.4,0.4,0.1,0.2,0.8,1,1,20,0.1×1. By solving the corresponding optimality system, we get an optimal control, which is shown in Figure 7(a). Figure 7(b) plots the cumulative balance functions for the optimal control and three static controls, from which it is seen that the optimal control overmatches these static controls in terms of the balance.Figure 7
Results in Example3: (a) an optimal control; (b) a comparison between the optimal control and three static controls.
(a) (b)We conclude from the above examples that a best-balanced patch-injecting strategy first stays at the maximum allowable patch injection rate, then sharply jumps to the minimum allowable patch injection rate, and finally stays at this rate.


## 6. Further Discussions

In this section, we examine the effects of some factors on the best balance of a patch-injecting strategy. For convenience, letγIopt denote a best-balanced patch-injecting strategy, Jopt=J(γIopt) the corresponding balance.


### 6.1. The Effects of the Four Rates

First, we inspect the effect of the four rates,βI, βP, γP, and δ, on the best balance.Experiment 6.
Consider the following instances of the VPT control problem:(21)G∣U,βI,0.4,0.4,0.1,0.2,0.8,1,1,20,0.1×1,where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, βI∈{0.1,0.2,…,0.9}. Figure 8 exhibits the best balances of these instances.Figure 8
The best balances in Experiment6.It is concluded from this experiment thatJopt is increasing with βI. As a result, the best balance can be improved by persuading the network users not to install suspicious software.Experiment 7.
Consider the following instances of the VPT control problem:(22)G∣U,0.1,βP,0.4,0.1,0.2,0.8,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, βP∈{0.1,0.2,…,0.9}. Figure 9 displays the best balances of these instances.Figure 9
The best balances in Experiment7.It is concluded from this experiment thatJopt is increasing with βP. Again, this conclusion demonstrates that warning the network users not to install suspicious software would improve the best balance.Experiment 8.
Consider the following instances of the VPT control problem:(23)G∣U,0.1,0.4,γP,0.1,0.2,0.8,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, γP∈{0.1,0.2,…,0.9}. Figure 10 exhibits the best balances of these instances.Figure 10
The best balances in Experiment8.It is concluded from this experiment thatJopt is decreasing with γP. Therefore, the best balance can be improved by reminding the network users of timely installing new patches.Experiment 9.
Consider the following instances of the VPT control problem:(24)G∣U,0.1,0.4,0.4,δ,0.2,0.8,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, δ∈{0.1,0.2,…,0.9}. Figure 11 exhibits the best balances of these instances.Figure 11
The best balances in Experiment9.It is concluded from this experiment thatJopt is increasing with δ. It follows that the best balance can be improved by developing patches that can defend against future viruses.


### 6.2. The Effects of the Two Bounds

Second, let us investigate the effects of the minimum allowable patch injection rate and the maximum allowable patch injection rate on the best balance.Experiment 10.
Consider the following instances of the VPT control problem:(25)G∣U,βI,0.1,0.4,0.4,0.1,γI_,γI¯,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, γI_,γI¯∈{0.1,0.2,…,0.9}. Figure 12 exhibits the best balances of these instances.Figure 12
The best balances in Experiment10.
(a)
G S W ∣ U S W (b)
G S F ∣ U S F (c)
G E M ∣ U E MIt is concluded from this experiment thatJopt is increasing with γI_ and is decreasing with γI_. In practice, we should reduce the lowest allowable patch injection rate and enhance the highest allowable patch injection rate to achieve a better balance.


## 6.1. The Effects of the Four Rates

First, we inspect the effect of the four rates,βI, βP, γP, and δ, on the best balance.Experiment 6.
Consider the following instances of the VPT control problem:(21)G∣U,βI,0.4,0.4,0.1,0.2,0.8,1,1,20,0.1×1,where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, βI∈{0.1,0.2,…,0.9}. Figure 8 exhibits the best balances of these instances.Figure 8
The best balances in Experiment6.It is concluded from this experiment thatJopt is increasing with βI. As a result, the best balance can be improved by persuading the network users not to install suspicious software.Experiment 7.
Consider the following instances of the VPT control problem:(22)G∣U,0.1,βP,0.4,0.1,0.2,0.8,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, βP∈{0.1,0.2,…,0.9}. Figure 9 displays the best balances of these instances.Figure 9
The best balances in Experiment7.It is concluded from this experiment thatJopt is increasing with βP. Again, this conclusion demonstrates that warning the network users not to install suspicious software would improve the best balance.Experiment 8.
Consider the following instances of the VPT control problem:(23)G∣U,0.1,0.4,γP,0.1,0.2,0.8,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, γP∈{0.1,0.2,…,0.9}. Figure 10 exhibits the best balances of these instances.Figure 10
The best balances in Experiment8.It is concluded from this experiment thatJopt is decreasing with γP. Therefore, the best balance can be improved by reminding the network users of timely installing new patches.Experiment 9.
Consider the following instances of the VPT control problem:(24)G∣U,0.1,0.4,0.4,δ,0.2,0.8,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, δ∈{0.1,0.2,…,0.9}. Figure 11 exhibits the best balances of these instances.Figure 11
The best balances in Experiment9.It is concluded from this experiment thatJopt is increasing with δ. It follows that the best balance can be improved by developing patches that can defend against future viruses.


## 6.2. The Effects of the Two Bounds

Second, let us investigate the effects of the minimum allowable patch injection rate and the maximum allowable patch injection rate on the best balance.Experiment 10.
Consider the following instances of the VPT control problem:(25)G∣U,βI,0.1,0.4,0.4,0.1,γI_,γI¯,1,1,20,0.1×1, where G∣U∈{GSW∣USW,GSF∣USF,GEM∣UEM}, γI_,γI¯∈{0.1,0.2,…,0.9}. Figure 12 exhibits the best balances of these instances.Figure 12
The best balances in Experiment10.
(a)
G S W ∣ U S W (b)
G S F ∣ U S F (c)
G E M ∣ U E MIt is concluded from this experiment thatJopt is increasing with γI_ and is decreasing with γI_. In practice, we should reduce the lowest allowable patch injection rate and enhance the highest allowable patch injection rate to achieve a better balance.


## 7. Concluding Remarks

Virus patches play an important role in restraining computer viruses. This paper has addressed the problem of seeking patch-injecting strategies that achieve the best balance between the patch-developing cost and the impact of virus. The problem has been reduced to an optimal control problem, and a scheme for solving the optimal control problem has been presented. Finally, the effects of some factors on the best balance of a patch-injecting strategy have been examined.Some relevant problems are yet to be resolved. First, the problem of how to select a given number of patch injection nodes so that the balance is optimized is worth study. Second, in this article it is assumed that the patch propagation rate is fixed. In practice, the network defender may change this rate flexibly through rewriting the communication protocol. In this situation, we will face a new and more complex balance problem. Next, in this article the virus injection rate is assumed to be fixed. In reality, the virus maker may flexibly change the rate to avoid detection. In this context, it is appropriate to deal with the balance problem through game-theoretic approach [43–46]. Finally, the research approach used in this article may be applied to some other areas such as cloud security [47, 48] and Internet of Things security [49].



---

*Source: 2315627-2019-06-10.xml*