Re: glibc qsort() vulnerability

On Tue, Feb 13, 2024 at 12:41 AM Andres Freund <andres(at)anarazel(dot)de> wrote:

> Hi,
>
> On 2024-02-12 17:04:23 -0600, Nathan Bossart wrote:
> > On Mon, Feb 12, 2024 at 01:31:30PM -0800, Andres Freund wrote:
> > > One thing that's worth checking is if this ends up with *worse* code
> when the
> > > comparators are inlined. I think none of the changed comparators will
> end up
> > > getting used with an inlined sort, but ...
> >
> > Yeah, AFAICT the only inlined sorts are in tuplesort.c and bufmgr.c, and
> > the patches don't touch those files.
> >
> > > The reason we could end up with worse code is that when inlining the
> > > comparisons would make less sense for the compiler. Consider e.g.
> > > return DO_COMPARE(a, b) < 0 ?
> > > (DO_COMPARE(b, c) < 0 ? b : (DO_COMPARE(a, c) < 0 ? c : a))
> > > : (DO_COMPARE(b, c) > 0 ? b : (DO_COMPARE(a, c) < 0 ? a :
> c));
> > >
> > > With a naive implementation the compiler will understand it only cares
> about
> > > a < b, not about the other possibilities. I'm not sure that's still
> true with
> > > the more complicated optimized version.
> >
> > You aren't kidding [0]. Besides perhaps adding a comment in
> > sort_template.h, is there anything else you think we should do about this
> > now?
>
> I'd add also a comment to the new functions. I think it's fine otherwise. I
> wish there were formulation that'd be optimal for both cases, but this way
> we
> can at least adapt all places at once if either find a better formulation
> or
> change all our sorts to happen via an inline implementation of qsort or
> such.
>

I suspect that this has to do with the fact that we "abuse" the type system
by performing arithmetics on booleans converted to integers and the
compilers do not have rules for dealing with these.

For example, with the inline function "static inline cmp(a,b) { return a <
b ? -1 : a > b ? 1 : 0; }"

Which trivially can be rewritten by the compiler using very basic rules, as
follows:

DO_COMPARE(a,b)
(a < b ? -1 : a > b ? 1 : 0) < 0
a < b ? (-1 < 0) : a > b ? (1 < 0) : (0 < 0)
a < b ? true : a > b ? false : false
a < b ? true : a > b ? false : false
a < b ? true : false
a < b

When it comes to (a < b) - (a > b) there are no such rules added since it
is not a very common case.

Clang fares better for this case and at least shows the two alternatives as
equal.

Maybe we should change to use the original version equivalent to the inline
function above since that works better with surrounding code?

Best wishes,
Mats Kindahl

>
> Greetings,
>
> Andres
>