Efficient Attack Graph Technology Based On Gradient Attack Monotonicity Assumption

With the rapid development of computer network technology, network security is confronted with more and more threats of malicious usage. Network attacks become more efficient and intelligent than ever. It is commonly known that some network attacks often take a multi-step combination of atomic attacks by taking advantage of multiple vulnerabilities. In view of this multi-step combined atomic attacks caused by vulnerabilities, it is the focus of research to carry out effective identification of potential threat, scientific evaluation of the risk of network security, and building a network security technology system to guide the construction of the current network security risk assessment.Attack graph is a key technology of network security analysis. Based on the attack graph-related technology research, this paper proposed the concept of network security gradient (NSG) to reflect the direction of network attacks and network defense hierarchy. Accordingly, we improved the monotonicity assumption to reduce the size of attack graph. By using the concept of network security gradient, the generation of attack graph could be divided into sub-tasks, as a result, we designed a parallel of the attack graph generation algorithm. Under the assumption of the gradient attack, we implemented calculating metrics to get the possibility of every single atomic attack, which made the attack path be quantitatively analyzed.According to the characteristics of the network, we proposed two gradient algorithms to mark network security gradient automatically. First, we proposed a static network security gradient marking algorithm. We tried to translate the value of equipment, and the defense configuration information of the network into the gradient. Then, we introduced a dynamic network security gradient marking algorithm to determine the gradients of subnets by monitoring network traffic. Finally, we combined these two algorithms, and marked network security gradients of a sample network. Experiment shows that when the network size was 400, automatic gradient marking error rate remained at 12%.For the attack graph generation efficiency was not high, we made parallel graph generation algorithm based on the gradient attack assumption. First, we introduced NSG and gradient attack monotonicity assumption (GAMA) to reflect both the direction of network attacks and hierarchy of network defense. Secondly, after marking the NSG of the network environment, we described a parallel algorithm to generate attack graph based on GAMA. Thirdly, an algorithm complexity analysis was made to prove that the parallel attack graph generation algorithm could highly improve the attack graph generation efficiency and reduce the attack graph complexity. The experiments showed that when the network size is 400, the traditional attack graph generation algorithm was 30 times longer than the parallel algorithm in terms of time spending.For quantitative analysis of attack path, we first proposed an attack path search algorithm on a given target. Then, we introduced a metric system for atomic attack success rate (AASR) calculating to reflect the likelihood of a successful atomic attack. Thirdly, we showed administrators how to maintain network security according to the AASR, and explored attack paths which really threaten network security. Finally, we defined atomic attack appearance (AAP), which referred to the average occurrence rate on attack paths, to assess the importance of a single atomic attack and thus fix key vulnerabilities in time.Generally, our methods not only effectively improve the attack graph generation algorithm and support the attack graph analysis techniques, but also play a positive role in promoting attack graph technologies development in future.