This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: Opinion of SUSE security about O(n^2) worst case in POWER string ops?
- From: Rich Felker <dalias at libc dot org>
- To: Joseph Myers <joseph at codesourcery dot com>
- Cc: Segher Boessenkool <segher at kernel dot crashing dot org>, Carlos O'Donell <carlos at redhat dot com>, Andreas Schwab <schwab at suse dot de>, Mel Gorman <mgorman at suse dot de>, GNU C Library <libc-alpha at sourceware dot org>
- Date: Fri, 24 Jul 2015 18:25:09 -0400
- Subject: Re: Opinion of SUSE security about O(n^2) worst case in POWER string ops?
- Authentication-results: sourceware.org; auth=none
- References: <55B14DE5 dot 2000209 at redhat dot com> <alpine dot DEB dot 2 dot 10 dot 1507241502560 dot 5465 at digraph dot polyomino dot org dot uk> <20150724165218 dot GA32019 at gate dot crashing dot org> <20150724175557 dot GC16376 at brightrain dot aerifal dot cx> <alpine dot DEB dot 2 dot 10 dot 1507242133290 dot 773 at digraph dot polyomino dot org dot uk>
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