Shorthand style property handlers (FontHandler and roughly a dozen
siblings) tokenize a CSS value and feed it to css.recursiveCheck,
which searches for a way to partition the tokens so every group is
accepted by one of a handful of validator functions. The search was
unmemoized: every recursive call is made on a suffix of the token
slice, and the same suffix was re-explored once per partition path
that reached it. For values with several tokens that more than one
validator accepts on their own (e.g. runs of whitespace, which
FontFamilyHandler treats as a valid empty entry), the number of such
paths grows combinatorially with the number of tokens, making
wall-clock cost roughly double per extra token. A short,
attacker-controlled style value can hang a server sanitizing
untrusted HTML.
Memoize recursiveCheck on the length of the remaining token suffix:
distinct suffixes of a given slice always have distinct lengths, and
the outcome for a suffix depends only on its length within one
top-level call (the validator set is constant throughout), so this
caches each of at most len(value) distinct subproblems exactly once.
This does not change any validator's behavior or which values are
accepted or rejected, only how many times each subproblem is solved,
turning the exponential search into a polynomial one.
Closes#225
dualfroz
eb1d9c9bec