王震 袁勇 安波 李明楚 王飛躍

1.大連理工大學(xué)軟件學(xué)院 遼寧 大連 116620 2.南洋理工大學(xué)計算機(jī)工程學(xué)院 新加坡 639798 3.中國科學(xué)院自動化研究所 北京100080 4.青島智能產(chǎn)業(yè)技術(shù)研究院山東青島266109

在現(xiàn)代社會中,保護(hù)各種關(guān)鍵公共基礎(chǔ)設(shè)施和目標(biāo)是各國安全機(jī)構(gòu)面臨的一項(xiàng)非常有挑戰(zhàn)性的任務(wù).比如,安全機(jī)構(gòu)需要保護(hù)公共交通網(wǎng)絡(luò)和乘客免受恐怖襲擊以及其他破壞活動;并且有責(zé)任阻止毒品、武器、錢財?shù)仍趪抑g非法流通;也同樣需要保護(hù)稀有動物和自然資源等免遭非法狩獵、非法捕撈以及過度砍伐行為的破壞.隨著網(wǎng)絡(luò)社會的發(fā)展,安全機(jī)構(gòu)還需要及時發(fā)現(xiàn)和遏制網(wǎng)絡(luò)謠言,維護(hù)健康的網(wǎng)絡(luò)環(huán)境.最近幾年來,日益增長的國際恐怖主義威脅,加劇了安全機(jī)構(gòu)面臨的挑戰(zhàn).特別是公交、地鐵、火車和飛機(jī)等公共交通網(wǎng)絡(luò)每天承載數(shù)以百萬的乘客,使得它們成為恐怖分子的主要攻擊目標(biāo),這些年針對這些目標(biāo)的恐怖襲擊造成了巨大的人員傷亡和經(jīng)濟(jì)損失.比如,2001年9月11日恐怖分子劫持民航客機(jī)撞擊美國紐約世界貿(mào)易中心和華盛頓五角大樓的事件中,造成了2974人死亡并造成272億元直接經(jīng)濟(jì)損失.2004年發(fā)生在西班牙馬德里的火車連環(huán)爆炸案造成191人死亡,1755人受傷和預(yù)計2.12億歐元的經(jīng)濟(jì)損失.2005年發(fā)生在英國倫敦的地鐵和公交爆炸案,造成52人死亡,700余人受傷,并造成預(yù)計20億英鎊的經(jīng)濟(jì)損失,2014年3月1號發(fā)生在我國昆明的火車站暴力砍殺事件,造成了29人死亡,143人受傷.

面對這些恐怖襲擊和安全威脅,安全機(jī)構(gòu)可以采用的措施包括在入口處或者外圍路網(wǎng)設(shè)置安檢口進(jìn)行車輛檢查以及在系統(tǒng)中進(jìn)行警力的巡邏防控等.近年來,各國也都在安全資源方面大大增加了投入,但是這些資源畢竟是有限的,安全機(jī)構(gòu)不可能在任何時候都提供全面的安全保護(hù).而且,恐怖分子和罪犯可以通過提前觀察來發(fā)現(xiàn)安全機(jī)構(gòu)的保護(hù)措施中的固定模式和弱點(diǎn),并據(jù)此來選擇最優(yōu)的攻擊策略.比如,如果我們固定只是在周二和周四兩天對火車進(jìn)行安全檢查,同樣,在對機(jī)場進(jìn)行巡邏時,我們固定上午9點(diǎn)在第一航站樓進(jìn)行巡邏,10點(diǎn)在第二航站樓,11點(diǎn)在第三航站樓,恐怖分子就可以輕易地觀察到并利用這些固定的模式,制定攻擊策略.所以,安全機(jī)構(gòu)需要通過隨機(jī)化調(diào)度安全資源來降低對手的偵查能力.但是安全機(jī)構(gòu)在進(jìn)行有效的隨機(jī)安全資源調(diào)度時面臨著非常多的困難.一個困難是如何給各種安全部門可以采取的行動賦予不同的權(quán)重.一些保護(hù)目標(biāo)比其他目標(biāo)更脆弱,另外有些保護(hù)目標(biāo)因?yàn)槿藛T更密集或者具有特殊的政治意義而對恐怖分子來說更加吸引力,所以在制定安全資源的分配調(diào)度方案時,需要把這些因素考慮進(jìn)去,而不能簡單地把所有保護(hù)目標(biāo)看作是等價的.而人類天生不擅長產(chǎn)生這種隨機(jī)的安全策略,無法產(chǎn)生真正的隨機(jī)行為.更為困難的是,在公共交通網(wǎng)絡(luò)和其他一些非常安全領(lǐng)域中,警力資源的調(diào)度問題規(guī)模驚人得大,即使不考慮隨機(jī)性的問題,人工調(diào)度也是一個非常昂貴和耗費(fèi)體力的工作.所以如何找出有限的安全資源的最優(yōu)配置方案,以獲取最佳的安全保護(hù)方案是安全領(lǐng)域資源分配中迫切需要解決的關(guān)鍵問題.

博弈論為研究有限安全資源的最優(yōu)部署策略提供了一個恰當(dāng)?shù)臄?shù)學(xué)模型.安全博弈論將安全部門和攻擊者(如恐怖分子)之間的博弈建模成Stackelberg博弈.盡管Stackelberg博弈模型是早在20世紀(jì)30年代提出來的[1],Wang Fei-Yue教授[2]在1990年就提出把Nash和Stackelberg策略引入到智能控制與優(yōu)化中,用于協(xié)調(diào)過程的監(jiān)控.但是Stackelberg博弈在安全部門領(lǐng)域中有限資源優(yōu)化調(diào)度中的應(yīng)用是在2006年Vincent Conitzer和Tuomas Sandolm發(fā)表了奠基性論文[3]后迅速發(fā)展起來的.該領(lǐng)域早期的主要研究者是南加利福尼亞大學(xué)Milind Tambe教授領(lǐng)導(dǎo)的TEAMCORE研究小組以及杜克大學(xué)Vicent Conitzer教授領(lǐng)導(dǎo)的研究小組,但是近些年越來越多的學(xué)者參與到這項(xiàng)研究中.相關(guān)的論文廣泛發(fā)表在人工智能領(lǐng)域的頂級會議IJCAI、AAAI和AAMAS上,安全博弈論的研究已經(jīng)成為當(dāng)前人工智能研究的熱點(diǎn)之一.

經(jīng)典的Stackelberg博弈模型通常有一個領(lǐng)導(dǎo)者和一個跟隨者.每一位參與者都有其可以執(zhí)行的行動集合,即純策略集.混合策略允許參與者以某種概率選擇不同純策略,每位參與者的收益取決于所有參與者的純策略組合,參與者混合策略的收益是純策略收益的期望,領(lǐng)導(dǎo)者先行選擇策略,跟隨者觀察到領(lǐng)導(dǎo)者的策略,然后根據(jù)觀察結(jié)果做出最優(yōu)回應(yīng).在安全領(lǐng)域,安全部門必須利用有限的資源保護(hù)有可能被攻擊的目標(biāo),而攻擊者(如恐怖分子)能夠觀察到安全部門的策略.因此,安全博弈可以很好地抽象為Stackelberg博弈,其中攻擊者充當(dāng)追隨者的角色,安全部門充當(dāng)領(lǐng)導(dǎo)者的角色[3].安全部門的純策略表示為對哪幾個可能的攻擊目標(biāo)進(jìn)行巡邏或者設(shè)置安檢點(diǎn),比如,在機(jī)場的哪幾個入口設(shè)置安檢點(diǎn)或者在哪些航班上安排空中警察.而攻擊者的純策略可以表示為攻擊哪一個目標(biāo),比如,某一個特定的航班,我們可以根據(jù)一些專家意見和歷史數(shù)據(jù)確定攻擊者對每個可能的攻擊目標(biāo)實(shí)施攻擊成功對雙方帶來的收益值.我們也可以考慮收益值的不確定性,將模型擴(kuò)展成貝葉斯(Bayesian)Stackelberg博弈[4].對這些博弈模型進(jìn)行求解可以得到領(lǐng)導(dǎo)者的Stackelberg均衡策略,這個均衡策略通常是一個混合策略,即以某個概率分布選擇各種可能的行動或資源分配,安全部門就可以利用這個策略來產(chǎn)生最佳的安全資源的調(diào)度方案.

近些年來,安全博弈論的研究取得了很大的進(jìn)展.研究者們不斷提出適應(yīng)于不同問題場景的Stackelberg博弈均衡策略求解算法.以這些算法為核心開發(fā)的很多實(shí)際應(yīng)用系統(tǒng)已經(jīng)被美國不同領(lǐng)域的安全機(jī)構(gòu)所使用.比如,ARMOR系統(tǒng)自2007年開始就被洛杉磯警方應(yīng)用在洛杉磯國際機(jī)場,用于規(guī)劃機(jī)場檢查點(diǎn)的設(shè)置以及警犬的巡邏路線[5];IRIS系統(tǒng)自2009年起被美國聯(lián)邦空中警察署(FAMS)應(yīng)用在由美國始發(fā)的航班上,用于為這些航班進(jìn)行調(diào)度分配空中警察[6];PROTECT系統(tǒng)用于規(guī)劃美國海岸警衛(wèi)隊(duì)的巡邏路線,以幫助美國海岸警衛(wèi)隊(duì)在執(zhí)行保護(hù)港口、水路和海岸安全時提高效率,目前已經(jīng)在洛杉磯、波士頓和紐約的港口使用,并在被推廣到美國更多的港口[7];TRUSTS系統(tǒng)用于協(xié)助警方制定地鐵的巡邏日程以防止逃票、地鐵站內(nèi)的非法交易及恐怖襲擊等安全危機(jī),目前正在洛杉磯地鐵上進(jìn)行測試[8].這些成功的應(yīng)用為未來安全博弈論領(lǐng)域的應(yīng)用提供了廣泛的前景,當(dāng)然同時隨著問題規(guī)模的增加,以及考慮人的有限理性和在實(shí)際執(zhí)行中的不確定性等因素,也為求解算法的研究提出了巨大的挑戰(zhàn).

1 安全博弈論的基本概念

本節(jié)介紹安全博弈論涉及到的一些基本概念.首先介紹Stackelberg博弈的概念,其次是它的擴(kuò)展形式貝葉斯Stackelberg博弈,然后介紹強(qiáng)Stackelberg均衡的概念,最后給出安全博弈論的基本模型,以及最基本的模型求解算法.

1.1 Stackelberg博弈

經(jīng)典的Stackelberg博弈是由一個領(lǐng)導(dǎo)者和一個跟隨者構(gòu)成的雙人博弈[1].領(lǐng)導(dǎo)者首先確定自己的混合策略,跟隨者首先通過觀察得到領(lǐng)導(dǎo)者的策略,然后選擇能夠最大化其收益的策略進(jìn)行博弈.因?yàn)楸疚闹饕P(guān)注Stackelberg博弈在安全領(lǐng)域中的應(yīng)用,在這些領(lǐng)域中,領(lǐng)導(dǎo)者試圖保護(hù)一些目標(biāo)免受潛在的攻擊.所以,術(shù)語“保護(hù)者”和“領(lǐng)導(dǎo)者”,以及“攻擊者”和“跟隨者”分別可以互換使用.為了表達(dá)的簡單,我們也經(jīng)常把領(lǐng)導(dǎo)者(保護(hù)者)稱為“她”,而把跟隨者(攻擊者)稱為“他”.

在Stackelberg博弈中,領(lǐng)導(dǎo)者因?yàn)槭紫茸龀霾呗赃x擇,而可以獲得較多的利益,這經(jīng)常被稱為“先行者優(yōu)勢”.利用文獻(xiàn)[3]中給出的一個簡單的收益矩陣來解釋這種優(yōu)勢,如圖1所示.

圖1 Stackelberg博弈收益矩陣舉例

領(lǐng)導(dǎo)者是行參與者,跟隨者是列參與者.這個博弈唯一的純策略納什均衡是領(lǐng)導(dǎo)者選擇a策略而跟隨者選擇c策略,這樣領(lǐng)導(dǎo)者得到的收益是2.但是實(shí)際上,對于領(lǐng)導(dǎo)者來說,b策略是嚴(yán)格占優(yōu)策略.所以,如果領(lǐng)導(dǎo)者可以先行確定自己選擇b策略,跟隨者為了使自己獲得更高的收益會選擇d策略,從而使得領(lǐng)導(dǎo)者得到3的收益.進(jìn)一步,如果領(lǐng)導(dǎo)者可以先行確定選擇a和b各為0.5的混合策略,跟隨者仍然會選擇d策略,從而可以使得領(lǐng)導(dǎo)者得到更高的3.5的期望收益1在這類博弈中,我們經(jīng)常假設(shè)當(dāng)對于跟隨者來說兩個純策略帶來的收益相同時,他會選擇對領(lǐng)導(dǎo)者更有利的策略來打破僵局,否則,最優(yōu)策略的概念將無法很明確的定義,這個我們會在后面介紹強(qiáng)Stackelberg均衡時,詳細(xì)介紹..下面,我們給出Stackelberg博弈更一般化的定義.領(lǐng)導(dǎo)者(保護(hù)者/安全部門)用Θ來表示,跟隨者(攻擊者)用Ψ來表示.每個參與者有一個純策略集,領(lǐng)導(dǎo)者的純策略集用,跟隨者的純策略集用來表示.混合策略是定義在參與者純策略集上的概率分布,x∈X表示領(lǐng)導(dǎo)者的混合策略,q∈Q表示跟隨者的混合策P略.這里,xi∈[0,1]表示領(lǐng)導(dǎo)者使用純策略θi∈Θ的概率P,類似的,qi∈[0,1]表示跟隨者使用純策略ψi∈Ψ的概率.我們用SΘ來表示領(lǐng)導(dǎo)者純策略的索引集,SΨ表示跟隨者純策略的索引集.所有可能的純策略組合下,領(lǐng)導(dǎo)者和跟隨者的收益分別定義為:

給定領(lǐng)導(dǎo)者的混合策略x∈X和跟隨者的混合策略q∈Q,可以將上面純策略的收益函數(shù)拓展到混合策略的形式,分別定義為:

1.2 貝葉斯Stackelberg博弈

Stackelberg博弈的每個參與者(領(lǐng)導(dǎo)者或者跟隨者)都可以拓展成有多種可能的類型,每種類型的收益值不同,這樣就成了貝葉斯Stackelberg博弈.在安全領(lǐng)域中,通常假設(shè)保護(hù)者(領(lǐng)導(dǎo)者)Θ的類型是確定的.而攻擊者(跟隨者)可能是多種類型中的一種,用γ∈Γ來表示.比如,安全部門面臨潛在的攻擊者可能是恐怖襲擊分子,也可能是毒品走私者.每種類型用一個不同的而且很可能是不相關(guān)的收益矩陣來表示.也就是說,面對不同類型的攻擊者時,領(lǐng)導(dǎo)者和跟隨者的收益都是變化的.領(lǐng)導(dǎo)者不知道在某一確定的時刻他所面對的跟隨者是哪種類型的,但是,她知道各種類型的攻擊者出現(xiàn)的可能性.我們用pγ來表示一種特定的類型的跟隨者γ∈Γ出現(xiàn)的概率.跟隨者知道自己屬于哪種類型,所以他總是對領(lǐng)導(dǎo)者和他自己的收益具有完全信息.在這種情況下,領(lǐng)導(dǎo)者和跟隨者的純策略集還是不變的(分別是和),所以對于每種跟隨者的類型,所有可能的純策略組合下,領(lǐng)導(dǎo)者和跟隨者的收益定義為:

另外,每種跟隨者類型γ∈Γ的混合策略用qγ∈Q來表示.相應(yīng)地,對于給定的跟隨者類型γ∈Γ,領(lǐng)導(dǎo)者的混合策略x∈X和跟隨者的混合策略qγ∈Q,領(lǐng)導(dǎo)者和追隨者的期望收益分別定義為:

在這種形式化的模型中,領(lǐng)導(dǎo)者的目標(biāo)是在考慮到所有可能的跟隨者類型都會選擇最佳響應(yīng)的情況下,選擇一種能夠最大化她的期望收益的混合策略x∈X.這樣,每種跟隨者都選擇在對應(yīng)的收益矩陣下,對這個領(lǐng)導(dǎo)者的混合策略的最佳響應(yīng)策略.我們定義所有跟隨者類型的最佳響應(yīng)組合如下:

這樣,Stackelberg博弈中描述的“首先領(lǐng)導(dǎo)者承諾使用某一混合策略,然后每個跟隨者觀察這一策略,之后選擇最佳響應(yīng)”的場景可以很好地刻畫安全領(lǐng)域中安全部門所遇到的問題.安全部門需要首先部署好巡邏策略,對目標(biāo)進(jìn)行保護(hù).對手通過觀察監(jiān)視來知道安全部門的混合策略,然后選擇最大化自己期望收益的目標(biāo)進(jìn)行攻擊.攻擊者雖然知道安全部門的混合策略,但是他仍然不知道他將要實(shí)施攻擊的那一天,安全部門到底采用哪種巡邏方案.在Stackelberg博弈中,領(lǐng)導(dǎo)者是否能夠獲得先動者優(yōu)勢,有一個非常重要的因素是,是否允許采用混合策略.如果領(lǐng)導(dǎo)者只能采用純策略,那么先動者可能得到更高的收益也可能得到更壞的收益.例如,在石頭剪刀布博弈中,先動者不管承諾采用哪種純策略都肯定會失敗.但是如果先動者可以選擇混合策略,那么先動者得到的收益至少不會比同時行動時差.Letchford等人[9],給出了不同類型的博弈下先動者優(yōu)勢的詳細(xì)討論.

1.3 強(qiáng)Stackelberg均衡

