CodeQL library for Python
codeql/python-all 2.2.0 (changelog, source)
Search

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, pumpEnd, pumpEnd) 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, 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.

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.

Trace

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

Parameters