文章快速检索  
  高级检索
不完全信息条件下计算机网络对抗行动鲁棒博弈模型
王长春, 汤锦辉, 朱永文, 程晓航    
空军装备研究院, 北京 100085
摘要:在分析不完全信息计算机网络对抗问题特点基础上, 运用马尔可夫决策描述网络状态转移过程, 用区间数刻画不确定参数, 以折扣总回报值为目标函数, 提出计算机网络对抗行动鲁棒博弈模型. 采用凸分析理论对计算机网络对抗鲁棒博弈模型进行分析, 得到网络攻防双方的收益函数为等度、连续凸函数, 攻防双方存在均衡策略且为一个压缩映射. 通过算例分析, 验证方法的可行性和有效性.
关键词网络对抗     区间数     鲁棒博弈     凸分析    
Robust game model of computer network operation with incomplete information
WANG Chang-chun, TANG Jin-hui, ZHU Yong-wen, CHENG Xiao-hang     
Air Force Equipment Academy, Beijing 100085, China
Abstract:On the basis of analyzing the characteristic of computer network operation (CNO), describing the network transaction by Markov process, describing the uncertain factors by interval number, a new CNO mode whose objective function is the summary of discounted reward is established. Then, it is proved that the reward function of CNO is a contraction mapping and equi-continuous function, and the equilibrium strategy is got by solving the corresponding nonlinear programming problem. In the end, the calculation and sensitive analysis of example demonstrate the proposed method is feasible and effective.
Key words: network operation     interval coefficients     robust game     convex analysis    

0 引言

在计算机网络对抗中,信息是指一切与攻防行动有关的知识, 包括网络系统脆弱性、攻防参与者的攻防能力、过去的攻防 行动和结果以及外界环境的作用等. 对于完全信息条件下计算机网络对抗问题, 笔者已经在文献[1]中进行了研究. 然而,在许多实际问题中, 攻防双方往往存在许多不完全信息. 对于网络防御者来说, 虽然能够准确、具体和全面地了解网络状态 和网络拓扑结构, 但是无法预测攻击者在何时、何地以何种方式进行攻击, 网络攻击引发的大混乱可能在不知不觉中拉开序幕.对于网络攻击者来说, 虽然在对抗过程中占主动地位, 但是在目标系统信息获取上往往还只是一个盲目搜索和攻击试探的过程. 导致计算机网络对抗过程存在许多不完全信息的主要原因有:

1) 技术因素. 由于局中人运用传感器来对网络状态进行观察, 并在此基础上确定其最优策略.但是没有一个传感器能够精确地对环境进行感知, 通常都存在一个虚警率,也就是说对局中人行动策略的信息是不完全的.

2) 对抗因素. 在网络对抗过程中, 攻击者运用网络侦查手段探测目标对象的突破口, 实施多种攻击;防御者采用多种安全防护技术手段, 动态监测分析各种攻击事件,在最短的时间内修复系统. 这种``魔高一尺, 道高一丈''的循环使得对抗过程充斥着各种不完全信息.

3) 结构因素. 病毒、木马及网络蠕虫等攻击具有明显的分岔、混沌等非线性复杂动力学行为特征.

本文所研究的不完全信息条件下计算机网络对抗问题, 就是在网络攻击者和防御者不确切知道网络状态转移概率、网络对抗效果的前提下,研究如何处理各种不确定性参数, 并通过模型求解来制定出科学有效的网络对抗方案. 传统不完全信息博弈方法需要专家给出各种可能事件的概率分布, 然后再通过海萨尼转换进行计算[2, 3]. 但是抽取专家知识是一个十分困难的事情, 尤其是当专家对这些问题所掌握的先验信息不是很多的时候. 虽然要专家给出各个参数的概率分布很困难, 但是给出各个参数的取值范围还是比较容易做到的, 本文正是基于这样的考虑来展开研究工作的. 首先将攻防条件下网络状态转移概率和收益值用一个区间数来表示, 在此基础上建立不完全信息计算机网络对抗的鲁棒博弈模型, 推导出模型的各种性质,并且通过算例验证模型的有效性. 1 不完全信息条件下计算机网络对抗行动鲁棒博弈模型 1.1 鲁棒博弈模型定义

在1967年之前,对不完全信息博弈尚未找到处理方法, 现在普遍认同的规范化方法是由海萨尼提出来的[4]. 然而,已有不少学者对Harsanyi具有相同先验概率和共同知识提出了置疑[5, 6, 7], 并且海萨尼方法在应用过程中, 需要通过统计分析或者专家判断来给出各种类型的概率分布, 然而要得到随机参数的概率分布是非常困难的. 特别是具有自适应性的计算机网络对抗行为,即使有一些历史数据, 由于这些数据在未来对抗活动会随着时间的推移而改变, 会在未来对抗活动中失效.

作为鲁棒性博弈问题的开山之作, Aghassi等针对收益函数为一个区间数的问题[8], 提出一种与概率分布无关的鲁棒博弈模型,在定义鲁棒均衡概念基础上, 运用多线性方程组理论设计了模型求解算法. 沿着这条思路, 日本东京大学Nishimura教授假设每个局中人策略属于某类不确定集合[9], 且每个局中人都是运用鲁棒优化方法制定策略,在此基础上, 提出与概率分布无关的$N$人博弈框架,给出了鲁棒博 弈问题均衡策略存在的充分必要条件[10], 并将原问题转化为二级锥互补问题进行求解. 加利福利亚大学Pita教授针对恐怖主义袭击安全策略制定问题, 运用寡头鲁棒博弈模型对问题建模, 模型考虑了恐怖分子攻击过程中的各种不确定性, 并运用混合整数规划进行求解[11].

为了对鲁棒性博弈理论有一个更加清楚的认识, 现从不完全信息表示、期望收益值计算、均衡策略定义、均衡策略存在性条件、求解方法、模型运用条件七个方面与传 统的Bayesian博弈模型进行对比,如表 1所示. 在表中,$i\in(1,2,\cdots, N)$ 表示鲁棒博弈问题所有局中人集合; $\tilde{C}$ 表示局中人收益矩阵集合; $S$ 表示所有局中人策略集合; $S_{a_{i}}$ 表示除了局中人 $i$ 其它局中人的策略集合; $\tilde{P}$ 为不确定事件的概率分布函数集合; $u^{i}$ 为局中人 $i$ 的行动策略; $x^{-i}$ 除了局中人 $i$ 其它局中人的行动策略; 并分别定义$x^{-i}=(x^{1},\cdots,x^{i-1},x^{i+1},\cdots,x^{N})$, $(x^{-i},u^{i})=(x^{1},\cdots,x^{i-1},u^{i},x^{i+1},\cdots, x^{N})$.

表 1 贝叶斯博弈模型与鲁棒博弈模型比较
1.2 计算机网络对抗行动模型

与传统博弈模型不同, 本文将运用区间数方法来对不确定性参数进行刻画[20, 21, 22]. 不完全信息条件下计算机网络对抗行动鲁棒博弈模型用一个五元组$(I,S, A,\tilde{P},\tilde{C})$ 表示,其中:

1) $I=\{1,2,\cdots,N\}$ 是参加网络对抗的局中人集合. 若攻击者的数量大于2,则表示分布式系统攻击; 若防御系统的数量大于2, 则表示多个防御系统协同防御.

2) $S=\{s_{1},s_{2},\cdots,s_{k}\}$ 是网络对抗过程中的状态集合.

3) $A=\{a_{1},a_{2},\cdots,a_{s}\}$ 表示所有局中人在网络所有状态的行动集合,$a_{s}$ 表示网络处于状态$s$ 时所有局中人策略集合且$a_{S}=\prod_{i=1}^{N}a_{S}^{i}$.

4) $\tilde{P}: S\times A \times S\rightarrow [0,1]$ 是计算机网络对抗过程状态转移概率函数. 与文献[4] 模型类似, 状态转移函数由网络状态和攻防双方所采取的行动决定, 所不同的是转移概率值不是一个具体的实数,而是一个区间数.

5) $\tilde{C}: S\times A \times S\rightarrow \mathbb{R}$, $\tilde{C}=\prod\limits_{s\in{S}}\prod\limits_{i\in{I}} \tilde{C}_{sa_{s}}^{i}$,其中$\tilde{C}_{sa_{s}}^{i}$ 表示网络处于状态$s$ 时局中人采取行动~$a_{s}$ 时,局中人$i$ 的收益值或者报酬值,该值也是一个区间数.

