1 Introduction↩︎

Counting operations make it possible to express bounded repetition, indicating that something happens at least \(l\) times but no more than \(h\) times. Matching strings using regular expressions with counting operations (c-regexes) can be slow due to the additional complexity introduced by counting operations. Two typical approaches are used for matching with c-regexes. The first is counter-expansion, employed by RE2 [@Cox10], which rewrites c-regexes into equivalent regexes without counting. However, this approach becomes inefficient when the bounds of counting operations are large, as it constructs duplicate states for each possible counter value [@TuronovaHLSVV20]. The second approach uses counter automata (CAs) [@GeladeGM12]; for example, variants of it are used in the Java regex engine. This approach tracks the number of repetitions using counter variables, but in the Java matcher, this approach inherits the inefficiencies of backtracking matchers [@TuronovaHHLVV22; @DavisCSL18].

During matching, a CA constructed from a c-regex \(r\) may generate a number of counting configurations, linear in the bounds of the counting operators in \(r\). Thus, the worst-case matching time of Thompson-like matching algorithms, that is, matching algorithms following a breadth-first approach, on CAs depends on the bounds of the counting operators, which can be large. Since the bounds are in practice encoded in decimal (as opposed to unary), a counter range \(\{l, h\}\) contributes only \(O(\log h)\) characters to the textual length of \(r\), yet may induce \(\Theta(h)\) distinct counter configurations during matching. Consequently, the matching time can be exponential in the textual length of \(r\).

The counting-set data structure [@TuronovaHLSVV20; @HolikSTV23] has been proposed to address this inefficiency by allowing the simultaneous application of the increment-by-one counter operation on multiple counter values. However, the cost of replicating counting-sets at branching transitions is expensive. In this work, we address this problem by introducing a sparse counting-set structure, which reduces the size of counting-sets by keeping track of only essential counter values. In summary, our contribution is not a new automaton model, but a sparse representation for counting-sets with preserved acceptance behavior and improved bounds on d-sparse flat c-regexes.

1.0.0.1 Related work.

Compact handling of bounded repetition in pattern matching has a long history. XFA [@SmithEJ08] augments finite-state automata with auxiliary variables, including counters, and is motivated by intrusion detection signatures with heavily repeating subpatterns. Björklund et al. [@BjorklundMT15] study the incremental evaluation of succinct regular expressions with numerical constraints, giving bounds for maintaining matches under edits. In the non-backtracking matching literature closer to our setting, counter automata [@GeladeGM12; @TuronovaHLSVV20], counting-set automata [@HolikSTV23; @TuronovaHLSVV20], and bit-vector automata [@GlaunecKM23] each trade expressiveness for efficiency differently. Our work stays within the counting-set framework of [@HolikSTV23; @TuronovaHLSVV20] and targets its main remaining bottleneck: the cost of replicating large counting-sets at branching transitions, which we eliminate through a sparse representation.

2 Preliminaries↩︎

By \({\mathbb{N}}\) we denote the set of positive integers and let \({\mathbb{N}}_0\) and \({\mathbb{N}}_{\infty}\) be \({\mathbb{N}}\) union the singleton sets \(\{0\}\) and \(\{\infty\}\), respectively. We assume that \(n<\infty\) for all \(n \in {\mathbb{N}}_0\). If \(M, N \subseteq {\mathbb{N}}_0\) and \(k \in {\mathbb{N}}_0\), then \(k \circleddash M\), \(N \circleddash k\) and \(M \circleddash N\) denote \(\{k \circleddash m \mid m \in M\}\), \(\{ n \circleddash k \mid n \in N \}\) and \(\{ m \circleddash n \mid m \in M, n \in N \}\), respectively, for \(\circleddash\) any binary operator on \({\mathbb{N}}_0\). For \(l \in {\mathbb{N}}_0\) and \(h \in {\mathbb{N}}_\infty\), with \(l\le h\), we denote by \([l,h]\) the interval given by \(\{n \in {\mathbb{N}}_0 \mid l \le n \le h\}\). Thus, to simplify our presentation, we adopt the convention of denoting all integers greater than or equal to \(l\), as \([l,\infty]\), instead of \([l,\infty)\).

