llvm dev - Jan 2016 - RFC: Extend UBSan with qsort checks

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

Hi Yuri,

On Mon, Jan 11, 2016 at 9:53 AM, Yury Gribov via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi all,
>
> UndefinedBehaviorSanitizer currently does not check for undefined
> behaviors which result from improper usage of standard library functions.
>
It's not really an undefined behavior per se: you just violate the contract
provided by library functions (at least I haven't found a clause in C++
standard
that specifies that the behavior of smth. like std::sort() with invalid
operator< is invalid). The actual behavior of these functions is
determined by library authors, and can be anything from UB to unspecified
result, to nicely formatted error report (if you're using a debug version
of system library):
I think I actually encountered all these cases.

That said, the benefit of checking the sorting routines is clear: I'm not
surprised you were able to catch numerous bugs with your tool.

UBSan currently doesn't have interceptors, and all of its checks [1] are
designed to work without runtime library support, so that it can be used as
a mitigation
tool (with -fsanitize-trap=undefined). It's challenging to add UBSan
interceptors at this point: this would limit the tool portability (at least
portability of some functionality),
and complicate interoperation of UBSan with another tools. There is an
opportunity to, say, add qsort() interceptor to ASan/TSan/MSan, and check
arguments there.
This functionality can be controlled by a runtime flag.

Why do you need compiler instrumentation? Do you want to automatically
inject hooks to SortChecker into std::sort() functions, so that you don't
need to annotate C++ standard library code?
We submitted some annotations to libc++ code (e.g. to report containter
overflow bugs in sanitizers).

[1] -fsanitize=vptr is an only notable exception

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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>


-- 
Alexey Samsonov
vonosmas at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160112/b3092a4f/attachment.html>

(+correct cfe-dev list)

On Tue, Jan 12, 2016 at 2:57 PM, Alexey Samsonov <vonosmas at gmail.com>
wrote:
> Hi Yuri,
>
> On Mon, Jan 11, 2016 at 9:53 AM, Yury Gribov via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi all,
>>
>> UndefinedBehaviorSanitizer currently does not check for undefined
>> behaviors which result from improper usage of standard library
functions.
>>
>
> It's not really an undefined behavior per se: you just violate the
> contract provided by library functions (at least I haven't found a
clause
> in C++ standard
> that specifies that the behavior of smth. like std::sort() with invalid
> operator< is invalid). The actual behavior of these functions is
> determined by library authors, and can be anything from UB to unspecified
> result, to nicely formatted error report (if you're using a debug
version
> of system library):
> I think I actually encountered all these cases.
>
> That said, the benefit of checking the sorting routines is clear: I'm
not
> surprised you were able to catch numerous bugs with your tool.
>
> UBSan currently doesn't have interceptors, and all of its checks [1]
are
> designed to work without runtime library support, so that it can be used as
> a mitigation
> tool (with -fsanitize-trap=undefined). It's challenging to add UBSan
> interceptors at this point: this would limit the tool portability (at least
> portability of some functionality),
> and complicate interoperation of UBSan with another tools. There is an
> opportunity to, say, add qsort() interceptor to ASan/TSan/MSan, and check
> arguments there.
> This functionality can be controlled by a runtime flag.
>
> Why do you need compiler instrumentation? Do you want to automatically
> inject hooks to SortChecker into std::sort() functions, so that you
don't
> need to annotate C++ standard library code?
> We submitted some annotations to libc++ code (e.g. to report containter
> overflow bugs in sanitizers).
>
> [1] -fsanitize=vptr is an only notable exception
>
> 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
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
>
> --
> Alexey Samsonov
> vonosmas at gmail.com
>


-- 
Alexey Samsonov
vonosmas at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160112/b64894da/attachment-0001.html>