博弈論中,最常見的解概念是Nash均衡.在這個均衡的策略組合下,任何一個參與者不能通過單方面改變策略來增加自己的收益[10].Stackelberg均衡是在Stackelberg博弈中Nash均衡概念的一種精煉.它是一種子博弈完美均衡.在這個均衡下,每個參與者在原博弈的每個子博弈中都會選擇最佳響應(yīng).這樣可以在均衡路徑中把只有在不可信威脅下存在的均衡策略組合消除.子博弈完美均衡是一種很自然的要求,但是當(dāng)多個策略對于跟隨者來說沒有區(qū)別時,這個概念沒法保證有唯一解.為了得到唯一解,Leitmann[11]提出了兩種Stackelberg均衡的概念,之后被Breton等人[12]分別命名為“強(qiáng)Stackelberg均衡”和“弱Stackelberg均衡”.當(dāng)跟隨者在多個策略下收益相同時,在強(qiáng)均衡的情況下,假設(shè)他總是選擇對領(lǐng)導(dǎo)者最有利的策略;而在弱均衡的情況下,假設(shè)他總是選擇對領(lǐng)導(dǎo)者最不利的策略.強(qiáng)Stackelberg均衡在所有Stackelberg博弈中都是存在的,而弱均衡不一定存在[12].Von Stengel和Zamir[13]指出領(lǐng)導(dǎo)者經(jīng)常能夠通過選擇無限接近于均衡解的策略使得跟隨者傾向于選擇對她有利的策略,從而達(dá)到她更想要的強(qiáng)均衡.所以在大多數(shù)安全博弈的文獻(xiàn)中,我們采用強(qiáng)Stackelberg均衡作為解的概念.下面給出強(qiáng)Stackelberg均衡的定義.

定義1.一個策略組合為強(qiáng)Stackelberg均衡,當(dāng)且僅當(dāng)它滿足以下條件:

1)領(lǐng)導(dǎo)者策略為最佳響應(yīng):

2)跟隨者策略為最佳響應(yīng):

3)當(dāng)跟隨者存在多個最佳響應(yīng)時,跟隨者選擇對領(lǐng)導(dǎo)者有利的策略來打破僵局:

其中,Q?(x)是當(dāng)領(lǐng)導(dǎo)者的策略為x時,跟隨者的最佳響應(yīng)集合.

1.4 Stackelberg安全博弈

本文,關(guān)注的是一類特殊的安全領(lǐng)域的貝葉斯Stackelberg博弈,我們稱之為安全博弈.為了能夠讓讀者更直觀地理解安全博弈論的模型和求解思路,首先簡單描述洛杉磯警方(LAWA)決定什么時候在哪條通往洛杉磯機(jī)場(LAX)的道路上設(shè)置車輛檢查站中遇到的安全問題場景,然后介紹將這個問題建模成貝葉斯Stackelberg博弈的方法.

在洛杉磯機(jī)場,有特定數(shù)量的道路可以通往機(jī)場.恐怖分子可能會駕駛帶有爆炸物品的汽車通過某一條道路進(jìn)入機(jī)場,對機(jī)場實(shí)施恐怖襲擊.洛杉磯警方可以通過在這些道路上設(shè)置車輛檢查站來防止這種攻擊.但是他們遇到的問題是,一方面沒有足夠的警力資源同時在所有的道路上設(shè)置檢查站,另一方面因?yàn)槁每偷牧髁刻?如果對所有旅客都進(jìn)行篩查會花費(fèi)非常長的時間從而造成旅客的延誤.所以警方需要制定一個應(yīng)該什么時間和地點(diǎn)設(shè)置檢查點(diǎn)來檢查駛往機(jī)場的車輛的方案.洛杉磯警方要求在設(shè)計方案時要考慮到以下3個方面:1)潛在的襲擊者會觀察到警方的調(diào)度方案然后再確定他們的攻擊策略,這樣會使得確定性的調(diào)度方案非常容易被攻擊;2)警方對可能遇到的對手的信息是未知的或者不確定的;3)在隨機(jī)化的同時,還要考慮不同的保護(hù)目標(biāo)可能帶來的成本和收益的差別.令T={t1,···,tn}為n個需要保護(hù)的目標(biāo)組成的集合(比如通往機(jī)場的道路的數(shù)量).保護(hù)者有可能用一些資源來保護(hù)這些目標(biāo)(比如,警方可以同時設(shè)置檢查點(diǎn)的個數(shù)),用R={r1,···,rm}來表示.假設(shè)警方有兩個資源(可以同時設(shè)置兩個車輛檢查站),則警方的純策略的集合為P={(t1,t2),(t1,t3),···,(tn?1,tn)}, 也就是在n個保護(hù)目標(biāo)中選出兩個的所有組合.假設(shè)可能面臨的攻擊者類型的數(shù)量為k.每一種攻擊者類型γ∈Γ可以選擇在n個目標(biāo)中選擇任何一個進(jìn)行攻擊,或者選擇根本不進(jìn)行攻擊,所以攻擊者的純策略集合為PΨ={t1,···,tn,none}.

當(dāng)目標(biāo)ti沒有被保護(hù)而受到類型為γ的攻擊者攻擊時,保護(hù)者的收益用表示,攻擊者的收益用表示.類似地,當(dāng)該目標(biāo)被保護(hù)著而受到攻擊時,保護(hù)者的收益用表示,攻擊者的收益用表示.在具體的安全領(lǐng)域問題中,這些收益值可以由領(lǐng)域?qū)＜襾斫o出.但是,通常這些收益值之間需要滿足和.也就是說,對于同一個目標(biāo)ti,對于任意一個攻擊者類型γ,當(dāng)該目標(biāo)沒有被保護(hù)時,攻擊者進(jìn)行攻擊得到收益要比該目標(biāo)被保護(hù)時進(jìn)行攻擊得到的收益高,而對于保護(hù)者恰恰相反.這個性質(zhì)對于安全領(lǐng)域的問題通常是普遍適用的.這個要求類似于零和博弈的條件,但是比零和博弈的條件更寬松.Powell[14]給出了一些這種博弈通常不是零和博弈的原因.因?yàn)樵诎踩I(lǐng)域中,恐怖分子可能因?yàn)橐恍┨厥獾恼我蛩卣J(rèn)為某些特定的目標(biāo)特別重要,而這些目標(biāo)在警方眼里并不是特別重要;又比如,恐怖分子有時候可能認(rèn)為即使是一個失敗的攻擊也能給他帶來一定的收益,因?yàn)楣魩淼囊恍┕姷目只?另外恐怖分子可能在對特定的目標(biāo)進(jìn)行攻擊時需要有額外的花費(fèi),而這些目標(biāo)對警方來說可能并不是特別重要.圖2給出了對于一個目標(biāo)進(jìn)行攻擊時可能產(chǎn)生的4個收益值示例.當(dāng)警方在保護(hù)該目標(biāo)時,攻擊者選擇攻擊該目標(biāo),警方得到的收益為5,而攻擊者得到的收益為?10;而如果警方?jīng)]有在保護(hù)該目標(biāo),而攻擊者選擇進(jìn)行攻擊,警方得到的收益為?20,而攻擊者得到的收益為30.

圖2 對一個目標(biāo)進(jìn)行攻擊的可能產(chǎn)生的收益值示例

有了以上這些定義,可以寫出每種攻擊者類型的標(biāo)準(zhǔn)型收益矩陣.圖3給出了一個具有兩個目標(biāo)、兩種攻擊者類型、一個保護(hù)資源的貝葉斯安全博弈的收益矩陣示例.

圖3 貝葉斯安全博弈收益矩陣示例

在圖3的表示方式中,每種攻擊者類型對應(yīng)一個收益矩陣,所以一共有k個收益矩陣,但是在最基本的貝葉斯Stackelberg博弈的求解算法(1.5中介紹的第一個算法MultiLPs)中,要求將這k個收益矩陣通過海薩尼轉(zhuǎn)換(Harsanyi transformation)變換成一個大的標(biāo)準(zhǔn)型博弈矩陣然后進(jìn)行求解.而這個變換產(chǎn)生的新的收益矩陣中,攻擊者的純策略數(shù)量是隨著攻擊者的類型指數(shù)級增長的.比如,如果在圖3的表示形式中,每個攻擊者的純策略數(shù)量為n+1,攻擊者的類型數(shù)量為k,而在經(jīng)過海薩尼轉(zhuǎn)換后得到的標(biāo)準(zhǔn)型博弈矩陣中,攻擊者的純策略數(shù)量為(n+1)k個,這樣會使得問題的求解非常復(fù)雜,所以在安全博弈的問題中,通常直接使用1.3中的緊湊型的表示方式,然后直接針對這個緊湊型的表示方式來設(shè)計求解算法,這主要是利用了安全博弈問題中一個很重要的特點(diǎn),也就是不同攻擊者類型的收益矩陣之間是相互獨(dú)立的.

實(shí)際上,即使利用1.3中的表示方式,我們還會面臨另外一個問題,也就是在這個表示方式中,如果保護(hù)者的資源數(shù)量為m,而需要保?護(hù)的￠目標(biāo)數(shù)量為k,那么保護(hù)者的純策略的數(shù)量為≈nm,所以保護(hù)者的純策略數(shù)量是隨著資源的數(shù)量指數(shù)級增長的,這會使得每個矩陣行的數(shù)量會非常大.而實(shí)際上,我們可以給出一種更加緊湊的表示方式,使得矩陣行的數(shù)量為n.這是因?yàn)樵诎踩┺牡氖找婢仃囍?還有另外一個非常重要的特點(diǎn),也就是雙方的收益只與要被攻擊的目標(biāo)是否被保護(hù)者保護(hù)有關(guān),而與攻擊目標(biāo)以外的其他目標(biāo)是否被當(dāng)前保護(hù)者的純策略所保護(hù)無關(guān).比如,當(dāng)攻擊者選擇從第一條道路進(jìn)入機(jī)場實(shí)施攻擊時,警方有沒有保護(hù)第二條或者第三條道路,不影響雙方得到的收益.下面利用這一特點(diǎn),給出一種更緊湊的安全博弈表示方式.

定義一個每個目標(biāo)被保護(hù)的概率向量C,其中每個目標(biāo)t被保護(hù)的概率為Pct.因?yàn)楸Ｗo(hù)者一共有m個資源,所以有約束m.然后t對于每種攻擊者類型γ定義一個每個目標(biāo)被攻擊的概率向量Aγ,我們P限定每個目標(biāo)t被攻擊的概率[0,1],并且[0,1].因?yàn)樵趶?qiáng)StaPckelberg均衡時,攻擊者的最優(yōu)策略為純策略.而=0P意味著攻擊者選擇的純策略為不攻擊任何目標(biāo),=1 且=1意味著攻擊者選擇的純策略為攻擊目標(biāo)ti.當(dāng)一個目標(biāo)t被類型為γ的攻擊者攻擊時,保護(hù)者的收益用式(10)中的(t,C)來表示.這樣,當(dāng)攻擊者的攻擊概率向量為Aγ時,保護(hù)者的期望收益用式(11)中的(C,Aγ)來表示.類似地,我們也可以定義攻擊者的收益(t,C)和(C,Aγ).另外在式(12)中給出另外一個有用的定義攻擊集:在給定保護(hù)概率向量C下,所有能夠給攻擊類型為γ的攻擊者帶來最大期望收益的攻擊目標(biāo)集合.

在強(qiáng)Stackelberg均衡(SSE)時,攻擊者在攻擊集中選擇最大化保護(hù)者期望收益的目標(biāo)進(jìn)行攻擊.我們用t?來表示這個最優(yōu)的目標(biāo).那么當(dāng)保護(hù)者面臨攻擊類型γ的概率為pγ時,保護(hù)者的SSE期望收益為(C)=(t?,C)×pγ,而攻擊者的期望收益為(C)=(t?,C).

1.5 幾個基本的求解算法(Baseline Solvers)

本節(jié)介紹求解Stackelberg博弈的3個基本算法,它們分別是Conitzer和Sandholm于2006年提出的MultiLPs算法[3]、Paruchuri等人于2008年提出的DOBSS算法[4]和Kiekintveld等人于2009提出的ERASER算法[15].MultipleLPs是針對標(biāo)準(zhǔn)型的Stackelberg博弈求解的最基本多項(xiàng)式時間的算法,它也可以用來求解貝葉斯Stackelberg博弈,但是需要將收益矩陣通過海薩尼轉(zhuǎn)換變成標(biāo)準(zhǔn)型的,會使得求解時間隨著追隨者類型指數(shù)級增長.DOBSS算法是針對貝葉斯Stackelberg博弈提出的一個基本求解算法,它直接對圖3形式的收益矩陣進(jìn)行求解.ERASER算法是針對貝葉斯安全博弈提出的最基本的求解算法,它直接針對1.4節(jié)中提出的最緊湊形式的貝葉斯安全博弈進(jìn)行求解.

1.5.1 MultiLPs算法

本節(jié)介紹由Conitzer和Sandholm[3]提出的求解貝葉斯Stackelberg博弈中領(lǐng)導(dǎo)者最優(yōu)策略的基準(zhǔn)算法.這個算法利用強(qiáng)Stackelberg均衡的定義,將求解領(lǐng)導(dǎo)者最優(yōu)混合策略的問題建立成以下優(yōu)化問題:

其中,=haγ?i表示所有貝葉斯跟隨者的最優(yōu)純策略,也就是每種跟隨者類型對于領(lǐng)導(dǎo)者策略的最佳響應(yīng)純策略.x?是需要求解的領(lǐng)導(dǎo)者的最優(yōu)混合策略.式(13)等價于一個多線性規(guī)劃(LP)問題.思想是枚舉所有可能的跟隨者純策略組合aΨ=haγi,其中γ∈Γ,aγ∈P對于跟隨者的每一種純策略組合求解以下線性規(guī)劃問題得到當(dāng)aΨ為跟隨者的最佳響應(yīng)時,領(lǐng)導(dǎo)者的最優(yōu)混合策略.

(2)游客出行方式更加靈活。三峽游輪旅游方式不再是主要出行方式，部分游客會趨向于選擇以更加靈活的方式在景區(qū)之間流動。以自駕游大軍及背包客為代表的游客群體正在逐漸突破傳統(tǒng)三峽旅行方式，新的旅行方式以恩施州大峽谷景區(qū)為代表，該景區(qū)將逐步成為三峽地區(qū)新的旅游輻射中心。

其中,最優(yōu)一個約束保證aΨ是跟隨者的最佳響應(yīng).在所有的線性規(guī)劃中,有些線性規(guī)劃可能是無解的,但是總存在至少一個線性規(guī)劃有可行解.進(jìn)而,領(lǐng)導(dǎo)者的最佳混合策略x?就是在所有有可行解的LP中目標(biāo)函數(shù)值最大(也就是領(lǐng)導(dǎo)者的期望收益)的規(guī)劃所對應(yīng)的解.

1.5.2 DOBSS算法

DOBSS有效地將求解指數(shù)級的線性規(guī)劃問題減少成求解一個緊湊型的MILP問題,從而使得這個問題可以非常高效地利用運(yùn)籌學(xué)研究中提出的先進(jìn)的規(guī)劃問題求解技術(shù).DOBSS MILP的核心思想是用0～1向量aγ=[] 來表示跟隨者的純策略.其中,如果跟隨者類型γ的個體選擇第j個純策略則=1,否則為0.其中,U(x,j)表示當(dāng)領(lǐng)導(dǎo)者選擇混合策略x而跟隨者選擇他的第j個純策略時領(lǐng)導(dǎo)者的期望收益,而U(x,j)是相應(yīng)的跟隨者的期望收益.M是一個大常數(shù).

1.5.3 ERASER算法

ERASER算法的基本思想和DOBSS一樣,但是它直接對緊湊型的安全博弈進(jìn)行求解.這樣,它就可以避免枚舉指數(shù)級的保護(hù)者的純策略.ERASER的MILP如下所示:其中,保護(hù)者的策略用1.4節(jié)中定義的向量C來表示.和在DOBSS中一樣,攻擊者類型γ的策略為aγ.(C,t)和(C,t)分別表示當(dāng)保護(hù)者的策略向量為C,而攻擊者類型γ的個體選擇攻擊目標(biāo)t時,保護(hù)者和攻擊者的期望收益.R表示保護(hù)者擁有的資源的數(shù)量,M是一個大常數(shù).

2 安全博弈論的實(shí)際應(yīng)用系統(tǒng)和新興的應(yīng)用方向

安全博弈論是一個以實(shí)際應(yīng)用為導(dǎo)向的研究領(lǐng)域.過去幾年,基于Stackelberg安全博弈框架設(shè)計的實(shí)際應(yīng)用系統(tǒng)已經(jīng)被美國不同領(lǐng)域的安全機(jī)構(gòu)所使用,并且嘗試應(yīng)用到其他更多安全領(lǐng)域中.這些具體的實(shí)際應(yīng)用場景為安全博弈論的研究提出了很多挑戰(zhàn),本節(jié)介紹安全博弈論的實(shí)際應(yīng)用系統(tǒng)和一些新興的應(yīng)用方向,為后文討論算法研究進(jìn)展和新的研究挑戰(zhàn)提供問題場景.

2.1 ARMOR-機(jī)場檢查站的設(shè)置及巡邏調(diào)度系統(tǒng)

洛杉磯國際機(jī)場(LAX)是美國最大的目的地機(jī)場,每年的旅客流量在6000到7000萬左右,因此也成為美國西海岸主要的恐怖襲擊目標(biāo)之一,過去幾年已經(jīng)有多名密謀襲擊者被抓獲.洛杉磯警方采取不同的措施來保護(hù)機(jī)場,包括設(shè)置車輛檢查站、警察部隊(duì)(和警犬)在航站樓巡邏,安全篩選和檢查乘客行李.