We denote a partial function \(f\) from a set \(X\) to a set \(Y\) by \(f: X{\,\rightharpoonup\,} Y\). A partial function \(f: X{\,\rightharpoonup\,}Y\) is often represented as \(\{x \!: f(x)\}_{x \in X}\). For example, \(\{a\!:x, b\!: y\}\) denotes a function \(f\) such that \(f(a) = x\), \(f(b) = y\) and \(f(x)\) is undefined for all other \(x \in X\). A relation \(\to\) on sets \(A\) and \(B\) is functional if for \(a \in A\) there exists at most one \(b \in B\) such that \(a \to b\).

An alphabet \(A\) is a set of characters, and a string \(w = a_1 a_2 \cdots a_n\) over \(A\) is a finite sequence of characters with \(a_i\in A\). The length \(|w|\) of the string \(w\) is the number \(n\) of characters in \(w\). Similar notation is used to denote the cardinality of a finite set \(B\), that is, \(|B|\), but given notational conventions, this will not create confusion. The empty string of length zero is denoted by \(\varepsilon\). For strings \(u = a_1 a_2 \cdots a_n\) and \(v = b_1 b_2 \cdots b_m\), their concatenation \(u \cdot v\) is the string \(a_1 a_2 \cdots a_n b_1 b_2 \cdots b_m\). Languages over the alphabet \(A\) are sets of strings over \(A\). For two languages \(L_1\) and \(L_2\), their concatenation \(L_1 \cdot L_2\) is defined as \(\{ uv \mid u \in L_1, v \in L_2\}\). For a language \(L\), we define \(L^0 = \{ \varepsilon \}\) and \(L^{i+1} = L^i \cdot L\) for all \(i \ge 0\). The Kleene star and plus of \(L\) are defined by \(L^* = \bigcup_{i \ge 0} L^i\) and \(L^+ = \bigcup_{i \ge 1} L^i\), respectively. Thus, \(L^* = L^+\cup \{\varepsilon\}\).

2.1 Symbolic regular expressions with counter operators↩︎

In practice, regexes extensively use character classes, such as \d, which are equivalent to (0|1|\(\cdots\)|9) in Perl-compatible regular expression syntax. That is, \d is a predicate matching a set of characters. To harmonize with this, we operate on symbolic regular expressions in which counter operators might also be present. Readers more comfortable with ordinary regular expressions over an alphabet \(A\) may, throughout, read each predicate \(\sigma\) simply as a single character of \(A\); the algorithmic content does not depend on the predicate machinery beyond the membership test \(a \in {{[\![}{}{\sigma}{]\!]}{}}\). We begin with the definition of a Boolean algebra—see [@symlearn] for more details.

When the domain \(A\) is an alphabet, each predicate \(\sigma\) defines the set \({{[\![}{}{\sigma}{]\!]}{}} \subseteq A\) of symbols satisfying the predicate, which are the character classes of practical regular expressions.

By \(L(r)\) we denote the language associated with a c-regex \(r\), which is defined inductively as follows. We let \(\sigma\in\Sigma\) and \(r_1\) and \(r_2\) be c-regexes. Then, we define (1) \(L(\varepsilon) = \{ \varepsilon \}\) and \(L(\sigma) = {{[\![}{}{\sigma}{]\!]}{}}\); (2) \(L(r_1 \cdot r_2) = L(r_1) \cdot L(r_2)\) and \(L(r_1 | r_2) = L(r_1) \cup L(r_2)\); (3) \(L(r_1^*) = L(r_1)^*\), \(L(r_1^+) = L(r_1)^+\) and \(L(r_1^?) = L(r_1) \cup \{ \varepsilon \}\); and (4) \(L(r_1^{\{l,h\}}) = \bigcup_{i \in [l,h]} (L(r_1))^i\).

