Draft of a paper to appear in IPSJ-SIGPRO.

Checking Time Linearity of Regular Expression Matching
Based on Backtracking
Satoshi Sugiyama1,a)Yasuhiko Minamide1,b)Abstract: Most implementations of regular expression matching in programming languages are based on backtracking. With this implementation strategy, matching may not be achieved in linear time with respect to the length of the
input. In the worst case, it may take exponential time. In this paper, we propose a method of checking whether or
not regular expression matching runs in linear time. We construct a top-down tree transducer with regular lookaheadthat translates the input string into a tree corresponding to the execution steps of matching based on backtracking. The
regular expression matching then runs in linear time if the tree transducer is of linear size increase. To check thisproperty of the tree transducer, we apply a result of Engelfriet and Maneth. We implemented the method in OCaml
and conducted experiments that checked the time linearity of regular expressions appearing in several popular PHP
programs. Our implementation showed that 47 of 393 regular expressions were not linear.
Keywords: regular expression, tree transducer, linear size increase

1. Introduction
Regular expressions are extensively used in programs that manipulate strings such as web programs. However, there is an issue that regular expression matching may take an unexpectedly
long time. In the worst case, it may take exponential time withrespect to the length of the input. This is because most implementations of regular expression matching in programming languages
are based on backtracking. Recently, it has been pointed out that
this issue can be exploited for DoS attack [14]. Furthermore, thismay not only be just a matter of time, but may also change thebehavior of a program unexpectedly in implementations such as
PCRE (Perl-compatible regular expression) [10]. PCRE involves
a limit on the number of steps executed for regular expression
matching. If the number of steps exceeds this limit, the matchingis considered to fail even if it would succeed eventually without
the limit [10] *1 .
In this paper, we develop a method to check whether regularexpression matching runs in linear time with respect to the lengthof the input. This method is significant for the following situations.
• The method can be used as a criterion for selecting a particular implementation of regular expression matching. Although regular expression matching based on backtracking
takes exponential time in the worst case, its execution is fast
for expressions with linear execution time. It would then be
possible to choose an implementation based on backtracking
for those expressions with linear execution time.
• The method can be used to check existing programs in1
a)
b)
*1

Department of Computer Science, University of Tsukuba
sugiyama@score.cs.tsukuba.ac.jp
minamide@cs.tsukuba.ac.jp
Whether the limit has been exceeded can be checked by calling the function ‘preg last error()’, which returns the latest error code in the PCRE.
However, many programs do not check the error code.

volving regular expression matching. We could then ascertain that regular expression matching runs in a reasonableamount of time and does not exceed the limit. If we wereto find regular expressions whose matching may not run inlinear time, we could then devise a more eﬃcient equivalent
regular expression, or use another implementation not basedon backtracking.
Our method constructs a tree transducer from a regular expression and then applies the theory of tree transducers to check its
properties. We construct a top-down tree transducer with regularlookahead that translates an input string into a tree corresponding to the execution steps of matching based on backtracking.
The size of the output tree is proportional to the running time
for regular expression matching. Therefore, the regular expression matching runs in linear time if the size of every output treeof the tree transducer is linearly bounded by the size of the input tree. We say that a transducer is of linear size increase if
it has this property. It is decidable whether a tree transducer isof linear size increase by checking whether an equivalent input
proper tree transducer is finite copying. The notion of finite copying was introduced by Aho and Ullman [1] and it says that any
position of an input is translated by a transducer boundedly manytimes. To check this property, we apply a result of Engelfriet andManeth [7].
We have implemented the method in OCaml and conducted experiments that checked the time linearity of regular expressions
appearing in several popular PHP programs. The experiments
showed that 47 of 393 regular expressions were not linear. It
should be noted that our implementation only checks the property of finite copying. Although linear size increase does not imply finite copying in general, we believe that finite copying isa necessary and suﬃcient condition for linear size increase fortransducers constructed from regular expressions by our method.

1

Draft of a paper to appear in IPSJ-SIGPRO.

2. Preliminaries
The set of natural numbers is denoted by N. For k ∈ N, [k]denotes the set {1, . . . , k}. For a set S , |S | is the cardinality of S .
For a relation r ⊆ S × T and an element s ∈ S , r(s) = {t ∈∪T | (s, t) ∈ r}. For S ′ ⊆ S , r(S ′ ) = s∈S ′ r(s). The domain
and range of r are defined by dom(r) = {s ∈ S | r(s) , ∅} andrange(r) = r(S ). For r1 ⊆ S × T and r2 ⊆ T × U, their composition is r1 ◦ r2 = {(s, u) ∈ S × U | (s, t) ∈ r1 , (t, u) ∈ r2 }.
A ranked alphabet is a tuple (Σ, Arity) where Σ is a finite set
and Arity is a function of type Σ → N. For σ ∈ Σ, Arity(σ) is thearity of σ. If we write σ(n) , it implicitly requires Arity(σ) = n.
Σ(n) denotes {σ | σ(n) ∈ Σ}.
A structure constructed from a ranked alphabet is called aranked tree and we usually call it just a tree. The set of trees
constructed by a ranked alphabet Σ is denoted by T Σ . A subset of T Σ is called a tree language. Let X be a set of variables.
Then, T Σ (X) is the set of trees constructed from Σ and X. V(t)denotes the set of nodes of a tree t and is inductively defined by
V(σ(t1 , . . . , tk )) = {ϵ} ∪ {iu | u ∈ V(ti ), i ∈ [k]} where ϵ represents the root of the tree. For a tree t, the size of t is defined bysize(t) = |V(t)|. For a node u, t/u denotes the subtree of t at u. It
is defined by t/ϵ = t and σ(t1 , t2 , . . . , tk )/iu = ti /u. The lexicographic order over the nodes of t is denoted by ≤. For t ∈ T Σ (X),t1 , . . . , tk ∈ T Σ , x1 , . . . , xk ∈ X, we denote by t[xi ← ti | i ∈ [k]]the tree obtained by substituting ti for xi in t.
We define two representations of strings over Σ as trees. In
MON(Σ), every σ ∈ Σ has rank 1 and an additional symbol withrank 0 is used to denote the end of a string. In S T R(Σ), everyσ ∈ Σ has rank 0 and two additional symbols are used: a symbol
denoting the empty string and a symbol with rank 2 denoting theconcatenation of two strings. That is,(0)
MON(Σ) = {σ(1) |σ ∈ Σ} ∪ {ϵ M},

S T R(Σ) = {σ(0) |σ ∈ Σ} ∪ {•(2) , ϵS(0) }.
For example, the string abc is represented as a(b(c(ϵ M ))) overMON(Σ) and •(a, •(b, c)) over S T R(Σ). In the case of MON(Σ),
strings and trees are in one-to-one correspondence. In the case of
S T R(Σ), their correspondence is one-to-many. For example, thestring abc can be represented as •(•(a, b), c) or •(•(a, ϵS ), •(b, c))in addition to the representation above. For S T R(Σ), we say t iscompact if it is either ϵS or a tree that does not contain ϵS .

