Web Security

Representation and Analysis of Coordinated Attacks

Sviatoslav Braynov and Murtuza Jadliwala Department of Computer Science and Engineering

University at Buffalo Buffalo, NY 14260

{sbraynov, msj3} @ cse.buffalo.edu

ABSTRACT In this paper, we propose a formal m o d e l o f c o o r d i n a t e d attacks in w h i c h several attackers cooperate towards a c o m m o n m a l i c i o u s goal. T h e model investigates b o t h attack p l a n n i n g and vulnerabil- ity analysis, thereby p r o v i d i n g a u n i f o r m approach to s y s t e m and adversary modelling. In addition, the model is general e n o u g h to explain b o t h c o o r d i n a t e d a n d single attacks.

In the paper, we define the n o t i o n o f c o o r d i n a t e d - a t t a c k graph, propose an a l g o r i t h m for efficient generation o f c o o r d i n a t e d - a t t a c k graphs, d e m o n s t r a t e how c o o r d i n a t e d - a t t a c k c a n b e u s e d for vul- nerability analysis, and discuss an i m p l e m e n t a t i o n o f a coordinated- attack graph.

Coordinated-attack graphs can facilitate a wide r a n g e o f tasks, such as m o d e l checking, o p p o n e n t modelling, intrusion response, sensor configuration, and so forth. In addition, they can b e used in robotic warfare, where several intelligent software agents automat- ically produce a n d l a u n c h c o o r d i n a t e d attacks.

Categories and Subject Descriptors D.2.4 [Software Engi neeri ng]: S o f t w a r e / P r o g r a m Verification - - formal methods, model checking

General Terms Security

Keywords C o o r d i n a t e d attack, attack graph, adversary modelling, attack plan, model c h e c k i n g

1. INTRODUCTION Organized attacks a i m i n g at disrupting critical infrastructure are

usually b e y o n d the power o f a single attacker. To achieve their goal, several attackers cooperate b y resource sharing, task alloca- tion, a n d synchronization. Coalitions o f malicious attackers m a y include b o t h h u m a n and artificial agents, i.e., intelligent software agents acting o n b e h a l f o f h u m a n s . A r e c e n t C E R T report [ 13] c o n - cludes that m o d e r n attack tools are rapidly e v o l v i n g and b e c o m i n g

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. FMSE'03, October 30, 2003, Washington, DC, USA. Copyright 2003 ACM 1-58113 -781-8/03/0010 ...$5.00.

m o r e sophisticated. U n l i k e early attacks, l a u n c h e d b y a single at- tacker to a single victim, r e c e n t attacks are b e t t e r c o o r d i n a t e d and difficult to discover. A notorious e x a m p l e is the O c t o b e r 23rd at- tack o n D N S root servers [20].

M o s t literature o n distributed attacks h a s traditionally focused o n distributed denial o f services (DDoS), in w h i c h an attacker b r e a k s into several m a c h i n e s , or j o i n s other attackers to s i m u l t a n e o u s l y attack a target h o s t or network. A distributed attack, however, is a very simple f o r m o f c o o r d i n a t e d attack, w h e r e m a n y i n t e l l i g e n t attackers coordinate in real time. G i v e n the present state o f coor- dinated attacks, we could expect new a n d m o r e d a m a g i n g patterns o f distributed attacks in the n e a r future. Our c o n c e r n is t h a t cur- r e n t attack patterns h a v e not utilized the full potential for real t i m e coordination and cooperation.

In our previous research [5], we identified several p r o b l e m s w i t h c o o r d i n a t e d attacks:

• C o o r d i n a t e d attack s c o u l d b e d e s i g n e d to a v o i d detection. M a n y d e f e n s e technologies can b e easily defeated b y a so- phisticated c o o r d i n a t e d attack c a p a b l e o f b r e a k i n g the attack pattern into m a n y apparently i n n o c e n t pieces. T h i n k o f the following example. C o n s i d e r a large crowd (users, processes, hosts, threads) w i t h few attackers h i d i n g inside it and execut- ing a c o o r d i n a t e d attack plan. Due to the large crowd, it is practically i m p o s s i b l e to discern individual attackers m a n y o f w h i c h could b e p e r f o r m i n g apparently i n n o c u o u s actions. O n c e the attack succeeds it is clear w h o the attackers are, but at this point it is too late to m a k e a difference.

• It is difficult to d ifferentiate b e t w e e n d e c o y a n d actual attacks. C o n s i d e r the case w h e r e m e m b e r s o f a malicious group l a u n c h several s i m u l t a n e o u s attacks o n a system. In order to m i s l e a d the intrusion r e s p o n s e system, all but one o f these attacks are d e s i g n e d to b e decoy. T h a t is, they are l a u n c h e d for the sole purpose o f distracting the intrusion re- sponse system and c o n s u m i n g its resources. D e c o y attacks m a y h a v e different goals. T h e y could: create m a n y simul- taneous alerts in order to m i s l e a d or c o n f u s e the IDS; waste s y s t e m response t i m e o n decoy goals; or p e r f o r m a DoS at- tack on the IDS.

• T h e r e is a large variety o f c o o r d i n a t e d attacks. Attackers m a y attack single or multiple victims. S o m e attacks could b e automatically replicated or duplicated, thereby a c c u m u l a t i n g m o r e power. O t h e r attacks m a y b e supporting, i.e.,launched in parallel w i t h the m a i n attack, with the aim o f p r o v i d i n g auxiliary functionality such as cover-up, back-up, trace re- m o v i n g , etc.

A l t h o u g h the p a p e r discusses primarily insider attacks, the m o d - els p r e s e n t e d are general e n o u g h to b e applied to a wide r a n g e o f scenarios i n c l u d i n g insider, outsider, a n d m i x e d attacks.

43

Since the actions o f different attackers interact, we c a n n o t spec- ify the effects o f an individual attacker's action w i t h o u t taking into a c c o u n t w h a t actions m i g h t b e p e r f o r m e d b y o t h e r attackers at the s a m e time. It is often the case t h a t the effect an action is modi- fied b y a n o t h e r action executed c o n c u r r e n t l y b y a n o t h e r attacker. In o t h e r words, the result o f a j o i n t action, executed s i m u l t a n e o u s l y b y several attackers, could go b e y o n d the sum o f individual actions.