We use \(|r|_\Sigma\) to denote the number of occurrences of predicates in \(r\). The counting-height of the c-regex \(r\) is the maximum depth of nested counting operators in \(r\). If \(r\) contains no counter operations, we define the counting-height of \(r\) as \(0\). A c-regex is flat if the counting-height of the regex is at most \(1\). Let \(H(r)\) denote the largest finite bound in a counter range in \(r\) (i.e.every subexpression \(s^{\{l,h\}}\) has \(l\le H(r)\) and, if \(h\not =\infty\), then \(h\le H(r)\)).

We use a typewriter font to denote specific c-regex instances for readability. For example, we write ‘(a|bc){2,10}’ instead of ‘\((a | bc)^{\{2, 10\}}\)’. Furthermore, although we may avoid infinite counter ranges by rewriting \(r^{\{l,\infty\}}\) as \(r^{\{l,l\}}r^*\), we will see in Section 3 that this rewrite harms matching performance when using sparse counting-sets.

2.2 Counter automata↩︎

Counter automata (CAs) are an extension of nondeterministic finite-state automata designed to match c-regexes [@KongYCGHMY22; @TuronovaHLSVV20]. Our definition closely aligns with the formalism presented by Turonova et al. [@TuronovaHLSVV20].

Let \(C = \{c_1, c_2, \ldots, c_k \}\) be a finite set of counter variables. A function \(\alpha: C \to {\mathbb{N}}_0\) is called an assignment for \(C\), and the set of all assignments for \(C\) is denoted as \({\mathsf{Assign}}(C)\). A guard over \(C\) is any function \(\psi: c_i \in C \mapsto \psi_i\), where \(\psi_i\) is a Boolean combination of predicates of the form \(\top\) (true), \(\bot\) (false), \(c_i \le h\) and \(l \le c_i\) with \(l\in {\mathbb{N}}_0\) and \(h\in{\mathbb{N}}_\infty\) (note, the predicate \(c_i\le\infty\) is always satisfied). An assignment \(\alpha\) satisfies \(\psi\) if, for every counter variable \(c_i\), the boolean expression \(\psi_i(n_i)\), which is obtained from \(\psi_i\) by substituting \(c_i\) with its value \(n_i = \alpha(c_i)\) in \(\psi_i\), evaluates to true; we denote this by \(\alpha \models \psi\). The set of all guards over \(C\) is denoted by \({\mathsf{Guard}}(C)\).

An action over \(C\) is a function \(\theta: c_i \mapsto \theta_i(c_i)\), where \(\theta_i \in \{ {\mathsf{nop}}, {\mathsf{reset}}, {\mathsf{inc}}, {\mathsf{inact}}\}\), and (1) \({\mathsf{nop}}: n \mapsto n\), (2) \({\mathsf{reset}}: n \mapsto 1\), (3) \({\mathsf{inc}}: n \mapsto n+1\), and (4) \({\mathsf{inact}}: n \mapsto 0\). We denote by \({{{[\![}{}{\alpha}{]\!]}{}}_{\theta}}\) the assignment obtained by applying \(\theta\) to \(\alpha\). Thus, \({{{[\![}{}{\alpha}{]\!]}{}}_{\theta}}(c_i) := \theta_i(\alpha(c_i))\). The set of all actions over \(C\) is denoted as \({\mathsf{Action}}(C)\).

