feat(invariant): Support coverage-guided fuzzing

[QiuhaoLi]

Component

Forge

Describe the feature you would like

Currently, the forge fuzz testing and invariant testing don’t support coverage-guided fuzzing, which could generally improve the fuzzing performance. The forge fuzzer can’t find the correct sequence B(2)->C(3)->A(1)->D(4) with 10000 runs for the code below:

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;

import {Test, console} from "forge-std/Test.sol";

contract Puzzle {
    uint256 private counter;
    bool public hacked; // B(2)->C(3)->A(1)->D(4)

    function A(uint256 x) external {
        if (counter == 2 && x == 1) counter++; else counter = 0;
    }
    function B(uint256 x) external {
        if (counter == 0 && x == 2) counter++;
    }
    function C(uint256 x) external {
        if (counter == 1 && x == 3) counter++; else counter = 0;
    }
    function D(uint256 x) external {
        if (counter == 3 && x == 4) hacked = true; else counter = 0;
    }
}
contract CounterTest is Test {
    Puzzle public puzzle;

    function setUp() public {
        puzzle = new Puzzle();
    }
/// forge-config: default.invariant.runs = 10000
    function invariant_Puzzle() view external {
        assertEq(puzzle.hacked(), false);
    }
}

If it’s coverage-guided and will store and mutate the previous sequences, the final sequence will be solved step by step like B(2)->X->X->X, B(2)->C(3)->X->X, …, B(2)->C(3)->A(1)->D(4).

For example, we can make two strategies: 1. Random Generator (the current one, 50%). 2. Coverage-guided (50%).

If the coverage-guided strategy is picked up, pop a sequence from the new coverage sequence deque and mutate on it (mutate on calldata is ignored here):

1. Insert a new random tx. 50%
2. Exchange two txs’ positions. 20%
3. Repeat a tx. 20%
4. Change a tx’s msg.value. 10%
5. Increase the mutate count of the sequence; if the count > 100, delete it from the deque; otherwise, push it back to the deque.

After getting the new mutated sequence:

1. Get the coverage before a sequence is executed.
2. Get the coverage after a sequence is executed.
3. If there is a new contract or new code hit (we don’t consider the hit number or path for now). Shrink the sequence to a smaller one that triggers the same coverage and push it into the new coverage deque.
4. The new coverage sequence deque has a max size of 64MB (configable?). And the sequence max length is 64 (configable?).

Additional context

No response

[QiuhaoLi]

@grandizzy @klkvr for your thoughts on this :)