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

Qualys Security AdvisoryFor the algorithm lovers: Nontransitive comparison functions lead toout-of-bounds read & write in glibc's qsort()========================================================================Contents========================================================================SummaryBackgroundExperimentsAnalysisPatchDiscussionAcknowledgmentsTimeline    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, dueto 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()). Wehave not tried to find such a vulnerable program in the real world.All glibc versions from at least September 1992 (glibc 1.04) to thecurrent release (glibc 2.38) are affected, but the glibc's developershave independently discovered and patched this memory corruption in themaster branch (commit b9390ba, "stdlib: Fix array bounds protection ininsertion sort phase of qsort") during a recent refactoring of qsort().About our advisory, the glibc security team issues the followingstatement:------------------------------------------------------------------------This memory corruption in the GNU C Library through the qsort function isinvoked by an application passing a non-transitive comparison function, whichis undefined according to POSIX and ISO C standards.  As a result, we are ofthe opinion that the resulting CVE, if any, should be assigned to any suchcalling applications and subsequently fixed by passing a valid comparisonfunction to qsort and not to glibc.  We however acknowledge that this is aquality of implementation issue and we fixed this in a recent refactor ofqsort.  We would like to thank Qualys for sharing their findings and helpingus validate our recent changes to qsort.------------------------------------------------------------------------========================================================================Background========================================================================While browsing through Postfix's HISTORY file, we stumbled across apuzzling 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 functionmust return an integer less than, equal to, or greater than zero if thefirst argument is considered to be respectively less than, equal to, orgreater 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):------------------------------------------------------------------------intcmp(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 couldsimply "return (a > b) - (a < b);" and still be transitive and perfectlycorrect:- 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 csuch 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 isin fact nontransitive, because the subtraction in "return (a - b);" isprone to integer overflows:------------------------------------------------------------------------intcmp(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 extremelycommon, as discussed in this excellent blog post from Ted Unangst:  https://flak.tedunangst.com/post/subtraction-is-not-comparisonand as hinted at in OpenBSD's manual page for qsort(): "It is almostalways an error to use subtraction to compute the return value of thecomparison function."Fortunately, when passed to a robust qsort() implementation, thesenontransitive comparison functions should (at the worst) result in anincorrectly sorted array; certainly not in a memory corruption. However,the aforementioned entry from Postfix's HISTORY file suggests that notall 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 directlyexhibit 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 usesthe 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 readthe glibc's qsort() implementation; to our great surprise, we discoveredthat the glibc's qsort() is not, in fact, a quick sort by default, but amerge sort (in stdlib/msort.c).Most likely, merge sort was chosen over quick sort to avoid quick sort'sworst-case performance, which is O(n^2); on the other hand, merge sort'sworst-case performance is O(n*log(n)). But merge sort suffers from onemajor drawback: it does not sort in-place -- it malloc()ates a copy ofthe array of elements to be sorted. As a result, if this array is verylarge (lines 212-217), or if this malloc() fails (lines 219-229), thenthe glibc's qsort() falls back to a quick sort (in stdlib/qsort.c),because quick sort does sort in-place:------------------------------------------------------------------------163 void164 __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   else178     {...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 algorithm226              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 forcingqsort() to call _quicksort(). Locally, forcing the malloc() at line 221to 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); andthis works even when executing a SUID-root program. So we executed ourprogram in the following loop instead:------------------------------------------------------------------------$ while true; do n=$((RANDOM*64+RANDOM+1)); prlimit --as=$((n*4/2*3)) ./qsort $n; doneAborted (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 thesorted 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 1350809Starting 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:4444            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 - 20x7ffff78af008: 0x005280020x7ffff78af00c: 0x800000000x7ffff78af010: 0x000000000x7ffff78af014: 0xc6109e4c0x7ffff78af018: 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, wemust 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 simplecheck "tmp_ptr > base_ptr &&" can be added in front of the cmp() call atline 227 (of course this does not magically result in a correctly sortedarray if cmp() is nontransitive, but at least it does not result in amemory 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 masterbranch (which will become glibc 2.39 in February 2024), by the followingcommit ("stdlib: Fix array bounds protection in insertion sort phase ofqsort"):  https://sourceware.org/git?p=glibc.git;a=commit;h=b9390ba93676c4b1e87e218af5e7e4bb596312acIndeed, the glibc developers have recently refactored qsort() andreplaced the merge sort (and its fallback to quick sort) with anintrospective sort (a combination of quick sort, heap sort, andinsertion sort):  https://en.wikipedia.org/wiki/Introsort  https://sourceware.org/pipermail/libc-alpha/2023-October/151907.htmlDuring this refactoring, the glibc developers have proactivelydiscovered (and patched) the out-of-bounds memory accesses in theinsertion sort (probably because these out-of-bounds memory accessesbecame directly exposed to the misbehavior of nontransitive comparisonfunctions, instead of being safely hidden behind a malloc() failure inthe merge sort).Last-minute note: in January 2024, the glibc developers have revertedthis refactoring of qsort(), back to the original merge sort, plus afallback 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 thatuses a nontransitive comparison function to qsort() attacker-controlledelements); however, vulnerable programs are certain to exist in the realworld:- 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 toreach the memory corruption) is easy: either execute the target program(e.g., a SUID-root program) with a low RLIMIT_AS, or allocate a largeamount of memory with another program on the same machine.Remotely, forcing this malloc() failure is harder: either allocate alarge amount of memory (e.g., a memory leak) in the network service thatis 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 memorycorruption in qsort() as a vulnerability in the glibc itself, asexplained in the "Summary" of our advisory.2024-01-16: We backported commit b9390ba to all current and past stableversions of the glibc, and sent this patch and a draft of our advisoryto the linux-distros@openwall (to piggyback on the glibc embargo forCVE-2023-6246). They immediately acknowledged receipt of our email.2024-01-30: Coordinated Release Date (18:00 UTC).