层次化分类淘汰法的网络最优弥补模型

李远敏（厦门理工学院计算机与信息工程学院，福建厦门361024）

层次化分类淘汰法的网络最优弥补模型

李远敏
（厦门理工学院计算机与信息工程学院，福建厦门361024）

针对求解最优弥补的特点和需求，利用层次化分类淘汰，提出一种基于层次化分类淘汰法的最优弥补模型（HSE－ONHM），得到最优弥补的精确解.为了验证HSE－ONHM的可行性和有效性，分别采取穷举法和层次化淘汰算法求解同一目标网络环境的最优弥补.实验结果表明：无论是淘汰次数还是CPU消耗时间，层次化分类淘汰法比穷举法优越；层次化分类淘汰法的计算时间随着初始属性节点数量呈指数增加，该实验结果与算法性能分析结果一致.

最优弥补模型；层次化淘汰算法；穷举法；网络安全

网络脆弱性评估的目的之一是为网络管理者及用户提供最优弥补，提高目标网络系统的安全性［1－6］.由于采取不同的安全弥补措施需要花费不同的成本代价，最优弥补即在有限资源的前提下，以最小的成本代价保证目标网络系统正常、安全运行.Phillips等［7］首次提出了最优弥补建议的分析方法，但该方法由于分析过于简单，其准确性有待进一步考察.Sheyner等［8－9］提出了一种攻击图自动生成方法，并基于攻击图对最优弥补建议进行了理论分析.Homer等［10］认为安全弥补措施提高目标网络系统的安全性的同时，会受到多种条件的约束，基于此，利用逻辑攻击图提出了一种自动化网络配置管理方法.该方法通过多次迭代分析，最终会给出权衡了各种约束的网络配置方案.本文提出了一种基于层次化分类淘汰法的网络最优弥补模型（HSE－ONHM），能得到最优弥补的精确解.

1 网络最优弥补模型

求解最优弥补时，若只弥补一个初始属性节点能保证目标网络系统正常、安全运行，且需耗费的成本代价为a，则其他所有的除弥补该初始属性节点外，仍弥补其他初始属性节点的弥补策略，需耗费的成本代价必须大于a.根据代价最小原则，应将这些策略淘汰.

基于此，为了得到目标网络系统最优弥补的精确解，对精确搜索方法进行了改进，提出一种基于层次化分类淘汰法的最优弥补模型（HSE－ONHM）.该模型首先根据攻击图中的初始属性节点进行分类；然后，对弥补策略进行层次化淘汰，依据代价最小原则，淘汰成本代价相对比较大的弥补策略，直至分类中的所有弥补策略都被淘汰，与此同时，得到最优弥补.

在具体的实现过程中，该方法主要分为两个步骤.

步骤1 将弥补策略进行分类.

步骤2 将淘汰成本代价大的弥补策略.

若弥补初始属性节点c1能保证目标网络系统正常、安全运行，即g（｛10…0｝）＝0，根据代价最小原则，则除弥补c1外，仍弥补其他初始属性节点的弥补策略都应被淘汰.设1－弥补｛cN＝1｝，使g（x）＝0，其中，N为初始属性节点的编号.具体的淘汰规则为

淘汰2－弥补中的弥补策略：2i＋2j，0≤i≤n－1，i≠N，j＝N；

淘汰3－弥补中的弥补策略：2i＋2j＋2k，0≤i≤j≤n－1，i，j≠N，k＝N；

淘汰n－弥补中的弥补策略：2i＋2j＋…＋2m，0≤i＜j＜…＜s≤n－1，i，j，…，s≠N，m＝N.

具体有以下4个淘汰步骤.

步骤1 依次判断1－弥补｛ci＝1｝中的弥补策略.

步骤2 若g（x）≠0，将该策略从1－弥补中淘汰.

步骤3 若g（x）＝0，令N＝i，并将弥补代价与cost比较.若弥补代价≥cos t，按照淘汰规则逐层淘汰弥补策略；若弥补代价cos t，则cos t＝弥补代价，然后，按照淘汰规则逐层淘汰弥补策略.

