Page MenuHomePhabricator

[clang][ubsan] Implicit Cast Sanitizer - integer truncation - clang part
ClosedPublic

Authored by lebedev.ri on Jul 5 2018, 1:18 AM.

Details

Summary

C and C++ are interesting languages. They are statically typed, but weakly.
The implicit conversions are allowed. This is nice, allows to write code
while balancing between getting drowned in everything being convertible,
and nothing being convertible. As usual, this comes with a price:

unsigned char store = 0;

bool consume(unsigned int val);

void test(unsigned long val) {
  if (consume(val)) {
    // the 'val' is `unsigned long`, but `consume()` takes `unsigned int`.
    // If their bit widths are different on this platform, the implicit
    // truncation happens. And if that `unsigned long` had a value bigger
    // than UINT_MAX, then you may or may not have a bug.

    // Similarly, integer addition happens on `int`s, so `store` will
    // be promoted to an `int`, the sum calculated (0+768=768),
    // and the result demoted to `unsigned char`, and stored to `store`.
    // In this case, the `store` will still be 0. Again, not always intended.
    store = store + 768; // before addition, 'store' was promoted to int.
  }

  // But yes, sometimes this is intentional.
  // You can either make the conversion explicit
  (void)consume((unsigned int)val);
  // or mask the value so no bits will be *implicitly* lost.
  (void)consume((~((unsigned int)0)) & val);
}

