# A Security Assessment Mechanism for Software-Defined Networking-Based Mobile Networks
## 4 Modeling Network Attack Using Attack Graph
### Definition of Attack Graph and Generation Algorithm  
To define and generate attack graphs for SDN-MNs, we use previous work of our group which proposed an attack graph generation algorithm to address the efficiency problem [26].  
The basic concepts of attack graph are defined as follows:  
**Definition 1**: _Attack Graph._ An attack graph is defined as a tuple \(AG=(A,S,G,E_{b},E_{f})\). In the definition, \(A\) denotes Action objects, \(S\) denotes State objects and \(G\) denotes Goal objects. Also \(E_{b}\) denotes backward pointers. Finally, \(E_{f}\) denotes forward pointers.  
The attack graph definition is shown in Figure 5. In Figure 5, real lines denote forward pointers and dotted lines denote backward pointers. Rings identify the instances of State objects, and squares represent the instances of Action objects, and triangles represent the instances of Goal objects.  
In the example, _state0_ is the initial security state of the network. When action \(a1\) or \(a2\) is performed, the security state transfers to _state1_. Based on _state1_, if the attacker performs action \(a3\), the security state continues to transfer to state3. At the end, the attacker reaches the attack goal. The rest of the attack graph has the same meaning.  
According to the definition of attack graph given above, the attack graph generation algorithm generates attack graphs based on a network knowledge base. The network knowledge base includes vulnerabilities, network connectivity, _etc._ We use a \"state evolution process\" algorithm to generate attack graphs. The state evolution process is illustrated in Figure 6.  
Figure 5: Attack graph definition for SDNs.  
Figure 6: State evolution process for an attack graph.  
Until the process meets termination condition, state objects are recursively evolving in the process. In each cycle, the process applies all possible malicious actions. The process includes several function entities as follows:  
1. Privilege propagation entity The privilege propagation function entity is responsible for propagate the privilege according to the current network state.
2. Connectivity analysis entity The connectivity analysis function entity firstly analyzes the network topology and filtering policy information and then it produces the connectivity between any two nodes.
3. Exploits execution entity The exploits execution function entity tries to apply all exploit objects to the state objects.
4. Backward marking entity The backward marking function entity removes all the former indicates. After actions are applied, it marks re-satisfied items with a fresh indicate for the consequences.
5. Graph building entity The graph building function entity generates a forward pointer or backward pointer according to the actions' trigger.
6. Goal check entity The goal check function entity confirms whether the attack is successful in the current security context.
7. Termination check entity The termination check function entity confirms whether the process has no more ways to evolve. The process should be terminated once there is not a forward pointer. After a complete procedure, the generated attack graph is derived. For more detailed information about the sub-modules of the process readers can refer to [26].