在网络对抗的各个状态,各局中人可以采取混合策略, 令$x_{s}^{i}=(x_{s,1}^{i},\cdots,x_{s,m_{s}^{i}}^{i})\in X_{s}^{i}$ 为局中人$i$ 行动$a_{s}^{i}$ 的概率分布,其中$m_{s}^{i}$ 为集合$a_{s}^{i}$ 行动个数,$X_{s}^{i}$为局中人$i$的策略集合. 假设局中人$i$ 在网络对抗各个状态的稳定策略为$x^{i}=(x_{1}^{i}, \cdots,x_{M}^{i})$,$x^{-i}=(x^{1},\cdots,x^{i-1},x^{i+1}, \cdots,x^{N})$ 表示除局中人$i$ 外其它所有局中人所采取的策略. 为了将局中人$i$ 策略$u_{i}$ 与其它局中人策略区别开来, 定义$(x^{-i},u^{i})=(x^{1},\cdots,x^{i-1},u^{i},x^{i+1}, \cdots,x^{N})$. 在此基础上可以得到,对抗策略$a_{s}\in A$ 被采取的概率为$\prod_{m=1, m\neq1}^{N}x_{s,a_{s}^{m}}^{m}u_{s,a_{s}^{m}}^{i}$,并且对于 $\forall s\in S$,$i\in I$,局中人$i$ 从状态$s$ 开始对抗的期望总收益值$g_{s}^{i}(x_{s}^{-i},u_{s}^{i},v^{i})$ 可以表示为:

$g_{s}^{i}(x_{s}^{-i},u_{s}^{i},v^{i})=\sum \limits_{a_{s}\in A}\prod \limits_{m=1,m\neq1}^{N}x_{s,a_{s}^{m}}^{m}u_{s,a_{s}^{i}}^{i}\bigg( \tilde{C}_{sa_{s}}^{i}+\beta_{i}\sum\limits_{k=1}^{M}\tilde {P}_{sa_{s}k}v_{k}^{i}\bigg)$ (1)
其中,$\tilde{C}_{sa_{s}}^{i}$ 表示网络处于状态$s$ 局中人$i$采取行动$a_{s}$时,局中人$i$的收益值; $v_{k}^{i}$ 为网络转移到状态$k$ 时局中人$i$ 的稳定收益值. 从(1) 式可以得到, 局中人$i$ 的期望收益值由网络处于状态$s$ 时即刻期望收益值和系统处于未来状态时期望收益值两部分组成. 2 计算机网络对抗行动鲁棒博弈模型分析 2.1 网络对抗鲁棒均衡策略定义

对于目标函数含区间参数优化问题,国内外学者主要包括3类处理方法: 其一是基于区间数序关系的规划方法,思想是在引入区间数序关系基础上, 将问题转化为参数确定问题求解[12]; 其二是基于最大最小后悔准则的区间规划方法,如文献[13, 14]; 其三是通过构造双层规模来求取决策变量的最优取值点或取值区间\,[15]. 根据计算机网络对抗特点, 本章选择最大最小后悔准则方法对模型进行分析. 如果局中人$i$鲁棒均衡策略存在, 根据Bellman等式和最大最小后悔准则[16],局中人$i$ 的鲁棒收益值$w_{s}^{i}$ 满足:

$w_{s}^{i}=\min\limits_{u_{s}^{i}\in X_{s}^{i}}\max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C}, \tilde {P}_{sa_{s}k}\in\tilde{P}}\sum \limits_{a_{s}\in A}\prod \limits_{m=1,m\neq1}^{N}x_{s,a_{s}^{m}}^{m} u_{s,a_{s}^{i}}^{i}\bigg(\tilde{C}_{sa_{s}}^{i}+\beta_{i}\sum\limits_{k=1}^{M}\tilde {P}_{sa_{s}k}w_{k}^{i}\bigg)$ (2)

为使变量表示简易,定义局中人$i$ 在网络状态$s$ 时的最优期望收益值函数$\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde {P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i}) \\ =\sum \limits_{a_{s}\in A}\prod_{m=1, m\neq1}^{N}x_{s,a_{s}^{m}}^{m}u_{s,a_{s}^{i}}^{i} (\tilde{C}_{sa_{s}}^{i}+\beta_{i}\sum_{k=1}^{M}\tilde {P}_{sa_{s}k}w_{k}^{i})$,从而等式(2) 可以简化为 $w_{s}^{i}=\min \limits_{u_{s}^{i}\in X_{s}^{i}} \max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C},\tilde {P}_{sa_{s}k}\in\tilde{P}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde {P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})$. 根据文献[8] 均衡策略定义, 下面给出不完全信息条件下计算机网络对抗行动鲁棒博弈均衡策略定义.

定义1 (网络对抗鲁棒博弈均衡策略) 网络对抗策略$x \in X$ 为不完全信息条件下计算机网络对抗行动鲁棒博弈模型的均衡策略, 当且仅当存在最优期望收益向量$w=(w^{1},\cdots,w^{N})$, 使得对于任意局中人$i\in I$,网络状态$s\in S$,满足:

$\begin{aligned} w_{s}^{i}=\min \limits_{u_{s}^{i}\in X_{s}^{i}}\max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C},\tilde {P}_{sa_{s}k}\in\tilde{P}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde {P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})\\ x_{s}^{i}\in \arg \min \limits_{u_{s}^{i}\in X_{s}^{i}}\max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C},\tilde {P}_{sa_{s}k}\in\tilde{P}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde {P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i}) \end{aligned}$ (3)
该均衡策略表明: 如果网络对抗策略$x$ 中每个局中人的策略相对于其它局中人来说,都是最优鲁棒性响应策略, 那么策略$x$ 为不完全信息条件下计算机网络对抗模型的马尔可夫完美均衡[13]. 在对网络对抗鲁棒博弈均衡策略定义的基础上, 下一节将对模型均衡策略的存在性进行证明. 2.2 网络对抗鲁棒模型分析

计算机网络对抗鲁棒博弈模型均衡策略存在性证明过程分为两个阶段,在证明过程中假设收益值和转移概率集合都是有界闭集.

第一阶段 证明在计算机网络对抗过程中, 局中人的最优响应策略是一个压缩映射,并且对于任意对抗策略, 存在唯一一个鲁棒性收益向量与之对应.

定义网络对抗局中人$i$ 稳定策略收益集合为$W^{i}\equiv\{w_{s}^{i}\in \mathbb{R}\}_{s\in S}$,所有局中人稳定策略收益空间为$W\equiv \{ W^{i}\}$,稳定收益空间$W$ 的无穷范数定义为$\|w\|_{\infty}=\max \limits_{i\in I,s\in S}|w_{s}^{i}|$.

命题1 在计算机网络对抗鲁棒博弈模型中,如果局中人$i$ 稳定策略收益向量映射函数$\gamma_{s}^{i}: X_{s}^{i}\times W^{i}\rightarrow \mathbb{R}$ 定义为$\gamma_{s}^{i}(x_{s}^{-i}, w^{i})=\min \limits_{u_{s}^{i}\in X_{s}^{i}}\max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C},\tilde {P}_{sa_{s}k}\in\tilde{P}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})$, 所有局中人稳定策略收益空间的映射函数定义为$\gamma_{x}(w): W \rightarrow W$, 其中$(\gamma_{x}(w))_{is}=\gamma_{s}^{i}(x_{s}^{-i},w^{i})$, 那么网络对抗策略空间$X$ 中的任意对抗策略$x$, 局中人收益映射函数$\gamma_{x}(w)$ 为一个压缩映射.

证明 假设收益空间中的任意收益向量$w$ 和$\theta$, $\beta =\max \limits_{i\in I}\beta_{i}$,其中$\beta_{i}$ 为局中人$i$ 的折扣因素. 那么对于局中人$i\in I$,网络对抗状态$s\in S$,收益向量$w$ 满足:

