Fuzz Driven Development by Midas Lambrichts
Sometimes you can come up with an easy method to verify correctness, but you struggle with finding actual examples for the unit tests. You know that "For all x it holds that …", but you can't come up with good possibilities for x. This is where relying on fuzzing can quickly drive forward development through providing you with some real examples of what your code doesn't yet cover, allowing you to quickly cover a lot of ground. Together we'll go through the process of using cargo fuzz in order to build a quick program that can squash JSON Patch operations (RFC 6902), touching upon some utilities/libraries from the Rust community (fuzzing tools, serde_json,…), and learning some lessons about what kind of misconceptions you might have when getting started with fuzzing.
Hello everyone. I'm Mira Plumes and I'm here today to talk to you about first driven development when you know that you don't know. So first of all, who am I? As I said, I'm Mia Sami. And by day I'm a senior software engineer for the filling solutions. I am a synthesis. I also have various social media which you can find me. I'm not the most active person. If you have any questions or just want to chat, you can reach me on these for people attending bus. Com. You can also reach me right now in the discord if you have any questions or if anything is unclear. So for the subtitle, when you know you don't know, this refers to one of the strengths of frustration development, and even with a minimal amount of the main knowledge, you'll still write decent software without any major mistakes because post driven development will guide you through it. And you'll learn as you go without having to fear that you've just made a big whoopsy. You only need to be able to come up with one simple thing, some invariant and the rest you'll learn as you go. But to understand first driven development, we first of course, have to understand what Fuzzing is. So fuzzing. According to the rest Facebook, which is an excellent resource for anyone getting started with Fuzzing. First testing is a software testing technique used to find security and stability issues by providing pseudo ran data as input to the software. So basically what it's going to do is just going to come up with random data and give that an input to your software and then it's gonna monitor your software for some things. Most of the time it's going to just see if your software crashes. If it crashes, it'll report that back to you that for this input, something crashed. There are other variants. Sometimes it will keep fuzzing indefinitely and just collect crashes. And then when you say okay, you can stop running it'll, report them all in one go. If that's not clear yet, we'll see also a bit of fuzzing later on. Once we go to an example and that should clarify it for you. Okay, so we are hurting now. First driven development. So first, Roman development is a six step process, which the first one is determining the variant. So that was a seat I was referring to earlier. The one thing that you need to know, this doesn't always need to be correct. You can start with an incorrect invariant. You just need to be able to come with a starting point. Second step, you'll write a first target that expresses that invariant for your Fuzzing target. Sit between the Fuzzer and your software, which can do a bit of manipulation on the data before passing it along to your software. And we're going to run the fissure until it gets as a failure. And we're going to think about why did this fail our software why does this cost a crash or whatever? Then, depending on our reflection, we might just have to write some new unit tests and do some development and then step six. The final step is a non final step because it's iteration. You're going to restart again most of the time, certainly with more mature projects or when you've been stuff doing those driven development for a while. Sorry. Most of time you're just going to return to step re, run your further again until it finds another failure. Another bug in your program sometimes also notice that this doesn't really make sense if you reflect on it. And that might be because your filling target doesn't really express the invariant that you want. So you might have to change your fuzzing target. Sometimes you even after the reflection see that your invariant actually doesn't make sense or isn't very good. So you have to change the invariant. These are the six steps of frustration development. Now let's try to map this on where we were in the wild. You'll find most fuzzers today or fuzzing targets today and that's on parsers or compilers. So the first one is German, a variant for a parser. Most of the time it is going to be it shouldn't panic. It should either return an error or on a cable. Should not panic also goes for most compilers. It should accept or reject, but it shouldn't crash. Then a fuzzing target that expresses this invariant is it take whatever input the fuzzer comes up with and you pass it along to your parser you don't even care about OK, or just an doesn't crash. Then we're gonna run the fuzzer until it fails, which in this case means that our parser crashed somewhere and it panicked somewhere. And we're going to think about why most of the time is just some path you missed or something like that. But since we have a pretty simple posing target and a pretty simple invariant, it's very unlikely it is going to be one of those two. So you're going to write a unit test for this input which just gives an input so that your test coverage increase in any develop suggest the test passes and your trade again in this case most of time back to step three. So now we know first proven development or have seen it for a bit. We're going to write a library which used by using self driven development to develop it. The library that we're going to write is a chase and pitch squasher. Most of you will know what Jason is. What is Jason bench? Assume we have this Jason document to start with two properties, a name with a value myth and a ranking eight. Later on the user gains some popularity is ranking goes up, it goes to rank five. Okay, you gain some more popularity a bit more. This ranking goes up to four. These changes, we can express them as a JSON document itself. So the change from ranking five to four. We can say another case in array, there is an operation there to replace flash ranking. So that property from the root. Let value number with value four. Again, if the user, for example, changes his name and by consequences, ranking drops a lot. There's another Jason patch for that change one to change the ranking to 950 and want to change the name. Those are two patch operations. And this is one Chason pitch. That array is the Jason pitch. The increase in it are the patch operations. So then again, another change ranking shoots up to one. He did something amazing. Another Jason batch an array with one operation in it to change the ranking to the value one. So those are chasing pitches. Now we know what Jason pitches are now the squashing part. So if we have our operations from before Jason patches, we can express the same effect from that starting document to get the same end document shorter. So in this case, we can express the same thing from the same starting document to get the same end document by just replacing the ranking with one and the name with Midas. And that has the same effect scoped out on these documents on starting document. And that's the squashing operation that we're gonna try to do. So now we know what we're trying to write. Okay, that's what our library is going to do. It's going to take this squashing. It takes a lot a set of patches, and it tries to minimize it a bit. So the library is going to look like this. We have a public function which takes the patches and that's going to forward basically to squash operations, which takes an Iterator over all the operations and all of the matches. And for now we're just going to leave to do in there. So we don't have any logic yet. And this is our starting point now. So this is what we're going to use for first Rosen development. So step one, we're gonna ride an invariant coming to come up with an invariant. And this is what I said before. The effect should be the same. So the effect of applying the squashed patch should be the same as a blank. All the benches that were squashed in their order. That's the invariant this is. Then if we do this, it's still correct. It's still the squash is still doing the same thing. So step two, firing target. This is what it looks like for CarGurus, for target exclamation bar. Then the data is what the further is giving you. So we take what further gives us the data, and then we're going to see if it matches an input trip. If we can deserialize it into our input struct, if it can. Okay, great. We'll return it and we will. We'll return assign it to the input variable. If it doesn't, then I return from this function from disclosure so at the future itself. Well, mutate again and try the next iteration because we can't make sense of what it has given us. The input strict itself is two things, one starting value, so we can apply patches to it to see if our squash patch does the same and then the patches them themselves. So if you have that, then we're going to squash the patches from the input. That's where our library is going to do. And then we're going to apply the patches in order that we've been given them, that the further has generated for us to get our normal result. And now we're going to apply our pitch to the starting value to get the squashed results. Andthen we're gonna see if they're the same. They should because it's the same effect. The end documents should be the same. So this is our filing target in this case. So step three running into failure. Nobody has ever seen it is what it looked like when you start a fuzzer. I sped it up with a factor of 100 because it took a while, but I'd like to draw your attention again to that. We still don't have any implementation. We still have to do in there. And by showing this, I'd like to show you that first thing can only show the presence of box and it can show the absence, so it can come up with can, for example of where we fail to a polar invariant, but its Gant guarantees that we're upholding the invariant. And what I'm trying to show here is the duration of the fuzzing before it fails does not equal value quality. Sorry, because again, we still have that to do in there. So step four reflect. Well, it took a while to get our first crash show. It's difficult for the fuzzer to come up with the input struct that we expect. There are some other ways around it. Structure were fuzzing, which you can read about in the first book ebook. You can see the fuzzer with some data, but that's out of scope of this talk. And then this is for brevity. Normally this would come become obvious after a few iterations, but I'm gonna already do it here is that the start state and the pageants don't always make sense together. For example, if a while he might come up with something, the fuzzer might give you something like this that you have a name and a ranking, and then it's the operation. The patch is removed, a non existing property. If we do this in our fuzzing target, it would fail because we cannot apply the patch to the document. So it's not going to fail because we do something wrong or or library can be 100% correct, but purely the patch doesn't make sense on the document. So that's what we reflected about. This is a bit of a shortcut to get you to come along with the next steps because they are bit more important now. So we're gonna iterate. So we saw that we have some problems with our filling target, but it could also be that our invariant isn't that great. So let's take another look at our embarrassing. So what we had was the effect of applying the squash, but should be the same as applying all the patches that were squared in their org. This doesn't express anything about what we're actually trying to do the squashing. I basically can return one patch that is all the other patches together, and that would still have this in varying if we can come up with a variant that also expresses beside the effect that it should minimize it, then we'll have a better progression rule or for development. So as a key Nite among you might have noticed earlier on the example is that if you take the initial document and the document and you calculated the badge between those that you have the minimal disk that can be and we can squash towards if we have all the all the other ones, the beginning and the end, that's the minimal one. You can do a shorter expression of the difference between star and end, then the difference between start and end. So that's our goal. That's what we're trying to achieve. So that's what we're going to compare against. We're no longer looking at the effect, but we're looking at the pitch itself. So to pour this into a fuzzing target, step two, we no longer try to deserialize into the input script. Now we're deserializing into a vector of consequent Jason values such as we ourselves can calculate consequent patches between them. So again, if we can do this, we continue. If we can't return for will mutate again because we don't crash, give us an ext input that might be this Serializable. Also again, because we're going to calculate patches. If we only get one or zero document, we can't calculate subsequent patches. So we're not going to be able to do anything with that same story, just returns it that the user will use it again. Then we're gonna do that actual calculation to get all the patches between all the documents. And we're also going to calculator when I'm calling the global patched one between the first one and the last one, because that's the one that's minimal. That's one that we're gonna compare against, and then we squash the patches and then compare. There's a bit more boilerplate here because our library if you have zero batch operations, it will return none instead of a batch batch with zero operations. So it's a bit more polite, but it's just comparing the minimal diff with what we squash into. So now we're going to run until failure, and then a after a while, this is what we're going to be created with. That the threat and in panic had not yet implemented bigger. Still, we have that to do in there. And then we're also shown what input cost of failure. And if we Zoom in on that a bit, we can see that it's two. One, an array of two and one new line tab. New line. But for us only this is important array of two and one. So first document is two. The second document is one and that the fuzzing target will calculate a pitch between them and give that pitch because there's only one. Well, two documents. One bitch. Give it a bitch to R library, and then we'll hit to do so. Let's reflect a bit might actually help to write something that pass something instead of leaving to do so an actual implementation might help. So we're gonna take whatever the failing input was. In this case, we have two and one. What I like to do is write a helper function that basically does the same as a fitting target, such as I can write these very neat, very tiny unit tests very quickly by just copy pasting that input from the fuzzer into here. So this is our first unit test or logic now is just to do and minimal thing that we can do to make this pass is just return all of the patch operations as a vector, and that would then resolve in the unit succeeding and we can iterate again. So we again brunt until failure. This time we have a bit of a bigger error message at the end that the important parts are the search and failed message. So the left versus the right with the global patch versus the squash patch. And at the bottom again we have the input that failed. So now we have three consequent documents of number 44 and number four and the number seven. And then if I tie this up a bit and make it a bit more readable, the global pitch would be replace the root with number seven. What our library right now returns is replace to route with four and then replace a route with seven. So let's think about this a bit. So I see that if the bot is the same, that I only need to care about the last one. We used to live two operations, but the first one has the same path and it's the second one that basically still has an effect at the end. So when multiple operations are the effort Saint Paul, we only need to keep the last one. So we again for this into a unit test again. Same thing. Only the Empath needs to change this for this and another name, of course. And then we develop. So our implementation instead of just collecting into the vector. Now we're gonna use a hash map from the both to the patch operation. Look to all operations and insert them by their path. And if you insert something that already exists, that is going to be overridden in the hash map. So then to get back into our vector of batch operations, we just train the hash map and only care about the pet operation. The bot, the bot that we use the skis, we can drop them. You only need the batch operations as a vector. So we collected again. So this will make our unit test pause again so we can iterate again. We can re into failure this time. This is what we'll end up with. The failing input would be four and array with two inside it and an MTA. The global patch here will be replaced. The root by an empty array. Wheels or squash operations will still return. Replace the route with an array with number two inside of it, and then remove the first element of the road. So here we see that our previous our previous assumption still holds that the same bot needs to be squashed because this one is talking about a different ball. So for a different Port, we still might have to squash so that's our reflection. Even if the pass is different, we might still have to do some squashing between them. So we write a unit test again and then we develop. This is way too much code to show you, but the main idea is a user RainX tree, which can give you keys. So the pots which are parents or prefixes of the pot you're currently looking at or all the keys which start with the prefix that you give it. So basically children potentially of what you're using and then you have all sorts of combinations you can get into. Not going to show it here for property sake. After you've done the end units bosses, we're going to iterate again. I know fun times, so we're going to run it until failure this time of failing input looks something like this. An empty object zero an empty object. The global patch. It's going to be empty because you're going to compare an empty object with an empty object. You don't need to do anything. Our library will return that the squashed badge is a replace operation with the with the root part and replace it with an empty object. So our previous assumption still hold. This is all operating on the root path, but if you think of it about this is and more in terms of the patches, is that the patches don't contain any information where you come from. If this initial document this empty object was anything else, we would succeed at them. The patch operation would be squash pitch and the global pitch would be the same. Again, be the JSON patches don't contain any information from where you start. It only it only describes where you go to like you start from something and you replace it with and then that value is contained in a patch. What value you started with is not contained in the patch. So here actually, we can realize that the patches themselves don't contain enough information to always come up with a minimal pitch because we don't know what you start from. So that's our reflection this time again, sometimes it's impossible to get that minimal diff solely from the patches. You'll need the starting document as well to be able to come up with that that minimal patch. So we have two options. Now we can either change our library's API, so you'll have to pass in that starting document as well. And that way we can guarantee that we will be able to calculate the minimal is, or we can allow for suboptimal results. If you find it more important that you don't have to give in the initial document based on what you want to do, you're going to develop some more unit tests and or not, you're gonna iterate because if you choose one of those options, you'll have to come up with a new invariant, because for the second one, the allowing optimal results breaks are invariant. So we'll have to we come up with another one or do some conditions on our invariant. So what we've been doing again, the six steps of fuzz driven development. You determine an invariant, you write a fuzzing target, then expresses invariant, your Rene dental failure. You reflect on that failure, potentially develop and do some unit testing, and then you iterate again. Those are the six steps of first driven development. So why does this work? Why this works is because what we're doing on a broader scope than the six steps. So what we're doing is basically we are using a non cognitive process fuzzing sort of further software, which is a program that to try and guide our cognitive development of software. And we just need to provide a simple seed and em barring. So we start with a little bit of cognitive work, and now we have to use kind of and show us where we're lacking in our invariant implementation expression of our invariant. So why this is good or why am I want to use is because the cognitive caps that you might have and you have if you have a limited domain knowledge, they get less chance to manifest because you're not driving. What you're gonna implement. Next is the fuzzer that's gonna show you do here, there's still something missing, and you need to take care of it. So, for example, you might not have or I didn't think about the different parts still having to be combined together for a minimal patch, or that you might have to provide the starting document to be able to give you that minimal pitch. In some cases, those are things that are important to know if you want to write a good library, that I didn't know those, and I'm not sure if any of you already saw those or could think of those. So with a very limited domain knowledge, we still written a library with still with already does a lot, and we don't have to be afraid that we've embedded some of our lack of knowledge in there, which will come back to bite. Nds later on. So with that, I hope that I've given you a new tool to put in your developer Arsenal, which is first brain development. And I hope you have fun at the rest of the conference. And if you still have questions on sewing this cord, so maybe talk to you there by one.