SortChecker++ verifies that comparators in C++ APIs like std::sort or std::binary_search satisfy the Strict Weak Ordering axioms. Violation of these axioms is undefined behavior and may lead to all sorts of runtime errors including aborts (also here, see this answer, Qualys analysis and my slides for explanations).

SortChecker++ is an extension of SortChecker tool which does similar job to C sorting APIs.

The tool has been tested on LLVM 6.0 (Ubuntu 18.04), 10.0 (Ubuntu 20.04) and 14.0 (Ubuntu 22.04).

List of found issues:

• Libosmium: Missing prepare_for_lookup in test_members_database.cpp (fixed)
• ZeroC Ice: Unsorted array in lookupKwd (fixed)
• GiNaC: Potential issue in comparator in test_antipode (fixed)
• ArrayFire: Irreflexive comparator (already fixed in latest)
• Giac: Non-asymmetric comparator in polynome_less (already fixed in latest)

Note that some (but not all!) errors found by Sortchecker++ can also be found via -D_LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK.

How to build

To use, first install dependencies:

$ sudo apt install libclang-dev llvm-dev

and then build the tool

$ make clean all

How to use

SortChecker works by instrumenting the input file, i.e. inserting additional checking code into it. You can run it manually via

$ SortChecker file.cpp -- $CXXFLAGS

then compile via

$ g++ file.cpp $CXXFLAGS -Ipath/to/sortcheck.h

Finally run the resulting executable and it will report any errors e.g.

$ ./a.out
sortcheck: file.cpp:23: non-asymmetric comparator at positions 1 and 0

(you'll probably want to combine this with some kind of regression or random/fuzz testing to achieve good coverage, also see the SORTCHECK_SHUFFLE option below).

You could also use compiler wrappers in scripts/ folder to combine instrumentation and compilation:

$ PATH=path/to/scripts:$PATH make clean all

Instrumented program may be controlled with environment variables:

• SORTCHECK_VERBOSE=N - verbosity (N is an integer)
• SORTCHECK_SYSLOG=1 - dump messages to syslog (in addition to stderr)
• SORTCHECK_ABORT_ON_ERROR=1 - call abort() on detected error
• SORTCHECK_EXIT_CODE=N - call exit(CODE) on detected error (N is an integer)
• SORTCHECK_OUTPUT=path/to/logfile - write detected errors to file instead of stdout
• SORTCHECK_CHECKS=mask - set which checks are enabled via bitmask (e.g. mask=0xfffe would disable the generally uninteresting irreflexivity checks)
• SORTCHECK_SHUFFLE=val - reshuffle containers before checking with given seed; a value of rand will use random seed (helps to find bugs which are not located at start of array)

Interpreting the error messages

tbd