$\gamma_{s}^{i}(x_{s}^{-i},w^{i})=\psi_{s}^{i}(C_{sa_{s}}^{*i}(x_{s}^{-i},u_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},u_{s}^{*i}),x_{s}^{-i},u_{s}^{*i},w^{i})$ (4)
其中,$u_{s}^{*i}$ 表示网络对抗局中人$i$ 在满足收益向量$w$ 前提下, 使最大收益值最小化的策略. 同样,对于收益向量$\theta$ 满足:
$\gamma_{s}^{i}(x_{s}^{-i},\theta_{s}^{i})=\psi_{s}^{i}(C_{sa_{s}}^{'i}(x_{s}^{-i},z_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i}),x_{s}^{-i},z_{s}^{*i},\theta^{i})$ (5)
其中$ z_{s}^{*i}$ 表示局中人$i$ 在满足收益向量$\theta$ 前提下, 使最大收益值最小化的策略. 式(4) 表明当局中人$i$ 收益向量为 $w^{i}$ 的时候,网络对抗过程中局中人采取策略$u_{s}^{*i}$ 可以使得 $\max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C},\tilde {P}_{sa_{s}k}\in\tilde{P}}\psi_{s}^{i} (\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})$ 取得最小值, 如果采取其它策略$ z_{s}^{*i}$,那么:
$\psi_{s}^{i}(C_{sa_{s}}^{'i}(x_{s}^{-i},z_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i}),x_{s}^{-i},z_{s}^{*i},w^{i})\geq \gamma_{s}^{i}(x_{s}^{-i},w_{s}^{i})$ (6)
同样根据(5) 式得到:
$\psi_{s}^{i}(C_{sa_{s}}^{*i}(x_{s}^{-i},u_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},u_{s}^{*i}),x_{s}^{-i},u_{s}^{*i},\theta^{i})\geq \gamma_{s}^{i}(x_{s}^{-i},\theta_{s}^{i})$ (7)
因此,可以得到:
$\begin{aligned} &\gamma_{s}^{i}(x_{s}^{-i},w_{s}^{i})-\gamma_{s}^{i}(x_{s}^{-i},\theta_{s}^{i})\\ =&\ \psi_{s}^{i}(C_{sa_{s}}^{*i}(x_{s}^{-i},u_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},u_{s}^{*i}),x_{s}^{-i},u_{s}^{*i},w^{i})-\psi_{s}^{i}(C_{sa_{s}}^{'i}(x_{s}^{-i},z_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i}),x_{s}^{-i},z_{s}^{*i},\theta^{i})\\ \leq&\ \psi_{s}^{i}(C_{sa_{s}}^{'i}(x_{s}^{-i},z_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i}),x_{s}^{-i},z_{s}^{*i},w^{i})-\psi_{s}^{i}(C_{sa_{s}}^{'i}(x_{s}^{-i},z_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i}),x_{s}^{-i},z_{s}^{*i},\theta^{i})\\ =&\sum \limits_{a_{s}\in A}\prod \limits_{m=1, m\neq1}^{N}x_{s,a_{s}^{m}}^{m}z_{s}^{*i}\bigg\{C_{sa_{s}}^{'i}(x_{s}^{-i}, z_{s}^{*i}) +\beta_{i}\sum\limits_{k=1}^{M}P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i})w_{k}^{i}\bigg\}-\sum \limits_{a_{s}\in A}\prod \limits_{m=1,m\neq1}^{N}x_{s,a_{s}^{m}}^{m}z_{s}^{*i}\\ &\bigg\{C_{sa_{s}}^{'i}(x_{s}^{-i}, z_{s}^{*i})+\beta_{i}\sum\limits_{k=1}^{M}P_{sa_{s}k}(x_{s}^{-i}, z_{s}^{*i}) \theta_{k}^{i}\bigg\}\leq \sum \limits_{a_{s}\in A}\prod \limits_{m=1,m\neq1}^{N}x_{s,a_{s}^{m}}^{m}z_{s}^{*i} \beta_{i}\sum\limits_{k=1}^{M}P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i}) \\ & (w_{k}^{i}-\theta_{k}^{i}) \leq \sum \limits_{a_{s}\in A}\prod \limits_{m=1, m\neq1}^{N}x_{s,a_{s}^{m}}^{m}z_{s}^{*i}\beta_{i}\sum\limits_{k=1}^{M}P_{sa_{s}k}(x_{s}^{-i}, z_{s}^{*i})\|w_{k}^{i}-\theta_{k}^{i}\|_{\infty}=\beta \|w-\theta\|_{\infty} \end{aligned}$ (8)

与上面证明过程类似,当$x_{s}^{-i}$ 固定的时候,对于任意局中人$i\in I$,网络状态$s\in S$,网络对抗局中人收益映射函数 $\gamma_{s}^{i}$ 满足:

$\begin{aligned} &\gamma_{s}^{i}(x_{s}^{-i},\theta_{s}^{i})-\gamma_{s}^{i}(x_{s}^{-i},w_{s}^{i})\\ =&psi_{s}^{i}(C_{sa_{s}}^{'i}(x_{s}^{-i},z_{s}^{*i}), P_{sa_{s}k}(x_{s}^{-i},z_{s}^{*i}),x_{s}^{-i},z_{s}^{*i}, \theta^{i})- \psi_{s}^{i}(C_{sa_{s}}^{*i}(x_{s}^{-i},u_{s}^{*i}), P_{sa_{s}k}(x_{s}^{-i},u_{s}^{*i}), x_{s}^{-i},u_{s}^{*i},w^{i})\\ \leq&psi_{s}^{i}(C_{sa_{s}}^{*i}(x_{s}^{-i},u_{s}^{*i}),P_{sa_{s}k}(x_{s}^{-i},u_{s}^{*i}),x_{s}^{-i}, u_{s}^{*i},\theta^{i})-\psi_{s}^{i}(C_{sa_{s}}^{*i}(x_{s}^{-i},u_{s}^{*i}), P_{sa_{s}k}(x_{s}^{-i},u_{s}^{*i}),x_{s}^{-i},u_{s}^{*i}, w^{i})\\ \leq&beta \|w-\theta\|_{\infty} \end{aligned}$ (9)

因而得到: $\|\gamma_{x}(w)-\gamma_{x}(\theta)\|_{\infty}\leq \beta \|w-\theta\|_{\infty}$,根据压缩映射定理可知命题1 成立.

命题2 设$w(x)$ 为计算机网络对抗策略$x\in X$ 鲁棒收益向量,那么对于任意对抗策略$x\in X$,满足:

1) 任意局中人$i\in I$,网络状态$s \in S$,存在唯一一个收益值,使得局中人收益向量$w_{s}^{i}(x)=\min \limits_{x_{s}^{i}\in X_{s}^{i}}$\\ $\max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C},\tilde {P}_{sa_{s}k}\in\tilde{P}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k},x_{s},w^{i}(x))$;

2) 网络对抗鲁棒收益向量$w(x)$ 有界.

证明 1) 由于收益值空间$(W,\|\cdot\|_{\infty})$ 是一个完备空间,且根据命题1,局中人收益映射 $\gamma_{x}(w): W \rightarrow W$ 是一个压缩映射. 因此根据Bananch 压缩映射性质知, 映射$\gamma_{x}(w)$ 存在唯一不动点$w$. 也就是说存在唯一向量$w$, 使得$\gamma(w_{x})=w_{x}$. 即,任意局中人$i \in I$,任意网络状态$s \in S$,有$w_{s}^{i}(x)=\min \limits_{x_{s}^{i}\in X_{s}^{i}}\max \limits_{{\tilde{C}_{sa_{s}}}^{i}\in\tilde{C},\tilde {P}_{sa_{s}k}\in\tilde{P}}$$\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\\ \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})$,命题2 性质1 成立.

2) 对于命题2 的第二个性质,用$(\gamma_{x})^{n}$ 来表示$n$ 层嵌套关系$\gamma_{x}(\cdots \gamma_{x}(\gamma_{x}(w))\cdots$, $w_{0})$ 为网络对抗鲁棒博弈问题的任意初始向量, 定义行动序列$w_{n+1}=\gamma_{x}(w_{n})$. 再次使用Banach 压缩映射性质,得到: $\lim \limits_{n\rightarrow {\infty}}(\gamma_{x})^{n}(w_{0})=\lim \limits_{n\rightarrow {\infty}}w_{n}=w_{x}$.

由于$\gamma_{x}(w)$ 是压缩映射,根据命题1 有$\|w_{m}-w_{m-1}\|_{\infty}\leq \beta \|w_{m-1}-w_{m-2}\|_{\infty}\leq \cdots\leq \beta^{m-1}\|w_{1}-w_{0}\|_{\infty}$. 多次利用范数三角不等式得到:

$\begin{aligned} &\|w_{m}-w_{0}\|_{\infty}\leq\|w_{m}-w_{m-1}\|_{\infty}+|w_{m-1}-w_{m-2}\|_{\infty}+\cdots+|w_{1}-w_{0}\|_{\infty} \leq \beta^{m-1} \\ & |w_{1}-w_{0}\|_{\infty}+ \beta^{m-2}|w_{1}-w_{0}\|_{\infty}+\cdots+|w_{1}-w_{0}\|_{\infty}=(\beta^{m-1}+\beta^{m-2}+\cdots+1)|w_{1}- \\ & w_{0}\|_{\infty} \leq \frac{1}{1-\beta}|w_{1}-w_{0}\|_{\infty} \end{aligned}$ (10)

因此,$\lim \limits_{m\rightarrow {\infty}}\|w_{m}-w_{0}\|_{\infty}=\|w_{x}-w_{0}\|_{\infty}\leq \frac{1}{1-\beta}|w_{1}-w_{0}\|_{\infty}$. 并且当$w_{0}=0$ 时, 得到:

