bug: fuzzer dict does not contain immutables

[mds1]

Component

Forge

Have you ensured that all of these are up to date?

• Foundry
• Foundryup

What version of Foundry are you on?

forge 0.2.0 (233ab70 2022-04-01T00:51:18.292928+00:00)

What command(s) is the bug in?

forge test

Operating System

macOS (amd)

Describe the bug

Below is a contract and test that have very little state, so you'd expect both tests to fail relatively quickly because the fuzzer should try using each owner address as input. However, this does not happen, and most of the time these tests pass, whether I use 100 or 100k fuzz runs. I have not yet investigated this, but potential causes:

1. Values are not actually being added to the dictionary
2. Values improperly encoded/formatted before being added
3. All random fuzz inputs (or other useless state, such as nonces, gas used, etc.) are being added to the dictionary, blowing up its size and making it less likely for the owner addresses to be used

pragma solidity 0.8.13;

import "ds-test/test.sol";
import "forge-std/Vm.sol";

contract FuzzerDict {
  // Immutables should get added to the dictionary.
  address public immutable immutableOwner;
  // Regular storage variables should also get added to the dictionary.
  address public storageOwner;

  constructor(address _immutableOwner, address _storageOwner) {
    immutableOwner = _immutableOwner;
    storageOwner = _storageOwner;
  }
}

contract FuzzerDictTest is DSTest {
  FuzzerDict fuzzerDict;
  Vm vm = Vm(HEVM_ADDRESS);

  function setUp() public {
    fuzzerDict = new FuzzerDict(address(100), address(200));
  }

  // Fuzzer should try `fuzzerDict.immutableOwner()` as input, causing this to fail
  function testImmutableOwner(address who) public {
    assertTrue(who != fuzzerDict.immutableOwner());
  }

  // Fuzzer should try `fuzzerDict.storageOwner()` as input, causing this to fail
  function testStorageOwner(address who) public {
    assertTrue(who != fuzzerDict.storageOwner());
  }
}

[mds1]

Here is a gist with the outputs from running RUST_LOG=foundry_evm=trace forge test --match-contract FuzzerDictTest. There are two files, one called debug-256-fuzz-runs.rs, and debug-100-fuzz-runs.rs: https://gist.github.com/mds1/9331b9a35e6d4a6da1f572457c517c93

I'm assuming rows with state are values added to the fuzzer's dict, and rows with calldata are the actual test inputs. Assuming that's true, in the 256 run example:

• address(100) and address(200) correspond to 0x00..064 and 0x00..0c8, and are not found anywhere in that file
• 0xb4c79dab8f259c7aee6e5b2aa729821864227e84 is the address of the FuzzerDictTest test contract. It shows up as state, but never as calldata
• 0xce71065d4017f316ec606fe4422e11eb2c47c246 is the address of the FuzzerDict contract. It never shows up anywhere

In the 1000 run example:

• 0x00...064 is added to the state and seems to get used as calldata since the testImmutableOwner failure is found. However, 0x00...0c8 is not seen anywhere and the testStorageOwner failure is not found
• Both FuzzerDictTest and FuzzerDict addresses are not seen anywhere

I have not repeated this analysis multiple times to confirm how consistent these fuzzer state/calldata values are

[onbjerg]

I don't think we handle immutables. How is the value of storageOwner added to the stack (not too familiar with this part of Solidity)? If it's not using PUSH*, then we won't find it:

• We add push bytes (bytes immediately after PUSH*)
• We add storage
• We add some information about addresses (i.e. addresses called)
• We add topics/data from logs

I'm not sure how we would handle immutables tbh

Edit: Took the liberty of editing the issue title to reflect that this is (most likely) an issue with immutables not being in the fuzz dict, not that the fuzz dict is broken in general

[mds1]

We add push bytes (bytes immediately after PUSH*)

So from the debugger I've confirmed immutableOwner is added with PUSH

storageOwner is added to the stack via an SLOAD, but given it's in storage I'd expect it to be added to the dict anyway?

Took the liberty of editing the issue title to reflect that this is (most likely) an issue with immutables not being in the fuzz dict, not that the fuzz dict is broken in general

The above results in that gist are actually showing the opposite. With 1000 fuzz runs we successfully found the failure in testImmutableOwner which indicates immutables are in the dict, and we do not find the failure in testStorageOwner indicating storage was not in the dict.

I just ran the tests using the default 256 runs 10 times. Because the state space is so small here I'd expect both to tests to fail almost always (to clarify, we are looking for failures here). However, in practice testImmutableOwner only failed once, and testStorageOwner never failed

[onbjerg]

That's really weird and should not be the case at all. I'll have to investigate, but if you want to debug further using dbg!() or something, the relevant functions that lift state are:

For building the initial state from DB (slots, push bytes etc.):

https://github.com/gakonst/foundry/blob/233ab70b92e4fa451e251c72983af7a0c9f771db/evm/src/fuzz/strategies/state.rs#L50

For lifting state from calls:

https://github.com/gakonst/foundry/blob/233ab70b92e4fa451e251c72983af7a0c9f771db/evm/src/fuzz/strategies/state.rs#L78

Edit: Looking over your trace again, we select bytes(0) a lot, which is really odd, too.

[mds1]

Great, thanks! I'll try to take a look this weekend / early next week if you don't beat me to it 🙂

Am I interpreting that trace correctly in that state rows show the data being added to the dict, and calldata rows are the fuzzer inputs used for that test run? That doesn't seem exactly correct since the number of calldata rows does not seem to equal the number of test runs (e.g. in the 256 run file there's 316 calldata entries and 196 state entries, even though 256 runs of each test were executed)