cryptographic

Published on February 2017 | Categories: Documents | Downloads: 22 | Comments: 0 | Views: 278
of 207
Download PDF   Embed   Report

Comments

Content

COLLABORATIVE DETECTION AND FILTERING OF DDOS ATTACKS IN ISP CORE NETWORKS

by

Yu Chen

A Dissertation Presented to the FACULTY OF THE GRADUATE SCHOOL UNIVERSITY OF SOUTHERN CALIFORNIA In Partial Fulfillment of the Requirements for the Degree DOCTOR OF PHILOSOPHY (ELECTRICAL ENGINEERING)

December 2006

Copyright 2006

Yu Chen

UMI Number: 3257687

Copyright 2006 by Chen, Yu All rights reserved.

UMI Microform 3257687 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P.O. Box 1346 Ann Arbor, MI 48106-1346

Dedication
To Qing, my loving wife. For her unfailing love, selfless sacrifice, constant encouragement and support.

ii

Acknowledgements
I am deeply grateful to my advisor Professor Kai Hwang. First of all, he gave me the opportunity to pursue my Ph.D. studies in this exciting research area of network security. Secondly, without his invaluable advice, guidance, and support, I could not have achieved what I have done. Most importantly, after years of work under his supervision, I learned from Professor Hwang’s enthusiasm and commitment to research. This attitude will benefit me in my future careers and for the rest of my life. I am deeply indebted to Professor Ricky Yu-Kwon Kwok from Hong Kong University. Thank God that Dr. Kwok was visiting USC and working in our group. Dr. Kwok led my first publication in the network security area and helped me to identify an interesting research topic. I am so thankful for his time and wisdom spent with me. I am also thankful to Professor Bhaskar Krishnamachari and Professor Ramesh Govindan for serving on my committee. In particular, I am indebted to Professor Bhaskar for his help and guidance during my job search process. It is an honor to have the opportunity to learn from him. I also want to thank Wei-Shinn Ku, my friend and co-author of the CAT paper. I will never forget the days and nights we spent together tuning the programs on the DETER testbed. I also would like to thank Mr. Kevin Lahey and his colleagues at USC ISI for their kindness and cooperation when we needed to occupy hundreds of machines on the DETER testbed. I would also like to thank all the members of the GridSec research group that I worked with over past years. In particular, I would like to thank Min Cai, Ying Chen,

iii

Xiaosong Lou, Jie Lv, Shanshan Song, and Runfang Zhou for their meaningful discussions and collaboration. I cannot thank them enough for their support. I would also like to express my thankfulness to my parents and parents-in-law for their unconditional support. They helped me get through many difficult times, and shared my joy and sadness. Without them, I could not have completed the study. Finally, I want to thank the NSF for the financial support of this research and dissertation work funded by NSF Grant No. ACI-0325409.

iv

Table of Contents
Dedication ……………………………………………………………………………… ii Acknowledgements ……………………………………………………………………... iii List of Tables …………………………………………………………………………… viii List of Figures …………………………………………………………………………… ix Abstract ………………………………………………………………………………… xiii 1. Introduction ………………………………………………………….…………….. 1 1.1. Understanding Distributed Denial-of-Services (DDoS) Attacks ……………... 2 1.1.1. How do DDoS Attacks Work? ………………………………………... 2 1.1.2. Why do DDoS Attacks Work? ………………………………………... 6 1.1.3. Challenges in Defense against DDoS Attacks ………………………… 8 1.2. Approaches in this Thesis …………………………………………………… 9 1.3. Overview of the Thesis ……………………………………………………… 13 2. Related Works …………………………………………………………………… 14 2.1. Overview of Internet Security Protocols ……………………………………… 14 2.2. DDoS Attack Defense Schemes ……………………………………………… 16 2.2.1. Detection Techniques ………………………………………………… 17 2.2.2. IP Traceback Techniques ……………………………………………… 18 2.2.3. Congestion Control Techniques ……………………………………… 20 2.2.4. Flow Filtering Techniques …………………………………………… 22 2.2.5. Deployment Tradeoffs ………………………………………………… 23 2.2.6. Other Techniques ……………………………………………………… 25 2.3. Summary ……………………………………………………………………… 26 3. Secure Infrastructure Protocol for IPV6 ………………………………………… 28 3.1. Motivation …………………………………………………………………… 28 3.2. SIP Overview ………………………………………………………………… 30 3.3. Inter-Domain Trust Control …………………………………………………… 32 3.4. Message Functionality and Format …………………………………………… 34 3.4.1. Message Description ………………………………………………… 34 3.4.2. Message Format ……………………………………………………… 37 3.5. Potential Applications …………………………………………………...…… 39 3.6. Summary ……………………………………………………………………… 40 4. Detection of DDoS Attacks in Multiple ISP Networks ………………………… 42 4.1. Introduction …………………………………………………………………… 42

v

4.2. Framework of Distributed Change-Point Detection ……………………………44 4.2.1. Distributed Change Detection System ………………………………… 44 4.2.2. Change-Point Detection Principles …………………………………… 46 4.3. Change Detection at a Single Router ………………………………………… 48 4.3.1. Anomaly Detection at Router Level …………………………………… 48 4.3.2. CAT Subtree Construction Algorithm ………………………………… 51 4.4. Merging CAT Subtrees from Multiple Domains ……………………………… 54 4.4.1. Global CAT Tree Construction ……………………………………… 54 4.4.2. Complexity Analyses ………………………………………………… 58 4.5. Experiment Results and Performance Analyses ……………………………… 60 4.5.1. Introduction to DETER Testbed ……………………………………… 61 4.5.2. Experiment Setup ……………………………………………………… 63 4.5.3. Performance Metrics ………………………………………………… 64 4.5.4. Impact of DCP Parameters …………………………………………… 64 4.5.5. Detection Accuracy …………………………………………………... 67 4.6. Scalability Analysis and Limitations ………………………………………… 70 4.6.1. Domain Scalability Analysis ………………………………………… 70 4.6.2. Other Options and Implementation Limitations ……………………… 72 4.7. Summary ……………………………………………………………………… 73 5. Identification and Filtering of Malicious DDoS Attack at Flow Level ………… 75 5.1. Adaptive Packet Dropping Principle ………………………………………… 75 5.2. MAFIC Algorithm Design …………………………………………………… 77 5.3. Experimental Results and Performance Analysis …………………………… 79 5.3.1. Simulation Setup and Performance Metrics ………………...….……… 79 5.3.2. Attacking Packet Dropping Accuracy ………………………………… 80 5.3.3. Effects of Flow Cutting ……………………………………………… 82 5.3.4. False Alarm Rates …………………………………………………… 84 5.3.5. Legitimate Packet Dropping Rate …………………………………… 86 5.4. Summary ……………………………………………………………………… 87 6. Collaborative Detection of Shrew DDoS Attacks Using Spectral Analysis …… 89 6.1. Introduction …………………………………………………………………… 89 6.2. Shrew Attack Characteristics in Frequency Domain ………………………… 92 6.2.1. Shrew DDoS Attack Properties ……………………………………… 92 6.2.2. Traffic Spectrum and Template Distribution ………………………… 95 6.3. Collaborative Anomaly Detection …………………………………………… 99 6.3.1. Pivot Frequency in Traffic Streams …………………………………… 99 6.3.2. Hypothesis Test ……………………………………………………… 101 6.3.3. Collaborative Detection Algorithm …………………………………… 105 6.4. Experiment Results and Performance Analysis ……………………………… 108 6.4.1. Experiment Setup ……………………………………………………… 108 6.4.2. Detection Accuracy …………………………………………………… 109 6.4.3. Effects of Local Detection Threshold α ……………………………… 111 6.4.4. Effects of Global Detection Threshold β ……………………………… 112 6.5. Scalability and Overhead Analysis …………………………………………… 113 6.6. Summary ……………………………………………………………………… 114

vi

7. Amplitude Filtering of Shrew Attack Flows …………………………………… 116 7.1. Normalized Amplitude Spectral Analysis …………………………………… 116 7.1.1. Shrew DDoS Attack Flow Properties ………………………………… 116 7.1.2. Analysis of Amplitude Spectrum Distribution ………………………… 118 7.2. Flow Filtering atop Amplitude Hypothesis Testing …………………………… 122 7.2.1. Hypothesis Test Analysis ……………………………………………… 122 7.2.2. Shrew-Filtering Algorithm Design …………………………………… 125 7.3. Experiment Results and Performance Analysis ……………………………… 127 7.3.1. Experiment Setup ……………………………………………………… 127 7.3.2. Filtering Efficiency …………………………………………………… 128 7.3.3. Response Time ………………………………………………………… 132 7.4. Scalability, Deployment, and Limitations …………………………………… 135 7.5. Summary ……………………………………………………………………… 136 8. Summaries and Conclusions ……………………………………………………… 138 8.1. Summary of Contributions …………………………………………………… 138 8.2. Preliminary Accelerator Design ……………………………………………… 141 8.3. Further Research Works ……………………………………………………… 143 Bibliography …………………………………………………………………………… 145 Appendices A. Publications ……………………………………………………………………… 158 B. DETER Experiment Configuration ……………………………………………… 160 C. DETER Experiment JAVA Code (Router) ……………………………………… 161 D: DETER Experiment JAVA Code (Server) ……………………………………… 167

vii

List of Tables
Table 3.1 Table 3.2 Table 4.1 Table 4.2 Table 4.3 Table 4.4 Table 5.1 Table 5.2 Table 6.1 Table 6.2 Table 7.1 Table 7.2 Abbreviations and Definitions in SIP Messages …………………... 35 Definitions of SIP Message Fields ………………………………… 38 Information in an Alert Message Sent from a Router …………….. 52 Internet Neighborhood Distribution in August 2006 ……………… 59 Hardware/Software Information of DETER Testbed ……………… 62 Stacheldraht Packet Size vs. Packet Rate …………………………. 67 Definition of Notations in MAFIC ………………………………… 80 Default Setting of Parameters in MAFIC …………………………. 80 Notations and Abbreviations used in Chapter 6 and 7 …………….. 92 Gaussian Distribution of Attack Template …………………………. 99 Error Level of Shrew-Filtering ……………………………………. 124 Error Levels in Filtering with Different Sampling Times ………… 134

viii

List of Figures
Figure 1.1 Figure 1.2 Figure 1.3 Traffic flow distribution of typical direct DDoS attacks …………… 3 Traffic flow distribution of reflector-based DDoS attacks …………. 4 Collaborative defense architecture crossing multiple ISP core networks ……………………………………………………… 10 Roadmap of this dissertation ……………………………………….. 12 Three levels of communication in using the SIP between two servers in Two autonomous systems ……………………………….. 31 Illustration of trust based information sharing …………………… 34 Format of SIP messages ……………………………………………. 37 Distributed change-point detection od DDoS flooding attacks over multiple autonomous systems (ASs) ……………….………... 45 An illustration of change aggregation tree (CAT) constructed at the end router (R0) connected to the victim system ………………. 46 Four basic traffic patterns of traffic changes at the 2x2 router I/O ports ..........................................................................................

Figure 1.4 Figure 3.1

Figure 3.2 Figure 3.3 Figure 4.1

Figure 4.2

Figure 4.3

49

Figure 4.4

Control flow in constructing the CAT subtree specified in Algorithm 4.2 ……………………………………………………… 53 An example 6-domain global CAT tree construction environment ... 57 Merging CAT subtrees from nearby domains to outer domains to build the global CAT tree, where AS0 is the victim destination domain ……....................................................................................... 58 Schematic of DETER testbed ……………………………………… 61 Total alerts raised plotted against the router threshold applied on 34 routers in 4 domains using a 500 ms monitoring window ……… 65

Figure 4.5 Figure 4.6

Figure 4.7 Figure 4.8

ix

Figure 4.9

Variations of the global CAT size over 4 AS domains in 500 ms monitoring window ………………………………………….……. 66 The router alerts detected with and without DDoS attacks plotted against the monitoring window size ………………………………. 67 Effects of server threshold on the detection rate of 3 DDoS attack types ………………………………………………………… 68 Effects of the threshold on false-positive rate ……………………. 69 ROC curve showing the tradeoff between detection rate and false-positive rate …………………………………………………. 69 Scalability of the distributed change-point detection system over increasing number of AS domains ………………………………… 71 The protocol control actions of MAFIC algorithm ……………….. 78 Attack packet dropping accuracy of MAFIC algorithm under different traffic conditions …………………………………………. 81 Traffic reduction rates and flow bandwidth variations of MAFIC algorithm under different traffic conditions ……………………….. 83 False positive and negative rates of MAFIC algorithm under different traffic conditions ………………………………………… 85 Legitimate-packet dropping rates of MAFIC algorithm under different traffic conditions ………………………………………… 87 The collaborative detection and filtering (CDF) architecture for defense against shrew DDoS attacks over multiple routers in the same autonomous system …………………………………………. 90 Three traffic streams under three scenarios – the shrew DDoS attack stream in part (b) hides in six legitimate traffic flows in part (a) to form the traffic stream in part (c) ………………………. 94 Comparison of normalized traffic density (PSD) of two traffic streams with and without shrew attacks …………………………... 96

Figure 4.10

Figure 4.11

Figure 4.12 Figure 4.13

Figure 4.14

Figure 5.1 Figure 5.2

Figure 5.3

Figure 5.4

Figure 5.5

Figure 6.1

Figure 6.2

Figure 6.3

x

Figure 6.4

Comparison of the cumulative energy spectrum of two traffic streams with and without shrew attacks …………………………… 97 Average attack template distribution over a low frequency band for all attack streams in training set Sa ……………………….. 98 Determination of the pivot frequency p and the two spectral pivot point yo for the attack-free stream in Fig. 6.2(a) and ya for the attack stream in Fig. 6.2(c) ………………………………. 100 Template distribution of attack/no-attack streams at the attack pivot frequency ……………………………………………………. 102 Variation of the likelihood function with respect to the normalized spectral pivot value …………………………………… 103 Plots of the anomaly detection rate Rd and false positive rate Rfp averaged over 8,000 sample traffic streams in the template database ……………………………………………... 104 Collaborative detection scheme and use of detection trees ………... 107 ROC curve showing the tradeoffs between anomaly detection rate and false positive rate under collaborative detection of shrew attacks, compared with the result of using an isolated router ……… 110 Shrew attack detection results from testing 4,000 traffic streams over 2 to 40 routers under the independent and two collaborative modes …………………………………............................................ 111 Effects of global threshold (β) on collaborative detection of shrew DDoS attacks using three cooperative ranges of routers ………….. 113 An illustration of various types of shrew attack flows ……………. 117 Normalized amplitude spectrum of the shrew pulse stream and of the TCP flow …………………………………………………… 119 Normalized cumulative amplitude spectrum of the shrew stream and of the TCP flow ……………………………………………… 121 Normalized CAS distribution of the shrew stream and of the TCP flow at the pivot point ……………………………………….. 123

Figure 6.5

Figure 6.6

Figure 6.7

Figure 6.8

Figure 6.9

Figure 6.10 Figure 6.11

Figure 6.12

Figure 6.13

Figure 7.1 Figure 7.2

Figure 7.3

Figure 7.4

xi

Figure 7.5 Figure 7.6 Figure 7.7 Figure 7.8

Control flow in the amplitude filtering algorithm ………………… 126 The simulation scenario and experimental setting ………………… 128 Scenarios of TCP flows under single shrew attacks ………………. 129 Normalized throughput of TCP flows under 4 spatially distributed shrew attack flows ……………………………………… 131 Normalized throughput of TCP flows under 4 temporal distributed shrew attack flows ……………………………………… 132 Effects of sampling lengths on the TCP throughput ……………… 133 Function blocks of shrew DDoS attack detection accelerator……… 142

Figure 7.9

Figure 7.10 Figure 8.1

xii

Abstract
Distributed denial of services (DDoS) attacks pose a major threat to the Internet. Although one promising solution should be a real distributed scheme covering a wide area, most reported solutions conform to the end-to-end paradigm and target end-node victims. Because these solutions could not detect anomalies incurring inside the intermediate network, they could not detect the DDoS attacks at an early stage. This dissertation explores the defense against DDoS attacks from an ISP perspective. A distributed scheme over multiple ISP domains is proposed, which relies on ISP network routers monitoring traffic fluctuations and information sharing with peers. To resolve the security policy conflicts, a new secure infrastructure protocol (SIP) is developed to establish trust between ISPs. SIP provides a secure platform supporting collaborative detection and responses to DDoS attacks. Distributed schemes are proposed to fight against both the brute force flooding DDoS attacks and the stealthy low-rate TCP-targeted DDoS attacks. Having observed the directionality and aggregation characteristics in the spatiotemporal pattern of the flooding flows, a distributed change-point (DCP) detection architecture was developed using change aggregation trees (CAT). The DCP scheme detects traffic variances across network domains and all CAT servers exchange alert information to make global detection decisions. After early detection, MAlicious Flow Identification and Cutoff (MAFIC) issues lightweight probes to flow sources to segregate malicious flows with minimized bilateral damage.

xiii

A novel spectral template-matching approach is proposed to counter shrew DDoS attacks. Combining digital signal processing techniques and hypothesis testing, collaborative detection and filtering (CDF) detects and cuts off shrew attack flows embedded in legitimate TCP/UDP streams by spectral analysis. The performance of the distributed schemes is evaluated through intensive experiments on DETER testbeds and NS-2 simulators. Experiment results show a significant improvement was achieved by detecting anomalies crossing multiple ISP networks cooperatively. Information sharing among neighbor routers and SIP servers effectively increased detection rates while decreasing the number of false alarms. The experiments verified the effectiveness of DCP and CDF schemes and achieved encouraging results.

xiv

Chapter 1 Introduction
In past decades, information technology has revolutionized almost every facet of our lives. Government, commercial, and educational organizations depend on computers and Internet to such an extent that day-to-day operations are significantly hindered when the networks are “down” [Gor05]. The prosperity of the Internet also attracts abusers and malicious attackers. Distributed Denial of Services (DDoS) attacks are one of the major threats to Internet relative services and applications. Previously, most of these kinds of attacks were motivated for personal reasons or for prestige since successful attacks on popular web servers may gain the respect of the hacker community [Mir04]. We saw that popular e-business websites (Yahoo!, Microsoft, SUN, Amazon, etc.) were forced to be offline for hours and suffered financial losses [Goh06], [Her00], [Lem01a], [Lem01b]. However, things became worse. Nowadays, the hackers’ interest is far beyond obtaining unauthorized access for private information or showing their power in their community. Attackers are motivated for more concrete financial benefits [Ley04], [Pou04] or for certain political reasons [Rob03]. In 2005, the FBI caught an entrepreneur who hired a hacker to launch DDoS attacks against his major competitors’ websites in order to jumpstart his sales [FBI05]. Recently, a British student’s popular advertising site has come under a DDoS attack from blackmailers

1

demanding a ransom [Kaw06]. In 2003, the cyberwar between Israel and Palestine revealed that DDoS attacks can effectively paralyze opposing networks for days [All03]. Therefore, there is an impending requirement for effective DDoS detection and response techniques. This chapter briefly discusses how and why DDoS attacks work, then overviews the approach and roadmap for this dissertation.

1.1. Understanding DDoS Attacks
1.1.1. How Do DDoS Attacks Work?
Typically DDoS attacks aim at the availability of network services by attacking network infrastructure. They deprive the victim of providing or receiving certain services through the Internet. Attackers take advantage of the capability limitations of network resources or protocol deficiencies to achieve their goals. As the amount of computers connected to the Internet keeps growing, attackers can easily recruit a huge zombie army by compromising up to millions of machines [Eve05], [San05]. DDoS attacks are becoming more and more complicated and they are merging in various forms [Hou01]. This section presents the approaches that attackers adopt to launch attacks from a different numbers of perspectives.

1.1.1.1. Direct vs. Reflector-based Attacks Considering the flow directions of DDoS attack traffic from attack machines to the victim, the DDoS attacks can be classified into two major types. The first one is direct attacks, which takes a straightforward idea; in this case, zombies send huge amount of packet directly targeting victim machine(s). To serve this purpose, attackers often have compromised and gained control over thousands or even millions of vulnerable machines.

2

The attacking packets are routed to the victim from zombies distributed widely on the Internet. Figure 1.1 illustrates such a scenario. To escape from being caught by traceback techniques, the attacker often constructs a hierarchical botnet. Even if the victim figures out the attack traffic sources, the attacker is still untouched. It is very challenging, if not impossible, to trace back to the physical machine the attacker used.

Figure 1.1. Traffic flow distribution of typical direct DDoS attacks

Another type is the reflector-based attack. It is more complicated and harder to trace back compared to direct attacks. As shown by Fig. 1.2, one more layer is induced into the hierarchical architecture. Instead of sending packets to victims directly, the zombies take advantage of the TCP three-way handshake mechanism. Zombies are instructed to continuously send TCP connection-requesting SYN packets to other innocent IP hosts. Those SYN packets carry a spoofed source IP belonging to the victim. As the second phase of the TCP connection handshake, those innocent hosts reply to the victim with SYN/ACK packets according to the source IP address in the requesting packets they received. In this

3

manner, malicious SYN packets are being “reflected” off innocent nodes and their SYN/ACK responses are being used to flood and attack the victim [Gib02]. This type of attack is more difficult to fight back and costs less for the attacker. The attacker does not need to compromise as many zombies as direct flooding. As long as the victim’s IP address is known, the attacker can amplify his/her capability easily by sending SYN packets to any Internet IP hosts. Additionally, as all packets the reflectors receive are normal packets with the source address spoofed, this makes it even harder to trace the path back to the zombies.

Figure 1.2. Traffic flow distribution of reflector-based DDoS attacks

1.1.1.2. Brute Force vs. Protocol Exploitation based Attacks From the attackers’ viewpoint, DDoS attacks are classified into two categories according to the mean of performing an attack: brute force based and protocol exploitation

4

based DDoS attacks. The rationale of brute force based DDoS attacks lies in the fact that there are limited resources allocated for a victim. The targeted resource includes victim machine’s buffer space, CPU cycle, or link bandwidth. Generally, the attacker’s goal is to overwhelm the victims by the packet flood beyond what the victim can handle. Then the victim cannot respond to normal requests from legitimate users because of link bandwidth exhausted, queue buffer overflow, or computing power running out. To be more concrete, the brute force based DDoS attacks are further divided into two types: • End system oriented brute force-based DDoS attacks: this type of attack targets the victim’s bandwidth, buffers, memory, and CPU cycles. Attacks such as SYN flooding [CER96] and Smurf [CER98] attacks belong to this type. DDoS attacks mimicking flash crowds are also in this category [Kan05]. • Network infrastructure oriented brute force-based DDoS attacks: such type DDoS attacks tempt to overwhelm critical Internet infrastructure elements such as DNS root servers and BGP routers. During the early days of the Internet, security was not a major concern and it was designed for scientific utility for people in a small circle. That leaves the protocols vulnerable to today’s malicious abusers. As the most popular protocol, TCP protocols attract the attention from many DDoS attackers. Below we list two protocol exploitation-based DDoS attacks reported: • TCP SYN Flooding [CER96]: attacks take advantage of TCP’s three-way handshaking connection establishment procedure. When an attacker sends enough SYN packets, the half-open listen queue of the victim is fully occupied. Subsequently, all following legitimate connection requests are denied.

5



Shrew DDoS Attacks [Kuz03]: this type of low-rate TCP-targeted DDoS attack aims at the RTO mechanism of TCP protocol to degrade the throughput of legitimate TCP flows to close to zero. By periodically constructing a busy status on the link, the attacker can force normal TCP flows to go through the RTO repeatedly. This type of attack is stealthy and hard-to-detect. This dissertation will focus on shrew DDoS attacks in chapter 6 and 7.

1.1.1.3. Resource Exhaustion vs. Resource Stealing based Attacks Based on the impact against the victim, we can also divide DDoS attacks into two categories: resource exhaustion based and resource stealing based DDoS attacks [Ald05]. The resource exhaustion based attacks target both end system and network resources including main buffers, memory, CPU cycles, disk bandwidth, and network bandwidth. In contrast, the resource stealing based attacks aim at stealing network resources from legitimate users either by capturing these resources or by creating the illusion to legitimate users that the requested resources are not available. The attacks reported in literatures like shrew attacks [Kuz03] and Reduction-of-Quality (QoS) attacks [Gui04], [Gui05] belong to this category. They force legitimate TCP clients to keep going through congestion avoidance mechanisms and thus throttle their throughput heavily.

1.1.2.

Why Do DDoS Attacks Work?
Some researchers believe that the root of DDoS problems is the lack of enough

R&D efforts placed on the security concerns in Internet design [Ald05]. However, that is only part of the reason. DDoS attacks are not simply a weak spot that can be mended with slight protocol changes or by deployment of sophisticated defense schemes at potential target sites.

6

Looking back on history, the Internet’s design goal is functionality, not security. The network fabric tries to provide fast, simple and cheap communication at the network level. More complicated functionalities are assigned to end hosts. Under such an end-to-end paradigm and the so called best efforts principle, end users are allowed to manage their communication as they wish, and add complexities while leaving the intermediate network fabric simple and efficiency. By its nature, the Internet is a large distributed system without central authority. Due to its anarchic culture, it is infeasible to place all networks and users under the same control. Hence, it is impossible to guarantee all end hosts have the latest security software installed and suitable policies applied. When any of the end users become malicious, they are always able to find enough vulnerable hosts and recruit them into their zombie army. The intermediate network fabric will do nothing to stop attacking traffic flows. On the contrary, the network passively forwards packets to the destination. In fact, the network helps attackers to reach their goal. Why do DDoS attacks work? Answering this question is critical and insightful to our efforts in detecting and responding against DDoS attacks. In the following I summarize the main reasons of why DDoS attacks work. • Each individual host possesses limited resources: each Internet host only has limited resources such as bandwidth, buffer size, memory size, etc. When the amount of requests are beyond the capability of the host, newer requests won’t receive the services; • The power of many is greater than the power of a few: as long as there are enough vulnerable machines in the wild, an attacker is always able to recruit enough zombies. Considering that the botnet consists of millions of machines [Eve05],

7

theoretically speaking, it is capable of overpowering any end hosts in the Internet (if there is no defense); • Lack of centralized uniform control: domains are managed by local authorities and conform to different security policies. In fact, not all machines in every domain are under protection strong enough to avoid being compromised and recruited into the zombie army; • Dummy intermediate network fabric: attack traffic presents spatiotemporal propagation patterns different from normal fluctuations. Instead of detecting and responding to anomalies observed inside the intermediate network, the networks under best effort principle help the attacker reach her goal.

1.1.3.

Challenges in Defense against DDoS Attacks
Over the past decade, the plethora research efforts have proven that it is extremely

difficult to reach a comprehensive solution of the DDoS attacks. As illustrated in section 1.1.2, the root of DDoS attacks lies in the anarchical nature of the Internet itself. The main challenges researchers face include the following: • Similar contents vs. Malicious intent: the attack packets share the same formats with legitimate ones since they are generated using the same protocol. The only difference is its malicious intent. Unless analyzing their statistic characteristics or even checking the payload, the individual malicious packet looks no different from normal applications. • Handling huge traffic volume: when a brute force based DDoS attack is launched, there are overwhelmingly large numbers of packets flooding the victim. In order to segregate malicious packets, the countermeasures often involve packet processing

8

works such as packet marking, string matching, filtering, etc. The scalability is a major concern when an attacker can easily recruit thousands or even millions of zombies. • Recognizing attacks that are becoming more and more sophisticated: nowadays, the DDoS attack tools can be easily downloaded online and they are getting more and more sophisticated. In general, it is unlikely that the defenders can predict the behaviors of the next generation of attack tools. Because Internet architecture, protocols, and applications on the Internet are so diverse and complex, no one can predict all the possible vulnerabilities that attackers may exploit. • Controlling large portions of attack traffic: attack traffic is generated by multiple zombies distributed widely. To relieve the pressure of overwhelming incoming packets, the defense scheme must be able to control a large portion of total attack traffic. To a distributed defense scheme, this implies that a defense scheme can cover a wide area on the Internet. Obviously it has prohibitively costs and requires close cooperation among users. • Social Challenges: there are some non-technique constraints that prevent certain DDoS attack defense schemes from being deployed. Today’s Internet is so large that it is difficult to have a solution to be deployed simultaneously. Aside from considering the effectiveness, a customer also has to consider the economic benefits by deploying the scheme.

1.2. Approaches in this Dissertation
Although early researchers have pointed out that the promising solution must be a distributed one that covers a wide area on the Internet [Pap03], most of the previously

9

reported works conform to the end-to-end paradigm and target end-node victims. Few efforts have been injected to solve the problem from the ISP perspective. Besides violating the endto-end paradigm, one of the major concerns is the limited functionality that the best efforts based intermediate network can perform. However, as I illustrated in the previous section, one root of the DDoS attacks lies in the best effort philosophy of networks. Based on the observation that more intelligence is necessary for Internet fabric to effectively defend against the DDoS attacks, this dissertation takes a different approach compared to previously reported research. I propose to defend DDoS attacks from the ISP’s perspective. Multiple ISP networks collaboratively obtain a larger spatiotemporal vision of the traffic variance as illustrated by Fig. 1.3.

Figure 1.3 Collaborative defense architecture crossing multiple ISP core networks This architecture pushes the traffic monitoring and management functionalities into intermediate networks. As shown in Fig. 1.3, the system is deployed over multiple ISP core network domains. There is a central server in each domain. The system detects the traffic changes, aggregates detected changes, and collects alerts over collaborative servers. Routers

10

are in charge of detecting attacks and raising alerts, whereas the servers aggregate distributed alerts. Routers monitor the incoming and outgoing traffic flows at input and output interfaces. Periodically, each router reports the traffic status to the server inside the domain. If a router observes abnormal traffic variations, an alert message is generated. Servers in different domains form an overlay network or communicate with each other through virtual private network (VPN) channels. A server is responsible for analyzing the received alerts of the entire domain. The server also exchanges information with other domain severs. By monitoring how traffic anomalies propagate crossing ISP domains and by sharing information crossing multiple Internet domains or autonomous systems (ASs), we can timely detect the DDoS attacks at an early stage, before the damage is done to the victim. Figure 1.4 illustrates the roadmap of the dissertation. Due to the various security policies applied and privacy concerns of ISPs, we need a secure policy negotiation and message exchange platform. For this purpose, I propose a novel securing infrastructure protocol (SIP), which allows ISPs to decide how much private information is visible to peers while effectively performing anomaly detection. SIP specifies a trust negotiation mechanism, a communication mechanism, message specifications, and message formats. Atop the SIP protocol, I address both brute force based DDoS flooding attacks and one type of the protocol exploitation based attack, the low-rate TCP-targeted DDoS attack. To detect flooding attacks at an early stage, a novel distributed change-point (DCP) detection scheme is proposed using distributed change aggregation trees (CAT). CAT takes advantage of the large spatiotemporal pattern of the traffic surge propagation observed crossing multiple ISP domains. Once it is confirmed that there is a DDoS flooding attack launched, the malicious flow identifying and cutting off (MAFIC) scheme is triggered. The

11

MAFIC algorithm segregates the malicious attacking flows from legitimate flows by adaptive packet dropping. It can cut off most of the attack traffic with very low bilateral damage to innocent applications.

Figure 1.4. Roadmap of this dissertation The low-rate TCP-targeted DDoS attacks are stealthy, periodic, pulsing, and lowrate in attack volume. It is difficult to detect and fight against such kinds of attacks using traffic volume based time domain approaches for the flooding type attacks. This dissertation suggests a defense method called collaborative detection and filtering (CDF) working in frequency domains. The CDF scheme detects and filters off low-rate attack flows hidden in legitimate TCP/UDP streams by spectral analysis against a pre-stored template of average attack spectral characteristics. The CDF scheme is suitable for either software or hardware implementation.

12

In literature, the low-rate TCP-targeted DDoS attacks are also known as shrew attacks [Kuz03], periodical pulsing attacks [Luo05a], or Reduction-of-Quality (QoS) attacks [Gui04], [Gui05]. For convenience, this dissertation will use the term shrew attacks in sequel.

1.3. Overview of this Dissertation
This dissertation is organized as the following: • Chapter 2 surveys the cutting edge status of research in the DDoS defense schemes. • Chapter 3 presents the securing infrastructure protocol (SIP) that is the foundation of the collaborative DDoS defense scheme atop multiple ISP domains. • Chapters 4 and 5 report the distributed collaborative defense scheme that is against brute force based DDoS flooding attacks. The change aggregation tree (CAT) based detection scheme and the malicious flow identifying and cutting off (MAFIC) algorithm atop adaptive packet dropping are discussed in detail respectively. • Chapters 6 and 7 address the stealthy, hard-to-detect low-rate TCP-targeted DDoS attacks. A novel approach combining the frequency domain spectrum analysis and hypothesis-testing framework is proposed. This scheme can accurately and effectively detect and filter off low-rate DDoS attack flows. • Chapter 8 summarizes the major contributions of this dissertation. I will also discuss the limitation of current solutions and indicate future research directions.

13

Chapter 2 Related Works
This chapter briefly reviews the reported works closely related to this dissertation including the development of Internet security protocols and the state of the art research in DDoS attack defense schemes.

2.1. Overview of Internet Security Protocols
A number of protocols have been developed to secure the Internet. Each addresses one or more facets of the problem, but there is no “magic dust” that can solve all security problems by sprinkling it on the network. Current standard Internet security mechanisms address three security problems: 1) Confidentiality, dependable cryptography to avoid information eavesdropping, 2) Authentication, a strict access control method to block illegal access, and 3) Integrity, techniques such as digital signatures to detect unauthorized revisions. Essentially, these measures are on the information security track and provide protection by information hiding. The one time password scheme [Hal98] makes password guessing attacks very difficult and is robust in response to replay attacks. HMAC [Kra97] suggested a sharedsecret authentication technique based on the fact that both sides know the same secret key. TLS [Die99] provides an encrypted authentication channel on top of TCP using certificates. SASL [Mye97] provides a framework for negotiating, authentication, and encryption

14