$\begin{aligned} &\|w_{1}-w_{0}\|_{\infty}\leq \frac{1}{1-\beta}\max \limits_{i \in I,s \in S}\mid\gamma_{s,x_{s}^{-i}}^{i}(0) \mid=\max \limits_{i \in I,s \in S}\bigg|\min \limits_{x_{s}^{i}\in X_{s}^{i}}\max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}},\tilde{P}_{sa_{s}k}\in {\tilde{P}}}\sum \limits_{m=1,m\neq i}^{N}x_{s,a_{s}^{m}}^{m}u_{s,a_{s}^{i}}^{i}\tilde {C}_{sa_{s}}^{i}\bigg|\\ &=\max \limits_{i \in I,s \in S}\bigg| \sum \limits_{a_{s}\in A}\prod \limits_{m=1,m\neq i}^{N}x_{s,a_{s}^{m}}^{m}x_{s,a_{s}^{m}}^{*i} C_{sa_{s}}^{*i}(x^{-i},x^{*i})\bigg| \leq \max \limits_{i \in I,s \in S} \sum \limits_{a_{s}\in A}\prod \limits_{m=1,m\neq i}^{N}x_{s,a_{s}^{m}}^{m}x_{s,a_{s}^{m}}^{*i}\{\max \limits_{a_{s} \in A_{s}}\\ &\{\sup \limits_{\tilde {C}_{sa_{s}}^{i} \in \tilde{C}}\mid \tilde {C}_{sa_{s}}^{i} \mid \} \}=\max \limits_{i \in I,s \in S} 1 \{\max \limits_{a_{s} \in A}\{\sup \limits_{\tilde {C}_{sa_{s}}^{i} \in \tilde{C}}\mid \tilde {C}_{sa_{s}}^{i} \mid\}\}=\max \limits_{i \in I,s \in S,a_{s} \in A} 1 \sup \limits_{\tilde {C}_{sa_{s}}^{i} \in \tilde{C}}\mid \tilde {C}_{sa_{s}}^{i} \mid \end{aligned}$ (11)
其中$x^{*i}$ 是最优值,由于$\tilde{C}_{sa_{s}}^{i}$ 有界, 所以$\|w_{m}-w_{0}\|$ 也是有界的. 因此,对于任意网络对抗策略$x \in X$,鲁棒收益向量$w(x)$ 都是有界的. 命题2 性质2 成立. 证毕.

命题2是计算机网络对抗行动鲁棒博弈模型一个重要结论. 命题2 性质1 表明: 当局中人收益向量映射函数$\gamma _{s}^{i}(x_{s}^{-i},\cdot)$ 已知时,对于其它局中人固定策略$x_{s}^{-i}$,局中人$i$ 都存在唯一一个鲁棒收益值$w_{s}^{i}$ 与之对应. 这就意味着, 在网络对抗过程中,对于其它局中人任意策略$x^{-i}$ 和一个鲁棒收益向量$w$,在网络每个状态上局中人$i$ 最大期望收益的最小值与收益向量$w$ 保持一致. 命题2 性质2 说明, 对于其它局中人任意固定策略$x_{s}^{-i}$,利用局中人收益映射$\gamma _{x}: W \rightarrow W$ 反复进行迭代$w_{s}^{i}(0)$, 那么局中人收益映射$\gamma _{x}: W \rightarrow W$ 的输出将收敛到收益空间$W$ 上唯一固定点.

第二阶段 首先对计算机网络对抗行动鲁棒博弈模型的性质进行分析, 在此基础上运用Kakutani 不动点定理, 证明网络对抗鲁棒博弈模型存在均衡策略.

性质1 如果对于任意$\varepsilon >0$,存在$\delta (\varepsilon)>0$,使得对于$p,q \in X_{s} \times W^{i}$ 有$d_{1}(p,q) < \delta (\varepsilon)$,那么, 对于任意收益向量$\tilde {C}_{sa_{s}}^{i} \in \tilde{C}$, 网络状态转移概率$\tilde {P}_{sa_{s}k} \in \tilde{P}$, 最优期望收益函数满足: $\mid\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}, w^{i})-\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k}, u_{s},\theta^{i})\mid < \varepsilon$,且为等度连续函数.

证明 为便于表述,令$p=(x_{s},w^{i})$,$q=(u_{s}, w^{i})$,定义以下三个辅助范数算子: $d_{X_{s}}(x_{s},u_{s})= \max\limits_{i \in I} \mid x_{s}^{i}-\\ u_{s}^{i}\mid$, $d_{W^{i}}(w^{i},\theta_{i})= \max\limits_{s \in S} \mid w_{s}^{i}-\theta_{s}^{i}\mid$,$d_{1}(p,q)=d_{X_{s}}(x_{s}, u_{s})+d_{W^{i}}(w^{i},\theta_{i})$.

由于收益值$\tilde {C}_{sa_{s}}^{i} \in \tilde{C}$ 和$\tilde{C}$ 有界,所以对于任意局中人$i\in I$,网络状态$s\in S$,都有$\mid \tilde {C}_{sa_{s}}^{i}\mid \leq K$,其中$0 $\begin{aligned} =&bigg| \sum \limits_{a_{s}\in A}\prod \limits_{m=1}^{N}\tilde{C}_{sa_{s}}^{i}(x_{s,a_{s}^{m}}^{m}-u_{s,a_{s}^{m}}^{m}) +\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\tilde {P}_{sa_{s}k}\bigg( \prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}w_{k}^{i}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\theta_{k}^{i} \bigg)\bigg| \\ \leq&bigg| \sum \limits_{a_{s}\in A}\prod \limits_{m=1}^{N}\tilde{C}_{sa_{s}}^{i}(x_{s,a_{s}^{m}}^{m}-u_{s,a_{s}^{m}}^{m}) \bigg|+\bigg|\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\tilde {P}_{sa_{s}k}w_{k}^{i} \bigg(\prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}w_{k}^{i}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\theta_{k}^{i} \bigg)\bigg| \\ \leq&\ K \sum \limits_{a_{s}\in A}\bigg| \prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}- \prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\bigg|+\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\bigg| \bigg(\prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}w_{k}^{i}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m} \theta_{k}^{i}\bigg)\bigg|\\ \end{aligned}$ (12)

令$\delta_{1}(\varepsilon)=\frac{\min \{\varepsilon, 1\}}{3K(2^{N}-1)\prod_{i=1}^{N}m_{s}^{i}}$, $\delta_{2}(\varepsilon)=\frac{\min \{\varepsilon, 1\}}{3M\beta_{i}\prod_{i=1}^{N}m_{s}^{i}}$, $\delta_{3}(\varepsilon)=\frac{\min \{\varepsilon, 1\}}{3HM\beta_{i}(2^{N}-1)\prod_{i=1}^{N}m_{s}^{i}}$, 并且$\delta(\varepsilon)=\min\{\delta_{1}(\varepsilon),\\ \delta_{2}(\varepsilon),\delta_{3}(\varepsilon)\}$.

根据$d_{1}(p,q)\leq \delta(\varepsilon)$ 可以推导, 对于任意局中人$i\in I$,网络状态$s \in S$ 及对抗策略$a_{s}^{i} \in A$,都有: $x_{s,a_{s}^{m}}^{m}=u_{s,a_{s}^{m}}^{m}+\alpha_{s,a_{s}^{m}}^{m}$, $w_{s}^{i}=\theta_{s}^{i}+\gamma_{s}^{i}$,其中$\mid \alpha_{s,a_{s}^{m}}^{m} \mid < \delta(\varepsilon)$,$\mid \gamma_{s}^{i}\mid < \delta(\varepsilon)$. 利用代数空间性质[17],逐步对性质1 进行证明:

$\begin{aligned} \bigg| \prod \limits_{m=1}^{N}(u_{s,a_{s}^{m}}^{m}+\alpha_{s,a_{s}^{m}}^{m})-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\bigg|= \bigg|\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\bigg(\prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg)\bigg(\prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\bigg)\bigg| \end{aligned}$ (13)
其中$I'=\{1,2,\cdots,N\}/I$,并且根据$\prod \limits_{m \in I}\mid \alpha_{s,a_{s}^{m}}^{m}\mid <(\gamma_{1}(\varepsilon))^{\mid I \mid} \leq \gamma_{1}(\varepsilon)$,可进一步得到:
$\begin{aligned} \bigg| \prod \limits_{m=1}^{N}(u_{s,a_{s}^{m}}^{m}+\alpha_{s,a_{s}^{m}}^{m})-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\bigg| \leq \sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\bigg| \prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg| \bigg| \prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\bigg| \end{aligned}$ (14)
在此基础上,式(12) 的第一项可表达为:
$\begin{aligned} &K \sum \limits_{a_{s}\in A}\bigg| \prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\bigg| \leq K \sum \limits_{a_{s}\in A}\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\bigg| \prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg| \bigg| \prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\bigg| \\ &\leq K \sum \limits_{a_{s}\in A}\sum_{I \subseteq 1,2,\cdots,N, \mid I\mid \geq 1}\bigg| \prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg| < K \sum \limits_{a_{s}\in A}\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\gamma_{1}(\varepsilon)=\frac{\varepsilon}{3} \end{aligned}$ (15)
同样,式(12) 的第二项可表示为:
$\begin{aligned} &\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\bigg| \prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}w_{k}^{i}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\theta_{k}^{i}\bigg|=\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\bigg| \prod \limits_{m=1}^{N}(u_{s,a_{s}^{m}}^{m}+\alpha_{s,a_{s}^{m}}^{m})w_{k}^{i}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\theta_{k}^{i} \bigg|\\ &=\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} \bigg|\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}(w_{k}^{i}-\theta_{k}^{i})+w_{k}^{i}\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\bigg| \end{aligned}$ (16)

