《安全通论》(5)——攻防篇之“非盲对抗”之“劝酒令”

杨义先，钮心忻

(北京邮电大学 信息安全中心，北京 100876)



《安全通论》(5)
——攻防篇之“非盲对抗”之“劝酒令”

杨义先，钮心忻

(北京邮电大学 信息安全中心，北京 100876)

编者按：网络空间安全的本质就是攻防对抗。“安全对抗”又分为两大类：盲对抗和非盲对抗。在本系列之二《安全通论》(2)——攻防篇之盲对抗中，对 “盲对抗”已经有所介绍，并给出了黑客(红客)攻击(防守)能力的精确极限，针对“非盲对抗”，文章继续引用经典游戏来进行分析。在该文中，酒友们在宴会上常玩的“猜拳”和“划拳”等劝酒令，也成了《安全通论》的研究内容，仍然采用统一的“信道容量方法”，给出了“赢酒杯数”和“罚酒杯数”的理论极限，还给出了醉鬼获胜的调整技巧。当然，这些内容也是《安全通论》不可或缺的组成部分。文章还针对所有“输赢规则线性可分”的“非盲对抗”，给出了统一的解决方案。为与本刊风格一致，我们对文字略作了一些微调。阅读原文可登录科学网原文网络链接地址：http://blog.sciencenet.cn/blog-453322-950146.html。

杨义先

教授，博士生导师，灾备技术国家工程实验室主任，北京邮电大学信息安全中心主任，教育部网络攻防重点实验室主任，《微型机与应用》编委，主要研究方向：网络空间安全、现代密码学和纠错编码等。

钮心忻

博士，教授，博士生导师。北京邮电大学学士和硕士学位，香港中文大学电子工程系博士学位。1997年起在北京邮电大学信息工程学院(现计算机学院)从事教学与科研工作。主要研究方向：网络与信息安全、信号与信息处理等。

0 引言

以网络空间安全、经济安全、领土安全等为代表的所有安全问题的核心就是“对抗”！所以，无论花多少篇幅，都必须把它研究透彻，至少是要尽可能透彻。哪怕是多次变换角度，甚至利用古老游戏和时髦娱乐项目，来全面深入地研究安全对抗问题，都是值得的。

“安全经络”是《安全通论》的第一块基石，文献[1]已经打好了这块基石。

“安全对抗”是《安全通论》的第二块基石。“安全对抗”分为两大类：盲对抗、非盲对抗。为了打好这第二块基石，我们已经在文献[2]中，统一研究了“盲对抗”，并给出了黑客(红客)攻击(防守)能力的精确极限。针对“非盲对抗”，虽然已经找到了统一的研究方法(信道容量法)，但是，由于“非盲对抗”的模型千变万化，我们只好“见招拆招”。比如，分别在文献[3]和[4]中，以“石头剪刀布游戏”、“猜正反面游戏”和“手心手背游戏”为对象，研究了“非盲对抗”的三个有趣实例，给出了输赢极限和获胜技巧。本文对酒桌上著名的两个实例(划拳、猜拳)进行分析，仍然采用统一的“信道容量方法”，给出了“赢酒杯数”和“罚酒杯数”的理论极限，还给出了醉鬼获胜的调整技巧。当然，这些内容也是《安全通论》不可或缺的组成部分。此外，针对“非盲对抗”的很大一个子类(输赢规则线性可分的情况)，我们给出了统一的解决方案。

1 “猜拳”赢酒

“猜拳”是宴会上主人和客人闹酒的游戏形式之一。其游戏规则是：在每个回合中，主人和客人同时独立亮出如下4种手势之一：虫子、公鸡、老虎、棒子，然后，双方共同根据如下“胜负判定规则”来决定该罚谁喝一杯酒：

“虫子”被“公鸡”吃掉；“公鸡”被“老虎”吃掉；“老虎”被“棒子”打死；“棒子”被“虫子”蛀断。

除此之外，主客双方如果平局，则互不罚酒。

