頻譜稀缺是許多通信系統面臨的問題，在軍事領域和其他領域都是如此。認知無線電網絡是一種機會主義地利用廣播頻譜的方法。其基本概念包括將用戶分為兩類：第一類和第二類。主要用戶在資源分配過程中擁有優先權，而次要用戶需要使用頻譜進行通信。本論文試圖應用認知無線電的概念來實現高流量環境下的蜂群通信。主要用戶可能包括無法控制的優先友好或敵對發射器。這項研究采用了認知無線電的概念和機器學習算法，在網絡內開發了一種動態聚類技術，將優化資源分配。提出了三種方法來訓練神經網絡以找到最佳的頻譜分配。即使提出的算法沒有超過基線啟發式的表現，但證明了最優解決方案的存在。建議繼續這項研究，因為所使用的算法可以進一步修改并以各種方式應用。

網絡空間是支持戰場物聯網（IoBT）的數字通信網絡，是以防御為中心的傳感器、計算機、執行器和人類以數字方式連接的模式。一個安全的IoBT基礎設施有助于在分布式子系統中實時實施觀察、定位、決定、行動（OODA）循環。網絡犯罪分子和戰略對手的成功黑客行為表明，像IoBT這樣的網絡系統并不安全。三條工作路線展示了一條通往更強大的IoBT的道路。首先，收集了企業網絡流量的基線數據集，并通過生成方法對其進行建模，允許生成真實的、合成的網絡數據。接下來，通過算法制作了網絡數據包的對抗性例子，以欺騙網絡入侵檢測系統，同時保持數據包的功能。最后，提出了一個框架，使用元學習來結合各種薄弱模型的預測能力。這導致了一個元模型在數據包的整體準確性和對抗性實例檢測率方面優于所有基線分類器。國防戰略強調網絡安全是保衛國土和在信息時代保持軍事優勢的必要條件。這項研究提供了學術觀點和應用技術，以推進美國防部在信息時代的網絡安全態勢。

圖 22. 對抗性樣本的生成和測試的4個步驟

圖23. 元學習框架通過智能地結合每個基礎模型的預測能力來加強對對抗性攻擊。對抗性訓練的分類器是通過5.3所述的增強數據集進行訓練。

論文引言

1.1 動機

美國國防部（DoD）預計，未來的戰爭將主要在網絡領域進行，對手包括戰略競爭對手和非國家行為者。由于美國從未打過一場全面的網絡戰爭，因此對 "路線規則"并不十分了解[6]。敵人有可能通過已知和未知的威脅載體來攻擊美國的利益。這些攻擊的影響可能是非動能性的，即對信息系統的未獲許可的訪問或控制，或者是動能性的，即攻擊導致物理資產的破壞、基礎設施的損害或死亡。許多遺留的網絡物理系統在建造時沒有預見到網絡漏洞[7]。隨著戰場物聯網的發展，包括更多的這些系統，潛在的網絡威脅暴露也在增加。想象一下，當士兵的可穿戴設備在戰斗中因網絡攻擊而發生故障時，會出現怎樣的混亂。至關重要的是，我們要在對手利用這些缺點之前，用新技術解決我們軍隊的網絡安全問題。生成式機器學習和元學習是新興領域，可能為網絡安全研究中一些長期存在的障礙提供解決方案。

入侵檢測系統（IDS）是一種阻止和防御網絡攻擊的方法[7]。不幸的是，IDS需要大量的數據集進行訓練[2]。有機的網絡攻擊數據，帶有標記的條目，是出了名的稀缺。NSL-KDD[8]試圖糾正被廣泛引用的KDD-CUP基準數據集的問題，然而，即使是改進的版本也是過時的，而且范圍有限。

生成式機器學習是人工智能的一個領域，有可能以新的方式解決未解決的問題。諸如馬爾科夫鏈蒙特卡洛、自動編碼器和生成對抗網絡（GANS）和自動編碼器的方法被用來估計未知的概率分布函數。對多樣化和現實的生成數據的應用是很迫切的，特別是對網絡。生成方法提供了一個分析和綜合網絡數據的途徑，而生成方法與元學習的結合提供了一個防止某些網絡攻擊的機會。

本章的其余部分介紹了三個促進美國網絡系統安全的研究課題。第2章提供了一個相關主題的總體文獻回顧，以及一個精心挑選的可能對讀者特別有價值的來源的快速參考表。第3至5章提供了與貢獻1、2和3相對應的已完成的研究手稿。以前發表的研究是第六章，最后總結了研究的主要發現以及它們對現代防御的影響。附錄提供了不適合于主文件的額外信息。附錄A是元學習NIDS的相關研究，不適合于所述貢獻。附錄B是一個參考的AFIT論文表。附錄C包括支持貢獻1的數據表格。

1.2 研究貢獻