根据命题2(2) 可知,网络对抗局中人鲁棒收益值有界, 并且$\prod_{m=1}^{N}u_{s,a_{s}^{m}}^{m}(w_{k}^{i}-\theta_{k}^{i}) \leq \mid \prod_{m=1}^{N}u_{s,a_{s}^{m}}^{m} \mid \mid w_{k}^{i}\\-\theta_{k}^{i}\mid$,$\sum\limits_{I \subseteq 1,2, \cdots,N,\mid I\mid \geq 1}\prod\limits _{m \in I}\alpha_{s,a_{s}^{m}}^{m}\prod\limits _{m \in I'}u_{s,a_{s}^{m}}^{m} \leq \sum\limits_{I \subseteq 1,2,\cdots, N,\mid I\mid \geq 1} \mid \prod_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\mid \mid \prod_{m \in I'}u_{s,a_{s}^{m}}^{m} \mid$,利用范数三角不等式性质,式(16) 满足:

$\begin{aligned} & \beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} \bigg|\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}(w_{k}^{i}-\theta_{k}^{i})+w_{k}^{i} \sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\bigg| \\ & \leq \beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} \bigg| \prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\bigg| |(w_{k}^{i}-\theta_{k}^{i})|+\beta_{i} H \sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\bigg| \prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg| \bigg|\prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\bigg| \end{aligned}$ (17)

又因为$\mid\prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\mid \leq 1$,且$w_{k}^{i}-\theta_{k}^{i}=\gamma _{s}^{i}$,因此式(17) 满足:

$\begin{aligned} &\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} \bigg| \prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\bigg| |(w_{k}^{i}-\theta_{k}^{i})|+\beta_{i} H \sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1}\bigg| \prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg| \bigg|\prod \limits_{m \in I'}u_{s,a_{s}^{m}}^{m}\bigg| \\ &\leq \beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} | \gamma _{s}^{i}|+\beta_{i} H \sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1} \bigg| \prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg| \end{aligned}$ (18)

又因为$\mid\gamma_{s}^{i}\mid < \delta (\varepsilon) \leq \delta_{2} (\varepsilon)$,且$\mid\prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\mid \leq \mid \alpha_{s,a_{s}^{m}}^{m}\mid <\delta(\varepsilon) \leq \delta_{3}(\varepsilon)$,因此式(18) 可表示为:

$\begin{aligned} &\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} \mid \gamma _{s}^{i}\mid+\beta_{i} H \sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} \sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1} \bigg| \prod \limits_{m \in I}\alpha_{s,a_{s}^{m}}^{m}\bigg| \\ & <\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M} \delta_{2}(\varepsilon) + \beta_{i} H \sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\sum_{I \subseteq 1,2,\cdots,N,\mid I\mid \geq 1} \delta_{3}(\varepsilon) =\frac{\varepsilon}{3}+\frac{\varepsilon}{3}=\frac{2\varepsilon}{3} \end{aligned}$ (19)

最后得到:

$\begin{aligned} &\mid\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k},x_{s},w^{i})-\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k},u_{s},\theta^{i})\mid\\ &\leq K \sum \limits_{a_{s}\in A}\bigg| \prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\bigg|+\beta_{i}\sum \limits_{a_{s}\in A}\sum\limits_{k=1}^{M}\bigg| \bigg(\prod \limits_{m=1}^{N}x_{s,a_{s}^{m}}^{m}w_{k}^{i}-\prod \limits_{m=1}^{N}u_{s,a_{s}^{m}}^{m}\theta_{k}^{i}\bigg)\bigg| <\frac{\varepsilon}{3}+\frac{2\varepsilon}{3}=\varepsilon \end{aligned}$ (20)

根据Arzcla-Ascoli定理[18], 推导最优期望收益函数$\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s},w^{i})$ 为等度连续函数,因此,性质1 成立,证毕! 这个性质对于我们证明计算机网络对抗鲁棒博弈模型存在均衡策略很关键, 并且可以推导出网络对抗鲁棒博弈模型的其它性质.

性质2 定义局中人$i$ 最大收益$f_{s}^{i}(x_{s}^{-i}, u_{s}^{i},w^{i})=\max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}},\tilde{P}_{sa_{s}k}\in {\tilde{P}}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})$, 那么对于任意局中人$i \in I$,网络状态$s \in S$,局中人$i$ 最大收益函数$f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i})$ 是连续的.

证明 根据局中人$i$ 最大收益函数$f_{s}^{i}(x_{s}^{-i}, u_{s}^{i},w^{i})=\max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}},\tilde{P}_{sa_{s}k}\in {\tilde{P}}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})$ 的定义, 令函数最大值$\max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}}, \tilde{P}_{sa_{s}k}\in {\tilde{P}}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})=a$, $p=(x_{s}^{-i},u_{s}^{i},w^{i})$,$q=(y_{s}^{-i},z_{s}^{i}, \theta^{i})$,根据性质1 可知: 任意$\varepsilon >0$, 如果存在$\delta (\varepsilon) >0$,使得对于任意$p,q \in X_{s}\times W^{i}$ 有$d_{1}(p,q) <\delta(\varepsilon)$,那么, 对于任意收益值$\tilde{C}_{sa_{s}}^{i}\in \tilde{C}$, 任意网络状态转移概率$\tilde{P}_{sa_{s}k}\in {\tilde{P}}$,都满足: $\mid \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k}, x_{s}^{-i},u_{s}^{i},w^{i})-\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},y_{s}^{-i},z_{s}^{i},\theta^{i}) \mid < \varepsilon$.

因而,对于任意收益值$\tilde{C}_{sa_{s}}^{i}\in \tilde{C}$,任意网络状态转移概率$\tilde{P}_{sa_{s}k}\in {\tilde{P}}$,都满足: $ \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k},y_{s}^{-i},z_{s}^{i},\theta^{i}) \\ \leq \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k}, x_{s}^{-i},u_{s}^{i},w^{i})+ \varepsilon \leq a+\varepsilon $. 也就说,对于任意收益值$\tilde{C}_{sa_{s}}^{i}\in \tilde{C}$, 任意网络状态转移概率$\tilde{P}_{sa_{s}k}\in {\tilde{P}}$, 满足$\max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}}, \tilde{P}_{sa_{s}k}\in {\tilde{P}}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i}) \leq a+\varepsilon$.

一方面,选取收益值$\tilde{C}_{sa_{s}}^{0}\in {\tilde{C}}$, 状态转移概率值$\tilde{P}_{sa_{s}k}^{0}\in {\tilde{P}}$, 使得$\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{0},\tilde{P}_{sa_{s}k}^{0}, x_{s}^{-i},u_{s}^{i},w^{i})\geq a-\varepsilon /2$. 另一方面, 由于$d_{1}(p,q) < \delta (\varepsilon)$,根据性质1 可知: $\mid \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{0},\tilde{P}_{sa_{s}k}^{0},y_{s}^{-i},z_{s}^{i},\theta^{i}) -\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{0},\tilde{P}_{sa_{s}k}^{0},x_{s}^{-i},u_{s}^{i},w^{i})\mid < \varepsilon$, 因此,可以进一步得到:

$\begin{aligned} &\max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}},\tilde{P}_{sa_{s}k}\in {\tilde{P}}} \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k},y_{s}^{-i},z_{s}^{i},\theta^{i})\\ &\geq \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{0},\tilde{P}_{sa_{s}k}^{0},y_{s}^{-i},z_{s}^{i},\theta^{i}) \geq \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{0},\tilde{P}_{sa_{s}k}^{0},x_{s}^{-i},u_{s}^{i},w^{i}) - \varepsilon \geq (a- \varepsilon/2)- \varepsilon/2 \geq a-3\varepsilon/2 \end{aligned}$ (21)

综上可以得到,对于任意$\varepsilon >0$,如果存在$\delta (\varepsilon)$ 使得$d_{p,q} < \delta (\varepsilon)$ 存在,那么:

$\begin{aligned} a-2\varepsilon \leq a-3\varepsilon/2 \leq \max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}},\tilde{P}_{sa_{s}k}\in {\tilde{P}}} \psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i},\tilde{P}_{sa_{s}k},y_{s}^{-i},z_{s}^{i},\theta^{i}) \leq a+\varepsilon \leq a+2\varepsilon \end{aligned}$ (22)

因此,网络对抗局中人$i$ 最大收益函数$f_{s}^{i}(x_{s}^{-i}, u_{s}^{i},w^{i})$ 是连续的,证毕.

性质3 在计算机网络对抗过程中, 固定其它局中人策略$x_{s}^{-i}$,那么局中人$i$ 最大收益函数$f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i})$ 是关于对抗策略$u_{s}^{i}$ 的凸面.

证明 设$y_{s}^{i}$,$z_{s}^{i}$ 为局中人$i$ 在网络状态$s$ 时行动集合中的元素,对于任意$\lambda \in [0,1]$, 满足:

