1、第9章-沙盤演練的最佳攻防策略第1頁，共65頁。第9章 沙盤演練的最佳攻防策略從第7章和第8章，其實(shí)我們已經(jīng)知道：在任何現(xiàn)實(shí)的網(wǎng)絡(luò)空間安全對(duì)抗中，無論有多少個(gè)紅客與黑客參戰(zhàn)，無論大家的價(jià)值觀是多么千差萬別（當(dāng)然一定要事先確定，不能邊戰(zhàn)邊修改價(jià)值觀），也無論是多么復(fù)雜的混戰(zhàn)，只要大家以自身利益最大化為目標(biāo)，那么，就一定存在能夠共贏的最佳結(jié)局（即，納什均衡狀態(tài)）。第2頁，共65頁。第9章 沙盤演練的最佳攻防策略這個(gè)結(jié)果雖然已被嚴(yán)格的數(shù)學(xué)證明了，但是，由于它太抽象，以致于對(duì)安全界的許多人（特別是決策者們）來說，可能難以理解。又由于“納什均衡狀態(tài)”對(duì)樹立正確的安全觀念非常重要，所以，本章將提煉出專門針

2、對(duì)網(wǎng)絡(luò)攻防沙盤演練的，真正能夠使矛盾雙方都達(dá)到最佳結(jié)局（納什均衡狀態(tài)）的攻防策略計(jì)算方法。第3頁，共65頁。1. 最佳攻防策略與武器庫的豐富和淘汰原則2. 最佳攻防策略的計(jì)算第9章 沙盤演練的最佳攻防策略第4頁，共65頁。我們用沙盤演練來陳述觀點(diǎn)。設(shè)黑客攻方有m種攻擊手段，分別記為A=a1,a2,am；紅客守方有n種防護(hù)手段，分別記為B=b1,b2,bn。當(dāng)攻方用手段ai來攻，而守方用bj來防時(shí)，記攻方此時(shí)所獲得的收入為dij，1im，1jn；當(dāng)然，此時(shí)，守方的損失也為dij（也可以說守方的收入為-dij）。記mn矩陣D=dij為黑客攻方的收入矩陣，它當(dāng)然也是紅客守方的損失矩陣。一最佳攻防策略

3、與武器庫的豐富和淘汰原則第5頁，共65頁。這種沙盤非常接近實(shí)戰(zhàn)：1）雖然在實(shí)戰(zhàn)中，也許無法準(zhǔn)確掌握對(duì)方的全部手段，但是，可以在平常，通過日積月累，了解其大概（當(dāng)然，越精準(zhǔn)越好）；2）雖然在政治對(duì)抗中，收入矩陣D難以達(dá)成共識(shí)，但是，在經(jīng)濟(jì)對(duì)抗中，就完全沒有這個(gè)問題了，所以，此時(shí)的沙盤就能夠很逼真了。一最佳攻防策略與武器庫的豐富和淘汰原則第6頁，共65頁。當(dāng)攻守雙方的收入（損失）矩陣確定后，它們的整體實(shí)力就確定了，余下的問題就是在如此實(shí)力的條件下，各方如何為自己爭(zhēng)得最大的利益，即，攻方要想獲得盡可能多的收入，而守方則想盡可能地減少損失。下面，就來給出相關(guān)的攻防策略（稱為最優(yōu)策略），使得能夠同時(shí)滿足

4、攻守雙方的愿望。在平時(shí)，攻守雙方應(yīng)該努力提高自己的本領(lǐng)，使得自己在收入（損失）矩陣中占據(jù)優(yōu)勢(shì)；在戰(zhàn)時(shí)，攻守雙方一定要理智，要以自己利益最大化為目標(biāo)，而不做損人不利己的事情。一最佳攻防策略與武器庫的豐富和淘汰原則第7頁，共65頁。下面在攻守雙方都是理智的前提下，來進(jìn)行沙盤演練：一方面，對(duì)于任意1im，假如攻方用手段ai展開攻擊，那么，守方一定會(huì)用使自己的損失dij達(dá)到最?。?，min1jndij）的那個(gè)手段bj來進(jìn)行防護(hù)；于是，在精明的守方不出差錯(cuò)的前提下，攻方所能夠企望獲得的最大收入是max1immin1jndij。一最佳攻防策略與武器庫的豐富和淘汰原則第8頁，共65頁。另一方面，對(duì)于任意1j

