key: cord-0518589-vszsrzi1
authors: Taynitskiy, Vladislav; Gubar, Elena; Fedyanin, Denis; Petrov, Ilya; Zhu, Quanyan
title: Optimal Control of Joint Multi-Virus Infection and Information Spreading
date: 2020-07-19
journal: nan
DOI: nan
sha: 33d37b35a1eca437106d3fccb4224bb7781400af
doc_id: 518589
cord_uid: vszsrzi1

Nowadays, epidemic models provide an appropriate tool for describing the propagation of biological viruses in human or animal populations, or rumours and other kinds of information in social networks and malware in both computer and ad hoc networks. Commonly, there are exist multiple types of malware infecting a network of computing devices, or different messages can spread over the social network. Information spreading and virus propagation are interdependent processes. To capture such independencies, we integrate two epidemic models into one holistic framework, known as the modified Susceptible-Warned-Infected-Recovered-Susceptible (SWIRS) model. The first epidemic model describes the information spreading regarding the risk of malware attacks and possible preventive procedures. The second one describes the propagation of multiple viruses over the network of devices. To minimize the impact of the virus spreading and improve the protection of the networks, we consider an optimal control problem with two types of control strategies: information spreading among healthy nodes and the treatment of infected nodes. We obtain the structure of optimal control strategies and study the condition of epidemic outbreaks. The main results are extended to the case of the network of two connected clusters. Numerical examples are used to corroborate the theoretical findings.

Recent advances in information technologies have witnessed an exponential growth in the number of devices connected to the Internet and the rapid expansion of the use of social networks. The proliferation of devices creates opportunities to spread information more conveniently but has also created a large attack surface for the malware to exploit existing vulnerabilities of the devices and spread malicious codes over the Internet. The channels of malware spreading nowadays are not just limited to computer networks but also include mobile networks and online social networks. Moreover, the wide applications of networks generate an increasing amount of security threats. Computer virus or malware spread and attack a large number of nodes as the network connectivity increases. It can disrupt computer functionalities, collect sensitive confidential information, and gain illegal access to private computer networks at a much larger scale. Therefore, it is critical to design preventive and effective treatment strategies.

The control of malware spreading can be considered as an optimal control problem that defines a trade-off solution between the cost of fast and periodic development of patches and the value of the recovery of the devices. At the same time, information propagation of the vulnerability of the computing devices and personal accounts in social networks as well as the knowledge of the effective protection measures can help raise the awareness of the security threats and their solutions to reduce the number of infected devices. Generally, multiple types of viruses co-exist at the same time. Hence, we model the malware spreading as Susceptible-Infected-Recovered-Susceptible (SIRS) dynamics in which the population of devices is grouped into several subpopulations, i.e., the susceptible (S), the infected (I) and recovered (R). In addition, a group of infected nodes is also divided into several subgroups. The SIRS dynamics describe the evolution of the population size that can be controlled using special patching and recovery. Spreading of information is also described by the modified SIR model, which includes susceptible (S), warned (W), and recovered (R) nodes. Here, warned nodes are informed of the necessity of protection of their accounts and devices from their neighbors.

The goal of the work is to combine the two epidemic processes in one model. One epidemic process describes the dissemination of the information and the other one is the spreading of the viruses. We consider a generalized Susceptible-Warned-Infected-Recovered-Susceptible (SWIRS) model, which extends the model for information spreading by incorporating the SIRS model that describes the propagation of two types of malware. In the paper, we present the stability analysis of SWIRS model, formulate a controlled SWIRS model, and show the structure of the optimal policies of spreading information about virus protection and optimal treatment. Moreover, we carry out a series of numerical simulations to corroborate the results.

