Beanstalk: The Finale
Beanstalk
DeFiHardhatFoundry
250,000 USDC
View results
Previous Next
Submission Details
Severity: medium
Valid

quickSort function does not work as expected, compromising the calculation of Beans per Well to be minted during a flood

crunter

Summary

Peg maintenance of the Bean price is achieved in several ways depending on the specific state of the protocol. During a flood, the bean price is above the peg value and there is an excessive low debt level. To address this, Beanstalk mints additional Beans. However, the calculation of the Beans to be minted can be compromised due to an incorrect implementation of the array sorting function.

Vulnerability Details

During a flood, contracts/libraries/Silo/LibFlood.sol::quickSort function is intended to sort in descending order a given Well deltaBs array arr to calculate the amount of Beans per Well that should be minted. This is a critical step as it directly impacts Bean issuance for the protocol in order to maintain the peg of the Bean price. However, on most cases the resulting array will not be sorted correctly because of a bug within the quickSort function.

Internally, the quickSort function attempts to improve performance on random data by choosing the median of arr[left].deltaB, arr[right].deltaB and arr[middle].deltaB as pivot.

uint mid = uint(left) + (uint(right) - uint(left)) / 2;
WellDeltaB memory pivot = arr[uint(left)].deltaB > arr[uint(mid)].deltaB
? (
arr[uint(left)].deltaB < arr[uint(right)].deltaB
? arr[uint(left)]
: arr[uint(right)] //<@ FINDING
)
: (arr[uint(mid)].deltaB < arr[uint(right)].deltaB ? arr[uint(mid)] : arr[uint(right)]); //<@ FINDING

Nevertheless, the scheme used to get the pivot does not take into account the following two cases:

  • (arr[left].deltaB > arr[mid].deltaB) && arr[left].deltaB > arr[right].deltaB && (arr[right].deltaB < arr[mid].deltaB)

  • (arr[left].deltaB < arr[mid].deltaB) && arr[mid].deltaB > arr[right].deltaB && (arr[right].deltaB < arr[left].deltaB)

This results in poor pivot selection.

In addition, on line 270 the function uses recursion to sort the elements on the left side of the array.

if (left < j) {
return quickSort(arr, left, j); // <@ FINDING
}
if (i < right) {
return quickSort(arr, i, right);
}
return arr;

However, because of the return statement used, the right side of the array never gets sorted, rendering the entire quickSort function useless.

Proof of concept

The test/foundry/sun/Flood.t.sol::testQuickSort test provided in the protocol repository is sufficient to demonstrate the code error in the function by simply changing the input array and running it. For example, changing the sign of wells[4] value:

- wells[4] = LibFlood.WellDeltaB(address(4), -500);
+ wells[4] = LibFlood.WellDeltaB(address(4), 500);

The following code is a very detailed test of the quickSort function in order to illustrate the problems encountered. This code works as a standalone foundry contract test as it does not depend on external files or additional information. Executing it with a verbosity level of two (-vv) is enough to see the logged explanation of the outputs.