5、n，假如守方用手段bj來進(jìn)行防護(hù)，那么，攻方一定會(huì)用使自己的收入dij達(dá)到最大（即，max1imdij）的那個(gè)手段ai去展開攻擊；于是，在精明的攻方不出差錯(cuò)的前提下，守方所能夠企望的最小損失是min1jnmax1imdij。假如在收入矩陣D中，碰巧成立等式max1immin1jndij=min1jnmax1imdij=dst，一最佳攻防策略與武器庫的豐富和淘汰原則第9頁，共65頁。這時(shí)就意味著，“攻方所企望的最大收入”=“守方所企望的最小損失”，即攻守雙方都達(dá)到了自己的目的，這時(shí)攻擊手段as和防護(hù)手段bt當(dāng)然就是各自的最佳手段了，因?yàn)?，這些手段使他們的利益都最大化了，此時(shí)，稱該對(duì)抗存在最佳純策

6、略（as，bt）。當(dāng)然，最佳攻防手段可能會(huì)有多組，但是，他們?cè)谑杖刖仃囍兴鶎?duì)應(yīng)的最佳收入值是相等的。一最佳攻防策略與武器庫的豐富和淘汰原則第10頁，共65頁。但是，并非所有收入矩陣D都能夠碰巧滿足等式max1immin1jndij=min1jnmax1imdij，比如，若在攻防手段中存在封閉環(huán)（就像石頭、剪刀、布游戲那樣），那么，這個(gè)等式就不成立。不過，幸好有如下定理：定理9.1（最佳純策略存在性定理）：在收入矩陣為D的攻防對(duì)抗中，存在攻守雙方的最佳策略的充分必要條件是：存在某組對(duì)抗（as，bt）使得對(duì)一切1im，1jn成立ditdstdsj。一最佳攻防策略與武器庫的豐富和淘汰原則第11頁，共

7、65頁。證明：先證充分性，由于ditdstdsj故max1imditdstmin1jndsj，又因?yàn)閙in1jnmax1imdijmax1imdit和min1jndsjmax1immin1jndij,所以有，min1jnmax1imdijdstmax1immin1jndij。一最佳攻防策略與武器庫的豐富和淘汰原則第12頁，共65頁。另一方面，對(duì)任給i和j，有min1jndijdijmax1imdij，所以，max1immin1jndijmin1jnmax1imdij。于是，綜合起來便有max1immin1jndij=min1jnmax1imdij，充分性證畢。一最佳攻防策略與武器庫的豐富和淘汰

8、原則第13頁，共65頁?，F(xiàn)在來證必要性。若有s和t，使得max1imdit=min1jnmax1imdij和min1jndsj=max1immin1jndij，則由max1immin1jndij=Min1jnmax1imdij就有，max1imdit=min1jndsjdstmax1imdit=min1jndsj所以，對(duì)任意i，j都有： ditmax1imditdstmin1jndsjdsj證畢。一最佳攻防策略與武器庫的豐富和淘汰原則第14頁，共65頁。為便于深入研究，現(xiàn)引進(jìn)關(guān)于二元函數(shù)鞍點(diǎn)的概念。定義9.1：設(shè)f(x,y)為一個(gè)定義在xA及yB上的實(shí)值函數(shù)，如果存在aA和bB，使得對(duì)一切xA

