渗透测试是目前进行网络安全评估的重要手段,每一次的渗透测试都需要一种分析方法作为指导,目前用于渗透测试的分析方法分别有基于攻击树、攻击图和Petri网的,基于攻击图的渗透测试方法是研究的重点。现有对攻击图的研究主要集中于解决如何去探测从攻击主机到目的主机的攻击路径,如何解决攻击图所固有的状态爆炸问题。但是立足点都是要找出所有从攻击主机到目标主机的路径,没有对路径的量化评估,这样生成的攻击图虽然会比较全面,但是很难快速地发现网络中相对最为脆弱的环节,缺少针对性,不能为后续的渗透测试的实施提供更有价值的指导。同时,由于路径的探测比较盲目,所以在攻击图生成的效率上也会比较低。为了解决现有问题,本文提出了低代价攻击图的概念,利用CVSS评分系统以及对攻击步长的限制,找出利用难易程度较低的攻击路径关联成图。本文就低代价攻击图的生成给出了两种方法,分别为基于限定阈值的攻击图生成方法和基于启发式搜索策略的攻击图生成方法。第一种方式以用户设置的阈值为依据,利用深度优先遍历寻找攻击路径,边扩展节点边判断阈值,最后生成在阈值范围内的所有攻击路径组成低代价攻击图。第二种方式利用启发式搜索的思想,在估价函数的引导下,进行节点的边探测边扩展,最后直接生成最低代价的攻击图。第一种方法可以找到脆弱程度在一定范围内的攻击路径,第二种方法可以直接找到网络中最为薄弱的环节。这两种方式生成的攻击图,都具有明确的针对性,在生成效率上都有了很大提升,同时也进一步缩小了攻击图的规模,为渗透测试的实施提供了更加明确的指导依据。