For other CodeQL resources, including tutorials and examples, see the CodeQL documentation

Make

Module SuperlinearBackTracking

Modules

Module Make

A parameterized module implementing the analysis described in the above papers.

Import path


                                import codeql.regex.nfa.SuperlinearBackTracking

Imports

Make<SuperlinearBackTracking::Make::TreeImpl>

Classes and predicates that create an NFA and various algorithms for working with it.

Predicates

delta	Gets a state for which there exists a transition in the NFA from `s’.
distBackFromEnd	Gets the minimum length of a path from `r` to some an end state `end`.
getAThreewayIntersect	Gets a char that is matched by all the edges `s1`, `s2`, and `s3`.
getAnEndTuple	Gets the tuple `(pivot, succ, succ)` from the product automaton.
getReasonString	Gets a message for why `term` can cause polynomial backtracking.
isEndTuple	Holds if `tuple` is an end state in our search. That means there exists a pair of loops `(pivot, succ)` such that `tuple = (pivot, succ, succ)`.
isPumpable	Holds if matching repetitions of `pump` can: 1) Transition from `pivot` back to `pivot`. 2) Transition from `pivot` to `succ`. 3) Transition from `succ` to `succ`.
isReDoSCandidate	Holds if states starting in `state` can have polynomial backtracking with the string `pump`.
isStartLoops	Holds if `pivot` and `succ` are a pair of loops that could be the beginning of a quadratic blowup.
minAndMaxIntersect	Gets the minimum and maximum characters that intersect between `a` and `b`. This predicate is used to limit the size of `getAThreewayIntersect`.
polynomialReDoS	Holds if repetitions of `pump` at `t` will cause polynomial backtracking.
step	Holds if there are transitions from the components of `q` to the corresponding components of `r` labelled with `s1`, `s2`, and `s3`, respectively.
step	Holds if there are transitions from the components of `q` to `r1`, `r2`, and `r3 labelled with`s1`,`s2`, and`s3`, respectively.
tupleDeltaBackwards	Holds if there exists a transition from `r` to `q` in the product automaton. Notice that the arguments are flipped, and thus the direction is backwards.

Classes

PolynomialBackTrackingTerm	A term that may cause a regular expression engine to perform a polynomial number of match attempts, relative to the input length.
StateTuple	A state in the product automaton. The product automaton contains 3-tuples of states.
Trace	A list of tuples of input symbols that describe a path in the product automaton starting from some start state.

Parameters

TreeImpl

RegexTreeViewSig