MULTI-STEP ATTACK DETECTION VIA BAYESIAN MODELING UNDER MODEL PARAMETER UNCERTAINTY

ABSTRACT

Organizations in all sectors of business have become highly dependent upon information systems for the conduct of business operations. Of necessity, these information systems are designed with many points of ingress, points of exposure that can be leveraged by a motivated attacker seeking to compromise the confidentiality, integrity or availability of an organization’s information assets. To protect its assets, an organization needs to implement information security controls that mitigate the risks associated with these techniques. One of the key controls available to an organization today is the intrusion detection system (IDS), which is used to detect specific events associated with unauthorized or suspicious activity. Traditional IDS systems have two limitations that this research addresses. First, most IDS systems are tuned to detect specific attacks, but do not attempt to automatically reason across multiple attacks. Such emphasis on “single-step” attacks, as opposed to “multi-step” attacks puts the entire burden of reasoning across multiple steps of a potential attack on the security analyst. Second, traditional IDS systems do not explicitly consider uncertainty, which limits the analyst’s ability to model situations in which uncertainty might be a significant factor.

This research examines the issue of multi-step attack detection in the presence of uncertainty in order to provide guidance to practitioners regarding the design and implementation of intrusion detection systems. First, we consider the bounding of uncertainty in a linear Bayesian model of multi-step attacks. In this work we outline a tradeoff between uncertainty and latency in the multi-step case: low inference uncertainty can be achieved but only at the price of latency in terms of the attack stage at which uncertainty levels become small. Next, we consider the problem of detection in a general attack topology. In this work, we show how to formulate queries for general definitions of intrusion and how to propagate parameter uncertainty through the model to a query result. In the case of zero parameter uncertainty, we provide an efficient algorithm to enumerate useful operating points within the 2-dimensional design space of detection rate x false positive rate. For the uncertain parameter case, we show how operating points become 2-dimensional operating boxes and show that the general problem of operating box enumeration is highly computationally complex, necessitating heuristic solutions. Next, we return our focus to the linear attack topology and theoretically show specific cases under which model parameter uncertainty cannot produce output uncertainty. Finally, we conduct experiments evaluating two heuristic solutions to the general detection problem under uncertainty, heuristics based on our theoretical results. We show that a heuristic solution based on our operating point enumeration algorithm provides results very close to those of full enumeration. Additionally, our experimental results show the significance of uncertainty in the multi-step attack detection cases considered, illustrating the importance of considering uncertainty when designing detection systems in the multi-step case.

Chapter 1

Introduction

1.1.     Research Problem

Organizations in all sectors of business have become highly dependent upon information systems for the conduct of business operations. Of necessity, these information systems are designed with many points of ingress, points of exposure that can be leveraged by a motivated attacker seeking to compromise the confidentiality, integrity or availability of an organization’s information assets. The vulnerability of information systems was first demonstrated on a large scale in 1988 with the Morris Worm attack [1] which infected Sun Microsystems Sun 3 and VAX hosts running version of 4 BSD UNIX by exploiting a variety of software flaws. Following the Morris Worm, the Code Red [2] worm in 2001 infected 359,000 hosts in less than 14 hours and the Slammer [3] worm in 2003 infected 90% of vulnerable hosts within 10 minutes, demonstrating the incredible scale of the risks involved with operating vulnerable systems. Recent cyber attacks include the Stuxnet worm attack against Iran which is believed to have been engineered by a collaboration of nation states as an alternative to a conventional military attack [4] , “Operation Payback” by the hacker group Anonymous which launched distributed denial of service (DDoS) attacks against several financial companies for ideological reasons [5] and a variety of attacks against social networking sites, such as the 2012 attack against LinkedIn [6] in which millions of passwords were stolen and then shared in the hacker underground.

Cyber attacks are perpetrated through a wide variety of technical techniques in addition to non-technical means, such as social engineering approaches that target the human element of the information system. To protect its information assets, an organization needs to implement information security controls that mitigate the risks associated with these techniques. One of the key controls available to an organization today is the intrusion detection system (IDS), which is used to detect specific events associated with unauthorized or suspicious activity and issue an alert to an analyst who then has the responsibility for interpreting the alert and deciding how to respond.

Traditional IDS systems have two limitations that this research addresses. First, most IDS systems are tuned to detect specific attacks, such as a buffer overflow attack against a web server, but do not attempt to automatically reason across multiple attacks. Such emphasis on “singlestep” attacks, as opposed to “multi-step” attacks puts the entire burden of reasoning across multiple steps of a potential attack on the security analyst. Second, traditional IDS systems do not explicitly consider uncertainty, which limits the analyst’s ability to model situations in which uncertainty might be a significant factor.