C u r r e n t research on vulnerability analysis, i n c l u d i n g g r a p h - b a s e d systems [22, 24, 17, 15, 16, 23] a n d correlation-attack l a n g u a g e s [7, 21, 26], has m a i n l y focused on serial attacks, i.e., s e q u e n c e s o f a t o m i c actions leading to a security breach. A l t h o u g h correlation analysis has b e e n applied to a n a l y z e r e l a t i o n s h i p s b e t w e e n different o n g o i n g attacks, little attention was paid to c o r r e l a t i n g individual actions across users in order to identify a single attack. In a coordi- n a t e d attack, attackers' actions interfere w i t h o n e another, m a k i n g it difficult to a n a l y z e an action out o f the context o f o t h e r actions. Consider, for example, two legitimate users w i t h different access rights. W h i l e the first user has access to sensitive data, a n d n o ac- cess to an external network, the s e c o n d u s e r h a s external n e t w o r k access, and n o access to sensitive data. T h e users could collude a n d l a u n c h a c o o r d i n a t e d i n s i d e r attack. T h e y could first e s t a b l i s h a covert c h a n n e l b e t w e e n t h e m , and t h e n let the s y s t e m leak sen- sitive information. In this case, m o s t i n t r u s i o n detection systems would detect an authorized access to sensitive data a n d a n autho- rized n e t w o r k access, w i t h o u t b e i n g able to correlate them.

T h e simplest way to h a n d l e interactions b e t w e e n c o n c u r r e n t at- tackers' actions is to c o n s i d e r e a c h j o i n t action as a n atomic action, i.e., to consider the group o f attackers as a single attacker. Specifi- cally, i f A~ d e n o t e s the actions available to attacker i, t h e n the j o i n t action space is A1 x A2 x ... × A n . T h a t is, a j o i n t action is a c o m b i n a t i o n o f all individual actions t a k e n at the same time. One m a y see e a c h e l e m e n t o f the j o i n t action space as an a t o m i c action, a n d specify its effect using existing specification l a n g u a g e s such as STATL [21] and P - B E S T [7]. T h e m a i n a d v a n t a g e o f this reduc- tion is t h a t v u l n e r a b i l i t y analysis c a n b e p e r f o r m e d u s i n g available m e t h o d s a n d tools. S u c h an approach, however, h a s s o m e seri- ous d i s a d v a n t a g e s as far as expressiveness is concerned, as well as ease o f r e p r e s e n t a t i o n and analytic power. First, the n u m b e r o f j o i n t actions increases e x p o n e n t i a l l y w i t h the n u m b e r o f attackers ( a s s u m i n g t h a t e a c h attacker c a n execute at m o s t o n e action at a time). T h i s leads to a super-exponential b l o w u p o f specification and s y s t e m models. Second, this r e d u c t i o n fails to a c c o u n t for the interaction b e t w e e n attacker's actions, and t h e r e b y to p r o v i d e data for further correlation analysis. Third, it fails to exploit the fact t h a t m a n y a t t a c k e r s ' a c t i o n s m a y not interact at all, or interact un- d e r s o m e conditions only.

In this p a p e r we p r o p o s e a f o r m a l m o d e l o f c o o r d i n a t e d attacks in w h i c h several attackers coordinate their actions to achieve the c o m m o n goal o f c o m p r o m i s i n g a c o m p u t e r or n e t w o r k system. A distinctive feature o f the m o d e l is its ability to a c c o u n t for concur- r e n t i n t e r d e p e n d e n t attackers' actions. In a c o n c u r r e n t - a c t i o n at- tack, e a c h individual action can b r i n g a b o u t the desired effect o n l y i f properly c o o r d i n a t e d w i t h o t h e r actions w h i c h could b e concur- rently or sequentially applied.

T h e p a p e r is o r g a n i z e d as follows. Section 2 introduces a for- mal model o f c o n c u r r e n t systems. Section 3 defines the n o t i o n o f c o o r d i n a t e d attack plan. Section 4 discusses h o w several attack plans m a y c o m b i n e into a c o o r d i n a t e d - a t t a c k graph. T h e section also presents an efficient a l g o r i t h m for g e n e r a t i n g attack graphs. Section 5 illustrates h o w c o o r d i n a t e d - a t t a c k g r a p h s can b e u s e d for v u l n e r a b i l i t y analysis. Finally, Section 6 discusses an i m p l e m e n t a - tion o f a c o o r d i n a t e d - a t t a c k graph.

2. F O R M A L F R A M E W O R K In this section, we describe a m o d e l o f c o o r d i n a t e d attacks t h a t

accounts for synergy a n d c o o r d i n a t i o n a m o n g attackers.

1. S is a finite set o f s y s t e m states

2. So C S is a set o f initial sets

3. S y s t e m states are truth a s s i g n m e n t s to g r o u n d a t o m i c f o r m u - lae. A state is r e p r e s e n t e d as a set (or c o n j u n c t i o n ) o f those g r o u n d atomic f o r m u l a e t h a t are true in the state. F o r exam- ple, the state in w h i c h u s e r l has l o g g e d a n d accessed filel is r e p r e s e n t e d as:

logged(user1) A accessed(user1, f i l e l )

T h i s implies the c l o s e d world a s s u m p t i o n , i.e., every a t o m i c f o r m u l a not listed in a state evaluates to FALSE.

4. A~ is the set o f actions available to attacker i. T h e j o i n t action space is A = A1 x A2 x ... x A n . T h a t is, e a c h j o i n t action d = ( a l , a2, ..., a n ) , a i C A i , is a c o m b i n a t i o n o f individual actions p e r f o r m e d b y e a c h o f the attackers. T h r o u g h o u t this paper, w e a s s u m e that an attacker can p e r f o r m at m o s t o n e action at a time. S o m e o f the actions c o u l d b e e, a null or n o - o p action. We a s s u m e t h a t e E A~ for i = 1, ..., n . In o t h e r words, s o m e attackers could b e idle at s o m e stages o f the attack.

