yangleader的个人博客分享 http://blog.sciencenet.cn/u/yangleader 教授,博士生导师,北邮信息安全中心主任

博文

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

已有 7704 次阅读 2016-1-13 15:27 |个人分类:爽玩人生|系统分类:科研笔记

《安全通论》(5

------攻防篇之“非盲对抗”及“劝酒令”

杨义先,钮心忻

北京邮电大学信息安全中心

 

摘要:“非盲对抗”变化多端,很难“一招致胜”,只好“见招拆招”。不过,这倒增添了不少乐趣。你看,酒友们在宴会上玩的“划拳”和“猜拳”等劝酒令,也成了《安全通论》的严肃研究内容。本文仍然采用统一的“信道容量方法”,给出了醉鬼“赢酒杯数”和“罚酒杯数”的理论极限,还给出了醉鬼获胜的调整技巧。当然,这些内容也是《安全通论》不可或缺的组成部分。本文还针对所有“输赢规则线性可分”的“非盲对抗”,给出了统一的解决方案。

 

(一)前言

 

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

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

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

 

(二)“猜拳”赢酒

 

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

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

除此之外,主客双方就算平局,互不罚酒。

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

将此“猜拳游戏”用数学方式表示出来便是:设主人和客人分别用随机变量XY来表示,它们的可能取值有四个:0123。具体地说:

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

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

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

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

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

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

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

0<Pr(X=i)=pi<1i=0,1,2,3p0+p1+p2+p3=1

0<Pr(Y=i)=qi<1i=0,1,2,3q0+q1+q2+q3=1

0<Pr(X=i,Y=j)=tij<1i, j=0,1,2,30≤i,j≤3tij=1

px=0≤y≤3txyx=0,1,2,3

qy0≤x≤3txyy=0,1,2,3

 

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

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

如果本回合“主人”赢,那么,就有(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个“比特”被成功地从“猜拳主人信道”(XZ)的输入端,发送到了输出端”。

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

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

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

首先,(XZ)的联合概率分布为:

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

所以,“猜拳主人信道”(XZ)的信道容量就是:

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

这里的最大值Max是针对满足如下条件的实数而取的:0<pitij<1, i,j=0,1,2,3; p0+p1+p2+p3=10≤i,j≤3tij=1px=0≤y≤3txy。所以,这个C实际上是满足条件q0+q1+q2+q3=10<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)各自同时独立地,在手上亮出05,这六种手势之一;并在嘴上吼出010,这11个数之一。也就是说,每个回合中,“主人A”是一个2维随机变量,即,A=XY),其中,0X5是“主人”手上显示的数,而0Y10是“主人”嘴上吼出的数。同样,“客人B”也是一个2维随机变量,即,B=FG),其中,0F5是“客人”手上显示的数,而0G10是“客人”嘴上吼出的数。

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

如果,x+f=y,那么,“主人”赢,罚“客人”喝一杯酒;

如果,x+f=g,那么,“客人”赢,罚“主人”喝一杯酒;

如果上述两种情况都不出现,那么,就算“平局”,主客双方互不罚酒,接着进行下一回合。仔细一点说:双方嘴上吼的数一样(即,g=y)时,“平局”出现;双方虽然吼的数各不相同,但是,他们“手上显示的数之和”不等于“任何一方嘴上吼的数”时,“平局”也出现。

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

由概率论中的大数定律,频率趋于概率,所以,根据“主人(A)”和“客人(B)”的习惯,即,过去他们“斗酒”的统计规律(如果他们是初次见面,那么,不妨让他们以“热身赛”的方式,先“斗酒”一阵子,然后,记下他们的习惯就行了),就可以分别给出AB及其分量XYFG的概率分布,以及四个随机变量(XYFG)的联合概率分布:

“主人”手上显示x的概率:0<Pr(X=x)=px<10x≤5x0+x1+x2+x3+x4+x5=1

“客人”手上显示f的概率:0<Pr(F=f)=qf<10f≤5f0+f1+f2+f3+f4+f5=1