Recent literature has seen a surge of interest in using optimal control and stability equilibrium analysis to study malware protection in computer networks, social networks, and ad-hoc networks (See Fedyanin (2011); Zuzek (2015) ; Taynitskiy (2015 ; Zhu (2017, 2019) ; Moon (2019) ; Huang and Zhu (2019a,b) ). Moreover, the clusters of the population play an important role. Several waves of the viruses propagation might occur due to sequential propagation information from one cluster to another even when a single cluster model might predict just a monotone spreading.

In this paper, we establish a control-theoretic model to design optimal quarantining and immunization strategies to mitigate the impact of epidemics on our society. The recent spreading of ransomware (e.g., CryptoLocker, Cryp-toDefense, or CryptoWall) has spread using spam emails to extort money from home users and businesses alike by locking files on a PC or network storage (See Luo (2009); Newman (2016) ). Mean-field dynamical systems are used to model the underlying evolution of the host subpopulations. In Wang (2017) , many variants of optimal control models of SIR-epidemics are investigated in the context of medical vaccination and health promotion campaigns. Previous studies have shown the application of epidemic frameworks to the models of network protection as in Mieghem (2009); Sahneh (2013) ; Vespignani (2015) ; Farooq and Zhu (2017, 2019); Taynitskiy ( , 2018 ; Altman (2019). Many different research works have provided many variants of epidemic models in computer security. Spreading information on social networks is presented in Moore (2002) .

The rest of the paper is organized as follows. Section 2 presents the controlled SWIRS mathematical model. In Section 2.1, we formulate the SWIRS model. Sections 2.2 and 2.3 show the stability analysis of the diseasefree equilibrium. Section 2.4 describes the optimal control problem and Section 2.5 presents the structure of optimal protection and information spreading policies. In Section 3, theoretical results are applied to the case of clusterized population. Section 4 presents the series of numerical experiments. Section 5 concludes the paper.

In this section, we formulate a two-level modified SIRS model (Susceptible-Infected-Recovered-Susceptible) with two different types of viruses circulated in a population of size N . This auxiliary partitioning allows capturing two processes that occur in both computer and social networks. The first process is the propagation of information on harmful malware attacks and the protection of personal data, documents, projects, etc. We consider this spreading process as the first level hierarchy in the Susceptible-Warned-Infected-Recovered-Susceptible (SWIRS) model. The second process, which corresponds to the physical propagation of antivirus software, is considered as the second level of the model, which is a modified Susceptible-Infected-Recovered-Susceptible (SIRS) model with two competitive viruses. Thereby, in contrast to classical SIRS models, where populations are divided into three groups: Susceptible (S), Infected (I), and Recovered (R), here the Infected subgroup is divided into two subgroups: a subgroup of nodes infected by the first type of virus V 1 and the subgroup infected by the second type V 2 . Spreading information on the first level adds a new group Warned (W ) into consideration. This group consists of the nodes, which have received information about possible the risks of virus attack/spreading and ready to use special tools for protections. We model the epidemic process as a system of nonlinear differential equations. The total number of nodes in the network during the entire process remains constant and equal to n S + n W + n V1 + n V2 + n R = N . Let S(t) = n S (t) N ,

N as a fraction of the Susceptible, the Warned, the Infected, and the Recovered nodes, respectively. At the beginning of the epidemic, at time t = 0, the majority of the individuals are in the Susceptible state, and a small fraction of individuals are infected by different types of virus. Hence, initial states are

. Behaviour of the system is described by a system of nonlinear differential equations:

where β S i are infection rates for susceptible nodes for virus V i , i = 1, 2 and β W i are infection rates for the warned nodes. On the second level of the epidemic process, we can view a self-recovery rate σ 1 for virus V 1 or σ 2 for virus V 2 as the probability that infected nodes from subgroups I 1 or I 2 are recovered from the infection without incurring any costs on our system. On the first level, nodes that are informed of virus attacks have recovery rate σ 3 . Without loss of generality, we can say that the second virus V 2 is stronger than the first V 1 , and with the probability ε virus V 2 can supersede the first virus in the node infected by the first virus.

The application of antivirus patches reduces the number of the infected. It can be interpreted as control parameters by u 1 (t) and u 2 (t) in (1), where u i are the fractions of the infected under treatment, u 1 (t), u 2 (t) ∈ [0, 1], for all t. The warned nodes can avoid an epidemic by taking special quarantine measures. Control parameter u 3 (t) is the fraction of susceptible nodes that become warned of the virus spreading at time t.

In this section, the stability of the equilibrium points of the uncontrolled system is presented, where u i = 0, i = 1, 2, 3 (Capasso (1993) ; Allen (2008); Wu (2013); Sharma (2015)). The disease-free equilibrium is defined as the steady-state, where I 1 (t) = I 2 (t) = 0 for any t. Assume that I 1 (t) = I 2 (t) = 0, which means that the system is independent of the viruses, and we obtain simplified SWIRS-model:Ṡ

(2) By solving the system (2), we obtain two disease-free equilibrium points:

Local stability of the disease-free equilibrium points is verified by studying the real parts of eigenvalues p l of the Jacobian matrix at these points, i.e., Re p l ≤ 0 for all l (Capasso (1993) ).

1) Consider the first disease-free equilibrium point E 1 = (1, 0, 0, 0, 0). Define the Jacobian at this as Jac 1 :

This Jacobian has five eigenvalues p 1 = 0,

) are non-negative, equilibrium point E 1 will be asymptotically stable if the following conditions are hold: 2) For the second disease-free equilibrium point E 2 , the Jacobian Jac 2 has the following form

