Skip to content

SSA Interpreter: indexing with overflow succeeds #9856

@aakoshh

Description

@aakoshh

Aim

Testing #9853

The following program succeeds in the SSA interpreter, but fails with ACIR and Brillig

fn main() -> pub bool {
    let mut e: [(Field, bool); 1] = [((-1), true)];
    e[2147483648_u32].1
}

Expected Behavior

The interpreter should fail with Index OOB.

Bug

cargo run -q -p nargo_cli -- interpret --force --silence-warnings --show-ssa
After Initial SSA:
acir(inline) fn main f0 {
  b0():
    v2 = make_array [Field -1, u1 1] : [(Field, u1); 1]
    v3 = allocate -> &mut [(Field, u1); 1]
    store v2 at v3
    v4 = load v3 -> [(Field, u1); 1]
    v7 = unchecked_mul u32 2147483648, u32 2
    v8 = array_get v4, index v7 -> Field
    v10 = unchecked_add v7, u32 1
    v11 = array_get v4, index v10 -> u1
    return v11
}

--- Interpreter result after Initial SSA:
Ok(u1 1)
---
...
--- Interpreter result after Dead Instruction Elimination (step 44):
Ok(u1 1)
---
After Verifying no dynamic array indices to reference value elements (step 45):
acir(inline) predicate_pure fn main f0 {
  b0():
    v2 = make_array [Field -1, u1 1] : [(Field, u1); 1]
    v5 = unchecked_mul u32 2147483648, u32 2
    v7 = unchecked_add v5, u32 1
    v8 = array_get v2, index v7 -> u1
    return v8
}

--- Interpreter result after Verifying no dynamic array indices to reference value elements (step 45):
Ok(u1 1)
---

By contrast in ACIR we get the following error:

cargo run -q -p nargo_cli -- execute --force --silence-warnings 
error: Index out of bounds, array has size 2, but index was 4294967297
  ┌─ src/main.nr:3:5

3 │     e[2147483648_u32].1
  │     -----------------

  = Call stack:
    1. src/main.nr:3:5

Failed to solve program: 'Index out of bounds, array has size 2, but index was 4294967297'

I assume the way ACIR implements unchecked_add is by using a Field, because e.g. if we try to index by u32::MAX_VALUE it complains that array has size 2, but index was 8589934591, whereas the SSA interpreter wraps around.

I'm not sure if unchecked_add in ACIR should not wrap around instead as well. It looks like Brillig does wrap around.

To Reproduce

See above.

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

None

Blocker Context

No response

Nargo Version

nargo version = 1.0.0-beta.12 noirc version = 1.0.0-beta.12+affa9727ac36f708b4e59db5c7c18c817446acb2 (git version hash: affa972, is dirty: true)

NoirJS Version

No response

Proving Backend Tooling & Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response

Metadata

Metadata

Assignees

Labels

bugSomething isn't working

Type

No type

Projects

Status

📋 Backlog

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions