Skip to content

avoid non-transitive comparisons leading to out of bounds read and write in ldb_qsort() and glibc qsort()

Douglas Bagnall requested to merge samba-team/devel/samba:douglas-compares-safely into master

Qualys pointed out on the OSS-Security list that the glibc quicksort implementation allows out of bounds access when the compare function is non-transitive (that is, when the combination of A > B and B > C does not imply A > C).

https://www.openwall.com/lists/oss-security/2024/01/30/7

This bug has been well hidden because glibc qsort() is usually a mergesort, not quicksort. It falls back to quicksort if a memory allocation for mergesort fails.

What makes it worse for Samba is we have a fork of an old version of glibc quicksort that we adapted for ldb_qsort(), which provides qsort_r()-like semantics.

A common source of non-transitivity in compare functions is using subtraction to get a signed integer (as in return a - b;). The Qualys post works through an example with int values, the crux of which is that 0 - INT_MIN results in INT_MIN.

In Samba compare code we have a few subtractions that can overflow, and many that probably can't. An example of the former is in comparing ACEs we often subtract the access masks, which are uint32_t. By the rules of unsigned a = 0x80000001, b = 1, then a - b == b - a == 0x80000000 which is INT_MIN when cast to int by the function signature (supposing 32 bit ints of course, it's worse otherwise).

There are examples of subtraction that probably can't go wrong in practice but might in theory in our strcasecmp_m functions, where we subtract codepoint_t values, which is an alias for uint32_t. It shouldn't be possible to set the values beyond the range of Unicode (2 million or so). But here I think we should avoid the subtraction, just in case.

There are other cases we subtract values we know can't overflow: they are char or bool. Here, I still think we shouldn't subtract, because it leads us into bad habits.

So, I propose a new macro that does the thing you want, comparing a and b and returning an int that is guaranteed to be appropriately negative, or zero, or positive. It is called NUMERIC_CMP(a, b), and it works for anything that is comparable with < and > (including pointers and floats). It is currently defined thus:

#define NUMERIC_CMP(a, b) (((a) > (b)) - ((a) < (b)))

which maybe looks weird, but has the same result as something like this

#define NUMERIC_CMP(a, b) (((a) > (b)) ? 1 : ((a) < (b)) ? -1 : 0)

but encourages the compiler toward branchless code.

There are a couple of tests that have to change away from asserting exact cmp return values to asserting the values are greater or less than zero.

There's more to do.

glibc decided this wasn't a CVE for them, since it was the fault of the various projects for using non-transitive comparisons.

Checklist

  • Commits have Signed-off-by: with name/author being identical to the commit author
  • (optional) This MR is just one part towards a larger feature.
  • (optional, if backport required) Bugzilla bug filed and BUG: tag added
  • Test suite updated with functionality tests
  • Test suite updated with negative tests
  • Documentation updated
  • CI timeout is 3h or higher (see Settings/CICD/General pipelines/ Timeout)

Reviewer's checklist:

  • There is a test suite reasonably covering new functionality or modifications
  • Function naming, parameters, return values, types, etc., are consistent and according to README.Coding.md
  • This feature/change has adequate documentation added
  • No obvious mistakes in the code

Merge request reports