k . Jacobian matrix Jac 2 has five eigenvalues:

where q ∈ {1, 2} and

The following conditions define the stability disease-free equilibrium. Proposition 2. Equilibrium point E 2 will be asymptotically stable if the following conditions hold

In this subsection, the global stability of disease-free equilibrium E 0 (S, 0, 0, 0, R) is discussed. For this purpose, we use the following Lyapunov function: L(W, I 1 , I 2 ) = W + I 1 + I 2 .

(6) here function L(0) = 0 and L(·) ≥ 0 otherwise. The derivative of L(W, I 1 , I 2 ) with respect to the system (1) gives:

The disease-free equilibrium point is asymptotically stable if the derivative L(·)| (1) < 0. This condition is satisfied if the following conditions hold:

since variables W , I 1 , I 2 are nonnegative. Conditions (8) show that if the self recovery rates are higher than the infection rates, then the epidemics vanishes.

It is clear that the protection measures have their costs. Let the objective function J be the sum of two functionals, which correspond to the two levels of the model. On the first level, functional J 1 describes the costs of the quarantine measures, i.e. the costs of disseminating information about the epidemics to susceptible nodes. On the second level, functional J 2 defines the cost of antivirus treatment and includes the costs incurred by infected nodes, costs of spreading antivirus, and the benefit from the recovered nodes.

At any given t, f 1 (I 1 (t)), f 2 (I 2 (t)) are infection costs; L(W (t)) is the utility of the warned nodes. Function g(R(t)) defines the benefit rate for recovered nodes; functions h 1 (u 1 (t)), h 2 (u 2 (t)) are costs for antivirus treatments and h 3 (u 3 (t)) is cost of information spreading. Here functions f i (I i ) are non-decreasing and twice-differentiable, convex functions, f i (0) = 0, f i (I i ) > 0 for I i > 0, i = 1, 2, g(R) and L(W ) are non-decreasing and differentiable functions, and h i (u i (t)) is twice-differentiable and increasing function in u i (t) such as h i (0) = 0, h i (x) > 0, i = 1, 2, 3, when u i > 0. Also costs of information spreading are lower than costs for antivirus treatments h 3 (·) < h 1 (·) and h 3 (·) < h 2 (·).

The aggregated system costs over the time interval [0, T ] are defined as J = J 1 + J 2 , where

and the optimal control problem is to minimize these costs, i.e., min {u1,u2,u3} J.

By using Pontryagin's maximum principle (Pontryagin (1962)), we construct the optimal control u(t) = (u 1 (t), u 2 (t), u 3 (t)) to the problem described above in Section 2. To simplify the presentation, we use short-hand notations S, I 1 , u 1 , etc. in place of S(t), I 1 (t), u 1 (t), etc. Define the associated Hamiltonian H and adjoint functions λ S (t), λ W (t), λ I1 (t), λ I2 (t), λ R (t) as follows:

(10) The adjoint system is defined as follows:

with the transversality conditions given by

According to Pontryagin's maximum principle, there exist continuous and piece-wise continuously differentiable costate functions λ r (t), r ∈ {S, W, I 1 , I 2 , R} that satisfy (11) and (12) for t ∈ [0, T ] together with continuous functions u * 1 (t), u * 2 (t) and u * 3 (t): u2,u3∈[0,1] H(λ, S, W, I 1 , I 2 , R, u 1 , u 2 , u 3 ). (13)

In this subsection, we construct the structure of the optimal control u * (t) = (u * 1 (t), u * 2 (t), u * 3 (t)). Proposition 3. The following statements hold for the optimal control problem described in Section 2:

• When h i (·) are concave functions, then there exists t 0 ∈ [0, T ] such that for any i = 1, 2, 3 :

• When h i (·) are strictly convex functions, then there exist the time t 0 , t 1 , 0 < t 0 < t 1 < T such that for any i = 1, 2, 3 (α(t) ∈ (0, 1)):

We define functions ϕ i (t) as follows:

To prove Proposition 1, we consider the following auxiliary lemma.

Let's rewrite the Hamiltonian in terms of function ϕ i (t):

We can divide this maximization problem into three subproblems and find optimal control u * 1 (t), u * 2 (t) and u * 3 (t), separately. max u1,u2,u3

We obtain the following derivatives:

As h i (u i ) are increasing functions and I q ≥ 0 and S ≥ 0, then the Hamiltonian reaches its maximum if ψ i = h i (u i ) ≥ 0, i = 1, 2, 3. We can find such u i if and only if the following conditions are satisfied:

To complete the proof of proposition, we consider the auxiliary lemma.

Proof of the Lemma 1 is based on the following properties: Property 1: Let v(t) be a continuous and piece-wise differential function of t. Let v(t 1 ) = L and v(t) > L for all t ∈ (t 1 , . . . , t 0 ]. Thenv(t + 1 ) ≥ 0. Where v(t + 1 ) = lim x→t1+0 v(x).

Property 2: For any convex and differentiable function y(x), which is 0 at x = 0, y (x)x − y(x) ≥ 0 for all x ≥ 0.

We divide our proof into two parts. In the first part, we consider the case when t = T and show that derivatives of the functions λ R (t) − λ I1 (t), λ R (t) − λ I2 (t) and λ W (t) − λ S (t) are less or equal to zero to show that they are nonincreasing. In the second part, we use the method of proof by contradiction and show that on the whole interval [0, T ] these functions are also non-negative.

Step I. At time T , according to (12), we have that (11) it is obtained that all he derivatives are non-positivė

(18) Since g(·), f 1 (·), f 2 (·) and L(·) are increasing functions, at time T all functions are equal to 0 and their derivatives are less or equal to 0, then we can obtain that λ R (t) − λ I1 (t), λ R (t) − λ I2 (t) and λ W (t) − λ S (t) are non-increasing functions at t = T .

Step II. In this step, we show by contradiction that λ R (t) − λ I1 (t) ≥ 0 for all t ∈ [0, T ]. Proofs for the λ R (t) − λ I2 (t) and λ W (t) − λ S (t) use the same method and we will leave it to the readers.

The system of ODE (1) is autonomous, and, hence, the Hamiltonian and the control do not depend on the variable independent t. From (10), we obtain

(19) Suppose that there exists time moment t * ∈ (0, T ) at which λ R (t * ) − λ I1 (t * ) = 0. Using (19), consider the derivative of this function at the time moment t * + :

(20) From (10) and (21), we can obtain thaṫ

(21) Here, f 1 (I 1 ) is convex and differentiable function, from Property 2 and (19) we obtained thatλ R (t * + )−λ I1 (t * + ) ≤ 0, but according to our assumption the derivative should be greater or equal to zero. That leads to contradiction and completes the proof that λ R (t) − λ I1 (t) ≥ 0 for all t ∈ [0, T ]. Using the same method, we can prove that

Functions λ R (t) − λ I1 (t), λ R (t) − λ I2 (t) and λ W (t) − λ S (t) are non-negative at the interval [0, T ] and at t = T the derivatives of these functions are less or equal to 0 that completes the proof of the Proposition 4.

Functions h i (·) are concave Let h i (·) be a concave functions (h i (·) < 0), then according to (10) Hamiltonian is a convex function of u i , i = 1, 3. There could be two different options for u i ∈ [0, 1] that maximimize the Hamiltonian. If −h i (0) + ϕ i · 0 > −h i (1) + ϕ i · 1 or h i (1) > ϕ i , then optimal control -u i = 0 (Fig. 3  (right) ), otherwise -u i = 1 (Fig. 3 (left) ). For i = 1, 3, the optimal control parameters u i (t) are defined as follows: 

