Using Event-Based Method to Estimate Cybersecurity Equilibrium

Zhaofeng Liu, Ren Zheng, Wenlian Lu, and Shouhuai Xu

Abstract—Estimating the global state of a networked system is an important problem in many application domains. The classical approach to tackling this problem is the periodic (observation)method, which is inefficient because it often observes states at a very high frequency. This inefficiency has motivated the idea of event-based method, which leverages the evolution dynamics in question and makes observations only when some rules are triggered (i.e., only when certain conditions hold). This paper initiates the investigation of using the event-based method to estimate the equilibrium in the new application domain of cybersecurity, where equilibrium is an important metric that has no closed-form solutions. More specifically, the paper presents an event-based method for estimating cybersecurity equilibrium in the preventive and reactive cyber defense dynamics, which has been proven globally convergent. The presented study proves that the estimated equilibrium from our trigger rule i) indeed converges to the equilibrium of the dynamics and ii) is Zeno-free,which assures the usefulness of the event-based method.Numerical examples show that the event-based method can reduce 98% of the observation cost incurred by the periodic method. In order to use the event-based method in practice, this paper investigates how to bridge the gap between i) the continuous state in the dynamics model, which is dubbed probability-state because it measures the probability that a node is in the secure or compromised state, and ii) the discrete state that is often encountered in practice, dubbed sample-state because it is sampled from some nodes. This bridge may be of independent value because probability-state models have been widely used to approximate exponentially-many discrete state systems.

I. INTRODUCTION

ESTIMATING the global state of a networked system at any point in time is of fundamental importance in many application domains. This is because the real-time global state allows an engine (or administrator) to make prompt decisions.The classical approach to obtaining the global state of a networked system is the periodic method, which observes the state of every node in the networked system at every point in time (at an appropriate time resolution). Fig.1 illustrates a networked system of n nodes and a time interval [t1,tm] at a certain time resolution. In order to estimate the global state of the networked system at time t1,...,tm, the periodic method requires the observation of every node’s state at every point in time, leading to nm observations (or operations) in total.

Fig.1. Illustration of the advantage of the event-based method over the classical periodic (observation) method. The latter observes the state of every node at every point in time t1,...,tm (i.e., incurring nm observation events in total). The former only observes the state of some nodes at some points in time, which are highlighted with filled circles, meaning that the former incurs a much smaller (than nm) number of observations.

The nm complexity mentioned above has motivated the event-based method [1], [2]. The key idea underlying this method is to leverage the state evolution dynamics. As illustrated in Fig.1, this method only observes the state of some nodes at some points in time, effectively achieving“observation on demand” and incurring a much smaller number (than nm) of observations. While intuitive, the eventbased method is not always effective because it may fall victim to the so-called Zeno behavior [3], which renders it useless by incurring infinitely many observations within a finite period of time. Therefore, an event-based method must be proven Zeno-free.

A. Our Contributions

This paper initiates the investigation of adapting the eventbased method to the cybersecurity domain. In this domain, the global cybersecurity state of a network is a basic input for making effective, if not optimal, cyber defense decisions, such as whether to impose new cybersecurity restrictions or not.The paper investigates how to estimate the cybersecurity equilibrium in the context of preventive and reactive cyber defense dynamics, which is a particular kind of cybersecurity dynamics (and will be reviewed later). The dynamics have been proven globally convergent in the entire parameter universe (i.e., the dynamics always converge to a unique equilibrium for any possible initial state) [4]. Despite this exciting progress, one important problem is left unaddressed:How to estimate the equilibrium efficiently without knowing the value of every model parameter? Since the periodic observation method is inefficient (especially for large networks), the presented paper proposes adapting the eventbased method to estimate the cybersecurity equilibrium in the preventive and reactive cyber defense dynamics.

Specifically, this paper proposes an active event-based method for estimating the cybersecurity equilibrium and proves that the method is Zeno-free (i.e., it does not fall victim to the Zeno behavior). Numerical examples show that our eventbased method can reduce 98% of the observation cost when compared with the periodic method. In order to show how to use this event-based method in practice, we investigate how to bridge the gap between i) the continuous state in the dynamics model, which is dubbed probability-state because it measures the probability that a node is in the secure or compromised state, and ii) the discrete state that is often encountered in practice, dubbed sample-state because it is sampled from some nodes at some points in time. This bridge may be of independent value because probability-state models have been widely used to approximate discrete state systems with exponentially-many discrete states (incurred by a state-space explosion [5], [6]).

B. Related Work

The event-based method has been investigated in many application settings other than cybersecurity, such as sampling for stochastic systems [7], stabilizing control [8], self-triggered control [9], and set-membership filtering (SMF) [10]. A core research problem is to show that the method does not fall victim to the Zeno behavior (see, for example, [8], [11]–[19]),which can render the event-based method useless by imposing infinitely many observation events within a finite period of time and can prevent the estimated dynamics from converging [3].

