Reconstructing Control Flow Graphs from EVM Bytecode | Maxim Andreev, EVMole | ETHTaipei 2025

[Music] So hi everyone uh my name is Maxim Andre uh I'm software developer I write in different languages and you can find me by handle cdump in github xcom and uh telegram. So in today talk I going to tell you about uh control flow graph. I will overview existing tools which can help you deconstruct to get control flow graph from EVM byte code. Then I will perform uh describe the algorithm which I developed to benchmark this tool. uh after that I will uh present you my new unique uh algorithm which outperforms all existing solutions in term of speed and accuracy and finally I will talk about my open-source EVOL library uh where I implemented these algorithms and some other useful algorithms to analyze EVM bite code.

So let's start. Uh here is a basic uh contract uh source code. It's solidity. It's like uh simple token with only transfer function and all examples in my presentation will be based on uh this program on this contract. So if we compile this with solidity compiler and ask to uh output the binary runtime byte code uh this is this exactly uh binary part of runtime byte code which is deployed inside the blockchain.

So this is what's stored inside blockchain when you interact with a contract and as you can see it's uh just a number of byes and let's start to try to analyze it. The first part we can do is just disassemble it. uh because as we know EVM is uh just stack based virtual machine and uh it executes codes one by one and uh by reading the specification we know that if we see uh the byes like 60 80 it corresponds to push one push one uh 80 operation and if we see byte code uh by 52 then it's m store. It's one to one uh mapping. It's all in the EVM specification.

Uh next part we can uh define a basic block. This is the definition which I use. Uh the basic block um you can read it here. But in other words, it's the part of the bite code, part of the contract program uh where execution only goes forward. So if you start executing the first op code of this uh basic block, then you definitely will finish execute the last operation of this um basic block.

And of course if you are not running out of gas uh using this definition we can uh split the previous uh bite code to these blocks like if we occur if we see jump conditional jump then uh it's by definition start of new block then we have some instructions again conditional jump start of new block uh here we see revert so again by definition we can start a new block and so on. Uh this basic blocks is uh very common in the uh program analysis. So it's um usually the first time of every analysis based on the bite code because it's these basic blocks by definition are very easy and the control flow uh cannot get out of this basic block. Uh if we uh take a graph of these basic blocks connected of the first program from the program from the first slide we can see this one and if we zoom some part of it we can see uh some blocks which we can read. As you can already remember, the first instruction is usually uh push 180 and uh on the 11 offset we have conditional jump and we can take a false branch or the true branch and so on.

Uh same thing for the conditional jumps and uh we can have non-conditional jump where the destination is on the stack. So here we can have only one edge. Here I mark revert blocks by red but it's no matter doesn't matter. So uh there are some existing tools which can help you build this control flow graph from the bite code which is the this are some of them if evmc cfg svm it's written in java rust rust javascript or typescript and python but uh what's the problem here's the slide from my previous talk at ecc7 where I presented my eimo library. The talk was about function selectors and anglements from the bite code.

And here we have the same exactly the same problem. We have some tools but uh how accurate are they? Which one is the best? We don't know like we have some tool like blackbox and no it's not blackbox it's open source set but we don't know how uh how accurate are they. So I think it's uh the first part is which we need to solve.

So here is my uh proposed benchmark algorithm. Uh the first one we need to construct basic blocks. Uh by definition from the previous slides nothing new here. Uh and after that we can filter out definitely unreachable block. Uh because some compilers can generate uh that code.

Uh as you know in the end of the bite code there's some metadata metadata inside the contract. So uh using this technique we can uh find block which is definitely cannot be reach because in the EVM uh virtual machine by definition you cannot jump to the any arbitral location inside the contract. You can jump only to the destination which uh op code is a jump desk. So using this technique we can do it. uh after that we can uh get get definition to the two sets.

