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

Subtraction in `variance()` will revert due to underflow

kunhah

Summary

The function variance() in Statistics.sol subtracts the average from each number in the array but the type is uint, because of that the function will revert unless all numbers are the same

Vulnerability Details

The function variance() does a subtraction by iterating on every number on the array and subtracting by the average that was previously calculated

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;
}

The problem is that uint does not support negative values, because of that all subtractions that result in a negative amount will revert, and since it is the average of the numbers in the array, it will revert if the average is bigger than one of the numbers of the array, because of that, the only case it will not revert is if all numbers in the array are equal, and that is unlikely to happen.

Impact

This function is called in the finalizeValidation() function, which is called in the end of the validate() function, because of that, almost all calls to validate() will revert, for this reason I believe it is a high.

Proof of code

Install foundry, create a file in a subfolder in the test folder, and paste this:

// SPDX-License-Identifier: Apache-2.0
pragma solidity ^0.8.20;
​
import { Test } from "../../lib/forge-std/src/Test.sol";
import { console } from "../../lib/forge-std/src/console.sol";
​
contract Statistics {
​
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;
}
​
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;
}
​
function stddev(uint256[] memory data) internal pure returns (uint256 ans, uint256 mean) {
(uint256 _variance, uint256 _mean) = variance(data);
mean = _mean;
ans = sqrt(_variance);
}
​
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 TestLib is Test, Statistics {
​
function test_testAvg(uint256 number1, uint256 number2, uint256 number3, uint256 number4, uint256 number5) public {
uint256[] memory data = new uint256[]();
data[0] = number1 % 1e50;
data[1] = number2 % 1e50;
data[2] = number3 % 1e50;
data[3] = number4 % 1e50;
data[4] = number5 % 1e50;
require(number1 != number2, "test_testAvg: numbers must be different");
uint256 ans = avg(data);
//console.log(ans);
}
​
function test_testStddev(uint256 number1, uint256 number2, uint256 number3, uint256 number4, uint256 number5) public {
uint256[] memory data = new uint256[]();
data[0] = number1 % 1e50;
data[1] = number2 % 1e50;
data[2] = number3 % 1e50;
data[3] = number4 % 1e50;
data[4] = number5 % 1e50;
require(number1 != number2, "test_testStddev: numbers must be different");
vm.expectRevert();
(uint256 ans, uint256 mean) = stddev(data);
}
​
function test_testSqrt() public {
uint256 x = 16;
uint256 ans = sqrt(x);
//console.log(ans);
}
​
function test_testVariance(uint256 number1, uint256 number2, uint256 number3, uint256 number4, uint256 number5) public {
uint256[] memory data = new uint256[]();
data[0] = number1 % 1e50;
data[1] = number2 % 1e50;
data[2] = number3 % 1e50;
data[3] = number4 % 1e50;
data[4] = number5 % 1e50;
require(number1 != number2, "test_testVariance: numbers must be different");
vm.expectRevert();
(uint256 ans, uint256 mean) = variance(data);
}
}

All calls to stddev() and variance() will revert as expected. The 1e50 limit is to avoid overflows that will fail the test.

Tools Used

Foundry

Recommendations

Cast to int256 when calculating, the multiplication by itself will make the number always positive afterwards:

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;
+ int256 diff = int256(data[i]) - int256(mean);
- sum += diff * diff;
+ sum += uint256(diff * diff);
}
ans = sum / data.length;
}
Updates

Lead Judging Commences

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