Searching Forward Complete Attack Graph Generation Algorithm Based on Hypergraph Partitioning

Attack graph is an effective method for network vulnerability analysis, existing methods of attack graph can't meet the requirements of the dynamical analysis of the large-scale complex network. In this paper, we proposed a searching forward complete attack graph generation algorithm based on hypergraph partitioning. First, ensure the load balancing of each of the computing agents by hypergraph partitioning; second, summarize various new attack templates; third, propose vulnerabilities exploited assumption, improve the efficiency of attack graph generation, reduce the recomputed work of attack graph generation dynamically; last, propose a new idea that generating the attack graph from the vulnerabilities to attacker reversely, ensure the integrity of vulnerabilities analysis, reduce the additional store memory and computing resources