Re: [PATCH v3] powerpc: strstr optimization

[Joseph Myers <joseph at codesourcery dot com>]

On Wed, 22 Jul 2015, Tulio Magno Quites Machado Filho wrote:

> >> If there's a quadratic worst case newly introduced for 2.22, I'd consider 
> >> that a security hole (denial of service) that needs to block the release 
> >> of 2.22 until it's fixed (possibly by removing the implementation in 
> >> question).
> 
> Could you elaborate why a quadratic worst case in a string function can be
> considered a denial of service, please?

Because code may use strstr on untrusted inputs, meaning small inputs 
(e.g. MB in size) cause large (effectively infinite) CPU usage - any case 
where an attacker can cause your resource usage to grow more than linearly 
with their usage is a denial-of-service problem.  Thus gnulib considers 
such strstr implementations buggy and disables them (so preventing any of 
your optimizations from being effective for any program using gnulib), but 
not everything uses gnulib.

(There are cases, e.g. untrusted regular expressions, where glibc can't 
reasonably avoid such resource usage, and so anyone using untrusted 
regular expressions must apply resource limits externally.  But strstr 
isn't such a case.)

> > Tulio,
> >
> > Could you please review the possibility of quadratic behaviour and respond
> > prompty? I don't want this to hold up the release.
> 
> I confirm this algorithm does have a quadratic worst case, which appears if
> needle <= 2048.
> If the needle > 2048, it falls back to the previous implementation.

strstr should be O(m+n) (for needle length m, haystack length n); a naive 
implementation could be O(mn).  Are you saying that, for constant m <= 
2048, it's O(n^2)?  Because O(mn) for bounded m is fine (the threshold 
2048 would preferably have been determined by some sort of benchmark, but 
the precise choice of threshold isn't something to block a release).

-- 
Joseph S. Myers
joseph@codesourcery.com