步骤4 依次类推，直至所有的弥补策略都被淘汰.即1－弥补，2－弥补，…，n－弥补都为空，与此同时，得到最优弥补.

2 算法复杂度分析

目标网络系统中主机数量为H，初始属性节点数量为C.在具体的实现过程中，首先，分析1－弥补中的弥补策略；然后，分析2－弥补中的弥补策略；依次类推，1－弥补算法的复杂度比其他弥补算法的复杂度要高.因此，该算法的时间复杂度即1－弥补算法的时间复杂度.

在1－弥补算法中，主要有两个子函数：弥补策略淘汰子函数和弥补策略判断子函数.其中，前者的目标是依据淘汰规则逐层淘汰xn的弥补策略，后者的目标是判断该弥补策略是否已被淘汰.

弥补策略判断子函数的时间复杂度为O（C），在弥补策略淘汰子函数中，首先，将十进制弥补策略转换为二进制形式，时间复杂度为O（C）；然后，遍历［xa，xb）中的所有弥补策略，依次判断该策略是否被淘汰，时间复杂度为O（｜xb－xa｜）·O（C）.［xa，xb）为弥补策略中包含未被淘汰弥补策略的最小敬意，｜xb－xa｜≤2C.因此，弥补策略淘汰子函数的时间复杂度为

在1－弥补算法中，依次判断1－弥补中的弥补策略，时间复杂度为O（C）.若该弥补策略的g（x）＝0，调用弥补策略淘汰子函数，按照淘汰规则逐层淘汰弥补策略，时间复杂度为O（2C）·O（C）；然后，计算该弥补策略的弥补代价，时间复杂度为O（C）；将弥补代价与cos t比较，若弥补代价小于cos t，则cos t等于弥补代价，按照淘汰规则逐层淘汰弥补策略，时间复杂度为O（2C）·O（C）.因此，1－弥补算法的时间复杂度为

3 实验结果与分析

为了验证HSE－ONHM的可行性和有效性，分别采取穷举法（算法1）和层次化淘汰算法［12］（算法2）求解同一目标网络环境的最优弥补.实验环境如下：服务器为PowerEDGE R710；操作系统为RetHAT V5.4；内存为32GB；CPU为2.26GHz.无论是淘汰次数还是CPU消耗时间，层次化淘汰算法比穷举法要优越很多；层次化淘汰算法的计算时间会随着初始属性节点数量呈指数增加，该实验结果与算法性能分析结果一致.

步骤1 求约束条件g（x）.假设攻击者的攻击目标是属性节点c15，g（x）为

由于g（x）＝0，因此，属性节点c15不能被满足，即e11，c11，e10，c12构成的循环路径在实际的应用中是不存在的，而且该循环路径涉及的节点c15，e13，c13，e11，c11，e10，c12应被删除.

简单的攻击图，如图1所示.简化的攻击图，如图2所示.

图1 简单攻击图示例Fig.1 Simple attack graph example

图2 简化攻击图Fig.2 Simplified attack graph

步骤2 利用HSE－ONHM求最优弥补.在步骤1获得g（x）的基础上，求攻击目标c9的最优弥补，令弥补初始属性节点的成本代价为｛cos t（c1），cos t（c5），cos t（c14），cos t（c16），cos t（c17）｝＝｛2，4，3，5，6｝.求解过程，如表1所示.表1中：淘汰策略列中｛c17＝1｝表示逐层淘汰｛c17＝1｝的弥补策略.

在HSE－ONHM中，虽然对初始属性节点采取了二进制编码，将弥补策略转化成了二进制序列，但在具体的实现过程中，为了提高算法的性能和效率，将二进制序列转化成了十进制数.由表1可知：最优弥补为｛c1，c5，c14，c16，c17｝＝｛1，0，0，0，0｝，即只弥补初始属性c1，并且弥补成本代价为2.

表1 HSE－ONHM的求解过程Tab.1 Solving process of the HSE－ONHM

4 结束语