9、和yB，都有f(x,b)f(a,b)f(a,y)，那么，稱（a,b）為函數(shù)f的一個(gè)鞍點(diǎn)。由定義9.1及定理9.1可知，在收入矩陣為D的情況下，存在純策略意義最佳解dst（即，攻防雙方存在最佳策略as和bt）的充要條件是：dst是矩陣D的一個(gè)鞍點(diǎn)。下面，矩陣D的鞍點(diǎn)也稱為攻防對(duì)策的鞍點(diǎn)。一最佳攻防策略與武器庫的豐富和淘汰原則第15頁，共65頁。上面的定理9.1還可以再直觀解釋為：如果dst是收入矩陣D中第s行中最小值，同時(shí)也是第t列中最大值，則dst即為攻防最佳對(duì)策的收入值，并且（as，bt）就是攻防雙方的最佳對(duì)策解，即，當(dāng)攻方選取了攻擊手段as后，守方為了使其所失最少，只有選擇防護(hù)手段bt，否

10、則就可能失得更多；反之，當(dāng)守方選取了防護(hù)手段bt后，攻方為了得到最大的收入，他也只能選取攻擊手段as，否則，就會(huì)贏得更少。于是，攻防雙方的對(duì)抗在（as，bt）處達(dá)到了一個(gè)平衡的共贏狀態(tài)，任何一方若想打破這個(gè)狀態(tài)，他都會(huì)自遭損失。一最佳攻防策略與武器庫的豐富和淘汰原則第16頁，共65頁。收入矩陣的最佳攻防對(duì)策可能不唯一，但是，其多組最佳攻防策略之間，滿足如下性質(zhì)。性質(zhì)1（無差別性）。即若(as,bt)和(au,bv)是同一個(gè)收入矩陣D的兩組最佳對(duì)策，那么，dst=duv。即，收入矩陣最佳對(duì)策的值是唯一的。換句話說，攻防雙方不必在各種最佳策略之間去做選擇，反正，最終結(jié)果都一樣。性質(zhì)2（可交換性）。

11、即若(as,bt)和(au,bv)是同一個(gè)收入矩陣D的兩組最佳對(duì)策，那么，(as,bv)和(au,bt)也都是最佳對(duì)策。由此可知，當(dāng)攻方采用最佳攻擊手段時(shí)，他一定能夠贏得最佳收入，并不依賴于守方到底采用哪種最佳防護(hù)手段；同理，當(dāng)守方采用最佳防護(hù)手段時(shí)，他一定能夠最小損失，并不依賴于攻方到底采用哪種最佳攻擊手段。一最佳攻防策略與武器庫的豐富和淘汰原則第17頁，共65頁。前面已經(jīng)知道：收入矩陣為D時(shí)，攻方有把握至少贏得收入v=max1immin1jndij，守方有把握的至多損失是u=Min1jnmax1imdij；一般，攻方贏得的收入不會(huì)多于守方的所失，即總有vu當(dāng)u=v時(shí)，收入矩陣存在純策略意義

12、下的最佳解u=v。然而，一般情形并不總是如此，實(shí)際中出現(xiàn)的更多情形是v0，則jdijyj*=v。解釋出來便是：若攻擊手段i不可缺少，那么，攻方堅(jiān)持不懈地只用i來攻擊n次時(shí)，守方若出招最佳防護(hù)策略y*，那么，最后的收入之和剛好等于最佳收入值v。(2)若yj*0，則idijxi*=v。解釋出來便是：若防護(hù)手段j不可缺少，那么，守方堅(jiān)持不懈地只用j來防護(hù)m次時(shí)，攻方若出招最佳攻擊策略x*，那么，攻方最后的收入之和剛好也等于最佳收入值v。一最佳攻防策略與武器庫的豐富和淘汰原則第38頁，共65頁。(3)若jdijyj*v，則yj*=0。解釋出來便是：若守方連續(xù)m次使用防護(hù)手段j，而攻方出招最佳攻擊策略x

13、*，并且最后的收入之和大于最佳收入值v，那么，防護(hù)手段j也可被淘汰了。一最佳攻防策略與武器庫的豐富和淘汰原則第39頁，共65頁。證明: 按定義有v=maxxS1E(x,y*)，故，v-jdijy*j=maxxS1E(x,y*)-E(i,y*)0又因ix*iv-jdijy*j=v-ijdijx*iy*j=0 并且x*i0，i = 1 , , m所以，當(dāng)x*i0時(shí)，必有jdijy*j=v；當(dāng)jdijy*j0為任一常數(shù)；則有(1)：V2=aV1；(2)T1=T2。換句話說，如果黑客的攻擊能力普遍提高a倍的話，那么，他可以在沿用過去攻擊策略的情況下，將其最佳攻擊收入也提高a倍。上面的定理9.7和定理9

