The Key Techniques Of Attack Graph Generating For Large-scale Network

Attack graph is a model-based vulnerabilities assessment method. Attack graph technology analyzes the relationships among vulnerabilities, and uses graph displaying all of the attack paths which threat network security. Network adminstrators can use attack graph to observe the interrelations between vulnerabilities easily, and select the minimum cost to harden networks. Attack graph technology includes attack graph generation technology and attack graph analysis technology. Attack graph generation technology is a method, which uses target network information and exploit patterns to construct attack graph, and is the base of attack graph technology. Attack graph anaylsis technology is a method, which can get the key node and path or quantify the vulnerability by analyzing attack graph.Attack graph generation technology suffers from two problems. One is scalability problem. Because of increasing hosts and vulnerabilities, and the high time complexity of current attack graph generation algorithms, it is necessary to improve the scalability of attack graph generation algorithms. The other is reachability model problem. Host reachability is a requirement for forming attack path between single vulnerability, and is an important prerequisite for generating attack graph. The current reachability model express incomprehensive and can't compute automatically. So, it is necessary to build a host reachability model, which is comprehensive, appropriate abstract and calculated automatically. Then, a algorithm of computing host reachability based on the host reachability model should be proposed.In order to solve the above problem, this paper has studied the key technology of attack graph generation. The main work has the followings:Firstly, we have studied the typical attack behaviors and their dependent reachability based on the hierarchical model of TCP/IP protocols, and have established a host reachability model based on TCP/IP protocols. We have proposed a algorithm of computing host reachability automatically. This algorithm inputs ACL rules and route rules, and ouput the reachability among all of the hosts, which are essential input of attack graph generation algorithm.Secondlly, in order to improve the scalability of attack graph generation algorithm, we have designed and implemented an Attack Graph Generation Algorithm on Parallel (PAG). Firstly, PAG algorithm divides the task of generating attack graph into several sub-tasks. Secondlly, all of the sub-tasks are handled pallerel on multiple processors, and every sub-task constructs a sub-attack graph. Lastly, the last attack graph is formed by combining the whole sub-attack graphs. Experiments and research show that the performance of PAG is better than the other algorithms.Lastly, we have tested the required time and funticon of the above two algorithms in the networks of different sizes. Experimental results show the validity and correctness of the above two algorithms.