The goal of this research is to address these limitations by assisting the analyst in detecting multi-step attacks in the presence of uncertainty. To accomplish this goal, we provide the analyst with new tools. These include: a general attack modeling approach which incorporates uncertainty in system and environmental parameters and which can propagate uncertainty through to an inference result, a systematic approach to detection in the face of uncertainty incorporating a heuristic solution and guidance regarding expected results in various situations based on experimental findings.

The conceptual approach to multi-step detection is presented in Figure 1.1-1. This diagram shows three elements: enterprise observables, a set of N sensors and an alert processing node. The enterprise observables and N sensors represent the traditional elements of intrusion detection. The former includes all of the various observable events within an enterprise for which a sensor might be designed to detect an intrusion event, such as a sequence of system calls in the execution of a particular process on a particular host, or the payload contents of a network packet.

Traditional IDS systems include these two elements and a management console which may aggregate alerts and provide visualization assistance to the analyst but which does not typically provide explicit analyst support for interpreting alerts in the context of multi-step attacks.

The design of the alert processing node of Figure 1.1-1 is the subject of this thesis. It processes the output of sensors (i.e. individual alerts) and issues system-level alerts, a process referred to here as system-level detection. The alert processing node issues system-level alerts according to the logic illustrated in Figure 1.1-2. Based on a domain model and an intrusion definition, a detection set is determined. This detection set defines the set of sensor output vectors (observables) that will trigger a system-level alert, i.e. if the set of N sensor outputs matches a member of the detection set, then a system-level alert is issued. Note that the scope of this thesis only includes algorithm design aspects of the alert processing node, i.e. the algorithms necessary for its function; the alert processing node itself was not implemented as part of this thesis.

The alert processing approach described above considers the impact of model parameter uncertainty, as will be explained in detail in subsequent chapters. To illustrate the potential benefits of this approach, consider the following hypothetical example. Suppose an organization analyzes its costs of responding versus not responding to a particular intrusion and obtains the following cost function:

		Intrusion Has Occurred?
		YES	NO
Attack Response?	YES	C1	C2
	NO	C3	C4

 

The expected costs under such a cost function depend on the system-level true positive rate, the system-level false positive rate and the prior probability of attack. Figure 1.1-3 shows the resulting (normalized) costs in the 2-dimensional parameter space of system-level true positive rate x system-level false positive rate. In this figure, costs are represented as a color map with white representing minimum cost, black representing maximum cost and shades of gray representing intermediate costs. In this example, the following values were used: C1=5, C2=10; C3=100 and C4=4 along with a probability of intrusion of 0.01. These costs were chosen to reflect a hypothetical scenario in which the cost of a missed detection was very high. The analyst’s goal in this scenario is to minimize overall operating costs. Suppose a security analyst models the intrusion scenario and determines a set of potential system operating configurations, two of which are shown in Figure 1.1-3. Because point E1 resides in a lower cost region of Figure 1.1-3, the analyst will choose operating configuration 1 for system operation. If the analyst’s estimates are accurate, this will be the optimum choice.

E1

E2

Figure 1.1-3. Estimated Operating Points

Suppose, however, that the analyst’s estimates are inaccurate because uncertainty in the intrusion scenario was not modeled. In this case, the location of the true operating points associated with operating configurations 1 and 2 might differ significantly from the estimates. Using the approach presented in this thesis, the analyst instead would have been able to obtain imprecise estimates of system operating points, represented as boxes as shown in Figure 1.1-4. These boxes contain the (unknown) true points associated with the system operating configurations. Suppose, hypothetically that the true points associated with operating configurations 1 and 2 are T1 and T2, respectively, as shown in the figure. If these true points were known to the analyst, operating configuration 2, instead of 1 would be selected by the analyst. Presumably, for the analyst who does not model uncertainty, this discrepancy will eventually be discovered once the system has been operational for a significant amount of time and the observed true/false detection rates are found to disagree from the expected rates.

B1

B2

E1

E2

T1

T2

Figure 1.1-4. Operating Boxes

Benefits of the Proposed Approach