5. T C S × A × S is a trinary relation, the transition rela- tion, w h i c h gives possible transitions b e t w e e n states. T h a t is, T ( s l , ~, s2) describes a transition f r o m state Sl to s2, i f j o i n t action ~ is t a k e n in state s l . In this paper, w e c o n s t r a i n our a t t e n t i o n to d e t e r m i n i s t i c transitions. T h e m o d e l c a n easily b e g e n e r a l i z e d to h a n d l e n o n d e t e r m i n i s t i c actions b y intro- d u c i n g a p r o b a b i l i t y distribution o n the space o f resulting ac- tions. N o t e that the j o i n t action ~ is n o t an a t o m i c action, but a v e c t o r o f individual actions, e a c h defined separately. S i n c e the effects o f the c o n c u r r e n t actions applied to s l interfere, the resulting state s2 is d e t e r m i n e d b y all c o n c u r r e n t actions.

6. G is the attackers' goal, i.e., a first-order f o r m u l a d e s c r i b i n g a c o m p r o m i s e d s y s t e m state. S o , SG C S is a set o f s y s t e m states in w h i c h the goal is satisfied. N o t e that, G could b e a c o m p l e x goal c o n s i s t i n g o f several c o n c u r r e n t goals. In this case, it c o u l d b e r e p r e s e n t e d as a c o n j u n c t i v e lists o f f o r m u - las.

For the ease o f notation, e a c h action is d e s c r i b e d b y a generic ac- tion s c h e m a specifying: w h o is p e r f o r m i n g the action, w h a t are the action preconditions, w h a t other actions m u s t b e p e r f o r m e d c o n c u r - rently, a n d w h a t is the final effect o f the action. F i g u r e 1 describes the f o r m a t o f a n action schema. In a schema, action p r e c o n d i t i o n s specify w h i c h a t o m i c f o r m u l a e m u s t b e true in the c u r r e n t state o f the s y s t e m in order to apply the action. T h e p o s t c o n d i t i o n s specify w h i c h a t o m i c f o r m u l a e b e c o m e true a n d w h i c h b e c o m e false after the action is executed. T h e c o n c u r r e n t list specifies other actions t h a t m u s t b e s i m u l t a n e o u s l y executed or not executed for a given action to h a v e its i n t e n d e d effect. To specify a concrete action, all free variables in a s c h e m a m u s t b e b o u n d to constants. In o t h e r words, every action is a fully instantiated action schema. We as- s u m e t h a t c o n j u n c t i v e lists, pre- and p o s t c o n d i t i o n s are consistent, i.e., j o i n t l y satisfiable. T h a t is, there exists at least o n e variable a s s i g n m e n t t h a t satisfies t h e m in at least o n e s y s t e m state. For ex- ample, a c o n c u r r e n t action list m u s t n o t require t h a t a particular action b e applied and n o t applied at the s a m e t i m e in a given state.

4 4

action <first-order predicate> :parameters

<list-of-free-variables> :preconditions

< conjuctive-list-of-predicates > :concurrent <conjuctive-list-of-action-names> :postconditious <conjuctive-list-of-predicates>

Figure 1: Action schema

An action (a fully instantiated action schema) can be executed only i f it's preconditions are true. After the action execution, the system state is changed in the following way. All positive literals from postconditions are added into the state description while all negative literals are removed. For example, i f executed in state

l o g g e d ( u s e r 1 ) A a c c e s s e d ( u s e r 1 , f i l e 1 )

a logging off action with a postcondition not(logged(user1)) will change the current state to

a c c e s s e d ( u s e r 1 , f i l e l ) )

Our action representation significantly differs from representa- tions used in attack graphs. First, it allows for free variables, thereby allowing an action schema to present a whole class o f instant ac- tions. When an action schema is instantiated, all variables must be bound to constants. Second, it allows for concurrent actions, and explicitly describes action dependence. Synchronization and coordination among attackers is captured by the concurrent action list. It specifies what actions must be executed concurrently in or- der to enable positive synergy, and what action combinations are prohibited in order to avoid negative synergy. That is, some actions must be taken (for positive synergy) or must not be taken (for neg- ative synergy) in order for a given action to have its intended effect specified by postconditions. Since an attacker can perform at most one action at a time, all concurrent actions must be performed by different attackers.

Figure 2 represents two concurrent actions corresponding to a symbolic link race condition [10]. In this attack, two insiders, user1 and user2, cooperate in order to gain access to file, which they are not authorized to access. User1 creates symbolic link file1 pointing to file2. We suppose that user1 has access to read and write both file1 and file2. After establishing the symbolic link, user1 calls open(filel, O_RDWR). The system resolves the symbolic link and checks that access to file2 is allowed. Meanwhile, user2 changes the symbolic link file1 to point to file. As a result, the system exe- cutes open(file, O_RDWR), granting user1 access to file.

The intended semantics o f an action scheme is captured by the following definition.

DEFINITION 1. A j o i n t action ~ = ( a l , a2, ..., a,~), a i E Ai, a combination o f individual actions, is consistent in the current state sift."

• The preconditions o f all individual actions are jointly logi- cally consistent in s. That is, the conjunction o f all atomic formulae in precondition lists evaluates to T R U E in s.

• The postconditions are jointly consistent in s. That is, there are no two actions such that the first one brings about a ground atom while the second action brings about the nega- tion o f that atom. In other words, action effects do not con- flict with one another.

action open(user 1,file,O_RDWR) :parameters

u s e r l , file, filel, file2 :preconditions

can-access(userl, file 1,O_RDWR)A can-access(userl, file2,O_RDWR) A symbolic-link(file 1,file2)

:concurrent change-link(user2, file 1, file) :postconditions opened(user, file, O_RDWR)

action change-link(user2, filel, file) :parameters

user2, file, filel :preconditions

can-access(user2, filel,O_RDWR) :postconditions symbolic-link(filel,file)

Figure 2: Action description

• Each action a j mentioned in the concurrent list o f some ai belongs to the joint action. In other words, it is executed by some other attacker j , different f r o m i.

• The negation o f action aj, mentioned in the concurrent list o f some ai, does not belong to the j o i n t action. In other words, no other action negatively interferes with ai.

I f a joint action ~ is consistent in s, then it can be executed in that state. This results in a concurrent execution o f several actions. The resulting state is obtained by adding all positive literals and delet- ing all negative literals from the postcondition lists o f concurrent actions.

3. A C O O R D I N A T E D ATTACK P L A N In an adversarial environment, the best defence strategy depends