To the best of the authors’ knowledge, the presented study is the first to introduce the idea of event-based sampling into the cybersecurity domain. This is made possible by a recent breakthrough showing that a certain class of cybersecurity dynamics is globally convergent in the entire parameter universe [4], a characterization that was not proven until 10 years after the model was first introduced in [20]. The notion of cybersecurity dynamics [5], [6] was introduced to model and analyze cybersecurity from a whole-network perspective.This notion, as discussed in [5], [6], has roots in earlier studies in biological epidemiology (e.g., [21]–[25]) and its variants in cyber epidemiology (e.g., [26]–[36]), interacting particle systems [37], and microfoundation in economics [38]. This notion has opened the door to a new research field with many results (e.g., [39]–[50]).

However, the previous studies leave one important question unaddressed: How can one quantify the equilibrium in the real-world when the values of some model parameters are not known? This paper will fill the lacuna by showing that the event-based method can be naturally adapted to tackle this problem in the context of preventive and reactive cyber defense dynamics, which is globally convergent in the entire parameter universe [4]. Special cases of this dynamic are(partially) characterized in previous studies such as [33]–[36],[48], which mostly focus on the epidemic threshold, namely a condition under which the dynamics will converge to the equilibrium zero (i.e., a special equilibrium that does not need to be estimated). In the cybersecurity domain, the notion of epidemic threshold is less relevant because the dynamics rarely “die out”, which is inherent to the nature of the dynamics (e.g., computers can become compromised by means other than infection, contrary to biological dynamics).

The estimation of equilibrium has been explored in a smaller parameter regime [48], within which the dynamics were known to be convergent while certain parameters were specified (i.e., the structure of the global attack-defense graph,which will be elaborated later). In contrast, the presented paper investigates how to estimate the cybersecurity equilibrium in the entire parameter universe, making results applicable to broader scenarios. This is made possible by the theoretical result that the dynamics are globally convergent in the entire parameter universe [4].

It is worth mentioning that the preventive and reactive cyber defense dynamics are particular kinds of cybersecurity dynamics for quantifying cybersecurity from a holistic perspective [51]–[55]. There are other kinds of cybersecurity dynamics, which aim to accommodate adaptive defenses [45],active defenses [56]–[58], and proactive defenses [43].Adapting the event-based method to these kinds of dynamics is an important open problem for future research.

C. Paper Outline

In Section II, the paper briefly reviews the preventive and reactive cyber defense dynamics model and its global convergence in the entire parameter universe [4]. In Section III, an event-based method for estimating the equilibrium is presented. Section IV involves a discussion on how to apply this event-based method in practice by bridging the gap between the probability-state in the theoretical model and the sample-state in practice. Section V concludes the paper with open problems and further research topics.

II. PROBLEM STATEMENT

A. Review of Preventive and Reactive Defense Dynamics

The idea of a preventive and reactive cyber defense dynamics model was first introduced in [20] and partially analyzed in [48], while noting that its special cases were studied earlier in [33]–[35]. However, all these studies only contribute a partial understanding of the dynamics corresponding to a special parameter regime rather than the entire parameter universe. Very recently, it is proven that these dynamics are globally convergent in the entire parameter universe, meaning that there is always a unique equilibrium[4], whose exact value (or position) depends on the parameter values rather than the initial state of the dynamics.

In the dynamics model, the defender employs two classes of defenses:

1) Preventive Defenses: These correspond to the use of intrusion prevention tools to block cyber attacks before they reach a target or before they can cause any damage.

2) Reactive Defenses: These correspond to the use of antimalware tools to detect compromised computers and then clean them up.

On the other hand, the attacker wages two kinds of attacks:

1) Push-based Attacks: These correspond to the use of computer malware to spread across the network.

2) Pull-based Attacks: These correspond to the use of compromised or malicious websites to attack browsers when vulnerable browsers visit those malicious websites.

The model abstracts the attack-defense interaction taking place over an attack-defense graph structure G=(V,E), where V is the vertex set representing computers and (u,v)∈E means computer u can wage push-based attacks against computer v directly (i.e., the communication from u to v is allowed by the security policy). This means that G is, in general, different from the underlying physical network structure because(u,v)∈E may represents a variety of communication paths(rather than a single physical link), and that G can be derived from the security policy of a networked system and the physical network in question. The presented study does not make any restrictions on the structure of G; for example, G may be directed or undirected. Let A=[avu]n×ndenote the adjacency matrix of G, where avu=1 if and only if (u,v)∈E.Since the model aims to describe the attacks between computers, we set avv=0. Let deg(v) be the degree of node v ∈V when G is undirected or the in-degree of v when G is directed,where deg(v)=|Nv| with Nv={u ∈V: (u,v)∈E}.

The dynamics can equally be described with either a continuous-time model or a discrete-time model [4]. The presented paper focuses on the continuous-time model. At any point in time, a node v ∈V is in one of two states: “0” means secure but vulnerable, whereas “1” means compromised. Let sv(t) denote the probability that v is secure at time t and iv(t)denote the probability that v is compromised at time t. Note that sv(t)+iv(t)=1 for v ∈V and for t ≥0; thus, these terms interchangeably describe the probability-state of a given computer.