Using the approach proposed in this thesis, however, the analyst can achieve benefits over the conventional approach described above. First, the boxes resulting from the uncertainty modeling immediately alert the analyst to the significant ambiguity in the choice between operating configurations 1 and 2. This knowledge may motivate the analyst to employ uncertainty reduction efforts, such as imposing more stringent requirements during the sensor acquisition or design phase of system development with the result that the boxes will shrink as uncertainty is removed, eventually being reduced down to points corresponding to the true points T1 and T2. The resulting benefit is that the analyst will have selected operating configuration 2 at the outset, rather than adopting it much later. Of course, to realize this benefit, the organization must employ uncertainty reduction efforts which themselves will impose a cost. Rather than accept the costs of uncertainty reduction, however, the organization has a second option regarding the handling of the ambiguity between operating configurations 1 and 2: the analyst can choose to operate the system in a hybrid configuration, alternating between configuration 1 and 2 in various proportions. This is an option that would not have been considered under the conventional approach because the conventional approach claims no ambiguity exists in the decision. By operating in this hybrid manner, the organization may achieve lower overall operating costs than if operating configuration 1 had been chosen (although not as low as if operating configuration 2 had been chosen).

1.2.     Problems Addressed in this Study

1.2.1. Multi-Step Attacks: Uncertainty Bounding

This chapter which also appears in [7] addresses two fundamental IDS issues, confidence in an inference drawn from IDS output and the low base rate problem. Both issues are examined in the context of attack inference in a Bayesian network. With regard to the first issue, we show that high confidence Bayesian inference is infeasible under typical conditions of uncertain model parameters. We argue that model parameters cannot be confidently estimated with arbitrarily high confidence and hence IDS inference uncertainty is an issue to be addressed. The second issue plagues IDS systems in the form of reducing predictive value to very low levels.

We examine both issues and show that neither is fatal because many real-world attacks involve multiple chained exploits. We refer to probabilistic inference in such cases as multi-step inference. The traditional case of inferring the occurrence of an exploit via observation of an alert associated with that one exploit is referred to here as single-step inference. Our analysis shows that the two issues of inference confidence and predictive value, which can be so acute in the single-step case, are alleviated in the multi-step case, given our assumptions.

Regarding the conceptual detection process of Figure 1.1-1, this chapter’s work concerns one very specific configuration of the alert processing node. This configuration corresponds to a detection set consisting of the intersection of all sensor alerts, i.e. the detection condition under which each sensor has been observed to issue an alert. More comprehensive analysis is undertaken in the following chapter.

1.2.2. System-Level Detection

In this chapter, the design of the alert processing node of Figure 1.1-1 is considered. Specifically, with regard to Figure 1.1-2, we consider the construction of the domain model, intrusion definitions and algorithms for enumeration of detection sets. To accomplish this, we adopt a rational practitioner perspective and systematically examine the issue of attack detection in the presence of uncertainty in the context of multi-step attacks. As a result, we present several contributions. First, we comprehensively address intrusion detection in the multi-step case via a Bayesian approach and show how uncertainty can be incorporated into the model. Through the incorporation of dummy detection and query nodes, we show that our model is very flexible in terms of the variety of intrusion definitions under which it could be used by an analyst for detection. For the point probability case, we present our Enumerate Operating Points algorithm which yields the full set of useful detection sets in a given detection scenario. For the uncertain case, we define the concept of the operating box, the uncertain analog of the traditional operating point, and show that enumeration of operating boxes is a highly computationally complex problem, necessitating heuristic approaches. Our contributions in this chapter thus provide the analyst with new tools for not only performing detection over multiple attack steps in a general manner, but also for incorporating uncertainty into the detector itself, capabilities that given the analyst new options for reasoning about potential attacks against the systems they defend.

1.2.3. Analytic Study of the Linear Attack Model

This chapter considers the linear attack chain model and defines two categories of intrusion under this model. Through analysis, analytical expressions for system parameter values are obtained for each intrusion type. Using these analytical results, we have identified cases where model parameter uncertainty cannot produce corresponding uncertainty in the system-level detection parameters. These results constitute guidance to practitioners seeking to design a multistep linear detection system because they provide a basis for a practitioner to prioritize uncertainty reduction efforts.

1.2.4. Experiments

This chapter revisits the linear attack topology considered in Chapters 3 and 5 and experimentally evaluates heuristics for enumerating operating boxes under this topology. Two heuristic approaches are defined and the results of each are compared with full enumeration results against a small attack chain instance under a set of intrusion types. Experimental results show that both heuristics perform very well with the heuristic based on the Enumerate Operating Points algorithm providing marginally better results. Additionally, the experimental results of this chapter show that uncertainty in system detection parameters can vary significantly under the conditions studied, suggesting the importance of considering the effects of uncertainty in a multistep detection system.

MULTI-STEP ATTACK DETECTION VIA BAYESIAN MODELING UNDER MODEL PARAMETER UNCERTAINTY

Sharing is caring!