Bitmaps & Bitmasks: Efficient Tools to Compress Deterministic Automata
Main Article Content
Keywords
Deep Packet Inspection, Network Security, Regular Expressions, Finite Automata, Transition Compression
Abstract
Accelerating the signature matching function is essential to perform Deep Packet Inspection (DPI) at line rates. The conversion of the signatures into the Deterministic Finite Automaton (DFA) enables performance of this function at linear time. However, since the DFA is extremely storage inefficient, it is compressed before being stored in the memory. Although state-of-the-art bitmap-based compression algorithms can perform line rate signature matching, they only achieve transition compression of ~90-95%. Addressing the storage inefficiency, two bitmap-based transition compression algorithms were proposed by Subramanian et al. in 2016 to achieve transition compression of over 98%. A theoretical relationship is established in this article between the achievable signature matching throughput and the number of pipeline stages required to perform the decompression through the hardware accelerator based on the proposed techniques. Additional optimizations are proposed and evaluated to improve the per-stream signature matching throughput through the proposed decompression engines. The experimental evaluation of the optimizations shows that the per-stream signature matching throughput can be improved by a factor of 1.2–1.4x. A software model of the proposed decompression engines was designed and evaluated across a multitude of payload byte streams to verify the functional correctness of the proposed compression methods.
Downloads
Download data is not yet available.
References
Basu, A; Narlikar, G. 2005. ‘Fast incremental updates for pipelined forwarding engines’. IEEE/ACM Transactions on Networking, 690-703.
Becchi, M. 2016. Regular Expression Processor. Retrieved from http://regex.wustl.edu/
Becchi, M; Crowley, P. 2007a. ‘An improved algorithm to accelerate regular expression evaluation’. 3rd ACM/IEEE Symposium on Architecture for networking and communications systems (pp. 145-154). Florida: ACM.
Becchi, M; Crowley, P. 2007b. ‘A hybrid finite automaton for practical deep packet inspection’. CoNEXT '07, Proceedings of the 2007 ACM CoNEXT conference. New York.
Becchi, M; Crowley, P. 2013. ‘A-DFA: A Time- and Space-Efficient DFA Compression Algorithm’. ACM Transactions on Architecture and Code Optimization, 4:1-4:26.
Chen, X; Jones, B; Becchi, M; Wolf, T. 2016. ‘Picking Pesky Parameters: Optimizing Regular Expression Matching in Practice’, IEEE Transactions on Parallel and Distributed Systems, 27 (5), May, pp. 1430-1442.
Cong, L; Yan, P; Ai, C; Jie, W. 2014. ‘A DFA with Extended Character-Set for Fast Deep Packet Inspection’. IEEE Transactions on Computers, 1925-1936.
Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C. 2009. Introduction to Algorithms, Third Edition. MIT Press.
Ficara, D; Giordano, S; Procissi, G; Vitucci, F; Antichi, G; Pietro, AD. 2008. ‘An improved DFA for fast regular expression matching’. ACM SIGCOMM Computer Communication Review, 38(5), 29-40.
Handley, M; Paxson, V; Kreibich, C. 2001. ‘Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantics’. Proceedings of the 10th USENIX Symposium. Washington D.C.
Holcomb, J. 2016. securityevaluators.com. Retrieved 26 March 2016 from https://securityevaluators.com/knowledge/presentations/soho_defcon21.pdf
John, EH; Rajeev, M; Ullman, JD. 2007. Introduction to Automata Theory, Languages, and Computation, 3rd Edition. Pearson.
Kumar, S; Dharmapurikar, S; Yu, F; Crowley, P; Turner, J. 2006. ‘Algorithms to accelerate multiple regular expressions matching for deep packet inspection’. ACM SIGCOMM. New York.
Lunteren, JV; Guanella, A. 2012. ‘Hardware-accelerated regular expression matching at multiple tens of Gb/s’. INFOCOM, 2012 Proceedings IEEE. Orlando.
Michela, B; Mark, F; Patrick, C. 2008. ‘A workload for evaluating deep packet inspection architectures’. IEEE International Symposium on Workload Characterization, 2008. IISWC 2008 (pp. 79-89).
Nourani, M; P.Katta. 2007. ‘Bloom Filter Accelerator for String Matching’. Proc. ICCCN (pp. 185-190). Honolulu.
Paxson, V. 1999. ‘Bro: a system for detecting network intruders in real-time’. Computer Networks: The International Journal of Computer and Telecommunications Networking, 2435-2463. Retrieved from http://www.bro-ids.org/
Qi, Y; Wang, K; Fong, J; Xue, Y; Li, J; Jiang, W; Prasanna, V. 2011. ‘FEACAN: Front-end acceleration for content-aware network processing’. INFOCOM, 2011 Proceedings IEEE. Shanghai.
Rafael, A; Stenio, F; Djamel, S; Judith, K; Géza, S. 2012. ‘Deterministic Finite Automaton for scalable traffic identification: The power of compressing by range’. Network Operations and Management Symposium. IEEE.
Rafael, A; Stenio, F; Djamel, S; Judith, K; Géza, S. 2015. ‘Design and optimizations for efficient regular expression matching in DPI systems’. Computer Communications, 103-120.
Rajaraman, R; Sanu, M; Vasantha, E; Ram, K; Shay, G. 2008. ‘A 2.1 GHz 6.5 mW 64-bit Unified PopCount/BitScan Datapath Unit for 65 nm High-Performance Microprocessor Execution Cores’. 21st International Conference on VLSI Design (VLSID 2008). IEEE.
Ramanarayanan, R; Mathew, SK; Krishnamurthy, RK; Gueron, S; Erraguntla, VK. 2012. US Patent No. 8214414: Combined set bit count and detector logic.
Roesch, M. 1999. ‘Snort - Lightweight Intrusion Detection for Networks’. Proceedings of the 13th USENIX conference on System Administration (pp. 229-238). Washington. Retrieved from http://www.snort.org
Sappington, B. 2016. Parks Associates. Retrieved from http://www.jungo.com/wp-content/uploads/Jungo%20WP_CiscoUpdate3_3-11-13.pdf
Smith, R; Estan, C; Jha, S; Kong, S. 2008. ‘Deflating the big bang: fast and scalable deep packet inspection with extended finite automata’. Proceedings of the ACM SIGCOMM 2008 conference on Data communication. New York.
Song, H; Sproull, T; Attig, M; Lockwood, J. 2005. ‘Snort Offloader: A Reconfigurable Hardware NIDS Filter’. Proceedings of Field Programmable Logic and Applications.
Subramanian, SS; Lin, P; Herkersdorf, A. 2014. ‘Deep packet inspection in residential gateways and routers Issues and challenges’. 14th International Symposium on Integrated Circuits (ISIC). Singapore.
Subramanian, SS; Lin, P; Herkersdorf, A; Wild, T. 2016. ‘Hardware acceleration of signature matching through multi-layer transition bit masking’. International Telecommunication Networks and Applications Conference. Dunedin: IEEE.
Team Cymru Threat Intelligence Group. 2016. ‘SOHO Pharming’. Retrieved 26 March 2016, from https://www.doc.ic.ac.uk/~maffeis/331/TeamCymruSOHOPharming.pdf
Tuck, N; Sherwood, T; Calder, B; Varghese, G. 2004. ‘Deterministic memory-efficient string matching algorithms for intrusion detection’. INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong.
Wang, K; Qi, Y; Xue, Y; Li, J. 2011. ‘Reorganized and Compact DFA for Efficient Regular Expression Matching’. 2011 IEEE International Conference on Communications. Kyoto.
Wesley, M; Stenio, F; Rafael, A; Djamel, S; Judith, K; Szabó, G. 2012. ‘Benchmarking of compressed DFAs for traffic identification: Decoupling data structures from models’. IEEE Global Communications Conference. IEEE.
Xu, C; Chen, S; Su, J; Yiu, SM; Hui, LC. 2016. ‘A Survey on Regular Expression Matching for Deep Packet Inspection: Applications, Algorithms, and Hardware Platforms’. IEEE Communications Surveys & Tutorials, 18(4).
Yang, X; Junchen, J; Rihua, W; Yang, S; H. Jonathan, C. 2014. ‘TFA: A Tunable Finite Automaton for Pattern Matching in Network Intrusion Detection Systems’. IEEE Journal on Selected Areas in Communications, 1810-1821.
Yu, F; Chen, Z; Diao, Y; Lakshman, T; Katz, R. H. 2006. ‘Fast and memory-efficient regular expression matching for deep packet inspection’. Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems. New York.
Yu, X; Lin, B; Becchi, M. 2014. ‘Revisiting State Blow-Up: Automatically Building Augmented-FA While Preserving Functional Equivalence’. IEEE Journal on Selected Areas in Communications, 32(10), 1822-1833.
Zeydel, BR; Baran, D; Oklobdzija, VG. 2010. ‘Energy-Efficient Design Methodologies: High-Performance VLSI Adders’. IEEE Journal of Solid-State Circuits, 1220-1233.
Becchi, M. 2016. Regular Expression Processor. Retrieved from http://regex.wustl.edu/
Becchi, M; Crowley, P. 2007a. ‘An improved algorithm to accelerate regular expression evaluation’. 3rd ACM/IEEE Symposium on Architecture for networking and communications systems (pp. 145-154). Florida: ACM.
Becchi, M; Crowley, P. 2007b. ‘A hybrid finite automaton for practical deep packet inspection’. CoNEXT '07, Proceedings of the 2007 ACM CoNEXT conference. New York.
Becchi, M; Crowley, P. 2013. ‘A-DFA: A Time- and Space-Efficient DFA Compression Algorithm’. ACM Transactions on Architecture and Code Optimization, 4:1-4:26.
Chen, X; Jones, B; Becchi, M; Wolf, T. 2016. ‘Picking Pesky Parameters: Optimizing Regular Expression Matching in Practice’, IEEE Transactions on Parallel and Distributed Systems, 27 (5), May, pp. 1430-1442.
Cong, L; Yan, P; Ai, C; Jie, W. 2014. ‘A DFA with Extended Character-Set for Fast Deep Packet Inspection’. IEEE Transactions on Computers, 1925-1936.
Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C. 2009. Introduction to Algorithms, Third Edition. MIT Press.
Ficara, D; Giordano, S; Procissi, G; Vitucci, F; Antichi, G; Pietro, AD. 2008. ‘An improved DFA for fast regular expression matching’. ACM SIGCOMM Computer Communication Review, 38(5), 29-40.
Handley, M; Paxson, V; Kreibich, C. 2001. ‘Network Intrusion Detection: Evasion, Traffic Normalization, and End-to-End Protocol Semantics’. Proceedings of the 10th USENIX Symposium. Washington D.C.
Holcomb, J. 2016. securityevaluators.com. Retrieved 26 March 2016 from https://securityevaluators.com/knowledge/presentations/soho_defcon21.pdf
John, EH; Rajeev, M; Ullman, JD. 2007. Introduction to Automata Theory, Languages, and Computation, 3rd Edition. Pearson.
Kumar, S; Dharmapurikar, S; Yu, F; Crowley, P; Turner, J. 2006. ‘Algorithms to accelerate multiple regular expressions matching for deep packet inspection’. ACM SIGCOMM. New York.
Lunteren, JV; Guanella, A. 2012. ‘Hardware-accelerated regular expression matching at multiple tens of Gb/s’. INFOCOM, 2012 Proceedings IEEE. Orlando.
Michela, B; Mark, F; Patrick, C. 2008. ‘A workload for evaluating deep packet inspection architectures’. IEEE International Symposium on Workload Characterization, 2008. IISWC 2008 (pp. 79-89).
Nourani, M; P.Katta. 2007. ‘Bloom Filter Accelerator for String Matching’. Proc. ICCCN (pp. 185-190). Honolulu.
Paxson, V. 1999. ‘Bro: a system for detecting network intruders in real-time’. Computer Networks: The International Journal of Computer and Telecommunications Networking, 2435-2463. Retrieved from http://www.bro-ids.org/
Qi, Y; Wang, K; Fong, J; Xue, Y; Li, J; Jiang, W; Prasanna, V. 2011. ‘FEACAN: Front-end acceleration for content-aware network processing’. INFOCOM, 2011 Proceedings IEEE. Shanghai.
Rafael, A; Stenio, F; Djamel, S; Judith, K; Géza, S. 2012. ‘Deterministic Finite Automaton for scalable traffic identification: The power of compressing by range’. Network Operations and Management Symposium. IEEE.
Rafael, A; Stenio, F; Djamel, S; Judith, K; Géza, S. 2015. ‘Design and optimizations for efficient regular expression matching in DPI systems’. Computer Communications, 103-120.
Rajaraman, R; Sanu, M; Vasantha, E; Ram, K; Shay, G. 2008. ‘A 2.1 GHz 6.5 mW 64-bit Unified PopCount/BitScan Datapath Unit for 65 nm High-Performance Microprocessor Execution Cores’. 21st International Conference on VLSI Design (VLSID 2008). IEEE.
Ramanarayanan, R; Mathew, SK; Krishnamurthy, RK; Gueron, S; Erraguntla, VK. 2012. US Patent No. 8214414: Combined set bit count and detector logic.
Roesch, M. 1999. ‘Snort - Lightweight Intrusion Detection for Networks’. Proceedings of the 13th USENIX conference on System Administration (pp. 229-238). Washington. Retrieved from http://www.snort.org
Sappington, B. 2016. Parks Associates. Retrieved from http://www.jungo.com/wp-content/uploads/Jungo%20WP_CiscoUpdate3_3-11-13.pdf
Smith, R; Estan, C; Jha, S; Kong, S. 2008. ‘Deflating the big bang: fast and scalable deep packet inspection with extended finite automata’. Proceedings of the ACM SIGCOMM 2008 conference on Data communication. New York.
Song, H; Sproull, T; Attig, M; Lockwood, J. 2005. ‘Snort Offloader: A Reconfigurable Hardware NIDS Filter’. Proceedings of Field Programmable Logic and Applications.
Subramanian, SS; Lin, P; Herkersdorf, A. 2014. ‘Deep packet inspection in residential gateways and routers Issues and challenges’. 14th International Symposium on Integrated Circuits (ISIC). Singapore.
Subramanian, SS; Lin, P; Herkersdorf, A; Wild, T. 2016. ‘Hardware acceleration of signature matching through multi-layer transition bit masking’. International Telecommunication Networks and Applications Conference. Dunedin: IEEE.
Team Cymru Threat Intelligence Group. 2016. ‘SOHO Pharming’. Retrieved 26 March 2016, from https://www.doc.ic.ac.uk/~maffeis/331/TeamCymruSOHOPharming.pdf
Tuck, N; Sherwood, T; Calder, B; Varghese, G. 2004. ‘Deterministic memory-efficient string matching algorithms for intrusion detection’. INFOCOM 2004. Twenty-third Annual Joint Conference of the IEEE Computer and Communications Societies. Hong Kong.
Wang, K; Qi, Y; Xue, Y; Li, J. 2011. ‘Reorganized and Compact DFA for Efficient Regular Expression Matching’. 2011 IEEE International Conference on Communications. Kyoto.
Wesley, M; Stenio, F; Rafael, A; Djamel, S; Judith, K; Szabó, G. 2012. ‘Benchmarking of compressed DFAs for traffic identification: Decoupling data structures from models’. IEEE Global Communications Conference. IEEE.
Xu, C; Chen, S; Su, J; Yiu, SM; Hui, LC. 2016. ‘A Survey on Regular Expression Matching for Deep Packet Inspection: Applications, Algorithms, and Hardware Platforms’. IEEE Communications Surveys & Tutorials, 18(4).
Yang, X; Junchen, J; Rihua, W; Yang, S; H. Jonathan, C. 2014. ‘TFA: A Tunable Finite Automaton for Pattern Matching in Network Intrusion Detection Systems’. IEEE Journal on Selected Areas in Communications, 1810-1821.
Yu, F; Chen, Z; Diao, Y; Lakshman, T; Katz, R. H. 2006. ‘Fast and memory-efficient regular expression matching for deep packet inspection’. Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems. New York.
Yu, X; Lin, B; Becchi, M. 2014. ‘Revisiting State Blow-Up: Automatically Building Augmented-FA While Preserving Functional Equivalence’. IEEE Journal on Selected Areas in Communications, 32(10), 1822-1833.
Zeydel, BR; Baran, D; Oklobdzija, VG. 2010. ‘Energy-Efficient Design Methodologies: High-Performance VLSI Adders’. IEEE Journal of Solid-State Circuits, 1220-1233.
Article Sidebar
Published
Sep 24, 2018
Article Details
How to Cite
Subramanian, S. S., Lin, P., Herkersdorf, A., & Wild, T. (2018). Bitmaps & Bitmasks: Efficient Tools to Compress Deterministic Automata. Journal of Telecommunications and the Digital Economy, 6(3), 41–75. https://doi.org/10.18080/jtde.v6n3.125
Issue
Section
Telecommunications
Copyright Telecommunications Association Inc.
