近年來網際網路的發展相當迅速，各種與網路相關的應用相當廣泛，但同時也產生了許多網路安全的問題。由於攻擊者可以偽造來源IP隱藏自己的位置並發動攻擊，因此要找出攻擊者相當困難。目前已經有許多研究提出各種封包溯源機制，其中封包轉存機制只需單一封包就能追踨到攻擊者，但它需要大量的儲存空間；封包標記機制雖然不需要在路由器上儲存封包資訊，但它需要收集大量的攻擊封包；複合封包溯源機制結合了封包轉存機制及封包標記機制，可做到單一封包追蹤，且減少路由器轉存所需的儲存量。然而根據其轉存方式的不同又可分為轉存封包摘要以及轉存路徑資訊等兩類。轉存封包摘要的這類方法儲存量將隨著封包數量增加而成長，另一類的方法儲存量則可受到路徑數目的控制。在本篇論文中，我們將提出一個轉存路徑資訊的低儲存量16位元標記複合封包溯源機制。我們比較現有轉存路徑資訊的複合封包溯源機制RIHT以及HAHIT。RIHT與HAHIT不會受到封包數量影響，相較之下前者使用32位元標記機制會有封包重組的問題，後者使用16位元標記機制解決了封包重組的問題但儲存量卻比前者來的高。我們的方法除了具備單一封包溯源、不受封包數量影響的特性以及使用16位元標記機制解決封包重組問題等優點，同時也針對其轉存機制與儲存量來改善，在worst case的情況下我們較HAHIT下降66%的儲存量，在average case的情況下我們的儲存需求甚至比使用32bits封包標記欄位的RIHT還低。

The Internet technology has been widely applied in many areas in the past decades and therefore its security issues have also attracted more and more concern. Because adversaries may spoof their source IPs and launch attacks, many traceback schemes have been proposed to identify the attack source. Packet logging uses only one packet to achieve IP traceback, but it requires much storage. Packet marking does not need to store any packet information on the routers, but it has to collect a large amount of attacking packets. Hybrid IP traceback schemes combine the two methods, using only one packet for traceback and reducing the storage requirements during packet logging. Current hybrid IP traceback schemes have two logging methods: logging of packet digests; logging of route info. While the first method’s storage requirements increase with the rise of packet numbers, the second method’s storage requirements are bounded by route numbers. Thus, we propose a 16-bit hybrid IP traceback scheme with low storage requirements. We analyze and compare current related schemes RIHT and HAHIT. Both of their performance is not affected by packet numbers. But RIHT’s marking field takes 32 bits and may lead to the failure of packet re-assembly. HAHIT uses 16 bits as its marking field to prevent the failure but pushes up its storage requirements. The main contributions of our scheme include: we use only one single packet for traceback; our performance is not affected by packet numbers; it is fragment compatible; we improve the logging method and decrease the storage requirements. Compared with HAHIT in the worst case, ours can decrease the storage requirements by 66%. In the average case, we can even keep our storage requirements lower than RIHT, whose marking field takes 32 bits.

摘要 I
Abstract II
誌謝 III
圖目錄 V
表目錄 VI
一、 前言 1
二、 我們的方法 6
2.1 標記和轉存機制 9
2.2 重建路徑 14
三、 實驗分析 18
3.1 實驗環境 18
3.2 路由器維度對轉存表大小的影響 18
3.3 threshold與轉存表大小對轉存次數的影響 20
3.4 儲存量分析 21
3.5 計算量分析 24
3.6 誤判率及漏判率 25
四、 結論 27
五、 參考文獻 28

圖 1. IP表頭中的標記欄位 6
圖 2. 網路拓撲 7
圖 3. 單一轉存表HTK之範例 10
圖 4. 封包標記及轉存演算法 12
圖 5. 標記、轉存與路徑重建實例 14
圖 6. 重建路徑演算法 16
圖 7. 路徑長度分佈 18
圖 8. 路由器維度對轉存表大小的影響 19
圖 9. 轉存表大小與THRESHOLD與平均轉存次數的關係 20
圖 10. 轉存次數比較 21
圖 11. WORST CASE儲存量比較 22
圖 12. AVERAGE CASE儲存量比較 23
圖 13. 總儲存量比較 23
圖 14. 重建路徑平均搜尋次數比較 25
圖 15. 誤判次數比較 26

表 1. 符號 7

