Going Beyond 100% Coverage

Transcript

All right, thank you for having me. I'm Alex. This talk is called going uh beyond 100% coverage. Uh very briefly about me. I run a audit company that specializes in stateful fuzzing um for DeFi. We are EVM only. I um um used to be a developer. My smart contracts handled hundreds of millions of dollars. And from that I decided to I decided that fuzzing was uh uh very helpful for security. And so I basically started recon with my co-founder Antonio Vano.

Um my experience as a researcher uh I basically have about half a million dollars in uh bounties and uh contest wins. And this year thanks to stateful fuzzing I prevented a critical exploit on Ethereum mainet. Uh basically saved the protocol and prevented $20 million from being stolen. Thank you. And uh yeah, if you want to check what we do, we do effectively audit powered by invariant testing and we also have a platform to run this type of test in the cloud and soon we'll uh do our best to fully automate that thanks to AI so that nobody has to maintain this test anymore. So this talk is about uh coverage. So uh I'm going to take you past 100% coverage. But before

we can get to that, we need to uh get to 100%. So obviously there's many definitions to coverage. It could be line coverage, branch coverage, modified decision and condition coverage. But for the sake of argument, I'm going to use some new terminology that hopefully shows you the idea visually. I'm going to also show you uh one of our internal tools related to that. And so even though coverage is not the holy grail in the sense that you will find all bugs, it is still the best metric we have to measure our progress. and uh we would evaluate both formal as well as concrete tools based on their ability to test various combinations. Therefore, it's not the full picture, but it's a very

good guiding function for progress. Um I'm going to quickly construct this idea of a coverage class. U we're going to quickly see them. So if it's a bit too abstract, don't worry. I'm going to dig deeper. But fundamentally, given a function, we're going to take all the storage values that can influence it. We're going to take all the inputs and we're going to create some sort of a mathematical group where we have the storage combinations and the union with all the possible inputs and we then specify all the possible coverages that derive off of that. Therefore, we can have three types of coverage classes. We can have a non-reverting coverage class which is what we would use to explore state and explore combinations. We would

have a reverting class which for the purpose of fuzzing is not particularly useful but it could still be useful to identify the service attacks. And lastly we would have an assertion breaking coverage class meaning a um set of inputs and states that would lead us to break an assertion. This is the type of targets that we want to hit for invariant testing. And uh if these ideas sound roughly similar it's because I didn't know that other people already wrote about them. You can likely find them in the literature as extended EPAs, extended enabled preserving abstraction or as the idea of modified condition and decision coverage which is how NAZA tests its own uh software. Uh but the key idea is really we analyze its

function. We look at the preconditions, the various states as well as the inputs that will reach that specific coverage and we group them together because symbolically and mathematically uh they belong to the same group and um so when we want to visualize them I'm going to show this internal tool called the um the liner and basically I have a simple function here from liquid governance and you can see that we have various paths. This is very similar to how a symbolic tool um will think. We basically have a case in which we have zero votes. So we have an early return. We have a case in which we have non-zero votes and the payout per votes is non zero. So we will cover the entire function. And then we have a scenario in which there are there

are non-zero votes but we also have zero um uh total votes and I think we got a revert or something like that. And obviously this becomes insanely overwhelming. You can see a very small function from liquidity governance again. Uh, and this this will probably drive anybody insane, but I'm not advocating for you actually doing this, but I'm advocating that as you um formalize your auditing process, this is how you formalize it. This will guarantee that you have effectively went through all the combinations. And so even though this is a superhuman, I wouldn't define this as um impossible nor useless. So as I said, I would suggest this is how I would say that an

auditor could quantify that they're done and yet we will still miss bugs. So the takeaway from uh thinking about coverage classes is that formal tools as well as fuzzers could visualize their progress through these uh v um UX uh stuff and they will basically show us the progress that they're making. Obviously the uh real holy grail of coverage will be puff coverage. uh meaning you try all the combinations symbolically for all possible inputs. But fundamentally even just having the ability to know that we explore certain of these combinations is a massive step towards in terms of improving the developer experience as well as the ability of uh guiding the

fuzzer or at least getting some feedback from the formal uh tool which at this point would just tell you that it uh timed out giving you no particular actionable insight. You can read more about the uh my my notes. Uh this is a GitHub repo I open sourced and it will likely continue to change as I read the literature and think about this more. So this is kind of the let's say the uh more academic part of this whereas now we're going to uh go into the more pragmatic uh aspect. So the key question is really why can we hit 100% coverage?