mechanisms to be used over a TCP stream. A combination of TLS and SASL can make up the shortcomings of TLS where only servers have certificates as SASL permits the use of more traditional client authentication technologies. SSH [Ylo06] provides a secure connection between client and server. It operates very much like TLS, but is optimized as a protocol for remote connections on terminal-like devices. GSS-API [Wra00] provides a framework for applications needing authentication, integrity, and/or confidentiality. Compared to TSL applied atop TCP, GSS-API can be easily used with UDP-based applications. Kerberos [Koh93] also provides a mechanism for two entities to authenticate each other and exchange keying material. It may be used by itself in a protocol, or it also could be used as a mechanism under SASL and GSS-API. DNSSEC [Eas99] digitally signs DNS records to prevent DNS cache contamination attacks. It in turn can be used to defeat name-based authentication and to redirect traffic to or past an attacker. With encryption and digital signatures embedded, Security/Multiparts [Gal95] are preferred for email protection. OpenPGP [Cal98] and S/MIME [Ram99] use certificates to identify users and provide secrecy and authentication of email messages. Among all these works, the Security Architecture for the Internet Protocol (IPsec) [Ken98a], [Ken98b], [Ken98c], [Pip98], [Tha98] is most relevant to my work. IPsec provides security services at the IP layer to protect both IP and upper layer protocols. The set of security services it can provide includes access control, connectionless integrity, data origin authentication, confidentiality, and limited traffic flow confidentiality. IPsec uses Authentication Header (AH) [Ken98b] and Encapsulating Security Payload (ESP) [Ken98c] protocols to provide traffic security. Although sharing similarities with IPsec since both are installed at the IP layer, SIP handles threats of different nature. Like other standard Internet security protocols, IPsec is

15

also designed under the philosophy that end-to-end security is better [Bel98]. IPSec tries to not rely on the security of the infrastructure. It protects the communications from the end hosts. When faced with today’s distributed attacks against Internet infrastructures, IPSec is not capable of serving our purpose effectively.

2.2. DDoS Attack Defense Schemes
Basically, DDoS attacks consist of two phases. The first phase is to recruit a zombie army by gaining access and installing zombie software in vulnerable machines. The second phase is to launch an attack against the ultimate victim. Therefore defense schemes can be divided into two categories: preventive and responsive approaches. The former is to prevent attackers from recruiting individual machines as zombies by reducing the chance of being compromised. These defense schemes are more related to works in intrusion detection and malware prevention areas. The responsive approaches correspond to the second phase of DDoS attacks after the attacker has already recruited his/her zombie army. They are designed to defend launched attacks. This dissertation focuses on a responsive approach. Hence, this section focuses on the state of the art DDoS attack detection and responding schemes. In general, tackling DDoS attacks entails three critical issues: (1) Timely detection, 2) Accurately identifying the machines participating in forwarding malicious flows and (3) Incisively cutting off the malicious flows at those machines. For example, through some response mechanisms (e.g., traceback [Bel03b]), the victim may be able to identify the ingress routers that participate in forwarding the malicious flows. Such routers are called Attack Transit Routers (ATRs) [Cai04]. The next step is to instruct these ATRs to segregate malicious flows from legitimate ones and preferentially block all malicious flows.

16

2.2.1.

Detection Techniques
To defend against DDoS attacks efficiently, a real-time detection of network

anomalies is preferable. When DDoS attacks are launched, there are some features in traffic that will signal the anomalies. The most often used features in today’s detection techniques include 1) surges in traffic volume, 2) diverse source IP addresses, and 3) content features. Traffic volume is the most common and direct feature used to detect abnormal network activities. Traffic congestion may suggest that an overwhelming amount of packets is coming and rate limiting mechanisms are required [Mah02]. Bro [Pax99] is a generalpurpose network intrusion detection system (IDS) that monitors the traffic volume over a network link. However, Bro itself becomes the victim of DDoS attacks [Cro03]. Sample/hold and multistage filters are suggested to identify large flows [Est01]. They are faster than other traffic measure methods using DRAM such as Cisco’s NetFlow [Cis03]. A MUti-Level Tree for Online Packet Statistics (MULTOPS) is proposed by [Gil01], which is a tree structure that detects ongoing bandwidth attacks. However, it is ineffective when an attack is launched through multiple distributed sources or the source spoofing is used. It is simple to detect attacks by monitoring traffic volume. However, this method fails to distinguish the flash crowd from real attacks. In both cases, the traffic volume increases quickly. Early research reveals that source IP spoofing is common in DDoS attacks and a lot of new addresses appear during the attack [Jun02]. Therefore, source IP monitoring (SIM) is developed to detect DDoS attacks [Pen03], [Pen04]. The argument is that when a flash crowd happens, most of the addresses appeared before. In contrast, in DDoS attacks more new addresses appear. A cumulative sum algorithm was developed to monitor the amount of new IP addresses. However, it requires an offline database to keep track of IP addresses in normal traffic.

17

Besides the traffic volume and source IP addresses, IP header contents or the statistic properties in time and frequency domains are useful in detecting DDoS attacks [Hus03], [Pap03]. The DDoS attacks usually cause some sudden change of variables of the network, so the change point detection methods are currently widely used in finding the attacks. Researchers at University of Michigan [Wan04] have suggested a centralized DDoS defense scheme to monitor the change points at the gateway level. They adopted the nonparametric CUSUM method to detect TCP SYN flooding attacks. Peng et al. [Pen03] took a similar approach to monitoring the source IP addresses. Recently, Soule et al. [Sou05] implemented a defense scheme that combines filtering and statistical methods. Under TCP SYN flooding, the difference between the traffic volumes is distinguished by a CUSUM algorithm [Wan04]. Once the sum exceeds a certain threshold, the TCP SYN DDoS attack is detected. Some theoretical analysis was reported by Blazek, et al [Bla01] to model changepoint detection for DDoS defense.

2.2.2.

IP Traceback Techniques
IP traceback aims to trace IP packets to their origins [Alj03] in order to stop the

malicious packets at their source. Under DDoS attacks, the source IP addresses of attack packets are often spoofed. Therefore, we need extra information and methods to trace the real source. We roughly divide current traceback techniques into the following categories and summarize their properties. • Link testing: the main idea is to start from the victim and go back to the upstream links, and then determine which links carried the attack traffic. CenterTrack [Sto00] traces back on an overlay network in a hop-by-hop manner. It uses IP tunnels to reroute interesting datagrams directly from edge routers to special

18

tracking routers. The tracking routers then determine the ingress edge router by observing tunnels. Hal Burch [Bur00] proposed to identify the path of attack traffic through controlled flooding. One problem is that controlled floding itself is a DoS attack since it induces local congestions and may cause bilateral damages against innocent users. The major drawback of link testing techniques is that it is very time-consuming to establish the attacking path. • Messaging: routers send ICMP messages to the destination when an extraordinarily large amount of packets are observed aiming the same target [Bel01]. This mechanism is not sensitive to highly distributed attacks where each individual zombie only sends a small amount of packets. And the ICMP packets are often dropped when routers experience high data rates. Two revised schemes [Man01], [Wan03a] are proposed to make up the weaknesses by introducing one control bit or a special message. The messaging method increases the network traffic and is not feasible under distributed attacks. • Logging: Logging may be the most direct detection method for analyzing traffic patterns. Although to store all the data in the network is impossible, probabilistic sampling or storing transformed information is still feasible, for example, through trajectory sampling [Duf00] and hash-based traceback methods [Sno01], [Bab02]. Although it needs excessive processing and storage requirements, logging traceback may be a promising choice in active defense systems. It provides relatively precise detection and doesn’t need a large amount of attack packets. When the DDoS attack signature or deployment signature is detected, we require the logging traceback to find the real source of the attacker. Then it is possible to protect the victim before the suffering occurs.

19



Packet Marking: The idea of packet marking is to insert traceback data into the IP packet for marking the packet on its way through the various routers from the attack source to the destination. Probabilistic Packet Marking (PPM) [Sav00], [Sav01] is the main method of packet marking. The assumption of PPM is that the attacking packets are much more frequent than the normal packets. It requires less traffic volume than ICMP traceback, but it encounters computational difficulties as the numbers of attack sources increase. To perform a successful traceback, enough packets must be collected to reconstruct each edge of the attack path and then the full attack graph. Moreover, PPM is vulnerable to some attack of adding falsified information to the packets, for example, Groups Of Strongly Similar Birthdays (GOSSIB) [Wal02].

2.2.3.

Congestion Control Techniques
A myriad of algorithms have been designed for rate-control packet dropping used in

areas such as congestion control, network traffic management or active queue management. Notable examples include RED [Flo93], CHOKe [Pan00], etc. However, these algorithms cannot be applied in fighting against DDoS attacks because a successful algorithm should identify the malicious flows even if they behave well before they arrive the victim network. Furthermore, the algorithms should also keep the false positive rate low to avoid unnecessary adverse effects on legitimate user traffic. To fight against the negative impacts resulting from the increased application of non-congestion-controlled best-effort traffic on the Internet, Floyd and Fall [Flo99] argued for the necessity of congestion control mechanisms in routers to identify and restrict the bandwidth usage of selected high-bandwidth best-effort flows. Three approaches to

20

identifying misbehaving flows are suggested: (1) identify flows that are not TCP-friendly; (2) identify unresponsive flows; and (3) identify flows using disproportionate bandwidth. On the other hand, an alternative solution is the per-flow scheduling or fair-queuing. There are several other efforts that are based on this idea. Representative examples can be found in ECN [Flo94], Robust ECN [Spr03], TFRC [Han03], RAP [Rej99], WEBRC [Flo00], [Lub04], and ATCP [Par01]. TCP trunking [Kun99] is used to implement TCP style congestion control on aggregated traffic streams sharing the same pair of starting and ending routers. By installing the management TCP connections at both ends, UDP or any other un-responding flows will also be constrained in their bandwidth usage. The management TCP connection mechanism allows the TCP trunk to have guaranteed minimum bandwidth (GMD). Beyond that, a TCP trunk can use higher bandwidth that is available. This approach is helpful to control aggregated traffic streams sharing a pair of common routers. However, in combating DDoS attacks, the flows we want to monitor only contain one useful piece of identifying information—the packets have the same destination. Their source IP addresses are often spoofed. Therefore, it is a baffling question as to whether we can treat them as a trunk just based on the same destination IP and, perhaps, the port number. Targeting on the aggregate congestion control for distributed multimedia applications, Ott et al. [Ott04] suggested an approach that inserts a new protocol layer on top of IP and below the TCP/UDP layer. Using the Coordination Protocol (CP), a cluster Aggregation Point (AP) identifies Cluster-to-Cluster application packets and attaches network probe information to each. Essentially, this new protocol layer performs the congestion control functionality corresponding to an aggregate level higher than IP packets. An explicit congestion control mechanism is adopted based on calculating the RTT (round-

21

trip time), available bandwidth, loss rate, etc. The major drawback of this approach is the need to modify the protocols implemented in routers, at least routers playing the role of AP.

2.2.4.

Flow Filtering Techniques
Segregating and filtering off malicious flows without hurt legitimate traffic is the

main goal for defenders. From the point of view of deployment, filtering can be classified as ingress filtering [Fer00] and egress filtering [San00]. Ingress filtering is deployed on the external interface of a network and drops all spoofed incoming packets. For example, the IP addresses belong to its internal network. On the other hand, egress filtering is applied on the internal interface of a network to deal with the packets going out. In the same way, egress filtering drops all the packets that do not have their local network addresses. It would be an efficient defense scheme against DDoS attacks if these filtering mechanisms are widely accepted and deployed, because they could perfectly stop all spoofed packets travelling through the Internet. Furthermore, the filtering mechanisms help to traceback any packet’s original source, since they force users to send true IP addresses. However, these mechanisms are not widely deployed by the ISPs or even resisted because of liability problems. Roshan Thomas proposed a legitimacy-based DDoS filtering scheme, NetBouncer [Tho03]. It maintains a legitimacy list to differentiate malicious packets and legitimate packets. If the packets are not on the list, NetBouncer will proceed to administer a variety of legitimacy tests to challenge the client to prove its legitimacy. However, this scheme has not been tested in real network environment. Another filtering mechanism that has been proposed is Hop-Count Filtering [Jin03]. The idea is that although the attacker can forge any field in the IP header, the number of hops an IP packet takes to reach its destination cannot be falsified. So Hop-Count Filtering

22

(HCF) could be mainly applied to filter the spoofed IP packets. It extracts the TTL information from the IP head to compute the hop-count, then by comparing the computed hop-count with the stored hop-count, the likely spoofed packets are identified. Because this method still has a false positive rate, it takes no action to defend attacks until in the action state. Steven J. Templeton also found that the final TTL values from an IP address are generally clustered around a single value [Tem03], but no solution has been provided.

2.2.5.

Deployment Tradeoffs
Different options exist regarding where the DDoS defense is deployed. MULTOPS

[Gil01] and D-WARD [Mir05] suggested filtering or rate limiting on suspicious flows at the source end. The security managers often focus on protecting their own networks and choose local detection approaches [Car06]. For instance, the COSSACK [Pap03] and DefCOM [Mir03] deploy detectors at the victim side and send an alert to filter or to a rate limiter located on the source side. Chen and Song [Che05a] proposed a perimeter-based defense scheme for ISP to enable anti-DDoS services for their customers. Their scheme relies on the edge routers to identify the flooding sources and use rate-limiting filters. There are different options regarding the location where the DDoS detection and filtering modules should be deployed based on different assumptions. In the D-Ward project [Mir05], the localized attack detection is performed at the source edge network. However, the lack of motivation and high false positive rates prevent such egress points filtering techniques from being adopted widely. In contrast, in the COSSACK project [Pap03], researchers chose to observe traffic using watchdogs deployed at the ingress/egress points of the target network. Once traffic volume anomalies are detected, a watchdog sends an alarm to other watchdogs asking them

23

to perform flow screening. However, the premise of this design is that other edge networks are willing to act cooperatively. Unfortunately, no one can guarantee that networks located in different countries managed under different rules may behave accordingly. Recognizing those drawbacks, researchers made reported efforts to loosely couple more complicated functions with IP protocol [Kat97] to implement DDoS detection in the core of the network [Pap03]. There are two major concerns that prevent their further steps. The first one is that the multi gigabyte data rate prevents the heavily burdened core routers from sharing too much capability to perform appreciable traffic analysis for security. Secondly, it is difficult to decide a threshold which indicates whether the traffic volume is beyond the range of normal variance. DefCOM [Mir03], [Mir05b] is the reported research that is most close to my effort. It builds a distributed peer-to-peer network of cooperative defense nodes scattered throughout the Internet. It divides the peer nodes into three categories according to the assigned functions. An alert generator detects the attack and delivers the alarm to the rest of the peer network, a rate limiter puts rate constraints on high volume traffic destined for the victim, and a classifier performs selective rate limiting by differentiating legitimate and attack packets. Essentially, DefCOM makes efforts to integrate the D-WARD, COSSACK and core routers with a peer-to-peer overlay. It still depends on the edge networks to cooperatively run security programs like the watchdog of COSSACK and the D-WARD agents. As we indicated previously, the anarchical culture of the Internet makes it impossible to have all edge networks well behaved. Another potential problem of DefCOM lies in the distributed allocation of alert generator, rate limiter and classifier functions. In some cases, the malicious flows still travel

24

through the network before being filtered off by the rate limiter even if they were correctly classified as malicious ones by the classifier. Also, it is doubtful whether the alerts can reach classifier and rate-limiter modules timely while the victim network is overwhelmed by flooding.

2.2.6.

Other Techniques
Recognizing that most DDoS attacks are launched automatically through certain

toolkits, researchers proposed to use human-centric interfaces to distinguish human users and automated zombies [Sta05a]. The connections cannot be established unless they are validated at any of the entry points using either a cryptographic authentication mechanism or a Graphic Turing test to distinguish humans from attack scripts [Die00]. Thus, the DDoS attack bottleneck is shifted from the server to the high-performance routers deployed around the server. MOVE [Sta05b] and GORE [Cho05] are based on similar principles. Yau and his colleagues [Yau05] proposed to install “appropriate” throttles at distributed routing points to protect a server system from being overwhelmed by excessive service requests. The max-min fair queue mechanism is proven effective for filtering off traffic generated by aggressive attackers. Essentially, it is a rate-limiting mechanism installed on the upstream routers of the server being protected. A minority first scheme is suggested to provide good quality of service (QoS) to sources that use the network resources properly and poor QoS to resources that use network resources so excessively as to result in network congestion [Ahn03]. The major weakness of the queue analysis based approaches is that the source address spoofing makes it challenging to perform flow identification. Recently, a more aggressive approach called speak-up is proposed to defend DDoS attacks using offensive strategies [Wal06]. With speak-up, the server under attack

25

encourages all clients to generate a higher volume of traffic if the resource permits. In this manner, the good traffic may crowd out the malicious attack traffic and capture a larger portion of the server’s resources. Authors claim that this approach is effective for defending servers against application-level DDoS attacks. One potential problem of speak-up is that the link bandwidth could exhaust when all clients respond actively. It is possible to incur congestions in the network on links where both attack traffic and legitimate flows travel by. Other un-related traffic sharing the links may suffer.

2.3. Summary
This chapter overviews the state of the art research in defense against DDoS attacks. Today’s DDoS detection systems are mostly based on detecting the flooding consequences rather the causes of traffic surges [Car06], [Cha02a], [Hou01], [Moo01], [Sch97], [Spe04]. Flooding consequences are displayed by the congestion of communication links [Mah02], an overflow in a half-open SYN queue [Lem02], or an imbalance between incoming and outgoing traffic on router ports [Wan04]. Unfortunately, the damage has already been done when these flooding consequences are observed. Thus, it is highly desired to detect the launching of DDoS attacks at a very early stage, instead of waiting for the flooding to become widespread. Looking at the defense schemes discussed in this chapter, almost all reported DDoS attack defense schemes conform to the end-to-end paradigm. This paradigm prevents a real distributed defense scheme from being constructed. Therefore, this dissertation explores a new method of performing DDoS defense in the core network. This dissertation proposes a strategy to defend DDoS attacks from the ISP’s perspective. By pushing traffic monitoring and management functionalities into intermediate networks, multiple ISP networks can

26

collaboratively obtain a larger spatiotemporal vision of the traffic. By applying the approach of cooperating crossing domains, we can timely detect and respond to DDoS attacks before the damage is done.

27

Chapter 3 Secure Infrastructure Protocol for IPv6
Traditional security protocols focus on information security that protects the confidentiality, integrity and authentication of network connections. However, attacks on Internet infrastructure aim at undermining service availability, network stability and reliability. This chapter presents a secure infrastructure protocol (SIP) that provides a platform on which multiple ISP networks can work cooperatively to defend against DDoS attacks. In the long-term, SIP can be an integrated part of the IPv6 standard to make a robust infrastructure for the next generation Internet.

3.1. Motivation
There is sufficient motivation for ISPs to deploy a distributed DDoS attack defense mechanism throughout their networks. First of all, ISPs can monitor whether their infrastructure is under attack or is being used to transfer attack traffic. Secondly, ISPs can help each other to defend distributed attacks by identifying and performing rate-limiting against the attack traffic. Additionally, such a robust infrastructure could be a selling point from a marketing perspective. More customers may be attracted if an ISP claims that using its networks leads to less breakdown experiences. In my approach, routers monitor local traffic aggregation patterns and exchange detected potential anomalies with other routers under the same authority. Since they are

28

under the same authority, ISPs can ensure that all routers work cooperatively and follow the same rules. Even if there is a random fluctuation in legitimate traffic, routers can get rid of most of the false alarms by communicating and reinforcing each other’s suspicious alarms. I believe that such a communication needs to be implemented inside the core networks as a light-weight out-of-band mechanism. One concern is that the SIP approach violates the end-to-end principle, which is one of the Internet’s original principles. However, the end-to-end arguments are not offered as an absolute. There are functions that can only be implemented in the core of the network, and issues of efficiency and performance may motivate core-located features [Blu01]. When the Internet was created, it was supposed to be used by scientists and engineers who were willing to behave well and cooperatively. After decades of development, the Internet has stepped out the ivory tower and has become the most popular platform and infrastructure for the general public. It also attracts users with various backgrounds and different motivations. Like any community, malicious users and abusers are unavoidable. Today, there is less and less reason to believe that we can trust other end-points to behave as desired. The loss of trust leads to the end of the early model of the Internet – a group of mutually trusting users attached to a transparent network. On the other hand, there are more demanding applications that cannot be satisfied by non-guaranteed services provided according to the best-efforts model. Instead, they require more sophisticated Internet services that can ensure a certain quality of service. Real-time video and audio streaming delivery are typical examples. Therefore, making the network more trustworthy and robust, while the end-hosts cannot be trusted, implies more mechanisms in the core networks to enforce desired behavior. Blumenthal and Clark [Blu01] indicated a new principle considering the fact that efforts of putting more functions inside the Internet

29

jeopardize generality and flexibility as well as historic patterns of innovation. The new principle indicates that elements implementing invisible or hostile functions to the end-toend application have to be “in” the network in general. As a result, the application cannot be expected to include that intermediate element voluntarily.

3.2. SIP Overview
Obviously, the distributed DDoS attack defense schemes match Blumenthal and Clark’s new principle. DDoS defense technologies need to be integrated into the network infrastructure and need to be done in a coordinated manner across the backbone [Mar02]. The sources of DDoS attacks are malicious end users and they take advantage of the bestefforts based intermediate networks. Victim end-hosts cannot protect themselves by enforcing the security measures of local networks. It is imperative to implement DDoS defense schemes transparently in the core networks to end applications. I propose the SIP protocol, a light-weight protocol that can be deployed inside the ISP core networks. Basically, SIP provides a secure and efficient platform supporting traffic monitoring, flow analysis, packet scanning, and packet filtering functions at the router level in ISP domains. The SIP elements are routers in core networks and a SIP server in each ISP domain. Cooperation between ISPs is achieved through message exchanging among SIP servers. Routers belonging to different domains won’t communicate with each other directly. To serve this purpose, a 3-level communication model is adopted as illustrated in Fig. 3.1. Inside a domain, routers exchange information with peer routers and report locally detected traffic anomalies to the domain SIP server. SIP servers perform two roles. At the intra-domain level, servers collect alerts or anomaly reports from routers and perform traffic analysis to identify whether there is attack traffic traveling through the domain. At the inter-

30

domain level, SIP servers communicate with servers located in other domains. Due to privacy concerns, ISPs are often reluctant to reveal inside information to competitors, such as topology, bandwidth configuration, or capabilities. Hence, aside from managing the information exchange, SIP servers also are in charge of security policy negotiations. The next section provides a more detailed discussion of trust negotiation.

Figure 3.1 Three levels of communication used in the SIP (secure infrastructure protocol) between two SIP servers in two ISP networks.

SIP is a lightweight protocol that is suitable for supporting Internet infrastructure security, where the network-layer collaborations among routers are desired. Atop SIP, many security functions such as the detection and isolation of worms, DDoS attack detection, or a distributed intrusion detection systems (IDS) [6], [32] can be implemented in the core network without help from end hosts. SIP provides a secure information exchanging mechanism in a layer closer to the physical network inside the ISP networks compared with application layer security models. The SIP is not an IP multicast protocol in a traditional sense for two important reasons. In the vertical direction of the network layer model, SIP protocol sits on top of the IP layer and is transparent to transport layer protocols. From the perspective of deployment,

31

SIP holds its responsibility as limited in routers of a physical network. There are no end hosts or edge network servers involved. The purpose of SIP is to provide a mechanism that enables lower layer (layer 3) network devices to communicate with other devices without interference from the end hosts. To cope with the performance demands of core network routers, this protocol is designed to be implemented using specialized embedded hardware in routers.

3.3. Inter-Domain Trust Control
ISPs often adopt different security policies. In addition, ISPs do not want competitors to map their networks, the available bandwidth limits and so on even if the ISPs are working in a collaborative DDoS defense agreement. The SIP addresses the privacy issue at the policy level instead of authentication, authorization, or channel encryption. Based on a multilateral security trust negotiation framework called Adaptive Trust Negotiation and Access Control (ATNAC) suggested by Ryutov et al. [Ryu05], I propose a simple and feasible trust management scheme. Using this scheme, SIP can help establish trust among ISPs and enter a collaborative DDoS defense system agreement. By trust negotiating, ISPs can determine how much private information is allowed to be shared with others. Combining GAA-API and TrustBuilder schemes, ATNAC regulates when and how sensitive information is disclosed to other parties and captures dynamically changing system security requirements. An ATNAC framework enables a user to detect and thwart attacks on electronic business transactions, adaptive information disclosure and resource access policies according to a level of suspicion. ATNAC also supports a cost effective trust negotiation. Compared with e-business applications that involve multilateral trust negotiation in a

32

dynamic manner, the cooperative operation among ISPs is more stable. Therefore, such a complicated scheme as ATNAC is unnecessary. Each SIP server needs to perform a trust negotiation once only when an ISP network joins the collaborative defense. As show in Fig. 3.1, the inter-domain information exchange is through SIP servers. The trust level determines how much sensitive information can be disclosed when detected anomalies are reported. When an ISP decides to join a collaborative defense agreement with its peers, the administrator sets up the trust levels. SIP currently possesses three trust levels. The highest one is the full trust (FT), the second one is basic trust (BT), and the lowest one is no trust (NT). Their meaning is straightforward. With full trust, the SIP server will provide all necessary information that describes the characteristics of the detected anomaly. With basic trust, the SIP server only sends some statistic information that contains no private and sensitive data. When there is no trust established, there is no cooperative activity. The contents of detailed information being transferred in communication also depend on the type of anomalies detected. This is varied among different concrete problems. Figure 3.2 illustrates how trust levels control the information sharing. When a SIP server detects anomalies in an ISP domain, the server checks the trust levels corresponding to the peer domains in the trust level table. Then according to the information sharing police associated to each trust level, the server determines how much information needs to be sent along with an alert to a cooperative domain. For example, in the detection of DDoS flooding attacks as discussed in Chapter 4, the detailed information describes the spatiotemporal pattern of traffic surge propagation. Such pattern reveals the network topology of the ISP. Without full trust, the ISP may not be willing to let the competitor map its inner topology. Therefore, alternatively the SIP server

33

only transfers a statistical description of the pattern such as the profile of the pattern, including how many nodes, the height of the CAT, the width of the CAT and so on.

Figure 3.2 Illustration of trust based information sharing.

3.4. Message Functionality and Format
This section presents the messages used in SIP protocol in detail. Each SIP node is a layer-3 network device (router or gateway) in an AS supporting the SIP. Messages are designed to serve the functions described in previous subsections. Their formats and data fields are varied accordingly. Table 3.1 summarizes the abbreviations used throughout the discussion.

3.4.1.

Message Discription
Before a node can send messages reporting locally detected anomalies, it must

establish a multicast tree called Local Multicast Tree (LMT) that consists of its peer nodes. Meanwhile, a node has to join a LMT to receive anomaly alerts from its peers. The depth of

34

the tree is determined by how wide the area monitored by the node. In this manner, each node is the root of a multicast tree and also is a child in multiple multicast trees rooted by its peers.

Table 3.1 Abbreviations and Definitions in SIP Messages
Abbreviation LMT LRA LSU LAA ADQ ADP MAX_LIFE_TIME MAX_ADV_INT MIN_ADV_INT MAX_RES_DLY Definition/Default Setting Local Multicast Tree LMT Root Advertisement message LMT Set Up message Local Anomaly Alert message Anomaly Detail Request message Anomaly Detail Reply message The maximum number of minutes the node status is alive / 30 min. The allowed maximum interval between subsequent LRA / 12 min. The allowed minimum interval between subsequent LRA / 8 min. The maximum delay for response to the LSU message / 10 sec.

When there is no anomaly being detected, the SIP nodes periodically multicast LMT Root Advertisement (LRA) messages through their multicast interfaces, announcing their alive status and indicating a lifetime. Each node maintains a LMT and resets the lifetime of the sender as the predefined MAX_LIFE_TIME on receiving a LRA message if the lifetime field is zero. When a new node joins the domain or restarts from power off, it broadcasts a LMT Set Up (LSU) message to ask for immediate LRAs, without the requirements of waiting for the next periodic ones to arrive. The Distance field of the LSU packet is set as the maximum hops that the LMT can cover. If and only if there is no LRA response in 2 MAX_RES_DLY, the node broadcasts LMT again. On receiving a LSU message, the receivers add a child node to their LMT along with responding with a LRA message. The default LRA message multicasting rate is once every 10 minutes, and the MAX_LIFE_TIME default value is 30 minutes. In real-world implementation, the LRA

35

advertisements are not strictly periodic. The interval between subsequent transmissions is randomized to reduce the probability of synchronization with the advertisements from other nodes on the same link. For this purpose, SIP nodes maintain a separate transmission interval timer for each advertising interface. Each time a multicast advertisement is sent from an interface, that interface’s timer is reset to a uniformly distributed random value between the configured MAX_ADV_INT and MIN_ADV_INT. Expiration of the timer will trigger the next advertisement multicasting and a new random value is set. The default set of MAX_ADV_INT and MIN_ADV_INT are 720 seconds and 480 seconds respectively. A similar mechanism is adopted corresponding to the LSU message in order to avoid synchronous answers flooding the sender. The unicast responses are delayed for a small random interval no greater than the MAX_RES_DLY that is set to 10 seconds by default. When traffic anomalies are detected, the node multicasts a Local Anomaly Alert (LAA) message to its children on the LMT. On receiving a LAA message, a receiver will perform security actions accordingly. At the same time, the receiver resets the lifetime of the node that generates the alert. Consisting of alerts only, the LAA messages won’t cause much overhead to the network. The alert types and countermeasures depend on the concrete application. If a node is interested in more detailed information regarding the received alert, it may “pull” what it want by sending an Anomaly Detail Request (ADQ) message in response to LAA message. The alert generating node will return the requested information in an Anomaly Detail Reply (ADP) message. This pair of messages provides a mechanism for nodes to make more accurate decisions.

36

3.4.2.

Message Format
Similar to an ICMP packet, SIP messages are also encapsulated in IP packets. The

message source address is the IP address belonging to the interface from which this message is sent. The Protocol field is set to a value reserved for SIP. The destination address is the IP address of the node to which the message is sent. My discussion focuses on the SIP message format. The field of the IP header is discussed only if it is closely related to certain SIP messages. Figure 3.3 shows the format of SIP messages and Table 3.2 summarizes the value and meaning of each field in the SIP message.

Figure 3.3. Format of a SIP Messages.

37

Table 3.2 Definitions of SIP Message Fields
Field Type Value 0 1 0 1 2 Code 3 4 5 6 Definition This is a normal SIP message Error control message in SIP LMT Root Advertisement message LMT Set Up message Local Traffic Pattern message New Node Join message Local Anomaly Alert message Anomaly Detail Request message Anomaly Detail Reply message The 16-bit one’s complement of the one’s complement sum of the SIP message, starting with the SIP Type. For computing the checksum, the checksum field set to 0. Indicate the depth of the multicast tree The number of minutes the node is available The IP address of the central SIP server The physical port to which the new node is connected The IP address of the new node seen by the receiver Indicate the category of the anomaly detected. Currently, we specify code 1 for low-rate DDoS attacks and 2 for flooding DDoS attacks. Describe how dangerous, emergence of the alert. Or the confidence level of this alert. Sequence number of the alert message Sequence number of the detail request message Detailed information of the alert requested by peer The number of upstream branches of this pattern The number of downstream branches of this pattern

Checksum

Distance Lifetime Central Server IP Address Connection Interface ID New Node IP Address

Alert Code

Alert Level Alert Seq. Req. Seq. Anomaly Description Payload Upstream Port Number Downstream Port Number

All SIP messages share the same ICMP Type value 128 and are separated from each other by different Code numbers. LRA and LSU messages are used to establish and maintain

38

the LMT. The Distance field indicates the range of cooperation and also the size of LMT. The Lifetime is used to notify the peers of the availability status of the sender. If the Lifetime field is set to zero, the receiver refreshes it to the default MAX_LIFE_TIME. The Alert Code field in the LAA message specifies the category of anomalies detected, and the Alert Level field is used to indicate the degree of danger, emergence of a threat, or the confidence level of an alert. To request more detailed information of a received alert message, the request initiator has to indicate which alert message it is interested in. The ADQ message consists of Alert Code, Alert sequence number, and a Request Sequence number. The Alert Code and sequence number are necessary to specify the alert. The request sequence number is used to verify the answer. Along with the timestamp in the IP header, sequence numbers are used to track the status of received alerts. Also, they serve against play-back attacks.

3.5. Potential Applications
SIP is not designed only for the purpose of DDoS attack detection as described in this dissertation. In fact, SIP is designed to provide a high efficiency information exchanging mechanism in a layer closer to the physical network. This is helpful to avoid the performance punishment resulting from the lack of awareness of underlying network structures. The items defined in LMT could be used with great flexibility. For example, the usage of Distance item is essentially a metrics to measure a group of nodes. It could be defined according to certain applications instead of using the number of hops. For instance, each node may be assigned a unique ID, the distance could be the number of difference bits in their IDs; or SIP nodes could be arranged in a peer-to-peer fashion, and a distributed hash table (DHT) based routing scheme could be used.

39

Besides the traffic monitoring tasks, SIP is a protocol in which various network layer security applications such as the detection and isolation of worms, DDoS attack detection, or the distributed intrusion detection mechanisms can be implemented. Similar to the research in multicast mechanisms, research in these security areas are also trying to design overlay networks on top of physical networks to achieve high bandwidth utility, high throughput, low latency, and low management overhead. SIP is an ideal candidate for the hardware implemented network security protocol because of its simple data formats. One major challenge in making network fabric robust against malicious Internet infrastructure attacks lies in the conflict that routers cannot afford to execute security functions due to limited computing power. Implemented in reconfigurable hardware, SIP can push the traffic anomaly-monitoring task to a lower layer of the packet processing procedure. The suspicious traffic patterns are detected even before the traffic hits the routing fabric in the core of routers. Currently, I am implementing SIP and its application in low-rate DDoS attack detection atop a Xilinx Vertex IV FPGA device, which supports a MicroBlaze soft-processor and FFT cores.

3.6. Summary
Protecting the Internet infrastructures from malicious attacks has been a compelling task. As tremendous damages may be caused before the end hosts realize them, end hosts based defense systems cannot respond swiftly to anomalies that happen inside the network. To push security functions into the core network, I propose SIP protocol that enables layer 3 intermediate network devices to monitor traffic anomalies collaboratively. SIP protocol is different from traditional IP multicast, application layer multicast, and overlay network multicast protocols that have been reported previously. In the vertical

40

