另外,定理3还揭示了一个实事:如果采用对数最优的攻击组合策略,那么对于每个系统的攻击投入,所获得的收益比例的期望值不会在此轮攻击结束后变化。具体来说,假如初始的攻击资金分配比例为b*,那么第一轮攻击后,第i个系统的收益与整合攻击组合的收益的比例为(b*iXi)/(b*TX),其期望为:
E[(b*iXi)/(b*TX)]= b*i E[Xi/(b*TX)]= b*i
因此,第i个系统在本轮攻击结束后的收益占整个攻击组合收益的比例的数学期望值,与本轮攻击开始时第i个系统的攻击投入比例相同。一旦选定按比例进行攻击组合,那么在期望值的意义下,该攻击组合比例将保持不变。
现在深入分析定理1中n轮攻击后黑客的收益情况。令
W*=maxbW(b,F)=maxbE(log(bTX))
为最大增长率,并用b*表示达到最大增长率的攻击组合。
定义2:一个因果的攻击组合策略定义为一列映射bi:Rm(i-1)→В,其中bi(x1,x2,…,xi-1)解释为第i轮攻击的攻击组合策略。
由W*的定义可以直接得出:对数最优攻击组合使得最终收益的数学期望值达到最大。
引理3:设Sn*为定理1所指的在对数最优攻击组合b*之下n轮攻击后黑客的收益。又设Sn为采用定义2中的因果攻击组合策略bi在n轮攻击后黑客的收益。那么,E(log Sn*)=n W*≥E(logSn)。
证明:maxE(logSn)=max[E∑ni=1log(bTiXi)]
=∑ni=1{maxE[log(bTi(X1,X2,…,Xi-1)Xi]}
=∑ni=1{E[log(b*TXi)]}=nW*
此处,第一项和第二项中的最大值(max)是对b1,b2,…,bn而取的;第3项中的最大值(max)是对bTi(X1,X2,…,Xi-1)而取的。可见,最大值恰好是在恒定的攻击组合bT*之下达到的。证毕。
到此就知道:由定理2中的b*给出的攻击组合能够使得黑客收益的期望值达到最大值,而且所得的收益Sn*以高概率在一阶指数下等于2nW(*)。其实还可以得到如下更强的结论。
定理4:设Sn*和Sn如引理3所述,那么依概率1有,
limn→∞sup{[log(Sn/S*n)]/n}≤0
证明:由定理2可推出E(Sn/S*n)≤1,从而,由马尔可夫不等式得到:
Pr(Sn>tnS*n)=Pr[(Sn/S*n)>tn]<1/tn,因此,Pr{[log(Sn/S*n)]/n>[logtn]/n}≤1/tn
取tn=n2,并对所有n求和,得到:
∑∞n=1Pr{[log(Sn/S*n)]/n>(2logn)/n}≤∑∞n=1(1/n2)=π2/6
利用BorelCantelli引理得:
Pr{[log(Sn/S*n)]/n>(2logn)/n,无穷多个成立}=0
这意味着,对于被攻击的每个系统向量序列,都存在N,使得当n>N时,均有log(Sn/S*n)/n<(2logn)/n成立。于是,依概率1,limn→∞sup{[log(Sn/S*n)]/n}≤0成立。证毕。
该定理表明,在一阶指数意义下,对数最优攻击组合的表现相当好。
散户炒股都有这样的经验:如果能够搞到某些“内部消息”(学术上称之为“边信息”),那么炒股赚钱的可能性就会大增;但是,到底能够增加多少呢?下面就来回答这个问题。当然,这里将其叙述为:边信息对黑客收益的可能影响。
定理5:设X服从分布f(x),而bf为对应于f(x)的对数最优攻击组合。设bg为对应于另一个密度函数g(x)的对数最优攻击组合。那么采用bf替代bg所带来的增长率的增量满足如下不等式:ΔW=W(bf,F)-W(bg,F)≤D(f|g)。这里,D(f|g)表示相对熵(见参考文献[1])。
证明:ΔW=∫f(x)log(bTfx)-∫f(x)log(bTgx)
=∫f(x){log[(bTfx)/(bTgx)]}
=∫f(x){log[(bTfx)/(bTgx)][g(x)/f(x)][f(x)/g(x)]}
=∫f(x){log[(bTfx)/(bTgx)][g(x)/f(x)]} +D(f|g)
≤log{∫f(x)[(bTfx)g(x)]/[(bTgx)f(x)]}+D(f|g)
=log[∫g(x)(bTfx)/(bTgx)]+D(f|g)
≤log1+D(f|g)=D(f|g)。证毕。
定理6:由边信息Y所带来的增长率的增量ΔW满足不等式:ΔW≤I(X;Y)。这里I(X;Y)表示随机变量X与Y之间的互信息。
证明:设(X,Y)服从分布f(x,y),其中X是被攻击系统的“投入产出比”向量,而Y是相应的边信息。当已知边信息Y=y时,黑客采用关于条件分布f(x|Y=y)的对数最优攻击组合,从而在给定条件Y=y下,利用定理5,可得:
ΔWY=y≤D[f(x|Y=y)│f(x)]
=∫xf(x|Y=y)log[(f(x|Y=y))/f(x)]dx
对Y的所有可能取值进行平均,得到:
ΔW≤∫yf(y){∫xf(x|Y=y)log[(f(x|Y
=y))/f(x)]dx}dy=∫y∫xf(y)f(x|Y=y)log[(f(x|Y
=y))/f(x)][f(y)/f(y)]dxdy
=∫y∫xf(x,y)log{f(x,y)/[f(x)f(y)]}dxdy=I(X;Y)
从而,边信息Y与被攻击的系统向量序列X之间的互信息I(X;Y)是增长率的增量的上界。证毕。
该定理6形象地说明,“内部消息”能够使黑客的“黑产收益”增长率的精确上限不超过I(X;Y)。
下面再考虑被攻击系统依时间而变化的情况。