一个回合结束后，主客双方再进行下一回合的“猜拳”。

将此“猜拳游戏”用数学方式表示出来便是：设主人和客人分别用随机变量X和Y来表示，它们的可能取值有4个：0，1，2，3。具体如下：

当主人(或客人)亮出“虫子”时，记X=0(或Y=0)；

当主人(或客人)亮出“公鸡”时，记X=1(或Y=1)；

当主人(或客人)亮出“老虎”时，记X=2(或Y=2)；

当主人(或客人)亮出“棒子”时，记X=3(或Y=3)。

如果某回合中，主人亮出的是x(即X=x，0≤x≤3)，而客人亮出的是y(即Y=y，0≤y≤3)，那么，本回合主人赢(即罚客人一杯酒)的充分必要条件是：(x-y)mod4=1；客人赢(即罚主人一杯酒)的充分必要条件是：(y-x)mod4=1；否则，本回合为“平局”，即主客双方互不罚酒，接着进行下一回合的“斗酒”。

这个“猜拳”游戏显然是一种“非盲对抗”。主人和客人到底谁输谁赢？最多会被罚多少杯酒？他们怎样才能让对方多喝，而自己少喝？下面就用《安全通论》的“信道容量法”来回答这些问题。

由概率论中的大数定律，频率趋于概率，所以，根据“主人(X)”和“客人(Y)”的习惯，即过去他们“斗酒”的统计规律(如果他们是初次见面，那么不妨让他们以“热身赛”方式先“斗酒”一阵子，然后记下他们的习惯)，就可以分别给出X和Y的概率分布，以及(X，Y)的联合概率分布：

0

0

0

px=∑0≤y≤3txy，x=0,1,2,3；

qy=∑0≤x≤3txy，y=0,1,2,3。

为了分析“主人”赢酒情况，我们构造一个随机变量Z=(Y+1)mod4。然后，再用随机变量X和Z构成一个信道(X；Z)，称它为“猜拳主人信道”，即该信道以X为输入、Z为输出。

下面来分析几个事件等式。如果某回合中，主人亮出的是x(即X=x，0≤x≤3)，而客人亮出的是y(即Y=y，0≤y≤3)，那么：

如果本回合“主人”赢，则有(x-y)mod4=1，即，y=(x-1)mod4，于是，z=(y+1)mod4=[(x-1)+1]mod4=xmod4=x，换句话说，此时，“猜拳主人信道”的输出Z始终等于输入X，也就是说，一个“比特”被成功地从输入端X发送到了输出端Z。

反过来，如果在“猜拳主人信道”中，一个“比特”被成功地从输入端X发送到了输出端Z,那么，此时就有“输出z始终等于输入x，即z=x”，也就有(x-y)mod4=(z-y)mod4=[(y+1)-y]mod4=1mod4=1，于是，根据“猜拳”规则，就该判“主人赢”，即客人罚酒一杯！

结合上述正反两种情况有：

引理1：在“猜拳”游戏中，“主人赢一次”就等价于“1个“比特”被成功地从“猜拳主人信道”(X；Z)的输入端发送到了输出端”。

由引理1，再结合仙农信息论的著名“信道编码定理”[5-6]：如果“猜拳主人信道”的容量为C，那么，对于任意传输率k/n≤C，都可以在译码错误概率任意小的情况下，通过某个n比特长的码字，成功地把k个比特传输到收信端。反过来，如果“猜拳主人信道”能够用n长码字，把S个比特无误差地传输到收信端，那么，一定有S≤nC。把这段话翻译一下，便有如下定理：

定理1(猜拳主人赢酒定理)：设由随机变量(X；Z)组成的“猜拳主人信道”的信道容量为C，那么，在剔除掉“平局”的情况后有：(1)如果主人想罚客人k杯酒，那么，他一定有某种技巧(对应于仙农编码)，使得他能够在k/C个回合中，以任意接近1的概率达到目的。反过来，(2)如果主人在n回合中，赢了S次，即，罚了客人S杯酒，那么，一定有S≤nC。

