So, you think you can write an EVM decompiler? - Yannis Smaragdakis

Transcript

Thank you. Can everybody hear me? Okay. Yes. Excellent. Let me see if I have a pointer as well. I do. So, I think that's great. So, I'm Janice Maragdakis. Uh, well, obviously the Google slide conversion that didn't work too well um with DDO uh and with the University of Athens. So I'm going to talk about writing an EVMD compiler and try to give you a bit of background. Uh so I'll say what this talk is about in just one second. But just to set the context, uh what we have at DDOB is a longunning EVM decompiler. Uh it's been operating for over se over seven years now since

September of 2018. It's called Gigahorse. It was originally deployed as contract library. Uh now it's uh in the D-DO security app and it's used by many hundreds of people every day to reverse engineer smart contracts, anything that doesn't have verified source code, beat bots, beat hacks, whatever. Uh we have about 10,000 registered users for our service uh already. And we have documented the algorithms in several research publications and I'm not going to go too deeply into the algorithms today, but you're going to get a feel for them, I hope. uh for the most part the decompiler is open source. Uh I'll give you the URL at the end. Uh it's the source level the very last step is

proprietary but for the most part it's an open source platform so you can build on that and many people have already. Now what's the point of this talk? What am I trying to do here? I'm going to try to say a bit about what's hard about building an EVM compiler. Uh how did we do it? How do we do the DDO decompiler gigahorse? Uh is this the only way? What are the gaps? What's still to be done? And to get to that, I need to answer what are the hard problems when we do EVM decompilation. And if you already know, it's roughly these here. Control flow recovery, function recognition, memory modeling, and storage modeling.

So, we'll have a brief view of some of those and a more in-depth view of the very first couple. And the good news is I'm not going to show you algorithms. Uh, so but you'll get a very good feel for them from examples. Uh, so it's you can follow everything I'm going to say here. The bad news is that at specific times I'm going to demand your attention and I'm even going to ask you to tell me what you think. uh because there are key points that will have examples and I want you to follow the example uh because that's the only way to understand the difficulty here. So let's get going. Decompilation uh the Ethereum VM you probably know is

an extremely low-level stackbased virtual machine. So we have no variables. Uh all our operations are on untyped values 256-bit integers. uh we have no functions, no arrays, no nothing. All we have for control flow is dumps and the dump targets are what's called dynamic and that's going to be a major part of what we're going to discuss today that dumps are dynamic and compilers are very aggressive to optimize when they produce EVM bte code.

So in fact we can have even the reuse of the same little block of instructions when it's used in completely different settings like from different functions. You have completely different setups. So you may have different state of the stack but you reuse exactly the same instructions just because of compiler optimizations. So reverse engineering that is going to be pretty hard and we'll see examples. Now let's look at a simple smart contract and again the conversion from Google slides failed a bit with the formatting but you can read it. Uh we have it's not a realistic contract but what we want us to uh to concentrate on is that we have two

public functions simple transfer and transfer with fee. Uh also down here the public f function transfer with fee says that it does a transfer obviously based on the IRC20 interface and it just subtracts default fee and FAFB which come from storage. I'm sorry default fee comes from storage. FAB are arguments and I have a comment here it makes three private function calls. Why? What are the three private function calls here? There are no function private function calls right that we can see. It's just an external call to transfer. I lost my pointer.

What are the three private function calls in the body of this function? >> Subtraction. It's the subtractions. So, we have three hidden calls in here. Is there a way to get my pointer back? Thank you. uh because of the save sub function that gets inserted here for the subtractions. So all of those are going to be low-level artifacts that we'll need to reverse engineer to recover that there's one function that does the safe subtraction and it's called three times in here.

Okay. So when you compile this simple contract you get this that's bite code in hex form and more realistically you get something like this which I had to a bridge so that's not the whole thing it's 710 instructions but that's really the disassembled by code that's the way we should think about byte code and that's extremely lowle and a few of the low-level aspects we're going to see them again a little later in the talk are that All the operations are over a value stack. So regardless of whether I'm doing addition, multiplication, equality check or a dump, everything I get my operants from the stack. And I

even get from the stack the targets of a dump instruction. So where I'm going to go next or I may go next comes from the stack. And we'll get back to that. And again I I lost my pointer. Okay. So we'll get back to these examples. They're just magnified segments from this piece of code because they will demonstrate some interesting things that we want to look at later. Now, what's decompilation? Decompilation in its simplest form can be defined as recovery of higher level structured information from this very low-level bite code. So, it doesn't have to be solidity that we get out. In fact, most of the time it's not solidity. We can

get back you. We can get a structured intermediate representation, but we definitely get something that has variables. It recognizes what's a function call versus what's an if or a for? What's a regular dump inside the function versus a function call? So, we want to have structure. We want to know the structure of the program. Am I now dumping potentially to that instruction or am I doing a calculation with things that are on top of the stack? So that's what we want to achieve with decompilation.

And the output of our decompiler looks like this. We call it tac or three address code. Of course, you cannot read the small font, but I'll magnify some simple parts so you get the idea. I mean, we recover functions. we reverse engineer uh the jumps that are proper jumps inside the code that are ifs or fors versus calls to private functions. So all of these are things that we should be able to recover. Most control flow also talk about variables and not the stack and private functions. Okay, so that's the task of the compilation.

So what's difficult? What are the difficulties? The first two difficulties that I mentioned are control flow recovery and function recovery. Recognizing a function and recognizing how many arguments it takes, how many return values it has, etc. So let's start with the first one, control flow. And we're getting back to our previous example. And you can see here a fragment of code. And in fact what this one does the very top one is it recognizes a call to a public function. So we have a four byte selector here for a public function and we compare it with equality. We compare the call data load argument what

we get from the public arguments with this four byte selector. And you can see we have a jump I here and it directly jumps internally where to constant address 3B in the hex under what condition the result of the equality with this function selector. So hopefully with this explanation you kind of follow the low-level instructions even though we didn't explicitly introduce every single one of them. Now the problem of control flow recovery for EVM bite code is what's in bold here.

I'm sorry. Execution of the code determines the structure of the code. Which means when I have a dump instruction, if I'm going to be able to tell whether it's a dump that corresponds to an if, it's the buck j the back jump from f4, or it's a function call, or it's a function return. I need to find out what's at the top of the stack at that particular point. So that's what's going to tell me all of these things. Am I going to jump to a function entry point and I'm am I going to jump to something unknown that potentially was put there by a caller

and hence I may return or am I jumping to something that looks like it's in the same function. So there's no way to determine the structure of the code, whether I'm doing a local dump or a function call without actually doing a full simulation of the execution or a partial simulation of the execution to know what's at the top of the stack at that particular point. And by top of the stack, you'll hear me say this, I don't really mean just the top of the stack. I mean at any position on the stack. I'm just using top of the stack as a shorten. So in in uh we we also need to be answering at every point any location on the stack is does it contain a jump

label or a runtime value. And you'll see very soon why we'll need that. But this is a good point where you can actually be a decompiler pretty well with very little info. What do you think this segment does? Top segment here. It does a dump and it does a dump. The top of the stack is clear. It does a dump to a constant address, hex 104.

And the second position on the stack has address 4D that we notice is the address right after the dump. So what would you think this is? an if a for a function call or a function return. I want an answer. Yes, a function call. And that's a great theory because that's exactly the pattern that we expect for a function call. We pushed a return address here. So we push the return address which is right after this instruction. We push a constant. we jump to the constant and the function will get back to that

return address because it's going to pop everything and it knows that on the stack there's a return address and it will continue from there. So this segment here with fairly local reasoning we can tell that it's a function call. How about this segment down here though? This segment down here is completely agnostic, right? All it does is some swaps. swap of position three with position one. Another swap. Pop pop pop dump. It could be anything. We don't know what's the state of the stack at that point. The point that we do the dump. It could be literally anything. It could and in fact it could even be different

things re depending on how we got to this point. This is extremely rare but it could happen. It could be different things, different control flow constructs depending on how we got to this segment. Now, if you followed this, you have the structure of what's hard about control flow reconstruction. So, how do decompilers go about resolving this problem? Clearly, we said the problem is execution of the code determines the structure of the code. Well, then just execute the code, right?

That's the pretty obvious answer. Execute the code to discover its structure. And several decompilers have tried to do exactly that. They've tried to do symbolic execution. So what does symbolic execution mean? It means that part of my state is symbols. They are really like don't care variables. All we care about is their identity. And another part of my state is constants. Which part do I care about? I care about the part of the stack that's actually labels that are targets of ifs, fors, function calls. I don't care about the part that has to do with addition, multiplication, addresses, numbers. I'm not going to

execute the full contract. I'm going to execute the part that will give me its structure. So that's the idea of symbolic execution for decompilers. And several decompilers do exactly that. Now to give you an idea I told you that our decompiler has been continuously running since 2018. So for over seven years now during that time if you were to ask people what's the other decompiler that you would use other than DD back seven years ago it was something called porocity that most people here have never even heard of. uh about five years ago it was panoramix which is still in use but has not been updated in many years. These days it's him RS. So

