Predicate isStartLoops
Holds if pivot
and succ
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 != succ
.
The case where pivot = succ
causes exponential backtracking and is handled by the js/redos
query.
Import path
import semmle.javascript.security.performance.SuperlinearBackTracking
predicate isStartLoops(State pivot, State succ)