A Comparative Study of Dictionary Matching with Gaps: Limitations, Techniques and Challenges
Abstract
Cyber security is a critical modern concern. Network intrusion detection systems (NIDS) perform protocol analysis, content searching and content matching, in order to detect harmful software. The high performance demands of NIDS applications in both speed and space consumption, as well as the diverse characteristics of the scenario conditions, have motivated a recent line of research on several formal problems all within the broad scope of dictionary matching with gaps. The goal of this paper is to supply a comparative survey of this line of research in terms of the problems, the formally proven limitations of any solution suggested, the techniques developed to deal with the limitations and different problems, to supply complementary techniques, and finally, to point out existing challenges still to be handled by future work.
References
[1]
Krishnamurthy, M., Seagren, E.S., Alder, R., Bayles, A.W., Burke, J., Carter, S., Faskha, E.: How to Cheat at Securing Linux. Syngress Publishing Inc., Elsevier Inc (2008)
[2]
Aho AV and Corasick MJ Efficient string matching: an aid to bibliographic search Commun. ACM 1975 18 6 333-340
[3]
Amir A and Călinescu G Alphabet-independent and scaled dictionary matching J. Algorithms 2000 36 1 34-62
[4]
Amir A, Farach M, Galil Z, Giancarlo R, and Park K Dynamic dictionary matching J. Comput. Syst. Sci. 1994 49 2 208-222
[5]
Amir A, Farach M, Idury RM, Poutré JAL, and Schäffer AA Improved dynamic dictionary matching Inf. Comput. 1995 119 2 258-282
[6]
Amir A, Keselman D, Landau GM, Lewenstein M, Lewenstein N, and Rodeh M Text indexing and dictionary matching with one error J. Algorithms 2000 37 2 309-325
[7]
Brodal, G.S., Gasieniec, L.: Approximate dictionary queries. In: 7th Annual Symposium on Combinatorial Pattern Matching CPM (Laguna Beach, California, USA), June 10–12, pp. 65–74 (1996)
[8]
Cole, R., Gottlieb, L., Lewenstein, M., Dictionary matching and indexing with errors and don’t cares. In: Proceedings 36th Annual ACM Symposium on the Theory of Computing (STOC), ACM Press, pp. 91–100 (2004)
[9]
Idury RM and Schäffer AA Multiple matching of parameterized patterns Theor. Comput. Sci. 1996 154 2 203-224
[10]
Kleene, S.C.: Representation of events in nerve nets and finite automata
[11]
Bille P and Farach-Colton M Fast and compact regular expression matching Theor. Comput. Sci. 2008 409 3 486-496
[12]
Bille, P., Thorup, M.: Regular expression matching with multi-strings and intervals. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17–19, 2010 (Moses Charikar, ed.), SIAM, pp. 1297–1308 (2010)
[13]
Myers EW A four russians algorithm for regular expression pattern matching J. ACM 1992 39 2 430-448
[14]
Amir A, Kopelowitz T, Levy A, Pettie S, Porat E, and Shalom BR Mind the gap! online dictionary matching with one gap Algorithmica 2019 81 6 2123-2157
[15]
Amir, A., Kopelowitz, T., Levy, A., Pettie, S., Porat, E., Shalom, B.R.: Mind the gap: essentially optimal algorithms for online dictionary matching with one gap. In: 27th International Symposium on Algorithms and Computation, ISAAC (Sydney, Australia), December 12–14, pp. 12:1–12:12 (2016)
[16]
Amir, A., Levy, A., Porat, E., Shalom, B.R.: Online recognition of dictionary with one gap. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), August 28–30, pp. 3–17 (2017)
[17]
Verint Systems, Personal communication. 2013, Addres: Maskit St. 33 Herzliya Israel
[18]
Amir A, Levy A, Porat E, and Shalom BR Dictionary matching with a few gaps Theor. Comput. Sci. 2015 589 34-46
[19]
Chase M and Shen E Substring-searchable symmetric encryption PoPETs 2015 2015 2 263-281
[20]
Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. ACM CCS 06 (Ari Juels Rebecca N. Wright and Sabrina De Capitani di Vimercati, eds.), ACM Press, pp. 9–88 (2006)
[21]
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: IEEE Symposium on Security and Privacy IEEE Computer Society Press, pp. 44–55 (2000)
[22]
Boneh, D., Crescenzo, G.D., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. EUROCRYPT 2004 (Christian Cachin and Jan Camenisch, eds.), LNCS, vol. 3027, Springer, pp. 506–522 (2004)
[23]
Desmoulins, N., Fouque, P.A., Onete, C., Sanders, O.: Pattern matching on encrypted streams, ASIACRYPT (2018)
[24]
Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (San Diego, CA, USA), May 16–18, pp. 71–80 (1993)
[25]
Shalom, B.R.: Parameterized dictionary matching with one gap. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), pp. 103–116 (2018)
[26]
Shalom BR Parameterized dictionary matching and recognition with one gap Theor. Comput. Sci. 2021 854 1-16
[27]
Levy, A., Shalom, B.R.: Online parameterized dictionary matching with one gap. In: Stringology (Proceedings of the Prague Stringology Conference), pp. 41–55 (2019)
[28]
Levy, A., Shalom, B.R.: Online parameterized dictionary matching with one gap. Submitted for publication (2020)
[29]
Burr, S.A., Erdős, P.: On the magnitude of generalized ramsey numbers for graphs. Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday) (János Bolyai, ed.), Colloq. Math. Soc., vol. 1, 1975, p. 214–240
[30]
Kucherov G and Rusinowitch M Matching a set of strings with variable length don’t cares Theor. Comput. Sci. 1997 178 12 129-154
[31]
Zhang M, Zhang Y, and Hu L A faster algorithm for matching a set of patterns with variable length don’t cares Inf. Process. Lett. 2010 110 6 216-220
[32]
Haapasalo, T., Silvasti, P., Sippu, S., Soisalon-Soininen, E.: Online dictionary matching with variable-length gaps. In: 10th International Symposium on Experimental Algorithms SEA (Kolimpari, Chania, Crete, Greece), May 5–7, pp. 76–87 (2011)
[33]
Hon W, Lam TW, Shah R, Thankachan SV, Ting H, and Yang Y Dictionary matching with a bounded gap in pattern or in text Algorithmica 2018 80 2 698-713
[34]
Amir, A., Levy, A., Porat, E., Shalom, B.R.: Dictionary matching with one gap. In: The Proceedings of the 25th Symposium on Combinatorial Pattern Matching (CPM), pp. 11–20 (2014)
[35]
Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS. pp. 434–443 (2014)
[36]
Grønlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. FOCS 621–630 (2014)
[37]
Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3sum conjecture. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2016)
[38]
Pǎtraşcu, M.: Towards polynomial lower bounds for dynamic problems. STOC 603–610 (2010)
[39]
Bjørklund, A., Pagh, R., Vassilevska Williams, V., Zwick, U.: Listing triangles. In: Proceedings 41st Int’l Colloquium on Automata, Languages, and Programming (ICALP (I)), pp. 223–234 (2014)
[40]
Itai, A., Rodeh, M.: Finding a minimum circuit in a graph 7(4), 413–423 (1978)
[41]
Chiba N and Nishizeki T Arboricity and subgraph listing algorithms SIAM J. Comput. (SICOMP) 1985 14 1 210-223
[42]
Pettie, S., Kopelowitz, T., Porat, E.: Dynamic set intersection. WADS (2015)
[43]
Cohen H and Porat E Fast set intersection and two-patterns matching Theor. Comput. Sci. 2010 411 40–42 3795-3800
[44]
Bansal N and Williams R Regularity lemmas and combinatorial algorithms Theory Comput. 2012 8 1 69-94
[45]
Amir A, Levy A, Porat E, and Shalom BR Online recognition of dictionary with one gap Inf. Comput. 2020 275 104633
[46]
Mortensen CW Fully dynamic orthogonal range reporting on RAM SIAM J. Comput. 2006 35 6 1494-1525
[47]
Amir A, Farach M, and Muthukrishnan S Alphabet dependence in parameterized matching Inf. Process. Lett. 1994 49 3 111-115
[48]
Baker BS Parameterized duplication in strings: algorithms and an application to software maintenance SIAM J. Comput. 1997 26 5 1343-1362
[49]
Deguchi, S., Higashijima, F., Bannai, H., Inenaga, S., Takeda, M.: Parameterized suffix arrays for binary strings. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), September 1–3, pp. 84–94 (2008)
[50]
Ferragina P and Grossi R The string b-tree: a new data structure for string search in external memory and its applications J. ACM 1999 46 2 236-280
[51]
Ganguly, A., Hon, W., Shah, R.: A framework for dynamic parameterized dictionary matching. In: 15th Scandinavian Symposium and Workshops on Algorithm Theory SWAT (Reykjavik, Iceland), June 22–24, pp. 10:1–10:14 (2016)
[52]
Keller O, Kopelowitz T, and Lewenstein M On the longest common parameterized subsequence Theor. Comput. Sci. 2009 410 51 5347-5353
[53]
Lewenstein, M.: Parameterized pattern matching. Encyclopedia of Algorithms 1525–1530,(2016)
[54]
Mendivelso, J., Pinzón, Y.: Parameterized matching: Solutions and extensions. In: Proceedings of the Prague Stringology Conference (PSC) (Prague, Czech Republic), August 24–26, pp. 118–131 (2015)
[55]
Willard DE Log-logarithmic worst-case range queries are possible in space Inf. Process. Lett. 1983 17 2 81-84
Recommendations
Dictionary matching: review of the aho-corasick algorithm and vision for large dictionaries
ICIST '18: Proceedings of the 8th International Conference on Information Systems and TechnologiesPattern-matching techniques have recently been applied to network security applications such as intrusion detection, virus protection, and spam filters. The widely used the Aho-Corasick algorithm can simultaneously match multiple patterns while ...
Efficient Algorithms for Image Template and Dictionary Matching
Given a large text image and a small template image, the Template Matching Problem is that of finding every location within the text which looks like the pattern. This problem, which has received attention for low-level image processing, has been ...
Compressed automata for dictionary matching
We address a variant of the dictionary matching problem where the dictionary is represented by a straight line program (SLP). For a given SLP-compressed dictionary D of size n and height h representing m patterns of total length N, we present an O ( n 2 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 March 2022
Accepted: 27 June 2021
Received: 04 August 2020
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024