// SPDX-License-Identifier: MIT
pragma solidity >=0.6.0 <0.9.0;
​
import {Test, console} from "forge-std/Test.sol";
​
struct WellDeltaB {
address well;
int256 deltaB;
}
​
contract quickSortTest is Test {
WellDeltaB[] public arr0; // random data array
WellDeltaB[] public expectedOutputArray; // expected sorted output array
WellDeltaB public expectedPivot;
​
QuickSort sortArray;
​
function setUp() public {
sortArray = new QuickSort();
​
// initialize arr0 with random data
// arr0 deltaB values = [39, 6, 27, -14, 15];
​
arr0.push(WellDeltaB(address(1), int256(39)));
arr0.push(WellDeltaB(address(2), int256(6)));
arr0.push(WellDeltaB(address(3), int256(27)));
arr0.push(WellDeltaB(address(4), int256(-14)));
arr0.push(WellDeltaB(address(5), int256(15)));
​
//left deltaB : arr0.deltaB[0] = 39
//right deltaB: arr0.deltaB[4] = 15
//mid deltaB: arr0.deltaB[2] = 27
//For this specific set of random data, the expected pivot for the first iteration is the middle value: 27
​
expectedPivot.well = address(3);
expectedPivot.deltaB = 27;
​
// expected ordered array deltaB values = [39, 27, 15, 6, -14]
expectedOutputArray.push(WellDeltaB(address(1), int256(39)));
expectedOutputArray.push(WellDeltaB(address(3), int256(27)));
expectedOutputArray.push(WellDeltaB(address(5), int256(15)));
expectedOutputArray.push(WellDeltaB(address(2), int256(6)));
expectedOutputArray.push(WellDeltaB(address(4), int256(-14)));
}
​
function testPivotCalculation() public view {
WellDeltaB memory pivot1;
WellDeltaB memory pivot2;
​
// this calculates the pivot only for the first iteration of the recursive
// quickSort function, in order to illustrate the mistake in the original function
pivot1 = sortArray.pivotOriginal(arr0, 0, int256(arr0.length - 1));
pivot2 = sortArray.pivot2(arr0, 0, int256(arr0.length - 1));
​
console.log("Expected pivot (1st iteration): %i", expectedPivot.deltaB);
console.log("Original pivot (1st iteration): %i", pivot1.deltaB);
console.log("Corrected pivot (1st iteration): %i", pivot2.deltaB);
​
assert(pivot1.deltaB != expectedPivot.deltaB); // The original calculation for the pivot is incorrect
assert(pivot2.deltaB == expectedPivot.deltaB);
}
​
function testQuickSortFunction() public view {
WellDeltaB[] memory arr1;
WellDeltaB[] memory arr2;
​
arr1 = sortArray.quickSort(arr0, 0, int256(arr0.length - 1));
arr2 = sortArray.quickSort2(arr0, 0, int256(arr0.length - 1));
​
// print to console the original deltaBs array
console.log("Original array deltaBs:");
for (uint i; i < arr0.length; i++) {
console.log("deltaB: %i", arr0[i].deltaB);
}
​
// print to console the sorted deltaBs array using the original quickSort function
console.log("\nSorted array using the original quickSort function:");
for (uint i; i < arr1.length; i++) {
console.log("deltaB: %i", arr1[i].deltaB);
}
​
// print to console the sorted deltaBs array using the corrected quickSort function
console.log("\nSorted array using the corrected quickSort function:");
for (uint i; i < arr2.length; i++) {
console.log("deltaB: %i", arr2[i].deltaB);
}
​
// compare the expected output with the original quickSort function output
bool quickSortSuccess = sortArray.compareArrays(
expectedOutputArray,
arr1
);
​
// compare the expected output with the corrected quickSort function output
bool quickSort2Success = sortArray.compareArrays(
expectedOutputArray,
arr2
);
​
assert(quickSortSuccess == false); // proves that the original quickSort function does not work properly
assert(quickSort2Success == true); // proves the functionality of the quickSort2 function
}
}
​
contract QuickSort {
// ******** The original quickSort function ***********
// made public for practical testing purposes
function quickSort(
WellDeltaB[] memory arr,
int left,
int right
) public pure returns (WellDeltaB[] memory) {
if (left >= right) return arr;
​
// Choose the median of left, right, and middle as pivot (improves performance on random data)
uint mid = uint(left) + (uint(right) - uint(left)) / 2;
WellDeltaB memory pivot = arr[uint(left)].deltaB > arr[uint(mid)].deltaB
? (
arr[uint(left)].deltaB < arr[uint(right)].deltaB
? arr[uint(left)]
: arr[uint(right)]
)
: (
arr[uint(mid)].deltaB < arr[uint(right)].deltaB
? arr[uint(mid)]
: arr[uint(right)]
);
​
int i = left;
int j = right;
while (i <= j) {
while (arr[uint(i)].deltaB > pivot.deltaB) i++;
while (pivot.deltaB > arr[uint(j)].deltaB) j--;
if (i <= j) {
(arr[uint(i)], arr[uint(j)]) = (arr[uint(j)], arr[uint(i)]);
i++;
j--;
}
}
​
if (left < j) {
return quickSort(arr, left, j);
}
if (i < right) {
return quickSort(arr, i, right);
}
return arr;
}
​
// ******** The corrected quickSort function ***********
// made public for practical testing purposes
function quickSort2(
WellDeltaB[] memory arr,
int left,
int right
) public pure returns (WellDeltaB[] memory) {
if (left >= right) return arr;
​
// Choose the median of left, right, and middle as pivot (improves performance on random data)
uint mid = uint(left) + (uint(right) - uint(left)) / 2;
WellDeltaB memory pivot;
​
if (arr[uint(left)].deltaB > arr[uint(mid)].deltaB) {
if (arr[uint(left)].deltaB < arr[uint(right)].deltaB) {
pivot = arr[uint(left)];
} else {
if (arr[uint(right)].deltaB > arr[uint(mid)].deltaB) {
pivot = arr[uint(right)];
} else {
pivot = arr[uint(mid)];
}
}
} else {
if (arr[uint(mid)].deltaB < arr[uint(right)].deltaB) {
pivot = arr[uint(mid)];
} else {
if (arr[uint(right)].deltaB > arr[uint(left)].deltaB) {
pivot = arr[uint(right)];
} else {
pivot = arr[uint(left)];
}
}
}
​
int i = left;
int j = right;
while (i <= j) {
while (arr[uint(i)].deltaB > pivot.deltaB) i++;
while (pivot.deltaB > arr[uint(j)].deltaB) j--;
if (i <= j) {
(arr[uint(i)], arr[uint(j)]) = (arr[uint(j)], arr[uint(i)]);
i++;
j--;
}
}
​
if (left < j) {
arr = quickSort2(arr, left, j);
}
if (i < right) {
return quickSort2(arr, i, right);
}
return arr;
}
​
// ******** The original pivot calculation ***********
function pivotOriginal(
WellDeltaB[] memory arr,
int left,
int right
) public pure returns (WellDeltaB memory) {
// Choose the median of left, right, and middle as pivot (improves performance on random data)
uint mid = uint(left) + (uint(right) - uint(left)) / 2;
WellDeltaB memory pivot = arr[uint(left)].deltaB > arr[uint(mid)].deltaB
? (
arr[uint(left)].deltaB < arr[uint(right)].deltaB
? arr[uint(left)]
: arr[uint(right)]
)
: (
arr[uint(mid)].deltaB < arr[uint(right)].deltaB
? arr[uint(mid)]
: arr[uint(right)]
);
​
return pivot;
}
​
// ******** The corrected pivot calculation ***********
function pivot2(
WellDeltaB[] memory arr,
int left,
int right
) public pure returns (WellDeltaB memory) {
// Choose the median of left, right, and middle as pivot (improves performance on random data)
uint mid = uint(left) + (uint(right) - uint(left)) / 2;
WellDeltaB memory pivot;
​
if (arr[uint(left)].deltaB > arr[uint(mid)].deltaB) {
if (arr[uint(left)].deltaB < arr[uint(mid)].deltaB) {
pivot = arr[uint(left)];
} else {
if (arr[uint(right)].deltaB > arr[uint(mid)].deltaB) {
pivot = arr[uint(right)];
} else {
pivot = arr[uint(mid)];
}
}
} else {
if (arr[uint(mid)].deltaB < arr[uint(right)].deltaB) {
pivot = arr[uint(mid)];
} else {
if (arr[uint(right)].deltaB > arr[uint(left)].deltaB) {
pivot = arr[uint(right)];
} else {
pivot = arr[uint(left)];
}
}
}
​
return pivot;
}
​
function compareArrays(
WellDeltaB[] memory arr1,
WellDeltaB[] memory arr2
) public pure returns (bool) {
if (arr1.length != arr2.length) {
return false;
}
for (uint i = 0; i < arr1.length; i++) {
if (
arr1[i].well != arr2[i].well || arr1[i].deltaB != arr2[i].deltaB
) {
return false;
}
}
return true;
}
}
​

