# Evaluating the Performance of a Static Patching Strategy against Computer Viruses

Authors: Da-Wen Huang; Lu-Xing Yang; Xiaofan Yang; Xiang Zhong; Yuan Yan Tang
Journal: Complexity
 (2020)

---

## Abstract

To cope with evolving computer viruses, antivirus programs must be periodically updated. Due to the limited network bandwidth, new virus patches are typically injected into a small subset of network nodes and then forwarded to the remaining nodes. A static patching strategy consists of a fixed patch injection rate and a fixed patch forwarding rate. This paper focuses on evaluating the performance of a static patching strategy. First, we introduce a novel autonomous node-level virus-patch propagation model to characterize the effect of a static patching strategy. Second, we show that the model is globally attracting, implying that regardless of the initial expected state of the network, the expected fraction of the infected nodes converges to the same value. Therefore, we use the asymptotic expected fraction of the infected nodes as the measure of performance of a static patching strategy. On this basis, we evaluate the performances of a few static patching strategies. Finally, we examine the influences of a few parameters on the performance of a static patching strategy. Our findings provide a significant guidance for restraining malware propagation.


---

## Body

## 1. Introduction

Computer networks have become a part of our life. Meanwhile, the rapid spread of digital viruses over networks has posed a huge threat to human society [1]. For instance, the total loss caused by Wannacry, the notorious ransomware, was estimated to be as high as four billion US dollars [2, 3]. Consequently, restraining the propagation of malicious codes has long been a major concern in cyber security [4].To effectively inhibit the diffusion of malware, we must gain a deep insight into its propagation law. Inspired by mathematical epidemiology [5], in the early 1990s Kephart and White [6] proposed the first computer virus propagation model. After years of development, there has formed a new applied mathematics named malware propagation theory, which is devoted to the modeling and study of malware propagation. The earlier malware propagation models build on homogeneously mixed networks [7–15] or some special inhomogeneous networks such as scale-free networks [16–18]. In view of the structural diversity of real-world networks, it is essential to model and study malware propagation on arbitrary networks. The emergent node-level propagation models are especially suited to this demand, because they can accurately account for the effect of the network topology on propagation processes [19, 20]. In the past few years, a number of node-level malware propagation models have been proposed [21–23].For the purpose of restraining the spread of malware, [24, 25] suggested to disseminate virus patches through computer networks. To evaluate the performance of a patch forwarding rate, a number of compartmental virus-patch propagation models have been proposed [26–30]. Recently, a node-level virus-patch propagation model has been suggested [31]. With the evolution of malware, existing antivirus programs are insufficient to defend against future digital viruses. Therefore, security service providers have to keep injecting new virus patches into networks. Due to the limited network bandwidth, virus patches are typically injected into a subset of network nodes and then forwarded to the remaining nodes [25]. Unfortunately, none of the above models takes patch injection into account.Ref. [32] is closely related to our work. In this paper, a simple virus-patch propagation model with patch injection was introduced, and the model was shown to admit a unique globally stable equilibrium. Unfortunately, the results obtained in this paper are applicable to homogeneously mixed networks only. In our opinion, this defect can be overcome by introducing a node-level virus-patch propagation model with patch injection.Ref. [33] is related to our work. In this paper, the problem of seeking cost-effective dynamic patch injection rates was modeled as a game between the virus maker and the security service provider, and a heuristic algorithm for solving the game problem was presented. However, the resulting patch injection rates are time-varying and hence are difficult to realize.The present paper focuses on evaluating the performance of a static patching strategy. First, we introduce an autonomous node-level virus-patch propagation model to characterize the effect of a static patching strategy on the expected state of the associated computer network. Second, we show that this model is globally attracting, which implies that regardless of the initial expected state of the network, the expected fraction of the infected nodes in the network converges to the same value. Therefore, we recommend the asymptotic expected fraction of the infected nodes as the measure of performance of a static patching strategy. Next, we evaluate the performances of a few static patching strategies. Finally, we examine the effects of a few parameters on the performance of a static patching strategy. To our knowledge, this is the first time the performance of a static patching strategy is evaluated by means of node-level malware propagation theory. In view of ease in realizing static patching strategies, our findings provide a significant guidance for restraining malware propagation.The subsequent materials are organized in this fashion. Section2 introduces a virus-patch mixed propagation model, and Section 3 investigates the dynamical properties of the model. Section 4 evaluates the performance of a few static patching strategies, and Section 5 examines the effects of some parameters. This work is summarized by Section 6.


## 2. The Modeling of the Patching Problem

We define thepatching problem as the problem of evaluating the performance of a static patching strategy. This paper focuses on this problem. For this purpose, this section focuses on the modeling of the problem.


### 2.1. Terms and Notations

Consider a computer network and letV={1,2,…,N} denote the set of all network nodes. Suppose viruses and patches propagate through the directed subnets Gv=V,Ev and Gp=V,Ep of the network, respectively. Let A=aijN×N and B=bijN×N denote the adjacency matrices of Gv and Gp, respectively.Suppose that at any timet≥0, each node is assumed to be in one of three possible states: susceptible, infected, and patched. Susceptible nodes are uninfected and have not received the newest patch. Hence, they are vulnerable to the newest virus. Patched nodes have received the newest patch. Hence, they are uninfected and immune to the newest virus. Let Xkt=0 denote the event of node k being susceptible at time t, Xkt=1 the event of node k being infected at time t, and Xkt=2 the event of node k being patched at time t. Then the vector(1)Xt=X1t,X2t,…,XNt,represents the network’s state at timet.Let(2)Skt=PrXkt=0,Ikt=PrXkt=1,Pkt=PrXkt=2.AsSkt+Ikt+Pkt=1, the vector(3)Et=I1t,…,INt,P1t,…,PNt,represents the network’s expected state at timet.


### 2.2. The Virus-Patch Mixed Propagation Model