但是他們遇到的問題是,一方面沒有足夠的警力資源來全天候?qū)C(jī)場發(fā)生的每件事情進(jìn)行監(jiān)控,另一方面因?yàn)槁每偷牧髁刻?如果對所有旅客都進(jìn)行篩查會花費(fèi)非常長的時間從而造成旅客的延誤.所以洛杉磯警方必須要采取一些措施進(jìn)行抽檢.如果他們按照確定的計劃設(shè)置車輛檢查點(diǎn)以及警察部隊(duì)和警犬的巡邏,恐怖分子可以通過觀察輕易地知道警方的計劃,然后規(guī)避開檢查點(diǎn)和巡邏路線實(shí)施攻擊,使得警方的計劃失效,所以警方需要采用隨機(jī)化的策略.洛杉磯警方在制定隨機(jī)化的安保策略時主要需要解決以下兩個問題.第一個是考慮到有非常多的道路可以通往機(jī)場,應(yīng)該什么時間在什么地點(diǎn)設(shè)置檢查點(diǎn)來檢查駛往機(jī)場的車輛.圖4(a)是在機(jī)場的一個入站口設(shè)置的車輛檢查點(diǎn)的例子.警察檢查經(jīng)過的車輛,當(dāng)發(fā)現(xiàn)可疑車輛時,警方將對其進(jìn)行更加詳細(xì)的檢查.洛杉磯警方希望得到一個特定時間段的車輛檢查點(diǎn)隨機(jī)設(shè)置方案.比如,如果一共有3條路可以通往機(jī)場,而同一時間段只能設(shè)置兩個車輛檢查點(diǎn),那么一個可能的設(shè)置方案是周一在入口1和入口2設(shè)置車輛檢查點(diǎn),周二在入口1和入口3設(shè)置檢查點(diǎn),等等.第二個問題是制定警犬在洛杉磯國際機(jī)場8個航站樓之間的巡邏路線.比如如果有3只警犬,一種可能的分配方案是第一天將警犬分別安排在1,3,6航站樓,第二天安排在2,4,6航站樓等.因?yàn)槁迳即墖H機(jī)場目前擁有的8個航站樓有不同的特性,如大小、載客量、客流量、國際與國內(nèi)航班數(shù)量.這些因素導(dǎo)致8個航站樓有不同的風(fēng)險評估結(jié)果,所以安排巡邏方案的時候就要考慮到這些因素.圖4(b)是洛杉磯機(jī)場警犬巡邏的一個例子.

圖4 洛杉磯國際機(jī)場安全問題[16]

考慮到面臨的以上實(shí)際問題,洛杉磯警方要求在設(shè)計方案是要考慮到以下3個挑戰(zhàn):1)潛在的襲擊者會觀察到警方的調(diào)度方案,然后再確定他們的攻擊策略,這樣會使得確定性的調(diào)度方案非常容易被攻擊;2)警方對可能遇到的對手的信息是未知的或者不確定的;3)在隨機(jī)化的同時,還要考慮不同的保護(hù)目標(biāo)可能帶來的成本和收益的差別.基于貝葉斯Stackelberg博弈論的ARMOR系統(tǒng)(Assistant for Randomized Monitoring over Routes)用于規(guī)劃洛杉磯國際機(jī)場檢查點(diǎn)的設(shè)置以及警犬的巡邏路線.以設(shè)置檢查點(diǎn)為例,假設(shè)洛杉磯國際機(jī)場有n條進(jìn)入機(jī)場的道路,警方在這n條道路上設(shè)置m(m

2.2 IRIS-空中警察調(diào)度系統(tǒng)

美國聯(lián)邦空中警察署(FAMS)負(fù)責(zé)將空中警察分配到始發(fā)地美國的航班上,以阻止?jié)撛诘墓?每架飛機(jī)具有不同的重要性,由于飛機(jī)上的乘客數(shù)量,地點(diǎn)和目的地城市的人口數(shù)量,來自不同國家的國際航班,還有其他一些特殊事件等原因,空中警察的分配問題比ARMOR系統(tǒng)更具挑戰(zhàn):他們每天需要將數(shù)量有限的空中警察分配給成千上萬的商業(yè)航班,空中警察的分配必須遵守各種類型的限制條件,如每一名空中警察需要飛回其基地,并滿足起飛、降落、休息等很多時間上的約束.找出滿足所有限制條件的,并考慮每架飛機(jī)的不同重要性的最優(yōu)隨機(jī)調(diào)度策略是一項(xiàng)非常困難的任務(wù).在此背景下,TEAMCORE研究小組開發(fā)了IRIS系統(tǒng)(Intelligent Randomization In Scheduling),并于2009年10月開始為所有國際航班的空中警察進(jìn)行調(diào)度[6].

在IRIS系統(tǒng)中,保護(hù)目標(biāo)為n個航班的集合,攻擊者可以從這n架航班中選擇任何一架進(jìn)行攻擊.FAMS可以將m

2.3 PROTECT-海岸警衛(wèi)隊(duì)巡邏系統(tǒng)

美國海岸警衛(wèi)隊(duì)(USCG)的任務(wù)包括維持海上安全、港口安全以及內(nèi)河航道的安全.由于恐怖主義和毒品走私的威脅,這些地方面臨的風(fēng)險日益增加.美國海岸警衛(wèi)隊(duì)通過巡邏的方式來保護(hù)港口的基礎(chǔ)設(shè)施.然而,有限的安全資源使海岸警衛(wèi)隊(duì)無法隨時隨地保護(hù)所有重要設(shè)施,攻擊者便有了可乘之機(jī).為了協(xié)助美國海岸警衛(wèi)隊(duì)的資源分配,TEAMCORE研究小組設(shè)計了基于Stackelberg博弈模型的PROTECT系統(tǒng)(Port Resilience Operational/Tactical Enforcement to Combat Terrorism)[18?20].

開發(fā)PROTECT系統(tǒng)的目的是幫助美國海岸警衛(wèi)隊(duì)在執(zhí)行保護(hù)港口、水路、和海岸安全(合稱PWCS)時提高效率.對PWCS的巡邏著眼于保護(hù)重點(diǎn)設(shè)施,由于資源所限,任何設(shè)施都無法獲得全天候的保護(hù),因此對資源配置的優(yōu)化就變得至關(guān)重要.PROTECT系統(tǒng)同時考慮攻擊者的觀測能力和不同設(shè)施的價值,輸出美國海岸警衛(wèi)隊(duì)巡邏的日程表,包括什么時候開始巡邏,每次巡邏經(jīng)過哪些目標(biāo)區(qū)域,以及在每個目標(biāo)區(qū)域里執(zhí)行的巡邏活動.

和之前的系統(tǒng)相比,PROTECT系統(tǒng)有很多創(chuàng)新點(diǎn).首先,它不像以前的系統(tǒng)那樣假設(shè)攻擊者是完全理性的,而是基于行為經(jīng)濟(jì)學(xué)中的隨機(jī)最優(yōu)選擇(quantal response)理論對攻擊者的行為進(jìn)行建模;第二,為了提高效率,系統(tǒng)在尋找均衡和最優(yōu)解時采取了更加緊湊的方式來表示攻擊者的策略空間;第三,PROTECT系統(tǒng)通過真實(shí)的數(shù)據(jù)來評價其性能:1)比較人工產(chǎn)生的調(diào)度方案和PROTECT系統(tǒng)產(chǎn)生的調(diào)度方案在實(shí)際應(yīng)用中的效果;2)利用真人實(shí)戰(zhàn)演習(xí)對系統(tǒng)進(jìn)行攻擊,并分析結(jié)果數(shù)據(jù).PROTECT模型已經(jīng)部署在波士頓、紐約、洛杉磯的港口,并且可能被更多的美國港口采用[21?22].PROTECT系統(tǒng)除了用來保護(hù)港口外,還被用于紐約史泰登島的渡輪保護(hù).在這個問題中,需要利用救生船對目標(biāo)區(qū)域進(jìn)行巡邏來保護(hù)載有乘客的擺渡船.面臨的主要挑戰(zhàn)是被保護(hù)的目標(biāo)(擺渡船)是在連續(xù)的空間中不斷移動的,而攻擊者可以選擇任何時刻進(jìn)行攻擊.這種移動目標(biāo)的保護(hù)使得博弈模型變成連續(xù)策略集空間,帶來巨大的計算挑戰(zhàn).

2.4 TRUST-城市軌道交通系統(tǒng)安全系統(tǒng)

城市軌道交通系統(tǒng)面臨著多方面的安全挑戰(zhàn),包括防止逃票,阻止非法交易和打擊恐怖襲擊.特別地,在一些城市的軌道交通系統(tǒng)中(比如,洛杉磯的地鐵),乘客被要求自覺購票乘車,但是沒有采取強(qiáng)制措施.警方會在地鐵站中進(jìn)行巡邏,抽查行人的車票,如果遇到逃票的乘客將給予罰款.這樣一種信用乘車的方式可能會面臨由于嚴(yán)重逃票帶來的經(jīng)濟(jì)損失.以洛杉磯地鐵為例,它每天運(yùn)送約30萬乘客,每年逃票帶來的損失預(yù)計為560萬美元.洛杉磯警察局(LASD)雇傭一些工作人員在列車上或者站臺上檢票.由于巡邏檢票的工作人員數(shù)量較少,不可能覆蓋所有的列車和站臺,因此洛杉磯警察局需要一些機(jī)制來設(shè)計檢票人員的巡邏路線.如果巡邏檢票的調(diào)度策略有比較固定的模式,那么逃票者可能會觀察到這個模式并且利用它來逃票.目前洛杉磯警察局依賴人工制定巡邏日程,但是由于人工制定的調(diào)度策略通常有固定模式,而且日程的制定需要考慮很多復(fù)雜的因素,比如列車運(yùn)行時間、發(fā)車間隔、日程長度等,因此制定調(diào)度策略的人工負(fù)擔(dān)很重.

TRUST系統(tǒng)將地鐵系統(tǒng)巡邏問題抽象成領(lǐng)導(dǎo)者-跟隨者的Stackelberg博弈.領(lǐng)導(dǎo)者(洛杉磯警察局)采用混合策略,跟隨者(可能逃票的乘客)觀察到這個策略并決定是否買票.由于運(yùn)輸系統(tǒng)的復(fù)雜性使得可能的巡邏策略數(shù)量呈指數(shù)級增長,這給計算最優(yōu)巡邏策略提出了很大挑戰(zhàn).為了解決此問題,TRUST使用了緊湊的表達(dá)方式,同時考慮到了時間和空間結(jié)構(gòu)[23].洛杉磯警察局目前正在洛杉磯地鐵上測試TRUST系統(tǒng),計劃根據(jù)系統(tǒng)產(chǎn)生的日程來安排巡邏,并檢測收入是否增長進(jìn)而確定逃票者是否減少.在對這個系統(tǒng)進(jìn)行測試的過程中,遇到的一個非常重要的挑戰(zhàn)是在實(shí)際使用中,由系統(tǒng)產(chǎn)生的巡邏方案經(jīng)常會被干擾打斷.這些干擾來自于,警察在巡邏過程中經(jīng)常被迷路的旅客要求幫助他找到要去的地方,有些時候,警察還會在巡邏過程中遇到其他一些突發(fā)事件需要處理.這要求系統(tǒng)能夠在遇到這種干擾之后動態(tài)地產(chǎn)生新的巡邏方案.

另外一個挑戰(zhàn)來自于,在地鐵站等場所經(jīng)常發(fā)生偷盜,非法交易等犯罪事件.與策略式的恐怖襲擊不同,犯罪通常是機(jī)會性的,犯罪分子會在交通系統(tǒng)中隨機(jī)移動,發(fā)現(xiàn)合適的作案時機(jī)實(shí)施犯罪.所以如何有效地抑制這種犯罪是一個很有挑戰(zhàn)的任務(wù).這是一個數(shù)據(jù)密集的領(lǐng)域,可以采用數(shù)據(jù)挖掘工具分析以前犯罪案件的數(shù)據(jù),得出犯罪案件經(jīng)常發(fā)生的地點(diǎn)、犯罪行為的變化趨勢以及可能發(fā)生的犯罪類型.希望通過發(fā)掘犯罪活動的時空模式,最優(yōu)地安排有限的安全資源.同時,這會使得地鐵的巡邏成為一個多個目標(biāo)的優(yōu)化問題,這也是一個新的研究挑戰(zhàn).

2.5 GUARDS-全國范圍航空保護(hù)系統(tǒng)

美國運(yùn)輸安全管理局(US Transportation Security Administration(TSA))負(fù)責(zé)保護(hù)美國400多個機(jī)場的安全.這些機(jī)場每天需要服務(wù)28000架民航客機(jī)和總共大約87000架飛機(jī).為了保護(hù)如此龐大的交通網(wǎng)絡(luò),TSA雇傭了接近48000名交通安全人員.這些安全人員需要執(zhí)行各種各樣的安全措施來保護(hù)每個機(jī)場的安全.除了我們都知道的一些常見的安全措施,如行人安全檢查,TSA還需要用這些有限的人員來執(zhí)行其他上百種不同的安全保護(hù)措施來保護(hù)機(jī)場安全,這使得這個問題成為非常復(fù)雜的資源分配問題.另外,TSA不能產(chǎn)生一種最優(yōu)的保護(hù)策略直接應(yīng)用在所有的機(jī)場上,因?yàn)槊總€機(jī)場是不同的,需要有自己特定的保護(hù)策略,而同時TSA還需要在各個機(jī)場之間設(shè)定一個通用的標(biāo)準(zhǔn)來協(xié)調(diào)各機(jī)場之間的保護(hù)策略.

為了幫助TSA調(diào)度資源來更好地保護(hù)機(jī)場,TEAMCORE團(tuán)隊(duì)開發(fā)了一個新的全國范圍航空保護(hù)的應(yīng)用系統(tǒng)GUARDS(Game-theoretic Unpredictable and Randomly Deployed Security).考慮到之前的應(yīng)用都是只用在一個位置,GUARDS系統(tǒng)主要面臨3個新的挑戰(zhàn):1)這個系統(tǒng)需要考慮到上百種不同的安全保護(hù)措施;2)需要考慮到多種潛在的威脅,這使得攻擊者的類型數(shù)大量增加;3)因?yàn)橛薪咏?00個終端用戶,所以不可能為每個機(jī)場設(shè)計一個系統(tǒng),需要上百個終端用戶設(shè)計用戶友好的系統(tǒng),可以讓用戶能夠很容易地輸入自己特有的信息,從而產(chǎn)生出適合各自機(jī)場特有的安全保護(hù)策略.GUARDS系統(tǒng)目前正在一個機(jī)密的機(jī)場接受評估和測試[24?25].

2.6 新興的應(yīng)用方向

除了上面提到的這些已經(jīng)成功應(yīng)用的系統(tǒng)之外,最近幾年還涌現(xiàn)出了一些新的應(yīng)用方向.

2.6.1 網(wǎng)絡(luò)領(lǐng)域的新興應(yīng)用方向

一個主要的領(lǐng)域是保護(hù)大規(guī)模的城市網(wǎng)絡(luò),如交通網(wǎng)絡(luò)、計算機(jī)網(wǎng)絡(luò)、電力網(wǎng)絡(luò)[26]和其他一些可以用網(wǎng)絡(luò)來建模的領(lǐng)域.比如,在2008年孟買恐怖襲擊之后,孟買警方開始在城市的道路上設(shè)置一些車輛檢查站.Tsai等人[27]將這一問題建模成城市道路網(wǎng)絡(luò)上孟買警方和攻擊者之間的安全博弈問題.在這個城市安全博弈中,保護(hù)者的純策略是將保護(hù)資源部署在網(wǎng)絡(luò)的一些邊上,比如,選擇城市網(wǎng)絡(luò)中的一些道路來布置車輛檢查點(diǎn).而攻擊者的純策略是選擇網(wǎng)絡(luò)上一條從源點(diǎn)到目標(biāo)點(diǎn)之間的路徑,比如從港口登陸點(diǎn)到城市中的一個重要建筑.保護(hù)者的策略集空間隨著可用的資源數(shù)量指數(shù)級增長,而攻擊者的策略集空間隨著網(wǎng)絡(luò)的規(guī)模指數(shù)級增長.為了解決這種大規(guī)模的問題,需要設(shè)計新的算法來為孟買城市網(wǎng)絡(luò)這種250多個點(diǎn)和600多條邊組成的城市道路網(wǎng)絡(luò)來生成隨機(jī)化的資源調(diào)度方案.

Stackelberg安全博弈模型同樣可以被應(yīng)用在一些參與者表現(xiàn)出“傳染”行為的對抗性領(lǐng)域.例如,營銷人員研究了以口相傳的廣告/病毒市場,試圖理解為什么有些產(chǎn)品像病毒一樣傳播,有些卻不被注意[28].鎮(zhèn)壓叛亂是在武裝沖突中爭取當(dāng)?shù)仡I(lǐng)導(dǎo)者支持的斗爭,包括提供安保和給予醫(yī)藥支持等行為.電力網(wǎng)絡(luò)中保護(hù)者需要為一些電站設(shè)置冗余來防止由于恐怖襲擊或者天災(zāi)導(dǎo)致的級聯(lián)故障[26].就像以口相傳的廣告或者維和行為一樣,這些行為通過鄰里間傳播會產(chǎn)生巨大的社會影響.現(xiàn)實(shí)中可能存在多個參與方試圖通過某些策略影響同一個社會網(wǎng)絡(luò).例如一個參與者試圖傳播影響,另一個參與者通過傳播自己的影響來阻止第一個參與者影響的擴(kuò)張.這個“阻塞”問題描述了政府或維和者面臨的情形:通過每天/每周/每月為當(dāng)?shù)氐念I(lǐng)導(dǎo)者提供支持來阻止恐怖分子的激進(jìn)主義和武裝沖突的擴(kuò)張.安全博弈論可以分析這種大規(guī)模的網(wǎng)絡(luò)對抗中的資源分配策略.