3. Tree-based Semantics of Regular Expression Matching
We focus on regular expression matching with priorities compatible with Perl and represent the execution steps of regular expression matching by a tree. The size of the tree is proportional
to the running time of the matching. Therefore, we can decide its
running time from the size of the tree. The semantics of regularexpression matching is given by the nondeterministic parser of
Sakuma et al. [15] defined by using the list monad.
The syntax of regular expressions is standard and defined asfollows.

r

::=
|
|
|
|

ϵ
c
r1 r2
r1 |r2r1∗(empty string)(symbol)(concatenation)(alternation)(repetition)

The language of a regular expression r, denoted by L(r), is defined as follows.
L(ϵ)
L(c)
L(r1 r2 )L(r1 |r2 )L(r1∗ )

=
=
=
=
=

{ϵ}
{c}
L(r1 )L(r2 )L(r1 ) ∪ L(r2 )L(r1 )∗For the purposes of this discussion, we exclude regular expressions that contain a subexpression r1∗ such that ϵ ∈ L(r1 ). Thisis because such expressions prevent a simple and intuitive definition of the semantics of Sakuma et al. [15] below, making themnonterminating and ill defined. Furthermore, such regular expressions are rarely used in practice.
Regular expressions in programming languages have priorities
in matching. In the alternation r1 |r2 , r1 has a higher priority thanr2 . If both of them match, the string is considered as matchedwith r1 . Repetition r1∗ is expanded as r1∗ = r1 r1∗ |ϵ and it therefore matches as many repetitions of substrings matching with r1
as possible.
The semantics is defined so that a result of matching with ahigher priority comes earlier in the list. The concatenation of
two lists is denoted by ++. The semantics of regular expression
matching is defined as follows.
Definition 3.1 (Semantics of regular expression matching).
N[[r]] :: Σ∗ → Σ∗ list
N[[ϵ]]w = [w] [w′ ]
N[[c]]w =  []if w = cw′
otherwise

N[[r1 r2 ]]w = N[[r1 ]]w ≫= λw′ .N[[r2 ]]w′
N[[r1 |r2 ]]w = N[[r1 ]]w ++ N[[r2 ]]w
N[[r1∗ ]]w = (N[[r1 ]]w ≫= λw′ .N[[r1∗ ]]w′ ) ++ [w]N[[r]]w returns a list of all possible strings that are obtained byconsuming a prefix of w matching with r.
Although the above semantics shows how to run regular expression matching, it explicitly says nothing about the execution
steps of regular expression matching. We therefore extend the semantics by using the tree monad instead of the list monad, where
the size of the tree abstracts the number of execution steps required for matching. The tree monad used corresponds to the
SearchTree monad [12] of Hackage 2, which is a Haskell library.
The tree monad is defined as follows.
α tree::=||Unit αFailOr (α tree) × (α tree)

The bind function ≫= is defined as follows.

2

Draft of a paper to appear in IPSJ-SIGPRO.

n=0

n=0
=

t0

n=2

Or

=

t2
Fail

Or

Unit abTrees of T [[a∗ ]]an b

v0

=

Fail
v1

=

T [[r1 r2 ]]w = T [[r1 ]]w ≫= λw′ .T [[r2 ]]w′
T [[r1 |r2 ]]w = Or(T [[r1 ]]w, T [[r2 ]]w)
T [[r1∗ ]]w = Or(T [[r1 ]]w ≫= λw′ .T [[r1∗ ]]w′ , Unit w)
The function T [[r]] preserves the priority of regular expression
matching. For example, t1 is a higher priority than t2 for Or(t1 ,t2 ).
We then have the following theorem.
Theorem 3.3.
leaflist(T [[r]]w) = N[[r]]w
where the function leaflist is defined as follows.
= [w]
= []
= (leaflist t1 )++(leaflist t2 )The size of the tree returned by the function T [[r]] is proportional to the time required to search all possible results of regularexpression matching. We can therefore discuss the running time
for searching all possible results of matching w with r by deciding
the size of the tree T [[r]]w.
Example 3.4 (Case of O(n)). Let us consider tn = T [[a∗ ]]an b.
Figure 1 shows t0 , t1 , and t2 . The size of each tree is size(t0 ) = 3,size(t1 ) = 5, and size(t2 ) = 7. Then, size(tn ) = 2n + 3. The actual
execution times by PCRE are 31.0ms for n = 1, 000, 000, 61.9ms
for n = 2, 000, 000, and 124ms for n = 4, 000, 000 *2 .
Example 3.5 (Case of O(n2 )). Let us consider un = T [[a∗ a∗ ]]an b.
Figure 2 shows u0 , u1 , and un . The size of each tree is as follows.
We show the average time for five executions in the C language.

Or

Unit aab

Unit bv1

Unit abFail

if w = cw′
otherwiseOr

Or

Fail ≫=tree f = FailT [[r]] :: Σ∗ → Σ∗ tree

=

tn

Or

Or

The semantics of regular expression matching is then extended
by the tree monad so that it abstracts its execution steps.
Definition 3.2 (Tree-based Semantics of Regular Expression
Matching).

n

n=2

Or

n=1

Unit w ≫=tree f = f w
Or(t1 , t2 ) ≫=tree f = Or(t1 ≫=tree f, t2 ≫=tree f )∗ ∗Trees of T [[a a ]]a b≫=tree :: α tree → (α → β tree) → β tree

leaflist (Unit w)
leaflist Failleaflist (Or(t1 , t2 ))

Or

n=0

Unit bUnit bT [[ϵ]]w = Unit w Unit w′
T [[c]]w =  Fail

=

un−1

t1

v2

Fig. 1*2

unOr

Unit ab
FailFailFig. 2

Unit aabOrOr

general case
=

u0

t0

Fail
Or

=

u1

Or

Or

Unit b

n=1
t1

n=1
=

u0

v0

v0

Fail

Fig. 3

Trees of T [[(aa∗ )∗ ]]an bsize(u0 ) = 2 + size(t0 ) = 5
size(u1 ) = size(u0 ) + size(t1 ) + 1 = 11size(un ) = size(un−1 ) + size(tn ) + 1
size(un ) is expanded as follows.
size(un ) =n∑(size(tk ) + 1) + size(t0 ) + 2
k=1

n
∑
=
(2n + 4) + 5
k=1= n2 + 5n + 5
The actual execution times by PCRE are 1.41s for n = 10, 000,
5.70s for n = 20, 000, and 22.7s for n = 40, 000.
Example 3.6 (Case of O(2n )). Let us consider vn =T [[(aa∗ )∗ ]]an b. Figure 3 shows v0 , v1 , and v2 . The size ofeach tree is as follows.
size(v0 ) = 3
size(v1 ) = size(v0 ) + 4 = 7
size(v2 ) = size(v0 ) + size(v1 ) + 5 = 15
The size of vn is calculated as follows.
size(vn ) =n−1∑size(vk ) + n + 3

k=1= size(vn−1 ) +n−2∑size(vk ) + (n − 1) + 3 + 1

k=1= 2size(vn−1 ) + 1
n+1
∑
=
2k
k=0

= 2n+2 − 1
The actual execution times by PCRE are 1.07s for n = 23, 2.14s
for n = 24, and 4.27s for n = 25. If the limit on execution steps isset to 1, 000, 000, 000, then the limit is exceeded for n = 28.
The function T [[r]] searches all results matching an input string

3

Draft of a paper to appear in IPSJ-SIGPRO.