We introduce a collection of six assumptions as follows.(A1)
Due to virus injection, each susceptible node gets infected at any time at the average rateβI, which we refer to as virus injection rate.(A2)
Due to virus propagation, the susceptible nodek gets infected at time t at the average rate βP∑j=1NajkIjt, where βP is a constant we refer to as virus propagation rate.(A3)
Due to patch injection, each unpatched node gets patched at any time at the average rateγI, which we refer to as patch injection rate.(A4)
Due to patch forwarding, the unpatched nodek gets patched at time t at the average rate γP∑j=1NbjkPjt, where γP is a constant we refer to as patch propagation rate.(A5)
Due to system reinstallation, each infected node gets susceptible at any time at the average rateδI, which we refer to as reinstallation rate.(A6)
Due to emergence of new virus, each patched node gets susceptible at any time at the average rateδP, which we refer to as patch failure rate.These assumptions are schematically shown in Figure1.Figure 1
Diagram of assumptions (A1)–(A6).Based on the above assumptions and according to the differential dynamical system theory [34], the network’s expected state evolves over time according to the following differential dynamical system:(4)dIktdt=βI+βP∑j=1NajkIjt1−Ikt−Pkt−δI+γI+γp∑j=1NbjkPjtIkt,t≥0,1≤k≤N,dPktdt=γI+γP∑j=1NbjkPjt1−Pkt−δPPkt,t≥0,1≤k≤N.Here,(5)E0∈Ω=I1,…,IN,P1,…,PN∈R+2NIk+Pk≤1,k=1,…,N.We refer to the system as avirus-patch propagation (VPP) model. The model accounts for the effect of the static patching strategy. For convenience, we abbreviate this model as(6)dEtdt=FEt,t≥0.


### 2.3. The Modeling of the Patching Problem

The patch injection rateγI and the patch forwarding rate γP are both under the control of the security service provider. Specifically, γI is determined directly by the security service provider, while γP can be adjusted by rewriting the patch forwarding protocol. In what follows, we refer to the two-dimensional vector γI,γP as a static patching strategy.For the VPP model (4), let M=Gv,Gp,βI,βP,δI,δP. The expected fraction of the infected nodes at time t is(7)It=1N∑i=1NIit.So, the asymptotic expected fraction of the infected nodes can be measured by(8)PMγI,γP=liminft→∞It=liminft→∞1N∑i=1NIit.Obviously, the smaller the quantity, the better the static patching strategy. Henceforth, we will use this quantity as the indicator of the performance of the static patching strategyγI,γP.By combining the above discussions, the patching problem comes down to the following problem:Patching Model: Given a 6-tuple
M
=
G
v
,
G
p
,
β
I
,
β
P
,
δ
I
,
δ
P
and a Patching Strategy
γ
I
,
γ
P
. Determine
P
M
γ
I
,
γ
P.


## 2.1. Terms and Notations

Consider a computer network and letV={1,2,…,N} denote the set of all network nodes. Suppose viruses and patches propagate through the directed subnets Gv=V,Ev and Gp=V,Ep of the network, respectively. Let A=aijN×N and B=bijN×N denote the adjacency matrices of Gv and Gp, respectively.Suppose that at any timet≥0, each node is assumed to be in one of three possible states: susceptible, infected, and patched. Susceptible nodes are uninfected and have not received the newest patch. Hence, they are vulnerable to the newest virus. Patched nodes have received the newest patch. Hence, they are uninfected and immune to the newest virus. Let Xkt=0 denote the event of node k being susceptible at time t, Xkt=1 the event of node k being infected at time t, and Xkt=2 the event of node k being patched at time t. Then the vector(1)Xt=X1t,X2t,…,XNt,represents the network’s state at timet.Let(2)Skt=PrXkt=0,Ikt=PrXkt=1,Pkt=PrXkt=2.AsSkt+Ikt+Pkt=1, the vector(3)Et=I1t,…,INt,P1t,…,PNt,represents the network’s expected state at timet.


## 2.2. The Virus-Patch Mixed Propagation Model

We introduce a collection of six assumptions as follows.(A1)
Due to virus injection, each susceptible node gets infected at any time at the average rateβI, which we refer to as virus injection rate.(A2)
Due to virus propagation, the susceptible nodek gets infected at time t at the average rate βP∑j=1NajkIjt, where βP is a constant we refer to as virus propagation rate.(A3)
Due to patch injection, each unpatched node gets patched at any time at the average rateγI, which we refer to as patch injection rate.(A4)
Due to patch forwarding, the unpatched nodek gets patched at time t at the average rate γP∑j=1NbjkPjt, where γP is a constant we refer to as patch propagation rate.(A5)
Due to system reinstallation, each infected node gets susceptible at any time at the average rateδI, which we refer to as reinstallation rate.(A6)
Due to emergence of new virus, each patched node gets susceptible at any time at the average rateδP, which we refer to as patch failure rate.These assumptions are schematically shown in Figure1.Figure 1
Diagram of assumptions (A1)–(A6).Based on the above assumptions and according to the differential dynamical system theory [34], the network’s expected state evolves over time according to the following differential dynamical system:(4)dIktdt=βI+βP∑j=1NajkIjt1−Ikt−Pkt−δI+γI+γp∑j=1NbjkPjtIkt,t≥0,1≤k≤N,dPktdt=γI+γP∑j=1NbjkPjt1−Pkt−δPPkt,t≥0,1≤k≤N.Here,(5)E0∈Ω=I1,…,IN,P1,…,PN∈R+2NIk+Pk≤1,k=1,…,N.We refer to the system as avirus-patch propagation (VPP) model. The model accounts for the effect of the static patching strategy. For convenience, we abbreviate this model as(6)dEtdt=FEt,t≥0.


## 2.3. The Modeling of the Patching Problem

