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

On Tue, Jan 12, 2016 at 10:27 PM, Yury Gribov via cfe-dev <
cfe-dev at lists.llvm.org> wrote:
>
> As for C++11, it has for e.g. srtd::sort:
>
> "Requires: operator< (for the version with no arguments) or comp
(for the
> version with a comparison argument) defines a strict weak ordering
(25.4)."
>
> which also sounds like UB.

Exactly correct.
If your comparison operator does not define a SWO, then you have no
guarantees of the results. Crashes are common.

In principle, I am very much in favor of a checker like this.
Passing an invalid comparison operator is one of the most common misuses of
std::sort.

I worry about the cost, though.

-- Marshall
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160114/4c967cf5/attachment.html>

I don't have the full thread for context.

There is no practical way to test if a given comparison function satisfies
a strict-weak ordering or not. The issue is the requirement of transitivity:

a < b && b < c => a < c

Any test would have to ensure that this holds for all triplets in the
sequence being sorted (and you would have to verify the other axioms as
well).

The reason why sort can crash if this is violated is because it establishes
a sentinel at a partition point and assumes nothing will cross the sentinel
- you can bounds check with some additional cost but the ordering is still
going to be undefined if this axiom is violated and there is no guarantee a
bounds check will catch it.

There are some tests that can be done for common failures though - for
example a common failure of sort is trying to sort a floating point
sequence with float or doubles that contains NaNs. You can test for NaNs on
such a sequence with an additional linear pass. But it doesn't help if you
have a custom comparison that is passed in, that does something like
compare the first member of a struct that is of type double.

There are many pre-conditions in STL (and most any other library interface)
that cannot easily be validated.

Sean


On Thu, Jan 14, 2016 at 10:11 PM, Marshall Clow <mclow.lists at gmail.com>
wrote:
> On Tue, Jan 12, 2016 at 10:27 PM, Yury Gribov via cfe-dev <
> cfe-dev at lists.llvm.org> wrote:
>
>>
>> As for C++11, it has for e.g. srtd::sort:
>>
>> "Requires: operator< (for the version with no arguments) or
comp (for the
>> version with a comparison argument) defines a strict weak ordering
(25.4)."
>>
>> which also sounds like UB.
>
>
> Exactly correct.
> If your comparison operator does not define a SWO, then you have no
> guarantees of the results. Crashes are common.
>
> In principle, I am very much in favor of a checker like this.
> Passing an invalid comparison operator is one of the most common misuses
> of std::sort.
>
> I worry about the cost, though.
>
> -- Marshall
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160115/40a1a4a7/attachment-0001.html>

On 01/15/2016 11:47 AM, Sean Parent wrote:
> I don't have the full thread for context.
There you go: 
http://lists.llvm.org/pipermail/llvm-dev/2016-January/093835.html
> There is no practical way to test if a given comparison function satisfies
> a strict-weak ordering or not. The issue is the requirement of
transitivity:
>
> a < b && b < c => a < c
>
> Any test would have to ensure that this holds for all triplets in the
> sequence being sorted (and you would have to verify the other axioms as
> well).
Right, that's why I have to intercept qsort to check transitivity.
> The reason why sort can crash if this is violated is because it establishes
> a sentinel at a partition point and assumes nothing will cross the sentinel
> - you can bounds check with some additional cost but the ordering is still
> going to be undefined if this axiom is violated and there is no guarantee a
> bounds check will catch it.
Ah, good to know, thanks.
> There are some tests that can be done for common failures though - for
> example a common failure of sort is trying to sort a floating point
> sequence with float or doubles that contains NaNs. You can test for NaNs on
> such a sequence with an additional linear pass. But it doesn't help if
you
> have a custom comparison that is passed in, that does something like
> compare the first member of a struct that is of type double.
>
> There are many pre-conditions in STL (and most any other library interface)
> that cannot easily be validated.
>
> Sean
>
>
> On Thu, Jan 14, 2016 at 10:11 PM, Marshall Clow <mclow.lists at
gmail.com>
> wrote:
>
>> On Tue, Jan 12, 2016 at 10:27 PM, Yury Gribov via cfe-dev <
>> cfe-dev at lists.llvm.org> wrote:
>>
>>>
>>> As for C++11, it has for e.g. srtd::sort:
>>>
>>> "Requires: operator< (for the version with no arguments) or
comp (for the
>>> version with a comparison argument) defines a strict weak ordering
(25.4)."
>>>
>>> which also sounds like UB.
>>
>>
>> Exactly correct.
>> If your comparison operator does not define a SWO, then you have no
>> guarantees of the results. Crashes are common.
>>
>> In principle, I am very much in favor of a checker like this.
>> Passing an invalid comparison operator is one of the most common
misuses
>> of std::sort.
>>
>> I worry about the cost, though.
>>
>> -- Marshall
>>
>>
>