这里的最大值遍取所有可能的攻击组合b=(b1,b2,…,bm)T,bi≥0, ∑bi=1。如果某个攻击组合b*使得增长率W(b,F)达到最大值,那么,这个攻击组合就称为“对数最优攻击组合”。
为了简化上角标,本文对b*和b(*)交替使用,不加区别。
定理1:设Χ1,Χ2,…,Χn是服从同一分布F(x)的独立同分布随机序列。令S*n=∏i=1n b*TΧi是在同一攻击组合b*之下n轮攻击之后黑客的收益,那么,
(logS*n)/n → W*,依概率1。
证明:由强大数定律可知:
依概率1
所以,证毕。
引理1:W(b,F)关于b是凹函数,关于F是线性的,而W*(F)关于F是凸函数。
证明:增长率公式为W(b,F)=∫log(bTx)dF(x),由于积分关于F是线性的,因此,W(b,F)关于F是线性的。又由对数函数的凸性可知:
对该公式两边同取数学期望,便推出W(b,F)关于b是凹函数。最后,为证明W*(F)关于F是凸函数,假设F1和F2是收益列向量的两个分布,并令b*(F1)和b*(F2)分别是对应于两个分布的最优攻击组合。令b*(λF1+(1-λ)F2)为对应于λF1+(1-λ)F2的对数最优攻击组合,那么,利用W(b,F)关于F的线性特性,有:
因为b*(F1)和b*(F2)分别使得W(b,F1)和W(b,F2)达到最大值。证毕。
引理2:关于某个分布的全体对数最优攻击组合构成的集合是凸集。
证明:令b*1和b*2是两个对数最优攻击组合,即,W(b1,F)=W(b2,F)=W*(F)。由W(b,F)的凹性可以推出:
W[λb1+(1-λ)b2,F]≥λW(b1,F)+(1-λ)W(b2,F)=W*(F)
也就是说,λb1+(1-λ)b2还是一个对数最优的攻击组合。证毕。
令В={b∈Rm: bi≥0, ∑mi=1bi=1}表示所有允许的攻击组合。
定理2:设黑客欲攻击的m个系统的收益列向量X=(X1,X2,…,Xm)T服从联合分布F(x),即X~F(x),那么,该黑客的攻击组合b*是对数最优(即使得增长率W(b,F)达到最大值的攻击组合)的充分必要条件是:
当b*i>0时,E[Xi/(b*TX)]=1; 当b*i=0时,E[Xi/(b*TX)]≤1。
证明:由于增长率W(b)=E[log(bTX)]是b的凹函数,其中b的取舍范围为所有攻击组合形成的单纯形。于是,b*是对数最优的,当且仅当W(·)沿着从b*到任意其他攻击组合b方向上的方向导数是非正的。于是,对于0≤λ≤1,令bλ=(1-λ)b*+λb,可得:
[dW(bλ)/dλ]│λ=0+≤0,b∈В
由于W(bλ)在λ=0+处的单边导数为:
[dE(log(bTλX))/dλ]│λ=0+
=limλ→0{E[log[[(1-λ)b*TX+λbTX]/[b*TX]]]}/λ
=E{limλ→0{[log[1+λ[(bTX)/(b*TX)-1]]]/λ}}
=E[(bTX)/(b*TX)]-1
这里λ→0表示从正数方向趋向于0。于是,对所有b∈В都有:E[(bTX)/(b*TX)]-1≤0。如果从b到b*的线段可以朝着b*在单纯形В中延伸,那么W(bλ)在λ=0点具有双边导数且导数为0,于是,E[(bTX)/(b*TX)]=1;否则,E[(bTX)/(b*TX)]<1(注:此定理的更详细证明可参考文献[1]的定理16.2.1的证明过程),证毕。
由上面的定理2,可以得出如下推论:
定理3:设S*=b*TX是对应于对数最优攻击组合b*的黑客收益,令S=bTX是对应于任意攻击组合b的随机收益,那么,对所有的S有E[log(S/S*)]≤0 当且仅当对所有S有E(S/S*)≤1。
证明:对于对数最优的攻击组合b*,由定理2可知,对任意i有E[Xi/(b*TX)]≤1。对此式两边同乘以bi,并且关于i求和,可得到:
∑mi=1{biE[Xi/(b*TX)]}≤∑mi=1bi=1
这等价于E[(bTX)/(b*TX)]= E(S/S*)≤1,因为E[log(S/S*)]≤log[E(S/S*)]≤log1=0,其逆可由Jensen不等式得出,证毕。
此定理表明,对数最优攻击组合不但能够使得增长率最大化,而且,也能使得每轮攻击的收益比值E(S/S*)最大化。