林永松臺灣大學：資訊管理學研究所溫 雅 芳Wen, Ya-FangYa-FangWen2007-11-262018-06-292007-11-262018-06-292007http://ntur.lib.ntu.edu.tw//handle/246246/54299由於電腦硬體成本逐漸下降、軟體性能逐漸上昇，大部份的關鍵性網路都已電腦化控制。這些與日常生活息息相關的網路系統，一旦其毀損，除了對我們的生活造成極大的不方便，更是在生命與財產方面，引起不小的損失。所以，有效地評估與衡量關鍵性網路系統的存活性，是現今資訊安全領域中亟需重視的議題。 有鑑於此，我們提出一個全新且簡單的網路存活性指標—網路分隔度(Degree Of Separation, DOS)。這是一種網路傷害指標，用來衡量網路遭受毀損的平均程度。DOS值愈大，代表其網路毀損愈嚴重，即表示必須付出更大的代價去修復整個網路。倘若其損害程度大於某一門檻值，則我們宣稱該網路已全然毀損。 因此，我們模擬一個網路攻防情境以建立一個最佳化資源配置目標之數學線性規劃模型，並加入DOS指標的概念來評估其存活性。在求解的過程之中，利用“拉格蘭日鬆弛法”與“梯度法”來幫助我們逐漸找到最佳解。 最後，經由實驗證明，不僅我們所提出的三階段選擇 (3-Stage Selection, 3SS) 攻擊演算法能夠有效評估攻擊成本，而且針對不同的網路拓樸所提出的網路資源配置策略效果顯著。Due to the decreasing cost of computer hardware and the increasing capacity of computer software, most critical networks are being progressively computerized. If one of these systems were to fail, it would not only cause extreme inconvenience in our daily lives, but could even have catastrophic or fatal consequences. Thus, how to assess and evaluate the survivability of a system effectively is a crucial issue in the field of information security. In this thesis, we propose a simple and novel metric of network survivability, called Degree of Separation (DOS). DOS is a survivability metric used to measure the average damage level of a system; naturally, the larger the DOS value, the more serious the network damage will be. If the DOS value is larger than a pre-established threshold, we say that the network has been compromised. We express the scenario of network attack-defense as a mathematical linear programming model to near-optimize the resource allocation policies. In the process of problem solving, we adopt the concept of DOS to assess the network survivability and use the Lagrangean Relaxation method and the subgradient method to approach the optimal solution. Finally, based on the experiment results, not only can the 3-stage selection (3SS) attack algorithm we proposed evaluate the attack cost effectively, but are the results of different defense budget allocation policies to different network topologies quite significant.口試委員會審定書 I 誌謝 II 論文摘要 III THESIS ABSTRACT IV Table of Contents VI List of Figures VIII List of Tables IX Chapter 1 INTRODUCTION 1 1.1 Background 1 1.2 Motivation 4 1.3 Literature Survey 6 1.3.1 Network Survivability 6 1.3.2 Scale-free Networks 10 1.4 Thesis Organization 14 Chapter 2 DEGREE OF SEPARATION 15 2.1 Introduction 15 2.2 Illustration 16 2.3 Lemma 21 Chapter 3 PROBLEM FORMULATION 23 3.1 Model 1 23 3.1.1 Problem Description and Assumptions 23 3.1.2 Mathematical Model 25 3.1.3 Problem Reformulation 29 3.2 Model 2 31 3.2.1 Problem Description and Assumptions 31 3.2.2 Mathematical Model 33 3.2.3 Problem Reformulation 37 Chapter 4 SOLUTION APPROACH 40 4.1 Lagrangean Relaxation Method 40 4.2 Solution Approach for Model 1 45 4.2.1 Lagrangean Relaxation 45 4.2.1.1 Subproblem 1 (related to decision variable xp) 47 4.2.1.2 Subproblem 2 (related to decision variable yi) 48 4.2.1.3 Subproblem 3 (related to decision variable twi, ci) 49 4.2.2 The Dual Problem and the Subgradient Method 50 4.2.3 Getting Primal Feasible Solutions 52 Chapter 5 COMPUTATIONAL EXPERIMENTS 58 5.1 Simple Algorithm 58 5.1.1 Degree-based Attack Algorithm (DAA) 59 5.1.2 Popularity-based Attack Algorithm (PAA) 61 5.2 Experiment Environment 63 5.3 Experiment Results and Discussion 66 5.3.1 Experiment Results of Model 1 67 5.3.2 Discussion of Experiment Results for Model 1 75 5.3.3 Experiment Results of Model 2 77 5.3.4 Discussion of Experiment Results for Model 2 80 Chapter 6 SUMMARY AND FUTURE WORK 81 6.1 Summary 81 6.2 Future Work 84 REFERENCES 871191894 bytesapplication/pdfen-US網路分隔度拉格蘭日鬆弛法網路存活性最佳化資源配置無尺度網路Degree of SeparationLagrangean RelaxationNetwork SurvivabilityOptimizationResource AllocationScale-free Networkotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54299/1/ntu-96-R94725048-1.pdf