Great. Yeah, hello, everyone. My name is Sebastian.
This work is about identifying and fixing out-of-gas errors in smart contracts with
what we call smart fuzzing. And it's joint work together with the group of Professor Vijay Ganesh
from the University of Waterloo, with three great PhD and Master's students.
So just starting with a quick intro, but you all probably know this. On Ethereum,
you have smart contracts that are executed on the EVM. And calling a function on one of those
smart contracts changes the state. And these state changes often involve transfers of funds.
However, these smart contracts are just programs which may contain bugs. And exploiting those
can lead to stolen or frozen funds. So there's another part of the intro here is that
Ethereum virtual machine has this gas mechanism, which charges callers when they want to execute
some smart contract function. And the execution fee is computed by the product of the gas price
and the amount of gas that that code consumes. Now, in order to prevent denial-of-service attacks,
there's a block gas limit. And if the gas consumed by a certain smart contract function
exceeds this block gas limit, then the transaction is reverted. However, the gas is wasted.
So the caller needs to pay that price. And like I mentioned, it's meant to prevent denial-of-service
attacks on the Ethereum network because people don't want to... if a malicious attacker submits a
very resource-intensive piece of code, it could lead to a halt of the network. However, this
defense mechanism, which is the block gas limit, may also cause a denial-of-service
on smart contract functions. And this will lead to frozen funds, where by frozen funds,
you can also see them as lost funds. Here's a toy example. For instance, you have a
naive implementation of a bank in a smart contract. And in that implementation, you have this function,
which is called push interest payments, basically pushing the interest that the customers of that
bank received. And it iterates with this for loop over all users. It does some heavy computation,
which is not shown here, in order to compute the interest for each user. And then it sends
each user the amount of interest they are due. Now, you notice here that this loop bound is
controlled by users, because the more users are registered, the longer this loop is going to be.
And if it gets long enough, then the block gas limit will be reached when executing this function,
which will lead to a denial-of-service and no one will get their interest anymore.
This, a similar sort of situation where the block gas limit was hit happened a few years ago
with a governmental smart contract where they were set to pay out a jackpot of 1100 ETH.
However, it got stuck because the function that was meant to pay out was using too much gas.
And this was due to the fact that the contract wanted to clear its internal storage. And doing
that using these two instructions, which compiled to code which iterates over all locations and
deletes them one by one. So basically, due to the fact that there were too many participants
in this smart contract, it was hitting the block gas limit and the funds were frozen
for a certain period of time. However, with a new hard fork, the block gas limit was increased.
And the winning user was able to get their jackpot out,
thankfully. But it took some time, they couldn't do it immediately. And if there
were no hard fork, or if there were more participants, maybe it was still be stuck.
Here's just an indication of how the block gas limit has evolved over time.
So you can see at the beginning, it was somewhere around 3 million.
It was increased up almost to 5 million in 2016. However, it also was decreased at some point
for a shorter period of time. And then afterwards, it keeps increasing. At today, it's around 10
million. And it may also increase further, but who knows. So this is a dynamic parameter.
It's not exactly changing every day. But people should keep in mind that this is not something
that you can rely on forever. And what we see during our smart contract security audits is that
many projects still contain these gas usage issues. There's, of course, state of the art
tools like Slither and Mithril, which can detect these kinds of concerns very easily
using static analysis, for instance. And they are freely available and well known in the community.
However, the question is always, what do you do after you detect them? You tell the
developer, yeah, you need to fix it. And then he is like, how can I fix it? Of course,
an ideal way to fix this would be to completely remove the loops. But sometimes that's not an
option. And when it's not an option, what you can do is to do some kind of gas analysis
to determine how much gas the instructions use. And if possible, add a require statement
at the beginning of the function somewhere to notify the user that this is going to fail
with an out-of-gas error and not make them waste too many funds on the actual gas
until it hits the out-of-gas error. So this currently is sometimes manual work to detect
this bound or what parameters could lead to an out-of-gas error. And it's pretty
tedious depending on it's very specific to the smart contract that you're using.
So in this talk, we basically want to automate this process. We want to generate
this kind of denial-of-service exploit and then also fix the issue.
And there are several challenges. The first one, which is probably the easiest of them all,
is how do you determine the exact gas usage during execution? Then depending on which
functions you may have, they may have like a large search space. So if you have several
function input parameters, which are uints or strings, they can have a lot of possible
values. So how do you search through all of those possible values and determine the ones
which could lead to an out-of-gas issue? And the third one is also the fact that you're not just
looking... you cannot just isolate this search for one particular function because several
functions might be dependent on each other in the sense of the state variables that they
change. So we're going to see some examples of those. For determining the gas usage,
there's multiple approaches. One can be done pre-execution using the estimate gas function
from Web3, or you can do it post-execution using the gasLeft function from Solidity.
And we use the gasLeft function in our implementation.
The second challenge was about large number of inputs, and there's different fuzzing heuristics
you can use in order to do that. The brute force one is just randomly picking possible
input values, which is slow. Another one, which is faster but is not always applicable if you
don't have a strict ordering between your inputs, is to use divide and conquer.
And the one which we'll be using in our approach is reinforcement learning, which is
also fast and more generally applicable than divide and conquer. There's also other possible
heuristics, so we're not saying that these are the only three. Of course, many people will come
up with other heuristics, which are maybe better, maybe not. But what we wanted to look into was
how to use reinforcement learning for this kind of purpose. And in our approach, we model the
problem as a Markov decision process, where the S is all states of the EVM. A, the set of
actions is basically smart contract functions with possibly random inputs or maybe more
carefully designed inputs. This is basically the secret sauce or the most important part of
the modeling part. How do you generate your action set? Which actions your reinforcement
learning agent can perform? The probability of transitioning from one state in the set S to
another, we set to one because the EVM is fully deterministic, so there's no question whether
executing a certain function with certain inputs in a state will lead to different states. It's
deterministic. And then the reward function for a certain state is basically one minus
the amount of gas you have left over the block gas limit. And again, with the reward function,
we're playing a bit around with it at the moment. This is just to give you an indication.
We actually are also penalizing if we want to get to the exact bound where this
out of gas error happens. So we're looking at ways in which we can penalize if not only that
there's no gas left, but it actually would use much more gas than available. So for that,
we're setting the block gas limit pretty high. One example of a super simple function where
such an out of gas error could occur is shown here with this sum function. It's a pure function
which just iterates over integer numbers up to a given value n and computes their sum.
So the goal of the reinforcement learning agent here would be to
find a large value for this input n such that this function runs out of gas.
The second example is a bit different. It has two input parameters and it computes a division of n
by m in order to obtain the bound and then iterates and computes the sum. And now you can
see that the goal of the reinforcement learning agent has slightly changed into finding a large
value for n and a small value for n. But m should not be equal to zero, otherwise we have a division
by zero. And the third example, which is showing the inter-function dependency, is actually
a contract containing several functions and a list of entries as a state variable.
And you'll notice that the function which contains the loop is called sumEntries.
It iterates over all these entries and computes their sum. However, this function does not have
an input parameter as the ones we saw on the previous slides. This basically means that
another function in the smart contract is probably going to affect the length of this list.
And the one that it does affect is this addEntry function.
And other functions like getEntry do not affect this length. So the goal here is the goal for the
reinforcement learning agent, which doesn't understand the semantics of the names here.
So reinforcement learning agent doesn't understand what addEntry means or getEntry or sumEntries.
It just sees functions and tries to execute them. The goal here is basically to generate a trace
of function calls of this form, and then to determine the value of n,
such that when it calls the sumEntries function afterwards, it's going to run out of gas.
And the question here is, how do you determine which functions... let's say you have a smart
contract with, I don't know, dozens of functions, right? There are such smart contracts. Which one
should the reinforcement learning agent call in order to obtain a proper trace where an out-of-gas
issue occurs, right? This may be very difficult. It's a very large search space because you also
have possible different function calls with many parameters. So it's a large search.
The solution that we propose for this is to first do reverse taint analysis and then
forward taint analysis on the smart contract in order to determine which functions are relevant
to call for the reinforcement learning agent. If you're unfamiliar with taint analysis,
it's a form of information flow analysis where you taint or tag a memory location,
which could be a variable x, and then you trace the flow of the execution of the smart contract
and the tainted memory location. And this way you determine which other locations or instructions
are affected by this tainted location. This taint could be either explicit,
where you have a direct assignment between the tainted memory location and another,
or it could be implicit, where you have a condition that depends on this tainted memory
location. So here's the example, slightly modified function, some entries from our
third example on the previous slides. We have here a list of entries, we have this function,
some entries where we also introduced a parameter n just for the sake of illustrating implicit
information flow as well. And basically, it compares whether this input parameter is zero,
or if it's greater than the length. And based on that comparison, it assigns the bound to a
different value, right? And then it loops over that bound. Now here, we start our reverse taint
analysis from the last executed instruction that meaning here, it's basically the loop bound,
and we go backward from there. And we basically taint all the other memory locations that are
affected by the bound. So n is affected by the bound explicitly because it's assigned here.
And it's also affecting the entries length. However, it's also implicitly affecting these
two values here. It's also therefore implicitly or explicitly affecting the state variable
entries, right? And now that we have this information with the reverse taint analysis,
we do our forward taint analysis where we know that our entries state variable is tainted.
And we start looking into the functions. And we see that the addEntry function
is also tainted because it affects the entries length. The other function, which is called
getEntries, does not affect the entries.length. Therefore, it's not tainted. And we can do
that with more other functions that are in the smart contract. This way, we have a subset of
functions that our reinforcement learning agent can call. Now, the question is, what do you do
once you know where and when the out-of-gas error occurs? Basically, fix it. And one way to fix it
would be to add these kind of require statements. And we
revisit the previous examples that we saw on the previous slides.
The first one was this simple sum function. And here, you can basically add a require statement
at the beginning with this bound that you determined before. This, of course, can be
something that you can set depending on how the block gas limit evolves. So, it doesn't
need to be a hard-coded constant here. It could also be a state variable of the smart contract.
This way, you prevent the caller from wasting gas if the value of n is too large.
Similarly, you can do a bound on the second example that we had.
And you can place the require here. Later, you can place it earlier.
And you can also do it where you have multiple functions. And notice here that we're not
blocking the sum entries function, which actually contains the loop, and it would actually be the
function that reaches the block gas limit. You place the fix inside of the functions which affect
the entries.length and would basically prevent the length from becoming large enough
to cause an out-of-gas error.
So, that was pretty much it. In conclusion, we all know loops can cause
out-of-gas errors, and these errors can lead to frozen or lost funds.
And detecting such errors is easy, but determining the exact input that is going to
cause it is harder. And here, I'm not just saying any input, but basically being able to fix.
So, we're talking about the boundary condition between where it doesn't run out of gas and then
it runs out of gas. So, in order to determine this input and to generate the fix, we use fuzzing
with reinforcement learning as a heuristic, which is fast and generally applicable.
And we also employ taint analysis in order to guide the fuzzing, so to guide the reinforcement
learning agent as to which functions should be called and which not.
That's my talk. Thanks a lot for your attention. Any questions? Yeah, me neither.
Yep. Thank you.
How's it going? Can you hear me? Hey, how's it going, everybody?
I'm just going to get my screen shared here. Yeah, I can also just hang out and...