Fix undefined behavior in CheckedInt

RESOLVED FIXED in mozilla16

Status

()

Core
MFBT
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: bjacob, Assigned: bjacob)

Tracking

unspecified
mozilla16
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(4 attachments)

Created attachment 636770 [details] [diff] [review]
fix undefined behavior in CheckedInt

According to IOC,

 http://embed.cs.utah.edu/ioc/

while running TestCheckedInt, we are relying on undefined behavior in CheckedInt's +, -, * operators. Sample error:

CLANG ARITHMETIC UNDEFINED at <./mozilla/CheckedInt.h, (690:1)> : Op: *, Reason : Signed Multiplication Overflow, BINARY OPERATION: left (int32): 65535 right (int32): 65535 


The precise issue is in the operators generated by the MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR macro:

#define MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP)                \
template<typename T>                                                  \
inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs,            \
                                 const CheckedInt<T> &rhs)            \
{                                                                     \
  T x = lhs.mValue;                                                   \
  T y = rhs.mValue;                                                   \
  T result = x OP y;                                                  \
  T isOpValid = detail::Is##NAME##Valid(x, y);                        \
  /* Help the compiler perform RVO (return value optimization). */    \
  return CheckedInt<T>(result,                                        \
                       lhs.mIsValid && rhs.mIsValid && isOpValid);    \
}

The problem is that |result| is unconditionally computed, regardless of |isOpValid|.

The fix is to rewrite this as:

#define MOZ_CHECKEDINT_BASIC_BINARY_OPERATOR(NAME, OP)                \
template<typename T>                                                  \
inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs,            \
                                 const CheckedInt<T> &rhs)            \
{                                                                     \
  T x = lhs.mValue;                                                   \
  T y = rhs.mValue;                                                   \
  T isOpValid = detail::Is##NAME##Valid(x, y);                        \
  if (isOpValid) {                                                    \
    T result = x OP y;                                                \
    return CheckedInt<T>(result, lhs.mIsValid && rhs.mIsValid);       \
  } else {                                                            \
    return CheckedInt<T>(T(0), false);                                \
  }                                                                   \
}
Attachment #636770 - Flags: review?(jwalden+bmo)
(Assignee)

Updated

5 years ago
OS: Linux → All
Hardware: x86_64 → All
(Assignee)

Comment 1

5 years ago
Created attachment 636776 [details] [diff] [review]
another fix in the unit test

This was also found by IOC. Now it runs cleanly without errors.

The issue was that for signed types of size >= the size of |int|, computing x<<1 for x = the minimum representable value is undefined behavior. (This is not an issue for smaller types due to implicit conversion to int). Anyway, I fixed this part of the unit test by switching to unsigned types since this is purely bit-field manipulation.
(Assignee)

Updated

5 years ago
Attachment #636776 - Flags: review?(jwalden+bmo)
(Assignee)

Comment 2

5 years ago
Ken, Mo, you'll probably want to sync WebKit's copy with this. It might be easiest to wait for this to land in mozilla-central and then copy the files, unless you have substantial local changes.

Comment 3

5 years ago
Noted.  I'll do the sync.  Thanks for the heads up
Blocks: 633560
Comment on attachment 636770 [details] [diff] [review]
fix undefined behavior in CheckedInt

Review of attachment 636770 [details] [diff] [review]:
-----------------------------------------------------------------

::: mfbt/CheckedInt.h
@@ +683,5 @@
> +    T result = x OP y;                                                \
> +    return CheckedInt<T>(result, lhs.mIsValid && rhs.mIsValid);       \
> +  } else {                                                            \
> +    return CheckedInt<T>(T(0), false);                                \
> +  }                                                                   \