direction of the network layer model, SIP protocol sits on top of the IP layer and is transparent to transport layer protocols. From the respective of deployment, SIP holds its responsibility limited in routers of a physical network. No end hosts are involved. I verified the usability of SIP protocol through experiments on a distributed cooperative DDoS attack detection scheme. Implemented on top of SIP, my algorithms effectively improved the detection accuracy against low-rate DDoS attack streams. The experiment on DETER testbeds revealed that SIP is an efficient platform on which network security schemes can be implemented. The SIP messages are designed concisely to avoid incurring much communication and processing overhead. In addition, it may not be as intrusive to the network code as the IPsec protocol. SIP prefers support from specially designed hardware while being implemented in core network routers, but it is primarily for the performance concerns, not mandatory requirements. To make SIP a standard protocol for next generation networks, my efforts will take two directions. The first is further experiment on more applications on top of SIP. In this dissertation, I developed mechanisms atop SIP to defend against flooding DDoS attacks and shrew DDoS attacks. More applications, for example, the early detection and containment of Internet worms, will be developed. Secondly, I will be implementing SIP on the platform of reconfigurable hardware. Implementation atop reconfigurable hardware platforms using FPGA or network processor units are capable of carrying out meaningful work without incurring much impact on the system throughput.

41

Chapter 4 Detection of DDoS Attack in Multiple ISP Networks
This chapter focuses on the distributed change-point (DCP) detection based scheme for early detection of flooding DDoS attacks. Beginning with a brief introduction to its rationale, this chapter presents the algorithms of the crossing domain collaborative detection on top of a change aggregation tree (CAT). The results of this experiment on the DETER testbed verifies that the DCP scheme is effective.

4.1. Introduction
To defend against distributed denial of services (DDoS) attacks, we wish to achieve real-time detection of incurred network anomalies. Thus, it is highly desired to detect the launching of DDoS attacks at the earliest stage, instead of waiting for the flooding to become widespread. However, at the early stage of a DDoS attack, the traffic changes are difficult to detect because very little fluctuations in traffic are observable at aggregate traffic levels. Due to the high data rate in today’s Internet, routers cannot afford much computing and storage resources for security purposes. That makes monitoring the Internet traffic at individual flow level cost prohibitive to cover all possible flows that identify using the 5tuple {source IP address, destination IP address, source port number, destination port number, protocol}.

42

To be cost-effective, we propose to monitor the traffic at a superflow level. A superflow contains all packets destined for the same network domain from all possible source IP addresses, using any port numbers, and applies various protocols such as TCP or UDP, etc. This level lies between the level of large-scale aggregate traffic and individual 5tuple marked flows. This approach is inspired by the classless inter-domain routing (CIDR) idea [Ful93]. All packets of a superflow have the same destination domain IP address. When a DDoS attack is launched, attacking flows converge toward the victim host. Therefore, we can observe that abnormal traffic volume surges on routers along the paths of aggregation. Usually these changes in traffic flows present a directionality converging towards the victim. Random fluctuations incurred by legitimate traffic flows do not present such converging properties. Once a DDoS flooding attack has been launched, the spatiotemporal traffic pattern tends to form a tree. By recognizing such tree-like traffic anomaly patterns, we can detect the DDoS attacks. To each individual router, such patterns are observed as directionality and convergence in spatiotemporal distribution changes of traffic volumes as a pattern of varied combination of different incoming and outgoing ports. Routers that have observed the anomaly traffic surges are referred to as attack-transit routers (ATRs) since they participate in the transferring the malicious attacking flows. Motivated by the desire to have lightweight detection with low complexity [Bel03], [Che05], [Wan04], we propose a distributed change-point (DCP) detection architecture using a new mechanism, called change aggregation tree (CAT). Supported by the communication platform provided by SIP, this CAT mechanism obtains a global vision of traffic surge propagation. Inside the ISP domain, the routers detect abrupt changes of superflows at individual levels. The CAT server uses the traffic change patterns collected by ATRs to construct the local CAT subtree, which represents the attack flow propagation

43

pattern. In addition, CAT servers belonging to different domains send the local constructed CAT subtree to the destination domain that is identified by the domain IP address of the superflow. Subsequently, the CAT server in the destination domain merges the received CAT subtrees from other servers to form a global CAT tree. The global CAT tree is rooted at the last- hop router to the edge network where the victim resides, the nodes on the tree are ATRs, and the edges are links between ATRs whereby the malicious attacking flows travel towards the victim.

4.2. Framework of Distributed Change-Point Detection
The DCP scheme detects the start of DDoS flooding attacks by monitoring the abrupt traffic changes at distributed network points. Once a sufficiently large CAT tree is constructed that exceeds a certain preset threshold value, a suspicious attack is declared. This section presents the principles behind the DCP system. In this section, the issue of change detection is conducted at the level of individual routers. In next two sections, we will extend the DCP scheme across network domains.

4.2.1.

Distributed Change-Point Detection System
Figure 4.1 presents the system architecture of the DCP scheme. The system is

deployed over multiple AS domains. There is a central CAT server in each domain. The system detects the traffic changes, aggregates detected changes, and collects alerts over collaborative CAT servers. Routers are in charge of attack detection and raising alert, whereas the CAT servers aggregate distributed alerts. The root of the CAT is located at the last-hop domain server. Each tree node corresponds to an attack-transit router (ATR). Each tree edge corresponds to a link between the attack-transit routers.

44

The CAT servers at different domains could form an overlay network or communicate with each other through virtual private network (VPN) channels or an overlay network. The router monitors the incoming and outgoing traffic flows at its input and output ports. Periodically, each router reports the traffic status to the CAT server in its domain. If a router observes abrupt traffic variations, which are far above the historical average, an alert message is sent to the CAT server. The server is responsible to construct the CAT tree for the entire domain. The CAT server also exchanges CAT information with other domain severs.

(a) Multi-domain defense system

(b) Inter-domain communications via VPN tunnels or overlay network atop the CAT servers

Figure 4.1. Distributed change-point detection of DDoS flooding attacks over multiple autonomous systems (AS) or multiple AS domains.

In the sequel, AS domains and ISP core networks are used interchangeably. The CAT detection scheme does not need to specify an absolute threshold on the volume of traffic. The detection is done by checking the number of nodes (routers) raising the alerts from the CAT subtree. Figure 4.2 illustrates how a CAT subtree is constructed at a single domain server. Figure 4.2(a) shows a flooding attack launched from 4 zombies, the routers that are located along the routing path to the victim detect an abnormal surge of traffic at

45

their I/O ports. They report the suspicious flows with the involved upstream and downstream routers to the CAT server. Using Algorithm 4.2 that is to be discussed in section 4.4, the server constructs a CAT rooted at the end router R0 in Fig. 4.2(b). The server recursively scans through all upstream routers to construct the tree. The CAT presents a traffic-flow tree pattern rooted at the router connected to the edge network, where the victim is attached. With sufficient exchange of alert information from related domains, the system can detect the DDoS flooding attack at a very early launching stage, before the super-flows can reach the victim network.

(a) Traffic pattern of a DDoS flooding attack

(b) CAT subtree rooted at router R0

Figure 4.2. An illustration of change aggregation tree (CAT) constructed at the end router (R0) connected to the victim system.

4.2.2.

Change-Point Detection Principle
In change-detection problems, if pre-change and post-change distributions are

known, the CUSUM statistic has been suggested as a way to solve the problem [Bla01]. Due to the lack of such statistical distribution models, we adopt a non-parametric approach for its

46

simplicity and independence to distributions. Let t1, t2, …. , tm be discrete time instants and x(tm, i) be the number of packets received by a router during time slot m at port i. The historical estimate average number of packets X (tm , i ) is defined iteratively by:
X (t m , i ) = (1 − α ) ⋅ X (t m−1 , i ) + α ⋅ x(t m , i )

(4.1)

where 0 < α < 1 is an inertia factor showing the sensitivity of the long-term average behavior to the current traffic variation. Higher α implies more dependence on the current variation. We define below Sin(tm, i) as the deviation of input traffic from the average at time slot tm.

Sin (t m , i ) = max{0, Sin (t m−1 , i ) + x(t m , i ) − X (t m , i )}

(4.2)

The subscript in indicates that this is the statistics of the incoming traffic. While a DDoS flooding attack is being launched, the cumulative deviation is noticeably higher than the random fluctuations. Since Sin(tm, i) is sensitive to the changes in the average of the monitored traffic [Bla01], I measure the abnormal deviation from historical average as follows. The deviation from average (DFA) is the ratio of such an attack indicator. The incoming traffic DFA is defined below at time tm and at port i:

DFAin (t m , i ) = Sin (t m , i ) X (t m , i )

(4.3)

If the DFA exceeds a router threshold β, the measured traffic surge is considered a suspicious attack. The threshold β measures the magnitude of traffic surge over the average traffic value. This parameter is preset based on previous router use experience. In a monitoring window of 100 ms to 1 s, a normal superflow is rather smooth due to the statistical multiplexing of all independent flows heading for the same destination [Jia05]. If there is no DDoS attack, we expect a small deviation rate far below β. In section 6, we will discuss the impact on the performance of the CAT detection scheme when β is chosen between 2 ≤ β ≤ 5. Let τ be the earliest time when a router detects abnormal deviation in traffic volume. This time instant is formally defined below:

47

τ = min{t m : Sin (tm , i ) / X (tm , i ) ≥ β }

(4.4)

For outgoing traffic, we define y(tm, i) as the number of packets in time tm leaving at port i and Y (tm , i ) be the historical average of the number of leaving packets. Similarly:
Y (t m , i) = (1 − α ) ⋅ Y (tm−1 , i) + α ⋅ y (t m , i )
S out (t m , i ) = max{0, S out (t m−1 , i ) + y (t m , i ) − Y (t m , i )}

(4.5) (4.6)

Using above equations we can calculate the deviation of current traffic volume compared to the historical average volume. Then the combination of input and output port gives us a clue to tell how incoming traffic surges go through the router. Such patterns are used to segregate different traffic conditions at routers. Next section shows how to use these equations and parameters to detect the abrupt changes in traffic volume for certain superflows. Please note that the word “abrupt” does not imply a huge fluctuation amplitude. As long as the surge is obvious in the monitoring window, that change is an abrupt change.

4.3. Change Detection at a Single Domain
This section shows how a CAT server in a single domain constructs the CAT subtree using collected anomaly patterns from ATRs. Before introducing the algorithm of tree construction, we discuss the principle of anomaly detection at individual routers.

4.3.1.

Anomaly Detection at Router Level
Each router monitors traffic variations and counts the packet number within each

monitory window at each I/O port. We use the term traffic pattern to refer to the combination of traffic surges at all I/O ports of a router. In general, a router with m-input ports and n-output ports may encounter 2m+n possible traffic patterns. The height of the black boxes in Fig.4.3 signifies the magnitude of traffic volume at the relevant links. The raised block height indicates a surge detected and the lower height stands for normal traffic flow.

48

(a) Flow through

(b) Partial Aggregation

(c) Full Aggregation

(d) Scatter Pattern

Figure 4.3. Four basic traffic patterns of traffic changes at a 2 Ñ… 2 router I/O ports

All packets of a superflow must be homing towards the same destination network. Before entering the destination domain, the flow paths present a converging homing-tree pattern. Only at the destination domain, the superflow scatters packets towards a particular edge network specified by the destination IP address. There exist 16 possible traffic patterns for a 2 Ñ… 2 router. For simplicity, we illustrate in Fig.4.3 only 4 basic traffic patterns at a 2 Ñ… 2 router with m = n = 2. The remaining 12 traffic patterns can be specified similarly. a. Flow-through pattern: This traffic pattern is shown in Fig. 4.3(a). The router forwards the entire traffic flow from an input port to a selected output port without subdividing or diverting the traffic to other outgoing ports. b. Partial aggregation pattern: All the incoming flows are merged at one outgoing port iout, not all incoming flows contain traffic surges as shown in Fig. 4.3(b).

49

c. Full aggregation pattern: The outgoing flow merges multiple incoming flows, all containing traffic surges exceeding the threshold β. This router is considered a merge point on the attacking path (Fig.4.3(c)). d. Scatter pattern: The incoming flow scatters at this router. This pattern is not part of a DDoS attack (Fig. 4.3(d)). This pattern is observed only in the destination domain. Another statistical parameter, deviation ratio (DR), is defined below to measure the ratio of incoming packets from port iin have propagated to output port iout. DR is the ratio of traffic deviations between the input and output ports.

DR(iin , iout ) = Sout (tm , iout ) Sin (tm , iin )

(4.7)

If DR > 1, the router amplifies the input deviation. This corresponds to a full surge of traffic volume. DR ≈ 1 implies the router merely plays the role of a forwarder. This phenomenon is observed in the partial surge at one input port. Meanwhile, the case of DR < 1 indicates that the incoming wave is scattered to multiple ports. It is not part of the convergence traffic of DDoS attacks. Therefore, by checking the DR value, a router determines whether the pattern is part of a CAT tree incurred with a DDoS attack. To be more precise, we specify a local detection algorithm for suspicious traffic patterns here. When a router detects that a DFAin exceeds the deviation threshold β, it calculates the deviation rate between the outgoing and incoming ports. If DR is close to or larger than one, the traffic aggregation pattern is considered suspicious. The router generates an alert message and reports the pattern to the server. Otherwise, the router sends a regular status message indicating no anomaly observed. Essentially, the DR specifies how much of the incoming traffic surges is propagated through the router. This DR measure is directly related to the detection rate. Below is the pseudo code of Algorithm 4.1 for local change detection at the router level.

50

Algorithm 4.1: Attack detection at router level Input: x(t, i) and y(t, i): Incoming and outgoing packets at time t and port i, respectively X ( t m − 1 , i ) : Historical average of packet arrivals up to time m-1 at port i

Y ( t m − 1 , i ) : Historical average of outgoing packets up to time m-1 at port i Router detection threshold β based on past experience Output: Alert messages sent to the central CAT server. Procedure: 01: Update historical average of I/O packets in a flow 02: Calculate DFAin using Eq. (4.3) 03: If DFAin ≥ β Then 04: Calculate DR using Eq. (4.7) 05: If DR ≈ 1.0 Then 06: Suspicious pattern detected. Send out an alert message to CAT server. 07: Else 08: Nothing suspicious. Send out a regular status message CAT server.

4.3.2.

CAT Subtree Construction Algorithm
This section describes the details of CAT subtree construction at each CAT server in

a single network domain. Each network domain generates a local subtree based on locally collected information. The global CAT tree is generated by merging all subtrees. While the flooding traffic merges at the victim end, the routers along the paths capture suspicious traffic patterns. In this section, we concentrate the subtree construction in a single network domain. Algorithm 4.2 specifies the subtree construction at a single domain CAT server. The router also reports the ID of a superflow causing the traffic surge. Besides the number of upstream and downstream routers, the alert message provides the upstream and downstream router IDs. Since all routers are under the same authority and work cooperatively, each router knows their immediate neighbors connected through the ports. The alert message provides information for the server to include the routers in the CAT subtree. Table 4.1 summarizes the information carried in a typical alert message from an attack-transit router. The major purpose of sending the flow status message is to report where the suspicious flows are captured. To indicate the location of a suspicious flow, the router

51

identifier has to be sent. It is also mandatory to identify the superflow identifier of the n-bit prefix of the destination IP addresses. To construct the CAT, the status report provides the upstream and downstream router identifiers instead of router I/O port numbers. Since all routers are under the same ISP authority and work cooperatively, each router knows their immediate neighbors. Using the reported status information, the domain server detects suspicious attacks based on the CAT tree constructed. To clarify the control flow, this construction process is specified by a flowchart in Fig. 4.4.

Table 4.1. Information in an Alert Message Sent from a Router
Parameter nd_id fl_id up_num dn_num up_id dn_id Router status Brief Definition The router ID, The superflow ID Number of upstream nodes Number of downstream nodes node ID of upstream node node ID of downstream node Suspicious attack or normal traffic

Algorithm 4.2: CAT Subtree Construction in a Single Domain Server Input: Traffic alert messages received from all routers In the same AS domain Output: A data structure describing the CAT subtree constructed in this domain Procedure: 01: Read all suspicious patterns in and arrange them according to router ID 02: Start from the suspicious node with minimum ID Rmin 03: root Rmin 04: read the upstream node number up_num 05: read the downstream node number dn_num 06: node_number node_number + up_num - 1 07: While up_num > 0 08: Read in one upstream node Rup 09: Add Rup as a leaf node 10: scan through its upstream nodes 11: up_num up_num – 1 12: End While 13: While dn_num = 1 14: Read the downstream node Rdn; 15: root Rdn 16: node_number node_number + 1 17: Scan through other upstream nodes of new root; 18: dn_num dn_num of the new root 19: End While

52

Figure 4.4. Control flow in constructing the CAT subtree specified in Algorithm 4.2.

The output of Algorithm 4.2 is a single-domain CAT subtree similar to the one shown in Fig.4.2(b). The CAT tree is specified by a hierarchical data structure. The tree starts from the root node, which carries the superflow ID, the number of routers involved, root node ID, and the count of child nodes at the next level. The next level lists the

53

information pair {L1 node ID, count of children at next level L2}. This process continues until reaching the leave nodes of the tree. The CAT subtree is eventually sent to the CAT server of the destination domain. In Algorithm 4.2, the domain server constructs the CAT subtree based on collected status reports from the routers. Routers which detected no attacks are not involved in the tree construction. Figure 4.4 illustrates the process flow of CAT subtree construction. Starting from the node Rmin with a minimum ID, the CAT server takes it as the root node. The server scans through upstream child nodes identified by up_id. This descendent search is performed iteratively until the leaf nodes are reached. If there is a downstream router Rdn, we take router Rdn as the new root and repeat the procedure. Meanwhile, the descendent search procedure is repeated for all upstream routers of root Rdn. Then we check the downstream router of Rdn and repeat the procedure until the downstream router is out of the domain boundary.

4.4. Merging CAT Subtrees from Multiple Domains
This section describes the extension of the single-domain detection scheme that is used to work on multiple network domains. After presenting the mechanism of cross-domain attack detection, we analyze the complexity of the global CAT tree growth.

4.4.1.

Global CAT Tree Construction
In a DDoS flooding attack, the attacker often recruits many zombies widely

distributed over the Internet. The flooding traffic may travel through multiple AS domains before reaching the edge network, where the victim is physically attached. Routers at the upstream domains observe the suspicious traffic flows earlier than routers at the downstream

54

networks. Our DCP detection system was designed to have strong collaborations among all domain servers along the superflow paths. Algorithm 4.3 specifies the merge of CAT subtrees for detecting DDoS attacks across multiple network domains.

Algorithm 4.3: Global CAT Tree construction and detection decision Input: CAT subtree description from participating domain servers, the server detection threshold θ. Output: The global CAT tree over multiple AS domains. Raise the alert for an imminent DDoS attack. Procedure: 01: Construct the local CAT sub-tree (Algorithm 2) periodically 02: Receiving sub-trees from other CAT servers 03: If local subtree exists, Then Check the superflow ID, 04: If this domain is the destination domain, Then Set distance r = 1 05: Merge subtrees from domains at distance r to the current global tree 06: r r+1 07: While { there are un-checked sub-trees }, generate the CAT profile 08: If CAT profile ≥ θ Then DDoS attack is detected and raise an alert 09: Else Check the root router position 10: If root router is connected to other domain 11: Then Sent the global CAT tree to the destination domain server 12: Else Raise an attack alert based on the global tree merged

The CAT subtrees constructed at all traversed domains must be merged to yield a global CAT tree at the destination domain. The final declaration of a DDoS attack is the result of threshold detection using the global CAT tree. During such an event, not only does the victim network launch appropriate countermeasures, but some traceback actions are also taken by all attack-transit routers along the superflow paths. The actions include dropping of suspicious packets or rate limiting against the flows. The global CAT tree shows the propagation pattern of flooding attack flows.The leaf nodes are directly related to the zombies used. The height of the global CAT tree corresponds to the superflow hop count. Some highly distributed attacks may recruit thousands or even millions of zombies, the global CAT tree may cover a wide area on the

55

Internet. Therefore, we use the global CAT tree profile θ as a global detection threshold. The CAT profile indicates how many routers have observed abnormal traffic surges. Thus θ is an integer bounded by the domain size or by the number of ATRs. The tree width and height thus reveal the scope of the DDoS attack. Through experiments on the DETER testbed, we obtain the global detection threshold value by training from some attack datasets. These threshold values have yielded the highest detection rate and lowest false positive rate during the training period. On receiving subtrees from upstream CAT servers, the CAT server in the destination domain builds the global CAT tree from its local subtree. Once the global CAT tree is formed, the server compares the CAT profile with the global detection threshold θ to decide on a DDoS attack. An alert is raised and necessary countermeasures are triggered, accordingly. Figure 4.5 shows an example network environment involving 6 AS domains. The victim system is located in the AS1 domain. Zombies are scattered widely in the Internet outside the illustrated domains. By detecting abnormal traffic changes in each domain, the CAT server creates a CAT subtree locally at each domain using Algorithm 4.2. Figure 4.5(b) shows three steps taken to merge the 6 subtrees generated by 6 CAT servers of 6 AS domains. All 6 subtrees have resulted from checking the packets belonging to the same superflow traffic destined for the same domain AS1. Five subtrees generated at AS 2, 3, 4, 5, and 6 at upstream domains are sent to AS1 at Step 2. Then, the concatenated CAT subtrees are connected to the downstream subtree at AS1. Thus the global CAT tree is finally rooted at the last hop router to an edge network R0 that is attached to the victim system.

56

(a) DCD architecture over 6 domains

(b) Merging 6 subtrees to yield a global CAT tree Figure 4.5. An example 6-domain global CAT tree construction environment

57

4.4.2.

CAT Tree Growth Complexity Analysis
The complexity of the CAT growth is analyzed below based on Internet topology

data available from open literature [ISO06], [Sig03]. Figure 4.6 illustrates the process of the CAT tree growth out of merging subtrees from closer to remote domains. Let r be the logical distance of an AS domain to the destination domain. The server checks the received subtrees in increasing order of distance r. The system merges the subtrees from ASs located in distance r = 1 first to form a partial global tree. Next, it merges the subtrees from domains at distance r = 2. The merging process repeats with distances r = 3, 4, until all subtrees are merged into a large global CAT tree.

Figure 4.6. Merging CAT subtrees from nearby domains to outer domains to build the global CAT tree, where AS 0 is the victim destination domain

I analyze below the complexity of global CAT tree growth at intra-domain and interdomain levels. Periodically, the routers monitor traffic conditions and report anomalies to the server in the domain. The local setting parameters α and β affect the size of the local CAT subtrees constructed at routers. Given a domain consisting of N routers, the number of alerts that CAT server receives is proportional to N. The passing-threshold CAT subtrees constructed (Algorithm 2) equal to the number of alerts received by the server. Therefore,

58

the detection time is approximated by O(N) within each domain. Of course, different domain sizes (N) may end up with specific variable subtree generation times. At the inter-domain level, the complexity of global CAT tree merging is highly dependent on the network topology. We treat the Internet as an undirected graph G of M nodes and E edges. The diameter of the graph is denoted as δ. Siganos et al. [Sig03] models the Internet neighborhood as an H-dimensional sphere with a diameter δ. H is the dimension of the network topology [Fal99]. For example, H = 1 for a ring topology and H = 2 for a 2dimensional mesh. Any two nodes are within the effective diameter, δef hops away from each other. Faloutsos estimated δef by the following expression:

δ ef = (

M2 1H ) M + 2E

(4.8)

As of Feb. 28, 2002, the dimension of Internet was calculated as H = 5.7 in an average sense. The ceiling of this diameter δef is thus set to 6. Let NN(h) be the number of domains located at distance h from a typical domain in the Internet. Table 2 gives the domain distribution – the probability of an AS domain residing exactly h hops away from a reference domain , and the exact number of domains in that distance range. Table 4.2. Internet Neighborhood Distribution in August 2006 [ISO06] Hop Count, h Domain Count, NN(h) 1 14 2 2,818 3 13,493 4 13,342 5 4,445 6 788 ≥7 102

Domain Distribution, ph 0.04% 8.05% 38.55% 38.12% 12.7% 2.25% 0.29%

Although the actual number of Internet AS domains keeps increasing with respect to time, the Faloutsos reports [Fal99] and [Sig03], indicated that this AS distribution is pretty stable over time. This implies that a packet can reach almost all domains in the Internet by traversing through 6 hops. Therefore, we set the maximum hop count rmax = 6 in Fig.4.6. Let

59

ph be the probability of having AS domain located at distance h from the reference point. The average number of domains used to build a global CAT tree is upper bounded by:

T = ∑ NN (h) × ph
h =1

rmax

(4.9)

Substituting the entries in Table 2 into Eq.(4.9), we obtain the expected domain count T = 14×0.004 + 2818×0.0805 + 13493×0.3855 + 13342×0.3812 + 4445×0.127 + 788×0.0225 + 102×0.0029 = 11,097 domains used in various Internet applications. This domain count posts a loose upper bound on the expected number of ISP domains involved in building the global CAT tree. In reality, only a handful of the ISP-controlled AS domains may commit to defending DDoS attacks, collaboratively. On the conservative side, consider 5% of ISP AS domains are committed to defend DDoS attacks, collectively. Thus the above upper bound could be reduced to only 168 ISP domains, provided that they all conform to the distribution in Table 4.2. In actuality, as long as the partially merged CAT tree profile exceeds the detection threshold θ, the decision process can be ended much earlier. Our DETER experimental results suggest that at most 4 to 8 out of 16 domains will suffice to detect TCP SYN and UDP flooding attacks. Based on these 25% to 50% domain involvement, we find, on the average, that the DCP detection system can scale well to cover T×30.3%×5%×(25% to 50%) = 42 to 84 domains in ISP controlled domains. The actual number of AS domains involved could be even fewer, if the whole defense system is built by collaboration among domains controlled by a single ISP or just by a handful of cooperative ISP companies.

4.5. Experiment Results and Performance Analysis
We verify the performance of the newly proposed DCP detection scheme with DDoS attack experiments on the DETER testbed [Ben06], [DET04] at USC ISI, which

60

consists of more than 200 nodes. The experimental setting and performance results are reported below.

4.5.1.

Introduction to DETER Testbed
The DETER (Cyber Defense Technology Experimental Research) [DET04],

[DET05] test-bed is a computer facility to support experiments in a broad range of cybersecurity research projects, including those experiments that involve "risky" codes. Figure 4.7 is taken from the DETER project web page [DET04], it shows a schematic of the DETER test bed. This diagram omits the detailed configuration of the DETER control plane, since this should not be relevant to most users. The functional paths are shown as dotted lines.

User

Internet
Ethernet Bridge with Firewall

'Gatekeeper'

Control DB

‘User’ Server
User files User Acct & Data logging

'Boss' Server
Web/DB/SNMP, switch mgmt

Node Serial Line Server …

Control Network VLAN
N @100bT Control ports

Power Serial Line Server

PC

PC
N x 4 @1000bT Data ports

PC

160 Power Controller

Programmable Patch Panel (VLAN switch)
DETER Project – Aug 04

Figure 4.7. Schematic of DETER Test-bed [DET04]

The DETER test-bed is designed to provide an experimental environment in which government, academic, and industry cyber-security researchers can safely analyze and measure attacks and develop attack mitigation and confinement strategies. DETER testbed is

61

being developed and operated by the DETER project funded by the National Science Foundation (NSF) and the Department of Homeland Security (DHS). Participating organizations are USC/ISI, UC Berkeley, and McAfee Research. DETER is constructed using the cluster testbed technology developed by the University of Utah and known as "Emulab". A cluster is a set of experimental nodes in a single room, interconnected through a programmable "backplane" or “patch panel”, which can dynamically establish a distinct network topology for each experiment. The DETER test bed includes two clusters, one at USC ISI (ISI) and one at UC Berkeley (UCB). Within each cluster, there are one or more sets of identical nodes. The script for an experiment may ask for allocation of nodes from any single set or from a selection of these sets of nodes. In the DETER test bed, each node is a PC machine with significant disk storage, at least 2MB of memory, and four 10/100/1000bT Ethernet interfaces to the programmable patch panel. Table 4.3 lists the hardware information of the test-bed. Table 4.3 Hardware/Software Information of DETER Test-bed
Category Test Nodes • • • • • • • • • • • • • • • • • Hardware Information 64 PC733 PC nodes: Dual 733MHz Pentium III processors 8 PC2800 PC nodes: Dual 2.8GHz Pentium 4 Xeon processors 30 PC2800 PC nodes: located at UC Berkeley A users and file server Two serial servers for console access One series server for console access at UC Berkeley A DB, web, DNS and operation server Serial server for power controllers Remote power controllers Two power controllers at UC Berkeley One Cisco 6509 high end switch One Foundry FastIron Edge Switch 9604 One Foundry FastIron 1500 Switch at UC Berkeley A Dell P4 2.8GHz FreeBSD running PC as a router Four Ethernet ports on each PC node are connected to the testbed backplane. All 288 ports can be connected in arbitrary ways by setting up VLANs on the switches via remote configuration tools. The fifth Ethernet port on each PC is connected to the Foundry FastIron. Software Information • • • FreeBSD 4.7 RedHat Linux 7.3 RedHat Linux 9

Servers

FreeBSD 4.9-RELEASE

Switches and Routers

N/A

Layout

N/A

62

Under the control of an experimental script, the Emulab control software automatically allocates a set of free nodes and sets up the interconnections to allow a particular experiment to proceed. The control software automatically loads kernels and other software into the nodes and configures the VLAN switch, firewalls, NFS mount points, and other system parameters to isolate it from any other experiments that may be running simultaneously. Control of the PCs is then turned over to the experimenter. To define and set up an experiment on the DETER test bed, a user (i.e., an experimenter) defines a configuration using a scripting language that is derived from the "ns" simulation language. In accordance with this script, the test bed control plane allocates nodes, loads the specified disk images, and starts the experiment.

4.5.2.

Experiment Setup
To evaluate the performance of the CAT-based DDoS detection system, we allow

variations in network topology, background traffic, and attack generation. We adopt the reallife ISP topologies downloaded from the Rocketfuel Project at University of Washington [And06]. We report below the DETER results on up-to-16 collaborative domains. Within each domain, we consider a typical configuration of 7 to 12 routers. Due to the limited nodes in the DETER testbed, we choose the smallest ISP configuration topology from the Rocketfuel dataset. For example, 34 routers were simulated over 4 AS domains. The link bandwidth among the network domains was set at 100 MB/s. To generate the background traffic closer to reality, we use the OC48 trace dataset from the CAIDA project [Mon96] and regenerate Internet traces using the Harpoon traffic generator [Som04]. To generate DDoS attacks, we

63

use the toolkit Stacheldraht V4 [Dit00]. Stacheldraht can generate ICMP and UDP, TCP SYN flooding and Smurf attacks.

4.5.3.

Performance Metrics
The performance of our DCP detection scheme is evaluated with three metrics:

detection rate, false-positive alarms, and system overhead. All metrics are measured under different attacks using TCP, UDP, and ICMP protocols. The detection accuracy is measured using three metrics: the detection rate Rd, false-positive rate Rfp, and the receiver operating characteristic (ROC) curve. The detection rate Rd is defined by: Rd = a / n (4.10)

where a is the number of DDoS attacks detected by our DCP system and n is the total number of attacks generated by the toolkit Stacheldraht during experimentation. Now consider the experiments on regular traffic containing no DDoS attacks. Let p be the total number of alerts raised by the CAT server out of m CAT trees constructed for normal traffic without any attacks during one monitory window. The false-positive rate Rfp is defined by:

Rfp = p / m

(4.11)

The ROC curve shows the tradeoff between the detection rate and false-positive rate. Section 6.4 reports the detection accuracy measured under different detection thresholds. Another critical issue is the time overhead to detect the launch of DDoS attacks. The average detection time τ measures from the start of a DDoS attack to the time to raise the attack alarm. The monitory window should be greater than this detection time.

4.5.4.

Impact of DCP Parameters
To evaluate the effectiveness of the DCP detection scheme, through DETER testbed

experiments we studied the impact of choosing different value of inertia factor α in the range

64

(0.1, 0.5), the router detection threshold β in the range (2, 5), and the monitoring period τ in the rage of (100ms, 1000ms). Below we report the number of alerts raised at routers and analyze the CAT subtree properties. We used 34 routers divided into 4 ASs in the DETER testbed. When the traffic fluctuation exceeds the deviation threshold β, the router raises the alerts. Otherwise, no alert is raised, if no anomaly is detected at router ports. Figure 4.8 compares the total numbers of alerts raised by the routers with SYN flooding compared with the cases of no attacks. More alerts are raised with attacks, compared with the cases of no attacks.

Figure 4.8. Total alerts raised plotted against the router threshold applied on 34 routers in 4 AS domains using a 500 ms monitoring window

The two left bars in Fig.4.8 in each group correspond to heavy-dependence on the past average traffic. Under attacks, the leftmost bars stay around 20 alerts, rather insensitive to increasing threshold β. Without attacks, the second (gray) bars reduce from 12 to 5 alerts as β increases. This implies that β = 3.5 is a good choice to distinguish attacks from no attacks, when α is chosen as low as 0.1. The two right bars (fabric vs. black) are associated with the aggressive choice of a high inertia factor α = 0.3. The fabric bars with attacks are

65

much higher than the black bars without attacks. For α ≥ 0.3 and β ≥ 3.5, the alert bars reduce to zero, meaning attacks and no attacks are no longer distinguishable. Figure 4.9 plots the global CAT tree profile in terms of the number of ATRs involved. On the average, there are 20 router nodes (alerts) in the CAT subtree raised by actual attacks, compared with fewer than 5 nodes in the tree triggered by regular traffic without attacks. These results suggest an optimal router threshold β ≥ 3.5, when the inertia ratio α is chosen as low as 0.1. With 20 routers involved out of 34 routers raised alerts, the router alert rate is 20/34 = 58%.

Figure 4.9. Variations of the global CAT size over 4 AS domains in 500 ms monitoring window

Figure 4.10 presents the influence of monitoring window size on the total number of alerts raised in 4 AS domains. We find the optimal monitoring window size w to be 100 ms in DETER experiments. Figure 4.10 shows that 22 alerts are raised with attacks, compared with only 3 alerts (false alarms) from no attacks. The false positive alarms increase steadily with increasing window size. However, the number of 22 raised alerts from real SYN attacks stays about the same level for all window sizes monitored.

66

Figure 4.10. The router alerts detected with and without DDoS attacks plotted against the monitoring window size

4.5.5.

Detection Accuracy
We study below the detection accuracy of the DCP scheme under TCP SYN, UDP,

