陈黎丽，王震，郭云川，华佳烽，姚宇超，李凤华,4

（1. 西安电子科技大学综合业务网络国家重点实验室，陕西 西安 710071；2. 中国科学院信息工程研究所第五研究室，北京 100093；3. 杭州电子科技大学网络空间安全学院，浙江 杭州 310018；4. 中国科学院大学网络空间安全学院，北京 100049）

1 引言

近年来，“网络黑产”事件频繁发生，攻击者以“趋利”的思想策略地发动针对性的攻击。例如，2018年12月，攻击者通过加密电脑上的doc、jpg等常用文件的勒索病毒，利用微信支付二维码勒索赎金，但支付宝用户并未受到影响。目前，大部分的Internet服务提供商与大型企业网络部署了网络监测系统[1-3]，系统管理员通过网络监测器（如流量分析程序、网络入侵防御系统和防火墙等）对网络性能数据进行实时收集，从而监测网络的性能和安全状况。虽然现有的网络监测系统可以收集到一些安全数据（如网络流量、CPU占用率等），但是针对上述“策略式攻击”相关的安全数据缺少精准有效的监测策略。同时，由于受到资源成本的限制，只能部署有限数量的采集代理进行安全数据的监测采集。因此，在敌对环境中，如何优化部署采集代理获取更好的监测效果成为一个极为重要的课题。

在敌对环境中，优化部署采集代理问题面临着以下几个挑战。首先，采集代理针对不同类型设备采集的内容存在差异，例如，载有防火墙的设备可采集到UFW、Snort等相关日志信息，载有数据库服务器的设备可采集到MySQL相关日志信息。上述日志信息存在数据异构性，为数据解析威胁事件带来困难。因此，需要对异构性的安全数据进行统一度量。其次，上述的安全数据与威胁之间存在关联关系，不同的异构数据组合能监测到不同的威胁。因此，为了更精准地监测“策略式攻击”，需要考虑如何部署有限数量的采集代理，使采集到的异构数据组合获得尽可能好的监测效果。最后，采集代理一旦部署，无法在短时间内移除，攻击者通过漏洞扫描、网络渗透、社会工程学等手段获取网络系统的信息（如漏洞信息、防火墙的位置等），并且策略地选择对其“最有利”（“最有利”指的是使网络攻击影响最大）的方式实施攻击。因此，需要考虑如何优化部署采集代理，在应对敌对情况时监测效果具有顽健性。

针对监测点部署问题，现已有不少学者开展了相关研究。在网络测量领域中，网络测量部署模型主要以优化为主体思想，并在此基础上提出了一系列的启发式近似算法[4-7]，为本文的研究奠定了基础。网络测量系统主要测量链路流量或端到端带宽、时延、分组丢失率等性能参数[8]。然而，本文研究的采集代理部署在不同类型的设备上，安全数据类型不同，包括网络流量数据、网络日志数据和设备状态数据，这些数据具有很强的异构性。在环境监测领域中，现有工作主要解决如何放置有限数量的传感器来检测污染物的问题[9-11]。其中，文献[10]对敌对情况下如何部署采集器进行了研究，将对抗设置为对手在知道传感器位置的情况下选择在哪里进行污染，该设置与本文敌对情景设置相近。然而，环境监测中的采集项主要包括污染物类型、污染物质量和污染时间等相关参数[11]。而本文主要从网络威胁层面考虑，例如，威胁事件发生的概率、威胁事件对目标系统的影响等。最后，在网络安全监测领域中，已有不少采集代理的部署方法。例如，基于访问控制策略的部署方法[2]和基于线性规划的部署方法[12-14]。其中，文献[14]对异构性强的日志信息进行度量，利用日志与威胁之间的关联关系构建优化目标，并对该方法的伸缩性进行讨论，该度量方法为统一量化异构数据提供了启发。然而，本文研究的是在敌对情况中进行采集代理的部署，不仅要考虑日志数据、流量数据和设备状态数据这 3类异构数据，而且还要考虑敌对环境中部署方法的顽健性，以上3个方面的相关研究无法直接解决本文的问题，因此，本文提出了一种适用于敌对情况下的采集代理优化部署算法——采集代理顽健部署（RCD, robust collection deployment）算法。本文的主要贡献如下。