on what the defendant believes about the attacker's strategy, which in turn depends on what the attacker believes about the defendant strategy, and so forth, leading to an infinite recursion o f beliefs. In game theory and artificial intelligence, several methods have been proposed to represent and reason about adversaries [6]. Current research on vulnerability analysis usually represents an information system only from the perspective o f the security analyst, thereby missing the other part o f the equation. As Sun Tzu puts it in his treatise on the art o f war [25]: " I f you know the enemy and know yourself, you need not fear the result o f a hundred battles. I f you know yourself but not the enemy, for every victory gained you will also suffer a defeat."

In this section, we propose a formal model o f coordinated at- tacks which can serve both as a semantic model o f a concurrent computer (or network) system and as a planning model for a group o f attackers. That is, the model incorporates the viewpoints o f both the security analyst and the attackers. This is quite a natural ap- proach, given that an attacker usually launches an attack based on a model o f the system, and the system analysts evaluates a model against a set o f possible attacks. In addition, the model is general enough to explain both coordinated and single attacks.

The semantics o f individual actions in coordinated attacks is dif- ferent from their semantics in individual attacks. In coordinated attacks, it is not individual actions that transform one state o f the system into another. Rather, the state transitions are triggered by j o i n t actions concurrently executed by several attackers.

45

DEFINITION 2. A n individual plan pi f o r attacker i is a se- quence o f actions

i i i p~ = ( a 0 ( s o ) , a 2 ( s l ) , , a k ( S k ) )

where action a i j ( s j ) is executed in state s j by attacker i.

A n individual plan is deterministic in the sense that e a c h attacker k n o w s w h a t action to execute at every state o f the system. A t first sight, this m i g h t s e e m a limiting a s s u m p t i o n since attackers are usu- ally p r e p a r e d to react to u n f o r e s e e n failures and contingencies. F o r example, attackers often e m p l o y c o n t i n g e n c y plans t h a t allow t h e m to r e c o v e r f r o m u n e x p e c t e d accidents. S u c h scenarios traditionally fall in the d o m a i n o f c o n t i n g e n c y p l a n n i n g [ 19, 3]. U s i n g standard m e t h o d s f r o m c o n t i n g e n c y planning, the model p r e s e n t e d in this p a p e r can easily b e e x t e n d e d to include c o n d i t i o n a l actions.

We a s s u m e that the s y s t e m state is accessible for attackers in the sense that they h a v e the k n o w l e d g e and the skills to differentiate b e t w e e n the states in the attack plan. T h i s a s s u m p t i o n prevents m i s c o o r d i n a t i o n c a u s e d b y inability o f an attacker to correctly de- t e r m i n e the p r e s e n t state o f the system. B y this, we do not as- s u m e that attackers h a v e c o m p l e t e k n o w l e d g e o f every situation they could encounter. First, attackers n e e d to differentiate b e t w e e n attack-relevant states, not b e t w e e n all possible states. Second, in order to differentiate b e t w e e n relevant states, attackers n e e d o n l y to k n o w or discern s o m e distinctive features o f the states.

I f we c o m b i n e all actions executed at a certain stage o f the attack j , j : 1, ..., k, we o b t a i n the attackers' j o i n t action at that stage. It is natural to define a c o o r d i n a t e d attack plan as a s e q u e n c e o f attackers' j o i n t actions.

DEFINITION 3. A coordinated-attack plan P f o r a group o f at- tackers G is the union o f coordinated individual plans o f the mem- bers o f the group. The coordination between attackers is specified at action level trough precondition and concurrent conditions.

T h a t is, a c o o r d i n a t e d - a t t a c k p l a n P is a sequence o f j o i n t actions:

p : ( a 0 ( s 0 ) , a l ( s l ) , , a k ( s k ) )

w h e r e a j o i n t action a j (s j ) , taken in state s j , is defined as the c o m - b i n a t i o n o f all c o n c u r r e n t actions executed by e a c h attacker in s j :

a j ( s j ) : ( a l j ( s j ) , a2y ( s j ) , ..., a n n ( s j ) )

Every c o o r d i n a t e d - a t t a c k plan starts in the current state so and finishes in s o m e final state w h e r e the a t t a c k e r s ' s goal (or goals) is achieved, i.e., the s y s t e m security is c o m p r o m i s e d . T h e p l a n speci- fies w h a t action has to b e taken b y e a c h a g e n t in e a c h state, in order to r e a c h the goal state. A t first sight it m a y s e e m counterintuitive that the attackers' goal is always satisfied in the final state. T h e goal o f planning, however, is to plan for success. A f t e r all n o b o d y plans for failure. W h e t h e r or n o t a p l a n will succeed d e p e n d s o n the validity o f its assumptions.

A c o o r d i n a t e d - a t t a c k p l a n c a n b e c o n v e n i e n t l y r e p r e s e n t e d as a directed and acyclic m u l t i g r a p h w h e r e n o d e s represent s y s t e m states and arcs c o r r e s p o n d to actions. All arcs leaving a n o d e rep- r e s e n t actions c o n c u r r e n t l y started at that node. Similarly, all arcs p o i n t i n g to a n o d e r e p r e s e n t actions c o n c u r r e n t l y finished at that node. T h e i n t e n d e d m e a n i n g is that all arcs b e t w e e n two n o d e s m u s t b e traversed c o n c u r r e n t l y (by different attackers), in order to m o v e the s y s t e m f r o m the first to the s e c o n d state. Figure 3 shows a c o o r d i n a t e d - a t t a c k plan for the race c o n d i t i o n example. T h e attack- e r s ' goal is to open file ~, w h i c h they are not authorized to access. T h e y start in the initial state so and achieve t h e i r goal o f o p e n i n g t f in s5. Note that, in order to m o v e the s y s t e m f r o m state s2 to s5, u s e r l ' s action a12 has to b e c o n c u r r e n t l y applied w i t h user2's

actions a22, a23, and a24. T h a t is, links c o n n e c t i n g s2 a n d s5 m u s t b e traversed concurrently.

It is worth n o t i n g t h a t a c o o r d i n a t e d - a t t a c k graph h a s n o loops. After all, n o b o d y plans to take an action that has n o effect. Since our plans are deterministic, there are n o cycles, either. A con- tingency plan, however, m a y have cycles r e p r e s e n t i n g recoveries (backtracking, for example) f r o m partial failures.

