CodeQL library for JavaScript
Search

Module SuperlinearBackTracking

Provides classes for working with regular expressions that can perform backtracking in superlinear time.

Import path

import semmle.javascript.security.performance.SuperlinearBackTracking

Imports

ReDoSUtil

Provides classes for working with regular expressions that can perform backtracking in superlinear/exponential time.

Predicates

concretise

Gets a string corresponding to the trace t.

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.

isReachableFromStartTuple

Holds if there exists a pair of repetitions (pivot, succ) in the regular expression such that: tuple is reachable from (pivot, pivot, succ) in the product automaton, and there is a distance of dist from tuple to the nearest end-tuple (pivot, succ, succ), and a path from a start-state to tuple follows the transitions in trace.

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.

polynimalReDoS

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 withs1,s2, ands3`, 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.

SuperLinearReDoSConfiguration

An instantiaion of ReDoSConfiguration for superlinear ReDoS.

Trace

A list of tuples of input symbols that describe a path in the product automaton starting from some start state.