It may be useful to look ahead to Example 2 with Figure [fig:ca-construction] for a CA as we complete the definitions. For a string \(w\), we define when a CA \(M\) accepts \(w\). A configuration (config) of \(M\) is a pair \((q, \alpha) \in Q \times {\mathsf{Assign}}(C)\). We define a transition relation \(\to_{(M,a)}\), for a character \(a \in A\), over configs, as follows: \[(p, \alpha) \to_{(M,a)} (q, \beta) \iff \exists (p,\sigma, \psi, \theta, q) \in \Delta: \alpha \models \psi \land a \in {{[\![}{}{\sigma}{]\!]}{}} \land \beta = {{{[\![}{}{\alpha}{]\!]}{}}_{\theta}}.\] Then, for a string \(w=a_1 a_2 \cdots a_n \in A^*\) with \(a_i \in A\), we define \(\to_{(M,w)}\) as follows: \[(q_0, \alpha_0) \to_{(M,w)} (q_n, \alpha_n) \iff (q_0, \alpha_0) \to_{(M,a_1)} (q_1, \alpha_1) \to_{(M,a_2)} \cdots \to_{(M,a_n)} (q_n, \alpha_n).\] We write \(\to_w\) for \(\to_{(M, w)}\) when \(M\) is clear from the context.

The initial config of \(M\) is \((q_{\mathsf{init}}, \alpha_{\mathsf{init}})\), where \(\alpha_{\mathsf{init}}(c_i) = 0\) for all \(c_i \in C\), and final configs of \(M\) are configs \((q, \alpha)\) satisfying \(\alpha \models F(q)\). We call a config \((q, \alpha)\) reachable if \((q_{\mathsf{init}}, \alpha_{\mathsf{init}}) \to_w (q, \alpha)\) for some string \(w \in A^*\). If the config \((q, \alpha)\) is final, then we say \(M\) accepts \(w\). We define \(L(M) := \{w \in A^* \mid \text{M accepts w}\}\).

2.3 Thompson-like matching algorithm↩︎

For a c-regex \(r\) and a string \(w \in A^*\), a Thompson-like matching algorithm decides whether \(w \in L(r)\), as follows: Consider a CA equivalent to \(r\), which we denote by \(M(r)\). A super-config of \(M\) refers to a set of configs of \(M(r)\). Next, we define the functional relations \(\Rightarrow_a\) and \(\Rightarrow_w\), over super-configs, for each super-config \(S\), character \(a \in A\) and \(w = a_1 a_2 \cdots a_n \in A^*\), as follows: \[\begin{align} S \Rightarrow_{(M, a)} \{ (q, \beta) \in Q \times {\mathsf{Assign}}(C) \mid \exists (p, \alpha) \in S: (p, \alpha) \to_{(M, a)} (q, \beta) \}, \\ (S \Rightarrow_{(M, w)} S_n) \iff (S \Rightarrow_{(M, a_1)} S_1 \Rightarrow_{(M, a_2)} S_2 \Rightarrow_{(M, a_3)} \cdots \Rightarrow_{(M, a_n)} S_n). \end{align}\] We write \(\Rightarrow_w\) for \(\Rightarrow_{(M, w)}\) when \(M\) is clear from the context.

Note that if \(\{ (p, \alpha) \} \Rightarrow_w T\), then \((p, \alpha) \to_w (q, \beta)\) if and only if \((q, \beta) \in T\). Finally, \(w \in L(M)\) if \(S_{\mathsf{init}}\Rightarrow_w S_n\), where \(S_{\mathsf{init}}:= \{(q_{\mathsf{init}}, \alpha_{\mathsf{init}})\}\) is the initial super-config, and \(S_n\) contains a final config.

2.4 Flat counter automata↩︎

Next, we consider the position CA constructed from a c-regex \(r\) with the position construction as in [@GeladeGM12]; for example, [fig:position-construction] shows the position CA of the c-regex a((bc){2,10})+d{3,3}. The position CA of \(r\) has \(|r|_{\Sigma}\) states (where \(|r|_{\Sigma}\) denotes the number of predicates from \(\Sigma\) in \(r\)) and at most \({(|r|_{\Sigma})}^2\) transitions, and it has the properties outlined next (see [@HolikSTV23]). We begin with two required definitions.

