Crashes during symbolic execution in recursive map/step

fala13 commented 6 months ago

Component

Heimdall (Core)

Have you ensured that you are up to date?

[ ] Bifrost
[X] Heimdall

What version of Heimdall are you on?

latest main (commit 34462eb433627a6eb93c6339f20b3676000888d4)

Operating System

Linux

Describe the bug

While using the heimdall as a library I stumbled upon a lot of silent crashes of my app. To try and find the issue I started running in debug mode, but then constantly got arithmetic assertions thrown from vm.rs and range_map.rs. After putting there #![allow(arithmetic_overflow)] vector capacity and out of bounds crashes started popping, confirming the issue is not only limited to debug builds.

Arithmetic overflows assertions are enabled in debug but disabled by default in release, so that is maybe why the issue is under the radar. I guess the overflow issue is valid and should be investigated first in debug mode. I'm not familiar enough with the vm.rs yet to be able to fix it on my own.

The issue can be easily reproduced on contract 0xa57b8d98dae62b26ec3bcc4a365338157060b234 on Ethereum or by putting below UT at the end of test_decompile.rs (issues visible both in debug and release test runs):

#[tokio::test]
    async fn benchmark_build_abi_crashing() {
        let default_panic = std::panic::take_hook(); // stop on crash
        std::panic::set_hook(Box::new(move |info| {
            default_panic(info);

            std::thread::spawn(move || {
                // Create a new Tokio runtime for async operations
                let rt = tokio::runtime::Runtime::new().unwrap();
                rt.block_on(async {
                    // Exit the process
                    std::process::exit(1);
                });
            });
        }));

        async fn bench() {
            let args = DecompilerArgs {
                target: String::from("0xa57b8d98dae62b26ec3bcc4a365338157060b234"),
                rpc_url: String::from("https://eth.llamarpc.com"),
                default: true,
                skip_resolving: false,
                include_solidity: false,
                include_yul: false,
                output: String::from(""),
                name: String::from(""),
                timeout: 100,
            };
            let _ = heimdall_core::decompile::decompile(args).await;
        }
        for i in 0..100 {
            bench().await;
        }
    }

result of release test run RUST_BACKTRACE=1 cargo test -p heimdall-core --test test_decompile -r -- benchmark::build_abi_crashing --nocapture

24-04-2024 13:34:29.257067Z INFO ⠙ executing '0x354af919' thread '' panicked at crates/common/src/ether/evm/core/vm.rs:238:35: index out of bounds: the len is 21256 but the index is 18446744073709551615 stack backtrace: 0: rust_begin_unwind 1: core::panicking::panic_fmt 2: core::panicking::panic_bounds_check 3: heimdall_common::ether::evm::core::vm::VM::_step 4: heimdall_common::ether::evm::core::vm::VM::step 5: heimdall_common::ether::evm::ext::exec::::recursive_map 6: heimdall_common::ether::evm::ext::exec::::recursive_map 7: heimdall_common::ether::evm::ext::exec::::recursive_map 8: heimdall_common::ether::evm::ext::exec::::recursive_map 9: heimdall_common::ether::evm::ext::exec::::recursive_map 10: heimdall_common::ether::evm::ext::exec::::recursive_map 11: heimdall_common::ether::evm::ext::exec::::recursive_map 12: heimdall_common::ether::evm::ext::exec::::recursive_map 13: heimdall_common::ether::evm::ext::exec::::recursive_map 14: heimdall_common::ether::evm::ext::exec::::recursive_map 15: heimdall_common::ether::evm::ext::exec::::recursive_map 16: heimdall_common::ether::evm::ext::exec::::recursive_map 17: heimdall_common::ether::evm::ext::exec::::recursive_map 18: heimdall_common::ether::evm::ext::exec::::recursive_map 19: heimdall_common::ether::evm::ext::exec::::recursive_map 20: heimdall_common::ether::evm::ext::exec::::recursive_map 21: heimdall_common::ether::evm::ext::exec::::recursive_map 22: heimdall_common::ether::evm::ext::exec::::recursive_map 23: heimdall_common::ether::evm::ext::exec::::recursive_map 24: heimdall_common::ether::evm::ext::exec::::recursive_map 25: heimdall_common::ether::evm::ext::exec::::recursive_map 26: heimdall_common::ether::evm::ext::exec::::recursive_map 27: heimdall_common::ether::evm::ext::exec::::recursive_map 28: heimdall_common::ether::evm::ext::exec::::recursive_map 29: heimdall_common::ether::evm::ext::exec::::recursive_map 30: heimdall_common::ether::evm::ext::exec::::recursive_map 31: heimdall_common::ether::evm::ext::exec::::recursive_map 32: heimdall_common::ether::evm::ext::exec::::recursive_map 33: heimdall_common::ether::evm::ext::exec::::recursive_map 34: heimdall_common::ether::evm::ext::exec::::recursive_map 35: heimdall_common::ether::evm::ext::exec::::recursive_map 36: heimdall_common::ether::evm::ext::exec::::symbolic_exec_selector note: Some details are omitted, run with RUST_BACKTRACE=full for a verbose backtrace. error: test failed, to rerun pass -p heimdall-core --test test_decompile