本論文提出了三個研究課題以支持軍隊安全態勢的現代化。雖然每個課題都可以獨立進行，但本論文采取了連續的方法，早期研究的結果增強了后來的工作。本論文的總體目標是證明在建立一個對對抗性攻擊具有強大抵抗力的入侵檢測系統方面取得了重大進展。

貢獻1：生成真實的合成網絡數據。

第一個研究目標是對現代網絡數據的概率分布進行建模，并從基線分布中生成額外的、現實的數據。預定的生成模型可以是明確的，以概率分布函數的形式，或隱含的，如GAN。生成方法將在第2.2節討論。無論怎樣，模型生成的現實數據必須證明與基線數據的分布相匹配。與第4.2節中NSL-KDD[8]、KDD-CUP[9]、UNSW-NB15[10]等其他基準數據集不同，生成的數據必須能夠代表現代政府系統中的網絡流量，包括授權和惡意行為者的例子，而且比例適當。惡意流量必須是現代網絡攻擊的代表，并反映原始分布中未觀察到的例子。一個可能的策略是通過在敵對環境中收集的真實網絡數據或在現實的高保真模擬中收集的數據來訓練一個生成模型。然后，基線數據可以用來訓練一個生成模型，能夠從與基線相同的分布中創建新的、現實的例子。

特別是，生成模型應該強調對模式崩潰的復原力，并且應該對變量之間的宏觀層面的關聯性進行建模。如果成功，現實生成的網絡數據將被用作創建對抗性例子的起點。擴大的、生成的數據集比小的真實數據集更受歡迎，因為它展示了生成方法的可行性，以克服新型網絡攻擊中的數據不足。隨著網絡日志數據中新現象的發現，它們將被復制到更大的數量，有利于創建對抗性例子和強大的IDS。如果生成方法不能產生現實的數據，那么目標二可以使用數量更多的基線數據來實現，而這些數據的獲取是昂貴和費力的。為了支持貢獻1，已經提交并接受了兩篇存檔的同行評審論文。《網絡領域生成方法的挑戰和機遇》已被《2021年冬季模擬會議論文集》接受，《為訓練和評估網絡入侵檢測系統的機器學習分類器生成現實的網絡數據》已提交給《應用專家系統》。這兩項工作都是由Marc Chal′e（主要作者）撰寫的，委員會成員為支持學位論文研究做出了貢獻。支持貢獻1的工作在第三章和附錄C中介紹。

貢獻2：生成對抗性樣本。

第2個研究目標是產生能夠躲避現代IDS的對抗性樣本。對抗性樣本必須使用新的技術來創建，包括適用的生成方法。對抗性樣本必須超越諸如[11]的工作，強制執行網絡數據的不可變方面[12]，并實現端到端的攻擊。解決這一挑戰可能會增加最先進的網絡攻擊對當前IDS的有效性，但一旦這些技術被確定，它們就可以在強大的IDS中得到解決。盡管最近在計算機視覺領域創造對抗性攻擊方面取得了進展，但在網絡領域產生對抗性攻擊是特別具有挑戰性的[12]。為了使被擾亂的互聯網協議（IP）數據包能夠促進端到端的網絡攻擊，數據包必須保持其專門的數據結構以及執行時的原始功能。雖然圖像可以不受限制地被擾動，并產生一個有效的圖像文件，但在互聯網上傳輸的IP數據包在擾動過程中會被破壞，導致無效的端到端攻擊。盡管最初對網絡領域的對抗性攻擊的研究[11] [13] [14]集中在擾亂網絡數據的特征向量上，但更困難的任務是擾亂網絡數據包的實際有效載荷，同時保持其原始功能[13] [15] [12]。或者，可以生成一個對抗性的特征向量，然后反向設計成一個能躲避IDS的功能性IP數據包。在努力實現端到端黑盒攻擊的過程中，我們必須證明對抗性例子可以被限制在網絡領域的標準內。這一目標在提交給《計算機與工業工程》的期刊文章《基于約束優化的網絡入侵檢測系統轉移攻擊的對抗性實例生成》中實現。 這項工作是由Marc Chal′e（主要作者）撰寫的，委員會成員為支持論文研究做出了貢獻。支持貢獻2的工作在第四章和附錄D中介紹。

貢獻3：展示一個強大的入侵檢測系統。

入侵檢測系統在保護網絡系統數據的保密性、完整性和可用性方面發揮著重要作用，但它們存在根本性的缺陷。幾種流行的基于規則的IDS對惡意軟件的檢測率在實踐中是驚人的低。一項研究發現，Zeek使用其基于規則的警報系統只檢測到52%的惡意軟件攻擊[16]。這種乏善可陳的表現可能促使了機器學習入侵檢測系統的最新發展。雖然近年來IDS的能力有所提高，但對手也在不斷創新他們的方法。此外，自2005年以來，美國報告的入侵事件的比率一直在增加。大多數IDS漏洞被認為是規避攻擊的結果，其中IP數據包被修改為看似無害，但實際上是有害的[17]。在現代，諸如[11]這樣的規避攻擊使用啟發式方法來擾亂IP數據包的特征，騙過IDS。

因此，最終的研究目標是利用GML和元學習等技術，提高基于機器學習的IDS的分類性能和魯棒性，如[2]。通過分類性能，我們特別指出了召回率（檢測率）和準確率的指標。穩健性是指算法對來自于與訓練所用的例子不同的分布的例子有很好的概括傾向[18]；它是當今網絡環境中模型的一個越來越重要的特征。

雖然貢獻2暴露了基于ML的IDS的安全漏洞，但貢獻3提供了一個解決方案。這一研究目標在MADFACTS中實現。MADFACTS: Meta-learning Augmented Defense For Adversarial Cyber Techniques是一篇已完成的長篇文章，正等待提交給《計算機與安全》、《未來互聯網》或《優化通訊》等刊物。這項工作是由Marc Chal′e（主要作者）撰寫的，委員會成員為支持論文研究做出了貢獻。支持貢獻3的工作將在第四章介紹。

影響。

上述研究目標對物聯網的網絡防御和整個國家安全有協同的影響。貢獻1旨在解決網絡領域長期缺乏標記的高質量訓練數據的問題。貢獻2提供了一個技術優勢，以對抗那些希望開發針對物聯網的新型對抗性攻擊的網絡犯罪分子和對手。貢獻1和貢獻2的成功加強了貢獻3的工作，其中一個強大的IDS擊敗了對手的例子。這些成就符合軍事戰略的更大愿景，即在所有領域（包括網絡、空間、陸地、空中和海上）實現機動性自由。加強整個IoBT的網絡安全對于指揮官在現代跨域戰爭中造成預期的影響是必不可少的，因為指揮、控制、情報和識別是決策的骨干，而且越來越數字化了。這項研究提供了一條有希望的途徑，以提高對抗不斷變化的攻擊威脅的穩健性。

為了打擊日益多變和易變的現代惡意軟件，機器學習（ML）現在是對現有基于簽名的惡意軟件分流和識別技術的一種流行和有效的補充。然而，ML也是對手的一個現成的工具。最近的研究表明，惡意軟件可以通過深度強化學習（RL）技術進行修改，以繞過基于人工智能和基于簽名的反病毒系統，而不改變其原有的惡意功能。這些研究只專注于生成規避樣本，并假設靜態檢測系統為敵人。

惡意軟件檢測和回避本質上形成了一個雙方的貓鼠游戲。在本文中，我們模擬現實生活中的場景，按照零和多智能體強化學習（MARL）的范式，提出了第一個用于規避惡意軟件檢測和生成的雙人競爭博弈。我們對最近的惡意軟件進行的實驗表明，所產生的惡意軟件檢測智能體對對抗性攻擊更加強大。此外，所產生的惡意軟件修改智能體能夠產生更多的規避樣本，騙過基于人工智能和其他反惡意軟件技術。

關鍵詞：對抗性學習，惡意軟件分析，神經網絡，強化學習，馬爾科夫決策過程

圖1：單次的H4rm0ny訓練過程。還顯示了所有系統配置的結果。從我們的數據集中選擇一個惡意軟件的樣本。然后，它被送到一個修改的過程中。如果任何修改產生了一個惡意軟件的回避樣本，該樣本將被訓練成檢測智能體。一旦樣本被訓練成檢測智能體，修改智能體的策略就會隨著對惡意軟件樣本和檢測智能體的狀態所采取的一系列行動而更新。

近年來，針對工業生態系統的高級持續性威脅（APT）的復雜性急劇增加。這使得開發超越傳統解決方案的高級安全服務成為必須，輿論動力學（Opinion Dynamics）就是其中之一。這種新穎的方法提出了一個多智能體協作框架，允許跟蹤APT的整個生命周期。在本文中，我們介紹了TI&TO，這是一個攻擊者和防御者之間的雙人博弈，代表了一個現實的場景，雙方都在爭奪現代工業結構中的資源控制權。通過使用博弈論來驗證這種技術，我們證明，在大多數情況下，輿論動力學包括有效的第一項措施，以阻止和減少APT對基礎設施的影響。為了實現這一目標，攻擊者和防御者的模型都被標準化，并應用了一個公平的評分系統，后者用不同的策略和網絡配置運行了幾個模擬測試案例。

引言

世界各地的公司面對的網絡安全攻擊數量明顯增長，導致了巨大的經濟損失[2]。當涉及到關鍵的基礎設施（即核電站、電網、運輸和制造系統）時，這種情況變得更加嚴重，其工業控制系統必須在所有條件下保持工作。在這里，我們處理的是SCADA（監督控制和數據采集）系統，幾十年來一直在與外部網絡隔離的情況下工作；反過來，如今它們正越來越多地整合新技術，如物聯網（IoT）或云計算，在削減成本的同時外包各種服務。因此，需要做出更大的努力來跟上這種進步，以應對這些系統可能帶來的最新的攻擊載體和可利用的漏洞。

