Fuzzing the Solidity Compiler by Bhargava Shastry (Devcon5)

Yeah. Uh let's So with that out of the way, let's get started. Um So like I said, um usually in the in in the information security community, uh the the focus of security testing is uh things like network switches which process uh external data and provide access to private infrastructure. So compiler is not, let's say, a popular target. Um so let me be clear and state that our threat model is not by the user who's a developer.

So we don't assume that the the person using the compiler is malicious, but rather we focus on uh if the code generated by the optimizer is correct, right? So for example, if you have a function, this is uh you will style program. Uh essentially what it's doing is defining function foo which returns X and essentially setting that X to two. So if you And it's storing uh at location zero in the EM uh in the memory the value returned by foo. So essentially you expect this to store uh the value two in the location zero, right?

So And this is what you get on the right-hand side after optimization, which is a straight up store zero two. So essentially we want to make sure that it's uh correct code, right? And it behaves the compiler behaves as expected. Um so for those of you who are not familiar with fuzz testing, fuzzing in a nutshell is essentially like this. So you in a in a loop, you what you do is you generate input and feed that input to the program under test.

And essentially you can do it for as long as you want, but typically uh you won't have any gains beyond a certain threshold. So at some point you do control C or end the whole process. Um it's been shown to be surprisingly effective at finding bugs uh because most often unit tests capture a subset of program behavior and here we random randomly generate things that are usually corner cases somehow and break the program. Um however, applying traditional fuzz testing is limited because our use case is essentially actually testing the compiler and it's very important to generate valid programs for the compiler which means let's say you have the valid program on the left. So let me program on the left which defines a contract and a function foo inside the contract that does something, right?

Um and you apply and the fuzzer let's assume that the fuzzer applies some mutation. A mutation is essentially any operation which tweaks bytes, adds bytes, or removes bytes from the byte stream on the left. So you can think So the fuzzer sees the input as a stream of bytes so uh on the left and just tweaks bytes and adds, removes. So it could create a mutation like the code shown on the right which basically tweaks the keyword function and public, right? Because it's totally random.

So you can imagine that with a very high likelihood a random mutation at the at the input level is going to be simply rejected by the fuzzer and we don't want that because we want to uh the program to be parsed and then optimized and then test the optimizer. So this clearly won't work or it works but it's not very efficient. Um so basically the learning is that uh fuzzing a compiler requires generating valid programs and now generating valid programs requires some sort of structure awareness. Um so, let me talk about what is structural awareness and how we approach this problem. So, essentially we start with a high-level specification.

Uh the specification is written in the interface description language called protocol or protocol buffers, is the whole thing. Um it was originally developed by Google, but it's used for various purposes. Uh also in testing. So, uh essentially uh in the protocol language you can uh define um units of data as messages. Uh and each message contains uh one or more uh fields from other messages.

So, for example, um it's useful to talk of the specification of the U programming language that we're testing in a top-down fashion. At the very top you have uh a program, so the message program, which contains a repeated sequence of a message called block, which we also define as a repeated sequence of a message called statement, and so on and so forth. So, you could you could Although it's not shown on this uh slide deck, you could uh define a message called if statement, uh a for statement, so on and so forth, which contain other fields, and then make statement a union of all these statements. Um you could use the keyword one of to make the union of these statements. Um so, essentially build the specification in a top-down fashion until you have all the leaf nodes, uh typically literals or uh constants and stuff like that.

And yeah, essentially try to cover as many aspects of the programming language as possible. Bear in mind that this is fully uh handwritten, so it's not exhaustive or complete, but for the purpose of testing, the hope is that it covers sufficient language features for us to get a sufficient assurance that uh, things work as expected. Of course, you can find this uh, full spec at the link below, if you're interested. Um, so the next thing is input generation. Uh, we have the spec, how do we convert the spec into a valid input?

Um, we don't generate the input ourselves. Fortunately, there is a library called libprotobuf-mutator, which is also developed by Google, which takes the specification shown in the previous slide deck, and converts it into a valid input, um, which is an instantiation of the spec. So, each input is essentially a tree. For example, it can look like uh, what is shown below here. So, you have it defines blocks, and blocks contains a statement, uh, which is an if statement in this case, and the if statement has a condition, which contains a binary operation, which is an equality, and the first operand of that equality is a variable reference.

Uh, the variable's ID zero, and then the constant that it is being compared against is zero. Um, this is the textual form of uh, protobuf message, uh, for clarity. Um, but of course, this is not doesn't really make sense yet to feed this to the to the compiler, right? Uh, because the Yul um, optimizer does not recognize protobuf. So, we need a program that converts uh, an instance of the protobuf message into a valid Yul program.

And this is where the converter program comes in. So, this is something that we have to write, but fortunately, this is not too complex, um, and it's about 1,000 lines of code. Um, so essentially, converter is a source-to-source translator. The input is the protocol serialization format and the output is the U program. So, we talked about the protocol message in the previous slide.

How it looks like when you convert it to U code is shown at the bottom. So, essentially it's an if statement with a variable called X_0. If it's check that it's equal to zero. Um of course this is a snippet of a larger piece of a program, so it doesn't make sense to feed this to the father yet. But this is just to give you an idea uh how the conversion looks like and what it what's the input and the output of the conversion process.

Uh but in reality we have a complete valid program which compiles and does something. So, to put these two pieces together, what we have is a specification that we had written in the beginning. And the library uh libprotocol fair mutator. We use a library to generate input, but that input is not ready to be fed yet because it's in protocol language. So, we use a program called we write a program called protocol converter which converts from this language to a valid test program that can then be fed to the compiler.

