An Attack Graph Based Approach for Threat Identification of an Enterprise Network

Introduction

With the increased reliance and dependence on networks, the threats that an enterprise faces, both external as well as internal, has also increased phenomenally. A security administrator is always faced with the challenge of identifying these threats, and in retrospect, securing the organization’s network. The classical approach of identifying the vulnerabilities of individual hosts using commercially available tools, like the Retina and Nessus, does not take into account vulnerability interactions. These vulnerability interrelationships are very important to get a holistic view of network security from the security administrator’s point of view. The vulnerability interactions are best captured by an attack graph, which helps in identifying all the possible ways in which an attacker can reach a critical resource on the network.

The attack graph generation is a first step towards threat identification of an enterprise network. There are two basic approaches of generating an attack graph, namely the state based approach (Ammann et al., 2002; Philips et al., 1998) and host based approach (Ammann et al., 2005; Ingols et al., 2006). Several previous approaches (Ammann et al., 2002; Li et al., 2006) have used the combination of a forward and backward chaining algorithm to identify an attack graph. The state based approach gives information at a more granular level whereas its representation soon becomes very large and complex even for a moderate size network (Sheyner et al., 2002). On the other hand, in a host based attack graph each node will be identified as a network entity and the edges will be privileges obtained after applying exploits among them. The host based approach gives a compact representation which may be useful for a visual representation and handle scalability at the cost of abstracting several low level details related to exploit correlation, vulnerability and attacker privileges. For example, obtaining user level privilege on a host, say host 1, and escalation of that privilege to the super user level can be treated as two distinguished states in a state based approach. On the other hand, a host based approach combines all such individual privileges and retains the highest level privilege as a graph edge. Availability of the low level details in a state based attack graph makes it convenient for proper risk management.

The proposed approach uses the state based forward chaining algorithm (Ammann et al., 2002) to generate an attack graph with necessary exploits. The necessary exploits are the set of exploits, subset of which will be actually used by the attacker to obtain the goal. Therefore, the forward reachable attack graph may contain redundancies. The run time complexity of such forward chaining algorithm can be represented by the polynomial O (|A|². E) (Ammann et al., 2002), where A is the number of network conditions and E is the number of exploits. Each vertex in the generated attack graph is used to represent network state and the corresponding exploits, the edges are used to represent the causal relationship among network states and exploits. The proposed approach in Ammann et al. (2002) does a backward search to generate attack graph with sufficient exploits from the forward reachable attack graph. Our proposed approach differs from Ammann et al. (2002) in that it works in two dimensions. On one hand it identifies the most probable attack path(s) based on the attack surface measure of the individual hosts, independent of the vulnerabilities or the exploits that may exist and on the other hand that for identifying the actual exploit correlation for risk mitigation rather than generating an attack graph it uses a forward reachable graph and thus identifies all the possible network securing options.