and ICMP attacks with different packet rates. The reported results correspond to α = 0.1, β = 2.0, and w = 500 ms. In Stacheldraht [Dit00], the UDP and ICMP packet rate for each individual zombie is adjustable through setting different UDP and ICMP packet sizes. The longer is the packet length, the lower is the packet rate. The TCP SYN attacks use a fixed packet size of 64 bytes with a fixed packet rate. The maximum UDP and ICMP packet sizes are limited to 1024 bytes in Stacheldraht. We observed similar detection rate for TCP SYN and UDP/ICMP attacks with 128-byte packets. Table 4.4 below lists the packet rate of different flooding types we used in our experiments. Table 4.4. Stacheldraht packet size vs. packet rate
128 bytes UDP ICMP TCP SYN 66k packet/second 60k packet/second 512 bytes 21k packet/second 20k packet/second 1024 bytes 12k packet/second 12k packet/second

Fixed 64 bytes packet size, 62k packet/second

67

The accuracy is reflected by having higher detection rate. The False positive alarms should be maintained as low as possible. Tradeoffs exist between these two measures. Figure 4.11 plots the variances of the detection rate (Eq.4.7) with respect to different server detection threshold θ applied. The TCP SYN attack has the highest detection rate close to 100% for θ ≤ 12. The low-rate UDP attacks have a lower detection rate than that of TCP attacks. For UDP attacks that have 512-byte packets, the detection rate can be kept above 80% with θ ≤ 9. As the packet size increases to 1024 bytes, the detection rate drops to zero when θ ≥ 7. These results suggest that in order to maintain high detection rates on TCP and UDP SYN attacks, we need to make θ rather low, such as θ = 5 and maximize the packet size to 1024 bytes.

Figure 4.11. Effects of server threshold on the detection rate of 3 DDoS attack types.

Figure 4.12 plots the false positive alarm rate against the CAT server threshold θ. The CAT incurred by random fluctuation in normal traffic is much smaller. With a server detection threshold θ = 4, the false positive rate drops to less than 1%. However, the real challenge lies in the fact that highly distributed attacks may use low packet rates to escape from being detected [Sou05]. Only after sufficient attack flows are merged, the deviation is

68

detected by the routers. Hence, a lower threshold is mandatory to make the detection accuracy high with very low false positive rate as revealed in Fig.4.12.

Figure 4.12. Effects of threshold on false-positive rate

The ROC curve shown in Fig.4.13 reveals the tradeoffs between the detection rate and false positive rate under different attack types. Our DCP detection scheme achieves a detection rate as high as 99% with less than 1% of false positive rate for high-rate DDoS attacks.

Figure 4.13. ROC curve showing the tradeoff between detection rate and false-positive rate

69

All three curves in Fig.4.13 support this claimed advantage. Even for low-rate UDP attacks, our choice of low CAT threshold θ maintains a detection rate of 91% at a falsepositive rate of 23%. This result proves the effectiveness of the DCP detection system.

4.6. Scalability Analysis and Limitations
The complexity of DDoS attack patterns keeps growing as new vulnerabilities and more sophisticated attack tools appear. To deploy a distributed security scheme in ISP core networks, the scalability is often related to the network size, domain number, data rate, link capacity, or router number involved. This section studies the scalability of the DCP scheme in terms of detection performance and system overhead experienced. Then we discuss flash crowd, security holes, and limitations of the DCP system.

4.6.1.

Domain Scalability Analysis
One advantage of cross-domain DDoS attack detection is its enlarged coverage area.

For a small AS domain, it is rather difficult to distinguish normal traffic fluctuations from malicious flooding traffic. This is due to inadequate alert information collected locally. We have to use the CAT subtrees constructed by upstream domains to assess the earlier impact of the superflow traffic caused by the DDoS attack. Even before the target network is overwhelmed, an early warning could be raised. Through experiments on the DETER testbed, we studied the effectiveness of crossdomain cooperation up to 16 AS domains. Figure 4.14 plots the detection rates of three DDoS attack types against the number of domains involved. The detection rate becomes saturated after sufficient number of AS domains are involved. The results are obtained under

70

the system settings: α = 0.1, β = 2.0, w = 500 ms, and θ = 5. Recall that we assume 8 to 10 routers per domain in the DETER experiments. With a small AS domain containing 8 routers, θ = 5 implies that more than half of the routers are generating alerts as attack transits on the superflow path.

Figure 4.14. Scalability of the distributed change-point detection system over increasing number of AS domains

For 64-byte TCP SYN and UDP attacks, the optimal domain number is 4. For UDP 512-byte packets, the detection rate saturates at 8 domains. For UDP 1024-byte packets, again 4 AS domains would be sufficient. This implies only 25% (4/16) to 50% (8/16) of the participating domains would be sufficient to detect the DDoS attacks. With this proportion, we have assessed in section 5.2 the scalability of the DCP system to cover 42 to 84 ISP-controlled AS domains in fighting the TCP SYN and UDP flooding attacks, collectively. These numbers are manageable in real-life deployment of DCP system, considering the added monitoring burden of the routers and the role of the CAT server employed in each domain.

71

4.6.2.

Other Options and Implementation Limitations
It is a big challenge to discriminate DDoS attacks from fluctuation of legitimate

traffic patterns, called flash events [Car06], [Jun02]. When flash crowd happens, the CAT server creates a similar tree and could raise a false alarm. We suggest adding a few new features to separate the real DDoS attack traffic from the flash crowd. The idea is to check newly appeared source IP addresses. For each superflow, in addition to traffic volume, we need to monitor the distribution of source IP addresses. More new source IP addresses will appear in DDoS attacks than that in a flash crowd [Par01]. Packet content matching offers another potential solution. However, this option is limited by packet payload being encrypted or not allowed to be examined. Compromised insiders are often the most difficult problem to solve in security control. Infected routers may hide suspicious traffic patterns or send false alarms to the CAT server. These false alarms can weaken the use of the CAT tree as a means of attack detection. Our detection scheme is deployed in ISP core networks. We can make it more robust by introducing a topology verification procedure. Knowing the network topology, the CAT server is capable of rectifying the falsely reported traffic patterns according to the upstream and downstream relationship. Single or limited number of Byzantine defectors could be blocked this way. As discussed in Section 4.4, the CAT server in the destination domain needs to merge all received CAT subtrees for the purpose of global detection. The global CAT tree actually provides useful information for traceback or pushback. In the literature, packet marking offers another option to trace the path of attack flows [Alj03], [Ioa02], [Sun04] and [Yaa05]. The victim launches traceback or pushback operations only after DDoS attack is fully detected. In contrast, our DCP system finishes the traceback task as soon as the merged

72

CAT tree becomes sufficiently large. Our system pushes the defense line to upstream domains, where traffic surges are first observed. The analysis on average Internet topology suggests using at most 84 domains to cope with TCP SYN and UDP flooding attacks. These correspond to the saturated detection rate (98%) and low false alarm rate (below 1%). If we lower to 65% detection rate with and higher false alarms (say 15%), the server detection threshold (θ) can be further lowered. This implies that fewer AS domains could make the global decisions. Based on DETER experiments, we feel that it would be sufficient to involve only 28 ISP domains in detecting DDoS flooding attacks.

4.7. Summary
It is critical to detect the DDoS flooding attacks at their early stage before damage can be done to legitimate applications. This chapter discusses an early DDoS detection scheme based on the new CAT mechanism. Our major contributions are summarized in 4 technical impact aspects: 1) Detect changes at attack-transit routers: Based on the anomaly pattern detected in related network domains, our scheme detects a DDoS flooding attack before the victim is overwhelmed. This approach captures the abrupt traffic changes at attack-transit routers. The high detection rate of DDoS attacks was achieved with very low false positive rates. 2) Scalable Performance over Multiple ISP Domains: Our DCP detection scheme is suitable for deployment at the ISP core networks. The providerlevel cooperation can eliminate the need of intervention by edge networks. Our FETER experimental results prove that 4 to 8 domains are sufficient to

73

yield 98% detection rate of TCP SYN and UDP flooding attacks. Based on recent Internet AS domain distributions and the DETER domain coverage, we conclude through an averaging analysis that the DCP scheme scales well to cover up to 84 ISP-controlled network domains in real-life Internet environments. 3) A New SIP Protocol for Trust Negotiation among AS Domains: To support inter-AS collaboration, the SIP protocol is proposed to resolve policy conflicts and regulate an alert message format. Our SIP protocol is part of USC/ISI effort in securing Internet infrastructure against DDoS or worm attacks [Che06a], [Ryu05] that threaten the availability, reliability, and dependability of Internet services. 4) Valuable Design Parameters from Intensive DETER Experiments: We have verified the effectiveness of the DCP scheme through intensive experiments on the DETER testbed. The engineering data on the inertia factor α, router threshold β, global detection threshold θ, and monitory window size w are very useful design parameters for building future DCP prototype or production systems against DDoS attacks in real-life Internet environments.

74

Chapter 5 Identification and Filtering of DDoS Attacks at Flow Level
Fighting against DDoS attacks effectively on the Internet has been a pressing task which involves two critical issues: (1) accurately identifying the machines participating in the forwarding of malicious flows, and (2) incisively cutting the malicious flows at those machines. Our DCP scheme discussed in Chapter 4 is capable of detecting the DDoS flooding attacks and allocating ATRs in domains that work cooperatively. This chapter introduces MAFIC, a novel probing based packet dropping mechanism that can effectively cut off malicious attacking flows and protect legitimate TCP flows with low collateral damage.

5.1. Adaptive Packet Dropping Principle
The MAFIC algorithm handles two major challenges in identifying DDoS attack flows: source IP spoofing and multiple distributed zombie utilization. There are two scenarios at the extreme of the spectrum of IP spoofing. On one hand, all source IP addresses are illegal or unreachable. On the other hand, all the attack packets carry legitimate source IP addresses. Note that “legitimate” means that the source IP address of a packet is a valid address of a certain subnet within a certain AS. It does not mean that the source IP address represents the true IP address of the machine that launches the attack flows.

75

The algorithm handles DDoS attacks lying somewhere in between these two extreme cases, that is, some IP addresses are bogus but some others are “legitimate” in the above sense. For packets with illegal or unreachable source IP addresses, I place them in a data structure called Permanently Drop Table (PDT) directly and drop all such kind of packets. The rationale is that although probably they are not part of the DDoS attack we are fighting against, we believe that they do not belong to any normal application. It could be safe to drop all of such packets without affecting innocent users. Furthermore, if the packets carry legitimate source IP addresses, I use addresses as part of the label of a flow instead of taking count on that to figure out the sender. Then, all packets with the same label will be treated as members of the same flow. Many traffic management algorithms identify misbehaving flows by monitoring and comparing their bandwidths with other flows sharing the link. One problem arises when we apply such an idea in packet classification against DDoS attacks. As multiple zombies are used to launch the attack concurrently, the traffic from each single zombie may behave well by occupying bandwidth shares similar to general TCP-like traffic, or even less. In view of this important observation, a MAFIC algorithm adopts an adaptive packet dropping policy that segregates the malicious flows from others and minimizes the impact on innocent users’ traffic flows. On receiving the notification of DDoS attacks from the victim CAT server, each ATR begins uniform packet dropping proportionally. Afterward, a Suspicious Flow Table (SFT) is established and flows of those dropped packets are recorded. Meanwhile, the ATRs keep watching the variances of arrival rates of these suspicious flows. If the arrival rate of a flow decreases accordingly, it is moved from the SFT to the Nicely-behaved Flow Table (NFT) because it behaves properly in a TCP-friendly manner. Otherwise, the non-responsive flows are added into PDT. An important point is that

76

even though such flows may not be malicious, their non-TCP-friendly behavior would not be helpful for releasing the victim from the flooding of packets.

5.2. MAFIC Algorithm Design
In this section, we describe the detailed mechanisms of the MAFIC algorithm. The pseudo-code of the algorithm is shown below. Although source IP addresses are generally spoofed in attacking packets, they still give us some useful information. Thus, the 5-tuple {Source IP, Destination IP, Source Port Number, Destination Port Number, Protocol}, is used as a label to mark each flow in the table.

77

To minimize the storage overhead incurred by the extra lists added to implement my Adaptive Packet Dropping Algorithm, the system stores only the output of a hash function with the label as the input instead of the label itself. Figure 5.1 shows the protocol control actions of the MAFIC algorithm. One critical issue in the algorithm is the value of the timer used to check if the flow behaves according to the packet drop. Fortunately, RTT information is available in most TCP traffic flows.

Figure 5.1. The protocol control actions of MAFIC algorithm. (NFT: Nice flow table, SFT: suspicious flow table, PDT: permanently drop table)

78

To allow a moderate amount of time for the legitimate sources to respond, we use 4 x RTT as the timer. While a packet is dropped, the current time stamp is added into the SFT along with the hashed label. Once more packets belonging to this flow arrive, the time stamps are compared with the record and the arrival rate is updated. As soon as a flow is found to have lowered its sending rate accordingly before the timer expires, it is moved to NFT and no more dropping is done against its packets. Meanwhile, if the sending rate is not decreased, the flow is moved to PDT and all its future packets are dropped.

5.3. Experimental Results and Performance Analysis
This section reports the experiment results using an NS-2 simulator. The performance of the MAFIC mechanism is evaluated through the effectiveness of malicious flow cutting off and the bilateral damages on legitimate flows. The simulation results show that MAFIC is a promising approach to segregate attacking traffic from legitimate flows.

5.3.1. Simulation Setup and Performance Metrics
The MAFIC algorithm was implemented using the NS-2 simulator, which is a widely recognized a packet level discrete event simulator [Net04]. A subclass of Connector named as LogLogCounter is added to the head of each SimplexLink and a TrafficMonitor is coded into the simulator to compute the traffic matrices. The LogLogCounter class is used to compute the summary of distinct packets traversed through each router. When a packet is forwarded to a particular link by the routing module on each node, the recv method of the LogLogCouter object associated with this link is called. While triggered by the alert from victim node, the LogLogCounter object begins to tentatively drop incoming packets targeting the victim with certain probability, and puts the flow into the SFT.

79

Then it keeps monitoring the packets’ arrival rate for a time period of 4 x RTT. If the incoming rate of the flow decreases accordingly, the LogLogCounter object moves the flow into the NFT and will not drop any packets belonging to this flow in the future; otherwise, it will put the flow into the PDT and all packets of that flow will be considered as malicious attacks and dropped. The TrafficMonitor keeps track of all LogLogCounter objects and for each time period, it is triggered to compute the traffic matrix using the setunion counting algorithm. Notations used throughout result plots are listed in Table 5.1. The default settings of parameters are listed in Table 5.2.

Table 5.1. Definition of Notations

Table 5.2. Default Setting of Parameters

5.3.2. Attacking Packet Dropping Accuracy
The attacking packet-dropping accuracy indicates how accurate the SFT/PDT mechanism identifies the attack packets and drops them. Specifically, I define the accuracy

80

as the percentage of dropped malicious packets among total number of malicious packets that arrive at the ATRs. Figure 5.2 shows the attacking packet dropping accuracy under various traffic conditions.

(a) Under three suspicious packet dropping probabilities: 70%, 80%, and 90%

(b) Under 4 source packet sending rates from 100kbps to 5Mbps

(c) With 30, 50, 70, and 100 flows

(d) For 4 fractions of TCP flows from 35% to 95%

Figure 5.2. Attack packet dropping accuracy of MAFIC algorithm under different traffic conditions.

Figures 5.2 (a) and (b) show the attacking packet dropping accuracy results under different traffic volumes. As can be seen, the MAFIC algorithm is very robust because the accuracy is consistently within the range of 99.2% to 99.8% even under dramatically different traffic conditions. In Figure 5.2 (c), very high accuracy is achieved with scenarios where TCP flows accounted for 5% to 95% of total traffic flows. Even in the “worst” case,

81

accuracy around 99.2% is obtained. Figure 5.2 (d) presents the accuracy with different domain sizes ranging from 40 to 150 routers, and the results show that the accuracy is mostly around 99.8%.

5.3.3. Effects of Flow Cutting
In the design of algorithms to fighting against DDoS attacks, the responsiveness of the defense scheme is one of the most critical considerations. Figure 5.3 shows the results of variations of flow bandwidth before and after the MAFIC algorithm is invoked. As soon as the MAFIC algorithm is triggered, routers begin to drop packets having destination addresses matching the victim’s address. As seen in Fig.5.3 (a), the arrival rate towards the victim is cut to a very low value within a time period of 2 x RTT. By setting the dropping probability to 90%, the flows targeting the victim links are cut off to about 95%. The results also indicate that the arrival rates are cut down to 85% and 80% if we set the dropping probability to 80% and 70%, respectively. In Figure 5.3 (b), 95% of the flows in the total traffic volume are TCP flows. Packet rates decreased drastically as soon as the adaptive dropping algorithm triggered into its probing phase. It is important to note that after the cutting of attacking flows, the legitimate flows regain their bandwidth shares after they passed the test in the probing. Figure 5.3 (c) shows the traffic rate at the 2 x RTT time after the adaptive dropping algorithm has been triggered in scenarios in which a percentage of TCP among total traffic varied from 5% to 95%. The results indicate that the MAFIC algorithm responds quickly as soon as the attack is detected. Figure 5.3 (d) shows the flow bandwidth variations. It is observed that the probing mechanism is indeed effective. Indeed, the higher percentage for TCP flows, the faster the traffics is cut down.

82

(a) Under three packet dropping probabilities

(b) Flow bandwidth variation for 10 to 50 flows

(c) For packet dropping probability of 80% over 10 flows

(d) Flow bandwidth variation for TCP flows from 5% to 95%

(e) For 4 fractions of TCP flows from 35% to 95%

Figure 5.3. Traffic reduction rates and flow bandwidth variations of MAFIC algorithm under different traffic conditions.

83

Similar to the results in Figure 5.3 (b), legitimate TCP flows quickly gain back their bandwidth shares after the probing phase and non-responsive flows are cut off completely. Figure 5.3 (e) shows the traffic reduction rates in different sized domains with router numbers from 40 to 150. The results indicate that MAFIC algorithm responds quickly in a highly scalable manner. With different percentages of TCP flows among total traffic, the adaptive dropping algorithm cuts off more than 90% of the traffic in 2 x RTT time after MAFIC is triggered into its probing phase.

5.3.4. False Alarm Rates
False positive rates (θp) and false negative rates (θn) are important parameters to characterize the performance of detection algorithms against network attacks. A False positive rate is defined as the percentage of legitimate packets wrongly dropped as malicious attacking packets out of the total traffic packets. A False negative rate is the percentage of attacking packets that were not dropped or hidden in the traffic to hit the victim node across the defense line without being detected. While the θp indicates the sensitivity and accuracy of the detector, it also evaluates the impact on well-behaved applications. The θn reflects the effectiveness of the algorithm against malicious attacks. There is always a tradeoff between the intrusion detection rate and the false alarm rate. The simulation results on false alarms are plotted in Fig.5.4. The false positives are shown in Figs. 5.4 (a, c, e) and the false negatives plotted in Figs. 5.4 (b, d, f). The θp rates are very low – upper-bounded by 0.06% for all three cases under different traffic conditions. In general, the θp increases with the total traffic volume and percentage of TCP flows. But the θp may cease to increase or even drop when the dropping probability (Pd) becomes very high, such as Pd = 0.9 in Fig.5.4 (a). Similarly, the θn may drop for high TCP or high total traffic volumes in Fig.5.4 (b).

84

(a) θp for three packet dropping probabilities: 70%, 80%, and 90%

(b) θn for three packet dropping probabilities: 70%, 80%, and 90%

(c) θp for 30, 50, 70, and 100 flows

(d) θn for 30, 50, 70, and 100 flows

(e) θp for 4 TCP flow rates from 35% to 95%

(f) θn for 4 TCP flow rates from 35% to 95%

Figure 5.4. False positive and negative rates of MAFIC algorithm under different traffic conditions.

In general, the θn reduces with increasing traffic volume. But θn may increase again when the traffic exceeds a certain limit as seen in Fig.5.4 (b). The θn is higher than the θp but

85

still within 5% in the worst case, and around 1% in a majority of the cases. Both false alarm rates increase slowly but fluctuate with the number of domains as seen in Fig.5.4 (c, f).

5.3.5. Legitimate Packet Dropping Rate
The legitimate-packet dropping rate (Lr) is defined as the amount of packets in wellbehaved flows dropped during the dropping process and during the probing phase. Lr indicates how much legitimate users would “pay” for protection against DDoS attacks. Figure 5.5 illustrates the variance of Lr under different traffic conditions.

(a) Lr rates for 3 packet dropping probabilities

(b) Lr rates for 30 to 100 flows

(c) Lr rates for 4 of TCP flows from 35% to 95%

Figure 5.5. Legitimate-packet dropping rates of MAFIC algorithm under different traffic conditions.

86

Legitimate packet dropping rate is considered as an important issue since it determines the degree of adverse effects that a general user would suffer. Figure 5.5 (a) shows the results of Lr during the probing phase corresponding to different packet dropping probabilities. Even with very high dropping probabilities (70%, 80%, 90%), the costs of legitimate flows are trivial. Furthermore, as the total traffic volume grows, the Lr tends to be stable and converged to the value of about 1%. This result clearly represents a negligible influence to most applications. Figure 5.5 (b) shows that the higher dropping rate paid for identification is not a result of more dropping. Rather, there are fewer legitimate packets in total traffic. In an extreme scenario, only a very small number of packets might be sent out when a single TCP flow is facing the competition of a large number of malicious flows. Even with only less than 10 packets dropped during the probing phase, the cost becomes pretty high. Figure 5.5 (c) indicates that with a different number of routers in an AS, the Lr fluctuates from well-behaved flows during probing. In most cases, in simulations, the rate is below 3%, which is certainly acceptable in most practical applications.

5.4. Summary
This chapter presents a novel MAFIC scheme for malicious flow identification and cutoff by implementing a new adaptive packet dropping and probing algorithm. By monitoring the response to packet loss from the flow source, malicious attacking flows are accurately identified and all their packets are then dropped before reaching the victim. Extensive NS-2 based simulation results show that MAFIC responds quickly to reduce the traffic rate by limiting flow bandwidth incisively. Indeed, MAFIC can identify and cut off

87

