基于并行遗传算法的网络最优弥补模型

吴蓓

摘 要： 将攻击图与并行遗传算法相结合，提出了一种基于并行遗传算法的网络最优弥补模型（PGA?ONHM），该模型能得到目标网络系统的近似解。为了验证该模型的可行性、有效性和可扩展性，从不同的分析角度进行仿真验证，实验结果表明：并行遗传算法的CPU消耗时间随着初始属性节点数量的增加呈多项式增加，随着子群体数量的增加呈减小趋势；无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越；并行遗传算法可以得到较好的加速比，能够克服局部最优解的问题，可以适用于大规模复杂的网络系统。

关键词： 网络脆弱性； 攻击图； 网络脆弱性弥补； PGA?ONHM

中图分类号： TN915.08?34 文献标识码： A 文章编号： 1004?373X（2016）05?0105?05

0 引 言

人类在享受互联互通和信息共享带来的便捷与效益的同时，网络技术发展过程中对安全性的忽视，导致网络环境中存在各式各样的安全隐患，严重威胁着网络运营及合法用户的信息安全。因此，寻找并弥补威胁网络关键资源的脆弱性是提高网络安全性的一种有效方法。文献[1]基于逻辑推理的方法，首先将最优弥补求解问题转化为布尔表达式；然后求解该布尔表达式的析取范式，从而得到所有的弥补措施；最后通过分析比较得到最优弥补建议。该方法在最坏情况下具有不可避免的指数时间复杂度，无法应用于网络规模较大的真实目标网络系统。文献[2]提出采用归纳有序二元决策图（ROBDD）的方法求解最优弥补。该方法可以有效地获取攻击图的最优弥补，但在该方法中，未对脆弱性进行度量标准的说明，因此在实际应用上具有一定的局限性。

由于求解最优弥补问题是NP完全性问题，对于NP完全性问题，采用启发式搜索方法可以更快地获得结果。并行遗传算法[3?6]具有以下优势：覆盖面大，利于全局择优；对问题的依赖性较小，求解的鲁棒性较好；具有并行计算的特点，可以用大规模的并行计算来提高计算速度；特别适用于复杂大系统问题的优化求解，但其存在收敛速度慢、局部搜索能力差等不足之处。并行遗传算法可以克服经典遗传算法的不足，提高遗传算法求解的速度和质量。基于此，本文将攻击图与并行遗传算法相结合，提出了一种基于并行遗传算法的网络最优弥补模型（Optimal Network Hardening Model Based on Parallel Genetic Algorithm，PGA?ONHM）。

3 实验结果与分析

为了验证PGA?ONHM模型的可行性、有效性和可扩展性，本文从不同分析角度做了两组实验，并对实验结果进行了分析。实验环境如下：服务器PowerEDGE R710，操作系统RetHAT V5.4，内存32 GB，CPU 2.26 GHz。

3.1 算法性能验证实验

由算法性能分析可知，该算法性能与目标网络系统中初始属性节点数量[C，]迭代次数[D，]子群体[U]等参数有关。为了验证不同网络环境下这些参数对算法性能的影响，在得到最优解的前提下，分别设计了如下两组实验。

第一组实验验证初始属性节点数量不同时，单次迭代的平均计算时间如图3所示。由图3可知，单次迭代的平均计算时间随着初始属性节点数量[C]的增加呈多项式增加趋势。

第二组实验验证子群体数量（即处理器数量）对算法性能的影响。令初始属性节点数量为500，当子群体数量不同时，单次迭代的平均时间如图4所示。由图4可知，单次迭代的平均计算时间随着[U]的增加呈减小趋势。

由上述两组实验结果可知，在PGA?ONHM模型中，算法CPU消耗的时间随着初始属性节点数量[C]的增加呈多项式增加趋势，随着子群体数量[U]的增加呈减小趋势，实验结果与算法性能分析结果一致。

3.2 算法对比实验

（1） 经典遗传算法和并行遗传算法对比实验，实验结果如表1所示。表1列出了在初始属性节点数量不同的情况下，求解最优弥补时两种算法的平均迭代次数和单次迭代的平均计算时间。

从实验结果可以看出：一方面，针对同一目标网络环境，无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越，其主要原因是在并行遗传算法的具体实现过程中，首先将总群体分成若干子群体，然后将子群体分配到各自的处理机上，独立地进行遗传算法的进化操作，实现了从全局角度开发群体进化的并行性，从而提高了计算效率；另一方面，并行遗传算法具有良好的可扩展性，当初始属性节点数量达到2 000时，单次迭代的平均计算时间也不过7 ms。

（2） 加速比实验。目前公认的评价并行遗传算法性能的指标是加速比，即并行遗传算法与经典遗传算法完成等量工作所耗时间的比例，它标志着一个并行遗传算法的好坏。本文在相同的硬件环境下，对同一目标网络环境通过改变处理器数量，进行了加速比实验，实验结果如表2所示。加速比和处理器数量的关系如图5所示。由图5可知，加速比与处理器几乎呈线性关系，因此，本文所提并行遗传算法可以得到较好的加速比，是行之有效的并行手段。

4 结 论

PGA?ONHM模型通过建立数学模型将攻击图与并行遗传算法相结合，得到最优弥补的近似解。为了验证该模型的可行性、有效性和可扩展性，本文从不同的分析角度做了两组实验，实验结果表明：CPU消耗时间随着初始属性节点数量的增加呈多项式增加，随着子群体数量的增加呈减小趋势；无论是平均迭代次数还是单次迭代的平均计算时间，并行遗传算法比经典遗传算法都要优越；加速比与处理器呈线性关系；能够克服局部最优解的问题，可以适用于大规模复杂的网络系统。

参考文献

[1] JHA S， SHEYNER O， WING J M. Two formal analyses of attack graphs [C]// Proceedings of 15th IEEE Conference on Computer Security Foundations Workshop. [S.l.]： IEEE， 2002： 49?63.

[2] NOEL S， JAJODIA S， O′BERRY B， et al. Efficient minimum?cost network hardening via exploit dependency graphs [C]// Proceedings of 19th Annual Conference on Computer Security Applications. [S.l.]： IEEE， 2003： 86?95.

[3] WANG L Y， NOEL S， JAJODIA S. Minimum?cost network hardening using attack graphs [J]. Computer communications， 2006， 29（18）： 3812?3824.

[4] HOMER J. From attack graphs to automated configuration management： an iterative approach [R]. Kansas： Kansas State University Technical Report， 2008.

[5] SI J Q， ZHANG B， MAN D P， et al. Approach to making strategies for network security enhancement based on attack graphs [J]. Journal on communications， 2009， 30（2）： 123?128.

[6] CHEN F， WANG L Y， SU J S. An efficient approach to minimum?cost network hardening using attack graphs [C]// Procee?dings of 2008 the 4th International Conference on Information Assurance and Security. Naples： IEEE， 2008： 209?212.

[7] CHEN F， ZHANG Y， SU J S， et al. Two formal analyses of attack graphs [J]. Journal of software， 2010， 21（4）： 838?848.

[8] CHEN F. A hierarchical network security risk evaluation approach based on multi?goal attack graph [D]. Changsha： National University of Defense Technology， 2008.

[9] ALBANESE M， JAJODIA S， NOEL S. Time?efficient and cost?effective network hardening using attack graphs [C]// Proceedings of the 42nd IEEE/IFIP Annual International Conference on Dependable Systems and Networks. Boston： IEEE， 2012： 1?12.