9.4. Network Attack Graphs

Network attack graphs represent a collection of possible penetration scenarios in a computer network. Each penetration scenario is a sequence of actions taken by the intruder, typically culminating in a particular goal—administrative access on a particular host, access to a database, service disruption, and so on. For appropriately constructed network models, attack graphs give a bird’s-eye view of every scenario that can lead to a serious security breach.

9.4.1. Network Attack Model

We model a network using either the tuple of inputs, <S,R,S₀, L>, in the first algorithm (Figure 9.1) or the Bücchi automaton, M, of the second algorithm (Figure 9.2).

To be concrete, for the remainder of this chapter we will work in the context of the second algorithm. Also, rather than use the full Bücchi automaton to model attacks on a network, for our application to network security, we use a simpler attack model M = <S,τ,s₀>, where S is a finite set of states, τ⊆S × S is a transition relation, and s₀ϵS is an initial state. The state space S represents a set of three agents I = {E,D,N}. Agent E is the attacker, agent D is the defender, and agent N is the system under attack. Each agent iϵ I has its own set of possible states S_i, so that S = × _iϵIS_i.

With each agent iϵI we associate a set of actions A_i, so that the total set of actions in the model is A = ∪_iϵIA_i. A state transition in a network attack model corresponds to a single action by the intruder, a defensive action by the system administrator (or security software installed on the network), or a routine network action. The single root state s₀ represents the initial state of each agent before any action has taken place. In general, the attacker’s actions move the system toward some undesirable (from the system’s point of view) state, and the defender’s actions attempt to counteract that effect. For instance, in a computer network, the attacker’s actions would be the steps taken by the intruder to compromise the network, and the defender’s actions would be the steps taken by the system administrator to disrupt the attack.

Real networks consist of a large variety of hardware and software pieces, most of which are not involved in cyber attacks. We have chosen six network components relevant to constructing network attack models. The components were chosen to include enough information to represent a wide variety of networks and attack scenarios, yet keep the model reasonably simple and small. The following is a list of the components:

We construct an attack model M based on these components. Table 9.1 defines each agent i’s state S_i and action set A_i in terms of the network components. This construction gives the system administrator an entirely passive “detection” role, embodied in the alarm action of the intrusion detection system. For simplicity, regular network activity is omitted entirely.

Table 9.1. Network attack model.

Agent i ϵ I	Si	Ai
E	I	A
D	Ids	{alarm}
N	H × C × T	⊘

It remains to make explicit the transition relation of the attack model M. Each transition (s₁,s₂)ϵτ is either an action by the intruder or an alarm action by the system administrator. An alarm action happens whenever the IDS is able to flag an intruder action. An action aϵA requires that the preconditions of a hold in state s₁ and the effects of a hold in s₂. Action preconditions and effects are explained in Section 9.4.2.

9.4.2. Network Components

We now give details about each network component.

Hosts

Hosts are the main hubs of activity on a network. They run services, process network requests, and maintain data. With rare exceptions, every action in an attack scenario will target a host in some way. Typically, an action takes advantage of vulnerable or misconfigured software to gain information or access privileges for the attacker. The main goal in modeling hosts is to capture as much information as possible about components that may contribute to creating an exploitable vulnerability.

A host h ϵ H is a tuple <id, svcs, sw, vuls>, where

• id is a unique host identifier (typically, name and network address).

• svcs is a list of service name/port number pairs describing each service that is active on the host and the port on which the service is listening.

• sw is a list of other software operating on the host, including the operating system type and version.

• vuls is a list of host-specific vulnerable components. This list may include installed software with exploitable security flaws (e.g., a setuid program with a buffer overflow problem), or misconfigured environment settings (e.g., existing user shell for system-only users, such as ftp).

Network Connectivity

Following Ritchey and Ammann [11], connectivity is expressed as a ternary relation C ⊆ H × H × P, where P is a set of integer port numbers. C(h₁,h₂,p) means that host h₂ is reachable from host h₁ on port p. Note that the connectivity relation incorporates firewalls and other elements that restrict the ability of one host to connect to another. Slightly abusing notation, we say R(h₁,h₂) when there is a network route from h₁ to h₂.

Trust

We model trust as a binary relation T ⊆ H × H, where T (h₁,h₂) indicates that a user may log in from host h₂ to host h₁ without authentication (i.e., host h₁ “trusts” host h₂).

Services

The set of services S is a list of unique service names, one for each service that is present on any host on the network. We distinguish services from other software because network services so often serve as a conduit for exploits. Furthermore, services are tied to the connectivity relation via port numbers, and this information must be included in the model of each host. Every service name in each host’s list of services comes from the set S.

Intrusion Detection System

We associate a Boolean variable with each action, abstractly representing whether or not the IDS can detect that particular action. Actions are classified as being either detectable or stealthy with respect to the IDS. If an action is detectable, it will trigger an alarm when executed on a host or network segment monitored by the IDS; if an action is stealthy, the IDS does not see it.

We specify the IDS as a function ids: H × H × A →{d,s,b}, where ids(h₁, h₂,a)= d if action a is detectable when executed with source host h₁ and target host h₂;ids(h₁,h₂,a)= s if action a is stealthy when executed with source host h₁and target host h₂; and ids(h₁,h₂,a) = b if action a has both detectable and stealthy strains, and success in detecting the action depends on which strain is used. When h₁ and h₂ refer to the same host,ids(h₁,h₂,a) specifies the IDS component (if any) located on that host. When h₁ and h₂ refer to different hosts,ids(h₁,h₂,a) specifies the IDS component (if any) monitoring the network path between h₁ and h₂.

Actions

Each action is a triple <r,h_s, h_t>, where h_s ϵ H is the host from which the action is launched, h_tϵ H is the host targeted by the action, and r is the rule that describes how the intruder can change the network or add to his or her knowledge about it. A specification of an action rule has four components: intruder preconditions, network preconditions, intruder effects, and network effects. The intruder preconditions component places conditions on the intruder’s store of knowledge and the privilege level required to launch the action. The network preconditions specifies conditions on the target host state, network connectivity, trust, services, and vulnerabilities that must hold before launching the action. Finally, the intruder and network effects components list the action’s effects on the intruder and network, respectively.

Intruder

The intruder has a store of knowledge about the target network and its users. The intruder’s store of knowledge includes host addresses, known vulnerabilities, user passwords, information gathered with port scans, and so on. Also associated with the intruder is the function plvl: Hosts →{none, user, root}, which gives the level of privilege that the intruder has on each host. For simplicity, we model only three privilege levels. There is a strict total order on the privilege levels:none≤user≤root.

Omitted Complications

Although we do not model actions taken by user services for the sake of simplicity, doing so in the future would let us ask questions about effects of intrusions on service quality. A more complex model could include services provided by the network to its regular users and other routine network traffic. These details would reflect more realistically the interaction between intruder actions and regular network activity at the expense of additional complexity.

Another activity worth modeling explicitly is administrative steps taken either to hinder an attack in progress or to repair the damage after an attack has occurred. The former corresponds to transitioning to states of the model that offer less opportunity for further penetration; the latter means “undoing” some of the damage caused by successful attacks.