The patch injection rateγI and the patch forwarding rate γP are both under the control of the security service provider. Specifically, γI is determined directly by the security service provider, while γP can be adjusted by rewriting the patch forwarding protocol. In what follows, we refer to the two-dimensional vector γI,γP as a static patching strategy.For the VPP model (4), let M=Gv,Gp,βI,βP,δI,δP. The expected fraction of the infected nodes at time t is(7)It=1N∑i=1NIit.So, the asymptotic expected fraction of the infected nodes can be measured by(8)PMγI,γP=liminft→∞It=liminft→∞1N∑i=1NIit.Obviously, the smaller the quantity, the better the static patching strategy. Henceforth, we will use this quantity as the indicator of the performance of the static patching strategyγI,γP.By combining the above discussions, the patching problem comes down to the following problem:Patching Model: Given a 6-tuple
M
=
G
v
,
G
p
,
β
I
,
β
P
,
δ
I
,
δ
P
and a Patching Strategy
γ
I
,
γ
P
. Determine
P
M
γ
I
,
γ
P.


## 3. The Dynamics of the VPP Model

Obviously, the solution to the patching model depends on the dynamics of the VPP model (4). In this section, we investigate the dynamics of this model. First, we show that the model is positively invariant. Second, we prove that the model admits a unique equilibrium. Finally, we prove that the equilibrium is globally attracting.


### 3.1. Positive Invariance

Lemma 1.
The VPP model (4) is positively invariant with respect to Ω.Proof.
Let∂Ω denote the boundary of Ω. Then ∂Ω consists of the following hyperplanes.(9)Hk=I1,…,IN,P1,…,PN∈ΩIk=0,k=1,…,N,(10)HN+k=I1,…,IN,P1,…,PN∈ΩPk=0,k=1,…,N,(11)H2N+k=I1,…,IN,P1,…,PN∈ΩIk+Pk=1,k=1,…,N.
For1≤k≤N, let nk denote the 2N-dimensional row vector with the k-th component being negative one and all of the remaining components being zero, nN+k the 2N-dimensional row vector with the N+k-th component being negative one and all of the remaining components being zero, and nN+2k the 2N-dimensional row vector with the k-th and N+k-th components being one and all of the remaining components being zero. Obviously, Hk,HN+k, and H2N+k have nk, nN+k, and n2N+k as their respective outer normal vectors. Suppose E=I1,…,IN,P1,…,PN is a smooth point on ∂Ω. We deal with three cases, respectively.
Case 1.
E
∈
H
k. Then, FE,nk=−βI+βP∑j=1NajkIj1−Pk<0.
Case 2.
E
∈
H
N
+
k. Then, FE,nN+k=−γI−γP∑j=1NbjkPj<0.
Case 3.
E
∈
H
2
N
+
k. Then, FE,n2N+k=−δIIk−δPPk<0.
Hence,FE always points to the interior of Ω. The claim follows from [35].


### 3.2. Equilibrium

For a differential dynamical system, an equilibrium is a system state such that if the initial system state is the state, all of the future system states will be the state.Theorem 2.
The VPP model (4) has a unique equilibrium. Moreover, let E∗=I1∗,…,IN∗,P1∗,…,PN∗ denote the equilibrium, then P−<Pk∗<Pk¯, 1≤k≤N, where(12)P−=γIδP+γI,Pk¯=γI+γP∑j=1NbjkδP+γI+γP∑j=1Nbjk,1≤k≤N.Proof.
First, we show that the subsystem(13)dPktdt=γI+γP∑j=1NbjkPjt1−Pkt−δPPkt,t≥0,1≤k≤N,
admits a unique equilibrium. Obviously, the claim holds if and only if the continuous mappingG=g1,…,gN: 0,1N→0,1N, defined by(14)gkP=γI+γP∑j=1NbjkPjδP+γI+γP∑j=1NbjkPj,P=P1,…,PN∈0,1N,1≤k≤N,
admits a unique fixed point. By the well-known Brouwer Fixed Point Theorem [36], we get that G admits a fixed point, denoted P∗=P1∗,…,PN∗. It is easily verified that P−<Pk∗<Pk¯, 1≤k≤N. It remains to show the uniqueness of the fixed point. Otherwise, suppose G admits another fixed point Q∗=Q1∗,…,QN∗. Let(15)ω=max1≤k≤NPk∗Qk∗,k0∈argmax1≤k≤NPk∗Qk∗.
We may assumeω>1. Then(16)Pk0∗=gk0P∗≤gk0ωQ∗=γI+γPω∑j=1Nbjk0Qj∗δP+γI+γPω∑j=1Nbjk0Qj∗<ωγI+γP∑j=1Nbjk0Qj∗δP+γI+γP∑j=1Nbjk0Qj∗=ωgk0Q∗=ωQk0∗.
This contradicts the assumption thatPk0∗=ωQk0∗. So, P∗ is the unique fixed point of G. Hence, the subsystem (13) has a unique equilibrium P∗.
Second, we prove that the VPP model (4) has a unique equilibrium. The claim holds if and only if the function H=h1,…,hN defined by(17)hkI=βI+βP∑j=1NajkIj1−Pk∗βI+βP∑j=1NajkIj+δI+γI+γP∑j=1NbjkPj∗,I=I1,…,IN∈0,1N,1≤k≤N,
admits a unique fixed point. The argument is analogous to the previous argument. LetI∗=I1∗,…,IN∗ denote the unique fixed point of H. Then, the model (4) admits the unique equilibrium E∗=I1∗,…,IN∗,P1∗,…,PN∗.As the VPP model (4) is a multi-dimensional nonlinear differential dynamical system, it is extremely difficult or even impossible to get a closed-form formula for its unique equilibrium. The following theorem provides a numerical method for calculating the equilibrium.Theorem 3.
LetE∗=I∗,P∗=I1∗,…,IN∗,P1∗,…,PN∗ be the equilibrium of the VPP model (4). Define a pair of recursive sequences, Pn=P1n,…,PNnn=0∞ and In=I1n,…,INnn=0∞, as follows.(18)Pkn+1=γI+γP∑j=1NbjkPjnδP+γI+γP∑j=1NbjkPjn,1≤k≤N,n=0,1,…,Pk0=0,1≤k≤N,(19)Ikn+1=βI+βP∑j=1NajkIjn1−Pk∗βI+βP∑j=1NajkIjn+δI+γI+γP∑j=1NbjkPj∗,1≤k≤N,n=0,1,…,Ik0=0,1≤k≤N.
Then,(20)limn→∞Pn=P∗,limn→∞In=I∗.Proof.
The two sequences are obviously bounded. By induction onn, we get that the two sequences are increasing. So, the two sequences converge. By the argument for Theorem 2, we get Eq. (20).


