Strange issue with postfix increment and array indexing

[lastmjs]

Describe the bug

While incorporating a sha224 library into one of my boa projects, I noticed the sha224 implementation was producing incorrect hashes when run through boa. With enough fiddling, I seem to have found a couple issues. This bug report highlights one of them. The code below describes how to reproduce it.

To Reproduce

Here is the code to run through boa, focusing on the original strToInt function. It is just one of the functions that was causing the sha224 hashing to be incorrect. This same or a similar problem manifests in 0.13 or on the main branch as of yesterday:

// https://github.com/litejs/crypto-lite
// THE MIT LICENSE

// Copyright (c) Lauri Rooden <lauri@rooden.ee>

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

function strToIntWithBug(str) {
    var i = 0;
    var arr = [];
    var len = arr.len = str.length;

    for (; i < len;) {
        arr[i>>2] = str.charCodeAt(i++)<<24 | str.charCodeAt(i++)<<16 | str.charCodeAt(i++)<<8 | str.charCodeAt(i++);
    }

    return arr;
}

function strToIntWithoutBug(str) {
    var i = 0
    var arr = [];
    var len = arr.len = str.length;

    for (; i < len;) {
        arr[i>>2] = str.charCodeAt(i)<<24 | str.charCodeAt(i+1)<<16 | str.charCodeAt(i+2)<<8 | str.charCodeAt(i+3);
        i += 4;
    }

    return arr;
}

JSON.stringify({
    strToIntWithBug: strToIntWithBug('hello'),
    strToIntWithoutBug: strToIntWithoutBug('hello')
});

The return result printed with Rust will be this:

Ok(
    String(
        "{\"strToIntWithBug\":[null,1751477356,1862270976],\"strToIntWithoutBug\":[1751477356,1862270976]}",
    ),
)

Expected behavior

There is an extra null element in the strToIntWithBug result. This element should not be there.

Build environment (please complete the following information):

• OS: Ubuntu 20.04
• Version: 0.13 or latest commits on main branch
• Target triple: wasm32-unknown-unknown or x86_64-unknown-linux-gnu
• Rustc version: rustc 1.58.1 (db9d1b20b 2022-01-20)

Additional context

A similar issue can be found here: #1918

[Razican]

I did some debugging here, and the reason behind this is the order in which we evaluate expressions. This code:

arr[i>>2] = str.charCodeAt(i++)<<24 | str.charCodeAt(i++)<<16 | str.charCodeAt(i++)<<8 | str.charCodeAt(i++);

In theory, the first thing that should get evaluated is arr[i>>2], which for the first iteration is arr[0 >> 2] or arr[0]. Then, we should evaluate the right hand side, which would increment i until it's 4.

But with Boa, we seem to be evaluating first the right hand side, and then the left hand side, which in the first iteration, arr[i>>2] is arr[4>>2] and therefore arr[1]. This means that it tries to set the second element of the array, and by default that creates a "null" element as the first element in arr[0].

[raskad]

This seems to be a very interesting issue. The following example returns different results in v8, spidermonkey and boa:

i = 0
arr = []
arr[i++] = i++

boa

arr[0] // undefined
arr[1] // 0

v8

arr[0] // undefined
arr[1] // 2

spidermonkey

arr[0] // 1
arr[1] // undefined

[Razican]

They are all wrong, right? I guess the correct result should be:

arr[0]; // 1
arr.length; // 1
i; // 2

[jedel1043]

They are all wrong, right? I guess the correct result should be:

arr[0]; // 1
arr.length; // 1
i; // 2

That's the correct result, but SpiderMonkey does get it right, since arr[1] === undefined implies that arr.length === 1, and both i++ should result in i === 2

[Razican]

From our VM perspective, this is tricky to get right, because we have to first calculate the object node (arr), then the field getter (i++, so i), and then the value (so, the result of adding 1 to i).

The way we do it right now is the inverse. We first calculate the value, then the field name, then the object node. This is much easier, because in a post-increment node, we can push the final result of adding 1 to i at the bottom of the stack, and use the rest of the stack to do the assignment.

But, since we need to first get the object node, then the field name calculation, and finally the value, the post-increment result needs to be "stored" until the whole field name gets calculated. This gets even more complex with expressions such as this one:

arr[i++][i++] = i++;

Which, it's the same as writing:

arr[0][1] = 2;
i = 3;

I'm a bit out of my depth on how to do this, to be honest xD if anyone has some ideas, I'm happy to read and try to implement it since the VM is definitely not my specialty, and it would be a nice learning opportunity for me.

[jedel1043]

Would it be feasible to treat in-place increments as syntax sugar?
I was thinking, maybe we could desugar this:

  arr[i++][i++] = i++;

