Basic Search / Detailed Display

Author: 阿渡
Aldo - Oktavianus Tamaela
Thesis Title: An Autonomous System Traceback to Counter Large-Scale Anonymous Attack in Internet
An Autonomous System Traceback to Counter Large-Scale Anonymous Attack in Internet
Advisor: 洪西進
Shi-Jinn Horng
Committee: 鍾國亮
Kuo-Liang Chung
梅興
Hsing Mei
王永鐘
Yung-Chung Wang
蘇民揚
Ming-Yang Su
Degree: 碩士
Master
Department: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
Thesis Publication Year: 2008
Graduation Academic Year: 96
Language: 英文
Pages: 58
Keywords (in other languages): Autonomous System, Packet Marking, DDoS Attack, IP Traceback
Reference times: Clicks: 271Downloads: 0
Share:
School Collection Retrieve National Library Collection Retrieve Error Report
  • Since Distributed Denial of Service (DDoS) attacks become increasingly threatening in Internet, IP traceback has received much concern by researchers. This mechanism tries to locate the exact location of anonymous packets sent by attackers and reveals the paths traversed by these packets during DDoS attacks. Locating the real source of these packets is somehow a very difficult task. However, tracing the approximate location is more practical as suggested by many researchers.
    In this paper, we propose a traceback scheme named as Distance Clustered Autonomous System Traceback (DCAST) that uses Autonomous System as its unit of tracing. Our approach is based on packet marking. While other similar traceback approach suffers uncertainty to locate the attack origin, as we will discuss in this thesis, our proposed scheme does not. The proposed scheme is capable of tracing thousands of nodes involved in attacks. It is also able to discern in the reconstructed attack graph which node is the source of an attack and which one is not the source of an attack.
    Only 25 bits of marking information is required. We overload IP header of a packet with this information. Thus, our scheme requires no additional bandwidth. Our marking strategy and reconstruction technique bring several merits such as: greatly suppressing the number of false positives; avoiding uncertainty of locating attack origin; and introducing optimal marking probability which avoids marking spoofing attack and optimizes the necessity number of packets for path reconstruction.
    Moreover, the proposed scheme is analyzed and validated with simulation using real Autonomous System dataset. Experimental result shows that with up to 11000 attack source, our scheme is able to reconstruct attacking graph without false positive node and without false negative source, which means it can locate all attack sources. We conduct real experimental implementation as prototype to show the correctness of our marking algorithm and reconstruction procedure.


    Since Distributed Denial of Service (DDoS) attacks become increasingly threatening in Internet, IP traceback has received much concern by researchers. This mechanism tries to locate the exact location of anonymous packets sent by attackers and reveals the paths traversed by these packets during DDoS attacks. Locating the real source of these packets is somehow a very difficult task. However, tracing the approximate location is more practical as suggested by many researchers.
    In this paper, we propose a traceback scheme named as Distance Clustered Autonomous System Traceback (DCAST) that uses Autonomous System as its unit of tracing. Our approach is based on packet marking. While other similar traceback approach suffers uncertainty to locate the attack origin, as we will discuss in this thesis, our proposed scheme does not. The proposed scheme is capable of tracing thousands of nodes involved in attacks. It is also able to discern in the reconstructed attack graph which node is the source of an attack and which one is not the source of an attack.
    Only 25 bits of marking information is required. We overload IP header of a packet with this information. Thus, our scheme requires no additional bandwidth. Our marking strategy and reconstruction technique bring several merits such as: greatly suppressing the number of false positives; avoiding uncertainty of locating attack origin; and introducing optimal marking probability which avoids marking spoofing attack and optimizes the necessity number of packets for path reconstruction.
    Moreover, the proposed scheme is analyzed and validated with simulation using real Autonomous System dataset. Experimental result shows that with up to 11000 attack source, our scheme is able to reconstruct attacking graph without false positive node and without false negative source, which means it can locate all attack sources. We conduct real experimental implementation as prototype to show the correctness of our marking algorithm and reconstruction procedure.

    Contents Abstract ii Acknowledgments iii Contents iv List of Figures vii List of Tables vi Chapter 1 Introduction 1 1.1 Problem Statements 4 1.2 Research Objective 5 1.3 Contribution of the Thesis 5 1.4 Organization of the Thesis 6 Chapter 2 Related Works on IP traceback 7 2.1 IP Traceback Schemes 7 2.1.1 Link Testing: Controlled Flooding 8 2.1.2 Packet Logging 9 2.1.3 ICMP Traceback (iTrace) 10 2.1.4 Packet Marking: Probabilistic Packet Marking-like schemes 11 2.2 Revisiting Autonomous System Edge Marking (ASEM) 12 Chapter 3 The Proposed Scheme 16 3.1 Source Ambiguity 16 3.2 Utilizing Autonomous System Number for Traceback 20 3.3 Overview of Our Proposed Scheme 20 3.4 Marking Algorithms 24 3.4.1 Using Distance Clustering to Deal with Source Ambiguity Problem 26 3.4.2 Using Distance Clustering to Help Reconstruction Process 28 3.5 Marking Probability 28 3.5.1 Static Marking Probability 29 3.5.2 Dynamic Marking Probability with NO-Remarking Policy 31 3.5.3 Dynamic Marking Probability with Remarking-Allowed Policy 32 3.6 Reconstruction Procedure 34 Chapter 4 Performance Evaluation and Experiment 40 4.1 Analysis and Simulation 40 4.1.1 Analysis 43 4.1.2 Simulation in One-Hop Cluster 46 4.1.3 Simulation in Real Autonomous System Dataset 47 4.2 Experimental Implementation 50 4.2.1 Detailed Implementation 51 4.2.2 Implementation Result 52 Chapter 5 Conclusion 55 References 57

    References

    [1] D. Moore, C. Shannon, D.J. Brown, G.M. Voelker, and S. Savage. “Inferring Internet Denial-of-Service Activity”. In ACM Transactions on Computer Systems 24(2), 115-139 (2006).
    [2] C. Douligeris and A. Mitrokotsa. “DDoS attacks and defense mechanisms: classification and state-of-the-art”. Computer Networks 44, 643-666 (2004).
    [3] P. Ferguson and D. Senie. “Network ingress filtering: defeating denial of service attacks which employ IP source address spoofing”. RFC 2827 (2000).
    [4] S. Savage, D. Wetherall, A. Karlin, and T. Anderson. “Network Support for IP Traceback”. In IEEE/ACM Transaction on Networking 9(3), 226-237 (2001)
    [5] A. Belenky and N. Ansari. “On deterministic packet marking”. Computer Networks 51, 2677-2700 (2007).
    [6] C. Brenton. “Egress Filtering FAQ”. SANS Intitute 2007, Available from <http://www.sans.org/reading_room/whitepapers/firewalls/1059.php>.
    [7] K. Park and H. Lee. “On the Effectiveness of Route-Based Packet Filtering for Distributed DoS Attack Prevention in Power-Law Internet”. In Proceeding of the ACM SIGCOMM’01 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 15-26 (2001).
    [8] S.M. Bellovin. “ICMP traceback messages”. IETF Draft, March 2000.
    [9] H. Burch and H. Cheswick. “Tracing anonymous packets to their approximate source”. In Proceeding of USENIX LISA Conference, 319-327 (2000).
    [10] A. Belenky and N. Ansari. “IP Traceback with Deterministic Packet Marking”. IEEE Communication Letters 7(4), 162-164 (2003).
    [11] D.X. Song and A. Perrig. “Advanced and authenticated marking scheme for IP traceback”. In Proceeding of IEEE INFOCOM, 2, 878-886 (2001).
    [12] Z. Gao and N. Ansari. “A practical and robust inter-domain marking scheme for IP traceback”. Computer Networks 51, 732-750 (2007).
    [13] V. Paruchuri, A. Durresi, and L. Barolli. “FAST: Fast Autonomous System Traceback”. International Conference on Advanced Networking and Applications (AINA), 498-505 (2007).
    [14] Z. Gao and N. Ansari. “Tracing cyber attacks from the practical perspective”. IEEE Communications Magazine 43, 123-131 (2005).
    [15] S. Shioda and H.J. Wang. “A Comparative study on different probabilistic packet marking schemes for IP traceback”. IEEE TENCON Region 10 Conference, 1-4 (2006).
    [16] C. Gong and K. Sarac. “IP traceback based on packet marking and logging”. IEE International Conference on Communications 2, 1043-1047 (2005).
    [17] H. Aljifri. “IP traceback: a new denial-of-service deterrent?”. IEEE Security & Privacy 1, 24-31 (2003).
    [18] R. Stone. “CenterTrack: An IP Overlay Network for Tracking DoS Floods”. In Proceeding 9th Usenix Security Symposium, Usenix Association, 199-212 (2000).
    [19] A.C. Snoeren et al. “Single Packet IP Traceback”. IEEE/ACM Transaction on Networking, 10(6), 721-734 (2002).
    [20] M. Ma. “Tabu marking scheme to speedup IP traceback”. Computer Networks, 50(18), 3536-3549 (2006).
    [21] J. Liu, Z. Lee, and Y. Chung. “Dynamic probabilistic packet marking for efficient IP traceback”. Computer Networks, 51(3), 866-882 (2007).
    [22] National Laboratory for Applied Network Research, AS Path Length. Available from: http://moat.nlarnr.net/ASPL.
    [23] A. Yaar, A. Perrig, and D. Song. “FIT: Fast Internet Traceback”. In Proceeding IEEE Infocom, 2, 1395-1406 (2005).
    [24] Z. Gao and N. Ansari. “Directed geographical traceback”. 3rd International Conference on Information Technology: Research and Education, 221-224 (2005).
    [25] M.T. Goodrich. “Probabilistic Packet Marking for Large-Scale IP Traceback”. IEEE/ACM Transactions on Networking, 16(1), 15-24 (2008).
    [26] B. Zhang, R. Liu, D. Massey, and L. Zhang. “Collecting the Internet AS-level Topology”. SIGCOMM Computer Communications Review, 35(1), 53-61 (2005).
    [27] V. Paruchuri, A. Durresi, R. Kannan, and S. S. Iyengar. ”Authenticated Autonomous System Traceback”. In Proceeding of the 18th IEEE International Conference on Advanced Information Networking and Applications, 1, 406-413 (2004).
    [28] D. Dean, M. Franklin, and A. Stubblefield. “An Algebraic Approach to IP Traceback”. ACM Transactions on Information and System Security (TISSEC) 5(2), 119-137 (2001).
    [29] S. Kent, C. Lynn, and K. Seo. “Secure Border Gateway Protocol (S-BGP)”. IEEE Journal on Selected Areas in Communications, 18(4), 582-592 (2000).
    [30] http://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html
    [31] CAIDA. http://www.caida.org/.
    [32] W. Feller. “An Introduction to Probability Theory and Its Applications”. John Wiley & Sons, Inc., 3rd edition, (1968).
    [33] http://www.tcpdump.org/
    [34] http://www.packetfactory.net/projects/libnet/.

    QR CODE