1) 将敌对环境下采集代理优化部署问题归结为一个攻防博弈问题，并且考虑到采集代理获取的安全数据的异构性，构建度量攻防博弈（MADG，metric attack and defense game）模型。

2) 在MADG模型的基础上，利用系统、威胁和采集代理以及三者之间的关联关系构建威胁-采集树，利用威胁事件发生的可能性和威胁事件对系统的影响构建攻击效用函数。

3) 利用上述目标函数的次模性，提出了一种基于贪婪的采集代理顽健部署算法——RCD算法，该算法能找到一组性能至少与最优集合一样的部署位置集合，但时间成本会稍微增加。

4) 通过构建具体网络案例模型和扩展模型，从求解时间和求解质量方面进行了一系列的实验，并与精确求解算法和启发式算法进行了对比，表明RCD算法的顽健性和可扩展性。

2 相关工作

首先，从3个角度对网络监测点部署的相关研究进行了梳理。其次，为了直观地描述敌对环境，借鉴了威胁建模中威胁树的思想，并对威胁建模的相关工作进行了梳理。

2.1 监测点部署

近年来，很多学者从不同角度对网络监测点部署问题开展了研究。首先，在网络测量领域中，主要研究工作集中在网络测量部署模型及其优化算法上。Aqil[3]把网络测量部署问题映射为经典优化问题，利用经典优化问题的难解性和近似算法进行求解。Breitbart等[4]使用同样的映射，采用整数规划来解决优化问题。Hochbaum[5]则设计了一个启发式算法求解近似解。此外，Chaudet等[7]对网络测量部署模型和优化算法进行了归纳总结。Suh等[6]针对主动监测时部署信标分配问题和被动监测时部署tap设备的分配问题进行研究，提出了一个问题组合和高效通用混合整数规划（MIP, mixed integer programming）公式。上述工作侧重于优化问题的描述和求解，没有考虑采集项中是否存在异构性，且在敌对环境方面没有给出相关讨论。

其次，在环境监测领域中，针对放置有限数量的传感器来检测污染物的问题，Leskovec等[9]最早将部署采集器监测水污染的问题归结为“爆发检测”问题，并提出了基于贪婪的优化部署算法——CELF（cost-effective lazy forward selection）算法。Comboul等[11]考虑了水分配网中不确定参数对部署方案的影响，从确定系统、不确定系统和灵敏传感器3个方面对优化部署问题进行优化，利用目标函数次模性提出贪婪算法求解最优化问题。此外，Kraused等[10]针对敌对环境下水分配网络中采集器优化部署的问题进行了研究，其中对抗设置为对手在知道传感器位置的情况下选择污染位置，并对此提出了一种具有顽健性的优化部署算法——Saturation算法。以上研究虽然与本文的研究领域不同，但是解决的问题与本文的问题都是有限个数节点的优化部署问题。

在网络安全监测领域中，为了尽早发现复杂网络中病毒的传播，Yu等[12]提出了一种最小化最坏的感染规模的启发式算法——MMI（minimizing the maximum infection）算法，该算法具有较快的收敛速度。Zhou等[13]研究了如何有效地部署传感器位置，以便在网络中早期发现动态有害级联问题，并将级联的动态属性因素考虑在内，在 CELF算法[9]的基础上，提出了UBG（upper bound based greedy）算法，求出收益函数的上界，以便删除不必要的检测时间估计，同时为了提升计算速度，提出了 2个加速算法。Thakore等[14]先对异构的日志信息进行了度量，并通过日志信息与威胁事件的关系建立了映射关系，然后又在度量的基础上提出了一个启发式优化部署算法——GOMD（greedy algorithm to compute the optimal monitor deployment）算法。此外，Talele等[2]针对采集已知攻击问题的局限性，提出了一种计算网络监控位置的方法，该方法利用主机间可用访问控制策略的通用性来计算大规模系统的采集代理的部署位置。上述这些工作均忽略了攻击者对采集代理部署策略的影响，因此现存的优化部署方案顽健性不足，无法很好地应对敌对环境。

2.2 威胁建模

