臺灣博碩士論文加值系統

現代組織企業越來越倚重資訊科技來協助日常的營運作業。然而，這樣的依賴性卻是建立在危害事件發生頻繁且惡意攻擊層出不窮的環境下，任何的綱路斷線或是機器故障都會造成嚴重的經濟損失。因此，為了達到持續性服務的目標，我們提出一個植基於冗餘配置的方法，期望將潛在威脅發生的可能性降到一個可以接受的程度。
在本論文中，我們將攻防雙方的戰役模擬成一個兩階的非線性整數規劃問題。在內層問題中 (ARS模型)，攻擊者透過分配有限的攻擊能量來最大化網路元件面對危害事件的脆弱度。相反地，在外層問題中 (RAPMA模型)，防守者嘗試在有限的預算限制下，透過冗餘元件的適當部署來最小化攻擊者所帶來的傷害。其中，我們發展一個以拉格蘭日鬆弛法為基礎的演算法來快速地解決此數學規劃問題。

Modern organizations have increasingly relied on information technology to facilitate daily business operations. However, the dependency is built upon an environment where hazardous events happen frequently and malicious attacks emerge in an endless stream. To attain the objective of “continuity of services”, we propose an approach based on redundancy allocation to reduce the possibility of threats occurring to an acceptable degree.
In the thesis, we formulate a “battle” between the attacker and the network into a two-level programming problem. In the inner problem (ARS model) an attacker allocates the limited attack powers to maximize the vulnerability of network against hazardous events. Contrarily, in the outer problem (RAPMA model) a defender attempts to minimize the damages by deploying redundant components appropriately with the limited budgets. We develop a Lagrangean Relaxation-based algorithm to solve the programming problem efficiently.

謝辭 i
論文摘要 ii
THESIS ABSTRACT iii
Table of Content v
List of Tables vii
List of Figures ix
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 3
1.3 Literature Survey 5
1.3.1 Risk Management 6
1.3.2 Survivability 7
1.3.3 Redundancy Allocation Problem 11
1.4 Proposed Approach 13
1.5 Thesis Organization 14
Chapter 2 RAPMA and ARS Model 17
2.1. Problem Description 17
2.2. Problem Formulation of RAPMA Model 21
2.3. Problem Formulation of ARS Model 32
Chapter 3 37
3.1. Solution Approach for the ARS Model 37
3.1.1 Lagrangean Relaxation Method 37
3.1.2 Lagrangean Problem of ARS Model 41
3.1.3 The Dual Problem and Subgradient Method 47
3.1.4 Getting Primal Feasible Solutions 48
3.2. Solution Approach for the RAPMA Model 51
Chapter 4 Computational Experiments 53
4.1. Experiment Environment 53
4.2. Simple Algorithms 54
4.2.1 Minimum Cost Spanning Tree Algorithm 54
4.2.2 Greedy-based Algorithm 55
4.3. Experiment Results 56
4.3.1. Experiments for ARS Model 56
4.3.2. Experiments for RAPMA Model 64
4.4. Discussion of Experiment Results 70
Chapter 5 Conclusion and Future Work 73
5.1. Conclusion 73
5.2. Future Works 75
References 77

[1] Wojciech Molisz, “Survivability Function ─ A Measure of Disaster-Based Routing Performance,” IEEE Journal on Selected Areas in Communication, vol. 22, no. 9, November 2004
[2] Howard F. Lipson, David A. Fish, “Survivability ─ A New Technical and Business Perspective on Security,” CERT ® Coordination Center Software Engineering Institute
[3] Benjamin B.M. Shao, “Optimal Redundancy Allocation for Information Technology Disaster Recovery in the Network Economy,” IEEE Transactions on Dependable and Secure Computing, Vol. 2, No.3, July-September 2005
[4] David W. Coit, Abdullah Konak, “Multiple Weighted Objectives Heuristic for the Redundancy Allocation Problem,” IEEE Transactions on Reliability, Vol. 55, No. 3 September 2006
[5] Jose E. Ramirez-Marquez, David W. Coit, Abdullah Konak, “Redundancy Allocation for series-parallel systems using a max-min approach,” IIE Transactions (2004) 36, 891-898
[6] Yong Jiang, James D. McCalley, Tim Van Voorhis, “Risk-Based Resource Optimization for Transmission System Maintenace,” IEEE Transactions on Power Systems, Vol. 21, No. 3, August 2006
[7] Chunghun Ha, Way Kuo, “Multi-Path Heiristic for Redundancy Allocation: The Tree Heuristic,” IEEE Transactions on Reliability, Vol. 55, No. 1, March 2006
[8] Herve Kerivin, Dritan Nace, Thi-Tuyet-Loan Pham, “Design of Capacitated Survivable Network with a Single Facility,” IEEE/ACM Transactions on Networking, Vol. 13, No. 2, April 2005
[9] Young-Soo Myung, Hyun-joon Kim, Dong-wan Tcha, “Design of Communication Networks with Survivability Constraints,” Management Science, Vol. 45, No. 2 (Feb., 1999), 238-252
[10] Soumyo D. Moitra, Suresh L. Konda, “A Simulation Model for Managing Survivability of Networked Information Systems,” Technical Report CMU/SEI-2000-Tr-020 ESC-TR-2000-020
[11] Chenxi Wang, “A Security Architecture for Survivability Mechanisms,” a dissertation presented to the School of Engineering and Applied Science at the University of Virginia
[12] John Koroma, Wei Li, Demetrios Kazakos, “A Generalized Model for Network Survivability,” TAPIA’03 October 15-18, 2003, Atlanta, Georgia., USA
[13] David M. Nicol, William H. Sanders, Kishor S. Trivedi, “Model-Based Evaluation: From Dependability to Security,” IEEE Transactions on Dependable and Secure Computing, Vol.1, No. 1, January-March 2004
[14] Zeev Zeitlin, “Integer Allocation Problems of Min-Max Type with Quasiconvex Separable Functions,” Operation Research, Vol. 29, No. 1, January-February 1981
[15] John C. Knight, Elisabeth A. Strunk, Kevin J. Sullivan, “Towards a Rigorous Definition of Information System Survivability,” Proceedings of the DARPA Information Survivability Conference and Exposition (DISCEX’03)
[16] J. McDermott,” Attack-Potential-Based Survivability Modeling for High-Consequence System,” Proceedings of the Third IEEE International Workshop on Information Assurance (IWIA’05)
[17] M. S. Chern, “On The Computational Complexity of Reliability Redundancy Allocation in A Series System,” IEEE Transactions on Reliability, Vol. R-36, No. 5 pp.621-623, 1987
[18] Marshall L. Fisher, “An Applications Oriented Guide to Lagrangian Relaxation,” Interfaces, Vol. 15, No. 2, pp. 10-21, April 1985
[19] M. L. Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problem,” Management Science, Vol. 27, No. 1, pp. 1-18, January 1981
[20] L.A. Gordon, M.P. Loeb, W. Lucyshyn, R. Richardson, “2006 CSI/FBI Computer Crime and Security Survey,” Computer Security Institute, 2006, http://GoCSI.com
[21] Fotios Harmantzis, Manu Malek, “Security Risk Analysis and Evalution,” IEEE Communication Society
[22] Ram Dantu, Kall Loper, Prakash Kolan, “Risk Management using Behavior based Attack Graphs,” Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC’04)
[23] Stefano Bistarelli, Fabio Fioravanti, Pamela Peretti, “Defense Tree for Economic Evaluation of Security Investments,” Proceedings of the First International Conference on Availability, Reliability and Security (ARES’06)