### 3.3. Global Attractiveness

For a differential dynamical system, an equilibrium is globally attracting if the system state always approaches it. An equilibrium of a differential dynamical system is globally stable if (a) it is globally attracting, and (b) for any neighborhood of the equilibrium, there is a neighborhood of the equilibrium such that when starting from within the second neighborhood, the system will always stay within the first neighborhood. Now, examine the global attractiveness of the equilibrium of the VPP model. For this purpose, we will use the following well-known lemma.Lemma 4 (Chaplygin lemma [37]).
Given a smoothn-dimensional differential system(21)dxtdt=fxt,t≥0.
Let(22)dytdt≤fyt,dztdt≥fzt,t≥0,
wherey0=z0=x0. Suppose for any a1,…,an≥0, there hold(23)fix1+a1,…,xi−1+ai−1,xi,xi+1+ai+1,…,xn+an≥fix1,…,xn,i=1,…,n.
Thenyt≤xt, zt≥xt, t≥0.For our purpose, we prove the following lemma.Lemma 5.
LetEt=I1t,…,INt,P1t,…,PNt (t≥0) be a solution to the model (4). Then there exists t0>0 such that(24)0<Pkt<1,t≥t0,1≤k≤N.Proof.
Obviously, we have(25)dPktdt≥γI1−Pkt−δPPkt,t≥0,1≤k≤N,
and(26)dPktdt≤γI+γP∑j=1Nbjk1−Pkt−δPPkt,t≥0,1≤k≤N.
Consider the comparison systems(27)duktdt=γI1−ukt−δPukt,t≥0,1≤k≤N,
and(28)dvktdt=γI+γP∑j=1Nbjk1−vkt−δPvkt,t≥0,1≤k≤N,
whereuk0=vk0=Pk0, 1≤k≤N. By Lemma 4, we have(29)ukt≤Pkt≤vkt,t≥0,1≤k≤N.
Obviously, the system (27) admits the globally stable equilibrium P−,…,P−, and the system (28) admits the globally stable equilibrium P1¯,…,PN¯. So,(30)P−=limt→∞ukt≤liminft→∞Pkt≤limsupt→∞Pkt≤limt→∞vkt=Pk¯,1≤k≤N.
The claimed inequalities follow.
Now, let us present the main result of this paper as follows.Theorem 6.
The equilibrium of the VPP model (4) is globally attracting.Proof.
LetE∗=I∗,P∗=I1∗,…,IN∗,P1∗,…,PN∗ be the equilibrium of the model (4). First, we show that P∗ is a globally stable equilibrium of the subsystem(31)dPktdt=γI+γP∑j=1NbjkPjt1−Pkt−δPPkt,t≥0,1≤k≤N.
LetPt=P1t,…,PNt be a solution to the subsystem. Let(32)ΛPt=max1≤k≤NPktPk∗,λPt=min1≤k≤NPktPk∗,t≥t0,
wheret0 is given by Lemma 5. Let(33)ΘPt=max  ΛPt−1,0+max1−λPt,t≥t0.
ThenΘPt≥0, and ΘPt=0 if and only if Pt=P∗. Let D+ and D+ denote the upper-right and lower-right Dini derivatives, respectively. Then we have two claims as follows.
Claim 1. D+ΛPt≤0 if ΛPt≥1, and D+ΛPt<0 if ΛPt>1.
Claim 2. D+λPt≥0 if λPt≤1, and D+λPt>0 if λPt<1.
We prove the first claim only, because the second claim can be proved analogously. Choose:(34) k0∈argmax1≤k≤NPktPk∗
such thatD+ΛPt=Pk0′t/Pk0∗. As ΛPt≥1, we have Pk0t≥Pk0∗. So,(35)Pk0∗Pk0tPk0′t=γI1−Pk0tPk0∗Pk0t+γP1−Pk0tPk0∗Pk0t∑j=1Nbjk0Pjt−δPPk0∗≤γI+γP∑j=1Nbjk0Pj∗1−Pk0∗−δPPk0∗=0.
Hence,D+ΛPt≤0, As the inequality is strict if ΛPt>1, i.e., we have D+ΛPt<0 if ΛPt>1.
Next, we treat three cases, respectively.
Case 1.
Λ
P
t
<
1
,
λ
P
t
<
1. Then ΘPt=1−λPt. So, D+ΘPt=−D+λPt<0.
Case 2.
Λ
P
t
>
1
,
λ
P
t
>
1. Then ΘPt=ΛPt−1. So, D+ΘPt=D+ΛPt<0.
Case 3. ΛPt≥1,λPt≤1. Then (36)ΘPt=ΛPt−λPt.So, (37)D+ΘPt=D+Pt−D+λPt≤0 .
Moreover, the equality holds if and only ifPt=P∗.
It follows from the LaSalle Invariance Principle [34] that P∗ is globally attracting. Hence, for any 0<ϵ<Pk∗, there exists t1ϵ>t0 such that(38)Pk∗−ϵ<Pkt<Pk∗+ϵ,t≥t1ϵ,1≤k≤N.
Substituting these inequalities into the firstN equations in the model (4), we get(39)dIktdt≥βI+βP∑j=1NajkIjt1−Pk∗−ϵ−Ikt−δI+γI+γP∑j=1NbjkPj∗+ϵIkt,t≥t1ϵ,1≤k≤N,
and(40)dIktdt≤βI+βP∑j=1NajkIjt1−Pk∗+ϵ−Ikt−δI+γI+γP∑j=1NbjkPj∗−ϵIkt,t≥t1ϵ,1≤k≤N.
Consider the comparison systems(41)dukt;ϵdt=βI+βP∑j=1Najkujt;ϵ1−Pk∗+ϵ−ukt;ϵ−δI+γI+γP∑j=1NbjkPj∗−ϵukt;ϵ,t≥t1ϵ,1≤k≤N,
and(42)dvkt;ϵdt=βI+βP∑j=1Najkvjt;ϵ1−Pk∗−ϵ−vkt;ϵ−δI+γI+γP∑j=1NbjkPj∗−ϵvkt;ϵ,t≥t1ϵ,1≤k≤N,
whereukt1ϵ=vkt1ϵ=Ikt1ϵ, 1≤k≤N. By Lemma 4, we have(43)ukt;ϵ≤Ikt≤vkt;ϵ,t≥t1ϵ,1≤k≤N.
Similarly to the previous argument, we can show that the system (41) admits a globally stable equilibrium u∗ϵ=u1∗ϵ,…,uN∗ϵ, and the system (42) admits a globally stable equilibrium v∗ϵ=v1∗ϵ,…,vN∗ϵ. So, we get(44)uk∗ϵ=limt→∞ukt;ϵ≤liminft→∞Ikt≤limsupt→∞Ikt≤limt→∞vkt;ϵ=vk∗ϵ,1≤k≤N.
Obviously, we havelimϵ→0u∗ϵ=limϵ→0v∗ϵ=I∗. By Eq. (44), we get(45)Ik∗=limϵ→0uk∗ϵ≤liminft→∞Ikt≤limsupt→∞Ikt≤limϵ→0vk∗ϵ=Ik∗,1≤k≤N.
Hence,limt→∞It=I∗. Therefore, E∗ is the global attractor of the model (4).By Theorem6, we have the following result.Theorem 7.
For the VPP model (4), we have(46)PMγI,γP=1N∑i=1NIi∗.According to Theorem3, we may calculate the measure of performance of a static patching strategy using the iterations (18) and (19).


