Qualys Security Advisory
For the algorithm lovers: Nontransitive comparison functions lead to
out-of-bounds read & write in glibc's qsort()
========================================================================
Contents
========================================================================
Summary
Background
Experiments
Analysis
Patch
Discussion
Acknowledgments
Timeline
    CUT MY LIST IN TWO PIECES
    THAT'S HOW YOU START QUICK SORT
        -- https://twitter.com/QuinnyPig/status/1710447650112438710
========================================================================
Summary
========================================================================
We discovered a memory corruption in the glibc's qsort() function, due
to a missing bounds check. To be vulnerable, a program must call qsort()
with a nontransitive comparison function (a function cmp(int a, int b)
that returns (a - b), for example) and with a large number of attacker-
controlled elements (to cause a malloc() failure inside qsort()). We
have not tried to find such a vulnerable program in the real world.
All glibc versions from at least September 1992 (glibc 1.04) to the
current release (glibc 2.38) are affected, but the glibc's developers
have independently discovered and patched this memory corruption in the
master branch (commit b9390ba, "stdlib: Fix array bounds protection in
insertion sort phase of qsort") during a recent refactoring of qsort().
About our advisory, the glibc security team issues the following
statement:
------------------------------------------------------------------------
This memory corruption in the GNU C Library through the qsort function is
invoked by an application passing a non-transitive comparison function, which
is undefined according to POSIX and ISO C standards.  As a result, we are of
the opinion that the resulting CVE, if any, should be assigned to any such
calling applications and subsequently fixed by passing a valid comparison
function to qsort and not to glibc.  We however acknowledge that this is a
quality of implementation issue and we fixed this in a recent refactor of
qsort.  We would like to thank Qualys for sharing their findings and helping
us validate our recent changes to qsort.
------------------------------------------------------------------------
========================================================================
Background
========================================================================
While browsing through Postfix's HISTORY file, we stumbled across a
puzzling entry from February 2002:
------------------------------------------------------------------------
        Bugfix: make all recipient comparisons transitive, because
        Solaris qsort() causes SIGSEGV errors otherwise. Victor
        Duchovni, Morgan Stanley. File: *qmgr/qmgr_message.c.
------------------------------------------------------------------------
Segmentation faults in qsort()? Transitive comparison functions?
As explained in the manual page for qsort(), "The comparison function
must return an integer less than, equal to, or greater than zero if the
first argument is considered to be respectively less than, equal to, or
greater than the second." Of course, such a comparison function cmp()
must be transitive:
- if a < b (i.e., if cmp(pointer_to(a), pointer_to(b)) < 0);
- and if b < c (i.e., if cmp(pointer_to(b), pointer_to(c)) < 0);
- then necessarily a < c (i.e., cmp(pointer_to(a), pointer_to(c)) < 0).
For example, the following comparison function (which compares integers)
is transitive (and perfectly correct):
------------------------------------------------------------------------
int
cmp(const void * const pa, const void * const pb)
{
    const int a = *(const int *)pa;
    const int b = *(const int *)pb;
    if (a > b) return +1;
    if (a < b) return -1;
    return 0;
}
------------------------------------------------------------------------
A shorter and more efficient version of this comparison function could
simply "return (a > b) - (a < b);" and still be transitive and perfectly
correct:
- if a > b, it returns 1 - 0 = +1;
- if a < b, it returns 0 - 1 = -1;
- if a = b, it returns 0 - 0 = 0.
The question, then, is: how can a comparison function be nontransitive?
A comparison function cmp() is nontransitive if there exist a, b, and c
such that:
- a < b (because cmp(pointer_to(a), pointer_to(b)) < 0);
- b < c (because cmp(pointer_to(b), pointer_to(c)) < 0);
- but a >= c (because cmp(pointer_to(a), pointer_to(c)) >= 0 by
  mistake).
Although the following comparison function seems correct at first, it is
in fact nontransitive, because the subtraction in "return (a - b);" is
prone to integer overflows:
------------------------------------------------------------------------
int
cmp(const void * const pa, const void * const pb)
{
    const int a = *(const int *)pa;
    const int b = *(const int *)pb;
    return (a - b);
}
------------------------------------------------------------------------
For example, if a = INT_MIN, b = 0, and c = INT_MAX, then:
- a < b (because cmp(pointer_to(a), pointer_to(b)) returns INT_MIN - 0,
  which is correctly negative);
- b < c (because cmp(pointer_to(b), pointer_to(c)) returns 0 - INT_MAX,
  which is also correctly negative);
- but a > c by mistake (because cmp(pointer_to(a), pointer_to(c))
  returns INT_MIN - INT_MAX = +1, which is incorrectly positive because
  this subtraction overflows).
Unfortunately, such nontransitive comparison functions are extremely
common, as discussed in this excellent blog post from Ted Unangst:
  https://flak.tedunangst.com/post/subtraction-is-not-comparison
and as hinted at in OpenBSD's manual page for qsort(): "It is almost
always an error to use subtraction to compute the return value of the
comparison function."
Fortunately, when passed to a robust qsort() implementation, these
nontransitive comparison functions should (at the worst) result in an
incorrectly sorted array; certainly not in a memory corruption. However,
the aforementioned entry from Postfix's HISTORY file suggests that not
all qsort() implementations are robust.
========================================================================
Experiments
========================================================================
We therefore decided to assess the robustness of the glibc's qsort()
implementation, by calling it with a nontransitive comparison function:
------------------------------------------------------------------------
  1 #include <limits.h>
  2 #include <stdlib.h>
  3 #include <sys/time.h>
  4 
  5 static int
  6 cmp(const void * const pa, const void * const pb)
  7 {
  8     const int a = *(const int *)pa;
  9     const int b = *(const int *)pb;
 10     return (a - b);
 11 }
 12 
 13 int
 14 main(const int argc, const char * const argv[])
 15 {
 16     if (argc != 2) return __LINE__;
 17     const size_t nmemb = strtoul(argv[1], NULL, 0);
 18     if (nmemb <= 0 || nmemb >= (1<<28)) return __LINE__;
 19 
 20     int * const pcanary1 = calloc(1 + nmemb + 1, sizeof(int));
 21     if (!pcanary1) return __LINE__;
 22     int * const array = pcanary1 + 1;
 23     int * const pcanary2 = array + nmemb;
 24 
 25     struct timeval tv;
 26     if (gettimeofday(&tv, NULL)) return __LINE__;
 27     srandom((tv.tv_sec << 16) ^ tv.tv_usec);
 28 
 29     const int canary1 = *pcanary1 = (random() << 16) ^ random();
 30     const int canary2 = *pcanary2 = (random() << 16) ^ random();
 31     array[random() % nmemb] = INT_MIN;
 32 
 33     qsort(array, nmemb, sizeof(int), cmp);
 34     if (*pcanary1 != canary1) abort();
 35     if (*pcanary2 != canary2) abort();
 36     return 0;
 37 }
------------------------------------------------------------------------
- at lines 5-11, cmp() is the nontransitive comparison function
  introduced in the previous "Background" section;
- at lines 16-18, the number of elements to be sorted (simple integers)
  is read from the command line;
- at lines 20-23, the array of elements to be sorted is calloc()ated,
  along with a canary element below this array, and a canary element
  above this array;
- at lines 29-30, these two canary elements are randomized, and copied
  to the stack for later comparison;
- at line 31, one random element of the array is initialized to INT_MIN
  (all other elements are initialized to 0 by calloc());
- at line 33, the elements of this array are sorted by qsort();
- at lines 34-35, the two canary elements (below and above the sorted
  array) are checked against their stack copies, and if they differ (an
  out-of-bounds write in qsort()), abort() is called.
We chose the array elements a = INT_MIN and b = 0 because they directly
exhibit the problematic behavior of this cmp() function:
- a < b, because cmp(pointer_to(a), pointer_to(b)) returns INT_MIN - 0,
  which is correctly negative;
- but b < a by mistake, because cmp(pointer_to(b), pointer_to(a))
  returns 0 - INT_MIN = INT_MIN (the "Leblancian Paradox"), which is
  incorrectly negative (because this subtraction overflows).
We then executed our test program in a loop, on Fedora 39 (which uses
the latest glibc version, 2.38):
------------------------------------------------------------------------
$ while true; do n=$((RANDOM*64+RANDOM+1)); ./qsort $n; done
------------------------------------------------------------------------
Unsurprisingly, nothing happened: our program did not crash or abort().
While this loop was still running (and not crashing), we started to read
the glibc's qsort() implementation; to our great surprise, we discovered
that the glibc's qsort() is not, in fact, a quick sort by default, but a
merge sort (in stdlib/msort.c).
Most likely, merge sort was chosen over quick sort to avoid quick sort's
worst-case performance, which is O(n^2); on the other hand, merge sort's
worst-case performance is O(n*log(n)). But merge sort suffers from one
major drawback: it does not sort in-place -- it malloc()ates a copy of
the array of elements to be sorted. As a result, if this array is very
large (lines 212-217), or if this malloc() fails (lines 219-229), then
the glibc's qsort() falls back to a quick sort (in stdlib/qsort.c),
because quick sort does sort in-place:
------------------------------------------------------------------------
163 void
164 __qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
165 {
166   size_t size = n * s;
...
170   /* For large object sizes use indirect sorting.  */
171   if (s > 32)
172     size = 2 * n * sizeof (void *) + s;
173 
174   if (size < 1024)
175     /* The temporary array is small, so put it on the stack.  */
176     p.t = __alloca (size);
177   else
178     {
...
212       /* If the memory requirements are too high don't allocate memory.  */
213       if (size / pagesize > (size_t) phys_pages)
214         {
215           _quicksort (b, n, s, cmp, arg);
216           return;
217         }
218 
219       /* It's somewhat large, so malloc it.  */
220       int save = errno;
221       tmp = malloc (size);
222       __set_errno (save);
223       if (tmp == NULL)
224         {
225           /* Couldn't get space, so use the slower algorithm
226              that doesn't need a temporary array.  */
227           _quicksort (b, n, s, cmp, arg);
228           return;
229         }
230       p.t = tmp;
231     }
...
299 }
------------------------------------------------------------------------
We therefore decided to assess the robustness of the glibc's quick sort
(instead of its merge sort, which was clearly not crashing), by forcing
qsort() to call _quicksort(). Locally, forcing the malloc() at line 221
to fail is very easy: we simply execute our program with a low RLIMIT_AS
("The maximum size of the process's virtual memory", man setrlimit); and
this works even when executing a SUID-root program. So we executed our
program in the following loop instead:
------------------------------------------------------------------------
$ while true; do n=$((RANDOM*64+RANDOM+1)); prlimit --as=$((n*4/2*3)) ./qsort $n; done
Aborted (core dumped)
Aborted (core dumped)
Aborted (core dumped)
...
------------------------------------------------------------------------
Incredibly, we almost immediately observed crashes of our test program:
calls to abort(), because one of our canary elements (below or above the
sorted array) was overwritten (i.e., an out-of-bounds write in qsort()).
To understand these crashes, we examined one of them in gdb:
------------------------------------------------------------------------
$ gdb prlimit
(gdb) run --as=8104854 ./qsort 1350809
Starting program: /usr/bin/prlimit --as=8104854 ./qsort 1350809
...
Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
44            return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;
(gdb) backtrace
#0  __pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
#1  0x00007ffff7e698a3 in __pthread_kill_internal (signo=6, threadid=<optimized out>) at pthread_kill.c:78
#2  0x00007ffff7e178ee in __GI_raise (sig=sig@entry=6) at ../sysdeps/posix/raise.c:26
#3  0x00007ffff7dff8ff in __GI_abort () at abort.c:79
#4  0x0000555555555334 in main (argc=2, argv=0x7fffffffe338) at qsort.c:34
(gdb) select-frame 4
(gdb) p/x canary1
$1 = 0xc6109e4c
(gdb) p/x *pcanary1
$2 = 0x0
(gdb) x/xw pcanary1 - 2
0x7ffff78af008: 0x00528002
0x7ffff78af00c: 0x80000000
0x7ffff78af010: 0x00000000
0x7ffff78af014: 0xc6109e4c
0x7ffff78af018: 0x00000000
------------------------------------------------------------------------
- at address 0x7ffff78af010 (pcanary1), the original value of the canary
  (0xc6109e4c) was overwritten with 0x0 -- an out-of-bounds write;
- at address 0x7ffff78af00c (below pcanary1), the most significant word
  of an mchunk_size (heap metadata) was overwritten with 0x80000000
  (INT_MIN) -- another out-of-bounds write;
- at address 0x7ffff78af014 (above pcanary1), the first element of the
  array was overwritten with 0xc6109e4c (the original value of the
  canary), which was therefore read out-of-bounds beforehand (from
  pcanary1).
========================================================================
Analysis
========================================================================
To identify the root cause of these out-of-bounds memory accesses, we
must analyze the implementation of the glibc's quick sort:
------------------------------------------------------------------------
 87 void
 88 _quicksort (void *const pbase, size_t total_elems, size_t size,
 89             __compar_d_fn_t cmp, void *arg)
 90 {
 91   char *base_ptr = (char *) pbase;
...
108       while (STACK_NOT_EMPTY)
109         {
...
193         }
...
206     char *tmp_ptr = base_ptr;
...
214     for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
215       if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
216         tmp_ptr = run_ptr;
217 
218     if (tmp_ptr != base_ptr)
219       SWAP (tmp_ptr, base_ptr, size);
...
223     run_ptr = base_ptr + size;
224     while ((run_ptr += size) <= end_ptr)
225       {
226         tmp_ptr = run_ptr - size;
227         while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
228           tmp_ptr -= size;
...
246       }
...
248 }
------------------------------------------------------------------------
- at lines 108-193, when quick sort's partitions become smaller than
  MAX_THRESH (4 elements), _quicksort() switches to a final insertion
  sort (at lines 206-246), which is faster than quick sort for small or
  mostly sorted arrays;
- at lines 206-219, this insertion sort makes sure that the very first
  element of the array (base_ptr) is the smallest element of the array;
- at lines 226-228, this first element acts as a natural barrier that
  prevents tmp_ptr from being decremented below the array (because if
  tmp_ptr reaches base_ptr, then necessarily cmp(run_ptr, tmp_ptr) >= 0
  because tmp_ptr is base_ptr, the smallest element of the array);
- unfortunately this does not hold true if cmp() is nontransitive, in
  which case cmp(run_ptr, tmp_ptr) can be < 0 even if tmp_ptr is
  base_ptr, so tmp_ptr can be decremented below the array, where
  out-of-bounds elements are read and overwritten.
========================================================================
Patch
========================================================================
To patch these out-of-bounds memory accesses in _quicksort(), a simple
check "tmp_ptr > base_ptr &&" can be added in front of the cmp() call at
line 227 (of course this does not magically result in a correctly sorted
array if cmp() is nontransitive, but at least it does not result in a
memory corruption anymore).
In fact, while drafting this advisory, we discovered that such a check
("tmp_ptr != base_ptr &&") has already been added to the glibc's master
branch (which will become glibc 2.39 in February 2024), by the following
commit ("stdlib: Fix array bounds protection in insertion sort phase of
qsort"):
  https://sourceware.org/git?p=glibc.git;a=commit;h=b9390ba93676c4b1e87e218af5e7e4bb596312ac
Indeed, the glibc developers have recently refactored qsort() and
replaced the merge sort (and its fallback to quick sort) with an
introspective sort (a combination of quick sort, heap sort, and
insertion sort):
  https://en.wikipedia.org/wiki/Introsort
  https://sourceware.org/pipermail/libc-alpha/2023-October/151907.html
During this refactoring, the glibc developers have proactively
discovered (and patched) the out-of-bounds memory accesses in the
insertion sort (probably because these out-of-bounds memory accesses
became directly exposed to the misbehavior of nontransitive comparison
functions, instead of being safely hidden behind a malloc() failure in
the merge sort).
Last-minute note: in January 2024, the glibc developers have reverted
this refactoring of qsort(), back to the original merge sort, plus a
fallback to heap sort instead of quick sort; for more information:
  https://sourceware.org/pipermail/libc-alpha/2024-January/154051.html
========================================================================
Discussion
========================================================================
We have not tried to find a vulnerable program (i.e., a program that
uses a nontransitive comparison function to qsort() attacker-controlled
elements); however, vulnerable programs are certain to exist in the real
world:
- calls to qsort() are extremely common;
- nontransitive comparison functions are also common;
- all glibc versions from at least September 1992 (glibc 1.04, the first
  version that we could find online) to the current release (glibc 2.38)
  are affected by this memory corruption.
Locally, forcing a malloc() failure in qsort() (which is necessary to
reach the memory corruption) is easy: either execute the target program
(e.g., a SUID-root program) with a low RLIMIT_AS, or allocate a large
amount of memory with another program on the same machine.
Remotely, forcing this malloc() failure is harder: either allocate a
large amount of memory (e.g., a memory leak) in the network service that
is being targeted, or in another network service on the same machine.
========================================================================
Acknowledgments
========================================================================
We thank the glibc security team and the linux-distros@openwall.
========================================================================
Timeline
========================================================================
2023-12-12: We sent a draft of our advisory to the glibc security team.
They immediately acknowledged receipt of our email.
2023-12-19: The glibc security team decided to not treat this memory
corruption in qsort() as a vulnerability in the glibc itself, as
explained in the "Summary" of our advisory.
2024-01-16: We backported commit b9390ba to all current and past stable
versions of the glibc, and sent this patch and a draft of our advisory
to the linux-distros@openwall (to piggyback on the glibc embargo for
CVE-2023-6246). They immediately acknowledged receipt of our email.
2024-01-30: Coordinated Release Date (18:00 UTC).