Or1

Or

Or

Or

Fail

Fail

Or2

Or

Or
Unit ϵFig. 4

Fail

Unit aUnit ϵ

Or2

Fail

Fail

Success

Trees of T [[a∗ a∗ ]]a and first(T [[a∗ a∗ ]]a)with the regular expression r. However, in actual implementations based on backtracking, once a matching succeeds, the execution of matching stops and no other results are searched. Therefore, we need to construct a tree that represents the execution until
the first success. To represent such trees, we revise the definitionof trees as follows.
ctree

::=
|
|
|

mainly use bottom-up tree automata.
Definition 4.1 (Bottom-up tree automata). A bottom-up tree automaton is a tuple (P, Σ, h) where P is a finite set of states, Σ is aranked alphabet, and h is a family of functions called a transition
function. For σ(k) , hσ is a function of type Pk → P.
For better readability, if we have hσ (p1 , . . . , pk ) = p, we write
this transition as follows.

Success
Fail
Or1 ctree
Or2 ctree × ctreeIn Σ∗ tree, Unit ϵ represents a successful matching since it consumes the whole input string. From this consideration, we introduce a function that transforms Σ∗ tree into ctree.
We first introduce the following function that checks whether
a subtree contains a successful match.
 true if w = ϵhave succ (Unit w)= false otherwise= falsehave succ Failhave succ (Or(t1 , t2 )) = have succ t1 ∨ have succ t2
Then, the following function transforms Σ∗ tree into ctree.
 Success if w = ϵfirst (Unit w)= Failotherwise
first Fail= Fail
Or1 (first t1 )






 if have succ t1 = true
first (Or(t1 , t2 )) = 
Or2 (first t1 , first t2 )





otherwise
For matching a string w with a regular expression r, first(T [[r]]w)
is the tree representing the execution steps until the first successful match.
Example 3.7. Let us consider T [[a∗ a∗ ]]a. Figure 4 shows
T [[a∗ a∗ ]]a and first(T [[a∗ a∗ ]]a). At the root of T [[a∗ a∗ ]]a, Or istransformed to Or1 because its left subtree contains Unit ϵ. Because other nodes do not contain Unit ϵ in their left subtrees, thestructure of T [[a∗ a∗ ]]a is preserved by transforming Or into Or2 .

4. Tree Transducers of Linear Size Increase
4.1 Tree Automata
A tree automaton is an extension of an automaton that works
on trees instead of strings [2]. A top-down tree automaton starts
its computation from the root of a tree and moves on to its leaves,
whereas a bottom-up tree automaton starts its computation fromthe leaves of a tree and moves on to its root. In this paper, weσ(p1 , . . . , pk ) → p
The transition function h is extended to h̃ over T Σ as follows.
h̃(σ(t1 , . . . , tk )) = hσ (h̃(t1 ), . . . , h̃(tk ))In this paper, we sometimes use a bottom-up tree automaton(P, Σ, h, Q f ) with a set of final states Q f . We then say that t is
accepted by the tree automaton if h̃(t) ∈ Q f . A tree language isregular if it is accepted by some tree automaton.
Example 4.2 (Tree automata). Let us consider a tree automaton over a Boolean expression consisting of 0, 1, and disjunction. The automaton is described by (P, Σ, h, Q f ), where Σ ={or(2) , 0(0) , 1(0) }, P = {p0 , p1 }, and h consists of the following
rules.
0 → p0 ,1 → p1or(p1 , p0 ) → p1 , or(p0 , p1 ) → p1
or(p1 , p1 ) → p1 , or(p0 , p0 ) → p0
We then have the following transition for or(or(1, 0), 1).
or(or(1, 0), 1) ⇒ or(or(p1 , 0), 1)⇒ or(or(p1 , p0 ), 1) ⇒ or(p1 , 1)
⇒ or(p1 , p1 ) ⇒ p1
4.2 Tree Transducers
A tree transducer is an extension of a tree automaton that takes
a tree as input and produces a tree as output. As for tree automata, there are two variants, namely top-down and bottom-up
tree transducers. In this paper, we use an extension of top-downtree transducers, called top-down tree transducers with regularlookahead (or T R for short).
We now introduce some notations for the definition of topdown tree transducers with regular lookahead. Let the set of variables {x1 , x2 , . . . , xk } be denoted by Xk . We regard a tuple consisting of a state and a variable as a symbol of rank 0, and write⟨Q, Xk ⟩ = {⟨q, xi ⟩ | q ∈ Q, xi ∈ Xk }.
Definition 4.3 (Top-down tree transducer with regular lookahead). A top-down tree transducer with regular lookahead is atuple (Q, P, Σ, ∆, Q0 , R, h) where Q is a finite set of states, Σ is an
input ranked alphabet, ∆ is an output ranked alphabet, Q0 ⊆ Q
is a set of initial states, (P, Σ, h) is a bottom-up tree automaton,
called a lookahead automaton, and R is a set of transition rules.
Each transition rule in R has the following form:⟨q, σ(x1 , . . . , xk )⟩ → ζ ⟨p1 , . . . , pk ⟩where ζ ∈ T ⟨Q,Xk ⟩∪∆ and ⟨p1 , . . . , pk ⟩ is the condition represented
by a tuple of states p1 , . . . , pk of the lookahead automaton. Whenthe tree transducer reads σ at state q, the tree is rewritten to ζ ifh̃(xi ) = pi for i ∈ [k].

4Draft of a paper to appear in IPSJ-SIGPRO.

If the transition rule

following rule.
⟨q, or(x1 , x2 )⟩ → or(⟨q, x1 ⟩, ⟨q, x2 ⟩)⟨q, σ(x1 , . . . , xk )⟩ → ζ ⟨p1 , . . . , pk ⟩applies for all p1 , . . . , pk ∈ P, it is written in short form as follows.
⟨q, σ(x1 , . . . , xk )⟩ → ζ
In the following definition of the derivation relation for treetransducers, a tuple consisting of a state and a tree is regarded asa symbol of rank 0: ⟨Q, T Σ ⟩ = {⟨q, t⟩ | q ∈ Q, t ∈ T Σ }. We now
define the derivation relation ⇒ M of a top-down tree transducer
M with regular lookahead.
Definition 4.4 (Derivation relation). Let M=(Q, P, Σ, ∆, Q0 , R, h) be a T R . Let us consider the following
transition rule of M.
⟨q, σ(x1 , . . . , xk )⟩ → ζ ⟨p1 , . . . , pk ⟩For ξ1 , ξ2 ∈ T ⟨Q,TΣ ⟩∪∆ , if the following conditions hold, then wesay ξ2 is derived by ξ1 and write ξ1 ⇒ M ξ2 .
( 1 ) ξ1 /u = ⟨q, σ(s1 , . . . , sk )⟩.
( 2 ) h̃(si ) = pi (1 ≤ i ≤ k).
( 3 ) ξ2 = ξ1 [u ← ζ ′ ] where ζ ′ is the following tree.
ζ ′ = ζ[⟨q′ , xi ⟩ ← ⟨q′ , si ⟩ | ⟨q′ , xi ⟩ ∈ ⟨Q, Xk ⟩]The translation realized by a tree transducer M is denoted byτ M . For t ∈ T Σ , τ M (t) = {t′ ∈ T ∆ | q ∈ Q0 . ⟨q, t⟩ ⇒∗M t′ }.
The translation is extended for a tree language T : τ M (T ) =∪t∈T τ M (t).
Example 4.5 (Top-down tree transducer with regular lookahead).
For T Σ of Example 4.2, we consider a T R that translates a node
into its left subtree if the left subtree is evaluated to 1. The transducer is given by (Q, P, Σ, ∆, Q0 , R, h) where ∆ = Σ, Q = {q}, thelookahead automaton (P, Σ, h) is that of Example 4.2, and R has
the following rules.
⟨q, 0⟩ → 0 ,⟨q, or(x1 , x2 )⟩⟨q, or(x1 , x2 )⟩⟨q, or(x1 , x2 )⟩⟨q, or(x1 , x2 )⟩

→
→
→
→

⟨q, 1⟩ → 1
or(⟨q, x1 ⟩, ⟨q, x2 ⟩)or(⟨q, x1 ⟩, ⟨q, x2 ⟩)⟨q, x1 ⟩⟨q, x1 ⟩⟨p0 , p0 ⟩⟨p0 , p1 ⟩
⟨p1 , p0 ⟩⟨p1 , p1 ⟩We now show the transition of or(or(0, 1), or(1, 0)) by the transducer.
⟨q, or(or(0, 1), or(1, 0))⟩⇒ ⟨q, or(0, 1)⟩(1)⇒ or(⟨q, 0⟩, ⟨q, 1⟩)(2)⇒ or(0, ⟨q, 1⟩)(3)⇒ or(0, 1)(4)(1) Because the tree has the form ⟨q, or(x1 , x2 )⟩, the transition
is determined by h̃(or(0, 1)) = p1 and h̃(or(1, 0)) = p1 . The
tree is therefore rewritten by the following rule.
⟨q, or(x1 , x2 )⟩ → ⟨q, x1 ⟩⟨p1 , p1 ⟩(2) Because h̃(0) = p0 and h̃(1) = p1 , the tree is rewritten by the⟨p0 , p1 ⟩(3) The tree is rewritten by the rule ⟨q, 0⟩ → 0.
(4) The tree is rewritten by the rule ⟨q, 1⟩ → 1.
If the size of a tree obtained by the translation realized by a treetransducer M is linearly bounded with respect to the size of the
input tree, we say that M is of linear size increase: there existsc ∈ N such that size(t′ ) ≤ c · size(t) for any t ∈ T Σ and t′ ∈ τ M (t).
4.3 Finite Copying
We introduce a restriction of T R , called finite copying. If a treetransducer is finite copying, then it is of linear size increase [7].
Informally, a tree transducer M is finite copying if every subtree
t/u for u ∈ V(t) is translated boundedly many times by M for
any tree t. For the precise definition, we need to define the state
sequence at a subtree t/u that is the sequence of states translating the subtree t/u. To define state sequences, we introduce theextension of a T R that reads a state as an input symbol.
Definition 4.6 (Extension.
Definition4.1 [7]). Let M =R(Q, P, Σ, ∆, Q0 , R, h) be a T . The extension of M, denoted byˆ Q0 , R̂, ĥ) where Σ̂ = Σ ∪ {p(0) | p ∈ P},
M̂, is a T R (Q, P, Σ̂, ∆,∆ˆ = ∆ ∪ ⟨⟨Q, P⟩⟩, R̂ = R ∪ {⟨q, p⟩ → ⟨⟨q, p⟩⟩ | ⟨q, p⟩ ∈ ⟨Q, P⟩},ĥ p () = p for p ∈ P, and ĥΣ (p1 , . . . , pk ) = hσ (p1 , . . . , pk ) forσ ∈ Σ(k) , p1 , . . . , pk ∈ P.
We then define state sequences by using Definition 4.6.
Definition 4.7 (State sequence. Definition4.4 [7]). Let M =(Q, P, Σ, ∆, Q0 , R, h) be a T R , t ∈ T Σ and u ∈ V(t). Let p = h(t/u),ξ = M̂(s[u ← p]) ∈ T ⟨⟨Q,{p}⟩⟩∪∆ , and {v ∈ V(ξ) | ξ[v] ∈ ⟨⟨Q, {p}⟩⟩} ={v1 , . . . , vn } where v1 < . . . < vn . Then, the state sequencests M (t, u) of t at u is the sequence of states q1 · · · qn such thatξ[vi ] = ⟨⟨qi , p⟩⟩ for i ∈ [n].
The restriction of finite copying is defined by using Definition
4.7.
Definition 4.8 (Finite copying. Definition4.5 [7]). A T R M is finite copying if there exists c ∈ N such that |sts M (t, u)| ≤ c for anyt ∈ T Σ and u ∈ V(t).
Theorem 4.9 (Lemma 4.10(i)[7]). It is decidable whether or not
T R M is finite copying.
Proof. In [7], a macro tree transducer is used to construct astate sequence represented by T MON(Q) . However, in this paper,
we construct a state sequence represented by T S T R(Q) by using
a bottom-up tree transducer. This is because we do not have to
use a macro tree transducer. For the definition of bottom-up treetransducers, please refer to [5].
Let M = (Q, P, Σ, ∆, Q0 , R, h). The bottom-up tree transducer N that constructs a state sequence is given by ({r}, ∆ ∪⟨⟨Q, P⟩⟩, S T R(Q), {r}, R′ ). For ⟨⟨q, p⟩⟩ ∈ ⟨⟨Q, P⟩⟩, and δk ∈ ∆(k) ,R′ contains the following transition rules.
⟨⟨q, p⟩⟩→ r(q)δ0→ r(ϵS )δ1 (r(x))→ r(x)
δk (r(x1 ), . . . , r(xk ))→ r(•(x1 , •(x2 , . . . , •(xk−1 , xk ) . . .)))For t ∈ T Σ , u ∈ V(t), τN (τ M̂ (t[u ← h(t/u)])) is sts M (t, u) repre-

5Draft of a paper to appear in IPSJ-SIGPRO.

sented by S T R(Q). However, the trees in τN (τ M̂ (t[u ← h(t/u)]))may not be compact and may have some redundancy. We therefore make them compact by using Lemma 4.2[4] to discuss its
finiteness. Then, M is finite copying if and only if compactτN (τ M̂ (L)) is finite where L = {t[u ← h(t/u)] | t ∈ T Σ , u ∈ V(t)}.
Because L is regular, it is decidable whether or not τN (τ M̂ (L)) is
finite by using Lemma 3.8 [7].

5. Tree Transducer Simulating Regular Expression Matching
From a regular expression, we construct a tree transducer thatsimulates its matching and outputs the tree introduced in Section 3 that abstracts the execution steps of regular expression
matching based on backtracking. If the transducer is of linear size
increase, the running time of the matching for the regular expression is determined as linear. The construction of automata andtransducers in this section is based on the construction of Frischand Cardelli [8].
5.1 Construction of Automata by Frisch and Cardelli
In preparation for the construction of the tree transducer, we review the construction of an automaton from a regular expression
by Frisch and Cardelli [8].
We first define notations for list operations. We write x :: l forthe list obtained by adding the element x at the beginning of thelist l and l :: x for the list obtained by adding x at the end of l. The
operation :: is extended for a set of lists: x :: S = {x :: l | l ∈ S }.
We introduce locations of a regular expression: a location is asequence consisting of {fst, snd, lft, rgt, star}. The set of locations
in a regular expression r, denoted by λ(r), is defined as follows.
λ(ϵ)
λ(c)
λ(r1 r2 )λ(r1 |r2 )λ(r1∗ )

=
=
=
=
=

{[]}
{[]}
{[]} ∪ fst :: λ(r1 ) ∪ snd :: λ(r2 ){[]} ∪ lft :: λ(r1 ) ∪ rgt :: λ(r2 ){[]} ∪ star :: λ(r1 )The subexpression of r at a location l, denoted by r.l, is defined
as follows.
r.[]= r(r1 r2 ).(fst :: l) = r1 .l(r1 r2 ).(snd :: l) = r2 .l(r1 |r2 ).(lft :: l) = r1 .l(r1 |r2 ).(rgt :: l) = r2 .l(r1∗ ).(star :: l)= r1 .l
After matching a string with a subexpression r0 .l, the rest of thestring is matched with the successor of the subexpression. The
successor of a subexpression is defined as follows:succ([])
succ(l :: fst)
succ(l :: snd)succ(l :: lft)
succ(l :: rgt)
succ(l :: star)

=
=
=
=
=
=

qf
l :: sndsucc(l)succ(l)succ(l)l

where q f denotes the end of successful matching.
We now show the construction of an automaton from a regularexpression, following Frisch and Cardelli [8].
Definition 5.1 (Construction of an Automata from a Regular Expression). A nondeterministic automaton (Q, Σ ∪ {ϵ}, q f , E) isconstructed from a regular expression r0 where the set of states Q
is λ(r0 ) ∪ {q f } and the transition relation E ⊆ Q × (Σ ∪ {ϵ}) × Q
contains the following rules.
(l, c, succ(l)) ∈ E(l, ϵ, succ(l)) ∈ E(l, l :: fst) ∈ E(l, l :: lft) ∈ E, (l, l :: rgt) ∈ E(l, l :: star) ∈ E, (l, succ(l)) ∈ E

if r0 .l = c
if r0 .l = ϵ
if r0 .l = r1 r2
if r0 .l = r1 |r2
if r0 .l = r1∗

Let L(q) be the set of strings accepted by the automaton ofDefinition 5.1, starting from an initial state q ∈ Q.
Lemma 5.2 (Lemma 2 [8]). For all l ∈ λ(r0 ), we have L(l) =L(r0 .l)L(succ(l)). In particular, L([]) = L(r0 ).
5.2 Construction of Tree Transducers
In Section 3, we formulated T [[r]] that simulates regular expression matching and outputs a tree that abstracts its execution
steps. In this section, we construct a transducer that outputs thetree. A string w ∈ Σ∗ is considered as a tree over MON(Σ). For
example, the string abc is a tree a(b(c(ϵ M ))).
Definition 5.3 (Tree Transducer Simulating Regular Expression Matching). We define a top-down tree transducer Mr0 =(Q, Σ, ∆, Q0 , R) that searches all possible matchings with regular expression r0 . The input alphabet Σ is given by Σ = MON(Σ′ )for a set of characters Σ′ . The output alphabet ∆ is given by ∆ ={Success(0) , Fail(0) , Or(2) }. The set of states is Q = λ(r0 ) ∪ {q f }, theset of initial states is Qd = {[]}, and the set of transition rules R
has the following rules.
• Case l ∈ Q.
⟨l, c(x)⟩ → ⟨succ(l), x⟩ 
if r0 .l = c⟨l, c′ (x)⟩ → Fail





⟨l, ϵ M ⟩→ Fail⟨l, x⟩ → ⟨succ(l), x⟩
if r0 .l = ϵ⟨l, x⟩ → ⟨l :: fst, x⟩
if r0 .l = r1 r2⟨l, x⟩ → Or(⟨l :: lft, x⟩, ⟨l :: rgt, x⟩) if r0 .l = r1 |r2⟨l, x⟩ → Or(⟨l :: star, x⟩, ⟨succ(l), x⟩) if r0 .l = r1∗• Case: q f ∈ Q.
⟨q f , ϵ⟩ → Success
The top-down tree transducer Mr0 constructed from a regularexpression r0 reads the tree representation of an input string w
and outputs the tree that abstracts the computation matching w
with r0 .
It should be noted that the construction in Definition 5.3 contains ϵ-transitions and therefore does not conform to Definition
5.3 of top-down tree transducers with regular lookahead. However, the transition rules of Definition 5.3 have no loops of ϵtransitions and can therefore be transformed easily to give a transducer without ϵ-transitions.
Example 5.4 (Tree Transducer Simulating Regular Expression
Matching). We apply the top-down transducer Mr constructedfrom r = ab|c∗ to an input string ab.

6

Draft of a paper to appear in IPSJ-SIGPRO.

The set of states is Q = {[], [lft], [lft, fst], [lft, snd], [rgt], [rgt, star]}and the set of transition rules R contains the following rules.
⟨[], x⟩⟨[lft], x⟩⟨[lft, fst], a(x)⟩⟨[lft, snd], b(x)⟩⟨[rgt], x⟩⟨[rgt, star], c(x)⟩⟨q f , ϵ M ⟩

→
→
→
→
→
→
→

Or(⟨[lft], x⟩, ⟨[rgt], x⟩)⟨[lft, fst], x⟩⟨[lft, snd], x⟩⟨q f , x⟩Or(⟨[rgt, star], x⟩, ⟨q f , x⟩)⟨[rgt], x⟩
Success

where the transitions whose right hand side is Fail are omitted.
The following is the transition of the transducer for an input
ab.
⟨[], a(b(ϵ M ))⟩⇒ Mr Or(⟨[lft], a(b(ϵ M ))⟩, ⟨[rgt], a(b(ϵ M ))⟩)⇒ Mr Or⟨[lft, fst], a(b(ϵ M ))⟩,⟨[rgt], a(b(ϵ M ))⟩)⇒ Mr Or(⟨[lft, snd], b(ϵ M )⟩,⟨[rgt], a(b(ϵ M ))⟩)⇒ Mr Or(⟨q f , ϵ M ⟩,• Case r0 .l = r1 |r2 .
x∈L(l::lft)⟨l, x⟩ −→Or1 (⟨l :: lft, x⟩)x<L(l::lft)⟨l, x⟩ −→Or2 (⟨l :: lft, x⟩, ⟨l :: rgt, x⟩)• Case r0 .l = r1∗ .
⟨l, x⟩x∈L(l::star)⟨l, x⟩

x<L(l::star)−→−→

Or1 (⟨l :: star, x⟩)
Or2 (⟨l :: star, x⟩, ⟨succ(l), x⟩)

Example 5.6 (Tree Transducer Simulating Matching Based on
Backtracking). We apply the top-down transducer Mr′ constructed from r = ab|c∗ to an input string ab.
The set of transition rules of Mr′ is obtained by revising therules in Example 5.4 to give the following rules for the transitions from states [] and [rgt].
⟨[], x⟩x∈L([lft])−→

Or1 (⟨[lft], x⟩)⟨[], x⟩x<L([lft])

Or2 (⟨[lft], x⟩, ⟨[rgt], x⟩)−→⟨[rgt], x⟩x∈L([rgt,star])⟨[rgt], x⟩x<L([rgt,star])−→−→

Or1 (⟨[rgt, star], x⟩)
Or2 (⟨[rgt, star], x⟩, ⟨q f , x⟩)

The following is the transition of the transducer for an inputab.

⟨[rgt], a(b(ϵ M ))⟩)⇒ Mr Or(Success,⟨[], a(b(ϵ M ))⟩⟨[rgt], a(b(ϵ M ))⟩)