malicious flows with very high accuracy and a minimized impact on the performance of legitimate application flows. Furthermore, MAFIC has a very low storage demand. Most of its overhead results from the implementation of tables added to monitor the packet dropping policies. Each item of the two tables, NFT and PDT, requires only 1 bit to indicate if one packet belongs to a “nicely-behaved flow” or a “malicious flow”. For each incoming packet, its packet ID {Source IP, Port #, Destination IP, Destination Port #, Protocol} is used as the input to a hash function, of which the output is an index indicating one position in the tables. If the corresponding bit in the table equals 1, then this packet belongs to the hit table. Thus, the sizes of the NFT and PDT are very small. Instead of treating a packet as legitimate one when it not in PDT, the NFT and PDT are kept to make sure all incoming packets are under control. The SFT is larger than NFT and PDT because it needs to monitor the variation of traffic rate of flows once their packets begin to be dropped. Consequently, each item of the SFT has two members: one is a single bit indicator to tell if the flow is in SFT, while another is a corresponding counter remembering the previous traffic rate during the probing phase.

88

Chapter 6 Collaborative Detection of Shrew DDoS Attacks using Spectral Analysis
Shrew DDoS attacks are very different from the flooding type of attacks. They are stealthy, periodic, pulsing, and low-rate in attack traffic volume. These types of attacks may reduce the quality of services unnoticeably. This chapter presents the detection phase of our collaborative detection and filtering (CDF) scheme against the shrew DDoS attacks. The filtering phase will be discussed in chapter 7.

6.1. Introduction
Shrew attacks exploit the deficiencies in the RTO (Retransmission Time-Out) mechanism of TCP flows. It throttles legitimate TCP flows by periodically sending burst pulses with high peak rates in a low frequency. As such, TCP flows see congestion on the attacked link when they recover from RTO. Indeed, shrew attacks may reduce the throughput of TCP applications down to almost zero [Kuz03]. Given that more than 80% of traffic on the Internet today is using the TCP protocol, the majority of existing applications are at stake. The low-rate shrew DDoS attacks have a high peak rate, but a low average rate and exhibit a stealthy nature. Shrew attacks can damage the victim for a long time without being detected [Gui05]. Being masked by background traffic, countermeasures developed for

89

flooding DDoS attacks are not effective to combat against shrew attacks [Gui05], [Kuz03], [Mah01]. Shrew attacks are very difficult to detect within the time domain, but the situation is not necessarily true within the frequency domain. This chapter and chapter 7 present a new collaborative detection and filtering (CDF) scheme to detect and filter shrew DDoS attacks by combining DFT (discrete Fourier transform) and hypothesis test framework. Figure 6.1 illustrates the CDF architecture and process stages. I consider routers belonging to the same autonomous system (AS) and collaborating with each other to defend against shrew attacks. The CDF scheme is built with a training process and a testing process in a cascade as illustrated in Fig.6.1 (b).

(a) The CDF implementation network environment

(b) Traffic processing stages for CDF scheme Figure 6.1. The collaborative detection and filtering (CDF) architecture for defense against shrew DDoS attacks over multiple routers in the same autonomous system

90

The training process consists of a template generator and a pivoting frequency estimator (Algorithm 6.1). I have collected 8,000 sample traffic streams, half of which are legitimate without attacks (So) and the other half with shrew attacks (Sa). The template generator generates attack template threshold parameters (α, β, γ) and a Gaussian template distribution over 4,000 streams in the attack set Sa. Template distribution is characterized by template average distribution denoted as

µ(f) in Table 6.1. The template generation process will be detailed in Section 6.3. Template
spectrum of streams in sample sets Sa and So is characterized by two Gaussian distributions Na (µa, σa2) and No (µo, σo2), where the subscripts a, and o correspond to training streams with and without shrew DDoS attacks. Similarly, Gaussian distributions Nfa (µfa, σfa2), and Nfo(µfo, σfo2) are sampling over two training sets at the flow level. The testing phase is built with three algorithms for the purpose of determining pivoting frequency, detecting malicious streams, and filtering attack flows amid legitimate flows. In testing experiments, 4,000 incoming traffic streams X(i), were tested to validate the effectiveness of the CDF scheme. In a way, the complete scheme is based on template matching. These traffic patterns are statistically generated to cover a mixture of normal TCP and UDP flows with shrew attack streams. To detect a shrew attack stream that is embedded in an incoming traffic stream X(i), the energy spectrum Φ(f) is generated by the DFT engine. The energy Φ(p) at the pivotal frequency, where the gap between Φ(f) and µ(f) is the maximum, is computed by the pivoting module (Algorithm 6.1). The mean value of the traffic spectrum Φ(f) is compared with the template average µ(f) in the detection module (Algorithm 6.2). The template distributions Na(µa, σa2) and No(µo, σo2) are used for anomaly detection. After an attack stream is detected, attacking alerts will be sent to the filtering module (to be

91

discussed in Chapter 7), which segregates the shrew attack flows from normal TCP flows. The filtering process uses an amplitude spectrum Ψ(f) to separate two flow-level distributions (Nfa(µfa, σfa2) and Nfo(µfo, σfo2)). Notations, symbols, and abbreviations used in this paper are summarized in Table 6.1. Only brief definitions are given here, details are given in subsequent sections.

Table 6.1 Notations and Abbreviations used in Chapter 6 and 7.
Notations T R L Rd Rfp α β γ µ (f) Φ (f) Ψ (f) p y z Brief Definition Attack period (sec) Attack burst rate (K Pkts/sec) Attack burst width (sec) Anomaly detection rate False-positive alarm rate Local detection threshold Global detection threshold Packet filtering threshold Template average distribution Cumulative traffic spectrum (CTS) Cumulative amplitude spectrum (CAS) Attack pivot frequency CTS spectral pivot point CAS spectral pivot point Notations CDF RoQ DDoS DSP CTS SFT MFT PSD ASD Na No Nfa Nfo θ Definition Collaborative Detection and Filtering Reduction of Quality attacks Distributed Denial of Service attacks Digital Signal Processing Cumulative Traffic spectrum Suspicious flow table Malicious flow table Power spectrum density Amplitude spectrum density Sample distribution of attack traffic streams Sample distribution of legitimate traffic streams Sample traffic flow distribution of shrew attacks Sample distribution of legitimate TCP flows Normalized TCP throughput

6.2. Shrew Attack Characteristics in Frequency Domain
6.2.1. Shrew DDoS Attack Properties
Shrew attacks exploit the deficiencies in the RTO (Retransmission Time-Out) mechanism of TCP protocol. It throttles legitimate TCP flows by periodically sending burst pulses with high peak rates in a low frequency. As such, the TCP flows see congestion on the attacked link every time they recover from RTO. Indeed, shrew attacks may reduce the throughput of TCP applications down to almost zero [Kuz03]. Given that more than 80% of traffics on the Internet today are using TCP protocol, a majority of existing applications and

92

commercial services are at stake. It is difficult to detect periodic pulses using traffic volume analysis method within the time domain. This is because the average bandwidth consumption differs very little between attack–free and attacked streams. For higher throughput, the TCP protocol adopts a predefined value of RTO with a fixed incrementing pattern [Pax00]. By calculating the autocorrelation sequence of a set of sampled time series and converting them into frequency-domain spectrum using DFT, I find that the power spectrum density (PSD) of a traffic stream containing shrew attack streams has much higher energy in low-frequency band than that which appears in the spectrum for legitimate TCP/UDP traffic streams. Thanks to the mature digital signal analysis technology in hardware implementation, this scheme can be implemented by network processor or reconfigurable hardware [Att05]. DSP hardware pushes spectral analysis down to the lower layer of packetprocessing hierarchy. If the packets are processed by hardware and malicious flows are filtered out in a timely manner, the router workload will not increase much at the presence of shrew attacks. A shrew attack stream is modeled by three major parameters including period of attack T, width of burst L, and the burst rate R [Kuz03], [Luo05]. Figure 6.2 compares the time series of legitimate traffic streams (a), periodic pulsing shrew attack stream (b), and the mixture of legitimate and attack streams (c). Figure 6.2(b) presents a shrew attack stream modeled by T, L, and R. When a legitimate TCP stream and a shrew attack stream are both heading for the same destination, we observe: (1) the shrew attack peak rate remains constant while the TCP flow may increase differently; (2) the shrew stream arrives at the destination periodically, while the TCP flow arrives continuously.

93

(a) A sample traffic stream consisting of six legitimate TCP and UDP flows without any attack packet

(b) A shrew DDoS flow characterised by high burst rate (R), long attack period (T), and short burst width (L).

(c) Six normal TCP/UDP fows in Part (a) mingled with a single shrew DDoS attack stream from Part (b). Figure 6.2. Three traffic streams under three scenarios -- The shrew DDoS attack stream in Part (b) hides in six legitimate traffic flows in Part (a) to form the traffic stream in Part (c)

The period T is the time interval between two consecutive attack pulses. The burst width L indicates the time period during which attackers send packets in high rate. The burst height exhibits the peak rate by which attacking flow is sent. The period T is calculated by the estimated TCP RTO timer implementation from trusted sources. During the burst with a

94

peak rate R, the shrew pulses create a burst and severe congestion on the links to the victim. Legitimate TCP flows are forced to decrease their sending rate as governed by congestion control mechanism, accordingly. Figure 6.2 (a) and 6.2 (c) compare the sampled time series of packet arrivals of two scenarios: Six TCP flows without shrew attack streams embedded (Fig. 6.2 (a)), and the same six TCP flows with one shrew attack streams (Fig.6.2 (b)), which use the attack period T = 1 second, burst width L = 70 ms, and the burst rate R = 120 K packets/sec as shown in Fig.6.2 (b).

6.2.2.

Traffic Spectrum and Template Distribution
I take the number of packet arrivals at the router as a discrete signal series and

sample it with a period of 1 ms. Then the highest frequency is of 500 Hz. The sampling process effectively plays the role of a low pass filter that gets rid of high frequency noises. Another observation is that the sampled series also includes packets from legitimate flows. These packets are not necessarily all targeting at the same victim. The packet arrivals in each training stream or in each incoming traffic stream are modeled by a random process: {x(t), t = n ∆, n ∈ N}, where ∆ is a constant time interval, which I assume 1 ms. N is a set of positive integers, and at each time point t, x(t) is a random variable, representing the total number of packets arrived at a router in (t-∆, t]. This random process was referred to as the packet process [Che02]. Assume a wide sense stationary random process, and let’s define the autocorrelation function of the random signal x(t) in discrete time as follows:

R xx ( m ) =

1 N − m +1 ∑ [ x ( n ) x ( n + m )] N − m n=0

(6.1)

95

Rxx(m) captures the correlation of the packet process and itself at interval m. If there exist any periodicity, autocorrelation function is capable of enforcing it. The next step is to figure out the periodicity embedded inside the autocorrelation functions. I convert the autocorrelation time series using discrete Fourier transform to generate the power spectrum density (PSD) as follows:
PSD ( f ) = DFT ( R xx ( m ), f ) = 1 N

∑R
n=0

N −1

xx

( m ) × e − j 2πfn / N

, f=0,1,2,…,N-1

(6.2)

A shrew attack stream escapes being detected by occupying only a small share of link bandwidth, however, its properties in frequency domain cannot be hidden. After performing DFT on the autocorrelation sequence as Eq. (6.2), the PSD captures the periodical pattern of shrew attack stream in the frequency domain. Figure 6.3 compares the power spectrum density for two traffic stream patterns corresponding to with and without embedded shrew attacks. It is clear that the embedded shrew attack stream pushes the solid-line PSD curve towards the lower frequency band, while the no-attack stream has a wider frequency range of the power spectrum density in the dash-line curve.

Figure 6.3. Comparison of normalized traffic density (PSD) of two traffic streams with and without shrew attacks

96

After integrating the PSD function over a given frequency range, the resulting energy spectrum is used to determine the ratio of energy cumulated to a given frequency point. This corresponds to the size of area below the PSD curve. This cumulative traffic spectrum (CTS) Φ(f) is obtained below: Φ ( f ) = ∑ PSD (i )
i =1 f max i =1

∑ PSD (i )

(6.3)

As plotted in Fig. 6.4, the y-axis is the CTS normalized with respect to the total energy in the whole spectrum [0, 500] Hz. For a typical traffic stream containing shrew attack flows, more than 90% of the energy is distributed below 20 Hz. In contrast, for normal traffic streams without attacks, only 60% the energy is located below 20 Hz. This implies that the energy spectrum offers a sharp distinction by which to distinguish whether a sampled traffic spectrum contains shrew attacks or not.

Figure 6.4. Comparison of the cumulative energy spectrum of two traffic streams with and without shrew attacks

Through intensive NS-2 simulation experiments, I obtained 4,000 template CTS spectra over the attack dataset Sa. Based on the central limit theorem [All04], I assume the

97

template spectrum conforms to a Gaussian distribution N (µ, σ), where µ and σ are the mean and the standard deviation.

⎧µ ( f ) = ⎪ ⎪ ⎨ ⎪σ ( f ) = ⎪ ⎩



n i =1

Φi( f )/n
n i

1 n

∑ (Φ
i =1

( f ) − µ ( f ))

2

,

(6.4)

where n =4,000 is the size of sample space of Sa, and Φi(f) is the CTS of the i-th sample stream. Figure 6.5 plots the template energy distribution of the mean value µ(f) over the lowfrequency range up to 20 Hz. The template spectrum curve sits between the two traffic spectrum curves in Fig.6.4. This property is used to distinguish traffic streams containing a shrew attack stream from normal traffic streams by checking the spectrum gaps with the template average distribution µ(f).

Figure 6.5. Average attack template distribution over a low frequency band for all attack streams in training set Sa

Table 6.2 presents the attack template energy distribution on a frequency band lower than 20 Hz. At each frequency f, the mean µ(f) and standard deviation σ(f) are listed. These

98

table entries will be used to perform the CDF processes as template references in Algorithm 6.2. The spectral analysis discussed above can be applied over both training traffic and incoming traffic streams.

Table 6.2. Gaussian Distribution of Attack Template
Freq. f (Hz) Mean µ(f) St. Dev. σ(f) 1 0.15 0.11 3 0.30 0.13 5 0.45 0.14 7 0.58 0.14 9 0.73 0.14 10 0.75 0.14 11 0.77 0.13 13 0.79 0.13 15 0.81 0.13 17 0.82 0.10 19 0.83 0.09 20 0.84 0.08

6.3. Collaborative Anomaly Detection
I developed a scheme for collaborative anomaly detection using hypothesis test atop the spectral introduced in Section 6.2. Supported by alerts exchanging among multiple routers, this scheme detects shrew attack streams hidden among legitimate TCP/UDP flows. I start with the algorithm that determines attack pivot frequency, and then I specify the algorithms developed to perform the collaborative detection processes.

6.3.1.

Pivot Frequency in Traffic Streams
Having established the attack template database, we need to answer a basic question:

Which frequency point results in the highest detection accuracy? This point is called the pivot frequency point, which varies to different incoming traffic streams. We must first obtain the pivot frequency p in order to detect ongoing attacks accurately. Algorithm 6.1 determines the pivot frequency p. A spectral pivot point y = Φ(p) is associated with each traffic stream characterized by its CTS spectrum Φ(f). After sampling a time series of incoming stream, its CTS Φ(f) is generated through DFT. Then the gap d(f) =

µ(f) – Φ(f) is calculated using Table 2 entries over all frequencies in a spectral window up to

99

20 Hz. We obtain the pivot frequency p that must satisfy the following at the maximum gap point: d(p) = Max{d (f) = µ (f) – Φ (f) | for all f ≤ 20 Hz} Pseudo code specification of Algorithm 6.1 is given below.
Algorithm 6.1: Determination of Pivot Frequency in a Traffic Stream µ (f): Average template CTS spectrum. Input: Φi (f): The CTS computed from an incoming traffic stream Si. Output: : p: Pivot frequency for the traffic stream Si. y = Φi (p) : Spectral pivot at pivot frequency p Procedure: 01: Initialize the frequency window (0, 20 Hz) 02: while scan through the detection window 03: Calculate gaps at each frequency point d(f)=µ(f)–Φi(f) 04: endwhile 05: Find p such that d (p) = Max{d (f) | 0 ≤ f ≤ 20 Hz} and compute y = Φi (p) 06: return pivot frequency p and spectral pivot point y = Φi(p)

(6.5)

The spectral pivot point y = Φ(p) will be used in the shrew attack detection process. Figure 6.6 illustrates how to detect the pivot frequency using the traffic samples shown in Fig. 6.2(a) and 6.2(c). The spectrum of the shrew attack stream is indicated by the top CTS curve. The CTS curve of the attack-free stream lies below the template average spectrum curve at the middle.

Figure 6.6. Determination of the pivot frequency p and the two spectral pivot points yo for the attack-free stream in Fig. 6.2(a) and ya for the attack stream in Fig. 6.2(c).

100

For the stream containing shrew attack flows, the maximum gap between its CTS curve and the template CTS curve is located at the pivot frequency p = 6 Hz. The spectral pivot is thus found at a spectral pivot point denoted as ya = Φ (p) = Φ (6 Hz) = 0.7. Similarly, for the attack-free stream, the pivot frequency p = 8 Hz and yo = Φ (8 Hz) = 0.19.

6.3.2.

Hypothesis Test
Let’s consider two hypothetic events: Ho for an attack-free stream and H1 for a

traffic stream with shrew attacks. Using Algorithm 6.1, I obtain the template distribution Φ (p) by training 8,000 training traffic streams. According to the central limiting theorem [All04], assume two Gaussian distributions Φ(po): No(µo, σo2) = N(0.33, 0.272) and Φ(pa): Na (µa, σa2) = N(0.78, 0.162) for 4,000 attack-free and 4,000 streams containing shrew attacks, respectively. These two Gaussian distributions No and Na are plotted in Fig. 6.7. The solidline plotted on the right corresponds to distribution Na for attack streams. The dash-line plotted on the left plots distribution No, as resulting from attack-free training streams. In Fig.6.7, the detection rate of a shrew attack stream (event H1) is under the Na curve to the right of yo. The false detection alarm rate of an attack-free traffic stream (event Ho) is under the No curve to the left of yo. I need to choose a local detection threshold α to maximize the anomaly detection rate Rd and to minimize the false positive rate Rfp defined by the following two probability functions:
∞ Rd = Prob[H1|H1] = ∫y

o

⎧ ( y − µa )2 ⎫ exp ⎨− ⎬dy 2 2σ a ⎭ 2π σ a ⎩ 1
⎧ ( y − µo ) 2 ⎫ exp ⎨− ⎬dy 2 2σ o ⎭ 2π σ o ⎩ 1

(6.6a)

Rfp = Prob[H1|Ho] = ∫ ∞

yo

(6.6b)

101

Essentially, Rd is the successful detection probability that a true alarm is raised, when there is actually a shrew attack. The Rfp is the probability of raising a false alarm due to misdetections of an attack-free traffic stream.

Figure 6.7. Template distribution of attack/no-attack streams at the attack pivot frequency.

In order to tell whether there are any shrew attack streams embedded in a legitimate flow, we set up our hypothesis test rule. Defined below is a likelihood ratio L(y) of the pivot point y by the ratio of the two probability density functions, pa(y) and po(y), of the event H1 and event Ho, respectively,
L( y ) = pa ( y ) σ o y − µa 2 ⎤ 1 ⎡ y − µo 2 ) −( ) ⎥) = exp( ⎢( po ( y ) σ a σa 2 ⎣ σo ⎦

(6.7)

where pa (y) is the probability density of y in the Gaussian distribution Na, and po (y) is the probability density of y in the Gaussian distribution No. They are defined as:
⎧ ( y − µa )2 ⎫ exp⎨− ⎬ 2 2σ a ⎭ 2π σ a ⎩ 1 ⎧ ( y − µo ) 2 ⎫ exp⎨− ⎬ 2 2σ o ⎭ 2π σ o ⎩ 1

pa (y) = po (y) =

(6.8a) (6.8b)

102

Variation of the likelihood ratio L(y) at the spectral pivot point is plotted in Fig. 6.8. The larger is the L(y), the pivot point y is more likely to conform to the Na distribution. This implies that the stream is more likely to contain some shrew attack flows.

Figure 6.8. Variation of the likelihood function with respect to the normalized spectral pivot value

The local detection threshold α is selected to equal certain L(y) corresponding to a well chosen pivotal point y. In another word, given desired detection rate Rd*, the local detection threshold α is chosen as:
α = L(y) for a pivot point y such that Rd ≥ Rd*. (6.9)

As shown in Fig.6.7, there is an overlapped area under the two Gaussian distributions. To the right side of α, we have the Rfp in the overlapped area. To the left side of α, we have the false-negative area corresponding to the misdetection of a real attack as no attack. This implies that when L(y) > α, the hypothetic event H1 is true. Otherwise, the hypothetic event H0 is true. Based on the template distributions obtained from 8,000 training sample streams, I calculated Rd and Rfp using Eqs. (6.6a) and (6.6b) as plotted in Fig.6.9.

103

(a). ROC curve of Rd vs. Rfp

(b). Effects of variation in local threshold α Figure 6.9. Plots of the anomaly detection rate Rd and false positive rate Rfp averaged over 8,000 sample traffic streams in the template database.

Figure 6.9(a) plots the ROC (receiver operating characteristic) curve showing the tradeoff between Rd, and Rfp. Figure 6.9(b) plots the variation of Rd, and Rfp as α increase in the range from 0 to 12 of y. For example, to achieve a successful detection rate of 95% with α=0.5, we need to tolerate a false positive rate of 30%.

104

It is clear that Rd decreases slowly while Rfp decreases rapidly with increasing value of α. Consequently, we need a better mechanism that is able to keep a sufficiently high detection rate while maintaining a small false-positive rate. This requirement motivated me to develop the collaborative detection scheme.

6.3.3.

Collaborative Detection Algorithm
With the hypothesis testing, Algorithm 6.2 is developed. It is a distributed detection

scheme of shrew DDoS attacks using multiple collaborative routers. This detection measurement is deployed in upstream routers that are a few hops away from the victim server, because low-rate attacks may throttle legitimate TCP flows destined to the same victim. However, before reaching the target, the shrew attack streams occupy only a small share of bandwidth even at its peak rate. This property makes it difficult to detect correctly. The traffic statistics collected at neighboring routers are helpful for a router to verify its detection result. Previously, to reduce false positive alarms, we have to tolerate a higher false negative rate by choosing a larger local detection threshold α. Algorithm 6.2 tries to make up this deficiency by selecting a global cooperative threshold β. The global threshold β is lower than α in order to reach a higher detection rate. When the likelihood ratio function L(y) is higher than the local threshold α, the router starts the filtering mechanism and multicasts alerts to its neighbors. Routers whose likelihood ratio L(y) is smaller than α do not generate alerts. However, if their likelihood ratio L(y) values are larger than β, they decide whether to trigger the filtering mechanism after analyzing the resources of received alerts. If L(y) is lower than β, there is nothing suspicious. With distributed shrew attacks, alerts from immediate routers are connected to the receiver. Below is the pseudo code of Algorithm 6.2.

105

Algorithm 6.2: Collaborative Anomaly Detection Inputs: yi : The spectral pivot Φi(p) for an input stream Si α : Local detection threshold, β : Global detection threshold Na : Sample traffic distribution with shrew attacks No : Sample traffic distribution without shrew attacks Output: Traffic stream Si contains either shrew attacks or not Procedure: 01: Compute L(yi) using Eq.(6). 02: Case 1: L(yi) > α 03: The stream Si contains shrew attacks 04: Send out alert to collaborative routers 05: Call packet filtering routine 06: Case 2: β < L(yi) < α 07: Check the alerts from cooperative routers 08: if alerts come from cooperative routers, then 09: Call packet filtering routine 10: endif 11: Case 3: L(yi) < β 12: The stream Si contains no shrew attacks

Let’s consider the scenario in Fig. 6.10(a). Each dot stands for a router in an AS. The black dots are routers that have detected shrew attack streams embedded in legitimate flows (L(y) > α). They send alerts to all cooperative neighbors. The influence of different cooperative ranges among multiple routers will be studied later through intensive experiments. To simplify the discussions, in Fig.6.10 we assume that each alert is sent to neighbors in two-hop distance. The white dots are routers whose likelihood ratio L(y) is lower than the local threshold α, so they do not generate alerts. In addition, each node is the root of a detection tree that contains all of its neighbors in two-hop distance. The A, B and E is root nodes shown in Fig. 6.10(b). These trees keep the multicast group records. Each root knows to whom its alert is being sent. Distributed attacks are launched from zombies located widely and multiple shrew attack streams simultaneously approach the victim(s) located in the domain. Once a router detects likelihood ratio L(y) > α (black dots in Fig. 6.10), there are shrew DDoS attack streams

106

detected. It would multicast an alert along its detection tree and launch countermeasures to identify malicious flows and cut them off timely.

(a) Distributed shrew attacks from two sides of the AS

(b) Three detection trees Figure 6.10. Collaborative detection scheme and use of detection trees.

However, shrew attack streams do not appear evenly on all edge routers. Algorithm 2 gives routers a clue to check whether they are in the attacking range. For example, when L(y) < α at node A, alerts from neighbors warn that an attack is going on. In addition, the decision tree let node A has a vision of where these alerts come from. Alerts make node A realize that it is located at the center of attacking area. If L(y) > β, node A will launch countermeasures against the attacks. In contrast, node B will not take any further action although it received two alerts. Neither did any of its immediate neighbors raise any alert, which leads to the conclusion that there are suspicious flows entering the AS, but node B is not in the attacking range. However, decision trees and received alerts will tell

107

nodes C, D and E that they are at the attacking area. If their local likelihood ratio L(y) > β, they need to start flow filtering algorithm accordingly.

6.4. Experiment Results and Performance Analysis
I verified effectiveness and evaluated the performance of the spectral analysis based on detection algorithms through intensive NS-2 simulation experiments.

6.4.1.

Experiment Setup
I have studied the shrew attack characteristics through intensive simulation using the

NS-2 simulator [McC97], a widely recognized packet-level discrete event simulator. Figure 6.1(a) shows the typical network environment to deploy in which the CDF scheme is implemented. NS-2 simulations were carried out with multiple topologies generated by the GT-ITM toolkit developed by Georgia Tech. [GTI05]. I applied each topology for at least 1,000 experiments with shrew attack datasets similar to those used by [Che06c], [Kuz03], and [Sun04]. In particular, I generated shrew DDoS attack flows with a period T between 0.5s and 3.0s, the burst period L is in the range (30 – 90 ms). For single-source attacks, the burse rate R varies in 0.5 - 2 MB/s. In cases of distributed attacks from multiple sources, R varies in 0.1 - 2 MB/s. The background traffic without shrew attacks are generated according to statistical data generated by analyzing the Abilene-I trace dataset. This dataset is the first public OC48c backbone trace and it is released by the PMA Project [Abi05]. As illustrated by Fig. 6.1(a), I consider routers belonging to the same AS shown by the Internet subnet at the center.

108

The simulation assumed default network parameters in link capacity of 2 Mb/s. The RTT of TCP flows are uniformly distributed over 60 ms to 240 ms. The shrew DDoS attack dataset specified in Section 6.2 are applied here. While TCP-Tahoe, TCP-Reno and others present similar vulnerability under shrew attacks [Kuz03], I adopted the TCP-Reno standards in the experiments. I also examined the overhead in the CDF algorithms to assess the penalties and limitations of the scheme.

6.4.2.

Detection Accuracy
I evaluate the detection accuracy using two detection rates: anomaly detection rate

Rd and false alarm rate Rfp. The term anomaly is used to refer to an abnormal network condition caused by shrew attacks. The actual anomaly detection rate Rd is calculated as the ratio of detected attack streams over the total number of shrew attack streams embedded in normal traffic streams. The false-positive rate Rfp is the ratio of normal traffic flows being wrongly marked as having shrew attacks over the total number of legitimate traffic streams. Besides considering the two performance metrics, I also study the performance of the collaborative detection scheme (Algorithm 6.2) over several collaborative ranges. A single router which works independently is considered to have no collaboration with its neighbors. Collaborating with 1-hop routers involves 2 to 4 routers as immediate neighbors. 2-hop neighbors involve 4 to 16 routers within distance 2 from a given router. Finally, I set a limit to 8 to 40 routers in a 3-hop neighborhood. The ROC curves shown in Fig.6.11 report the performance of Algorithm 2, which is upper-bounded by the template ROC performance reported in Fig. 6.9(a). Three curves are plotted for using 1 router independently and up to 4 and 40 routers, respectively in 1-hop and 3-hop neighborhoods. The lower curve shows poor detection performance when using single

109

isolated routers. The detection results of using neighboring routers are shown in the top two curves. The neighborhood range has resulted in very little differences. When the false alarm is required to be very low, say below 0.05%, the 3-hop group performs slightly better than the 1-hop group. ROC plots clearly shows that a detection rate of 98% is achieved, if one can tolerate a false alarm rate of 30%. When the false-positive rate exceeds 20%, the Rd difference in using large collaborative routers diminishes. The ROC curve reveals that cooperation among routers effectively improves the performance. On the other hand, the increase of benefits from larger collaborations with more routers is trivial.

Figure 6.11. ROC curve showing the tradeoffs between anomaly detection rate and false positive rate under collaborative detection of shrew attacks, compared with the result of using an isolated router.

However, enlarging the collaborative range also triggers more alert messages to be propagated among the routers involved. The message being conveyed here is that using 2 to 4 routers within a 1-hop distance will serve the purpose, sufficiently, based on checking 4,000 traffic streams in the experiments.

110

6.4.3.

Effects of Local Detection Threshold α
Figure 6.12 presents variations of an average detection rate Rd and false positive rate

Rfp with different values of the local threshold α. The α magnitude is related to the selection of the CTS pivot point y = Φ(p). I compared the performance of independent detection by a single router with collaborative detection using multiple routers. With collaborative ranges in 1, 2 and 3 hops, I find that more routers can results in higher detection rates. For example at α = 4, the average Rd = 0.75 and 0.82, respectively, in using 4 and 40 routers.

(a) Effect of α variation on average detection rate

(b) Effect of α variation on false positive rate Figure 6.12. Shrew attack detection results from testing 4,000 traffic streams over 2 to 40 routers under the independent and two collaborative modes

111

As the value of α increases, the average detection rate decreases steadily towards zero. The message is that once should adopt a small α, if high detection rate is the major concern. On the other hand, we need to apply a larger α to reduce the false positive rate Rfp to a reasonably low level as illustrated in Fig. 6.9 (b). For example, to yield Rfp = 10%, the corresponding α should be set at 8. The use of independent routers results in an Rfp = 20%, doubling that of using 16 to 40 routers in 3-hop distance in the AS. Obviously, there exists a tradeoff between Rd and Rfp seen by both Fig. 6.11 and Fig. 6.12. The next section will reveal the effect of the global threshold β, which provides more options to maximize the detection rate and minimize the false alarms. Actually, achieving a 90% detection rate with 25% false alarms by no means imply that false alarms will block 25% legitimate flows. Filtering algorithm is designed to cope with this problem in chapter 7.

6.4.4.

Effects of Global Detection Threshold β
Based on the template database, I realized that it is necessary to choose the global

threshold β satisfying the inequalities 0 < β < α < 12. The proposed choice of β can increase the average detection rate by another 10% over the use of independent detection. The reason of using two thresholds lies in the effective reduction of the false positive rate with an increase of the Rd. The rule of the thumb is that one should choose β slightly lower than α. This results in good preservation of high detection rates with low false alarms. Figure 6.13 reports the effects of β on the detection rate Rd and false alarm rate Rfp, while fixed α = 4.42. In case of 3-hop collaboration, a detection rate of 79% is achieved with a false positive rate of 21% by changing the value β. In contrast, a false positive rate of 27% is incurred if the same detection rate of 79% is desired by changing α to 1.92 as shown in Fig.6.12.

112

Figure 6.13. Effects of global threshold (β) on collaborative detection of shrew DDoS attacks using three cooperative ranges of routers

These results also show that, on average, both performance metrics are less sensitive to variations in β or in the collaborative range size. Rd stays between 0.65 and 0.79 and Rfp is restricted between 0.2 and 0.15. As β decreases, the advantage of collaborating with more than 3 hops shows only a small gain. Actually, the global threshold β plays a vital role in fine-tuning, after local threshold α is constrained by keeping the false positive rate low.

6.5. Scalability and Overhead Analysis
The intensive NS-2 simulation experiments verified that the shrew attack detection mechanism is very promising to defend low-rate TCP-targeted DDoS attacks. The CDF works by integrating DSP, hypothesis testing, and statistical analysis. I discuss below the scalability, overhead, and accuracy issues and limitations of the defense scheme. To deploy a distributed security scheme in Internet core networks, scalability is the major concern. Generally, scalability is related to network size, data rate, link capacity, or the number of router involved. The collaborative shrew attack detection process (Algorithm 2) must count all incoming packets at the network interface. The shrew-filtering process (to

113

be discussed in Chapter 7) demands storage space and computing power to perform the filtering at the flow level. I have experimented on 4,000 traffic streams. Each stream has 8 to 20 flows. Thus, more than 50,000 flows were processed in the simulation experiments. One major obstacle in deploying DDoS defense schemes into the core network routers is the conflict between limited resources in routers and high data rate demanded [Pap03]. It was suggested to implement intrusion detection system (IDS) on a FPGA platform, which can process 32,768 complex rules at a data rate as high as 10 Gbps [Att05]. The sampling and packets filtering rules in shrew attack detection are not more complex than those IDS rules. The most time-consuming part is performing DFT on every traffic stream. This can be solved by using the Xilinx Virtex-4 FPGA, which calculates 512 DSP slices to execute in parallel with a 500 MHz clock. It has been estimated that these hardware implementations may have a speed gain of two orders of magnitude, compared with the software implementations. Overhead is another critical parameter to evaluate the performance of our amplitudefiltering algorithm. It is defined using the time interval from the moment a shrew attack is detected to the moment the countermeasure responses effectively. This time interval is often varied according to the traffic load on the link. However, the load on the link does not affect the response time of our amplitude-filtering algorithm. More detailed discussion is presented in chapter 7.

6.6. Summary
In this chapter, a collaborative detection scheme of shrew DDoS attacks is presented. The research contributions are summarized below in four technical aspects.

114

A.

Effective detection of shrew attacks at stream-level: Combining the spectral

analysis and the hypothesis testing framework, a novel scheme is proposed to detect shrew DDoS attacks at the traffic streaming level. The effectiveness of the spectral template matching approach is verified through intensive experiments. B.
Spectral modeling of Internet traffic patterns: The CDF model offers a

theoretical foundation on which a defense scheme is developed not only against shrew DDoS attacks but is also extendable to cope with flooding type of DDoS attacks. This area demands further research and experiments to prove the idea. C.
Detection accuracy versus false alarms: Extensive NS-2 simulation

experiments achieved encouraging results. CDF scheme detects anomalies successfully with low false-positive alarms. This implies possible tradeoffs between anomaly detection and false alarms. D.
Appealing to hardware implementations: The CDF scheme appeals to both

DSP software and FPGA hardware implementation. The scheme can also be implemented using network processors. It enables us to push frequency-domain monitoring down to a lower level in packet processing hierarchy. The DSP chips, FGPA, and network processors will reduce packet-processing time on routers.

115

Chapter 7 Filtering of Shrew DDoS Attack Flows in Frequency Domains
This chapter discusses a novel approach to filtering out shrew attack flows by analyzing the amplitude spectrum distribution in the frequency domains. Taking samples of packet arriving rates as a time-domain signal, and transforming the signal into frequency domains by DFT (Discrete Fourier Transform), I construct a filter using the hypothesis-test theory.

7.1. Normalized Amplitude Spectral Analysis
The pre-requirement for effectively cutting off a malicious shrew attack flow is to understand the flow’s properties in frequency domains and the differences from normal traffic flows.

7.1.1.

Shrew DDoS Attack Flow Properties
The earliest case of low-rate TCP-targeted DDoS attack was reported in 2001. It had

not been studied thoroughly, however, until Kuzmanovic and Knight [Kuz03] pioneered the work in identifying and characterizing such types of attacks. They studied the rationale of the shrew attack and analyzed the critical parameters that affect the efficiency of TCP flows. They also indicated the limitation of currently available DDoS defense mechanisms.

116

As shown in Fig. 7.1, a single source shrew attack is modeled as a square waveform packet stream with an attack period T, length of the burst L, and the burst rate R. The period T is calculated by the estimated TCP RTO timer implementations at legitimate sources. During the burst with a peak rate R, the shrew pulses create short bursts but severe congestion on the links to the victim. The legitimate TCP flows will decrease their sending rate as defined by the rate-limiting mechanism that cuts the window size and adapts to the network capacity.

(a) Single shrew attack stream

(b) Two shrew attack streams with the same period and half burst rate

(c) Two shrew attack streams with doubled period and same burst rate Figure 7.1. An illustration of various types of shrew attack flows.

For higher throughput, the TCP protocol uses a predefined value of RTO with a fixed RTO incrementing pattern [Pax00]]. The shrew attacks take advantage of this RTO recovery feature by adjusting the attack period to match the RTO period. The feature causes the shrew attack streams to occupy the link bandwidth periodically by sending pulses (Fig.

117

7.1). This makes the legitimate TCP flows always “see” heavily burdened links. Such legitimate TCP flows may undergo a congestion control and reduce their rates significantly. A successful shrew attack may occupy bandwidth lower than 10% of the legitimate TCP flows [Kuz03]. These kinds of periodic pulses are very difficult to detect by traffic management algorithms and by methods based on existing traffic volume analysis at the time domain. This is because the average share of bandwidth consumption is not very high. In distributed scenarios, attacks launched by multiple zombies could lower their individual traffic rates even further, thereby making detection much harder. As shown in Figs. 7.1 (b) and 7.1 (c), the distributed attack sources could decrease their average traffic rates either by lowering the peak rate or using longer attack periods. Detecting the signs of such attacks using a traffic time series is therefore ineffective.

7.1.2.

Analysis of Amplitude Spectrum Distribution
Although it is very challenging to detect and respond to the low-rate attacks using

defense measures developed against DDoS attacks, the periodicity itself provides a clue for developing new defense mechanisms [Che02]. Periodic signals and non-periodic signals present different properties in frequency domains. These variants could be conveniently detected using signal processing techniques. I took the number of arrived packets as the signal and sampled them every 1 ms. At each step, I sampled the number of arrived packets x(i). Then I converted the time-domain series into an amplitude spectrum density (ASD) using DFT (Discrete Fourier Transform) [All04]:
ASD ( f ) = DFT ( x (i ), f ) = 1 N −1 − j 2πfn / N , f = 0,1,2,…,N-1 ∑ x (i ) × e N n =0

(7.1)

118

(a) Single shrew attack flow

(b) Single TCP flow

(c) Comparison in low frequency band Figure 7.2. Normalized amplitude spectrum of the shrew pulse stream and of the TCP flow.

119

Figure 7.2 (a) shows the normalized amplitude spectrum of a shrew attack and Fig. 7.2 (b) is that of a legitimate TCP flow. The Nyquist sampling theorem [All04] indicates that the highest frequency of the analysis is 500 Hz. Compared with the single TCP flow, more energy from the shrew pulse stream appears in lower frequency bands. This property is more profound in Fig. 7.2 (c) which zooms into the low frequency band of [0 Hz, 50 Hz]. Based on observing the normalized amplitude spectrum, I found that it is feasible to design a detection algorithm by comparing the energy density of the shrew attack flow with the energy density of the TCP flow in the low frequency band from 0 Hz to 50 Hz. The difference between the summations of amplitude in this range could be large enough to segregate shrew pulse streams from the legitimate TCP flows. After the integration of the ASD over a given frequency range, the resulting cumulative amplitude spectrum (CAS) determines the ratio of energy accumulated to a given frequency point. This is the area below the ASD curve. The normalized CAS Ψ(f) is defined:
Ψ ( f ) = ∑ ASD (i )
i =1 f max i =1

∑ ASD (i )

(7.2)

Figure 7.3(a) compares the normalized CAS of TCP and shrew flows, and Fig. 7.3(b) zooms into the low frequency band of [0 Hz, 50 Hz]. It is around the frequency point of 20 Hz that the distance of the two curves is maximum. Almost 50% of the total energy of a shrew attack flow is located in the major peak ending around 20 Hz. In contrast, in the same frequency band, less than 15% of the total energy is located for a normal TCP flow. It is also the ending point of the first peak of amplitude spectrum curve of the shrew pulse in Fig. 7.2 (c). Similar to the stream level template construction in Chapter 6, the training process generates the CAS pivot z = Ψ(p) distribution by executing Algorithm 6.1 to determine the flow-level pivot frequency.

120

In point of fact, such a lower frequency band biased energy distribution could be used as the signature of low-rate shrew attacks. Since the shrew attack streams are aiming at the dynamic deficiency in the RTO mechanism of TCP protocol while trying to minimize the average bandwidth utilization, they have to construct congestions periodically at the moments when victims are recovering from RTO. This implies that if an attacker would like to blur the signature, he has to input more packets into the network at other time points. This will increase the bandwidth occupation and thus destroy the stealthy nature of low-rate shrew attacks.

(a) On the whole frequency band

(b) On the low frequency band Figure 7.3. Normalized cumulative amplitude spectrum of the shrew stream and of the TCP flow.

121

7.2. Flow Filtering atop Amplitude Hypothesis Testing
With the knowledge of CAT distribution, we need a rule to identify the signature and make a decision when a cumulative amplitude spectrum value at the CAS pivot-point has been calculated. Since there are two choices, the binary hypothesis test [Dev99] appeals to this application. Based on the differences in amplitude spectrum distribution, I set up a hypothesis test framework and select the optimal detection threshold. Then I designed an algorithm to identify and filter off the shrew attack flows. This section presents in detail the novel shrew-filtering algorithm.

7.2.1.

Hypothesis Test Analysis
Since noise signals existing in communication channels and introduced in the

sampling process are random, we need to confirm statistically that the variation of CAS at the pivot-point is limited in such a range that allows us to distinguish shrew pulse streams from TCP flows with high confidence. The obtained z assumes a Gaussian distribution according to the central limiting theorem. Figure 7.4 (a) presents a normalized histogram of CAS’ distribution at the pivotpoint. Both TCP and shrew streams’ data are calculated in a sample space of more than 8,000 data points. According to the Central Limit Theorem given a distribution with a mean µ and variance σ2, the sampling distribution approaches a Gaussian (Normal) distribution [Dev99]. Thus, we can describe the distribution of CAS at a pivot-point using the Gaussian distribution model:
G ( x; µ , σ ) = ⎧ ( x − µ) 2 ⎫ exp⎨− ⎬ 2σ 2 ⎭ 2πσ ⎩ 1

(7.3)

The statistics of TCP and shrew streams are given below:

122

⎧ Average( µ ) = 0.1131 TCP : ⎨ ⎩ S tan dard _ Deviation(σ ) = 0.026

⎧ Average( µ ) = 0.4985 Shrew: ⎨ ⎩S tan dard _ Deviation(σ ) = 0.038
Figure 7.4(b) shows the Gaussian distribution Nfa(µfa, σfa2) = N(0.50, 0.042) of a single shrew attack flow and the Gaussian distribution Nfo(µfo, σfo2) = N(0.11, 0.032) of a normal TCP flow. There is no overlap between the CAS distribution of a normal TCP flow and that of a single shrew attack flow.

(a) Normalized histogram

(b) Gaussian distribution curves Figure 7.4. Normalized CAS distribution of the shrew stream and of the TCP flow at the pivotpoint.

123

In fact, the gap between the two mean values is greater than 3.29 σ. A 3σ error level gives us a confidence interval of 99.7% [All04], meaning that an error level of ±3σ is good enough even in high precision detection scenarios. The same hypothesis detection method is applied at the flow level to distinguish shrew attack flow from a normal TCP flow. Again, we denote Ho to represent the hypothesis that the flow is not a shrew attack flow, while H1 corresponds to a shrew attack flow. To make flow filtering decisions, we define a flow level likelihood ratio L(z) at the pivot point z as:
L( z ) = p fa ( z ) p fo ( z ) =

σ fo z − µ fa 2 ⎤ 1 ⎡ z − µ fo 2 exp( ⎢( ) −( ) ⎥) σ fa σ fa 2 ⎢ σ fo ⎥ ⎣ ⎦

(7.4)

where pfa(z) is the probability density of z in the Gaussian distribution Nfa, and pfo(z) is the probability density of z in the Gaussian distribution Nfo. Since there is no overlap between the Nfa and Nfo, the filtering threshold γ is chosen at z = 0.28 where γ = L(z) = 1.9. Table 7.1 shows the probability of cutting off a normal TCP flow as a shrew attack flow lower than 0.1% with this γ value. This indicates that the CASbased flow filtering achieved an accuracy of 99.9%. With such a high filtering accuracy, the CDF scheme can tolerates a relatively high false positive rate. When Algorithm 6.2 raises a false alarm, the router depends on flow level hypothesis testing to determine whether a flow should be cut off. As indicated by Table 7.1, the probability that a legitimate TCP flow is filtered off is lower than 0.1%. A high false positive rate Rfp actually causes routers to call for unnecessary filtering. Table 7.1 Error Level of Shrew-Filtering
Error Level ±σ ±1.65σ ±1.96σ ±3σ ±3.29σ Prob. of Error 68% 90% 95% 99.7% 99.9% TCP Error level 0.1311±0.026 0.1311±0.043 0.1311±0.051 0.1311±0.078 0.1311±0.086 Shrew Error Level 0.4985±0.038 0.4985±0.046 0.4985±0.074 0.4985±0.114 0.4985±0.125

124

7.2.2.

Shrew-Filtering Algorithm Design
Based on the above hypothesis test framework, I proposed Algorithm 7.1 to cut off

flows with amplitude spectrum value at the pivot frequency higher than the detection threshold γ. A flow chart is given in Fig.7.5 to help readers follow the shrew filtering process. Although the source IP addresses are generally spoofed in attack packets, it is safe to use the 5-tuple {Source IP, Source Port, Destination IP, Destination Port, protocol} as flow labels. The filtering algorithm handles the incoming packets according to records in the Malicious Flow Table (MFT), Suspicious Flow Table (SFT) and Legitimate Flow Table (LFT).
Algorithm 7.1: Amplitude Filtering of Shrew Attacks at Flow Level Input: Ψi (p): The amplitude spectrum of an incoming traffic flow Fi identified by the 5-tuple identifier. γ: The amplitude filtering threshold obtained from the training process Output: Enable packet dropping in flow Fi Procedure: 01: while flow filtering is called by algorithm 2 on detecting shrew attacks 02: Check flow Fi for membership in various tables 03: Case 1: Fi is in LFT 04: Route the flow normally 05: Case 2: Fi is in MFT 06: Drop all packets in flow Fi 07: Case 3: Fi is in SFT 08: if Ψi (p) ≤ γ Then 09: Mark Fi as legitimate, move it into LFT 10: else 11: Fi contains shrew attacks, move it to MFT 12: Drop all the packets in flow Fi 12: end If 13: Case 4: Fi is not in any of the three tables 14: Add Fi flow into SFT 15: endwhile

If the router has initiated the amplitude filtering algorithm while confirming the alert, it starts checking incoming packets. If a packet label is in the set LFT, this packet is

125

routed normally. If it is in the set MFT, this packet is dropped. If it is in the set SFT, we continue sampling until time out. If there is no matching in any table, this packet belongs to a new flow and it would be added into the SFT, then the sampling begins and the timer starts.

Figure 7.5. Control flow in the amplitude-filtering Algorithm (LFT: Legitimate Flow able, SFT: Suspicious Flow Table, MFT: Malicious Flow Table, Ψ(p): Cumulative Amplitude Spectrum).

Once a timer is expired for a flow, we compare its amplitude spectrum likelihood ratio L(z) at pivot point with the threshold γ. If L(z) value is lower than the threshold, we move its record into LFT. All packets in this flow will be routed normally. If L(z) value is higher than the threshold γ, the flow is moved into the MFT and all its packets are dropped. The pseudo code of the amplitude spectral filtering process is specified in the Shrew-

126

Filtering Algorithm. For flow filtering, we adopt data structures SFT, LFT and MFT tables to track per flow status. We identify a flow using the 5-tuple {Source IP, Source Port, Destination IP, Destination Port, protocol}. Routers generally cannot afford to store 13 bytes for each flow for security purposes. To minimize the storage overhead incurred by the 3 large tables needed to implement the algorithm, we store only the output of a hash function with the label as the input.

7.3. Experiment Results and Performance Analysis
I verified the effectiveness and evaluated the performance of my spectral analysis based detection algorithm through intensive NS-2 simulation experiments.

7.3.1.

Experiment Setup
The shrew-filtering algorithm has been implemented in the NS-2 simulator, which is

a widely recognized packet level discrete event simulator [Net04]. A subclass of connector named ShrewFilter was added to the head of each SimplexLink. A TrafficMonitor was coded into the simulator to compute the traffic matrices. The ShrewFilter is used to process the sample array and to calculate the CAS of flows leading to the victim. Then, the MFT or LFT entries are set accordingly. The system configuration of the simulation scenario is shown in Fig. 7.6. The simulation consists of a variety of Internet traffic patterns. Multiple scenarios are studied including a single TCP flow vs. a single shrew flow, a single TCP flow vs. distributed shrew flows, multiple TCP flows vs. a single shrew flow, and multiple TCP flows vs. distributed shrew flows. The distributed attack patterns include the cases shown in Figs.

127

7.1(b) and 7.1(c). While TCP-Tahoe, TCP-Reno and others present similar vulnerability under shrew attacks [Hua01], the TCP-Reno standard was adopted the in experiments. We compare the results of our shrew-filtering algorithm with the well-known Drop Tail scheme.

Figure 7.6. The simulation scenario and experimental setting.

7.3.2.

Filtering Efficiency
The NS-2 simulations are carried out with different combinations of legitimate TCP

flows and shrew attack streams. We compared the TCP throughputs achieved by the shrewfiltering algorithm with the well-known Drop Tail scheme using the comparison metric normalized throughput (ρ), which is defined as: ρ=
Average throughput achieved by the TCP flow (or aggregate) with DDoS stream Throughput achieved without DDoS stream

(7.4)

The normalized throughput indicates the severity of the damage that the shrew streams have done to the performance of legitimate TCP flows. The lower the normalized throughput is, the greater the damage. In the simulations, assume the link capacity of the last hop to the victim is 2 Mbps. Since all TCP variants are equally vulnerable to shrew DoS streams of 50 ms or higher [Kuz03], I used TCP-Reno for the purpose of experiment. The

128

sources of the shrew attack streams are illustrated by Fig. 7.6. Their delay is a random variable uniformly distributed within (60 ms, 120 ms). I started with single shrew-stream scenarios. Fig. 7.7 compares the throughputs of TCP flows using the Drop Tail scheme and the shrew-filtering algorithm.

(a) Single TCP flow

(b) Five TCP flows Figure 7.7. Scenarios of TCP flows under single shrew attack.

The x-axis is the attack period and the y-axis is the normalized throughput TCP flows achieved. Fig. 7.7(a) shows the scenario of a single TCP flow under attack of a single shrew stream modeled in Fig. 7.1(a). Fig. 7.7(b) corresponds to the scenario of five TCP flows under attack from a single shrew stream.

129

It is clear that under the Drop Tail algorithm, the throughput of legitimate TCP flows is far below the actual attainable throughput and the link utilization is very inefficient. With the shrew-filtering algorithm, the gain in TCP throughput is significant. It reaches what legitimate flows can reach when there is no shrew stream. The hypothesis test model can identify shrew streams with high confidence. It filtered out shrew streams before they hurt the legitimate flows. Distributed shrew streams are hard to detect because of their much lower average traffic rates. Simulations are carried out using four shrew streams that are distributed in either space domain (Fig. 7.1 (b)) or time domain (Fig. 7.1 (c)), respectively. Again, I studied their effects on single and five legitimate TCP flows. Figure 7.8 presents the case where shrew streams are distributed in space but synchronized as in Fig. 7.1 (b). Four shrew streams are from four different sources with the same attack periods and the same burst lengths. However, their peak rate is only R/4. This means that their average traffic rate is only 1/4 of that of the single source attack. Figure 7.9 compares the throughputs of TCP flows under the Drop Tail algorithm and our shrew-filtering algorithm in the case that shrew streams are distributed in a timely fashion but synchronized as in Fig. 7.1(c). Four shrew streams are from four difference sources with the same peak rates and the same burst lengths. However, their attack periods are 4T. This distribution makes the interval between pulses four times longer to bring down the average traffic rate to 1/4 of that of the single source attack pulse stream. These results show that the shrew-filtering algorithm is indeed capable of recognizing distributed shrew streams with lower average traffic rate. This is one major advantage of frequency spectrum technique over bandwidth utilization analysis. Even if the

130

shrew streams were launched from more zombies to further lower their average bandwidth utilization, their frequency spectrum would possess the same properties.

(a) Single TCP flow

(b) Five TCP flows Figure 7.8. Normalized throughput of TCP flows under 4 spatially distributed shrew attack flows.

In other words, the shrew-filtering mechanism is effective even if the attack is launched through a larger number of streams with lower burst peak rates. In fact, if zombies use longer individual attack periods, higher percentages of flows’ energy will be located in the low frequency band that was being monitored.

131

(a) Single TCP flow

(b) Five TCP flows Figure 7.9. Normalized throughput of TCP flows under 4 temporal distributed shrew attack flows.

7.3.3.

Response Time
The response time is a critical parameter used to evaluate the performance of our

shrew-filtering algorithm. In general, the time that a DDoS defense algorithm takes to detect whether malicious flows exist or not is used as a matrix to monitor the traffic conditions. The time is varied according to the traffic load on the link. However, the load on the link does not affect the response time of the shrew-filtering algorithm. Results in Section 7.3.2 show that the performance of the shrew-filtering algorithm is coherent under different traffic conditions, where the same 5-second sampling time was

132

used. The effects of variant sampling length are determined by the signal’s periodicity. If the sampled sequence presents similar frequency characteristics of the original signal, then the variance of sampling time will not impact the detection precision. Figure 7.10 illustrates the effect of various sampling lengths on filtering accuracy.

(a) Distributions of CAS at pivot-point

(b) Throughput under 3 sampling times: 1, 3 and 5 seconds Figure 7.10. Effects of sampling lengths on the TCP throughput.

133

Figure 7.10 (a) presents the distribution of CAS at the pivot-point of TCP flows and shrew streams. They are sampled from 1 second to 5 seconds. As the sampling time decreases, the CAS at the pivot-point of TCP flow scatters wider. Therefore, the probability of treating a legitimate TCP flow as a shrew stream increases. However, the distributions of CAS at the pivot-point of shrew streams are pretty stable. If we stick to the threshold of 0.3, the high detection confidence level is maintained even when the sampling time decreases to 3 seconds. Table 7.2 shows the confidence levels of different sampling times. I observed ±1.96σ (95%), ±3σ (99.7%) and ±3.29σ (99.9%) error levels of TCP and shrew streams. When the sampling time (the response time τ) is longer than 2 seconds, there is no overlap between the ±3.29σ error level ranges of TCP flow and shrew stream. Therefore, the confidence level of detecting and filtering shrew streams is very high (99.9%) while τ ≥ 2 seconds. Table 7.2 Error Level of Filtering with Different Sampling Times
Sampling Time ±1.96σ/ 95% ±3σ/ 99.7% ±3.29σ/ 99.9% TCP Flow Shrew Stream TCP Flow Shrew Stream TCP Flow Shrew Stream 1 Second 0.1614±0.176 0.5036±0.050 0.1614±0.270 0.5036±0.076 0.1614±0.296 0.5036±0.083 2 Second 0.1445±0.094 0.4690±0.061 0.1445±0.144 0.4690±0.093 0.1445±0.158 0.4690±0.102 3 Second 0.1327±0.067 0.4508±0.067 0.1327±0.102 0.4508±0.103 0.1327±0.112 0.4508±0.113 4 Second 0.1258±0.078 0.4479±0.074 0.1258±0.120 0.4479±0.112 0.1258±0.132 0.4479±0.123 5 Second 0.1131±0.051 0.4985±0.074 0.1131±0.078 0.4985±0.114 0.1131±0.086 0.4985±0.125

When τ = 1 second, an overlap is observed in both ±3σ and ±3.29σ error ranges, but no overlap for ±1.96σ error level. This implies that information carried by sampled signal series cannot separate TCP flows from shrew streams with such a high confidence level (99.7%). However, the shrew-filtering algorithm could still respond to the shrew attacks in 1

134

second. I cut off it with little sacrifice in the confidence level (95%). Figure 7.10(b) shows the throughput of five TCP flows under the attack of four distributed shrew streams. Clearly, all sampling series achieved much higher throughput than the Drop Tail algorithm.

7.4. Scalability, Development, and Limitations
To deploy a distributed security scheme in a core network, the scalability issue is related to the network size, data rate, link capacity, or router number involved. The shrewfiltering process demands storage space and computing power to perform the filtering at flow level. One major obstacle in deploying the filtering schemes into the core network routers is the conflict between limited resources in routers and high data rates demanded [Mah01]. It was suggested to implement an intrusion detection system (IDS) on a FPGA platform, which can process 32,768 complex rules at a data rate as high as 10 Gbps [Att05]. The sampling and packet filtering rules are not more complex than those IDS rules. The most time-consuming part is to perform DFT on every traffic stream. This can be solved by using the Xilinx Virtex-4 FPGA, which calculates 512 DSP slices to execute in parallel with a 500 MHz clock. It has been estimated that these hardware implementations may have a speed gain of two orders of magnitude, compared with the software implementations. The performance of shrew filtering algorithms may suffer from the dynamics of source IP spoofing. In a flow- level sampling and filtering procedure, we uniquely identified each flow using the 5-tuple {Source IP, Source Port, Destination IP, Destination Port, protocol}. This may add some flow labeling overhead, if the attacker spoofs the source IP dynamically. If the spoofing source IP set is very large, the attacker may cause the MFT to overflow. The MFT overflow may decrease the performance of the shrew filtering process. It could be worse if the attacker uses different source IP in sending every pulse. One possible

135

solution to solve this dynamic spoofing problem is to also perform rate limiting at network interfaces, when we detect the existence of shrew attack streams. There is one limitation in our shrew-filtering scheme. It is still difficult to segregate malicious attacking flows from legitimate flows that exhibit similar periodic pulsing behaviors. The impact on short-lived burst traffic flows is light. Although they may be mistakenly marked as malicious flow, they have already passed the filter and thus do not affect the legitimate TCP flow. The problem is that short-lived burst traffic may waste space in the MFT. However, long-lived pulsing nature traffic is treated as malicious shrew attack flows. Previous research pointed out that such long-lived pulsing nature traffic can bring down the throughput of TCP flows sharing links with them even though they are not generated purposely to impair the normal TCP flows. Therefore, when TCP flows are throttled heavily, it is reasonable to block these pulsing streams.

7.5. Summary
In this chapter, I have proposed to cut off low-rate TCP-targeted DDoS attack flows using the periodicity properties of different flows in the frequency domain. Analysis and simulations show that more energy of low-rate shrew attacks is located in the lower frequency band, compared with the legitimate TCP flows. Using a hypothesis test theory and the Gaussian distribution model, I have shown that the shrew-filtering algorithm achieves a higher accuracy. Thus, this scheme can block malicious shrew flows with a high confidence level (> 99.9%), while exhibiting very low probability (< 0.1%) of blocking legitimate TCP flows.

136

One of the distinct advantages of this approach is that DFT and frequency domain analysis are standard digital signal processing (DSP) methods that could be implemented efficiently in hardware, thanks to the modern VLSI technology. Therefore, the shrewfiltering algorithm would not incur much overhead in routers since the whole process could be carried out in fast hardware, while the routers perform their normal routing operations.

137

Chapter 8 Conclusions
DDoS attacks are an impending threat to Internet related applications. This chapter summarizes the major contributions of this dissertation and discusses further directions for research. A preliminary design of reconfigurable hardware-based accelerators for shrew attack detection is also presented.

8.1. Summary of Contributions
In this research, I explored the approach of defending against DDoS attacks in ISP core networks. A new distributed defense scheme is proposed based on collaborative anomaly detection crossing ISP networks. The key contributions of this dissertation can be summarized from two perspectives. In the DDoS defense research community, this is the first real distributed defense mechanism that is deployed in the ISP core networks. My distributed scheme is not only able to cover a wide area of the Internet, but is also able to integrate new techniques into the backbone infrastructure. Considering the fast evolution of technology of both malicious attacks and defense, this feature is critical. From an ISP perspective, this distributed scheme can motivate ISPs to deploy defense in their networks. It could be a selling point to attract more customers since the ISPs

138

can claim that their network will suffer less breakdown experiences. In today’s Internet environment, the security is highly interdependent among ISP networks. This distributed scheme enables ISPs to monitor whether their infrastructure is under attack or is being used to transfer attacking traffic to others. ISPs can help each other to avoid financial loss. More concretely, my contribution is summarized as below: • A New SIP Protocol for Trust Negotiation among AS Domains: To push security functions into the core network, I propose a securing infrastructure protocol (SIP) enabling intermediate network devices to monitor traffic anomalies

collaboratively. SIP protocol is different from IP multicast, application layer multicast, and overlay network multicast protocols that have been reported previously. In the vertical direction of a network layer model, SIP protocol sits on top of the IP layer and is transparent to transport layer protocols. From the angle of view of deployment, SIP holds its responsibility as limited in routers of a physical network. No end hosts or servers are involved. • Distributed Change-Point Detection Scheme: Based on the anomaly pattern detected in related network domains, the distributed change-point (DCP) detection scheme detects a DDoS flooding attack before the victim is overwhelmed. This approach captures the abrupt traffic changes at attack-transit routers. The DCP scheme achieved a high detection rate of DDoS attacks with very low false positive rates. A DCP detection scheme is suitable for deployment at the ISP core networks. The ISP-level cooperation can eliminate the need of intervention from edge networks. The distributed detection scheme automatically performs traceback during the detection of suspicious traffic flows. Once a DDoS flooding attack is detected, we know the exact router or AS that the anomaly was observed.

139



Malicious flow identifying and cutting off algorithms: I propose a new approach called MAFIC—MAlicious Flow Identification and Cutoff—to support the adaptive packet dropping policy. I implemented a new adaptive packet dropping and probing algorithm. By monitoring the response to packet loss from the flow source, malicious attacking flows are accurately identified and all their packets are then dropped before reaching the victim. The extensive NS-2 based simulation results shows that MAFIC responds quickly to reduce the traffic rate by limiting flow bandwidth incisively. Indeed, MAFIC can identify and cut off malicious flows with very high accuracy and a minimized impact on the performance of legitimate application flows.



Collaborative detection and filtering off shrew attack flows in frequency domains: This dissertation presents a new spectral template-matching approach to countering shrew DDoS attacks. My collaborative detection and filtering (CDF) scheme detects shrew attack flows hidden in legitimate TCP/UDP streams by spectral analysis against a pre-stored template of average attack spectrum. Leveraging spectral analysis, a hypothesis-testing model makes the spectral template matching effective in detecting shrew DDoS attacks at traffic streaming levels and in cutting off malicious flows at a refined flow level. The simulation results show high detection accuracy by merging alerts from cooperative routers. Our CDF scheme appeals to both DSP software and FPGA hardware implementation. The scheme can also be implemented on network processors. One can push frequency-domain monitoring down to a lower level in the packet processing hierarchy. The DSP chips, FPGA, and network processors will all reduce the packet-processing time on routers.

140

8.2. Preliminary Accelerator Design
The major concern of deploying defense DDoS attacks in ISP core networks is the limited computing and storage resources routers can share for security purposes. Considering the computational complexity incurred by FFT and autocorrelation calculation, it is challenging to cope with the high data rate in today’s network (multi gigabyte). In general, it is preferable to detect the attacks swiftly before damages caused. Most software-based security mechanisms are not feasible in high-speed core networks. In fact, scanning network traffic at line speed for signatures of attacks is a challenging task in today’s high-speed networks. The software-based systems have severe performance limitations. On the other hand, the prohibitive cost and long design period makes it difficult for Application Specific Integrated Circuits (ASICs) to keep up with the evolution steps of Internet attack technologies. The significant achievement in VLSI techniques makes reconfigurable hardware a promising solution. FPGA devices have the flexibility of software combined with the speed of a hardware implementation, providing high performance and fast development cycles. The reconfigurability allows further updates of the security system in regards to the evolution of attacks and defense techniques. The high parallelism makes it capable of handling multi-gigabytes of data rates in the core networks. Much research has been reported relating to the application of reconfigurable hardware in the area of security or traffic monitoring in high-speed networks. These works can be roughly categorized into three sub areas: stream reassembly and state tracking [Sch04], header processing and packet classification [Tay05], [Son05], [Spi03], [Bab01], and content processing [Bak04], [Cla04], [Sug04]. For security purposes like Internet worm containment or DDoS attack defense, traffic monitor processing is composed neither of

141

solely header processing nor solely of content scanning. It is a combination effort integrating all of the techniques. For example, Attig et al. [Att05] proposed an intrusion detection system (IDS) design on a FPGA platform that can process 32,768 complex rules at data rates as high as 10 Gbps. My countering and spectral analysis method is not more complex than those IDS rules. Therefore, a reconfigurable hardware-based solution is ideal for performing shrew DDoS attack detection in real time in the high-speed network environment. To the best of my knowledge, there is no work reported that implements DDoS defense schemes atop FPGA devices. I have proposed a preliminary design of the embedded accelerator for shrew attack detection algorithms. In this architecture, the most important and time-consuming parts are autocorrelation calculation units and DFT converting units. The design needs to be optimized in terms of area efficiency and time constraints. Figure 8.1 illustrates the main function blocks in the embedded shrew DDoS attack detection accelerator.

Figure 8.1. Function blocks of shrew DDoS attack detection accelerator

The accelerator is connected to the network card and counts the incoming packets. The Packet Counting unit consists of several simple counters, each of them corresponding to one flow. The sampling unit records the counter values periodically, which is set as 1 ms. When the length of the sampled series reaches 4096 for a certain flow, I calculated its autocorrelation sequence and converted it into a frequency domain using DFT. Comparing

142

the PSD of a sampled flow with the statistic pattern obtained, we can detect the existance of shrew attack flows. Chapter 7 reveals that the length of a sampled series has significant impact on detection accuracy. With the sampling period of 1 ms, a series of 4096 is necessary if a detection rate of 95% is desired. Therefore, the accelerator needs to calculate the autocorrelation sequence and FFT of 4096 data points. The detection delay is another important concern. The shrew attacks achieve the maximum impact against TCP throughput when its period is in the range of 0.5 to 1.0 seconds. In addition, the TCP throughput drops quickly after several pulses of shrew attacks arrive. Hence, it is desired to obtain the traffic spectrum in a period higher than 0.5 seconds. This gives enough time to launch flowfiltering mechanisms to segregate malicious attacking flows from legitimate ones before damage caused.

8.3. Further Research Works
Based on the solid foundation laid by previous works, forthcoming research works will lead to two major tracks: 1) security protocol for next generation Internet infrastructures, and 2) reconfigurable embedded accelerator design. The following key problems are open for investigation: • Infrastructure Security Protocol in IPv6: Aside from establishing a framework under which ISPs can effectively and cooperatively monitor anomalies in core networks, I will address following questions to achieve infrastructure security in the context of IPv6: What functions have to be implemented in core networks? If anomalies are identified, what actions/ countermeasures are feasible?