安全博弈模型的方法同樣可以用于網(wǎng)絡(luò)安全的資源配置,比如包選擇或在大規(guī)模網(wǎng)絡(luò)中檢測可能的危險.隨著網(wǎng)絡(luò)攻擊的復(fù)雜程度以及預(yù)防網(wǎng)絡(luò)攻擊成本的持續(xù)上升,計算機(jī)系統(tǒng)和企業(yè)的計算機(jī)網(wǎng)絡(luò)面臨的壓力也逐年上升.許多新型檢測系統(tǒng)和監(jiān)管系統(tǒng)正在研發(fā)中,例如深度檢測包的方法或者周期性選擇網(wǎng)絡(luò)包的一個子集進(jìn)行探測分析方法等.攻擊/檢測問題可以被建模為一個兩方參與的博弈:攻擊者(闖入者)和防守者(檢測系統(tǒng)).攻擊者希望通過掃描網(wǎng)絡(luò)獲得網(wǎng)絡(luò)中重要機(jī)器的控制權(quán)(或者破壞這臺重要的機(jī)器),侵入到更加脆弱的系統(tǒng),獲得計算機(jī)網(wǎng)絡(luò)更多設(shè)備的操作權(quán).攻擊者的行為可以看作是通過一臺受控的機(jī)器(稱作源)向一個或多個脆弱的機(jī)器(稱作目標(biāo))發(fā)送惡意包.防守者的目標(biāo)是通過選擇一些包進(jìn)行檢測,識別出攻擊者,從而阻止攻擊.然而,由于包檢測會造成網(wǎng)絡(luò)延遲,防守者需要決定何時何地去檢測網(wǎng)絡(luò)使得對惡意包的檢測成功率最高.計算設(shè)計的挑戰(zhàn)主要包括如何有效地計算出最優(yōu)的防御策略.

2.6.2 保護(hù)自然資源領(lǐng)域的新興應(yīng)用方向

另外一類新的應(yīng)用方向是防止與環(huán)境自然資源相關(guān)的犯罪行為.第一個這類應(yīng)用是保護(hù)森林資源免受亂砍亂伐[29].在這種場景中,巡邏者需要保護(hù)一大片連續(xù)的地域以防止不法分子的砍伐.可是往往由于巡邏警察的數(shù)量不足,導(dǎo)致需要精心巡邏策略:如何進(jìn)行巡邏分布、巡邏的時間和地點(diǎn)、如何使違法砍伐最少、如何對森林的保護(hù)最大化.這個問題可以建模成一個Stackelberg博弈問題,著眼于求解巡邏密度的分配.

另外一個這類應(yīng)用是保護(hù)瀕危物種[30].瀕危物種的偷獵使得很多物種已經(jīng)達(dá)到不可持續(xù)發(fā)展的數(shù)量.比如,全球老虎的數(shù)量已經(jīng)比1900年減少了95%,導(dǎo)致9種虎群中的3種已經(jīng)完全滅絕.這些偷獵行為的主要動機(jī)是老虎、大象和犀牛等物種有很多的經(jīng)濟(jì)利益.為了防止這種行為,各個國家都建立了野生動物保護(hù)機(jī)構(gòu),但是相對于需要巡邏的區(qū)域來說,保護(hù)力量資源是遠(yuǎn)遠(yuǎn)不夠的.

另外一個這類應(yīng)用是保護(hù)海洋的漁類資源[31].海洋魚類是很多國家的重要食物來源.據(jù)世界自然基金會報告,過度捕撈導(dǎo)致英國、加拿大和其他近大西洋國家的鱈魚的數(shù)量已經(jīng)瀕臨危險.過去30年,全球鱈魚的數(shù)量已經(jīng)下降了70%,如果按照這個趨勢下去,15年之后鱈魚將在地球上滅絕.非法的,沒有申報的和不合乎條例的(illegal,unreported and unregulated fi shing(IUU))捕魚行為是海洋漁業(yè)資源可持續(xù)性的重要威脅.據(jù)美國國家海洋和大氣管理局(National Oceanic and Atmospheric Administration(NOAA))估計,IUU捕魚行為每年可以制造1100～2600噸海產(chǎn)食品,在一些魚類的捕撈中,IUU捕撈能夠占到40%的份額.這背后的主要驅(qū)動力是重大的經(jīng)濟(jì)利益和低風(fēng)險.任何國家都不可能保持全天候的保護(hù)海域來防止這種捕撈行為,所以如何有效地分配巡邏資源對美國海岸警衛(wèi)隊(duì)(US Coast Guard)等類似的機(jī)構(gòu)來說是個非常有挑戰(zhàn)性的問題.這個問題的主要挑戰(zhàn)在于,警方無法確切地知道魚群的位置,所以需要通過結(jié)合歷史數(shù)據(jù)和以往抓住非法捕魚者的記錄,結(jié)合機(jī)器學(xué)習(xí)的技術(shù)和博弈論的框架來設(shè)計新的算法.

除了以上兩個新興的應(yīng)用方向之外,最近針對大規(guī)模集體事件的恐怖襲擊也日益嚴(yán)重,比如2013年的波士頓馬拉松爆炸案.Yin等人[72]研究了馬拉松比賽這類集體事件中的安保資源分配問題.這一問題的主要挑戰(zhàn)在于,隨著比賽的進(jìn)行,賽段上不同位置的人數(shù)在發(fā)生變化,比如在比賽開始時,大部分人是聚集在起點(diǎn)處的,而在比賽接近結(jié)束時,更多的人位于終點(diǎn)處.所以在不同時間點(diǎn),賽段上的不同地點(diǎn)的收益是在不斷變化的,所以需要設(shè)計一種隨著時間連續(xù)變化的保護(hù)策略。

3 算法可擴(kuò)展性研究進(jìn)展

安全博弈論的應(yīng)用給研究提出了非常多的研究挑戰(zhàn),其中,最主要的挑戰(zhàn)來自于算法的可拓展性方面.DOBSS和ERASER等基本的博弈求解算法可以很好地解決機(jī)場車輛檢查點(diǎn)的布置問題,但是隨著安全部門安全策略和安全資源的數(shù)量和恐怖分子攻擊行為種類的增加,防御者和攻擊者的策略空間都可能會呈指數(shù)級增長,潛在的攻擊者的類型也會變得很多.這種大規(guī)模的問題場景甚至無法很好地在計算機(jī)中表示出來,更不要說利用現(xiàn)有的技術(shù)來進(jìn)行求解,所以如何設(shè)計更高效的博弈求解算法來應(yīng)對問題規(guī)模的增加成為一個主要的研究挑戰(zhàn).

在上文提到的各類應(yīng)用中,這類擴(kuò)展性問題已經(jīng)被提到.在空中警察調(diào)度的領(lǐng)域中,采用的調(diào)度方案需要將數(shù)量有限的空中警察分配給成千上萬的商業(yè)航班,并且滿足每一名空中警察需要飛回其基地的同時滿足起飛、降落、休息等很多時間上的約束.這使得防御者的策略空間非常龐大,不可能完全枚舉出來;在城市反恐的領(lǐng)域中,問題更加困難,保護(hù)者的策略集空間隨著可用的資源數(shù)量指數(shù)級增長,而攻擊者的策略集空間隨著網(wǎng)絡(luò)的規(guī)模指數(shù)級增長;而在全國范圍航空保護(hù)的領(lǐng)域中,保護(hù)者要面臨上百種潛在的攻擊威脅,使得攻擊者的類型數(shù)量增加;在PRPTECT系統(tǒng)保護(hù)移動的渡輪和TRUSTS系統(tǒng)保護(hù)每輛地鐵的領(lǐng)域中,被保護(hù)的目標(biāo)(擺渡船)是在不斷移動的,而攻擊者可以選擇任何時刻進(jìn)行攻擊.這種移動目標(biāo)的保護(hù)使得博弈模型變成連續(xù)策略集空間,大大增加了問題的復(fù)雜性和求解難度.

本節(jié),我們介紹安全博弈論方向在解決大規(guī)模的實(shí)際安全領(lǐng)域問題中在模型和算法方面取得的進(jìn)展.具體的,我們主要介紹以下4個工作:1)ASPEN,它是Jain等人[17]為了解決空中警察調(diào)度領(lǐng)域中保護(hù)者策略集空間增大問題所提出的一個master-salve算法;2)RUGGED,是Jain等人[32]為了解決城市反恐領(lǐng)域中,保護(hù)者和攻擊者的策略集都是指數(shù)級的問題而提出的一個double-oracle算法;3)HBGS算法,是Jain等人[33]為了解決攻擊者類型增大而提出的一個層次化算法;4)Transition Graph,是Yin等人[8,23]為了解決保護(hù)移動目標(biāo)的領(lǐng)域中,策略集同時受到時間和空間限制而提出的一種新的緊湊型的策略表示方法.

3.1 ASPEN算法

這一節(jié),我們主要介紹ASPEN算法,它主要是為了解決2.2節(jié)中FAMS在空中警察調(diào)度領(lǐng)域遇到的保護(hù)者策略集極其大的問題.它主要利用了在很多實(shí)際博弈論問題中一個很重要的特點(diǎn),也就是雖然問題的策略集非常大,但是最優(yōu)混合策略的支撐集很小,這就是說,在最后得到的最優(yōu)混合策略中,只有很少部分的純策略概率不為0,其他非常多的純策略的概率為0.ASPEN利用了這一特點(diǎn)使用策略生成(strategy generation)的方法,每次為保護(hù)者產(chǎn)生一個純策略,加入到優(yōu)化問題中,直到迭代收斂.

在這個安全博弈問題中,攻擊者可以選擇任意一架飛機(jī)進(jìn)行攻擊,而每一個空中警察可以被分配到一個可行的排班表上.每個排班表是由一組可以被放在一起保護(hù)的可行目標(biāo)組成,對于FAMS來說,一個排班表就是滿足起飛、降落、休息等很多時間上的約束的一次巡回飛行.一個聯(lián)合排班表需要把每個空警都安排在一個這樣的巡回飛行上,所以這樣的聯(lián)合排班表是有指數(shù)量級的.而保護(hù)者的一個純策略就是一個這樣的聯(lián)合排班表.因?yàn)閷τ谌绱她嫶蟮膯栴}規(guī)模,無法做到遍歷保護(hù)者的純策略集,所以ASPEN算法對保護(hù)者使用了策略生成的方法.它將這個問題分解成了一個主(Master)問題和一個從(Slave)問題,然后反復(fù)對兩個問題進(jìn)行迭代求解,過程如算法1所示.

首先給保護(hù)者隨機(jī)生成非常少數(shù)量的純策略,然后求解由這些純策略和攻擊者的策略組成的主優(yōu)化問題,得到在這個主問題下,保護(hù)者的最優(yōu)策略,然后求解從問題,給保護(hù)者生成一條新的能夠在目前主問題的情況下最大限度增加保護(hù)者期望收益的純策略,將其加入到主問題,然后再求解新的主問題,如此反復(fù)進(jìn)行,直到無法為保護(hù)者找到新的純策略時結(jié)束.

我們可以用圖5的圖形化方式來更加形象地表示這個迭代過程.算法步驟2中的主問題對當(dāng)前已經(jīng)生成的純策略集進(jìn)行操作,圖中我們用矩陣P來表示這個策略集.矩陣P的每一列代表一條純策略,如果目標(biāo)可以被純策略保護(hù),則矩陣?yán)锩娴脑貫?,反之為0.算法步驟5中從問題的目標(biāo)產(chǎn)生一個最好的聯(lián)合排班表加入到矩陣P中.聯(lián)合排班表的好壞用它能夠?yàn)楸Ｗo(hù)者增加多少期望收益來衡量.一個最簡單的方式是枚舉所有可能的純策略來看哪一條是最好的,ASPEN算法中將其轉(zhuǎn)化為一個最小花費(fèi)網(wǎng)絡(luò)流問題從而可以高效地找到最優(yōu)的策略.ASPEN算法總是可以收斂到最優(yōu)的混合策略.

這種主從問題的思想在解決一個策略參與方的策略集非常大的問題中非常有效,Gan等人最最近發(fā)表的一篇論文[73]中利用類似的方法解決了保護(hù)資源具有外部性的情形下的安全博弈的求解問題.

3.2 RUGGED算法

在2.6.1節(jié)中給出的網(wǎng)絡(luò)領(lǐng)域的應(yīng)用方向中,保護(hù)者和攻擊者的純策略集都是指數(shù)集的.以大城市道路網(wǎng)絡(luò)中隨機(jī)車輛檢查點(diǎn)的設(shè)置的問題為例,如果是一個由20個節(jié)點(diǎn)和190條邊組成的完全圖,保護(hù)者的資源數(shù)量為5,則保護(hù)者的純策略數(shù)量約為200萬個,而攻擊者的不含回路的可能攻擊路徑數(shù)量就有大約6618條.真實(shí)的網(wǎng)絡(luò)規(guī)模更大,比如在孟買的城市網(wǎng)絡(luò)中,就有250多個點(diǎn)和600多條邊,而安全部門通?？梢栽O(shè)置數(shù)十個檢查點(diǎn).本節(jié),介紹針對這一問題場景的RUGGEN算法[32].

圖5 ASPEN算法中的策略生成過程示意圖

RUGGED將這一問題建模成一個零和博弈問題.每個潛在的攻擊目標(biāo)都有一個收益值,如果保護(hù)者選擇設(shè)置檢查點(diǎn)的邊和攻擊者選擇的攻擊路徑有交集,則攻擊失敗,攻擊者的收益為0;如果雙方?jīng)]有交集,則攻擊成功,攻擊者得到攻擊目標(biāo)對應(yīng)的收益值.而保護(hù)者和攻擊者的收益之和為零.在這種零和博弈中,強(qiáng)Stackelberg均衡和Minimax均衡是等價的.每一方都沒法通過先動得到任何優(yōu)勢.求解Minimax均衡的問題可以轉(zhuǎn)化成線性規(guī)劃問題,在多項(xiàng)式時間內(nèi)求解.但是,因?yàn)樵谶@個問題中,個體的策略集是指數(shù)集的,使得標(biāo)準(zhǔn)的求解算法沒有辦法直接應(yīng)用過來.RUGGED利用了double-oracle的思想,對兩個參與者都使用類似于ASPEN中的策略生成的思想,從而避免枚舉兩個指數(shù)級的策略集空間.

RUGGED的算法流程如上所示.X是到目前為止得到的保護(hù)者的策略集,而A是攻擊者目前位置的策略集.CoreLP(X,A)求解由X和A組成的零和博弈得到雙方的最優(yōu)混合策略x和a.保護(hù)者模塊(Defender Oracle(DO))產(chǎn)生保護(hù)者對攻擊者目前的混合策略a的最佳響應(yīng)純策略(這個最佳響應(yīng)是從保護(hù)者所有的策略集中搜索的,而不局限于X中的策略).相似的,攻擊者模塊(Attacker Oracle(AO))產(chǎn)生攻擊者的最佳響應(yīng)攻擊路徑.這樣,該算法開始給博弈雙方都隨機(jī)產(chǎn)生很少數(shù)量的純策略,然后每次迭代給每個參與者最多增加一條最佳響應(yīng)策略.當(dāng)雙方都沒法找到最佳響應(yīng)策略時,算法結(jié)束.同樣可以給出一個圖形化的示意圖來表示這個迭代過程,如圖6所示.McMahan等人[34]等人證明了這個算法對零和博弈的正確性.

RUGGED算法可以在10個小時左右的時間內(nèi)求解出由250個點(diǎn)和4個安保資源構(gòu)成的問題.這個算法還是沒法達(dá)到實(shí)際的問題規(guī)模,主要的計算復(fù)雜性在于每個oracle模塊求解最佳響應(yīng)的問題都是NP-hard問題.RUGGED算法中將這兩個問題都轉(zhuǎn)換成了混合整數(shù)線性規(guī)劃問題(MILP),但是求解的復(fù)雜性依然是很大的.在最近的一個工作中,Jain等人[35]在RUGGED算法的基礎(chǔ)上進(jìn)行了優(yōu)化,提出了一個新的算法SNARES.這個算法的改進(jìn)主要體現(xiàn)在兩方面:1)初始時不是隨機(jī)產(chǎn)生策略,而是利用一些貪婪算法產(chǎn)生一些更優(yōu)的純策略;2)在每個oracle模塊,不需要每次都求解最佳響應(yīng)問題,而是先用貪婪算法求解較佳問題嘗試找到一個比現(xiàn)在X和A中的策略更好的純策略,如果能找到就直接把這個策略返回,如果找不到再求解NP-hard的最佳響應(yīng)問題.這個算法大大提高了運(yùn)算速度,可以在合理的時間內(nèi)求解出為孟買的城市規(guī)模布置10～15個車輛檢查點(diǎn)的問題.Double-oracle的算法思想也被用到了其他網(wǎng)絡(luò)領(lǐng)域的安全問題中.如網(wǎng)絡(luò)傳播,電力網(wǎng)絡(luò)級聯(lián)故障,計算機(jī)網(wǎng)絡(luò).

圖6 RUGGED算法中的策略生成過程示意圖

3.3 HBGS算法

在安全博弈中,另外一個影響算法可拓展性的方面是攻擊者類型的數(shù)量.特別是在GUARDS系統(tǒng)面臨的安全場景中,可能面臨的安全威脅的種類非常大.而貝葉斯Stackelberg博弈的求解是一個NP-hard的問題,沒法找到O(types)級的多項(xiàng)式時間的求解算法.本節(jié)介紹Jain等人[33]提出的求解大規(guī)模的貝葉斯Stackelberg博弈的HBGS算法.該算法利用了層級化技術(shù)先將求解大的貝葉斯博弈的問題分解成求解層次化組織的更小的貝葉斯博弈,通過求解更小規(guī)模的博弈,來為求解大規(guī)模的博弈提供一些剪枝規(guī)則,使得大規(guī)模博弈的求解速度更快,從而更高效地解決問題.