E a c h c o o r d i n a t e d - a t t a c k plan is linear, since it i n d u c e s a total or- der on the set o f states. In F i g u r e 3, the total order is r e p r e s e n t e d as a c h r o n o l o g i c a l t i m e line starting w i t h the initial state so, followed b y i n t e r m e d i a t e states a n d the final state s5.

4. ATTACK G R A P H F O R C O O R D I N A T E D ATTACKS

It is often the case that a group o f attackers c o m e s up with dif- f e r e n t plans for a c h i e v i n g their goals, a n d it is up to the group to c h o o s e w h i c h plan to follow. To evaluate s y s t e m vulnerability, a se- curity analyst needs a m o d e l o f possible attacks. A n attack m o d e l can also facilitate model-based intrusion detection, in w h i c h alerts are m a t c h e d against the m o d e l to discover attackers' c o o r d i n a t i o n patterns.

DEFINITION 4. A n adversary's instrumental capacity, ( A S , n ), is represented by:

• A S : The actions available to attackers.

• n : The maximal number o f attackers participating in an at- tack.

T h e n o t i o n o f a d v e r s a r y ' s i n s t r u m e n t a l capacity covers knowledge, skill levels, and tools available to attackers. In this paper, we con- sider h o m o g e n e o u s groups o f attackers, i.e., groups o f equally skilled and k n o w l e d g a b l e attackers. In o t h e r words, i f a n attacker c a n ac- c o m p l i s h a task, so c a n any other m e m b e r o f the group. Apparently, attackers share knowledge, tools, and e v e n teach o n e a n o t h e r t i m e permitting. T h e h o m o g e n e i t y a s s u m p t i o n also applies for software agents acting o n b e h a l f o f h u m a n attackers. A software a g e n t can easily replicate and l a u n c h new copies o f itself.

H o m o g e n e o u s attackers can benefit in m a n y ways f r o m cooper- ation. For example, in order to m a k e an attack short, i n d e p e n d e n t subtasks c a n b e a s s i g n e d to different attackers. In s o m e cases, ho- m o g e n e o u s attackers c a n cooperate to avoid detection (parallel port scanning). It is also possible t h a t s o m e steps o f a n attack m a y re- quire a j o i n t action that is b e y o n d the p o w e r o f a single attacker.

Note that the n o t i o n o f i n s t r u m e n t a l capacity does not c o v e r at- tackers' d e c i s i o n - m a k i n g skills. Different groups o f attackers can utilize the set o f available actions A S in different ways, s o m e groups m a k i n g m o r e efficient use o f actions t h a n others.

DEFINITION 5. A coordinated-attack graph is the union o f all coordinated-attack plans, which f o r a given adversary's instrumen- tal capacity ( A S , n), reach a goal state s, s E SG, when applied to the current state So. More formally, a coordinated-attack graph is:

C A G : (V, E , o~, So, S o , A S , n )

where (V, E ) is a multigraph o f system state transitions. Each node v E V, V _C S, represents a system state, and each arc a, a E A S , represents an attocker's action. The action set A S is the set o f all actions available to attackers, and n is the maximal number o f attackers that can participate in the attack. So is the current state, and SG are the goal states, a is a labelling which associates each arc with an action in A S .

46

alo: U1 logs in a l l : U1 creates sym a 1 2 : U 1 opens F1 link F1 Dointinq to F2

2 a20: u2 logs in a 2 1 : u 2 no-op a 2 2 : u 2 no-op a 3: U2changes sym a 2 4 : u 2 no-op link F1 to point to TF

Figure 3: Coordinated-attack plan

As shown, a coordinated-attack graph is the union o f all coordinated- attack plans that can reach the goal G, i.e., the plans having a final state in S a . A coordinated-attack plan can be automatically gener- ated by any sound and complete planning algorithm that allows for concurrent actions, such as P O M E A planning algorithm is sound if it generates only plans that are guaranteed to achieve the attack- ers' goals. A complete algorithm is guaranteed to generate a plan, i f a successful plan exists. Obviously, a complete planning algorithm can iteratively generate all existing plans, by disabling previously generated plans.

Figure 4 is an example o f a coordinated attack graph. The lower branch o f the attack graph represents the race condition attack dis- cussed above. The upper branch represents a similar attack called directory race cognition [ 10]. The dotted lines in Figure 4 are used to join concurrent links. That is, the two links leaving node so are concurrent, whereas the two links leaving s l represent a decision choice in which attackers have to chose from two available attack continuations.

Coordinated-attack graphs represent a semantic model o f a sys- tem and can facilitate a wide range o f tasks, such as model check- ing, opponent modelling, intrusion response, sensor configuration, and so forth. For example, a security feature o f a system can be proved using standard model-checking techniques. Current re- search on planning as model checking allows one to check a plan for its correctness, or to validate a property o f a system written in Computation Tree Logic (CTL)[12].

There has been a lot o f research on planning and concurrent plan- ning. And yet surprisingly, we could not find an efficient imple- mentation o f a concurrent planner. POMP-based planners [2], for example, fail to handle large state-action spaces. The exponen- tial size o f the action-space state could eventually be handled by model-checking planners, such as U M O P [14] and M B P [1] which make use o f Ordered Binary Decision Diagrams (OBDD). O B D D ' s are very compact and efficient representations o f the assignments satisfying'a given boolean formula. Planners using O B D D could handle state-action spaces o f magnitude 102o and higher [18]. Un- fortunately, neither M B P nor U M O P allow for concurrent planning.

Ohe major problem with all existing planning and model-checking systems is that they do not exploit action interdependencies to prune the state-action space. For example, a planning system would search for all possible action combinations applicable in a given state. The situation is further exacerbated, by the exponential growth o f the number o f states.

Concurrent actions might depend on one another in that an ac- tion execution might require the concurrent execution o f another

action. Such a dependence helps avoiding some futile search and increase planning efficiency. For example, i f an action is not ap- plicable in a state, neither are the actions depending on it. That is, all actions that require the concurrent execution o f the given action can be discarded. Action dependencies can be detected efficiently in polynomial time, and all inapplicable actions could be discarded, thereby significantly reducing the search space.

In this paper, we propose a method for pruning the size o f coor- dinated attack graphs. The method uses a data structure, the action- dependence graph, to explicitly represent dependencies and inter- action between concurrent actions.

