<div dir="ltr">Inviting Paul to the party (he wrote the <a href="https://gcc.gnu.org/svn/gcc/branches/google/gcc-4_9/libstdc++-v3/include/bits/stl_algo.h">libstdc++ sort checker</a>).</div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jan 12, 2016 at 11:09 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 10:08 AM, Yury Gribov wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 01/13/2016 09:57 AM, Kostya Serebryany wrote:<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 10:28 PM, Yury Gribov <<a href="mailto:y.gribov@samsung.com" target="_blank">y.gribov@samsung.com</a>><br>
wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On 01/13/2016 03:10 AM, Kostya Serebryany wrote:<br>
<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>
<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>
<br>
Search for "check sort predicate for strict weak ordering"<br>
<br>
</blockquote>
<br>
Nice, although this wouldn't catch violations of transitivity (which is<br>
probably the most important type of bug).<br>
<br>
<br>
</blockquote>
I thought it would...<br>
</blockquote>
<br>
But debug operator() only knows about 2 inputs whereas for transitivity<br>
you'll need to consider at least 3.<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Can you give a test?<br>
</blockquote></blockquote>
<br></span>
Here's an example of transitivity violation in GCC: <a href="https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68988" rel="noreferrer" target="_blank">https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68988</a><div class="HOEnZb"><div class="h5"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
On Tue, Jan 12, 2016 at 2:57 PM, Alexey Samsonov via llvm-dev <<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>> wrote:<br>
<br>
(+correct cfe-dev list)<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<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>
Hi Yuri,<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<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>
Hi all,<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
UndefinedBehaviorSanitizer currently does not check for undefined<br>
behaviors which result from improper usage of standard library<br>
functions.<br>
<br>
<br>
</blockquote>
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<br>
clause<br>
in C++ standard<br>
that specifies that the behavior of smth. like std::sort() with<br>
invalid<br>
operator< is invalid). The actual behavior of these functions is<br>
determined by library authors, and can be anything from UB to<br>
unspecified<br>
result, to nicely formatted error report (if you're using a debug<br>
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<br>
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<br>
[1] are<br>
designed to work without runtime library support, so that it can be<br>
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<br>
least<br>
portability of some functionality),<br>
and complicate interoperation of UBSan with another tools. There<br>
is an<br>
opportunity to, say, add qsort() interceptor to ASan/TSan/MSan, and<br>
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<br>
automatically<br>
inject hooks to SortChecker into std::sort() functions, so that you<br>
don't<br>
need to annotate C++ standard library code?<br>
We submitted some annotations to libc++ code (e.g. to report<br>
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>
<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<br>
(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<br>
cause<br>
aborts on some systems (<br>
<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<br>
qsort and<br>
friends (via LD_PRELOAD) and performs various sanity checks before<br>
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<br>
pretty<br>
sure most C++ developers have failed to write correct comparison<br>
function<br>
at least once.<br>
<br>
Could SortChecker functionality be considered for integration into<br>
UBSan? Extending SortChecker to C++ land would require<br>
significant work<br>
which has already been done in sanitizers (compiler instrumentation,<br>
portable parallel code, etc.). On the other hand, ability to<br>
detect new<br>
classes of bugs should benefit UBSan and community.<br>
<br>
</blockquote>
<br>
<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
-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>
<br>
</blockquote>
<br>
<br>
--<br>
Alexey Samsonov<br>
<a href="mailto:vonosmas@gmail.com" target="_blank">vonosmas@gmail.com</a><br>
<br>
<br>
</blockquote>
<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>
<br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
</blockquote>
<br>
</div></div></blockquote></div><br></div>