The first one is the set of all basic blocks after initial partitioning uh on algorithm from the previous slide. And the second set uh we run some tool on the same bite code and get another set of blocks which is reachable from the start of the contract uh based on the output of some algorithm. And using these two sets we can get to useful uh metrics like false positives and false negatives. The first one is the blocks that algorithm claims reachable but it's definitely not uh reachable by our analysis. And the false negatives it's valid blocks.

It's not marked but reachable by the algorithm. But um as I said uh some compilers especially older version or versions of solidity compiler or if you run modern version without uh enough optimization runs or some older Viper compilers may include uh that that code. So um it's not good but anyway I assume that the fewer uh false negative if we compare different algorithms usually indicates more precise analysis and based on this algorithm I benchmark every uh tool I mentioned before and get this results here false positive is zero which is good but false negatives uh dramatically differs for example the worst One is EVM CVG builder. It's like uh 80% of false negatives. And here you can see uh in the first column is EVM.

This is open source library where I implement the algorithm which I will describe on the next slides. You can see it's not only outperforms in terms of false negatives. It's 3.4 3% of false negatives. uh compared to the second place is 6.

3% but also the execution times is the lowest it's only 34 seconds. uh this benchmark were performed on the uh largest 1K data set which I obtain just I download all verified contracts get top 1k based on the size and assume that uh the most if the size of the contract is the biggest then probably it's the most difficult one because they have a lot of logic inside and so on. uh let's now dig into the algorithm which I implemented. Uh here this is the basic three basic blocks and you can see that in this case we can uh directly see the jump destination here is the conditional jump for the false branch we just uh it's next next instruction like we have 0 B now we jump to 0 C on the false branch and for the true branch uh the jump destination must be on step for conditional jump and it's uh pushed one instruction before. So it's trivial to analyze things like this and every tool which I uh checked can solve this without problems.

this trivial case. But what if we have some uh basic block like this jump desk swap swap pop jump uh we don't know the jump destination. It's uh pushed on the stack maybe 10 blocks ago maybe even in the start of the program. So this analysis is not trivial and uh this is the part where my algorithm outperforms existing tools. So uh let's start the description.

Uh the first part is the ST analysis. Uh as you can know EVM is a stack based uh machine and every uh bite code every op code interact with stack memory storage and uh here we take a look into the stack. Uh I introduce three types of stack values like symbolic stacks like before n it's nth element of the parent stack. So on the input of each block we can uh like represent the stack as before zero before one before two before three and stag rows up uh jump desk if we uh find offset to the valid jump desk destination and the other it's a result from the other app code because uh every app code like it's call up code or store up code somehow interacts with ST but we are not interesting in this during this analysis. So we just mark that some element from the st on the stack.

So on the input we have this symbolic stack. We execute basic block and got some uh another uh stack state. Uh so here's an example. Here's uh stack on the input. It's a basic block and we can execute it uh extraction by instruction like swap two we just swap two values this one with 0 one two with two.

So stack looks like this after swap two after swap one like this after pop like this and after jump like this. So here we can see that the jump destination. So it's before two. So uh let's take uh perform same analysis for each block each basic block inside the program. So here basic block and corresponding stack and now we can uh collapse some stacks for example we have uh some block inside here uh and we know it's jumps to before seven and we want to know uh to which location it's really jump and we know uh stack states for each parents of this block and we can collapse this and this to this.

No, because we just uh take other to other before zero becomes zero. It's a top location of the parent stack before two. And then we just copy the values of the parent stack. And uh same thing for this. So this all this branch can be collapsed to this in terms of the state of stack like modification of the stack after execution of this block.

So here we can see these blocks jumps to some value which is before true and the parent state of the state of the parent is like this. So before two zero 1 2. So it's really jumps to before one. We see that before one is unknown to us. So we need to go up see the parent of this stack to know the exact location of the jump.

So the algorithm looks very simple. We can recursively explore all parent paths until we find jump desk location. repeat until we know all unknown jump destination and we solve it. So here's implementation of this algorithm. It's uh in Rust it's simplified a little but the main state main part is we iterate of the parents of the current location and we analyze the like uh ST stack state.