⇒ Mr′ Or1 (⟨[lft], a(b(ϵ M ))⟩)⇒ Mr Or(Success,Or(⟨[rgt, star], a(b(ϵ M ))⟩, ⟨q f , a(b(ϵ M ))⟩))⇒ Mr Or(Success,Or(Fail, ⟨q f , a(b(ϵ M ))⟩))⇒ Mr Or(Success, Or(Fail, Fail))
The top-down transducer constructed by Definition 5.3 outputs
the tree that abstracts the execution steps searching all possible
matchings. To simulate matching based on backtracking, we extend the construction in Definition 5.3 by using regular lookahead
so that the output of the transition abstracts the execution thatstops at the first successful matching. To simplify the presentation, we formulate the transition rules of the top-down transducer
with regular lookahead in the following form. For a tree regular
language L, we writex∈L⟨q, σ(x)⟩ −→ ξfor a transition rule that rewrites ⟨q, σ(x)⟩ into ξ when x ∈ L.
Definition 5.5 (Tree Transducer Simulating Matching Based on
Backtracking). For a regular expression r0 , we define a top-downtree transducer Mr′0 = (Q, Σ, ∆′ , Q0 , R′ ) with regular lookaheadthat simulates matching based on backtracking. The output alphabet is revised to ∆′ = {Success(0) , Fail(0) , Or1 (1) , Or2 (2) }. For
r1 |r2 or r1∗ , if the branch with a higher priority succeeds, it outputs
Or1 , containing only the subtree corresponding to that branch. If
the branch with a higher priority fails, it outputs Or2 , containing
the two subtrees corresponding to both possibilities. The transition rules of R are revised so that R′ has the following rules forthe cases r0 .l = r1 |r2 and r0 .l = r1∗ .