For each state \(q \in Q\), we denote by \(C_q := \{ c_i \in C \mid q \in Q_i \}\) the set of counter variables whose scope contains \(q\). Furthermore, we define \(Q_0 := Q \setminus \bigcup_{c_i \in C} Q_i\) as the set of states outside the scope of any counter. Consequently, \(C_q = \emptyset\) for any \(q \in Q_0\).

The following two properties generalize the property presented in Appendix B.1 of Holı́k et al. [@HolikSTV23].

Each of these follows naturally from the structure of the counter scopes. For example, in 1 we are outside the scope, so the counter has no effect, [item:type-0]; cases 2 and 3 enter and exit the scope. Only case 3 is somewhat complex, as the transition goes from a state inside the scope to another inside the scope. This can happen either without interacting with the counter operation at all, giving us [item:type-0]; by iterating the counter operation once, giving us [item:type-2]; or by exiting the counter operation and reentering it, using some enclosing closure, resetting the counter in [item:type-3].

We focus on the position CAs of flat c-regexes, referred to as flat CAs. In a flat CA, \(|C_q| = 1\) for \(q \notin Q_0\) and \(|C_q| = 0\) otherwise. In the flat case, we simplify the notation of a config \((q, \alpha)\) as follows: If \(q \in Q_i\) for some \(c_i \in C\), then the config is written as \((q, \alpha(c_i))\); if \(q \in Q_0\), it is written as \((q, 0)\). Note that every c-regex can be converted into a flat c-regex using counter-expansion [@Cox10] where we perform the expansion for all but one of the nested counters.

2.5 Counter configurations↩︎

Next, we describe the counting-set data structure that is used to represent a set of counter values assigned to a counter variable at each state, following Turoňová et al. [@TuronovaHLSVV20]; see also Le Glaunec et al. [@GlaunecKM23] for a related bit-parallel approach.

We can compute \({\mathsf{check}}(s)\), \({\mathsf{inc}}(s)\), and \({\mathsf{add}_1}(s)\) in time \(O(1)\). The operation \({\mathsf{merge}}(s_1, s_2)\) runs in \(O(o_2)\) time because \(o_2\) bounds (from above) both the size of \(\ell^2\) and the number of elements in \(\ell^1\) that must be processed during the merge. The operation \({\mathsf{merge}}(s_1, s_2)\) is defined as a destructive update where \(s_1\) consumes \(s_2\). Consequently, \(s_2\) becomes unavailable for further use. When computing \({\mathsf{merge}}(s_1, s_2)\), the number of visited elements in \(\ell_1\) and \(\ell_2\) is bounded by \(2 \cdot o_2\). Moreover, since the offset of \(s_2\) is \(o_2\), this implies that there were \(o_2\) calls to \({\mathsf{inc}}\) on \(s_2\) before merging. Combined with the fact that \(s_2\) is consumed by \({\mathsf{merge}}(s_1, s_2)\), this implies that the amortized time complexity of \({\mathsf{merge}}(s_1, s_2)\) is constant [@HolikSTV23]. 3 illustrates the structure of a counting-set.

Counting set automata use counting sets for efficient matching of c-regexes with CAs [@TuronovaHLSVV20; @GlaunecKM23; @HolikSTV23]. As a basis for our proposed matching algorithm, we describe counter-configurations, which we subsequently modify to obtain sparse counting-sets.

Note that the counter values associated with a state \(q\) are placed in the set \(f(q)\), which is represented using the counting-set structure. This representation allows a c-config to increase all values simultaneously via the operation \({\mathsf{inc}}\).

