{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,25]],"date-time":"2025-11-25T20:26:45Z","timestamp":1764102405255,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T00:00:00Z","timestamp":1141171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2006,3]]},"abstract":"<jats:p>Network Intrusion Detection and Prevention Systems have emerged as one of the most effective ways of providing security to those connected to the network and at the heart of almost every modern intrusion detection system is a string-matching algorithm. String matching is one of the most critical elements because it allows for the system to make decisions based not just on the headers, but the actual content flowing through the network. Unfortunately, checking every byte of every packet to see if it matches one of a set of thousands of strings becomes a computationally intensive task as network speeds grow into the tens, and eventually hundreds, of gigabits\/second. To keep up with these speeds, a specialized device is required, one that can maintain tight bounds on worst-case performance, that can be updated with new rules without interrupting operation, and one that is efficient enough that it could be included on-chip with existing network chips or even into wireless devices. We have developed an approach that relies on a special purpose architecture that executes novel string matching algorithms specially optimized for implementation in our design. We show how the problem can be solved by converting the large database of strings into many tiny state machines, each of which searches for a portion of the rules and a portion of the bits of each rule. Through the careful codesign and optimization of our architecture with a new string-matching algorithm, we show that it is possible to build a system that is 10 times more efficient than the currently best known approaches.<\/jats:p>","DOI":"10.1145\/1132462.1132464","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"3-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":69,"title":["Bit-split string-matching engines for intrusion detection and prevention"],"prefix":"10.1145","volume":"3","author":[{"given":"Lin","family":"Tan","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana-Champaign, Urbana, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brett","family":"Brotherton","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timothy","family":"Sherwood","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"volume-title":"Workshop on Architectural Support for Security and Anti-virus (WASSA) Held in Cooperation with ASPLOS XI.]]","author":"Aldwairi M.","key":"e_1_2_1_2_1","unstructured":"Aldwairi , M. , Conte , T. , and Franzon , P . 2004. Configurable string matching hardware for speedup up intrusion detection . In Workshop on Architectural Support for Security and Anti-virus (WASSA) Held in Cooperation with ASPLOS XI.]] Aldwairi, M., Conte, T., and Franzon, P. 2004. Configurable string matching hardware for speedup up intrusion detection. In Workshop on Architectural Support for Security and Anti-virus (WASSA) Held in Cooperation with ASPLOS XI.]]"},{"volume-title":"Proceedings of the Field-Programmable Custom Computing Machines. 135--144","author":"Baker Z. K.","key":"e_1_2_1_3_1","unstructured":"Baker , Z. K. and Prasanna , V. K . 2004a. A methodology for synthesis of efficient intrusion detection systems on FPGAs . In Proceedings of the Field-Programmable Custom Computing Machines. 135--144 .]] Baker, Z. K. and Prasanna, V. K. 2004a. A methodology for synthesis of efficient intrusion detection systems on FPGAs. In Proceedings of the Field-Programmable Custom Computing Machines. 135--144.]]"},{"volume-title":"Proceeding of the 2004 ACM\/SIGDA 12th International Symposium on Field Programmable Gate Arrays. 223--232","author":"Baker Z. K.","key":"e_1_2_1_4_1","unstructured":"Baker , Z. K. and Prasanna , V. K . 2004b. Time and area efficient pattern matching on FPGAs . In Proceeding of the 2004 ACM\/SIGDA 12th International Symposium on Field Programmable Gate Arrays. 223--232 .]] 10.1145\/968280.968312 Baker, Z. K. and Prasanna, V. K. 2004b. Time and area efficient pattern matching on FPGAs. In Proceeding of the 2004 ACM\/SIGDA 12th International Symposium on Field Programmable Gate Arrays. 223--232.]] 10.1145\/968280.968312"},{"volume-title":"Proceedings of the USENIX Security Symposium.]]","author":"Baratloo A.","key":"e_1_2_1_5_1","unstructured":"Baratloo , A. , Singh , N. , and Tsai , T . 2000. Transparent run-time defense against stack smashing attacks . In Proceedings of the USENIX Security Symposium.]] Baratloo, A., Singh, N., and Tsai, T. 2000. Transparent run-time defense against stack smashing attacks. In Proceedings of the USENIX Security Symposium.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"volume-title":"IEEE Symposium on Field-Programmable Custom Computing Machines.]]","author":"Cho Y.","key":"e_1_2_1_7_1","unstructured":"Cho , Y. and Mangione-Smith , W . 2004. Deep packet filter with dedicated logic and read only memories . In IEEE Symposium on Field-Programmable Custom Computing Machines.]] Cho, Y. and Mangione-Smith, W. 2004. Deep packet filter with dedicated logic and read only memories. In IEEE Symposium on Field-Programmable Custom Computing Machines.]]"},{"volume-title":"12th International Converence on Field-Programmable Logic and Applications.]]","author":"Cho Y. H.","key":"e_1_2_1_8_1","unstructured":"Cho , Y. H. , Navab , S. , and Mangione-Smith , W. H . 2002. Specialized hardware for deep network packet filtering. In 12th International Converence on Field-Programmable Logic and Applications.]] Cho, Y. H., Navab, S., and Mangione-Smith, W. H. 2002. Specialized hardware for deep network packet filtering. In 12th International Converence on Field-Programmable Logic and Applications.]]"},{"volume-title":"Proceedings of the 13th International Conference on Field Programmable Logic and Applications.]]","author":"Clark C. R.","key":"e_1_2_1_9_1","unstructured":"Clark , C. R. and Schimmel , D. E . 2003. Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns . In Proceedings of the 13th International Conference on Field Programmable Logic and Applications.]] Clark, C. R. and Schimmel, D. E. 2003. Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns. In Proceedings of the 13th International Conference on Field Programmable Logic and Applications.]]"},{"volume-title":"Proceedings of USENIX Annual Technical Conference.]]","author":"Crosby S. A.","key":"e_1_2_1_10_1","unstructured":"Crosby , S. A. and Wallach , D. S . 2003. Denial of service via algorithmic complexity attacks . In Proceedings of USENIX Annual Technical Conference.]] Crosby, S. A. and Wallach, D. S. 2003. Denial of service via algorithmic complexity attacks. In Proceedings of USENIX Annual Technical Conference.]]"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/MM.2004.1268997"},{"key":"e_1_2_1_12_1","volume-title":"Tech. Rep. In preparation, successor to UCSD TR CS2001-0670","author":"Fisk M.","year":"2001","unstructured":"Fisk , M. and Varghese , G . 2001 . Applying fast string matching to intrusion detection. Tech. Rep. In preparation, successor to UCSD TR CS2001-0670 , University of California , San Diego .]] Fisk, M. and Varghese, G. 2001. Applying fast string matching to intrusion detection. Tech. Rep. In preparation, successor to UCSD TR CS2001-0670, University of California, San Diego.]]"},{"volume-title":"Proceedings of the 12th International Conference on Field-Programmable Logic and Applications. 404--413","author":"Gokhale M.","key":"e_1_2_1_13_1","unstructured":"Gokhale , M. , Dubois , D. , Dubois , A. , Boorman , M. , Poole , S. , and Hogsett , V . 2002. Granidt: Towards gigabit rate network intrusion detection technology . In Proceedings of the 12th International Conference on Field-Programmable Logic and Applications. 404--413 .]] Gokhale, M., Dubois, D., Dubois, A., Boorman, M., Poole, S., and Hogsett, V. 2002. Granidt: Towards gigabit rate network intrusion detection technology. In Proceedings of the 12th International Conference on Field-Programmable Logic and Applications. 404--413.]]"},{"volume-title":"Algorithms for packet classification","author":"Gupta P.","key":"e_1_2_1_14_1","unstructured":"Gupta , P. and McKeown , N. 2001. Algorithms for packet classification . IEEE Network Magazine .]] Gupta, P. and McKeown, N. 2001. Algorithms for packet classification. IEEE Network Magazine.]]"},{"volume-title":"Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. 111","author":"Hutchings B. L.","key":"e_1_2_1_15_1","unstructured":"Hutchings , B. L. , Franklin , R. , and Carver , D . 2002. Assisting network intrusion detection with reconfigurable hardware . In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. 111 .]] Hutchings, B. L., Franklin, R., and Carver, D. 2002. Assisting network intrusion detection with reconfigurable hardware. In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. 111.]]"},{"volume-title":"Intrusion detection\/prevention product revenue up 9&percnt","author":"Smarket","key":"e_1_2_1_16_1","unstructured":"ID Smarket . 2004. Intrusion detection\/prevention product revenue up 9&percnt ; in 1Q04. Infonetics Market Research. Tech . rep. June.]] IDSmarket. 2004. Intrusion detection\/prevention product revenue up 9&percnt; in 1Q04. Infonetics Market Research. Tech. rep. June.]]"},{"volume-title":"Annual International Symposium on Computer Architecture.]] 10","author":"Mai K.","key":"e_1_2_1_17_1","unstructured":"Mai , K. , Paaske , T. , Jayasena , N. , Ho , R. , Dally , W. , and Horowitz , M . 2000. Smart memories: A modular reconfigurable architecture . In Annual International Symposium on Computer Architecture.]] 10 .1145\/339647.339673 Mai, K., Paaske, T., Jayasena, N., Ho, R., Dally, W., and Horowitz, M. 2000. Smart memories: A modular reconfigurable architecture. In Annual International Symposium on Computer Architecture.]] 10.1145\/339647.339673"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/79538.79540"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of LISA'99: 13th Systems Administration Conference. 229--238","author":"Roesch M.","year":"1999","unstructured":"Roesch , M. 1999 . Snort---lightweight intrusion detection for networks . In Proceedings of LISA'99: 13th Systems Administration Conference. 229--238 .]] Roesch, M. 1999. Snort---lightweight intrusion detection for networks. In Proceedings of LISA'99: 13th Systems Administration Conference. 229--238.]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/65.912716"},{"key":"e_1_2_1_21_1","volume-title":"Tech. Rep. WRL-2001-2, HP Labs Technical Reports. Dec.]]","author":"Shivakumar P.","year":"2001","unstructured":"Shivakumar , P. and Jouppi , N . 2001 . CACTI 3.0: An integrated cache timing, power, and area model. Tech. Rep. WRL-2001-2, HP Labs Technical Reports. Dec.]] Shivakumar, P. and Jouppi, N. 2001. CACTI 3.0: An integrated cache timing, power, and area model. Tech. Rep. WRL-2001-2, HP Labs Technical Reports. Dec.]]"},{"volume-title":"Proceedings of the ACM\/USENIX Symposium on Operating System Design and Implementation (OSDI).]]","author":"Singh S.","key":"e_1_2_1_22_1","unstructured":"Singh , S. , Estan , C. , Varghese , G. , and Savage , S . 2004. Automated worm fingerprinting . In Proceedings of the ACM\/USENIX Symposium on Operating System Design and Implementation (OSDI).]] Singh, S., Estan, C., Varghese, G., and Savage, S. 2004. Automated worm fingerprinting. In Proceedings of the ACM\/USENIX Symposium on Operating System Design and Implementation (OSDI).]]"},{"volume-title":"Proceedings of the Field-Programmable Custom Computing Machines. 258--267","author":"Sourdis I.","key":"e_1_2_1_23_1","unstructured":"Sourdis , I. and Pnevmatikatos , D . 2004. Pre-decoded CAMs for efficient and high-speed NIDS pattern matching . In Proceedings of the Field-Programmable Custom Computing Machines. 258--267 .]] Sourdis, I. and Pnevmatikatos, D. 2004. Pre-decoded CAMs for efficient and high-speed NIDS pattern matching. In Proceedings of the Field-Programmable Custom Computing Machines. 258--267.]]"},{"key":"e_1_2_1_24_1","unstructured":"SpamDetection. Commtouch\u00ae software ltd. White paper: Recurrent pattern detection (RPD#8482;) technology. http:www.commtouch.com\/documents\/ Commtouch RPD White Paper.pdf.]]  SpamDetection. Commtouch\u00ae software ltd. White paper: Recurrent pattern detection (RPD#8482;) technology. http:www.commtouch.com\/documents\/ Commtouch RPD White Paper.pdf.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/296502.296503"},{"volume-title":"Wavescalar. In 36th International Symposium on Microarchitecture.]]","author":"Swanson S.","key":"e_1_2_1_26_1","unstructured":"Swanson , S. , Michelson , K. , Schwerin , A. , and Oskin , M . 2003 . Wavescalar. In 36th International Symposium on Microarchitecture.]] Swanson, S., Michelson, K., Schwerin, A., and Oskin, M. 2003. Wavescalar. In 36th International Symposium on Microarchitecture.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/357153.357155"},{"volume-title":"Annual International Symposium on Computer Architecture.]]","author":"Taylor M. B.","key":"e_1_2_1_28_1","unstructured":"Taylor , M. B. , Lee , W. , Miller , J. , Wentzlaff , D. , Bratt , I. , Greenwald , B. , Henry , Hoffmann, Johnson , P. , Kim , J. , Psota , J. , Saraf , A. , Shnidman , N. , Strumpen , V. , Frank , M. , Amarasinghe , S. , and Agarwal , A . 2004. Evaluation of the Raw microprocessor: An exposed-wire-delay architecture for ILP and streams . In Annual International Symposium on Computer Architecture.]] Taylor, M. B., Lee, W., Miller, J., Wentzlaff, D., Bratt, I., Greenwald, B., Henry, Hoffmann, Johnson, P., Kim, J., Psota, J., Saraf, A., Shnidman, N., Strumpen, V., Frank, M., Amarasinghe, S., and Agarwal, A. 2004. Evaluation of the Raw microprocessor: An exposed-wire-delay architecture for ILP and streams. In Annual International Symposium on Computer Architecture.]]"},{"volume-title":"the 23rd Conference of the IEEE Communications Society (Infocomm).]]","author":"Tuck N.","key":"e_1_2_1_29_1","unstructured":"Tuck , N. , Sherwood , T. , Calder , B. , and Varghese , G . 2004. Deterministic memory-efficient string matching algorithms for intrusion detection . In the 23rd Conference of the IEEE Communications Society (Infocomm).]] Tuck, N., Sherwood, T., Calder, B., and Varghese, G. 2004. Deterministic memory-efficient string matching algorithms for intrusion detection. In the 23rd Conference of the IEEE Communications Society (Infocomm).]]"},{"volume-title":"Workshop on Evaluating and Architecting Systems for Dependability.]]","author":"Xu J.","key":"e_1_2_1_30_1","unstructured":"Xu , J. , Kalbarczyk , Z. , Patel , S. , and Iyer , R. K . 2002. Architecture support for defending against buffer overflow attacks . In Workshop on Evaluating and Architecting Systems for Dependability.]] Xu, J., Kalbarczyk, Z., Patel, S., and Iyer, R. K. 2002. Architecture support for defending against buffer overflow attacks. In Workshop on Evaluating and Architecting Systems for Dependability.]]"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132462.1132464","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132462.1132464","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:50Z","timestamp":1750263530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132462.1132464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,3]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,3]]}},"alternative-id":["10.1145\/1132462.1132464"],"URL":"https:\/\/doi.org\/10.1145\/1132462.1132464","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2006,3]]},"assertion":[{"value":"2006-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}