## 3.1. Positive Invariance

Lemma 1.
The VPP model (4) is positively invariant with respect to Ω.Proof.
Let∂Ω denote the boundary of Ω. Then ∂Ω consists of the following hyperplanes.(9)Hk=I1,…,IN,P1,…,PN∈ΩIk=0,k=1,…,N,(10)HN+k=I1,…,IN,P1,…,PN∈ΩPk=0,k=1,…,N,(11)H2N+k=I1,…,IN,P1,…,PN∈ΩIk+Pk=1,k=1,…,N.
For1≤k≤N, let nk denote the 2N-dimensional row vector with the k-th component being negative one and all of the remaining components being zero, nN+k the 2N-dimensional row vector with the N+k-th component being negative one and all of the remaining components being zero, and nN+2k the 2N-dimensional row vector with the k-th and N+k-th components being one and all of the remaining components being zero. Obviously, Hk,HN+k, and H2N+k have nk, nN+k, and n2N+k as their respective outer normal vectors. Suppose E=I1,…,IN,P1,…,PN is a smooth point on ∂Ω. We deal with three cases, respectively.
Case 1.
E
∈
H
k. Then, FE,nk=−βI+βP∑j=1NajkIj1−Pk<0.
Case 2.
E
∈
H
N
+
k. Then, FE,nN+k=−γI−γP∑j=1NbjkPj<0.
Case 3.
E
∈
H
2
N
+
k. Then, FE,n2N+k=−δIIk−δPPk<0.
Hence,FE always points to the interior of Ω. The claim follows from [35].


## 3.2. Equilibrium

For a differential dynamical system, an equilibrium is a system state such that if the initial system state is the state, all of the future system states will be the state.Theorem 2.
The VPP model (4) has a unique equilibrium. Moreover, let E∗=I1∗,…,IN∗,P1∗,…,PN∗ denote the equilibrium, then P−<Pk∗<Pk¯, 1≤k≤N, where(12)P−=γIδP+γI,Pk¯=γI+γP∑j=1NbjkδP+γI+γP∑j=1Nbjk,1≤k≤N.Proof.
First, we show that the subsystem(13)dPktdt=γI+γP∑j=1NbjkPjt1−Pkt−δPPkt,t≥0,1≤k≤N,
admits a unique equilibrium. Obviously, the claim holds if and only if the continuous mappingG=g1,…,gN: 0,1N→0,1N, defined by(14)gkP=γI+γP∑j=1NbjkPjδP+γI+γP∑j=1NbjkPj,P=P1,…,PN∈0,1N,1≤k≤N,
admits a unique fixed point. By the well-known Brouwer Fixed Point Theorem [36], we get that G admits a fixed point, denoted P∗=P1∗,…,PN∗. It is easily verified that P−<Pk∗<Pk¯, 1≤k≤N. It remains to show the uniqueness of the fixed point. Otherwise, suppose G admits another fixed point Q∗=Q1∗,…,QN∗. Let(15)ω=max1≤k≤NPk∗Qk∗,k0∈argmax1≤k≤NPk∗Qk∗.
We may assumeω>1. Then(16)Pk0∗=gk0P∗≤gk0ωQ∗=γI+γPω∑j=1Nbjk0Qj∗δP+γI+γPω∑j=1Nbjk0Qj∗<ωγI+γP∑j=1Nbjk0Qj∗δP+γI+γP∑j=1Nbjk0Qj∗=ωgk0Q∗=ωQk0∗.
This contradicts the assumption thatPk0∗=ωQk0∗. So, P∗ is the unique fixed point of G. Hence, the subsystem (13) has a unique equilibrium P∗.
Second, we prove that the VPP model (4) has a unique equilibrium. The claim holds if and only if the function H=h1,…,hN defined by(17)hkI=βI+βP∑j=1NajkIj1−Pk∗βI+βP∑j=1NajkIj+δI+γI+γP∑j=1NbjkPj∗,I=I1,…,IN∈0,1N,1≤k≤N,
admits a unique fixed point. The argument is analogous to the previous argument. LetI∗=I1∗,…,IN∗ denote the unique fixed point of H. Then, the model (4) admits the unique equilibrium E∗=I1∗,…,IN∗,P1∗,…,PN∗.As the VPP model (4) is a multi-dimensional nonlinear differential dynamical system, it is extremely difficult or even impossible to get a closed-form formula for its unique equilibrium. The following theorem provides a numerical method for calculating the equilibrium.Theorem 3.
LetE∗=I∗,P∗=I1∗,…,IN∗,P1∗,…,PN∗ be the equilibrium of the VPP model (4). Define a pair of recursive sequences, Pn=P1n,…,PNnn=0∞ and In=I1n,…,INnn=0∞, as follows.(18)Pkn+1=γI+γP∑j=1NbjkPjnδP+γI+γP∑j=1NbjkPjn,1≤k≤N,n=0,1,…,Pk0=0,1≤k≤N,(19)Ikn+1=βI+βP∑j=1NajkIjn1−Pk∗βI+βP∑j=1NajkIjn+δI+γI+γP∑j=1NbjkPj∗,1≤k≤N,n=0,1,…,Ik0=0,1≤k≤N.
Then,(20)limn→∞Pn=P∗,limn→∞In=I∗.Proof.
The two sequences are obviously bounded. By induction onn, we get that the two sequences are increasing. So, the two sequences converge. By the argument for Theorem 2, we get Eq. (20).


