Fuzzing the Solidity compiler

Transcript

good okay so my talk is gonna be about using semantic testing framework to find box in the solidity compiler a brief note of introduction I'm a security engineer in the solidity team at B theorem foundation and most of my work involves like I said using semantic testing tools to find security critical bugs in the compiler before it a ship to end-users for those of you who are getting a bit impatient already this is a brief summary of my work or the talk that I'm gonna present before we set out to find security bugs in a piece of code

we need to define a threat model in other words what is the class of bugs that we are interested in and what threat it poses so for us the threat are the class of bugs that we interested in finding out are those that lead to incorrect code generation and these this is exactly the class of thoughts that we want to find before a compiler is shipped to end-users and the approach we use is a form of semantic fuzzing which is based on a specification so we generate randomly we randomly generate programs based on a handwritten specification and use this to get an assurance that most of the optimization

against randomly generated test programs he's done correctly and if it's not done correctly then we have an example use case where optimization is done incorrectly and that we flag as a bug for future investigation now this approach has been quite useful in practice so far we found about nine bucks using this approach in the solidity optimizer all of which have been of course patched by now and inspired by the success we continue to use this approach on a daily basis in a service that is called as continuous fuzzing so essentially every day solid

lead to solidity code is tested continuously so that as soon as we find a bug become to know about it and we fix it as soon as we find so let's get started as I mentioned in one of the earlier slides it's important to start with tread model and our threat model is the class of bugs which in which demonstrate a bug in the optimizer by which I mean let's say you have a program which after optimization behaves differently than before it was optimized which means that perhaps optimization was not done right

what we clearly exclude in this threat model at least for the class of bugs we call security critical our bugs which do not expose a bug in the optimizer in other words we explicitly don't consider the compiler user or the programmer to be malicious and we exclude the class of bugs which result in benign compiler crashes this light is mostly intended for people who are unfamiliar with fast testing so I'm going to give you a brief introduction in a nutshell fast testing means essentially in an iterative way in

a continuous loop generating random test input for a program on the test and essentially this process completes either when you found a bug or you've not found a bug but you are fairly satisfied that the input space that has been explored so far by the Father gives you some assurance to go ahead and ship the software so it's somewhat arbitrary but it's actually quite useful in practice and traditionally fascist ting has been pretty as simple as it sounds it's been pretty successful in finding some interesting corner cases in a vast variety of software now I said that it's

actually quite useful but done in the naive way randomly generating test inputs is not very useful to test programs such as the compiler and the reason for this is that let's say we start with a program that is shown on the left side which is solidity pseudocode and let's assume that it's synthetic syntactically well-formed and let's say the father generates a random mutation which results in the program shown on the right and you can clearly see that we are quite likely to end up with a mutation in which the father has essentially turned some essential

keywords into garbage in this case the keyword function and the keyword public and what this does is that it makes the test input unpossible and this is a problem to test the optimizer because it's right away rejected by the solidity parser so what we require is an approach that preserves the syntax of the target language and not only that in the best case it also introduces interesting language constructs that explore different parts of the optimizer I'm going to describe how we do this in the following slides so so far what we know is that the naive approach of

fuzzing which is to generate random test input is not very useful to test a program such as the compiler whose input is actually structurally well-formed so we needed we need an approach which takes this structure awareness into account so let me get started with how we do this our approach comprises three steps in step one we write a manual specification of the target language under test in this case it's actually Yool Yool is an intermediate language used by the solidity compiler for optimization purposes so what this specification

looks like is shown in the slide deck we use the protobuf interface description language developed at Google to write such a specification and the fundamental unit of description in protobuf language is something called a message so we can use this to define the syntax or the grammar of you'll in a bottom-up manner in such a way that we can define a block or a basic block to be a sequence of statements and upwards a program as a sequence of basic blocks of course I've left out a lot of different constructs to make it easier to comprehend but if you are interested I've linked the full

specification below so we use the product of entered interface description language to define what you'll syntax looks like and in step two what we use what we do is we employ a library called the lip root of mu data this has also been developed at Google and what lip wrote above mutator does is it accepts protocol specification and essentially generates random variants of messages that conform to the specification so you can think of it as a random generator of the specification that you write in the

