Strange CFG Benchmark Results for SEVM

[cdump]

Hey, I just added Control Flow Graph (CFG) support to my evmole tool and included benchmarks for several open-source tools I found:
CFG Benchmark Results

While SEVM performs very well for selectors/mutability (and for decompilation, though it's not benchmarked), it performs poorly in the CFG benchmark. I suspect I might be using it incorrectly.

Could you take a look at this part of the implementation? https://github.com/cdump/evmole/blob/master/benchmark/providers/sevm/main.mjs#L44

The expected output format is a list of edges between basic blocks, where each block is identified by the bytecode offset of its first opcode. Let me know if I'm misusing SEVM or if there's an alternative way to get accurate CFG results.

[acuarica]

Hey thanks for opening this. Great work with your evmole tool!

I'm at EthDenver this week, but I'll take a look when I have some time.

it performs poorly in the CFG benchmark

It might yes, sevm is not precise in terms of CFG generation. It does loop unroll, so that may lead to different CFGs.

a list of edges between basic blocks, where each block is identified by the bytecode offset of its first opcode

sevm performs basic block cloning. That means that two different basic blocks can have the same offset as id. This is because a single JUMP(I) instruction can have multiple destinations.

[cdump]

Found a bug on my side
Now, the results are much better: https://github.com/cdump/evmole/tree/master?tab=readme-ov-file#control-flow-graph

But anyway, take a look when you come back - there are probably more bugs in my code using SEVM :)

[cdump]

two different basic blocks can have the same offset as id.

that's not a problem and expected, I'm using pc, not block id

[acuarica]

You may want to take a look at

evm/test/dataset.test.ts

Lines 346 to 371 in c981c69

	function coverage(contract: Contract, ctx: Mocha.Context): {
	unreachableJumpDestChunks: number,
	unreachableJumpDestSize: number,
	nchunks: number,
	} {
	let nopcodes = 0;
	let unreachableJumpDestChunks = 0;
	let unreachableJumpDestSize = 0;
	const chunks = contract.chunks();
	for (const chunk of chunks) {
	if (chunk.content instanceof Uint8Array) {
	expect(chunk.states).to.be.undefined;
	expect(chunk.content.length).to.be.above(0);
	if (chunk.content[0] === JUMPDEST) {
	unreachableJumpDestChunks++;
	unreachableJumpDestSize += chunk.content.length;
	}
	} else {
	const block = contract.blocks.get(chunk.pcbegin);
	expect(chunk.states).to.not.be.undefined;
	expect(block).to.not.be.undefined;
	expect(block!.opcodes.length).to.be.equal(chunk.content.length);
	expect(chunk.content.length).to.be.above(0);
	nopcodes += chunk.content.length;
	}
	}

It computes the coverage for a given contract. The results are published as PR comments, see for example #156 (comment).

It's odd that evmole benchmarks report such a low coverage for sevm.

[cdump]

Here is one of the "easy" contracts where evmole benchmarks shows a false negative for sevm:

Contract: 0xeC0797C9a410C71aF3B87443DE8cD81bfC7e0A36
cfg: https://evmole.xyz/#0xeC0797C9a410C71aF3B87443DE8cD81bfC7e0A36/eth/control_flow
evmole edges: [[0,12],[0,16],[16,26],[16,65],[26,43],[26,70],[43,54],[43,106],[54,65],[54,288],[70,296],[106,124],[106,128],[128,167],[128,171],[171,185],[171,189],[189,219],[189,223],[223,311],[288,691],[296,78],[311,456],[311,684],[456,484],[484,493],[484,515],[493,484],[515,580],[515,613],[580,618],[613,618],[618,628],[618,682],[682,684],[684,78],[684,728],[691,311],[728,78]]]
sevm edges: Same as above, but missing [684,728]

The difference occurs in the 0x2bc JUMP destinations. EVMole indicates that the destination of this JUMP instruction depends on the execution path taken:

• If the execution passes through 0x006a (b3eeb5e2 function entrypoint), it jumps directly to 0x4e
  

• If the execution passes through 0x120 (efc81a8c function entrypoint), it first jumps to 0x2d8 and subsequently to 0x4e. The jump destination 0x2d8 is pushed onto the stack at instruction 0xc2c6: PUSH2 02d8