Why can I give a any tool a fuzzer formal tool etc the ability to explore all these states and I can still miss bugs? This is really uh the the key question and uh as I said even symbolically we could explore all the combination and still miss bugs which leads us to the fact that uh coverage is insensitive to the bugs. Uh and more specifically, it's the equivalent of you going on a hike and uh being so focused on just making it through the hike that you miss all mushrooms, whereas somebody else that is more experienced can enjoy the view and can fundamentally pick uh those mushrooms. So my uh intuition is that obviously code is math. we can

express coverage as a set as a system of equations that we have to resolve and therefore bugs must also be a property of the math that we're looking into. So I don't really have a exact answer. I can't point you to a formula to find a bug. But I think we can all agree that if you have a system of equations that gets you to coverage then you have to do something to that system of equations in order to find the bug. There is a missing piece there. And um over time I think we're going to zoom in into a few types of bugs although obviously we may never be able to find all of them. So as I said symbolically the you have a formula. So likely there is a more complicated formula that is basically uh

exploring less state space. And so if coverage if what whatever gets me to cover this is a elegant formula then there's likely a uglier formula which is likely the intersection between the formula that gets me to coverage and some other property that will lead me to a smaller state space and basically will lead me to the interesting state space and bugs which is kind of what we do as auditors and as such uh I think there's a big parallel between this idea symbolically and then this idea uh uh pragmatically.

So um yeah, my key insight or my key fees this year for this talk is that for the for the purpose of um you know making you think and giving you something actionable, we're going to effectively extend the definition of coverage by adding more to that metric. Meaning that we're still going to use coverage which as I said is blind to bugs. So it's still fundamentally a faulty approach. it's a um we're we're likely to still miss bugs. However, as we introduce more effectively more lines, more aspects of the code as part of the way in which we evaluate coverage, uh that that gives us a chance to uh miss less bugs that um that that effectively match with this uh

framework. So this is the key um idea uh fundamentally uh this is from academia um having a uh high coverage doesn't strongly correlate with finding bugs. However, having a big test suite that effectively chunks the code into various components does correlate with finding more bugs. Meaning that if you normalize for test size, meaning you you just take the minimal set of tests that will lead you to coverage, you are actually coverage is not particularly effective.

However, in practice, just effectively throwing a bunch of stuff uh into your test is is uh is actually fairly effective. And so the real the key idea is really we're going to uh extend coverage by adding new lines. And I'm going to talk about exactly these lines. So this is where this becomes a bit of a esoteric talk, a bit sci-fi. Bear with me. Hopefully the journey is worth it. So the first level of new coverage or extension of coverage will be implied lines, which is the idea that some lines of solidity imply other lines that either the compiler is adding and we're not seeing or that are executed through the node. A uh a pretty good example

would be message of value or a token that doesn't return boolean such as USDT. These lines of code are implied by the code that you're writing. So when you write a for loop with message of value uh being sent in a loop, meaning you introduce a fairly simple bug, the the lines that you're that you're supposed to be covering, the lines you're supposed to be testing for are in the EVM node. As such the um coverage the way we measure it which is just line coverage or branch coverage on the contract is completely insensitive to that because it's not accounting for the fact that that code is covering those parts of code and as such if we add a

way to incorporate that we will find bugs. Another great example would be a overflow where a overflow is effectively the operation or it happens because we introduce a value and then the compiler automatically inserts a mask to alter that value. As such, if we add an explicit check for every overflow that no truncation is happening or no alteration is happening, we will be able to catch all overflows at all times whether they're useful or not because some overflows may be done on purpose.

But what I'm really saying is that the compiler like uint 88 of a u 256 is implying a truncation and we as the human we are uh blind to it but the code is actually there. We're just not measuring it. So I feel like this is the most realistic example uh of an implied line. We're going to get more esoteric as we go down the list. But hopefully this again makes you think about how we could measure this better. So as I said message value obviously the line is only here it's just this uh uh line but what's really happening is account dotbalance minus equals etc in the node and we're also getting the balance etc.

And so th those lines exist we can all agree that they exist is that our methodology is blind to it. So this is actually solvable by simply writing better tools. uh same for a year C20. The reason why I put the year C20 is because I want to do a quick detour on star. The idea uh uh of star is the idea that a call uh could be done arbitrarily to any address. And this is something that auditors will hate you for because fundamentally a star means that I have to audit for anything and even formal tools just over approximate when whenever that happens. But uh this shows you the danger of star because a star

meaning an arbitrary call to an arbitrary address implies that you have to cover the universe for the line. It literally means the amount of lines that I would have to add to my coverage is infinite. So it's the definition of something that can be addressed. We call it constraining behavior and it's simply the idea that if I'm doing an audit, I want you to provide me with the list of integrations and then I want you to hardcode them. Ideally, just hardcode them, make the system immutable or provide me with a system that will ensure that those are the only integration you will interact with.

