臺灣博碩士論文加值系統

由於近年來電腦軟、硬體以及通訊技術的發達，使得企業以及個人能夠使用輕巧、便宜且高效能的設備，因此加速了網際網路的發展，各式各樣的網路應用服務也如雨後春筍般相繼推出。然而，人們對於網際網路的依賴，也同時令連接至網路的電腦以及伺服器更容易受到攻擊，這些攻擊會讓個人以及企業遭受極大的損失。此外，新的威脅持續增加，惡意攻擊者的攻擊手法也不斷翻新，加上零時差攻擊的出現，使得我們幾乎無法確保網路或是系統隨時處在安全的狀態當中。因此網路在惡意攻擊下的存活度便成為一個極為重要的議題。
在這篇論文當中，採用了一個新的指標-網路分隔度（Degree of Separation，DOS）來評估網路的損壞程度以及存活度。我們將一個網路攻防情境轉換成多回合的數學規劃問題，其中每一回合包含了三個階段。第一階段描述一個網路營運者要如何部署有限的防禦資源在網路的節點上，藉此提高攻擊者的攻擊成本。而在第二階段當中，惡意攻擊者利用有限的攻擊預算，對網路中的節點發動攻擊，目標是最大化網路的損壞程度。而在最後的階段，網路營運者希望能有效配置其有限的修復預算，修復被攻擊者破壞的節點，以最小化網路的損壞程度。在求解的過程中，使用拉格蘭日鬆弛法來幫助我們求得最佳解。

Because of the rapid advancement of computer and telecommunication technologies in recent years, smaller, less expensive and high performance devices are available for companies and individuals, which accelerate the growth of the Internet and make available to users a variety of new network applications/services. However, our dependency on the Internet has made the PCs and servers connected to the network more vulnerable to attacks, causing great losses to enterprises and individuals. Moreover, an increasing number of new threats, evolution of attack tactics and the emergence of zero-day attacks make it almost impossible for a system or network to keep “safe” at any moment. Therefore, survivability of a network under malicious attacks has become an extremely important issue.
In this thesis, we adopted a novel metric called Degree of Separation (DOS) to evaluate the damage level and survivability of a network. A network attack-defense scenario is converted to a multi-round mathematical programming problem. Each round contains three stages, in the first stage, the defender deploys his limited defense resources on the nodes in the network, in order to increase the attacker’s attack cost. In the second stage, the attacker uses his limited budget to launch attacks, trying to maximize the damage of the network. Finally, the defender tries to minimize network damage by repairing nodes compromised by the attacker, subject to his finite repair budget. The Lagrangean relaxation method is proposed here to obtain solutions for the problem.

謝誌 I
論文摘要 III
THESIS ABSTRACT V
Table of Contents VII
List of Tables XI
List of Figures XV
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 7
1.3 Literature Survey 9
1.3.1 Network Survivability 9
1.3.2 Degree of Separation 16
1.3.2.1 Introduction 16
1.3.2.2 Sensitivity of DOS 19
1.3.2.3 Other DOS Metrics 23
1.4 Thesis Organization 24
Chapter 2 Problem Formulation 25
2.1 Problem Description 25
2.2 Model 1 27
2.2.1 Problem Description and Assumption 27
2.2.2 Problem Notation and Formulation 30
2.3 Inner Problem of Model 1 33
2.3.1 Problem Description and Assumption 33
2.3.2 Problem Notation and Formulation 35
2.4 Model 2 39
2.4.1 Problem Description and Assumption 39
2.4.2 Problem Notation and Formulation 41
Chapter 3 Solution Approach 45
3.1 Lagrangean Relaxation Method 45
3.2 Solution Approach for the Inner Problem of Model 1 49
3.2.1 Lagrangean Relaxation 49
3.2.2 The Dual Problem and the Subgradient Method 52
3.2.3 Getting Primal Feasible Solutions 54
3.2.4 Summary of the Solution Approach for the Inner Problem 56
3.3 Solution Approach for Model 1 57
3.4 Solution Approach for Model 2 61
3.4.1 Lagrangean Relaxation 61
3.4.2 The Dual Problem and the Subgradient Method 64
3.4.3 Getting Primal Feasible Solutions 66
3.4.4 Summary of the Solution Approach for Model 2 67
Chapter 4 Computational Experiment 71
4.1 Computational Experiment with the Inner Problem of Model 1 71
4.1.1 Simple Algorithm 1 71
4.1.2 Simple Algorithm 2 72
4.1.3 Experiment Environment 73
4.1.4 Experiment Results 76
4.1.5 Discussion of Results 79
4.2 Computational Experiment with Model 1 81
4.2.1 Experiment Environment 81
4.2.2 Experiment Results 82
4.2.3 Discussion of Results 84
4.3 Computational Experiment with Model 2 85
4.3.1 Simple Algorithm 85
4.3.2 Experiment Environment 87
4.3.3 Experiment Results 88
4.3.4 Discussion of Results 92
4.4 Computational Experiment with Two-round Attack-defense 93
4.4.1 Experiment Environment 93
4.4.2 Experiment Results 96
4.4.2.1 Experiment Results of Case 1 96
4.4.2.2 Experiment Results of Case 2 98
4.4.2.3 Experiment Results of Case 3 99
4.4.3 Discussion of Results 101
Chapter 5 Conclusion and Future Work 103
5.1 Conclusion 103
5.2 Future Work 105
References 109
簡歷 113