求解貝葉斯Stackelberg博弈的最基本的算法是我們在1.5.1中介紹的Multi LPs算法.這個算法的求解過程可以表示成圖7(a)[33]的形式.它是一個由兩種攻擊者類型和兩個純策略組成的貝葉斯Stackelberg博弈例子,所有可能的攻擊者策略組合方式被表示成了樹的形式.這個樹的所有葉子節(jié)點(diǎn)是所有可能的攻擊者策略組合,比如葉子[1,1]表示攻擊者類型γ1和γ2都選擇純策略a1.在基本的MultiLPs算法中,每個葉子節(jié)點(diǎn)是一個線性規(guī)劃問題.為了計算最優(yōu)的保護(hù)者混合策略,這個樹的所有葉子節(jié)點(diǎn)都要被評估到,使得我們需要求解指數(shù)級數(shù)量的線性規(guī)劃,導(dǎo)致了這個問題的NP-hard性.而實(shí)際上我們可以利用分支定界法(branchand-bound)的思想對這個樹進(jìn)行搜索,而如果我們能夠?yàn)榍蠼膺@個大規(guī)模問題的分支定界過程提供一些有效的上下界和剪枝規(guī)則,從而減少線性規(guī)劃的求解數(shù)量,就可以大大提高運(yùn)算速度,甚至能夠使得MultiLPs的運(yùn)算速度比DOBSS算法還要快.

HBGS算法正是基于這點(diǎn)考慮,在求解這個大規(guī)模問題之前,先進(jìn)行預(yù)處理.如圖7(b)[33]所示,先把大規(guī)模的貝葉斯Stackelberg博弈分解成層次化組織的多個更小規(guī)模的博弈.每個更小的博弈(圖7(b)中的子節(jié)點(diǎn))只考慮更少的攻擊者類型,這樣子節(jié)點(diǎn)的計算時間比父節(jié)點(diǎn)的博弈指數(shù)級減小.比如,在圖7(b)的例子中,父節(jié)點(diǎn)的貝葉斯Stackelberg博弈有4種攻擊者類型,層次化的表示方式將它分解成4個只有一種攻擊者類型的博弈作為子節(jié)點(diǎn).這樣,子節(jié)點(diǎn)博弈的求解結(jié)果可以用來為上層的父節(jié)點(diǎn)提供剪枝規(guī)則、限制上下界和刪除到一些顯然不可行的策略組合,從而使得父節(jié)點(diǎn)的大規(guī)模的問題求解速度更快.這種層次化的技術(shù)可以有效地提高分支定界法的效率,可以和其他算法如APSEN來結(jié)合使用,從而提高大規(guī)模問題的求解速度.

3.4 緊湊的策略表示方式

在利用緊湊的策略表示方式的思想方面,一類非常重要的進(jìn)展是當(dāng)被保護(hù)目標(biāo)是移動個體時,策略的緊湊表示方式.這種情況在地鐵系統(tǒng)中,防止乘客逃票的問題和內(nèi)河河道中客輪的保護(hù)問題中都會出現(xiàn).以地鐵系統(tǒng)的情況為例,警方可以通過在地鐵站或者在地鐵車上進(jìn)行抽查來防止乘客的逃票行為.在這個問題中,需要生成的巡邏時間表是由在地鐵站進(jìn)行查票和在某輛地鐵上進(jìn)行查票行動組成的一個行動序列.每個行動需要指明一個巡邏隊(duì)在什么時間需要在什么地點(diǎn)進(jìn)行查票動作.這使得可能的巡邏時間表數(shù)量是指數(shù)級的,而且受到地鐵在不同站點(diǎn)間移動的空間和時間約束.

考慮由一條地鐵線路組成的交通系統(tǒng),有多輛車同時往返于這條線路上.這樣一個系統(tǒng)按照一個固定的時間安排來運(yùn)行,這個時間安排規(guī)定了在一天中,哪輛車在什么時間到達(dá)哪個站點(diǎn).所以,時間可以建模成連續(xù)的,只需要關(guān)注那些可能發(fā)生車輛到達(dá)/離開事件的時間點(diǎn).我們可以利用一個有向的轉(zhuǎn)移圖G=hV,Ei來表示地鐵線路一天的時間表,其中,一個節(jié)點(diǎn)由地鐵站s和時間點(diǎn)t的對組成.圖中的一條邊表示一個可能的行動.具體地說,節(jié)點(diǎn)hs,ti到節(jié)點(diǎn)hs0,t0i之間只有在滿足以下一個條件時才會有一條邊相連:1)S.是站點(diǎn)序列中地鐵站s的前一個或者后一個地鐵站,hs,ti和hs0,t0i是在某一輛地鐵的時間表上連續(xù)的兩個停車點(diǎn);2)s.=s,t

假設(shè)一共有λ個巡邏隊(duì),每個巡邏隊(duì)都可以被分配到一個不長于κ小時(比如κ=7)的巡邏任務(wù)上.每個巡邏隊(duì)都可以交互的進(jìn)行兩種巡邏行動:隨車檢查(巡邏隊(duì)在地鐵上對車上的乘客進(jìn)行檢查)和站點(diǎn)檢查(巡邏隊(duì)在站點(diǎn)上對進(jìn)入車站的旅客進(jìn)行檢查).一個巡邏純策略可以表示成圖G上的一個長度不大于κ的路徑,其中,一條邊e表示巡邏隊(duì)從邊的起點(diǎn)時刻點(diǎn)到邊的終點(diǎn)時刻點(diǎn)在一輛車上或者一個站點(diǎn)上進(jìn)行檢查.在圖8的例子中,如果κ=2而且λ=1,那么,圖中所有的長度為2的路徑都是有效的純策略,所以在這個博弈中,即使只有一個巡邏隊(duì),領(lǐng)導(dǎo)者的純策略數(shù)量也是指數(shù)級的.可以利用文獻(xiàn)[36]中類似的思想用轉(zhuǎn)移圖上每條邊的邊界覆蓋概率xe來緊湊地表示領(lǐng)導(dǎo)者的混合策略,也就是用每條邊上可能發(fā)生的檢查的期望數(shù)量.我們用表示V+?V轉(zhuǎn)移圖中所有可能的起始點(diǎn)的集合,用V??V表示所有可能的終止點(diǎn)的集合.為了表示的方便,可以給轉(zhuǎn)移圖增加一個指向所有V+中點(diǎn)的虛擬的起點(diǎn)v+和從所有V?中的點(diǎn)指向的一個虛擬的終點(diǎn)v?.由虛擬起點(diǎn)v+指出和指向虛擬終點(diǎn)v?的所有邊上的巡邏時間設(shè)置成0.這樣可以對轉(zhuǎn)移圖中的流量得到以下約束:

圖7 層次化求解貝葉斯Stackelberg博弈

圖8 轉(zhuǎn)移圖示例

第一個約束限制流入和流出轉(zhuǎn)移圖的總量為巡邏隊(duì)的總數(shù)λ,第二個約束限制了轉(zhuǎn)移圖上每個節(jié)點(diǎn)的流入量等于流出量,第三個約束限制了總共的巡邏時間為λ·κ,每條邊上的流量的理論上限為一個不大于λ的值α,也就是說每條邊上同時巡邏的警察的數(shù)量不可能超過λ.

但是在地鐵巡邏的問題中,僅僅定義每條邊上的邊界覆蓋概率xe并滿足上面幾個約束,可能會解出不可行或者沒法實(shí)際執(zhí)行的解.首先,它可能會導(dǎo)致解出的混合策略不滿足不大于κ的約束,因?yàn)榈?個約束只能約束所有巡邏隊(duì)的巡邏時間總和.比如圖9中給出的一個反例.

圖中邊v1→v2和邊v2→v3為兩個可行的巡邏動作,每個動作執(zhí)行時間為1h.巡邏必須從v1或者v3開始,但是可以在v1,v2和v3中的任意一個點(diǎn)結(jié)束,v+和v?是如上文所定義的虛擬起點(diǎn)和終點(diǎn).假設(shè)κ=1和λ=1.很容易可以檢驗(yàn)出來,這個例子滿足上面的3個約束.但是通過圖中給出的邊界覆蓋概率,我們能構(gòu)造出的唯一的混合策略是以50% 的可能性采取v+→v3→v?策略,另外50%的可能采取v+→v1→v2→v3→v?策略.這個混合策略顯然是不可行的,因?yàn)榈诙€策略的巡邏時間大于1h.這個問題出現(xiàn)的原因是在目前這種邊界概率的定義下,只能對平均的巡邏長度做約束,這樣就可能出現(xiàn)大于巡邏長度和小于巡邏長度的策略同時存在,而平均值滿足約束的情況.

其次,由滿足3個約束的邊界覆蓋概率構(gòu)造出來的混合策略可能會出現(xiàn)在不同車輛之間和隨車檢查與站點(diǎn)檢查之間頻繁交換很多次的巡邏策略,這樣的巡邏路線在實(shí)際中是不宜執(zhí)行的而且很容易出現(xiàn)錯誤.巡邏策略中的換乘次數(shù)越多,巡警在執(zhí)行的過程中就需要記住越多的指令,這也會增加巡警因?yàn)殄e過換乘導(dǎo)致策略無法執(zhí)行的可能性.比如,在圖8的例子中,hA,6PMi→hB,7PMi→hA,8PMi和hC,6PMi→hB,7PMi→hC,8PMi兩個巡邏策略每個需要一次換乘,而hA,6PMi→hB,7PMi→hC,8PMi和hC,6PMi→hB,7PMi→hA,8PMi兩個巡邏策略都不需要換乘.但是兩個策略對對應(yīng)的邊界覆蓋概率是一樣的,這時我們更希望得到第二對策略對,因?yàn)樗菀讓?shí)施.

為了解決上述提到的兩個問題,Yin Zhenyu等人[23]在點(diǎn)上加入了邊的歷史信息,構(gòu)造了一種基于歷史副本的轉(zhuǎn)移圖(HDT graph)來避免出現(xiàn)上面兩種情況.首先為了避免出現(xiàn)第一種情況,HDT圖將圖G分解成多個子圖副本,每個子圖副本對應(yīng)不同的可能起始時間點(diǎn).對應(yīng)起始時間點(diǎn)t?的子圖副本,只保留滿足t?≤t≤t?+κ的節(jié)點(diǎn)v=hs,ti∈V.這樣在每個子圖中,可以保證路徑的長度不會大于κ.同時因?yàn)榭赡艿钠鹗紩r間點(diǎn)的數(shù)量是有限的,是原來的轉(zhuǎn)移圖G的線性拓展.圖10[33]展示了如何針對圖8中的例子構(gòu)造HDT圖.在這個例子中,κ=2并且有兩個起始時間點(diǎn)6PM和7PM.所以,HDT圖由原始轉(zhuǎn)移圖的兩個受限的副本組成.在每個節(jié)點(diǎn)中,括號中的時間的意思是對應(yīng)的起始時間點(diǎn).比如,原始圖中的hA,7PMi點(diǎn)在HDT圖中存在兩個副本hA,7PM,(6PM)i和hA,7PM,(7PM)i.當(dāng)起始點(diǎn)為6PM 時,所有的可行巡邏方案只能在8PM 或者之前結(jié)束,所以在這左面的子圖副本中,我們不需要保留時間點(diǎn)為9PM的節(jié)點(diǎn).

圖9 邊界概率得到的不可行解的例子

圖10 考慮起始時間點(diǎn)的子圖副本示例

為了避免生成復(fù)雜的巡邏路徑,Yin等人[23]對HDT圖進(jìn)行了進(jìn)一步的拓展.主要思想是讓每個節(jié)點(diǎn)將在這一節(jié)點(diǎn)之前發(fā)生的上一個行動記錄下來.也就是說,給每個點(diǎn)創(chuàng)建多個副本,每個副本表示從不同的邊指向這個點(diǎn).如果節(jié)點(diǎn)v是一個可能的起始點(diǎn),我們在另外給它創(chuàng)建一個副本,代表在這個點(diǎn)之前沒有其他行動.如果v和v0之間有一條邊,我們?yōu)関點(diǎn)的所有副本和v0點(diǎn)的先驗(yàn)行動為(v,v0)的副本之間構(gòu)造連邊.如果一條邊的兩個頂點(diǎn)保存的先驗(yàn)行動的類型不一樣,我們稱這條邊為一個換乘邊.這樣在新的圖中,一個巡邏方案的換乘次數(shù)就是它包含的換乘邊的數(shù)量.為了優(yōu)先產(chǎn)生更簡單的巡邏方案,他們給每條換成邊定義了一個花費(fèi)β>0.這樣通過改變β的值就可以在解的質(zhì)量和換乘次數(shù)之間進(jìn)行折中.圖11[23]展示了如何將圖10左圖陰影框中的子圖加入先驗(yàn)行動信息.

圖11 考慮先驗(yàn)行動的HDT圖示例

因?yàn)橹挥幸粭l邊指向hA,7PM,(6PM)i,所以我們只為這個點(diǎn)構(gòu)造一個副本,代表先驗(yàn)行動為停留在A點(diǎn)進(jìn)行站點(diǎn)檢查.有3條邊指向節(jié)點(diǎn)hB,7PM,(6PM)i,所以我們?yōu)檫@個點(diǎn)構(gòu)造3個副本,分別表示先驗(yàn)行動為乘坐一輛從A到B的車進(jìn)行隨車檢查,在B點(diǎn)進(jìn)行站點(diǎn)檢查和乘坐一輛從C到B的車進(jìn)行隨車檢查.我們同樣需要給每條由hB,7PM,(6PM)i點(diǎn)指出的邊構(gòu)造3個副本.比如hB,7PM,(6PM)i→hB,7PM,(6PM)i邊的3個副本,只有“Stay”到“Stay”的邊不是換乘邊.構(gòu)造了這樣的HDT圖后,我們就這個圖中每個邊上的邊界覆蓋概率來作為這個問題更有效的緊湊策略表達(dá)方式.

4 算法魯棒性研究進(jìn)展

除了可拓展性方面的挑戰(zhàn)以外,另外一個非常重要的挑戰(zhàn)來自于算法的魯棒性方面.傳統(tǒng)的博弈論通常假設(shè)參與者是完全理性的并且具有完美記憶能力的.但在現(xiàn)實(shí)中這些假設(shè)可能并不準(zhǔn)確.

因此,在計算防御者的資源分配策略時,算法應(yīng)考慮各種不確定性,包括效用誤差、執(zhí)行誤差、觀測誤差以及能力的不確定性.另外,現(xiàn)實(shí)生活中的攻擊者常分布在基于社會、文化或有認(rèn)知偏見的聯(lián)盟中,因此如何借助社會科學(xué)和行為博弈論的思想(例如前景理論、隨機(jī)最優(yōu)選擇)來建立更符合實(shí)際的攻擊者行為模型也成為主要的研究挑戰(zhàn).

圖12 不確定性空間

4.1 收益不確定性

在實(shí)際應(yīng)用中,需要利用領(lǐng)域?qū)＜谊P(guān)于可用的保護(hù)資源、不同保護(hù)目標(biāo)的安全風(fēng)險和脆弱性以及潛在的恐怖分子的喜好和能力等方面的知識來建模收益矩陣.保護(hù)者的均衡策略對收益矩陣非常敏感,但是領(lǐng)域?qū)＜覍@些信息把握有很大的不確定性,特別是恐怖分子相關(guān)的信息.比如,雖然我們可能知道一些目標(biāo)比另外一些目標(biāo)對恐怖分子來說更有吸引力,但是我們很難精確地知道恐怖分子在選擇攻擊目標(biāo)時,如何評估人員傷亡、經(jīng)濟(jì)損失、媒體報道等因素給他們帶來的收益.這意味著我們可能無法給出在不同的攻擊情境下精確的收益值.

在傳統(tǒng)的安全博弈論工作中,通常利用貝葉斯博弈來對收益的不確定性進(jìn)行建模.假設(shè)存在有限多種攻擊者的類型,每種攻擊類型有對應(yīng)的出現(xiàn)概率和對應(yīng)的精確的收益矩陣.但是,在實(shí)際應(yīng)用中,這種方式有兩方面的不足.一是,這種有限貝葉斯Stackelberg博弈的均衡求解問題是NP-hard的.ARMOR系統(tǒng)中用的DOBSS算法只能求解到10種攻擊者類型和每種攻擊者只有5種攻擊行為的規(guī)模.目前在求解這一問題上最快的算法是3.3節(jié)中提到的HBGS算法,但是即使是這個算法,在攻擊者的可選攻擊行為只有5個的情況下,也無法達(dá)到大于50種攻擊類型的規(guī)模.在FAMS這種有上千種可能的攻擊行為的領(lǐng)域中,所有目前已知的算法都無法考慮很多種攻擊者類型.另外,利用有限貝葉斯Stackelberg博弈進(jìn)行建模,我們需要領(lǐng)域?qū)＜姨峁┟糠N攻擊者類型對應(yīng)的確切收益矩陣和確切的出現(xiàn)概率,這在很多實(shí)際場景中是無法得到的.針對這一問題,Kiekintveld等人[37]、Yin等人[38]和Nguyen等人[39]在這方面做了一系列研究進(jìn)展.

Kiekintveld等人[37]用連續(xù)的收益分布(比如高斯分布或者平均分布)來表示攻擊者的收益引入了一個無窮貝葉斯Stackelberg安全博弈.確切地說,這個模型假設(shè)可能的攻擊者類型是無窮多個的.假設(shè)其中某種攻擊者類型γ∈Γ被選擇的概率為Pb(γ),當(dāng)目標(biāo)ti被保護(hù)時,攻擊者類型攻擊這一目標(biāo)得到的收益用Uti),目標(biāo)沒有被保護(hù)時,攻擊者的收益用U(ti)來表示.因?yàn)榭赡艿墓粽哳愋蛿?shù)量是無限的,我們無法顯性地把所有的策略值表示出來.Kiekintveld等人[37]用可能的收益值的連續(xù)分布來代替:

這表示保護(hù)者對于攻擊者收益值的信念.比如,保護(hù)者認(rèn)為當(dāng)攻擊者攻擊一個被保護(hù)的目標(biāo)ti時,他以(ti,c)的概率得到收益r.這種建模方式使得領(lǐng)域?qū)＜铱梢愿雍啽愕貋肀硎緦τ诠粽呤找娴牟淮_定性.他們不需要給出確切的攻擊者類型數(shù)量、每種攻擊者出現(xiàn)的概率和對應(yīng)的確切收益值,只需要根據(jù)他們自己的信念或者不完全的情報信息給出攻擊者攻擊某一目標(biāo)時可能得到的收益分布即可.

然而因?yàn)楸旧碛邢薏┺牡那樾尉褪荖P-hard的,這個無窮貝葉斯博弈模型是無法得到精確解的,所以Kiekintveld等人[37]利用了數(shù)值解、蒙特卡洛采樣和近似優(yōu)化的思想為這一模型設(shè)計了多種近似求解算法.為了求解這個模型,我們需要求解出保護(hù)者的最優(yōu)覆蓋策略和每種攻擊者類型的最佳響應(yīng).這一問題可以分解成兩步,一是計算或者估計攻擊者的最佳響應(yīng)對保護(hù)者覆蓋策略的函數(shù);二是有了這個最佳響應(yīng)函數(shù)之后,搜索保護(hù)者的策略集空間來尋找保護(hù)者的最優(yōu)策略.為了近似地計算攻擊者的最佳響應(yīng)函數(shù),Kiekintveld等人[37]提出了兩種近似方法,分別是蒙特卡洛采樣方法和分段常量函數(shù)近似法.蒙特卡洛采樣方法的思想是,首先在攻擊者類型的分布函數(shù)中等可能性地采樣出有限數(shù)量的攻擊者類型,然后利用上面的兩個式子得到每種攻擊者類型對應(yīng)的收益值.然后利用改進(jìn)的貝葉斯ERASER算法來求解得到攻擊者的最佳響應(yīng)函數(shù),這種做法采樣的數(shù)量越多,得到的響應(yīng)函數(shù)越準(zhǔn)確,當(dāng)采樣數(shù)量趨近于無窮時,可以得到精確的響應(yīng)函數(shù).分段常數(shù)函數(shù)近似法的思想是,首先假設(shè)攻擊者決定在一個攻擊目標(biāo)集合的子集中更傾向于攻擊哪個目標(biāo)時,只考慮這個子集中的目標(biāo)被覆蓋的概率,不考慮其他目標(biāo)是否被覆蓋.比如,令D={1,2}?{1,2,3},則當(dāng)攻擊者評估攻擊目標(biāo)t1和攻擊目標(biāo)t2哪個更有利時,只需要知道覆蓋概率c1和c2,而不需要知道目標(biāo)t3被保護(hù)的概率c3.這個假設(shè)看似是合理的,但是并不是一直是最優(yōu)的.利用這個假設(shè)可以迭代地增加考慮的攻擊目標(biāo)子集,得到攻擊者的最佳響應(yīng)函數(shù).給定了攻擊者的最佳響應(yīng)函數(shù)后,為了有效地搜索保護(hù)者的策略集空間來尋找保護(hù)者的最優(yōu)策略,Kiekintveld等人[37]提出了復(fù)制動力學(xué)采樣和貪婪的蒙特卡洛搜索兩種近似方法.復(fù)制動力學(xué)采樣是一種局部搜索算法,基于復(fù)制動力學(xué)的思想.該算法首先有一個具有隨機(jī)覆蓋概率的初始種群,然后利用上文給出的攻擊者最佳響應(yīng)函數(shù)計算出這每個覆蓋概率下攻擊者和保護(hù)者的收益,利用這個收益來改變對應(yīng)的覆蓋概率,產(chǎn)生下一代個體的覆蓋概率.收益越大適應(yīng)度越大,覆蓋概率的改變越小.這樣經(jīng)過一段時間迭代后,得到較優(yōu)的覆蓋概率.貪婪的蒙特卡洛搜索的思想是從每個目標(biāo)的覆蓋概率都為0開始,每次給目標(biāo)增加一個小的增量的覆蓋概率.每個迭代步中,計算將這個小的增量增加到每個目標(biāo)上帶來的收益增量,然后選擇收益增量最大的目標(biāo),將這個小的增量增加在這個目標(biāo)上,算法直到所有的保護(hù)資源都已經(jīng)被分配完終止.實(shí)驗(yàn)結(jié)果表明即便使用這些近似求解算法,無窮貝葉斯模型比以往的有限貝葉斯模型在解的質(zhì)量和算法的可拓展性上都有很大的優(yōu)勢.

Yin Zhenyu等人[38]進(jìn)一步提出了一個新的統(tǒng)一的HUNTER算法可以高效地求解有限貝葉斯Stackelberg安全博弈和無限貝葉斯Stackelberg安全博弈.該算法利用了多種人工智能和運(yùn)籌學(xué)的新技術(shù)來提升算法的效率:第一,它在搜索攻擊者的最佳響應(yīng)策略時,使用最好優(yōu)先搜索(best- fi rst search)方法,這樣可以有效地減少搜索空間;第二,它通過首先求解一個線性規(guī)劃得到解的上界進(jìn)一步提升搜索的速度;第三,在求解線性規(guī)劃時,利用了Benders分解技術(shù)進(jìn)一步提高求解效率;第四,作者發(fā)現(xiàn)在父節(jié)點(diǎn)中得到的Bender’s cuts可以在子節(jié)點(diǎn)中使用,進(jìn)一步提高了運(yùn)算速度;最后,HUNTER應(yīng)用了一種啟發(fā)式的分支規(guī)則進(jìn)一步提高算法效率.這個算法在求解離散型攻擊者類型和無限攻擊者類型的模型中都有很好的解的質(zhì)量和可拓展性.

考慮到在很多安全問題場景下,即使讓領(lǐng)域?qū)＜医o出攻擊者對每個攻擊目標(biāo)的確切收益分布也是不可能的,Kiekintveld等人[39]提出了一種新的更簡單的收益不確定性的建模方法.在這種基于區(qū)間的建模方法中,對于每個攻擊目標(biāo),都給出一個攻擊成功和不成功時,攻擊者所能得到的最大和最小的可能收益.比如,我們可以用max和min表示目標(biāo)沒有被保護(hù)時的值,用Umax和Umin表示目標(biāo)被保護(hù)時的值.表1給出了一個由3個攻擊目標(biāo),1個保護(hù)資源的區(qū)間安全博弈收益矩陣示例.

這種建模方法的思想是,保護(hù)者只知道攻擊者的收益位于一個可能的區(qū)間以內(nèi),但是不知道確切的值.而且,保護(hù)者也不知道攻擊者的收益在這個區(qū)間內(nèi)的分布函數(shù),所以他們也沒法計算攻擊者的期望收益.在這個博弈中,強(qiáng)Stackelberg均衡的解概念就不適用了.Kiekintveld等人[39]利用了魯棒優(yōu)化中常用的最壞情況的解概念.也就是說,考慮攻擊者可能取定義的區(qū)間內(nèi)的所有收益值的組合,保護(hù)者的目標(biāo)是選擇一個最大化保護(hù)者最壞情況下的收益值的覆蓋向量C.給定覆蓋概率C,對于每一個目標(biāo),攻擊者有一個期望收益的范圍:

表1 區(qū)間安全博弈收益矩陣示例

所以在這個覆蓋概率下,攻擊者可以保證至少得到所有最小期望收益中的最大值,我們用R=maxtivmin(ti)來表示這個量.已知R值,則所有具有最大期望收益vmax(ti)≥R的目標(biāo)ti都有可能成為某種特定的攻擊者類型的最佳攻擊目標(biāo).我們可以定義一個潛在的攻擊目標(biāo)集Λ(C)={ti:vmax(ti)≥R}.另外,保護(hù)者對于每個攻擊目標(biāo)的期望收益為:di=ci·U(tti)+(1?ci)U(tti).所以,保護(hù)者的目標(biāo)是選擇一個覆蓋策略C,在這個策略下可以最大化保護(hù)者在潛在攻擊目標(biāo)中可能得到的最差收益:為了求解這一優(yōu)化問題,Kiekintveld等人[39]將這一問題轉(zhuǎn)化成一系列可行問題.首先,觀察到保護(hù)者的期望收益是隨著可用保護(hù)資源數(shù)量單調(diào)遞增的.保護(hù)者的可選覆蓋策略空間也是隨著保護(hù)資源數(shù)量單調(diào)遞增的.利用這一特點(diǎn),我們可以在保護(hù)者的期望收益空間內(nèi)進(jìn)行二分查找.在每一個迭代步中,已知保護(hù)者的資源數(shù)量,我們首先測試保護(hù)者取期望收益區(qū)間的中間值是否可行.如果不可行,最大收益一定小于中間值;如果可行,則最大收益一定大于等于中間值.利用這一方法,我們可以近似地得到保護(hù)者的最大收益.這是一個多項(xiàng)式時間的近似算法.

Nguyen等人[40]利用魯棒優(yōu)化中的極小化最大后悔值準(zhǔn)則針對基于區(qū)間的安全博弈模型提出了一種新的解的概念.首先我們定義并令I(lǐng)=則每一種可能的攻擊者類型對應(yīng)一個收益集合:

當(dāng)保護(hù)者的覆蓋概率為C時,保護(hù)者在面對這種攻擊者類型時的期望收益為:

保護(hù)者在采用覆蓋概率C時的最大后悔值定義為:

這意味著,選擇這個覆蓋概率在最壞的情況下,可能少得到的收益.極小化最大后悔值準(zhǔn)則的意思就是要選擇最大后悔值最小的覆蓋概率:

在表1的例子中,如果按照最大化最差收益的準(zhǔn)則,則保護(hù)者的最佳策略為[1.0,0.0,0.0],把所有的資源分配在最脆弱的目標(biāo)1上,因?yàn)檫@個目標(biāo)的收益和損失值都是最小的,盡管保護(hù)目標(biāo)1得到的收益很小.在這種準(zhǔn)則下,最大的后悔值為11.而如果用極小化最大后悔值準(zhǔn)則,保護(hù)者的最優(yōu)策略為[0.34,0.44,0.22],在這種情況下,最大的后悔值為6.2.極小化最大后悔值最優(yōu)策略的求解問題可以表示成以下優(yōu)化問題:

在這個問題中,和都是連續(xù)的,所有約束的數(shù)量是無窮多的,另外這個問題是非凸的,所以非常難求解.Nguyen等人[40]利用了約束采樣和約束生成的方法來近似地求解這一問題.基本思想是先隨機(jī)采樣產(chǎn)生一個約束子集,然后不斷地給這個松弛的問題增加違背的約束直到收斂到最優(yōu)解.實(shí)驗(yàn)結(jié)果表明這種算法可以很快得到質(zhì)量很好的解.

4.2 執(zhí)行與觀察誤差

為了保證上述算法所得解的最優(yōu)性質(zhì),算法對于攻擊者的策略選取進(jìn)行了嚴(yán)格的假設(shè).它們認(rèn)為保護(hù)者能夠嚴(yán)格地執(zhí)行自己的策略,即便在執(zhí)行混合策略的情況下;同時假定攻擊者能夠完全觀察到保護(hù)者的執(zhí)行策略,并在此基礎(chǔ)上選取期望收益最高的目標(biāo)進(jìn)行攻擊.但是在現(xiàn)實(shí)世界中,這兩個假設(shè)很難得到滿足.保護(hù)者的執(zhí)行誤差和攻擊者的觀察誤差不可避免地存在,進(jìn)而影響了博弈雙方的收益,這削弱了上述算法的有效性.在考慮攻擊者無法完全得知保護(hù)者策略的情況下,GUARD[41]假定攻擊者觀察到的策略將會服從錨定理論.該理論認(rèn)為在沒有得到任何信息的時候,人們傾向于認(rèn)為可能發(fā)生的情況服從平均分布,并且一旦得到有用信息,人們將會在平均分布上進(jìn)行偏移.GUARD算法認(rèn)為在保護(hù)者采取策略時,攻擊者觀察到的策略為=1/|X|·α+(1?α)P這樣攻擊者將會根據(jù)x0進(jìn)行決策,亦即0≤(al?∈XC)≤(1)M.雖然錨定理論是攻擊者的觀察偏見,但是可以看成一種觀察誤差.當(dāng)然也可以將錨定理論看做是由策略空間X到策略空間X0的映射,可以利用DOBSS求解x0,進(jìn)而求得保護(hù)者實(shí)際的執(zhí)行策略x.

在之后的工作中,研究者考慮了不同于錨定理論產(chǎn)生結(jié)果的觀察誤差,同時加入了保護(hù)者的執(zhí)行誤差.Yin等人[42]提出的RECON算法中,對于保護(hù)者的策略Cintend,其實(shí)際執(zhí)行策略y可以發(fā)生如下偏離:αi;而攻擊者所觀察到的并借以做出決策的策略Cobs也可以與實(shí)際執(zhí)行策略發(fā)生類似偏離:βi,而保護(hù)者只能最大化在誤差發(fā)生情況中的最差收益:其中在求解過程中,RECON通過引入Weakly Inducible目標(biāo)集S(Cint)將現(xiàn)有的雙層優(yōu)化問題變?yōu)閱螌觾?yōu)化問題.S(Cint)中目標(biāo)tj滿足:

相應(yīng)的規(guī)劃問題可以表述為:

其中,實(shí)驗(yàn)結(jié)果表明RECON相對于ERASER和COBRA具有更強(qiáng)的魯棒性,并且能為保護(hù)者帶來更高的收益.

RECON考慮的執(zhí)行誤差是靜態(tài)的,Jiang等人[43]考慮了動態(tài)執(zhí)行誤差.不同于以上算法,時序成為影響執(zhí)行誤差的因素之一.這種誤差產(chǎn)生的原因是上述算法獲得的保護(hù)策略在執(zhí)行過程中由于突發(fā)事件和調(diào)度問題可能得到中斷,進(jìn)而無法得到有效實(shí)施,產(chǎn)生誤差.這在現(xiàn)實(shí)生活中是突出存在的,并造成了可觀的損失.Jiang等人[43]考慮一類具有動態(tài)執(zhí)行誤差的貝葉斯Stackerberg博弈,其中保護(hù)者所擁有的總計R個巡邏單元i將會處在有限狀態(tài)空間S中的狀態(tài)si并執(zhí)行有限行為空間A中的行為ai.不同狀態(tài)之間的轉(zhuǎn)換服從馬爾科夫決策過程(MDP).Ti(si,ai,)為在當(dāng)前狀態(tài)si執(zhí)行的情況下,博弈轉(zhuǎn)化為 狀態(tài)的概率;Ri(si,ai,)是相應(yīng)轉(zhuǎn)換為保護(hù)者帶來的收益.這類收益是保護(hù)者在環(huán)境中獲得的收益,而非保護(hù)者與攻擊者發(fā)生博弈為保護(hù)者帶來P的收益.這樣攻擊者所能獲得的收益可以表示為γ∈ΓpγEt π[UΘ(t,π,aγ)],而攻擊者將會選擇攻擊期望收益最大的目標(biāo),即aγ∈Et π[UΨ(t,π,aγ)].在求解過程中,Jiang 等人[43]通過假設(shè)博弈具有可分離的收益并引入邊際轉(zhuǎn)換概率xi(si,ai,)以及邊際到達(dá)/執(zhí)行概率wi(si,ai),二者滿足如下約束:

這些約束條件解決了優(yōu)化過程的指數(shù)增長問題,并將優(yōu)化問題轉(zhuǎn)化為混合整數(shù)規(guī)劃問題,其優(yōu)化任務(wù)為:

求解結(jié)果是邊際概率,卻不能得到適用于馬爾科夫決策過程的策略.因此算法還需尋找能夠滿足最優(yōu)邊際概率的巡邏策略.

4.3 觀察能力的不確定性

在安全領(lǐng)域,研究者之所以選擇強(qiáng)Stackerberg均衡作為保護(hù)者的策略,便是基于攻擊者能夠?qū)ΡＷo(hù)者的策略進(jìn)行觀察,并在觀察之后選擇最優(yōu)響應(yīng),雖然在觀察過程中存在上述考慮的誤差.但是另外一種可能也會存在,就是攻擊者在執(zhí)行攻擊之前根本就無法得到保護(hù)者執(zhí)行策略的相關(guān)信息.這樣在完全理性的假設(shè)下,博弈結(jié)果將會是Nash均衡.在不同的博弈假設(shè)和收益矩陣的情況下,上述兩種均衡具有不同的性質(zhì),二者之間的聯(lián)系也有不同.Korzhyk等人[10]證明在安全博弈中,保護(hù)者的納什策略也是MINIMAX策略,而在滿足SSAS性質(zhì)的情況下,保護(hù)者的強(qiáng)Stackerberg策略也是納什策略.此外,在僅有一種保護(hù)資源的情況下,如果對于任何一個保護(hù)目標(biāo),(ti)6=E?,其中E?為MINIMAX策略攻擊者的收益值,那么保護(hù)者將會僅有一個強(qiáng)Stackerberg均衡策略.Korzhyk等人[44]考慮攻擊者具有pobs的概率可以完全觀察到攻擊者的策略,而有1?pobs的概率不能得知.保護(hù)者在不能得知攻擊者能否觀察到自己策略的情況下,將會通過最大化期望收益

來選擇最優(yōu)策略.由于攻擊者不能總是觀察到保護(hù)者的策略,這使得保護(hù)者的純策略仍然是一個分布,因此我們不再能夠?qū)懴滤屑儾呗?為了克服這個困難,設(shè)計算法在FIND-NE部分求解博弈的納什均衡策略,并以此作為保護(hù)者所選擇執(zhí)行的策略集元素加入D中,在現(xiàn)有策略集D的情況下,攻擊者將會采取納什均衡策略q,通過優(yōu)化保護(hù)者的期望收益,進(jìn)而求得保護(hù)者的最優(yōu)策略.相應(yīng)的算法流程如下:

在觀察能力的不確定性中,現(xiàn)有研究考慮的另一種情況是攻擊者只能夠觀察持續(xù)一段時間τ的攻擊者策略,然后設(shè)計自己的攻擊方案并執(zhí)行攻擊.這意味著觀察結(jié)果將會影響攻擊者的策略選取.An等人[45]假定攻擊者對于保護(hù)者執(zhí)行策略的先驗(yàn)概率服從狄利克雷分布,即:

在觀察到結(jié)果o后,利用貝葉斯規(guī)則可以求得后驗(yàn)分布:

則根據(jù)后驗(yàn)分布得到的邊際覆蓋概率為:

而攻擊者將會根據(jù)這樣的知識選擇最優(yōu)策略,此時攻擊者將會攻擊的目標(biāo)集為φ(o)=argmaxt∈T((t)+(1)(t)),因此保護(hù)者求解最優(yōu)策略的規(guī)劃問題成為如下形式P1形式:

對目標(biāo)函數(shù)取對數(shù)后使得其成為上凸的,成為P2形式:

在這種處理方法中,需要保護(hù)者事先得知攻擊者的觀察時間,而An等人[46]通過利用馬爾科夫決策過程模擬攻擊者的觀察行為放寬了這個假設(shè),相應(yīng)的博弈過程成為:1)保護(hù)者在得知攻擊者對于自己采用策略的先驗(yàn)分布的情況下選取混合策略x;2)攻擊者選擇進(jìn)行觀察或者進(jìn)行攻擊,若選擇進(jìn)行觀察,則根據(jù)現(xiàn)有觀察結(jié)果更新自己關(guān)于保護(hù)者策略的后驗(yàn)分布,如果選擇攻擊,則博弈結(jié)束.在求解過程中,作者證明在為每一個狀態(tài)o給定最優(yōu)值V(o)之后,利用BI-FS(Backward Induction with Forward Search)算法可以尋找到滿足攻擊者馬爾科夫決策過程的最優(yōu)解觀察圖O?.在此基礎(chǔ)上,求解保護(hù)者最優(yōu)策略的方法與之前方法類似.

在以往的研究中,攻擊者雖然能夠得知保護(hù)者的策略,因此,可以知道攻擊目標(biāo)被保護(hù)的概率,但是卻不能得知在攻擊發(fā)生的時候保護(hù)者采取的保護(hù)行為.在這個假設(shè)下,攻擊者可以通過隨機(jī)化自己的保護(hù)資源來提高自己的收益.但是這個假設(shè)在某種程度上并不直觀,因此,在相關(guān)文獻(xiàn)中放松了這個假設(shè),攻擊者雖然在不能得知在隨之而來的攻擊中保護(hù)者的保護(hù)行為,但是可以在觀察保護(hù)者現(xiàn)有保護(hù)行為的基礎(chǔ)上對其下一步保護(hù)行為進(jìn)行推測.

Vorobeychik等人[47]證明對于任何滿足:UΘ(s,θ,ψ)=UΨ(s,θ,ψ) 且γΘ=γΨ的隨機(jī)Stackerberg博弈,都存在一個確定的分別由保護(hù)者和攻擊者馬爾科夫穩(wěn)態(tài)策略構(gòu)成的強(qiáng)Stackerberg均衡.這時的博弈發(fā)生在圖G上,不同的資源分布將會受到圖的拓?fù)浣Y(jié)構(gòu)的影響,而在資源分布調(diào)整的時候,保護(hù)者需要承擔(dān)一定的花費(fèi).但是這個結(jié)果并不能廣泛成立,正如Vorobeychik等人[48]、Letchford等人[49]陳述的,在一般的隨機(jī)Stackerberg博弈中,保護(hù)者的最優(yōu)策略并不是馬爾科夫穩(wěn)態(tài)策略.在這種情況下,Vorobeychik等人[48]考慮的博弈過程是z0對應(yīng)保護(hù)資源分配的起始狀態(tài),而保護(hù)者將會參考固定長度K的保護(hù)行為歷史來決定自己接下來的行為,其中被用來參考的歷史稱為不同的狀態(tài),記為s.而當(dāng)且僅當(dāng)保護(hù)者可以在狀態(tài)s的最后一個覆蓋向量轉(zhuǎn)變到z的情況下,Bsz=1.文章證明對于任意狀態(tài)s∈S,z0∈Z,只有在Gzz0具有完全匹配的時候,Bzz0=1.而一個保護(hù)者的策略給出在任何狀態(tài)s∈S下,保護(hù)者選擇可能出現(xiàn)的覆蓋向量的概率分布.在上述博弈過程中,假定攻擊者將會考慮h博弈步內(nèi)的期望收益:

而保護(hù)者的最終受益還需要考慮不同保護(hù)資源策略之間轉(zhuǎn)變的花費(fèi),

其中,

將上述限制條件結(jié)合在一起就成了需要求解的規(guī)劃問題.上述約束條件中,整數(shù)變量的組合以及連續(xù)變量πsz與其他變量的非上凸關(guān)聯(lián)為問題的求解增加了困難.為了克服這些困難,如果上述變量中至少有一個是二值變量,McCormick不等式提供了一種混合整數(shù)規(guī)劃的近似,降低了問題求解的復(fù)雜度.

4.4 人類行為建模

為確保算法結(jié)果的最優(yōu)性質(zhì),上述算法對博弈雙方的決策過程做出了很強(qiáng)的假設(shè).它們認(rèn)為博弈雙方是完全理性而且攻擊者會沒有誤差地觀察到守護(hù)者的策略,在守護(hù)者策略是混合策略的時候這樣的假設(shè)顯得更加重要.然而,這些假設(shè)很難在真實(shí)世界中得到執(zhí)行,尤其是博弈雙方均為人類的時候.攻擊者如何在已有知識的情況下進(jìn)行決策成為影響上述算法有效性的一個關(guān)鍵假設(shè).一般來說,應(yīng)用系統(tǒng)利用博弈論中的完全理性以及利益最大化假設(shè)進(jìn)行建模.雖然這是一個為研究者普遍接受的假設(shè),但是這將會使得保護(hù)策略在面對使用不同決策過程的襲擊者時表現(xiàn)很差,這些算法并不能利用人類決策過程中顯而易見的弱點(diǎn)為保護(hù)者獲得更好的收益.因此,完全理性等博弈論經(jīng)典假設(shè)在多主體領(lǐng)域應(yīng)用的有效和合理性受到質(zhì)疑,并且引起了研究者的注意[50].此方面的一個重要進(jìn)展是BRASS[51].BRASS假定攻擊者能夠?qū)ψ顑?yōu)策略進(jìn)行ε的偏離.這意味著攻擊者將在與最優(yōu)收益偏離ε的范圍內(nèi)隨機(jī)選取策略,這樣在給定多個ε?最優(yōu)策略的情況下,由于隨機(jī)性的存在,保護(hù)者只能優(yōu)化自己可能得到的最差收益.因此,優(yōu)化問題約束條件

使得當(dāng)=1時,al?i∈X<ε,滿足了上面提到的ε偏離的要求.隨之加入規(guī)劃限制確保了算法解的有效性.這種思路不同于之前研究之處是,傳統(tǒng)方法假定攻擊者會選擇最大化保護(hù)者收益的策略.這項(xiàng)工作中表明BRASS相比DOBSS,能夠在面對智能攻擊者的時候取得更好的表現(xiàn).但是這樣工作中對于ε偏離產(chǎn)生的原因沒有進(jìn)行討論,相關(guān)的人類行為決策過程也沒有涉及.

這個問題在接下來的工作中得到回答.Yang等人[52]在行為經(jīng)濟(jì)學(xué)的前景理論和行為博弈論的隨機(jī)最優(yōu)化模型的基礎(chǔ)上分別提出了BRPT和BRQR算法,為算法中相關(guān)不同于經(jīng)典博弈論假設(shè)的改動提供了清晰的決策過程.前景理論認(rèn)為人類在決策過程中將會最大化自己的期望,這里的期望被定義為π(pi)V(ci),其中pi為ci實(shí)際發(fā)生概率,權(quán)重函數(shù)π(pi)是決策者賦予ci的概率.一般情況下,πpi+π1?pi<1.V(ci)為ci能夠帶來的收益.前景理論表明人的決策具有損失厭惡,也就是說,人們過低預(yù)測收益發(fā)生的概率而過高預(yù)測損失的發(fā)生概率.

圖13 前景理論的經(jīng)驗(yàn)函數(shù)

隨機(jī)最優(yōu)化模型認(rèn)為人們并不嚴(yán)格最大化自己的收益,而是隨機(jī)性地進(jìn)行行為決策:當(dāng)誤差所帶來的懲罰降低的時候,人們選擇非最優(yōu)策略的概率增加.在其他人的策略給定的情況下,選取行為i的概率為:(x)=其中(x)是選取攻擊者行為t的期望收益.同時,λ的取值決定了行為者p的理智程度:當(dāng)λ=0時,行為者對收益不加考慮地選擇行為,當(dāng)λ→∞時,隨機(jī)最優(yōu)化變?yōu)樽罴秧憫?yīng).

BRPT在假定攻擊者行為滿足前景理論的情況下給出最優(yōu)的保護(hù)策略.攻擊者攻擊目標(biāo)t而獲得的前景收益通過下式給出:π(xi)V()+π(1?xi)V().而攻擊者將會選擇前景收益最高的目標(biāo)進(jìn)行攻擊.這樣核心的規(guī)劃約束條件表示為:

為了克服非線性和非上凸函數(shù)π·為算法實(shí)現(xiàn)帶來的困難,BRPT采用了分段線性函數(shù)對其進(jìn)行近似,近似函數(shù)在圖14[52]展示.其中將π·分為了5部分線性函數(shù),這樣算法被改造成了一個混合整數(shù)線性規(guī)劃問題,提高了算法的運(yùn)算效率.

圖14 權(quán)重函數(shù)分段線性近似

在前景理論決策模型的基礎(chǔ)上,RPT模型通過引入攻擊者對執(zhí)行策略與最優(yōu)策略之間的ε偏離,融合了BRASS算法的優(yōu)勢,使得算法更加貼近現(xiàn)實(shí)情況.

相應(yīng)地,BRQR假定攻擊者的決策模型滿足隨機(jī)最優(yōu)化,這樣優(yōu)化問題的目標(biāo)函數(shù)可以表示為:

這樣算法面臨著目標(biāo)函數(shù)的非線性和非上凸性質(zhì)帶來的求解困難.該算法通過多次選取起始點(diǎn)迭代使得其有更大的可能性收斂于全局最優(yōu)解,而在每次迭代中只尋找局部最優(yōu)解.

PASAQ通過利用二分搜索克服了BRQR算法收斂性的問題,提升了算法的運(yùn)算速度,并且充分考慮了保護(hù)資源分配中的相關(guān)限制條件,使得其成為PROTECT系統(tǒng)的核心算法[53].

這些算法需要對保護(hù)者的純策略進(jìn)行遍歷,在應(yīng)用情景更為大型的時候無法使用.BLADE算法利用切割平面法對PASAQ進(jìn)行了擴(kuò)展[54].

切割平面方法主要體現(xiàn)在Separation Oracle部分,它利用了最小化范式的方法能夠有效地對一個不合適的策略集進(jìn)行切割,這保證了每一次的切割都能夠使得剩余策略集最大程度地接近合適的策略集.另一方面為了驗(yàn)證Quantual Response在解釋人類行為建模的意義,SU-BRQR[55]引入了一類新的主觀效益函數(shù)它為所有決策者可知的信息賦予了相應(yīng)的權(quán)重,增加了模型的合理性,但在求解過程中并沒有太大改變.

不同于上述行為經(jīng)濟(jì)學(xué)建模思路,穩(wěn)健優(yōu)化方法在MATCH算法中得到了再一次的改進(jìn).與在BRASS中僅考慮攻擊者對于最優(yōu)策略的偏離,而保護(hù)者最優(yōu)化自己的收益不同,MATCH限制了保護(hù)者的最大損失[56].相應(yīng)的規(guī)劃算法表示為:

約束條件5是算法中最重要的條件,不等式左側(cè)UΨ(x,q)?UΨ(x,)計算攻擊者由于采用偏離的最優(yōu)策略而產(chǎn)生的損失,不等式右側(cè)γ?UΘ(,x)給出了保護(hù)者所承受的期望損失,其中β表示保護(hù)者所能承受的極限期望損失.這一約束條件將保護(hù)者由于攻擊者的策略偏移而得到的最大收益和改進(jìn)保護(hù)策略缺點(diǎn)之間進(jìn)行了平衡.MATCH算法具有3個優(yōu)勢:1)它的運(yùn)算速度快于BRQR;2)它通過耦合攻擊者和保護(hù)者的表現(xiàn),為保護(hù)者帶來高于BRQR的收益;3)它避免了設(shè)計一種精確模型,增強(qiáng)了算法的普適性.

鑒于穩(wěn)健優(yōu)化和人類行為建模各有優(yōu)勢,MonitonicMaximin結(jié)合了上述兩種建模方法[57].其總體思路是在原有Maximin算法中加入對于攻擊者選取的策略的限制,并假定攻擊者的策略滿足單調(diào)性,隨機(jī)最優(yōu)化成為這種條件下的特例.實(shí)驗(yàn)證明該算法的表現(xiàn)優(yōu)于上面提到的MATCH算法.

5 算法效能評估進(jìn)展

在上述算法提出和相應(yīng)的安全系統(tǒng)設(shè)計的同時,對于算法和系統(tǒng)的評價機(jī)制的設(shè)計也進(jìn)入了研究者的考慮之中.計算機(jī)科學(xué)家在其具有豐富研究手段的算法運(yùn)行時間、算法復(fù)雜度、魯棒性及敏感性的方面給出了評價方法;但是由于多主體研究是理論結(jié)合實(shí)際問題的,因此,還要進(jìn)行更為細(xì)致和全面的考量,例如傳統(tǒng)的定量分析及領(lǐng)域?qū)＜乙庖娨彩侵档脜⒖嫉闹匾獦?biāo)準(zhǔn).Taylor等人[58?59]在對ARMOR系統(tǒng)進(jìn)行的評價中提出了多種評價機(jī)制選擇,其評價機(jī)制在以后的研究工作中得到了進(jìn)一步的創(chuàng)新和發(fā)展,形成了較為完善的評價機(jī)制.我們在此綜述如下.

5.1 算法博弈論的評價方法

利用博弈論視角來模擬安全問題是現(xiàn)有工作的基本假設(shè),也是最重要的假設(shè).博弈論給出了博弈雙方的博弈環(huán)境以及行為決策過程.算法博弈論利用計算機(jī)手段對博弈均衡進(jìn)行求解,現(xiàn)有的絕大多數(shù)工作將SSE作為目標(biāo)求解策略.因此,這類基本假設(shè)及算法求解中的表現(xiàn),成為計算機(jī)研究者評價過程中最為感興趣的一部分.

5.1.1 運(yùn)行時間與可擴(kuò)展性

有鑒于安全博弈問題的實(shí)用性背景,算法必須在相關(guān)部門可以承受的時間范圍之內(nèi)對問題進(jìn)行有效求解,而算法在問題尺度擴(kuò)大情況下的表現(xiàn)也得到了關(guān)注.

Pita等人[16]在改變貝葉斯Stackelberg博弈中對手種類的情況下,驗(yàn)證了DOBSS的表現(xiàn)要優(yōu)于ASAP和MultiLPs.Jain等人[60]在目標(biāo)數(shù)量、可用資源數(shù)量以及對手?jǐn)?shù)量3種不同的參數(shù)情況下表現(xiàn)了ERASER-C在運(yùn)行時間上少于DOBSS及MutiLPs.Pita等人[24?25]在不同領(lǐng)域數(shù)量、每一領(lǐng)域不同活動種類及不同資源數(shù)量3個方面表明了GUARD采用的緊湊表示具有比DOBSS采用的全表示更好的擴(kuò)展性,關(guān)于二者所需內(nèi)存分析中也驗(yàn)證了這一點(diǎn)[18].Tsai等人[6]也在3種不同的FAMS數(shù)量上驗(yàn)證了IRIS在求解時間上的實(shí)用性.由上可以看出,分析運(yùn)行時間隨著不同博弈參數(shù)的變化成為分析算法表現(xiàn)的基本步驟.

圖15 DOBSS、ASAP和MultipLP運(yùn)行時間

5.1.2 策略表現(xiàn)分析

除了對于算法運(yùn)行時間的可行性的考慮,研究者還討論了算法求解出的SSE策略為保護(hù)者帶來的收益進(jìn)行了分析.

Pita等人[24?25]集中分析了GUARD 中使用的策略相對均勻隨機(jī)策略帶來的保護(hù)者收益上的提升,同樣Tsai等人[6]中對IRIS策略、權(quán)重和均勻隨機(jī)策略進(jìn)行了比較.Shieh等人[18?22]提供了使用λ=1.5的PASAQ算法能夠給出比DOBSS、均勻隨機(jī)策略(保護(hù)者或攻擊者)更高收益的實(shí)驗(yàn)證據(jù).以上的結(jié)果說明采用博弈論框架下的SSE均衡策略確實(shí)能夠?yàn)楸Ｗo(hù)者帶來收益上的提升,而這是安全系統(tǒng)應(yīng)用的目的.因此,策略表現(xiàn)的分析驗(yàn)證了上述研究的實(shí)用價值.

圖16 GUARD求解策略收益分析

5.1.3 魯棒性

由于混合策略只具有統(tǒng)計意義,在每一時刻保護(hù)者只能選擇一個純策略進(jìn)行實(shí)施.這種策略的實(shí)施過程不可避免地帶來了實(shí)施誤差,進(jìn)而可能影響博弈雙方的實(shí)際收益.因此,驗(yàn)證所得策略的魯棒性成為評價機(jī)制的一個選擇.