网络脆弱性评估方法的最终目标之一，针对实际的目标网络系统，得到该网络的最优弥补，从而指导网络安全管理者有针对性地进行保护.运用基于层次化分类淘汰法的最有弥补模型求解最优弥补，对弥补策略进行层次化淘汰，依据代价最小原则，淘汰成本代价相对比较大的弥补策略，直至分类中的所有弥补策略都被淘汰，从而得到最优弥补.

［1］ YEH W C.A Revised layered－network algorithm to search for all d－minpaths of a limited－flow acyclic network［J］.IEEE Transations on Reliability，1998，47（4）：436－442.

［2］ IN Yongkun.A Simple algorithm for reliability evaluation of a stochastic－flow network with node failure［J］.Computers and Operations Research，2001，28（13）：1277－1285.

［3］ 骆剑锋，陈俞强.采用环加星型网络结构负载均衡集群技术的云平台设计［J］.华侨大学学报（自然科学版），2016，37（2）：164－167.

［4］ CHEN Run，MO Yong，PAN Zhan.Performance improvement of edge expansion technique for BDD－based network reliability analysis［J］.Journal of Computers 2013，8（9）：2190－2196.

［5］ JHA S，SHEYNER O，WING J M.Two formal analyses of attack graphs［C］∥Proceedings of 15th IEEE Computer Security Foundations Workshop.Ottawa：IEEE Press，2002：234－238.

［6］ NOEL S，JAJODIA S，O＇BERRY B，et al.Efficient minimum－cost network hardening via exploit dependency graphs ［C］∥Proceedings of 19th Annual Computer Security Applications Conference.Hangzhou：IEEE Press，2003：86－95.

［7］ PHILLIPS C，SWILER L.A graph－based system for network vulnerability analysis［C］∥Proc of the New Security Paradigms Workshop.Charlottesville：User Evaluation，1998：71－79.

［8］ SHEYNER O，HAINES J，JHA S，et al.Automated generation and analysis of attack graphs［C］∥Proc of the IEEE Symposm on Security and Privacy.Oakland：IEEE Computer Society Press，2002：254－265.

［9］ SHEYNER O.Scenario graphs and attack graphs［D］.Pittsburgh：Carnegie Mellon University，2004：256－257.

［10］ HOMER J.A comprenhensive approach to enterprise network security management［D］.Manhattan：Kansas State University，2008：148－150.

［11］ WANG Lingyu，NOEL S，JAJODIA S.Minimum－cost network hardening using attack graphs［J］.Computer Communications，2006，29（18）：3812－3824.

［12］ CHEN Feng，WANG Lingyu，SU Junshang.An efficient approach to minimum－cost network hardening using attack graphs［C］∥Proc of the Fourth International Conference on Information Assurance and Security.Tokyo：User E－valuation，2008：209－212.

（责任编辑：陈志贤 英文审校：吴逢铁）

Optimal Network Hardening Model Based on Hierarchical Classification Elimination

LI Yuanmin
（College of Computer and Information Engineering，Xiamen University of Technology，Xiamen 361024，China）

This paper considers the characteristics and requirement of solving the optimal hardening problem.A new optimal network hardening model based on hierarchical separatal elimination（HSE－ONHM）is proposed and accurate solution for optimal hardening is got.In order to verify the feasibility and effectiveness of the model，the optimal exhaustive method and hierarchical algorithm is taken for elimination of the same target for network environment.Experimental results show that either eliminated or the number of CPU time consuming，HSE－ONHM is superior.The computation time of HSE－ONHM with initial attribute node increases exponentially with the number.The experimental results are consistent with the performance analysis of the algorithm.

optimal hardening model；hierarchical classification elimination algorithm；enumeration method；network security

TP 393

A

1000－5013（2016）04－0515－04

10.11830／ISSN.1000－5013.201604025

2016－01－20

李远敏（1970－），男，副教授，主要从事信息融合、嵌入式系统的研究.E－mail：cxllymin＠163.com.

福建省教育厅A类项目（JA09217）；厦门理工学院高层次人才科技项目（YKJ08013R）