Reconstructing Control Flow Graphs from EVM Bytecode: Faster, Better, Stronger

Transcript

[Music] Hello. Uh hello everyone. Good morning. Uh my name is Maxim. I'm software developer. I write in different languages like C++, Go, Go, Python and so. And you can find me on the internet by handle by the nickname sedump on Twitter, GitHub and XCOM and Telegram of course. And today I'm going to talk you about uh control flow graph. I will present my new uh algorithm to reconstruct control flow graph from EVM byte code. I will

overview existing tools. I will show you how I benchmark them. Of course, I will describe my new algorithm and we'll talk about my EV mall opensource library. way I implement this and some other algorithms and if we have will have questions time for questions there will be question sessions. So here is a a basic uh contract. It's not ERC20 but some simple contract. If we compile it with solid compiler, all we can see is the binary of runtime part which is uh just uh pairs of bytes and we can decompile it. So basically like 60 80 it's instruction pan uh 80 and so on.

This is like a onetoone mapping just like written in the Ethereum yellow paper. And uh I need to give you some definition like a basic block. Basic block is a continuous. So you can read this definition but I can say it in the other words. Uh basic block is a set of instruction uh such if we execute first instruction block we will definitely execute the last instruction block. So it's block without uh any any possibility to break uh through execution and uh we can uh use this definition to break the uh the compiled output of

previous code to this basic blocks. As you can see, we can break on jump uh conditional jump instruction or the revert instruction because this instruction by the definition breaks the block execution. And if we combine this basic block with ages like uh how can we go from which block to which we can get the basically control flow graphs like basic blocks with ages and you can see like uh more than more than uh one output edge from some blocks because it's conditional jump. We have a through branch through branch we have a false

branch and so on. So uh some different uh tools exist to reconstruct control flow graphs from EVM byte code but uh all they have uh the same problem. I can repeat myself from the previous FCC presentation. We don't know how accurate are them. We don't know how which one is better. We don't know uh like we know that they works for in some kind of way but we don't know exactly how. So the first uh part which I uh did is to was uh introduce benchmark algorithm. It's not uh so easy like uh for the selectors or some other

stuff which I can just ask to solidity compiler to output. So the ground truth is not easy to get. So uh here how I can how I solved it. uh by the definition a basic block uh is continuous uh subsequence of map codes and if we and we can filter out definitely unreachable blocks uh usually it's just a meta data in the end of the contract but sometimes old compiler produce uh more uh definitely unreachable blocks for especially early versions of solid compiler and after that Uh we can uh

um set definition. We get we get set of basic blocks, set of all basic blocks after initial partition and removal invalid blocks and the set of blocks which uh some algorithms produce after control flow uh graph reconstruction. And uh we can now get false positive and true positive. Oh sorry false ne false false positive and false negatives and uh we can compare algorithm by algorithms by this matrix.

So uh false positive uh by definition it's a set of control flow graph blocks uh minus the set of basic blocks and should be empty in correct analysis because if some control flow graph reconstruction algorithm produce block uh which we definitely uh know it cannot be reached then it's it's totally a false positive. visual false negative is not so easy because it may include like dead code but we can assume that a few indicates more precisenmark algorithm. You can see EV mo where my

library where I implement my algorithm outperforms all other solutions in a number of basic block reconstructed and uh the false negative also the lowest and by the way the time um which EVMO uses to produce these results it's only 30 seconds and the second uh place is resolve use 40 times more time to get worse uh results. So uh now I will describe my algorithm.

As I said before, if we have a basic blocks, we can now we need to uh get edges from how can we get from uh each basic blocks to another. And this is trivial case because uh here is conditional jump. And of course we always know the uh false branch because it's fall through. And for the true branch uh in such good cases uh the destination is pushed to the stack in the same block but in this situation even in the previous instruction. So it's trivial case to get the uh true branch conditional jump destination.

But for some other blocks like uh you can see on the right uh basic block consist only for swap and pop and jump instruction and we cannot so we need to analyze previous like parent blocks to get the possible destination of this block and uh to get here to get it uh I introduce tech analysis like to when we enter basic block we have stack which is produced by the previous block. We can mark it like uh some B like uh before zero before one before two. This is uh results from the previous basic block.

Um and we know for every instruction how many uh stack elements it consumes, how many stack elements it produce and we can execute some basic instructions like uh pushes of constants, some uh basic math operations and after that we can uh get the new stack uh like symbolic stack results. I can show you an example. If we have this before, after the swap operation, we have this. After the swap one operation, we have this. After pop, we have this. And finally, we have this.

You can see that the first element of the stack didn't change and it only removes two oper two stack elements. And if we see uh more complicated example and we have um all stack uh analysis uh for each block, we can start to combine them because uh you can see on the right side that uh it's still um unknown for the last block. It's uh depends on the previous and some depends on the previous. But we can combine them because uh as you can see like before zero now becomes before two because we take the first element of the previous st and so on by combining them uh all

