臺灣博碩士論文加值系統

自從美國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.

謝 誌 I
論文摘要 II
THESIS ABSTRACT III
Contents V
List of Figures VII
List of Tables VIII
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 3
1.3 Literature Survey 3
1.3.1 From Information Security to Survivability 3
1.3.2 Scale-free Networks 9
1.4 Proposed Approach 12
Chapter 2 Problem Formulation 13
2.1 Model 1 13
2.1.1 Problem Description and Assumptions 13
2.1.2 Notation 15
2.1.3 Problem Formulation 16
2.1.4 Problem Reformulation 17
2.2 Model 2 20
2.2.1 Problem Description and Assumptions 20
2.2.2 Notation 22
2.2.3 Problem Formulation 22
Chapter 3 Solution Approach 24
3.1 Solution to Model 1 24
3.1.1 Introduction to the Lagrangean Relaxation Method 24
3.1.2 Lagrangean Relaxation 27
3.1.3 The Dual Problem and the Subgradient Method 29
3.1.4 Getting Primal Feasible Solutions 30
3.2 Solution to Model 2 33
3.2.1 Basic Concept 33
3.2.2 Lemma 34
Chapter 4 Computational Experiments 36
4.1 Simple Algorithm 1 36
4.2 Simple Algorithm 2 37
4.3 Parameters and Cases of the Experiment 37
4.4 Experimental Results 38
4.5 Discussion of the Results 45
4.6 Computational Complexity 46
Chapter 5 Summary and Future Work 48
5.1 Summary 48
5.2 Future Work 49
References 52

[1]雷定中, “資訊時代國家安全的基礎--通資網路存活率之研究,” 國防通信電子及資訊季刊 第五期, 2004
[2]Sean P. Gorman, Laurie Schintler, Raj Kulkarni, and Roger Stough, “The Revenge of Distance: Vulnerability Analysis of Critical Information Infrastructure,” Journal of Contingencies and Crisis Management vol. 12, pp. 48-63, 2004
[3]Michael Faloutsos, Petros Faloutsos , and Christos Faloutsos , “On Power-Law Relationships of the Internet Topology,” Computer Communications Review 29, pp. 251-263, 1999
[4]A. Broida and K. C. Claffy, “Internet topology: Connectivity of IP graphs, in Scalability and Traffic Control in IP Networks,” S. Fahmy and K. Park, eds., Proc. SPIE 4526, International Society for Optical Engineering, Bellingham, WA, pp. 172–187, 2001
[5]Q. Chen, H. Chang, R. Govindan, S. Jamin, S. J. Shenker, and W. Willinger, “The origin of power laws in Internet topologies revisited,” in Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, IEEE Computer Society, Los Alamitos, CA, 2002
[6]Murali Kodialam and T. V. Lakshman, “Detecting Network Intrusions via Sampling: A Game Theoretic Approach,” IEEE INFOCOM, 2003
[7]R. J. Ellison, D. A. Fisher, R. C. Linger, H. F. Lipson, T. Longstaff and N. R. Mead, “Survivable Network Systems: An Emerging Discipline,” Technical Report CMU/SEI-97-TR-013, Software Engineering Institute, Carnegie Mellon University, 1999
[8]Vickie R. Westmark, “A Definition for Information System Survivability,” IEEE Proceedings of the 37th Hawaii International Conference on System Sciences, 2004
[9]M, A. Schroeder, and K. T. Newport, “A Connectivity Using a Graph Theory Approach,” MTR 9278, The MITRE Corporation, Rome, NY, 1986
[10]M, A. Schroeder, “A Knowledge-Based Approach to the Computation of Network Nodal Survivability,” Military Communications Conference, MILCOM 90, 1990.
[11]Haizhuang Kang, Clive Bulter, and Qingping Yang, “A New Survivability Measure for Military Communication Networks,” Military Communications Conference, MILCOM 98, 1998
[12]Tong Ze Jiang, “A New Definition on Survivability of Communication Networks,” MILCOM, 1991
[13]Jianxu Shi and John P. Fonseka, “Traffic-Based Survivability Analysis of Telecommunication Networks,” IEEE, 1995
[14]Ali Zolfaghari and Fred J. Kaudel, “Framework for Network Survivability Performance,” IEEE Journal on Selected Areas in Communications, vol. 12, No.1, 1994
[15]Erdos, P. & Renyi A., “On the evolution of random graphs,” Publ. Math. Inst. Sci. 5, pp. 17-60, 1960
[16]Reka Albert, Hawoong Jeong, and Albert-Laszlo Barabasi, “Error and Attack Tolerance of Complex Networks,” Nature 406, pp. 378-381, 2000
[17]Duncan J. Watts and Steven H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature 393, pp. 440-442, 1998
[18]Reka Albert, Hawoong Jeong, and Albert-Laszlo Barabasi, “Diamater of the World Wide Web,” Nature 401, pp. 130-131, 1999
[19]Albert-Laszlo Barabasi and Reka Albert, “Emergence of Scaling in Random
Networks,” Science 286, pp. 509-512, 2001
[20]M. L. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problems”, Management Science, vol. 27, pp. 1-18, 1981
[21]A. M. Geoffrion, “Lagrangean Relaxation and its use in Integer Programming,” Mathematical Programming Study, vol. 2, pp. 82-114, 1974
[22]M. Held, et al., “Validation of subgradient optimization,” Math. Programming, vol. 6, pp. 62-88