大家读完觉得有帮助记得关注和点赞摘要移动目标防御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(K1) 个目标中选择一个进行入侵防御者则试图通过覆盖其中一个目标来防止攻击。记目标集合为 [K]{1,…,K}。设防御者和攻击者的动作集分别为 D和 A。在此安全博弈设定中自然有 DA[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个目标上的保护分配向量。具体地若 dk则 xk1否则 xk0。这隐含约束 ∑k1Kxk1。防御者的单阶段效用函数为 ud(d,a)xaUdc(a)(1−xa)Udu(a)。因此防御者的效用 ud由被攻击目标 a的收益决定若 xa1则取 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策略的定义对于 k1,…,K记且 πd(k)[πd(k∣1,1),…,πd(k∣1,K),πd(k∣2,1),…,πd(k∣K,K)]T其中 1K0K是所有元素为10的 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为任意向量。定义对角矩阵 E1diag(K2−1 times1,…,1,0)E2diag(K2−1 times0,…,0,1)并构造修正矩阵 D(πd,πa,f)(M(πd,πa)−I)E1f1K2TE2。注意 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)K1)列到第 (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}k1K决定了ZD策略的可行性因此我们称 {ϕk}k1K为可行性参数。由于采用ZD策略的玩家可以单方面决定玩家期望效用之间的线性关系线性参数 α,β,γ起着至关重要的作用。根据其配置可以为不同的战略目的构建几种典型的ZD策略案例。我们介绍三种典型的ZD策略均衡策略通过在定义2中取 α0我们得到均衡策略它满足 ∑k1Kϕk(πd(k)−π^(k))βSaγ1K2。拥有均衡策略的玩家可以均衡对手的效用无论对手选择什么策略 [32]。勒索策略令 β−χα其中勒索因子 χ≥1。相应的勒索策略满足 ∑k1Kϕk(πd(k)−π^(k))ϕ[(Sd−θ1)−χ(Sa−θ1)]p0。当 χ≥1时采用勒索策略的玩家可以确保其自身效用的任何改进都超过对手的改进 [32, 5]。慷慨策略慷慨策略定义为 β−χα其中慷慨因子 χ≤1其形式为∑k1Kϕ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,maxmax{ϕ1,…,ϕk−1,ϕk1,…,ϕK}为除 ϕk外的最大值类似地定义 ϕ−k,min为最小值。以下定理提供了ZD策略存在的充分必要条件其证明可在附录-B中找到。定理 1ZD策略的存在性. 对于任何线性参数 α,β,γ存在一个ZD策略 πdZD强制 αuˉd(πdZD,πa)βuˉa(πdZD,πa)γ0当且仅当存在 ϕ1,…,ϕK−1≥0且 ϕK0使得对于所有 k∈[K]定理1表明如果线性参数满足不等式9则存在具有相应线性关系的ZD策略。9中的第一行表示防御者成功保护目标时的效用关系第二行表示攻击者成功入侵目标时的效用关系。这两种不同的情况是安全博弈的重要特征使其区别于零和博弈和对称博弈。在确认ZD存在之后有必要进一步检查其性能。根据定义1SSE策略在面对采用BR策略的攻击者时总是为防御者提供最高的效用。因此评估ZD策略的性能上界非常重要显然SSE策略作为一个合适的基准进行比较如附录-C所证。定理 2ZD策略的性能上界. 在假设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ˉdSSEuˉ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中的约束仅由 K4个线性不等式和方程组成。与规划2中的非凸约束和混合整数变量相比规划11在提供与SSE策略相同收益的同时交付了更低的计算复杂度。因此当规划11的约束得到满足时防御者可以采用这种理想ZD策略作为一种计算高效的替代MTD策略。聚焦于前一节讨论的典型ZD策略案例我们可以推导出规划11的简化版本每个版本都针对不同的防御需求。推论 1均衡ZD. 在假设1下如果 Uac(K)≥Uac(1), Uau(1)≥Uac(1), Uau(K)≤Uac(1)且对于 k2,…,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)−θ)且对于 k2,…,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)−θ)且对于 k2,…,K有 0(Udu(k)−θ)−χ(Uau(k)−θ)则防御者的慷慨ZD策略可以带来最佳收益。IV-B 针对最优ZD策略由于这种理想ZD策略可能并不总是存在当偏离SSE策略时采用最优ZD策略来减轻防御者的效用损失是合理的。在下文中我们认为防御者作为领导者旨在ZD策略集中获得一个最优策略以维持良好的防御性能同时避免采用带来高计算成本的SSE策略。为了获得最优ZD策略我们引入以下符号。记并定义集合 Λ为所有不同 Λ(i1,i2)的并集即 Λ∪i1i2Λ(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}k1K。这启发我们通过以下三个步骤来计算ZD策略。寻找线性参数 α,β,γ需要选择ZD策略的线性参数 α,β,γ以产生令防御者满意的效用。根据定理3如果存在理想ZD策略则可以通过求解规划11来确定这些参数以获得性能上界。否则可以通过求解定理4中的规划12来获得最优ZD策略以最大化防御者的效用。构建可行性参数 {ϕk}k1K由于9中的条件允许参数 {ϕk}k1K有多个可行解我们只需要给出一个明确的构造。我们首先考虑一系列 {ϕk}k1K其中 ϕK,ϕK−1,ϕ1分别作为最小值、次小值和最大值。通过利用9强制执行这个顺序我们依次得到一个可行的 {ϕk}k1K。计算策略 πd给定可行性参数可以通过取3中的 π^(k)来顺序计算策略 πd。具体地在第 k步残差项 αSdβSaγ1K2−∑ik1K−1ϕi(πd(i)−π^(i))被视为固定量。然后应用加权参数 {ωk}k1K来获得满足5中约束的 πd的有效实现。防御者ZD策略的整体计算总结如算法1。此外我们引入定理5来展示算法1输出的最优性保证其证明见附录-F。算法 1 ZD策略计算输入配置 U_l^c(k) 和 U_l^u(k)l ∈ P, k ∈ [K]加权参数 {ω_k}_{k1}^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 * ∑_{k2}^{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} - ∑_{ik1}^{K-1} ϕ_i(π_d(i)-ˆπ(i)) - ω_k ϕ_k ˆπ(k)]^。 end for π_d(K) 1 - ∑_{k1}^{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]这意味着除非PNP否则不存在确定性的多项式时间精确算法。计算挑战主要来自两个方面约束的非凸性和二进制变量 π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中的 K4个线性不等式和方程组成的系统这可以在多项式时间内完成例如使用标准线性规划技术复杂度为 O(K3)。如果不存在理想ZD策略算法继续求解规划12以获得最优ZD策略该规划有五个变量α,β,γ,ud,ua。该规划涉及来自并集 Λ的 O(K)个线性约束来自凸包 Conv(G)的 O(K)个约束最多 2K个顶点以及ZD等式 αudβuaγ0。虽然ZD等式引入了非凸耦合但固定的变量数量确保了问题可以在约束数量的多项式时间内求解。因此步骤1可以以 O(K3)的复杂度求解。步骤2使用显式公式计算可行性参数 {ϕk}k1K涉及 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}k1K。这启发我们通过以下三个步骤来计算ZD策略寻找线性参数 α,β,γ需要选择ZD策略的线性参数 α,β,γ以产生令防御者满意的效用。根据定理3如果存在理想ZD策略则可以通过求解规划11来确定这些参数以获得性能上界。否则可以通过求解定理4中的规划12来获得最优ZD策略以最大化防御者的效用。构建可行性参数 {ϕk}k1K由于9中的条件允许参数 {ϕk}k1K有多个可行解我们只需要给出一个明确的构造。我们首先考虑一系列 {ϕk}k1K其中 ϕK,ϕK−1,ϕ1分别作为最小值、次小值和最大值。通过利用9强制执行这个顺序我们依次得到一个可行的 {ϕk}k1K。计算策略 πd给定可行性参数可以通过取3中的 π^(k)来顺序计算策略 πd。具体地在第 k步残差项 αSdβSaγ1K2−∑ik1K−1ϕi(πd(i)−π^(i))被视为固定量。然后应用加权参数 {ωk}k1K来获得满足5中约束的 πd的有效实现。防御者ZD策略的整体计算总结如算法1。此外我们引入定理5来展示算法1输出的最优性保证其证明见附录-F。算法 1 ZD策略计算输入配置 U_l^c(k) 和 U_l^u(k)l ∈ P, k ∈ [K]加权参数 {ω_k}_{k1}^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 * ∑_{k2}^{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} - ∑_{ik1}^{K-1} ϕ_i(π_d(i)-ˆπ(i)) - ω_k ϕ_k ˆπ(k)]^。 end for π_d(K) 1 - ∑_{k1}^{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]这意味着除非PNP否则不存在确定性的多项式时间精确算法。计算挑战主要来自两个方面约束的非凸性和二进制变量 π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中的 K4个线性不等式和方程组成的系统这可以在多项式时间内完成例如使用标准线性规划技术复杂度为 O(K3)。如果不存在理想ZD策略算法继续求解规划12以获得最优ZD策略该规划有五个变量α,β,γ,ud,ua。该规划涉及来自并集 Λ的 O(K)个线性约束来自凸包 Conv(G)的 O(K)个约束最多 2K个顶点以及ZD等式 αudβuaγ0。虽然ZD等式引入了非凸耦合但固定的变量数量确保了问题可以在约束数量的多项式时间内求解。因此步骤1可以以 O(K3)的复杂度求解。步骤2使用显式公式计算可行性参数 {ϕk}k1K涉及 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进行攻击。成功的防御意味着防御者拦截了攻击者的入侵即 dtat而成功的攻击发生在攻击者避开了部署的防护即 dtat。具体地S0表示防御者成功防护的收益。防御者将防护服务从设备 i迁移到设备 j的成本记为 Yi,j≥0。对于攻击者R0代表成功攻击获得的奖励而 Ck0表示攻击设备 k的相应成本。在此基础上防御者的覆盖收益为 Udc(k)S−K1∑i1KYi,k其中 K1∑i1KYi,k表示迁移到设备 k的期望成本对所有可能的前置位置取平均 [42]。当被攻击的设备未被保护时防御者的未覆盖收益为 Udu(k)−K1∑i1KYi,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∑i1KRiwak。图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计算相比所提出的方法在保持可比防御性能的同时显著降低了计算复杂度。未来我们计划将所提出的方法扩展到马尔可夫博弈、具有折扣长期奖励的重复博弈以及存在不确定性和非理性行为的场景。
面向移动目标防御的零行列式策略：存在性、性能与计算
发布时间：2026/6/10 4:12:19
大家读完觉得有帮助记得关注和点赞摘要移动目标防御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(K1) 个目标中选择一个进行入侵防御者则试图通过覆盖其中一个目标来防止攻击。记目标集合为 [K]{1,…,K}。设防御者和攻击者的动作集分别为 D和 A。在此安全博弈设定中自然有 DA[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个目标上的保护分配向量。具体地若 dk则 xk1否则 xk0。这隐含约束 ∑k1Kxk1。防御者的单阶段效用函数为 ud(d,a)xaUdc(a)(1−xa)Udu(a)。因此防御者的效用 ud由被攻击目标 a的收益决定若 xa1则取 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策略的定义对于 k1,…,K记且 πd(k)[πd(k∣1,1),…,πd(k∣1,K),πd(k∣2,1),…,πd(k∣K,K)]T其中 1K0K是所有元素为10的 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为任意向量。定义对角矩阵 E1diag(K2−1 times1,…,1,0)E2diag(K2−1 times0,…,0,1)并构造修正矩阵 D(πd,πa,f)(M(πd,πa)−I)E1f1K2TE2。注意 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)K1)列到第 (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}k1K决定了ZD策略的可行性因此我们称 {ϕk}k1K为可行性参数。由于采用ZD策略的玩家可以单方面决定玩家期望效用之间的线性关系线性参数 α,β,γ起着至关重要的作用。根据其配置可以为不同的战略目的构建几种典型的ZD策略案例。我们介绍三种典型的ZD策略均衡策略通过在定义2中取 α0我们得到均衡策略它满足 ∑k1Kϕk(πd(k)−π^(k))βSaγ1K2。拥有均衡策略的玩家可以均衡对手的效用无论对手选择什么策略 [32]。勒索策略令 β−χα其中勒索因子 χ≥1。相应的勒索策略满足 ∑k1Kϕk(πd(k)−π^(k))ϕ[(Sd−θ1)−χ(Sa−θ1)]p0。当 χ≥1时采用勒索策略的玩家可以确保其自身效用的任何改进都超过对手的改进 [32, 5]。慷慨策略慷慨策略定义为 β−χα其中慷慨因子 χ≤1其形式为∑k1Kϕ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,maxmax{ϕ1,…,ϕk−1,ϕk1,…,ϕK}为除 ϕk外的最大值类似地定义 ϕ−k,min为最小值。以下定理提供了ZD策略存在的充分必要条件其证明可在附录-B中找到。定理 1ZD策略的存在性. 对于任何线性参数 α,β,γ存在一个ZD策略 πdZD强制 αuˉd(πdZD,πa)βuˉa(πdZD,πa)γ0当且仅当存在 ϕ1,…,ϕK−1≥0且 ϕK0使得对于所有 k∈[K]定理1表明如果线性参数满足不等式9则存在具有相应线性关系的ZD策略。9中的第一行表示防御者成功保护目标时的效用关系第二行表示攻击者成功入侵目标时的效用关系。这两种不同的情况是安全博弈的重要特征使其区别于零和博弈和对称博弈。在确认ZD存在之后有必要进一步检查其性能。根据定义1SSE策略在面对采用BR策略的攻击者时总是为防御者提供最高的效用。因此评估ZD策略的性能上界非常重要显然SSE策略作为一个合适的基准进行比较如附录-C所证。定理 2ZD策略的性能上界. 在假设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ˉdSSEuˉ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中的约束仅由 K4个线性不等式和方程组成。与规划2中的非凸约束和混合整数变量相比规划11在提供与SSE策略相同收益的同时交付了更低的计算复杂度。因此当规划11的约束得到满足时防御者可以采用这种理想ZD策略作为一种计算高效的替代MTD策略。聚焦于前一节讨论的典型ZD策略案例我们可以推导出规划11的简化版本每个版本都针对不同的防御需求。推论 1均衡ZD. 在假设1下如果 Uac(K)≥Uac(1), Uau(1)≥Uac(1), Uau(K)≤Uac(1)且对于 k2,…,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)−θ)且对于 k2,…,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)−θ)且对于 k2,…,K有 0(Udu(k)−θ)−χ(Uau(k)−θ)则防御者的慷慨ZD策略可以带来最佳收益。IV-B 针对最优ZD策略由于这种理想ZD策略可能并不总是存在当偏离SSE策略时采用最优ZD策略来减轻防御者的效用损失是合理的。在下文中我们认为防御者作为领导者旨在ZD策略集中获得一个最优策略以维持良好的防御性能同时避免采用带来高计算成本的SSE策略。为了获得最优ZD策略我们引入以下符号。记并定义集合 Λ为所有不同 Λ(i1,i2)的并集即 Λ∪i1i2Λ(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}k1K。这启发我们通过以下三个步骤来计算ZD策略。寻找线性参数 α,β,γ需要选择ZD策略的线性参数 α,β,γ以产生令防御者满意的效用。根据定理3如果存在理想ZD策略则可以通过求解规划11来确定这些参数以获得性能上界。否则可以通过求解定理4中的规划12来获得最优ZD策略以最大化防御者的效用。构建可行性参数 {ϕk}k1K由于9中的条件允许参数 {ϕk}k1K有多个可行解我们只需要给出一个明确的构造。我们首先考虑一系列 {ϕk}k1K其中 ϕK,ϕK−1,ϕ1分别作为最小值、次小值和最大值。通过利用9强制执行这个顺序我们依次得到一个可行的 {ϕk}k1K。计算策略 πd给定可行性参数可以通过取3中的 π^(k)来顺序计算策略 πd。具体地在第 k步残差项 αSdβSaγ1K2−∑ik1K−1ϕi(πd(i)−π^(i))被视为固定量。然后应用加权参数 {ωk}k1K来获得满足5中约束的 πd的有效实现。防御者ZD策略的整体计算总结如算法1。此外我们引入定理5来展示算法1输出的最优性保证其证明见附录-F。算法 1 ZD策略计算输入配置 U_l^c(k) 和 U_l^u(k)l ∈ P, k ∈ [K]加权参数 {ω_k}_{k1}^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 * ∑_{k2}^{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} - ∑_{ik1}^{K-1} ϕ_i(π_d(i)-ˆπ(i)) - ω_k ϕ_k ˆπ(k)]^。 end for π_d(K) 1 - ∑_{k1}^{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]这意味着除非PNP否则不存在确定性的多项式时间精确算法。计算挑战主要来自两个方面约束的非凸性和二进制变量 π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中的 K4个线性不等式和方程组成的系统这可以在多项式时间内完成例如使用标准线性规划技术复杂度为 O(K3)。如果不存在理想ZD策略算法继续求解规划12以获得最优ZD策略该规划有五个变量α,β,γ,ud,ua。该规划涉及来自并集 Λ的 O(K)个线性约束来自凸包 Conv(G)的 O(K)个约束最多 2K个顶点以及ZD等式 αudβuaγ0。虽然ZD等式引入了非凸耦合但固定的变量数量确保了问题可以在约束数量的多项式时间内求解。因此步骤1可以以 O(K3)的复杂度求解。步骤2使用显式公式计算可行性参数 {ϕk}k1K涉及 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}k1K。这启发我们通过以下三个步骤来计算ZD策略寻找线性参数 α,β,γ需要选择ZD策略的线性参数 α,β,γ以产生令防御者满意的效用。根据定理3如果存在理想ZD策略则可以通过求解规划11来确定这些参数以获得性能上界。否则可以通过求解定理4中的规划12来获得最优ZD策略以最大化防御者的效用。构建可行性参数 {ϕk}k1K由于9中的条件允许参数 {ϕk}k1K有多个可行解我们只需要给出一个明确的构造。我们首先考虑一系列 {ϕk}k1K其中 ϕK,ϕK−1,ϕ1分别作为最小值、次小值和最大值。通过利用9强制执行这个顺序我们依次得到一个可行的 {ϕk}k1K。计算策略 πd给定可行性参数可以通过取3中的 π^(k)来顺序计算策略 πd。具体地在第 k步残差项 αSdβSaγ1K2−∑ik1K−1ϕi(πd(i)−π^(i))被视为固定量。然后应用加权参数 {ωk}k1K来获得满足5中约束的 πd的有效实现。防御者ZD策略的整体计算总结如算法1。此外我们引入定理5来展示算法1输出的最优性保证其证明见附录-F。算法 1 ZD策略计算输入配置 U_l^c(k) 和 U_l^u(k)l ∈ P, k ∈ [K]加权参数 {ω_k}_{k1}^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 * ∑_{k2}^{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} - ∑_{ik1}^{K-1} ϕ_i(π_d(i)-ˆπ(i)) - ω_k ϕ_k ˆπ(k)]^。 end for π_d(K) 1 - ∑_{k1}^{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]这意味着除非PNP否则不存在确定性的多项式时间精确算法。计算挑战主要来自两个方面约束的非凸性和二进制变量 π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中的 K4个线性不等式和方程组成的系统这可以在多项式时间内完成例如使用标准线性规划技术复杂度为 O(K3)。如果不存在理想ZD策略算法继续求解规划12以获得最优ZD策略该规划有五个变量α,β,γ,ud,ua。该规划涉及来自并集 Λ的 O(K)个线性约束来自凸包 Conv(G)的 O(K)个约束最多 2K个顶点以及ZD等式 αudβuaγ0。虽然ZD等式引入了非凸耦合但固定的变量数量确保了问题可以在约束数量的多项式时间内求解。因此步骤1可以以 O(K3)的复杂度求解。步骤2使用显式公式计算可行性参数 {ϕk}k1K涉及 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进行攻击。成功的防御意味着防御者拦截了攻击者的入侵即 dtat而成功的攻击发生在攻击者避开了部署的防护即 dtat。具体地S0表示防御者成功防护的收益。防御者将防护服务从设备 i迁移到设备 j的成本记为 Yi,j≥0。对于攻击者R0代表成功攻击获得的奖励而 Ck0表示攻击设备 k的相应成本。在此基础上防御者的覆盖收益为 Udc(k)S−K1∑i1KYi,k其中 K1∑i1KYi,k表示迁移到设备 k的期望成本对所有可能的前置位置取平均 [42]。当被攻击的设备未被保护时防御者的未覆盖收益为 Udu(k)−K1∑i1KYi,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∑i1KRiwak。图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计算相比所提出的方法在保持可比防御性能的同时显著降低了计算复杂度。未来我们计划将所提出的方法扩展到马尔可夫博弈、具有折扣长期奖励的重复博弈以及存在不确定性和非理性行为的场景。