end each input that lip wrote above mutator generates is a tree and in text form it looks vaguely like jason and as shown in the slide below it's not important to understand what this encodes because going to describe it briefly in the next slide ech in step three what we do is we can work this protobuf message into a valid you'll program of course this is necessary because we are ultimately testing the you'll optimizer so it does not understand anything other than the you language so we write a simple program called the converter which

accepts a valid protobuf message and converts it into a youth program so using these three steps we can in the end generate valid youth programs that can be used as ten test inputs for the optimizer so to give you an example I have tried to show what it looks like when a valid code snippet from the pro buff interface description language is converted into you so essentially the product of specific protobuf input consists of a block of statements and the statement consists of an if

statement whose condition is a binary operation we is an equality operation of a variable reference assuming that the variable has been previously declared and the constant zero so essentially this converts to the you'll snippet shown at the bottom of course this is a very simple example and already the protobuf language has made it a little more verbose but in practice we have longer sequences of such wrote above messages that we use to essentially encode a full-blown valid you'll program so in summary the workflow looks like this we

start with the manually written put up of specification shown on the left we use the lip wrote above and lip wrote above mutator libraries to generate various messages based on the spec we use a converter to convert East messages into valid youth programs and finally use these test programs to test the optimizer and see if there's a bug or not so if I have spoken about test input generation but actually we need an Oracle to decide whether there is a bug in the optimizer or not so how do we decide whether there's a bug for this we use an approach called differential

fuzzing which comprises four steps first we practice X of execution of an arbitrary you'll program I'm going to describe this briefly in the next slides in the next two steps is what we do is first we run the program that has been generated by the father and subsequently converted and obtain an execution rate trace of this program and second we optimize the same program and rerun it again and obtain other execution trace in the final step we compare the execution traces or side-effects of these two sets of programs now since side effects and capsulate

semantic properties of a program they have to be the same if we are executing the same program so whether it's optimized or unoptimized the side effect has to be the same so we can conclude that a T of the side effect of the two sets of programs is different then there's a it's most likely that there's a bug in the optimizer so now I describe how we obtain execution trace of an arbitrary you program for this we depend on the yule interpreter which essentially interprets an arbitrary you'll program and outputs the side-effect of the input you program as a trace or a string so it looks like

so on the left it takes a test you'll test program as input and outputs an execution trace the execution trace holds the side effect of the program that was executed it contains the sequence of fuel instructions that were executed and the side effects they had on storage and memory so putting all of this together our fuzzing setup looks like so we use a proto buff based program generator and we use a converter to convert this into you that is randomly generated is then fed

to the interpreter as is and also fed via the optimizer and these two programs are then compared to see if they have the same side effects in most cases they should but in very rare cases it's possible that they don't and when they don't it's quite likely that it's because of a bug in the optimizer and that's how we flag issues for further investigation more recently we have been experimenting with an additional plugin to improvised on the program generator to recap I mentioned that we use lip protobuf to generate programs but

recently we found that randomly generated programs may miss certain customizations that are required to test specific portions of the optimizer for example with what probability a certain construct is inserted or not so to make use of these customizations we've started to write a small plugin to improve on the program generator for example one simple custom mutation could be negation of a boolean condition in a branch statement so for example it's assumed that a small snippet of the code generated by the program program

generator is if x 0 equals 0 the custom mutation could NP mutate such a program such that the boolean condition is negated and this turns the test program from the one shown on the left at the bottom to the one shown on the right with the conditioned flipped now this is a very simple example but in practice it's often necessary to have mutations that essentially insert those you'll statements that cause difference in program control flow so for example in adding new statements such as break

continued return or leave such as these statements is often necessary to test various portions of the optimizer so using this approach like I said we found about nine bucks so far seven of them have been in the EULA optimizer and one in the sorry two in the optimization rule if we were to break down which component is affected but fortunately a significant the majority of these bugs were found when the yule optimizer was still in an experimental phase so they did not

affect production programs but in any case we were very quick to release patches so that the impact on end-users is minimized also another observation is that most of these bucks if you were to classify them according to security severity level most of them have low or very low severity and the reason for this is that the either can be already found during smart contract testing because they're simple enough to be flagged or that they require multiple prerequisites to be

