Differential Fuzzing of the Vyper Compiler

Transcript

Hello. Um I'm Charles. I'm actually subbing in uh for our security engineer who was going to present this a different talk but then um he got sick and so I am giving my own talk which is also on differential fuzzing but it's about AI decoding. So uh first of all why does that show of hands who knows what AI decoding is? Okay great. Um AI decoding is extremely hot in the compiler. Um you probably don't think about it much but [clears throat] whenever uh contracts excuse me contracts call each other on the EVM they follow a a standard called AI

encoding and decoding. It's a serialization format um along with some other things, metadata and stuff. But anyways, [clears throat] excuse me. Um AI decoding is the part where you decode data that's been encoded by another contract or in call data or maybe in code or data somewhere and you want to basically deserialize it into your own local memory structures. And there's something that's very interesting about how AI decoding works. So AI the AI spec defines two kinds of data. One is static data. So that's stuff whose length is known at uh statically. So for example, a unit 256. Everybody knows it's always

going to be 32 bytes. Um and then there's dynamic data. For example, a bytes type which has a dynamic length. It can it's variable at runtime basically. >> [snorts] >> So the way that AI the AI uh defines the data layout is it puts all the static uh data in one section and then where there's dynamic data it includes pointers to what's called the dynamic section. Uh so for example if we have some bytes uh this is a tpple of bytes by the way. So because it's a tpple, the AI defines one static field which is the location of the bytes data in the dynamic section and then it has the

dynamic section which is kind of a reasonable encoding of bytes which is the length uh word and then the data. [snorts] Uh a more complicated example is a tpple of a tpple of bytes. It's recursively defined here. [cough] uh and because uh I'm able to use the formatting with the bullets, you can see the recursive structure actually. So you have the static section of the outer tpple uh it points to this dynamic section. So the inner tpple of bytes is defined as a dynamic data structure and then you have this thing which is the inner sorry the static section of the inner tpple and then that points again into the dynamic section of the bytes or

sorry the dynamic section of the inner tpple which is the bytes and then you have the bytes data. [snorts] So uh why is AI decoding hard? Uh so this is from the AI spec the solidity docs. Um and this is how it defines how to write a decoder. And you'll notice that it doesn't really say how to def how to write it. It says uh you could have a strict decoder which basically expects uh the data to be uh encoded in the way that the this canonical encoder that I just kind of outlined. Or uh you could be a little

bit less smart and then everywhere you see a pointer in the static section you just follow it. Um, and so you don't check if the pointers are valid. You just kind of keep following them. And uh, we'll find out why this is kind of problematic in a minute. Um, but why is this a useful property? Um, the useful property is that sometimes people like to have kind of clever encodings of their data. So here's an example of like a tpple of two bytes. Uh, and this user is very clever and because the data is duplicated, you only need to uh write out ox12 34 one time and then in the static section where you

have the pointers to the bytes data, they point to the same location in the dynamic section. And so it's kind of like aliasing. So you can define very clever or interesting structures. Uh I'm getting looks from the audience uh where you you don't really uh encode it in like the obvious recursive way which is like encode this then encode this then encode this. You can have like weird pointers in out uh up around in the payload. Um the other reason why this is a useful property is because the implementation can be more efficient if you don't actually check that the data encoded is like super strict like each uh element

is followed continuously by the next element and so on. Uh you can do again what I just said which is like follow follow the pointers. Um so we've had this implementation of just like following the pointers for a long time. Uh and this uh was reported as a bug by uh Alex Wade a long time ago which is that uh when you decode stuff from call data or when Viper decodes stuff from call data we don't check that the pointers are valid and this is like maybe a problem because like uh here where I where we have uh yeah this is a simple example here this pointer could be invalid. It could be

like ox a million and then when you jump to that pointer or to the data where that points you just like get a bunch of zeros in the call data. Um so at the time we analyzed this and uh closed it because call data is always user controlled. So like even if you can force the compiler to like read like some pointer where it doesn't exactly expect uh you can't really do anything because it's just pointing to data that you also provided. So it's not really an issue. Um so when this this start to become a problem is when we implement the AI decode builtin. So AI decode is a user uh facing function that AI decodes

a buffer of data and the difference between this AI decode and the built-in call data decoder is that this operates on memory. So, uh, this is a very interesting bug. Um, because, oh, you can't actually see the, um, I wonder if I can open this actually. You can't see the the [clears throat] Y which breaks this. Oh, yes. Excellent. So, this is the call data which breaks it.