there are multiple decompilers that do symbolic execution which we don't do and they have kind of failed gradually and in which way do they fail and why do they fail and is this inherent? Well here's one example. Let's look at him. RS and let's look at how good it is to recover the code of the contract. Now if you check some metrics that are kind of undisputable like they are external calls inside smart contract byte code or events you expect to see them there in any decompilation. The contract does those things. It does those ex external calls or it emits those events. So they have to be there in any correct

decompilation and they're unique unique signatures. That's roughly what you get from Heimdal versus our decompiler. So you can see that symbolic executionbased decompilers and that was the case with previous ones as well. They fail to recover they fail to reverse a very large part of the code for complex contracts. So why do they fail? Because if your strategy for recovering the structure of the code is to execute the code then in the worst case you have to execute an exponential number of paths. Code as we know has infinite or if you prefer a finite thinking an exponential number of

paths and you cannot cover them all. So even though you need to only simulate the parts of the code that have to do with dump locations with dump destinations, it's still a very large number of paths and you may not be able to always find values to exercise all of them because there's complex manipulation of all values inside compiled code. So the compiler has performed very complex optimizations and all of this can uh make much more difficult the task of doing reliable symbolic executions for all paths. Now let's get back to our original example

here. And if I want to ask at this particular point, at any intermediate point, not the very last one. If I want to ask at any intermediate point in this block, is what's at the top of the stack a label or an integer or an address or bytes from a an AI encoded string or whatever, we wouldn't know for the most part. And that's exactly what complicates the task of a symbolic executionbased decompiler.

Okay. So what do we do instead in our decompiler? We do static analysis. We do an approximation of what the smart contract will do in all possible executions for all possible inputs. Uh so how do we distinguish executions that do things differently? because we clearly need to follow executions that may do different things, exercise different code for instance or use the same basic block uh in different ways. Uh we use what's called generally context sensitivity. So we classify executions into a finite but pretty large exponentially large in the worst case number of bins. And we use exactly the same algorithm which is an approximate over approximate algorithm

to tell us which part of the code will involve jump labels versus numbers, addresses etc. So I will give a very very high level view of our algorithm. At a very high level our algorithm can be simplified to when calling a function do we need to remember where it was called from? Where it was called from? Yes. When a function returns, do we need to remember it was ever called? No. Of course, the algorithm is a little more complex than that, but that's kind of the strategy for keeping a finite amount of context and distinguishing executions fairly reliably, and you can read more

about that in in several papers. Now, we went in great detail through the problem of recognizing control flow and I want to use this as an example for all the other problems that I'm going to discuss much more briefly because we have exactly the same shape of problems when we're trying to recognize private functions. Uh we need to recognize how many arguments are on a st on the stack at a particular point. when I return I need to recognize how many values are being returned compared to how many were being passed in. So all of that has to again do either a symbolic execution or an over

approximate static analysis of some kind. So again we need some complex algorithms. It's a fairly difficult problem. Now this wraps up the first couple of difficulties control flow and function argument and return recognition. How about difficulties three and four and I will be much more brief here. So memory modeling is a major major difficulty in EVM decompilation. So you probably know already that in EVM in the EVM we have storage and memory and now we also have transient storage but it's pretty much the same as storage for our purposes. So

memory is a transient scratch pad. It resets at the beginning of every transaction and it's used for any data operations over an unbounded amount of data like arrays and strings. So if we look at a contract that looks like this and it does some simple things that these simple things actually hide a lot of complexity. We have persistent storages. We have arguments that get passed through memory. Uh every hash operation hashes inside the memory buffer and the return gets also passed to memory which means that very simple things like this get translated.

Actually this is very high level intermediate language. This is much more than the three address code that we showed before and it's still this long. It gets translated into several loops that go and copy those arrays from storage to memory etc. So it's pretty hard to reverse engineer everything that the compiler does with memory. We heard earlier today things that will become much more complex with the spill region of SOLX or when the full solution for stack 2D comes to sol uh where we will have a spill region. Decompilers will need to recognize that that some memory locations are being used for local variables that were spilled over because

they were more than six in positions deep in the stack. But even now it's pretty complex to reverse engineer memory operations. So you to do this you need to reverse pretty arbitrary pointer computation. Uh this is based on the solidity free memory pointer and every decompiler or decompilation approach has to do something like that. We have our algorithms. Uh Certora for instance has similar free memory pointer modeling in the reconstruction. And of course, this is complex recovery that's only getting worse. So to wrap up with kind of an overview of the difficulties, I'm going

to give you a fairly subjective status of the compilation from my point of view and where I think there's promise or there where there's need for much better algorithms and where there is promise. Now these are numbers just to give you some intuition. Uh clearly arbitrary but I would say right now in terms of recovery of control flow we are doing very well very very well. Now of course you may want to do it differently. It's really tempting to try to do this with a symbolic executionbased algorithm instead of static analysis. In some cases you will get more precision and it

