FilterFA: a multiple string matching algorithm based on specification of character set
Multiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick al-gorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——FilterFA, based on specification of character set was...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2016-12-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2016277/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539582399610880 |
|---|---|
| author | Ping ZHANG Hui-min HE Chun-yan ZHANG Cong CAO Yan-bing LIU Jian-long TAN |
| author_facet | Ping ZHANG Hui-min HE Chun-yan ZHANG Cong CAO Yan-bing LIU Jian-long TAN |
| author_sort | Ping ZHANG |
| collection | DOAJ |
| description | Multiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick al-gorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——FilterFA, based on specification of character set was proposed. This algorithm compressed large character by the character set mapping function, and constructed a new automata based on the mapped character set,then space complexity decreased to O(|P||Σ′|). Experiments on synthetic datasets and real-world datasets (such as ClamAV) show that the storage overhead of FilterFA is only about 3% of that of AC, while the size of the character set is 8, and the false recognition rate is less than 2%. |
| format | Article |
| id | doaj-art-6871a12d98fb4701be1c0ea2f3d6f939 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2016-12-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-6871a12d98fb4701be1c0ea2f3d6f9392025-01-14T07:10:59ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2016-12-013710311459705345FilterFA: a multiple string matching algorithm based on specification of character setPing ZHANGHui-min HEChun-yan ZHANGCong CAOYan-bing LIUJian-long TANMultiple string matching is one of the core techniques of intrusion detection system, where Aho-Corasick al-gorithm is widely used. To solve the problem that huge storage overhead of AC would influence performance deeply, an improved algorithm ——FilterFA, based on specification of character set was proposed. This algorithm compressed large character by the character set mapping function, and constructed a new automata based on the mapped character set,then space complexity decreased to O(|P||Σ′|). Experiments on synthetic datasets and real-world datasets (such as ClamAV) show that the storage overhead of FilterFA is only about 3% of that of AC, while the size of the character set is 8, and the false recognition rate is less than 2%.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2016277/intrusion detectionmultiple string matchingspecification of character setcharacter set mapping |
| spellingShingle | Ping ZHANG Hui-min HE Chun-yan ZHANG Cong CAO Yan-bing LIU Jian-long TAN FilterFA: a multiple string matching algorithm based on specification of character set Tongxin xuebao intrusion detection multiple string matching specification of character set character set mapping |
| title | FilterFA: a multiple string matching algorithm based on specification of character set |
| title_full | FilterFA: a multiple string matching algorithm based on specification of character set |
| title_fullStr | FilterFA: a multiple string matching algorithm based on specification of character set |
| title_full_unstemmed | FilterFA: a multiple string matching algorithm based on specification of character set |
| title_short | FilterFA: a multiple string matching algorithm based on specification of character set |
| title_sort | filterfa a multiple string matching algorithm based on specification of character set |
| topic | intrusion detection multiple string matching specification of character set character set mapping |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2016277/ |
| work_keys_str_mv | AT pingzhang filterfaamultiplestringmatchingalgorithmbasedonspecificationofcharacterset AT huiminhe filterfaamultiplestringmatchingalgorithmbasedonspecificationofcharacterset AT chunyanzhang filterfaamultiplestringmatchingalgorithmbasedonspecificationofcharacterset AT congcao filterfaamultiplestringmatchingalgorithmbasedonspecificationofcharacterset AT yanbingliu filterfaamultiplestringmatchingalgorithmbasedonspecificationofcharacterset AT jianlongtan filterfaamultiplestringmatchingalgorithmbasedonspecificationofcharacterset |