Impact

Impact: High

This bug directly affects the issuance of Beans in order to maintain the price peg. Its impact is directly proportional to the size of the wellDeltaB array.

Likelyhood: Medium

Only presented during a flood.

Tools Used

Manual Review

Foundry

Recommended Mitigation

Previously presented in the proof of concept, it is advisable to change the scheme to obtain the pivot.
To include all the possible cases, an if-else conditional statement scheme is recommended:

// Choose the median of left, right, and middle as pivot (improves performance on random data)
uint mid = uint(left) + (uint(right) - uint(left)) / 2;
WellDeltaB memory pivot;
​
if (arr[uint(left)].deltaB > arr[uint(mid)].deltaB) {
if (arr[uint(left)].deltaB < arr[uint(right)].deltaB) {
pivot = arr[uint(left)];
} else {
if (arr[uint(right)].deltaB > arr[uint(mid)].deltaB) {
pivot = arr[uint(right)];
} else {
pivot = arr[uint(mid)];
}
}
} else {
if (arr[uint(mid)].deltaB < arr[uint(right)].deltaB) {
pivot = arr[uint(mid)];
} else {
if (arr[uint(right)].deltaB > arr[uint(left)].deltaB) {
pivot = arr[uint(right)];
} else {
pivot = arr[uint(left)];
}
}
}

It is critical to remove the return statement when sorting the left side of the array, to allow the right side to be processed as well.

if (left < j) {
- return quickSort(arr, left, j);
+ arr = quickSort(arr, left, j);
}
​
if (i < right) {
return quickSort(arr, i, right);
}
return arr;
Updates

Lead Judging Commences

inallhonesty Lead Judge 12 months ago
Submission Judgement Published
Validated
Assigned finding tags:

quicksort bad

Support

FAQs

Can't find an answer? Chat with us on Discord, Twitter or Linkedin.