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

`LibFlood.quickSort()` doesn't sort values

T1MOH

Summary

Quick sort algorithm is implemented wrong, it doesn't sort. This algorithm is used in core Flood logic during start of the new season.

Vulnerability Details

Quick sort algorithm should:

  1. Choose pivot value

  2. Set pivot value to its correct position

  3. Sort 2 arrays to the left of pivot and to the right.

Issue in implemented algorithm is that it returns on step 3 instead of performing sort on both sub-arrays:

function quickSort(
WellDeltaB[] memory arr,
int left,
int right
) internal pure returns (WellDeltaB[] memory) {
...
​
if (left < j) {
@> return quickSort(arr, left, j);
}
if (i < right) {
@> return quickSort(arr, i, right);
}
return arr;
}

Here is the test which shows incorrect sort:
https://gist.github.com/T1MOH593/47e65a762d1df81f0b1f1b08832a194b

Impact

This function is used in the following chain of calls:

SeasonFacet.gm()
Weather.calcCaseIdandUpdate()
LibFlood.handleRain()
LibFlood.getWellsByDeltaB() <------ Here sorting occurs
LibFlood.calculateSopPerWell() <--- Here sorted array is used

It is used in Flood concept. When Bean price > 1 USD and there is positive deltaB, it mints new Beans and swaps to Well to decrease Bean price. Here's docs page

LibFlood.quickSort() is expected to sort in descending order. Therefore calculateSopPerWell() expects that positive values are stored in array on indexes [0, positiveDeltaBCount - 1]. But this assumption is broken because of issue, so calculation of SOP is completely broken.
https://github.com/Cyfrin/2024-05-beanstalk-the-finale/blob/main/protocol/contracts/libraries/Silo/LibFlood.sol#L338

It's logic is quite complicated to describe, so will omit it. As a result incorrect amounts of SOP are minted during sunrize which completely breaks Bean's peg mechanism named Flood.

Tools Used

Manual Review

Recommendations

Do not return but sort both parts:

function quickSort(
WellDeltaB[] memory arr,
int left,
int right
) internal pure returns (WellDeltaB[] memory) {
...
​
if (left < j) {
- return quickSort(arr, left, j);
+ quickSort(arr, left, j);
}
if (i < right) {
- return quickSort(arr, i, right);
+ quickSort(arr, i, right);
}
return arr;
}
Updates

Lead Judging Commences

inallhonesty Lead Judge about 1 year 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.