威胁建模是针对攻击者如何执行潜在攻击或对系统构成安全威胁进行简化、抽象描述的过程。对威胁进行建模可以更直观地描述威胁和评估威胁影响。在威胁建模的工具中，威胁树是较常用的一种。Marback等[15]提出了一种基于威胁模型的安全测试方法，该方法可以从威胁树中自动生成安全测试序列，并将其转换为可执行测试。Pardue等[16]提出了一种基于威胁树和蒙特卡罗模拟的风险模型和风险评估技术，其目标是对直觉或风险估计进行合理而简洁的量化。Morikawa等[17]提出了威胁树模板来帮助非专家分析人员构建威胁树，每个模板都是一个冗余的威胁树，装载了代表许多可能攻击场景的分支，以及针对此类攻击的相应漏洞和对策的典型示例。目前，上述工作均从攻击的角度来描述威胁和威胁实现的条件，忽略了威胁和安全数据之间的内在联系。

3 模型

在描述模型之前，为了不出现异议，将采集器、采集代理、网络监测器统一用“采集代理”表示，涉及采集到的“安全数据”用“采集项”表示。在对敌对环境中优化部署采集代理问题进行建模之前，对该问题进行以下2个基本假设。

假设 1采集代理方面。每个采集代理的采集能力是相同的，部署在不同类型的设备上，不同类型的设备输出不同类型的数据，因此能够采集到的采集项具有差异。

假设 2威胁方面。攻击者是贪婪的，攻击者通过扫描、渗透、社会工程学等手段获取部署位置，从而选择对自己“最有利”的方式进行攻击，且不会进行无效攻击。

3.1 问题描述

本文所要优化的问题是如何优化部署采集代理获取更好的监测效果，并且可以保证部署的成本尽可能最少。本文将其建模为一个基于度量的零和博弈模型——MADG模型：管理员作为防守方（defender），其对应的防守策略是在通信网络上选取k个设备进行采集代理的部署；攻击者作为攻击方（attacker），其攻击策略是选取所有攻击方式中的一种。由于是零和博弈，因此有

攻击方根据获取的网络相关信息选择攻击效用值最大的一种攻击方式，而防守方选择使攻击方的攻击策略收益最小化的策略集合，即攻击方的目的是最大化攻击效用，防守方的目的是最小化攻击方的攻击效用。因此，该问题的目标函数可表示为

3.2 部署目标相关度量定义

为了对式(1)中的目标函数进行精确的分析，本节借鉴文献[14]中给出的度量框架的一部分，对本文目标函数中相关元素进行了定义和度量。本文的符号及其含义如表1所示。

表1 符号含义

定义 1威胁事件。已经造成攻击影响的事件和可能会对网络造成攻击影响的事件，即系统中存在的攻击或入侵行为，或者系统中可能出现的攻击或入侵行为。

本文使用Ψ表示能够在系统中检测到的和可能发生的所有威胁事件的集合。

威胁事件并非是采集代理直接采集的采集项条目，而是通过对一个或多个采集信息相关性的分析确定能够检测出的威胁。

定义 2内嵌式采集代理。实现网络监测的采集组件和采集器的统称。采集组件是安装在操作系统（如Windows系统、Linux系统等）中的软件，采集器是部署在终端（如手机终端、卫星终端等）上的传感器，两者都可以对部署的设备上的各种类型的数据进行收集，本文用S= {s1,s2, …,sm}表示内嵌式采集代理si(1≤i≤m)的集合。

采集项可以分为3类，即日志数据、网络流量数据和设备状态数据。其中，日志数据可以分为以下4类：1) 主机上安装的Windows系统、Linux系统等操作系统日志数据，2) 网络中部署的路由器、交换机等传输设备日志数据，3) 主机上记录的SSH、MySQL、HTTP、Web等具体服务运行日志数据，4) 安全防护系统防火墙、IDS等安全设备日志数据。

定义3特征信标。通过采集代理生成的信息可以推断出系统中发生的威胁事件，在此用ς表示[14]。

