Linux环境下基于正则表达式的DDoS防御算法研究及实现
摘要
随着Internet的发展,网络安全问题日益突出,其中分布式拒绝服务(Distributed Denial of Service,DDoS)攻击是当今Internet面临的主要威胁之一,更为严重的是现在尚无完全令人满意的防护手段和攻击检测手段,因此为其设计有效的防护手段和攻击检测手段是当前维护网络安全的重要目标。
DDoS(分布式拒绝服务攻击)是一种攻击强度大、危害严重的攻击方式。它利用合理的请求来占用过多的服务器资源,致使服务器超载,无法响应其他的请求。因为这种攻击一般通过分布在不同计算机上的攻击进程进行攻击,同时运用IP欺骗和洪水攻击等手段,因此对它进行检测和防御就非常困难。
相对于传统的模式匹配,正则表达式具有灵活高效的特点。随着DDoS防御检测技术的发展,传统上用于过滤数据包内容的模式集合(包含模式的匹配串)逐渐被正则表达式集合所代替。例如Linux的应用协议分类器L7-filter (Linux Application Protocol Classifier),通过基于正则表达式的模式集合识别应用层的数据包。目前,如何提高基于正则表达式的深度包检测技术的效率,是DDoS防御检测工作重点。
本文提出了一种新的基于正则表达式的匹配算法,在深入分析了DFA (Deterministic Finite Automaton)状态数对算法性能影响的基础上,本文进一步提出了构造最优DFA状态数的算法,该算法保证在任意有限的系统资源下算法具有优化的时间复杂度。在Linux环境下实现了该算法,并对基于L7-filter模式集合的网络数据包进行了大量对比实验。实验数据表明,与已有算法相比该算法具有优化的时间复杂度。
With the rapid development of Internet, network security is becoming more and more critical, DDoS(Distributed Denial of Services)attacks is one of the primary threats in today’s Internet, further more, there is no completely satisfying protective and detective means of attacks yet, so it is an very important target in the network security field to design more effective security solution and attack detection module.
Defense against DDoS(distributed denial-of-service)attacks is one of the hardest security problems on the Internet. Attackers usually send too many requests for service to engross the resource on the server, and server can not provide service for real request because of overloading. This kind of attack always control many computers distributed on the internet to attack the server. Mendacious IP and Flooding attack mode is also used in the attack. So it is very hard to detect and defend DDoS attack.
Traditional string-set-based defense technology is being replaced by regular expression-set-based technology. For example, in Linux Application Protocol classifier (L7-filter), all protocol identifiers are expressed as regular expressions. Similarly, Snort and Bro intrusion detection systems also use regular expressions as pattern language.
By analyzing the merits and demerits of the classical pattern matching algorithms, a new Pattern matching algorithm based regular expression which was proposed in this Paper. Based on the analysis of the impact of number of DFA states to the algorithm performance, further improvement to the algorithm was made by introducing a DFA state number optimization algorithm. The proposed algorithm has been implemented in Linux environment and lots of experiments have been done. Experimental results show that the performance of the proposed algorithm is much better than others.
DDoS(分布式拒绝服务攻击)是一种攻击强度大、危害严重的攻击方式。它利用合理的请求来占用过多的服务器资源,致使服务器超载,无法响应其他的请求。因为这种攻击一般通过分布在不同计算机上的攻击进程进行攻击,同时运用IP欺骗和洪水攻击等手段,因此对它进行检测和防御就非常困难。
相对于传统的模式匹配,正则表达式具有灵活高效的特点。随着DDoS防御检测技术的发展,传统上用于过滤数据包内容的模式集合(包含模式的匹配串)逐渐被正则表达式集合所代替。例如Linux的应用协议分类器L7-filter (Linux Application Protocol Classifier),通过基于正则表达式的模式集合识别应用层的数据包。目前,如何提高基于正则表达式的深度包检测技术的效率,是DDoS防御检测工作重点。
本文提出了一种新的基于正则表达式的匹配算法,在深入分析了DFA (Deterministic Finite Automaton)状态数对算法性能影响的基础上,本文进一步提出了构造最优DFA状态数的算法,该算法保证在任意有限的系统资源下算法具有优化的时间复杂度。在Linux环境下实现了该算法,并对基于L7-filter模式集合的网络数据包进行了大量对比实验。实验数据表明,与已有算法相比该算法具有优化的时间复杂度。
With the rapid development of Internet, network security is becoming more and more critical, DDoS(Distributed Denial of Services)attacks is one of the primary threats in today’s Internet, further more, there is no completely satisfying protective and detective means of attacks yet, so it is an very important target in the network security field to design more effective security solution and attack detection module.
Defense against DDoS(distributed denial-of-service)attacks is one of the hardest security problems on the Internet. Attackers usually send too many requests for service to engross the resource on the server, and server can not provide service for real request because of overloading. This kind of attack always control many computers distributed on the internet to attack the server. Mendacious IP and Flooding attack mode is also used in the attack. So it is very hard to detect and defend DDoS attack.
Traditional string-set-based defense technology is being replaced by regular expression-set-based technology. For example, in Linux Application Protocol classifier (L7-filter), all protocol identifiers are expressed as regular expressions. Similarly, Snort and Bro intrusion detection systems also use regular expressions as pattern language.
By analyzing the merits and demerits of the classical pattern matching algorithms, a new Pattern matching algorithm based regular expression which was proposed in this Paper. Based on the analysis of the impact of number of DFA states to the algorithm performance, further improvement to the algorithm was made by introducing a DFA state number optimization algorithm. The proposed algorithm has been implemented in Linux environment and lots of experiments have been done. Experimental results show that the performance of the proposed algorithm is much better than others.
引文
[1] David Moore, Geoffrey M. Voelker, and Stefan Savage. Inferring Internet denial-ofservice activity. In 10th Usenix Security Symposium[J]. 2001:324-325.
[2] http://www.cert.org/incidentee notes/IN-2000-04.htm1[EB/OL].
[3] P. Ferguson and D. Senie, Network ingress filtering: Defeating denial of service attacks which employ IP source address spoofing, RFC 2267[J]. 1998:872-880.
[4] Hevin Houle and George Weaver. Trends in denial of service[J]. 2000:332-343.
[5] Vern Paxson. An analysis of using reflectors for Distributed Denial-of-Service Attacks[J]. ACM Computer Communications Review (CCR), 31(3). 2001:288-291.
[6] CERT Coordination Center.TCP SYN flooding and IP spoofing attacks[EB/OL]. http://www.cert.org/advisories/CA-1996-21.html.
[7] D.J.Bernstein and Eric Schenk. Linux Kernel SYN Cookies Firewall Project"[EB/OL]. http://www.bronzesoft.org/projects/scfw.
[8] J.Lemon. Resisting SYN Flooding DoS Attacks with a SYN Cache[R]. Proceedings of USENIX BSD Conference. 2002:561-588.
[9] Check Point Software Technologies Ltd. SynDefender[EB/OL]. http://www.checkpoint com/products/ firewall-1.
[10] Netscreen 100 Firewall Appliance[EB/OL]. http://www.netscreen.com/.
[11] H.Wang, D. Zhang, and K. Cx Shin. SYN-dog[R]: Sniffing SYN Flooding Sources. Proc. of 22nd International Conference on Distributed Computing Systems (ICDCS'02). 2002:1099-1104.
[12] Felix Lau, Stuart H.Rubin, Michael H.Smith, Ljiljana Trajkovic. Distributed denial of service attacks[R]. IEEE International Conference on Systems, Man, and Cybernetics. 2000: 2275-2280.
[13] David Mankins, Rajesh Krishnan, Ceilyn Boyd, John Zao, Michael Frentz. Mitigating distributed denial of service attacks with dynamic resource pricing[R]. Proceedings of Annual Computer Security Applications Conference (ACSAC 2001). 2001: 411-421.
[14] Tieyan Li, Wai-Meng Chew, Kwok-Yan Lam. Defending against distributed denial of service attacks using resistant mobile agent architecture[R]. Proceedings of Parallel and Distributed Processing Symposium (IPDPS 2002). 2002: 216-224.
[15] Nathalie Weiler, Honeypots. distributed denial-of-service attacks[R]. Proceedings of Infrastructure for Collaborative enterprises (WET ICE 2002). 2002:109-114.
[16] Jelena Mirkovic, Gregory Prier, Peter Reiher. Source-end DDoS defense[R]. Second IEEE International Symposium on Network Computing and Applications(NCA 2003). 2003:171-178.
[17] Roshan Thomas, Brian Mark, Tommy Johnson, James Croall. NetBouncer client-legitimacy-based high-performance DDoS filtering[R]. Proceedings of DARPA Information Survivability Conference and Exposition. 2003: 14- 25.
[18] Tao Peng, Christopher Leckie, Kotagiri Ramamohanarao. Protection from distributed denial of service attacks using history-based IP filtering[R]. IEEE International Conference on Communications (ICC '03) 2003,5: 482-486.
[19] Gaeil Ahn, Kiyoung Kim, Jongsoo Jang. MF (minority first) scheme for defeating distributed denial of service attacks[R]. Proceedings of the Eighth IEEE International Computers and Communication Symposium (ISCC 2003). 2003:1233- 1238.
[20] Udaya Kiran Tupakula, Vijay Varadharajan. Counteracting DDoS attacks in multiple ISP domains using routing arbiter architecture[R]. The 11th IEEE International Conference on Networks (ICON2003). 2003: 455-460.
[21] Laura Feinstein, Dan Schnackenberg, Ravindra Balupari, Darrell Kindred. Statisticalapproaches to DDoS attack detection and response[R]. Proceedings of DARPA Information Survivability Conference and Exposition. 2003: 303-314.
[22] Abraham Yaar Adrian Perrig Dawn Song. a stateless Internet flow filter to mitigate DDoS flooding attacks[R]. Proceedings of the 2004 IEEE Symposium on Security and Privacy. 2004:1-14.
[23] Udaya Kiran Tupakula Vijay Varadharajan Ashok Kumar Gajam. CounteractingTCP SYN DDoS Attacks using Automated Model[R]. IEEE Communications Society Globecom. 2004:2240-2245.
[24] http://baike.baidu.com/view/5522.htm?fr=ala0[EB/OL].
[25] Mooi Choo Chuah, Wing Cheong Lau, Yoohwan Kim, H. Jonathan Chao. Transient Performance of PacketScore for blocking DDoS attacks[R]. IEEE Communications Society. 2004,4: 1892-1896.
[26] Yoohwan Kim, Wing Cheong Lau, Mooi Choo Chuah, H. Jonathan Chao. Packet Score: Statistics-based Overload Control against Distributed Denial-of-Service Attacks[R]. IEEE INFOCOM 2004. 2004.
[27] Carl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh Venkatesh. DoS Protection for Reliably Authenticated Broadcast[R]. NDSS 2004. 2004.
[28] Angelos Stavrou Angelos D. Keromytis Jason Nieh Vishal Misra Dan Rubenstein. MOVE: An End-to-End Solution To Network Denial of Service[R]. The 12th Annual Network and Distributed System Security Symposium. 2005.
[29]汤丽娟,张永平,张立莉.一种全面主动的防御DDo s攻击方案[J].微计算机信息(管控一体化),23 (6-3). 2007:35-37.
[31]刘飞,史小敏.基于Linux网关的DoS/DDoS防护系统的设计与实现[J].计算机工程,12(30). 2004:576-578.
[32] Jeffrey E.F. Friedl.精通正则表达式[M].余晟.北京:电子工业出版社, 2007.
[33]陈波. S YN Flo o d攻击的原理、实现与防范[J].计算机应用研究, 2003:80-83.
[34]张娜.基于正则表达式的深度包检测研究[D].上海:华东师范大学, 2007.
[35] A. V Aho and M. J. Corasick. Client string matching: An aid to bibliographic search[J]. Comm. of the ACM, 18(6). 1975:333-340.
[36] Denial of Service Attacking with TCP SYN flooding [EB/OL]. http://www.cert . org. tw. J an. 2000.
[37]刘俊超,赵国鸿,陈曙辉.一种用于深度报文检测的DFA状态表压缩方法[J].计算机工程与应用,44(22). 2008:74-76
[38]邓萍丽.基于L7-filter的应用跟踪系统设计[D].广州:中山大学, 2009.
[2] http://www.cert.org/incidentee notes/IN-2000-04.htm1[EB/OL].
[3] P. Ferguson and D. Senie, Network ingress filtering: Defeating denial of service attacks which employ IP source address spoofing, RFC 2267[J]. 1998:872-880.
[4] Hevin Houle and George Weaver. Trends in denial of service[J]. 2000:332-343.
[5] Vern Paxson. An analysis of using reflectors for Distributed Denial-of-Service Attacks[J]. ACM Computer Communications Review (CCR), 31(3). 2001:288-291.
[6] CERT Coordination Center.TCP SYN flooding and IP spoofing attacks[EB/OL]. http://www.cert.org/advisories/CA-1996-21.html.
[7] D.J.Bernstein and Eric Schenk. Linux Kernel SYN Cookies Firewall Project"[EB/OL]. http://www.bronzesoft.org/projects/scfw.
[8] J.Lemon. Resisting SYN Flooding DoS Attacks with a SYN Cache[R]. Proceedings of USENIX BSD Conference. 2002:561-588.
[9] Check Point Software Technologies Ltd. SynDefender[EB/OL]. http://www.checkpoint com/products/ firewall-1.
[10] Netscreen 100 Firewall Appliance[EB/OL]. http://www.netscreen.com/.
[11] H.Wang, D. Zhang, and K. Cx Shin. SYN-dog[R]: Sniffing SYN Flooding Sources. Proc. of 22nd International Conference on Distributed Computing Systems (ICDCS'02). 2002:1099-1104.
[12] Felix Lau, Stuart H.Rubin, Michael H.Smith, Ljiljana Trajkovic. Distributed denial of service attacks[R]. IEEE International Conference on Systems, Man, and Cybernetics. 2000: 2275-2280.
[13] David Mankins, Rajesh Krishnan, Ceilyn Boyd, John Zao, Michael Frentz. Mitigating distributed denial of service attacks with dynamic resource pricing[R]. Proceedings of Annual Computer Security Applications Conference (ACSAC 2001). 2001: 411-421.
[14] Tieyan Li, Wai-Meng Chew, Kwok-Yan Lam. Defending against distributed denial of service attacks using resistant mobile agent architecture[R]. Proceedings of Parallel and Distributed Processing Symposium (IPDPS 2002). 2002: 216-224.
[15] Nathalie Weiler, Honeypots. distributed denial-of-service attacks[R]. Proceedings of Infrastructure for Collaborative enterprises (WET ICE 2002). 2002:109-114.
[16] Jelena Mirkovic, Gregory Prier, Peter Reiher. Source-end DDoS defense[R]. Second IEEE International Symposium on Network Computing and Applications(NCA 2003). 2003:171-178.
[17] Roshan Thomas, Brian Mark, Tommy Johnson, James Croall. NetBouncer client-legitimacy-based high-performance DDoS filtering[R]. Proceedings of DARPA Information Survivability Conference and Exposition. 2003: 14- 25.
[18] Tao Peng, Christopher Leckie, Kotagiri Ramamohanarao. Protection from distributed denial of service attacks using history-based IP filtering[R]. IEEE International Conference on Communications (ICC '03) 2003,5: 482-486.
[19] Gaeil Ahn, Kiyoung Kim, Jongsoo Jang. MF (minority first) scheme for defeating distributed denial of service attacks[R]. Proceedings of the Eighth IEEE International Computers and Communication Symposium (ISCC 2003). 2003:1233- 1238.
[20] Udaya Kiran Tupakula, Vijay Varadharajan. Counteracting DDoS attacks in multiple ISP domains using routing arbiter architecture[R]. The 11th IEEE International Conference on Networks (ICON2003). 2003: 455-460.
[21] Laura Feinstein, Dan Schnackenberg, Ravindra Balupari, Darrell Kindred. Statisticalapproaches to DDoS attack detection and response[R]. Proceedings of DARPA Information Survivability Conference and Exposition. 2003: 303-314.
[22] Abraham Yaar Adrian Perrig Dawn Song. a stateless Internet flow filter to mitigate DDoS flooding attacks[R]. Proceedings of the 2004 IEEE Symposium on Security and Privacy. 2004:1-14.
[23] Udaya Kiran Tupakula Vijay Varadharajan Ashok Kumar Gajam. CounteractingTCP SYN DDoS Attacks using Automated Model[R]. IEEE Communications Society Globecom. 2004:2240-2245.
[24] http://baike.baidu.com/view/5522.htm?fr=ala0[EB/OL].
[25] Mooi Choo Chuah, Wing Cheong Lau, Yoohwan Kim, H. Jonathan Chao. Transient Performance of PacketScore for blocking DDoS attacks[R]. IEEE Communications Society. 2004,4: 1892-1896.
[26] Yoohwan Kim, Wing Cheong Lau, Mooi Choo Chuah, H. Jonathan Chao. Packet Score: Statistics-based Overload Control against Distributed Denial-of-Service Attacks[R]. IEEE INFOCOM 2004. 2004.
[27] Carl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh Venkatesh. DoS Protection for Reliably Authenticated Broadcast[R]. NDSS 2004. 2004.
[28] Angelos Stavrou Angelos D. Keromytis Jason Nieh Vishal Misra Dan Rubenstein. MOVE: An End-to-End Solution To Network Denial of Service[R]. The 12th Annual Network and Distributed System Security Symposium. 2005.
[29]汤丽娟,张永平,张立莉.一种全面主动的防御DDo s攻击方案[J].微计算机信息(管控一体化),23 (6-3). 2007:35-37.
[31]刘飞,史小敏.基于Linux网关的DoS/DDoS防护系统的设计与实现[J].计算机工程,12(30). 2004:576-578.
[32] Jeffrey E.F. Friedl.精通正则表达式[M].余晟.北京:电子工业出版社, 2007.
[33]陈波. S YN Flo o d攻击的原理、实现与防范[J].计算机应用研究, 2003:80-83.
[34]张娜.基于正则表达式的深度包检测研究[D].上海:华东师范大学, 2007.
[35] A. V Aho and M. J. Corasick. Client string matching: An aid to bibliographic search[J]. Comm. of the ACM, 18(6). 1975:333-340.
[36] Denial of Service Attacking with TCP SYN flooding [EB/OL]. http://www.cert . org. tw. J an. 2000.
[37]刘俊超,赵国鸿,陈曙辉.一种用于深度报文检测的DFA状态表压缩方法[J].计算机工程与应用,44(22). 2008:74-76
[38]邓萍丽.基于L7-filter的应用跟踪系统设计[D].广州:中山大学, 2009.