Near Optimal Filtering and Routing Policies against Distributed Denial-of-Service (DDoS) Attacks

分散式阻絕服務攻擊已成為今日網際網路之嚴重威脅。在分散式阻絕服務攻擊發生時，眾多惡意封包佔據了網路伺服器的資源，導致合法使用者資源存取之困難。即使在使用了過濾器機制來防範分散式阻絕服務攻擊，仍無法保證合法使用者完全不受此攻擊之損害。本論文中，我們將分散式阻絕服務攻擊之攻擊與防禦情境摸擬成一個兩階段的數學規劃問題。在內層問題中，防禦者試圖以分配其有限防禦資源來最大化受分散式阻絕服務攻擊損害之合法流量。而在外層問題則敘述分散式阻絕服務攻擊者之試圖以分配其有限攻擊資源來最小化合法流量。同時為了求得此問題的最佳解，我們採用以拉格蘭日鬆弛法為基礎的演算法來處理內層問題，而利用以次梯度法為基礎的演算法來處理外層問題。Distributed Denial-of-Service (DDoS) attacks have become an impending threat toward today’s Internet. During DDoS attacks, numerous malicious packets occupy a victim server and lead to the difficulty of the legitimate user’s access. Even if the filtering thwarts DDoS attacks, no legitimate users can escape the collateral damage.n this thesis, we model the DDoS attack-defense scenario as a two-level mathematical programming problem. In the inner problem, a defender tries to allocate the limited defense resources for the maximization of the legitimate traffic. In the outer problem, a DDoS attacker tries to allocate the limited attack resources in order to minimize the legitimate traffic. A Lagrangean relaxation-based algorithm is proposed to solve the inner problem, and a subgradient-based algorithm is proposed to solve the outer problem.論文摘要 IHESIS ABSTRACT IIIable of Contents IVist of Tables VIist of Figures VIIhapter 1 Introduction 1.1 Background 1.2 Motivation 4.3 Literature Survey 7.3.1 DDoS Attacks 7.3.2 Survivability and Resource Allocation 11.3.3 Autonomous Systems 13.4 Proposed Approach 15.5 Thesis Organization 16hapter 2 Problem Formulation of the ARAS and FAS models 17.1 Problem Description 17.2 Problem Formulation of the ARAS Model 19.3 Problem Formulation of the FAS Model 30hapter 3 Solution Approach 35.1 Solution Approach for the FAS Model 35.1.1 Lagrangean Relaxation Method 35.1.2 Lagrangean Relaxation 39.1.3 The Dual Problem and the Subgradient Method 43.1.4 Getting Primal Feasible Solutions 44.2 Solution Approach for the ARAS Model 46hapter 4 Computational Experiments 49.1 Computational Experiments for the FAS Model 49.1.1 Simple Algorithm 1 49.1.2 Simple Algorithm 2 50.1.3 Experiment Environment 51.1.4 Experiment Results 55.1.5 Discussion of Results 68.2 Computational Experiments for the ARAS Model 70.2.1 Experiment Environment 70.2.2 Experiment Results 72.2.3 Discussion of Results 76hapter 5 Conclusion and Future Work 78.1 Conclusion 78.2 Future Work 80eferences 8