The Technology Research Of Network Security Risk Assessment Based On Attack Graphs

With the rapid development of network technology and increasing networkattacks, more and more attention is paid to the network security. Network security riskassessment is an effective method to discover and handle the network securityproblems. Most methods of traditional network security risk assessment are forindependent vulnerabilities of hosts and ignore the interrelation among vulnerabilities.The individual vulnerabilities are not serious for network security, but the effectivecombined vulnerabilities will seriously damage network security condition.The dissertation presents a new method of network security risk assessmentbased on attack graphs which show the attack scenario the attacker exploitsvulnerabilities and dependency relationship among vulnerabilities to attack targetnetwork. We measure the amount of security risk and search the minimum costnetwork hardening measures based on attack graphs. The dissertation presents anetwork security risk framework based on attack graphs, which consists of fourmodules: information model representation, attack graph generation, risk computation andsecurity hardening.In the course of building attack graph, the dissertation firstly proposes the globalattack graph which represents all attack paths the attacker maybe exploit. Aframework for building the global attack graph is developed and the correspondingbuilding algorithm is presented. Because loop paths maybe exist in the global attackgraph, it is difficult to analyze the network security based on the global attack graph.The dissertation discusses three kinds of loop paths existed in attack graphs andproposes the methods of elimination loops. Then the dissertation provides a reversalsearching algorithm to generate the optimal subgraph of the global attack graph. Theoptimal subgraph eliminates all loops and is suitable for security analysis. We propose the acquisition algorithm of attack paths and decision algorithm whether an attackpath is the simplest or no in the subgrph.Because of the dependency among vulnerabilities, the dissertation proposes theaccurate calculation method based on Bayesian network for calculating nodeoccurrence probability. This method provides the accurate calculation approaches onthe condition of the parallel attack nodes, series attack nodes and attack experienceconsidered. We prove the correctness of the method by experiments. Because theBayesian network is only suitable for acyclic graph, the calculation method based onBayesian network is only for acyclic attack graphs and is exponential on algorithmcomplexity. So the method can not apply to large scale network.In order to calculate the node occurrence probability in large and cyclic attackgraphs, the dissertation proposes a maximum risk probability calculation methodbased on bucket principle. The method applies matrix multiplication to deducemultistep maximum risk adjacency matrix. Then the global maximum risk adjacencymatrix is generated by superimposing these multistep maximum risk adjacencymatrices, which presents risk probabilities of all nodes. Because the method onlyadopts the operation of matrix multiplication, the time complexity is polynomial andis suitable for large scale network. Another advantage of the method is to correctlydiscover and dispose loop in attack graphs. The dissertation discusses the conditionsthat the node is inside loop and the node is outside loop but it can be inside loop by aseries of attacks, then methods are proposed to discover and dispose in differentconditions.When the risk value of the node is beyond acceptance, security measures must beapplied. In order to ensure target node safety, security measures must cut off all attackpaths to target node. The dissertation represents the concepts of critical attack set andminimum critical set, and discusses that the problems of minimum critical set areequivalence of hitting set problem. Because the attack node depends on itsprecondition attribute nodes, the attack node can not disable without disabling itsprecondition attribute nodes. Only the initial node in attribute nodes can be disableddirectly. Previous work is assumption that the initial node can be independently disabled and there is one-to-one correspondence between the initial node and thehardening measure. This assumption is not true in most conditions. A hardeningmeasure can be applied to disable several initial attribute nodes. So the dissertationdrops this assumption and explains that the problem of the minimum cost hardeningmeasures set calculation can be converted to the weighted set cover problem. Thedissertation provides formal description of the minimum cost network hardeningproblem.To solve the minimum cost network hardening problem, the dissertation firstlypresents the method based on traditional security measures. Because we drops theassumption that initial attribute nodes can be independently disabled and the conceptof hardening measures is introduced, this method is more exactly. The two solvingsteps of this method are both NP-complete problem. Thus the time complexity of thismethod must be high. In order to improve the calculation efficiency, the calculationmethod of the minimum cost network hardening measure set based on conversion ispresented. We prove the equivalence of the minimum cost network hardening problemand the weighted hitting set problem and present the method of converting theminimum cost network hardening problem to the weighted hitting set problem. Thenwe discuss the expand problem of the minimum cost network hardening problem.Because the equivalence of the minimum cost network hardening problem andthe weighted hitting set problem and the weighted hitting set problem has been provedto be NP-complete, the algorithm complexity of exactly solving the minimum costnetwork hardening problem is exponential and is not suitable for large scale network.The dissertation provides approximation algorithm for the weighted hitting setproblem, and applies it to the calculation method based on traditional securitymeasures and the calculation method based on conversion. Then comparative analysisof the two methods is presented and comparative experiments on five different scaleattack graphs are presented. The result showed that the calculation method based onconversion has better computational efficiency and approximation ratio than thecalculation method based on traditional security measures.