$\begin{aligned} &f_{s}^{i}(x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i}),w^{i})=\sum \limits_{a_{s} \in A}\prod \limits_{m=1,m\neq1}^{N}x_{s,a_{s}^{m}}^{m}(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i})\\ &\qquad\qquad \times \bigg\{\tilde{C}_{sa_{s}}^{*i}(x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i}))+\beta_{i}\sum\limits_{k=1}^{M}\tilde {P}_{sa_{s}k}^{*}x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i})w^{i}\bigg\} \end{aligned}$ (23)
其中$C_{sa_{s}}^{*i}$ 为最优收益值,$P_{sa_{s}k}^{*}$ 为网络最优状态转移概率矩阵,其具体取值与$(x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i}))$ 有关,进一步得到:
$\begin{aligned} &f_{s}^{i}(x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i}),w^{i})=\lambda \sum \limits_{a_{s} \in A}\prod \limits_{m=1,m\neq1}^{N}x_{s,a_{s}^{m}}^{m}y_{s,a_{s}^{i}}^{i}\bigg\{C_{sa_{s}}^{*i}(x_{s}^{-i}, (\lambda y_{s}^{i}+ \\ &(1-\lambda)z_{s}^{i}))+\beta \sum\limits_{k=1}^{M}P_{sa_{s}k}^{*} (x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i}))w^{i}\bigg\}+(1-\lambda) \sum \limits_{a_{s} \in A}\prod \limits_{m=1,m\neq1}^{N}x_{s,a_{s}^{m}}^{m}z_{s,a_{s}^{i}}^{i} \\ & \bigg\{C_{sa_{s}}^{*i}(x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i}))+ \\ &\beta \sum\limits_{k=1}^{M}P_{sa_{s}k}^{*}(x_{s}^{-i},(\lambda y_{s}^{i}+(1-\lambda)z_{s}^{i}))w^{i}\bigg\} \leq \lambda \sum \limits_{a_{s} \in A}\prod \limits_{m=1, m\neq1}^{N}x_{s,a_{s}^{m}}^{m}y_{s,a_{s}^{i}}^{i}\bigg\{ C_{sa_{s}}^{*i}(x_{s}^{-i},y_{s}^{i})+\\ &\beta \sum\limits_{k=1}^{M}P_{sa_{s}k}^{*}(x_{s}^{-i}, y_{s}^{i})w^{i}\bigg\}+(1-\lambda)\sum \limits_{a_{s} \in A}\prod \limits_{m=1, m\neq1}^{N}x_{s,a_{s}^{m}}^{m}z_{s,a_{s}^{i}}^{i}\bigg\{ C_{sa_{s}}^{*i}(x_{s}^{-i},z_{s}^{i})+ \\ & \beta \sum\limits_{k=1}^{M}P_{sa_{s}k}^{*}(x_{s}^{-i},z_{s}^{i})w^{i}\bigg\} =\lambda f_{s}^{i}(x_{s}^{-i},y_{s}^{i},w^{i})+(1-\lambda) f_{s}^{i}(x_{s}^{-i},z_{s}^{i},w^{i}) \end{aligned}$ (24)

因此,局中人$i$ 最大收益函数$f_{s}^{i}(x_{s}^{-i},u_{s}^{i}, w^{i})$ 是关于对抗策略$u_{s}^{i}$ 的凸面. 证毕.

性质4 网络对抗局中人$i$ 稳定策略收益向量的映射函数$\gamma_{s}^{i}(x_{s}^{-i},w^{i})$ 关于其它局中人策略$x_{s}^{-i}$ 连续, 并且集合\{$\gamma_{s}^{i}(\cdot,w^{i})\mid w^{i}$ 有界\}是同等连续. 证明 定义局中人收益空间极值映射$\gamma_{s}^{i}(x_{s}^{-i}, w^{i})=\psi_{i}^{s}(C_{s}^{i}(x_{s}^{-i},u_{s}^{*i}), P_{s}(x_{s}^{-i},u_{s}^{*i},w^{i}),x_{s}^{-i},u_{s}^{*i}, w^{i})$ 和$\gamma_{s}^{i}(y_{s}^{-i},\\ w^{i})=\psi_{i}^{s}(C_{s}^{i}(y_{s}^{-i},z_{s}^{*i}), P_{s}(y_{s}^{-i},z_{s}^{*i},w^{i}),y_{s}^{-i},z_{s}^{*i}, w^{i})$,根据式(6) 和式(7),进一步得到:

\begin{aligned} \gamma_{s}^{i}(y_{s}^{-i},w^{i})-\gamma_{s}^{i}(x_{s}^{-i}, w^{i}) \leq&\ \psi_{i}^{s}(C_{s}^{i}(y_{s}^{-i},u_{s}^{*i}),P_{s}(y_{s}^{-i},u_{s}^{*i},w^{i}),y_{s}^{-i},u_{s}^{*i},w^{i})\\ &\ -\psi_{i}^{s}(C_{s}^{i}(x_{s}^{-i},u_{s}^{*i}), P_{s}(x_{s}^{-i},u_{s}^{*i},w^{i}),x_{s}^{-i},u_{s}^{*i},w^{i}) \end{aligned} (25)
$\begin{aligned} \gamma_{s}^{i}(x_{s}^{-i},w^{i})-\gamma_{s}^{i}(y_{s}^{-i}, w^{i}) \leq&psi_{i}^{s}(C_{s}^{i}(x_{s}^{-i},z_{s}^{*i}), P_{s}(x_{s}^{-i},z_{s}^{*i},w^{i}),x_{s}^{-i},z_{s}^{*i}, w^{i})\\ &\ -\psi_{i}^{s}(C_{s}^{i}(y_{s}^{-i},z_{s}^{*i}), P_{s}(y_{s}^{-i},z_{s}^{*i},w^{i}),y_{s}^{-i},z_{s}^{*i},w^{i}) \end{aligned}$$ (26)

根据性质1,可知最优期望收益映射函数$\psi_{i}^{s}$ 在有界集合$w^{i}$ 上是一致连续的,所以式(25) 和(26) 的右边等式都可以足够小. 因此, 局中人收益映射$\gamma_{s}^{i}(x_{s}^{-i},w^{i})$ 关于其它局中人策略$x_{s}^{-i}$ 连续. 证毕.

当其它局中人策略$x_{s}^{-i}$ 固定时,局中人$i$ 最优策略的收益值函数可以定义为: $\tau^{i}(x_{s}^{-i})=\{w^{i}=(w_{1}^{i},\cdots,\\ w_{m}^{i}) \mid w_{s}^{i}=\min \limits_{x_{s}^{i} \in X_{s}^{i}}\max \limits_{\tilde{C}_{sa_{s}}^{i}\in {\tilde{C}}, \tilde{P}_{sa_{s}k}\in {\tilde{P}}}\psi_{s}^{i}(\tilde{C}_{sa_{s}}^{i}, \tilde{P}_{sa_{s}k},x_{s}^{-i},u_{s}^{i},w^{i})\}$, 并且用$\tau_{s}^{i}(x_{s}^{-i})$ 表示$\tau^{i}(x_{s}^{-i})$ 的第$s$ 个元素. 在此基础上,可以得到性质5.

性质5 如果网络对抗策略序列$x_{s}^{-i,n}$ 和局中人$i$ 收益函数序列$\tau_{s}^{i}(x_{s}^{-i,n})$ 的极限值满足: $\lim \limits_{ n \rightarrow \infty} x^{-i,n} = x^{-i}$,$\lim \limits_{ n \rightarrow \infty} \tau_{s}^{i}(x^{-i,n}) = w_{s}^{i}$,那么,局中人$i$ 收益函数满足$\tau_{s}^{i}(x_{s}^{-i})= w_{s}^{i}$.

证明 由于

$\begin{aligned} \mid w_{s}^{i}-\gamma_{s}^{i}(x_{s}^{-i},w^{i})\mid \leq \mid w_{s}^{i}-\tau_{s}^{i}(x_{s}^{-i,n})\mid + \mid \tau_{s}^{i}(x_{s}^{-i,n})- \gamma_{s}^{i}(x_{s}^{-i},\tau_{s}^{i}(x_{s}^{-i,n})) \mid \\ +\mid \gamma_{s}^{i}(x_{s}^{-i},\tau_{s}^{i}(x_{s}^{-i,n}))-\gamma_{s}^{i}(x_{s}^{-i},w^{i})\mid \end{aligned}$ (27)

一方面,根据已知条件可以得到序列的极限值满足: $\lim \limits_{ n \rightarrow \infty} \mid w_{s}^{i}-\tau_{s}^{i}(x_{s}^{-i,n})\mid =0$,$\lim \limits_{ n \rightarrow \infty} \mid \gamma_{s}^{i}(x_{s}^{-i}, \tau_{s}^{i}(x_{s}^{-i,n}))-\gamma_{s}^{i}(x_{s}^{-i},w^{i})\mid = 0$,另一方面,根据性质4 可以得到序列的极限值满足: $\lim \limits_{ n \rightarrow \infty} \mid \tau_{s}^{i}(x_{s}^{-i,n})- \gamma_{s}^{i}(x_{s}^{-i},\tau_{s}^{i}(x_{s}^{-i,n})) \mid =\lim \limits_{ n \rightarrow \infty} \mid \gamma_{s}^{i}(x_{s}^{-i,n}, \tau_{s}^{i}(x_{s}^{-i,n}))- \gamma_{s}^{i}(x_{s}^{-i}, \tau_{s}^{i}(x_{s}^{-i,n})) \mid=0$.