into this

let 1i = i++;
let 2i = i++;
let 3i = i++;
arr [1i][2i] = 3i;

That way we don't need to juggle with the stack, we just need to extract the increments on parse and substitute the increments with variable names

[Razican]

This could be a posibility, yes, but we have not yet done any post-parsing / pre-compilation modification of the code. I guess this would be another phase. We could also add optimizations here too. So if we encounter 10+ 5, we could create the 15 constant, for example, and the execution would be faster.

[addisoncrump]

#1954 should handle this, but implementors should be careful that @jedel1043's solution is incomplete for scenarios like:

while ((arr[i++][i++] = i++) != 0) {}

It might be necessary to juggle the stack or to generate VM instructions which are not one-to-one with JS.

An alternative would be to pre-declare some variables and use a comma-operator, e.g.:

let 1i;
let 2i;
let 3i;
while (1i = i++, 2i = i++, 3i = i++, (arr[1i][2i] = 3i) != 0) {}

Which may work in all cases, though I haven't tested this obviously :)

[jedel1043]

#1954 should handle this, but implementors should be careful that @jedel1043's solution is incomplete for scenarios like:

while ((arr[i++][i++] = i++) != 0) {}

It might be necessary to juggle the stack or to generate VM instructions which are not one-to-one with JS.

An alternative would be to pre-declare some variables and use a comma-operator, e.g.:

let 1i;
let 2i;
let 3i;
while (1i = i++, 2i = i++, 3i = i++, (arr[1i][2i] = 3i) != 0) {}

Which may work in all cases, though I haven't tested this obviously :)

Or we could just put the increments at the end of the loop, I think.

let 1i = i++;
let 2i = i++;
let 3i = i++;
while (arr[1i][2i] = 3i){
    ... Statements ...
    1i = i++;
    2i = i++;
    3i = i++;
}

Interestingly, this is very close to how some languages desugar a for loop into a while loop

[lastmjs]

I believe this library is broken because of this issue: https://github.com/emn178/js-sha256

This is a pretty scary issue for our users, as any library could appear to function properly (no errors) but simply produce incorrect results.

[Razican]

Well, all libraries that have a bug produce incorrect results without giving any feedback that could indicate that a bug was triggered. The question is "how critical is the bug?" In this case, it seems that V8, one of the most used JS libraries has a similar bug to Boa too, so it seems it's either not so critical or very difficult to solve (which I think it's the case).

In any case, Boa is not ready for production use, as it can be seen from the sub 1.0 version number, and the "pre-release" marking in all the releases, so these bugs are expected. Note that even on the latest commit in the main branch, 40% of the official test suite is still failing, so we definitely have a ton of things to fix.

That said, this is on our radar, it's just tricky to get it right.

[lastmjs]

The code for js-sha256 works fine in V8 (Node.js). The bugs found in this issue with the libraries I've tested have never presented in V8 (Node.js) during my testing. I'm pretty sure I used Node.js and possibly Chrome to ensure that the issue was only with Boa.

This issue seems to indicate a critical bug that V8 (and I would assume the other major JS engines) do not have.

[Razican]

The code for js-sha256 works fine in V8 (Node.js). The bugs found in this issue with the libraries I've tested have never presented in V8 (Node.js) during my testing. I'm pretty sure I used Node.js and possibly Chrome to ensure that the issue was only with Boa.

This issue seems to indicate a critical bug that V8 (and I would assume the other major JS engines) do not have.

So, V8 has a bug, but it's not affecting this particular usage of the js-sha256 library. We have a different bug (but very much related), and in this case, it affects this library. What I mean is that a different library could break with V8 due to this bug, but many might have just been designed to work around the V8 bug, by testing them there.

We will try to fix this, of course, and I don't think we should release a 1.0 version before this gets fixed.

[lastmjs]

We suspect this is now breaking a keccak256 library for us, different hashes are produced in Boa and in Node. I find it highly unlikely that this bug is present in the other engines, as the JS engines do all kinds of crypto operations just fine with various libraries that the blockchain community relies on. But in Boa, we're often running into incorrect hashing outputs.

[Razican]

@jedel1043 @raskad do you think the solution offered above could be easily implemented in the byte compiler?

@lastmjs if you find resources to work on this, help is very much welcome.

[HalidOdat]

If no one is working on this, I'd like to try and solve this :)

[lastmjs]

I at least am not working on it, and I would love for this to be solved @HalidOdat

[addisoncrump]

I am revisiting the AST walking issue today. With AST walking, this should be a straightfoward rewrite by walking over the instructions and replacing with temporaries.