14、.8表明：平時(shí)的備戰(zhàn)，確實(shí)是有用的。當(dāng)然，如果守方通過備戰(zhàn)，使得收入矩陣的值減少，也可類似地降低自己的損失。一最佳攻防策略與武器庫的豐富和淘汰原則第42頁，共65頁。定理9.9：如果收入矩陣D是斜對(duì)稱矩陣，即，D=-DT，則，(1)其最佳對(duì)抗策略的收入值為0；(2)T1=T2，即，攻防雙方的最優(yōu)策略集是相同的。換句話說，此時(shí)攻守雙方每次出招都相同，所以，最終輸贏相等，總和為零。這時(shí)，也有類似于“以子之矛，攻子之盾”的情況。上面的定理9.7至定理9.9都很容易驗(yàn)證，此處略去細(xì)節(jié)。在給出定理9.10之前，先給出攻防對(duì)抗的優(yōu)超純策略定義。一最佳攻防策略與武器庫的豐富和淘汰原則第43頁，共65頁。定義

15、9.4：設(shè)攻方手段集S1=1,m，守方手段集S2=1,n，收入矩陣D=dij，如果對(duì)一切j=1,n，都有dsjdtj，即矩陣D的第s行元素均不小于第t行的對(duì)應(yīng)元素，則稱攻方的純策略s優(yōu)超于t（即，攻方的手段s始終比t厲害）；同樣，若對(duì)一切i=1,m，都有disdit，即矩陣D的第t列元素均不小于第s列的對(duì)應(yīng)元素，則稱守方的純策略s優(yōu)超于t（即，守方的手段s始終優(yōu)于t）。一最佳攻防策略與武器庫的豐富和淘汰原則第44頁，共65頁。定理9.10：設(shè)攻方手段集S1=1,m，守方手段集S2=1,n，收入矩陣D=dij，如果純策略1被其余純策略2,m中的某個(gè)策略所優(yōu)超，由D中去掉第一行，可得到一個(gè)新的(m

16、-1)n矩陣D1，于是有：(1)V=V1，即，基于D和D1的最佳對(duì)抗策略的收入值是相同的；(2)無論是基于D還是D1，守方的最優(yōu)防護(hù)策略都是相同的；(3)若(x2,xm)是D1中攻方的最優(yōu)攻擊策略，則(0,x2,xm)便是其在D中的最優(yōu)攻擊策略。一最佳攻防策略與武器庫的豐富和淘汰原則第45頁，共65頁。這個(gè)定理其實(shí)非常容易理解，即，如果攻方有一個(gè)手段很落后，以至于它完全可以被另一個(gè)攻擊手段所替代，那么，攻方扔掉該手段對(duì)整合對(duì)抗局勢(shì)不會(huì)產(chǎn)生任何影響，而守方也可以完全不必考慮如何來對(duì)付這種落后的武器。正如，攻方有了槍以后，還要刀干嗎；守方既然能夠?qū)Ω稑屃?，又何必?fù)?dān)憂刀呢。一最佳攻防策略與武器庫的豐