近年來最關鍵的問題之一是高級持續性威脅（APTs），這是一種復雜的攻擊，特別是針對目標基礎設施，由一個資源豐富的組織實施。它們的特點是利用零日漏洞（零時差攻擊），采用隱蔽技術，使威脅在受害者網絡中長期無法被發現。Stuxnet是第一個報道的這種性質的威脅[6]，但許多其他的威脅在之后被發現，通常是在攻擊完全執行后的幾個月[7]。在網絡安全方面，只是提出了一些機制來從整體上解決這個問題，超越了傳統的機制（如防火墻、入侵防御系統（IPS）、入侵檢測系統（IDS）、防病毒），這些機制只代表了在第一階段對APT的準時保護[21]。

在這些新穎的機制中，輿論動力學（Opinion Dynamics）[15]包括一個多智能體協作系統，通過分布式異常關聯，使攻擊的整個生命周期都可以被追蹤。在本文中，我們提出了一個理論但現實的方案，以證明該方法在不同類型的攻擊模式下的有效性，使用結構可控性領域[8]和博弈論[14]支持的概念。為了這個目標，我們開發了TI&TO，這是一個雙人博弈，攻擊者和防御者為控制現代工業結構中的資源而競爭。兩個玩家都有自己的動作和相關的分數，分別根據APT和基于Opinion Dynamics的檢測系統的行為。這個博弈最終在不同的模擬中運行，旨在展示算法的能力，同時也建議將該技術與其他防御方案結合起來進行最佳配置。因此，我們可以把我們的貢獻總結為：

• 正式定義TI&TO博弈，指定游戲板、每個玩家的目標和得分規則。
• 設計一個攻擊者模型，以一組階段的形式，靈活地表示APT的各個階段，以表示攻擊者的行動，這些行動受制于一個確定的分數。
• 設計一個基于使用意見動態和響應技術（即本地檢測、冗余鏈接、蜜罐）的防御者模型，以減少APT在網絡中的影響，這也意味著博弈中的相關得分。
• 進行的實驗驗證了該算法，并推薦了返回最佳結果的防御者的配置。

本文的其余部分組織如下。第2節介紹了 "輿論動力學"的概念，并強調了應用博弈論來檢測網絡攻擊的建議。在第3節中，定義了博弈，包括規則以及攻擊和防御模型。然后，進行了幾次模擬，并在第4節進行了討論。最后，在第5節中提出了結論和未來的工作。

非線性系統允許我們描述和分析物理和虛擬系統，包括動力系統、電網、機器人和神經網絡。涉及非線性的問題對在不確定性存在的情況下提供安全保證和魯棒性提出了挑戰。本文提供了利用非線性上界和下界知識的方法，解決了參數不確定的魯棒性驗證和優化問題。本文的前半部分發展了由一組非線性等式和不等式約束定義的非凸可行性集的凸約束。凸約束為求解非線性方程組提供了一個閉型凸二次條件。將原約束替換為所提出的條件，可將非凸優化問題求解為一系列凸優化問題，具有可行性和魯棒性保證。我們演示了它在模型預測控制(MPC)、神經網絡的魯棒性驗證、魯棒最優潮流(OPF)問題和機器人運動規劃中的應用。論文的第二部分關注非線性動力系統，并發展了驗證問題的可達性分析和約束輸入約束輸出分析。我們提供了一種基于優化的方法來計算標稱軌跡周圍的可達集。提出的方法使用收縮度量為可達集尋找模板。此外，我們開發了約束輸入-約束輸出分析來表征輸入和輸出信號的峰值量之間的關系。數值實驗證明了它們對一類廣泛的非線性系統的適用性。

//dspace.mit.edu/handle/1721.1/144602

在存在智能對手的情況下，博弈論模型（如安全博弈）已被證明是減輕保護和安全協議中可利用漏洞風險的有效工具，因為它們模擬了對手和防御者之間的戰略互動，并允許防御者在面對這種對手時計劃使用稀缺或有限的資源。然而，標準的安全博弈模型在允許防御者執行的規劃類型方面具有有限的表現力，因為它們只關注一組固定的安全資源的部署和分配。這忽略了兩個非常重要的規劃問題，它們涉及安全系統的戰略設計和部署的資源，以及安全協議的可用性和實施。當這些問題出現在現實世界的系統中時，如果不以一種原則性的方式來處理，安全協議的效用和效率就會出現重大損失。