[1] IBM Internet Security Systems X-Force research and development team, “X-Force 2009 Mid-Year Trend & Risk Report,” IBM, August 2009, http://www-935.ibm.com/services/us/iss/xforce/trendreports/.
[2] S. Peters, “2009 CSI Computer Crime and Security Survey,” Computer Security Institute, December 2009, http://gocsi.com.
[3] “Terms and Definitions Related to Quality of Service, Availability, and Reliability,” CCITT Fascicle III. 1 Rec. G. 106, 1984.
[4] M.S. Deutsch and R.R. Willis, “Software Quality Engineering: A Total Technical and Management Approach,” Englewood Cliffs, NJ: Prentice-Hall, 1988.
[5] L. Wu and P.K. Varshney, “On Survivability Measures for Military Networks,” IEEE Military Communications Conference, A New Era 1990, Volume 3, pp. 1120-1124, October 1990.
[6] T.-Z. Jiang, “A New Definition on Survivability of Communication Networks,” Conference Record of IEEE Military Communications Conference 1991 (MILCOM''91), Volume 3, pp. 901-904, November 1991.
[7] S.C. Liew and K.W. Lu, “A Framework for Network Survivability Characterization,” IEEE International Conference on Communications 1992 (ICC ''92), Volume 1, pp. 405-410, June 1992.
[8] J. Shi and J.P. Fonseka, “Traffic-based Survivability Analysis of Telecommunications Networks,” IEEE Global Telecommunications Conference, Volume 2, pp. 936-940, November 1995.
[9] 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, November 1997.
[10] K.J. Sullivan, S. Geist, and P. Shaw, “Mediators in Infrastructure Survivability Enhancement,” ACM Proceedings of the 3rdIinternational Workshop on Software Architecture, pp. 141-144, November 1998.
[11] A.P. Snow, U. Varshney, and A.D. Malloy, “Reliability and Survivability of Wireless and Mobile Networks,” Computer, Volume 33, Issue 7, pp. 49-55, July 2000.
[12] D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao, “Overview and Principles of Internet Traffic Engineering,” RFC3272, May 2002.
[13] V.R. Westmark, “A Definition for Information System Survivability,” Proceedings of the 37th IEEE Hawaii International Conference on System Sciences, Track 9, Volume 9, pp. 90303a, January 2004.
[14] “ATIS Telecom Glossary 2007,” Alliance for Telecommunications Industry Solutions, http://www.atis.org/glossary/definition.aspx?id=1039.
[15] S. Balasubramaniam, D. Botvich, W. Donnelly, and N. Agoulmine, “A Multi-layered Approach Towards Achieving Survivability in Autonomic Network,” IEEE International Conference on Telecommunications and Malaysia International Conference on Communications 2007 (ICT-MICC‘07), pp. 360-365, May 2007.
[16] M. Garg and J. C. Smith, “Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios,” Omega, Volume 36, Issue 6, pp. 1057-1071, December 2008.
[17] Z. Ma and A.W. Krings, “Survival Analysis Approach to Reliability, Survivability and Prognostics and Health Management (PHM),” IEEE Aerospace Conference 2008, pp. 1-20, March 2008.
[18] A.T. Murray, T.C. Matisziw, and T.H. Grubesic, “Critical network infrastructure analysis: interdiction and system flow,” Journal of Geographical Systems, Volume 9, Number 2, pp. 103-117, June 2007.
[19] J.C. Smith, C. Lim, and F. Sudargho, “Survivable network design under optimal and heuristic interdiction scenarios,” Journal of Global Optimization, Volume 38, Number 2, pp. 181-199, June 2007.
[20] Y.-F. Wen, “Near Optimal Network Defense Resource Allocation Policies for Maximization of Network Survivability,” Master Thesis, National Taiwan University, July 2007.
[21] M.L. Fisher, “An Applications Oriented Guide to Lagrangian Relaxation,” Interfaces, Vol. 15, No. 2, pp. 10-21, April 1985.
[22] M.L. Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problems,” Management Science, Volume 27, Number 1, pp. 1-18, January 1981.
[23] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, “Network Flows: Theory, Algorithms, and Applications: Chapter 16 Lagrangian Relaxation and Network Optimization,” Prentice-Hall, pp. 598-639, 1993.
[24] A. M. Geoffrion, “Lagrangean Relaxation and its Use in Integer Programming,” Mathematical Programming Study, Volume 2, pp. 82-114, 1974.