⇒ Mr′ Or1 (⟨[lft, fst], a(b(ϵ M ))⟩)
⇒ Mr′ Or1 (⟨[lft, snd], b(ϵ M )⟩)⇒ Mr′ Or1 (⟨q f , ϵ M ⟩)⇒ Mr′ Or1 (Success)In Example 5.4, there are leaves to the right of Success. On
the other hand, the output of Mr′ has no subtree to the right ofSuccess.
In Definition 5.5, the lookahead automaton was not explicitly given, to simplify the definition. In our implementation, weconstruct the lookahead automaton by constructing a top-downtree automaton from r0 and applying the subset construction to
the bottom-up tree automaton equivalent to the top-down tree
automaton. Let (P, Σ, h) be the lookahead tree automaton constructed in this manner and let us consider the following transition
rule.
x∈L(l::star)⟨l, x⟩ −→ Or1 (⟨l :: star, x⟩)
We then have the following transition rules for p ∈ P such thatl :: star ∈ p.
⟨l, x⟩ → Or1 (⟨l :: star, x⟩) ⟨p⟩
The top-down tree transducer with regular lookahead constructed from a regular expression r in Definition 5.5 simulates
regular expression matching based on backtracking and outputs atree that abstracts its execution steps. By then checking whether
Mr′ is of linear size increase, it can be decided whether the running time of the matching is linear with respect to the length of
the input string. Engelfriet and Maneth showed that it is decidable to check whether a total deterministic transducer is finite

7

Draft of a paper to appear in IPSJ-SIGPRO.

copying [7]. Although the construction of the transducer in thissection contains ϵ-transitions, there is exactly one possible transition for all states because of lookahead. This makes the transducer total and deterministic. We can therefore apply Theorem
4.9.

6. Implementation and Experimental Results
6.1 Implementation
Based on Sections 4 and 5, we implemented an analyzer ofregular expressions in OCaml. It consists of about 6, 000 lines
of code including empty lines and comments. It uses the parser
of Sakuma et al. [15], and supports the syntax of Perl-compatible
regular expressions, including the following extensions of regularexpressions.
r

::=
|
|
|
|
|

···
[c1 c2 . . . cn ]
r?
r∗?
r+
r{n}{m}(character class)(optional)(lazy repetition)(one or more repetitions)(repetition between n and m)

Lazy repetition r∗? matches a repetition of r for which a shorter
matching is given a higher priority. It is expanded as r∗? = ϵ|rr∗? .
Other extensions such as lookahead, atomic grouping, and backreference are not supported by our implementation. In our analyzer, a regular expression r not starting with ˆ, which matches
the start of a line, is treated as .∗? r and a regular expression r not
ending with $, which matches the end of a line, is treated as r.∗ .
If the top-down tree transducer with regular lookahead constructed from a regular expression r is of linear size increase, therunning time of matching for r is linear with respect to the lengthof the input string. Furthermore, if a tree transducer is finite copying, then the transducer is of linear size increase. It is therefore
sound to check the time linearity of regular expression matchingby checking whether the transducer is finite copying.
For top-down tree transducers with regular lookahead, finite
copying is a suﬃcient condition of linear size increase, but not anecessary condition, in general. To check whether a transducer
is of linear size increase, Engelfriet and Maneth [7] introduced asubclass of transducers called input proper. A transducer is input proper if any state of the transducer produces infinitely many
outputs. They showed that, for this subclass, linear size increase
implies finite copying and any transducer can be translated to an
equivalent input proper transducer. These give a decision procedure for linear size increase.
Because our implementation does not include the translationand only checks finite copying, it is not a sound and complete
checker. However, a transducer constructed from a regular expression must output either Or1 or Or2 when it reads a bounded
number of characters. Under these conditions, we believe thatlinear size increase implies finite copying and therefore that our
implementation is sound and complete without the translation. A
formal proof of this will be addressed in our future work.
In the following, we show how to check the time linearity of
regular expression matching in our implementation into more details. For the definitions of various subclasses of tree transducers,

Table 1 Subclasses of Tree Transducers
Subclass
LB−FS T
T R −FS T
QREL
LHOM

Description
Linear bottom-up tree transducers
Top-down tree transducers with regular lookahead
Finite state relabelingLinear homomorphism [16]please refer to [5], [6].
( 1 ) The top-down tree transducer Mr′ with regular lookahead isconstructed from a regular expression r using Definition 5.5.
( 2 ) If the state sequences obtained from its extension M̂r′ are finite, then Mr′ is finite copying.
We compose the two bottom-up tree transducers N of Theorem 4.9 and C below. By applying N, we obtain the state
sequences from τ Mr′ (w) for an input string w. The transducer
C normalizes trees on S T R(Σ) to compact trees. It is givenby ({qϵ , q}, S T R(Q), S T R(Q), {qϵ , q}, RC ) where Q is the setof states of Mr′ and RC has the following transition rules.
ϵS
σ

