1
00:00:01,050 --> 00:00:02,310
Great.

2
00:00:02,430 --> 00:00:03,590
Yeah, hello, everyone.

3
00:00:03,590 --> 00:00:04,870
My name is Sebastian.

4
00:00:05,770 --> 00:00:16,030
This work is about identifying and fixing out-of-gas errors in smart contracts with what we call smart fuzzing.

5
00:00:16,030 --> 00: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.

6
00:00:29,370 --> 00:00:34,910
So just starting with a quick intro, but you all probably know this.

7
00:00:34,910 --> 00:00:40,350
On Ethereum, you have smart contracts that are executed on the EVM.

8
00:00:40,370 --> 00:00:45,030
And calling a function on one of those smart contracts changes the state.

9
00:00:45,030 --> 00:00:49,590
And these state changes often involve transfers of funds.

10
00:00:50,130 --> 00:00:55,930
However, these smart contracts are just programs which may contain bugs.

11
00:00:55,990 --> 00:01:01,170
And exploiting those can lead to stolen or frozen funds.

12
00:01:01,230 --> 00: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.

13
00:01:18,150 --> 00: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.

14
00:01:28,430 --> 00:01:33,390
Now, in order to prevent denial-of-service attacks, there's a block gas limit.

15
00:01:33,990 --> 00:01:42,850
And if the gas consumed by a certain smart contract function exceeds this block gas limit, then the transaction is reverted.

16
00:01:43,430 --> 00:01:46,520
However, the gas is wasted.

17
00:01:47,070 --> 00:01:50,490
So the caller needs to pay that price.

18
00:01:50,850 --> 00: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

19
00:02:07,770 --> 00:02:13,610
resource -intensive piece of code, it could lead to a halt of the network.

20
00:02:14,030 --> 00:02:23,770
However, this defense mechanism, which is the block gas limit, may also cause a denial-of-service on smart contract functions.

21
00:02:23,910 --> 00:02:32,370
And this will lead to frozen funds, where by frozen funds, you can also see them as lost funds.

22
00:02:33,650 --> 00:02:35,510
Here's a toy example.

23
00:02:35,510 --> 00:02:42,870
For instance, you have a naive implementation of a bank in a smart contract.

24
00:02:42,870 --> 00: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.

25
00:02:56,510 --> 00:03:01,010
And it iterates with this for loop over all users.

26
00:03:01,030 --> 00:03:08,030
It does some heavy computation, which is not shown here, in order to compute the interest for each user.

27
00:03:08,030 --> 00:03:14,150
And then it sends each user the amount of interest they are due.

28
00:03:14,470 --> 00: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.

29
00:03:26,590 --> 00: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.

30
00:03:39,710 --> 00: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.

31
00:03:57,530 --> 00:04:03,910
However, it got stuck because the function that was meant to pay out was using too much gas.

32
00:04:03,910 --> 00:04:13,610
And this was due to the fact that the contract wanted to clear its internal storage.

33
00:04:13,610 --> 00: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.

34
00:04:27,230 --> 00: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.

35
00:04:39,690 --> 00:04:45,930
However, with a new hard fork, the block gas limit was increased.

36
00:04:46,010 --> 00:04:54,830
And the winning user was able to get their jackpot out, thankfully.

37
00:04:54,830 --> 00:04:59,890
But it took some time, they couldn't do it immediately.

38
00:04:59,990 --> 00:05:05,710
And if there were no hard fork, or if there were more participants, maybe it was still be stuck.

39
00:05:06,510 --> 00:05:14,290
Here's just an indication of how the block gas limit has evolved over time.

40
00:05:14,290 --> 00:05:18,070
So you can see at the beginning, it was somewhere around 3 million.

41
00:05:18,070 --> 00:05:25,330
It was increased up almost to 5 million in 2016.

42
00:05:25,450 --> 00:05:32,510
However, it also was decreased at some point for a shorter period of time.

43
00:05:32,970 --> 00:05:36,810
And then afterwards, it keeps increasing.

44
00:05:37,150 --> 00:05:40,390
At today, it's around 10 million.

45
00:05:40,750 --> 00:05:44,990
And it may also increase further, but who knows.

46
00:05:44,990 --> 00:05:47,410
So this is a dynamic parameter.

47
00:05:47,410 --> 00:05:50,550
It's not exactly changing every day.

48
00:05:50,550 --> 00:05:57,890
But people should keep in mind that this is not something that you can rely on forever.

49
00:05:58,410 --> 00:06:08,310
And what we see during our smart contract security audits is that many projects still contain these gas usage issues.

50
00:06:08,770 --> 00: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.

51
00:06:21,110 --> 00:06:26,810
And they are freely available and well known in the community.

52
00:06:26,990 --> 00:06:30,570
However, the question is always, what do you do after you detect them?

53
00:06:30,570 --> 00:06:35,190
You tell the developer, yeah, you need to fix it.

54
00:06:35,190 --> 00:06:38,270
And then he is like, how can I fix it?

