Solidity: ICE in the CSE optimizer

Created on 10 Feb 2020 · 18Comments · Source: ethereum/solidity

Description

This contract:

contract C
{
    struct s1 {
        uint x;
    }
    function fun_x() public {}
    function fun_y() public {}
    function f() public {
        uint h = true ? 1 : 3;
    }
    function f2() public {
    }
        function () r = true ? fun_x : fun_y;
    function f3() public {
    }
}

produces:

Invalid error: "InternalCompilerError"
terminate called after throwing an instance of 'std::runtime_error'
  what():  Invalid error: "InternalCompilerError"

when run with solfuzzer (solc alone seems ok)

On master, using AFL fuzzing. This was found with a new approach, that inlines a generic C-like source code mutation tool as a high-probability AFL havoc mutator.

Environment

Compiler version: 0.6.3-develop.2020.2.10+commit.e8eb1f2d.Linux.clang
Target EVM version (as per compiler settings): N/A
Framework/IDE (e.g. Truffle or Remix): N/A
EVM execution environment / backend / blockchain client: N/A
Operating system: Ubuntu 18.04 in docker

Steps to Reproduce

Save this contract in shrink.sol (or whatever filename)

contract C
{
    struct s1 {
        uint x;
    }
    function fun_x() public {}
    function fun_y() public {}
    function f() public {
        uint h = true ? 1 : 3;
    }
    function f2() public {
    }
        function () r = true ? fun_x : fun_y;
    function f3() public {
    }
}

produces:

> solfuzzer < shrink.sol 
Invalid error: "InternalCompilerError"
terminate called after throwing an instance of 'std::runtime_error'
  what():  Invalid error: "InternalCompilerError"

bug

Source

agroce

All 18 comments

@bshastry can you check this, please? I was not able to reproduce it. The assertion is triggered inside a catch clause. It would be good to know what the inner exception was.

chriseth on 10 Feb 2020

👍1

I'm running these on the afl-instrumented build, could cause reproduction problems. To get roughly that, compile with afl and crank AFL_INST_RATIO up to 10. I'll make a no-inst solc to check on, but assume anything only showing up with inst is still a real problem.

agroce on 10 Feb 2020

(There's some randomness in the instrumentation, but probably not critical)

agroce on 10 Feb 2020

Aha, may be that I somehow copied in wrong version.

0.6.3-develop.2020.2.10+commit.e8eb1f2d.Linux.clang is actual solc version output.

agroce on 10 Feb 2020

Is it possible to reduce the input a little more? Can you run this in a debugger and see where the inner exception is throw? Thanks!

chriseth on 10 Feb 2020

Let me see about further reduction, this is line level.

agroce on 10 Feb 2020

contract C {
  function fun_x () public {}
  function fun_y () public{}
  function f() public
  {
    int h=true?1:3;
  }
  function () r=true?fun_x:fun_y;
}

is a pretty minimal shrink. Debugger isn't installled on this docker, will get to that later this morning, maybe. With the right commit info above, and this, maybe it'll repro for you. Remember needs optimization on.

agroce on 10 Feb 2020

Exact solc run:

> solc shrink.sol --optimize
Internal compiler error during compilation:
/home/user/solidity/libsolidity/interface/CompilerStack.cpp(1068): Throw in function void solidity::frontend::CompilerStack::compileContract(const solidity::frontend::ContractDefinition &, map<const solidity::frontend::ContractDefinition *, shared_ptr<const solidity::frontend::Compiler> > &)
Dynamic exception type: boost::exception_detail::clone_impl<solidity::langutil::InternalCompilerError>
std::exception::what: Assembly exception for bytecode
[solidity::util::tag_comment*] = Assembly exception for bytecode

agroce on 10 Feb 2020

ah, maybe this will help:

(gdb) bt
#0  0x00007fda9f5a3ced in __cxa_throw () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#1  0x0000000000740376 in boost::throw_exception<solidity::evmasm::AssemblyException> (e=...)
    at /usr/include/boost/throw_exception.hpp:69
#2  0x0000000000bef8da in solidity::evmasm::Assembly::assemble (this=<optimized out>)
    at /home/user/solidity/libevmasm/Assembly.cpp:631
#3  0x000000000055c2e0 in solidity::frontend::CompilerContext::assembledObject (
    this=0xe15750 <vtable for boost::exception_detail::clone_impl<solidity::evmasm::InvalidDeposit>+136>)
    at /home/user/solidity/libsolidity/codegen/CompilerContext.h:251