DEFINITION 6. For a given adversary's instrumental capacity ( A S , k ), an action-dependence graph is a graph-based represen- tation o f the action set A S , where each action is represented by a node. A link is drawn from node a l to node a2 iff a2 belongs to the concurrent list o f action al, i.e., the execution o f al requires the execution o f a2.

The fact that the execution o f action a l requires the concurrent execution o f a2 can be viewed as a dependence o f a l on a2, i.e., action a l cannot be executed unless a2 is concurrently executed. Dependence is not a symmetric relation. In Figure 3, for example, action a12 depends on a23. In other words, userl cannot openfile unless user2 concurrently changes the symbolic link. The reverse, however, is not true. An example o f an action-dependence graph is

(o)

Figure 5: Action-dependence graph

shown in Figure 5. In this case, action a l requires the concurrent execution o f actions a2 and q3. Action a2 requires action a4, and so forth.

47

a 1 2 : U 1 opens . . / . . / e t c / F i l e

°% ****

alo: U1 logs in

a ' , : u2 oo-op _ _ ~ ~ r t o . . . . . . . . . . . . . . . t i ~ e

F 1 - F e ~

F2 - File 2 a 2 6 : u 2 no-op a27: u2 changes a28: u2 no-op TF - Target File Sym link - Symbolic Link sym link F1 to point to

TF

Figure 4: Coordinated-attack graph

The action-dependence graph in Figure 5 suggests that some ac- tions are more "costly" than other actions. For example, i f actions a2 and a4 can achieve the same goal, there is no point in using a2. I f a2 is to be used, then it requires a4, which by itself is sufficient for achieving the goal. This bring us to the following observation.

OBSERVATION 1. M i n i m u m concurrency: A set o f attackers tries to achieve their goal with minimal sets o f concurrent actions.

Put formally,

DEFINITION 7. A set o f concurrent actions Z is irreducible, i f no proper subset o f Z has the same effect as Z.

In other words, there is no point in using a large set o f concur- rent actions i f a smaller subset can achieve the desired effect. There are several reasons for choosing a small set o f concurrent actions at each stage o f an attack. First, small action sets could decrease the cost o f each stage, and therefore the total cost o f an attack. Sec- ond, choosing more actions requires satisfying more preconditions, unnecessarily increasing the complexity o f an attack. Third, small action sets can be carried out by a small number o f attackers.

The action-dependence graph in Figure 5 shows that actions a4, as, and a6 are independent. That is, each o f them can be executed on its own. The same cannot be said, however, for actions a t , a2, and a3, all o f which depend on other actions. Intuitively, actions a t , a2, and aa have different degrees o f dependence. For example, action a t requires the execution o f two other actions, while action a2 requires only one. M o r e formally,

DEFINITION 8. The degree o f dependence o f action a is:

