[00:01.050 --> 00:04.870]  Great. Yeah, hello, everyone. My name is Sebastian.
[00:05.770 --> 00:13.450]  This work is about identifying and fixing out-of-gas errors in smart contracts with
[00:13.450 --> 00:21.890]  what we call smart fuzzing. And it's joint work together with the group of Professor Vijay Ganesh
[00:21.890 --> 00:28.410]  from the University of Waterloo, with three great PhD and Master's students.
[00:29.370 --> 00:36.210]  So just starting with a quick intro, but you all probably know this. On Ethereum,
[00:36.210 --> 00:42.830]  you have smart contracts that are executed on the EVM. And calling a function on one of those
[00:42.830 --> 00:49.590]  smart contracts changes the state. And these state changes often involve transfers of funds.
[00:50.130 --> 00:57.170]  However, these smart contracts are just programs which may contain bugs. And exploiting those
[00:57.170 --> 01:07.510]  can lead to stolen or frozen funds. So there's another part of the intro here is that
[01:08.530 --> 01:15.750]  Ethereum virtual machine has this gas mechanism, which charges callers when they want to execute
[01:15.750 --> 01:24.230]  some smart contract function. And the execution fee is computed by the product of the gas price
[01:24.230 --> 01:30.970]  and the amount of gas that that code consumes. Now, in order to prevent denial-of-service attacks,
[01:30.970 --> 01:37.830]  there's a block gas limit. And if the gas consumed by a certain smart contract function
[01:37.830 --> 01:46.520]  exceeds this block gas limit, then the transaction is reverted. However, the gas is wasted.
[01:47.070 --> 01:54.050]  So the caller needs to pay that price. And like I mentioned, it's meant to prevent denial-of-service
[01:54.050 --> 02:04.530]  attacks on the Ethereum network because people don't want to... if a malicious attacker submits a
[02:07.770 --> 02:16.150]  very resource-intensive piece of code, it could lead to a halt of the network. However, this
[02:16.150 --> 02:19.970]  defense mechanism, which is the block gas limit, may also cause a denial-of-service
[02:20.820 --> 02:29.110]  on smart contract functions. And this will lead to frozen funds, where by frozen funds,
[02:29.110 --> 02:38.630]  you can also see them as lost funds. Here's a toy example. For instance, you have a
[02:38.630 --> 02:45.930]  naive implementation of a bank in a smart contract. And in that implementation, you have this function,
[02:45.930 --> 02:53.690]  which is called push interest payments, basically pushing the interest that the customers of that
[02:53.690 --> 03:03.630]  bank received. And it iterates with this for loop over all users. It does some heavy computation,
[03:03.630 --> 03:09.610]  which is not shown here, in order to compute the interest for each user. And then it sends
[03:10.570 --> 03:19.070]  each user the amount of interest they are due. Now, you notice here that this loop bound is
[03:19.070 --> 03:26.390]  controlled by users, because the more users are registered, the longer this loop is going to be.
[03:26.590 --> 03:33.750]  And if it gets long enough, then the block gas limit will be reached when executing this function,
[03:33.750 --> 03:38.130]  which will lead to a denial-of-service and no one will get their interest anymore.
[03:39.710 --> 03:47.110]  This, a similar sort of situation where the block gas limit was hit happened a few years ago
[03:47.850 --> 03:57.270]  with a governmental smart contract where they were set to pay out a jackpot of 1100 ETH.
[03:57.530 --> 04:03.910]  However, it got stuck because the function that was meant to pay out was using too much gas.
[04:03.910 --> 04:14.270]  And this was due to the fact that the contract wanted to clear its internal storage. And doing
[04:14.270 --> 04:24.430]  that using these two instructions, which compiled to code which iterates over all locations and
[04:24.430 --> 04:31.290]  deletes them one by one. So basically, due to the fact that there were too many participants
[04:31.290 --> 04:36.790]  in this smart contract, it was hitting the block gas limit and the funds were frozen
[04:37.290 --> 04:45.930]  for a certain period of time. However, with a new hard fork, the block gas limit was increased.
[04:46.010 --> 04:53.190]  And the winning user was able to get their jackpot out,
[04:53.830 --> 05:00.550]  thankfully. But it took some time, they couldn't do it immediately. And if there
[05:00.550 --> 05:05.710]  were no hard fork, or if there were more participants, maybe it was still be stuck.
[05:06.510 --> 05:14.290]  Here's just an indication of how the block gas limit has evolved over time.
[05:14.290 --> 05:18.070]  So you can see at the beginning, it was somewhere around 3 million.
[05:18.070 --> 05:29.750]  It was increased up almost to 5 million in 2016. However, it also was decreased at some point
[05:29.750 --> 05:39.330]  for a shorter period of time. And then afterwards, it keeps increasing. At today, it's around 10
[05:39.330 --> 05:47.410]  million. And it may also increase further, but who knows. So this is a dynamic parameter.
[05:47.410 --> 05:55.130]  It's not exactly changing every day. But people should keep in mind that this is not something
[05:55.770 --> 06:03.550]  that you can rely on forever. And what we see during our smart contract security audits is that
[06:03.550 --> 06:10.590]  many projects still contain these gas usage issues. There's, of course, state of the art
[06:10.590 --> 06:17.050]  tools like Slither and Mithril, which can detect these kinds of concerns very easily
[06:17.930 --> 06:26.810]  using static analysis, for instance. And they are freely available and well known in the community.
[06:26.990 --> 06:31.150]  However, the question is always, what do you do after you detect them? You tell the
[06:33.050 --> 06:38.770]  developer, yeah, you need to fix it. And then he is like, how can I fix it? Of course,
[06:38.770 --> 06:46.130]  an ideal way to fix this would be to completely remove the loops. But sometimes that's not an
[06:46.130 --> 06:50.670]  option. And when it's not an option, what you can do is to do some kind of gas analysis
[06:51.270 --> 07:01.410]  to determine how much gas the instructions use. And if possible, add a require statement
[07:02.070 --> 07:09.810]  at the beginning of the function somewhere to notify the user that this is going to fail
[07:09.810 --> 07:21.010]  with an out-of-gas error and not make them waste too many funds on the actual gas
[07:21.010 --> 07:29.890]  until it hits the out-of-gas error. So this currently is sometimes manual work to detect
[07:29.890 --> 07:38.230]  this bound or what parameters could lead to an out-of-gas error. And it's pretty
[07:38.230 --> 07:44.670]  tedious depending on it's very specific to the smart contract that you're using.
[07:45.690 --> 07:52.030]  So in this talk, we basically want to automate this process. We want to generate
[07:52.030 --> 07:58.110]  this kind of denial-of-service exploit and then also fix the issue.
[07:59.730 --> 08:06.130]  And there are several challenges. The first one, which is probably the easiest of them all,
[08:06.130 --> 08:13.270]  is how do you determine the exact gas usage during execution? Then depending on which
[08:13.270 --> 08:19.630]  functions you may have, they may have like a large search space. So if you have several
[08:19.630 --> 08:27.990]  function input parameters, which are uints or strings, they can have a lot of possible
[08:28.630 --> 08:33.330]  values. So how do you search through all of those possible values and determine the ones
[08:33.330 --> 08:43.430]  which could lead to an out-of-gas issue? And the third one is also the fact that you're not just
[08:43.430 --> 08:50.010]  looking... you cannot just isolate this search for one particular function because several
[08:50.010 --> 08:58.070]  functions might be dependent on each other in the sense of the state variables that they
[08:58.070 --> 09:04.690]  change. So we're going to see some examples of those. For determining the gas usage,
[09:04.690 --> 09:12.130]  there's multiple approaches. One can be done pre-execution using the estimate gas function
[09:12.130 --> 09:19.330]  from Web3, or you can do it post-execution using the gasLeft function from Solidity.
[09:19.850 --> 09:23.370]  And we use the gasLeft function in our implementation.
[09:24.690 --> 09:30.470]  The second challenge was about large number of inputs, and there's different fuzzing heuristics
[09:30.470 --> 09:37.590]  you can use in order to do that. The brute force one is just randomly picking possible
[09:38.250 --> 09:43.330]  input values, which is slow. Another one, which is faster but is not always applicable if you
[09:43.330 --> 09:48.330]  don't have a strict ordering between your inputs, is to use divide and conquer.
[09:49.690 --> 09:55.370]  And the one which we'll be using in our approach is reinforcement learning, which is
[09:56.030 --> 10:05.110]  also fast and more generally applicable than divide and conquer. There's also other possible
[10:05.110 --> 10:10.430]  heuristics, so we're not saying that these are the only three. Of course, many people will come
[10:10.430 --> 10:17.810]  up with other heuristics, which are maybe better, maybe not. But what we wanted to look into was
[10:17.810 --> 10:23.890]  how to use reinforcement learning for this kind of purpose. And in our approach, we model the
[10:23.890 --> 10:34.690]  problem as a Markov decision process, where the S is all states of the EVM. A, the set of
[10:34.690 --> 10:45.170]  actions is basically smart contract functions with possibly random inputs or maybe more
[10:45.730 --> 10:54.610]  carefully designed inputs. This is basically the secret sauce or the most important part of
[10:55.630 --> 11:00.990]  the modeling part. How do you generate your action set? Which actions your reinforcement
[11:00.990 --> 11:07.950]  learning agent can perform? The probability of transitioning from one state in the set S to
[11:07.950 --> 11:14.610]  another, we set to one because the EVM is fully deterministic, so there's no question whether
[11:15.390 --> 11:23.150]  executing a certain function with certain inputs in a state will lead to different states. It's
[11:23.150 --> 11:30.950]  deterministic. And then the reward function for a certain state is basically one minus
[11:31.550 --> 11:39.750]  the amount of gas you have left over the block gas limit. And again, with the reward function,
[11:39.750 --> 11:44.190]  we're playing a bit around with it at the moment. This is just to give you an indication.
[11:45.140 --> 11:54.710]  We actually are also penalizing if we want to get to the exact bound where this
[11:55.300 --> 12:04.350]  out of gas error happens. So we're looking at ways in which we can penalize if not only that
[12:04.350 --> 12:11.830]  there's no gas left, but it actually would use much more gas than available. So for that,
[12:11.830 --> 12:20.650]  we're setting the block gas limit pretty high. One example of a super simple function where
[12:20.650 --> 12:27.190]  such an out of gas error could occur is shown here with this sum function. It's a pure function
[12:27.190 --> 12:36.830]  which just iterates over integer numbers up to a given value n and computes their sum.
[12:36.830 --> 12:41.310]  So the goal of the reinforcement learning agent here would be to
[12:42.110 --> 12:48.630]  find a large value for this input n such that this function runs out of gas.
[12:49.290 --> 12:58.070]  The second example is a bit different. It has two input parameters and it computes a division of n
[12:58.070 --> 13:05.830]  by m in order to obtain the bound and then iterates and computes the sum. And now you can
[13:05.830 --> 13:11.610]  see that the goal of the reinforcement learning agent has slightly changed into finding a large
[13:11.610 --> 13:19.650]  value for n and a small value for n. But m should not be equal to zero, otherwise we have a division
[13:19.650 --> 13:27.150]  by zero. And the third example, which is showing the inter-function dependency, is actually
[13:28.770 --> 13:34.970]  a contract containing several functions and a list of entries as a state variable.
[13:34.970 --> 13:40.390]  And you'll notice that the function which contains the loop is called sumEntries.
[13:40.810 --> 13:48.490]  It iterates over all these entries and computes their sum. However, this function does not have
[13:48.490 --> 13:54.750]  an input parameter as the ones we saw on the previous slides. This basically means that
[13:55.770 --> 14:03.730]  another function in the smart contract is probably going to affect the length of this list.
[14:04.190 --> 14:11.030]  And the one that it does affect is this addEntry function.
[14:11.170 --> 14:18.210]  And other functions like getEntry do not affect this length. So the goal here is the goal for the
[14:18.210 --> 14:23.870]  reinforcement learning agent, which doesn't understand the semantics of the names here.
[14:23.870 --> 14:29.670]  So reinforcement learning agent doesn't understand what addEntry means or getEntry or sumEntries.
[14:29.670 --> 14:36.270]  It just sees functions and tries to execute them. The goal here is basically to generate a trace
[14:36.790 --> 14:45.370]  of function calls of this form, and then to determine the value of n,
[14:45.370 --> 14:52.370]  such that when it calls the sumEntries function afterwards, it's going to run out of gas.
[14:52.930 --> 14:59.890]  And the question here is, how do you determine which functions... let's say you have a smart
[14:59.890 --> 15:07.630]  contract with, I don't know, dozens of functions, right? There are such smart contracts. Which one
[15:07.630 --> 15:16.350]  should the reinforcement learning agent call in order to obtain a proper trace where an out-of-gas
[15:17.060 --> 15:23.210]  issue occurs, right? This may be very difficult. It's a very large search space because you also
[15:23.210 --> 15:30.650]  have possible different function calls with many parameters. So it's a large search.
[15:31.170 --> 15:37.030]  The solution that we propose for this is to first do reverse taint analysis and then
[15:37.030 --> 15:43.790]  forward taint analysis on the smart contract in order to determine which functions are relevant
[15:43.790 --> 15:50.050]  to call for the reinforcement learning agent. If you're unfamiliar with taint analysis,
[15:50.050 --> 15:56.950]  it's a form of information flow analysis where you taint or tag a memory location,
[15:56.950 --> 16:02.570]  which could be a variable x, and then you trace the flow of the execution of the smart contract
[16:04.330 --> 16:11.170]  and the tainted memory location. And this way you determine which other locations or instructions
[16:11.170 --> 16:19.970]  are affected by this tainted location. This taint could be either explicit,
[16:19.970 --> 16:26.130]  where you have a direct assignment between the tainted memory location and another,
[16:27.130 --> 16:32.530]  or it could be implicit, where you have a condition that depends on this tainted memory
[16:33.490 --> 16:43.870]  location. So here's the example, slightly modified function, some entries from our
[16:43.870 --> 16:49.930]  third example on the previous slides. We have here a list of entries, we have this function,
[16:49.930 --> 16:58.050]  some entries where we also introduced a parameter n just for the sake of illustrating implicit
[16:59.630 --> 17:08.190]  information flow as well. And basically, it compares whether this input parameter is zero,
[17:08.190 --> 17:15.110]  or if it's greater than the length. And based on that comparison, it assigns the bound to a
[17:15.110 --> 17:21.730]  different value, right? And then it loops over that bound. Now here, we start our reverse taint
[17:21.730 --> 17:34.330]  analysis from the last executed instruction that meaning here, it's basically the loop bound,
[17:34.330 --> 17:41.270]  and we go backward from there. And we basically taint all the other memory locations that are
[17:41.270 --> 17:47.650]  affected by the bound. So n is affected by the bound explicitly because it's assigned here.
[17:48.180 --> 17:55.790]  And it's also affecting the entries length. However, it's also implicitly affecting these
[17:55.790 --> 18:04.490]  two values here. It's also therefore implicitly or explicitly affecting the state variable
[18:05.010 --> 18:10.440]  entries, right? And now that we have this information with the reverse taint analysis,
[18:10.440 --> 18:17.960]  we do our forward taint analysis where we know that our entries state variable is tainted.
[18:18.400 --> 18:25.160]  And we start looking into the functions. And we see that the addEntry function
[18:25.900 --> 18:33.400]  is also tainted because it affects the entries length. The other function, which is called
[18:33.400 --> 18:40.420]  getEntries, does not affect the entries.length. Therefore, it's not tainted. And we can do
[18:40.420 --> 18:45.660]  that with more other functions that are in the smart contract. This way, we have a subset of
[18:45.660 --> 18:52.100]  functions that our reinforcement learning agent can call. Now, the question is, what do you do
[18:52.100 --> 19:01.340]  once you know where and when the out-of-gas error occurs? Basically, fix it. And one way to fix it
[19:01.340 --> 19:05.220]  would be to add these kind of require statements. And we
[19:06.100 --> 19:12.260]  revisit the previous examples that we saw on the previous slides.
[19:13.360 --> 19:19.520]  The first one was this simple sum function. And here, you can basically add a require statement
[19:19.520 --> 19:26.820]  at the beginning with this bound that you determined before. This, of course, can be
[19:26.820 --> 19:33.380]  something that you can set depending on how the block gas limit evolves. So, it doesn't
[19:33.380 --> 19:38.400]  need to be a hard-coded constant here. It could also be a state variable of the smart contract.
[19:40.080 --> 19:46.380]  This way, you prevent the caller from wasting gas if the value of n is too large.
[19:47.740 --> 19:53.040]  Similarly, you can do a bound on the second example that we had.
[19:54.000 --> 20:00.880]  And you can place the require here. Later, you can place it earlier.
[20:01.860 --> 20:09.020]  And you can also do it where you have multiple functions. And notice here that we're not
[20:09.020 --> 20:15.000]  blocking the sum entries function, which actually contains the loop, and it would actually be the
[20:15.000 --> 20:22.520]  function that reaches the block gas limit. You place the fix inside of the functions which affect
[20:23.040 --> 20:32.860]  the entries.length and would basically prevent the length from becoming large enough
[20:33.840 --> 20:36.500]  to cause an out-of-gas error.
[20:38.780 --> 20:44.960]  So, that was pretty much it. In conclusion, we all know loops can cause
[20:45.720 --> 20:51.560]  out-of-gas errors, and these errors can lead to frozen or lost funds.
[20:51.560 --> 20:58.660]  And detecting such errors is easy, but determining the exact input that is going to
[20:58.660 --> 21:07.320]  cause it is harder. And here, I'm not just saying any input, but basically being able to fix.
[21:07.320 --> 21:13.620]  So, we're talking about the boundary condition between where it doesn't run out of gas and then
[21:13.620 --> 21:25.660]  it runs out of gas. So, in order to determine this input and to generate the fix, we use fuzzing
[21:26.420 --> 21:32.620]  with reinforcement learning as a heuristic, which is fast and generally applicable.
[21:33.180 --> 21:40.780]  And we also employ taint analysis in order to guide the fuzzing, so to guide the reinforcement
[21:40.780 --> 21:45.600]  learning agent as to which functions should be called and which not.
[21:47.640 --> 23:02.950]  That's my talk. Thanks a lot for your attention. Any questions? Yeah, me neither.
[23:13.030 --> 23:16.230]  Yep. Thank you.
[23:24.450 --> 23:42.650]  How's it going? Can you hear me? Hey, how's it going, everybody?
[23:44.270 --> 23:55.690]  I'm just going to get my screen shared here. Yeah, I can also just hang out and...