Yes, there is a -Wconversion` diagnostic group, but first, it is kinda
noisy, since it warns on everything (unlike sanitizers, warning on an
actual issues), and second, there are cases where it does not warn.
So a Sanitizer is needed. I don't have any motivational numbers, but i know
i had this kind of problem 10-20 times, and it was never easy to track down.

The logic to detect whether an truncation has happened is pretty simple
if you think about it - https://godbolt.org/g/NEzXbb - basically, just
extend (using the new, not original!, signedness) the 'truncated' value
back to it's original width, and equality-compare it with the original value.

The most non-trivial thing here is the logic to detect whether this
ImplicitCastExpr AST node is actually an implicit conversion, or
part of an explicit cast. Because the explicit casts are modeled as an outer
ExplicitCastExpr with some ImplicitCastExpr's as direct children.
https://godbolt.org/g/eE1GkJ

Nowadays, we can just use the new part_of_explicit_cast flag, which is set
on all the implicitly-added ImplicitCastExpr's of an ExplicitCastExpr.
So if that flag is not set, then it is an actual implicit conversion.

As you may have noted, this isn't just named -fsanitize=implicit-integer-truncation.
There are potentially some more implicit conversions to be warned about.
Namely, implicit conversions that result in sign change; implicit conversion
between different floating point types, or between fp and an integer,
when again, that conversion is lossy.

One thing i know isn't handled is bitfields.

This is a clang part.
The compiler-rt part is D48959.

Fixes PR21530, PR37552, PR35409.
Partially fixes PR9821.
Fixes https://github.com/google/sanitizers/issues/940. (other than sign-changing implicit conversions)

Diff Detail

Repository
rC Clang

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
vsk added inline comments.Jul 19 2018, 12:58 PM
docs/UndefinedBehaviorSanitizer.rst
96

Nitpicks:
kind of issues -> issue
promotions -> conversions

132

Could you make this more explicit? It would help to point out that this check does not diagnose lossy implicit integer conversions, but that the new check does. Ditto for the comment in the unsigned-integer-overflow section.

lib/CodeGen/CodeGenFunction.h
464

Why not 0 instead of 8, given that in the common case, this stack is unused?

469

I'm not sure the cost of maintaining an extra vector is worth the benefit of the added assertion. Wouldn't it be cheaper to just store the number of pushed casts? You'd only need one constructor which accepts an ArrayRef<const CastExpr *>.

test/CodeGen/catch-implicit-integer-truncations.c
30

There's no need to check the profile metadata here.

160

nit, aren't these true-negatives because we expect to see no errors?

lebedev.ri marked 6 inline comments as done.

Rebased ontop of yet-again rewritten D49508.
Addressed all @vsk's review notes.

More review notes wanted :)

lebedev.ri added inline comments.Jul 20 2018, 5:35 AM
docs/UndefinedBehaviorSanitizer.rst
132

Is this better?

lib/CodeGen/CodeGenFunction.h
464

No longer relevant.

469

No longer relevant.

test/CodeGen/catch-implicit-integer-truncations.c
30

I was checking it because otherwise HANDLER_IMPLICIT_CAST would have over-eagerly consumed , !prof !3 too.
But there is actually a way around that..

160

Right.

vsk added inline comments.Jul 20 2018, 10:34 AM
docs/UndefinedBehaviorSanitizer.rst
132

Looks good.

155–156

Please add "the implicit-cast group of checks" to this list.

lib/CodeGen/CodeGenFunction.h
464

I'm referring to CastExprStack within ScalarExprEmitter, which still allocates space for 8 pointers inline.

lebedev.ri added inline comments.Jul 20 2018, 10:41 AM
lib/CodeGen/CodeGenFunction.h
464

Ah, you mean in the general case when the sanitizer is disabled?

vsk added inline comments.Jul 20 2018, 10:57 AM
lib/CodeGen/CodeGenFunction.h
464

Yes. It's a relatively minor concern, but clang's stack can get pretty deep inside of CodeGenFunction. At one point we needed to outline code by hand to unbreak the ASan build. Later I think we just increased the stack size rlimit. I don't see a countervailing performance benefit of allocating more space inline, at least not here.

lebedev.ri added inline comments.Jul 20 2018, 11:27 AM
lib/CodeGen/CodeGenFunction.h
464

No, i agree and totally understand.
I just didn't think about that sanitizer-less context.

lebedev.ri marked 11 inline comments as done.

Address @vsk's review notes.

Rebased on top of svn tip / git master, now that D49508 has landed,
which means there shouldn't be any more false-positives (and it's a bit faster to detect that the check shouldn't be emitted, too).

Ping, any more notes? :)

vsk accepted this revision.Jul 24 2018, 11:47 AM

LGTM, although I think it'd be helpful to have another +1 just to be safe.

I did two small experiments with this using a Stage1 Rel+Asserts compiler:

Stage2 Rel+Asserts build of llvm-tblgen:
ninja llvm-tblgen 384.27s user 14.98s system 1467% cpu 27.203 total

Stage2 Rel+Asserts build of llvm-tblgen with implicit-cast checking:
ninja llvm-tblgen 385.15s user 15.02s system 1472% cpu 27.170 total

With caveats about having a small sample size here and testing with an asserts-enabled stage1 build, I don't see any red flags about the compile-time overhead of the new check. I would have liked to measure the check against more code, but I couldn't complete a stage2 build due to a diagnostic which might plausibly point to a real issue in tblgen:

/Users/vsk/src/llvm.org-lldbsan/llvm/utils/TableGen/RegisterInfoEmitter.cpp:604:17: runtime error: implicit cast from type 'int' of value -1 (32-bit, signed) to type 'const unsigned short' changed the value to 65535 (16-bit, unsigned)

With -fno-sanitize-recover=all disabled, I found a few more reports:

/Users/vsk/src/llvm.org-lldbsan/llvm/include/llvm/Object/Archive.h:278:38: runtime error: implicit cast from type 'int' of value -1 (32-bit, signed) to type 'uint16_t' (aka 'unsigned short') changed the value to 65535 (16-bit, unsigned)
--> uint16_t FirstRegularStartOfFile = -1;

/Users/vsk/src/llvm.org-lldbsan/llvm/lib/Analysis/MemorySSA.cpp:199:12: runtime error: implicit cast from type 'size_t' (aka 'unsigned long') of value 4969132974595412838 (64-bit, unsigned) to type 'unsigned int' changed the value to 3765474150 (32-bit, unsigned)
--> hash_combine() result casted to unsigned

/Users/vsk/src/llvm.org-lldbsan/llvm/lib/CodeGen/TargetLoweringBase.cpp:1212:30: runtime error: implicit cast from type 'unsigned int' of value 512 (32-bit, unsigned) to type 'unsigned char' changed the value to 0 (8-bit, unsigned)
--> NumRegistersForVT[i] = getVectorTypeBreakdownMVT(...)

/Users/vsk/src/llvm.org-lldbsan/llvm/lib/Transforms/Scalar/EarlyCSE.cpp:136:12: runtime error: implicit cast from type 'size_t' (aka 'unsigned long') of value 16583795711468875482 (64-bit, unsigned) to type 'unsigned int' changed the value to 3116347098 (32-bit, unsigned)
--> hash_combine() result casted to unsigned
...

These four at least don't look like false positives:

  • Maybe we should consider special-casing assignments of "-1" to unsigned values? This seems somewhat idiomatic.
  • At least a few of these are due to not being explicit about dropping the high bits of hash_combine()'s result. Given that this check is opt-in, that that seems like a legitimate diagnostic (lost entropy).
  • The TargetLoweringBase.cpp diagnostic looks a bit scary.
lib/CodeGen/CGExprScalar.cpp
951

nit, extra parens?

This revision is now accepted and ready to land.Jul 24 2018, 11:47 AM
In D48958#1173860, @vsk wrote:

LGTM, although I think it'd be helpful to have another +1 just to be safe.

Thank you for the review!
It would indeed be great if someone else could take a look, especially since we are so close to the branching point.

In D48958#1173860, @vsk wrote:

...

In D48958#1173860, @vsk wrote:

These four at least don't look like false positives:

  • Maybe we should consider special-casing assignments of "-1" to unsigned values? This seems somewhat idiomatic.

I personally would use ~0U there.
One more datapoint: the implicit-sign-change will/should still complain about that case.
So personally i'd like to keep it.

  • At least a few of these are due to not being explicit about dropping the high bits of hash_combine()'s result. Given that this check is opt-in, that that seems like a legitimate diagnostic (lost entropy).
  • The TargetLoweringBase.cpp diagnostic looks a bit scary.
lebedev.ri added inline comments.Jul 25 2018, 2:46 PM
lib/CodeGen/CGExprScalar.cpp
944–968

Based on IRC disscussion with @rsmith, it seems this should be just return !Cast->getIsPartOfExplicitCast(); (and inline it), and no need for the CastExprStack and stuff.

lebedev.ri marked an inline comment as done.
lebedev.ri added a reviewer: erichkeane.
lebedev.ri added a subscriber: erichkeane.

Address @rsmith & @erichkeane [IRC] review notes:

  • D49838 - [AST] Sink 'part of explicit cast' down into ImplicitCastExpr
  • D49844 - [AST] Add a isActuallyImplicitCast() helper to the CastExpr class.
  • Drop no longer needed CastExprStackGuard, ScalarExprEmitter::IsTopCastPartOfExplictCast(), just use CastExpr::isActuallyImplicitCast() directly.

This should be a NFC change, there should not be any functionality change because of this.

test/CodeGenCXX/catch-implicit-integer-truncations.cpp
9–34

@rsmith these tests should be equivalent to what you have brought up, so that situation was already tested.

erichkeane accepted this revision.Jul 26 2018, 6:29 AM

1 Nit, otherwise LGTM.

docs/UndefinedBehaviorSanitizer.rst
94

I think the last 2 commas in this sentence are unnecessary?

aaron.ballman added inline comments.Jul 26 2018, 8:16 AM
docs/UndefinedBehaviorSanitizer.rst
92–96

How about: Implicit cast from a value of integral type which results in data loss where the demoted value, when cast back to the original type, would have a different value than the original. This issue may be caused by an implicit conversion.

lebedev.ri marked 2 inline comments as done.

Small rewording in docs/UndefinedBehaviorSanitizer.rst thanks to @erichkeane & @aaron.ballman!

docs/UndefinedBehaviorSanitizer.rst
92–96

Thank you!

Rebase,
Address @rsmith review notes - just inline D49844.

rsmith added inline comments.Jul 26 2018, 4:30 PM
docs/ReleaseNotes.rst
49–52

Regarding the name of this sanitizer: C and C++ refer to these as "implicit conversions" not "implicit casts", and "implicit cast" is a contradiction in terms -- a cast is explicit syntax for performing a conversion. We should use the external terminology here ("implicit-conversion") rather than the slightly-odd clang-specific convention of calling an implicit conversion an "implicit cast".

304

got -> may have been

306

implicit -> explicit

docs/UndefinedBehaviorSanitizer.rst
17

Don't use Title Caps here. "Problematic implicit conversions"

94

I would parenthesize the "where the demoted value [...] would have a different value from the original" clause, since it's just explaining what we mean by "data loss".

94

Is this really the right rule, though? Consider:

unsigned int x = 0x81234567;
int y = x; // does the sanitizer catch this or not?

Here, the value of x is not the same as the value of y (assuming 32-bit int): y is negative. But this is not "data loss" according to the documented meaning of the sanitizer. I think we should produce a sanitizer trap on this case.

130–137

Remove the "Please"s here. We don't need to beg the reader to read the rest of the sentence. Just "Note that this [...]. Also note that integer conversions may result in an unexpected computation result, [...]"

139–145

Likewise here.

include/clang/Basic/Sanitizers.def
139–141

-fsanitize=integer should include -fsanitize=implicit-integer-truncation.

lib/CodeGen/CGExprScalar.cpp
954–955

Check the Clang types here, not the LLVM types. There is no guarantee that only integer types get converted to LLVM IntegerTypes. (But if you like, you can assert that SrcTy and DstTy are IntegerTypes after checking that the clang types are both integer types.)

956–958

I believe this is redundant: we don't get here for an integer to boolean conversion, and a boolean to integer conversion would always be caught by the bit width check below.

962–964

I think you should also catch casts that change signedness in the case if the sign bit is set on the value. (Though if you want to defer this to a follow-up change and maybe give the sanitizer a different name, that's fine with me.)

lebedev.ri marked 9 inline comments as done and 2 inline comments as done.
lebedev.ri edited the summary of this revision. (Show Details)

Hopefully address @rsmith review notes:

  • s/cast/conversion/ where appropriate
  • Some wording in docs
  • Some 'legality' checks in ScalarExprEmitter::EmitIntegerTruncationCheck().

Oops, forgot to submit the inline comments.
(It is inconvenient that they aren't submitted with the rest.)

docs/ReleaseNotes.rst
306

Whoops.

docs/UndefinedBehaviorSanitizer.rst
94

I've reverted this to my original text.
It should now convey the correct idea, but i'm not sure this is correct English.

unsigned int x = 0x81234567;
int y = x; // does the sanitizer catch this or not?

No, it does not. It indeed should. I do plan on following-up with that,
thus i've adding the group (`-fsanitize=implicit-conversion`), not just one check.

include/clang/Basic/Sanitizers.def
139–141

Wow. Ok.

lib/CodeGen/CGExprScalar.cpp
954–955

Interesting, ok.

956–958

Uhm, i'll replace it with an assert then.

962–964

Yes, thank you for bringing this up.
That is certainly the plain, but i always planned to add that later on.

rsmith accepted this revision.Jul 30 2018, 10:50 AM

Only comments on documentation and assertions. Feel free to commit once these are addressed to your satisfaction.

docs/ReleaseNotes.rst
310

"Just like -fsanitize=integer" -> "Just like other -fsanitize=integer checks", now that this is part of -fsanitize=integer.

docs/UndefinedBehaviorSanitizer.rst
17

I don't think it makes sense to list this here, as it's not undefined behavior, and this is a list of undefined behavior that UBSan catches. (And I think it makes sense from a communication perspective to consider the non-UB checks to be "not part of UBSan but handled by the same infrastructure".)

94

bigger -> larger

... would read a bit better.

96

I don't think this last sentence adds anything, and it creates the impression that the issue is sometimes caused by something other than implicit integer conversions (which it isn't, as far as I can tell). Maybe just delete the last sentence here?

And instead, something like this would be useful:

"Issues caught by this sanitizer are not undefined behavior, but are often unintentional."

134–135

I don't think that's true (not until you add a sanitizer for signed <-> unsigned conversions that change the value). 4U / -2 produces the unexpected result 0U rather than the mathematically-correct result -2, and -fsanitize=implicit-conversion doesn't catch it. Maybe just strike this sentence for now?

In fact... I think this is too much text to be adding to this bulleted list, which is just supposed to summarize the available checks. Maybe replace the description with

Signed integer overflow, where the result of a signed integer computation cannot be represented in its type. This includes all the checks covered by ``-ftrapv``, as well as checks for signed division overflow (``INT_MIN/-1``), but not checks for lossy implicit conversions performed before the computation (see ``-fsanitize=implicit-conversion``).
138–145

And here something like:

Unsigned integer overflow, where the result of an unsigned integer computation cannot be represented in its type. Unlike signed integer overflow, this is not undefined behavior, but it is often unintentional. This sanitizer does not check for lossy implicit conversions performed before such a computation (see ``-fsanitize=implicit-conversion``).
161

If we're going to list which sanitizers are enabled here, we should list them all:

Enables ``signed-integer-overflow``, ``unsigned-integer-overflow``, ``shift``, ``integer-divide-by-zero``, and ``implicit-integer-truncation``.
lib/CodeGen/CGExprScalar.cpp
960

I think it's generally better for the text in an assertion to describe the violated assumption directly:

"clang integer type lowered to non-integer llvm type"

968

I think you should only check DstType here. The point of the assert is that there is no such thing as a truncation to bool (conversion from integer to bool is a comparison against 0, and if we get here for such a case, there's a bug elsewhere). Other than that, bool is a perfectly-normal 1-bit unsigned integer type, and doesn't need to be treated as a special case.

lebedev.ri marked 9 inline comments as done.
lebedev.ri edited the summary of this revision. (Show Details)

Address last portion of @rsmith review notes.

@rsmith, @vsk, @erichkeane - thank you for the review!

lebedev.ri added inline comments.Jul 30 2018, 11:59 AM
docs/UndefinedBehaviorSanitizer.rst
134–135

I will assume you meant "lossy implicit conversions performed *after* the computation".

rsmith added inline comments.Jul 30 2018, 1:58 PM
docs/UndefinedBehaviorSanitizer.rst
134–135

I really meant "performed before", for cases like 4u / -2, where -2 is implicitly converted to UINT_MAX - 2 before the computation. Conversions that are performed after a computation aren't part of the computation at all, so I think it's much clearer that they're not in scope for this sanitizer.

lebedev.ri added inline comments.Jul 30 2018, 2:01 PM
docs/UndefinedBehaviorSanitizer.rst
134–135

Ok, with that additional explanation, i do see the error of my ways, and will re-adjust the docs accordingly.
Sorry.