d ( a ) = {0m + 1 otherwise.ifacti°naisindependent'

where m is the maximal degree o f dependence o f immediate suc- cessors o f a.

Definition 8 is only applicable to acyclic action-dependence graphs. To apply it to cyclic graphs, we need to transform the initial graph to an acyclic one in which every node corresponds to a maximal strongly connected components o f the initial graph. The degree o f dependence o f a node in the original graph is then defined as the degree o f dependence o f the strongly connected component to which that node belongs.

In Figure 5, the degree o f dependence is shown in parenthesis next to each action. A n action-dependence graph and degrees o f dependence can be computed in polynomial time using standard graph algorithms. In Figure 6, we present the D B C P (Dependency- Based Concurrent Planning) algorithm, which makes use o f an action- dependence graph to prune the search space. The algorithm has four input variables: the set A o f all joint actions inserted into the plan so far, the current subgoal S u b g o a l , the set o f available ac- tions A S , and the set o f available agents n. S u b g o a l is a list o f preconditions that have not been achieved. At the beginning, it is initialized to the goal G. The algorithm works backwards. That is, it starts with the goal preconditions and tries to satisfy them by choosing appropriate actions, which" in turn requires satisfying new preconditions, and so forth, until all preconditions are satisfied or cannot be satisfied, given the set o f available actions A S and num- ber o f agents n. A t each step D B C P chooses a minimal action set that satisfies a subgoal, thereby reducing both the cost o f search and the total cost o f the plan.

48

DBCP(A, Subgoal, AS, n) A+-- O AvailableAttackers~-- n Satisfied~-- 0 while (Subgoal ~ 0) and (AvailableAttackers > 0) do

choose Precondition Q from Subgoal choose action A~ad from A S with minimal dependence that

brings about Q I f Aadd does not exist then return failure Satisfied*-- Satisfied U Q JointAction ~ A~da Subgoal~-- Subgoal - Q AvailableAttackers ~-- AvailableAttackers - 1 for each Postcondition P in Aaad

i f P ~ Satisfied t h e n Satisfied ~-- Satisfied U P for each action Acon on which action Aaaa depends do

Flag ~-- false for each precondition P in Acon do

if (P ~ Q) and ( P ~ Satisfied) then do

Q ~ - - Q u P Flag ~ - true

enddo enddo if (Flag) then do

i f (AvailableAttackers = 0) then return failure else AvailableAttackers ~-- AvailableAttackers - 1

JointAction ~-- JointAction U Acon enddo

enddo A ~ - A u JointAction

enddo i f Subgoal = 0 then return A else return failure

Figure 6: Dependency Based Concurrent Planning (DBCP) al- gorithm

5. V U L N E R A B I L I T Y A N A L Y S I S F O R C O - O R D I N A T E D A T T A C K S

Planning used for model checking has proved to be practical and general enough to tackle a wide range o f problems [12]. Efficient planning algorithms (including OBDD-based algorithms) can gen- erate plans automatically and deal with large problem spaces. Us- ing planning for vulnerability analysis has several advantages:

• It provides a uniform approach to both system and adversary modelling.

• When a security property is invalidated by a planner, the planner produces a coordinated-attack plan that can be used by attackers to synchronize their actions. Moreover, a com- plete planner can generate all plans invalidating the s e c u f t y property. Knowing the attackers' plans can help a security analyst to prevent attacks and plan incident response.

• A coordinated-attack model can be used for a model-based intrusion detection which looks for specific coordination pat- terns between users' activities,

• Planning can help not only vulnerability analysis, but also robotic attacks in which several intelligent agents automati- cally produce and launch a coordinated attack.

To perform plan-based model checking, we use the adversary's instrumental capacity (AS, n) as a system model, L P G as a com- plete and sound planner [11], and a specification o f the security property p written in CTL. Unlike other system models implemented as a finite state transition system, our model is parametric: it de- pends on the number o f available attackers, n. For different n, the planner will generate different transition systems. A t first sight, it seems unusual that the system model depends on an exogenous parameter, n. On the other hand, it is quite natural to evaluate a system against different attack scenarios. For example, a system which is safe for a given set o f actions A S and a given number o f attackers n, might not be safe for the same action set A S and n + 1 attackers.

In our case, model-checking works as follows. For a given safety property p written in CTL, we generate the set o f all states where p holds:

States(p) = {s E S , p E L ( s ) }

Then, we set the goal states S c = States(p). Finally, we run the planner with A S , n, S c as input variables. A complete planner is guaranteed to generate a plan (if such a plan exists) starting at the current state So and reaching one o f the goal states s, s E S o . The existence o f a plan invalidates the security property p, while the non-existence validates it. Note that a property is always checked for a fixed set o f actions A S , and the maximal number o f attackers.

6. I M P L E M E N T A T I O N In this s e c t i o n , we show how the race condition attack shown in

Figure 3 can be modelled and analyzed using Planning Domain Description Language, PDDL, and implemented in LPG (Local search for Planning Graphs) [ 11 ]. We have chosen the latest version P D D L 2.1 used in the Third International Planning Competition in 2002 [9]. P D D L 2.1 is a versatile description language capable o f expressing temporal and numerical properties o f planning domains [81.

Before choosing LPG, we studied the applicability o f several planners to the coordinated attack domain. A major challenges was the representation o f concurrent actions. Initial attempts to model the coordinated attack domain using non deterministic plan- ners, such as M B P [ 1 ], failed. One o f the major drawbacks o f M B P is its inability to support temporal and numerical features o f ac- tions, such as action duration and the invariants that must hold over the duration. In PDDL, a durative action is represented by two atomic actions corresponding to the end points o f the durative ac- tion. P D D L also allows for concurrent execution o f actions, pro- vided that the end-points o f one action do not interact with the end points or with the invariants o f another action.

L P G uses a compact representation o f a planning graph to define a search neighborhood and to evaluate its elements using a parame- terized function. The function assigns weights to different types o f inconsistencies in the current plan, and dynamically evaluates them during search, using discrete Lagrange multipliers. Whereas most o f the current planners estimate plan quality based on the number o f actions exclusively, L P G also takes into account the execution cost o f an action. L P G uses this information to produce plans o f good quality by minimizing an objective function which includes the overall execution cost o f a plan. [11].

We modelled the coordinated-attack domain with P D D L 2.1 and used L P G to generate plans. The domain model is the following. Two users (user1 and user2) simultaneously log on to a system, both having access rights to file f l , which is a symbolic link to file f 2 . User1 executes open_file with f l as argument. In the meanwhile, user2 removes the symbolic link from f l to f 2 and

49

;; Version L P G - v l . 0 ;; Seed 100348977 ;; Command line: ./lpg -o attack_domain.pddl - f attack_problem -n 1 ;; Problem: attack_problem ;; Search time: 0.050 Parsing time: 0.010 Mutex time: 0.000 ;; Actions: 5 Execution cost: 5.000 Duration: 9.000

0.001: 0.002: 2.003: 3.004: 4.005:

(LOG_USER1 U2 F1 TF)[2.000] ;; cost 1.000 (LOG_USER2 U1 F1 TF)[2.000] ;; cost 1.000 (OPEN_OPENFILE U2 F1 TF)[1.000] ;; cost 1.000 ( C H A N G E J A N K U1 F1 TF)[1.000] ;; cost 1.000 (CLOSE_OPENFILE U2 F1 TF)[5.000] ;; cost 1.000

Time 60

Figure 7: LPG-generated attack plan for the race condition do- main

creates a new symbolic link f l to the target file t f , which could be /etc/shadow, for example. As a result, user1 opens the target file t f which he is not authorized to access.

To succeed in the attack, attackers' actions must be synchro- nized. For example, action open_file must be executed first, and change_link must be executed after open_file has started, but be- fore it finishes.

The attack domain consists o f 5 durative actions which cause transitions (defined as a single action or a combination o f actions) between states in the attack graph. We modelled open_file as a com- plex action consisting o f two atomic actions open_open f i l e and close_open file. First, open_file starts with open_open f i l e rais- ing a signal which is captured by change_link and used as a precon- dition for starting change_link. This guarantees that change_link can start only after open_openfile has started . After finishing, change_link raises another flag which is used as a precondition for close_openfile to finish. In other words, we used temporal synchro- nization constraints (that hold at the start and end o f the action) to ensure that change_link is executed between the start and the end o f open_file.

The plan generated by the L P G planner for the race-condition attack is shown in Figure 7. The P D D L 2.1 code for the attack domain, attack problem, and the output o f the planner are included in Appendix A for reference.

In Figure 7, the second logging operation is executed at m o m e n t 0.002, whereas the first logging starts at 0.001. The difference is due to the fact that the actions will always be sequential unless executed in parallel processing environments.

7. C O N C L U S I O N S In this paper we defined the notion o f coordinated-attack graph,

proposed an algorithm for efficient generation o f coordinated-attack graphs, demonstrated how coordinated-attack can be used for vul- nerability analysis, and discussed an implementation o f a coordinated- attack graph.

Coordinated-attack graphs can facilitate an wide range o f tasks, such as model checking, opponent modelling, intrusion response, sensor configuration, and so forth.

There are several open directions for future research: automatic intention recognition for coordinated attacks, adversafial planning, automatic sensor configuration for detecting coordinated attacks, etc. Solving all these problems will help improve systems security against coordinated attacks.

8. A C K N O W L E D G E M E N T S The authors thank the anonymous reviewers for their helpful

comments and suggestions.

9. R E F E R E N C E S [1] P. Bertoli, A. Cimatti, M. Pistore, M. Rovefi, and P. Traverso.

MBP: a model based planner. In JCAI'O1 Workshop on Planning under Uncertainty, pages 71-78, 2001.

[2] C. Boutilier and R. Brafman. Partial-oder planning with concurrent interacting actions. Journal of Artificial Intelligence Research, 14:105-136, 2001.

[3] C. Boutilier, T. Dean, and S. Hanks. Planning under uncertainty: Structural assumptions and computational leverage. In M. Ghallab and A. Milani, editors, New Directions in AI Planning, pages 157-172. IOS Press (Amsterdam), 1996.

[4] S. Brainov and T. Sandholm. Reasoning about others: Representing and processing infinite belief hierarchies. In Proceedings of the Fourth International Conference on Multiagent Systems, pages 71-78, Boston, 2000.

[5] S. Braynov. On future avenues for distributed attacks. In Proceedings of the 2nd European Conference on Information Warfare and Security (ECIW), Reading, UK, 2003.

[6] D. Carmel and S. Markovitch. Opponent modeling in m u l t i - a g e n t systems. In G. WeiB and S. Sen, editors, Adaptation and Learning in Multi-Agent Systems, pages 40-52. Springer-Verlag: Heidelberg, Germany, 1996.

[71 S. Eckmann, G. Vigna, and R. Kemmerer. STATL: An attack language for state-based intrusion detection, 2000.

[8] M. Fox and D. Long. PDDL 2.1: Techical Documentation. April 25, 2003.

[9] M. Fox and L. Long. PDDL 2.1: An extension to PDDL for expressing temporal planning domains. Technical Report, Department o f Computer Science, University o f Durham, U K , 2001.

T. Garfinkel. Traps and pitfalls: Practical problems in in system call interposition based security tools. In Proc. Network and Distributed Systems Security Symposium, February 2003. A. Gerevini and I. Serina. LPG: a planner based on planning graphs with action costs. In Proceedings of the Sixth Int. Conference on A1 Planning and Scheduling (AIPS'02), pages 13-22, 2002.

E Giunchiglia and P. Traverso. Planning as model checking. In In Proceeding of the Fifth European Conference on Planning, pages 1-20, 1999. A. Householder, K. Houle, and C. Dougherty. Computer attack trends challenge internet security. Security and Privacy, 1, 2002. R. Jensen and M. Veloso. Obdd-based universal planning for synchronized agents in non-deterministic domains. Journal of Artificial Intelligence Research, 13:189-226, 2000. S. Jha, O. Sheyner, and J.Wing. Minimization and reliability analyses o f attack graphs, 2002. S. Jha, O. Sheyner, and J.Wing. Two formal analyses o f attack graphs. In Computer Security Foundations Workshop (CSFW), pages 49-63, Nova Scotia, Canada, 2002. S. Jha and J. Wing. Survivability analysis o f networked systems. In International Conference on Software Engineering, pages 307 - 317, Toronto, Canada, 2001. J.R. Burch, E.M. Clarke, K.L. McMillan, D.L. Dill, and L.J. Hwang. Symbolic Model Checking: 1020 States and

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[171

[181

50

Beyond. In Proceedings o f the Fifth Annual IEEE Symposium on Logic in Computer Science, pages 1-33, Washington, D.C., 1990. IEEE Computer Society Press.

[19] N. Kushmerick, S. Hanks, and D. Weld. An algorithm for probabilistic least-commitment planning. In Proceedings o f the Twelfth National Conference on Artificial Intelligence (AAAI-94), volume 2, pages 1073-1078, Seattle, Washington, USA, 1994. A A A I Press/MIT Press.

[20] J. Legon. FBI seeks to trace massive Net attack. CNN, October 28, 2002.

[21] U. Lindqvist and R Porras. Detecting computer and network misuse through the production-based expert system toolset (p-best). In Proceedings o f the 19991EEE Symposium on Security and Privacy, pages 146-161, Oakland, California, 1999.

[22] C. Phillips and L. Swiler. A graph-based system for network-vulnerability analysis. In Proceedings o f the i998 Workshop on New Security Paradigms, pages 71-79, 1998.

[23] B. Schneier. Attack trees: Modeling security threats. Dr. Dobb 's Journal, December, 1999.

[24] L. Swiler, C. Phillips, D. Ellis, and S. Chakerian. Computer-attack graph generation tool. In DARPA Information Survivability Conference and Exposition, pages 146-161, Anaheim, California, 2001.

[25] S. Tzu and L. Giles. Sun Tzu on theArt o f War. Kegan Paul Intl, 2002.

[26] G. Vigna, S. Eckmann, and R. Kemmerer. Attack languages. In In Proceedings o f the IEEE Information Survivability Workshop, 2000.

A P P E N D I X A P D D L 2.1 code for the a t t a c k d o m a i n

(define (domain attack_domain) (:requirements :strips :equality :typing :fluents :durative-actions)

(:types users files slink) (:predicates

(loggedl ?u - users) (logged2 ?v - users) (access ?u - users ? f - files) (opening ?p - files) (opened ?q - files) (sym_link ?x -files ?y - files)

) (:durative-action log_user 1

:parameters (?r - users ? f - files ?g - files) :duration (= ?duration 2) :condition (at start (not (loggedl ?r))) :effect (and

(at end (loggedl ?r)) (at end (access ?r ?f))

) )

(:durative-action log_user2 :parameters (?r - users ? f - files ?g - files) :duration (= ?duration 2)

:condition (at start (not (logged2 ?r))) :effect (and

(at end (logged2 ?r)) (at end (access ?r ?f))

) )

(:durative-action open_openfile :parameters (?r - users ?f - files ?g - files) :duration (= ?duration 1) :condition (and (at start (loggedl ?r)) (at start (access ?r

?t))) :effect (at end (opening ?f))

)

(:durative-action change_link :parameters (?l - users ?s -files ?t - files) :duration (= ?duration 1) :condition (and (at start (logged2 ?1)) (at start (opening ?s))) :effect (at end (sym_link ?s ?t))

)

(:durative-action close_openfile :parameters (?r - users ? f - files ?g - files) :duration (= ?duration 5) :condition (and (at start (loggedl ?r)) (at start (access ?r ?f))

(at start (opening ?f)) (at start (sym_link ?f ?g))) :effect (and

(at end (opened ?g)) )

P D D L 2.1 code for the a t t a c k d o m a i n

(define (problem attack_problem) (:domain attack_domain) (:objects

u l - users u2 - users f l - files t f - files

) (:init

(not (loggedl u l ) ) (not (loggedl u2)) (not (logged2 u 1)) (not (logged2 u2))

) (:goal

(opened tf) ) (:metric minimize (total-time)))

51