一种在防御约束下进行网络拆解的强化学习框架

《Neurocomputing》：A reinforcement learning framework for network dismantling under defense constraints

　　刘凯|青峰|郭丰伟|张凌|陈超|黄金才|刘忠|范长军中国国防科技大学系统工程学院，长沙，410073摘要复杂网络拆解对于打击恐怖组织等有害网络具有战略意义。然而，有害网络中的某些节点可能受到保护。若不考虑这一点，攻击者可能会耗费大量资源却仍无法将其清除。我们将这一问题定义为“在防御约束下的网络拆解”。针对这一问题，现有研究主要聚焦于基于攻防博弈的均衡策略，而针对具有未知受保护节点的网络的有效拆解策略研究仍然较少。在此，我们提出了一种基于强化学习的在防御约束下的网络拆解框架。该框架在启发式防御策略与设计模型之间建立了交互环境，通过具备防御意识的奖励信号来学习有效的攻击策略，从而拆解具有未知受保护节点的网络。大量实验表明，在不同的模拟防御机制下，我们的算法在大多数情况下均优于基准方法，无论是合成网络还是真实网络。本研究为在防御约束下的网络拆解提供了高效解决方案，对打击有害网络具有重要意义。引言网络为复杂社会系统提供了多种建模框架[1]、[2]、[3]，其中节点和边的结构可表示蛋白质相互作用[4]、[5]、社会关系[6]、[7]、[8]、电网[9]、军事合作[10]、[11]等等。由于其在维护国家安全和社会稳定方面的重要作用，网络常常成为恶意攻击的目标。因此，相关研究分为两条路径：提升有益网络的安全性[12]、[13]、[14]（如交通和电力系统[9]），以及拆解有害网络（如恐怖组织或疾病传播网络[15]、[16]、[17]、[18]）。后者被称为网络拆解[19]、[20]，其目标是通过策略性地移除一部分节点或边来破坏网络的结构和功能，以实现最小化特定目标函数[21]、[22]。由于高度异构的连接性，大多数真实网络对随机攻击具有较强的抵抗力，这使得它们难以被拆解[23]、[24]、[25]。不过，研究人员逐渐发现，基于网络拓扑结构的协议能够实现快速、精准的拆解。早期研究中采用了基于中心性的方法，这些方法可分为静态方法和动态方法。静态方法包括度中心性[23]、k核分解[26]、介数中心性[27]等。这些算法可扩展为动态版本，即在每次移除节点后更新网络结构并重新计算中心性指标。然而，这类方法的静态版本性能较差，而动态版本的计算复杂度较高。为平衡拆解效果与效率，研究人员随后提出了许多启发式方法，包括集体影响法[21]、遗传算法[28]、禁忌搜索法[29]、模拟退火法[30]以及人工蜂群算法[31]。近年来，人工智能的发展推动了基于机器学习的方法的出现。FINDER[32]利用图神经网络对节点进行特征描述，并通过马尔可夫决策过程和强化学习学习最优移除序列。MINER[33]则将这一思路扩展到多重网络。HITTER[34]用于处理超网络。HDGED[10]和SHATTER[11]专门研究异构作战网络的拆解策略。此外，SHEAR[35]和FIGHTER[36]则探索基于高价值边的网络拆解方法。这些基于深度强化学习的方法显著提升了拆解的效率与质量。然而，现有的网络拆解研究都假定所有节点被移除的难度相同。实际上，被攻击的节点可能受到保护，这会导致攻击效果下降、彻底失败甚至资源浪费。一些学者注意到了这一现象，进而开展了关于复杂网络中攻防博弈的研究。李等人建立了具有非均匀成本约束的静态攻防博弈模型，分析了在不同资源分配比例下攻击者和防御者的均衡策略[37]。胡等人从攻防博弈的角度研究了社交网络中关键节点的识别，探讨了对攻击者和防御者都至关重要的节点特征[38]。田等人提出了一个动态攻防框架，用于分析恶意软件传播过程中攻击者与防御者之间的战略互动[39]。现有研究要么仅从攻击者的角度研究网络拆解，忽视了网络的防御行为；要么通过数学模型结合传统算法来研究攻防博弈——这种方法大多局限于均衡策略分析，通常将每一方的策略选项限制为两到三种[37]、[38]、[39]。将防御行为纳入复杂网络拆解研究中具有重要的实际意义。现实世界网络中的关键节点往往受到保护。以犯罪网络为例，直接清除核心人物极为困难，这些关键人物通常有层层防御措施保护。在拆解策略设计中忽略防御因素，可能会导致理论模型与现实脱节，从而使所提出的攻击策略在实际应用中效率低下甚至完全无效。图1展示了这种风险：对受保护的节点发起攻击可能会失败，因此经过多轮攻击后，网络仍可能保留较大的连通分量。我们将这一问题定义为“在防御约束下的网络拆解”。迄今为止，针对这一问题的研究仍然较少。网络拆解本质上是一个NP难问题[22]，这意味着在多项式时间内找到全局最优解在计算上是不可行的。此外，某些关键节点可能受到保护，这种信息的不完整性进一步增加了问题的不确定性和计算复杂性。为应对这一挑战，我们研究了在防御约束下的网络拆解问题，并提出了ADNet，这是一种端到端的深度强化学习框架，能够明确纳入防御机制。我们将拆解过程建模为带有防御约束的马尔可夫决策过程，并设计具备防御意识的奖励信号，引导智能体攻击那些仍有影响力但防御较弱的次级关键节点，从而在对抗环境下生成有效的节点移除序列。我们的主要贡献如下：我们将防御约束引入传统的网络拆解问题，构建了更为真实且具有挑战性的场景；我们提出了ADNet，这是一种基于强化学习的框架，通过具备防御意识的奖励信号有效拆解受保护的网络，同时分析了不同防御策略和网络结构对ADNet性能的影响，该算法展现出良好的泛化能力；实验结果表明，无论是在合成网络还是真实网络中，且在不同的模拟防御机制下，我们的算法都具有良好的拆解效果，能够从小规模训练数据有效推广到大规模真实网络。本文结构如下：第2节阐述了网络拆解问题的形式化定义。第3节介绍了ADNet的离线训练及真实环境模拟方法。第4节展示了实验结果。最后，第5节给出了结论。问题形式化从形式上讲，我们定义了一个单层、无权重、无向的图，其中是节点集合，节点数量为；是边集合，边数量为。图的邻接矩阵为，当节点与节点之间存在边时取值，否则取值。网络拆解可以理解为依次移除一系列节点的过程。对于具有未知受保护节点的网络拆解问题，防御参考序列由以下方式定义：ADNet旨在基于图神经网络和深度强化学习，在具有防御能力的网络中寻找攻击序列，如图2所示。ADNet将具有未知受保护节点的网络中节点移除序列的搜索过程建模为马尔可夫决策过程。这一过程涉及通过状态、动作和奖励与环境进行顺序交互。此处，环境即为待分析的图，状态对应于……实验在实验部分，我们首先介绍了用于评估和比较ADNet性能的数据集和基准方法。其次，我们分析了不同防御策略和网络结构对ADNet的影响，并测试了我们的算法及基准方法在合成网络和真实网络中，在不同模拟防御机制下的拆解效果。结论现有的网络拆解研究主要遵循两种路径：第一种是仅从攻击者角度出发开发拆解方法，这类研究往往忽视了目标节点可能受到保护的现实，因此在遇到实际防御时会导致攻击无效和资源浪费。第二种是运用数学模型分析攻防博弈中的均衡策略，但这些研究大多局限于理论分析，涉及复杂的计算过程……CRediT作者贡献声明刘凯：写作——审稿与编辑、写作——初稿撰写、可视化、验证、软件、方法论、研究、形式分析、数据整理、概念构建。青峰：写作——审稿与编辑、写作——初稿撰写、验证、方法论、研究、概念构建。郭丰伟：写作——审稿与编辑、验证、软件、概念构建。张凌：写作——审稿与编辑、监督、研究。陈超：写作——审稿与编辑、利益冲突声明作者声明不存在任何可能影响本文研究的已知财务利益或个人关系。刘凯拥有中国东北林业大学的学士学位，目前在中国国防科技大学系统工程学院攻读管理科学与工程专业的博士学位。她的研究兴趣包括图神经网络和网络科学。