Let's write this this way, to get rid of else-after-return oddities, to reduce indentation, and to make the invalidity case read as a mere side show:

  if (!detail::Is##NAME##Valid(x, y))
    return CheckedInt<T>(T(0), false);
  return CheckedInt<T>(T(x OP y), lhs.mIsValid && rhs.mIsValid);

(I'm only assuming the T() on x OP y is necessary, don't add it if it's not needed.)
Attachment #636770 - Flags: review?(jwalden+bmo) → review+
Attachment #636776 - Flags: review?(jwalden+bmo) → review+
(Assignee)

Comment 5

5 years ago
http://hg.mozilla.org/integration/mozilla-inbound/rev/d0d426929fda
http://hg.mozilla.org/integration/mozilla-inbound/rev/79f74e4d885c
(Assignee)

Updated

5 years ago
Assignee: nobody → bjacob
Target Milestone: --- → mozilla16
https://hg.mozilla.org/mozilla-central/rev/d0d426929fda
https://hg.mozilla.org/mozilla-central/rev/79f74e4d885c
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
(In reply to Jeff Walden [:Waldo] (busy, try to prefer other reviewers if possible) from comment #4)
> Comment on attachment 636770 [details] [diff] [review]
> fix undefined behavior in CheckedInt
> 
> Review of attachment 636770 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> ::: mfbt/CheckedInt.h
> @@ +683,5 @@
> > +    T result = x OP y;                                                \
> > +    return CheckedInt<T>(result, lhs.mIsValid && rhs.mIsValid);       \
> > +  } else {                                                            \
> > +    return CheckedInt<T>(T(0), false);                                \
> > +  }                                                                   \
> 
> Let's write this this way, to get rid of else-after-return oddities, to
> reduce indentation, and to make the invalidity case read as a mere side show:
> 
>   if (!detail::Is##NAME##Valid(x, y))
>     return CheckedInt<T>(T(0), false);
>   return CheckedInt<T>(T(x OP y), lhs.mIsValid && rhs.mIsValid);
> 
> (I'm only assuming the T() on x OP y is necessary, don't add it if it's not
> needed.)

This doesn't appear to have been addressed...
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
(Assignee)

Comment 8

5 years ago
Oops. Sorry, doing it ASAP.
(Assignee)

Comment 9

5 years ago
Created attachment 640068 [details] [diff] [review]
apply Jeff's review comment; further simplification; remove the separate operator/ implementation

So it turned out that while doing this fix, one could go a bit further, so there seems to be just enough here to ask for a new review.
Attachment #640068 - Flags: review?(Ms2ger)
Comment on attachment 640068 [details] [diff] [review]
apply Jeff's review comment; further simplification; remove the separate operator/ implementation

Review of attachment 640068 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM with the braces added, thanks.

::: mfbt/CheckedInt.h
@@ +712,5 @@
>  inline CheckedInt<T> operator OP(const CheckedInt<T> &lhs,            \
>                                   const CheckedInt<T> &rhs)            \
>  {                                                                     \
> +  if (!detail::Is##NAME##Valid(lhs.mValue, rhs.mValue))               \
> +    return CheckedInt<T>(0, false);                                   \

{}
Attachment #640068 - Flags: review?(Ms2ger) → review+
From mfbt/STYLE:

== Bracing ==

Don't brace single statements.

  if (y == 7)
    return 3;
  for (size_t i = 0; i < 5; i++)
    frob(i);

But do brace them if the statement (or condition(s) or any additional
consequents, if the braces would be associated with an if statement) occupies
multiple lines.


-> So I don't think that braces are needed here.
http://hg.mozilla.org/integration/mozilla-inbound/rev/5a372bbee65c

(With blank line after the if)
Created attachment 640070 [details] [diff] [review]
HasSignBit should return bool

Just something I noticed while glancing at this code. This is a remnant of an earlier design where we tried to keep everything of sign T to avoid useless conversions. We're no longer doing that. This HasSignBit function is only used in 2 occurences in this file, where its return value is used as a bool anyway.
Attachment #640070 - Flags: review?(Ms2ger)
Comment on attachment 640070 [details] [diff] [review]
HasSignBit should return bool

Review of attachment 640070 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks.

::: mfbt/CheckedInt.h
@@ +242,5 @@
>   * Ideas taken from IntegerLib, code different.
>   */
>  
>  // Bitwise ops may return a larger type, so it's good to use these inline
>  // helpers guaranteeing that the result is really of type T.

Move this down, I guess.
Attachment #640070 - Flags: review?(Ms2ger) → review+
http://hg.mozilla.org/integration/mozilla-inbound/rev/3cfacdaa3438
https://hg.mozilla.org/mozilla-central/rev/5a372bbee65c
https://hg.mozilla.org/mozilla-central/rev/3cfacdaa3438
Status: REOPENED → RESOLVED
Last Resolved: 5 years ago5 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.