I extended --ion-check-range-analysis to include checking for Beta nodes. This turned up some cases where range analysis wasn't setting the max_exponent_ field properly. I have not yet done any analysis to determine whether the bugs found are actually security-relevant, but since the bugs are in range analysis code, and they're present in various branches, I'm filing it as a protected bug to be on the safe side.

Comment on attachment 798626 [details] [diff] [review] range-make-infinite.patch [Security approval request comment] How easily could an exploit be constructed based on the patch? Not trivially. It's just an incorrect range from range analysis, and the patches here only show how to observe it with the help of --ion-check-range-analysis, so it would take some creativity to construct a testcase which observes the bug without that flag, and in a security-relevant way. Do comments in the patch, the check-in comment, or tests included in the patch paint a bulls-eye on the security problem? I don't think so. This bug was only found with --ion-check-range-analysis, so while it's theoretically exploitable without that, it's probably not easy. Which older supported branches are affected by this flaw? It appears this flaw is in all branches back to Firefox 23. If not all supported branches, which bug introduced the flaw? It appears to go back to bug 699883. Do you have backports for the affected branches? If not, how different, hard to create, and risky will they be? The patch easily backports to all affected branches. mozilla-release requires a small adjustment due to the ion->jit rename. How likely is this patch to cause regressions; how much testing does it need? It is unlikely to cause regressions. This code hasn't changed a lot in several releases, so the fix is very likely to have the same effect in all of them.

(In reply to Dan Gohman [:sunfish] from comment #0) > I extended --ion-check-range-analysis to include checking for Beta nodes. > This turned up some cases where range analysis wasn't setting the > max_exponent_ field properly. From what I knew, Beta Nodes had an incorrect max_exponent of 32 for int, I don't know if this is also the case for doubles. The only invariant that we want to maintain for security reasons is that max_exponent must remain an *over approximation*. Now, not having this invariant means that one can fool the JS engine in truncating operations which were not supposed to be truncated. Notice that as soon as the max_exponent reach 32, there is no way to make it go down except with an explicit truncate.

Comment on attachment 798628 [details] [diff] [review] This patch contains the new dynamic checks. Review of attachment 798628 [details] [diff] [review]: ----------------------------------------------------------------- This looks good except for the duplication of the Range pointer on the LIR nodes. ::: js/src/jit/LIR-Common.h @@ +4973,5 @@ > }; > > class LAssertRangeV : public LInstructionHelper<0, BOX_PIECES, 3> > { > + const Range *range_; Please undo any modification of this file, we otherwise we would have it twice in memory. Remember that the MIR is still alive at the code gen, there is no need to duplicate anything. The LIR is just some meta data of the MIR used by the register allocator. ::: js/src/jit/Lowering.cpp @@ -2477,5 @@ > MOZ_ASSUME_UNREACHABLE("Unexpected Range for MIRType"); > break; > } > > - lir->setMir(ins); I don't understand why?