為了解決這些局限性，在這篇論文中，我為安全博弈的規劃問題引入了一個新的層次結構，將問題分為三個層次的規劃（i）戰略規劃，考慮長期的規劃期限，以及與游戲設計有關的決策，這些決策限制了可能的防御者策略；（ii）戰術規劃，考慮較短的期限，處理資源的部署，以及在戰略層面的限制下選擇防御者策略；（iii）行動規劃，處理在現實世界中的策略實施。

首先，以戰略規劃為重點，我討論了選擇一組資源和時間表類型的設計問題。我引入了一個新的基本問題，即資源團隊和戰術的同步優化（SORT），它模擬了戰略和戰術規劃的耦合問題，在選擇資源類型方面對游戲設計進行了優化，并對它們在現場的實際部署進行了優化。我提供了有效解決SORT問題的算法，該算法使用優化問題的分層放松來計算這些戰略層面的投資決策。我表明，這種更具表現力的模型使防御者能夠進行更精細的決策，從而在效用上獲得巨大的收益。其次，在資源異質性的安全博弈的相關性和艱巨性的激勵下，我還通過提供一個計算異質資源的適應性策略的框架來解決戰術規劃方面的挑戰。最后，我研究了行動規劃的問題，這在安全博弈的文獻中從未被正式研究過。我提出了一個可操作策略的新解決方案概念，它隨機選擇一個最優選擇的純策略子集，其基數由防御者選擇。我展示了計算這種可操作策略的難度，并提供了一種用于計算可操作的最佳均衡的算法。

在所有這些問題中，我的動力來自于現實世界的挑戰，以及開發可在現實世界中使用的解決方法。因此，許多工作都是與Panthera、WWF和其他非政府組織（NGO）合作，幫助保護國家公園和野生動物免受森林砍伐和偷獵，以及與TSA合作，保護我們的機場等關鍵基礎設施免受恐怖襲擊。正因為如此，在處理這三個層次的規劃時，我開發的解決方案不僅是新穎的、學術上有趣的，而且是可部署的、對現實世界有影響的。

學位論文摘要

在這篇論文中，我們研究了博弈論在確定各種基礎設施保護策略的應用。博弈模型是在防御者和對手之間進行的。防御者尋求最小化對基礎設施網絡的損害，而對手的目標則是最大化。本論文分為兩部分。在第一部分，我們考慮資源分配博弈模型，在第二部分，我們研究巡邏和搜索博弈。

在資源分配博弈領域，我們解決了文獻中現有的一些限制。其中一個限制是，這些模型大多假設博弈的參數是確定的，或者遵循一個已知的分布。而在現實中，博弈的某些參數可能是不確定的，沒有已知的分布，或者關于它們的分布信息可能是不可靠的。為此，我們研究了目標估值不確定情況下的一次性安全博弈。我們提出了一個模型，在這個模型中，雙方都使用一種穩健的方法來應對目標估值的不確定性。我們表明這個模型的納什均衡是門檻型的，并開發了封閉式的解決方案來描述均衡點的特征。然后，我們將我們的模型應用于向美國10個城市地區分配安全資金的真實案例。

另一個限制是缺乏解決分層決策的模型。保護基礎設施及其用戶免受蓄意攻擊，需要在組織結構中做出戰略和運行決策。盡管通常是分開分析的，但這些決策是相互影響的。為了解決這個問題，我們開發了一個兩階段的博弈模型。在第一階段，玩家做出投資決策，在第二階段，他們決定保衛/攻擊哪些網站。我們區分了在第二階段出現的兩種類型的博弈。最大損害博弈和滲透/騷擾博弈。我們證明，在預算約束下，這個博弈的解決方案是唯一的。事實上，當第二階段的博弈是滲透/騷擾類型時，投資-防御博弈有一個獨特的閉式解，這是非常直觀的。結果顯示，增加對一個目標地點的防御投資會降低防御和攻擊該目標的概率。然而，攻擊投資的增加會增加防守和攻擊該目標的概率。同樣，防御者（攻擊者）投資效率的提高會導致防御者和攻擊者的投資減少（增加）。我們還將提出的模型應用于一個真實的案例。真實數據的結果表明，攻擊者從失敗的攻擊中得到的懲罰是決定防御者的投資和防御概率的最佳分布的重要因素。防御者的第二階段防御決策是對第一階段投資決策的補充。也就是說，在得到很少或零投資的目標地點中，最重要的一個地點在第二階段以相對高的防御概率被覆蓋。此外，隨著攻擊者預算的增加，防御投資從不太重要的站點轉移到更重要的站點。

我們還研究了資源分配模型中的總體性保護選項。總體保護指的是同時保護多個目標的選項，例如，應急響應、邊境安全和情報。大多數帶有總體保護的防御性資源分配模型都假定只有一個總體保護選項可以保護所有目標。然而，這可能并不現實，例如，應急反應投資可能只覆蓋某個區域。為了解決這個問題，我們開發了一個新的資源分配模型，以適應針對故意攻擊的通用總體保護。該模型還考慮了多種自然災害類型。我們表明，我們提出的模型是一個凸優化問題，因此可以在多項式時間內求解到最佳狀態。此外，整個國家層面的資源分配問題可以被分解成更小的城市層面的子問題，從而產生一個更有效的算法。數字實驗證明了所提方法的性能。

