java-topology/tools/tickets/defects/solc-0002.md

id	repo	file	line	status	severity	complexity	pattern
solc-0002	ethereum/solidity	libevmasm/Assembly.cpp	1077	unpatched	MEDIUM	O(J × N) — J relative jumps, N instructions	std::find on instruction sequence for each RJUMP/RJUMPI target resolution

Description

In the EVM EOF (EVM Object Format) control flow graph builder, each relative jump (RJUMP, RJUMPI) resolves its target by scanning the full instruction sequence:

auto const tagIt = std::find(items.begin(), items.end(), item.tag());  // O(|items|)

This is inside a loop over all instructions (idx in items). For a function with J relative jumps and N total instructions, this is O(J × N). A pre-pass building a tag → index map would reduce this to O(N + J).

Context

This code is in the EOF stack height validation pass (Assembly::eofValidate() or equivalent). EOF is EVM Object Format — an updated EVM bytecode container format proposed for Ethereum. As of 2026, EOF is not yet widely deployed (still in EIP proposal / testnet stage), so real-world exposure is limited. The same TODO comment region mentions incomplete support for RJUMPV, indicating this code is still evolving.

Fix

Pre-compute a tag → index map before the loop:

// CWE-407 fix: build tag→index map once instead of scanning per jump
std::unordered_map<AssemblyItem, size_t> tagIndex;
for (size_t i = 0; i < items.size(); ++i)
    if (items[i].type() == Tag)
        tagIndex[items[i]] = i;

// Then inside the loop:
if (item.type() == RelativeJump || item.type() == ConditionalRelativeJump)
{
    auto it = tagIndex.find(item.tag());
    solAssert(it != tagIndex.end(), "Tag not found.");
    successors.emplace_back(it->second);
}

Note: AssemblyItem hashability needs verification — if no std::hash specialization exists, use std::map<AssemblyItem, size_t> (O(log N) lookup, still O(J log N) total vs O(J × N) current).

Complexity after fix

O(N log N + J log N) with ordered map, or O(N + J) with hash map.

Work items

• patch
• unit test (large EOF function with many RJUMP instructions)
• benchmark (EOF compilation of contract with complex control flow)