Summary
The quickSort function in LibFlood has its sort logic broken when there are repeated deltaB values inside the array. This results in incorrect elements order, leading to major errors in SOP distribution as the calculateSopPerWell relies on the descending logic provided by the quickSort to distribute the sop.
LibFlood -> handleRain
...
WellDeltaB[] memory wellDeltaBs,
uint256 totalPositiveDeltaB,
uint256 totalNegativeDeltaB,
uint256 positiveDeltaBCount
@> ) = getWellsByDeltaB();
@> wellDeltaBs = calculateSopPerWell(
wellDeltaBs,
totalPositiveDeltaB,
totalNegativeDeltaB,
positiveDeltaBCount
);
for (uint i; i < wellDeltaBs.length; i++) {
@> sopWell(wellDeltaBs[I]);
}
}
PoC
On Flood.t.sol import the foundry console log
+ import "forge-std/console.sol";
Paste the two tests below:
function testQuickSort_whenRepeatedPositiveElements_returnWrongSort() public {
LibFlood.WellDeltaB[] memory wells = new LibFlood.WellDeltaB[](5);
int right = int(wells.length - 1);
wells = new LibFlood.WellDeltaB[](6);
right = int(wells.length - 1);
wells[0] = LibFlood.WellDeltaB(address(0), 200);
wells[1] = LibFlood.WellDeltaB(address(1), 0);
wells[2] = LibFlood.WellDeltaB(address(2), 400);
wells[3] = LibFlood.WellDeltaB(address(3), -200);
wells[4] = LibFlood.WellDeltaB(address(4), 200);
wells[5] = LibFlood.WellDeltaB(address(5), 2);
wells = LibFlood.quickSort(wells, 0, right);
console.log("Printing sorted deltaB");
for (uint256 i = 0; i < wells.length; i++) {
console.logInt(wells[i].deltaB);
}
assertEq(wells[0].deltaB, 400);
assertEq(wells[1].deltaB, 200);
assertEq(wells[2].deltaB, 200);
assertEq(wells[3].deltaB, 2);
assertEq(wells[4].deltaB, 0);
assertEq(wells[5].deltaB, -200);
}
function testQuickSort_whenRepeatedNegativeElements_returnWrongSort() public {
LibFlood.WellDeltaB[] memory wells = new LibFlood.WellDeltaB[](5);
int right = int(wells.length - 1);
wells = new LibFlood.WellDeltaB[](6);
right = int(wells.length - 1);
wells[0] = LibFlood.WellDeltaB(address(0), 400);
wells[1] = LibFlood.WellDeltaB(address(1), 0);
wells[2] = LibFlood.WellDeltaB(address(2), -100);
wells[3] = LibFlood.WellDeltaB(address(3), 200);
wells[4] = LibFlood.WellDeltaB(address(4), -100);
wells[5] = LibFlood.WellDeltaB(address(5), 2);
wells = LibFlood.quickSort(wells, 0, right);
console.log("Printing sorted deltaB");
for (uint256 i = 0; i < wells.length; i++) {
console.logInt(wells[i].deltaB);
}
assertEq(wells[0].deltaB, 400);
assertEq(wells[1].deltaB, 200);
assertEq(wells[2].deltaB, 2);
assertEq(wells[3].deltaB, 0);
assertEq(wells[4].deltaB, -100);
assertEq(wells[5].deltaB, -100);
}
Run forge test --match-test testQuickSort_whenRepeated -vv
Output:
Repeated positive values
[FAIL. Reason: assertion failed: 2 != 200] testQuickSort_whenRepeatedPositiveElements_returnWrongSort() (gas: 18771)
Logs:
Printing sorted deltaB
400
200
@> 2
@> 200
@> -200
@> 0
[FAIL. Reason: assertion failed: 2 != 200] testQuickSort_whenRepeatedPositiveElements_returnWrongSort() (gas: 18771)
Repeated negative values
Ran 2 tests for test/foundry/sun/Flood.t.sol:FloodTest
[FAIL. Reason: assertion failed: 2 != 200] testQuickSort_whenRepeatedNegativeElements_returnWrongSort() (gas: 17657)
Logs:
Printing sorted deltaB
400
200
2
@> -100
@> -100
@> 0
As shown in the outputs above the sorting is broken and this also impacts the sorting of the next elements. i.e: "400, 200, 2, 200, -200, 0"
Impact
Tools Used
Foundry & Manual Review
Recommendations
On quickSort add support to check for repeated values.
function quickSort(
WellDeltaB[] memory arr,
int left,
int right
) internal 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)]);
+ WellDeltaB memory pivot = arr[uint(mid)];
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--;
+ while (arr[uint(i)].deltaB > pivot.deltaB || (arr[uint(i)].deltaB == pivot.deltaB && uint(i) < mid)) i++;
+ while (pivot.deltaB > arr[uint(j)].deltaB || (pivot.deltaB == arr[uint(j)].deltaB && uint(j) > mid)) 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;
}
After the fix, all tests pass. Run: forge test --match-contract FloodTest, output:
Suite result: ok. 15 passed; 0 failed; 0 skipped; finished in 864.56ms (1.34s CPU time)
