大家读完觉得有帮助记得关注和点赞！！！
摘要
移动目标防御（MTD）通常被建模为重复的攻防博弈，以缓解持续性威胁。尽管强斯塔克尔伯格均衡（SSE）刻画了领导者-追随者框架下防御者的最优策略，但计算SSE通常伴随极高的计算复杂度，这严重限制了其在多目标MTD问题中的实际部署。本文提出采用零行列式（ZD）策略来构建MTD策略，旨在同时实现高防御性能和显著降低的计算复杂度。我们首先推导了ZD策略存在的充分必要条件，并研究了其性能表现，证明其性能上界与SSE策略相当。接着，我们构建了两种规划方案，用于在不同条件下寻找最优的ZD策略参数。此外，我们设计了一种算法来计算所提出的ZD策略，并通过与传统SSE计算的对比进行了复杂度分析。最后，我们在两个实际应用场景中进行了实验，验证了我们的结果。
I. 引言
移动目标防御（MTD）已成为应对日益严峻的持续性威胁、增强系统安全性的有力手段 [48, 15, 47]。与静态防护机制不同，MTD使防御者能够在多个关键目标间主动迁移防护资源，或随时间动态更新系统配置，从而遏制攻击 [22, 35]。这种交互本质上可建模为一种重复安全博弈，其中参与者根据历史结果调整策略。凭借其动态和主动性，MTD已广泛应用于信息物理系统（CPS），包括物联网（IoT）、云计算环境和操作系统 [46, 36, 6]。因此，如何有效构建MTD策略成为一个日益核心的问题。
防御者与攻击者之间的交互通常采用领导者-追随者框架建模，因为防御策略一旦部署便很少更新 。攻击者作为追随者，在探索和适应防御策略后选择最佳响应（BR）策略；而防御者作为领导者，在考虑攻击者行为的前提下最大化自身效用。该均衡被称为强斯塔克尔伯格均衡（SSE） ，它定义了此框架下防御者的最优策略。因此，防御者的SSE策略常被用于MTD部署以实现高性能防御 。
然而，SSE策略在重复安全博弈中的实际部署因其高计算复杂度而严重受阻。即使在单阶段斯塔克尔伯格安全博弈中，将SSE重构为混合整数线性规划后，其复杂度也会随目标数量的增加而急剧上升 [24]。扩展到重复博弈时，问题进一步演变为混合整数非凸规划，使得寻找全局精确解更加困难 [41, 2]。因此，尽管SSE策略对防御者是最优的，但其计算负担沉重，阻碍了防御者及时采用有效的MTD策略 [4, 3]。这促使我们探索一种新的方法，以构建兼具足够高效益和显著低复杂度的MTD策略。
零行列式（ZD）策略因其在单方面强制设定效用关系方面的卓越能力而备受关注，最初在迭代囚徒困境（IPD）中被提出 [32]。ZD策略允许玩家单方面强制建立双方期望效用之间的线性关系，无论对手采取何种策略。这种单方面强制性使得ZD驱动的方法能够以开环方式运行，便于快速部署，在人机交互（HCI）和演化博弈中具有吸引力 [43, 21]。
近年来，ZD策略在CPS中也引起了越来越多的关注，包括物联网、众包系统和区块链平台。然而，现有研究大多集中在双动作博弈 [23, 7, 40, 14] 或仅限于均衡ZD策略 [42]，这两者都只是ZD策略空间的一个有限子集。在安全博弈中，双动作博弈对应于仅有两个可行目标的场景，而均衡ZD策略仅固定一方的效用，限制了其在一般MTD中充分探索多样战略互动的能力。这些局限性凸显了对一种通用的、计算高效的、专为多目标MTD量身定制的ZD驱动方法的需求。
受此启发，本文致力于开发一种ZD驱动的方法来构建MTD策略，以实现高防御性能和低计算复杂度，区别于传统的SSE策略。为此，我们旨在研究ZD策略的存在性并刻画其性能。此外，还需要设计一种高效算法来计算所提出的ZD策略，并对其复杂度进行分析。
主要贡献总结如下：
理论构建：我们将重复安全博弈中的ZD策略表述为MTD策略，并刻画了其关键性质。特别地，我们推导了ZD策略存在的充分必要条件（定理1）。我们进一步研究了ZD策略的性能，表明其性能上界与SSE策略相匹配（定理2）。
优化方案：我们通过简化约束，建立了寻找ZD策略关键线性参数的规划方案。如果性能上界可达，我们提出了一种规划来寻找一组与防御者SSE效用一致的理想ZD策略参数（定理3）。如果不可达，我们构建了另一种规划来寻找最大化防御者效用的最优ZD策略参数（定理4）。
算法与复杂度：我们设计了一种算法（算法1）来计算所提出的ZD策略，并从形式上证明了其最优性保证（定理5）。此外，我们证明了该算法的计算复杂度显著低于传统的SSE计算。
相关工作：下文将从SSE和ZD策略的角度，重点围绕它们在CPS（尤其是MTD问题）中的应用进行文献综述。
SSE策略：SSE已广泛应用于CPS相关的安全场景。在单阶段斯塔克尔伯格安全博弈中，SSE常用于刻画防御者的最优防护策略 [24, 37]。单领导者多追随者（SLMF）斯塔克尔伯格框架被提出用于通过协调多中继来增强物理层安全 [13]。信号博弈也被用于建模安全环境中的欺骗和信息泄露 [31]。为了同时考虑误感知和欺骗，研究者为SLMF安全博弈开发了超博弈框架 [10]。最近，三级斯塔克尔伯格模型被引入，用于分析分层网络安全系统中的内部人员影响 [44]。总体而言，这些研究证明了SSE在建模CPS战略互动方面的有效性。
SSE在MTD问题中吸引了大量关注，特别是在防御者与攻击者存在重复互动的场景中。为了捕捉MTD机制的动态特性，基于SSE的方法已通过马尔可夫决策模型得到扩展 [16]。随后的研究进一步探讨了MTD策略的时间调度和时空部署 [26, 25]。此外，信号传递 [15] 和欺骗 [29] 等实际因素被纳入考量，以影响重复安全博弈中的攻击者行为。最近，针对两人马尔可夫博弈中攻击者响应的不确定性，研究者提出了鲁棒斯塔克尔伯格公式 [27]。基于斯塔克尔伯格的MTD方法也已应用于边缘智能等实际系统 [34]。总体而言，SSE在MTD策略的设计与分析中扮演着核心角色，并在现有研究中被广泛采用。
ZD策略：ZD策略最早在IPD中被提出 [32]，表明采用ZD策略的玩家可以单方面强制建立双方期望效用之间的线性关系。此后，ZD策略在公共物品博弈、人机交互和演化博弈中得到了广泛研究 [43, 19, 21]。基于其强制建立的线性关系，ZD策略大致可分为三种典型类型：均衡策略（固定对手效用）[32]、勒索策略（保证己方效用不低于对方）[32, 5] 和慷慨策略（促进合作，允许对方获得更高效用）[38]。
ZD策略在CPS中逐渐受到关注，但大多数现有研究集中在双动作博弈，即每个玩家只有两种可用动作。在众包系统中，ZD策略被用于激励合作，请求者和工人反复在合作与背叛之间选择 [23]。在审计和信号博弈中，防御者通过信号传递和审计采用ZD策略，而攻击者选择攻击或退出 [7]。在矿池管理中，多玩家互动中采用了ZD联盟，每个矿池在攻击与非攻击动作间选择 [40]。类似地，在区块链系统中，ZD策略被设计为交易交易的激励机制 [14]。
这种双动作形式通常对应于玩家仅面对两个可行目标的场景。CPS中考虑多动作博弈的研究极少。具体而言，均衡ZD策略曾被用于具有多个服务的物联网系统 [42]。需要注意的是，均衡ZD策略仅代表通用ZD策略空间的一个受限子集，不足以充分挖掘多样化的战略互动。因此，将通用ZD策略应用于多目标MTD问题仍然具有挑战性。
II. 预备知识与模型构建
本节介绍MTD的安全博弈模型，回顾带有SSE的领导者-追随者框架，并概述本文要解决的问题。
II-A 安全博弈模型
MTD策略是一种在无限时间范围 T={0,1,…,t,…}上，防御者 D与攻击者 A之间进行重复安全博弈的主动防御技术 [24, 27, 42, 29]。记玩家集合为 P={d,a}。攻击者从 K(K>1) 个目标中选择一个进行入侵，防御者则试图通过覆盖其中一个目标来防止攻击。记目标集合为 [K]={1,…,K}。设防御者和攻击者的动作集分别为 D和 A。在此安全博弈设定中，自然有 D=A=[K]，每个玩家选择一个目标进行保护或攻击。记防御者效用函数为 ud:D×A→R，攻击者效用函数为 ua:D×A→R。
考虑一个被广泛研究的重复单阶段安全博弈情形 [24, 20, 8]。设系数 Udc(k)表示当目标 k被攻击且同时被防御者覆盖时的防御者收益。若目标 k未被防御者覆盖，防御者的收益由系数 Udu(k)表示。给定防御者和攻击者的动作组合 (d,a)∈D×A，记 x=[x1,…,xK]T为防御者在 K个目标上的保护分配向量。具体地，若 d=k，则 xk=1；否则 xk=0。这隐含约束 ∑k=1Kxk=1。防御者的单阶段效用函数为 ud(d,a)=xaUdc(a)+(1−xa)Udu(a)。因此，防御者的效用 ud由被攻击目标 a的收益决定：若 xa=1，则取 Udc(a)，否则取 Udu(a)。类似地，攻击者的单阶段效用函数可由系数 Uac(k)和 Uau(k)建立，即 ua(d,a)=xaUac(a)+(1−xa)Uau(a)。
在重复安全博弈中，玩家通常采用记忆一阶策略，即玩家当前的动作取决于上一阶段的结果 [29]。设 dt和 at分别表示当前阶段 t≥1防御者和攻击者的动作，dt−1和 at−1表示他们在上一阶段 t−1的动作。记 ΔD为防御者动作集 D上的概率分布集合。防御者的记忆一阶策略定义为条件概率分布 πd(⋅∣dt−1,at−1)∈ΔD。具体地，πd(k∣dt−1,at−1)给出了在上阶段防御者动作为 dt−1、攻击者动作为 at−1的条件下，防御者在本阶段选择目标 k的概率。类似地，记 ΔA为攻击者动作集 A上的概率分布集合。攻击者的记忆一阶策略定义为 πa(⋅∣dt−1,at−1)∈ΔA。相应地，防御者的当前动作 dt从分布 dt∼πd(⋅∣dt−1,at−1)中抽取，攻击者的当前动作 at服从 at∼πa(⋅∣dt−1,at−1)。
在此设定下，重复的攻防互动导致效用动态变化。这种效用变化和长期互动要求双方考虑所有阶段的累积效用，而非单一阶段。因此，我们使用双方的期望长期效用来建模其目标 [16, 27, 11]：
简而言之，重复安全博弈记为 G={P,D,A,uˉd,uˉa,πd,πa}。防御者旨在通过记忆一阶策略 πd最大化其期望长期效用 uˉd。由于它在不同阶段动态地在不同目标间转移防护，因此 πd被视为一种MTD策略。
II-B 回顾SSE策略
在现实安全环境中，防御策略通常是可观测且持久的，部署后保持不变。这使得攻击者能够耐心观察和分析防御者的策略。因此，防御者与攻击者之间的互动很自然地建模为领导者-追随者框架 [24, 41]。具体而言，防御者是领导者，提前宣布策略；攻击者是追随者，在观察到防御者策略后选择自己的策略。
攻击者通常对防御者宣布的策略 πd采用最佳响应（BR）策略，因为这能最大化攻击者的效用。具体地，攻击者BR策略的集合定义为：BR(πd)=argmaxπa∈ΔAuˉa(πd,πa)。不失一般性，若存在多个最优策略，追随者会打破平局选择对防御者最不利的那个 [24, 10]。防御者旨在考虑攻击者的情况下最大化其期望效用，该均衡被定义为强斯塔克尔伯格均衡（SSE） [24, 41, 10]。
定义 1. 策略组合 (πdSSE,πaSSE)被称为重复安全博弈 G的SSE，如果
由于SSE定义了领导者-追随者框架下防御者的最优策略，其计算吸引了广泛关注。这个问题自然被处理为一个双层优化问题：上层防御者选择 πdSSE，下层约束确保攻击者的策略属于 BR(πdSSE)。为了解决这个双层优化问题，一种常见方法是将攻击者的优化问题重构为一组约束 [24, 37]。然后，原始的双层优化问题可以被重构为单层优化问题 [41, 10]。设 Z是一个足够大的常数，W,Q∈RK×K是分别表示与每个状态相关的防御者和攻击者收益的矩阵。因此，SSE可以通过以下混合整数规划求解，其证明见附录-A。
引理 1. 防御者的SSE策略 πd可通过以下规划求解：
II-C 问题陈述
尽管许多现有工作通过混合整数规划（2）解决SSE计算问题，但需要注意的是，当目标数量 K很大时，其计算复杂度会显著增加。这种复杂性源于几个因素。首先，该规划通过处理攻击者的BR策略引入了非凸可行域，这使得寻找全局最优的防御者策略变得复杂 [41]。其次，混合整数约束的存在进一步加剧了计算难度。即使在混合整数线性规划中，像分支定界这样的专用算法在某些条件下也常表现出指数级时间复杂度 [4]。因此，SSE的计算复杂度可能相对于目标数量呈指数增长 [28]，使得该问题在大规模场景下越来越难以解决。
总的来说，尽管SSE策略对防御者是最优的，但其计算负担沉重，阻碍了防御者及时采用有效的MTD策略。因此，本文旨在解决以下重要问题：
问题 1： 寻找一种新的方法来构建防御者的MTD策略，使其兼具足够高的收益和显著更低的复杂度。
为了解决这个问题，我们考虑以下在安全问题中被广泛采用的假设。
假设 1. 对于所有 k∈[K]，有 Udc(k)>Udu(k)。
假设1对于防御者抵抗攻击的动机是合理的，即如果目标 k被攻击，防御者保护目标 k的效用高于不保护该目标的效用。
III. ZD策略
如上所述，防御者通过承诺一个策略拥有单方面优势，而攻击者会采用BR策略。这自然引出了一个问题：能否利用这种单方面优势来解决问题1。ZD策略因能够单方面强制建立玩家期望效用之间自确定的线性关系而日益受到关注。在本节中，我们将介绍安全博弈 G中ZD策略的正式定义和基础性质。
III-A ZD策略的定义
对于 k=1,…,K，记
且 πd(k)=[πd(k∣1,1),…,πd(k∣1,K),πd(k∣2,1),…,πd(k∣K,K)]T，其中 1K（0K）是所有元素为1（0）的 K维列向量。此外，对于 l∈P，令
且 Sl=[SlT(1),…,SlT(K)]T为玩家在所有动作组合上的收益向量。在下文中，我们给出ZD策略的定义，并解释其为何能单方面强制建立玩家期望效用之间的线性关系。
定义状态转移矩阵 M(πd,πa)为（公式4，此处省略具体矩阵展开以节省篇幅，其核心是联合动作概率的排列）。
定义 2. 防御者的策略 πd是一个ZD策略，如果存在 α,β,γ∈R和 ϕk∈R，使得
对于任意防御者策略 πd和攻击者策略 πa，状态转移矩阵 M(πd,πa)由（4）定义，平稳向量 v满足 vT(M(πd,πa)−I)=0。令 f=[f1,f2,…,fK2]T为任意向量。定义对角矩阵 E1=diag(K2−1 times1,…,1,0)，E2=diag(K2−1 times0,…,0,1)，并构造修正矩阵 D(πd,πa,f)=(M(πd,πa)−I)E1+f1K2TE2。注意 D(πd,πa,f)将 M(πd,πa)−I的最后一列替换为 f。那么，如 [32, 39] 所示，
利用这一恒等式，（1）中的防御者和攻击者的期望效用可以重写为
因此，对于任何参数 α,β,γ∈R，我们有
此外，对于 k∈[K−1]，πd(k)−π^(k)是 D(πd,πa,αSd+βSa+γ)从第 ((k−1)K+1)列到第 (kK)列的 K个向量之和。因此，如果防御者的策略 πd满足（5），那么 D(πd,πa,αSd+βSa+γ)的最后一列是前 (K−1)K列的线性组合，即 det(D(πd,πa,αSd+βSa+γ))=0。因此，一旦防御者确定了线性参数 α,β,γ，并根据定义2中的这些参数选择了ZD策略 πd，则两个玩家的期望效用满足以下线性关系：
据此，我们称 α,β,γ为ZD策略的线性参数。此外，如定义2所示，给定任何线性参数，参数 {ϕk}k=1K决定了ZD策略的可行性，因此我们称 {ϕk}k=1K为可行性参数。
由于采用ZD策略的玩家可以单方面决定玩家期望效用之间的线性关系，线性参数 α,β,γ起着至关重要的作用。根据其配置，可以为不同的战略目的构建几种典型的ZD策略案例。我们介绍三种典型的ZD策略：
均衡策略：通过在定义2中取 α=0，我们得到均衡策略，它满足 ∑k=1Kϕk(πd(k)−π^(k))=βSa+γ1K2。拥有均衡策略的玩家可以均衡对手的效用，无论对手选择什么策略 [32]。
勒索策略：令 β=−χα，其中勒索因子 χ≥1。相应的勒索策略满足 ∑k=1Kϕk(πd(k)−π^(k))=ϕ[(Sd−θ1)−χ(Sa−θ1)]+p0。当 χ≥1时，采用勒索策略的玩家可以确保其自身效用的任何改进都超过对手的改进 [32, 5]。
慷慨策略：慷慨策略定义为 β=−χα，其中慷慨因子 χ≤1，其形式为：∑k=1Kϕk(πd(k)−π^(k))=ϕ[(Sd−θ1)−χ(Sa−θ1)]+p0。采用慷慨策略的玩家的效用改进不会高于对手，从而促进妥协与合作 [38]。
备注 1. 大多数现有的关于CPS的研究主要集中在双目标设置下的ZD策略 [23, 7, 40, 14, 11]。在这种只有两个目标的情况下，（5）中的第一个等式涉及 22维向量，这使得对特定ZD性质的分析是可处理的。然而，在多目标场景中，这个维度增加到 K2，并且随着 K的增长，策略形式变得极其复杂。因此，在多目标场景中，通用ZD策略的性质似乎比双目标情况复杂得多。
III-B ZD的基础性质
有了ZD策略的定义，我们自然会关心它的存在性和性能。在安全博弈的背景下，防御者ZD策略的线性参数 α,β,γ必须属于一个可行集，以确保ZD策略 πdZD的存在。记
我们定义 ϕ−k,max=max{ϕ1,…,ϕk−1,ϕk+1,…,ϕK}为除 ϕk外的最大值，类似地定义 ϕ−k,min为最小值。以下定理提供了ZD策略存在的充分必要条件，其证明可在附录-B中找到。
定理 1（ZD策略的存在性）. 对于任何线性参数 α,β,γ，存在一个ZD策略 πdZD强制 αuˉd(πdZD,πa)+βuˉa(πdZD,πa)+γ=0，当且仅当存在 ϕ1,…,ϕK−1≥0且 ϕK=0，使得对于所有 k∈[K]，
定理1表明，如果线性参数满足不等式（9），则存在具有相应线性关系的ZD策略。（9）中的第一行表示防御者成功保护目标时的效用关系，第二行表示攻击者成功入侵目标时的效用关系。这两种不同的情况是安全博弈的重要特征，使其区别于零和博弈和对称博弈。
在确认ZD存在之后，有必要进一步检查其性能。根据定义1，SSE策略在面对采用BR策略的攻击者时，总是为防御者提供最高的效用。因此，评估ZD策略的性能上界非常重要，显然，SSE策略作为一个合适的基准进行比较，如附录-C所证。
定理 2（ZD策略的性能上界）. 在假设1下，对于防御者的ZD策略 πdZD，
其中 (πdSSE,πaSSE)是安全博弈 G的SSE。
图1展示了SSE和ZD策略下玩家期望效用对 (uˉd,uˉa)的示意图比较。红星表示SSE结果，对应 (uˉdSSE,uˉaSSE)；蓝方块表示ZD结果，对应 (uˉdZD,uˉaZD)。蓝线代表ZD直线 αuˉd+βuˉa+γ=0。该图说明了防御者的性能差距，即 uˉdSSE>uˉdZD。
特别地，当ZD策略为防御者实现了性能上界，即（10）中的等式成立时，我们将该ZD策略称为理想ZD策略。然而，这种理想策略可能并不总是存在。如图1所示，由于可行效用对和ZD参数的限制，并不总能构建一条穿过SSE结果的ZD线性关系，这导致了防御者SSE策略和ZD策略之间的性能差距。在这些情况下，采用最优ZD策略是合理的，它在所有可行的ZD策略中为防御者产生最优性能。既然定理1保证了ZD策略的存在，定理2建立了ZD策略的性能上界，我们将在下一节研究如何选择ZD策略。
IV. ZD识别规划
请注意，任何ZD策略都由参数 α,β,γ表征。为了确定一个具体的ZD策略，我们在本节中建立应如何构建这些参数。
IV-A 针对理想ZD策略
由于定理2中SSE策略是防御者的最优防御策略，自然要研究是否存在一种理想ZD策略能为防御者带来最佳收益。以下定理建立了这种理想ZD策略存在的条件，其证明见附录-D。
定理 3（理想ZD的规划）. 在假设1下，如果线性参数 α,β,γ是以下规划的可行解，则防御者的ZD策略可以带来最佳收益：
当 α,β,γ满足规划（11）中的条件时，防御者可以获得与定理2中SSE策略相同的最佳收益，这证实了理想ZD策略的存在。此外，定理3提供了一种构建此类策略的实用方法：通过求解规划（11）得到 α,β,γ，就可以直接推导出理想ZD策略的线性参数。
此外，值得注意的是，规划（11）中的约束仅由 K+4个线性不等式和方程组成。与规划（2）中的非凸约束和混合整数变量相比，规划（11）在提供与SSE策略相同收益的同时，交付了更低的计算复杂度。因此，当规划（11）的约束得到满足时，防御者可以采用这种理想ZD策略作为一种计算高效的替代MTD策略。
聚焦于前一节讨论的典型ZD策略案例，我们可以推导出规划（11）的简化版本，每个版本都针对不同的防御需求。
推论 1（均衡ZD）. 在假设1下，如果 Uac(K)≥Uac(1), Uau(1)≥Uac(1), Uau(K)≤Uac(1)，且对于 k=2,…,K有 Uau(k)=Uac(1)，则防御者的均衡ZD策略可以带来最佳收益。
推论 2（勒索ZD）. 在假设1下，如果 χ=Uac(1)−θUdc(1)−θ≥1, 0≤(Udc(K)−θ)−χ(Uac(K)−θ), 0≥(Udu(K)−θ)−χ(Uau(K)−θ), 0≤(Udu(1)−θ)−χ(Uau(1)−θ)，且对于 k=2,…,K有 0=(Udu(k)−θ)−χ(Uau(k)−θ)，则防御者的勒索ZD策略可以带来最佳收益。
推论 3（慷慨ZD）. 在假设1下，如果 χ=Uac(1)−θUdc(1)−θ≤1, 0≤(Udc(K)−θ)−χ(Uac(K)−θ), 0≥(Udu(K)−θ)−χ(Uau(K)−θ), 0≤(Udu(1)−θ)−χ(Uau(1)−θ)，且对于 k=2,…,K有 0=(Udu(k)−θ)−χ(Uau(k)−θ)，则防御者的慷慨ZD策略可以带来最佳收益。
IV-B 针对最优ZD策略
由于这种理想ZD策略可能并不总是存在，当偏离SSE策略时，采用最优ZD策略来减轻防御者的效用损失是合理的。在下文中，我们认为防御者作为领导者，旨在ZD策略集中获得一个最优策略，以维持良好的防御性能，同时避免采用带来高计算成本的SSE策略。
为了获得最优ZD策略，我们引入以下符号。记
并定义集合 Λ为所有不同 Λ(i1,i2)的并集，即 Λ=∪i1=i2Λ(i1,i2)，表示所有可能的线性参数集合。此外，我们定义
为所有可能效用对的凸包。在下文中，我们制定一个规划来确定与最优ZD策略相对应的参数 α,β,γ，其证明见附录-E。
定理 4（最优ZD的规划）. 在假设1下，可以通过求解以下规划找到关于防御者最优ZD策略的线性参数 α,β,γ：
我们首先详细解释（12）中的每个约束。(α,β,γ)∈Λ检查所有可行ZD策略的线性参数集合；(ud,ua)∈Conv(G)探索所有可能的玩家效用对；而 αud+βua+γ=0展示了玩家效用与线性参数之间的关系。尽管规划（12）包含许多不等式和方程，但由于变量数量固定（限制在五个），它仍然是可处理的。与规划（2）相比，变量的减少使得规划（12）更加简单和可解。
定理3和定理4都描述了如何构建相应ZD策略的线性参数 α,β,γ，从而为策略 πd的算法设计奠定了基础。这两个定理的主要区别在于它们的解决方法。定理4提供了比定理3更通用的方法，用于识别能产生接近SSE策略效用的ZD策略的线性参数。从计算角度看，求解定理4中的（12）通常比求解定理3中的（11）更复杂。尽管如此，两者都比直接计算SSE策略容易处理得多。因此，这两个定理为计算ZD策略提供了实用且高效的方法，详细的算法设计和复杂度分析将在下一节中介绍。
V. ZD策略计算
在上一节中，我们已经展示了如何找到与ZD策略相对应的线性参数。基于这些结果，我们现在展示ZD策略的具体计算以及计算复杂度分析。
V-A 算法设计
如定义2所示，防御者的ZD策略 πd取决于线性参数 α,β,γ和可行性参数 {ϕk}k=1K。这启发我们通过以下三个步骤来计算ZD策略。
寻找线性参数 α,β,γ：需要选择ZD策略的线性参数 α,β,γ以产生令防御者满意的效用。根据定理3，如果存在理想ZD策略，则可以通过求解规划（11）来确定这些参数以获得性能上界。否则，可以通过求解定理4中的规划（12）来获得最优ZD策略，以最大化防御者的效用。
构建可行性参数 {ϕk}k=1K：由于（9）中的条件允许参数 {ϕk}k=1K有多个可行解，我们只需要给出一个明确的构造。我们首先考虑一系列 {ϕk}k=1K，其中 ϕK,ϕK−1,ϕ1分别作为最小值、次小值和最大值。通过利用（9）强制执行这个顺序，我们依次得到一个可行的 {ϕk}k=1K。
计算策略 πd：给定可行性参数，可以通过取（3）中的 π^(k)来顺序计算策略 πd。具体地，在第 k步，残差项 αSd+βSa+γ1K2−∑i=k+1K−1ϕi(πd(i)−π^(i))被视为固定量。然后，应用加权参数 {ωk}k=1K来获得满足（5）中约束的 πd的有效实现。
防御者ZD策略的整体计算总结如算法1。此外，我们引入定理5来展示算法1输出的最优性保证，其证明见附录-F。
算法 1 ZD策略计算
输入：配置 U_l^c(k) 和 U_l^u(k)，l ∈ P, k ∈ [K]；加权参数 {ω_k}_{k=1}^K，满足 ∑ ω_k = 1。 输出：防御者ZD策略 π_d。 1: 寻找线性参数 α, β, γ： if 存在 (11) 的可行解 then 返回 α, β, γ。 else 求解 (12) 并返回最优解 α, β, γ。 end if 2: 构建可行性参数 ϕ_1, …, ϕ_K： ϕ_K = 0。 ϕ_{K-1} = max{ |αU_d^c(K)+βU_a^c(K)+γ|, |αU_d^u(K)+βU_a^u(K)+γ| }。 for k = K-2, …, 2 do ϕ_k = |αU_d^c(k)+βU_a^c(k)+γ| + ϕ_{K-1}。 end for ϕ_1 = 2 * ∑_{k=2}^{K-1} ϕ_k + |αU_d^u(1)+βU_a^u(1)+γ| + |αU_d^c(1)+βU_a^c(1)+γ|。 返回 ϕ_1, …, ϕ_K。 3: 计算防御者ZD策略 π_d： for k = K-1, K-2, …, 1 do π_d(k) = [αS_d + βS_a + γ1_{K^2} - ∑_{i=k+1}^{K-1} ϕ_i(π_d(i)-ˆπ(i)) - ω_k ϕ_k + ˆπ(k)]^+。 end for π_d(K) = 1 - ∑_{k=1}^{K-1} π_d(k)。 返回 π_d。定理 5（最优性保证）. 给定游戏配置 Udc(k),Udu(k),Uau(k),Uac(k)（k∈[K]），算法1输出的策略 πd在所有防御者可行的ZD策略中产生最优效用。
V-B 计算复杂度
接下来，我们通过算法1分析SSE策略和ZD策略的计算复杂度。
计算SSE的复杂度：（2）中的混合整数规划是NP难的 [4]，这意味着除非P=NP，否则不存在确定性的多项式时间精确算法。计算挑战主要来自两个方面：约束的非凸性和二进制变量 πa(k∣i,j)∈{0,1}的存在。对于凸混合整数多项式规划，分支定界算法在最坏情况下的复杂度随整数变量数量呈指数增长 [4, 3]。我们的公式中涉及 K3个二进制变量，导致最坏情况时间复杂度为 O(2K3)。即使在更简单的混合整数线性规划情况下，计算精确解在计算上仍然要求很高。现有的分支定界方法的理论分析，可能辅以割平面技术，在特定假设下产生的复杂度界限如 O((M′)2K)[2]，这在 K上仍然是指数的。这种复杂性是重复博弈中计算SSE的固有问题，不仅仅是我们单层混合整数规划重构的结果。复杂性理论进一步支持了这一固有困难：在一般和随机博弈中寻找纳什均衡是PPAD完全的 [12, 9]，这强烈表明不存在针对相关均衡问题的多项式时间精确算法。
因此，通过（2）中的混合整数规划计算精确的SSE策略会带来 O(2K3)的最坏情况时间复杂度。计算负担随目标数量 K呈指数增长，使得在大规模实例中精确计算SSE策略变得难以处理。
计算ZD的复杂度：我们通过检查算法1中概述的三个步骤来分析ZD策略的计算复杂度。
步骤1：寻找理想或最优ZD策略的线性参数 α,β,γ。要检查理想ZD策略是否存在，可以求解（11）中的 K+4个线性不等式和方程组成的系统，这可以在多项式时间内完成，例如使用标准线性规划技术，复杂度为 O(K3)。如果不存在理想ZD策略，算法继续求解规划（12）以获得最优ZD策略，该规划有五个变量：α,β,γ,ud,ua。该规划涉及来自并集 Λ的 O(K)个线性约束，来自凸包 Conv(G)的 O(K)个约束（最多 2K个顶点），以及ZD等式 αud+βua+γ=0。虽然ZD等式引入了非凸耦合，但固定的变量数量确保了问题可以在约束数量的多项式时间内求解。因此，步骤1可以以 O(K3)的复杂度求解。
步骤2：使用显式公式计算可行性参数 {ϕk}k=1K，涉及 O(K)次操作。
步骤3：迭代计算防御者的ZD策略 πd，同样需要 O(K)次操作。
由于算法1的每一步都在多项式时间内运行，因此计算ZD策略的总体复杂度在 K上是多项式的，更具体地说，是 O(K3)。
与计算SSE策略的指数复杂度 O(2K3)相比，计算ZD策略的多项式复杂度 O(K3)使其成为一种计算高效的替代方案。因此，算法1以显著更低的计算成本实现了可比的防御性能，尤其是在具有许多目标的大规模安全博弈中。
V. ZD策略计算
在上一节中，我们展示了如何找到与ZD策略对应的线性参数。基于这些结果，我们现在介绍ZD策略的具体计算方法，并分析其计算复杂度。
V-A 算法设计
如定义2所示，防御者的ZD策略 πd取决于线性参数 α,β,γ和可行性参数 {ϕk}k=1K。这启发我们通过以下三个步骤来计算ZD策略：
寻找线性参数 α,β,γ：需要选择ZD策略的线性参数 α,β,γ以产生令防御者满意的效用。根据定理3，如果存在理想ZD策略，则可以通过求解规划（11）来确定这些参数，以获得性能上界。否则，可以通过求解定理4中的规划（12）来获得最优ZD策略，以最大化防御者的效用。
构建可行性参数 {ϕk}k=1K：由于（9）中的条件允许参数 {ϕk}k=1K有多个可行解，我们只需要给出一个明确的构造。我们首先考虑一系列 {ϕk}k=1K，其中 ϕK,ϕK−1,ϕ1分别作为最小值、次小值和最大值。通过利用（9）强制执行这个顺序，我们依次得到一个可行的 {ϕk}k=1K。
计算策略 πd：给定可行性参数，可以通过取（3）中的 π^(k)来顺序计算策略 πd。具体地，在第 k步，残差项 αSd+βSa+γ1K2−∑i=k+1K−1ϕi(πd(i)−π^(i))被视为固定量。然后，应用加权参数 {ωk}k=1K来获得满足（5）中约束的 πd的有效实现。
防御者ZD策略的整体计算总结如算法1。此外，我们引入定理5来展示算法1输出的最优性保证，其证明见附录-F。
算法 1 ZD策略计算
输入：配置 U_l^c(k) 和 U_l^u(k)，l ∈ P, k ∈ [K]；加权参数 {ω_k}_{k=1}^K，满足 ∑ ω_k = 1。 输出：防御者ZD策略 π_d。 1: 寻找线性参数 α, β, γ： if 存在 (11) 的可行解 then 返回 α, β, γ。 else 求解 (12) 并返回最优解 α, β, γ。 end if 2: 构建可行性参数 ϕ_1, …, ϕ_K： ϕ_K = 0。 ϕ_{K-1} = max{ |αU_d^c(K)+βU_a^c(K)+γ|, |αU_d^u(K)+βU_a^u(K)+γ| }。 for k = K-2, …, 2 do ϕ_k = |αU_d^c(k)+βU_a^c(k)+γ| + ϕ_{K-1}。 end for ϕ_1 = 2 * ∑_{k=2}^{K-1} ϕ_k + |αU_d^u(1)+βU_a^u(1)+γ| + |αU_d^c(1)+βU_a^c(1)+γ|。 返回 ϕ_1, …, ϕ_K。 3: 计算防御者ZD策略 π_d： for k = K-1, K-2, …, 1 do π_d(k) = [αS_d + βS_a + γ1_{K^2} - ∑_{i=k+1}^{K-1} ϕ_i(π_d(i)-ˆπ(i)) - ω_k ϕ_k + ˆπ(k)]^+。 end for π_d(K) = 1 - ∑_{k=1}^{K-1} π_d(k)。 返回 π_d。定理 5（最优性保证）. 给定游戏配置 Udc(k),Udu(k),Uau(k),Uac(k)（k∈[K]），算法1输出的策略 πd在所有防御者可行的ZD策略中产生最优效用。
V-B 计算复杂度
接下来，我们通过算法1分析SSE策略和ZD策略的计算复杂度。
计算SSE的复杂度：（2）中的混合整数规划是NP难的 [4]，这意味着除非P=NP，否则不存在确定性的多项式时间精确算法。计算挑战主要来自两个方面：约束的非凸性和二进制变量 πa(k∣i,j)∈{0,1}的存在。对于凸混合整数多项式规划，分支定界算法在最坏情况下的复杂度随整数变量数量呈指数增长 [4, 3]。我们的公式中涉及 K3个二进制变量，导致最坏情况时间复杂度为 O(2K3)。即使在更简单的混合整数线性规划情况下，计算精确解在计算上仍然要求很高。现有的分支定界方法的理论分析，可能辅以割平面技术，在特定假设下产生的复杂度界限如 O((M′)2K)[2]，这在 K上仍然是指数的。这种复杂性是重复博弈中计算SSE的固有问题，不仅仅是我们单层混合整数规划重构的结果。复杂性理论进一步支持了这一固有困难：在一般和随机博弈中寻找纳什均衡是PPAD完全的 [12, 9]，这强烈表明不存在针对相关均衡问题的多项式时间精确算法。
图2展示了物联网系统中的MTD策略。图3展示了物联网系统中ZD策略与SSE策略的性能比较。红色曲线显示了通过算法1计算的ZD策略实现的防御者效用，而蓝色曲线对应于通过求解（2）获得的SSE策略下的防御者效用。子图 (a)-(i) 展示了不同目标数 K和攻击者成本结构 ζ下的实验结果。
因此，通过（2）中的混合整数规划计算精确的SSE策略会带来 O(2K3)的最坏情况时间复杂度。计算负担随目标数量 K呈指数增长，使得在大规模实例中精确计算SSE策略变得难以处理。
计算ZD的复杂度：我们通过检查算法1中概述的三个步骤来分析ZD策略的计算复杂度。
步骤1：寻找理想或最优ZD策略的线性参数 α,β,γ。要检查理想ZD策略是否存在，可以求解（11）中的 K+4个线性不等式和方程组成的系统，这可以在多项式时间内完成，例如使用标准线性规划技术，复杂度为 O(K3)。如果不存在理想ZD策略，算法继续求解规划（12）以获得最优ZD策略，该规划有五个变量：α,β,γ,ud,ua。该规划涉及来自并集 Λ的 O(K)个线性约束，来自凸包 Conv(G)的 O(K)个约束（最多 2K个顶点），以及ZD等式 αud+βua+γ=0。虽然ZD等式引入了非凸耦合，但固定的变量数量确保了问题可以在约束数量的多项式时间内求解。因此，步骤1可以以 O(K3)的复杂度求解。
步骤2：使用显式公式计算可行性参数 {ϕk}k=1K，涉及 O(K)次操作。
步骤3：迭代计算防御者的ZD策略 πd，同样需要 O(K)次操作。
由于算法1的每一步都在多项式时间内运行，因此计算ZD策略的总体复杂度在 K上是多项式的，更具体地说，是 O(K3)。
与计算SSE策略的指数复杂度 O(2K3)相比，计算ZD策略的多项式复杂度 O(K3)使其成为一种计算高效的替代方案。因此，算法1以显著更低的计算成本实现了可比的防御性能，尤其是在具有许多目标的大规模安全博弈中。
VI. 实验验证
为了验证我们构建ZD驱动的MTD策略的方法，我们在包括物联网系统和众包系统在内的代表性应用场景中验证了我们的结果。
VI-A 物联网系统
我们考虑一个如图2所示的物联网系统 [1, 15, 42]，它正遭受持续性攻击。为了保护 K个设备上的关键资源，防御者动态地在设备间迁移防护服务。在每个阶段，防御者选择一个设备 dt部署防护服务，而攻击者选择一个设备 at进行攻击。成功的防御意味着防御者拦截了攻击者的入侵，即 dt=at；而成功的攻击发生在攻击者避开了部署的防护，即 dt=at。具体地，S>0表示防御者成功防护的收益。防御者将防护服务从设备 i迁移到设备 j的成本记为 Yi,j≥0。对于攻击者，R>0代表成功攻击获得的奖励，而 Ck>0表示攻击设备 k的相应成本。在此基础上，防御者的覆盖收益为 Udc(k)=S−K1∑i=1KYi,k，其中 K1∑i=1KYi,k表示迁移到设备 k的期望成本，对所有可能的前置位置取平均 [42]。当被攻击的设备未被保护时，防御者的未覆盖收益为 Udu(k)=−K1∑i=1KYi,k，反映了防御者仅承担分摊的迁移成本而未获得任何安全收益。类似地，攻击者的覆盖收益为 Uac(k)=−Ck，代表攻击成本。当攻击者成功攻击一个未受保护的设备时，其未覆盖收益为 Uau(k)=R−Ck。为了检验ZD策略与SSE策略之间的效用差异，我们为不同的运营场景引入了两个参数。参数 θ∈[0,1]控制防御者的迁移成本分布 Yi,j(θ)，捕捉不同水平的移动性和重构灵活性。参数 ζ∈{1,2,3}索引不同的攻击者成本结构 Ck(ζ)，对应于不同的攻击能力和强度。
如图3所示，我们比较了通过算法1获得的ZD策略的防御者效用与SSE策略下的效用。尽管SSE策略始终产生更高的效用，但在所有考虑的场景中，SSE与ZD策略之间的偏差仍然很小。这表明，尽管SSE是最优的，但两种策略之间的性能差距是有限的。值得注意的是，对于某些参数配置，ZD策略实现了与SSE策略相同的效用。这些结果表明，采用所提出的ZD策略不会导致防御性能的显著损失，在某些情况下甚至能保持最优的防御效用。
图4展示了ZD策略和SSE策略的平均计算时间。橙色曲线显示了通过算法1计算ZD策略的平均计算时间，蓝色曲线对应于使用（2）求解SSE策略的平均计算时间。浅橙色和浅蓝色阴影区域分别表示50次独立运行中计算时间的范围（即最小值到最大值）。图4(a)采用线性坐标，图4(b)采用对数坐标。
在图4中，我们进一步比较了ZD策略和SSE策略的计算时间，其中我们随机生成游戏配置并取50个独立案例的平均计算时间。在图4(a)中可以清楚地观察到，对于 K∈[2,15]，计算SSE策略所需的时间远多于计算ZD策略所需的时间。此外，在图4(b)中，当 K较大时（纵轴取对数），SSE策略的计算时间增长远快于ZD策略。因此，对于大规模目标问题，计算SSE策略变得不切实际，而ZD策略在维持防御性能方面仍保持计算高效。
VI-B 众包系统
我们考虑一个众包系统 [17, 23, 18]，其中请求者发布一个由 K个任务（如图像标注、文本翻译和数据验证）组成的大规模项目，如图5所示。在每个阶段，请求者优先考虑任务并分配验证资源，以鼓励工人专注于当前任务。工人可能是诚实的（可信赖的）或恶意的（不可信赖的）。诚实的工人忠实地遵循请求者的指示，并努力交付高质量的结果。相反，恶意工人试图通过秘密提交低质量结果或将精力转移到其他任务上来阻碍项目进展并获取额外利益。
图5展示了包含诚实和恶意工人的众包系统。
具体地，令 Rkr表示任务 k完成时的请求者奖励。如果由于恶意行为导致任务 k被提交为低质量，请求者会获得额外的损失 mk。此外，令 c表示请求者的额外验证资源成本。对于工人，令 Rkw和 Rˉkw分别表示诚实工人和恶意工人收到的奖励。此外，令 ak表示恶意工人通过将精力从任务 k秘密转移到其他任务所能获得的额外收益。那么，当请求者验证任务 k时，如果提交了高质量结果，请求者的覆盖收益为 Udc(k)=Rkr−c。否则，Udc(k)=Rkr−mk−c。当请求者不验证任务 k时，请求者的未覆盖收益降至 Udu(k)=−c，反映仅产生了验证资源成本。对于工人，诚实工人在任务 k被验证并接受时获得收益 Uac(k)=Rkw，否则 Uau(k)=0。相比之下，恶意工人获得 Uac(k)=Rˉkw，以及 Uau(k)=K1∑i=1KRiw+ak。
图6展示了当与类型在诚实和恶意之间周期性切换的工人互动时，请求者在ZD和SSE策略下的长期平均效用。橙色曲线代表通过算法1计算的ZD策略下的请求者效用，蓝色曲线对应于通过求解（2）获得的SSE策略下的效用。子图(a)–(c)考虑了工人初始为诚实的情况，切换周期分别为50、20和10。子图(d)–(f)考虑了工人初始为恶意的情况，具有相同的切换周期。浅红色阴影区域表示工人处于恶意状态的阶段，而无阴影区域对应于诚实工人。
如图6所示，我们展示了在工人类型周期性切换下请求者的长期平均效用，其中工人随时间在诚实和恶意行为之间交替。如图6(a)–(c)所示，当工人初始为诚实时，与SSE策略相比，ZD策略导致的长期平均效用波动更小。此外，如图6(d)–(f)所示，当工人初始为恶意时，ZD策略实现了比SSE策略更高的长期平均效用。这一优势源于ZD策略的单方面强制性，使其能够动态变化的对抗行为下保持稳定且鲁棒的性能。
VII. 结论
本文研究了在重复安全博弈中构建MTD策略的ZD策略。我们分析了ZD策略的存在性和性能，并研究了其性能表现。为了实现实际部署，我们为理想ZD策略和最优ZD策略分别开发了规划方案。此外，我们设计了一种算法来计算所提出的ZD策略，并证明了其最优性保证。与传统的SSE计算相比，所提出的方法在保持可比防御性能的同时，显著降低了计算复杂度。未来，我们计划将所提出的方法扩展到马尔可夫博弈、具有折扣长期奖励的重复博弈，以及存在不确定性和非理性行为的场景。