143

What is the impact on innocent traffic if false positive alarms are raised? Is the security of the protocol itself robust enough? How can attackers take advantage of the protocol? What if one or more nodes are compromised? How much overhead is incurred to routers supporting this protocol? How much bandwidth has to be reserved for it? • Reconfigurable Embedded Accelerator Architectures: Compared to general purpose embedded architectures, adaptivity and scalability are two essential concerns. I will explore the following critical issues in security oriented embedded network devices: How can we foster the evolution of the device along with the rapid changes in attack patterns and emerging of new applications? What kind of real-time reconfiguration mechanism is desired? What kind of adaptive scheme is able to ensure a device powerful enough to survive the foreseeable future?

144

Bibliography
[Abi05] [Abr98] [Abr02] [Ahn03] Abilene-I data set, the Passive Measurement and Analysis (PMA) project, http://pma.nlanr.net/traces/long/ipls1.html; P. Abry and D. Veitch, “Wavelet Analysis of Long-Range-Dependent Traffic,” IEEE Trans. Information Theory, vol. 44, no. 1, 1998, pp. 2–15; P. Abry, R. Baraniuk, P. Flandrin, R. Riedi, and D. Veitch, “Multiscale Nature of Network Traffic,” IEEE Signal Processing Magazine, vol. 19, no. 3, 2002; G. Ahn, K. Kim, and J. Jang, “MF (Minority First) Scheme for Defeating Distributed Denial of Service Attacks,” Proceedings of the 8th International Symposium on Computers and Communications (ISCC’03), 2003; B. Al-Duwairi, “Mitigation and Traceback Countermeasures for DDoS Attacks,” Ph.D. dissertation, Computer Engineering, Iowa State University, 2005; H. Aljifri, “IP Traceback: A New Denial-of- Service Deterrent,” IEEE Security and Privacy Magazine, May/June 2003, pp. 24-31; P. Allen and C. Demchak, “The Palestinian-Isreal: Cyberwar,” Military Review, March-April, 2003; R. Allen and D. Mills, Signal Analysis: Time, Frequency, Scale, and Structure, Wiley, N. J. 2004; T. Anderson, R. Mahajan, N. Spring, and D. Wetherall, “Rocketfuel: An ISP Topology Mapping Engine,” http://www.cs.washington.edu/research/ networking/rocketfuel/, 2006; M. Attig and J. Lockwood, “A Framework For Rule Processing in Reconfigurable Network Systems,” in Proc. of IEEE Symposium on FieldProgrammable Custom Computing Machines (FCCM), Napa, CA, April 17-20, 2005; F. Baboescu and G. Varghese, "Scalable Packet Classification", SIGCOMM'01, San Diego, CA., USA, August 2001; T. Baba and S. Matsuda, “Tracing Network Attacks to Their Sources,” IEEE Internet Computing, Vol. 6, No. 3, 2002;

[Ald05]

[Alj03] [All03] [All04] [And06]

[Att05]

[Bab01] [Bab02]

145

[Bak04]

