Detecting DoS vulnerabilities caused by gas limits with fuzzing by Sebastian Banescu

so hello everyone my name is Sebastian and today I'm going to be presenting this topic about detecting denial of service vulnerabilities caused by gas limits using fuzzing and other techniques but we're not just going to stop at detecting we're also going to be looking into how to generate exploits and fixes for these vulnerabilities this is joint work together with Professor Vijay Ganesh from the University of Waterloo as well as the group of his PhD students working on smart contract security so probably most of you already know this but I created the presentation for general public so not assuming that everyone everyone knows about smart contracts they're just programs executed on a virtual machine if you're in virtual machine and calling a function in a smart contract changes the state of the EVM and these changes the state changes often involve transfers of funds and so on programs of course might contain bugs any type of program so therefore smart contracts also contain probably bugs and exploiting these bugs and smart contract can lead to stolen or frozen funds as we've seen many times in the past on the other hand there is the notion of gas the EVM has this gas mechanism which charges the function callers or the transaction senders and execution fee which is consumed computed using gas price times gas consumed and there is a block gas limit for each block that is mined and the gas consumed by any function call in transaction cannot surpass this block gas limit if it does the transaction is reverted and this is meant to prevent resource abuse and denial of service attacks on the etherium network however it can cause denial of service attack that smart contract level by by not allowing a user to call the function and fully execute it so this could lead to to frozen funds and frozen funds are basically lost funds here's a tour example and here's this is something which you could naively implement if you're not familiar with salinity or gas and gas issues in aetherium basically you want to reward all the users of a certain Bank let's say and you want to push out interest payments every month or every year and you do that you basically is a iterate over all users and you do some computation based on how much balance or how much deposit they have and now much time they have kept their deposit there and you basically send them this interest now you notice that this users dot length is controlled or influenced by users joining this Bank right so the more users you have the more iterations this for loop is going to have and if it gets out of like if it at some point passes the block gas limit it's going to cause the transaction to revert and if there's no other way to push out interests it basically is going to lead to a lot of unhappy users this Bank and other problems so that's the basic idea more famous exam are you still with me oh you broke up okay and she seemed to be frozen so I can still see your screen okay Oh word where did you lose me yes exactly now I can see the screen again perfect okay so yeah that was the start and you said a more famous example okay so more famous example is this project called governmental and it's from 2016 and they suffered for some time due to this kind of block cast limit so there was a denial of service for the payout of the jackpot which was 1100s because the payout mechanism was using too much gas and a part of this as part of this a payout mechanism the the contract was clearing internal storage using these instructions and this was compiling to something that iterates over storage locations and delete them deletes them one by one and because the list was too long it reached that the block as limit at that point in time and that led to frozen funds so this is this is the source where I took this information from this reddit post and of course like back in 2016 the block s limit was quite lower as than it is today so I was under five million and today it's 10 million as we see it it keeps evolving it keeps growing with some exceptions from most of the time the block estimate is increased at a certain hard fork and the motivation for this work that we're doing and trying to detect and exploit this automatically is because there's simply too many accounts and also smart contracts on the etherium network to try to do this manually and find this out so we were basically during our audits even today we're seeing a lot of gas usage issues in the cotton the smart contracts and using state-of-the-art tools like slither or my frill you can detect these issues it's pretty easy to detect basically look for loops and some computations or function calls in those loops and there's many tools really available that that find this issue however what do you do once you detect them right one thing you can do is try to remove the loops and redesign your code such that you completely avoid loops and you just try to accumulate values as other functions are called however if that's not an option you can just maybe do a gas analysis or determine when exactly the the error the out of gas that occurs and you can add something like a required statement or an assert statement to basically prevent the revert from happening and prevent the waste of gas and this is a currently a manual potentially lengthy and tedious process so the solution which we propose and in this work is to automatically generate these kind of denial-of-service experts that lead to out of gas that's more contract level there's several challenges the first one is like how do you determine the exact gas usage during an execution second one is how do you search for these to the large search space of possible inputs to the functions there could be functions they have several parameters or even like there could be multiple functions that need to be called in order to reach a state where this kind of gos or out of gas error is reached so the first challenge is actually easy to solve you to web three and solidity features we're in our proach we use the gas left function from solidity and we basically simulate everything on top of the curve the ghannouchi Network having the Ganassi tool and the second challenge is more I'm going to talk more about that one so fuzzing a large number of inputs is more tricky there's several possible fuzzing heuristics for instance you can brute-force every possible input and that's very slow you can do a divide and conquer approach which is faster but it's not always applicable if you don't have certain rules like keep your intervals and so on that you can easily divide in and into partitions or basically for this for our approach we're using reinforcement learning which is also fast and is more generally applicable and we'll see in a second why there is also possible other possible heuristics not saying this is the best one but this is the one we we chose for our project so the reinforcement learning approach it looks like this we basically model the problem as a Markov decision process where we say that the set of states s is all of the states so the EVM basically we're just a state as a state of the evm the possible set of actions is calling smart contract function with some randomly chosen input or also like more carefully chosen inputs increasing those inputs decreasing them and so on so these are like the actions that the agents the reinforcement learning agent can take the probability of transitioning from one state to another when basically when executing a given action is is always 100% because the EVM is deterministic and the the interesting part is the reward function basically the the reward that the agent gets when he transition to a state s is one - the division between the gas left and the block as limit and this is because we're rewarding action that are going to consume more gas you know so if the transaction that led to the state has used more gas we're going to give a higher reward because we want to reach out of gas error so this is pretty intuitive here's a simple example of a pure function that just receives value as input an integer value as an input and it iterates over all integer values from zero to that number sums them up and return the sum the goal of the reinforcement learning agent would be here to find the right value for n which leads to this kind of out of gas error and we're going to see later how this code is fix another example is maybe a slightly different functions still pure function that has two parameters and/or like you can even think about more parameters but basically you you do some computations with these parameters and they don't always influence the result or like the gas usage in the same way so here you can see that we're dividing n by M so the goal of the reinforcement learning agent is to find a large value for N and a small value for M but M should not be 0 because otherwise it leads to a division by zero and what are V be sort of the right values for this or like what was for maybe something else we're going to see later what's the right way to fix this here's another example where there's a small contract that is vulnerable it has several entries in integer entries in them and it it has several functions and the first function just adds an entry in the list I saw a typo there the second function gets that the entry at a certain location and the third function sums up the list of entries quickly returning the some so here you can see that the goal is to find a trace of function calls like this basically adding little entries up to N and summing them up and the question is what's the value of n such that when you call some of some entries it leads to block an out of gas error so the challenge is how to determine like first you need to determine which functions effect basically be the loop bounds because as we saw before there were there was also a function called get entry and the reinforcement agent should not be calling that it would be just wasting from time calling that one because it's not going to affect their loop bounds inside of some entries and the solution to detect which functions affect the loop bounds that we are taking is to do reverse taint analysis and then forward taint analysis so for those of you who are not familiar taint analysis is a form of information flow analysis where you first paint or tag a memory location for example a variable X then you trace the flow of that tainted value through the execution of your smart contract functions and you determine which instructions or which other memory values are affected by that painted part the information flow may be explicit where you have a direct assignment memory transfer and it could also be implicit where different values in memory depend indirectly on your tainted value for instance if you have a branch condition like this if X greater than 0 and inside of the if and else branches you have other values like other variables like a and B those variables will be implicitly pain goodbye ex the reverse paint analysis on that function we slightly modified this function some entries to also include an impatient tail implicit paint sample / or can you still hear me you were breaking up but now you're back okay so here we modified the some entries function a bit in order to show that can you still hear okay be sure to show that there is a possibility of an implicit tape we start from the loop at the close to the bottom and we taint the bound variable and we go up we go in reverse and we see that first the end the variable n is tainted by bound because there's an explicit assignment and also the length of the entries list is also painted explicitly and we also have an implicit painting of those variables but since they're already explicitly painted and basically they're tainted we also have a paint of their constant zero so that instruction is also tainted where a bound is assigned zero value and based on this analysis we can say that okay the function the input of the function some entries is tainted and also the state variable entries is tainted that is the length of this state variables state variable is tainted so once we once we determine this we can do a forward paint analysis where we just paint the entries dot length and we start executing each function to see which instruction with which instructions in which function may affect the entries length and we see that only the add entry function affects the length of the entries list the get entries functions does not therefore the reinforcement a learning agent can just try to call this function before it tries to see if it if it ran out of gas using that some entries function which is not shown here due to lack of space so the question here towards the end is like okay we took this approach we did all this stuff we ran the reinforcement learning agent so what do we do once we know where the out of gas error occurs I already hinted towards the answer we basically fix the the code and fixing could look something like this if removing the loop is not an option you could have a require statement close to the beginning of the code which basically signals that the parameter that you or the parameters that you provided will lead to an out of gas error the second example which I showed you could also go for fixing actually after you've done all the computation you can add this require statement which is easier than necessary then then checking values for different inputs and the third example is also interesting because we're not placing the require statement inside of the function which has the loop like not inside of some entries but we're placing it inside of the function that affects the length of the the loop so inside of the add entry function and of course these values are just like preliminary preliminary values like they're not there just mocks you can also not just hard code the values in there but you can also let it be settable by the contract owner such that if there's a fork or the Gregg action that is increased they can adapt this or if the OP code cost of the cost of the opcodes changes these values can be changed as well in conclusion just want to say that probably no loops cause out of gassers and smart contracts and these can lead to frozen and hence lost funds detecting such problems is quite easy with state-of-the-art tools how determining exactly when they would occur with which input is harder and we're taking the approach of fuzzing with reinforcement learning and taint analysis to generate the inputs needed for an out of gas or faster and in a more general way and yeah we're using taint analysis to guide fuzzing from my site thank you very much any questions thank you so much yeah so now first to the people in the room if you have any questions for the bastion use the raise your hand feature so that I can see that you would like to ask something and to the people in the livestream we know you're lagging behind so we will wait for you for one minute and you can put your question in the guitar chat yes Jocelyn thanks John nice talk what tool are you using for for this you need for reinforcement learning or which part so so one approach like out we're building a custom tool for this one okay okay so it's everything built into us well it's going to be published but it's basically the joint effort between the University and Quon stamp and we're going to release the the code once the paper is accepted