【作者】 闫峰；

【导师】 刘淑芬；

【作者基本信息】 吉林大学 ， 计算机系统结构， 2014， 博士

【摘要】 随着网络技术的飞速发展，网络攻击事件的不断增多，网络安全问题越发引起人们的关注。网络安全风险评估是一种发现和处理网络安全问题的有效方法。传统的网络安全风险评估方法大都针对主机的孤立脆弱性的评估，没有考虑脆弱性间的依赖关系给网络的安全风险带来的影响。独立脆弱性可能不会对网络造成严重危害，但多个脆弱性被有效的组合起来却可能对网络造成巨大伤害。本文提出基于攻击图的网络安全风险评估方法，将攻击图技术应用到网络安全风险评估中，通过攻击图展示攻击者利用网络中脆弱性及脆弱性间依赖关系综合入侵目标网络的攻击场景，并在此基础上计算网络的安全风险和寻找最小代价的网络加固措施。本文给出了基于攻击图的网络安全风险评估框架，它包括网络信息模型化表示、攻击图生成、风险计算及安全加固四个模块。在攻击图的构建中，文章首先提出了构建全局攻击图。全局攻击图从攻击者最大限度获得网络安全要素的角度，描绘一切可被攻击者的采用的攻击路径。为了构建全局攻击图，本文提出全局攻击图的构建框架，并给出全局攻击图的构建算法。由于全局攻击图描述了任意两个节点间的攻击路径，因此可能存在环路，这给基于攻击图的安全分析带来困难。为此，本文对攻击图中可能存在的三类环路进行讨论，给出消除环路的办法，并提出逆向搜索算法生成关于攻击目标的不含环路的最优攻击子图。在目标最优攻击子图基础上，本文对到达目标的攻击路径进行分析，并给出了获取攻击路径的算法及判断攻击路径是否为最简攻击路径的判定算法。由于攻击图的各节点间相依赖，为了准确计算各节点的发生概率，本文提出基于贝叶斯网络的精确概率计算方法。该方法分别给出攻击节点间的串联、并联及考虑攻击经验情况下，节点发生概率精确计算办法，并通过实例验证了方法的正确性。但是，由于贝叶斯网络本身是无环图，基于贝叶斯网络概率计算方法也只能适用于无环的攻击图，且计算繁杂度为指数级，不适合大规模网络使用。为了在含环的大规模攻击图中计算节点发生概率，根据“木桶原理”，本文提出了基于邻接矩阵的最大风险概率计算方法。该方法通过矩阵相乘运算推导出多步最大风险邻接矩阵，并将1步到n步最大风险邻接矩阵叠加，生成全局最大风险邻接矩阵，计算出全部节点的风险概率。该方法由于只采用矩阵相乘运算，因此计算繁杂度为多项式级，适用于大规模网络。该方法另外一个优势是能够正确识别和处理环路，对节点在环路内部及节点虽然在环路外部，但是经过若干步攻击会进入环路内部情况分别讨论，给出相应的识别和处理办法。通过风险计算得了到各节点的风险值，对超出接受程度的风险，必须采用安全加固措施消除风险。为了保证目标节点的安全，所采用安全加固措施必须能够切断所有到达目标节点的攻击路径。为此，本文描述关键攻击集及最小关键攻击集的概念，阐述了求解最小关键攻击集等价于碰集问题。由于攻击图中攻击节点依赖于前提属性节点，因此无法直接通过消除关键攻击集中的攻击节点阻止攻击，只能通过消除攻击节点所依赖的初始属性节点来阻止攻击。以前的研究文献中都假设初始属性可以独立消除，初始属性节点与加固措施一一对应，求解最小代价网络加固问题就是求解最优弥补集问题。但是，这种假设在很多情况下是不成立的，一个加固措施往往可同时消除多个初始属性节点。因此，本文放弃了这种假设，阐述了求解最小代价加固措施集问题，可转化为数学中的加权集合覆盖问题。本文还给出最小代价网络加固问题形式化描述。为了求解最小代价网络加固问题，本文首先提出基于弥补集的计算方法。该方法采用了传统的基于弥补集的计算思想，但放弃了初始属性节可以独立消除的假设，并且引入加固措施及加固措施集等思想，所以更能精确求解。但是，基于弥补集的计算方法的两个步骤都是NP完全问题，所以对应算法的复杂度必然很高。为了提高计算效率，本文提出基于转换的最小代价加固措施集计算方法，证明了最小代价网络加固问题与加权碰集问题的等价性，给出了将最小代价网络加固问题转化为加权碰集问题的办法，讨论了最小代价网络加固问题的扩展问题。由于最小代价网络加固问题与加权碰集问题等价，而加权碰集问题是已被证明的NP完全问题，因此精确求解最小代价网络加固问题的算法的时间复杂度必然为指数级，不适合大规模攻击图。为此，本文针对碰集问题提出近似算法，并将其应用基于弥补集的计算方法和基于转换的计算方法中。本文对基于弥补集计算方法和基于转换的计算方法进行对比分析，并通过五个不同规模的攻击图实例进行实验对比，结果表明基于转换的计算方法在计算效率和接近全局最优解的近似度上都优于基于弥补集计算方法。更多还原

【Abstract】 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.更多还原