## 3.3. Global Attractiveness

For a differential dynamical system, an equilibrium is globally attracting if the system state always approaches it. An equilibrium of a differential dynamical system is globally stable if (a) it is globally attracting, and (b) for any neighborhood of the equilibrium, there is a neighborhood of the equilibrium such that when starting from within the second neighborhood, the system will always stay within the first neighborhood. Now, examine the global attractiveness of the equilibrium of the VPP model. For this purpose, we will use the following well-known lemma.Lemma 4 (Chaplygin lemma [37]).
Given a smoothn-dimensional differential system(21)dxtdt=fxt,t≥0.
Let(22)dytdt≤fyt,dztdt≥fzt,t≥0,
wherey0=z0=x0. Suppose for any a1,…,an≥0, there hold(23)fix1+a1,…,xi−1+ai−1,xi,xi+1+ai+1,…,xn+an≥fix1,…,xn,i=1,…,n.
Thenyt≤xt, zt≥xt, t≥0.For our purpose, we prove the following lemma.Lemma 5.
LetEt=I1t,…,INt,P1t,…,PNt (t≥0) be a solution to the model (4). Then there exists t0>0 such that(24)0<Pkt<1,t≥t0,1≤k≤N.Proof.
Obviously, we have(25)dPktdt≥γI1−Pkt−δPPkt,t≥0,1≤k≤N,
and(26)dPktdt≤γI+γP∑j=1Nbjk1−Pkt−δPPkt,t≥0,1≤k≤N.
Consider the comparison systems(27)duktdt=γI1−ukt−δPukt,t≥0,1≤k≤N,
and(28)dvktdt=γI+γP∑j=1Nbjk1−vkt−δPvkt,t≥0,1≤k≤N,
whereuk0=vk0=Pk0, 1≤k≤N. By Lemma 4, we have(29)ukt≤Pkt≤vkt,t≥0,1≤k≤N.
Obviously, the system (27) admits the globally stable equilibrium P−,…,P−, and the system (28) admits the globally stable equilibrium P1¯,…,PN¯. So,(30)P−=limt→∞ukt≤liminft→∞Pkt≤limsupt→∞Pkt≤limt→∞vkt=Pk¯,1≤k≤N.
The claimed inequalities follow.
Now, let us present the main result of this paper as follows.Theorem 6.
The equilibrium of the VPP model (4) is globally attracting.Proof.
LetE∗=I∗,P∗=I1∗,…,IN∗,P1∗,…,PN∗ be the equilibrium of the model (4). First, we show that P∗ is a globally stable equilibrium of the subsystem(31)dPktdt=γI+γP∑j=1NbjkPjt1−Pkt−δPPkt,t≥0,1≤k≤N.
LetPt=P1t,…,PNt be a solution to the subsystem. Let(32)ΛPt=max1≤k≤NPktPk∗,λPt=min1≤k≤NPktPk∗,t≥t0,
wheret0 is given by Lemma 5. Let(33)ΘPt=max  ΛPt−1,0+max1−λPt,t≥t0.
ThenΘPt≥0, and ΘPt=0 if and only if Pt=P∗. Let D+ and D+ denote the upper-right and lower-right Dini derivatives, respectively. Then we have two claims as follows.
Claim 1. D+ΛPt≤0 if ΛPt≥1, and D+ΛPt<0 if ΛPt>1.
Claim 2. D+λPt≥0 if λPt≤1, and D+λPt>0 if λPt<1.
We prove the first claim only, because the second claim can be proved analogously. Choose:(34) k0∈argmax1≤k≤NPktPk∗
such thatD+ΛPt=Pk0′t/Pk0∗. As ΛPt≥1, we have Pk0t≥Pk0∗. So,(35)Pk0∗Pk0tPk0′t=γI1−Pk0tPk0∗Pk0t+γP1−Pk0tPk0∗Pk0t∑j=1Nbjk0Pjt−δPPk0∗≤γI+γP∑j=1Nbjk0Pj∗1−Pk0∗−δPPk0∗=0.
Hence,D+ΛPt≤0, As the inequality is strict if ΛPt>1, i.e., we have D+ΛPt<0 if ΛPt>1.
Next, we treat three cases, respectively.
Case 1.
Λ
P
t
<
1
,
λ
P
t
<
1. Then ΘPt=1−λPt. So, D+ΘPt=−D+λPt<0.
Case 2.
Λ
P
t
>
1
,
λ
P
t
>
1. Then ΘPt=ΛPt−1. So, D+ΘPt=D+ΛPt<0.
Case 3. ΛPt≥1,λPt≤1. Then (36)ΘPt=ΛPt−λPt.So, (37)D+ΘPt=D+Pt−D+λPt≤0 .
Moreover, the equality holds if and only ifPt=P∗.
It follows from the LaSalle Invariance Principle [34] that P∗ is globally attracting. Hence, for any 0<ϵ<Pk∗, there exists t1ϵ>t0 such that(38)Pk∗−ϵ<Pkt<Pk∗+ϵ,t≥t1ϵ,1≤k≤N.
Substituting these inequalities into the firstN equations in the model (4), we get(39)dIktdt≥βI+βP∑j=1NajkIjt1−Pk∗−ϵ−Ikt−δI+γI+γP∑j=1NbjkPj∗+ϵIkt,t≥t1ϵ,1≤k≤N,
and(40)dIktdt≤βI+βP∑j=1NajkIjt1−Pk∗+ϵ−Ikt−δI+γI+γP∑j=1NbjkPj∗−ϵIkt,t≥t1ϵ,1≤k≤N.
Consider the comparison systems(41)dukt;ϵdt=βI+βP∑j=1Najkujt;ϵ1−Pk∗+ϵ−ukt;ϵ−δI+γI+γP∑j=1NbjkPj∗−ϵukt;ϵ,t≥t1ϵ,1≤k≤N,
and(42)dvkt;ϵdt=βI+βP∑j=1Najkvjt;ϵ1−Pk∗−ϵ−vkt;ϵ−δI+γI+γP∑j=1NbjkPj∗−ϵvkt;ϵ,t≥t1ϵ,1≤k≤N,
whereukt1ϵ=vkt1ϵ=Ikt1ϵ, 1≤k≤N. By Lemma 4, we have(43)ukt;ϵ≤Ikt≤vkt;ϵ,t≥t1ϵ,1≤k≤N.
Similarly to the previous argument, we can show that the system (41) admits a globally stable equilibrium u∗ϵ=u1∗ϵ,…,uN∗ϵ, and the system (42) admits a globally stable equilibrium v∗ϵ=v1∗ϵ,…,vN∗ϵ. So, we get(44)uk∗ϵ=limt→∞ukt;ϵ≤liminft→∞Ikt≤limsupt→∞Ikt≤limt→∞vkt;ϵ=vk∗ϵ,1≤k≤N.
Obviously, we havelimϵ→0u∗ϵ=limϵ→0v∗ϵ=I∗. By Eq. (44), we get(45)Ik∗=limϵ→0uk∗ϵ≤liminft→∞Ikt≤limsupt→∞Ikt≤limϵ→0vk∗ϵ=Ik∗,1≤k≤N.
Hence,limt→∞It=I∗. Therefore, E∗ is the global attractor of the model (4).By Theorem6, we have the following result.Theorem 7.
For the VPP model (4), we have(46)PMγI,γP=1N∑i=1NIi∗.According to Theorem3, we may calculate the measure of performance of a static patching strategy using the iterations (18) and (19).


