達成網路存活性最大化之近似最佳化網路防禦資源配置策略

Abstract

由於電腦硬體成本逐漸下降、軟體性能逐漸上昇，大部份的關鍵性網路都已電腦化控制。這些與日常生活息息相關的網路系統，一旦其毀損，除了對我們的生活造成極大的不方便，更是在生命與財產方面，引起不小的損失。所以，有效地評估與衡量關鍵性網路系統的存活性，是現今資訊安全領域中亟需重視的議題。 有鑑於此，我們提出一個全新且簡單的網路存活性指標—網路分隔度(Degree Of Separation, DOS)。這是一種網路傷害指標，用來衡量網路遭受毀損的平均程度。DOS值愈大，代表其網路毀損愈嚴重，即表示必須付出更大的代價去修復整個網路。倘若其損害程度大於某一門檻值，則我們宣稱該網路已全然毀損。 因此，我們模擬一個網路攻防情境以建立一個最佳化資源配置目標之數學線性規劃模型，並加入DOS指標的概念來評估其存活性。在求解的過程之中，利用“拉格蘭日鬆弛法”與“梯度法”來幫助我們逐漸找到最佳解。 最後，經由實驗證明，不僅我們所提出的三階段選擇 (3-Stage Selection, 3SS) 攻擊演算法能夠有效評估攻擊成本，而且針對不同的網路拓樸所提出的網路資源配置策略效果顯著。

Due to the decreasing cost of computer hardware and the increasing capacity of computer software, most critical networks are being progressively computerized. If one of these systems were to fail, it would not only cause extreme inconvenience in our daily lives, but could even have catastrophic or fatal consequences. Thus, how to assess and evaluate the survivability of a system effectively is a crucial issue in the field of information security. In this thesis, we propose a simple and novel metric of network survivability, called Degree of Separation (DOS). DOS is a survivability metric used to measure the average damage level of a system; naturally, the larger the DOS value, the more serious the network damage will be. If the DOS value is larger than a pre-established threshold, we say that the network has been compromised. We express the scenario of network attack-defense as a mathematical linear programming model to near-optimize the resource allocation policies. In the process of problem solving, we adopt the concept of DOS to assess the network survivability and use the Lagrangean Relaxation method and the subgradient method to approach the optimal solution. Finally, based on the experiment results, not only can the 3-stage selection (3SS) attack algorithm we proposed evaluate the attack cost effectively, but are the results of different defense budget allocation policies to different network topologies quite significant.