本篇論文主要是針對分散式阻絕服務攻擊提出的解決方案，由於目前的網路協定屬於IPv4架構，存在無法確認來源端的問題，且此種攻擊不易防禦進而威脅到商業主機營運。在Yaar等人提出的PI架構利用路徑編碼資訊來抵禦攻擊，藉由完整二元樹演算法(Complete Binary Tree)將網路架構進行編碼程序能夠獲得良好的效果，然而根據網路測量顯示出網路上的路由器有27%的網路卡超過2張，顯示PI架構無法滿足真實網路架構，接著Gao等人提出了Color架構來解決PI架構網路卡數之問題，尚有不足之處。因此本研究繼續藉由利用位元編碼(Bits-Encoding)方式對路由器的網路卡編碼成2位元來記錄路徑，其次藉由雜湊路徑上第一台路由器的網路卡獲得Path Signature (PS) Number資訊，經由此兩種觀念改變原有架構效能，除了滿足真實網路架構和改善路徑追蹤效能，也能夠對可能的攻擊路徑數目減少至最低。

In this paper,we present a solution for Distributed Denial of Service Attack. Owing to the insecurity design of IP Protocol,it could not identify source. And those online company might be threatened and lost a lot of money. Yaar presented PI scheme to use path-encoding information against the attack. It is good to proceed to encode internet framework with the complete binary tree. However,The CAIDA study show that only 27% interfaces is more than 2 interfaces. After that, Gao improved the problem of insufficient interfaces of PI scheme. But it is not enough for the scheme. By Bit-Encoding and PS-Number information ,We strengthen the above-mentioned schemes. It could either improve the efficiency of Traceback and decrease the possible of attack paths.

目 錄
1.緒論...................................................1
1.1研究背景與動機.....................................1
1.2研究目的與方法.....................................2
1.3研究架構...........................................3
2 文獻探討...............................................4
2.1 分散式阻絕服務攻擊簡介............................4
2.2 抵禦分散式阻絕服務困難............................5
2.3 抵禦分散式阻絕服務攻擊的類型：....................6
2.3.1 INGRESS-FILTER................................6
2.3.2 LINK-TESTING..................................7
2.3.3 ICMP-TRACEBACK................................8
2.3.4 MARKING.......................................9
2.3.5 LOGGING......................................11
2.3.6 PI架構.......................................13
2.3.7 色彩架構.....................................14
2.3.8 傳統路徑追蹤架構優劣比較.....................16
3. 演算法設計...........................................17
3.1 封包標記欄位的探討...............................17
3.2 路由器網路卡數的探討.............................19
3.3路徑長度的考量的探討..............................21
3.4封包標記架構設計..................................22
3.5路徑重建程序......................................25
3.6 模擬分析.........................................27
3.6.1實驗數據資料來源.............................30
3.6.2統計模擬的方式...............................32
3.6.3實驗結果.....................................34
3.7 PI架構、COLOR架構與PS架構的優劣比較............36
3.8 與標記架構和稽核兩種架構優劣比較.................38
4.評估討論..............................................39
4.1路由器網路卡數目..................................39
4.2在網路架構改變的影響下............................39
4.3 標記演算法的時間複雜度比較.......................39
4.4網路服務供應商(ISP)的協助.........................40
5.限制和未來...........................................41
5.1安全認證..........................................41
5.2過濾封包模組擴充..................................41
6.結論..................................................42
7.參考文獻..............................................43

圖 目 錄
圖1攻擊路徑與偽造路徑...................................5
圖2 Ingress Filer過濾封包圖.............................6
圖3 Link testing-based traceback........................7
圖4 ICMP based traceback 示意圖.........................8
圖5 Marking演算法.......................................9
圖6 Packet Logging.....................................11
圖7 Bloom演算法和SPIE系統架構圖........................12
圖8 PI標記利用完滿二元樹模型建構的演算法...............13
圖9將二元樹模型擴充到八元樹模型........................14
圖10 Fragment ID 和Offset表示將被覆寫的欄位............17
圖11網路卡數目的機率分布...............................20
圖12網路卡數目的累積機率積分布.........................20
圖13 CAIDA所統計的路徑長度數目的比率...................21
圖14封包標記程序圖.....................................23
圖15路徑重建過程.......................................26
圖16單一路徑下決定的機率...............................34
圖17三種架構無法決定的路徑數目的比較...................35 
表目錄
表1封包標記追蹤能力比較..................................16
表2 CAIDA實驗-各路徑長度封包數量機率布........................................31
表3 CAIDA的實驗-路由器網路卡數目的機率分布...............................31
表4本研究架構與PI和Color兩種架構優劣比較.....................................37
表5本研究架構與傳統式PPM和Logging演算法綜合比較...................38

[1]H.Burch,B.Cheswick,“Tracing Anonymous Packets to Their Approximate Source”,Usenix LISA, Dec, 2000, pp.319-327
[2]D.X.Song,A.Perrig,“Advanced and Authenticated Marking Schemes for IP Traceback”,In:Proc: IEEE INFOCOM ,Apr ,2001,pp.878-886 
[3]A.Yaar,A.Perrig,D.Song,“Pi: A Path Identification Mechanism to Defend against DDoS Attacks”, In:Proc. IEEE Symposium on Security and Privacy,May ,2003,pp.93-107
[4]S.Savage,D.Wetherall,A.Karlin,T.Anderson, Practical Network Support for IP Traceback, In Proc.ACM SIGCOMM Conference ,August,2000,pp.295-306
[5]S.Savage,D.Wetherall,A.Karlin,T.Anderson, Network support for IP traceback, ACM/IEEE Transactions on Networking, vol.9, no:3,June, 2001, pp.226-237.
[6]A.Belenky and N.Ansari, IP Traceback with Deterministic Packet Marking, IEEE Comm.Letters, vol.7, no.4, Apr, 2003, pp.162-164
[7]F.Y.Lee and S.Shieh ,“Defending against spoofed DDoS attacks with path fingerprint”, Computers & Security 24, May, 2005, pp.571-586
[8]T.W.Doeppner, P.N.Klein, A.koyfman ,“Using Router Stamping to identify the Source of IP Packets”, In the ACM , Computer and Communications Security,Nov, 2000,pp.184-189
[9]J.Mirkovic,G.Prier,P.Reiher,“Attacking DDos at the Souce”, In Proc.ICNP 2002, Nov, 2002, pp.312-321
[10]A.C.Snoeren,C.Partidge,L.Sanchez,C.E.Jones,“Hash-Based IP Traceback”,In Proc.ACM SIGCOMM 2001 Conference, August, 2001, pp.3-14
[11]M.Adler,Amherst,“Tradeoffs in Probabilistic Packet Marking for IP Traceback”, In Proc. 34th ACM Symp. Theory of Computing, ACM Press, 2002, pp.407–418. L.Chen,Thomas,A.Longstaff,Kathleen,M, Carley, “Characterization of defense mechanisms against distributed denial of service attacks”, in the computers & Security,pp.665-678
[12]P.Almquist,“Type of service in the internet protocol suite RFC 1349”,July 1992
[13]K.Nichols, S.Blake, F.Baker,and D.Black, “Definition of the Differentiated Service field(DS field)in the IPv4 and IPv6 headers”,In RFC 2474,Dec,1998
[14]I.Stoica and H.Zhang,“Providing guaranteed services without per flow management”,In ACM SIGCOMM'99, May, 1999, pp.81-94
[15]Z.Gao,N.Ansari,K.Anantharam,“A New Marking Scheme to Defend against Distributed Denial of Service Attacks”,In the ACM, May, 2004, pp.2256-2260
[16]C.Jin,H.Wang,K.G.Shin,“Hop-Count Filter:An Effective Defense Against Spoofed”, In Proc.ACM, Computer and communications security, 2003,pp.30-41
[17]D.Dean, M.Franklin, A.Stubblefield .“An algebraic approach to IP traceback”,In ACM Trans, Information and System Security, vol.5, no.2, May ,2002, pp.119-137
[18]C.Douigeris, A.Mitrokotsa,“DDoS attacks and defense mechanisms: classification and state-of-the-art”,In Computer Networks ,vol.4,Apr,2005 ,pp.643- 666
[19]P.Ferguson,D.Senie,“Network Ingress filtering : defeating Denial of Service attacks which employ IP source address spoofing”,in:RFC 2827,2001
[20]S.Bellovin,“The ICMP Traceback message”, Internet Draft draft-bellovin-itrace-00.txt,March,2000
[21]D.Moore,G.Voelker,and S.Savage,“Inferring Internet Denial-of-Service Activity”, In Pro.USENIX Security Symposium, August 2001, pp.115-139
[22]R.Stone,“An IP Overlay Network for Tracking Dos Floods”,In Proc.USENIX Security Symposium, July, 2000, pp.199-212
[23] Belenky and N.Ansari,“IP Traceback with Deterministic Packet Marking”.IEEE Comm. Letters,vol.7, no.4, Apr, 2003, pp.162-164
[24]CAIDA, http://www.caida.org/tools/measurement/iffinder
[25]L.Gao,“On inferring autonomous system relationships in the internet”,In IEEE/ACM, vol.9, December, 2001, pp.733-725
[26]L.Gao,J.Rexford,“Stable Internet Routing Without   Global Coordination”,In IEEE/ACMTransactions on Networking (TON), vol.9,December , 2001, pp.681-69