Fig.2 describes the state-transition diagram for a node v ∈V at time t, where θv,1→0(t) abstracts the effectiveness of the reactive defenses and θv,0→1(t) abstracts the capability of attacks against the preventive defenses. Let β ∈(0,1] be the probability that a compromised computer changes to the secure state because the attacks are detected and mitigated up by the reactive defenses. Then, θv,1→0(t)=β. On the other hand, θv,0→1(t) is more inclusive because it accommodates both push-based and pull-based attacks. In order to model the power of pull-based attacks against the preventive defenses,let α ∈[0,1] denote the probability that a secure computer becomes compromised despite the presence of the preventive defenses (i.e., the preventive defenses are penetrated by the pull-based attacks). In order to model the power of push-based attacks against the preventive defenses, let γ ∈(0,1] denote the probability that a compromised computer u wages a successful attack against a secure computer v despite the preventive defenses (i.e., the preventive defenses are penetrated by push-based attacks), where (u,v)∈E. Under the assumption that the attacks are waged independently of each other, it holds that

Fig.2. The state-transition diagram of any v ∈V that leads to a nonlinear Dynamical System with the nonlinear term θv,0→1(t), as shown in (1).

The preceding discussion leads to the following continuoustime nonlinear dynamical system for v ∈V:

The dynamics can be rewritten as a system of n nonlinear equations for v ∈V

The global convergence of system (2) presented in [4] can be summarized as follows:

1) If the attacker wages both push-based and pull-based attacks (i.e., α>0), system (2) is globally convergent in the entire parameter universe and the dynamics converge to a unique nonzero equilibrium exponentially.

2) If the attacker only wages push-based attacks (i.e.,α=0), system (2) is still globally convergent in the parameter universe but the convergence speed depends on the model parameters and the largest eigenvalue λA,1of adjacency matrix A is as follows:

a) If λA,1<β/γ, the dynamics converge to equilibrium 0 exponentially (see also [35], [48]).

b) If λA,1=β/γ, the dynamics converge to equilibrium 0 polynomially.

c) If λA,1>β/γ, the dynamics converge to a unique nonzero equilibrium exponentially.

This leads to:

Lemma 1 [4]: System (2) converges exponentially when α>0 and when α=0 and λA,1≠β/γ.

It is worth mentioning that the results also hold for the more general setting with node-dependent parameters αvand βvand e dge-dependent parameter γuv[4].

B. Problem Statement: Estimating Cybersecurity Equilibrium

Even though system (2) has been proven globally convergent in the entire parameter universe, there is no analytic result on the value of the equilibrium, which remains a hard

TABLE I NOTATIONS USED THROUGHOUT THE PAPER

problem (except for special cases, such as the aforementioned equilibrium 0). As discussed previously, the periodic method may be used to estimate the equilibrium, but in many cases,this is too costly. This observation reiterates the purpose of this paper, which is to investigate the use of an event-based method as an alternative. This paper focuses on estimating the equilibrium in the parameter regime where System (2)converges exponentially, namely when α>0 (i.e., there are pull-based attacks) or when α=0 (i.e., there are no pull-based attacks) but λA,1≠β/γ, as shown in Lemma 1. The paper leaves it to future works to address the special parameter regime α=0 and λA,1=β/γ, where the dynamics converge polynomially; as the techniques used in the presented paper are applicable to exponential convergence but not polynomial convergence.

C. Notations

III. AN EVENT-BASED METHOD

In this section, the paper proposes an event-based method for estimating the cybersecurity equilibrium of system (2) and analyzes its properties, including Zeno-freeness. Then, the method is adapted to accommodate the practical case where state observations are not conducted arbitrarily but conducted at predetermined points in time.

A. Designing Event-based Trigger Rule

Fig.7. Correlation between the false-negative rate in the sample-state observation and the bias of the equilibrium estimation.

V. CONCLUSION

This paper has shown how to use the event-based method to estimate the equilibrium of preventive and reactive cyber defense dynamics. Numerical examples confirmed that the event-based method can estimate the equilibrium while reducing 98% of the state observation cost incurred by the periodic method. The paper also spots an empirical phenomenon that the slower the convergence of the dynamics, the more observation cost is saved by the event-based method.Moreover, the presented study probed into the practical use of the event-based method, by bridging the gap between the probability-state in the theoretical model and the sample-state in practice, which may be of independent value.

There are many open problems for future research, such as:What is the lower-bound observation cost of an event-based method? Do there exist better, or even optimal, forms of event-based methods? How can the aforementioned empirical phenomenon (that the slower the convergence, the more observation cost is saved) be rigorously proven (or disproven)? Can other models cope with the case of polynomial convergence speed of a system (2)? Can other models handle situations where the observation errors are indeterminate (e.g.,when only the upper or lower bound of the false negative rate are known)? Can the presented method be applied to other dynamics under different event-trigger scenarios? Can other event-based methods be designed for cybersecurity dynamics models [41], [44], [47] that do not make the current assumption of dynamics independence?

ACKNOwLEDGMENT

We thank Zongzong Lin for his constructive advice on improving the proof of this paper. We thank Eric Ficke and Yihan Xu for proofreading the paper.