The cost optimal control system based on the Kermack–Mckendrick worm propagation model

Abstract

Although the network worm propagation models are able to predict trends in the spread of the worm, these papers did not consider the economic losses caused by the worm propagation. This paper uses the Hamiltonian approach of the optimal control theory and proposes the cost optical control system based on the Kermack–Mckendrick worm propagation model. In the cost optical control system, we control and process the infectious hosts. In this paper, we present an optimization model that takes into account infection cost and treatment cost. The simulation on the cost optical control system is carried out, and then the results of the analysis are given. In conclusion, the cost optical control system of the Kermack–Mckendrick model can provide the optical control of the worm propagating and effectively reduce the worm propagation with minimum cost.

Introduction

In recent years, under the high-speed network environment, the worms ¹ with a dramatic increase in the frequency and virulence of such outbreaks have become one of the major threats to the security of the internet. Each network worm outbreaks almost always lead to huge losses. Major events on the worm are listed as shown in Table 1.

Table 1.

Major events on the worm.

Name of the worm	Time	Losses
Morris worm	1988	The direct economic losses amounted to $96,000,000
Melissa worm	1999	The economic loss of over 1.2 billion dollars
LoveLetter	May 2000	The loss of more than 10 billion dollars
CodeRed	July 2001	The direct economic loss of over 2.6 billion dollars
WantJob	December 2001	Losses amounting to tens of billions of dollars
SQLexp	January 2003	The direct economic loss of over 2.6 billion dollars

Table 1 indicates that these worms create unnecessary network traffic and cause huge economic losses. The analysis, early warning and control of network worm propagation by human have become a hot research field of network security. Foreign scholars have undertaken extensive research on how to describe the worm propagation model. According to the famous American magazine “Science” article, many scholars by the large number of cases illustrated that the spread of computer viruses is similar to spread of the human disease model.^2–5 And then, many scholars analyzed the relationship between computer virus propagation theory and the theory of epidemics propagation. ⁶ On this basis, the improved traditional epidemiological model, i.e. Analytical Active Worm Propagation model is proposed, along with a description of the CodeRedII propagation model. ⁷ The flash worm propagation model is proposed, ⁸ and it has been optimized based on the SIS model, ⁹ and the P2P network worm propagation model has also been optimized. ¹⁰ In this paper, the optimal control theory is applied to the network worm propagation model system, and the cost optical control system based on the Kermack–Mckendrick (KM) worm propagation model is proposed. Through simulation and experiment, it is proved that this cost optimal control system has a favorable effect in controlling the spread of worms and reduces the total costs.

The rest of the paper is organized as follows. The following section analyzes the KM worm propagation model. The KM model is simulated by using MATLAB and the analysis is given. The next section presents a cost optimal control system that takes into account infection cost of the worm infection and the treatment cost of infected hosts for the price performance of the objective function in the Hamiltonian approach. The simulation of cost optimal control system and the analysis are given. The significance of the cost optimal control system in the control of worm propagation is analyzed. The final section gives the conclusion.

Analysis of the KM worm propagation model

Simple epidemic model (SEM) can be used to predict network worm initial propagation trends but cannot accurately predict the propagation of the internet worms,^11–13 because in the SEM, there are only two host state: susceptible and infected, and one state transmission: “susceptible → infection.” The man-made preventive measures, network congestion and other factors are not fully considered in the SEM worm propagation model, which is unscientific. Subsequent worm outbreak led to the repair of the system patches as well as other measures of prevention and immune isolation. So it is not suitable for the SEM to describe and reveal the correct trends in the spread of the worm. In KM model, the states of the host are “susceptible,” “infected” and “removed.” Infected host infects other susceptible host with the rate of infection. And infected host is removed to “removed” state with the removed rate. The KM model system is shown as follows