And basically uh you convince it to read data from ox which is outside of the payload uh outside of the y-buffer. So the way that these are um laid out basically you can force it uh to read data from outside of y which in this case we mutate it in between the invocations to abid code. Um so that's a kind of weird thing right that's pretty uncommon.

Um oops how do we open this again? Control F5 for this. Oops. Whoa. Okay. [snorts] Okay. So, that's kind of weird. And uh this is what's called a talk to apparently. So basically uh if you can force convince the user to like it's time of check versus time of use. So if you can convince like some poor developer to write some code that AI

decodes the same data in between there's another memory right then there's like this weird bug. Um okay so this is like just the start of the journey. So then we like started to fix this bug uh and [laughter] these are some commit messages uh involving some fixes and the whole thing is very tricky and I don't want to get into it too much because of time and also uh it's a little bit inside baseball but basically um you run into a few problems uh one so for example this

is an there one of these is an optimization So like when you notice that the length is zero, uh you think that you can like actually check some of the recursion in the um ABI decoder, but you actually can't because you need to check that some of the pointers are valid. Um so and then there's other weird things where you're doing pointer arithmetic. So the user if they provide uh some attacker payload can force some like arithmetic overflow actually in during decoding. So there's all these kind of like weird pointer things which can happen.

Um and by the way we fixed all these within one 10 minutes. Uh we fixed all these within one release cycle. So these were like we like did some fixes and then we like went through them and found some other issues. Um so eventually what we realized was that we actually need a spec. So we want to allow uh stuff like this which users think is uh important or interesting. Uh but we also want to uh basically avoid bad pointer behavior. Uh and the way we defined it is so here uh this is not even a recursive thing but this is

recursive right so basically the pointers are currently allowed to point anywhere uh and as I mentioned with the call data uh that's okay because the user controls all the data so what we ended up deciding is that we allow these arbitrary weird pointers that aren't like necessarily pointing to continuous things but they have to be within the user provided payload. So you can jump so from this inside thing you can maybe jump out here, you can jump up here, you can jump up here but you can never jump out of it.

And uh along the way we kind of realized that this is impossible to like test, right? Uh which is why this is a fuzzing talk. Um, so yes. So this is what we ended up deciding on. And um, I wonder why this slide is wrong. Is the slide wrong? No, it's not. Okay. Uh so this is so eventually we decided that in order to test this we needed to write a simple implementation in Python and this Python uh implementation is basically the spec and the reason is

that the compiler code for the AI decoder is full of stuff like this. It's long. It's probably hundreds of lines. It's one of the most complicated parts of the compiler. Um and it does all kinds of weird optimizations for different cases. uh because the code is so hot, it really does need to be fairly optimized. Um so what we did was we wrote a spec implementation which is this and it's here and basically it's supposed to be as simple as possible.

Um maybe I'll pull it up if I have time at the end. Uh and then we fuzz it. So we we check that the spec implementation decodes data the same way that the compiler does. So we take the same data, we feed it to the spec implementation and we also feed it to the compiler and see that they give the same result. Um why is this actually interesting? Um the interesting thing is that doing this the naive way where you just like feed random data to both of these um you know implementations doesn't really work. And the reason is that the input spaces is is absolutely massive right like if you

take that bytes example that's like 128 bytes that's like uh I don't know what 8 to the 128 is the size of the input space and also like [clears throat] the any given pointer which is something that could be a problem for us during decoding is a unit 256 and that's like a huge thing we could like run this until the heat death of the universe and ever find a bug. And I just did this naturally because I think about the heat death of the universe all the time. Um, so here, so we we noticed this, right? We started running the fuzzer and we're like, it's not finding any bugs like

[snorts] uh and in fuzzing like you don't want to be like biasing the fuzzer too much. You don't want to be like, oh, but we're not finding any bugs, so there must be something wrong with fuzzer. But like it should kind of be finding known bugs after some amount of time. Uh and if you think about it conceptually like it's not going to find bugs like if you just provide a string of random bytes to this one of these things or whatever uh it's just going to be trivially invalid, right? It's going to be a trivially invalid AI payload. So there's a couple techniques we used.

Uh one is mutating valid data. So you take a valid AI payload and then you kind of point mutate it or you do something weird. You uh take a chunk a slice of 32 bytes and rewrite it into some other 32 bytes. Um still weren't finding bugs. And the reason for this uh is that conceptually when you think about the AI decoder, when you think about it for long enough, I'm probably not in the first five minutes, but eventually you're like uh g whiz uh the only hard things in the AI decoder are actually uh these pointer dreferences because everything else is

straightforward and a unit 256 is just like you copy 32 bytes. You can't get it wrong. Uh when you decode the bytes, that's also just a copy. you can't really get it wrong. The only tricky thing is like ensuring that all the user pointers are valid. So, uh we started doing something which I consider a little bit clever which is uh kind of making the AI payload as full of uh up pointers as possible uh like poison pointers. So we like bias the fuzzer heavily or not that heavily but a little bit. Uh and this is actually the part of the fuzzer which does it. Uh to

when you do the point mutations to kind of draw from things that could be valid pointers or they're like maybe just outside of the range of the valid space. Uh and this is uh interesting because it introduces the concept of like high value data. Uh so I think the kind of uh yeah so this is very interesting right? Uh so here's the important part. We take the for the um data that we're going to point mutate with or like the word you take it and it's kind of bounded by the length of the payload. And like anything in the range of like minus length of payload to

length of payload* 2 or something is probably like a reasonably good thing especially with like um integer overflow. So this checks like all kinds of things. It checks out of bounds overflow off by ones. Um, yeah, I probably have like 3 minutes left. So, I think the takeaway is, uh, that you kind when you fuzz, you kind of want to have an idea of what values are high value, what things are high value, what things are poisonous to your program, and kind of try to guide your fuzzer towards those things. um you don't want to do it too much because kind of the point of fuzzing is also to find bugs that you don't know about. But if you have some idea of what is

poisonous to your program uh then uh which is funny because we're talking about snakes viper uh then you want to kind of bias your fuzzer a little bit with those. And uh here's our in the interest of time have to stop. Uh here's our GitHub Telegram group. Uh any questions? uh no actually [laughter] >> it's it's still running >> please.

>> So uh I missed what fuzzing technology do you use? Well, yeah, there's a library in Python called Hypothesis, and it basically lets you combine different strategies into larger strategies. >> I I I don't know specifics, but I do know that uh AFL, which has dominated fuzzing for the past 12 years, supposedly had exactly this motivation to be really good at finding uh serialization bugs or bugs in big binary buffers uh as input. So I don't know if hypothesis is AFL based uh which is kind of this the library that now many languages use for fuzzing. If it is uh I'm a bit surprised but I don't know enough. So maybe it's completely natural

like you said it's very hard to fuzz those things. >> Um AFL is interesting because it's coverage based right and uh when we're fuzzing the compiler what we're actually interested in is the coverage of the generated binary. Uh, and it's like not that easy to create uh uh coverage based hooks for AFL for the EVM bite code. Yeah. >> Uh, okay.

>> Sorry, my bad. I I just wanted to ask you if you have some thoughts on how you would improve the developer experience of generating custom mutators for fuzzing from your own experience. >> Oh, uh that is a really interesting question because um [snorts] so if you see here uh the mutation uh routine is kind of weird. you like draw from the way I implemented it is you draw from like a list of possible actions and then you apply those actions to the original payload like uh edit add uh delete whatever word um and um that's actually really slow because the way that hypothesis works is

it like creates some weird a full of the possible actions and then it like traverses it so it's like not it doesn't really feel native. Uh so I have a lot of thoughts about that but maybe we can take it offline. Thanks for that. Um, is there anything in particular you were using or techniques to uh identify whether the the fuzzer was making progress >> and like >> that's a good question. Uh, so uh basically we would run it against like various commits and see if it found bugs and it actually uh was pretty effective at that.

>> Yeah. Um, >> but say if it's running for a day, like there's no flame graph or like, you know, if it's running for a day, it's always the problem of maybe if I just run it for a day plus one, it'll find the thing. >> Yeah. Uh, that's uh one of the things that's really hard to reason about with fuzzers, right? Is like what kinds of inputs have you already done? It's really unintuitive. Uh, what kinds of inputs have you already tried? What kinds of inputs are you going to explore next? Uh, like what is the input space and how do you traverse it? Uh so that is one thing I wish we had uh better visibility on. There's like debugging facilities in hypothesis uh which kind of let you inspect this but it's really manual. It's not like an an amazing beautiful dashboard. Yeah.

Okay. I think we're at time. Thanks.