由该“猜拳主人赢酒定理”可知，只要求出“猜拳主人信道”的信道容量C，那么，主人“赢酒”的“杯数”极限就确定了。下面就来求信道容量C。

首先，(X，Z)的联合概率分布为：

Pr(X=i,Z=j)=Pr(X=i,(Y+1)mod4=j)=Pr(X=i,Y=(j-1)mod4)=ti(j-1)mod4，i,j=0,1,2,3,4

所以，“猜拳主人信道”(X；Z)的信道容量就是：

C=Max[I(X,Z)]=Max{∑0≤i,j≤3[ti(j-1)mod4]

log[ti(j-1)mod4]/(piqj)}

这里的最大值Max是针对满足如下条件的实数而取的：0

同理，可以分析“客人赢酒”的情况，此处不再赘述。

可见，“主人”赢酒的多少(C(q0,q1,q2,q3))，其实取决于“客人”的习惯(q0,q1,q2,q3)。如果主客双方都固守他们的习惯，那么，他们的输赢已经“天定”了；如果“主人”或“客人”中有一方见机行事(即调整自己的习惯)，那么，当他调整到其信道容量大过对方时，他就能够整体上赢；如果“主人”和“客人”双方都在调整自己的习惯，那么，他们最终将达到动态平衡。

2 “划拳”赢酒

“划拳”比“猜拳”更复杂，是宴会上主人和客人闹酒的另一种游戏形式。

该游戏规则是：在每个回合中，主人(A)和客人(B)各自同时独立地在手上亮出0～5这6种手势之一，并在嘴上吼出0～10这11个数之一。也就是说，每个回合中，“主人A”是一个2维随机变量，即A=(X，Y)，其中，0≤X≤5是“主人”手上显示的数，而0≤Y≤10是“主人”嘴上吼出的数。同样，“客人B”也是一个2维随机变量，即B=(F，G)，其中，0≤F≤5是“客人”手上显示的数，而0≤G≤10是“客人”嘴上吼出的数。

如果在某个回合中，“主人”和“客人”的2维数分别是(x,y)和(f,g)，那么，“划拳”游戏的罚酒规则是：

如果，x+f=y，那么，“主人”赢，罚“客人”喝一杯酒；如果，x+f=g，那么，“客人”赢，罚“主人”喝一杯酒；如果上述两种情况都不出现，则为“平局”，主客双方互不罚酒，接着进行下一回合。具体来说：双方嘴上吼的数一样(即g=y)时，“平局”出现；双方虽然吼的数各不相同，但是，他们“手上显示的数之和”不等于“任何一方嘴上吼的数”时，“平局”也出现。

这个“划拳”游戏显然也是一种“非盲对抗”。下面就用《安全通论》的“信道容量法”来研究游戏双方的输赢问题。

与前文“猜拳”游戏类似，由概率论中的大数定律，频率趋于概率，根据“主人(A)”和“客人(B)”的习惯，即过去他们“斗酒”的统计规律，就可以分别给出A和B及其分量X、Y、F、G的概率分布，以及4个随机变量(X，Y，F，G)的联合概率分布：

“主人”手上显示x的概率：0

“客人”手上显示f的概率：0

“主人”嘴上吼y的概率：0

“客人”嘴上吼g的概率：0

“主人”手上显示x，嘴上吼y的概率：

0

“客人”手上显示f，嘴上吼g的概率：

0

“主人手上显示x，嘴上吼y；同时，客人手上显示f，嘴上吼g”的概率：

0

为了分析“主人”赢酒情况，构造一个2维随机变量：Z=(U,V)=(Xδ(G-Y)，X+F)，这里的δ函数定义为：δ(0)=0；δ(x)=1，如果x≠0。于是：

Pr[Z=(u,v)]=∑x+f=v,xδ(g-y)=utxyfg=:duv，这里，0≤v≤10，0≤u≤5。

然后，再用随机变量A和Z构成一个信道(A；Z)，称它为“划拳主人信道”，即，该信道以A为输入，以Z为输出。

下面来分析几个事件等式。如果某回合中，主人手上亮出的是x(即X=x，0≤x≤5)，主人嘴上吼的是y(即Y=y，0≤y≤10)；而客人手上亮出的是f(即F=f，0≤f≤5)，客人嘴上吼的是g(即G=g，0≤g≤10)。那么，根据“划拳”的评判规则有：

如果本回合“主人”赢，那么，x+f=y，同时y≠g。于是，δ(g-y)=1，进一步就有：Z=(u,v)=(xδ(g-y)，x+f)=(x,y)=A，换句话说，此时，“划拳主人信道”的输出Z始终等于输入A，也就是说：一个“比特”被成功地从输入端A发送到了输出端Z。

反过来，如果在“划拳主人信道”中，一个“比特”被成功地从输入端A发送到了输出端Z，那么，此时就有“输出z=(u,v)=(xδ(g-y)，x+f)始终等于输入(x,y)”，也就有：xδ(g-y)=x同时x+f=y，即，y≠g且x+f=y，于是，根据“划拳”规则，就该判“主人赢”，即，客人罚酒一杯！

结合上述正反两种情况，便有：

引理2：在“划拳”游戏中，“主人赢一次”就等价于“1个“比特”被成功地从“划拳主人信道”(A；Z)的输入端，发送到了输出端”。

由引理2，再结合仙农信息论的著名“信道编码定理”[5-6]：如果“划拳主人信道”的容量为D，那么，对于任意传输率k/n≤D，都可以在译码错误概率任意小的情况下，通过某个n比特长的码字，成功地把k个比特传输到收信端。反过来，如果“划拳主人信道”能够用n长码字，把S个比特无误差地传输到收信端，那么，一定有S≤nD。把这段话翻译一下，便有如下定理：

定理2(划拳主人赢酒定理)：设由随机变量(A；Z)组成的“划拳主人信道”的信道容量为D。那么，在剔除掉“平局”的情况后有：(1)如果主人想罚客人k杯酒，那么，他一定有某种技巧(对应于仙农编码)，使得他能够在k/D个回合中，以任意接近1的概率达到目的。反过来，(2)如果主人在n回合中赢了S次，即，罚了客人S杯酒，那么，一定有S≤nD。

由该“划拳主人赢酒定理”可知，只要求出“划拳主人信道”的信道容量D，那么，主人“赢酒”的“杯数”极限就确定了。下面就来求信道容量D：

D=Max[I(A,Z)]

=Max{∑a,zPr(a,z)log[Pr(a,z)/[Pr(a)Pr(z)]]}

=Max{∑x,y,f,gPr(x,y,xδ(g-y),x+f)log[Pr(x,y,xδ(g-y),x+f)/[Pr(x,y)Pr(xδ(g-y),x+f)]]}

=Max{∑x,y,f,gtx,y,xδ(g-y),x+flog[tx,y,xδ(g-y),x+f/

[bxydxδ(g-y),x+f]]}

这里的最大值是针对满足如下条件的正实数而取的：

0≤y≤10；∑0≤y≤10ry=1；

0≤y≤10，0≤x≤5，∑0≤y≤10,0≤x≤5bxy=1；

0≤g≤10，0≤f≤5，∑0≤g≤10,0≤f≤5hfg=1。

所以，“划拳主人信道”的容量D其实是满足条件0≤f≤5；f0+f1+f2+f3+f4+f5=1；0≤g≤10；∑0≤g≤10sg=1的fi，gj的函数，0≤i≤5,0≤j≤10。

同理，可以分析“客人赢酒”的情况，此处不再赘述。

可见，“划拳主人”赢酒的多少(D(gj,fi))，其实取决于“客人”的习惯(gj,fi)。如果主客双方都固守他们的习惯，那么，他们的输赢已经“天定”了；如果“主人”或“客人”中有一方见机行事(即，调整自己的习惯)，那么，当他调整到其信道容量大过对方时，他就能够整体上赢；如果“主人”和“客人”双方都在调整自己的习惯，那么，他们最终将达到动态平衡。

