考慮智慧型惡意攻擊下之網路存活度最大化

Abstract

自從美國911攻擊事件發生之後，如何有效保護重要資訊基礎建設已成為一個重要的課題。而同為重要資訊基礎建設之一的網際網路，在近年來，隨著駭客入侵與攻擊重要主機事件層出不窮，網路安全議題亦逐漸受到專家重視。然而在理論與實務上，資訊安全都告訴我們，沒有任何系統是百分之百的安全。因此我們不應該問「這個系統安不安全」，而是要關心「這個系統有多安全」。量化的「存活度」概念便應運而生，成為網路安全專家衡量一個網路處於不正常（包含隨機錯誤與惡意攻擊）的狀態下，維持正常服務程度的效能指標。 另外，網路攻防也是網路安全專家所關心的議題。為了有效提升網路的存活度，網路營運者必須投資一筆固定預算並加以妥善配置。而相對的，攻擊者針對網路營運者所採用的資源配置策略，也會因應調整其攻擊方式，以最少的攻擊成本達成攻擊目的。 在本篇論文中，我們首先評估一個既有網路的存活度，也就是討論在給定的網路拓樸中，給定一種資源配置策略，一個攻擊者攻擊成功所需花費的最小成本；隨後我們討論：在一個給定的網路中，網路營運者（防禦者）投資一筆固定預算的情況下，應該如何有效的配置資源，才能使得攻擊者攻擊成功所花費的總成本最大。攻防的標的我們設定為：若干給定關鍵節點之間的正常連結。此時我們假設攻擊者是夠聰明的，在給定的防禦資源配置策略下，攻擊者總是能夠找到最小的攻擊成本策略，使得給定的關鍵節點之間無法連通。 我們將整個問題仔細地分析成最佳化數學模型，而這個問題在本質上是一個非線性混合整數規劃問題，具有高度的複雜度與困難度。我們採用以拉格蘭日鬆弛法為基礎的演算法來處理此一問題。在實驗設計方面，我們針對隨機網路、格狀網路與無尺度網路這三種不同網路拓樸，討論其網路的存活特性。 另外，我們針對這個問題的特性，提出了一個數學證明。我們也在最後提出許多豐富議題供後人從事相關研究。

Since the 911 terrorist attacks in the United States, how to protect critical information infrastructures effectively has become an even more important topic. One critical information infrastructure, the Internet, has drawn increasing attention from network security experts because of the growing number of malicious attacks on it. However, experience tells us that, in both theory and practice, a system cannot be 100% secured. Therefore, we should not ask “Is the system secure?” but “How secure is the system?” A quantitative “survivability” concept has become an important performance metric for evaluating how a network sustains normal services under abnormal conditions, including random errors and malicious attacks. Other issues of interest to network security experts are network attack and defense scenarios. To enhance network survivability effectively, a network operator needs to invest a fixed amount of budget and distribute it properly. However, a potential attacker will always adjust his attack strategies to compromise a network with the minimal cost, if he knows the resource allocation policy of a network operator. In this thesis, we first evaluate the survivability of a given network. That is, we assess the minimal attack cost incurred by an attacker, under given network topologies and budget allocation policies. We then discuss how a network operator should allocate fixed budget resources such that the minimal attack cost incurred by an attacker can be maximized. The target of the attack and defense is assumed to be the connectivity of given critical OD-pairs. In cases of budget allocation decisions, we assume that an attacker is smart enough, so he can always find the strategy of minimal attack cost to disconnect critical OD-pairs. We analyze the problems as optimization-based models, in which the problem structures are by nature nonlinear with mixed integer programming. To resolve such difficult problems, we adopt Lagrangean relaxation-based algorithms in conjunction with a number of optimization techniques. In the experimental design, we also evaluate the network survivability properties of different network topologies, including random networks, grid networks, and scale-free networks. In addition, we present a lemma based on the problem’s properties. We believe our work could provide the foundation for evaluating network survivability under various attack and defense scenarios. To this end, we conclude by indicating several interesting and challenging research directions.