Regular Expression Matching using Bit Vector Automata
Regular Expression Matching using Bit Vector Automata
复制标题
使用位向量自动机进行正则表达式匹配
DOI：
10.1145/3586044
复制
发表时间：
2023
影响因子：
--
通讯作者：
Mamouras, Konstantinos
中科院分区：
文献类型：
--
作者：
Le Glaunec, Alexis;Kong, Lingkun;Mamouras, Konstantinos
正则表达式(正则表达式)在现代软件中随处可见。正则表达式匹配有多种实现技术，大致可分为(1)依赖回溯搜索，或(2)基于有限状态自动机。选择使用回溯的实现通常是因为它们能够支持高级模式匹配构造。不幸的是，众所周知，它们存在严重的性能问题。对于某些正则表达式，匹配的运行时间可能与输入文本的大小成指数关系。为了提供更强的匹配效率保证，基于自动机的正则表达式匹配是首选。然而，对于某些模式，即使是这些正则表达式引擎也可能表现出严重的性能下降。其主要原因是，实践中使用的正则表达式并不是完全由经典的规则结构构建的，即连接、非确定选择和Kleene的星形。它们涉及其他结构，以提供简洁和方便的表达。其中最常见的结构是有界重复(也称为计数)，它描述了模式在固定次数内的重复。我们的算法是基于一种新的自动机模型，我们称之为非确定位向量自动机(NBVA)。该模型被选择为在表达上等价于具有有界计数器的非确定反自动机，这是一种非常自然的模型，用于表达具有有界重复的模式。我们证明了存在一类有界重复的正则表达式，它可以在独立于重复界的时间内匹配。我们的算法足够通用，可以覆盖实践中出现的绝大多数具有挑战性的有界重复。我们在一个正则表达式引擎中提供了我们的方法的实现，我们称之为BVA-SCAN。我们在几个真实数据集上将BVA-SCAN与最先进的正则表达式引擎进行了比较。
Regular expressions (regexes) are ubiquitous in modern software. There is a variety of implementation techniques for regex matching, which can be roughly categorized as (1) relying on backtracking search, or (2) being based on finite-state automata. The implementations that use backtracking are often chosen due to their ability to support advanced pattern-matching constructs. Unfortunately, they are known to suffer from severe performance problems. For some regular expressions, the running time for matching can be exponential in the size of the input text. In order to provide stronger guarantees of matching efficiency, automata-based regex matching is the preferred choice. However, even these regex engines may exhibit severe performance degradation for some patterns. The main reason for this is that regexes used in practice are not exclusively built from the classical regular constructs, i.e., concatenation, nondeterministic choice and Kleene's star. They involve additional constructs that provide succinctness and convenience of expression. The most common such construct is bounded repetition (also called counting), which describes the repetition of the pattern a fixed number of times.In this paper, we propose a new algorithm for the efficient matching of regular expressions that involve bounded repetition. Our algorithms are based on a new model of automata, which we call nondeterministic bit vector automata (NBVA). This model is chosen to be expressively equivalent to nondeterministic counter automata with bounded counters, a very natural model for expressing patterns with bounded repetition. We show that there is a class of regular expressions with bounded repetition that can be matched in time that is independent from the repetition bounds. Our algorithms are general enough to cover the vast majority of challenging bounded repetitions that arise in practice. We provide an implementation of our approach in a regex engine, which we call BVA-Scan. We compare BVA-Scan against state-of-the-art regex engines on several real datasets.
登录
查看更多内容
连续时间信号定量在线监测的组合框架
DOI：
10.1007/978-3-030-88494-9_8
发表时间：
2021
期刊：
Runtime Verification 2021
影响因子：
--
作者：
Mamouras, Konstantinos;Chattopadhyay, Agnishom;Wang, Zhifu
通讯作者：
Wang, Zhifu
使用微米自动机处理器发现生物序列中的基序
DOI：
--
发表时间：
2016
期刊：
IEEE/ACM Transactions on Computational Biology & Bioinformatics
影响因子：
--
作者：
Indranil Roy;S. Aluru
通讯作者：
S. Aluru
影响因子：
--
作者：
H. Barringer;A. Goldberg;K. Havelund;Koushik Sen
通讯作者：
H. Barringer;A. Goldberg;K. Havelund;Koushik Sen
具有有限滞后的在线信号监控
DOI：
10.1109/tcad.2020.3013053
发表时间：
2020
影响因子：
2.9
作者：
Mamouras, Konstantinos;Wang, Zhifu
通讯作者：
Wang, Zhifu
重新思考正则表达式引擎以解决 ReDoS 问题
DOI：
--
发表时间：
2019
期刊：
ESEC/SIGSOFT FSE
影响因子：
--
作者：
James C. Davis
通讯作者：
James C. Davis