[1]A. Belenky and N. Ansari, “Accommodating Fragmentation in Deterministic Packet Marking for IP Traceback,” IEEE Global Telecommunications Conference, vol. 3, pp. 1374–1378, Dec. 2003.
[2]A. Belenky and N. Ansari, “IP traceback with deterministic packet marking,” IEEE Communications Letters, vol. 7, no. 4, pp. 162–164, April 2003.
[3]A. Belenky and N. Ansari, “Tracing multiple attackers with deterministic packet marking (DPM),” IEEE Pacific Rim, vol.1, pp.49–52, Aug. 2003.
[4]A.C. Snoeren, C. Partridge, L.A. Sanchez, C.E. Jones, F. Tchakountio, B. Schwartz, S.T. Kent, and W.T. Strayer, “Single-packet IP traceback,” IEEE/ACM Transactions on Networking, vol.10, no.6, pp.721–734, Dec. 2002.
[5]A. Hussain, J. Heidemann, and C. Papadopoulos, “A Framework for Classifying Denial of Service Attacks,” in Proc. ACM SIGCOMM ’03, Karlsruhe, Germany, pp.99-110, Aug. 2003.
[6]A. Yaar, A. Perrig, and D. Song, “FIT: Fast Internet Traceback,” in Proc. IEEE INFOCOM2005, vol. 2, pp.1395–1406, Mar. 2005.
[7]Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Communications of the ACM, vol. 13, no. 7, pp. 422-426, July 1970.
[8]C. Gong and K. Sarac, “A More Practical Approach for Single-Packet IP Traceback Using Packet Logging and Marking,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, no. 10, pp.1310-1324, Oct. 2008.
[9]CIADA. (2003). CAIDA's Router-Level Topology Measurements [Online]. Available: http://www.caida.org/tools/measurement/skitter/router_topology/.
[10]CAIDA. (2010). CAIDA’s skitter project. [Online]. Available: http://www.caida.org/tools/skitter/.
[11]D. E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addision Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998, pp. 513-558.
[12]D. X. Song and A. Perrig, “Advanced and Authenticated Marking Chemes for IP Traceback,”IEEE INFOCOM2001, vol. 2, pp. 878-886, Apr. 2001.
[13]H. Tian, J. Bi, X. Jiang and W. Zhang, “A Probabilistic Marking Scheme for Fast Traceback,” IEEE Computer Society 2010 Second International Conference on Evolving Internet, pp. 137–141, Sept. 2010.
[14]I. Stocia and H. Zhang, “Providing Guaranteed Services Without Per Flow Management,” in Proc. ACM SIGCOMM’99, vol. 29, pp. 81-94, Oct. 1999.
[15]J. Liu, Z.J. Lee and Y.C. Chung, “Dynamic Probabilistic Packet Marking for Efficient IP Traceback,” Computer Network, vol. 51, pp. 866-882, Feb. 2007.
[16]K. H. Choi and H. K. Dai, “A Marking Scheme Using Huffman Codes for IP Traceback,”The 7th International Symposium on Parallel Architectures, Algorithms and Networks (SPAN’04), pp. 421-428, May 2004.
[17]L. Zhang and Y. Guan, ”TOPO: A Topology-aware Single Packet Attack Traceback Scheme,”IEEE International Conference on Security and Privacy in Communication Networks (SecureComm 2006), pp. 1-10, Aug. 2006.
[18]M.H. Yang and M.C. Yang, “RIHT: A Novel Hybrid IP Traceback Scheme,” IEEE Transactions on Information Forensics and Security , vol. 7, no. 4, pp. 789-797, Apr. 2012.
[19]S. Malliga and A. Tamilarasi, “A Hybrid Scheme Using Packet Marking and Logging for IP Traceback,” International Journal of Internet Protocol Technology, vol. 5, no. 1/2, pp. 81-91, Apr. 2010.
[20]S. Malliga and A. Tamilarasi, “A Proposal for New Marking Scheme with Its Performance Evaluation for IP Traceback,” WSEAS Transactions on Computer Research, vol. 3, no. 4, pp. 259-272, Apr. 2008.
[21]S. Savage, D. Wetherall, A. Karlin, and T. Anderson, “Network Support for IP Traceback,” IEEE/ACM Transactions on Networking, vol. 9, no. 3, pp. 226-237, June 2001.
[22]Security Assessment of the Internet Protocol Version 4, IETF RFC 6274, July 2011.
[23]V.Paruchuri, A.Durresi and S.Chellapan, “TTL based Packet Marking for IP Traceback,” IEEE GLOBECOM 2008, pp. 1-5, Nov. 30 2008-Dec. 4 2008.
[24]W. John and S. Tafvelin, “Analysis of Internet Backbone Traffic and Header Anomalies observed,”IMC’07: 7th ACM SIGCOMM conference on Internet measurement, pp. 111-116, 2007.
[25]Ning Lu, Yulong Wang, Fangchun Yang, Maotong Xu, “A Novel Approach for Single-Packet IP Traceback Based on Routing Path,”pdp, pp.253-260, 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing, 2012.
[26]Y. Wang, S. Su, Y. Yang, J. Ren, “A More Efficient Hybrid Approach for Single-Packet IP Traceback,” Parallel, Distributed and Network-Based Processing (PDP), 2012 20th Euromicro International Conference on. IEEE, 2012.
[27]M.H. Yang, “Hybrid Single-Packet IP Traceback with Low Storage and High Accuracy,” The Scientific World Journal , Dec. 2013.
[28]V. K. Soundar Rajam, and S. Shalinie. “A Novel Traceback Algorithm for DDoS Attack with Marking Acheme for Online System,” Recent Trends In Information Technology (ICRTIT), 2012 International Conference on. IEEE, 2012.
[29]Saurabh S. and A.S. Sairam. “Linear and Remainder Packet Marking for fast IP traceback,” Communication Systems and Networks (COMSNETS), 2012 Fourth International Conference on. IEEE, 2012.
[30]H. Tian, J. Bi, and P. Xiao. “A Flow-Based Traceback Scheme on an AS-Level Overlay Network,” Distributed Computing Systems Workshops (ICDCSW), 2012 32nd International Conference on. IEEE, 2012.
[31]E. Hilgenstieler, E.P. Duarte Jr., G. Mansfield-Keeni, N. Shiratori.“Extensions to The Source Path Isolation Engine for Precise and Efficient Log-based IP Traceback, ” Computers &; Security 29.4 (2010): 383-392.