that we can uh like explore our parents block and get the final st uh symbolic st result. So in this example you can see that the last block is jumps to something which is before two and uh the stack result for the parent block is before two element is before one. So we need to jump to before one of the parent block and so on. So basically algorithm is recursively explore all parents until we find the definitely jump destination. So we find the output destination of this block. repeat the soul until all uh

unknown jump destination are resolved because some are already resolved as I show you in the first slide where the jump destination is trivial like it's pushed to the stack in the same block and uh get profit but actually this is how this algorithm looks like simplified version uh so basically we have a hashmap of all parents which we premputee. We have uh stack uh element at position for each block which we also premp compute and we can resolve with parents it's which I show you show for slides earlier. But the first problem is cycles because uh

because a node uh node can be visited multiple times and unlike typical graph traversal algorithms we cannot just uh introduce a hash set and never visit uh this note again if you visited before. So I introduced to one another uh thing which I called intermediate states. Uh if we visited this block and the result of the symbolic st is completely the same. So we can uh hash the stack seam. That means if we uh go around we will definitely will go out to the same destination. So we can uh break the uh our execution here because uh we

definitely know that we will never see any other outcome no matter how times we visited this block. And uh this is how I check it in the code. And uh after that I any way need to limit the total number of of operations because uh some contract uh uh very strange contracts. Uh so I analyzed all all mainet contracts with my algorithm. It's about one and a half one and a half million. It's all analyzed in 15 minutes on 24 CPU coursees and only like free free contracts. it's less than uh one

person affected by this limit. So it's fine to introduce this limit. And uh another um um part of my algorithm that uh if my algorithm don't know the result is certainly if it's uncertain it will uh uh explicitly indicates it with uh option this rust code. So I can see I don't know how to the destination of this block. So I just say it's none.

And this is how results from my algorithm looks like. Like like the block starts at this uh pointer extraction pointer ends here. And uh for the jump it's a jump to the predefined destination. For the conditional jump we have a true and false branches destinations. And uh in dynamic jump if the jump destination um depends on the path how we uh came to this block then I produce like if we came from this node then we go out to the this node it's similar like a fee function in SSA analysis if you want know and what makes my algorithmic it's

bottom up analysis so uh I'm not trying to go from top to bottom like from entry point and uh analyze everything. I trying to go from bottom to up and so only part of uh the actual blocks are analyzed which uh um decreases the total time of analysis. It avoids uh path explosions because I uh track nodes which I visited with uh stack with symbolic stacks and uh advanced loop detections.

Uh as I said before I uh introduced this algorithm in my open source library. It's called EV mole. It's available in Rust uh JavaScript, TypeScript and Python. It's fully open source and uh you can visit it on evol.xyz. This is uh demo of using this library. Uh besides the control flow graph uh you can it can um get you selectors of the functions uh function arguments state mutability storage usage and now it's get basic blocks and control flow graphs. And this is how it look like.

You can just uh put contract address. You can uh input the contract deployed by code and then you have tabs with function storage is assembled and control flow graph which is totally interactive. You can play with it. You can uh move it to try understand the uh control contract logic without uh source code of this contract. And uh again this is sources on GitHub. This is uh demo website. And this is QR code to the demo website. And I think we have some time for questions if you have one.

Yes, I see. Thank you. Um and uh I have a question and did the compiler optimization uh introduce any difficulties to your uh algorithm? Yes, of course. uh but I say that the modern version of solid compiler are better than the older versions because in older versions there's a lot of strange logic like uh a lot of dead code and I don't know is it a dead code or is it my algorithm failer so I need to review it with my eyes so I review all errors but of course uh all

these dynamic jumps it's introduced by um by compiler uh because if you run compiler without optimization probably it will get you like straightforward code without so complex logic but I said before uh I analyze all my net contracts and uh everything looks good so only small part of all contracts uh didn't so some contracts break my tool but it's very small number of contracts okay sounds great thank you for the question Hi. Um I think in the beginning of the talk uh you said yourself that um there are possibly different ways to represent

the CFG and if we use a different tools I think they might generate a slightly bit different uh kind of CFG. So how do you approach this problem and how do you compare your algorithm with other tools out there? H yes the same as I uh use for the as I said before my tool also extract selectors arguments and I compare with other tools the same way. So I packed other tools in docker and then write python script to prep-process the output to match the exact format like maybe 50% of the uh programs like other algorithms output in the same way but for the other half I need to do some post prep-processing but anyway I can get the uh like common part the total

number of nodes the nodes entry point exit points and so on that's how I compare it the connection Connections are more tricky what I yeah connection are more tricky that's uh because that's why I only count the total number of reachable nodes which is easier to get from all of it tools. Thank you. Thank you for the question. Is there any more question? Please raise your hand. Okay, no more question. Thank you for the speaker.

[Applause] [Music]