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`.
getEndTuple	Gets the tuple `(pivot, pumpEnd, pumpEnd)` from the product automaton.
getReasonString	Gets a message for why `term` can cause polynomial backtracking.
getStartTuple	Gets the tuple `(pivot, pivot, pumpEnd)` from the product automaton.
hasCommonStep	Holds if there are transitions from the components of `q` to `r1`, `r2`, and `r3 labelled with`s1`,`s2`, and`s3`, respectively. Where`s1`,`s2`, and`s3` all share at least one character.
isEndTuple	Holds if `tuple` is an end state in our search, and `tuple` is on a path from a start state to an end state. That means there exists a pair of loops `(pivot, pumpEnd)` such that `tuple = (pivot, pumpEnd, pumpEnd)`.
isPumpable	Holds if matching repetitions of `pump` can: 1) Transition from `pivot` back to `pivot`. 2) Transition from `pivot` to `pumpEnd`. 3) Transition from `pumpEnd` to `pumpEnd`.
isReDoSCandidate	Holds if states starting in `state` can have polynomial backtracking with the string `pump`.
isStartLoops	Holds if `pivot` and `pumpEnd` 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.
tupleDeltaBackwards	Holds if there exists a transition from `src` to `dst` in the product automaton. Where `src` and `dst` are both on a path from a start state to an end state. 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 `(q1, q2, q3)` in the product automaton, that is reachable from `(pivot, pivot, pumpEnd)`.
Trace	A list of tuples of input symbols that describe a path in the product automaton starting from a start state `(pivot, pivot, pumpEnd)`.

Parameters

TreeImpl

RegexTreeViewSig