f 2 (I 2 (t)) = 40I 2 (t); treatment costs -h 1 (u 1 (t)) = 20u 2 1 (t), h 2 (u 2 (t)) = 25u 2 1 (t); vaccination cost -h 3 (u 3 (t)) = 10u 2 3 (t); and utility functions are L(W (t)) = 2W (t) and g(R(t)) = 5R(t). The time interval in the first two experiments is equal to [0,20]. , we can see that information spreading and applied treatment are beneficial. Fig. 6 represents the dependence of the total number of infected nodes I total throughout the epidemic process on the parameters k and σ 3 in the uncontrolled (left) and the controlled (right) cases, where I total = T 0 I 1 (t) + I 2 (t)dt. Fig. 6 . Dependence of the total number of infected nodes on parameters k and σ 3 .

In experiment II, we present the structure of the optimal control policies for the SWIR-model, when γ = 0. In this case, after the treatment, the recovered node will not be infected again during the contacts with infected nodes. The final state of the system is (0, 0, 0, 0.82, 0.18).

The aggregated system costs in the uncontrolled case are J unctrl = 8.63 (J 1 = −3.16 and J 2 = 11.79). In the controlled case, the aggregated system costs reduced to J ctrl = −12.89 (J 1 = −10.64 and J 2 = −2.25). Experiment III presents the SWIRS model on a metapopulation network, the behavior of the system (25) in two different clusters is represented in Fig. 8 . Initial parameters are X 1 (0) = (0.4, 0.4, 0.1, 0.1, 0) and X 2 (0) = (1, 0, 0, 0, 0). Matrices A=B show the strong connections between these clusters, hence the epidemics which has been started in the first cluster continues in the second one. Final states are X 1 (30) = (0.97, 0, 0, 0, 0.03) and X 2 (30) = (0.9, 0, 0.02, 0.02, 0.06).

This paper presents a modified Susceptible-Warned-Infected-Recovered-Susceptible (SWIRS) model of simultaneous spreading of the virus protection information and the malware over a large population of nodes. We have investigated the stability of SWIR and SWIRS epidemic models with two coexisting malware types for heterogeneous populations. We have obtained the structure of the optimal control as well as the properties of feasible controls for a special class of cost functions. Numerical examples have been used to corroborate the results. We would further explore the stability properties of the epidemic process under optimal control. Another future work includes the extension of the SWIR model to an epidemic model over complex networks with different topologies.

An introduction to stochastic epidemic models. Mathematical epidemiology

Optimal control of epidemic evolution

Multilevel Strategic Interaction Game Models for Complex Networks

A differential game approach to decentralized virus-resistant weight adaptation policy over complex networks

Achieving Social Optimum in Dynamic Weight Adaptation for Virus Mitigation: A Potential Differential Game Approach

Secure and reconfigurable network design for critical information dissemination in the internet of battlefield things (IoBT)

Modeling, analysis, and mitigation of dynamic botnet formation in wireless IoT networks

On a model of informational control in social networks

Ransomware: A new cyber hijacking threat to enterprises. Handbook of research on information security and assurance

Virus spread in Networks

Generalized groupbased epidemic model for spreading processes on networks: GgroupEM

What we know about Friday's massive east coast Internet outage. Wired Magazine

The Mathematical Theory of Optimal Processes. Russia: Interscience

Stability analysis and optimal control of an epidemic model with vaccination

Generalized epidemic meanfield model for spreading processes over multilayer complex networks

Structure of optimal control in the model of propagation of two malicious softwares

Optimal Impulsive Control of Epidemic Spreading of Heterogeneous Malware

Optimal Security Policy for Protection Against Heterogeneous Malware. Static and Dynamic Game Theory: Foundations and Applications

Optimal Control of Heterogeneous Mutating Viruses. Games

Epidemic processes in complex networks

Unification of theoretical approaches for epidemic spreading in complex networks

Superinfection Behaviors on Scale-Free Networks with Competing Strains

Epidemic Model with Isolation in Multilayer Networks

The research has been partially supported by the RSF grant No. 16-19-10609, U.S. National Science Foundation Awards ECCS-1847056, CNS-1544782, and SES-1541164, and grant W911NF-19-1-0041 from U.S. Army Research Office (ARO).

