Redundancy and Defense Resource Allocation Algorithms to Assure Service Continuity against Natural Disasters and Intelligent Attackers

近年來企業持續營運管理逐漸受到企業組織的重視。於此範疇中，災害復原計畫是與資訊科技最息息相關的部分。而在實踐災害復原計畫的眾多辦法之中，冗餘的佈署是一項常被採用的有效解決方案；然而，過往探討冗餘配置問題的研究多聚焦於可靠性系統，較少著力於企業組織多所仰賴的網路系統。故本論文在考慮網路環境特性的條件之下，旨於將冗餘與額外防禦有效地搭配運用於網路系統，一方面達成其服務之持續性，另方面則提升其抵抗具備經驗累積能力之惡意攻擊的存活度。 於此論文中，我們建構了一個攻防雙方彼此角力的攻防情境，之後將其轉化為一個兩階段的非線性整數規劃問題：在內層問題（AEA模型）中，具備絕對經驗累積能力的攻擊者透過選擇適當的目標進行攻擊，企圖以最小化的成本攻克網路中的所有核心節點；反觀外層問題（RAP-EDM模型），防禦者則在有限的防禦資源預算之下，透過適當地佈署冗餘與額外防禦，以最大化被攻擊者最小化的總體攻擊成本。其後，我們採用以拉格蘭日鬆弛法為基礎的方法解決上述問題，並藉由電腦實驗結果證明所提出解決方案之優異性。In recent years, Business Continuity Management (BCM) has become an important issue to organizations. Within the scope of BCM, Disaster Recovery Planning (DRP) is one of the most IT-related problems, and redundancy is a frequently used approach to implement DRP. However, previous research on Redundancy Allocation Problem (RAP) focused on dealing with the problems related to reliable systems, instead of network systems that organizations rely on. Therefore, we discuss RAP in network environments. By efficient use of redundancy together with extra defense mechanisms, we attempt to ensure a network’s service continuity, and enhance its survivability against malicious attackers that utilizes accumulated experience. We construct an attack/defense scenario, in which an attacker and a defender competing against each other, and formulate it as a two-phase nonlinear integer programming problem. In the inner problem, AEA model, the attacker that utilizes accumulated experience attempts to minimize the total attack cost of compromising all core nodes in the network by choosing appropriate targets to compromise. By contrast, in the outer problem, RAP-EDM model, the defender allocates proper redundancy and extra defense mechanisms to maximize the minimized total attack cost under the consideration of a limited defense budget. We adopt a Lagrangean Relaxation-based solution approach to resolve the problem above, and further prove the efficacy of our approach by computer experiments.謝誌 I文摘要 IIIHESIS ABSTRACT Vable of Contents VIIist of Tables IXist of Figures XIhapter 1 Introduction 1.1 Background 1.2 Motivation 5.3 Literature Survey 6.3.1 Survivability 7.3.2 Redundancy Allocation Problem 11.4 Proposed Approach 14.5 Thesis Organization 15hapter 2 Problem Formulation 16.1 Problem Description 16.2 Problem Formulation of the RAP-EDM Model 17.3 Problem Formulation of the AEA Model 35hapter 3 Solution Approach 39.1 Solution Approach for the AEA Model 39.1.1 Lagrangean Relaxation Method 39.1.2 Lagrangean Problem of the AEA Model 41.1.3 The Dual Problem and the Subgradient Method 47.1.4 Getting Primal Feasible Solutions 47.2 Solution Approach for the RAP-EDM Model 49hapter 4 Computational Experiments 52.1 Computational Experiments with the AEA Model 52.1.1 Simple Attack Algorithm 1 and Simple Attack Algorithm 2 52.1.2 Randomized Allocation Algorithm 53.1.3 Core Focused Allocation Algorithm 53.1.4 Experiment Environment 54.1.5 Experiment Results 56.1.6 Discussion of Results 61.2 Computational Experiments with the RAP-EDM Model 62.2.1 Experiment Environment 62.2.2 Experiment Results 62.2.3 Discussion of Results 69hapter 5 Conclusion and Future Work 71.1 Conclusion 71.2 Future Work 73eferences 7