<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 12, 2016 at 10:28 PM, Yury Gribov <span dir="ltr"><<a href="mailto:y.gribov@samsung.com" target="_blank">y.gribov@samsung.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 01/13/2016 03:10 AM, Kostya Serebryany wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
FTR, here is one way to implement this in the library:<br>
<a href="https://gcc.gnu.org/svn/gcc/branches/google/gcc-4_9/libstdc++-v3/include/bits/stl_algo.h" rel="noreferrer" target="_blank">https://gcc.gnu.org/svn/gcc/branches/google/gcc-4_9/libstdc++-v3/include/bits/stl_algo.h</a><br>
Search for "check sort predicate for strict weak ordering"<br>
</blockquote>
<br></span>
Nice, although this wouldn't catch violations of transitivity (which is probably the most important type of bug).<div class="HOEnZb"><div class="h5"><br></div></div></blockquote><div><br></div><div>I thought it would... </div><div>Can you give a test?  </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On Tue, Jan 12, 2016 at 2:57 PM, Alexey Samsonov via llvm-dev <<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
(+correct cfe-dev list)<br>
<br>
On Tue, Jan 12, 2016 at 2:57 PM, Alexey Samsonov <<a href="mailto:vonosmas@gmail.com" target="_blank">vonosmas@gmail.com</a>><br>
wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Yuri,<br>
<br>
On Mon, Jan 11, 2016 at 9:53 AM, Yury Gribov via llvm-dev <<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi all,<br>
<br>
UndefinedBehaviorSanitizer currently does not check for undefined<br>
behaviors which result from improper usage of standard library functions.<br>
<br>
</blockquote>
<br>
It's not really an undefined behavior per se: you just violate the<br>
contract provided by library functions (at least I haven't found a clause<br>
in C++ standard<br>
that specifies that the behavior of smth. like std::sort() with invalid<br>
operator< is invalid). The actual behavior of these functions is<br>
determined by library authors, and can be anything from UB to unspecified<br>
result, to nicely formatted error report (if you're using a debug version<br>
of system library):<br>
I think I actually encountered all these cases.<br>
<br>
That said, the benefit of checking the sorting routines is clear: I'm not<br>
surprised you were able to catch numerous bugs with your tool.<br>
<br>
UBSan currently doesn't have interceptors, and all of its checks [1] are<br>
designed to work without runtime library support, so that it can be used as<br>
a mitigation<br>
tool (with -fsanitize-trap=undefined). It's challenging to add UBSan<br>
interceptors at this point: this would limit the tool portability (at least<br>
portability of some functionality),<br>
and complicate interoperation of UBSan with another tools. There is an<br>
opportunity to, say, add qsort() interceptor to ASan/TSan/MSan, and check<br>
arguments there.<br>
This functionality can be controlled by a runtime flag.<br>
<br>
Why do you need compiler instrumentation? Do you want to automatically<br>
inject hooks to SortChecker into std::sort() functions, so that you don't<br>
need to annotate C++ standard library code?<br>
We submitted some annotations to libc++ code (e.g. to report containter<br>
overflow bugs in sanitizers).<br>
<br>
[1] -fsanitize=vptr is an only notable exception<br>
<br>
One notorious instance of such errors is invalid usage of qsort or<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
bsearch routines (or std::sort and friends in case of C++):<br>
* using comparison function that violates ordering axioms (reflexivity,<br>
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<br>
fully sorted arrays, rare failed bsearches, etc.) but may as well cause<br>
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>
<br>
I've recently developed a simple proof-of-concept tool SortChecker (<br>
<a href="https://github.com/yugr/sortcheck" rel="noreferrer" target="_blank">https://github.com/yugr/sortcheck</a>) which intercepts calls to qsort and<br>
friends (via LD_PRELOAD) and performs various sanity checks before passing<br>
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<br>
open-source packages (GCC, Harfbuzz, dpkg, libXt, etc.). I'm also pretty<br>
sure most C++ developers have failed to write correct comparison function<br>
at least once.<br>
<br>
Could SortChecker functionality be considered for integration into<br>
UBSan? Extending SortChecker to C++ land would require significant work<br>
which has already been done in sanitizers (compiler instrumentation,<br>
portable parallel code, etc.). On the other hand, ability to detect new<br>
classes of bugs should benefit UBSan and community.<br>
</blockquote>
<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc 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>
<br>
</blockquote>
<br>
<br>
<br>
--<br>
Alexey Samsonov<br>
<a href="mailto:vonosmas@gmail.com" target="_blank">vonosmas@gmail.com</a><br>
<br>
</blockquote>
<br>
<br>
<br>
--<br>
Alexey Samsonov<br>
<a href="mailto:vonosmas@gmail.com" target="_blank">vonosmas@gmail.com</a><br>
<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>
<br>
<br>
</blockquote>
<br>
</blockquote>
<br>
</div></div></blockquote></div><br></div></div>