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.

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/.