glibc qsort() Out-Of-Bounds Read / Write

`  
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).  
  
  
`