#4  solidity::frontend::Compiler::assembledObject (
    this=0xe15450 <typeinfo for boost::exception_detail::clone_impl<solidity::evmasm::AssemblyException>>) at /home/user/solidity/libsolidity/codegen/Compiler.h:59
#5  0x00000000005466ae in solidity::frontend::CompilerStack::compileContract (this=<optimized out>, 
    _contract=..., _otherCompilers=...)
    at /home/user/solidity/libsolidity/interface/CompilerStack.cpp:1064
#6  0x0000000000545cb0 in solidity::frontend::CompilerStack::compile (this=0x2e2fc70)
    at /home/user/solidity/libsolidity/interface/CompilerStack.cpp:497
#7  0x000000000043d830 in solidity::frontend::CommandLineInterface::processInput (this=<optimized out>)
    at /home/user/solidity/solc/CommandLineInterface.cpp:1147
#8  0x000000000047797e in main (argc=3, argv=<optimized out>) at /home/user/solidity/solc/main.cpp:59

agroce on 10 Feb 2020

So the failing assertion is

        assertThrow(pos != size_t(-1), AssemblyException, "Reference to tag without position.");

I think we need to reproduce this to fix it. Thanks again for reporting!

chriseth on 10 Feb 2020

I can reproduce it with his latest example

Marenz on 10 Feb 2020

👍1

Problem seems to be in the CSE optimizer

Marenz on 10 Feb 2020

I can reproduce it with the shrunk example.

I think we need to reproduce this to fix it.

Do you mean we need to reproduce it via a standalone assembly snippet?

bshastry on 11 Feb 2020

@Marenz can you provide more details? Could this be a critical bug or is it always caught by the assertion?

chriseth on 11 Feb 2020

I basically disabled all optimizations and re-enabled them one by one until it crashed and the CSE was the one that caused it. I didn't get further in my analysis

Marenz on 11 Feb 2020

Still an issue today, seems to fail in the same place.

axic on 7 May 2020

Looks like an internal function referenced by the constructor, stored in storage but the optimizer removes the runtime tag of that function...

chriseth on 8 May 2020

This is a bug in the BlockDeDuplicator.

I'm using the following code

contract C {
    function fun_x() public {}
    function fun_() public {}
    function f() public { true ? 1 : 3;}
    function() r = true ? fun_x : f;
}

The above code produced the unoptimized assembly (./solc --asm):

======= /tmp/shrink.sol:C =======
EVM assembly:
    /* "/tmp/shrink.sol":0:142  contract C {... */
  mstore(0x40, 0x80)
    /* "/tmp/shrink.sol":123:127  true */
  0x01
    /* "/tmp/shrink.sol":123:139  true ? fun_x : f */
  tag_1
  jumpi
    /* "/tmp/shrink.sol":138:139  f */
  or(tag_0_7, shl(0x20, tag_2))
    /* "/tmp/shrink.sol":123:139  true ? fun_x : f */
  jump(tag_3)
tag_1:
    /* "/tmp/shrink.sol":130:135  fun_x */
  or(tag_0_11, shl(0x20, tag_4))
    /* "/tmp/shrink.sol":123:139  true ? fun_x : f */
tag_3:
    /* "/tmp/shrink.sol":108:139  function() r = true ? fun_x : f */
  0x00
  dup1
  0x0100
  exp
  dup2
  sload
  dup2
  0xffffffffffffffff
  mul
  not
  and
  swap1
  dup4
  0xffffffffffffffff
  and
  mul
  or
  swap1
  sstore
  pop
    /* "/tmp/shrink.sol":0:142  contract C {... */
  callvalue
    /* "--CODEGEN--":5:14   */
  dup1
    /* "--CODEGEN--":2:4   */
  iszero
  tag_5
  jumpi
    /* "--CODEGEN--":27:28   */
  0x00
    /* "--CODEGEN--":24:25   */
  dup1
    /* "--CODEGEN--":17:29   */
  revert
    /* "--CODEGEN--":2:4   */
tag_5:
    /* "/tmp/shrink.sol":0:142  contract C {... */
  pop
  jump(tag_6)
    /* "/tmp/shrink.sol":70:106  function f() public { true ? 1 : 3;} */
tag_2:
    /* "/tmp/shrink.sol":92:96  true */
  0x01
    /* "/tmp/shrink.sol":92:104  true ? 1 : 3 */
  tag_8
  jumpi
    /* "/tmp/shrink.sol":103:104  3 */
  0x03
    /* "/tmp/shrink.sol":92:104  true ? 1 : 3 */
  jump(tag_9)