→
→

qϵ (ϵS )q(σ)•(qϵ (x1 ), qϵ (x2 ))•(qϵ (x1 ), q(x2 ))•(q(x1 ), qϵ (x2 ))•(q(x1 ), q(x2 ))

→
→
→
→

σ∈Q
qϵ (ϵS )q(x2 )q(x1 )
q(•(x1 , x2 ))For the class of linear bottom-up tree transducers LB−FS T ,LB−FS T ◦ LB−FS T ⊆ LB−FS T [5]. N ◦ C can therefore
be constructed as a linear bottom-up tree transducer.
If range(τN◦C ◦ τ M̂r′ ) is finite, then M̂r′ is finite copying. To
check the finiteness of range(τN◦C ◦ τ M̂r′ ), we compose N ◦ Cwith a bottom-up transducer P that nondeterministically outputs a path from the root to some leaf for a tree over S T R(Q).
P is given by ({q}, S T R(Q), MON(S T R(Q)), {q}, RP ) where
RP has the following transition rules.
σ•(q(x1 ), q(x2 ))•(q(x1 ), q(x2 ))→→→q(σ(ϵ M ))q(σ(x1 ))q(σ(x2 ))σ ∈ S T R(Q)(0)Since P is also linear, N ◦ C ◦ P can be constructed as alinear bottom-up transducer. We constructed this composedtransducer manually.
( 3 ) For the class T R −FS T of top-down tree transducers withregular lookahead, T R −FS T ◦ LB−FS T ⊆ T R −FS T [6].
With this result, we can construct M̂r′ ◦ N ◦C ◦ P as T R −FS T
as follows.
(a) By using LB−FS T ⊆ QREL ◦ LHOM [5], we decompose
N ◦ C ◦ P into two transducers Mqrel and Mlhom such that
Mqrel ◦ Mlhom = N ◦ C ◦ P.
(b) By using T R −FS T ◦ QREL ⊆ T R −FS T [6], we constructM̂r′ ◦ Mqrel as T R −FS T .
(c) By using T R −FS T ◦ LHOM ⊆ T R −FS T [6], we constructM̂r′ ◦ Mqrel ◦ Mlhom as T R −FS T .
( 4 ) We check whether range(τ Mr′ ) is finite as follows. M̂r′ ◦Mqrel ◦Mlhom is a tree transducer from and to trees representing
strings. It can therefore be converted into a transducer Twith regular lookahead over strings. It is then converted to a8

Draft of a paper to appear in IPSJ-SIGPRO.

string transducer without lookahead by the subset construction.
( 5 ) We construct an automaton A whose language isrange(τ M̂r′ ◦Mqrel ◦Mlhom ). If T has a transition from q to q′that consumes input w and produces output v, then A has acorresponding transition from q to q′ that consumes v. The
language of A is infinite if and only if there is a loop thatis reachable from the initial states and to some final state.
We therefore check the finiteness of range(τ M̂r′ ◦Mqrel ◦Mlhom ) byremoving states that are not reachable from the initial statesor to any final state and by checking for the existence ofa loop. If it is finite, Mr′ is finite copying and the running
time of matching for the regular expression r is therefore
determined to be linear with respect to the length of the
input.
6.2 Experimental Results
We conducted experiments that checked the time linearity ofmatching for regular expressions used in several existing programs. We applied our implementation to 393 regular expressions
used in five programs: PHP-Fusion, phpMyAdmin, SquirrelMail,
TorrentFlux, and XOOPS. We configured our implementation sothat it stops and reports a time-out if it cannot decide the linearity
within 900 seconds. Our implementation showed that 47 regular expressions had nonlinear running times and that 7 regularexpressions caused a time-out. Results for several regular expressions are shown in Table 2. It should be noted that the running
time for a regular expression that is decided as nonlinear might
actually be linear for real implementations of regular matching
because various optimizations might be applied. For example, although the tree corresponding to matching an with (aa∗ )∗ b has the
structure shown in Example 3.6 and its size is exponential in n,
its running time on Perl is linear.
In Table 2, r1 matches a string that consecutively has<!DOCTYPE, any number of non-alphanumerical characters, and
XHTML or HTML. Since \W is a character class that matches nonalphanumerical characters, \W* does not match <!DOCTYPE. The
running time of r1 is therefore linear.
r2 matches a string that is partitioned into six arbitrary substrings separated by /. After .* matches the whole input string,/ is located by backtracking. Because / is located in linear time
and the matching of r2 repeats it, its running time is linear. If wewere to remove ˆ, then a subexpression .*?.* would implicitly
appear. Its running time would be nonlinear.
r3 matches a substring that starts with </applet or </link,then has an arbitrary number of characters except >, and ends
with >. The matching of this regular expression has a nonlinear
running time for a string of the form </link</link. . .</link.
We have checked the running times using PCRE for strings that
contain n repetitions of </link. The running times were 0.26 s
for n = 10, 000, 1.0 s for n = 20, 000, and 4.1 s for n = 40, 000.
This confirms the nonlinearity of the running time.
r4 matches a substring comprising zero or one $ character, thentwo or more uppercase alphabetical characters, then zero or one$ character, and two or more numerical characters. The running
time of this regular expression is nonlinear for strings compris-

ing uppercase alphabetical characters. If we ignore [$]?, the expression starts with .*?[A-Z]+. The matching of this part thencauses nonlinear running time when the matching fails. We havechecked the running times using PCRE for strings that contain nrepetitions of A. The running times were 0.61 s for n = 5, 000,
3.3 s for n = 10, 000, and 14 s for n = 20, 000. This confirms thatthe running time is nonlinear.
r5 matches a string that contains BAD or NO. Because it does
not start with ˆ, it is treated as starting with .*?.*. It therefore
has nonlinear running time for strings containing neither BAD nor
NO. We have checked the running times for n repetitions of A.
Using PCRE, we obtained 0.23 s for n = 2, 000, 000, 0.46 s forn = 4, 000, 000s, and 0.92 s for n = 8, 000, 000. Using Python,
we obtained 1.9 s for n = 10, 000, 7.5 s for n = 20, 000, and 30
s for n = 40, 000. These results can be interpreted in terms of
PCRE applying some optimization to .*?.*.
r6
matchesasubstringthatstartswithcontent-transfer-encoding:, then has an arbitrary numberof space characters, and ends with a string comprising alphabetical characters and at most one -. This regular expression
contains many subexpressions of the form r∗ and the matching
was conducted with an option that makes it case-insensitive. The
tree transducer with regular lookahead constructed from r6 had
82 states and its lookahead automaton had 63 states. The numberof the states of a lookahead automaton has an exponential eﬀect
on the time to decide whether the transducer is finite copying.
This causes a time-out by exceeding the limit of 900 s.

