林永松臺灣大學：資訊管理學研究所曾中蓮Tseng, Chung-lienChung-lienTseng2007-11-262018-06-292007-11-262018-06-292006http://ntur.lib.ntu.edu.tw//handle/246246/54254網際網路的普及和便利造成人們對網路的依賴，然而這也使得網路犯罪有機可乘。資訊竊取是造成最嚴重損失的網路犯罪之一，它不但造成金錢、財產之類的有形損失，還讓無形的企業及個人聲譽受損；因此如何幫助網際網路發展有效防禦策略，以降低資訊洩露的程度，就成了急需探討的研究議題。 在這篇論文中，我們將一個攻防情境轉化成二階的數學規劃問題；其中內層問題（AS模型）敘述一個惡意攻擊者該如何配置其有限攻擊資源到目標網路，以竊取最多的機敏資訊，而在外層問題（DRAS模型）中，目標網路的管理者則希望能有效配置其有限防禦資源，來將由資訊洩漏所引發的損失最小化。為了求得此問題的最佳解，我們採用以拉格蘭日鬆弛法為基礎的演算法來處理AS模型，而利用以次梯度法為基礎的演算法來處理DRAS模型。Dependency on the Internet is giving cyber criminals increasing opportunities to steal information. Information theft, one of the most damaging cyber-crimes, not only causes property damage and monetary loss to victims, it can also ruin their reputations. As a result, research into developing defense strategies against information theft on the Internet is a pressing need. In this paper, we model an offence-defense scenario as a two-level mathematical programming problem. In the inner problem, defined by the AS model, an attacker allocates his limited attack power intelligently to the targeted network in order to steal as much valuable information as possible. Meanwhile, in the outer problem, defined by the DRAS model, the operator of the targeted network allocates limited defense resources appropriately to minimize the damage incurred by information theft. The Lagrangean relaxation-based algorithm is adopted to solve the AS problem, and a subgradient-based algorithm is proposed to solve the DRAS problem.謝誌 I 論文摘要 II THESIS ABSTRACT III Table of Contents IV List of Tables VI List of Figures VII Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 6 1.3 Literature Survey 8 1.3.1 Quantitative Analysis of Network Survivability 8 1.3.2 Scale-free Networks 11 1.4 Proposed Approach 14 1.5 Thesis Organization 15 Chapter 2 Problem Formulation of the DRAS and AS Models 17 2.1 Problem Description 17 2.2 Problem Formulation of the DRAS Model 19 2.3 Problem Formulation of the AS Model 26 Chapter 3 Solution Approach 29 3.1 Solution Approach for the AS Model 29 3.1.1 Lagrangean Relaxation Method 29 3.1.2 First-Stage Relaxation 33 3.1.2.1 Lagrangean Relaxation 33 3.1.2.2 The Dual Problem and the Subgradient Method 37 3.1.2.3 Getting Primal Feasible Solutions 38 3.1.3 Second-Stage Relaxation 40 3.1.3.1 Lagrangean Relaxation 41 3.1.3.2 The Dual Problem and the Subgradient Method 43 3.1.3.3 Getting Primal Feasible Solutions 44 3.1.4 Summary of the Solution Approach for the AS Model 47 3.1.4.1 Lagrangean Relaxation-based Algorithm 47 3.1.4.2 Initial Multiplier Determination 48 3.2 Solution Approach for the DRAS Model 49 Chapter 4 Computational Experiments 53 4.1 Computational Experiments with the AS Model 53 4.1.1 Simple Algorithm 1 53 4.1.2 Simple Algorithm 2 54 4.1.3 Simple Algorithm 3 55 4.1.4 Experiment Environment 56 4.1.5 Experiment Results 58 4.1.6 Discussion of Results 65 4.2 Computational Experiments with the DRAS Model 69 4.2.1 Experiment Environment 69 4.2.2 Experiment Results 70 4.2.3 Discussion of Results 75 Chapter 5 Conclusion and Future Work 77 5.1 Conclusion 77 5.2 Future Work 79 References 83775266 bytesapplication/pdfen-US資訊竊取拉格蘭日鬆弛法數學規劃網路攻防網路存活度最佳化資源配置無尺度網路Information TheftLagrangean RelaxationMathematical ProgrammingNetwork Attack and DefenseNetwork SurvivabilityOptimizationResource AllocationScale-free Networks[SDGs]SDG16otherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54254/1/ntu-95-R93725002-1.pdf