特征信标并非采集代理采集到的实际数据，而是使用一些逻辑谓词对单个或多个采集代理获取的采集项进行连接和加工而生成的信息，是用来定义检测威胁的必要条件。特征信标的生成主要有 2个步骤：1) 对于每一个威胁事件，将每个采集代理采集的采集项进行分组，根据它们提供的证据类型支持检测威胁事件；2) 根据采集项和威胁事件的内在联系，确定需要采集哪些信标、可以监测到哪些威胁事件。

文献[18-19]对逻辑规范的后续研究工作提供了一定的研究依据，但该问题不是本文的重点，在此不再赘述。此外，在现有的开源情报（如OSINT）和入侵检测技术为关联关系映射提供了技术支持的同时，文献[20-23]针对不同类型网络中的威胁事件所对应的采集项进行了研究和调研，为该问题提供了一定的理论依据。

采用上述2个步骤，可以对采集到的异构数据格式进行统一，避免了来自不同类型设备上的日志、流量、设备状态信息格式的差异，同时该方法可以在一定程度上简化安全领域专家对特征信标的枚举。尽管无法指定采集代理数据的确定格式，但是专家能够理解每条特征信标提供的语义信息。

定义 4采集代理和特征信标对应关系。由一个映射函数表示ϕ:s→Φ(C)，即其中，Φ(C)为C的幂集。现对该映射进行说明：映射是从采集代理到采集项一对多的关系，并表示由给定采集代理生成的一组采集项。考虑多维网络的异构性、设备差异性较大等因素，针对任何一个威胁事件，可能有多种检测方法，本文统一采用最小特征信标集合来监测分析威胁事件。

定义 5最小特征信标集合。一组特征信标集合τ能够检测分析到一个威胁事件ψ，即所有最小特征信标集合中的元素足以监测到威胁事件ψ[14]。

定义 6检测威胁事件的证据。一个给定映射γ:Ψ→Φ(Φ(C))，其中，γ(ψ)=(τ|τ用于检测威胁事件ψ)[14]，γ是一个从威胁事件到特征信标的一对多的映射。在众多映射中，只要有一组特征信标监测到威胁事件即可。

定义 7真实性。采集代理的真实性是指采集代理所产生的特征信标是正确的[14]。

采集代理的真实性不是二元的，因此本文应用模糊逻辑来评估采集代理的真实性，即采集代理可能不会从真实的信标转变为错误的信标，而可能会继续为少数威胁事件以外的其他威胁事件提供正确的信标。正如 Hosmer[24]所提出的，模糊逻辑比概率论更适合这种情况。因此，本文定义了一个函数σS，将采集代理映射到生成信标的真实性作为一个模糊逻辑度，表示由采集代理生成的信标中有多少是真实的，即

其中，R为实数集合。

本文将采集代理的真实性映射到其产生的所有指标的真实性上。如果没有采集代理生成信标，默认情况下该采集代理的真实性为0，即

为了监测一个威胁事件，至少需要采集来自该威胁事件对应最小信标集合中的一个特征信标。因此，对于一个最小的特征信标集合τ，本文结合所有最小特征信标集合τ的真实值来定义该最小特征信标集合τ的置信度。最后，给出监测到的威胁事件Ψ的置信度的定义为：该威胁事件Ψ对应的所有最小特征信标集合的置信度的MTL分离值即为Ψ的置信度。

定义8置信度。置信度定义为[14]

本文考虑了攻击者在观察到采集代理的部署位置时，会选择破坏效果最大的威胁事件进行攻击，换言之，采集代理部署位置的集合，决定了攻击者的攻击策略。

为了直观地对敌对环境进行描述，本文借鉴威胁建模的思想通过威胁树对威胁事件、威胁特征信标和采集代理之间的内在联系，构建威胁-采集树模型，如图1所示，并给出了相关定义。

图1 威胁-采集树模型

定义9威胁-采集树。威胁-采集树是描述威胁事件和采集代理之间通过采集项中信标确定映射关系的一个层次结构，包括目标系统、攻击类型、威胁事件、信标和采集代理5个层次。其中，第一层是目标系统，即管理员需要保护的系统；第二层是目标系统可能受到攻击的攻击类型；第三层是每种攻击类型可以通过一些威胁事件来实现；第四层是每个威胁事件所对应的威胁特征信标；第五层是能够采集到威胁信标的采集代理。由此，本文将攻击方的效用Utilityattacker使用攻击方选取的威胁事件的风险函数Risk来表示。

