CairoVM runner is not checking Relocatable offset i16 overflow during runtime

[Okm165]

Bug Description

When running programs with array inputs, the Cairo VM loads the input into a newly allocated memory segment. However, if the input exceeds i16::MAX, an issue occurs where the runner uses an offset of type usize, allowing it to pass the checked_add checks. The problem arises because the Cairo VM’s registers are of type i16, which cannot hold values beyond i16::MAX. This results in overflow issues when the input exceeds the i16 limit.

Expected Behavior

The VM should handle inputs in a way that ensures memory addresses and offsets are properly checked against the i16 register limits, preventing overflows.

Proposed Solution

• Option 1: Change the Relocatable type from usize to i16, ensuring that all memory addresses conform to the i16 register limits.
• Option 2: Implement additional checks for i16 overflow to ensure the VM handles out-of-bound memory addresses gracefully without breaking the program.

Reference code can be found here.

The i16 registers design is detailed in section 2.4 of the Cairo Paper.

Additional Context

This overflow issue results from the disparity between the usize offset type in the runner and the i16 registers in the VM. Ensuring consistency or adding appropriate checks would prevent this problem.

Let me know your thoughts on this approach.

Cheers!

[Oppen]

A few comments:

1. The link doesn't link to the Cairo Paper, but to the Cairo Book.
2. From the actual Cairo Paper:

Therefore, Cairo implements option 1 above – there are no general-purpose registers, and all the operands of an instruction are memory cells. Thus, one Cairo instruction may deal with up to 3 values from the memory and perform one arithmetic operation (either addition or multiplication) on two of them, and store the result in the third.
Cairo has 2 address registers, called ap and fp, which are used for specifying which memory cells the instruction operates on. For each of the 3 values in an instruction, you can choose either an address of the form ap + off or fp + off where off is a constant offset in the range [−2^15, 2^15). Thus, an instruction may involve any 3 memory cells out of 2 · 2^16 = 131072. In many aspects, this is similar to having this many registers (implemented in a much cheaper way).
Accessing memory cells that cannot be described in the form above is possible using an instruction (see Section 5.2) that takes the value of a memory cell and treats it as the address of another memory cell. Note that the address space can be as large as the number of steps being executed.

Emphasis mine. As you may see, offsets are not mandated to be i16, but instead the appropriate addressing mode must be used when a larger offset is needed.

Further, from the original VM source code we can extract the explicit bound on segment size, which indirectly becomes the bound for the offset inside a given segment: 2^64, that is, a u64, or usize in most platforms Cairo will ever run.

[Okm165]

Sorry my bad copied link from wrong tab your is the one i intended to paste

[Okm165]

Ok i see you are right here let me try to reproduce the issue locally, will write soon.

[maciejka]

My guess is that Casm generated by the runner assumes that offset is always small and uses wrong addressing mode.

[maciejka]

It seems like this bug is caused by overflows in the runner. This issue can be closed.

[Oppen]

Fair enough.