Email this article Traffic-Aware Frequent Elements Matching Algorithms for Deep Packet Inspection
Abstract
Deep packet inspection sometimes is called application level semantic detection, which capable of examining the content of data packets in order to provide application-specific services and improve network security. Application traffic classification based on regular expressions is an essential step for deep packet inspection. However regular expression, especially multiple regular expressions matching is known to require intensive system resources and is often a performance bottleneck. Currently, the DFAs of regular expression are constructed in the preprocessing stage and the context of network streams is excluded which leads to low throughputs. In this paper, we analyzed the application level protocols and found that the protocols are uniformly distributed and it is changing dynamically. From the protocol distribution characteristic, we proposed an adaptive multiple regular expressions matching method for application traffic classification with deep packet inspection. The adaptive method, schedule the multiple DFAs through splay tree by matching probability other than linear scheduling in linked list, can adjust scheduling sequence according with the changing dynamic traffics. We evaluate the proposed method with the L7 rules; experiments proved that our method can improve the throughputs more than three times.
Keywords
References
[1] IANA: TCP and UDP port numbers”. http://www.iana.org/ assignm ents/port-numbers.
[2] A. Madhukar and C. Williamson. ”A Longitudinal Study of P2P Traffic Classification”. MASCOTS 2006.
[3] J. Levandoski, E. Sommer, and M. Strait.” Application Layer Packet Classifier for Linux”. http://l7-filter.sourceforge.net/.
[4] The world’s most popular network protocol analyzer”. http://www.ethereal.com/.
[5] Broadband World Forum Europe 2009. http://blog.ipoque.com/2009/09/dpi-the-end-of-the-internet/#more-377.
[6] A. C. Yao. “The complexity of pattern matching for a random string”. SIAM Journal of Computing, 8(3):368-387, 1979.
doi:10.1137/0208029
[7] G. Navarro, and K. Fredriksson. “Average complexity of exact and approximate multiple string matching”. Theoretical Computer Science, 321(2-3):283-290, 2004
doi:10.1016/j.tcs.2004.03.058
[8] N. Tuck, T. Sherwood, B. Calder, and G. Varghese. “Deterministic memory-efficient string matching algorithms for intrusion detection”. In Proceedings of the IEEE INFOCOM Conference, 2004, pp. 333-340.
[9] J. Moscola, J. Lockwood, R. P. Loui, and M. Pachos. “Implementation of a content-scanning module for an internet firewall”. Proceedings of IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), Napa, CA, April 2003, pp.31-38.
[10] F. Yu, R.H. Katz, and T.V. Lakshman, Gigabit rate packet patternmatching using TCAM, Proceedings of the network protocols, 12th IEEE International Conference on (ICNP04), Oct. 2004, pp.174-183.
[11] S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood. “Deep packet inspection using parallel Bloom filters”. IEEE Micro, Vol. 24, No. 1, 2004, pp. 52-61.
doi:10.1109/MM.2004.1268997
[12] SNORT Network Intrusion Detection System”. http://www.snort.org.
[13] K. Thompson. ”Programming Techniques: Regular expression search algorithm”. Communications of the ACM, 11(6):419-422, 1968.
doi:10.1145/363347.363387
[14] V-M.Gluskov. ”The abstract theory of automata”. Russian Mathematical Surveys, 16:1-53, 1961.
doi:10.1070/RM1961v016n05ABEH004112
[15] K. Lan and J. Heidemann. On the correlation of internet flow characteristics. Technical Report ISI-TR-574, USC/ISI, 2003.
[16] T. Karagiannis, A. Broido, N. Brownlee, K. Claffy, and M. Faloutsos. ”Is P2P dying or just hiding?”. In IEEE Globecom 2004, Dallas/Texas, USA, Nov, 2004.
[17] http://www.ipoque.com/resources/internet-studies/internet-study-2007
[18] CNCERT’s (Chinese Network Center for Emergency and Reponses) traffic statistics in 2008.
[19] A. El-Atawy, T. Samak, E. Al-Shaer, and H. Li. On using online traffic statistical matching for optimizing packet filtering performance. In IEEE INFOCOM’07, May 2007.
[20] Adel El-Atawy, Ehab Al-Shaer, Tung Tran, Raouf Boutaba, "Adaptive Early Packet Filtering for Defending Firewalls against DoS Attacks", In the 28th Annual IEEE Conference on Computer Communications (INFOCOM'09), Rio De Janeiro, Brazil, April 2009.
[21] H. Hamed, A. El-Atawy, and E. Al-Shaer. Adaptive statistical optimization techniques for firewall packet filtering. In IEEE INFOCOM’06, April 2006.
[22] A. El-Atawy, T. Samak, E. Al-Shaer, and H. Li. On using online traffic statistical matching for optimizing packet filtering performance. In IEEE INFOCOM’07, May 2007.
[23] Hazem Hamed and Ehab Al-Shaer. Dynamic rule-ordering optimization for high-speed firewall filtering. In ASIACCS ’06: Proceedings of the 2006 ACM Symposium on Information, computer and communications security, pages 332–342, New York, NY, USA, 2006. ACM.
[24] Qunfeng Dong, Suman Banerjee, Jia Wang, and Dheeraj Agrawal. Wire speed packet classification without tcams: a few more registers (and a bit of logic) are enough. SIGMETRICS Perform. Eval. Rev., 35(1):253–264, 2007.
doi:10.1145/1269899.1254914
[25] H. Hamed and E. Al-Shaer. Adaptive statistical optimization techniques for firewall packet filtering. Technical Report TR-05-012, DePaul University, 2005.
[26] Daniel Dominic Sleator, Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985.
doi:10.1145/3828.3835
Full Text: PDF