巡邏和搜索博弈通常是在一個圖上進行的，玩家在一個時間范圍內做出決策。在巡邏博弈中，防御者控制一組巡邏者并指揮他們在圖上行走，以盡量減少對手的攻擊損失，而對手則選擇一個目標和攻擊時間。為了成功地摧毀一個目標地點，對手需要一些準備時間而不被巡邏者打斷。大多數巡邏博弈模型都假設站點的價值是相同的，或者說它們不會隨時間變化。然而，這并不是一個現實的假設。特別是在軟目標的情況下，這些值可能對應于一個地點的占用水平，因此，這樣的值可能是不同的，并可能隨時間變化。我們提出了具有隨時間變化的節點值和基于節點的攻擊時間的新模型。我們使用列生成、列和行生成等算法數值地解決這些模型。我們將這些算法應用于美國一個主要城市的城市鐵路網的真實案例。結果顯示了所提出的解決方法的效率。他們還證明了額外的巡邏員的回報率是遞減的。

在搜索博弈中，一個隱藏者將一組物體隱藏在一組潛在的隱藏地點。搜索者控制一組搜索隊，指揮他們在網絡上行走，找到隱藏的物體，使目標函數得到優化。然而，在某些情況下，玩家可能會將藏匿地點相互區分開來，目標是優化加權搜索時間。為了解決這個問題，我們引入了一個新的離散搜索博弈，并考慮到了不同地點的權重。我們表明，在某些條件下，該博弈有一個封閉式的納什均衡。對于一般情況，我們開發了一種基于列和行生成的算法。我們表明搜索者的子問題是NP-hard的，并提出了一個分支和價格算法來解決它。我們還提出了一個用于Hider子問題的多項式時間算法。數值實驗研究了該方法的性能，并揭示了對該博弈特性的洞察力。

第一章 簡介

恐怖襲擊是對國民經濟和生活質量的一個嚴重關切。每年都有成千上萬的人因為這些襲擊而喪生或受傷或被綁架。2015年，全世界共發生11774起恐怖襲擊事件，造成28300多人死亡，35300多人受傷。此外，有超過12,100人被綁架或劫持為人質[22]。恐怖主義的持續威脅帶來的心理影響也是相當大的。這類事件在社會上造成了恐懼、驚慌、焦慮和苦惱。

保護關鍵基礎設施不受恐怖主義侵害是國土安全的首要任務之一[104]。對關鍵基礎設施的物理保護可以防止成功實施高影響力的恐怖襲擊。此外，對針對關鍵基礎設施的恐怖襲擊作出即時反應，可以防止與此類襲擊相關的連帶效應。

這些原因以及在過去幾十年中發生的許多引人注目的恐怖襲擊，突出了此類基礎設施的安全建模和分析是一個主要的研究議程。通過評估與基礎設施內每個站點相關的風險、緩解計劃以及設計保護戰略和響應政策，可以大大減少攻擊的后果。基礎設施安全最近成為研究人員越來越感興趣的主題。人們提出了不同的方法來模擬安全問題中的戰略互動，這些方法包括系統分析[115]、數學建模[51]、概率風險分析[33, 39, 73, 100, 115, 116]，以及對抗性風險分析[123]。然而，由于恐怖分子的攻擊可能是戰略性的，對這種攻擊的博弈論分析會產生更真實的結果。因此，最近的研究集中在開發博弈論模型來捕捉恐怖主義風險，并將結果應用于加強安全措施。其中一個模型ARMOR[112, 113, 114, 118]已被部署在洛杉磯國際機場（LAX）以加強機場的安全。

這項研究的重點是博弈論的應用，為各種基礎設施尋找最佳保護策略，以抵御蓄意攻擊。這項工作可以分為兩部分：資源分配模型，以及巡邏和搜索博弈模型。

