Automated generation of attack graphs always encounters efficiency problem when using attack graphs to analyse the vulnerabilities of large networks. This paper proposes a backward approach to attack graphs generation based on attack patterns with great efficiency. Firstly, we propose a novel model of network based on the key attributes of networks, which is improved upon the previous models. This model optimizes the network connections and downsizes the network. Secondly, after abstracting a large number of vulnerabilities, we sum up a few attack patterns, based on which we build an efficiency approach to attribute attack graphs generation. Thirdly, the backward approach we propose solves the problem of loop attack paths. Finally, the experimental result shows that, our backward approach generates partial attack graphs which illustrate the potential interrelations among the known vulnerabilities just related to the given attack goal in the targeted network, while other forward approaches generate full attack graphs. And we show the experimental evidence that our attribute attack graph generation algorithm is very efficient, the complexity of the algorithm is between O(|H|2) and O(|H|3).%在使用攻击图方法分析网络中脆弱性之间关系时,网络规模一直是制约攻击图生成算法效率的根本因素.本文提出了一个基于攻击模式的高效攻击图反向生成算法.首先,对已有网络模型做出改进,提出了新型的基于网络中关键属性的模型,该模型使用子网掩码压缩网络连接关系,达到缩小网络规模的目的.其次,使用网络模型中的关键属性对脆弱性进行描述,进而抽象出攻击模式,使攻击图生成算法建立在有限的攻击模式上,提高了算法效率.再次,提出了基于攻击模式的属性攻击图自动生成算法,该算法根据攻击目标反向推导出攻击路径.此外,算法在生成属性攻击图时,能够识别攻击路径中的“圈”,只保留有意义的“圈”,且不进入“圈”的循环之中.最后,通过实验和分析表明,算法生成的属性攻击图相比正向算法生成的攻击图在节点数量上要少,不存在与达到攻击目标无关的节点.算法具有较好的时间复杂度O(|H|2)～O(|H|3),相比同类算法具有较高的效率,可以应用于大规模网络.
展开▼