Functions h i (·) are strictly convex Let h i (·) be a strictly convex functions (h i (·) > 0), then Hamiltonian is concave function. Consider the following derivative:where x ∈ [0, 1], u * i (t) = x i . There could be three different types of points at which the Hamiltonian reaches its maximum (Fig. 4) . To find them, we need to consider the derivatives of the Hamiltonian at u i = 0 and u i = 1. If the derivatives (23) at u i = 0 are non-increasing (−h i (0)+ ϕ i ≤ 0), then the value of the control that maximizes the Hamiltonian is less than 0, and according to our restrictions (u i ∈ [0, 1]) optimal control will be equal to 0 (Fig. 4a ). If the derivatives at u i = 1 are increasing (−h i (1) + ϕ i > 0), it means that the value of the control that maximizes the Hamiltonian is greater than 1. Hence the optimal control will be equal to 1 (Fig. 4c) , otherwise, we can find such value u * i ∈ (0, 1) ( Fig. 4b) :In this case h i is strictly convex and h i is strictly increasing functions, so h (0) < h (1). Thus there exist points t 0 and t 1 (0 < t 0 < t 1 < T ) so that conditions (24) are satisfied, and according to ϕ i are decreasing functions. After obtaining the optimal control u * 1 (t) and u * 2 (t), we need to sort all infected nodes by the number of neighbors and treat them in order, starting with the first one on the list. Similar procedure is used to find the number of susceptible nodes, among which it is necessary to disseminate information about virus attacks, using the structure of the u * 3 (t).

The clustering of the nodes in the network can be considered as a natural extension of the SWIRS model from Section 2. We assume that all nodes inside the one cluster follow the same behavioral rules. However, the infection can be transferred among clusters. For this reason, we consider a case of a network with N nodes, which can be divided into several clusters. Here, the matrix A = {a τ µ } is the adjacency matrix of the first level of SWIRS model, where information about possible consequences of malware attacks is spreading, and B = {b τ µ } is the adjacency matrix of the second level, where special antivirus patches are applied. Denote as ka τ µ the probability that a node from cluster τ of size N τ and a node from a cluster µ of size N µ change their states from S to W at every time instant. The probability that a susceptible node from cluster τ will be infected due to the contact with a node from a cluster µ, infected by virus V l , l ∈ {1, 2} is equal to β S V l b τ µ . A warned node from cluster τ will be infected by virus V l , l = {1, 2} through the contact with the node from a cluster µ with probability β W V l b τ µ . Vector X j (t) = (S j (t), W j (t), I 1j (t), I 2j (t), R j (t)) defines the proportions distribution of being in each of the states for the cluster j = 1, . . . , M at t. For any t ∈ [0, T ], the sum of the probabilities for any node j is equal to S j (t) + W j (t) + I 1j (t) + I 2j (t) + R j (t) = 1. All other parameters in the system remain the same as in Section 3.1. This simultaneous process of information spreading and patching is described by a system of nonlinear differential equations:where l defines the sum from 1 to M . Initial states are (0) for all clusters j.The aggregated system costs on the time interval [0, T ] are defined as J = J 1 + J 2 , where ) and the optimal control problem is to minimize these costs, i.e., min {u1j ,u2j ,u3j } J.We focus on a case when both malware can cause extreme damages, and there is a need to lock down the entire system to prevent future destruction. To avoid this lockdown or other expensive security activity, we have to construct a constant control such that any malware will be instantly eliminated, even though the time when the viruses attack the system cannot be precisely identified. We assume thatWe have to define the condition for u which remains system in disease free state with minimum costs. We assume that h 1 (u 1j ) = h 2 (u 2j ) = h 3 (u 3j ) = u. The initial state of the system is the equilibrium point E 2 from the Section 3.2. (25) can be reformulated as:It is assumed that viruses can infect only one node at one time moment, then the system can be transformed in the following way:where m is a node which was infected by a virus. Inequalities (28) can be rewritten as u qj (0) ≥ (β S q S 0 j + β W q W 0 j )b jm − σ 1 , q = 1, 2.We find control strategies that maintain the disease free state in the the worst case of epidemics. This value provides an estimation on system costs when h j = u j (t) on the time interval [0, T ]. Summing the control parameters gives:where u ij (t) is the control of a type i ∈ {1, 2, 3} in a cluster µ at time t. As a result, we obtain