為防止蓄意攻擊而進行的資源分配通常是昂貴的，決定如何分配資源以保護關鍵基礎設施是一個困難的問題。許多因素會影響這種分配政策，例如，在實踐中，公平在確定防御分配方面起著重要作用[129]。此外，創造一種平衡以保護不同類型的威脅（例如，生物攻擊與炸彈攻擊，或恐怖主義與非恐怖主義預防活動之間）是另一個因素。其中一些因素已經在靜態安全博弈的文獻中得到了解決。然而，仍然有一些限制。例如，大多數基礎設施安全博弈假設博弈的參數是確定的或遵循一個已知的分布。而在現實中，博弈的一些參數可能是不確定的，沒有已知的分布，或者關于它們的分布信息可能是不可靠的。在這項研究中，我們建立了具有和不具有私人信息的不完全信息基礎設施安全博弈的穩健無分布模型。此外，決策的層次性在文獻中經常被忽略。然而，分配資源以保護關鍵的基礎設施涉及到組織結構中不同層次的決策：戰略和運行決策。這些決策相互影響，需要同時進行研究。在這項研究中，我們開發了兩階段的博弈模型來解決這個問題。此外，大多數現有的帶有總體保護選項的資源分配模型都假定只有一個總體保護選項可以保護所有目標。然而，在現實中，可能有許多總體保護方案，而每個方案可能只覆蓋一個子集的目標。為了解決這個問題，我們開發了一個新的資源分配模型，該模型具有通用的總體保護選項。我們還開發了高效的分解算法來尋找最佳的資源分配。

巡邏和搜索博弈通常是在一個圖形上進行的，玩家在一個時間范圍內做出決定。設計巡邏隊來保護開放的大眾運輸系統和其他軟目標帶來了獨特的挑戰，這些挑戰在巡邏博弈的文獻中還沒有被解決。其中一個挑戰是這些系統內人群規模的動態性質。因為對手的主要目標是造成人員傷亡，所以節點的價值取決于居住在這些節點的人數。這些數字隨著時間的推移而變化，恐怖分子往往根據這些變化來確定他們的攻擊時間[68]。其他挑戰包括處理多個攻擊者，適應人力資源的限制，以及開發有效的方法來設計一般網絡的巡邏。我們通過開發具有動態變化的節點值、基于節點的攻擊時間、多個巡邏員和多個攻擊者的新模型來應對這些挑戰。為了有效地解決這些模型，我們開發了先進的解決算法，如列生成，以及列和行生成。在搜索博弈中，一個隱藏者將一組物體隱藏在一組潛在的隱藏地點。搜索者控制一組搜索隊，指揮他們在網絡上行走，找到隱藏的物體，從而使目標函數得到優化。大多數搜索博弈模型都假定隱藏地點是相同的，玩家的目標是優化搜索時間。然而，在某些情況下，玩家可能會將藏匿地點相互區分開來，目標是優化加權搜索時間。為了解決這個問題，我們引入了一個新的離散搜索博弈，并考慮到了不同地點的權重。

1.1 問題陳述和研究動機

本研究考慮的主要問題是確定針對故意破壞（如恐怖襲擊）的最佳保護策略。因為對手的決策也是有策略的，所以對這些問題的博弈論分析會產生更現實的結果。本研究中考慮的博弈模型是在防御者（她）和對手（他）之間進行的。防御者想要最小化對基礎設施網絡的損害，而對手則想要最大化。這些模型可以分為兩類：資源分配博弈，以及巡邏和搜索博弈。在資源分配模型中，有一個N個目標的集合。每個目標i都有一個Ci的值。防守方決定防守哪個目標，而對抗方決定攻擊哪個目標。如果雙方都選擇相同的目標i，那么以δi的概率，攻擊將被檢測并挫敗。這個概率被稱為檢測概率。以下矩陣的(i, j)部分顯示了如果防御者選擇目標i，而對手選擇目標j的預期損害。注意，這個矩陣對應于對手的報酬矩陣，對手試圖使預期損害最大化。

我們的目標是在各種條件下，如博弈參數的不確定性和私人信息的存在，以閉合形式描述納什均衡（NE）的特征。

我們在這篇論文中討論的另一個問題是決策的層次性。保護基礎設施及其用戶不受破壞，需要在一個組織的層次結構中做出戰略和運行決策（見圖1.1）。戰略決策是具有長期影響的長期決策。例如，對目標站點進行 "加固"[17]以減少攻擊的成功概率的投資決策被歸類為戰略決策。這包括對新技術的投資，以加強網站的安全性。另一方面，運行決策是與日常運作有關的短期決策，如巡邏、分配第一反應者和安排車輛檢查站。請注意，"戰略 "這個詞也可以用來描述參與者。在這種情況下，"戰略玩家 "指的是一個理性的玩家，其目標是最大化回報。因此，在本論文中，"戰略決策 "是指具有長期影響的長期決策，"戰略參與者 "是指以報酬最大化為目標的理性參與者。大多數研究只關注純粹的戰略決策[63, 107]或純粹的運行決策[16, 35, 36, 38]。然而，這些決策是相互影響的。例如，在某一區域安裝閉路電視攝像機可能會使該區域的巡邏變得不必要。或者將金屬探測器和安檢系統分配給目標地點，可能會影響到這些目標中巡邏隊的最佳調度。此外，投資一項新技術以加強某個目標地點的安全，可能會降低其目標的吸引力，影響保衛該目標的最佳概率。因此，在同一個模型中考慮戰略和行動決策會產生一個更全面的分析。

圖1.1: 戰略決策與運行決策