3 线性可分“非盲对抗”的抽象模型

设黑客(X)共有n招来发动攻击，即随机变量X的取值共有n个，不妨记为{x0,x1,…xn-1}={0,1,2,…,n-1}，这也是黑客的全部“武器库”。

设红客(Y)共有m招来抵抗攻击，即随机变量Y的取值共有m个，不妨记为{y0,y1,…ym-1}={0,1,2,…,m-1}，这也是红客的全部“武器库”。

注意：在下面推导中，将根据需要在“招xi，yj”和“数i,j”之间等价地变换，即：xi=i，yj=j，其目的在于，既把问题说清楚，又在形式上简化。

在非盲对抗中，每个黑客武器xi(i=0,1,…,n-1)和每个红客武器yj(j=0,1,…,m-1)之间，存在着一个红黑双方公认的输赢规则，于是，一定存在2维数集{(i,j),0≤i≤n-1,0≤j≤m-1}的某个子集H，使得“xi胜yj”当且仅当(i,j)∈H。如果这个子集H的结构比较简单，那么，我们就能够构造某个信道，使得“黑客赢一次”等价于“1比特信息被成功地从该通信信道的发端传输到了收端”，然后，再利用著名的仙农信道编码定理即可。比如：

在“石头剪刀布”游戏中，H={(i,j):0≤i,j≤2，(j-i)mod3=2}；

在“猜正反面”游戏中，H={(i,j):0≤i=j≤1}；

在“手心手背”游戏中，H={(i,j,k):0≤i≠j=k≤1}；

在“猜拳”游戏中，H={(i,j):0≤i,j≤3，(i-j)mod4=1}；

在“划拳”游戏中，H={(x,y,f,g):0≤x,f≤5；0≤g≠y≤10；x+f=y}。

在文献[3,4]和本文中，已经针对以上各H构造出了相应的通信信道。但是，对一般的H，却很难构造出这样的通信信道，不过，有一种特殊情况还是可以有所作为的，即，如果上面的集合H可以分解为H={(i,j):i=f(j),0≤i≤n-1,0≤j≤m-1}(即，H中第一个分量j是其第二个分量的某种函数)，那么，我们就可以构造一个随机变量Z=f(Y)。然后，考虑信道(X；Z)，于是便有如下事件等式：

如果在某个回合中，黑客出击的招是xi，而红客应对的招是yj，那么：

如果“黑客赢”，则有i=f(j)，也就是说，此时信道(X；Z)的输出便是Z=f(yj)=f(j)=i=xi，即，此时信道的输出与输入相同，即1个比特被成功地从信道(X；Z)的输入端发送到了输出端。

反过来，如果“1个比特被成功地从信道(X；Z)的输入端发送到了输出端”，那么，此时就该有“输入=输出”，即“i=f(j)”，这也就意味着“黑客赢”。

结合上述正反两个方面，得到如下定理：

定理3(线性非盲对抗极限定理)：在“非盲对抗”中，设黑客X共有n种攻击法{x0,x1,…xn-1}={0,1,2,…,n-1}；设红客Y共有m种防御法{y0,y1,…ym-1}={0,1,2,…,m-1}，又设红黑双方约定的输赢规则是：“xi胜yj”当且仅当(i,j)∈H。这里H是矩形集合{(i,j),0≤i≤n-1,0≤j≤m-1}的某个子集。

如果H关于黑客X是线性的，即，H可以表示为H={(i,j):i=f(j),0≤i≤n-1,0≤j≤m-1}(即，H中第一个分量i是其第二个分量j的某种函数f(.))，那么，便可以构造一个信道(X；Z)，其中Z=f(Y)，使得若C是信道(X；Z)的信道容量，则有：

(1)如果黑客想赢k次，那么，他一定有某种技巧(对应于仙农编码)，使得他能够在k/C个回合中，以任意接近1的概率达到目的；

