  Regular expression matching using backtracking can have exponential runtime,
leading to an algorithmic complexity attack known as REDoS in the systems
security literature. In this paper, we build on a recently published static
analysis that detects whether a given regular expression can have exponential
runtime for some inputs. We systematically construct a more accurate analysis
by forming powers and products of transition relations and thereby reducing the
REDoS problem to reachability. The correctness of the analysis is proved using
a substructural calculus of search trees, where the branching of the tree
causing exponential blowup is characterized as a form of non-linearity.