17、富和淘汰原則第46頁，共65頁。證明：不妨設(shè)攻擊手段2優(yōu)超于1，即，d2jd1j，j=1,n。若x=(x2,xm)和(y1,yn)是D1的最佳攻防策略解，由定理9.3，有，nj=1dijyjV1mi=2dijxi對(duì)所有i=2,m和j=1,n；這里V1是基于D1的最佳攻擊策略的收入值。因?yàn)?優(yōu)超于1，所以，nj=1d1jyjnj=1d2jyjV1。一最佳攻防策略與武器庫的豐富和淘汰原則第47頁，共65頁。合并上面的兩式，可得，nj=1dijyjV1mi=2dijxi+d1j.0，對(duì)所有i=1,m和j=1,n。或者，E(i,y)V1E(x,j)，對(duì)所有i=1,m和j=1,n。由定理9.4便知，(x

18、,y)就是D的最佳對(duì)抗策略解，其中x=(0,x2,xm)，且V1=V，基于D的最佳攻擊收入。 證畢。一最佳攻防策略與武器庫的豐富和淘汰原則第48頁，共65頁。推論：在定理9.10中，若1不是為純策略2,m中之一所優(yōu)超，而是為2,m的某個(gè)凸線性組合所優(yōu)超，則定理的結(jié)論仍然成立。此處的定理9.10實(shí)際給出了一個(gè)化簡(jiǎn)收入矩陣D的原則，或者說淘汰落后攻防手段的原則，稱之為優(yōu)超原則，即，當(dāng)攻方的某個(gè)攻擊手段ai被其他攻擊手段或其凸線性組合所優(yōu)超時(shí)，可在收入矩陣D中劃去第i行，而得到一個(gè)與原對(duì)抗等價(jià)但收入矩陣階數(shù)較小的攻防對(duì)抗，從而，使得求解其最佳對(duì)抗策略解時(shí)更容易些。類似地，對(duì)防守方來說，可以在收入矩陣

19、D中劃去被其他列或其他列的凸線性組合所優(yōu)超的那些列。一最佳攻防策略與武器庫的豐富和淘汰原則第49頁，共65頁。到此，我們給出了三個(gè)方面的有趣結(jié)果：1）如何使攻防武器庫中的已有武器，發(fā)揮最大的作用，即，給出了最佳攻防策略，見定理9.5的證明過程；2）如何對(duì)已有的武器庫進(jìn)行精練，淘汰落后的武器，使得戰(zhàn)時(shí)所用的武器能夠更好地發(fā)揮作用，即，定理9.6和定理9.10等；3）如何豐富武器庫，定理9.7和定理9.8等。一最佳攻防策略與武器庫的豐富和淘汰原則第50頁，共65頁。雖然在定理9.5的證明過程中，我們已經(jīng)給出了如何計(jì)算最佳攻防策略，但是，本節(jié)想再做一些細(xì)節(jié)強(qiáng)調(diào)。先看最簡(jiǎn)單的情況：攻守雙方都各只有兩種

20、手段，即，攻方的收入矩陣為22階的，即，D=dij，i,j=1,2。二最佳攻防策略的計(jì)算第51頁，共65頁。如果D有鞍點(diǎn)，則很快可求出攻防雙方的最優(yōu)純策略；如果D沒有鞍點(diǎn)，則可證明攻防雙方最優(yōu)混合策略中的x*i，y*j均大于零。于是，由定理9.6可知，為求最優(yōu)混合攻防策略，可求解下列方程組：()：d11x1+d21x2=v； d12x1+d22x2=v； x1+x2=1()：d11y1+d12y2=v； d21y1+d22y2=v； y1+y2=1二最佳攻防策略的計(jì)算第52頁，共65頁。當(dāng)矩陣D不存在鞍點(diǎn)時(shí)，可以證明上面方程組()和()一定有嚴(yán)格非負(fù)解x*=(x*1,x*2)（最佳攻擊策略）、

21、y*=(y*1,y*2)（最佳防護(hù)策略）和最佳收入值v，其中，x*1=(d22-d21)/(d11+d22)-(d12+d21)和x*2=(d11-d12)/(d11+d22)-(d12+d21)y*1=(d22-d12)/(d11+d22)-(d12+d21)和y*2=(d11-d21)/(d11+d22)-(d12+d21)v=(d11d22-d12d21)/(d11+d22)-(d12+d21)二最佳攻防策略的計(jì)算第53頁，共65頁。對(duì)一般的攻防對(duì)抗情況，最佳策略解可用如下線性方程組方法：根據(jù)定理9.4，求解最佳攻防對(duì)策解(x*,y*)的問題等價(jià)于求解不等式方程組idijxiv, 1jn

