This guide was written by whitehat Alexander Schlindwein, known for discovering the critical vulnerability in Fei Protocol discussed in this advanced tutorial.

Imagine the following scenario: you just found a critical vulnerability that allows funds in a smart contract to be drained. The exploit, however, is complicated and requires multiple payload parameters to be set correctly for it to be effective or even profitable at all.

It quickly turns out that calculating optimal parameters by hand is infeasible, due to the complex nature of the exploit. And yet, you want to responsibly disclose a Proof of Concept (PoC) that maximizes the amount of funds that can be drained from the contract. Why? Because it’s often true that the greater the funds at risk, the higher the bug bounty reward.

In such a situation, linear programming can be an exceptionally helpful tool. This is an advanced tutorial for whitehats who are looking to take their hacking skills to the next level.

Linear Programming

Linear programming, also called Linear optimization or LP, is a method to minimize or maximize a mathematical expression (objective) by finding optimal values for the objective’s variables (decision variables) while adhering to certain rules (constraints). For example, the following linear problem can be solved by an LP solver:

maximize 5X + 6Y // Objective. X and Y are decision variablesX + Y ≤ 5 // 1. Constraint
3X + 2Y ≤ 12 // 2. Constraint
X ≥ 0 // 3. Constraint
Y ≥ 0 // 4. Constraint

LP methods are widely used to solve difficult real-world problems ranging from setting traffic light intervals for optimal traffic flow, to airlines achieving maximum profit for seat pricing. As bug bounty hunters, we can also utilize this technique for our PoCs.

Different kinds of optimization problems

Depending on the constraints and equations we want to use in our model, we need to choose a fitting solver, since not every solver can take on every problem. There are minor details of our problem which will have a significant effect on which solvers we can use. Optimization problems can be roughly categorized into the following categories (not exhaustive):

• LP — Linear Problem: All decision variables are from the set of real numbers and all equations are linear
• MILP — Mixed-Integer linear problem: Decision variables can be restricted to be integers. All equations are linear
• NLP — Non-linear Problem: All decision variables are from the set of real numbers. Equations can be non-linear
• MINLP — Mixed-Integer non-linear problem: Decision variables can be restricted to be integers. Equations can be non-linear

Free vs. Commercial Solvers

For more complex problems, there are also commercial solvers available, e.g. IBM CPLEX or Gurobi. One of the main differences between free and commercial solvers is that commercial solvers exceed the performance of free solvers by orders of magnitude and can take on significantly larger problems.

However, since we are not trying to simulate the traffic flow of an entire metropolis, we will most likely be able to use a freely available solver for our use case of optimizing smart contract exploit parameters.

Using Optimization to Build a PoC

The Fei Protocol Flashloan Vulnerability is a prime example of a situation where optimization can be used to find optimal attack parameters. We will now start to build the model used for the PoC from scratch.

For the PoC we will use GEKKO, a publicly available, free Python package that provides a unified interface to various solvers for the different types of problems listed above.

Note: I’d highly suggest reading the blog post above first if you haven’t already, since the following sections will assume general knowledge about how the exploit works.

The Model

We begin by creating a GEKKO model. The model is a container that will include all relevant data for our optimization problem like decision variables and constraints.

m = GEKKO()

External Constants

Fixed constants that do not change during optimization are called Params. We initialize the following three constants for later use in the model.

The current peg price as reported by Fei’s oracle. The peg is used to calculate how many FEI are paid out when making a purchase on the bonding curve.

peg = m.Param(value=3178.0327)

The current amount of WETH in the FEI/WETH Uniswap V2 pool. This is relevant when temporarily bringing the pool out of balance.

p0 = m.Param(value=141245.117)

The current amount of FEI in the FEI/WETH Uniswap V2 pool. Again, this is relevant when temporarily bringing the pool out of balance.

p1 = m.Param(value=463938347)

Decision Variables

This problem has two decision variables:

1. d (dump): How much ETH should be dumped into the FEI/WETH Uniswap pool
2. b (buy): How much ETH should be spent to purchase FEI from the bonding curve