7. Related Work
Kirrage et al. developed a method to check whether the running time of a regular expression matching is exponential [13].
They introduced a nondeterministic abstract machine that simulates regular expression matching. If there is a string that has two
diﬀerent sequences of matching steps for this abstract machine,
it is reported that the running time for the regular expression is
exponential. However, this method does not consider priorities
in matching, being based on the operational semantics that nondeterministically searches all the possibilities for matching. This
causes false-positives for regular expression matching based on
backtracking. For example, the running time for (.*a.*|a)*is reported as ‘exponential’ in their method even if it is actually
linear. In constrast, the present paper is based on the semantics
that precisely models priorities in regular expression matchingand does not cause such false-positives. For (.*a.*|a)*, it decides that it has a linear running time because any string containing more than one a is matched with .*a.*, causing the matchingof a on the right-hand side of | to always fail.
Pioneering work on the size of the output of a tree transducer
was done by Aho and Ullman [1]. They studied the size increasecaused by a generalized syntax-directed translation, which is avariant of a top-down tree transducer, and showed that it is decidable whether the size increase by the translation is O(ni ) fora nonnegative integer i, and whether it is exponential. The results of Engelfriet and Maneth [7] extend these results to macro
tree transducers for linear size increase. The tree transducer constructed from a regular expression in this paper intrinsically re-9Draft of a paper to appear in IPSJ-SIGPRO.

Table 2 Experimental Results
Regular expression
r1 =<!DOCTYPE\W*X?HTMLr2 =ˆ.*\/.*\/.*\/.*\/.*\/.*$
r3 =</*(applet|link|style|script|iframe|frame|frameset)[ˆ>]*>r4 =([$]?[A-Z]+)([$]?\d+)r5 =(.*)(BAD|NO)(.*)$
r6 =ˆ.*(content-transfer-encoding:)\s*(\w+-?(\w+)?).*

quires lookahead and it is therefore not possible to apply the results of Aho and Ullman to the transducer. However, we believethat it will be possible to extend their method to transducers withregular lookahead and to check their other properties related tosize increase.
For implementations of regular expression matching based on
the theory of automata, it has been considered diﬃcult to implement submatching that properly respects priorities in matching.
Recently, several methods that respect Perl-compatible priorities
have been proposed [3], [8], [9]. In particular, the regular expression library RE2 [11], which is based on automata, has attracted
much attention. However, we do not consider that all the issuesof regular expression matching have been solved in such implementations. For example, regular expressions in programming
languages include backreference that cannot be handled by thetheory of automata. In addition, it is common to use a fixed number of repetitions, defined as follows.
r

::=
|

···
rn

References
[1]
[2]

[3]
[4]

[6]

An implementation based on automata such as RE2 constructs anautomaton by unfolding the above repetition. It may therefore
construct an automaton whose size is exponential with respect tothe size of a regular expression. This blowup cannot be avoided
even if the implementation is based on NFA.

[7]

8. Conclusion

[10]
[11]

For regular expression matching based on backtracking, wehave developed a method to check whether the matching of agiven regular expression can be performed in linear time withrespect to the length of the input string. We construct a top-downtree transducer with regular lookahead from a regular expression.
For a given input string, this transducer outputs the tree that represents the execution steps matching the string with the regularexpression. It is then possible to check the time linearity of aregular expression by checking whether or not the constructedtransducer is of linear size increase.
A particular contribution of this paper is that we apply a theoretical result for tree transducers on linear size increase to a practical problem on regular expression matching. This problem is ofgreat interest in practice because the matching of a regular expression with nonlinear running time may cause DoS vulnerabilities
or pervert the behavior of matching for implementations with alimit on the number of execution steps.
Three issues should be addressed in future work. The first issue is to prove that linear size increase implies finite copying fora transducer constructed from a regular expression. We believethat this holds because the transducer must output some symbol

Running time
15.8 s757 s
373 s
1.30 s
0.970 s
900 swhen it reads boundedly many characters. The second issue is togenerate example inputs for a regular expression with nonlinear
running time. We would like to generate an example input thatshows nonlinear behavior by the regular expression. The third
issue involves about the construction of a tree transducer for aregular expression that includes r1∗ where ϵ ∈ L(r1 ). The naive
application of the method in this paper to such a regular expression causes nontermination by our decision procedure.

[5](fixed number of repetition)

Resultlinearlinearnonlinear
nonlinear
nonlineartime-out

[8]
[9]

[12]
[13]

[14]
[15]
[16]

Aho, A. V. and Ullman, J. D.: Translations on a Context-free Grammar, Inform. and Control, Vol. 19, pp. 439–475 (1971).
Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard,F., Lugiez, D., Tison, S. and Tommasi, M.: Tree Automata
Techniques and Applications, Available on: http://www.grappa.
univ-lille3.fr/tata (2007). release October, 12th 2007.
Cox, R.: Implementing Regular Expressions (2007). http://swtch.
com/˜rsc/regexp/.
Drewes, F. and Engelfriet, J.: Decidability of the Finiteness of Rangesof Tree Transductions, Inform. and Comput., Vol. 145, pp. 1–50
(1998).
Engelfriet, J.: Bottom-up and Top-down Tree Transformations - aComparison, Math. Syst. Theory, Vol. 9, pp. 198–231 (1975).
Engelfriet, J.: Top-down Tree Transducers with Regular Look-ahead,
Math. Syst. Theory, Vol. 10, pp. 289–303 (1977).
Engelfriet, J. and Maneth, S.: Macro Tree Translations of Linear Size
Increase are MSO Definable, SIAM J. Comput, Vol. 32, pp. 950–1006(2003).
Frisch, A. and Cardelli, L.: Greedy Regular Expression Matching,
ICALP 2004, pp. 618–629 (2004). LNCS 3142.
Haber, S., Horne, W., Manadhata, P., Mowbray, M. and Rao, P.: Efficient Submatch Extraction for Practical Regular Expressions, LATA,
pp. 323–343 (2013). LNCS 7810.
Hazel, P.: PCRE Man Page. http://www.pcre.org/pcre.txt.
Hosting, G. P.: re2: An Eﬃcient, Principled Regular Expression Library. http://code.google.com/p/re2/.
IHG:
Control.Monad.SearchTree.
http://hackage.
haskell.org/package/tree-monad-0.3/docs/
Control-Monad-SearchTree.html#t:SearchTree.
Kirrage, J., Rathnayake, A. and Thielecke, H.: Static Analysis forRegular Expression Denial-of-Service Attacks, International Conference on Network and System Security (NSS 2013), pp. 135–148(2013). LNCS 7873.
OWASP: Regular Expression Denial of Service - ReDoS (2012).
https://www.owasp.org/index.php/Regular_expression_
Denial_of_Service_-_ReDoS.
Sakuma, Y., Minamide, Y. and Voronkov, A.: Translating Regular Expression Matching into Transducers, Journal of Applied Logic,
Vol. 10, No. 1, pp. 32–41 (2012).
Thatcher, J. W.: Generalized2 Sequential Machine Maps, J. Comp.
Syst. Sci., Vol. 4, pp. 339–367 (1970).

10

Draft of a paper to appear in IPSJ-SIGPRO.

Satoshi Sugiyama received his B.Sc. degree in information science from University of Tsukuba in 2012. He is currently on the master course at Universityof Tsukuba. His research interests include
software verification and the theory of automata and formal languages.

Yasuhiko Minamide is an Associate
Professor in the Department of Computer Science, University of Tsukuba.
He received his M.Sc. and Ph.D. from
Kyoto University in 1993 and 1997. His
research interests include the theory of
programming languages and software
verification. He is a member of ACM,
IPSJ, and JSSST.

11