Dria
Swan
NFTHardhat
21,000 USDC
View results
Previous Next
Submission Details
Severity: high
Valid

LLMOracleCoordinator::validate failure due to underflow in Statistics::variance

0xlouistsai

Summary

In the Statistics library, the variance function fails because the calculation data[i] - mean might produce a negative result, causing an underflow in the uint256 type. Consequently, LLMOracleCoordinator::validate will fail as it calls LLMOracleCoordinator::finalizeValidation, a private function that uses Statistics::stddev, which in turn calls Statistics::variance. As a result, all validation operations will fail.

Vulnerability Details

In the Statistics library, the variance function is implemented as follows:

function variance(uint256[] memory data) internal pure returns (uint256 ans, uint256 mean) {
mean = avg(data);
uint256 sum = 0;
for (uint256 i = 0; i < data.length; i++) {
>@ uint256 diff = data[i] - mean; // @audit-issue underflow issue
sum += diff * diff;
}
ans = sum / data.length;
}

Consider a uint256 array with elements [1, 2, 3, 4, 5]. The function first calculates the average value (mean), which is (1 + 2 + 3 + 4 + 5) / 5 = 3.

The loop then iterates over each element to compute diff, but at i = 0, where data[0] = 1, the calculation diff = data[0] - mean results in 1 - 3, which should be -2. Since diff is defined as a uint256, this negative result causes an underflow, resulting in the revert of the transaction. This underflow leads to transaction revert, and any downstream calculations, such as those in the stddev function (which relies on variance), will also fail, ultimately causing the LLMOracleCoordinator::validate function to revert.

The following Foundry test serves as a PoC. Run forge test --mt testExploit, and the test will pass, indicating that the operation will indeed revert.

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
​
import "forge-std/Test.sol";
​
/// @notice Simple statistic library for uint256 arrays, numbers are treat as fixed-precision floats.
library Statistics {
/// @notice Compute the mean of the data.
/// @param data The data to compute the mean for.
function avg(uint256[] memory data) internal pure returns (uint256 ans) {
uint256 sum = 0;
for (uint256 i = 0; i < data.length; i++) {
sum += data[i];
}
ans = sum / data.length;
}
​
/// @notice Compute the variance of the data.
/// @param data The data to compute the variance for.
function variance(uint256[] memory data) internal pure returns (uint256 ans, uint256 mean) {
mean = avg(data);
uint256 sum = 0;
for (uint256 i = 0; i < data.length; i++) {
uint256 diff = data[i] - mean;
sum += diff * diff;
}
ans = sum / data.length;
}
​
/// @notice Compute the standard deviation of the data.
/// @dev Computes variance, and takes the square root.
/// @param data The data to compute the standard deviation for.
function stddev(uint256[] memory data) internal pure returns (uint256 ans, uint256 mean) {
(uint256 _variance, uint256 _mean) = variance(data);
mean = _mean;
ans = sqrt(_variance);
}
​
/// @notice Compute the square root of a number.
/// @dev Uses Babylonian method.
/// @param x The number to compute the square root for.
function sqrt(uint256 x) internal pure returns (uint256 y) {
uint256 z = (x + 1) / 2;
y = x;
while (z < y) {
y = z;
z = (x / z + z) / 2;
}
}
}
​
contract UnderflowTest is Test {
function setUp() public {}
​
function testExploit() public {
uint256[] memory data = new uint256[](); // The uint256 array would be [1, 2, 3, 4, 5]
for (uint256 i = 0; i < 5; i++) {
data[i] = i + 1;
}
​
vm.expectRevert(); // The following operation will revert
Statistics.variance(data);
}
}
​

Impact

When a registered oracle calls LLMOracleCoordinator::validate, this function subsequently calls the private finalizeValidation function once the status is marked as completed. Within finalizeValidation, Statistics::stddev is invoked to obtain the (stddev, mean) pair. However, inside Statistics::stddev, the Statistics::variance function is called. If the elements in the array are not identical, the calculation may cause an underflow, leading to a transaction revert. Consequently, the status will never reach completion due to the recurring transaction revert.

Tools Used

Manual Review

Recommendations

To handle the underflow scenario, add a check before the subtraction in the variance function. This would ensure that the difference calculation does not cause an unintended underflow.

function variance(uint256[] memory data) internal pure returns (uint256 ans, uint256 mean) {
mean = avg(data);
uint256 sum = 0;
for (uint256 i = 0; i < data.length; i++) {
- uint256 diff = data[i] - mean;
+ uint256 diff = data[i] > mean? data[i] - mean:mean - data[i];
sum += diff * diff;
}
ans = sum / data.length;
}
​
Updates

Lead Judging Commences

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

Underflow in computing variance

Support

FAQs

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