Abstract:

In order to avoid the combination of states occurred in the generation of attack graphs while analyzing network vulnerabilities and to make the attack graphs available for analyzing the multitargets’ vulnerabilities, a new method of generating attack graphs based on greedy policies is proposed. The method introduces the  network node correlations, uses greedy policies to reduce the amount of vulnerabilities, chooses the attack routes that allow attackers to gain network node priority with the greatest potential and generate the attack graphs with those attack routes. The algorithm analysis and the experimental results show that the cost of time and space of the method is the polynomial level of the network node number and the network node correlation number, which means it has solved the problem of the great combination of states effectively. The attack graph it generates covers all network nodes that attackers can access, so the method can be used to analyze the multitargets’ vulnerabilities.

Key words: network vulnerability analysis;network node correlation;multitargets attack graph;greedy policy