因此,可以得到$\lim \limits_{ n \rightarrow \infty} \mid w_{s}^{i}-\gamma_{s}^{i}(x_{s}^{-i},w^{i})\mid =0$. 证毕.

命题3 对于不完全信息计算机网络对抗问题的鲁棒马尔可夫博弈模型, 如果不确定转移概率和收益值集合为一个紧集, 并且所有局中人只有有限个行动,那么, 该计算机网络对抗问题存在一个均衡策略.

证明 命题3 的证明过程等价于证明计算机网络局中人策略空间映射$\phi: X \rightarrow 2^{X}$ 存在不动点$x$,使得$\phi(x)=x$. 为此, 按以下三个步骤对命题进行证明.

首先,根据模型性质2 可知,$f_{s}^{i}(x_{s}^{-i},u_{s}^{i}, w^{i})$ 是关于转移概率和收益值的连续函数. 由于连续函数在紧集上存在最小值,因此$\arg\min\limits_{u_{s}^{i} \in \Delta}f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i})\neq \emptyset$. 进而根据命题2,可知等式$w_{s}^{i}=\min\limits_{u_{s}^{i} \in \Delta}f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i})$ 成立, 因此$\phi(x)\neq \emptyset$. 即,对于任意对抗策略$x \in X$, 策略空间映射满足$\phi(x) \subseteq X$.

其次,我们将证明策略空间$\phi(x)$ 为凸集. 一方面,假设向量$(z^{1}, \cdots,z^{N})$ 和向量$(v^{1},\cdots,v^{N})$ 都属于策略空间$\phi(x^{1},\cdots,x^{N})$,那么对于任意局中人$i \in I$,网络状态$s \in S$,网络对抗策略$u_{s}^{i}$, 满足$f_{s}^{i}(x_{s}^{-i},z_{s}^{i},w^{i}) =f_{s}^{i}(x_{s}^{-i},v_{s}^{i},w^{i}) \leq f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i})$. 进而,对于任意局中人$i \in I$,网络状态$s \in S$,$\lambda \in [0,1]$, 都有$w_{s}^{i}=\lambda f_{s}^{i}(x_{s}^{-i},z_{s}^{i},w^{i})+ (1-\lambda)f_{s}^{i}(x_{s}^{-i},v_{s}^{i},w^{i}) \leq f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i})$. 另一方面, 由于局中人最大收益映射函数$f_{s}^{i}(x_{s}^{-i},u_{s}^{i},\\ w^{i})$ 是凸的,得到:

$\begin{aligned} f_{s}^{i}(x_{s}^{i},(\lambda z_{s}^{i}+ (1-\lambda)v_{s}^{i}),w^{i}) \leq \lambda f_{s}^{i}(x_{s}^{-i},z_{s}^{i},w^{i})+ (1-\lambda)f_{s}^{i}(x_{s}^{-i},v_{s}^{i},w^{i}) \leq f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i}) \end{aligned}$ (28)

因此,可以得到$\lambda (z^{1},\cdots,z^{N}) + (1-\lambda)(v^{1}, \cdots,v^{N}) \in \phi(x^{1},\cdots,x^{N}) $. 即, 网络对抗局中人策略空间映射$\phi(x)$ 为凸集.

最后,证明策略空间映射$\phi(x)$ 是上半连续的. 为此,假设$\lim \limits_{n \rightarrow \infty}x_{n}=x$,$\lim \limits_{n \rightarrow \infty}y_{n}=y$ 且$y_{n} = \phi(x_{n})$, 进而可以得到$\lim \limits_{n \rightarrow \infty}\tau_{s}^{i}(x_{s}^{-i,n}) = w_{s}^{i}$. 对于任意局中人$i \in I$,网络任意状态$s \in S$,运用三角不等式,可以得到:

$\begin{aligned} &\lim \limits_{n \rightarrow \infty}\mid f_{s}^{i}(x_{s}^{-i},y_{s}^{i},w^{i})-w_{s}^{i}\mid \leq \lim \limits_{n \rightarrow \infty}\mid f_{s}^{i}(x_{s}^{-i},y_{s}^{i},w^{i})- f_{s}^{i}(x_{s}^{-i,n},y_{s}^{i,n},\tau_{s}^{i}(x_{s}^{-i,n}))\mid +\\ & \lim \limits_{n \rightarrow \infty}\mid f_{s}^{i}(x_{s}^{-i,n},y_{s}^{i,n}, \tau_{s}^{i}(x_{s}^{-i,n}))- w_{s}^{i} \mid = \lim \limits_{n \rightarrow \infty}\mid f_{s}^{i}(x_{s}^{-i},y_{s}^{i},w^{i})- f_{s}^{i}(x_{s}^{-i,n},y_{s}^{i,n},\tau_{s}^{i}(x_{s}^{-i,n}))\mid+\\ & \lim \limits_{n \rightarrow \infty}\mid \tau_{s}^{i}(x_{s}^{-i,n})- w_{s}^{i} \mid=0 \end{aligned}$ (29)

因而,$w_{s}^{i}=f_{s}^{i}(x_{s}^{-i},y_{s}^{i},w^{i})$. 根据模型性质5,可以得到$\tau_{s}^{i}(x^{-i})=w^{i}$. 进一步得到:

$\begin{aligned} w_{s}^{i}=f_{s}^{i}(x_{s}^{-i},y_{s}^{i},w^{i})=\tau_{s}^{i}(x^{-i})=\min \limits_{u_{s}^{i} \in \Delta}f_{s}^{i}(x_{s}^{-i},u_{s}^{i},w^{i}) \end{aligned}$ (30)

即$y\in \phi(x)$,这就证明了计算机网络局中人策略空间映射$\phi(x)$ 是上半连续的. 综上可以得到: 策略空间映射$\phi(x)$ 是一个闭集, 并且对于局中人所有策略$x$ 都是上半连续,根据Kakutani 不动点定理, 可知存在不动点$x$,使得$\phi(x)=x$. 即, 计算机网络对抗行动鲁棒模型存在均衡策略,证毕.

命题1和命题2说明在计算机网络对抗过程中, 攻防双方的最优响应策略是一个压缩映射, 并且对于任意对抗策略,存在唯一一个鲁棒性收益向量与之对应. 性质1$\sim$性质5 说明如果不确定转移概率和收益值集合为一个紧集, 并且只有有限个行动策略, 那么攻防双方的收益函数为等度、连续凸函数,并且双方存在均衡策略. 网络对抗行动鲁棒模型的三个命题、五个性质之间的相互关系如图 1所示, 这些性质不仅说明计算机网络对抗鲁棒博弈模型是严谨的、科学的, 而且可以帮助指挥员对不完全信息条件下网络对抗的均衡策略、对抗结果有更加深刻的理解.

图 1 网络对抗行动鲁棒博弈模型各性质之间的相互关系
3 算例应用与分析

以某网络服务器为研究对象,将网络对抗过程划分为两个状态$S$=\{服务器完好状态$s_{1}$, 服务器损坏状态$s_{2}$\},在$s_{1}$状态, 攻击者行动策略为$a_{1}$=\{破解文件服务器密码$a_{11}$, 植入拒绝服务病毒$a_{12}$\}, 防御者行动策略为$d_{1}$=\{删除有威胁用户$d_{11}$, 安装反嗅探装置$d_{12}$\}. 在$s_{2}$状态, 攻击者行动策略为$a_{2}$=\{窃取文件服务器数据$a_{21}$\}, 防御者行动策略为$d_{2}$=\{移除嗅探装置$d_{21}$\},如图 2所示. 具体来说,网络状态转移概率为:\vspace{1mm} $\tilde{P}_{11}=\begin{bmatrix} [0.4,0.8] & [0.2,0.5] \\ 1 & 1 \end{bmatrix}$,$\tilde{P}_{12}$=$\begin{bmatrix} [0.3,0.7] & [0.4,0.7] \\ 0 & 0 \end{bmatrix}$,$P_{21}=[0.5]$,$P_{22}=[0.5]$, 在各个网络状态上对抗策略的收益值分别为: $C_{1}=\begin{bmatrix} 4 & 6 \\ 7 & 3 \end{bmatrix}$,$C_{2}=[2]$.

图 2 不完全信息网络对抗过程描述及转化

在此已知条件下,本文的目标是制定一个鲁棒性攻防策略, 以应对未来网络对抗过程中的不确定性. 为此,首先运 用凸准则对不确定参数进行处理,将其转化为含参数的确定性问题, 如图 2(b)所示. 然后运用文献[1]方法对问题进行求解,具体如下:

目标函数为: minimize\quad $\{v_{1}-(4a_{11}d_{11}+6a_{11}d_{12}+7a_{12}d_{11}+3a_{12}d_{12})-[(0.4-0.4 \lambda_{1})a_{11}d_{11}+(0.5-0.3 \lambda_{2})a_{11}d_{12}+ \\ a_{12}d_{11}+a_{12}d_{12}]v_{1}- [(0.7-0.4 \lambda_{3})a_{11}d_{11}+(0.7-0.3 \lambda_{4})a_{11}d_{12}]v_{2}\} +(v_{2}-2a_{21}d_{21}-0.5a_{21}d_{21}v_{1} \\ -0.5a_{21}d_{21}v_{2})$

