臺灣博碩士論文加值系統

分散式阻斷服務攻擊對於現今的網際網路是最嚴重的安全威脅之ㄧ，攻擊者經由耗盡主機或網路資源，來達到阻絕或降低合法使用者應有的服務。此種攻擊因易於施行、難於預防及追蹤，因此，最近幾年來，已成為目前網路攻擊方式之大宗。
目前，針對解決或減緩分散式阻斷服務攻擊(DDoS)已有多種機制被提出；如攻擊路徑追蹤(IP traceback)。
本論文著重在攻擊路徑追蹤(IP traceback)之研究，以期許找出攻擊來源，達到治本的方法。然而，目前在網路攻擊路徑追蹤研究的論文中，以機率式封包標記法，為較優秀的方法，因為該方法能實現事後追蹤、不需耗用額外網路頻寬、不需佔用路由器的儲存空間，且也不會增加所傳送封包的大小。
然機率式封包標記法(PPM)亦存在四個有待改善之議題：
1. 攻擊路徑重建運算負荷。
2. 追蹤機制的強韌度。
3. 重建攻擊路徑所須蒐集的標記封包數量。
4. 機率式封包標記法(PPM)雖可由逐步漸增的方式來建置到路由器，但如在攻擊路徑中有不支援PPM的路由器時，可能會導致受害者端重建出不完整、甚至是錯誤的路徑。

而本論文先經由改良現有機率式封包標記法中路徑重建運算負荷和追蹤機制的強健度，我們提出一個具有身分識別功能的機率式封包標記法(ID-based PPM，IDPPM)，使所蒐集到的攻擊路徑片段能更快速地被分群並重組，事先分群的作為，能減低於分散式阻斷服務攻擊(DDoS)攻擊之下機率式封包標記法因攻擊路徑片段重組時誤判狀況，而建出錯誤攻擊路徑的情況(false positive)，以強健機率式封包標記法。使得機率式封包標記法追蹤能更快建出攻擊路徑，而其他議題也期望在未來逐一改善。透過改良機率式封包標記法，也將能更完善地防制分散式阻斷服務攻擊(DDoS)。

The distributed Denial of Service (DDoS) attack is one of the most serious security threats in the Internet today. It tries to consume resources of a remote host or network, thereby denying and degrading service legitimate users.
Because the DDoS attack are simple to implement, difficult to prevent and trace. In the last several years, Internet denial-of-service attacks have increased in frequency, severity and sophistication. .
Currently there are several mechanisms against DoS or DDoS attacks, such as IP traceback.
A promising solution to the IP traceback is probabilistic packet marking (PPM). This traceback approach can be applied during or after an attack, and it does not require any additional network traffic, router storage, or packet size increase.
Therefore, the research on countering DoS/DDoS attacks will be based on PPM scheme. In this thesis, there are four outstanding improvements PPM criteria—
1. Computing overhead for marked attack packets
2. robust against the false positive
3. Convergent amount of marked attack packets
4. Incrementally deployment
A modified probabilistic packet marking (PPM) version ID-based PPM, IDPPM, against the distributed denial-of-service attack is presented. This method is proposed to improve the original PPM complexity of fragments combination through clustering these fragments in advance. Furthermore, by reducing the time of fragments combination, the attack path reconstruction can be speeded up. We also use the TTL value to verify the reconstructed edge information except the original hash verification, and reduce the probability of false positive in PPM.

Contents
摘要 i
ABSTRACT iii
ACKNOWLEDGMENTS v
List of Table vii
List of Figure viii
Chapter 1 Introduction 1
Chapter 2 Related Work 5
2.1 DoS/DDoS Attack overview 5
2.2 DDoS Countermeasures 8
2.2.1 Hop-by-hop Tracing 9
2.2.2 Logging 11
2.2.3 ICMP Traceback 13
2.2.4 PPM-like schemes. 16
2.3 PPM Overview 19
Chapter 3 The proposed ID-based PPM 27
3.1 Proposed Methods in improving PPM’s computational overhead 27
3.2 Proposed Method in improving PPM robustness 31
Chapter 4 Experiments 37
4.1 Simulation 37
4.1.1 Simulation Topology 37
4.1.2 Simulation Scenario 38
4.2 Improving computational overhead 40
4.3 Improving the robustness 43
Chapter 5 Conclusions and Future Works 46
References 48

List of Table
Table 2.1: advantages and disadvantages of logging 13
Table 2.2: Advantages and disadvantages of ICMP-based traceback. 15
Table 2.3: Qualitative comparison of existing schemes for combating anonymous attacks. 17
Table 4.1: The flow configurations in the simulation 38
Table 4.2: Attack source information 45
Table 4.3 The fake attack source is generated by PPM 45