55
00:06:38,270 --> 00:06:44,090
Of course, an ideal way to fix this would be to completely remove the loops.

56
00:06:44,930 --> 00:06:47,030
But sometimes that's not an option.

57
00:06:47,070 --> 00: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.

58
00:06:58,410 --> 00: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.

59
00:07:24,010 --> 00: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.

60
00:07:37,530 --> 00:07:44,670
And it's pretty tedious depending on it's very specific to the smart contract that you're using.

61
00:07:45,690 --> 00:07:50,930
So in this talk, we basically want to automate this process.

62
00:07:50,930 --> 00:07:58,110
We want to generate this kind of denial-of-service exploit and then also fix the issue.

63
00:07:59,730 --> 00:08:01,730
And there are several challenges.

64
00:08:01,730 --> 00: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?

65
00:08:11,770 --> 00:08:17,830
Then depending on which functions you may have, they may have like a large search space.

66
00:08:17,830 --> 00:08:29,430
So if you have several function input parameters, which are uints or strings, they can have a lot of possible values.

67
00:08:29,430 --> 00: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?

68
00:08:40,350 --> 00: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.

69
00:08:59,370 --> 00:09:02,130
So we're going to see some examples of those.

70
00:09:02,430 --> 00:09:06,510
For determining the gas usage, there's multiple approaches.

71
00:09:06,750 --> 00: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.

72
00:09:19,850 --> 00:09:23,370
And we use the gasLeft function in our implementation.

73
00:09:24,690 --> 00: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.

74
00:09:34,130 --> 00:09:40,230
The brute force one is just randomly picking possible input values, which is slow.

75
00:09:40,230 --> 00: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.

76
00:09:49,690 --> 00: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.

77
00:10:03,570 --> 00:10:08,270
There's also other possible heuristics, so we're not saying that these are the only three.

78
00:10:08,430 --> 00:10:14,910
Of course, many people will come up with other heuristics, which are maybe better, maybe not.

79
00:10:14,910 --> 00:10:21,250
But what we wanted to look into was how to use reinforcement learning for this kind of purpose.

80
00:10:22,130 --> 00: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.

81
00:10:33,450 --> 00:10:47,730
A, the set of actions is basically smart contract functions with possibly random inputs or maybe more carefully designed inputs.

82
00:10:47,730 --> 00:10:57,090
This is basically the secret sauce or the most important part of the modeling part.

83
00:10:57,090 --> 00:10:59,550
How do you generate your action set?

84
00:10:59,550 --> 00:11:02,590
Which actions your reinforcement learning agent can perform?

85
00:11:03,090 --> 00: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.

86
00:11:22,810 --> 00:11:24,530
It's deterministic.

87
00:11:24,850 --> 00: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.

88
00:11:36,750 --> 00:11:42,270
And again, with the reward function, we're playing a bit around with it at the moment.

89
00:11:42,270 --> 00:11:44,190
This is just to give you an indication.

90
00:11:45,140 --> 00:11:57,490
We actually are also penalizing if we want to get to the exact bound where this out of gas error happens.

91
00:11:57,790 --> 00: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.

92
00:12:10,950 --> 00:12:14,850
So for that, we're setting the block gas limit pretty high.

93
00:12:16,610 --> 00: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.

94
00:12:26,450 --> 00:12:36,830
It's a pure function which just iterates over integer numbers up to a given value n and computes their sum.

95
00:12:36,830 --> 00: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.

96
00:12:49,290 --> 00:12:52,730
The second example is a bit different.

97
00:12:52,730 --> 00: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.

98
00:13:05,330 --> 00: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.

99
00:13:15,690 --> 00:13:20,750
But m should not be equal to zero, otherwise we have a division by zero.

100
00:13:22,030 --> 00: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.

101
00:13:34,970 --> 00:13:40,390
And you'll notice that the function which contains the loop is called sumEntries.

102
00:13:40,810 --> 00:13:46,650
It iterates over all these entries and computes their sum.

103
00:13:46,650 --> 00:13:52,710
However, this function does not have an input parameter as the ones we saw on the previous slides.

104
00:13:53,010 --> 00:14:03,730
This basically means that another function in the smart contract is probably going to affect the length of this list.

105
00:14:04,190 --> 00:14:11,030
And the one that it does affect is this addEntry function.

106
00:14:11,170 --> 00:14:15,290
And other functions like getEntry do not affect this length.

107
00:14:15,290 --> 00: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.

108
00:14:23,870 --> 00:14:29,670
So reinforcement learning agent doesn't understand what addEntry means or getEntry or sumEntries.

109
00:14:29,670 --> 00:14:33,190
It just sees functions and tries to execute them.

110
00:14:33,190 --> 00: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.

111
00:14:52,930 --> 00: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?

112
00:15:04,750 --> 00:15:06,930
There are such smart contracts.

113
00:15:06,930 --> 00: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?

114
00:15:18,630 --> 00:15:20,910
This may be very difficult.

