Yury Gribov via llvm-dev
2016-Jan-11 17:53 UTC
[llvm-dev] 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
Alexey Samsonov via llvm-dev
2016-Jan-12 22:57 UTC
[llvm-dev] RFC: Extend UBSan with qsort checks
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>
Alexey Samsonov via llvm-dev
2016-Jan-12 22:57 UTC
[llvm-dev] RFC: Extend UBSan with qsort checks
(+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>