[llvm-dev] RFC: Extend UBSan with qsort checks

[Yury Gribov via llvm-dev]

Hi all,

UndefinedBehaviorSanitizer currently does not check for undefined 
behaviors which result from improper usage of standard library functions.

One notorious instance of such errors is invalid usage of qsort or 
bsearch routines (or std::sort and friends in case of C++):
* using comparison function that violates ordering axioms (reflexivity, 
symmetry, transitivity)
* returning unstable results from comparison function
* passing unsorted array to bsearch
* etc.

Errors like this will usually result in slightly invalid output (not 
fully sorted arrays, rare failed bsearches, etc.) but may as well cause 
aborts on some systems (https://bugzilla.samba.org/show_bug.cgi?id=3959).

I've recently developed a simple proof-of-concept tool SortChecker 
(https://github.com/yugr/sortcheck) which intercepts calls to qsort and 
friends (via LD_PRELOAD) and performs various sanity checks before 
passing control to libc e.g.
* sign(cmp(a, b)) == - sign(cmp(b, a)) for all array elements
* etc.

Results were quite inspiring: I've found several errors in popular 
open-source packages (GCC, Harfbuzz, dpkg, libXt, etc.). I'm also pretty 
sure most C++ developers have failed to write correct comparison 
function at least once.

Could SortChecker functionality be considered for integration into 
UBSan? Extending SortChecker to C++ land would require significant work 
which has already been done in sanitizers (compiler instrumentation, 
portable parallel code, etc.). On the other hand, ability to detect new 
classes of bugs should benefit UBSan and community.

-Y