CodeQL library for Java/Kotlin
codeql/java-all 0.9.1 (changelog, source)
Search

Predicate Make::isStartLoops

Holds if pivot and pumpEnd are a pair of loops that could be the beginning of a quadratic blowup.

There is a slight implementation difference compared to the paper: this predicate requires that pivot != pumpEnd. The case where pivot = pumpEnd causes exponential backtracking and is handled by the js/redos query.

Import path

import codeql.regex.nfa.SuperlinearBackTracking
predicate isStartLoops(State pivot, State pumpEnd)