The fundamental bug here is really slick. The static analyzer in the JIT incorrectly believes
Math.expm1(x)
can't return -0. But if x is -0, it can. That, in turn, means it believes
Object.is(Math.expm(x), -0)
must always be false. But if x is -0, it's true, not false. That, in turn, means that the JIT believes
array[Object.is(Math.expm(x), -0) * INDEX]
must be array[0], no matter what INDEX is. But if x is -0, it'll be array[INDEX]. That's a big problem, because the optimizer, guided by the static analyzer, removes the bounds check if the bounds check can't ever fail.
But it's not quite that simple, because another consequence of of the static analyzer's misperception is that
Object.is(Math.expm(x), -0) * INDEX
is the constant 0, no matter what value x takes and no matter what INDEX is, and the JIT will simply constant-fold 0 in for the whole expression, so the bounds check really won't matter.
But constant folding is an optimization, not a security boundary, and easily "defeated": replace the -0 constant in that expression with an object reference:
obj = { o: -0 }
Object.is(Math.expm(x), obj.o)
You can read that code and see that it's the constant -0, but the static analyzer needs to do escape analysis to make sure the object reference really does just evaluate to a constant, and escape analysis happens after the typing analysis, so the constant folding doesn't happen.
The end result of the bug is a sort of "black magic zero/one chimera" that, mixed into an expression, tricks the JIT into stripping bounds checks. It's an extremely cool exploit primitive. It's doubly cool because if you don't have Andrea's writeup or a really nuanced understanding of v8 internals, you could stare at that exploit for eternity and never understand why it works.
> The fundamental bug here is really slick. The static analyzer in the JIT incorrectly believes Math.expm1(x)
can't return -0.
I can't get past this part.
When a Googler "believes" Union(PlainNumber, NaN) represents the set of possible return values for a math function and commits that in the code, how is there not an automated set of tests that use one out of every other IEEE754-associated type as input to then check whether it generates output which falls outside the assumed set of types?
I mean in this case you've even got NegativeZero as its own type. What's even the point of having a type with a single value if you don't hurl it at every manually-entered optimization that it could conceivably invalidate?
I don't know, to me, this sounds like one of the more subtle examples of the kinds of mistakes that lead to security failures. Like, it might be an almost archetypical example of the "all bugs are security vulnerabilities" hypothesis. They got code execution from expm1!
But if you believe that this is an example of wanton abuse at Google, you can trade on that belief, and in a sense put your money where your mouth is, because this is a whole class of potential bugs, not just one bug; the same pattern will recur for other places where the v8 typer is wrong about the possible results of functions. Go do a sweep! If you find one, the value of the resulting bug might be pretty decent.
> it might be an almost archetypical example of the "all bugs are security vulnerabilities" hypothesis
This article will be my new go-to example when someone handwaves a bug away with a complacent “it’ll never happen” and “it’s not that big of a deal”. Yes it will, and yes it is.
certainly V8 tries to be correct and this bug will be fixed. Chromium's position is "security in depth". They know it's impossible to have zero bugs therefore the entire architure assumes there will be bugs and tries to prevent them from causing any harm. This is also why there are roughly 10x less code execution bugs in chrome vs other browsers. same number of bugs overall but most lead nowhere
I wouldn't be surprised if NegativeZero got introduced to fix some other bug along the same lines involving a different function, and when fixing that bug they neglected to notice that it applies to expm1 as well. Math.expm1 is... a bit obscure. I could certainly see myself making the same mistake.
> how is there not an automated set of tests that use one out of every other IEEE754-associated type as input to then check whether it generates output which falls outside the assumed set of types?
It's slightly worse than that. Math.expm1(-0) = -0 is explicitly called out as part of the standard[1]. You don't need to throw every IEEE754 at your functions to make sure they're all correct, but validating the explicitly defined corner cases is table stakes.
Hmmm! Wonder how hard it might be to make a build of v8 available that replaces assumes with asserts, and perhaps replaces code believed to be unreachable with assert(false)? If it's something like LLVM IR, where assume is just an intrinsic taking a Boolean expression, would seem relatively straightforwards- would probably need to run before every pass in the optimizer...but should be doable.
Here's what I don't get. Why isn't Math.expm1 just implemented in JavaScript?
Math.expm1 = (x) => Math.pow(Math.E, (x)) - 1;
With this monkey patched version, Math.expm1(-0) now returns 0. I've been writing JavaScript for a long time and I didn't even know Math.expm1 was a thing. Was it really necessary to implement this inside V8?
expm1 avoids catastrophic cancellation (due to finite precision floating point), and so is more accurate for x close to zero than naive(x) = exp(x) - 1, e.g. expm1(1e-100) != 0, but naive(1e-100) = 0.
Even good old C includes several functions that seem "redundant" at first glance [0] but are necessary for edge cases. I suppose this is similar to mechanics like fused multiply-add [1].
The reason expm1 exists is because that naive approach is numerically poor when x is small (then e^x is almost 1, and subtracting two almost equal values throws away significant digits and gives you an inaccurate result).
I don't know what the rules for JavaScript semantics are - this version will break if someone redefines `Math.pow`. Is that ok or does that break JavaScript semantics?
That's the wrong answer and your algorithm is bad. The point of expm1 is to be accurate for small arguments using the Taylor series or Chebeyshev polynomial representation.
I know what a Padé approximant is but I am not sure how it is relevant. expm1 is available as part of the math library in JavaScript, just as it is also available for C. You do not have to implement it yourself.
The exact implementation depends on your math library, but in glibc it appears to reduce the argument modulo log 2, and then uses an approximation found in part by the Remez algorithm for the exponential function on the range [0, 0.5 log2]. My assumption here is that the Remez algorithm will often be preferred over Padé, but I am not an expert on these things. The Padé approximant gives an approximation “near” a point but the Remez algorithm finds an approximation over an entire interval. In either case, the Remez algorithm is only used to construct one part of the function, and there is also some effort to propagate error from the argument reduction. The resulting algorithm claims <1 ULP error.
For matrix exponentiation you would need a library.
But it's not quite that simple, because another consequence of of the static analyzer's misperception is that
is the constant 0, no matter what value x takes and no matter what INDEX is, and the JIT will simply constant-fold 0 in for the whole expression, so the bounds check really won't matter.But constant folding is an optimization, not a security boundary, and easily "defeated": replace the -0 constant in that expression with an object reference:
You can read that code and see that it's the constant -0, but the static analyzer needs to do escape analysis to make sure the object reference really does just evaluate to a constant, and escape analysis happens after the typing analysis, so the constant folding doesn't happen.The end result of the bug is a sort of "black magic zero/one chimera" that, mixed into an expression, tricks the JIT into stripping bounds checks. It's an extremely cool exploit primitive. It's doubly cool because if you don't have Andrea's writeup or a really nuanced understanding of v8 internals, you could stare at that exploit for eternity and never understand why it works.