[compiler] Sentinel-initialized scan + StorageMap default: out-of-bounds write at key 16 in compiled 15-puzzle (v26.1.0, v26.2.0)
- Dominant language
- Rust
- Stars
- 1.7k
- Forks
- 218
- Avg merge
- 1d 1h
- Merged PRs (30d)
- 9
Description
## Summary
Two behaviors combine to produce a silent **out-of-bounds storage write that the Fe source does not authorize**:
1. A sentinel-initialized empty-cell scan (`let mut j: usize = 16`) falls through when no element matches — execution continues with the out-of-range sentinel `16`.
2. `StorageMap.get()` returns the default value for ANY key. Using the sentinel as a key into an adjacency table whose default is `0`, combined with an adjacency predicate where "movable to cell 0" evaluates true for the all-zero encoding, accepts a move **with no empty cell on the board** and then writes `board.set(key: 16, val)` — outside the modeled 0..15 domain.
In a packed-u256 board representation this pollutes bits ≥64 of the word; with other layouts it could hit neighboring logical fields.
## Minimal reproduction
Fe source pattern (abridged from a real 15-puzzle contract):
```fe
fn find_empty(self) -> usize {
let mut j: usize = 16
let mut i: usize = 0
while i < 16 {
if self.board[i] == 0 { j = i }
i += 1
}
j // can be 16 if no zero exists
}
pub fn move_field(mut self, index: u256) {
// bounds check on `index` only; NOT on find_empty result
let empty_idx = self.find_empty()
let encoded = ADJACENCY[empty_idx] // OOB read when empty_idx == 16 → default 0
if !is_movable_to(encoded, index as u256) { revert(Error::NotMovable) }
let val = self.board[index]
self.board.set(index, 0)
self.board.set(empty_idx, val) // OOB WRITE at key 16
}
```
`is_movable_to(0, target)` decodes slot words of the default-0 encoding as "movable to target 0" → true for `index == 0`.
### Steps
1. Deploy the compiled GameBitboard (v26.2.0 build) with constructor `(validator: , board: 0x1FEDCBA987654321)` — note: **no zero nibble**.
2. Call selector `0x8bf02f32` (`moveField(uint256)`) with arg `uint256(0)`.
3. Call SUCCEEDS (source semantics say it must revert `NotMovable`).
4. Storage slot 1 changes from `0x…1FEDCBA987654321` to `0x…11fedcba987654320` — nibble 0 zeroed AND new nibble written at bits 64–67 ("cell 16" = shift 64).
## Versions affected
- **fe v26.1.0** — confirmed (this build is deployed on Ethereum mainnet by the Bountiful bounty contracts)
- **fe v26.2.0** (commit 1fffb9e, official release binary, macOS arm64) — confirmed identical behavior; not fixed
## Impact
Any fe contract combining a sentinel-initialized scan with a StorageMap lookup keyed by the scan result silently accepts inputs its source logic rejects and writes storage outside the modeled domain. Severity depends on layout: packed words corrupt adjacent bit-fields; multiple maps sharing a base word could alias unrelated entries.
Found during an independent audit of the Bountiful bug-bounty contracts (the audited instance itself cannot be exploited on mainnet because its boards are fixed and valid, but the compiler-level pattern generalizes).
Full differential harness and dual-version regression test available on request.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start with the compiler paths for StorageMap.get(), StorageMap.set(), and indexed access, then reproduce the v26.2.0 GameBitboard case using the stated constructor and moveField(uint256) call. Compare the compiled behavior with the Fe source expectation that the call reverts NotMovable. Done means the sentinel case cannot perform the out-of-bounds write and a regression test covers the no-zero board.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100