u256 overflow in logical shift optimization rule leads to incorrect computation

[bshastry]

Description

(Found by LPM+libFuzzer: Minimized by hand)

The following code should reduce to mstore(0,0) instead it reduces to mstore(0,2)

{
  foo(2)
  function foo(x)
  {
    mstore(0, shl(1,shl(not(0),x)))
  }
}

I believe the problem lies in the following logical shift optimization rules

solidity/libevmasm/RuleList.h

Lines 348 to 353 in 4430fe6

	rules.push_back({
	// SHR(B, SHR(A, X)) -> SHR(min(A+B, 256), X)
	{Instruction::SHR, {{B}, {Instruction::SHR, {{A}, {X}}}}},
	[=]() -> Pattern { return {Instruction::SHR, {std::min(A.d() + B.d(), u256(256)), X}}; },
	false
	});

wherein the following optimization happens

• SHR(B, SHR(A, X)) -> SHR(min(A+B, 256), X)

However, for the corner cases that trigger a u256 overflow in the addition of A and B such as B=1 and A=not(0), min(A+B, u256(256)) incorrectly reduces to 0. When there's an overflow in the shift size, we'd want to shift by u256(256) instead.

Subsequently SHR(0, X) correctly reduces to X.

This bug/reasoning applies for the logical shift left operator as well.

This bug was a bit tricky to minimize because a simpler program such as the following is correctly computed.

{mstore(0, shl(1,shl(not(0),2)))}

Although I can't pin-point the reason for this, I guess that the optimization steps applied before logical shift optimizations (within the expression simplifier) somehow ensure that the buggy shift optimization rule is not triggered.

Introduction of a function makes it non-trivial enough for the buggy shift optimization rule to kick in.

Potential fix

In logical shift optimization rule

• check for u256 overflow after addition of nested shift sizes
• in case of an overflow, do std::max(A+B, u256(256)) where A and B are shift sizes
• else do std::min(A+B, u256(256))

Environment

• Compiler version: latest develop
• Target EVM version (as per compiler settings): petersburg
• Framework/IDE (e.g. Truffle or Remix): n/a
• EVM execution environment / backend / blockchain client: n/a
• Operating system: n/a

Steps to Reproduce

The bug may be reproduced using yulopti using the s option (expression simplifier). The debug output is from the AST printer at the time expression simplifier is called first before and then after the buggy shift optimization rule has been applied.

$ ./test/tools/yulopti --input-file <code.yul>
----------------------                                                                          
{                                                                                               
  foo(2)                                                                                        
  function foo(x)                                                                               
  {                                                                                             
    mstore(0, shl(1,shl(not(0),x)))                                                             
  }                                                                                             
}                                                                                               
                                                                                                
(q)quit/(f)flatten/(c)se/initialize var(d)ecls/(x)plit/(j)oin/(g)rouper/(h)oister/              
  (e)xpr inline/(i)nline/(s)implify/varname c(l)eaner/(u)nusedprune/ss(a) transform/            
  (r)edundant assign elim./re(m)aterializer/f(o)r-loop-pre-rewriter/                            
  s(t)ructural simplifier/equi(v)alent function combiner/ssa re(V)erser/?                       
  stack com(p)ressor?
 s
ES AST
{
    foo(2)
    function foo(x)
    {
        mstore(0, shl(1, shl(not(0), x)))
    }
}----------------------
{
    foo(2)
    function foo(x)
    {
        mstore(0, x)
    }
}

[axic]

Ah finally got it, you surmise that addition of two u256 can overflow. I think the fix is to do bigint(A) + B.

[axic]

Unfortunately this is a buglist item 😢

[chriseth]

Good that we plan to make another release before the breaking one :)