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