22、；ixi=1 ；xi0, 1im和 jdijyjv, 1im；jyj=1 ；yj0, 1jn。又根據(jù)定理9.5和定理9.6，如果假設(shè)最優(yōu)攻防策略中的x*i和y*j均不為零，即可將上述兩個(gè)不等式組的求解問題轉(zhuǎn)化成求解下面兩個(gè)方程組的問題：（I）：idijxi=v，j=1,n； ixi=1和（II）：jdijyj=v，i=1,m；jyj=1二最佳攻防策略的計(jì)算第54頁，共65頁。如果該方程組（I）和（II）存在非負(fù)解x*和y*，便求得了一個(gè)最佳攻防對(duì)策解(x*,y*)。如果由上述兩個(gè)方程組求出的解x*和y*中有負(fù)的分量，則可視具體情況，將（I）和（II）式中的某些等式改成不等式，繼續(xù)試算求解，直至

23、求出最佳攻防對(duì)策解。這種方法由于事先假設(shè)x*i和y*j均不為零，故當(dāng)x*和y*的實(shí)際分量中有些為零時(shí)，（I）和（II）式一般無非負(fù)解，而隨后的試算過程則是無固定規(guī)程可循的。因此，這種最佳攻防策略的計(jì)算方法在實(shí)際應(yīng)用中具有一定的局限性。二最佳攻防策略的計(jì)算第55頁，共65頁。計(jì)算最佳攻防策略的更好的方法，是如下的線性規(guī)劃方法。由定理9.5已知，最佳攻防對(duì)策的求解等價(jià)于一對(duì)互為對(duì)偶的線性規(guī)劃問題，而定理9.4表明，最佳攻防對(duì)策解x*和y*等價(jià)于下面兩個(gè)不等式組的解。()： idijxiv，j=1,n； ixi=1； xi0，i=1,m()： jdijyjv，i=1,m； jyj=1； yj0，j=

24、1,n其中，v=maxxS1minyS2E(x,y) = minyS2maxxS1E(x,y)就是最佳攻防對(duì)策的收入值。二最佳攻防策略的計(jì)算第56頁，共65頁。定理9.11：最佳攻防策略的收入值為，v=maxxS1min1jnE(x,j) = minyS2max1imE(i,y)。證明：因v是最佳攻防對(duì)策的收入值，故，v=maxxS1minyS2E(x,y)=minyS2maxxS1E(x,y)。一方面，任給xS1，有min1jnE(x,j)minyS2E(x,y)，故，maxxS1min1jnE(x,j)maxxS1minyS2E(x,y)二最佳攻防策略的計(jì)算第57頁，共65頁。另一方面，任

25、給xS1，yS2,有，E(x,y)=nj=1E(x,j)yjmin1jnE(x,j)故，minyS2E(x,y)min1jnE(x,j)和maxxS1minyS2E(x,y)maxxS1min1jnE(x,j)于是，v=maxxS1min1jnE(x,j)同理可證v=minyS2max1imE(i,y)。證畢。二最佳攻防策略的計(jì)算第58頁，共65頁。下面給出求解攻防對(duì)抗最佳策略的線性規(guī)劃方法。作變換(根據(jù)定理9.7，不妨設(shè)v0)：fi=xi/v，i=1,m，則不等式組（I）變?yōu)椋?)： idijfi1，j=1,n； ifi=1/v； fi0，i=1,m根據(jù)定理9.11，有v=maxxS1min1jn(idijxi)，二最佳攻防策略的計(jì)算第59頁，共65頁。這樣，不等式組()即等價(jià)于線性規(guī)劃問題：(P)：最小化z=ifi；idijfi1，j=1,n ；fi0同理，作變換gj=yj/v，j=1,n則不等式組（II）變?yōu)槎罴压シ啦呗缘挠?jì)算第60頁，共65頁。()：jdijgj1，i=1,m； jgj=1/v ； gj0，j=1,n其中，v=minyS2max1imjdijyj，與之等價(jià)的線性規(guī)劃問題是：(D)：最大化w=jgj；jdijgj1，i=1,m；gj0，j=