Opinion of SUSE security about O(n^2) worst case in POWER string ops?

[Rich Felker]

On Fri, Jul 24, 2015 at 09:34:26PM +0000, Joseph Myers wrote:
> On Fri, 24 Jul 2015, Rich Felker wrote:
> 
> > On Fri, Jul 24, 2015 at 11:52:18AM -0500, Segher Boessenkool wrote:
> > > On Fri, Jul 24, 2015 at 03:04:20PM +0000, Joseph Myers wrote:
> > > > Note that it is not clear if we do have O(n^2) worst case, or O(2048n) = 
> > > > O(n).  The claim of O(n^2) if m <= 2048 in 
> > > > <https://sourceware.org/ml/libc-alpha/2015-07/msg00752.html> seems rather 
> > > > odd to me.
> > > 
> > > I have looked at the code and I don't see it either, it is just O(mn).
> > 
> > O(n^2) was just sloppy language for "quadratic", whereas the real
> > quadratic-time for naive strstr algorithms is O(mn). It's still
> > quadratic, but in 2 variables rather than one.
> 
> And if it's only O(mn) for bounded m, that's linear and not a problem 
> (although preferably the threshold should be determined based on 
> benchmarking).

In general both n and m could be under user/attacker control, though
there are certainly classes of problems where only one is. But even if
m is bounded, C*m*n operations can be problematic in comparison to
optimized approaches to strstr which have C*n/m operations in typical
cases.

Rich