result of debug test run RUST_BACKTRACE=1 cargo test -p heimdall-core --test test_decompile -- benchmark::build_abi_crashing --nocapture

24-04-2024 13:35:05.929562Z INFO ⠙ executing '0x9123d404' thread '' panicked at crates/common/src/ether/evm/core/memory.rs:170:38: attempt to add with overflow stack backtrace: 0: rust_begin_unwind at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/std/src/panicking.rs:647:5 1: core::panicking::panic_fmt at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/panicking.rs:72:14 2: core::panicking::panic at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/panicking.rs:144:5 3: heimdall_common::ether::evm::core::memory::Memory::expansion_cost at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/core/memory.rs:170:38 4: heimdall_common::ether::evm::core::vm::VM::_step at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/core/vm.rs:998:32 5: heimdall_common::ether::evm::core::vm::VM::step at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/core/vm.rs:1344:27 6: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:94:25 7: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:269:44 8: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 9: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 10: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 11: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:272:44 12: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 13: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:272:44 14: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:272:44 15: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 16: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 17: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 18: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:272:44 19: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 20: heimdall_common::ether::evm::ext::exec::::recursive_map at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:260:44 21: heimdall_common::ether::evm::ext::exec::::symbolic_exec_selector at /home/fala/crypto/heimdall-rs/crates/common/src/ether/evm/ext/exec/mod.rs:60:13 22: heimdall_core::decompile::decompile::{{closure}}::{{closure}} at ./src/decompile/mod.rs:494:21 23: heimdall_common::utils::threading::run_with_timeout::{{closure}} at /home/fala/crypto/heimdall-rs/crates/common/src/utils/threading.rs:81:22 note: Some details are omitted, run with RUST_BACKTRACE=full for a verbose backtrace. error: test failed, to rerun pass -p heimdall-core --test test_decompile

Jon-Becker commented 6 months ago

Hey! Thank you for opening. I'll investigate this weekend, i'm hoping to have 0.8.0 out by monday so i'll try to get this fix in as well

fala13 commented 5 months ago

@Jon-Becker , unfortunately the issue is still there, reproducible with same test, occurring at the same place in code.

In addition in 0.8, I'm seeing another issue with indexing across two potentially different ranges in build_abi() in abi.rs:54 that causes sporadic crashes also with this test, e.g. on the Uni V3 Router 0x68b3465833fb72A70ecDF485E0e4C7bD8665Fc45:

running 1 test
thread 'benchmark::build_abi_crashing' panicked at crates/decompile/src/core/out/abi.rs:54:52:
index out of bounds: the len is 1 but the index is 1
stack backtrace:
   0: rust_begin_unwind
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/std/src/panicking.rs:647:5
   1: core::panicking::panic_fmt
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/panicking.rs:72:14
   2: core::panicking::panic_bounds_check
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/panicking.rs:208:5
   3: <usize as core::slice::index::SliceIndex<[T]>>::index
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/slice/index.rs:255:10
   4: core::slice::index::<impl core::ops::index::Index<I> for [T]>::index
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/slice/index.rs:18:9
   5: <alloc::vec::Vec<T,A> as core::ops::index::Index<I>>::index
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/alloc/src/vec/mod.rs:2771:9
   6: heimdall_decompiler::core::out::abi::build_abi::{{closure}}::{{closure}}
             at /home/fala/crypto/heimdall-rs/crates/decompile/src/core/out/abi.rs:54:52
   7: core::iter::adapters::map::map_fold::{{closure}}
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/iter/adapters/map.rs:89:28
   8: <core::iter::adapters::enumerate::Enumerate<I> as core::iter::traits::iterator::Iterator>::fold::enumerate::{{closure}}
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/iter/adapters/enumerate.rs:107:27
   9: <core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::fold
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/slice/iter/macros.rs:232:27
  10: <core::iter::adapters::enumerate::Enumerate<I> as core::iter::traits::iterator::Iterator>::fold
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/iter/adapters/enumerate.rs:113:9
  11: <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::fold
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/iter/adapters/map.rs:129:9
  12: core::iter::traits::iterator::Iterator::for_each
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/iter/traits/iterator.rs:858:9
  13: alloc::vec::Vec<T,A>::extend_trusted
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/alloc/src/vec/mod.rs:2962:17
  14: <alloc::vec::Vec<T,A> as alloc::vec::spec_extend::SpecExtend<T,I>>::spec_extend
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/alloc/src/vec/spec_extend.rs:26:9
  15: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter_nested::SpecFromIterNested<T,I>>::from_iter
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/alloc/src/vec/spec_from_iter_nested.rs:62:9
  16: <alloc::vec::Vec<T> as alloc::vec::spec_from_iter::SpecFromIter<T,I>>::from_iter
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/alloc/src/vec/spec_from_iter.rs:33:9
  17: <alloc::vec::Vec<T> as core::iter::traits::collect::FromIterator<T>>::from_iter
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/alloc/src/vec/mod.rs:2836:9
  18: core::iter::traits::iterator::Iterator::collect
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/iter/traits/iterator.rs:2054:9
  19: heimdall_decompiler::core::out::abi::build_abi::{{closure}}
             at /home/fala/crypto/heimdall-rs/crates/decompile/src/core/out/abi.rs:46:21
  20: <core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::for_each
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/slice/iter/macros.rs:254:21
  21: heimdall_decompiler::core::out::abi::build_abi
             at /home/fala/crypto/heimdall-rs/crates/decompile/src/core/out/abi.rs:25:5
  22: heimdall_decompiler::core::decompile::{{closure}}
             at /home/fala/crypto/heimdall-rs/crates/decompile/src/core/mod.rs:287:15
  23: test_decompile::benchmark::build_abi_crashing::{{closure}}::bench::{{closure}}
             at ./tests/test_decompile.rs:156:37
  24: test_decompile::benchmark::build_abi_crashing::{{closure}}
             at ./tests/test_decompile.rs:159:21
  25: <core::pin::Pin<P> as core::future::future::Future>::poll
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/future/future.rs:124:9
  26: <core::pin::Pin<P> as core::future::future::Future>::poll
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/future/future.rs:124:9
  27: tokio::runtime::scheduler::current_thread::CoreGuard::block_on::{{closure}}::{{closure}}::{{closure}}
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:659:57
  28: tokio::runtime::coop::with_budget
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/coop.rs:107:5
  29: tokio::runtime::coop::budget
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/coop.rs:73:5
  30: tokio::runtime::scheduler::current_thread::CoreGuard::block_on::{{closure}}::{{closure}}
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:659:25
  31: tokio::runtime::scheduler::current_thread::Context::enter
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:404:19
  32: tokio::runtime::scheduler::current_thread::CoreGuard::block_on::{{closure}}
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:658:36
  33: tokio::runtime::scheduler::current_thread::CoreGuard::enter::{{closure}}
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:737:68
  34: tokio::runtime::context::scoped::Scoped<T>::set
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/context/scoped.rs:40:9
  35: tokio::runtime::context::set_scheduler::{{closure}}
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/context.rs:176:26
  36: std::thread::local::LocalKey<T>::try_with
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/std/src/thread/local.rs:286:16
  37: std::thread::local::LocalKey<T>::with
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/std/src/thread/local.rs:262:9
  38: tokio::runtime::context::set_scheduler
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/context.rs:176:9
  39: tokio::runtime::scheduler::current_thread::CoreGuard::enter
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:737:27
  40: tokio::runtime::scheduler::current_thread::CoreGuard::block_on
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:646:19
  41: tokio::runtime::scheduler::current_thread::CurrentThread::block_on::{{closure}}
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:175:28
  42: tokio::runtime::context::runtime::enter_runtime
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/context/runtime.rs:65:16
  43: tokio::runtime::scheduler::current_thread::CurrentThread::block_on
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/scheduler/current_thread/mod.rs:167:9
  44: tokio::runtime::runtime::Runtime::block_on
             at /home/fala/.cargo/registry/src/index.crates.io-6f17d22bba15001f/tokio-1.37.0/src/runtime/runtime.rs:349:47
  45: test_decompile::benchmark::build_abi_crashing
             at ./tests/test_decompile.rs:143:9
  46: test_decompile::benchmark::build_abi_crashing::{{closure}}
             at ./tests/test_decompile.rs:127:34
  47: core::ops::function::FnOnce::call_once
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/ops/function.rs:250:5
  48: core::ops::function::FnOnce::call_once
             at /rustc/25ef9e3d85d934b27d9dada2f9dd52b1dc63bb04/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
test benchmark::build_abi_crashing ... FAILED

fala13 commented 5 months ago

btw. added some prints to this problematic run and seems there is some issue with decompiling the multicall(bytes[]) in 0x68b3465833fb72A70ecDF485E0e4C7bD8665Fc45:

Example of previous good function that can be handled in this way: resolved: ResolvedFunction { name: "unwrapWETH9WithFee", signature: "unwrapWETH9WithFee(uint256,uint256,address)", inputs: ["uint256", "uint256", "address"], decoded_inputs: None } vs. analyzed: [(0, CalldataFrame { arg_op: "PUSH1(4)", mask_size: 32, heuristics: {Numeric} }), (1, CalldataFrame { arg_op: "PUSH32(36)", mask_size: 32, heuristics: {Numeric} }), (2, CalldataFrame { arg_op: "PUSH32(68)", mask_size: 20, heuristics: {} })]

The problematic function: resolved: ResolvedFunction { name: "multicall", signature: "multicall(bytes[])", inputs: ["bytes[]"], decoded_inputs: None } vs analyzed: [(0, CalldataFrame { arg_op: "PUSH1(4)", mask_size: 32, heuristics: {Numeric} }), (1, CalldataFrame { arg_op: "ADD(ADD(ADD(PUSH1(4), CALLDATALOAD(PUSH1(4))), PUSH1(32)), PUSH32(0))", mask_size: 32, heuristics: {} })]

Jon-Becker / heimdall-rs