List of Figure
Figure 1.1: PPM fields in IP header 3
Figure 1.2: The reconstruction procedure 4
Figure 2.1: Distributed Denial of Service (DDoS) Attacks 6
Figure 2.2: The aggregation of Smurf. 8
Figure 2.3: Router-based Pushback. 10
Figure 2.4: The router along the network path logs information 12
Figure 2.5: ICMP-based traceback. 15
Figure 2.6: A tree structure representation of countermeasures. 18
Figure 2.7: Packet marking procedure. . 19
Figure 2.8: PPM algorithm. 21
Figure 2.9: PPM operation diagram. 22
Figure 2.10: PPM fields in IP header. 22
Figure 2.11: A simplified attack path 24
Figure 2.12: The procedure of path reconstruction in PPM 26
Figure 3.1: ID-PPM sampling algorithm. 30
Figure 3.2 : False positive situation. 32
Figure 3.3: The relation among k, computational overhead, per-packet space overhead, and robustness. 32
Figure 4.1: The experimental topology 39
Figure 4.2: Comparison of the computational overhead. 42
Figure 4.3: Comparison of the computational overhead. 42
Figure 4.4: Comparison of the number of false positive 44
Figure 4.5 A simple IDPPM example for filtering the false positive 45

[1] Dittrich, D. “The tribe Flood Network distributed denial of service attack tool”.
http://staff.washington.edu/dittrich/misc/tfn.analysis.
[2] “computer emergency response team, cert advisory ca-2000-01: Denial-of-service developments”.
http://www.cert.org/advisories/ca-2000-01.html. 2000.
[3] D. Moore, G. Voelker, and S. Savage. “Inferring internet denial-of-service activity”. In Usenix Security Symposium, 2001.
[4] Savage, S., Wetherall, D., Karlin, A., & Anderson, T., (2001). “Network support for IP traceback”, IEEE/ACM Trans. Netw., Vol.9, No.3, pp.226–237. Also appeared in Proc. ACM SIGCOMM Conf., pp.295–306, Aug. 2000.
[5] Waldvogel, M., (2002). “GOSSIB vs. IP traceback rumors”, Proc. 18th Ann. Computer Security Applications Conf. (ACSAC 2002), pp.5–13.
[6] K.J. Houle, G.M. Weaver, “Trends in Denial of Service Attack Technology”, CERT Coordination Center, Oct 2001. http://www.cert.org/archive/pdf/DoS_trends.pdf
[7] “Overview of scans and DDoS attacks,”
[Online]. Available: www.iwar.org.uk/comsec/resources/dos/ddos.pdf
[8] David McGuire and Brian Krebs. “Attack on internet called largest ever. washingtonpost.com, October 2002” http://washingtonpost.com/wp-dyn/articles/A828-2002Oct22.html
[9] CERT CC. Trends in Denial of Service Attack Technology, October 2001.
[10] V. Paxson. An analysis of using reflectors for distributed denial-of-service attacks, ACM Computer Communications Review (CCR), 31(3), July 2001.
[11] CERT CC. Smurf attack.
http://www.cert.org/advisories/CA-1998-01.html.
[12] "CERT advisory CA-1998-01 smurf IP Denial-of-Service attacks," available at http://www.cert.org/advisories/CA-1998-01.html, January 1998.
[13] T. M. Gil, and M. Poletto, “MULTOPS: a data-structure for bandwidth attack detection”, 10th Usenix Security Symposium, 2001, pp.23-38.
[14] R. Mahajan, S. Floyd, and D. Wetherall, “Controlling High-Bandwidth Flows at the Congested Router”, IEEE ICNP 2001, pp.192-201.
[15] Y. Xiang, W. Zhou, and M. Chowdhury, “A Survey of Active and Passive Defence Mechanisms against DDoS Attacks”, Technical Report, TR C04/02, School of Information Technology, Deakin University, Australia, 2004.
[16] Y. Xiang and W. Zhou, “An Active Distributed Defense System to Protect Web Applications from DDoS Attacks”,iiWAS2004, pp. 559-568.
[17]Rantul Mahajan, Steven M. Bellovin, Sally Floyd, John Ioannidis, Vern Paxson, and Scott Shenker, “Controlling high bandwidth aggregates in the network,” Technical report, AT&T Center for Internet Research at ICSI, July 2001.
[18] Ioannidis, j., & Bellovin, S. M., (2002). “Implementing pushback: router-based defense against DDoS attacks”, Proc. Network and Distributed System Security Symp., pp.6–8, San Diego, CA.
[19] Park, K., & Lee, H., (2000). “A proactive approach to distributed dos attack prevention using route-based distributed filtering”, Technical Report CSD-00-017, Department of Computer Sciences, Purdue University.
[20] Burch, H., & Cheswick, B., (2000). “Tracing anonymous packets to their approximate source”, Usenix LISA (New Orleans) Conf., pp.313–322.
[21] Aljifri, H., (2003). “IP traceback: a new denial-of-service deterrent?” IEEE Security & Privacy Magazine, Vol.1, No.3, pp.24–31.
[22] G. Sager. Security Fun with OCxmon and cflowd. Presentation at the Internet 2 Working Group, Nov. 1998.
[23] R. Stone. CenterTrack: An IP Overlay Network for Tracking DoS Floods. In to appear in Proceedings of thje 2000 USENIX Security Symposium, Denver, CO, July 2000.
[24] Stone, R., (2000). “CenterTrack: An IP overlay network for tracking DoS floods”, Proc. 9th USENIX Security Symp., pp.199–212, Denver, CO
[25] Baba, T., & Matsuda, S., (2002). “Tracing network attacks to their sources”, IEEE Internet Computing, Vol.6, No.2, pp.20–26
[26] Snoeren, A. C., Partridge, C., Sanchez, L. A., Jones, C. E., Tchakountio, F., Kent, S. T., & Strayer, W. T., (2001). ”Hash-based IP traceback”, Proc. ACM 134 SIGCOMM Applications, Technologies, Architectures, and Protocols for Computer Communication, pp.3–14.
[27] Hassan Aljifri University of Miami (2003). “IP Traceback: A New Denial-of-Service Deterrent?”, IEEE security & Privacy, pp24-27
[28] Bellovin, S. M., (2000). “ICMP traceback messages”, IETF, Internet Draft, draft-bellovin-itrace-00.txt.
[29] Bellovin, S. M., Leech, M., Taylor, T., (2001). “ICMP traceback messages”,IETF, Internet Draft, draft-ietf-itrace-01.txt.
[30] Mankin, A., Massey, D., Wu, C. L., Wu, S. F., & Zhang, L., (2001) “On design and evaluation of `intention-driven' ICMP traceback”, Proc. IEEE Int. Conf. Computer Communications and Netw., pp.159–165.
[31] Wu, S. F., Zhang, L., Massey, D., & Mankin, A., (2001). “Intention-Driven ICMP Trace-back”, IETF, Internet Draft, draft-wu-itrace-intention-00.txt.
[32] Wu, S. F., Zhang, L., Massey, D., & Mankin, A., (2001). “Intention-Driven ICMP Trace-back”, IETF, Internet Draft: draft-wu-itrace-intention-01.txt.
[33] Dawn X. Song and Adrian Perrig., (2001), “Advanced and authenticated marking schemes for IP traceback,” Proc. IEEE INFOCOM, pp.878–886
[Online]. Available: http://www.cert.org/advisories/CA-96.21.ping.html
[34] Dean, D., Franklin, M., & Stubblefield, A., (2001). ”An algebraic approach to IP traceback,” Proc. of the Network and Distributed System Security Symp.(NDSS), pp.3–12.
[35] Park, K., & Lee, H., (2001). “On the effectiveness of probabilistic packet marking for IP traceback under Denial of Service attack,” Proc. 20th Annual Joint Conf. IEEE Computer and Communications Societies, pp.338–347
[36] Computer Emergency Response Team, “CERT Advisory CA-92.21: TCP SYN flooding and IP spoofing attacks”,
[37] Kuznetsov, V., Simkin, A., & Sandstrom, H., (2002). “An evaluation of different IP traceback approaches”, Proc. 4th Intl. Conf. Information and Communications Security, pp.37–48
[38] He, C., (2002). Formal specifications of traceback marking protocols, An Honors Thesis, The University of Texas at Austin Department of Computer Sciences Austin, Texas
[39] K.T. Law, John C.S. Lui, and David K.Y. Yau., (2002) “You can run, But you can’t hide: An Effective Methodology to traceback DDoS attackers”, Proc.10th IEEE int’l Symp , MASCOTS ’02..
[40] Templeton, S. J., and Levitt, K. E., “Detecting spoofed packets”, Proc. 3rd IEEE DARPA Information Survivability Conference and Exposition (DISCEX), Washington, D.C, 2003, pp.164–175,
[41] Internet Storm Center. [Online]. Available: http://isc.incidents.org/
[42] LBNL Network Research Group. UCB/ LBNL/ VINT Network Simulator—ns (version 2), DARPA: VINT project.
[Online]. Available:http://www.isi.edu/nsnam/ns
[43] “Internet mapping”, http://research.lumeta.com/ches/map/dbs/index.html
[44] Teo peng, Christopher Lecki and Kotairi Ramamohanroa, “Adjusted Probabilistic Packet Marking,” in the Pro. of Networking 2002, Pisa, Italy ,May 2002.