tag_8:
    /* "/tmp/shrink.sol":99:100  1 */
  0x01
    /* "/tmp/shrink.sol":92:104  true ? 1 : 3 */
tag_9:
  pop
    /* "/tmp/shrink.sol":70:106  function f() public { true ? 1 : 3;} */
  jump  // out
    /* "/tmp/shrink.sol":14:40  function fun_x() public {} */
tag_4:
  jump  // out
    /* "/tmp/shrink.sol":0:142  contract C {... */
tag_6:
  dataSize(sub_0)
  dup1
  dataOffset(sub_0)
  0x00
  codecopy
  0x00
  return
stop

sub_0: assembly {
        /* "/tmp/shrink.sol":0:142  contract C {... */
      mstore(0x40, 0x80)
      callvalue
        /* "--CODEGEN--":5:14   */
      dup1
        /* "--CODEGEN--":2:4   */
      iszero
      tag_1
      jumpi
        /* "--CODEGEN--":27:28   */
      0x00
        /* "--CODEGEN--":24:25   */
      dup1
        /* "--CODEGEN--":17:29   */
      revert
        /* "--CODEGEN--":2:4   */
    tag_1:
        /* "/tmp/shrink.sol":0:142  contract C {... */
      pop
      jumpi(tag_2, lt(calldatasize, 0x04))
      shr(0xe0, calldataload(0x00))
      dup1
      0x26121ff0
      eq
      tag_3
      jumpi
      dup1
      0x2e1fb2bc
      eq
      tag_4
      jumpi
      dup1
      0x4753a67d
      eq
      tag_5
      jumpi
    tag_2:
        /* "--CODEGEN--":12:13   */
      0x00
        /* "--CODEGEN--":9:10   */
      dup1
        /* "--CODEGEN--":2:14   */
      revert
        /* "/tmp/shrink.sol":70:106  function f() public { true ? 1 : 3;} */
    tag_3:
      tag_6
      tag_7
      jump  // in
    tag_6:
      stop
        /* "/tmp/shrink.sol":42:67  function fun_() public {} */
    tag_4:
      tag_8
      tag_9
      jump  // in
    tag_8:
      stop
        /* "/tmp/shrink.sol":14:40  function fun_x() public {} */
    tag_5:
      tag_10
      tag_11
      jump  // in
    tag_10:
      stop
        /* "/tmp/shrink.sol":70:106  function f() public { true ? 1 : 3;} */
    tag_7:
        /* "/tmp/shrink.sol":92:96  true */
      0x01
        /* "/tmp/shrink.sol":92:104  true ? 1 : 3 */
      tag_13
      jumpi
        /* "/tmp/shrink.sol":103:104  3 */
      0x03
        /* "/tmp/shrink.sol":92:104  true ? 1 : 3 */
      jump(tag_14)
    tag_13:
        /* "/tmp/shrink.sol":99:100  1 */
      0x01
        /* "/tmp/shrink.sol":92:104  true ? 1 : 3 */
    tag_14:
      pop
        /* "/tmp/shrink.sol":70:106  function f() public { true ? 1 : 3;} */
      jump  // out
        /* "/tmp/shrink.sol":42:67  function fun_() public {} */
    tag_9:
      jump  // out
        /* "/tmp/shrink.sol":14:40  function fun_x() public {} */
    tag_11:
      jump  // out

    auxdata: 0xa2646970667358221220ccf6df9d64de41e3f3d92617ef3358933e874733a96bb195064e4db54340ed6c64736f6c63782b302e362e382d646576656c6f702e323032302e352e31352b636f6d6d69742e63613433313466352e6d6f64005c
}

When --optimize is enabled, inside sub_0, the BlockDeDuplicator does the following changes. (the first one gets replaced by the second)

tag_5 <- tag_4
tag_8 <- tag_6
tag_10 <- tag_6
tag_11 <- tag_9
tag_4 <- tag_3
tag_9 <- tag_7

The tags, tag_7 and tag_11 are referenced from the top in or(tag_0_7, shl(0x20, tag_2)) and or(tag_0_11, shl(0x20, tag_4) respectively. When the replacements happen at the top, tag_11 gets replaced by tag_9, but tag_9 doesn't exist at this point because it was replaced by tag_7. This is what causes the error "Reference to tag without position."

I'll fix it in a PR.