定义10风险。风险是威胁事件发生的可能性与威胁事件的影响的乘积，即风险效用函数，具体可形式化定义为

其中，Pψ为攻击方在防守方部署了采集代理时，威胁事件ψ可能发生的概率，Iψ为威胁事件ψ对系统的影响，即

其中，Ec表示影响系统机密性，wc表示影响系统机密性的权重，Ei表示影响系统完整性，wi表示影响系统完整性的权重，Ea表示影响系统可性，wa表示影响系统可用性的权重。“影响”表示一种威胁事件对系统的影响，本文从机密性、完整性和可用性3个方面对其进行衡量。

Pψ为攻击方在防守方部署了采集代理时，某一个威胁事件可能发生的概率。该概率是该威胁事件发生但未被最小特征信标集合监测到的概率与该威胁事件发生且被最小特征信标集合监测到的概率之和，即

根据数学归纳，可以将式(4)简化为

通过上述定义和度量，现将目标函数表示为

3.3 部署目标属性

根据3.2节中给出的效用函数可以发现，该效用函数具有次模性，即在采集代理部署节点足够的情况下，再添加一个采集代理的部署点能获得的收益并不比部署该点前的收益大。后文中使用函数R来代替Riskψ，目标函数R具有以下特性。

1) 次模性：若对所有Sd1⊆Sd2⊆V且s∈VSd，则有

2) 单调性：若对所有的Sd1⊆Sd2⊆V，则有

3) 规定：R(V)=0。

因此，攻击者收益问题可以形式化为其中，R具有标准单调次模性，k是部署点个数的限制。式(7)是一个NP-hard问题[25]，该问题经常使用启发式算法求近似解。Nemhauser等[26]提出一个基本结论：对于具有次模性的函数，贪婪算法实现了一个常数因子近似值，通过贪婪算法集合Sd至少获得一个常数分数该常数分数是基于通过最优解获取的观察点值。例如除非 P=NP[22]，否则没有多项式时间算法可以提供更好的近似保证。

因此，针对本文的问题选择使用贪婪算法，其算法思想为：从一个空集开始，迭代地添加一个元素)，直到添加元素的个数满足k的要求，则贪婪算法选择完毕。

针对敌对环境，优化采集代理部署问题解决以下问题，即

防守方的目标是选择一组设备点部署采集代理，能够应对攻击方时监测效果表现最好。因此要考虑攻击方对部署策略的影响。本文的敌对环境设置为攻击方知道防守方采集代理部署的位置Sd，选择对防守方结果最坏的Ri。应注意的是，尽管所有的Ri都具有次模性，但是G(Sd)=maxi Ri(Sd)不具备次模性。在这个设置中，简单贪婪算法可以执行。

本文的目标是找到在应对策略式攻击时表现良好的采集代理部署位置。因此，本文在连续博弈的矩阵中寻找一种平衡，每一个Sd作为一行，每个Ri作为一列。

定理 1对于式(9)所示问题，除非 P=NP，否则不存在任何多项式时间逼近算法。

证明设n是实际问题中的规模大小，β(.)＞0是任意一个关于n的正函数。如果存在一个多项式时间算法，能够保证找到一组个数为k的集合S′d，则有

则P =NP。

因此，除非 P=NP，否则就不存在任何可以提供保证的算法。证毕。

4 顽健性采集代理部署算法

由于本文的优化部署目标函数是最小化攻击方效用，该效用使用了度量值作为目标函数和约束条件，目标函数具有非线性和非凸性。因此，不可能使用凸优化技术（如内部点方法）来解决此目标函数。此外，还有一个额外的限制，即采集代理部署变量是二进制的，所以使用梯度下降方法的混合整数非线性程序解决方案也没有用处，因为度量函数在搜索空间上不是连续的。同时考虑到敌对环境的设置，本文借鉴了文献[10]对抗设置来针对目标函数的优化。

4.1 RCD算法思路

RCD算法是在贪婪算法的基础上进行的。首先，将式(9)问题进行转换，找到替代的方案。

设集合Sd的大小最大为k，对于所有i可以满足Ri(Sd)≤z，z尽可能小。

然后，解决目标转换后成为式(11)问题：对于每个z的取值，可找到成本最低的集合Sd，对于所有的i可以满足Ri(Sd)≤z。如果成本最低的集合最多具有k个元素，则z是可行的。

最后，用一个固定的z来描述近似解方程(10)。对于z＞ 0，有

最初的函数Ri在z的位置被截断，其中，函数也是次模函数[27]，其平均值是

次模函数在凸组合下是封闭的，因此，是单调的次模函数。

4.2 RCD算法

本节详细介绍 RCD算法过程，该算法能找到一组，至少和最优集合一样的结果，但求解时间会稍微增加。贪婪算法和 RCD算法具体伪代码如算法1和算法2所示。

算法1贪婪算法

输入，z

输出采集代理S的部署位置集合Sd

算法2RCD算法RCD(R1,R2,…,Ri,k)

输入效用函数R1,R2,…,Ri，采集代理个数k

输出采集代理S的部署位置集合Sdbest

12) 输出Sdbest

首先，计算出算法2中所能取到的最大值zmax和最小值zmin，其中，最大值zmax是当所有采集代理都没有部署时，攻击方效用值最大；最小值zmin是当所有设备节点上都部署采集代理，攻击方效用最小。其次，求出最大值zmax和最小值zmin的平均值z，同时，针对任意一组采集代理集合Sd都可以计算出对应的收益。再次，调用算法1，根据均值z与依次找出每一轮中增量绝对值最大的设备节点ID的组合，并且将其赋值给Sdbest；如果Sdbest个数不满足k的要求，则使用z当前的取值赋给zmax或zmin。最后，再次调用算法1，依次循环来找到满足目标函数的部署集合。需要注意的是，每次调用算法1时，都是从空集开始的。

5 实验

5.1 算例

本节以一个小型网络为目标，如图2所示，将MADG模型和RCD算法进行实例化，该算例中网络设备节点共有5个，可以部署采集代理的设备，根据开放式Web应用程序安全项目（OWASP, Open Web Application Security Project）中top10的攻击类型，选取排名靠前的4类网络威胁事件。

图2 小型网络

采集代理与各指标之间的映射关系为

最小信标集合与威胁事件的对应关系为

根据上述思路可以在采集项中提取对应信息，生成特征信标。本算例中生成的特征信标为

ς1: SSH尝试失败次数＞阈值

ς2: SSH开始尝试次数＞阈值

ς3: Syn半连接个数

ς4: XXS尝试通过资源上的URL字符串/logfile/index.php?page =capture_data.php

ς5: XXS尝试通过表格NET_STAT_INFO注入ς6: XXS尝试通过资源上的URL字符串/logfile/index.php

ς7: 包含MySQL版本的字符串

ς8:接收到网络数据分组的个数＞正常值ς9: HTTP PHP文件POST请求

ς10: MySQL注入HTTP获取尝试

ς11: CPU利用率＞正常值

ς12：表格NET_STAT_INFO尝试SQL注入

ς13: MySQL注入类型询问

根据威胁事件与威胁事件特征信标之间的关系、威胁事件特征信标和采集代理之间的内在联系，构建威胁-采集树模型，如图3所示。每个威胁事件的最小特征信标集合发生的概率如表2所示。

表2 最小特征信标集合发生的概率

图3 小算例的威胁-采集树模型

由于每个特征信标是由不同的采集代理采集的采集项生成的，因此每个特征信标的置信度与生成它的采集代理的置信度保持一致。根据图2的网络结构可知，s1为防火墙被攻击方攻击的概率比较大，那么它的置信度相对就会小一些，因此，通过MTL给出s1的置信度为0.3，依次类推，给出其他设备置信度，如表3所示。

表3 采集代理置信度

通过对系统的机密性（confidentiality）、完整性（integrity）和可用性（availability）3个方面的考虑，同时参照OWASP中top10列表中的信息，给出本节算例中每个威胁事件的影响值，如表4所示。

表4 威胁事件影响值

本节算例分别使用EXACT算法、GOMD算法[14]、RCD算法进行计算，相关数据如表5所示，3种算法的具体求解数据见附录。

表5 3种算法求解

5.2 扩展

为测试本文提出的RCD算法的扩展性，在BA网络上使用50个设备节点、100个威胁事件作为基准进行实验，并从中生成不同规模的网络和不同规模的威胁事件集合，分别对每种规模的网络进行100次实验，取平均值作为实验结果。

本节主要对 RCD算法的时效性和顽健性进行验证，分别对其运行时间和求解质量进行实验，并与EXACT算法、MMI算法[12]和GOMD算法[14]进行对比。以上所有实验均在Windows 10的64位系统上运行，该系统加载Inter(R) i7处理器、500 GB硬盘和8 GB内存。

首先，本文在不同规模的网络（设备节点数量从0个节点增加到50个节点，步长为5）上进行实验，采集代理的数量k=3，各算法的运行时间如图4所示，求解质量如表6所示。

图4 不同规模网络的运行时间对比

表6 不同规模网络的求解质量对比

实验表明，EXACT算法随着网络规模增长（20个设备节点时）求解时间开始急剧增长，然而MMI算法[12]和 GOMD 算法[14]的求解时间增长相对缓慢；RCD算法求解时间的增长介于EXACT算法和GOMD算法之间。其中，当设备节点为35个时，由于要多次调用Greedy算法，RCD算法的运行时间出现急剧增长。

在求解质量方面，攻击者对目标系统的影响值越大，求解数值越大，求解的质量就越差。实验表明，MMI算法的求解质量最差，GOMD算法在小规模的网络下（如设备节点在 10个以内）所得解与EXACT算法保持一致，但随着网络规模的增加，GOMD算法与EXACT算法之间存在很大的偏差，而RCD算法始终与EXACT算法保持一致。

其次，在网络规模固定（设备节点数量为 50）的情况下，通过改变采集代理的数量（k=0，3，5，10，15，20，25），对RCD算法和3种对比算法进行实验。各算法的运行时间如图5所示，求解质量如表7所示。

图5 相同规模网络的运行时间对比

表7 相同规模网络的求解质量对比

随着采集代理数量的增加，产生的排列组合数量过多，EXACT算法计算时间急剧上升。当采集代理数量为3时，运行时间为730.057 s，当采集代理数量为5时，运行时间为1 500 s；MMI算法和GOMD算法可以在相对较短的时间内计算出有效解，计算时间的趋势呈线性增长；RCD算法在开始阶段，计算时间随着采集代理数量呈线性增长，当采集代理数量增加到3个时，运行时间增长趋势变缓，当采集代理数量增加到5个时，计算时间趋于稳定。

实验表明，当网络设备数量总数相等时，采集代理数量增加到一定数量后，EXACT算法求解质量会趋于恒定，且无法给出有效解。虽然 MMI算法和GOMD算法可以给出有效解，但求解质量无法达到精确解值。然而，RCD算法基本与EXACT算法保持一致，随着采集代理的数量增加，当EXACT算法无法给出有效解时，RCD算法仍然可以继续给出有效解。

通过实验表明，本文提出的RCD算法以时间成本为代价，保证了求解质量的精确度，因此该算法是有效可行的，且具有顽健性，还能够进行一定的扩展。

6 结束语

本文针对敌对情况下采集代理优化部署问题进行了研究。首先，将攻防双方建模为一个攻防博弈问题，提出一个度量攻防博弈模型——MADG模型；其次，对模型中涉及的系统、威胁和采集代理的相关属性进行定义和度量，并通过威胁事件和采集项之间的复杂联系构建了威胁-采集树；再次，采用数学规划对攻击方的效用函数进行构建，即优化的目标函数，并设计了一个具有顽健性的采集代理部署算法——RCD算法，使防守方在面对攻击方进行策略式攻击时，部署策略具有比较好的顽健性；最后，通过构建实际算例，分析了本文方法的有效性和可扩展性。

附录 3种算法的具体求解数据

3种算法的具体求解数据如表8～表10所示。

表8 EXACT算法精确求解

（表8续表）

表9 GOMD算法近似求解

（表9续表）

表10 RCD算法近似求解

（表10续表）