AsArrays Manual Review Findings

AAS-01M: Incorrect EVM Memory Assumptions

Type	Severity	Location
Logical Fault		AsArrays.sol:L80-L89, L96-L106, L112-L121

Description:

The AsArrays::ref, AsArrays::unref, and thereby AsArrays::slice (for the uint256[] data type) are invalid implementations as they do not conform to the intricacies of the EVM's memory space.

Specifically, the AsArrays::slice function incorrectly assumes that an array pointer can be transformed to a new array by shifting the pointer's value in 32 byte increments per the elements the user wishes to skip. This is incorrect, as a valid array pointer will contain the array's length in the first 32 byte slot and the elements after it, meaning that shifting the pointer will result in an array that has a length equal to the begin - 1 element.

In turn, this will cause the data := ptr assignment in AsArrays::unref to produce an array with length equal to self[begin - 1] containing all entries that fit within that length as well as corrupt memory data due to an "overflow" of the allocated memory as a result of the overwritten array length should it exceed the initial size.

On the other hand, the AsArrays::unref function will instantiate a data pointer with an array with a specified size, however, the size will be overwritten by the ensuing assignment. This means that whatever the expected size, the resulting data array will use the aforementioned self[begin - 1] entry (or the actual size, if begin is 0) as the length and the local declaration will be immediately discarded.

As a final note, the AsArrays::testRefUnref function is an ineffective test as it will not mutate the length of the array nor will it skip any elements in which case the malfunctions we described do not surface.

Impact:

Any AsArrays::slice operation will either result in corrupted data or transaction failure, either of which can be considered of significant severity.

Example:

Copy
80/**
81 * @notice Returns a reference to the array
82 * @param data array to be referenced
83 * @return ptr reference of the array
84 */
85function ref(uint256[] memory data) internal pure returns (uint ptr) {
86    assembly {
87        ptr := data
88    }
89}
90
91/**
92 * @notice Returns dereferrenced array (slice) starting at ptr and containing size elements
93 * @param ptr reference of the array
94 * @return array of given size
95 */
96function unref(uint256 ptr, uint256 size) internal pure returns (uint256[] memory) {
97    uint256[] memory data = new uint256[](size);
98    assembly {
99        data := ptr
100        // safer:
101        // for { let i := 0 } lt(i, size) { i := add(i, 1) } {
102        //     mstore(add(data, add(0x20, mul(i, 0x20))), mload(add(ptr, mul(i, 0x20))))
103        // }
104    }
105    return data;
106}
107
108/**
109 * @notice Used to test memory pointers on the current evm
110 * @return true - memory ok, false - memory error
111 */
112function testRefUnref() internal pure returns (bool) {
113    uint256[] memory dt = new uint256[](3);
114    for (uint i = 0; i < dt.length; i++) {
115        dt[i] = i;
116    }
117    uint256 wptr = ref(dt);
118    uint256[] memory data;
119    data = unref(wptr, 3);
120    return data.length == 3 && data[0] == 0 && data[1] == 1 && data[2] == 2;
121}
122
123/**
124 * @notice Returns a slice of the array
125 * @param self Storage array containing uint256 type variables
126 * @param begin Index of the first element to include in the slice
127 * @param end Index of the last element to include in the slice
128 * @return slice of the array
129 */
130function slice(uint256[] memory self, uint256 begin, uint256 end) internal pure returns (uint256[] memory) {
131    require(begin < end && end <= self.length);
132    return unref(ref(self) + begin * 0x20, end - begin);
133}

Recommendation:

We advise the overall approach to efficient array slicing to be revised as it is presently incorrect, causes data corruptions as well as potential unhandled errors.

To note, slices of in-memory arrays can already be acquired using the slice syntax (i.e. arr[a:b]) for calldata arrays and could be a viable replacement to a custom slice implementation.

Alleviation (59b75fbee1):

The codebase was refactored with the AsArrays::unref implementation removed and the AsArrays::slice implementation revised, however, the AsArrays::slice implementation remains incorrect.

Specifically, it will copy less than the actual elements it is meant to due to calculating the end pointer as add(src, length) instead of add(src, mul(length, 0x20)) thus causing the ensuing for loop to terminate early.

In turn, this will lead to the array incorrectly yielding zeroed out entries instead of failing. We advise the end pointer to be updated properly so as to fully alleviate this exhibit.

As a final note, both AsArrays::slice implementations incorrectly calculate the end pointer until which the iteration should run.

Alleviation (efbeab6478):

The Astrolab DAO team evaluated the follow-up alleviation chapter of this exhibit and opted to omit the functions from the contract entirely, rendering this exhibit alleviated by omission.

AAS-02M: Incorrect Usage of Memory

Type	Severity	Location
Language Specific		AsArrays.sol:L24, L43, L64

Description:

The referenced statements will write to the 0x60 memory pointer which is meant to represent the initial value of dynamic memory arrays, thereby corrupting all future array instantiations.

Impact:

Any invocation of the AsArrays::sum, AsArrays::max, or AsArrays::min functions will cause future array instantiations to be corrupted.

Example:

Copy
36/**
37 * @notice Returns the max value in an array.
38 * @param self Storage array containing uint256 type variables
39 * @return value The highest value in the array
40 */
41function max(uint256[] storage self) public view returns (uint256 value) {
42    assembly {
43        mstore(0x60, self.slot)
44        value := sload(keccak256(0x60, 0x20))
45
46        for {
47            let i := 0
48        } lt(i, sload(self.slot)) {
49            i := add(i, 1)
50        } {
51            switch gt(sload(add(keccak256(0x60, 0x20), i)), value)
52            case 1 {
53                value := sload(add(keccak256(0x60, 0x20), i))
54            }
55        }
56    }
57}

Recommendation:

We advise the code to utilize the self.slot directly or to properly reserve memory using the free memory pointer at 0x80.

Alleviation (59b75fbee1):

The code was updated to load the free memory pointer at 0x40, however, the actual free memory pointer is not updated after its memory has been utilized which is incorrect.

For more details on how to securely utilize the free memory pointer, kindly consult the relevant Solidity documentation resource.

Alleviation (efbeab6478):

The free memory pointer is updated correctly in all relevant instances, and is updated twice redundantly in the AsArrays::sum function.

As the original issue has been alleviated properly, we consider this exhibit addressed despite the inefficiency described.