Z. Baker and V. Prasanna, "A Methodology for the Synthesis of Efficient Intrusion Detection Systems on FPGAs", In Proceedings of the Twelfth Annual IEEE Symposium on Field Programmable Custom Computing Machines 2004 (FCCM '04), 2004; P. Barford, J. Kline, D. Plonka, and A. Ron, “A signal analysis of network traffic anomalies,” Proc. of ACM Internet Measurement Workshop, Marseille, France, November 6-8, 2002; S. Bellovin, “Report of the IAB Security Architecture Workshop,” Network Working Group, RFC 2316, IETF, 1998; S. Bellovin, M. Leech, and T. Taylor, “ICMP Traceback Messages,” InternetDraft draft-ieft-itrace-01.txt, October 2001; S. Bellovin, J. Schiller, and C. Kaufman, “Security Mechanism for the Internet”, Network Working Group, RFC 3631, IETF, 2003; A. Belenky and N. Ansari, “On IP Traceback,” IEEE Communications Magazine, July 2003, pp. 142–153. T. Benzel, B. Braden, D. Kim, C. Neuman, A. Joseph, K. Sklower, R. Ostrenga, and S. Schwab, “Experience with DETER: A Testbed for Security Research”, Second IEEE Conf. on Testbeds and Research Infrastructures for the Development of Networks and Communities (TridentCom2006); R. Blazek, H. Kim, B. Rozovskii, and A. Tartakovsky, “A Novel Approach to Detection of DoS Attacks via Adaptive Sequential and Batch-sequential Change-Point Detection Methods,” Proc. of IEEE Workshop on Information Assurance and Security, June 2001; M. Blumenthal and D. Clark, “Rethinking the Design of the Internet: the End-toEnd Arguments vs. the Brave New World,” ACM Transactions on Internet Technology, Vol.1, No.1, Aug. 2001; H. Burch and B. Cheswick, “Tracing Anonymous Packets to Their Approximate Source,” 14th Systems Administration Conference (LISA 2000), New Orleans, Louisiana, Dec. 2000; M. Cai, Y.-K. Kwok, and K. Hwang, “A Scalable Set-Union Counting Approach to Pushing Back DDoS Attacks,” USC GridSec Technical Report TR-2004-21, Oct. 2004, http://GridSec.usc.edu/TR.html ; M. Cai, K. Hwang and Y. Chen, “Integrating Misuse and Anomaly-based Intrusion Detection Systems with Weighted Signature Generation”, IEEE Trans. On Dependable and Secure Computing, revised Sept. 2005;

[Bar02]

[Bel98] [Bel01] [Bel03] [Bel03b] [Ben06]

[Bla01]

[Blu01]

[Bur00]

[Cai04]

[Cai05]

146

[Cal98] [Car06] [CER96] [CER98] [Cha02a] [Cha02b] [Che05a]

J. Callas, L. Donnerhacke, H. Finney, and R. Thayer, “OpenPGP Message Format,” Networking Working Group, RFC 2827, IETF, 1998; G. Carl, G. Kesidis, R. Brooks, and S. Rai, “Denial-of-Service Attack Detection Techniques,” IEEE Internet Computing, January/February 2006; CERT Advisory CA-1996-21 TCP SYN Flooding and IP Spoofing Attacks, http://www.cert.org/advisories/CA-1996-21.html, as of Aug. 30, 2006; CERT Advisory CA-1998-01 Smurf IP Denial-of-Service Attacks, http://www.cert.org/advisories/CA-1998-01.html, as of Aug. 30, 2006; A. Chakrabarti and G. Manimaran, “Internet Infrastructure Security: A Taxonomy”, IEEE Network, November 2002; R. K. C. Chang, “Defending Against Flooding-Based Distributed Denial-ofService Attacks: A Tutorial,” IEEE Communications Magazine, October 2002; S. Chen and Q. Song, “Perimeter-Based Defense against High Bandwidth DDoS Attacks,” IEEE Trans. on Parallel and Distributed Systems, Vol. 16, No. 6, June 2005; Y. Chen, Y.-K. Kwok, and K. Hwang, “MAFIC: Adaptive Packet Dropping for Cutting Malicious Flows to Pushback DDoS Attacks,” IEEE International Workshop on Security in Distributed Computing Systems (SDCS’05), in conjunction with ICDCS 2005, Columbus, OH., USA, June 6-10, 2005; Y. Chen and K. Hwang, "Collaborative Detection and Filtering of Shrew DDoS Attacks using Spectral Analysis," Journal of Parallel and Distributed Computing, Special Issue on Security in Grids and Distributed Systems, Vol.66, Issue 9, September 2006; Y. Chen and K. Hwang, “Collaborative Change Detection of DDoS Attacks on Community and ISP Networks”, IEEE International Symposium on Collaborative Technologies and Systems (CTS 2006), Las Vegas, NV., USA, May 15-17, 2006; C. M. Cheng, H. T. Kung, and K. S. Tan, “Use of spectral analysis in defense against DoS attacks,” Proc. of 2002 IEEE GLOBECOM, Taipei, China; R. Chertov, S. Fahmy, and N. Shroff, “Emulation versus Simulation: A Case Study of TCP-Targeted Denial of Service Attack,” in Proc. of 2nd International IEEE CreateNet Conference on Testbeds and Research Infrastructures, March 2006; S. Chou, A. Stavrou, J. Ioannidis, and A. Keromytis, "gore: Routing-Assisted Defense Against DDoS Attacks," in the Proceedings of the 8th Information Security Conference (ISC), September 2005, Singapore;

[Che05b]

[Che06a]

[Che06b]

[Che02] [Che06c]

[Cho05]

147

[Cis03] [Cla04]

Cisco 2003;

NetFlow,

Http://www.cisco.com/warp/public/732/Tech/nmp/netflow/,

C. Clark and D. Schimmel, "Scalable pattern matching for high speed networks", in Proceedings of the 12th Annual IEEE Symposium on FieldProgrammable Custom Computing Machines (FCCM’04), 20-23 April 2004 Page(s):249 – 257; S. Crosby and D. Wallach, “Denial-of-Service via Algorithmic Complexity Attacks,” Proceedings of the 12th USENIX Security Symposium, Aug. 2003; M. Delio, “New Breed of Attack Zombies Lurk,” http://www.wired.com/news/ technology/0,1282,43697,00.html, as of Oct. 31, 2005 DETER and EMIST Network Project, “Cyber Defense Technology Networking and Evaluation,” Communications of the ACM, Vol.47 (2004), No.3; “The DETER Testbed: Overview,” http://www.isi.edu/deter/docs/testbed.overview.pdf; J. Devore and N. Farnum, “Applied Statistics for Engineers and Scientists,” Duxbury Press, 1999; T. Dierks and C. Allen, “The TLS Protocol, Version 1.0,” Network Working Group, RFC 2246, IETF, 1999; S. Dietrich, N. Long, and D. Dittrich, “Analyzing Distributed Denial of Service Tools: The Shaft Case,” Proceedings of USENIX LISA XIV, 2000; X. Dimitropoulos, D. Krioukov, G. Riley, and K. Claffy, "Revealing the Autonomous System Taxonomy: The Machine Learning Approach," the Passive and Active Measurement (PAM) Workshop in 2006; D. Dittrich, “The ‘Stacheldraft’ Distributed Denial of Service Attack Tool,” http://staff.washington. edu/dittrich/, 2000; N. Duffield and M. Grossglauser, “Trajectory Sampling for Direct Traffic Observation,” ACM SIGCOMM 2000, August 2000; D. Eastlake, “Domain Name System Security Extensions,” Network Working Group, RFC 2535, IETF, 1999; J. Evers, “’Bot Herders’ May Have Controlled 1.5 Million PCs,” ZDNet News, Oct. 21, 2005, http://news.zdnet.com/2100-1009_22-5906896.html; C. Estan and G. Varghese, “New Directions in Traffic Measurement and Accounting,” 2001 ACM SIGCOMM Internet Measurement Workshop, San Francisco, CA., Nov. 2001;

[Cro03] [Del01] [DET04] [DET05] [Dev99] [Die99] [Die00] [Dim06]

[Dit00] [Duf00] [Eas99] [Eve05] [Est01]

148

[Fal99] [FBI05]

M. Faloutsos, C. Faloutsos, and P. Faloutsos, "On Power-law Relationships of the Internet Topology," Proc. of ACM SIGCOMM, Aug. 1999; FBI, “THE CASE OF THE HIRED HACKER: Entrepreneur and Hacker Arrested for Online Sabotage,” FBI.gov Headline Story, Apr. 18, 2005, http://www.fbi.gov/page2/ april05/hiredhacker041805.htm; P. Ferguson and D. Senie, “Network Ingress Filtering: Defeating Denial of Service Attacks which employ IP Source Address Spoofing,” Network Working Group, RFC 2827, IETF, 2000; S. Floyd and V. Jacobson, “Random Early Detection Gateways for Congestion Avoidance,” IEEE/ACM Transactions on Networking, vol. 1, no. 4, pp. 397-413, Aug. 1993; S. Floyd, “TCP and Explicit Congestion Notification,” ACM Computer Communications Review, vol. 24, no. 5, Oct. 1994, pp. 10–23; S. Floyd and K. Fall, “Promoting the Use of End-to-End Congestion Control in the Internet,” IEEE/ACM Trans. Networking, vol. 7, no. 4, Aug. 1999; S. Floyd, M. Handley, J. Padhye, and J. Widmer, “Equation-Based Congestion Control for Unicast Applications,” Proc. ACM SIGCOMM, 2000; V. Fuller, T. Li, J. Yu, and K. Varadhan, “Classless Inter-Domain Routing (CIDR): an Address Assignment and Aggregation Strategy,” Network Working Group, RFC 1519, IETF, 1993; J. Galvin, S. Murphy, S. Crocker, and N. Freed, “Security Multiparts for MIME: Multipart/Signed and Multipart/Encrypted,” Network Working Group, RFC 1847, IETF, 1995; S. Gibson, “Distributed Reflection Denial of Service,” Feb. 22, 2002, available at http://grc.com/dos/drdos.htm; T. Gil and M. Poletto, “MULTOPS: a Data-Structure for Bandwidth Attack Detection,” in Proceedings of 10th USENIX Security Symposium, August 2001; N. Gohring, “Attack Hits SUN Public Grid Service on day one,” Network World, Mar. 23, 2006, http://www.networkworld.com/news/2006/032306attack-sun-public-grid.html; L. Gordon, M. Loeb, W. Lucyshyn, and R. Richardson, “10th Annual CSI/FBI Computer Crime and Security Survey,” Computer Security Institute (CSI), 2005; “GT-ITM: Georgia Tech Internet Topology Models,” http://www.cc.gatech.edu /projects/gtitm/, Nov. 03, 2005;

[Fer00]

[Flo93]

[Flo94] [Flo99] [Flo00] [Ful93]

[Gal95]

[Gib02] [Gil01] [Goh06]

[Gor05] [GTI05]

149

[Gui04]

M. Guirguis, A. Bestavros, and I. Matta, “Bandwidth Stealing via Link Targeted RoQ Attacks,” Proc. 2nd IASTED Int’l Conf. on Communication and Computer Networks, Nov. 2004; M. Guirguis, A. Bestavros, I. Matta, and Y. Zhang, “Reduction of Quality (RoQ) Attacks on Internet End Systems,” IEEE INFOCOM, Miami, FL., March 2005; N. Haller, C. Metz, P. Nesser, and M. Straw, “A One-Time Password System,” Network Working Group, RFC 2289, IETF, 1998; M. Handley, S. Floyd et al., “TCP Friendly Rate Control (TFRC): Protocol Specification,” IETF RFC 3448, Jan. 2003; X. He, C. Papadopoulos, J. Heidemann, and A. Hussain, “Spectral Characteristics of Saturated Links,” under submission, http://www.isi.edu/~johnh/PAPERS/ He04a.html; A. Hermida, “Yahoo Attack Exposes Web Weakness,” BBC online news, 2000, http://news.bbc.co.uk/1/hi/sci/tech/635444.stm; K. Houle, G. Weaver, N. Long, and R. Thomas, "Trends in Denial of Service Attack Technology", 2001, www.cert.org/archive/pdf/; P. Huang, A. Feldmann, and W. Willinger, “A Non-Intrusive, Wavelet-Based Approach to Detecting Network Performance Problems,” Proc. ACM SIGCOMM Internet Measurement Workshop, 2001; A. Hussain, J. Heidemann, and C. Papadopoulos, “A Framework for Classifying Denial of Service Attacks,” Proc. ACM SIGCOMM, 2003; K. Hwang, Y. Chen, and H. Liu, “Defending Distributed Systems against Malicious Intrusions and Network Anomalies”, Proc. of International Workshop on Security in Systems and Networks, (NSS’05), in conjunction with the IEEE IPDPS, Denver, CO. April 8, 2005; J. Ioannidis and S. M. Bellovin, “Implementing Pushback: Router-Based Defense against DDoS Attacks,” Network and Distributed System Security Symposium (NDSS), San Diego, California, Feb. 6-8, 2002; ISO 3166 Report, AS Resource http://bgp.potaroo.net/ iso3166/ascc.html; Allocations, Aug. 8, 2006,

[Gui05] [Hal98] [Han03] [He 04]

[Her00] [Hou01] [Hua01]

[Hus03] [Hwa05]

[Ioa02]

[ISO06] [Jia05] [Jin03]

H. Jiang and C. Dovrolis, “Why is The Internet Traffic Bursty in Short Time Scales?” SIGMETRICS’05, June 6-10, 2005, Banff, Alberta, Canada; C. Jin, H. Wang, and K. G. Shin, "Hop-count Filtering: An Effective Defense Against Spoofed DDoS Traffic", Proceedings of the 10th ACM Conference on

150

Computer and Communication Security, (CCS 2003), Washington D.C., USA, pp.30-41, October 27-31, 2003; [Jun02] J. Jung, B. Krishnamurthy, and M. Rabinovich, “Flash Crowds and Denial-ofService Attacks: Characterization and Implications for CDNs and Web Sites,” Proceedings of Int’l World Wide Web Conference, ACM Press, 2002; S. Kandula, D. Katabi, M. Jacob, and A. Berger, "Botz-4-Sale: Surviving Organized DDoS Attacks That Mimic Flash Crowds", 2nd Symposium on Networked Systems Design and Implementation (NSDI), Boston, MA, May 2005; D. Katz, "IP Router Alert Option," IETF RFC 2113, February 1997; D. Kawamoto, “Blackmailers Try to Black Out Million Dollar Homepage,” ZDNet News, Jan. 18, 2006, http://news.zdnet.com/2100-1009_226028131.html; S. Kent and R. Atkinson, “Security Architecture for the Internet Protocol,” Network Working Group, RFC 2401, IETF, 1998; S. Kent and R. Atkinson, “IP Authentication Header,” Network Working Group, RFC 2402, IETF, 1998; S. Kent and R. Atkinson, “IP Encapsulating Security Payload (ESP),” Network Working Group, RFC 2406, IETF, 1998; Y. Kim, W. C. Lau, M. C. Chuah, and H. J. Chao, “PacketScore: StatisticsBased Overload Control Against Distributed Denial of-Service Attacks,” INFOCOM 2004; J. Kohl and C. Neuman, “The Kerberos Network Authentication Service (V5),” Network Working Group, RFC 1510, IETF, 1993; H. Krawczyk, M. Bellare, and R. Canetti, “HMAC: Keyed-Hashing for Message Authentication,” Network Working Group, RFC 2104, IETF, 1997; H.T. Kung and S.Y. Wang, “TCP Trunking: Design, Implementation and Performance”, Proc. ICNP, 1999; A. Kuzmanovic and E. Knightly, “Low-Rate TCP-Targeted Denial of Service Attacks—The Shrew vs. the Mice and Elephants,” Proc.of 2003 ACM SIGCOMM, Karlsruhe, Germany, August 25-29, 2003; Y. K. Kwok, R. Tripathi, Y. Chen, and K. Hwang, “ Hawk: Halting Anomaly with Weighted Choking to Rescue Well-Behaved TCP Sessions from Shrew DoS Attacks”, IEEE Int’l Conference on Distributed Computing Systems, (ICDCS-2005), Zhangjiaje, China, August 2005;

[Kan05]

[Kat97] [Kaw06]

[Ken98a] [Ken98b] [Ken98c] [Kim04]

[Koh93] [Kra97] [Kun99] [Kuz03]

[Kwo05]

151

[Lan03] [Law05]

K. C. Lan, A. Hussain, and D. Dutta, “The Effect of Malicious Traffic on the Network,” Proc. PAM, La Jolla, Apr. 6-8, 2003; T.K.T. Law, J.C.S. Lui, and D.K.Y. Yau, "You can run, but you can't hide: an effective statistical methodology to trace back DDoS attackers," IEEE Trans. on Parallel and Distributed Systems, Vol. 16, no. 9, Sept. 2005; J. Lemon, “Resisting SYN Flooding DoS Attacks with a SYN Cache”, Proceedings of USENIX BSDConf 2002, February, 2002;

[Lem02]

[Lem01a] R. Lemos, “Attack Knocks out Microsoft Websites,” CNET News.com, Jan. 25, 2001, http://news.com.com/2100-1001-251573.html; [Lem01b] R. Lemos, “A Year Later, DDoS Attacks Still a Major Web Threat,” CNET News, Feb. 7, 2001, http://news.com.com/2009-1001-252187.html; [Ley04] [Lub04] [Luo05a] J. Leyden, “WorldPay Struggles Under DDoS Attack (again),” the Register, Oct. 10, 2004, http://www.theregister.co.uk/2004/10/04/worldpay_ddos/; M. Luby and V. Goyal, “Wave and Equation Based Rate Control (WEBRC) Building Block,” IETF RFC 3738, April 2004; X. Luo and R. Chang, “On a New Class of Pulsing Denial-of-Service Attacks and the Defense,” Proc. of Network and Distributed System Security Symposium (NDSS'05), San Diego, CA., Feb. 2-5, 2005; X. Luo, R. Chang, and E. Chan, “Performance Analysis of TCP/AQM Under Denial-of-Service Attacks,” in Proc. of IEEE MASCOTS, Atlanta, GA., Sept. 2005; R. Mahajan, S. Bellovin, S. Floyd, J. Ioannidis, V. Paxson, and S. Shenker, "Controlling High Bandwidth Aggregates in the Network," Computer Comm. Review, July 2002; A. Mankin, D. Massey, C. Wu, S. Felix Wu, and L. Zhang, “On Design and Evaluation of Intention-Driven ICMP Traceback,” Proceedings of Computer Communications and Networks, 2001; C. Marsan, “DDoS Attack Highlights Net Problems,” Network World News, Oct. 28, 2002, http://www.networkworld.com/news/2002/1028ddos.html; S. McCanne and S. Floyd, http://www.isi.edu/nsnam/ns/, 1997; NS-2 Network Simulator,

[Luo05b]

[Mah02]

[Man01]

[Mar02] [McC97] [Mir03]

J. Mirkovic, M. Robinson, P. Reiher, and G. Kuenning, “Alliance Formation for DDoS Defense,” Proc. of the New Security Paradigms Workshop, ACM SIGSAC, August 2003;

152

[Mir04]

J. Mirkovic and P. Reiher, “A Taxonomy of DDoS Attack and DDoS Defence Mechanisms,” ACM Computer Communications Review, vol. 34, no. 2, April 2004; J. Mirkovic and P. Reiher, "D-WARD: A Source-End Defense Against Flooding DoS Attacks," IEEE Trans. on Dependable and Secure Computing, July 2005; J. Mirkovic, M. Robinson, P. Reiher and G. Oikonomou, “Distributed Defense Against DDOS Attacks,” Technical Report CIS-TR-2005-02, CIS Department, University of Delaware, 2005; T. Monk and K. Claffy, “Cooperation in Internet Data Acquisition and Analysis,” Coordination and Administration of the Internet Workshop, Cambridge, MA., Sept. 8-10, 1996, (CAIDA Project), http://www.caida.org/; D. Moore, G. Voelker, and S. Savage, “Inferring Internet Denial-of-Service Activity,” Proc. of the 10th USENIX Security Symposium, 2001; J. Myers, “Simple Authentication and Security Layer (SASL),” Network Working Group, RFC 2222, IETF, 1997; N. Naoumov and K. Ross, “Exploiting P2P Systems for DDoS Attacks,” International Workshop on Peer-to-Peer Information Management (keynote address), Hong Kong, May 2006; P. Ning, S. Jajodia, and X. S. Wang, “Abstraction-based Intrusion Detection in Distributed Environment”, ACM Trans. On Information and System Security, Nov. 2001, pp. 407-452; D. E. Ott, T. Sparks, and K. Mayer-Patel, “Aggregate Congestion Control for Distributed Multimedia Applications,” Proc. INFOCOM, 2004; R. Pan, B. Prabhakar, and K. Psounis, “CHOKe: A Stateless Active Queue Management Scheme for Approximating Fair Bandwidth Allocation,” Proc. INFOCOM 2000, Vol. 2, Apr. 2000, pp. 942–951; C. Papadopoulos, R. Lindell, J. Mehringer, A. Hussain, R. Govindan, "COSSACK: Coordinated Suppression of Simultaneous Attacks," Proc. of DISCEX III, 2003; K. Park and H. Lee, “On the Effectiveness of Route-Based Packet Filtering for Distributed DoS Attack Prevention in Power-Law Internet,” Proc. ACM SIGCOMM 2001; C. Partridge, D. Cousins, A. Jackson, R. Krishnan, T. Saxena, and W. Strayer, “Using Signal Processing to Analyze Wireless Data Traffic,” Proc. of ACM Workshop on Wireless Security, Atlanta, GA, Sept. 28-28, 2002;

[Mir05] [Mir05b]

[Mon96]

[Moo01] [Mye97] [Nao06]

[Nin01]

[Ott04] [Pan00]

[Pap03]

[Par01]

[Par02]

153

[Pax99] [Pax00] [Pen03]

V. Paxon, “Bro: A System for Detecting Network Intruders in Real-Time,” Computer Networks, Vol. 31, No. 23-24, 1999; V. Paxson and M. Allman, “Computing TCP’s Retransmission Timer,” Internet RFC 2988, November 2000; T. Peng, L. Christopher, and R. Kotagiri, "Detecting Distributed Denial of Service Attacks by Sharing Distributed Beliefs," The Eighth Australasian Conference on Information Security and Privacy (ACISP 2003), Wollongong, Australia, July 9-11, 2003; T. Peng, L. Christopher, and R. Kotagiri, “Detecting Distributed Denial of Service Attack Using Source IP Address Monitoring,” IEEE INFOCOM 2004, Hong Kong; D. Piper, “The Internet IP Security Domain of Interpretation fro ISAKMP,” Network Working Group, RFC 2407, IETF, 1998; J. Postel, “Internet Control Message Protocol,” Network Working Group, RFC 792, IETF, 1981; K. Poulsen, “Feds Bust DDoS ‘Mafia’,” The Register, Aug. 27, 2004, http://www.theregister.co.uk/2004/08/27/ddos_mafia_busted/; P. Pradhan, T. Chiueh, and A. Neogi, “Aggregate TCP Congestion Control Using Multiple Network Probing,” Proc. ICDCS, 2000; M. Qin and K. Hwang. “Frequent Episode Rules for Internet Traffic Analysis and Anomaly Detection”, Proc. of IEEE Network Computing and Applications, (NCA2004), Cambridge, MA. Sept. 2004; B. Ramsdell, “S/MIME Version 3 Message Specification,” Network Working Group, RFC 2633, IETF, 1999; R. Rejaie, M. Handley, and D. Estrin, “RAP: An End-to-End Rate-Based Congestion Control Mechanism for Real-Time Streams in the Internet,” Proc. INFOCOM, 1999; P. Roberts, “Al-Jazeera Hobbled by DDoS Attack: News Site Targeted for Second Day,” Infoworld, March 26, 2003, http://www.infoworld.com/article/ 03/03/26/HNjazeera_1.html; T. Ryutov, L. Zhou, C. Neuman, T. Leithead, and K. E. Seamons, "Adaptive Trust Negotiation and Access Control," ACM Symposium on Access Control Models and Technologies (SACMAT'05), Stockholm, Sweden, June 1-3, 2005; SANS Web Pages, “Egress Filtering,” http://www.sans.org/y2k/egress.htm, Feb. 2000;

[Pen04]

[Pip98] [Pos81] [Pou04] [Pra00] [Qin04]

[Ram99] [Rej99]

[Rob03]

[Ryu05]

[San00]

154

[San05]

T. Sanders, “Cops Smash 100,000 Node Botnet: Largest Zombie Army Ever Detected,” vnunet.com, Oct. 10, 2005, http://www.vnunet.com/vnunet/news/ 2143475/dutch-police-foil-100-node; S. Savage, D. Wetherall, A. Karlin, and T. Anderson, "Practical Network Support for IP Traceback", ACM SIGCOMM 2000, August, 2000; Stefan Savage, David Wetherall, Anna Karlin and Tom Anderson, "Network Support for IP Traceback", ACM/IEEE Transactions on Networking, Vol.9, No.3, pp.226-237, June, 2001 C. Schuba, I. Krsul, M. Kuhn, G. Spafford, A. Sundaram, and D. Zamboni, “Analysis of a denial of service attack on TCP,” Proc. of IEEE Symp. on Security and Privacy, May 1997; D. Schuehler and J. Lockwood, "A Modular System for FPGA-based TCP Flow Processing in High-Speed Networks", 14th International Conference on Field Programmable Logic and Applications (FPL), Springer LNCS 3203, Antwerp, Belgium, August 2004, pp. 301-310; G. Siganos, M. Faloutsos, P. Faloutsos, and C. Faloutsos, "Power-Laws and the AS-level Internet Topology", ACM/IEEE Trans. on Networking, pp. 514-524, Aug. 2003; A. Snoren, C. Partridge, L. Sanchez, C. Jones, F. Tchakountio, S. Kent, and W. Strayer, “Hash-based IP Traceback,” ACM SIGCOMM 2001, 2001; J. Sommers and P. Barford, “Self-Configuring Network Traffic Generation,” in Proc. of ACM Internet Measurement Conference, Taormina, Sicily, Italy, Oct. 25-27, 2004; H. Song and J.W. Lockwood, "Efficient Packet Classification for Network Intrusion Detection using FPGA", International Symp. on Field-Programmable Gate Arrays (FPGA'05), Monterey, California, Feb 20-22, 2005; A. Soule, K. Salamatian, and N. Taft, “Combining Filtering and Statistical Methods for Anomaly Detection,” in Proc. of ACM Internet Measurement Conf., Berkeley, Oct. 2005; S. M. Specht and R. B. Lee, “Distributed Denial of Service: Taxonomies of Attacks, Tools and Countermeasures,” Proc. of Parallel and Dist. Comp. Systems, San Francisco, Sept. 15-17, 2004; E. Spitznagel, D. Taylor, and J. Turner, “Packet Classification Using Extended TCAMs,” in Proceedings of IEEE International Conference on Network Protocols (ICNP), 2003;

[Sav00] [Sav01]

[Sch97]

[Sch04]

[Sig03]

[Sno01] [Som04]

[Son05]

[Sou05]

[Spe04]

[Spi03]

155

[Spr03] [Sta05a]

N. Spring, D. Wetherall, and D. Ely, “Robust Explicit Congestion Notification (ECN) Signaling with Nonces,” IETF RFC 3540, June 2003; A. Stavrou, D. Cook, W. Morein, A. Keromytis, V. Misra, and D. Rubenstein, “WebSOS: An Overlay-based System for Protecting Web Servers from Denial of Service Attacks,” Journal of Communication Networks, special issue on Web and Network Security, Vol. 48, No. 5, August 2005; A. Stavrou, A. Keromytis, J. Neih, V. Misra, and D. Rubenstein, “MOVE: An End-to-End Solution to Network Denial of Service,” Proceedings of Network and Distributed System Security Symposium (NDSS’05), San Diego, CA., USA, Feb. 3-4, 2005; R. Stone, “CenterTrack: An IP Overlay Network for Tracking DoS Floods,” 9th USENIX Security Symposium, August 2000; Y. Sugawara, M. Inaba, and K. Hiraki, "Over 10Gbps String Matching Mechanism for Multi-stream Packet Scanning Systems", 14th International Conference on Field Programmable Logic and Applications (FPL), Springer LNCS 3203, Antwerp, Belgium, August 2004, pp. 484-493; H. Sun, J. Lui, and D. Yau, “Defending Against Low-rate TCP Attacks: Dynamic Detection and Protection,” in Proc. of 2004 IEEE Int’l Conf. on Network Protocols (ICNP), Berlin, Germany, Oct. 5-8, 2004; M. Sung and J. Xu, “IP Traceback-Based Intelligent Packet Filtering: A Novel Technique for Defending Against Internet DDoS Attacks,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 9, Sept. 2003; D. Taylor and J. Turner, "Scalable Packet Classification using Distributed Crossproducting of Field Labels", IEEE INFOCOM 2005; S. Templeton and K. Levitt, "Detecting Spoofed Packets", DARPA Information Survivability Conference and Exposition, April 22-24, 2003; R. Thayer, N. Doraswamy, and R. Glenn, “IP Security Document Roadmap,” Network Working Group, RFC 2411, IETF, 1998; R. Thomas, B. Mark, T. Johnson, and J. Croall, "NetBouncer: Client-legitimacybased High-performance DDoS Filtering", DARPA Information Survivability Conference and Exposition III, Vol.1, pp.14-25, April 22-24, 2003; M. Waldvogel, "GOSSIB vs. IP Traceback Rumors", 18th Annual Computer Security Applications Conference, San Diego, California, USA, pp.5-13, December 09-13, 2002; M. Walfish, M. Vutukuru, H. Balakrishnan, D. Karger, and S. Shenker "DDoS Defense by Offense," ACM SIGCOMM 2006, Pisa, Italy, September 2006;

[Sta05b]

[Sto00] [Sug04]

[Sun04]

[Sun03]

[Tay05] [Tem03] [Tha98] [Tho03]

[Wal02]

[Wal06]

156

[Wan03a] B. Wang and H. Schulzrinne, “A Denial-of-Service-Resistant IP Traceback Approach,” 3rd New York Metro Area Networking Workshop (NYMAN 2003), 2003; [Wan03] H. Wang and K. G. Shin, “Transport-Aware IP Routers: A Built-In Protection Mechanism to Counter DDoS Attacks,” IEEE Trans. Parallel and Distributed Systems, vol. 14, no. 9, Sept. 2003; H. Wang, D. Zhang, and K. Shin, “Change-Point Monitoring for the Detection of DoS Attacks,” IEEE Trans. on Dependable and Secure Computing, Vol. 1, Oct.-Dec., 2004; X. Wang, S. Chellappan, P. Boyer, and D. Xuan, “On the Effectiveness of Secure Overlay Forwarding Systems under Intelligent Distributed DoS Attacks,” IEEE Trans. on Parallel and Distributed Systems, Vol. 17, July 2006; J. Wray, “Generic Security Service API Version 2: C-bindings,” Network Working Group, RFC 2744, IETF, 2000; A. Yaar, A. Perrig, and D. Song, "FIT: Fast Internet Traceback," INFOCOM 2005, Miami, Florida, March 13-17, 2005; D. Yau, J. Lui, F. Liang, and Y. Yam, “Defending Against Distributed Denialof-Service Attacks with Max-Min Fair Server-Centric Router Throttles,” IEEE/ACM Transactions on Networking, Vol. 13, No. 1, February 2005; T. Ylonen and C. Lonvick, “The Secure Shell (SSH) Protocol Architecture,” Network Working Group, RFC 4251, IETF, 2006;

[Wan04]

[Wan06]

[Wra00] [Yaa05] [Yau05]

[Ylo06]

157

Appendices A. Publications
Book Chapter Contribution
[1]

Y. Chen, M. Cai, and K. Hwang, “Internet Worm and DDoS Defense with Dynamic Hardware and Network Processors,” contribution to Hardware-based Security, edited by Ruby Lee and Sean Smith, to be published by Morgan Kaufman Publishers in 2006.

Journal Publications
[1]

Y. Chen, K. Hwang, and W. Ku, “Distributed Change Detection of DDoS Attacks over Multiple Network Domains”, submitted to IEEE Transaction on Parallel and Distributed Systems, August 14, 2006. Under Review.

[2]

Y. Chen and K. Hwang, “Collaborative Detection and Filtering of Shrew DDoS Attacks using Spectral Analysis,” Journal of Parallel and Distributed Computing, special issue on Security in Grids and Distributed Systems, Vol. 66, Issue 9, September 2006.

[3]

K. Hwang, Y.-K. Kwok, S. Song, M. Cai, Yu Chen, and Ying Chen, “Security Binding and Worm/DDoS Defense Infrastructure for Trusted Grid Computing,” International Journal on Critical Infrastructures, 2005.

[4]

M. Cai, K. Hwang, Y.-K. Kwok, S. Song, and Y. Chen, “Collaborative Internet Worm Containment”, IEEE Security and Privacy Magazine, May/June 2005.

Conference/Workshop Publications
[1]

Y. Chen and K. Hwang, “Collaborative Change Detection of DDoS Attacks on Community and ISP Networks,” the 2006 IEEE International Symposium on

158

Collaborative Technologies and Systems (CTS’06), Las Vegas, Nevada, USA, May. 15-17, 2006.
[2]

Y. Chen, K. Hwang, and Y.-K. Kwok, “Filtering of Shrew DDoS Attacks in Frequency Domain,” the First IEEE LCN Workshop on Network Security (WoNS), in conjunction with the LCN 2005, Sydney, Australia, Nov. 15-17, 2005.

[3]

Y.-K. Kwok, R. Tripathi, Y. Chen, and K. Hwang, “HAWK: Halting Anomalies with Weighted Choking to Rescue Well-Behaved TCP Sessions from Shrew DoS Attacks,” the 2005 International Conference on Computer Networks and Mobile Computing (ICCNMC’05), Zhangjiajie, China, Aug. 2-4, 2005.

[4]

Y. Chen, Y.-K. Kwok, and K. Hwang, “MAFIC: Adaptive Packet Dropping for Cutting Malicious Flows to Push Back DDoS Attacks,” the 2nd International Workshop on Security in Distributed Computing Systems (SDCS’05), in conjunction with ICDCS 2005, Columbus, OH, USA, June 6-10, 2005.

[5]

K. Hwang, Y.-K. Kwok, S. Song, M. Cai, R. Zhou, Yu Chen, Ying Chen, and X. Lou, “GridSec: Trusted Grid Computing with Security Binding and Self-Defense against Network Worms and DDoS Attacks,” in Proceedings of International Workshop on Grid Computing Security and Resource Management (GSRM-2005), in conjunction with the ICCS-2005, Atlanta, GA, May 22-24, 2005.

159

Appendices B. DETER Experiment Configure

160

Appendices C. DETER Experiment JAVA Code
(Router Side)

//This is part of the router side JAVA code import java.net.*; import java.io.*; public class CATClient4 { public static final int Speriod = 500; public static void main(String[] args) throws IOException { boolean first1 = true, first2 = true; long start, stop, elapsed; start = System.currentTimeMillis(); <========== while(true) client loop { while(true) { stop = System.currentTimeMillis(); elapsed = stop - start; if (elapsed >= Speriod) break; } start = stop; //System.out.println("current Time = " + stop); InetAddress addr = InetAddress.getByName("CAT4.try.NetShield.isi.deterlab.net"); System.out.println("addr = " + addr); Socket socket = null; try { socket = new Socket(addr, 8080); // Guard everything in a try-finally to make sure that the socket is closed: } catch (SocketException e) { System.out.println("==== Exception happen ... ===="); continue; } // for ip detection String s1, s2, temp, previous, inter = new String(); String[] IPtable = new String[10]; // //

161

int i, c= 0, counter = 0; // for packet counting String s1g, s2g, s3g, s4g, s5g, tempg, interf = new String(); //String[] s3g = new String[30]; long packetR = 0, packetT =0; long packetCR, packetCT; // packets received this period char sign =0;

// detect the interface //if (first1) //{ try { counter = 0; BufferedReader in = new BufferedReader( // <========== // <========== //new FileReader("ifconfig2.dat")); //new FileReader("ifconfig3.dat")); new FileReader("ipmap.dat")); temp = in.readLine(); inter = temp.substring(0, 4); s1 = in.readLine(); s2 = s1.substring(20, 29); //System.out.println("The interface is " + inter + " and IP is " + s2); IPtable[0] = s2 + inter; for (i = 0; i < 8; i++) temp = in.readLine(); inter = temp.substring(0, 4); s1 = in.readLine(); s2 = s1.substring(20, 29); //System.out.println("The interface is " + inter + " and IP is " + s2); counter++; previous =s2; IPtable[1] = s2 + inter; if (!previous.equals("127.0.0.1")) { for (i = 0; i < 8; i++) temp = in.readLine(); inter = temp.substring(0, 4);

162

s1 = in.readLine(); s2 = s1.substring(20, 29); //System.out.println("The interface is " + inter + " and IP is " + s2); counter++; previous =s2; IPtable[2] = s2 + inter; } else IPtable[2] = "10.0.00.0 000"; if (!previous.equals("127.0.0.1")) { for (i = 0; i < 8; i++) temp = in.readLine(); inter = temp.substring(0, 4); s1 = in.readLine(); s2 = s1.substring(20, 29); //System.out.println("The interface is " + inter + " and IP is " + s2); counter++; previous =s2; IPtable[3] = s2 + inter; } else IPtable[3] = "10.0.00.0 000"; if (!previous.equals("127.0.0.1")) { for (i = 0; i < 8; i++) temp = in.readLine(); inter = temp.substring(0, 4); s1 = in.readLine(); s2 = s1.substring(20, 29); //System.out.println("The interface is " + inter + " and IP is " + s2); counter++; previous = s2; IPtable[4] = s2 + inter; } else IPtable[4] = "10.0.00.0 000"; if (!previous.equals("127.0.0.1")) { for (i = 0; i < 8; i++) temp = in.readLine(); inter = temp.substring(0, 4); s1 = in.readLine();

163

s2 = s1.substring(20, 29); //System.out.println("The interface is " + inter + " and IP is " + s2); counter++; previous = s2; IPtable[5] = s2 + inter; } else IPtable[5] = "10.0.00.0 000"; in.close(); } catch(IOException e) { System.err.println("End of stream"); } //first1 = false; //}//if(first1) try { System.out.println("socket = " + socket); BufferedReader in = new BufferedReader( new InputStreamReader(socket.getInputStream())); // Output is automatically flushed by PrintWriter: PrintWriter out = new PrintWriter( new BufferedWriter( new OutputStreamWriter( socket.getOutputStream())),true); //if (first2) //{ //for (i = 0; i <= counter; i++) for (i = 0; i < 5; i++) out.println(IPtable[i]); //first2 = false; //} //================================================== //Catch the hostname try { BufferedReader in3 = new BufferedReader( new FileReader("host.dat")); String hostname = new String(); //String tmp = new String(); //tmp = in3.readLine(); //hostname = tmp.substring(0, 3); hostname = in3.readLine(); //System.out.println("The hostname is " + hostname); out.println(hostname); //System.out.println(); in3.close();

164

} catch(IOException e) { System.err.println("End of stream"); } //==========================================================

try { BufferedReader in2 = new BufferedReader( //new FileReader("packet2.dat")); new FileReader("/proc/net/dev")); for (i = 0; i < 3; i++) tempg = in2.readLine(); s1g = in2.readLine(); //System.out.println(s1g); out.println(s1g); s2g = in2.readLine(); //System.out.println(s2g); out.println(s2g); s3g = in2.readLine(); //System.out.println(s3g); out.println(s3g); s4g = in2.readLine(); //System.out.println(s4g); out.println(s4g); s5g = in2.readLine(); //System.out.println(s5g); out.println(s5g); in2.close(); } catch(IOException e) { System.err.println("End of stream"); } //================================================== try { String str = in.readLine(); //System.out.println(str); out.println("END"); } catch (SocketException e) { System.err.println(e); continue; } } finally { //try // <========== // <==========

165

//{ // <=========================== // Thread.currentThread().sleep(500, 1); (3000) //}catch (Exception e) //{ // System.err.println(e); //} //System.out.println("closing...");

// delay

//System.out.println("===== Processing Time " + (System.currentTimeMillis()-start)); //System.out.println(" "); //while(true) //{ // stop = System.currentTimeMillis(); // elapsed = stop - start; // if (elapsed >= Speriod) // break; //} //start = stop; socket.close(); } System.out.println("===== Processing Time " + (System.currentTimeMillis()-start)); System.out.println(" "); }//while client loop } } ///:~

//

166

Appendices D. DETER Experiment JAVA Code
(Server Side)

// This is part of the server side code of DETER experiment import import import import java.io.*; java.net.*; java.lang.*; java.util.Timer;

class router { String[] interfaceID = new String[5]; String[] IPs = new String[5]; String[] ASIPs = new String[5]; // String[] neighbors = new String[4]; int[] neighbors = new int[5]; // neighbor in logical topology String Hostname = new String(); String SelfIP = new String(); // IP address of this router double[][] pktavg = new double[5][2]; // average packet number of each interface double[][] pktdfa = new double[5][2]; // deviation from the average double[][] pktdr = new double[5][5]; // deviation ratio double[][] pktor = new double[5][5]; // offset ratio int[][] curpkt = new int[5][2]; // current packet number int[][] prepkt = new int[5][2]; // previous packet number int[] p_nb = new int[5]; int up_no; int dn_no; int[] up_r = new int[5]; int[] dn_r = new int[5]; int is_p; } public class CATServer15 { public static final int PORT = 8080; public static final double alpha = 0.1; history average public static final double beta = 2.0; to catch suspicious patterns // //the sesitivity of //the threshold of DFA // the flag whether this router is ATR // the physical neighbors

167

// Tree construction ============================================= // =============================================================== public static void main(String[] args) throws IOException { // <========== // <========== //InetAddress addr = InetAddress.getByName("127.0.0.15"); // CAT Server IP 127.0.0.15 Router# 15 InetAddress addr = InetAddress.getByName("CAT15.try.NetShield.isi.deterlab.net"); ServerSocket s = new ServerSocket(8080, 100, addr); System.out.println("Started: " + s); FileOutputStream result = new FileOutputStream ("suspic15.dat"); //Output files FileOutputStream record = new FileOutputStream ("CAT_Record15.txt"); //String[] IPtable = new String[5]; int i, j, k, p, q, r, interm, thishost = 0, counter = 0; int scan = 0, scan2 = 1; int Ycounter = 0; // counter of cycle number int Rcounter = 0, Tcounter = 0, TimerCounter = 0; int[] Reply = new int[40]; String[] IPtree = new String[100000]; router[] Routers = new router[40]; for (j =0; j < Routers.length; j++) Routers[j] = new router();

// initialize routers

String IP1, IP2, IP3, IP4, IP5 = new String(); String IF1, IF2, IF3, IF4, IF5 = new String(); String IFp1, IFp2, IFp3, IFp4, IFp5, thisIP = new String(); String pack1R, pack1T, pack2R, pack2T, pack3R, pack3T, pack4R, pack4T, pack5R, pack5T = new String(); String hostname = new String(); String str = new String(); IP1 = "0"; IP2 = "0"; IP3 = "0"; IP4 = "0"; IP5 = "0"; IF1 = "0"; IF2 = "0"; IF3 = "0"; IF4 = "0"; IF5 = "0"; thisIP = "0"; int ipack1R, ipack1T, ipack2R, ipack2T, ipack3R, ipack3T; int ipack4R, ipack4T, ipack5R, ipack5T; int CCounter = 0; int[] start_char = new int[16]; int[] end_char = new int[16]; int cur_char = 0;

168

int cur_str = 0; //periods // Initialization ============================================== for (j = 0; j < 8; j++) for (p = 0; p < 5; p++) for (q = 0; q < 5; q++) { Routers[j].pktdr[p][q] = 0.1; Routers[j].pktor[p][q] = 0.1; } for (j = 0; j < 8; j++) { Reply[j] = 0; Routers[j].up_no = 0; Routers[j].dn_no = 0; Routers[j].is_p = 0; for (k = 0; k < 5; k++) { Routers[j].up_r[k] = 999; Routers[j].dn_r[k] = 999; Routers[j].p_nb[k] = 999; } }

//Router information definition ============================ R1500 Routers[0].IPs[0] Routers[0].IPs[1] Routers[0].IPs[2] Routers[0].IPs[3] Routers[0].IPs[4] = = = = = "10.15.10.2"; "10.15.11.2"; "10.15.1.2"; "10.1.61.2"; "192.168.1"; = = = = = 1504; 1503; -1; -2; -3;

Routers[0].neighbors[0] Routers[0].neighbors[1] Routers[0].neighbors[2] Routers[0].neighbors[3] Routers[0].neighbors[4] Routers[0].ASIPs[0] Routers[0].ASIPs[1] Routers[0].ASIPs[2] Routers[0].ASIPs[3] Routers[0].ASIPs[4] = = = = =

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[0].Hostname = "r1500.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++)

169

{ Routers[0].pktavg[p][q] Routers[0].curpkt[p][q] Routers[0].prepkt[p][q] Routers[0].pktdfa[p][q] } = = = = 0; 0; 0; 0.1;

//======================================================= Routers[2].IPs[0] Routers[2].IPs[1] Routers[2].IPs[2] Routers[2].IPs[3] Routers[2].IPs[4] = = = = = "10.15.11.3"; "10.15.15.2"; "10.15.17.2"; "10.0.00.0"; "192.168.1"; = = = = = 1500; 1507; -1; -2; -3;

R1503

Routers[2].neighbors[0] Routers[2].neighbors[1] Routers[2].neighbors[2] Routers[2].neighbors[3] Routers[2].neighbors[4] Routers[2].ASIPs[0] Routers[2].ASIPs[1] Routers[2].ASIPs[2] Routers[2].ASIPs[3] Routers[2].ASIPs[4] = = = = =

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[2].Hostname = "r1503.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++) { Routers[2].pktavg[p][q] = 0; Routers[2].curpkt[p][q] = 0; Routers[2].prepkt[p][q] = 0; Routers[2].pktdfa[p][q] = 0.1; } //======================================================= Routers[3].IPs[0] Routers[3].IPs[1] Routers[3].IPs[2] Routers[3].IPs[3] Routers[3].IPs[4] = = = = = "10.15.10.3"; "10.15.12.2"; "10.15.13.2"; "10.15.14.2"; "192.168.1"; = = = = = 1500; 1505; 1506; 1507; -1; R1504

Routers[3].neighbors[0] Routers[3].neighbors[1] Routers[3].neighbors[2] Routers[3].neighbors[3] Routers[3].neighbors[4]

Routers[3].ASIPs[0] = "10.3.00.0";

170

Routers[3].ASIPs[1] Routers[3].ASIPs[2] Routers[3].ASIPs[3] Routers[3].ASIPs[4]

= = = =

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[3].Hostname = "r1504.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++) { Routers[3].pktavg[p][q] = 0; Routers[3].curpkt[p][q] = 0; Routers[3].prepkt[p][q] = 0; Routers[3].pktdfa[p][q] = 0.1; } //======================================================= R1505 Routers[4].IPs[0] Routers[4].IPs[1] Routers[4].IPs[2] Routers[4].IPs[3] Routers[4].IPs[4] = = = = = "10.15.12.3"; "10.15.21.3"; "10.0.00.0"; "10.0.00.0"; "192.168.1"; = = = = = 1504; 805; -1; -2; -3;

Routers[4].neighbors[0] Routers[4].neighbors[1] Routers[4].neighbors[2] Routers[4].neighbors[3] Routers[4].neighbors[4] Routers[4].ASIPs[0] Routers[4].ASIPs[1] Routers[4].ASIPs[2] Routers[4].ASIPs[3] Routers[4].ASIPs[4] = = = = =

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[4].Hostname = "r1505.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++) { Routers[4].pktavg[p][q] = 0; Routers[4].curpkt[p][q] = 0; Routers[4].prepkt[p][q] = 0; Routers[4].pktdfa[p][q] = 0.1; } //=================================================== Routers[5].IPs[0] Routers[5].IPs[1] Routers[5].IPs[2] Routers[5].IPs[3] Routers[5].IPs[4] = = = = = "10.15.99.2"; "10.15.13.3"; "10.15.19.2"; "10.0.00.0"; "192.168.1"; R1506

171

Routers[5].neighbors[0] Routers[5].neighbors[1] Routers[5].neighbors[2] Routers[5].neighbors[3] Routers[5].neighbors[4] Routers[5].ASIPs[0] Routers[5].ASIPs[1] Routers[5].ASIPs[2] Routers[5].ASIPs[3] Routers[5].ASIPs[4] = = = = =

= = = = =

606; 1504; 1510; -1; -2;

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[5].Hostname = "r1506.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++) { Routers[5].pktavg[p][q] = 0; Routers[5].curpkt[p][q] = 0; Routers[5].prepkt[p][q] = 0; Routers[5].pktdfa[p][q] = 0.1; } //=================================================== Routers[6].IPs[0] Routers[6].IPs[1] Routers[6].IPs[2] Routers[6].IPs[3] Routers[6].IPs[4] = = = = = "10.15.14.3"; "10.15.15.3"; "10.15.20.2"; "10.0.00.0"; "192.168.1"; = = = = = 1504; 1503; 1509; -1; -2; R1507

Routers[6].neighbors[0] Routers[6].neighbors[1] Routers[6].neighbors[2] Routers[6].neighbors[3] Routers[6].neighbors[4] Routers[6].ASIPs[0] Routers[6].ASIPs[1] Routers[6].ASIPs[2] Routers[6].ASIPs[3] Routers[6].ASIPs[4] = = = = =

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[6].Hostname = "r1507.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++) { Routers[6].pktavg[p][q] = 0; Routers[6].curpkt[p][q] = 0; Routers[6].prepkt[p][q] = 0; Routers[6].pktdfa[p][q] = 0.1; } //==================================================== R1509

172

Routers[7].IPs[0] Routers[7].IPs[1] Routers[7].IPs[2] Routers[7].IPs[3] Routers[7].IPs[4]

= = = = =

"10.12.22.3"; "10.15.18.2"; "10.15.20.3"; "10.0.00.0"; "192.168.1"; = = = = = 1207; 1510; 1507; -1; -2;

Routers[7].neighbors[0] Routers[7].neighbors[1] Routers[7].neighbors[2] Routers[7].neighbors[3] Routers[7].neighbors[4] Routers[7].ASIPs[0] Routers[7].ASIPs[1] Routers[7].ASIPs[2] Routers[7].ASIPs[3] Routers[7].ASIPs[4] = = = = =

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[7].Hostname = "r1509.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++) { Routers[7].pktavg[p][q] = 0; Routers[7].curpkt[p][q] = 0; Routers[7].prepkt[p][q] = 0; Routers[7].pktdfa[p][q] = 0.1; } //==================================================== Routers[1].IPs[0] Routers[1].IPs[1] Routers[1].IPs[2] Routers[1].IPs[3] Routers[1].IPs[4] = = = = = "10.15.18.3"; "10.15.19.3"; "10.0.00.0"; "10.0.00.0"; "192.168.1"; = = = = = 1509; 1506; -1; -2; -3; R1510

Routers[1].neighbors[0] Routers[1].neighbors[1] Routers[1].neighbors[2] Routers[1].neighbors[3] Routers[1].neighbors[4] Routers[1].ASIPs[0] Routers[1].ASIPs[1] Routers[1].ASIPs[2] Routers[1].ASIPs[3] Routers[1].ASIPs[4] = = = = =

"10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0"; "10.3.00.0";

Routers[1].Hostname = "r1510.try.netshield.isi.deterlab.net"; for (p = 0; p < 5; p++) for (q = 0; q < 2; q++) {

173

Routers[1].pktavg[p][q] Routers[1].curpkt[p][q] Routers[1].prepkt[p][q] Routers[1].pktdfa[p][q] }

= = = =

0; 0; 0; 0.1;

//================================================================

// Router information definition ================================= while(true){ try { // Blocks until a connection occurs: Socket socket = s.accept(); counter = 0; try { System.out.println ( "Connection accepted: "+ socket); BufferedReader in = new BufferedReader( new InputStreamReader( socket.getInputStream())); // Output is automatically flushed by PrintWriter: PrintWriter out = new PrintWriter( new BufferedWriter( new OutputStreamWriter( socket.getOutputStream())),true); System.out.println("The value of CCounter is " + CCounter); CCounter++; Tcounter = 0;

// periods while (true) { try { str = in.readLine(); // Guard everything in a try-finally to make sure that the socket is closed: } catch (SocketException e) { System.out.println("==== Exception happen ... ===="); System.out.println("counter is: " + counter); System.out.println(str); break; } //new PrintStream(result).println (str); Print to file \\=======>

174

if (str.equals("END")) { break; } //System.out.println("Echoing: " + str); if (counter == 0) { IP1 = str.substring(0, 9); IF1 = str.substring(9, 13); System.out.println("IP1 is " //System.out.println("IF1 is thisIP = IP1; } if (counter == 1) { IP2 = str.substring(0, 9); IF2 = str.substring(9, 13); System.out.println("IP2 is " //System.out.println("IF2 is thisIP = IP2; } if (counter == 2) { IP3 = str.substring(0, 9); IF3 = str.substring(9, 13); System.out.println("IP3 is " //System.out.println("IF3 is thisIP = IP3; } if (counter == 3) { IP4 = str.substring(0, 9); IF4 = str.substring(9, 13); System.out.println("IP4 is " //System.out.println("IF4 is thisIP = IP4; } if (counter == 4) { IP5 = str.substring(0, 9); IF5 = str.substring(9, 13); System.out.println("IP5 is " //System.out.println("IF5 is thisIP = IP5; }

+ IP1); " + IF1);

+ IP2); " + IF2);

+ IP3); " + IF3);

+ IP4); " + IF4);

+ IP5); " + IF5);

if (counter == 5) { i = 0; hostname = str; System.out.println("Hostname is " + hostname);

175

for (i =0; i < 8; i++) { if (Routers[i].Hostname.equals(hostname)) { //if ((Reply[i] != 0) && (Rcounter < 34)) //{ if (Reply[i] != 0) { Ycounter++; new PrintStream(result).println("============ Cycle #" + Ycounter); new PrintStream(result).println("The following nodes have no response:"); for (j = 0; j < 8; j++) { if (Reply[j] == 0) new PrintStream(result).print(" R" + j); Reply[j] = 0; } new PrintStream(result).println(" "); Rcounter = 0; scan = 1; } thishost = i; Reply[i] = 1; Routers[thishost].ASIPs[0] = IP1; Routers[thishost].ASIPs[1] = IP2; Routers[thishost].ASIPs[2] = IP3; Routers[thishost].ASIPs[3] = IP4; Routers[thishost].ASIPs[4] = IP5; System.out.println("#### Reply set to one for router R" + i); System.out.println("============= Rcounter = " + Rcounter); break; }//if } for (i =0; i < 5; i++) { if (Routers[thishost].IPs[i].equals(IP1)) { Routers[thishost].interfaceID[i] = IF1; Routers[thishost].p_nb[0] = Routers[thishost].neighbors[i]; } } for (i =0; i < 5; i++) { if (Routers[thishost].IPs[i].equals(IP2)) { Routers[thishost].interfaceID[i] = IF2;

176

Routers[thishost].p_nb[1] = Routers[thishost].neighbors[i]; } } for (i =0; i < 5; i++) { if (Routers[thishost].IPs[i].equals(IP3)) { Routers[thishost].interfaceID[i] = IF3; Routers[thishost].p_nb[2] = Routers[thishost].neighbors[i]; } } for (i =0; i < 5; i++) { if (Routers[thishost].IPs[i].equals(IP4)) { Routers[thishost].interfaceID[i] = IF4; Routers[thishost].p_nb[3] = Routers[thishost].neighbors[i]; } } for (i =0; i < 5; i++) { if (Routers[thishost].IPs[i].equals(IP5)) { Routers[thishost].interfaceID[i] = IF5; Routers[thishost].p_nb[4] = Routers[thishost].neighbors[i]; } } //for (i =0; i < 4; i++) //System.out.println("Stored interface " + Routers[thishost].interfaceID[i]); } if (counter == 6) { IFp1 = str.substring(2, 6); //System.out.println("IFp1 is " + IFp1); cur_str = 1; cur_char = 7; if (str.charAt(7) != ' ') { start_char[1] = 7; cur_char = 8; } while (cur_str < 12) {

177

if ((str.charAt(cur_char) == ' ') && (str.charAt(cur_char + 1) != ' ')) start_char[cur_str] = cur_char + 1; if ((str.charAt(cur_char) != ' ') && (str.charAt(cur_char + 1) == ' ')) { end_char[cur_str] = cur_char; cur_str++; } cur_char++; } pack1R = str.substring(start_char[2], end_char[2] + 1); // (17, 23) pack1T = str.substring(start_char[10], end_char[10] + 1); // (76, 82) ipack1R = Integer.parseInt(pack1R); ipack1T = Integer.parseInt(pack1T); if (Routers[thishost].pktavg[0][0] == 0) { if (Routers[thishost].prepkt[0][0] == 0) Routers[thishost].prepkt[0][0] = ipack1R; else { interm = ipack1R - Routers[thishost].prepkt[0][0]; //calculation Routers[thishost].curpkt[0][0] = interm; Routers[thishost].pktavg[0][0] = interm; } } else { interm = ipack1R - Routers[thishost].prepkt[0][0]; //calculation Routers[thishost].curpkt[0][0] = interm; Routers[thishost].pktavg[0][0] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[0][0]; Routers[thishost].pktdfa[0][0] = interm/Routers[thishost].pktavg[0][0]; Routers[thishost].prepkt[0][0] = ipack1R; } //System.out.println("pack1R is " + ipack1R); if (Routers[thishost].pktavg[0][1] == 0) { if (Routers[thishost].prepkt[0][1] == 0) Routers[thishost].prepkt[0][1] = ipack1T; else {

178

interm = ipack1T - Routers[thishost].prepkt[0][1]; //calculation Routers[thishost].curpkt[0][1] = interm; Routers[thishost].pktavg[0][1] = interm; } } else { interm = ipack1T - Routers[thishost].prepkt[0][1]; //calculation Routers[thishost].curpkt[0][1] = interm; Routers[thishost].pktavg[0][1] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[0][1]; Routers[thishost].pktdfa[0][1] = interm/Routers[thishost].pktavg[0][1]; Routers[thishost].prepkt[0][1] = ipack1T; } //System.out.println("pack1T is " + ipack1T); } if (counter == 7) { IFp2 = str.substring(2, 6); //System.out.println("IFp2 is " + IFp2); cur_str = 1; cur_char = 7; if (str.charAt(7) != ' ') { start_char[1] = 7; cur_char = 8; } while (cur_str < 12) { if ((str.charAt(cur_char) == ' ') && (str.charAt(cur_char + 1) != ' ')) start_char[cur_str] = cur_char + 1; if ((str.charAt(cur_char) != ' ') && (str.charAt(cur_char + 1) == ' ')) { end_char[cur_str] = cur_char; cur_str++; } cur_char++; } pack2R = str.substring(start_char[2], end_char[2] + 1); // (17, 23) pack2T = str.substring(start_char[10], end_char[10] + 1); // (76, 82)

179

ipack2R = Integer.parseInt(pack2R); ipack2T = Integer.parseInt(pack2T); if (Routers[thishost].pktavg[1][0] == 0) { if (Routers[thishost].prepkt[1][0] == 0) Routers[thishost].prepkt[1][0] = ipack2R; else { interm = ipack2R - Routers[thishost].prepkt[1][0]; //calculation Routers[thishost].curpkt[1][0] = interm; Routers[thishost].pktavg[1][0] = interm; } } else { interm = ipack2R - Routers[thishost].prepkt[1][0]; //calculation Routers[thishost].curpkt[1][0] = interm; Routers[thishost].pktavg[1][0] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[1][0]; Routers[thishost].pktdfa[1][0] = interm/Routers[thishost].pktavg[1][0]; Routers[thishost].prepkt[1][0] = ipack2R; } //System.out.println("pack2R is " + ipack2R); if (Routers[thishost].pktavg[1][1] == 0) { if (Routers[thishost].prepkt[1][1] == 0) Routers[thishost].prepkt[1][1] = ipack2T; else { interm = ipack2T - Routers[thishost].prepkt[1][1]; //calculation Routers[thishost].curpkt[1][1] = interm; Routers[thishost].pktavg[1][1] = interm; } } else { interm = ipack2T - Routers[thishost].prepkt[1][1]; //calculation Routers[thishost].curpkt[1][1] = interm; Routers[thishost].pktavg[1][1] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[1][1]; Routers[thishost].pktdfa[1][1] = interm/Routers[thishost].pktavg[1][1];

180

Routers[thishost].prepkt[1][1] = ipack2T; } //System.out.println("pack2T is " + ipack2T); } if (counter == 8) { IFp3 = str.substring(2, 6); //System.out.println("IFp3 is " + IFp3); cur_str = 1; cur_char = 7; if (str.charAt(7) != ' ') { start_char[1] = 7; cur_char = 8; } while (cur_str < 12) { if ((str.charAt(cur_char) == ' ') && (str.charAt(cur_char + 1) != ' ')) start_char[cur_str] = cur_char + 1; if ((str.charAt(cur_char) != ' ') && (str.charAt(cur_char + 1) == ' ')) { end_char[cur_str] = cur_char; cur_str++; } cur_char++; } pack3R = str.substring(start_char[2], end_char[2] + 1); // (17, 23) pack3T = str.substring(start_char[10], end_char[10] + 1); // (76, 82) ipack3R = Integer.parseInt(pack3R); ipack3T = Integer.parseInt(pack3T); if (Routers[thishost].pktavg[2][0] == 0) { if (Routers[thishost].prepkt[2][0] == 0) Routers[thishost].prepkt[2][0] = ipack3R; else { interm = ipack3R - Routers[thishost].prepkt[2][0]; //calculation Routers[thishost].curpkt[2][0] = interm; Routers[thishost].pktavg[2][0] = interm; } } else {

181

interm = ipack3R - Routers[thishost].prepkt[2][0]; //calculation Routers[thishost].curpkt[2][0] = interm; Routers[thishost].pktavg[2][0] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[2][0]; Routers[thishost].pktdfa[2][0] = interm/Routers[thishost].pktavg[2][0]; Routers[thishost].prepkt[2][0] = ipack3R; } //System.out.println("pack3R is " + ipack3R); if (Routers[thishost].pktavg[2][1] == 0) { if (Routers[thishost].prepkt[2][1] == 0) Routers[thishost].prepkt[2][1] = ipack3T; else { interm = ipack3T - Routers[thishost].prepkt[2][1]; //calculation Routers[thishost].curpkt[2][1] = interm; Routers[thishost].pktavg[2][1] = interm; } } else { interm = ipack3T - Routers[thishost].prepkt[2][1]; //calculation Routers[thishost].curpkt[2][1] = interm; Routers[thishost].pktavg[2][1] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[2][1]; Routers[thishost].pktdfa[2][1] = interm/Routers[thishost].pktavg[2][1]; Routers[thishost].prepkt[2][1] = ipack3T; } //System.out.println("pack3T is " + ipack3T); } if (counter == 9) { IFp4 = str.substring(2, 6); //System.out.println("IFp4 is " + IFp4); cur_str = 1; cur_char = 7; if (str.charAt(7) != ' ') { start_char[1] = 7; cur_char = 8; }

182

while (cur_str < 12) { if ((str.charAt(cur_char) == ' ') && (str.charAt(cur_char + 1) != ' ')) start_char[cur_str] = cur_char + 1; if ((str.charAt(cur_char) != ' ') && (str.charAt(cur_char + 1) == ' ')) { end_char[cur_str] = cur_char; cur_str++; } cur_char++; } pack4R = str.substring(start_char[2], end_char[2] + 1); // (17, 23) pack4T = str.substring(start_char[10], end_char[10] + 1); // (76, 82) ipack4R = Integer.parseInt(pack4R); ipack4T = Integer.parseInt(pack4T); if (Routers[thishost].pktavg[3][0] == 0) { if (Routers[thishost].prepkt[3][0] == 0) Routers[thishost].prepkt[3][0] = ipack4R; else { interm = ipack4R - Routers[thishost].prepkt[3][0]; //calculation Routers[thishost].curpkt[3][0] = interm; Routers[thishost].pktavg[3][0] = interm; } } else { interm = ipack4R - Routers[thishost].prepkt[3][0]; //calculation Routers[thishost].curpkt[3][0] = interm; Routers[thishost].pktavg[3][0] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[3][0]; Routers[thishost].pktdfa[3][0] = interm/Routers[thishost].pktavg[3][0]; Routers[thishost].prepkt[3][0] = ipack4R; } //System.out.println("pack4R is " + ipack4R); if (Routers[thishost].pktavg[3][1] == 0) { if (Routers[thishost].prepkt[3][1] == 0) Routers[thishost].prepkt[3][1] = ipack4T;

183

else { interm = ipack4T - Routers[thishost].prepkt[3][1]; Routers[thishost].curpkt[3][1] = interm; Routers[thishost].pktavg[3][1] = interm; } } else { interm = ipack4T - Routers[thishost].prepkt[3][1]; //calculation Routers[thishost].curpkt[3][1] = interm; Routers[thishost].pktavg[3][1] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[3][1]; Routers[thishost].pktdfa[3][1] = interm/Routers[thishost].pktavg[3][1]; Routers[thishost].prepkt[3][1] = ipack4T; } } if (counter == 10) { IFp5 = str.substring(2, 6); //System.out.println("IFp5 is " + IFp5); cur_str = 1; cur_char = 7; if (str.charAt(7) != ' ') { start_char[1] = 7; cur_char = 8; } while (cur_str < 12) { if ((str.charAt(cur_char) == ' ') && (str.charAt(cur_char + 1) != ' ')) start_char[cur_str] = cur_char + 1; if ((str.charAt(cur_char) != ' ') && (str.charAt(cur_char + 1) == ' ')) { end_char[cur_str] = cur_char; cur_str++; } cur_char++; } pack5R = str.substring(start_char[2], end_char[2] + 1); // (17, 23) pack5T = str.substring(start_char[10], end_char[10] + 1); // (76, 82) ipack5R = Integer.parseInt(pack5R);

184

ipack5T = Integer.parseInt(pack5T); if (Routers[thishost].pktavg[4][0] == 0) { if (Routers[thishost].prepkt[4][0] == 0) Routers[thishost].prepkt[4][0] = ipack5R; else { interm = ipack5R - Routers[thishost].prepkt[4][0]; Routers[thishost].curpkt[4][0] = interm; Routers[thishost].pktavg[4][0] = interm; } } else { interm = ipack5R - Routers[thishost].prepkt[4][0]; Routers[thishost].curpkt[4][0] = interm; Routers[thishost].pktavg[4][0] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[4][0]; Routers[thishost].pktdfa[4][0] = interm/Routers[thishost].pktavg[4][0]; Routers[thishost].prepkt[4][0] = ipack5R; } //System.out.println("pack5R is " + ipack5R); if (Routers[thishost].pktavg[4][1] == 0) { if (Routers[thishost].prepkt[4][1] == 0) Routers[thishost].prepkt[4][1] = ipack5T; else { interm = ipack5T - Routers[thishost].prepkt[4][1]; Routers[thishost].curpkt[4][1] = interm; Routers[thishost].pktavg[4][1] = interm; } } else { interm = ipack5T - Routers[thishost].prepkt[4][1]; Routers[thishost].curpkt[4][1] = interm; Routers[thishost].pktavg[4][1] = alpha * interm + (1 alpha) * Routers[thishost].pktavg[4][1]; Routers[thishost].pktdfa[4][1] = interm/Routers[thishost].pktavg[4][1]; Routers[thishost].prepkt[4][1] = ipack5T; } //System.out.println("pack5T is " + ipack5T); out.println("ACK from the server");

185

} //out.println("ACK from the server"); //if (thisIP.substring(0, 7).equals("192.168")) //{ // thisIP = "0"; //System.out.println("HERE"); // } //else //{ counter++; //System.out.println("The value of this IP is " + thisIP.substring(0, 6)); //} //result.close(); }//while } finally { System.out.println("closing..."); // for (p = 0; p < 5; p++) // for (q = 0; q < 2; q++) // System.out.println("The value of curpkt is " + Routers[thishost].curpkt[p][q]); // for (p = 0; p < 5; p++) // for (q = 0; q < 2; q++) // System.out.println("The value of prepkt is " + Routers[thishost].prepkt[p][q]);

// calculating DR ================================= Routers[thishost].pktdr[0][1] = Routers[thishost].pktdfa[1][1]/Routers[thishost].pktdfa[0][0]; Routers[thishost].pktdr[0][2] = Routers[thishost].pktdfa[2][1]/Routers[thishost].pktdfa[0][0]; Routers[thishost].pktdr[0][3] = Routers[thishost].pktdfa[3][1]/Routers[thishost].pktdfa[0][0]; Routers[thishost].pktdr[0][4] = Routers[thishost].pktdfa[4][1]/Routers[thishost].pktdfa[0][0]; Routers[thishost].pktdr[1][0] = Routers[thishost].pktdfa[0][1]/Routers[thishost].pktdfa[1][0]; Routers[thishost].pktdr[1][2] = Routers[thishost].pktdfa[2][1]/Routers[thishost].pktdfa[1][0]; Routers[thishost].pktdr[1][3] = Routers[thishost].pktdfa[3][1]/Routers[thishost].pktdfa[1][0]; Routers[thishost].pktdr[1][4] = Routers[thishost].pktdfa[4][1]/Routers[thishost].pktdfa[1][0]; Routers[thishost].pktdr[2][0] = Routers[thishost].pktdfa[0][1]/Routers[thishost].pktdfa[2][0];

186

Routers[thishost].pktdr[2][1] = Routers[thishost].pktdfa[1][1]/Routers[thishost].pktdfa[2][0]; Routers[thishost].pktdr[2][3] = Routers[thishost].pktdfa[3][1]/Routers[thishost].pktdfa[2][0]; Routers[thishost].pktdr[2][4] = Routers[thishost].pktdfa[4][1]/Routers[thishost].pktdfa[2][0]; Routers[thishost].pktdr[3][0] = Routers[thishost].pktdfa[0][1]/Routers[thishost].pktdfa[3][0]; Routers[thishost].pktdr[3][1] = Routers[thishost].pktdfa[1][1]/Routers[thishost].pktdfa[3][0]; Routers[thishost].pktdr[3][2] = Routers[thishost].pktdfa[2][1]/Routers[thishost].pktdfa[3][0]; Routers[thishost].pktdr[3][4] = Routers[thishost].pktdfa[4][1]/Routers[thishost].pktdfa[3][0]; Routers[thishost].pktdr[4][0] = Routers[thishost].pktdfa[0][1]/Routers[thishost].pktdfa[4][0]; Routers[thishost].pktdr[4][1] = Routers[thishost].pktdfa[1][1]/Routers[thishost].pktdfa[4][0]; Routers[thishost].pktdr[4][2] = Routers[thishost].pktdfa[2][1]/Routers[thishost].pktdfa[4][0]; Routers[thishost].pktdr[4][3] = Routers[thishost].pktdfa[3][1]/Routers[thishost].pktdfa[4][0]; // calculating OR ================================= Routers[thishost].pktor[0][1] = (Routers[thishost].curpkt[1][1] Routers[thishost].pktavg[1][1])/(Routers[thishost].curpkt[0][0] Routers[thishost].pktavg[0][0] + 1); Routers[thishost].pktor[0][2] = (Routers[thishost].curpkt[2][1] Routers[thishost].pktavg[2][1])/(Routers[thishost].curpkt[0][0] Routers[thishost].pktavg[0][0] + 1); Routers[thishost].pktor[0][3] = (Routers[thishost].curpkt[3][1] Routers[thishost].pktavg[3][1])/(Routers[thishost].curpkt[0][0] Routers[thishost].pktavg[0][0] + 1); Routers[thishost].pktor[0][4] = (Routers[thishost].curpkt[4][1] Routers[thishost].pktavg[4][1])/(Routers[thishost].curpkt[0][0] Routers[thishost].pktavg[0][0] + 1);

-

-

-

-

Routers[thishost].pktor[1][0] = (Routers[thishost].curpkt[0][1] Routers[thishost].pktavg[0][1])/(Routers[thishost].curpkt[1][0] Routers[thishost].pktavg[1][0] + 1); Routers[thishost].pktor[1][2] = (Routers[thishost].curpkt[2][1] Routers[thishost].pktavg[2][1])/(Routers[thishost].curpkt[1][0] Routers[thishost].pktavg[1][0] + 1);

187

Routers[thishost].pktor[1][3] = (Routers[thishost].curpkt[3][1] Routers[thishost].pktavg[3][1])/(Routers[thishost].curpkt[1][0] Routers[thishost].pktavg[1][0] + 1); Routers[thishost].pktor[1][4] = (Routers[thishost].curpkt[4][1] Routers[thishost].pktavg[4][1])/(Routers[thishost].curpkt[1][0] Routers[thishost].pktavg[1][0] + 1); Routers[thishost].pktor[2][0] = (Routers[thishost].curpkt[0][1] Routers[thishost].pktavg[0][1])/(Routers[thishost].curpkt[2][0] Routers[thishost].pktavg[2][0] + 1); Routers[thishost].pktor[2][1] = (Routers[thishost].curpkt[1][1] Routers[thishost].pktavg[1][1])/(Routers[thishost].curpkt[2][0] Routers[thishost].pktavg[2][0] + 1); Routers[thishost].pktor[2][3] = (Routers[thishost].curpkt[3][1] Routers[thishost].pktavg[3][1])/(Routers[thishost].curpkt[2][0] Routers[thishost].pktavg[2][0] + 1); Routers[thishost].pktor[2][4] = (Routers[thishost].curpkt[4][1] Routers[thishost].pktavg[4][1])/(Routers[thishost].curpkt[2][0] Routers[thishost].pktavg[2][0] + 1); Routers[thishost].pktor[3][0] = (Routers[thishost].curpkt[0][1] Routers[thishost].pktavg[0][1])/(Routers[thishost].curpkt[3][0] Routers[thishost].pktavg[3][0] + 1); Routers[thishost].pktor[3][1] = (Routers[thishost].curpkt[1][1] Routers[thishost].pktavg[1][1])/(Routers[thishost].curpkt[3][0] Routers[thishost].pktavg[3][0] + 1); Routers[thishost].pktor[3][2] = (Routers[thishost].curpkt[2][1] Routers[thishost].pktavg[2][1])/(Routers[thishost].curpkt[3][0] Routers[thishost].pktavg[3][0] + 1); Routers[thishost].pktor[3][4] = (Routers[thishost].curpkt[4][1] Routers[thishost].pktavg[4][1])/(Routers[thishost].curpkt[3][0] Routers[thishost].pktavg[3][0] + 1);

-

-

-

-

-

-

-

-

Routers[thishost].pktor[4][0] = (Routers[thishost].curpkt[0][1] Routers[thishost].pktavg[0][1])/(Routers[thishost].curpkt[4][0] Routers[thishost].pktavg[4][0] + 1); Routers[thishost].pktor[4][1] = (Routers[thishost].curpkt[1][1] Routers[thishost].pktavg[1][1])/(Routers[thishost].curpkt[4][0] Routers[thishost].pktavg[4][0] + 1); Routers[thishost].pktor[4][2] = (Routers[thishost].curpkt[2][1] -

188

Routers[thishost].pktavg[2][1])/(Routers[thishost].curpkt[4][0] Routers[thishost].pktavg[4][0] + 1); Routers[thishost].pktor[4][3] = (Routers[thishost].curpkt[3][1] Routers[thishost].pktavg[3][1])/(Routers[thishost].curpkt[4][0] Routers[thishost].pktavg[4][0] + 1); Rcounter++; System.out.println("OR, DR, DFA are calculated ..."); System.out.println(" ");

String asip = "0"; String nebip = "0"; String upstreamip = "0", downstreamip ="0"; //= new String(); String routerfile = "none"; int rid = 0; scan2 = 1; int dn_exist = 0; int up_exist = 0; System.out.println("**** scan2 is: " + scan2); System.out.println("**** scan is: " + scan); for (j = 0; j < 8; j++) { //new PrintStream(result).print(Reply[j] + " "); scan2 = scan2 * Reply[j]; } System.out.println("**** Scan2 is: " + scan2); if (scan2 != 0) { Ycounter++; new PrintStream(result).println("============ Cycle #" + Ycounter); new PrintStream(result).println("============ All Nodes are alive ==========="); } if ((scan != 0) || (scan2 != 0 )) { System.out.println("**** Start Scanning... ****"); //new PrintStream(result).print(CCounter + ": "); //new PrintStream(result).println(); scan = 0; scan2 = 1; Tcounter = 0; for (r = 0; r < 8; r++) {

189

for (j = 0; j < 5; j++) { if (Routers[r].pktdfa[j][0] >= beta) // beta is the threshold { for (k = 0; k < 5; k++) { if ((Routers[r].pktor[j][k] >= 0.9) && (j != k)) //DFA >=beta and OR > 0.9 { System.out.println("**** One pattern observed ****"); if ((Routers[r].p_nb[j] > -2) && (Routers[r].p_nb[k] > -2)) { new PrintStream(result).print("Suspicious Pattern From R" + r); new PrintStream(result).print(": Upstream R" + Routers[r].p_nb[j]); new PrintStream(result).println(", Downstream R" + Routers[r].p_nb[k]); //new PrintStream(result).println(" "); Routers[r].is_p = 1; if (Routers[r].up_no == 0) { Routers[r].up_r[0] = Routers[r].p_nb[j]; Routers[r].up_no++; } else { up_exist = 0; for (i = 0; i < Routers[r].up_no; i++) { if (Routers[r].up_r[i] == Routers[r].p_nb[j]) { up_exist = 1; } //if } //for i, check whether this neighbor is recorded already if (up_exist == 0) { Routers[r].up_r[Routers[r].up_no] = Routers[r].p_nb[j]; Routers[r].up_no++; } } //else if (Routers[r].dn_no == 0)

190

{ Routers[r].dn_r[0] = Routers[r].p_nb[k]; Routers[r].dn_no++; } else { dn_exist = 0; for (i = 0; i < Routers[r].dn_no; i++) { if (Routers[r].dn_r[i] == Routers[r].p_nb[k]) { dn_exist = 1; } //if } //for i if (dn_exist == 0) { Routers[r].dn_r[Routers[r].dn_no] = Routers[r].p_nb[k]; Routers[r].dn_no++; } } // else } // if not control port or unconnected ports } //if pktor >= 0.9 } //for k } // if } // for j if (Routers[r].is_p == 1) { Tcounter++; new PrintStream(result).print("**** Summarize Suspicious Pattern at R"); new PrintStream(result).println(r + " ****"); new Router Number: "); new new for Routers[r].up_r[i]); new new Router Number: "); new new for PrintStream(result).println(); PrintStream(result).print(" " + "Downstream PrintStream(result).print(Routers[r].dn_no); PrintStream(result).print(" --> "); (i = 0; i < Routers[r].dn_no; i++) PrintStream(result).print(" " + "Upstream

PrintStream(result).print(Routers[r].up_no); PrintStream(result).print(" --> "); (i = 0; i < Routers[r].up_no; i++) new PrintStream(result).print(" R" +

191

new PrintStream(result).print(" R" + Routers[r].dn_r[i]); new PrintStream(result).println(); new PrintStream(result).println(); } System.out.println("**** refresh information ... ****"); Reply[r] = 0; Routers[r].up_no = 0; Routers[r].dn_no = 0; Routers[r].is_p = 0; for (k = 0; k < 5; k++) { Routers[r].up_r[k] = 999; Routers[r].dn_r[k] = 999; Routers[r].p_nb[k] = 999; } } //for r new PrintStream(result).print("CAT node number: " + Tcounter); new PrintStream(result).println(); new PrintStream(result).println(); new PrintStream(record).println(Ycounter + " Tcounter); System.out.println("===== Writing CAT_Record File ====="); } " +

socket.close(); } } finally { //s.close(); } }//while } } ///:~

192

Sponsor Documents

Or use your account on DocShare.tips

Hide

Forgot your password?

Or register your new account on DocShare.tips

Hide

Lost your password? Please enter your email address. You will receive a link to create a new password.

Back to log-in

Close