Because as I'm arguing, if you want to be fully certain that of the security of your system or at least you want to get towards that, now you have to add all of the lines from that contract into your coverage. Like that's the only way for you to measure the actual effectiveness of test against that. And anytime you mock an integration, you're basically uh asserting that that uh system can be simplified down to that. And uh most of the time that requires more work. So constraining is a key aspect and is a very common reason why we get bugs like like the an example will be the pre-ompile bypass. There was a signature scheme that didn't account for the fact

that a pre-ompile will effectively return true and that's an example of having a star where now as the auditor I have to think of every possible combination every possible pre-ompile and that can be just too much. So you're much better off hard- coding those options so that way your coverage can reach that hypothetical 100% and you can own that code as well. So now we're going to enter the esoteric zone. So this is science fiction. Uh all the terminologies is made up by me. So if there's uh any reference in academia, please share because I I'm eager to learn. But fundamentally the next level is what I will call implied state which is something that happens for example in re-entrancey. Re-entry implies that a smart contract can be in a different

state. There is no storage value. There is nothing that describes that state. However, that state of execution is different behaviorally and semantically from the normal state of execution. The state of execution that we tested for. And so my argument is those type of bugs can be described by implicitly adding a storage value to the contract and then considering the coverage of that contract when that storage value is altered to be a different one. So an example is uh fairly straightforward is obviously we will fix this by adding the norra modifier. But you can see how simply adding a boolean flag and then asserting that anytime the withdraw

function is uh called with a different boolean flag. This is a different function and this is a different coverage will ensure that at least mentally we are considering those type of combinations. Obviously there's a million ways to avoid this. we will go back to the idea of constraining behavior. We would rather not have to think about this and so we would abide by check effects interactions. However, sometimes your system can't do that. And for that reason, this is the type of logic you want to apply. You want to think about these implied lines that effectively uh would better describe the uh the inaction state of the system. And so if we could just magically uh go into byte code and instrument it and put

various boolean flags, this is how we would go about analyzing contracts midexecution with these new types of states. The next level is meta properties and this is effectively properties that we use for uh invariant testing whether it's formal or uh concrete. But the key idea is that we take the system under test. We poke at its state which could be uh the actual uh state or the aggregation of various states. And so what tends to happen with meta properties which is particularly interesting uh based on the discussion we just had is that the meta properties is basically cutting reality or cutting the equations in a different way and is giving you the sensitivity that we're missing when we only think about

coverage. And that's because a good example would be if you have two variables. Say you have a sum of two variables where one variable and the other variable can be of the same magnitude or one variable and the other variable can be of massively different magnitudes. If you have a meta property that describes that state now uh how uh you you can now see when your system goes through a state in which one variable is leading or a state in which one variable is not leading. And so a class a classic example here will be perhaps describing the relation between uh shares and assets in a vault or other form of mathematical operations uh such as uh for example the relation between a

fee and the principle and so you can see how uh a meta property will make it so that not only you have the a line I don't know if I have code for this but I basically spoke about this yesterday I did a live um event where I was uh fuzzing as Mark an oracle and I show that because from coverage alone uh fuzzing the oracle would uh lead us to finding zero bugs and zero issues and then by adding stateful fuzzing and then looking at uh manipulating the price. the that property was basically cutting reality was creating this intersection between the formula of coverage and the uh the formula of the price and in that way we were able to see a 50 millionx

price manipulation and so sometimes it's literally a matter of distinguishing between the magnitude of two variables and it can make all the difference in the world um and so this is the code you can check again the the talk I did yesterday it's on uh DSS YouTube channel and so the last one that I have for is world splits something that I don't fully understand but fundamentally um because zed is a group uh it's not a group zed is a ring and uh we basically deal with integers then we have to account for the discrepancy between our perceived the perceived behavior of math which will be mostly linear mostly well behaved and what you know I drawn here in uh in two seconds to basically show

what we would call a step-wise alteration And so these type of uh alterations are how we find most bugs. This is my my favorite bug of this year. I it's in my um audit report for liquidity v2. But basically that uh truncation right there led me to investigate the ratio between batch debt and batch shares and it led me to find a way to borrow for free on liquidity. And so fundamentally all I did though if you think about it beside obviously a lot of effort was really finding that step. And so in conclusion the takeaways are we can improve fuzzers we should use these ideas to better uh show our work. And uh I just want to

give a massive shout out to my team Nikonor and not for uh helping me build the stuff that I showed you. Thank you for your attention. >> [applause]