$\{\frac{dS(t)}{\mathrm{dt}}=-\beta S(t)[N-S(\text{t})-R(t)]\frac{\mathrm{dI}(t)}{\mathrm{dt}}=\beta I(t)[N-I(\text{t})-R(t)]-\gamma I(t)\frac{\mathrm{dR}(t)}{\mathrm{dt}}=-\gamma I(t)S(t)+I(t)+R(t)=N0\le S(t),I(t),R(t)\le NI(0)=I_0<<NR(0)=0S(0)=N-I(0)-R(0)$

(1)

And the variables in the KM model are detailed in Table 2.

Table 2.

Variable in the Kermack–Mckendrick model.

Variables	Explanation
S(t)	Number of susceptible hosts at time t
I(t)	Number of infection hosts at time t
R(t)	Number of removed hosts from the infected hosts at time t
N	Total number of hosts under consideration, N = S(t) + I(t) + R(t)
β	Infected rate: “susceptible(S) → infected(I)”
γ	Removal rate: “infected(I) → removed(R)”

According to the KM model, after a certain period of time T, all hosts are infected by the worm and some of the infected host is converted to “removed” state. That is S(T) = 0, I(T) = 0, R(T) ≠ 0 and R(T) < N. In the KM model, set N = 100, I(0) = 1, R(0) = 0, S(0) = N − I(0) − R(0), γ = 0.03, β in order be equal to 0.02, 0.04 and 0.06. According to the formula (1), the trend of the worm propagation in KM model with different infection rate is obtained by numerical simulation as shown in Figure 1.

Figure 1.

Simulation of worm propagation with different infection rate.

Set N = 100, I(0) = 1 of R(0) = 0, S(0) = NI(0) − R(0), the infection rate β and removal rate γ be 0.02 and 0.03, the simulation of the KM worm propagation model is obtained as shown in Figure 2.

Figure 2.

Simulation of the KM model with infection rate 0.02.

If we define ρ = γ/β as the relative removed rate, and replace the first equation in formula (1) with the second equation, we will get dI(t)/dt = βI(t)S(t) − γI(t). Both sides of the equation divided by β at the same time is

$\frac{\mathrm{dI}(t)}{\mathrm{dt}}>0,S(t)>\rho$

(2)

Because there will not be new susceptible hosts arising, S(t) is monotonically decreasing when t grows. If S(t₀) < ρ, when t > t₀, there are S(t) < ρ and dI(t)/dt < 0. In other words, if the initial number of susceptible hosts is less than a certain value, namely S(0) < ρ, then the vulnerable hosts will not get infected.

The KM model has improved the SEM, because the KM model considers the state: “infected → immune.” However, this model is still not perfectly suitable for modeling network worm propagation. First, the KM model only takes the infective hosts’ immunity into consideration and ignores the susceptible hosts’ immunity. Second, as people are paying more and more attention to worms, the immune hosts’ removed rate should be increasing with time, so it is not appropriate to take γ as a constant.

Research of the cost optimal control system based on the KM model

In this paper, we present a cost optimal control system that takes into account infection cost of the worm infection and cost of the artificially batch control of infected hosts for the price performance of the objective function in the Hamiltonian approach. And the target of the cost optical control system of the KM model is to provide the optical control of the worm propagating and effectively reduce the worm propagation with minimum cost.

Analysis of the worm propagation without cost optical control

According to the KM worm propagation model, the worm propagation function I(t) is as follows

$\frac{\mathrm{dI}(t)}{\mathrm{dt}}=\beta I(t)[N-I(\text{t})-R(t)]-\gamma I(t)$

(3)

And R(t) in the KM model is as follows

$\frac{\mathrm{dR}(t)}{\mathrm{dt}}=\gamma I(t)$

(4)

The solution to equation (3) is as follows

$I(t)=\frac{I(0)(\beta N-\gamma )}{I(0)\beta +(\beta N-\gamma -I(0)\beta )e^{-(\beta N-\gamma )t}}$

(5)

When time is t → ∞, the number of the worm propagation I(∞) could be obtained as follows

$I(\infty )=N-\frac{\gamma }{\beta }$

(6)

The N − γ/β ≠ 0 and N − γ/β > 0, because γ/β is a nonzero constant. That I(∞) means that when the worm propagates, susceptible hosts will not be completely infected.

Analysis of the worm propagation with cost optical control

Based on optimal control theory, through research and analysis on the existing KM worm propagation model, the cost optimal control system corresponding to the KM model is proposed. The cost optimal control system is based on optimal control theory and the KM model with adding an artificial control of the infected hosts. And the cost optimal control system adds the treatment of the infectious hosts and takes into account infection cost and treatment cost. We provide a new method in which the problem of the cost optimal control of worm propagation is solved by using the Hamiltonian approach in the optimal control theory. Experiments show that the cost optical control system of the KM model can provide the optical control of the worm propagating and effectively reduce the worm propagation with minimum cost.

In the process of worm propagation, suppose that we control a certain number of the infected host, such as immune, patches and other measures, making the status of the infected host directly into the immune status. But this man-made batch requires a lot of cost. The greater the number of the infected host which are controlled and treated, the higher costs corresponding to the process of handling infected host. Therefore, the number of infected hosts of the artificially batch control by us should be reasonable. In order to calculate the scientific number of hosts treated in the artificially batch control strategy, we proposed the cost optical control system based on the Hamiltonian approach in the optimal control theory. The “removed” state hosts will be divided into two parts: the host of man-made batch control and the other host in the “removed” state hosts without treated. Then the worm propagation function I(t) is as follows

$\frac{\mathrm{dI}(t)}{\mathrm{dt}}=\beta I(t)[N-I(\text{t})-R(t)]-\gamma (I(t)-Q(t))-C_{\text{Q}}Q(\text{t})$

(7)

where λ > γ > 0 and I(t) ≥ Q(t) ≥ 0. Let A(t) denote the number of infected hosts which are not controlled in the artificially batch control strategy, A(t) = I(t) − Q(t). Then the worm propagation function I(t) is as follows

$\frac{\mathrm{dI}(t)}{\mathrm{dt}}=\beta I(t)[N-I(\text{t})-R(t)]-\gamma Q(t)-C_{Q}Q(\text{t})$

(8)

When Q(t) = I(t), all the infected host can be controlled with the artificially batch control strategy. Change in the number of infected host differential equations is as follows

$\frac{\mathrm{dI}(t)}{\mathrm{dt}}=\beta I(t)[N-I(\text{t})-R(t)]-C_{Q}Q(\text{t})$

(9)

Supposing that the treatment of each infected host is valid, every host can get immunity. Then worm infection will be no longer popular, and this state is called equilibrium. With the artificially batch control strategy, the KM worm propagation model could reach equilibrium. The variables in the cost optimal control system are detailed in Table 3.

Table 3.

Variable in the cost optical control system.

Variables	Explanation
N	Total number of hosts under consideration, N = S(t) + I(t) + R(t)
S(t), S*(t)	Number of susceptible hosts at time t
I(t), I*(t)	Number of infection hosts at time t
R(t), R*(t)	Number of removed hosts from the infected hosts at time t
Q(t), Q*(t)	Number of infected hosts controlled by the artificially batch control strategy
A(t)	Number of infected hosts which are not controlled
β	Infected rate: “susceptible(S) → infected(I)”
γ	Removal rate: “infected(I) → removed(R)”
CQ	Success rate of an infectious host in the artificially batch control strategy
C(Q(t))	Control cost of Q(t) hosts in the artificially batch control strategy
A	Control cost of an infected host in the artificially batch control strategy
λ,λ*	Adjoint variable in the Hamiltonian approach

Analysis of the cost optimal control problems in the KM model

In order to get Q(t), number of infected hosts controlled in the artificially batch control strategy and in order to optimize the process and costs in the worm propagation, the formulation of cost objective function is necessary. In this paper, the cost factors in the worm propagation contain only two cost factors: the loss caused by worm propagation and the cost caused when the infected host is treated with the artificially batch control strategy. Then the cost objective function C(I(t),C(Q(t))) of the cost optimal control system is shown as follows

$C(I(t),C(Q(t)))={\int }_0^T[C_{I}I(t)+C(Q(t))]\text{d}t$

(10)

Based on optimal control theory, the state equation of the cost optimal control system of the worm spread is as follows

$\frac{\partial I(t)}{\partial t}=\beta I(t)[N-I(\text{t})]-\gamma (I(t)-Q(t))-C_{Q}Q(\text{t})$

(11)

The system boundary conditions are

$\{I(0)=I_0;0\le Q(t)\le I(t)$

(12)

The cost optimal control system is to solve the problem: reducing and controlling the spread of the worm infections; making the cost objective function of the cost optimal control system C(I(t),C(Q(t))) to obtain the minimum and the cost of the system be less than the cost of the common KM worm propagation model; and simulating the trend of the control function Q(t).

Analysis of the cost optimal control system based on the KM model

Cost optimal control problem based on KM is a variation problem of equation of state constraints (equality constraints). In this case, we use Lagrange multiplication method to convert the variation equation of state constraints (equality constraints) to solve the extremism problem of the Hamilton (Hamilton) function H. This method is also called the Hamiltonian method.

The Hamilton (Hamilton) function H(I(t), Q(t), λ(t)) in this cost optimal control system is as follows

$H=C(I(\text{t}),\text{Q}(\text{t}))+\lambda (\text{t})\frac{\partial I(\text{t})}{\partial t}$

(13)

Equation (13) can also be expressed as follows

$H=C_{I}I(t)+C(Q(t))+\lambda (t)\mathrm{\hspace{1em}\hspace{1em}\hspace{1em}}\times [\beta (N-I(t))-\gamma (I(t)-Q(t))-C_{\text{Q}}Q(t)]$

(14)

In order to obtain the minimum of the cost objective function C(I(t),C(Q(t))), the minimum of the Hamilton (Hamilton) function H(I(t), Q(t), λ(t)) should be obtained. The adjoin equation in the Hamiltonian method should be proposed. The adjoin equation in the cost optimal control problem based on the KM model is shown as follows

$\frac{\partial \lambda (t)}{\partial t}=-\frac{\partial H(I(t),Q(t),\lambda (t))}{\partial I(t)}$

(15)

Equation (15) equals

$\frac{\partial \lambda (t)}{\partial t}=-C_I-\lambda (t)[N\beta -2\beta I(t)-\gamma ]$

(16)

The state equation of the worm propagation for the cost optimal control problem is as follows

$\frac{\partial I(t)}{\partial t}=\frac{\partial H(I(t),Q(t),\lambda (t))}{\partial \lambda (t)}$

(17)

Equation (17) equals

$\frac{\partial I(t)}{\partial t}=[-C_I-\lambda (t)[N\beta -2\beta I(t)-\gamma ]]\mathrm{\hspace{1em}\hspace{1em}\hspace{1em}}\times [\beta (N-I(t))-\gamma (I(t)-Q(t))-C_{\text{Q}}Q(t)]$

(18)

The governing equation of the worm propagation for the cost optimal control problem is as follows

$\frac{\partial H(I(t),Q(t),\lambda (t))}{\partial Q(t)}=0$

(19)

Equation (19) equals

$C\text{'}(Q(t))-\lambda (t)(\gamma -C_Q)=0$

(20)

where C′(Q(t)) is the C(Q(t))′ derivative function, set C′(Q(t)) = a*Q(t), the coefficient “a” is a nonzero constant and denotes control cost of an infected host in the artificial batch control strategy. According to the state equation of this system, the adjoin equation and the governing equation, the adjoin vector of the Hamiltonian method can be obtained as follows

$\frac{\text{d}{\lambda }^{*}(t)}{\mathrm{dt}}={\lambda }^{*}(t)(2\beta I^{*}(t)-N\beta +\gamma )-C_I$

(21)

And the cost optimal control system based on the KM worm propagation model is proposed as follows

$\{\frac{{\mathrm{dI}}^{*}(t)}{\mathrm{dt}}=\beta I^{*}(t)(N-I^{*}(t))-\gamma I^{*}(t)-\frac{(C_Q-\gamma {)}^2}{a}{\lambda }^{*}(t)\frac{\text{d}{S}^{*}(t)}{\mathrm{dt}}=-\beta I(t)(N-I(t))\frac{{\mathrm{dR}}^{*}(t)}{\mathrm{dt}}=\gamma I^{*}(t)Q^{*}(t)=\frac{(C_Q-\gamma )}{a}{\lambda }^{*}(t)I^{*}(0)=I_0{Q}^{*}(0)=R^{*}(0)=0,S^{*}(0){=\text{N}-\text{I}}^{*}(0){-\text{Q}}^{*}(0){-\text{R}}^{*}(0)$

(22)

Equation (22) is the cost optimal control system based on the Hamiltonian method and the KM worm propagation model. The results R*(t), S*(t), I*(t) and Q*(t) are calculated by Runge–Kutta algorithm. The next section will give the comparative analysis between this cost optimal control system and the common KM worm propagation model system by the numerical simulation.

Simulation of the cost optimal control system

Comparison of the cost J*(t) with the cost J(t)

Let J*(t) be the cost of the cost optimal control system, and J(t) be the cost of the common KM worm propagation model. In general KM worm propagation model, set N = 100, I(0) = 1, R(0) = 0, S(0) = N − I(0) − R(0) and the infection rate β = 0.02. And in the cost optimal control system based on the KM worm propagation model, set N = 100, I(0) = 1, R(0) = 0, S (0) = N − I(0) − R(0), the infection rate β = 0.02 and C_Q = 0.02. The comparison of the cost of the cost optimal control system with the cost of the common KM model is shown in Figure 3.

Figure 3.

Comparison of the cost J*(t) and J(t).

By analysis and comparison, the cost J*(t) of the cost optimal control system is less than the cost J(t) of the common KM worm propagation model. This system could make the cost objective function C(I(t), C(Q(t))) to obtain the minimum. And the cost of the system is less than the cost of the common KM worm propagation model.

Comparison of I*(t) with I(t).

Let I*(t) be the worm propagation equation in the cost optimal control system, and I(t) be the worm propagation equation in the common KM worm propagation model. In general KM worm propagation model, set N = 100, I(0) = 1, R(0) = 0, S(0) = N − I(0) − R(0) and the infection rate β = 0.02. And in the cost optimal control system based on the KM worm propagation model, set N = 100, I(0) = 1, R(0) = 0, S(0) = N − I(0) − R(0), the infection rate β = 0.02 and C_Q = 0.02. The comparison of the cost of the cost optimal control system with the cost of the common KM model is shown in Figure 4.

Figure 4.

Comparison of the worm propagation I*(t) and I(t).

By analysis and comparison, the worm propagation I*(t) of the cost optimal control system is less than the worm propagation I(t) of the common KM model. This system could also control the spread of the worm. And it is more effective than the common KM model. The cost optimization control system based on the KM propagation model could better control the spread of the worm with less cost than the common KM model.

Simulation of trends in the spread of the cost optimal control system with different rate C_Q.

In the cost optimal control system based on the KM worm propagation model, set N = 100, I(0) = 1, R(0) = 0, S(0) = N − I(0) − R(0), the infection rate β = 0.02 and C_Q in order be equal to 0.02 and 0.04. The comparison of the trend of the spread of the cost optimal control system with different C_Q is shown in Figures 5 and 6.

Figure 5.

Simulation of the cost optimal control system based on the KM model with C_Q = 0.02.

Figure 6.

Simulation of the cost optimal control system based on the KM model with C_Q = 0.04.

By analysis and comparison of the simulation of the cost optimal control system based on the KM model with C_Q = 0.02 and the simulation with C_Q = 0.04, the following conclusions are obtained: the bigger C_Q is, the higher the controlling effect is; if appropriate big human batch controlling rate, the system could more effectively control the spread of the worm.

In real life, the number of the controlled infectious hosts can be obtained by the Q*(t) in the cost optimal control system. At this time, we can achieve effective control of worm propagation effect and also make minimum economic losses caused by the worm infecting and propagating.

From the above simulation and analysis, the correctness and reasonability of the cost optimal control system based on the KM model is proved.

Conclusion

The cost optimal control system proposed in this paper is based on optimal control theory and the KM model with adding an artificial control of the infected hosts. And the cost optimal control system takes into account infection cost of the worm infection and the treatment cost of the artificially batch control of infected hosts. The reasonability and correctness of the model are proved through the simulation and experiment. Through analyzing and comparison of the simulation of the system with the common KM model, it can be concluded that the cost optimal control system could also control the spread of the worm. And it is more effective than the common KM model. The cost optimization control system could keep perfect control of the spread of the worm with less cost than the common KM model.