assertTrue fail to raise errors in fuzzing

[stephenctw]

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 (a81ea4c 2022-07-19T07:23:43.1341688Z)

What command(s) is the bug in?

forge test

Operating System

WSL2

Describe the bug

Fuzz test with assertTrue fails to raise error (testFuzzing). Remove the fuzz from test then assertTrue raises error properly(testNormal). The fuzz test should throw an error when the input is 2 ** 31 = 2147483648;

contract TrailingOneTest is Test {
    bytes constant trailing1table =
        hex"00010002000100030001000200010004000100020001000300010002000100050001000200010003000100020001000400010002000100030001000200010006000100020001000300010002000100040001000200010003000100020001000500010002000100030001000200010004000100020001000300010002000100070001000200010003000100020001000400010002000100030001000200010005000100020001000300010002000100040001000200010003000100020001000600010002000100030001000200010004000100020001000300010002000100050001000200010003000100020001000400010002000100030001000200010008";

    function setUp() public {}

    function testNormal() public {
        uint256 count = countTrailingOnes(2**31);
        assertTrue(count < 32);
    }

    function testFuzzing(uint32 _depth) public {
        vm.assume(_depth > 0);

        uint256 count = countTrailingOnes(_depth);
        assertTrue(count < 32);
    }

    function countTrailingOnes(uint32 _depth) private returns (uint256) {
        uint256 depth = _depth - 1;
        uint256 count = 1;

        // get count of trailing ones of _depth from trailing1table
        for (uint256 i = 0; i < 4; ) {
            uint256 partialCount = uint8(
                trailing1table[(depth >> (i * 8)) & 0xff]
            );
            count = count + partialCount;
            if (partialCount != 8) {
                break;
            }

            unchecked {
                ++i;
            }
        }

        return count;
    }

[onbjerg]

You are about 13 days outdated with your Forge version, but I also cannot reproduce this:

$ cat -p test/Contract.t.sol
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;

import "forge-std/Test.sol";

contract ContractTest is Test {
    function setUp() public {}

    function testFuzz(bool x) public {
        assertTrue(x);
    }
}

$ forge test
[⠊] Compiling...
[⠊] Compiling 9 files with 0.8.15
[⠒] Solc 0.8.15 finished in 846.11ms
Compiler run successful

Running 1 test for test/Contract.t.sol:ContractTest
[FAIL. Counterexample: calldata=0x91b140490000000000000000000000000000000000000000000000000000000000000000, args=[false]] testFuzz(bool) (runs: 0, μ: 0, ~: 0)
Test result: FAILED. 0 passed; 1 failed; finished in 294.37µs

Failed tests:
[FAIL. Counterexample: calldata=0x91b140490000000000000000000000000000000000000000000000000000000000000000, args=[false]] testFuzz(bool) (runs: 0, μ: 0, ~: 0)

Encountered a total of 1 failing tests, 0 tests succeeded

Most likely the fuzzer does not input 2**31 which is a separate issue - please update the issue to reflect that 😄

[stephenctw]

I updated the forge to latest and the issue remains the same. The code you use to reproduce is different than the one I posted. I also confirmed the value 2**31 is fed by fuzzer with a simple test.

    function test2Order31(uint32 v) public {
        vm.assume(v > 0);
        assertTrue(v < 2**31);
    }

[FAIL. Counterexample: calldata=0x29b2bfa50000000000000000000000000000000000000000000000000000000080000000, args=[2147483648]] test2Order31(uint32) (runs: 5, μ: 3323, ~: 3323)
Logs:
  Error: Assertion Failed

Test result: FAILED. 0 passed; 1 failed; finished in 21.24ms

Failed tests:
[FAIL. Counterexample: calldata=0x29b2bfa50000000000000000000000000000000000000000000000000000000080000000, args=[2147483648]] test2Order31(uint32) (runs: 5, μ: 3323, ~: 3323)

Encountered a total of 1 failing tests, 0 tests succeeded

I'll update the issue if I manage to simplify the reproducible code above.

[stephenctw]

Here is a slightly simplified version.

pragma solidity ^0.8.13;

import "forge-std/Test.sol";

contract FuzzBug is Test {
    function setUp() public {}

    function testNormalV1() public {
        uint256 count = countTrailingOnesV1(2**21 - 1);

        assertTrue(count <= 20);
    }

    function testNormalV2() public {
        uint256 count = countTrailingOnesV2(2**21);

        assertTrue(count <= 20);
    }

    function testFuzzingV1(uint32 _depth) public {
        vm.assume(_depth > 0);

        uint256 count = countTrailingOnesV1(_depth);
        assertTrue(count <= 20);
    }

    function testFuzzingV2(uint32 _depth) public {
        vm.assume(_depth > 0);

        uint256 count = countTrailingOnesV2(_depth);
        assertTrue(count <= 20);
    }

    function countTrailingOnesV1(uint32 _depth) private pure returns (uint256) {
        uint256 depth = _depth;
        uint256 count;

        while (depth & 1 > 0) {
            depth = depth >> 1;
            count ++;
        }

        return count;
    }

    function countTrailingOnesV2(uint32 _depth) private pure returns (uint256) {
        uint256 depth = _depth - 1;
        uint256 count;

        while (depth & 1 > 0) {
            depth = depth >> 1;
            count ++;
        }

        return count;
    }
}

testFuzzingV2 should also fail at input 2**21 like testNormalV2 does.

forge test --match-test "Fuzz|Normal"
[⠑] Compiling...
[⠆] Compiling 5 files with 0.8.15
[⠒] Solc 0.8.15 finished in 3.51s
Compiler run successful (with warnings)

Running 4 tests for test/foundry/FuzzBug.t.sol:FuzzBug
[FAIL. Counterexample: calldata=0xdafb8c2c00000000000000000000000000000000000000000000000000000000001fffff, args=[2097151]] testFuzzingV1(uint32) (runs: 27, μ: 4365, ~: 4246)
[PASS] testFuzzingV2(uint32) (runs: 256, μ: 3554, ~: 3466)
[FAIL] testNormalV1() (gas: 13741)
[FAIL] testNormalV2() (gas: 13907)
Test result: FAILED. 1 passed; 3 failed; finished in 90.82ms

Failed tests:
[FAIL. Counterexample: calldata=0xdafb8c2c00000000000000000000000000000000000000000000000000000000001fffff, args=[2097151]] testFuzzingV1(uint32) (runs: 27, μ: 4365, ~: 4246)
[FAIL] testNormalV1() (gas: 13741)
[FAIL] testNormalV2() (gas: 13907)

Encountered a total of 3 failing tests, 1 tests succeeded

Also not very sure what title best describe this issue.

[onbjerg]

I updated the forge to latest and the issue remains the same. The code you use to reproduce is different than the one I posted. I also confirmed the value 2**31 is fed by fuzzer with a simple test.

This is not necessarily always the case. I used vm.writeLine to log out what kind of numbers I got for testFuzzingV2 and I did not get 2**21 or 2**31. I didn't get any numbers at all where count > 20. If you substitute _depth in testFuzzingV2 with 2**21 exactly, it will fail, so assertTrue is working as intended and the title of the bug does not seem to be true

Not sure what the best title is either since it (to me) seems highly unlikely you will ever hit a failing case with random numbers. Not super strong with math, but given you need the first 21 bits to be 1 it seems extremely unlikely you would hit a number like that in 256 fuzz runs? Noting here that numbers >= 2**21 does not necessarily result in count > 20

Edit: Doing a assertTrue(count <= 10) makes the test fail in about 7500 runs. I think this is just because the chance of hitting numbers like the ones you want is extremely unlikely :/

[stephenctw]

This is not necessarily always the case. I used vm.writeLine to log out what kind of numbers I got for testFuzzingV2 and I did not get 221 or 231. I didn't get any numbers at all where count > 20. If you substitute _depth in testFuzzingV2 with 2**21 exactly it will fail, so assertTrue is working as intended and the title of the bug does not seem to be true

Not sure what the best title is either since it (to me) seems highly unlikely you will ever hit a failing case with random numbers. Not super strong with math, but given you need the first 21 bits to be 1 it seems extremely unlikely you would hit a number like that in 256 fuzz runs? Noting here that numbers >= 2**21 does not necessarily result in count > 20

I see, so to put it more precisely, the fuzzer didn't generate something that hit the edge cases in my test due to low probability. Would you recommend to write tests specifically for those edge cases?

[onbjerg]

Yes, I think so. Not entirely sure, maybe @mds1 has some ideas for how to improve the fuzzer in this case and/or use vm.assume. I'd encourage you to maybe create a discussion instead since this is not a bug on our side? If we find some actionable items out of that we can create issues to track :) And then close this one?

[stephenctw]

Yes, I think so. Not entirely sure, maybe @mds1 has some ideas for how to improve the fuzzer in this case and/or use vm.assume

Yeah I'd love to learn more about it.

[onbjerg]

You can create a discussion here https://github.com/foundry-rs/foundry/discussions/new

Feel free to ping me and @mds1 😄

[mds1]

@stephenctw IIUC, you are expecting the fuzzer to fail by finding a value with over 20 consecutive ones as the lowest order bits? If so, like @onbjerg said that is quite specific and therefore very unlikely for the fuzzer to find it.

Can you explain a bit more about your use case and what exactly you are trying to test? I'm not sure if this is a contrived example or representative of something that may be commonly tested. I ask because the best path forward on how to structure these tests and what changes we may want to make to foundry's fuzz logic might depend on the answer (the fuzzer isn't purely random, and does try to smart in various ways).

I'd recommend going with @onbjerg's suggestion of creating a discussion with details around your use case and what you'd expect from the fuzzer, and we can go from there 🙂

[stephenctw]

@stephenctw IIUC, you are expecting the fuzzer to fail by finding a value with over 20 consecutive ones as the lowest order bits? If so, like @onbjerg said that is quite specific and therefore very unlikely for the fuzzer to find it.

Can you explain a bit more about your use case and what exactly you are trying to test? I'm not sure if this is a contrived example or representative of something that may be commonly tested. I ask because the best path forward on how to structure these tests and what changes we may want to make to foundry's fuzz logic might depend on the answer (the fuzzer isn't purely random, and does try to smart in various ways).

I'd recommend going with @onbjerg's suggestion of creating a discussion with details around your use case and what you'd expect from the fuzzer, and we can go from there 🙂

Hey @mds1, basically I want to test and check if the output of my algorithm is under a certain valid value, something like the counting ones in the above code snippet. Now I understand that it is not what fuzzer is used for, instead I should specifically feed the inputs like 20 consecutive ones and test them individually. Thanks for the clarification!

[mds1]

Ah, yes you may be interested in #858 for some inspiration on how to structure those style tests. I also have https://github.com/mds1/solidity-generators which is mostly done and may help you generate the input arrays