“主人”嘴上吼y的概率:0<Pr(Y=y)=ry<10y≤100≤y≤10ry =1

“客人”嘴上吼g的概率:0<Pr(G=g)=sg<10g≤100≤g≤10sg =1

“主人”手上显示x,嘴上吼y的概率:

0<Pr[A=(x,y)]=Pr(X=x,Y=y)=bxy<10≤y≤10,0x≤50≤y≤10,0≤x≤5bxy =1

“客人”手上显示f,嘴上吼g的概率:

0<Pr[B=(f,g)]=Pr(F=f,G=g)=hfg<10≤g≤10,0f≤50≤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,0x,f≤50≤y,g≤10,0≤x,f≤5txyfg =1

 

为了分析“主人”赢酒情况,我们构造一个2维随机变量

Z=(U,V)=(Xδ(G-Y)X+F)

这里的δ函数定义为:δ(0)=0;δ(x=1,如果x0。于是,

Pr[Z=(u,v)]=x+f=v,xδ(g-y)=utxyfg=:duv,这里,0v100u5

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

下面来分析几个事件等式。如果某回合中,主人手上亮出的是x(即,X=x0x5),主人嘴上吼的是y(即,Y=y0y10);而客人手上亮出的是f(即,F=f0f5),客人嘴上吼的是g(即,G=g0g10)。那么,根据“划拳”的评判规则有:

如果本回合“主人”赢,那么,x+f=y同时yg。于是,δ(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,即,ygx+f=y,于是,根据“划拳”规则,就该判“主人赢”,即,客人罚酒一杯!

结合上述正反两种情况,我们便有:

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

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

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

由该“划拳主人赢酒定理”可知,只要求出“划拳主人信道”的信道容量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]]}

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

0y≤100≤y≤10ry=1

0≤y≤10,0x≤50≤y≤10,0≤x≤5bxy =1

0≤g≤10,0f≤50≤g≤10,0≤f≤5hfg =1

 

所以,实际上,“划拳主人信道”的容量D其实是满足如下条件

0f≤5f0+f1+f2+f3+f4+f5=10g≤100≤g≤10sg =1

figj的函数,0i≤5,0j≤10。

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

可见,“划拳主人”赢酒的多少(Dgj,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},这也是红客的全部“武器库”。

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

在非盲对抗中,每个黑客武器xi(j=0,1,…,m-1)和每个红客武器yj(j=0,1,…,m-1)之间,存在着一个红黑双方公认的输赢规则,于是,一定存在2维数集{i,j,0in-1, 0≤j≤m-1}的某个子集H,使得“xiyj”当且仅当(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):0x,f50gy10x+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)。然后,考虑信道(XZ),于是便有如下事件等式:

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

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

反过来,如果“1个比特被成功地从信道(XZ)的输入端发送到了输出端”,那么,此时就该有“输入=输出”,即“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},又设红黑双方约定的输赢规则是:“xiyj”当且仅当(i,j)H。这里H是矩形集合{i,j,0in-1, 0jm-1}的某个子集。

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

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

  2. 如果黑客在n个回合中,赢了S次,那么,一定有SnC

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

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

  2. 如果红客在n个回合中,赢了S次,那么,一定有SnD

 

(五)结束语

 

“石头剪刀布”、“手心手背”、“猜正反面”、“猜拳”和“划拳”等游戏,其实他们的输赢规则集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著,信息论基础,机械工业出版社出版,200711月,北京。阮吉寿,张华译;沈世镒审校。

[6]Shu LinDaniel J. Costello,Jr.著,差错控制码,机械工业出版社,20076月,北京。晏坚,何元智,潘亚汉等译。

 




https://blog.sciencenet.cn/blog-453322-950146.html

上一篇:《安全通论》(4):攻防篇之“非盲对抗”之“童趣游戏”
下一篇:趣谈“网络空间安全一级学科”
收藏 IP: 59.64.255.*| 热度|

7 武夷山 刘钢 黄永义 邓松柏 zjzhaokeqin aliala xiyouxiyou

该博文允许注册用户评论 请点击登录 评论 (6 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-4-18 13:44

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部