d = m.Var(lb=0, value=50000)
b = m.Var(lb=0, value=50000)

We set the lower bound lb to zero for both variables, meaning they are not allowed to go negative. Also note that we set a starting value of 50,000 for both variables. Solvers are not always perfect, and they can end up with a valid but suboptimal solution (“getting stuck at a local maximum”), which is what happens when we do not set a starting value in this case. Situations like this are found by trial and error and can often be fixed by playing around with different starting values.

Constraints

In this model, we only have a single constraint, which limits the total amount of ETH the exploit is allowed to use. The PoC uses Aave as a flash loan provider which at that time had roughly 700,000 ETH available for flash loans. GEKKO calls constraints Equations.

m.Equation(d + b <= 700000)

Building the Objective

At this point, we have everything set up to begin building the objective. The goal of this non-linear program is to maximize the profit, which is the difference between all funds we earn and all funds we spend during the exploit’s execution. We will model the exploit into mathematical expressions step-by-step while keeping track of all funds we earn and spend. For simplicity, we will ignore trading fees on Uniswap and in the Fei contracts.

1. Dump WETH into the Uniswap FEI/WETH pool

p0_d = p0 + d
p1_d = (p0 * p1) / p0_d
r1_d = p1 - p1_d

We dump d WETH into the pool, increasing its WETH balance by d. The pool’s FEI balance is decreased according to Uniswap’s famous x * y = k formula. We keep track of the FEI we earned in r1_d.

2. Buy FEI from Fei’s bonding curve

r1_b = b * peg

We spend b WETH to purchase FEI from the bonding curve and store the amount of FEI we earned in r1_b. Our previously set peg param also appears here.

3. Allocate funds from bonding curve purchase

p0_b = p0_d + b
p1_b = p1_d * (p0_b / p0_d)

Now we tell Fei to allocate funds collected from bonding curve purchases to the Uniswap pool by providing liquidity. The Fei contract holds b WETH from our purchase in step 2. The required FEI amount is freshly minted.

The Uniswap pool’s WETH balance is increased by b and the pool’s FEI balance is increased according to Uniswap’s x * y = k formula.

4. Spend FEI to buy back ETH on Uniswap

p1_f = p1_b + r1_d + r1_b
p0_f = (p0_b * p1_b) / p1_f
r0_f = p0_b - p0_f

In both steps 1 and 2, we earned FEI. We will now put all of these tokens back into the FEI/WETH pool to buy back WETH.

The Uniswap pool’s FEI balance is increased by the amount of FEI we received in steps 1 and 2. The pool’s WETH balance is decreased according to Uniswap’s x * y = k formula. The WETH we earned in this step is stored in r0_f.

5. The final objective

We can now sum up all profits and losses we made:

• We earned r0_f WETH during step 5
• We spent d WETH during step 1
• We spent b WETH during step 2

r0 = r0_f - d - b
m.Maximize(r0)

Results

Running the script with the parameters set as in the post mortem yields the following result:

EXIT: Optimal Solution Found. The solution was found. The final value of the objective function is -41590.7411392950 ---------------------------------------------------
Solver : IPOPT (v3.12)
Solution time : 1.810000001569279E-002 sec
Objective : -41590.7411392950
Successful solution
---------------------------------------------------
Results
Objective: -41590.741139
d: [506292.63444]
b: [193707.3655]

We should dump 506,292 WETH into the Uniswap pool and then spend 193,707 WETH to purchase FEI from the bonding curve. This will net us a profit of 41,590 WETH.

Note: When maximizing an objective, GEKKO will display the objective result with a flipped sign as can be seen here.

Summary

We’ve used optimization to successfully compute optimal attack parameters for the Fei flash loan vulnerability. Knowing how to leverage optimization techniques is a valuable skill for blockchain bug bounty hunters and I can only recommend learning about this technology to everyone active in this space.

P.S. Hackers subscribed to our newsletter are 35.8% more likely to earn a bug bounty. Click here to sign up.