Near Optimal Network Planning and Defense Resource Allocation Strategies for Minimizing Quality-of-Service (QoS) Violations under Attacks

隨著網際網路的方便性，資訊安全的問題也越來越重要。近幾年來，有意及無心的網路犯罪事件層出不窮。其中，攻克網路中某些特定的伺服器並降低其處理能力，是影響網路服務品質最常見的網路犯罪手法之一。因此我們應發展出有效的策略來防範如此的攻擊，例如防禦資源的配置。此外，網路規劃也必須納入資訊安全的考量。這篇論文中，我們提出一個最小最大化的數學規劃問題來塑造網路管理者和攻擊者間相互的行為。在內層問題（ARRAS問題）中，考慮的是一個攻擊者該選擇哪些節點來攻擊並有效配置其有限的攻擊資源，以最大化因為違反服務品質而網路管理者必須付出的代價，例如賠償。在外層問題（NPDRAS問題）中，網路管理者則希望在有限的預算中，設計一個良好的網路並有效的配置防禦資源，來最小化必須付出的代價。為了求得此問題的最佳解，我們利用拉格蘭日鬆弛法為基礎的演算法來處理內層的問題，並利用內層問題的解和調整預算的演算法來處理外層的問題。With the convenience of Internet, the problem of information security has caught more and more attentions. Events of witting or unwitting cybercrimes emerge in an endless stream in past years. Among them, to compromise particular servers and then degrade their process capability is one of the most popular cybercrimes in order to further affect the Quality-of-Service (QoS) of the network. For taking precautions against such attacks, we should develop effective defense strategies such as defense resources allocation. Besides, the network planning has to be considered in the realm of information security.n the thesis, we propose a min-max mathematical programming problem to model the mutual behavior between a network administrator and an attacker. In the inner problem, called the ARRAS problem, the attacker would like to maximize the total penalty the administrator has to pay for due to QoS violations by deciding which node to attack and allocating the limited attack budget effectively. In the outer problem, called the NPDRAS problem, the network administrator hopes to minimize the total penalty by planning a well network and allocating defense resources intelligently under a limited budget. For obtaining near optimal solutions, we use the Lagrangean relaxation-based algorithm to solve the ARRAS problem and exploit the solutions of ARRAS problem and the proposed budget adjustment procedure to solve the NPDRAS problem.口試委員審定書 I誌 II文摘要 IIIHESIS ABSTRACT IVable of Contents VIist of Tables VIIIist of Figures IXhapter 1 Introduction 1.1 Background 1.2 Motivation 6.3 Literature Survey 7.3.1 IP Multicast 7.3.2 QoS Routing 10.3.3 Single-Application Multiple-Stream 12.3.4 Survivability 15.4 Proposed Approach 18.5 Thesis Organization 18hapter 2 Problem Formulation 19.1 Problem Description 19.2 Problem Formulation of the NPDRAS Problem 22.3 Problem Formulation of the ARRAS Problem 33hapter 3 Solution Approach 38.1 Lagrangean Relaxation Method 38.2 The Solution Approach for the ARRAS Problem 41.2.1 Lagrangean Relaxation 41.2.2 The Dual Problem and the Subgradient Method 46.2.3 Getting Primal Feasible Solutions 47.3 The Solution Approach for the NPDRAS Problem 51hapter 4 Computational Experiments 54.1 Computational Experiments with the ARRAS Model 54.1.1 Simple Algorithms 54.1.2 Experiment Environment 56.1.3 Experiment Results 59.1.4 Discussion of Results 71.2 Computational Experiments with the NPDRAS Model 73.2.1 Experiment Environment 73.2.2 Experiment Results 74.2.3 Discussion of Results 74hapter 5 Conclusion 76.1 Summary 76.2 Future Work 77eferences 79歷 8