New GNU C Library (glibc) security flaw reported on 30 Jan 2024

[Vincent Lefevre]

On 2024-01-31 12:52:35 -0300, Adhemerval Zanella Netto wrote:
> On 31/01/24 11:55, Vincent Lefevre wrote:
[...]
> > This is what the ISO C standard says. But the glibc manual explicitly
> > allows non-transitive comparators.
> > 
> > See the example in 9.1 Defining the Comparison Function:
> > 
> >    Here is an example of a comparison function which works with an array
> > of numbers of type ‘double’:
> > 
> >      int
> >      compare_doubles (const void *a, const void *b)
> >      {
> >        const double *da = (const double *) a;
> >        const double *db = (const double *) b;
> > 
> >        return (*da > *db) - (*da < *db);
> >      }
> > 
> > The non-transitivity can be demonstrated with the following test
> > program:
> > 
> > #include <stdio.h>
> > #include <math.h>
> > 
> > int
> > compare_doubles (const void *a, const void *b)
> > {
> >   const double *da = (const double *) a;
> >   const double *db = (const double *) b;
> > 
> >   return (*da > *db) - (*da < *db);
> > }
> > 
> > int main (void)
> > {
> >   double t[3] = { 1.0, NAN, 2.0 };
> >   printf ("%d\n", compare_doubles(t+0, t+1));
> >   printf ("%d\n", compare_doubles(t+1, t+2));
> >   printf ("%d\n", compare_doubles(t+0, t+2));
> >   return 0;
> > }
> > 
> > which gives
> > 
> > 0
> > 0
> > -1
> > 
> > while the initial 0 0 implies a third 0 with a transitive comparator.
> 
> I see this is an manual issue rather than a GNU 'extension' to qsort semantic.
> And I think we should fix BZ#31322 by using a transitive comparison instead of
> trying to support such cases.

If this was intentional, users may already use such a nontransitive
comparison function. If this was not intentional, this shows that
the problem is not obvious and that users less experienced than the
glibc developers may fall in such a trap. So, in addition to make
the glibc manual clear on the subject, I think that the library
should handle such cases gracefully rather than considering that
such cases will never occur. For instance, this could be just an
indeterminate ordering. Or if the goal is to warn the user about
the issue (in case it is detected), an assertion failure instead
of indeterminate ordering.

-- 
Vincent Lefèvre <vincent@vinc17.net> - Web: <https://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <https://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)