||
《安全通论》(5)
------攻防篇之“非盲对抗”及“劝酒令”
杨义先,钮心忻
北京邮电大学信息安全中心
摘要:“非盲对抗”变化多端,很难“一招致胜”,只好“见招拆招”。不过,这倒增添了不少乐趣。你看,酒友们在宴会上玩的“划拳”和“猜拳”等劝酒令,也成了《安全通论》的严肃研究内容。本文仍然采用统一的“信道容量方法”,给出了醉鬼“赢酒杯数”和“罚酒杯数”的理论极限,还给出了醉鬼获胜的调整技巧。当然,这些内容也是《安全通论》不可或缺的组成部分。本文还针对所有“输赢规则线性可分”的“非盲对抗”,给出了统一的解决方案。
(一)前言
以网络空间安全、经济安全、领土安全等为代表的所有安全问题的核心,就是“对抗”!所以,无论花多少篇幅,都必须把它研究透彻,至少是要尽可能透彻。那怕是多次变换角度,甚至利用古老游戏和时髦娱乐项目,来全面深入地研究安全对抗问题,都是值得的。
“安全经络”是《安全通论》的第一块基石,文献[1]已经打好了这块基石。
“安全对抗”是《安全通论》的第二块基石。“安全对抗”分为两大类:盲对抗、非盲对抗。为了打好这第二块基石,我们已经在文献[2]中,统一研究了“盲对抗”,并给出了黑客(红客)攻击(防守)能力的精确极限。针对“非盲对抗”,我们虽然已经找到了统一的研究方法(信道容量法),但是,由于“非盲对抗”的模型千变万化,我们只好“见招拆招”。比如,分别在文献[3]和[4]中,以国际著名的“石头剪刀布游戏”、国内家喻户晓的“猜正反面游戏”和“手心手背游戏”为对象,研究了“非盲对抗”的三个有趣实例,给出了输赢极限和获胜技巧。本文则利用《安全通论》对酒桌上著名的两个实例(划拳、猜拳)进行分析,仍然采用统一的“信道容量方法”,给出了“赢酒杯数”和“罚酒杯数”的理论极限,还给出了醉鬼获胜的调整技巧。当然,这些内容也是《安全通论》不可或缺的组成部分。此外,针对“非盲对抗”的很大一个子类(输赢规则线性可分的情况),我们给出了统一的解决方案。
(二)“猜拳”赢酒
“猜拳”,在北京又称“棒打老虎”,是宴会上,主人和客人闹酒的法宝之一。其游戏规则是:在每个回合中,主人和客人同时独立亮出如下四种手势之一:虫子、公鸡、老虎、棒子。然后,双方共同根据如下“胜负判定规则”来决定该罚谁喝一杯酒:
“虫子”被“公鸡”吃掉;“公鸡”被“老虎”吃掉;“老虎”被“棒子”打死;“棒子”被“虫子”蛀断。
除此之外,主客双方就算平局,互不罚酒。
一个回合结束后,主客双方再进行下一回合的“猜拳”。
将此“猜拳游戏”用数学方式表示出来便是:设主人和客人分别用随机变量X和Y来表示,它们的可能取值有四个: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<Pr(X=i)=pi<1,i=0,1,2,3;p0+p1+p2+p3=1;
0<Pr(Y=i)=qi<1,i=0,1,2,3;q0+q1+q2+q3=1;
0<Pr(X=i,Y=j)=tij<1,i, j=0,1,2,3;∑0≤i,j≤3tij=1。
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<pi,tij<1, i,j=0,1,2,3; p0+p1+p2+p3=1;∑0≤i,j≤3tij=1;px=∑0≤y≤3txy。所以,这个C实际上是满足条件q0+q1+q2+q3=1和0<qi<1,i=0,1,2,3的正实数变量的函数,即,可以记为C(q0,q1,q2,q3),其中,q0+q1+q2+q3=1。
同理,可以分析“客人赢酒”的情况,此处不再复述了。
可见,“主人”赢酒的多少(C(q0,q1,q2,q3)),其实取决于“客人”的习惯(q0,q1,q2,q3)。如果主客双方都固守他们的习惯,那么,他们的输赢已经“天定”了;如果“主人”或“客人”中有一方见机行事(即,调整自己的习惯),那么,当他调整到其信道容量大过对方时,他就能够整体上赢;如果“主人”和“客人”双方都在调整自己的习惯,那么,他们最终将达到动态平衡。
(三)“划拳”赢酒
“划拳”比“猜拳”更复杂,它也是宴会上,主人和客人闹酒的另一个法宝。
该游戏是这样的:在每个回合中,主人(A)和客人(B)各自同时独立地,在手上亮出0到5,这六种手势之一;并在嘴上吼出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的概率分布,以及四个随机变量(X,Y,F,G)的联合概率分布:
“主人”手上显示x的概率:0<Pr(X=x)=px<1,0≤x≤5;x0+x1+x2+x3+x4+x5=1;
“客人”手上显示f的概率:0<Pr(F=f)=qf<1,0≤f≤5;f0+f1+f2+f3+f4+f5=1;
“主人”嘴上吼y的概率:0<Pr(Y=y)=ry<1,0≤y≤10;∑0≤y≤10ry =1;
“客人”嘴上吼g的概率:0<Pr(G=g)=sg<1,0≤g≤10;∑0≤g≤10sg =1;
“主人”手上显示x,嘴上吼y的概率:
0<Pr[A=(x,y)]=Pr(X=x,Y=y)=bxy<1,0≤y≤10,0≤x≤5,∑0≤y≤10,0≤x≤5bxy =1;
“客人”手上显示f,嘴上吼g的概率:
0<Pr[B=(f,g)]=Pr(F=f,G=g)=hfg<1,0≤g≤10,0≤f≤5,∑0≤g≤10,0≤f≤5hfg =1;
“主人手上显示x,嘴上吼y;同时,客人手上显示f,嘴上吼g”的概率:
0<Pr[A=(x,y),B=(f,g)]=Pr(X=x,Y=y,F=f,G=g)=txyfg<1,这里,
0≤y,g≤10,0≤x,f≤5,∑0≤y,g≤10,0≤x,f≤5txyfg =1。
为了分析“主人”赢酒情况,我们构造一个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)。如果主客双方都固守他们的习惯,那么,他们的输赢已经“天定”了;如果“主人”或“客人”中有一方见机行事(即,调整自己的习惯),那么,当他调整到其信道容量大过对方时,他就能够整体上赢;如果“主人”和“客人”双方都在调整自己的习惯,那么,他们最终将达到动态平衡。
(四)线性可分“非盲对抗”的抽象模型
设黑客(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(j=0,1,…,m-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)的信道容量,
如果黑客想赢k次,那么,他一定有某种技巧(对应于仙农编码),使得他能够在k/C个回合中,以任意接近1的概率达到目的。
如果黑客在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)的信道容量,那么有:
如果红客想赢k次,那么,他一定有某种技巧(对应于仙农编码),使得他能够在k/D个回合中,以任意接近1的概率达到目的。
如果红客在n个回合中,赢了S次,那么,一定有S≤nD。
(五)结束语
“石头剪刀布”、“手心手背”、“猜正反面”、“猜拳”和“划拳”等游戏,其实他们的输赢规则集H都是线性可分的,因此,它们全是本文定理3(线性非盲对抗极限定理)的特例而已。至于H为不可分情况,相应的信道构造就无从下手了,这个问题就作为公开问题,留待今后解决吧。
为了加深大家的印象,我们对“盲对抗”和“非盲对抗”,再做一些形象的描述:
所谓“盲对抗”,就是在每个攻防回合后,攻防双方都只知道自己的“自评结果”,而对敌方的“他评结果”一无所知。像大国斗智、战场搏杀、网络攻防、谍报战等比较惨烈的对抗,通常都属于“盲对抗”。这里的“盲”,与是否面对面无关,比如,“两泼妇互相骂街”就是典型的,面对面的“盲对抗”,因为,“攻方”是否骂到了“守方”的痛处,只有“守方”自己才知道,而且,被骂者通常还要极力掩盖其痛处,不让“攻方”知道自己的弱点在哪。当然,“一群泼妇互相乱骂”,更是盲对抗了。
所谓“非盲对抗”,就是在每个攻防回合后,双方都知道本回合的,一致的“胜败结果”。比如,像古老的“石头剪刀布”游戏中,一旦双方的手势亮出后,本回合的胜败结果就一目了然:石头胜剪刀,剪刀胜布,布胜石头。像许多赌博游戏、体育竞技等项目都属于“非盲对抗”。家喻户晓的童趣游戏“猜正反面游戏”、“手心手背游戏”和本文中的“划拳”和“划拳”等,也都是“非盲对抗”,只不过,在“手心手背游戏”中彼此对抗的人,不再是两个,而是三个。
更加形象地说,“泼妇骂架”是“盲对抗”,但是,“两流氓打架”却是“非盲对抗”了。因为,人的身体结构都相似,被打的痛处在哪,谁都知道,而且结论也基本一致的,所以,“打架”是“非盲的”,当然,“打群架”也是“非盲对抗”。但是,人的心理结构却千差万别,被骂的痛点会完全不同,所以,“骂架”是“盲的”。
《安全通论》的第三篇(黑客篇),努力提示黑客的本质!
特别说明:这本该是一篇高影响因子的SCI论文,但是,如今国人已被SCI绑架了,所以,老夫想带头摆脱SCI的束搏,故将此文在这里发表。本文欢迎所有媒体转载。
致谢:本文中的“划拳”和“猜拳”游戏,由北京CA总经理詹榜华博士提供,特此致谢。
参考文献
[1]杨义先,钮心忻,安全通论(1)之“经络篇”,见杨义先的科学网实名博客(http://blog.sciencenet.cn/blog-453322-944217.html )
[2]杨义先,钮心忻,安全通论(2):攻防篇之“盲对抗”,见杨义先的科学网实名博客,(http://blog.sciencenet.cn/blog-453322-947304.html)
[3]杨义先,钮心忻,安全通论(3):攻防篇之“非盲对抗”之“石头剪刀布游戏”,见杨义先的科学网实名博客,(http://blog.sciencenet.cn/blog-453322-948089.html)
[4]杨义先,钮心忻,安全通论(4):攻防篇之“非盲对抗”之“童趣游戏”,见杨义先的科学网实名博客,(http://blog.sciencenet.cn/blog-453322-949155.html)
[5]Thomas M. Cover, Joy A. Thomas著,信息论基础,机械工业出版社出版,2007年11月,北京。阮吉寿,张华译;沈世镒审校。
[6]Shu Lin,Daniel J. Costello,Jr.著,差错控制码,机械工业出版社,2007年6月,北京。晏坚,何元智,潘亚汉等译。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-12-22 18:57
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社