{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T12:41:02Z","timestamp":1789908062168,"version":"4.0.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2004,8,1]],"date-time":"2004-08-01T00:00:00Z","timestamp":1091318400000},"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. Embed. Comput. Syst."],"published-print":{"date-parts":[[2004,8]]},"abstract":"<jats:p>Network intrusion detection systems (NIDSs) are one of the latest developments in security. The matching of packet strings against collected signatures dominates signature-based NIDS performance. Network processors are also one of the fastest growing segments of the semiconductor market, because they are designed to provide scalable and flexible solutions that can accommodate change quickly and economically. This work presents a fast string-matching algorithm (called FNP) over the network processor platform that conducts matching sets of patterns in parallel. This design also supports numerous practical features such as case-sensitive string matching, signature prioritization, and multiple-content signatures. This efficient multiple-pattern matching algorithm utilizes the hardware facilities provided by typical network processors instead of employing the external lookup co-processors. To verify the efficiency and practicability of the proposed algorithm, it was implemented on the Vitesse IQ2000 network processor platform. The searching patterns used in the present experiments are derived from the well-known Snort ruleset cited by most open-source and commercial NIDSs. This work shows that combining our string-matching methodology, hashing engine supported by most network processors, and characteristics of current Snort signatures frequently improves performance and reduces number of memory accesses compared to conventional string-matching algorithms. Another contribution of this work is to highlight that, besides total number of searching patterns, shortest pattern length is also a major influence on NIDS multipattern matching algorithm performance.<\/jats:p>","DOI":"10.1145\/1015047.1015055","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T08:38:10Z","timestamp":1122971890000},"page":"614-633","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":75,"title":["A fast string-matching algorithm for network processor-based intrusion detection system"],"prefix":"10.1145","volume":"3","author":[{"given":"Rong-Tai","family":"Liu","sequence":"first","affiliation":[{"name":"National Tsing-Hua University, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nen-Fu","family":"Huang","sequence":"additional","affiliation":[{"name":"BroadWeb Corporation, HsinChu, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chih-Hao","family":"Chen","sequence":"additional","affiliation":[{"name":"National Tsing-Hua University, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chia-Nan","family":"Kao","sequence":"additional","affiliation":[{"name":"National Tsing-Hua University, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2004,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 18th IFIP International Information Security Conference (SEC2003)","author":"Anagnostakis K. G.","unstructured":"Anagnostakis , K. G. , Markatos , E. P. , Antonatos , S. , and Polychronakis , M . 2003. E2xB: A domain-specific string matching algorithm for intrusion detection . Proceedings of the 18th IFIP International Information Security Conference (SEC2003) . Anagnostakis, K. G., Markatos, E. P., Antonatos, S., and Polychronakis, M. 2003. E2xB: A domain-specific string matching algorithm for intrusion detection. Proceedings of the 18th IFIP International Information Security Conference (SEC2003)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/DISCEX.2001.932231"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646233.682242"},{"key":"e_1_2_1_6_1","unstructured":"DEFCON. http:\/\/www.shmoo.com\/cctf\/  DEFCON. http:\/\/www.shmoo.com\/cctf\/"},{"key":"e_1_2_1_7_1","unstructured":"Fisk M. and Varghese G. 2002. An analysis of fast string matching applied to content-based forwarding and intrusion detection. Tech rep CS2001-0670 (updated version) University of California San Diego.   Fisk M. and Varghese G. 2002. An analysis of fast string matching applied to content-based forwarding and intrusion detection. Tech rep CS2001-0670 (updated version) University of California San Diego."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380100608"},{"key":"e_1_2_1_9_1","unstructured":"Intel Network Processor. http:\/\/www.intel.com\/design\/network\/products\/npfamily\/  Intel Network Processor. http:\/\/www.intel.com\/design\/network\/products\/npfamily\/"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 17th AoM\/IAoM Inernational Conference on Computer Science.","author":"Kim S.","unstructured":"Kim , S. and Kim , Y . 1999. A fast multiple string-pattern matching algorithm . Proceedings of the 17th AoM\/IAoM Inernational Conference on Computer Science. Kim, S. and Kim, Y. 1999. A fast multiple string-pattern matching algorithm. Proceedings of the 17th AoM\/IAoM Inernational Conference on Computer Science."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN)","author":"Markatos E. P.","unstructured":"Markatos , E. P. , Antonatos , S. , Polychronakis , M. , and Anagnostakis , K. G . 2002. ExB: Exclusion-based signature matching for intrusion detection . Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN) , Cambridge, USA. 146--152. Markatos, E. P., Antonatos, S., Polychronakis, M., and Anagnostakis, K. G. 2002. ExB: Exclusion-based signature matching for intrusion detection. Proceedings of the IASTED International Conference on Communications and Computer Networks (CCN), Cambridge, USA. 146--152."},{"key":"e_1_2_1_12_1","unstructured":"Norton M. and Roelker D. 2002. Snort 2.0: Detection Revised. http:\/\/www.sourcefire.com\/technology\/whitepapers\/sf_snort20_ detection_rvstd.pdf  Norton M. and Roelker D. 2002. Snort 2.0: Detection Revised. http:\/\/www.sourcefire.com\/technology\/whitepapers\/sf_snort20_ detection_rvstd.pdf"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the DATE 2001 on Design, Automation and Test in Europe, IEEE Press, 420--429","author":"Paulin P.","unstructured":"Paulin , P. , Karim , F. , and Bromley , P . 2001. Network processors: A perspective on market requirements, processor architectures and embedded S\/W tools . Proceedings of the DATE 2001 on Design, Automation and Test in Europe, IEEE Press, 420--429 . Paulin, P., Karim, F., and Bromley, P. 2001. Network processors: A perspective on market requirements, processor architectures and embedded S\/W tools. Proceedings of the DATE 2001 on Design, Automation and Test in Europe, IEEE Press, 420--429."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1039834.1039864"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of ISCIS XVII, the Seventeenth International Symposium on Computer and Information Sciences.","author":"Shah N.","unstructured":"Shah , N. and Keutzer , K . 2002. Network processors: Origin of species , in Proceedings of ISCIS XVII, the Seventeenth International Symposium on Computer and Information Sciences. Shah, N. and Keutzer, K. 2002. Network processors: Origin of species, in Proceedings of ISCIS XVII, the Seventeenth International Symposium on Computer and Information Sciences."},{"key":"e_1_2_1_16_1","volume-title":"2nd Workshop on Network Processors (NP-2) at the 9th International Symposium on High Performance Computer Architecture (HPCA-9)","author":"Shah N.","year":"2003","unstructured":"Shah N. , Plishker , W. , Keutzer , K. 2003 . NP-Click: A programming model for the intel IXP1200 . In 2nd Workshop on Network Processors (NP-2) at the 9th International Symposium on High Performance Computer Architecture (HPCA-9) , Anaheim, CA. Shah N., Plishker, W., Keutzer, K. 2003. NP-Click: A programming model for the intel IXP1200. In 2nd Workshop on Network Processors (NP-2) at the 9th International Symposium on High Performance Computer Architecture (HPCA-9), Anaheim, CA."},{"key":"e_1_2_1_17_1","unstructured":"Snort. http:\/\/www.snort.org\/  Snort. http:\/\/www.snort.org\/"},{"key":"e_1_2_1_18_1","unstructured":"Spirent Communications http:\/\/smartbits.spirentcom.com\/  Spirent Communications http:\/\/smartbits.spirentcom.com\/"},{"key":"e_1_2_1_19_1","unstructured":"Vitesse. http:\/\/www.vitesse.com\/  Vitesse. http:\/\/www.vitesse.com\/"},{"key":"e_1_2_1_20_1","volume-title":"The performance of single-keyword and multiple-keyword pattern matching algorithms. Tech. rep. 94\/19","author":"Watson B. W.","unstructured":"Watson , B. W. 1994. The performance of single-keyword and multiple-keyword pattern matching algorithms. Tech. rep. 94\/19 , Eindhoven University of Technology . Watson, B. W. 1994. The performance of single-keyword and multiple-keyword pattern matching algorithms. Tech. rep. 94\/19, Eindhoven University of Technology."},{"key":"e_1_2_1_21_1","unstructured":"Whitehats. http:\/\/www.whitehats.com\/  Whitehats. http:\/\/www.whitehats.com\/"},{"key":"e_1_2_1_22_1","unstructured":"Wu S. and Manber U. 1994. A fast algorithm for multi-pattern searching. Tech. rep. TR94-17 Department of Computer Science University of Arizona.  Wu S. and Manber U. 1994. A fast algorithm for multi-pattern searching. Tech. rep. TR94-17 Department of Computer Science University of Arizona."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1015047.1015055","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1015047.1015055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:43:32Z","timestamp":1750286612000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1015047.1015055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,8]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,8]]}},"alternative-id":["10.1145\/1015047.1015055"],"URL":"https:\/\/doi.org\/10.1145\/1015047.1015055","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,8]]},"assertion":[{"value":"2004-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}