Defense against Distributed Denial-of-Service (DDoS) Attacks by Routing Assignment and Resource Allocation under Quality-of-Service (QoS) Constraints

隨著網路使用的普及，網路攻擊事件層出不窮，尤其是分散式阻絕服務攻擊，往往造成網路上服務提供者資源的損失以及使用者服務品質的權益受損。因此在遭受攻擊時，網路管理者為了維持使用者的服務品質，利用備用資源配置去良好地設計一個網路是有其需要的。 本論文中，在滿足服務品質限制下將利用路由選徑以及資源配置去防禦智慧型的分散式阻絕服務攻擊。我們將攻防的情境轉化成一個最大最小化的雙層數學規劃問題；內層問題 (最小化) 代表當一個網路遭受某種模式的攻擊時，網路管理者利用決定最少的防禦資源配置需求以及路由選徑策略與去維持網路內部使用者的服務品質，外層問題 (最大化) 則為網路管理者假設在給定攻擊流量時，有一攻擊者利用攻擊模式的調整以求最大化網路的整體防禦資源需求。為了求得最佳解，我們利用拉格蘭日鬆弛法為基礎的演算法來處理內層的問題，並利用次梯度法為基礎的演算法來解外層的問題。解出問題之後，我們預期發展出有效率且有效用的演算法。As the popularity of networks is increasing, network attack events occur frequently, especially Distributed Denial-of-Service (DDoS) attacks. Upon such attacks, system resources are dramatically consumed and the Quality-of-Service (QoS) perceived by users significantly degrades. In order to achieve the objective of “continuity of services”, it is then essential that a network be well designed by spare resource allocation so as to maintain acceptable QoS levels upon such attacks.n this thesis, the problem of defense against intelligent DDoS attacks by routing and budget allocation (RB) under QoS constraints is considered. This problem is formulated as a max-min integer programming problem, where the inner (minimization) problem is for network administrators to determine the minimum amount of defense budget required and effective internal routing policies so as to defend the network against a given pattern of DDoS attacks under given QoS requirements, while the outer (maximization) problem is for network administrators to evaluate the worst-case defense resource required when attacks adjust the patterns of DDoS attack flows (AF) under a fixed total attack power. A Lagrangean relaxation-based algorithm is proposed to solve the inner problem, while a subgradient-based algorithm is proposed to solve the outer problem. It is expected that efficient and effective algorithms be developed accordingly.謝 誌 ........................................................................................................... I文摘要 ................................................................................................... IIHESIS ABSTRACT ............................................................................ IIIable of Contents ..................................................................................... Vist of Tables ......................................................................................... VIIist of Figures ...................................................................................... VIIIhapter 1 Introduction ............................................................................ 1.1 Background ....................................................................................... 1.2 Motivation ......................................................................................... 3.3 Literature Survey .............................................................................. 5.3.1 DDoS Attack and Defense ................................................... 5.3.2 Characteristics of the Network ............................................ 6.3.3 Network Survivability.......................................................... 8.4 Proposed Approach ........................................................................... 8.5 Thesis Organization .......................................................................... 9hapter 2 Problem Formulation .......................................................... 10.1 Problem Description ....................................................................... 10.2 Problem Formulation ...................................................................... 11.3 Problem Formulation of the RB Problem ....................................... 22hapter 3 Solution Approaches ............................................................ 27.1 Lagrangean Relaxation Method ...................................................... 27.2 The Solution Approach for the RB Problem .................................. 31I.2.1 Lagrangean Relaxation ...................................................... 31.2.1 The Dual Problem and the Subgradient Method ............... 39.2.2 Getting Primal Feasible Solutions ..................................... 40.3 Simple Algorithms .......................................................................... 43.4 The Solution Approach for the AFRB Problem .............................. 45hapter 4 Computational Experiments ............................................... 49.1 Computational Experiments of RB Problem .................................. 49.1.1 Experimental Environments .............................................. 49.1.2 Computational Experiments .............................................. 52.1.3 Discussion of Results ........................................................ 60.2 Computational Experiments of AFRB Problem ............................. 60.2.1 Computational Experiments .............................................. 61.2.2 Discussion of Results ......................................................... 63hapter 5 Conclusion and Future Work.............................................. 65.1 Conclusion ...................................................................................... 65.2 Future Work .................................................................................... 66eferences ............................................................................................... 6