We define a flat c-regex \(r\) to be replicating if its corresponding position CA contains a state \(p \in Q_i\) with at least two outgoing transitions whose operations \(\theta(c_i)\) are from \(\{ {\mathsf{nop}}, {\mathsf{inc}}\}\) and whose predicates \(\sigma_1\) and \(\sigma_2\) are not disjoint (i.e., \({{[\![}{}{\sigma_1}{]\!]}{}} \cap {{[\![}{}{\sigma_2}{]\!]}{}} \ne \emptyset\)). 4 illustrates a CA of a replicating c-regex. In such a case, the matching algorithm in 5 needs to replicate the counting-set \(s\) in order to compute \(s'\). This replication requires time linear in the size of \(s\), which is at most \(H(r)\). Recall, \(H(r)\) denotes the largest finite bound in a counter range in \(r\) (i.e., every subexpression \(s^{\{l,h\}}\) has \(l\le H(r)\) and, if \(h\not =\infty\), then \(h\le H(r)\)). Next, we use this observation on the cost of replicating counting sets to analyse the time complexity of 5.

5 uses a counting-set data structure and c-configs to match an input string against a CA obtained by applying the position automaton construction to a flat c-regex. Notably, Line [line:condition-check] does not explicitly check guards for \({\mathsf{nop}}\) and \({\mathsf{inc}}\). This is unnecessary because (1) the guard component that corresponds to \({\mathsf{nop}}\) and \({\mathsf{inc}}\) is always \(\top\) and \(c_i < h_i\) by Property 1, and (2) counting-set’s \({\mathsf{inc}}\) operation implicitly filters out values that exceed the upper bound \(h_i\). For each state \(p\), the algorithm counts the number of outgoing transitions with \({\mathsf{nop}}\) or \({\mathsf{inc}}\) operations in Line [line:replication-count]. If more than one such transition exists, the corresponding counting-set is replicated in Line [line:replication]. Finally, as guaranteed by Property 1, the cases handled in Lines [line:transition-0], [line:transition-1], and [line:transition-2] are exhaustive and cover all possible transitions. Although we will not provide a formal correctness argument, note that the natural correctness invariant for 5 is the following: After processing the first i characters of the input, the c-config \(f\) maps each state \(q\) to exactly the set of counter values \(n\) such that the flat CA has a reachable config \((q,n)\) after that prefix.

For the proposition below to hold, we need to rewrite \(r^{\{l, \infty\}}\) as \(r^{\{l, l\}}r^*\). Alternatively, one may provide special treatment for the case \(r^{\{l, \infty\}}\) (not given in the pseudocode listed for Algorithm 5). For this, we split the transition for \((c_i < h, {\mathsf{inc}})\) of T4 in Definition 5 into \((c_i < l, {\mathsf{inc}})\) and \((c_i = l, {\mathsf{nop}})\) if \(h = \infty\), or by constraining the \({\mathsf{inc}}\) operation to have no effect once a counter reaches its lower bound \(l\) (if \(h = \infty\)).

3 Sparse counting-sets↩︎

Recall that the matching time complexity of replicating c-regexes depends on the maximum size of counting-sets. We propose a new data structure, the sparse counting-set, which stores only useful values. For example, for an expression \(E^{\{5,10\}}\) the sets \(\{4,5,6,7,8,9,10\}\) and \(\{4,10\}\) are indistinguishable under the counting operators; they both satisfy \({\mathsf{check}}\), and do so when applying \({\mathsf{inc}}\) up to six times, but stop satisfying \({\mathsf{check}}\) on a seventh \({\mathsf{inc}}\). This difference, at which any intermediary counter values become useless, will be used throughout this section. We let \(k=h-l+1\), with \(k=\infty\) when \(h=\infty\).

As the definition implies, we will consider Algorithm 5 from here with the operations replaced by their sparse variants. The following lemmas are derived from the definitions of these operations.

Before stating the size bound, we record an invariant that simplifies the analysis. Although Definition 9 allows arbitrary sequences of \({\mathsf{inc}}\), \({\mathsf{sparseAdd}_1}\), and \({\mathsf{sparseMerge}}\), the sparse counting-sets that actually arise during a run of Algorithm 5 always satisfy \(o - \ell_i \geq 1\) for every index \(i\) (i.e., the value \(0\) occurs only in the bare initial counting-set \((0,\langle 0\rangle,l,h)\), which has \(|\ell| = 1\)).

The reason is as follows. \({\mathsf{sparseMerge}}\) is invoked only at line 25, in the branch \(c(q) \neq \bot \wedge \theta' \in \{{\mathsf{nop}},{\mathsf{inc}}\}\); by Property 1 this forces \(p, q \in Q_i\) for some counter \(c_i\), and a routine induction on the outer iteration shows that any counting-set stored at a state in some \(Q_i\) has an offset of at least \(1\). Propagating this through the operations: \(\mathsf{inc}\) strictly increments every \(v_i := o - \ell_i\), \({\mathsf{sparseAdd}_1}\) only ever prepends an element with \(v = 1\), and \({\mathsf{sparseMerge}}\) preserves the \(v\)-values of its operands. Since neither operand of a \({\mathsf{sparseMerge}}\) in Algorithm 9 is the bare initial counting-set, the invariant \(v_i \geq 1\) therefore propagates throughout. We will use this fact freely in Lemma 2 and Proposition 4.

From the early stopping criteria in \({\mathsf{sparseMerge}}\), and using that, we merge sparse lists (i.e.we can apply the previous lemma to these two lists), we obtain the following proposition, which guarantees that the time complexity of \({\mathsf{sparseMerge}}\) improves on that of \({\mathsf{merge}}\) (assuming a large enough value of \(k\)), while preserving amortized constant time in the non-replicating case.

Combined with Lemma 2, we derive the following definition of \(d\)-sparse. This property enables efficient matching with c-configs that use sparse counting-sets instead of regular counting-sets, which we refer to as sparse counter configurations (sc-configs).

With all this in hand, we can now state a bound on the membership problem using sparse counting-sets, stated in terms of \(d\). In many cases, \(d\) will be quite small, and in addition, in practice, this bound is pessimistic, as it accounts for the possibility of replicating sets linearly many times.

4 Experimental evaluation↩︎

We evaluate the efficiency of our sparse counting-set approach against baselines. Efficiency is quantified by the total computation steps required for symbol evaluations, guard checks, and counting-set operations. This includes (1) the number of processed counter values during \({\mathsf{merge}}\) operations and (2) the number of counter values involved in the replication of counting-sets. Performance is assessed through targeted analyses of hand-crafted patterns and large-scale evaluations on the Polyglot and Snort3 under adversarial and random input scenarios.

4.1 Results on targeted regular expressions↩︎

Manually designed c-regexes have one of the following properties: (a) non-replicating, (b) 2-sparse, or (c) neither. We evaluate and compare four distinct methods—counter-expansion followed by Thompson NFA matching (c-expansion), Thompson-like matching with super-configs (super-config), standard counter-configs (c-config), and counter-configs with sparse counting-sets (sc-config). For the c-expansion method, the position CA construction is applied to the counter-expanded regex, yielding a standard position NFA where all guards are \(\psi(c) = \top\) and actions are \(\theta(c) = {\mathsf{nop}}\).

The results in 7 highlight the advantages of our sparse counting-set approach. First, both the counter-expansion and super-config methods fail to achieve linear-time matching. As shown in 7 (b), the standard c-config approach is also limited, achieving linear-time performance only on non-replicating c-regexes. However, by incorporating the sparse counting-set, we extend this capability to achieve linear-time matching for replicating c-regexes that are \(d\)-sparse for a bounded \(d\). The reason our sparse counting-set provides no advantage in 7 (c) is explained by Lemma 2. For a counting operator such as {k,k}, the upper bound \(H'(l,h)\) of the number of values in a sparse counting-set becomes equal to an upper bound \(h\) for the non-sparse one, as \(h - l + 1\) is simply \(1\). As both bounds are k, any potential benefit from sparsity is lost.

Furthermore, our experimental results demonstrate that for cases with a finite upper bound \(h\) in a counter operation \(r^{\{l, h\}}\), the performance of the super-config method is within a constant factor of the counter-expansion approach. This result aligns with the theoretical explanation—each config \((q,n)\) in the super-config approach is equivalent to a state in the position NFA generated by counter-expansion. The constant factor difference arises from the elimination of guards and actions in the position NFA of the expanded regex.

4.2 Results on real-world regular expressions↩︎

Next, we use c-regexes from two sources: the Polyglot regex corpus by Davis et al. [@DavisMCSL19] and the Talos LightSPD Snort3 ruleset (snapshot-31470). Polyglot contains 511,196 patterns (30,833 with counters) and Snort3 contains 9,755 patterns (2,837 with explicit counters). Table 1 summarizes the structural properties of these patterns, determined via static analysis of their position counting automata.

We also compute the distribution of \(H'(l,h)\) for 64,792 and 4,734 individual counter operators found in flat regexes from Polyglot and Snort3, respectively, to assess the practical bound of the parameter d on matching performance. Figure 8 illustrates histograms of lower-bound \(l\) and upper-bound \(h\) of counter operators and the size \(H'(l,h)\) of sparse counting-sets in our approach.

The bottom row of 8 is the empirical distribution of \(H'(l,h)\), whose per-pattern maximum is exactly the \(d\) of 5. In both corpora, the mass concentrates at small values, with only a short tail at \(H'(l,h) \ge 10\); this is driven by the commonly occurring unbounded ranges, which give \(H'(l,h) = 2\) by Lemma 2. Hence, for most real-world patterns, \(d\) is a small constant, and the \(O(d \cdot (|r|_\Sigma)^2 |w|)\) bound is within a small factor of the non-replicating \(O((|r|_\Sigma)^2 |w|)\).

Our experiments evaluate the robustness of our approach by conducting two parallel sets of experiments simulating adversarial and random input scenarios. In both cases, we simulated a partial matching scenario by wrapping each pattern \(r\) as .*(r).* to generate corresponding input strings. Our final dataset is filtered to include only c-regexes that meet three criteria: they (a) contain at least one counting operation, (b) are supported by our implementation, and (c) have a successfully generated test case.

4.2.0.1 Adversarial (9):

EvilStrGen [@SuHLCG24] is designed to generate test cases that maximize the number of matching steps. EvilStrGen was configured to assume a non-backtracking engine and to generate string lengths of approximately 1,000. In summary, we use 10,108 and 611 c-regexes from the Polyglot and Snort3 datasets for the experiments with EvilStrGen, respectively.

4.2.0.2 Random (10):

We simulate a random-input scenario by generating matched inputs with Xeger². We use Xeger with its default limit \(10\), which decides the maximum number of repetitions for Kleene star, plus, and counting operators with infinite upper bounds. For the experiments with Xeger, we use 10,141 and 620 c-regexes from the Polyglot and Snort3 datasets, respectively.

5 Conclusion and future work↩︎

We introduced c-configs, a formalization of on-the-fly matching with counting-set automata [@HolikSTV23]. Based on this formalization, we presented a representation of super-configs as sparse counting-sets, minimizing the number of counter values that are required to be tracked.

One can utilize counter expansion to convert non-flat c-regexes into flat c-regexes. The choice of which counting operator to expand influences the resulting expression. For instance, the c-regex \(({\texttt{{a\{2,3\}b)\{2,2\}}}}\) can be expanded as either \({\texttt{{(aaa?b)\{2,2\}}}}\) or \({\texttt{{(a\{2,3\}b)(a\{2,3\}b)}}}\). Determining which expansion form leads to more efficient CA-based matching is left as future research. We would also like to explore the possibility of generalizing the (sparse) counting-set data structure to support non-flat c-regexes.

Acknowledgements↩︎

The authors thank Rick Bower and River Martin for their detailed review of the experimental results.

[@*]

---

1. Authors are listed alphabetically. While this work represents a collaborative effort, Sicheol Sung served as the lead author.↩︎

2. https://pypi.org/project/xeger/↩︎