Comment on attachment 798626 [details] [diff] [review] range-make-infinite.patch Review of attachment 798626 [details] [diff] [review]: ----------------------------------------------------------------- ::: js/src/jit/RangeAnalysis.cpp @@ +340,5 @@ > > Range *r = new Range( > newLower, newUpper, > lhs->decimal_ && rhs->decimal_, > Min(lhs->max_exponent_, rhs->max_exponent_)); If this rule is not wrong (it does not feel as being wrong from my point of view), then one of the input is wrong. ::: js/src/jit/RangeAnalysis.h @@ +234,5 @@ > > inline void makeLowerInfinite() { > lower_infinite_ = true; > lower_ = JSVAL_INT_MIN; > + max_exponent_ = MaxDoubleExponent; Doing so would be terrible, as this will disable the truncate phase.

Comment on attachment 798626 [details] [diff] [review] range-make-infinite.patch There is no need to ask for sec-approval before getting an r+ on the patch.

(In reply to Nicolas B. Pierron [:nbp] from comment #5) > Comment on attachment 798626 [details] [diff] [review] > range-make-infinite.patch > > Review of attachment 798626 [details] [diff] [review]: > ----------------------------------------------------------------- > > ::: js/src/jit/RangeAnalysis.cpp > @@ +340,5 @@ > > > > Range *r = new Range( > > newLower, newUpper, > > lhs->decimal_ && rhs->decimal_, > > Min(lhs->max_exponent_, rhs->max_exponent_)); > > If this rule is not wrong (it does not feel as being wrong from my point of > view), then one of the input is wrong. I think the real problem here is that there are many places in the Range code where it's unclear whether the code should be overriding the exponent by inferring a value from lower() and upper(), or whether it should be trusting the given exponent. My patch on bug 909528 is my initial attempt to clear up this confusion. > > ::: js/src/jit/RangeAnalysis.h > @@ +234,5 @@ > > > > inline void makeLowerInfinite() { > > lower_infinite_ = true; > > lower_ = JSVAL_INT_MIN; > > + max_exponent_ = MaxDoubleExponent; > > Doing so would be terrible, as this will disable the truncate phase. Looking at how makeLowerInfinite() is used, I don't see this. Values which have had makeLowerInfinite() called on their range aren't automatically safe to truncate anyway.

(In reply to Nicolas B. Pierron [:nbp] from comment #4) > Comment on attachment 798628 [details] [diff] [review] > This patch contains the new dynamic checks. > > Review of attachment 798628 [details] [diff] [review]: > ----------------------------------------------------------------- > > This looks good except for the duplication of the Range pointer on the LIR > nodes. > > ::: js/src/jit/LIR-Common.h > @@ +4973,5 @@ > > }; > > > > class LAssertRangeV : public LInstructionHelper<0, BOX_PIECES, 3> > > { > > + const Range *range_; > > Please undo any modification of this file, we otherwise we would have it > twice in memory. > Remember that the MIR is still alive at the code gen, there is no need to > duplicate anything. > > The LIR is just some meta data of the MIR used by the register allocator. I didn't see a need to be concerned about memory usage for AssertRange nodes, but your suggestion makes sense. Attached is an updated patch that works this way. > ::: js/src/jit/Lowering.cpp > @@ -2477,5 @@ > > MOZ_ASSUME_UNREACHABLE("Unexpected Range for MIRType"); > > break; > > } > > > > - lir->setMir(ins); > > I don't understand why? It made sense when the LIR was carrying its own range. Now that it's using the MIR node for the range, I reverted this.

(In reply to Dan Gohman [:sunfish] from comment #7) > (In reply to Nicolas B. Pierron [:nbp] from comment #5) > > Comment on attachment 798626 [details] [diff] [review] > > range-make-infinite.patch > > > > Review of attachment 798626 [details] [diff] [review]: > > ----------------------------------------------------------------- > > > > ::: js/src/jit/RangeAnalysis.cpp > > @@ +340,5 @@ > > > > > > Range *r = new Range( > > > newLower, newUpper, > > > lhs->decimal_ && rhs->decimal_, > > > Min(lhs->max_exponent_, rhs->max_exponent_)); > > > > If this rule is not wrong (it does not feel as being wrong from my point of > > view), then one of the input is wrong. > > I think the real problem here is that there are many places in the Range > code where it's unclear whether the code should be overriding the exponent > by inferring a value from lower() and upper(), or whether it should be > trusting the given exponent. The exponent is an over approximation, and we should always compute another over-approximation based on the exponent. We cannot use lower() and upper() to compute the exponent as these functions are returning discrete values which are outside the range of the exponent. The only case where lower() and upper() can be used, is when we know that these values are not open on the boundaries of the int32 range. > > > > ::: js/src/jit/RangeAnalysis.h > > @@ +234,5 @@ > > > > > > inline void makeLowerInfinite() { > > > lower_infinite_ = true; > > > lower_ = JSVAL_INT_MIN; > > > + max_exponent_ = MaxDoubleExponent; > > > > Doing so would be terrible, as this will disable the truncate phase. > > Looking at how makeLowerInfinite() is used, I don't see this. Values which > have had makeLowerInfinite() called on their range aren't automatically safe > to truncate anyway. I agree, it can have a fractional part. But even if a value is marked as LowerInfinite of the int32 range, it can still have a know and precise exponent. The infinite are only related to the int32 range, and nothing else. They are in no way meant to encode a double infinity. The only way to represent a double infinity is to use the max_exponent_ field. So, makeLowerInfinite should not manipulate the max_exponent field except resetting it to MaxInt32Exponent if it is lower.

Comment on attachment 800801 [details] [diff] [review] Updated per review feedback Review of attachment 800801 [details] [diff] [review]: ----------------------------------------------------------------- r=me, with the following fix applied. ::: js/src/jit/RangeAnalysis.cpp @@ +1663,5 @@ > + MInstructionIterator insertIter = iter; > + while (insertIter->isBeta()) > + insertIter++; > + > + block->insertAfter(*insertIter, guard); Note that the previous loop will walk until we reach a non-beta node. Such instruction can be control flow instruction which are supposed to mark the end of the instruction list. Also note that a control flow instruction has no range, which explain why the previous code was still safe. Here, you want to insert the MAssertRange before the insertIter if it has been used to walk any (beta) instructions. if (*insertIter == *iter) block->insertAfter(…, …); else block->insertBefore(…, …);

(In reply to Nicolas B. Pierron [:nbp] from comment #9) > (In reply to Dan Gohman [:sunfish] from comment #7) > > (In reply to Nicolas B. Pierron [:nbp] from comment #5) > > > Comment on attachment 798626 [details] [diff] [review] > > > range-make-infinite.patch > > > > > > Review of attachment 798626 [details] [diff] [review]: > > > ----------------------------------------------------------------- > > > > > > ::: js/src/jit/RangeAnalysis.cpp > > > @@ +340,5 @@ > > > > > > > > Range *r = new Range( > > > > newLower, newUpper, > > > > lhs->decimal_ && rhs->decimal_, > > > > Min(lhs->max_exponent_, rhs->max_exponent_)); > > > > > > If this rule is not wrong (it does not feel as being wrong from my point of > > > view), then one of the input is wrong. > > > > I think the real problem here is that there are many places in the Range > > code where it's unclear whether the code should be overriding the exponent > > by inferring a value from lower() and upper(), or whether it should be > > trusting the given exponent. > > The exponent is an over approximation, and we should always compute another > over-approximation based on the exponent. > We cannot use lower() and upper() to compute the exponent as these functions > are returning discrete values which are outside the range of the exponent. > > The only case where lower() and upper() can be used, is when we know that > these values are not open on the boundaries of the int32 range. I think you're getting confused by this code in the same way that I was :-}. The code quoted above has computed what intends to be the new values for lower_ and upper_. When that range is unbounded, those fields will have the value INT32_MIN and INT32_MAX, respectively. However, in Range's constructor, the arguments aren't just interpreted as the initialization for lower_ and upper_. They are interpreted as an actual bound on the range. So the constructor assumes that the value is actually bounded by [INT32_MIN,INT32_MAX], and it overrides the max_exponent value accordingly. Which is wrong, because it's actually supposed to be unbounded in that case. This is a clear example of the kind of API subtly that I aimed to address with my patch to bug 909528. I don't think it's quite right yet, but I think something in that direction is needed. > > > > > > > ::: js/src/jit/RangeAnalysis.h > > > @@ +234,5 @@ > > > > > > > > inline void makeLowerInfinite() { > > > > lower_infinite_ = true; > > > > lower_ = JSVAL_INT_MIN; > > > > + max_exponent_ = MaxDoubleExponent; > > > > > > Doing so would be terrible, as this will disable the truncate phase. > > > > Looking at how makeLowerInfinite() is used, I don't see this. Values which > > have had makeLowerInfinite() called on their range aren't automatically safe > > to truncate anyway. > > I agree, it can have a fractional part. But even if a value is marked as > LowerInfinite of the int32 range, it can still have a know and precise > exponent. > > The infinite are only related to the int32 range, and nothing else. They > are in no way meant to encode a double infinity. The only way to represent > a double infinity is to use the max_exponent_ field. > > So, makeLowerInfinite should not manipulate the max_exponent field except > resetting it to MaxInt32Exponent if it is lower. This change is not about fractional values. makeLowerInfinite is called specifically when the value is not bounded by [INT32_MIN,INT32_MAX], so MaxInt32Exponent is not appropriate.

(In reply to Dan Gohman [:sunfish] from comment #11) > (In reply to Nicolas B. Pierron [:nbp] from comment #9) > > (In reply to Dan Gohman [:sunfish] from comment #7) > > > (In reply to Nicolas B. Pierron [:nbp] from comment #5) > > > > Comment on attachment 798626 [details] [diff] [review] > > > > range-make-infinite.patch > > > > > > > > Review of attachment 798626 [details] [diff] [review]: > > > > ----------------------------------------------------------------- > > > > > > > > ::: js/src/jit/RangeAnalysis.cpp > > > > @@ +340,5 @@ > > > > > > > > > > Range *r = new Range( > > > > > newLower, newUpper, > > > > > lhs->decimal_ && rhs->decimal_, > > > > > Min(lhs->max_exponent_, rhs->max_exponent_)); > > > > > > > > If this rule is not wrong (it does not feel as being wrong from my point of > > > > view), then one of the input is wrong. > > > > > > I think the real problem here is that there are many places in the Range > > > code where it's unclear whether the code should be overriding the exponent > > > by inferring a value from lower() and upper(), or whether it should be > > > trusting the given exponent. > > > > The exponent is an over approximation, and we should always compute another > > over-approximation based on the exponent. > > We cannot use lower() and upper() to compute the exponent as these functions > > are returning discrete values which are outside the range of the exponent. > > > > The only case where lower() and upper() can be used, is when we know that > > these values are not open on the boundaries of the int32 range. > > I think you're getting confused by this code in the same way that I was :-}. > > The code quoted above has computed what intends to be the new values for > lower_ and upper_. When that range is unbounded, those fields will have the > value INT32_MIN and INT32_MAX, respectively. However, in Range's > constructor, the arguments aren't just interpreted as the initialization for > lower_ and upper_. They are interpreted as an actual bound on the range. So > the constructor assumes that the value is actually bounded by > [INT32_MIN,INT32_MAX], and it overrides the max_exponent value accordingly. > Which is wrong, because it's actually supposed to be unbounded in that case. I think we can solve this problem by changing the computation of newLower & newUpper by adding the infinity flags to them. int64_t newLower = Max(lhs->lower_ - lhs->lower_infinity_, rhs->lower_ - rhs->lower_infinity_); int64_t newUpper = Min(lhs->upper_ + lhs->upper_infinity_, rhs->upper_ + rhs->upper_infinity_); In which case the infinity flags would be carried over, and the exponent would be computed correctly.

(In reply to Dan Gohman [:sunfish] from comment #11) > (In reply to Nicolas B. Pierron [:nbp] from comment #9) > > (In reply to Dan Gohman [:sunfish] from comment #7) > > > (In reply to Nicolas B. Pierron [:nbp] from comment #5) > > > > > > > > ::: js/src/jit/RangeAnalysis.h > > > > @@ +234,5 @@ > > > > > > > > > > inline void makeLowerInfinite() { > > > > > lower_infinite_ = true; > > > > > lower_ = JSVAL_INT_MIN; > > > > > + max_exponent_ = MaxDoubleExponent; > > > > > > > > Doing so would be terrible, as this will disable the truncate phase. > > > > > > Looking at how makeLowerInfinite() is used, I don't see this. Values which > > > have had makeLowerInfinite() called on their range aren't automatically safe > > > to truncate anyway. > > > > I agree, it can have a fractional part. But even if a value is marked as > > LowerInfinite of the int32 range, it can still have a know and precise > > exponent. > > > > The infinite are only related to the int32 range, and nothing else. They > > are in no way meant to encode a double infinity. The only way to represent > > a double infinity is to use the max_exponent_ field. > > > > So, makeLowerInfinite should not manipulate the max_exponent field except > > resetting it to MaxInt32Exponent if it is lower. > > This change is not about fractional values. makeLowerInfinite is called > specifically when the value is not bounded by [INT32_MIN,INT32_MAX], so > MaxInt32Exponent is not appropriate. I agree, this function is called when the range is not bounded Int32 range, but this is not a reason to over-approximate it to MaxDoubleExponent, as such approximation will forbid any truncate optimizations which are relying on values which might be out-side the Int32 range, which are still representable on the mantissa of a double. So, we should not set the max_exponent to MaxDoubleExponent in these functions.

It sounds like there are no known security problems here, so I'm going to mark this audit. Please adjust the rating or comment if it is scarier than that.

Fixing this properly will be easier once the changes in bug 915846 are in.

The fixes are now just checked into mozilla-central as part of bug 915846. I can backport things if desired, but it sounds like that's not important here.