约束条件为: $v_{1}-4(d_{11}+6d_{12})-[(0.4-0.4\lambda_{1})d_{11}+(0.5-0.3\lambda_{2})d_{12}]v_{1} -[(0.7-0.4\lambda_{3})d_{11}+ \\ (0.7-0.3\lambda_{4})d_{12}]v_{2} \geq 0$ $v_{1}-(7d_{11}+3d_{12})-(d_{11}+d_{12})v_{1} \geq 0$ $v_{2}-2d_{21}-0.5v_{1}d_{11}-0.5v_{2}d_{12} \geq 0$ $(0.4-0.4 \lambda_{1})+(0.7-0.4 \lambda_{3})=1$ $(0.5-0.3 \lambda_{2})+(0.7-0.3 \lambda_{4})=1$ $a_{11}+a_{12}=1$ $d_{11}+d_{12}=1$ $d_{21}=1$ $0 \leq \lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4}\leq 1$

对以上非线性规划问题求解得到攻防双方在各个阶段的鲁棒均衡策略,如表 2所示. 同理,运用文献[19]中悲观准则、乐观准则对不完全信息网络对抗问题进行转化,如图 2(c)、2(d)所示. 通过表 2数据可以发现,采取悲观准则、乐观准则可能在某一个网络状态获得更大收益,但是网络对抗总收益值不如凸准则处理方法. 这是因为悲观准则和乐观准则虽然操作比较简单,但是在转化过程中没有从全局角度进行优化,且参数转化过程随机性比较大. 而凸准则方法是用不确定参数上、下限的凸组合来处理不确定变量,并将其纳入到整个优化过程. 因此,采用凸准则对问题进行求解,可以更好地应对计算机网络对抗中的不确定性.

表 2 网络攻防双方的最优策略及收益值
4 结束语 本章将博弈论和鲁棒性优化理论相结合,建立了不完全信息条件下计算机网络对抗鲁棒博弈模型,主要工作包括:

1) 分析不完全信息计算机网络对抗问题的特点, 并运用区间数来表示网络状态的转移概率, 在此基础上建立网络对抗鲁棒博弈模型. 与海萨尼提出的贝叶斯博弈模型不同, 鲁棒博弈模型不需要给出不确定参数的概率分布, 只需要知道参数的变化区间.

2) 当不确定转移概率集合为紧集, 且所有局中人只有有限个行动策略的时候, 运用凸分析理论对计算机网络对抗鲁棒博弈模型进行分析, 得到网络攻防双方的收益函数为等度、连续凸函数, 攻防双方存在均衡策略且为一个压缩映射.

3) 通过算例计算,得到攻防双方的均衡策略, 并对凸准则、悲观准则和乐观准则的求解效果进行对比, 验证了本文模型的有效性.

需要指出的是, 本文将整个网络攻防双方的动态交互过程视为一个马尔可夫决策过程, 并假设网络状态转移概率和收益值为不确定值, 攻防行动策略集合固定不变, 在此情况求解得到了攻防双方在网络各个阶段所采用的最优策略. 对于各网络状态下攻防双方的动态交互关系, 可以借鉴文献[23, 24, 25]研究方法, 考虑攻防双方的行动强度、行动时机等多种因素, 这是笔者下一步需要解决的问题.

参考文献
[1] 王长春, 程晓航, 朱永文,等. 计算机网络对抗行动策略的Markov博弈模型[J]. 系统工程理论与实践, 2014, 34(9): 2402-2410.Wang Changchun, Cheng Xiaohang, Zhu Yongwen, et al. A Markov game model of computer network operation[J]. Systems Engineering —— Theory & Practice, 2014, 34(9): 2402-2410.
[2] 贾春福, 钟安鸣, 张炜. 网络安全不完全信息动态博弈模型 [J]. 计算机研究与发展, 2006, 43(2): 530-533.Jia Chunfu, Zhong Anming, Zhang Wei. Incomplete informational and dynamic game model in network security[J]. Journal of Complex Research and Development, 2006, 43(2): 530-533.
[3] 姜伟, 方滨兴, 田志宏. 基于攻防随机博弈模型的网络安全测评和最优主动防御 [J]. 计算机学报, 2009, 32(4): 817-827.Jiang Wei, Fang Binxing, Tian Zhihong. Evaluating network security and optimal active defense based on attack defense game model[J]. Chinese Journal of Computers, 2009, 32(4): 817-827.
[4] 吴广谋, 吕周洋. 博弈论基础与应用 [M]. 南京: 东南大学出版社, 2009.Wu Guangmou, Lü Zhouyang. Induction and application of game theory[M]. Nanjing: Southeast University Press, 2009.
[5] Mertens J, Zamir S. Formulation of Bayeisan analysis for games with incomplete information[J]. International of Game Theory, 1985, 14(1): 1-29.
[6] Dow J, Werlang S. Nash equilibrium under Knightian uncertainty: Breaking down backward induction[J]. Journal Economic Theory, 1994, 64: 305-324.
[7] Marinacci M. Ambiguous game[J]. Game and Economic Behavior, 2000, 31(2): 191-219.
[8] Aghassi M, Bertsimas D. Robust game theory[J]. Mathematical Programming, 2006, 107: 231-273.
[9] Nishimura R, Hayashi S, Fukushima M. Robust Nash in N-person non-cooperative game: Uniqueness and reformulation[J]. Pacific Journal of Optimization, 2009, 5: 237-259.
[10] Nishimura R, Hayashi S, Fukushima M. Semi definite complementarity reformulation for robust Nash equilibrium problems with euclidean uncertainty sets[J]. Journal of Global Optimization, 2011, 53(1): 107-120.
[11] Pita J, Jain M, Tambe F. Robust solution to Stackelberg games: Addressing bounded rationality and limited observations in human cognition[J]. Artificial Intelligence, 2010, 174(15): 1142-1171.
[12] Jiang C, Han X, Liu G. The optimization of the variable binder force in U-shaped forming with uncertain friction coefficient[J]. Journal of Materials Processing Technology, 2007, 182(3): 262-267.
[13] Inuiguchi M, Sakawa M. Minimax regret solution to linear programming problems with an interval objective function[J]. European Journal of Operation Research, 1995, 150(86): 526-536.
[14] Averbakh I, Lebedev V. On the complexity of minmax regret linear programming[J]. European Journal of Operational Research, 2005, 160(1): 227-231.
[15] Kao C. Interval efficiency measures in data envelopment analysis with imprecise data[J]. European Journal of Operational Research, 2006, 174(2): 1087-1099.
[16] 胡奇英, 刘建庸. 马尔可夫决策过程引论 [M]. 西安: 西安电子科技大学出版社, 2000.Hu Qiying, Liu Jianyong. Introduction of Markov decision process[M]. Xi'an: Xi'an University of Electronic Technology Press, 2000.
[17] 俞建. 博弈论与非线性分析[M]. 北京: 科学出版社, 2008.Yu Jian. Game and nonlinear analysis[M]. Beijing: Science Press, 2008.
[18] 史树中. 凸性 [M]. 大连: 大连理工大学出版社, 2011.Shi Shuzhong. Convex theory[M]. Dalian: Dalian University of Technology Press, 2011.
[19] Givan R, Leach S, Dean T. Bounded parameter Markov decision processes[J]. Artificial Intelligence, 2000, 122: 71-109.
[20] Zhu H J, Du S G, Gao Z Y, et al. A probabilistic misbehavior detection scheme toward efficient trust establishment in delay-tolerant networks[J]. IEEE Transactions on Parallel and Distribution System, 2014, 25(1): 22-32.
[21] Aksen D, Akca S S, Aras N. A bilevel partial interdiction problem with capacitated facilities and demand outsourcing[J]. Computers & Operation Research, 2014, 41: 346-358.
[22] Zhu Q Y, Alpcan T, Bacsar T. Game theory meets network security and privacy[J]. ACM Computer Surveys, 2013, 45(3): 251-292.
[23] Gao X, Zhong W J, Mei S. A game-theory approach to configuration of detection software with decision errors[J]. Reliability Engineering & System Safety, 2013, 119: 35-43.
[24] Lelarge M. Coordination in network security games: A monotone comparative statics approach[J]. IEEE Journal on Selected Areas in Communications, 2013, 30(11): 2210-2219.
[25] Stefan R. On game-theoretic network security provisioning[J]. Journal of Network and Systems Management, 2013, 21(1): 47-64.
0

文章信息

王长春, 汤锦辉, 朱永文, 程晓航
WANG Chang-chun, TANG Jin-hui, ZHU Yong-wen, CHENG Xiao-hang
不完全信息条件下计算机网络对抗行动鲁棒博弈模型
Robust game model of computer network operation with incomplete information
系统工程理论与实践, 2015, 35(2): 481-492
Systems Engineering - Theory & practice, 2015, 35(2): 481-492.

文章历史

收稿日期:2013-06-06

相关文章

工作空间