## 4. The Performances of Some Patching Strategies

In this subsection, we evaluate the performances of some patching strategies. For this purpose, we need to acquire some networks. Pajek is a famous social network analysis software [38]. By setting the number of nodes as 100 and the edge-rewiring probability as 0.1 and using Pajek, we get a small-world network [39], which is denoted GSW and displayed in Figure 2. By setting the number of nodes as 100 and using Pajek, we get a scale-free network [40], which is denoted GSF and exhibited in Figure 3. Finally, Figure 4 exhibits a real-world email network GEM with 100 nodes [41].Figure 2
A synthetic small-world networkGSW.Figure 3
A synthetic scale-free networkGSF.Figure 4
A realistic email networkGEM.Example 8.
Consider the VPP model withM=GSW,GSF,0.01,0.01,0.01,0.02 and γI,γP=0.01,0.01. By calculations, we get PMγI,γP=0.1478. Figure 5 shows that 1/N∑i=1NIit→PMγI,γP for five different initial conditions, agreeing with Theorem 7.Figure 5
The evolution of the expected fraction of the infected nodes in Example8.Example 9.
Consider the VPP model withM=GSF,GEM,0.01,0.01,0.01,=0.02 and γI,γP=0.01,0.01. By calculations, we get PMγI,γP=0.0463. Figure 6 shows that 1/N∑i=1NIit→PMγI,γP for five different initial conditions, in accordance with Theorem 7.Figure 6
The evolution of the expected fraction of the infected nodes in Example9.Example 10.
Consider the VPP model withM=GEM,GSW,0.01,0.01,0.01,0.02 and γI,γP=0.01,0.01. By calculations, we get PMγI,γP=0.1084. Figure 7 shows that 1/N∑i=1NIit→PMγI,γP for five different initial conditions, conforming to Theorem 7.Figure7
The evolution of the expected fraction of the infected nodes in Example10.


## 5. Further Discussions

Now, let us investigate the effects of some parameters on the performance of a patching strategy.


### 5.1. The Effects of the Four Rates

First, let us examine how the four rates,βI, βP, δI, and δP, affect performance of a patching strategy.Theorem 11.
For the VPP model (4), PMγI,γP is increasing with βI, βP, and δP, and is decreasing with δI.Proof.
We argue for the first claim only. This is because the arguments for the remaining claims are similar. LetE1∗=I1∗,P1∗ denote the equilibrium of the VPP model with M1=Gv,Gp,βI1,βP,δI,δP and the static patching strategy γI,γP, E2∗=I2∗,P2∗ the equilibrium of the  VPP model with M2=Gv,Gp,βI2,βP,δI,δP and the static patching strategy γI,γP, where βI1<βI2. Let Pnn=0∞ be the solution to the recursion (18). By Theorem 3, we get(47)limn→∞Pn=P1∗=P2∗.
LetIn1n=0∞ be the solution to the recursion (19) with βI=βI1, In2n=0∞ the solution to the recursion (19) with βI=βI2. By Theorem 3, we get(48)limn→∞In1=I1∗,limn→∞In2=I2∗.
By induction onn, we get In1≤In2n=0,1,…. So,(49)I1∗=limn→∞In1≤limn→∞In2=I2∗.
Combining Eq. (47) with Eq. (49), we get PM1γI,γP≤PM2γI,γP.
The theorem demonstrates that the performance of a patching strategy can be improved by either reducing the virus injection rate or the virus propagation rate or the patch failure rate or enhancing the reinstallation rate.Example 12.
Consider the set of  VPP  models withM=GSW,GSF,βI,0.01,0.01,0.02 and γI,γP=0.01,0.01, βI∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(a) shows that PMγI,γP is increasing with βI, agreeing with the first claim of Theorem 11.Figure 8
The effects ofβI, βP, δI, and δP on PMγI,γP in Examples 12, 5, 6, and 7, respectively.
(a)
(b)
(c)
(d)Example 13.
Consider the set of VPP models withM=GSW,GEM,0.01,βP,0.01,0.02 and γI,γP=0.01,0.01, βP∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(b) shows that PMγI,γP is increasing with βP, in agreement with the second claim of Theorem 11.Example 14.
Consider the set of  VPP models withM=GSF,GEM,0.01,0.01,δI,0.02 and γI,γP=0.01,0.01, δI∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(c) shows that PMγI,γP is decreasing with δI, meeting the fourth claim of Theorem 11.Example 15.
Consider the set of  VPP models withM=GSF,GEM,0.01,0.01,0.01,δP and γI,γP=0.01,0.01, δP∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(d) shows that PMγI,γP is increasing with δP, in accordance with the third claim of Theorem 11.


