False positive: costly-loop detector when evaluating an if statement with assignment and return

[varunsrin]

Describe the issue:

A costly-loop warning triggers when evaluating a loop that contains an if statement that includes both an assignment to a state variable followed by a return. This shouldn't be flagged as costly because it is the most efficient way of assigning this value since it only triggers once before exiting the loop.

Code example to reproduce the issue:

uint 256 storedIndex = 0; 
arrayOfValues =  [1640995200, 1672531200, 1704067200];

function currYear() public {
  for (uint256 i = 0; i < arrayOfValues.length; i++) {
        if (arrayOfValues[i] > block.timestamp) {
            storedIndex = i;
            return;
        }
    }
}

Version:

0.8.3

Relevant log output:

currYear() has costly operations inside a loop:
	- storedIndex = i 
Reference: https://github.com/crytic/slither/wiki/Detector-Documentation#costly-operations-inside-a-loop

[plotchy]

@0xalpharush @montyly Would this be a good application for checking post-dominance of any form of loop breaking statement to remove costly operations false positives? In cases where a loop-breaker is immediately hit, the operation is only performed once

[0xalpharush]

Yeah, I think you could check if the post dominator node is a return and drops those from the results https://github.com/crytic/slither/blob/ce9dbf650d7acfee51ddafd844929f4e8d345672/slither/detectors/statements/costly_operations_in_loop.py#L39 Would you like to work on this issue @plotchy ?

[plotchy]

@0xalpharush I looked into this a little bit, but I think it's over my head.

From what I can see Slither uses this algo:

Naive implementation of Cooper, Harvey, Kennedy algo
    See 'A Simple,Fast Dominance Algorithm'

A Simple,Fast Dominance Algorithm

Skimmed the doc to see if they have a postdominance impl, and they wrote about difficulties doing it with jumps out of loops, which is what we'd be targetting...

Page 10: We also measured the time to compute postdominators and postdominance frontiers.3 The postdominance computation has a different behavior, because the reversed cfg has a different shape. This gives us additional insight into the behavior of the algorithms. In cfgs generated from real-world codes, it is more common to encounter irreducible graphs when calculating postdominance information. Broadly speaking, irreducible loops are caused by multiple-entry loops. While few modern languages allow a jump into the middle of a loop, almost all languages allow a jump out of the middle of the loop, and real-world codes tend to do this with some frequency. When we walk backwards through the cfg, jumps out of a loop become jumps into a loop, and irreducibility results.

If you have ideas I think it'd be fun to work together on it

[montyly]

As we have an end_loop node in Slither's CFG, and there is no goto-like in Solidity, the only additional entry points for loop in the reverse CFG are going to be the return/revert/throw/.. - I think. These nodes are also going to be directly entry points in the reverse cfg, so we might be ok-ish?

I haven't played with this in a while, but we might be ok by just adapting https://github.com/crytic/slither/blob/master/slither/core/dominators/utils.py to walk through the reverse cfg (node.sons instead of node.fathers).

[plotchy]

@montyly My very naive impl using node.sons over node.fathers and extending all relevant objects to have post_dominance properties produced this post dominator tree:

Contract:

Taken from https://github.com/crytic/slither/pull/629

pragma solidity ^0.8.13;
contract C {
    function f() public {
        for (uint i = 0; i < 10; i++) {
            if (i > 100) {
                break;
            }
            if (i < 3) {
                continue;
            }

            for (uint j = 0; j < 10; j++) {
                if (j > 10) {
                    continue;
                }
                if (j < 3) {
                    break;
                }

                j -= 1;
            }
        }
    }
}

Dom Tree Visualization

Post-Dom Tree Visualization

Edit: Tested with the following contract similar to the OP:

pragma solidity ^0.8.13;
contract PostDomTest {
    uint state_var;
    function f() public {
        for (uint i = 0; i < 10; i++) {
            if (i == 4) {
                state_var = i;
                return;
            }
        }
    }
}

Costly-operation test

state_var assignment does have the return node as a post-dominator, but I don't think these floating nodes should unattached from the tree

[plotchy]

Adding a thought here:

If there isn't a post-dominant return/revert/break/etc of the costly-operator, you can also check if all post-dominance frontier's of the node-id are then post-dominated by a return/revert/break/etc.

Ex:

pragma solidity ^0.8.13;
contract PostDomTest {
    uint state_var;
    function f() public {
        for (uint i = 0; i < 10; i++) {
            if (i == 4) {
                state_var = i;
                // return; //isn't post-dominated by return anymore

                // now check post-dominance frontier for node (state_var=i) and see if all options are pdom'd by return
                if (state_var == 5) {
                    return;
                } else {
                    return;
                }
            }
        }
    }
}

Which is the case in this example :+1: