WEBVTT 00:01.050 --> 00:02.310 Great. 00:02.430 --> 00:03.590 Yeah, hello, everyone. 00:03.590 --> 00:04.870 My name is Sebastian. 00:05.770 --> 00:16.030 This work is about identifying and fixing out-of-gas errors in smart contracts with what we call smart fuzzing. 00:16.030 --> 00:28.410 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. 00:29.370 --> 00:34.910 So just starting with a quick intro, but you all probably know this. 00:34.910 --> 00:40.350 On Ethereum, you have smart contracts that are executed on the EVM. 00:40.370 --> 00:45.030 And calling a function on one of those smart contracts changes the state. 00:45.030 --> 00:49.590 And these state changes often involve transfers of funds. 00:50.130 --> 00:55.930 However, these smart contracts are just programs which may contain bugs. 00:55.990 --> 01:01.170 And exploiting those can lead to stolen or frozen funds. 01:01.230 --> 01:18.150 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. 01:18.150 --> 01:28.070 And the execution fee is computed by the product of the gas price and the amount of gas that that code consumes. 01:28.430 --> 01:33.390 Now, in order to prevent denial-of-service attacks, there's a block gas limit. 01:33.990 --> 01:42.850 And if the gas consumed by a certain smart contract function exceeds this block gas limit, then the transaction is reverted. 01:43.430 --> 01:46.520 However, the gas is wasted. 01:47.070 --> 01:50.490 So the caller needs to pay that price. 01:50.850 --> 02:04.530 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 02:07.770 --> 02:13.610 resource -intensive piece of code, it could lead to a halt of the network. 02:14.030 --> 02:23.770 However, this defense mechanism, which is the block gas limit, may also cause a denial-of-service on smart contract functions. 02:23.910 --> 02:32.370 And this will lead to frozen funds, where by frozen funds, you can also see them as lost funds. 02:33.650 --> 02:35.510 Here's a toy example. 02:35.510 --> 02:42.870 For instance, you have a naive implementation of a bank in a smart contract. 02:42.870 --> 02:55.630 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. 02:56.510 --> 03:01.010 And it iterates with this for loop over all users. 03:01.030 --> 03:08.030 It does some heavy computation, which is not shown here, in order to compute the interest for each user. 03:08.030 --> 03:14.150 And then it sends each user the amount of interest they are due. 03:14.470 --> 03:26.390 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. 03:26.590 --> 03:38.130 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. 03:39.710 --> 03:57.270 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. 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:13.610 And this was due to the fact that the contract wanted to clear its internal storage. 04:13.610 --> 04:26.290 And doing that using these two instructions, which compiled to code which iterates over all locations and deletes them one by one. 04:27.230 --> 04:39.450 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. 04:39.690 --> 04:45.930 However, with a new hard fork, the block gas limit was increased. 04:46.010 --> 04:54.830 And the winning user was able to get their jackpot out, thankfully. 04:54.830 --> 04:59.890 But it took some time, they couldn't do it immediately. 04:59.990 --> 05:05.710 And if there 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:25.330 It was increased up almost to 5 million in 2016. 05:25.450 --> 05:32.510 However, it also was decreased at some point for a shorter period of time. 05:32.970 --> 05:36.810 And then afterwards, it keeps increasing. 05:37.150 --> 05:40.390 At today, it's around 10 million. 05:40.750 --> 05:44.990 And it may also increase further, but who knows. 05:44.990 --> 05:47.410 So this is a dynamic parameter. 05:47.410 --> 05:50.550 It's not exactly changing every day. 05:50.550 --> 05:57.890 But people should keep in mind that this is not something that you can rely on forever. 05:58.410 --> 06:08.310 And what we see during our smart contract security audits is that many projects still contain these gas usage issues. 06:08.770 --> 06:20.790 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. 06:21.110 --> 06:26.810 And they are freely available and well known in the community. 06:26.990 --> 06:30.570 However, the question is always, what do you do after you detect them? 06:30.570 --> 06:35.190 You tell the developer, yeah, you need to fix it. 06:35.190 --> 06:38.270 And then he is like, how can I fix it? 06:38.270 --> 06:44.090 Of course, an ideal way to fix this would be to completely remove the loops. 06:44.930 --> 06:47.030 But sometimes that's not an option. 06:47.070 --> 06:57.870 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. 06:58.410 --> 07:23.990 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. 07:24.010 --> 07:37.430 So this currently is sometimes manual work to detect this bound or what parameters could lead to an out-of-gas error. 07:37.530 --> 07:44.670 And it's pretty tedious depending on it's very specific to the smart contract that you're using. 07:45.690 --> 07:50.930 So in this talk, we basically want to automate this process. 07:50.930 --> 07:58.110 We want to generate this kind of denial-of-service exploit and then also fix the issue. 07:59.730 --> 08:01.730 And there are several challenges. 08:01.730 --> 08:11.070 The first one, which is probably the easiest of them all, is how do you determine the exact gas usage during execution? 08:11.770 --> 08:17.830 Then depending on which functions you may have, they may have like a large search space. 08:17.830 --> 08:29.430 So if you have several function input parameters, which are uints or strings, they can have a lot of possible values. 08:29.430 --> 08:39.810 So how do you search through all of those possible values and determine the ones which could lead to an out-of-gas issue? 08:40.350 --> 08:59.370 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. 08:59.370 --> 09:02.130 So we're going to see some examples of those. 09:02.430 --> 09:06.510 For determining the gas usage, there's multiple approaches. 09:06.750 --> 09:19.330 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. 09:19.850 --> 09:23.370 And we use the gasLeft function in our implementation. 09:24.690 --> 09:34.110 The second challenge was about large number of inputs, and there's different fuzzing heuristics you can use in order to do that. 09:34.130 --> 09:40.230 The brute force one is just randomly picking possible input values, which is slow. 09:40.230 --> 09:48.330 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. 09:49.690 --> 10:02.950 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. 10:03.570 --> 10:08.270 There's also other possible heuristics, so we're not saying that these are the only three. 10:08.430 --> 10:14.910 Of course, many people will come up with other heuristics, which are maybe better, maybe not. 10:14.910 --> 10:21.250 But what we wanted to look into was how to use reinforcement learning for this kind of purpose. 10:22.130 --> 10:33.350 And in our approach, we model the problem as a Markov decision process, where the S is all states of the EVM. 10:33.450 --> 10:47.730 A, the set of actions is basically smart contract functions with possibly random inputs or maybe more carefully designed inputs. 10:47.730 --> 10:57.090 This is basically the secret sauce or the most important part of the modeling part. 10:57.090 --> 10:59.550 How do you generate your action set? 10:59.550 --> 11:02.590 Which actions your reinforcement learning agent can perform? 11:03.090 --> 11:22.810 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. 11:22.810 --> 11:24.530 It's deterministic. 11:24.850 --> 11:36.530 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. 11:36.750 --> 11:42.270 And again, with the reward function, we're playing a bit around with it at the moment. 11:42.270 --> 11:44.190 This is just to give you an indication. 11:45.140 --> 11:57.490 We actually are also penalizing if we want to get to the exact bound where this out of gas error happens. 11:57.790 --> 12:10.950 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. 12:10.950 --> 12:14.850 So for that, we're setting the block gas limit pretty high. 12:16.610 --> 12:26.450 One example of a super simple function where such an out of gas error could occur is shown here with this sum function. 12:26.450 --> 12:36.830 It's a pure function which just iterates over integer numbers up to a given value n and computes their sum. 12:36.830 --> 12:48.630 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. 12:49.290 --> 12:52.730 The second example is a bit different. 12:52.730 --> 13:05.330 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. 13:05.330 --> 13:15.390 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. 13:15.690 --> 13:20.750 But m should not be equal to zero, otherwise we have a division by zero. 13:22.030 --> 13:34.970 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. 13:34.970 --> 13:40.390 And you'll notice that the function which contains the loop is called sumEntries. 13:40.810 --> 13:46.650 It iterates over all these entries and computes their sum. 13:46.650 --> 13:52.710 However, this function does not have an input parameter as the ones we saw on the previous slides. 13:53.010 --> 14:03.730 This basically means that 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:15.290 And other functions like getEntry do not affect this length. 14:15.290 --> 14:23.870 So the goal here is the goal for the 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:33.190 It just sees functions and tries to execute them. 14:33.190 --> 14:52.370 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. 14:52.930 --> 15:04.750 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? 15:04.750 --> 15:06.930 There are such smart contracts. 15:06.930 --> 15:18.630 Which one should the reinforcement learning agent call in order to obtain a proper trace where an out-of-gas issue occurs, right? 15:18.630 --> 15:20.910 This may be very difficult. 15:20.970 --> 15:27.870 It's a very large search space because you also have possible different function calls with many parameters. 15:27.870 --> 15:30.650 So it's a large search. 15:31.170 --> 15:46.630 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. 15:47.190 --> 16:06.970 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. 16:07.230 --> 16:16.790 And this way you determine which other locations or instructions are affected by this tainted location. 16:16.990 --> 16:34.450 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. 16:35.890 --> 16:46.890 So here's the example, slightly modified function, some entries from our third example on the previous slides. 16:46.890 --> 17:01.770 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. 17:03.010 --> 17:10.990 And basically, it compares whether this input parameter is zero, or if it's greater than the length. 17:11.530 --> 17:16.810 And based on that comparison, it assigns the bound to a different value, right? 17:16.830 --> 17:19.090 And then it loops over that bound. 17:19.650 --> 17:36.850 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. 17:36.890 --> 17:43.330 And we basically taint all the other memory locations that are affected by the bound. 17:43.430 --> 17:47.650 So n is affected by the bound explicitly because it's assigned here. 17:48.180 --> 17:52.710 And it's also affecting the entries length. 17:53.090 --> 17:57.470 However, it's also implicitly affecting these two values here. 17:58.010 --> 18:06.630 It's also therefore implicitly or explicitly affecting the state variable entries, right? 18:06.630 --> 18:17.960 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. 18:18.400 --> 18:21.700 And we start looking into the functions. 18:21.840 --> 18:31.500 And we see that the addEntry function is also tainted because it affects the entries length. 18:31.600 --> 18:38.040 The other function, which is called getEntries, does not affect the entries.length. 18:38.040 --> 18:39.640 Therefore, it's not tainted. 18:39.640 --> 18:43.540 And we can do that with more other functions that are in the smart contract. 18:43.740 --> 18:49.080 This way, we have a subset of functions that our reinforcement learning agent can call. 18:50.320 --> 18:57.720 Now, the question is, what do you do once you know where and when the out-of-gas error occurs? 18:58.520 --> 19:00.260 Basically, fix it. 19:00.260 --> 19:04.940 And one way to fix it would be to add these kind of require statements. 19:04.940 --> 19:12.260 And we revisit the previous examples that we saw on the previous slides. 19:13.360 --> 19:16.800 The first one was this simple sum function. 19:17.240 --> 19:25.940 And here, you can basically add a require statement at the beginning with this bound that you determined before. 19:25.940 --> 19:33.060 This, of course, can be something that you can set depending on how the block gas limit evolves. 19:33.060 --> 19:35.560 So, it doesn't need to be a hard-coded constant here. 19:35.560 --> 19:38.400 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 --> 19:56.880 And you can place the require here. 19:56.880 --> 20:00.880 Later, you can place it earlier. 20:01.860 --> 20:06.760 And you can also do it where you have multiple functions. 20:07.000 --> 20:19.460 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. 20:19.460 --> 20:36.500 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. 20:38.780 --> 20:42.000 So, that was pretty much it. 20:42.000 --> 20:51.560 In conclusion, we all know loops can cause out-of-gas errors, and these errors can lead to frozen or lost funds. 20:51.560 --> 21:01.820 And detecting such errors is easy, but determining the exact input that is going to cause it is harder. 21:01.920 --> 21:07.320 And here, I'm not just saying any input, but basically being able to fix. 21:07.320 --> 21:15.240 So, we're talking about the boundary condition between where it doesn't run out of gas and then it runs out of gas. 21:16.520 --> 21:32.620 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. 21:33.180 --> 21:45.600 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. 21:47.640 --> 21:48.780 That's my talk. 21:48.780 --> 21:50.620 Thanks a lot for your attention. 21:50.780 --> 21:51.940 Any questions? 23:01.390 --> 23:02.950 Yeah, me neither. 23:13.030 --> 23:13.830 Yep. 23:14.850 --> 23:16.230 Thank you. 23:24.450 --> 23:25.470 How's it going? 23:25.470 --> 23:26.610 Can you hear me? 23:41.090 --> 23:42.650 Hey, how's it going, everybody? 23:44.270 --> 23:48.750 I'm just going to get my screen shared here. 23:52.870 --> 23:55.690 Yeah, I can also just hang out and...