<div dir="ltr">FTR, here is one way to implement this in the library:<div><a href="https://gcc.gnu.org/svn/gcc/branches/google/gcc-4_9/libstdc++-v3/include/bits/stl_algo.h">https://gcc.gnu.org/svn/gcc/branches/google/gcc-4_9/libstdc++-v3/include/bits/stl_algo.h</a><br></div><div>Search for "<span style="font-size:12.8px">check sort predicate for strict weak ordering"</span></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 12, 2016 at 2:57 PM, Alexey Samsonov via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">(+correct cfe-dev list)</div><div class="gmail_extra"><div><div class="h5"><br><div class="gmail_quote">On Tue, Jan 12, 2016 at 2:57 PM, Alexey Samsonov <span dir="ltr"><<a href="mailto:vonosmas@gmail.com" target="_blank">vonosmas@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra">Hi Yuri,</div><span><div class="gmail_extra"><br></div><div class="gmail_extra">On Mon, Jan 11, 2016 at 9:53 AM, Yury Gribov via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br></div></span><div class="gmail_extra"><div class="gmail_quote"><span><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Hi all,<br>
<br>
UndefinedBehaviorSanitizer currently does not check for undefined behaviors which result from improper usage of standard library functions.<br></blockquote><div><br></div></span><div>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</div><div>that specifies that the behavior of smth. like std::sort() with invalid operator< is invalid). The actual behavior of these functions is</div><div>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):</div><div>I think I actually encountered all these cases.</div><div><br></div><div>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.</div><div><br></div><div>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</div><div>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),</div><div>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.</div><div>This functionality can be controlled by a runtime flag.</div><div><br></div><div>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?</div><div>We submitted some annotations to libc++ code (e.g. to report containter overflow bugs in sanitizers).</div><div><br></div><div>[1] -fsanitize=vptr is an only notable exception</div><span><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
One notorious instance of such errors is invalid usage of qsort or bsearch routines (or std::sort and friends in case of C++):<br>
* using comparison function that violates ordering axioms (reflexivity, symmetry, transitivity)<br>
* returning unstable results from comparison function<br>
* passing unsorted array to bsearch<br>
* etc.<br>
<br>
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 (<a href="https://bugzilla.samba.org/show_bug.cgi?id=3959" rel="noreferrer" target="_blank">https://bugzilla.samba.org/show_bug.cgi?id=3959</a>).<br>
<br>
I've recently developed a simple proof-of-concept tool SortChecker (<a href="https://github.com/yugr/sortcheck" rel="noreferrer" target="_blank">https://github.com/yugr/sortcheck</a>) which intercepts calls to qsort and friends (via LD_PRELOAD) and performs various sanity checks before passing control to libc e.g.<br>
* sign(cmp(a, b)) == - sign(cmp(b, a)) for all array elements<br>
* etc.<br>
<br>
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.<br>
<br>
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.</blockquote><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
-Y<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></span></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr">Alexey Samsonov<br><a href="mailto:vonosmas@gmail.com" target="_blank">vonosmas@gmail.com</a></div></div>
</font></span></div></div>
</blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br><div><div dir="ltr">Alexey Samsonov<br><a href="mailto:vonosmas@gmail.com" target="_blank">vonosmas@gmail.com</a></div></div>
</font></span></div>
<br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>