If it's other we do nothing. If it's CH desk we are finally find the jump location. And if it's before then we need to uh recursively call itself with uh new path and analyze all parents. Um here's the main functions like results this parent it's which I described for slide earlier before the collapsing of the state of the uh blocks get st it's just getting n element of the stack and get parents we have like hashmap of all parents of but we can uh see cycles and that's a tricky part because uh a node can be visited multiple times and unlike uh if you know graph raol algorithms usually uh you use hash set to visit every node only once but we cannot do it here because uh valid destination valid path of execution of the uh contract can visit each node multiple times. So we cannot use this approach.

And uh here I introduce like intermediate states how I call it. Um uh what I use we have uh jump destination which are we are looking for like we are uh trying to resolve jump destination for current block. we know we just jumps to like before three and we know it's parent uh collapsed parent stack and uh I said that if we uh hit this note again and with the same state of the parent and the same stake sim uh then we just trying to repeat ourself and we can uh break early this path. So uh the code before we need to just modify it like only proceed this if state jump is unique like new and uh also another precaution limit the number of operation during analysis for additional safety like if for some reason my algorithm is not working we don't want to spend uh in infinity time so I limit like I don't remember maybe 500,000 operations or maybe less but it affects only free free free contracts of all mainet contracts and by the way all mainet contracts it's about 1 and a half million uh was analyzed in 13 minutes on 24 CPU cores so this algorithm works very well and failed only in small number of contracts and uh of course uh sometimes I cannot find the true location of the ST of the jump. So I uh not not saying that this uh some random value just using uh option of your size.

So it can be none or null if you prefer JavaScript. And then this is how uh analysis results looks like. If it's jump, I output the jump destination. If it's uh conditional jump, I output the true and the false uh vacation. And if it's dynamic jump, then the destination of the jump based on the path we took to get into this node.

And what makes this algorithmic? At first it's a bottomup traversal because all some algorithms which I uh review before uh take another approach and goes from top to bottom. This algorithm avoids path explosion be because so it significantly reduce the complexity and uh it just identifies loops without false positive using this intermediate states and as I said it's all implemented in even more library uh it's a rust and javascript and python library so you can use it from the language which you prefer it's open source on github/cam/eol and uh few words about this library uh it has online demo of evol xyz. So besides the control flow uh reconstruction, it can also extract uh selectors of the contract, the arguments of the function, the state mutability, the storage like this function reads storage at zero slot and the type of this storage is mapping from address to and sign it integer. It's also can disassemble identify basic blocks and build control graph which is you can uh you can interact with it with your mouse.

So it's emoxyz and that's all this is link to the library. This is link to the source code and this QR is pointing to one of these things. I don't remember which one. Thank you. We got some time for questions.

Anyone has questions? So, how would the object format affect affect your algorithm? Uh, so how would the uh work on the EVM object formats? It's not supported yet. I took a look into it.

It's uh quite simple as first look to add it but I postpone it just uh just in case maybe well it will be released I will implement it but it's not the case like it's trivial to it. Thanks for the question. Any other questions? Hey, sorry on some like 300 contracts 333 con contracts that were affected by your limitation on the uh number of analysis steps. Do you remember if there was any like widely used contract among those or uh or not?

Because um I don't remember exactly but I took a look at some of these contracts and some were written in assembly. So it's not output of the compiler and uh some I don't know how it's produced. It's very strange contracts. So at first I tried to fix it. probably it's a bug inside my library but after I perform the benchmark on the whole mainet I found it's only like few hundreds of contracts on the whole whole network so it's better just to ignore it it it's fine very small number one last passion.

Okay, so that was a deep deep dive. I think it's the first time I saw so many BIC code in a conference talk. So, thanks again to Maxine from EV mall. I sh you. [Music]