So, finally we have an input that can be used to test the compiler. But then um testing the compiler actually requires encoding an expectation somehow. So, imagine that you randomly test randomly create a test program, but you don't know what it's supposed to be doing, what side effects it has. So, how do you encode an expectation, right? So, what do you check?

How do you check that this it's doing the right thing? Um the approach that we use is differential fuzz testing. So, essentially it involves tracking the side effects of a program using execution trace. Running program and then running the optimized version of program and comparing the side effects. So, we use the original program as a baseline uh to compare against um and we compare that with the optimized program.

So, it's not a complicated However, before we can do that, we need an execution trace which tracks side effects of the execution of the program, right? So, we need to know somehow what is happening to check whether it is happening correctly post optimization. And this is where uh the Yul interpreter comes in. Um yeah, Yul interpreter is essentially an interpreter for Yul programs um that was written by Chris. So, essentially what it does is it interprets arbitrary Yul programs.

So, um yeah. Apart from interpretation, what it additionally does is outputs the side effect of the program as a trace. A trace can be thought of as a string. So, for example, you have the test program on the left, you feed it to the Yul interpreter, it executes it uh step-by-step and then creates this execution trace shown on the right, which can look like you load something from memory from some address X and then store it store the store some value at address Y, do a data copy, so on and so forth. So, we built the execution trace of the test program uh using the Yul interpreter.

And finally, we are ready to actually like put these and put all of these blocks together and test the optimizer. So, we start with generating the the program, feed it to the interpreter, optimize the same program, feed that again the optimized version to the interpreter, and then we get two execution traces which are essentially strings, and then we can simply do string uh equality check, right? So, if uh, the execution traces of both these versions are equal, everything's fine as we expect. If it's not equal, there's a bug, uh, most likely in the optimizer, but in practice we've also had situations where the bug is somewhere else. But, with high likelihood it's the optimizer.

Um, so essentially like I said, we found about uh, this approach to be pretty effective in practice. We found about seven bugs, two of which were optimization uh, rule that was used to essentially optimize programs. Five were in the experimental new optimizer, but yeah, it's not supposed to be used by end users right now. Um, so that's the purpose of testing anyway. Um, so yeah, two were in the uh, EVM optimizer, so it was used in production, but fortunately it's low very low severity.

Um, yeah. Uh, mostly because the the the buggy rule in question had was optimizing constants, so uh, it was it was uh, a very specific pattern that was going wrong, and this pattern could be detected visually because it's uh, a compile time constant, or uh, yeah, that's essentially why it was low. Uh, the others were of course in the experimental version, so that's why we're testing it. Um, so that's what we've done. Uh, challenges remain going forward.

Uh, the main thing is we would like to find high severity bugs before the compiler ships, right? Because uh, that's what matters. Uh, the main problem with fuzzing a compiler for correctness is that it's usually slow it's a slow process. I mean, typically in fuzzing, uh, you select a small piece of uh, code that's security critical and fuzz it, which means typically you would like execution speeds of over 100 per second. But for example, if you want to test uh component uh we started to test the EBIV 2 encoder inside Solidity.

Um uh the problem is that compilation is slow, and this is perfectly fine for the use case because uh developers can spend an additional second or so to save gas, right? Uh the only problem is that if you uh apply for uh fuzz testing, it it it can become a bottleneck. So, um to find ways to uh basically make it more suitable to fuzzing is a challenge that we are currently working on. So, in conclusion, uh we started doing continuous structure-aware fuzzing to detect problems with the optimizer and uh alert us whenever there's a bug in in the in the code base. Um it's has been so far used used for mainly testing the optimizer and data and decoding.

Um it has decent assurance, but bear in mind that testing is not formal. It doesn't give you any formal guarantees. Um yeah, take that with a grain of salt, but yeah. That's about it. Yeah.

Thank you. Any questions? So, how much do you know about uh the coverage that you're able to get with say uh what one day of fuzzing like? Um with one day, it's hard to say, but with said you run it every day, right? So.

Oh, but that it builds a corpus over time. So, we started and then it uh builds a corpus and the the same corpus is used. So, you can think of it as a cumulative curve. It improves over time and then keeps increasing essentially. So, essentially right now as it stands, uh just for the optimizer, it's pretty good.

It's about 90 93% something of edge coverage. Yeah. And we keep trying to keep an eye on it and then see if we can improve it somehow. Do you have an idea of what's missing? Is it Is it syntactic features of the input language that aren't in the protocol buffer specification or is it something else?

Um So Uh I believe the syntactic issues are not a problem right now. Um So So the thing The main challenge is to keep up with language improvements. So new language features get added and that has to be reflected in the the protocol spec. So essentially to keep up with it and making sure that when there's some change uh that change is covered in the fuzzing process. So, yeah.

Um yeah, maybe what is missing is to to check if all branch statements inside the optimizer steps are covered uh at a very low level, but at a high level it's hard to say. Yeah. Okay. How do you decide when when is a issue or not? Because you are introducing some of the goals, so you will have different gas costs.

So when do you decide is a issue or not? So regarding gas costs, the Yul interpreter is oblivious to gas. There's no notion of gas. It just runs code. Uh regarding how we decide, uh basically uh there's a bug file by the fuzzing uh program and we it has a minimized input.

We try to rerun the input and check the side effects. Like it It's pretty uh simple workflow mainly because of the interpreter. So, you get an execution trace which is sort of readable and you compare the execution traces pre and post and it's pretty straightforward. So, it can quickly tell you whether it's a bug in the optimizer or there's some other problem. Of course, like you said, we introduced code and there could be a bug in the code that we introduced.

But, it doesn't take longer than I don't know, a few minutes typically to decide whether which bucket it falls into. Okay. Thank you.