satisfied for the buck to manifest and in most of these cases we find that the set of conditions that need to be satisfied for the bug to actually manifest itself is actually quite far-fetched in practice that's why most of them are low severity of course I spoke about custom mutations and one success we've had with these custom mutations is that a medium severity bug was actually found and this goes to show that customizations can always help so this brings me to the end of the talk in summary I presented to you the approach we're using called

continuous structural we're pausing to test solidity and its optimizer on a daily basis I mean of course the end goal is to find bugs very early and of course that will help us fix them early as well and this has been particularly useful to test the optimizer and of course data and in decoding which I didn't speak much about because most of the talk was focused on the optimizer our experience has been that this provides a decent assurance that the code has been well tested of course we have evidence that it works or it doesn't because if you have a failing test case this can be immediately flat for further

investigation but we need to bear in mind that a testing does not provide formal guarantees so this makes it important to continue the investigation on what can be done to essentially improve test coverage on the one hand or the likelihood that certain components of the optimizer are well tested which is what we've started to do recently thank you for your attention and I hope you had the opportunity to attend my colleague stocks which were yesterday and today if not you can always watch the video [Applause]

as you some question hi this any false positives or false negatives down the line when you are doing fuzzing and how we do that if so false positives are relatively easy because you can quickly determine reasonably quickly determine whether because you have an input test case which you can debug you can quickly determine whether it was the optimizer optimizer which which is the root cause or some shortcoming in the fuzzing setup false negatives are harder but of course

we need to bear in mind that in general testing will have false apostles negatives so the way we deal with false negatives is essentially on a manual investigation basis to check if test coverage is sufficient if all code paths are being covered or to essentially experiment a bit with the kind of test inputs that are generated if certain classes of inputs are missing so what can we do in the fuzzy to generate these inputs so it's a much more harder problem to solve yeah thanks first a thank you for your presentation

a question which is maybe a hypothetical but still interesting sir how many low level of optimization you have in the compiler is it possible for someone to include some security vulnerability on purpose for some member of the compiler team in order for the thing to be you know stealing some money or whatever so are you is it other places in the compiler compiler where only a few people understand or some optimizations that they're done by hand so are the places and the compiler a few people understand we are a team of I

think nine people or 10 people don't know so yeah I I believe we have contributors from outside so it's hard to define how many people understand but I think in general for any piece of software you could have an insider essentially introduced a bug I think there was a paper by I forget the name of the author in the 70s which showed that a cleverly designed compiler could introduce bugs but of course I mean that's not our purpose our aim is I mean the reason we are doing this is actually to find bugs soon so for us the more interesting threat is accidentally

introduced bugs causing problems so yeah you you you you use random generation to find bugs is it new random things every time or is it random once and then the same random thing over and over again every day it's random every time okay then how how long do you let it run before considering okay there is no bug

when you enter a new feature new features in the compiler I believe we don't have a precise definition for how long to run but the service that we use is called Google OSS fuzz and that runs every day for at least a few hours so if something has not been found for a few hours it is likely we miss it but it's in practice it's been quite unlikely it either finds it very fast or something is missing and we need to do extra work like I

mentioned the customization feature to actually find a bug usually we I feel that a few hours of fuzzing with a good set of inputs that has been accumulated over time it's efficient also bear in mind that the so called test input is a cumulative accumulation so if we start from d0 and let's say we enroll this project over two months ago so we have accumulated 60 days of inputs so it keeps getting better and better hopefully so it makes it easier to find new bugs but having said that like I said it is possible like the father itself has blind spots so it's important to customize it from time to time thank

you great talk Raghava thank you I was wondering whether you benched the Prada both mutator and orally fahza against other buzzers so have you have you looked at hunk foes have you played with I think Google released a few days ago fuzz bench that allows you to basically use your OSS first project and bench it against a whole sorts of different puzzles I'm just trying to understand if there's a few guys have done nearer sort of benchmarking to pick up a particular technology if that makes sense

no we've not done that I saw the project recently it would be definitely interesting to do that just just to know if we are missing something that some other father can catch so as far as I understand we need to somehow convince Google to add solidity to their benchmark so that we could use it or maybe we can treat tweak it ourselves but it will be definitely an interesting experiment to see if you're missing something yeah thanks for that you in the user permission no well thank you [Applause]

you