圖17 PROTECT系統(tǒng)在觀察噪聲下保護(hù)者的期望收益

Shieh等人[18?22]在博弈中加入了由于攻擊者觀察誤差、執(zhí)行誤差和收益誤差所引起的噪聲驗(yàn)證了使用λ=1.5的PASAQ算法能夠給出比DOBSS具有更高魯棒性的保護(hù)者策略.

5.2 數(shù)據(jù)建模模擬方法

除了考慮模型求解出的策略的性質(zhì)之外,研究者對于模型如何建立也考量,并且發(fā)展出通過已有數(shù)據(jù)建立博弈模型,評價相關(guān)算法優(yōu)劣的評價機(jī)制.Jain等人[60]利用來自LAX方面的真實(shí)數(shù)據(jù),建立了對于ARMOR獵犬問題進(jìn)行模擬的博弈模型.在評價中,筆者比較了不同情況下由ERASER-C產(chǎn)生的巡邏過程與均勻隨機(jī)巡邏過程的保護(hù)者的收益情況.

Yin等人[8,23]利用來自4條真實(shí)洛杉磯地鐵線路的數(shù)據(jù)集,根據(jù)列車時刻表建立了轉(zhuǎn)換網(wǎng)絡(luò),同時考慮了不同的時間上下地鐵人群分布變化以及列車運(yùn)行的真實(shí)情況,建立了仿真模型,進(jìn)行實(shí)驗(yàn)驗(yàn)證了TRUST系統(tǒng)在不同參數(shù)條件下的有效性.

相似地,Haskell等人[31]利用來自NOAA的海岸生態(tài)系統(tǒng)地圖中的漁業(yè)數(shù)據(jù),以及USCG漁船數(shù)據(jù),并將試驗(yàn)重點(diǎn)放在墨西哥灣的部分海域,通過將目標(biāo)海域離散化為網(wǎng)格建立了相關(guān)的博弈模型,并分別在考慮距離因素和不考慮距離因素的情況下,比較COmPASS與SUQR和MAXIMIN帶來的不同收益,肯定了COmPASS的更為優(yōu)良的表現(xiàn).Yang等人[30]利用了真實(shí)偷獵者的分布來模擬了野生動物保護(hù)的實(shí)驗(yàn)過程,檢驗(yàn)了不同的學(xué)習(xí)策略在適應(yīng)性的資源分配原則下對于偷獵行為的打擊作用.真實(shí)數(shù)據(jù)的獲取和在博弈模型中的應(yīng)用,極大地將理論算法與實(shí)際問題結(jié)合起來,而避免了真實(shí)應(yīng)用中較為龐大的人力物力耗費(fèi),成為評價安全系統(tǒng)表現(xiàn)的常用手段.

圖18 TRUST真實(shí)數(shù)據(jù)建模結(jié)果

5.3 真實(shí)世界中的應(yīng)用

安全問題是真實(shí)世界中的問題,而現(xiàn)有工作中的模型都或多或少地進(jìn)行了簡化和適用性的假設(shè).檢驗(yàn)這些簡化和假設(shè)是否會影響模型有效性的最可靠的手段仍然在真實(shí)世界中進(jìn)行應(yīng)用.但鑒于真實(shí)應(yīng)用場景的復(fù)雜性,為了對相關(guān)影響因素進(jìn)行區(qū)別對待,研究者在實(shí)驗(yàn)室中進(jìn)行了真實(shí)的但是規(guī)模較小、情景較為簡單的實(shí)驗(yàn)應(yīng)用,取得了令人信服的評價結(jié)果.

5.3.1 實(shí)驗(yàn)室應(yīng)用表現(xiàn)

Pita等人[56,58]進(jìn)行了一個簡單的在線博弈“海盜和寶藏”實(shí)驗(yàn)來模擬真實(shí)的LAX出入口情況.

而這個實(shí)驗(yàn)的結(jié)果很好地驗(yàn)證了ARMOR能夠在對手是真人個體的時候取得較高的收益.同樣的手段也應(yīng)用在文獻(xiàn)[52,55]評價中.實(shí)驗(yàn)室應(yīng)用的評價手段能夠在較少的花費(fèi)情況下獲得相當(dāng)接近真實(shí)大型應(yīng)用場景的數(shù)據(jù).尤其是對于一些含有對人類行為建模的工作,這樣的實(shí)驗(yàn)數(shù)據(jù)能夠極大程度上驗(yàn)證并反映行為建模的有效性,取得可信的評價結(jié)果.

圖19 海盜與寶藏博弈界面

5.3.2 真實(shí)系統(tǒng)布置表現(xiàn)

真實(shí)安全系統(tǒng)的表現(xiàn)具有最有利的評價特征.在這些表現(xiàn)產(chǎn)生的數(shù)據(jù)中,出現(xiàn)在現(xiàn)有評價機(jī)制中的有:Yin等人[8,23]給出了LASD測試TRUST系統(tǒng)表現(xiàn)的大體結(jié)果.Pita等人[16]在LAX中布置了ARMOR對該系統(tǒng)的運(yùn)行特征及敏感性進(jìn)行了分析,同樣地,Jain等人[60]公布了ARMOR的采用前后的犯罪行為數(shù)據(jù),肯定了其對于預(yù)防犯罪的積極作用.

Shieh等人[18?22]披露部分波士頓港口在PROTECT系統(tǒng)應(yīng)用前后為USCG帶來的區(qū)域巡邏次數(shù)的變化.系統(tǒng)運(yùn)行的全部數(shù)據(jù)由于安全原因并未得到完全公開,但是從現(xiàn)有數(shù)據(jù)中可以分析,基于博弈論的安全系統(tǒng)的設(shè)計和布置為傳統(tǒng)安全問題的解決帶來了新的重要影響.

圖20 PROTECT系統(tǒng)布置前后情況對比

5.4 行業(yè)專家評價

5.4.1 領(lǐng)域?qū)＜以u價

雖然上述提到的不同評價能夠在不同的方面為安全系統(tǒng)提供定量分析,但是每一種手段都有著其自身的局限性,且很難對安全系統(tǒng)提供全面且中肯的評價.在這種情況下,領(lǐng)域?qū)＜以u價就顯得極為重要.其所具有的相關(guān)專業(yè)知識以及在安全問題處理中的豐富經(jīng)驗(yàn)?zāi)軌蚩朔鲜龅娜秉c(diǎn).Jain等人[60]提到的領(lǐng)域內(nèi)專家的評價為:雖然ARMOR和IRIS系統(tǒng)并不能提供完全的安全性,但是它們可以幫助安全部門在現(xiàn)有資源的基礎(chǔ)上進(jìn)行最為有效的防御.

5.4.2 對手評價

除了領(lǐng)域內(nèi)專家的專業(yè)意見,最直接感受到安全系統(tǒng)的作用的應(yīng)當(dāng)是攻擊對手.因此,攻擊對手的評價顯得相當(dāng)重要.Shieh等人[18?22]提到:USCG為了能夠更好地了解攻擊對手對于潛在目標(biāo)的認(rèn)識創(chuàng)建了Adversatial Perspective Team.這個團(tuán)隊(duì)能夠從恐怖分子的角度對相應(yīng)的安全系統(tǒng)進(jìn)行評估,并且承認(rèn)了PROTECT系統(tǒng)為巡邏帶來的積極作用.

5.4.3 輿論評價

輿論評價是指社會相關(guān)媒體對于犯罪事件等社會不安定因素的評價和反映,從大眾的角度對相應(yīng)安全部門的行為進(jìn)行評價.Shieh等人[18?22]提供了部分USCG船員對于PROTECT系統(tǒng)實(shí)施后的直觀評價,肯定了該系統(tǒng)的作用,也表明了博弈論應(yīng)用于海洋安全領(lǐng)域問題的合理性.

6 新的研究挑戰(zhàn)

盡管現(xiàn)有的研究工作極大地提升了我們對于安全問題的防范能力,但是這些工作仍然是不完善的.仍然有新的應(yīng)用領(lǐng)域以及改進(jìn)方向?yàn)檠芯抗ぷ魈岢鎏魬?zhàn).這些挑戰(zhàn)多數(shù)來自于現(xiàn)有的有限計算能力,人類行為的不確定性以及現(xiàn)實(shí)場景中的特殊性質(zhì).

6.1 多目標(biāo)優(yōu)化

在現(xiàn)有的安全博弈論應(yīng)用中,防御者總是試圖最大化某個單一目標(biāo).然而,有些領(lǐng)域的防御者必須同時考慮多個目標(biāo).例如,洛杉磯警察局對地鐵系統(tǒng)的保護(hù)需要考慮逃票、普通犯罪以及恐怖襲擊等多種行為.從洛杉磯警察局的視角看,每種攻擊類型都有威脅(收入減少、財產(chǎn)被盜、生命威脅等).因?yàn)檫@些多元威脅的存在,通常沒有一種單一策略可以使所有攻擊類型的威脅最小化.由于針對某種特定攻擊的保護(hù)可能增加其他攻擊的威脅,因此,必須要做權(quán)衡和折衷.多目標(biāo)安全博弈可以用來應(yīng)對有多個相互矛盾的優(yōu)化目標(biāo)的安全博弈問題.在多目標(biāo)安全博弈中,不同攻擊類型的威脅用不同的博弈矩陣來表示,并且不需要對手攻擊類型的概率分布.與只有單個最優(yōu)解的單目標(biāo)貝葉斯安全博弈不同,多目標(biāo)安全博弈通常有一個帕累托邊界,它包含了求得的帕累托最優(yōu)解.通過將帕累托邊界展示給終端用戶,他們能夠更好地理解問題的結(jié)構(gòu)和不同安全目標(biāo)間的平衡.因此,終端用戶在選擇策略時能夠作出更明智的選擇.以上考慮的多目標(biāo)優(yōu)化任務(wù)局限于保護(hù)者角度,而攻擊者的多目標(biāo)優(yōu)化假設(shè)以及有限理性行為假設(shè)成為該方向的延續(xù)工作的相關(guān)主題得到了研究者的關(guān)注[61?62].

6.2 協(xié)同優(yōu)化

協(xié)同優(yōu)化,是指使用者(如空中警察署)和計算機(jī)協(xié)作制定的安全資源分配策略.在安全資源調(diào)度問題中通常存在很多限制條件.防御者通常受到資源數(shù)量的限制.另外,當(dāng)面臨一些特殊情況或者需要額外的知識時,使用者可能需要對防御者的行為設(shè)置限制以影響結(jié)果.例如,在IRIS系統(tǒng)中,有時需要強(qiáng)制在某些航班上安排空中警察(例如當(dāng)政府官員需要乘飛機(jī)時).在現(xiàn)有的安全博弈論應(yīng)用中,通常只計算出符合所有限制條件的最優(yōu)解.但由于使用者的有限理性以及對限制條件影響資源調(diào)度結(jié)果性能的有限了解,用戶定義的限制條件可能會產(chǎn)生很差的資源分配方案,甚至導(dǎo)致不存在滿足所有限制條件的分配方案.如果放開一些限制條件,分配方案的性能就會得到很大提升.放開一些限制條件有無數(shù)種方法,而計算機(jī)軟件并不知道哪些限制條件可以放開,放開多少,以及放開限制條件對分配方案性能的影響.因此,需要用戶和計算機(jī)通過協(xié)同優(yōu)化來共同制定安全資源分配策略.協(xié)同優(yōu)化研究面臨的挑戰(zhàn):第一,安全博弈和限制條件的規(guī)模使得不能使用窮盡的搜索算法去測試所有的限制條件組合;第二,用戶并不完全了解放開限制條件可能引起的后果,這就需要用戶偏好發(fā)掘技術(shù)(preference elicitation)的支持;第三,在用戶和計算機(jī)之間關(guān)于控制權(quán)轉(zhuǎn)移的決策也很具有挑戰(zhàn)性;第四,很難評價協(xié)同優(yōu)化方法的性能;第五,給計算機(jī)設(shè)計一個能夠解釋限制如何影響資源分配方案性能的用戶接口也是一個有挑戰(zhàn)性的問題[63].

6.3 多部門協(xié)作

在很多情況下,對于一個安全任務(wù),需要多個安全部門布置多種安全資源才能達(dá)到目的.例如,位于紐約的美國海岸警衛(wèi)隊(duì)可能需要協(xié)調(diào)從屬于海岸警衛(wèi)隊(duì)的船只和直升機(jī)以及NYPD的船只巡邏.在這種情況下,海岸警衛(wèi)隊(duì)指揮部門可能僅僅擁有關(guān)于NYPD巡邏船只的不確切的信息,但是需要在協(xié)調(diào)海岸警衛(wèi)隊(duì)自身安全資源的同時,也要與NYPD巡邏進(jìn)行協(xié)調(diào).這需要新的解的概念以及求解此類大型問題的有效算法.多部門協(xié)作問題并不限于上述例子,得到考慮的情景有不同安全部門的相同資源的布置,同一安全部門的不同資源的布置,不同安全部門的不同資源的布置[64],以及資源布置和巡邏過程中的聯(lián)合行動.聯(lián)合行動意味著保護(hù)者的多種資源能夠以團(tuán)隊(duì)工作的形式對關(guān)鍵區(qū)域進(jìn)行巡邏.這能夠?qū)τ诠粽弋a(chǎn)生超出單一資源分別進(jìn)行巡邏的震懾效果.團(tuán)隊(duì)工作更能夠預(yù)防單一保護(hù)資源在策略執(zhí)行過程中出現(xiàn)的偏差以及特殊情況帶來的巡邏過程中斷,而這能使得攻擊者沒有可乘之機(jī)來獲得更高的收益.然而聯(lián)合行動所獲得收益所具有的非線性以及問題的模塊化都為這個問題的求解帶來了特別的困難,這是在其他多部門協(xié)作場景中所不具有的[65?67].研究者利用了模塊化優(yōu)化以及分散馬爾科夫決策過程等適應(yīng)性模型和技術(shù)對這一困難進(jìn)行初步解決,而完全解決這類問題仍然需要更深入的工作.

6.4 犯罪行為建模

現(xiàn)有安全領(lǐng)域的相關(guān)工作絕大部分涉及對于博弈雙方?jīng)Q策過程的假設(shè).與經(jīng)典的理性人的假設(shè)不同,心理學(xué)以及行為經(jīng)濟(jì)學(xué)的研究進(jìn)展為我們提供了更為實(shí)際的模型,例如前景理論和量化反應(yīng)模型.大多數(shù)的這些模型具有不同于理性人假設(shè)的表現(xiàn),也使得優(yōu)化問題成為非上凸的進(jìn)而增加了求解為難度.如何探索出一個較為實(shí)際但是能夠克服優(yōu)化非上凸性質(zhì)的行為決策模型成為犯罪行為建模方面的一個考慮.同時,這些模型中具有的關(guān)鍵參數(shù)將會很大程度上影響犯罪行為建模的合理性.但是我們很難甚至幾乎不可能預(yù)知這些參數(shù)值.研究者采取機(jī)器學(xué)習(xí)手段分別對于正常數(shù)據(jù)與異常數(shù)據(jù)進(jìn)行學(xué)習(xí),對這些參數(shù)進(jìn)行預(yù)測,擬合出一個最佳的人類行為模型,提升了所建博弈模型的合理性[31,53].另外得到考慮的犯罪行為模型稱為機(jī)會性犯罪,它假設(shè)了大量潛在攻擊者隨著公共交通系統(tǒng)進(jìn)行轉(zhuǎn)站借以尋找合適的犯罪時機(jī),而巡邏人員在同樣的環(huán)境中對這樣的行為進(jìn)行檢查和抓捕,而攻擊者綜合考量每個攻擊目標(biāo)的吸引力,以及其沒有保護(hù)資源布置的情況進(jìn)行攻擊.這樣的模型結(jié)合了博弈論以及犯罪學(xué)的相關(guān)成果,為新型犯罪模型的提出提供了新的思路[68].

6.5 基于歷史數(shù)據(jù)的學(xué)習(xí)

研究工作早期應(yīng)用集中于反恐領(lǐng)域,而隨著研究范圍的擴(kuò)大,研究人員關(guān)注的安全問題也包括了日常發(fā)生的犯罪行為的預(yù)防,比如保護(hù)水產(chǎn)和海洋資源以及大規(guī)模鐵路系統(tǒng)的運(yùn)行等等.這些問題的一個關(guān)鍵特征是博弈雙方具有重復(fù)而且頻繁的交流,使得相關(guān)部門積累了豐富的數(shù)據(jù).這成為溝通博弈論領(lǐng)域與機(jī)器學(xué)習(xí)領(lǐng)域的一個契機(jī),亦即使得研究人員能夠在既往收集的數(shù)據(jù)中學(xué)習(xí)得到一個更能模擬保護(hù)者與環(huán)境以及對手之間結(jié)構(gòu)和關(guān)系以及收益情況的博弈模型[69].現(xiàn)有安全領(lǐng)域應(yīng)用的博弈收益矩陣多是在領(lǐng)域?qū)＜乙庖娨约皻v史數(shù)據(jù)的建議下確定的,但是在某些情況下,保護(hù)者很難確定攻擊者的收益,而且這些數(shù)值將會隨著時間發(fā)生變化,進(jìn)而影響到博弈結(jié)果[70].如何在盡可能少的博弈回合之下學(xué)習(xí)攻擊者的攻擊偏好,進(jìn)而為保護(hù)者設(shè)計更為有效的保護(hù)策略成為研究關(guān)注的話題.除此之外,對于動態(tài)巡邏過程中可能出現(xiàn)的中斷情況,控制系統(tǒng)如何根據(jù)現(xiàn)有巡邏資源的時間和空間信息設(shè)計出新的有效的巡邏過程,修復(fù)中斷使得整個系統(tǒng)正常運(yùn)轉(zhuǎn)下去[71].這成為在數(shù)據(jù)中學(xué)習(xí)的一個重點(diǎn)關(guān)注場景.