(2)如果黑客在n个回合中赢了S次，则一定有S≤nC。

如果H关于红客Y是线性的，即，H可以表示为H={(i,j):j=g(i),0≤i≤n-1,0≤j≤m-1}(即，H中第二个分量j是其第一个分量i的某种函数g(·))，那么，便可以构造一个信道(Y；G)，其中G=g(X)，使得若D是信道(Y；G)的信道容量，则有：

(1)如果红客想赢k次，那么，他一定有某种技巧(对应于仙农编码)，使得他能够在k/D个回合中，以任意接近1的概率达到目的;

(2)如果红客在n个回合中赢了S次，则一定有S≤nD。

4 结束语

“石头剪刀布”、“手心手背”、“猜正反面”、“猜拳”和“划拳”等游戏，其实它们的输赢规则集H都是线性可分的，因此，它们全是本文定理3(线性非盲对抗极限定理)的特例而已。至于H为不可分情况，相应的信道构造就无从下手了，这个问题就作为公开问题，留待今后解决吧。

为了加深大家的印象，我们对“盲对抗”和“非盲对抗”再做一些形象的描述：

所谓“盲对抗”，就是在每个攻防回合后，攻防双方都只知道自己的“自评结果”，而对敌方的“他评结果”一无所知。像大国斗智、战场搏杀、网络攻防、谍报战等比较惨烈的对抗，通常都属于“盲对抗”。这里的“盲”，与是否面对面无关，比如，“两泼妇互相骂街”就是典型的面对面的“盲对抗”，因为，“攻方”是否骂到了“守方”的痛处，只有“守方”自己才知道，而且，被骂者通常还要极力掩盖其痛处，不让“攻方”知道自己的弱点在哪。当然，“一群泼妇互相乱骂”，更是盲对抗了。

所谓“非盲对抗”，就是在每个攻防回合后，双方都知道本回合的一致的“胜败结果”。比如，像古老的“石头剪刀布”游戏中，一旦双方的手势亮出后，本回合的胜败结果就一目了然。像许多赌博游戏、体育竞技等项目都属于“非盲对抗”。家喻户晓的童趣游戏“猜正反面游戏”、“手心手背游戏”和本文中的“划拳”和“划拳”等，也都是“非盲对抗”，只不过，在“手心手背游戏”中彼此对抗的人，不再是两个，而是三个。

更加形象地说，“泼妇骂架”是“盲对抗”，但是，“两流氓打架”却是“非盲对抗”了。因为，人的身体结构都相似，被打的痛处在哪，谁都知道，而且结论也基本一致，所以，“打架”是“非盲的”，当然，“打群架”也是“非盲对抗”。但是，人的心理结构却千差万别，被骂的痛点会完全不同，所以，“骂架”是“盲的”。

(致谢：本文中的“划拳”和“猜拳”游戏，由北京CA总经理詹榜华博士提供，特此致谢。)

[1] 杨义先，钮心忻.安全通论(1)——经络篇[J].微型机与应用，2016，35(15)：1-4.

[2] 杨义先，钮心忻.安全通论(2)——攻防篇之“盲对抗”[J].微型机与应用，2016，35(16)：1-5.

[3] 杨义先，钮心忻.安全通论(3)——攻防篇之“非盲对抗”之“石头剪刀布”[J].微型机与应用，2016，35(17)：1-3.

[4] 杨义先，钮心忻.安全通论(4)——攻防篇之“非盲对抗”之“童趣游戏”[J].微型机与应用，2016，35(18)：3-5，9.

[5] COVER T M， THOMAS J A，著.信息论基础[M].阮吉寿，张华，译.北京：机械工业出版社，2007.

[6] Shu Lin， COSTELLO D J,JR.著，差错控制码[M].晏坚，何元智，潘亚汉，等，译.北京：机械工业出版社，2007.

(未完待续，系列之六《安全通论(6)——攻防篇之“多人盲对抗”》见下期)