我們研究了在考慮到人為和自然災害的資源分配模型中總體保護方案的影響。總體保護方案是指可以同時保護多個目標的替代方案。例如，對邊境安全和情報工作的投資有望保護多個目標免受恐怖主義的威脅。這一領域現有文獻的局限性在于，大多數現有的模型只考慮了保護所有目標的單一總體性保護方案。然而，這可能不是對現實的準確表述。例如，對邊境安全的投資可以分為不同的入境點，每一個入境點預計都會使離該特定入境點較近的地區受益。為此，一個新的資源分配模型，容納多個保護目標子集的總體保護措施，將導致一個更現實的分析。

本研究中調查的巡邏博弈G是一個由防御者和對手在連接圖Q = (N , E)上進行的零和博弈，節點集為N，邊集為E，時間跨度為T。防御者控制著一組安全人員（巡邏者）S，并指示他們在圖上行走，以盡量減少來自對手的攻擊的損害。而敵方控制著一組攻擊者A，并為每個攻擊者選擇一個節點和一個攻擊時間。為了成功地摧毀一個目標站點，攻擊者需要在目標上有一定數量的時間單位，不被任何巡邏者打斷。巡邏博弈文獻中的大多數論文都假設對手選擇一個目標進行攻擊，目標值在一段時間內是固定的，有些甚至假設所有目標是不可區分的，即它們都有相同的價值。然而，在許多現實情況下，情況并非如此。例如，在一個交通設施中，每個地點的人數、占用水平可以被認為是該地點的價值。此外，占用水平可能隨時間變化，預計在高峰期，占用水平會比正常時間高。因此，一個具有隨時間變化的節點價值、特定節點的攻擊時間、多個巡邏者和多個攻擊者的巡邏博弈模型將導致與現實更加一致的結果。

本研究中考慮的搜索博弈是在搜索者和隱藏者之間進行的。搜索者控制一組S個搜索隊，隱藏者控制一組H個要隱藏的對象。博弈是在一個完整的圖Q = (N , E)上進行的，其中N = {0, 1, 2, . ，N}是圖中節點的集合，E = {(i, j) : i, j∈N, i 6 = j}是邊的集合。文獻中的大多數搜索博弈模型都假設藏身之處是相同的，玩家的目標是優化搜索時間。然而，在某些情況下，玩家可能會將藏身之處相互區分開來，其目標是優化加權搜索時間。例如，在某些攻擊中（生物或化學），傷亡率取決于人口密度、環境條件等因素。因此，不同的地點可能有不同的傷亡率，而整體的損失將與暴露時間和傷亡率成正比。另一個例子是通過通信渠道檢測竊聽者的問題[37]。不同的信道可能有不同的傳輸能力，對網絡的破壞率將與檢測時間和信道的容量成正比。此外，藏匿地點可能分散在大片區域，搜索可能涉及多個搜索小組。為此，一個新的搜索博弈，容納了不同地點的不同權重，將導致一個更現實的分析。

1.2 研究貢獻

在這項研究中，提出了新的博弈論模型，以解決資源分配博弈、巡邏和搜索博弈領域中的一些現有差距。在資源分配博弈領域，主要貢獻是：擴展現有模型以處理分層決策；引入廣義的總體保護方案；用穩健的方法解決參數的不確定性；開發適合于更有效算法的新模型。在巡邏和搜索博弈領域，我們的主要貢獻是：納入了與時間相關的節點值，以及多個巡邏者和多個攻擊點；并引入新的和更有效的算法來解決博弈論模型。

在接下來的章節中，我們將介紹我們的主要貢獻，如下所述。

1.我們開發了一種穩健的方法來應對安全博弈中的參數不確定性，并在第二章提供了閉合形式的NE策略。

2.為了解決防范蓄意攻擊的決策的層次性問題，在第三章中，我們引入了一個兩階段的投資-防御博弈模型，并推導出某些條件下的閉合形式的NE策略。這個模型抓住了戰略投資決策和運行攻擊/防御決策的綜合效應。

3.在第四章中，我們提出了一個新的資源分配模型，用于保護資產免受人為和自然災害的影響，并具有廣義的總體保護。這個模型被證明導致了一個可分解的凸優化問題，因此可以被有效解決。

4.在第五章和第六章中，我們介紹了新的巡邏博弈模型，該模型具有與時間相關的節點值，基于節點的攻擊時間，多個巡邏者和多個攻擊點；并開發了高效的解決方法，基于列生成，以及列和行生成來解決現實的大小問題。

5.我們在第七章中介紹了一個新的搜索博弈模型，該模型具有不同的節點權重、多個搜索隊、多個隱藏對象和分散的隱藏地點；并在第七章中介紹了基于列和行生成的高效求解方法，以解決現實的大小模型。

6.我們在第八章中提出了本研究的結論并討論了未來的研究思路