### 5.2. The Effects of the Two Networks

Next, we inspect how the virus-propagating network and the patch-forwarding network affect the performance of a patching strategy.Theorem 16.
For the VPP model (4), PMγI,γP is increasing with the addition of new edges in Gv, and is decreasing with the addition of new edges in Gp.The argument for the theorem is analogous to that for Theorem7. Hence, it is omitted. This theorem shows that the performance of a patching strategy can be improved by reducing virus propagation channels or augmenting patch dissemination channels.


## 5.1. The Effects of the Four Rates

First, let us examine how the four rates,βI, βP, δI, and δP, affect performance of a patching strategy.Theorem 11.
For the VPP model (4), PMγI,γP is increasing with βI, βP, and δP, and is decreasing with δI.Proof.
We argue for the first claim only. This is because the arguments for the remaining claims are similar. LetE1∗=I1∗,P1∗ denote the equilibrium of the VPP model with M1=Gv,Gp,βI1,βP,δI,δP and the static patching strategy γI,γP, E2∗=I2∗,P2∗ the equilibrium of the  VPP model with M2=Gv,Gp,βI2,βP,δI,δP and the static patching strategy γI,γP, where βI1<βI2. Let Pnn=0∞ be the solution to the recursion (18). By Theorem 3, we get(47)limn→∞Pn=P1∗=P2∗.
LetIn1n=0∞ be the solution to the recursion (19) with βI=βI1, In2n=0∞ the solution to the recursion (19) with βI=βI2. By Theorem 3, we get(48)limn→∞In1=I1∗,limn→∞In2=I2∗.
By induction onn, we get In1≤In2n=0,1,…. So,(49)I1∗=limn→∞In1≤limn→∞In2=I2∗.
Combining Eq. (47) with Eq. (49), we get PM1γI,γP≤PM2γI,γP.
The theorem demonstrates that the performance of a patching strategy can be improved by either reducing the virus injection rate or the virus propagation rate or the patch failure rate or enhancing the reinstallation rate.Example 12.
Consider the set of  VPP  models withM=GSW,GSF,βI,0.01,0.01,0.02 and γI,γP=0.01,0.01, βI∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(a) shows that PMγI,γP is increasing with βI, agreeing with the first claim of Theorem 11.Figure 8
The effects ofβI, βP, δI, and δP on PMγI,γP in Examples 12, 5, 6, and 7, respectively.
(a)
(b)
(c)
(d)Example 13.
Consider the set of VPP models withM=GSW,GEM,0.01,βP,0.01,0.02 and γI,γP=0.01,0.01, βP∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(b) shows that PMγI,γP is increasing with βP, in agreement with the second claim of Theorem 11.Example 14.
Consider the set of  VPP models withM=GSF,GEM,0.01,0.01,δI,0.02 and γI,γP=0.01,0.01, δI∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(c) shows that PMγI,γP is decreasing with δI, meeting the fourth claim of Theorem 11.Example 15.
Consider the set of  VPP models withM=GSF,GEM,0.01,0.01,0.01,δP and γI,γP=0.01,0.01, δP∈{0.01,0.02,0.03,…,0.99,1}. Figure 8(d) shows that PMγI,γP is increasing with δP, in accordance with the third claim of Theorem 11.


## 5.2. The Effects of the Two Networks

Next, we inspect how the virus-propagating network and the patch-forwarding network affect the performance of a patching strategy.Theorem 16.
For the VPP model (4), PMγI,γP is increasing with the addition of new edges in Gv, and is decreasing with the addition of new edges in Gp.The argument for the theorem is analogous to that for Theorem7. Hence, it is omitted. This theorem shows that the performance of a patching strategy can be improved by reducing virus propagation channels or augmenting patch dissemination channels.


## 6. Summary

This paper has addressed the issue of evaluating the performance of a static patching strategy. We have introduced a novel node-level virus-patch propagation model and showed that the model is globally attracting. Hence, we have recommended the asymptotic expected fraction of the infected nodes as the indicator of performance of a patching strategy.There are some relevant problems that are worth studying. The virus-patch propagation model (4) can easily be extended to the situation where the patching rates are different for susceptible and infectious nodes, with similar results. In this paper it is assumed that the network topology is unchanged over time. However, many real-world computer neworks such as mobile networks are time-varying. Hence, it is worthwhile to extend this work to the time-varying network situation. In practice, a security service provider may flexibly adjust the patching strategy over time to mitigate the consequence of malware. In this situation, the problem of seeking a cost-effective dynamic patching strategy may be modeled as an optimal control problem [42, 43]. Additionally, when the virus maker is intelligent and rational, the problem of choosing a cost-effective patching strategy may boil down to a game problem [44–46].



---

*Source: 9408942-2020-01-21.xml*