115
00:15:20,970 --> 00:15:27,870
It's a very large search space because you also have possible different function calls with many parameters.

116
00:15:27,870 --> 00:15:30,650
So it's a large search.

117
00:15:31,170 --> 00: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.

118
00:15:47,190 --> 00: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.

119
00:16:07,230 --> 00:16:16,790
And this way you determine which other locations or instructions are affected by this tainted location.

120
00:16:16,990 --> 00: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.

121
00:16:35,890 --> 00:16:46,890
So here's the example, slightly modified function, some entries from our third example on the previous slides.

122
00:16:46,890 --> 00: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.

123
00:17:03,010 --> 00:17:10,990
And basically, it compares whether this input parameter is zero, or if it's greater than the length.

124
00:17:11,530 --> 00:17:16,810
And based on that comparison, it assigns the bound to a different value, right?

125
00:17:16,830 --> 00:17:19,090
And then it loops over that bound.

126
00:17:19,650 --> 00: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.

127
00:17:36,890 --> 00:17:43,330
And we basically taint all the other memory locations that are affected by the bound.

128
00:17:43,430 --> 00:17:47,650
So n is affected by the bound explicitly because it's assigned here.

129
00:17:48,180 --> 00:17:52,710
And it's also affecting the entries length.

130
00:17:53,090 --> 00:17:57,470
However, it's also implicitly affecting these two values here.

131
00:17:58,010 --> 00:18:06,630
It's also therefore implicitly or explicitly affecting the state variable entries, right?

132
00:18:06,630 --> 00: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.

133
00:18:18,400 --> 00:18:21,700
And we start looking into the functions.

134
00:18:21,840 --> 00:18:31,500
And we see that the addEntry function is also tainted because it affects the entries length.

135
00:18:31,600 --> 00:18:38,040
The other function, which is called getEntries, does not affect the entries.length.

136
00:18:38,040 --> 00:18:39,640
Therefore, it's not tainted.

137
00:18:39,640 --> 00:18:43,540
And we can do that with more other functions that are in the smart contract.

138
00:18:43,740 --> 00:18:49,080
This way, we have a subset of functions that our reinforcement learning agent can call.

139
00:18:50,320 --> 00:18:57,720
Now, the question is, what do you do once you know where and when the out-of-gas error occurs?

140
00:18:58,520 --> 00:19:00,260
Basically, fix it.

141
00:19:00,260 --> 00:19:04,940
And one way to fix it would be to add these kind of require statements.

142
00:19:04,940 --> 00:19:12,260
And we revisit the previous examples that we saw on the previous slides.

143
00:19:13,360 --> 00:19:16,800
The first one was this simple sum function.

144
00:19:17,240 --> 00:19:25,940
And here, you can basically add a require statement at the beginning with this bound that you determined before.

145
00:19:25,940 --> 00:19:33,060
This, of course, can be something that you can set depending on how the block gas limit evolves.

146
00:19:33,060 --> 00:19:35,560
So, it doesn't need to be a hard-coded constant here.

147
00:19:35,560 --> 00:19:38,400
It could also be a state variable of the smart contract.

148
00:19:40,080 --> 00:19:46,380
This way, you prevent the caller from wasting gas if the value of n is too large.

149
00:19:47,740 --> 00:19:53,040
Similarly, you can do a bound on the second example that we had.

150
00:19:54,000 --> 00:19:56,880
And you can place the require here.

151
00:19:56,880 --> 00:20:00,880
Later, you can place it earlier.

152
00:20:01,860 --> 00:20:06,760
And you can also do it where you have multiple functions.

153
00:20:07,000 --> 00: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.

154
00:20:19,460 --> 00: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.

155
00:20:38,780 --> 00:20:42,000
So, that was pretty much it.

156
00:20:42,000 --> 00: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.

157
00:20:51,560 --> 00:21:01,820
And detecting such errors is easy, but determining the exact input that is going to cause it is harder.

158
00:21:01,920 --> 00:21:07,320
And here, I'm not just saying any input, but basically being able to fix.

159
00:21:07,320 --> 00: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.

160
00:21:16,520 --> 00: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.

161
00:21:33,180 --> 00: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.

162
00:21:47,640 --> 00:21:48,780
That's my talk.

163
00:21:48,780 --> 00:21:50,620
Thanks a lot for your attention.

164
00:21:50,780 --> 00:21:51,940
Any questions?

165
00:23:01,390 --> 00:23:02,950
Yeah, me neither.

166
00:23:13,030 --> 00:23:13,830
Yep.

167
00:23:14,850 --> 00:23:16,230
Thank you.

168
00:23:24,450 --> 00:23:25,470
How's it going?

169
00:23:25,470 --> 00:23:26,610
Can you hear me?

170
00:23:41,090 --> 00:23:42,650
Hey, how's it going, everybody?

171
00:23:44,270 --> 00:23:48,750
I'm just going to get my screen shared here.

172
00:23:52,870 --> 00:23:55,690
Yeah, I can also just hang out and...