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

Predicate Make::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.

From theorem 3 in the paper linked in the top of this file we can therefore conclude that the regular expression has polynomial backtracking - if a rejecting suffix exists.

This predicate is used by SuperLinearReDoSConfiguration, and the final results are available in the hasReDoSResult predicate.

Import path

import codeql.regex.nfa.SuperlinearBackTracking
predicate isPumpable(State pivot, State pumpEnd, string pump)