We introduce the infix inclusion problem of two languages S and T that decides whether or not S is a subset of the set of all infixes of T. This problem is motivated from intrusion detection systems that identify malicious patterns according to their semantics, which are often disguised with additional information surrounding the patterns. In other words, malicious patterns are embedded as an infix of the whole patterns. We examine the infix inclusion problem, where a source S and a target T are finite, regular or context-free languages. We prove that the problem is 1) co-NP-complete when one of the languages is finite, 2) PSPACE-complete when S, T are regular, 3) EXPTIME-complete when S is context-free and T is regular and 4) undecidable for when S is either regular or context-free and T is context-free.
|Title of host publication||Developments in Language Theory - 26th International Conference, DLT 2022, Proceedings|
|Editors||Volker Diekert, Mikhail Volkov|
|Publisher||Springer Science and Business Media Deutschland GmbH|
|Number of pages||12|
|Publication status||Published - 2022|
|Event||26th International Conference on Developments in Language Theory, DLT 2022 - Tampa, United States|
Duration: 2022 May 9 → 2022 May 13
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||26th International Conference on Developments in Language Theory, DLT 2022|
|Period||22/5/9 → 22/5/13|
Bibliographical notePublisher Copyright:
© 2022, Springer Nature Switzerland AG.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)