may help with other steps like memory modeling but right now for our decompiler for instance control flow and storage modeling which I didn't talk about much uh we have an upcoming paper we'll put it up by the end of the month the final version uh but we are doing fantastically well in control flow modeling and storage modeling function recovery not so well but It's kind of just effort. Memory modeling. Well, that's the big open front there. If you really want to make a difference and get good decompilers better than the current state-of-the-art, well, you will work on memory modeling. Uh right now the best

we have is we recover let's say 90% of the memory operations. We can lift them to something higher level and it may never be 100%. or if there is there's definitely a lot of room for pretty ambitious approaches over here. So I think that's the number one need and of course this is secondarily a big need in the sense that you may do it differently than the way we do it and you actually may get pretty good mileage but you have to invent good ways to do it because it's not that easy at all. So that's pretty much all I had to say. I think I gave you an idea for what's hard about EVM decompilation. What are the

challenges and what's the current state? Uh we our decompiler the third incarnation of Gigahorse is open source. This is the repo. You can find it pretty easily by googling. You don't need to follow it from here. And of course uh you may know that it's deployed on our security app. uh and you can use it for contracts on eight different EVM chains. Uh as they come in, they get immediately decompiled. Thank you very much. >> Thank you so much, Janice. Wonderful talk and love the energy. Um we have a couple of questions for you. How much easier your work would be with EVM

object format? So the first two problems assuming that all we would have is uh calls inside object regions inside function regions and they are well formatted the first two problems would be much easier. Clearly the control flow recovery and the function recovery. If you put signatures of functions and you have an explicit call function instruction inside the EVM, of course these problems go away if you ensure that that's the only way you can call functions. So of course you could do that. But at the same time I could

say well why not execute solidity right away? Why do we need EVM? Is it I mean we could interpret solidity, right? Why do we need a bite code? So it there are a number of solutions if all you want is to make this problem go away and the eof was one approach that had its own set of complications but certainly it would solve the first couple of problems but it would come with its own set of complications. >> Next question. uh can you say a little more about the use cases and value of decompilation?

>> The use cases of VA and value of decompilation. So the primary use cases right now are for reverse engineering. And why would would you want to reverse engineer? First of all, every time we have a hack. Everyone, every security researcher in the world comes to our site to decompile the hack contract. Secondly, bots. Uh all all sorts of bots are deployed without source code. People want the obscurity when they deploy bots. Everyone else wants to know what the bot is doing. Thirdly, verification.

Uh we had a very interesting case recently by a major major bank international. You've heard of them and a major major partner of them in deploying smart contracts. uh who is giving them the source code is telling them this is the source code for that deployed contract but we're not going to tell sourceify or etherscan or anyone because we don't want this code verified there's no point for us but the bank wanted to know that their partner is telling the truth about this source code matching that contract and what they did was they use a decompiler instead of a compiler so it's there are all sorts of applications but primarily I would say Reverse engineering hacks and bots is

the main reason uh why people come and decompile smart contracts. Of course, also all sorts of learning purposes. You want to know what exactly a piece of code is going to do. I mean I may have audited code where I actually go to the decompiler and see specific patterns how they get translated and whether what I think is happening with memory and storage is what's exactly happening with memory and storage. For instance, >> does solidity have sorry um the first one. Do you think your decompiler can find or reverse search categories of private functions like an ERC721 slot calculation that got mangled by the optimizer?

>> So our decompiler so the question again is whether we can find all categories of private functions. uh we don't guarantee that we will find all private functions but if a private function is used from more than one place in the code uh very likely we will find it we will reverse it in some cases we even we will even prefer not to find it though uh when we actually get better behavior both the compilation and general static analysis by inlining very small functions. So it's never explicitly our goal to recover all the private functions, but when it's worth it, when it seems like

it's worth it, it's going to make the code much more understandable. We do try to do that, but it's a soft goal, let's say. >> And one last question, uh, do you consult selector databases to figure out the signature of functions, events, and errors? >> Um, yes, but we maintain our own these days. So we don't consult external databases because we have compiled many hundreds of thousands of contracts and we've gotten signatures ourselves. So we pretty much have uh a more complete database than what public or equally complete let's say. So yes we do consult a four byte database but nothing external at this point.

>> Awesome. Thanks. Um there are one or two other questions, but since we're going to break out for a coffee break, maybe you can catch Jiannis um during the coffee break to ask uh your questions. And the coffee break it will be right outside in the lunch area. Uh enjoy. We will be meeting here again at 400 p.m. sharp to begin with the next set of talks. Thanks.