Scalable, Graph-Based Network Vulnerability Analysis

Posted on | Edited on | In

Introduction

This post refers to Paper “Scalable, Graph-Based Network Bulnerability Analysis”, it provides a generation method of attack graph towards specific goals。
As an complicated attack is in need of a set of exploits, and each exploit needs multiple pre-conditions and can lead to a set of post conditions. So we can find all attributes that is concerned to a goal and all the potential exploits.

Model

  • A set of attributes $A={a_1,…,a_i,…,a_n}$
  • A set of exploits $E={e_1,..,e_k,…,e_m}$
  • A set of initially satisfied attributes $ U \subset A $
  • Monotonicity: Each condition is irreversible, which means once an attributed is satisfied, it will always remain satisfied.

Classification

Each node in the graph represents an attribute and an edge means an exploit, so first of all each attribute is combined to the exploits it concerns(pre-condition and post-condition is seperated).

Secondly, classify all the attributes into different layers, the initially satisfied attributes are classified into layer 0, the number of layer means the number of exploits needed to achieve this attribute.

Now we have a classified set of attributes.

Algorithm

Algorithm of marking attributes

Analysis

Three different algorithms are proposed to find the potential paths of exploits to achieve the final goals, findMinimal, findAll and findShort.
We’ve already have:

  • A set of marked attributes and their corresponding exploits $E={e_1,..,e_k,…,e_m}$
  • A set of target attributes to be satisfied S.
    return:
  • An attack, which means a serie of exploits to meet the target att.

findMinimal

Find an attack with minimal number of exploits. (There is something can’t be understood in paper: step 3.)

findMinimal(S, att)
   $S\neq\emptyset$
     if each $s_i \in S$ is marked
       1. Choose a minimal set of expoits $E_m$ where eachs $s_i \in S$ is a post-condition of
       some $e_j \in E_m$.
       2. Prepend all the $e_j \in E_m$ to att.
       3. Select a minimal set $E’_m \subset E_m$
       4. S’ is the set of unsatisfied pre-conditions in $E’_m$.
       5. Do findMinimal(S’,att)
     endIf
   endIf

findAll

Find all potential attacks which can meet the target.

findAll(S, E$_{all}$)
   if $S \neq \emptyset$
     if each $s_i \in S$ is marked
       1. Add all exploits $E_s$ that satisfy $S$ into $E_{all}$
       2. S’ is the set of unsatisfied pre-conditions in $E_{all}$
       3. Do findAll(S’,$E_{all}$)
     endIf
   endIf

findShort

Find the shortest path (lowest level) to meet the target.

findShort(S, att)
   if $S \neq \emptyset$
     if each $s_i \in S$ is marked
       1. For each $s_i$, find $e_s$ with the smallest level n
       2. Add all $e_s$ = $E_s$ into att
       3. S’ is the set of unsatisfied pre-conditions in $E_s$.
       4. Do findShort(S’,att)
     endIf
   endIf

comment

This is a basic manual generation method, which helps generate attack graph of specific attacks and do analysis through different point of view. It provides a representative method of attack graph, which contains both advantages and disadvatages of classical attack graph method.
Users have to know all the pre and post conditions of all the exploits, and all existing attributes of all the nodes.

Reference

[1] Ammann P, Wijesekera D, Kaushik S. Scalable, graph-based network vulnerability analysis[C]// ACM Conference on Computer and Communications Security, CCS 2002, Washington, Dc, Usa, November. DBLP, 2002:217-224.