MaxHeap.sol: Already extracted tokenId may be extracted again.

[c4-bot-5]

Lines of code

https://github.com/code-423n4/2023-12-revolutionprotocol/blob/main/packages/revolution/src/MaxHeap.sol#L102 https://github.com/code-423n4/2023-12-revolutionprotocol/blob/main/packages/revolution/src/MaxHeap.sol#L156

Vulnerability details

Impact

MaxHeap.sol#extractMax function only decreases the size variable without initializing the heap state variable. On the other hand, MaxHeap.sol#maxHeapify function involves the heap variable for the out-of-bound index which will contain dirty non-zero value. As a result, uncleared dirty value of heap state variable will be used in the process and already extracted tokenId will be extracted again.

Proof of Concept

MaxHeap.sol#extractMax function is following.

File: MaxHeap.sol
156:     function extractMax() external onlyAdmin returns (uint256, uint256) {
157:         require(size > 0, "Heap is empty");
158: 
159:         uint256 popped = heap[0];
160:         heap[0] = heap[--size];
161:         maxHeapify(0);
162: 
163:         return (popped, valueMapping[popped]);
164:     }

As can be seen, the above funcion decreases size state variable by one, but does not initialize the heap[size] value to zero. In the meantime,MaxHeap.sol#maxHeapify function is following.

File: MaxHeap.sol
094:     function maxHeapify(uint256 pos) internal {
095:         uint256 left = 2 * pos + 1;
096:         uint256 right = 2 * pos + 2;
097: 
098:         uint256 posValue = valueMapping[heap[pos]];
099:         uint256 leftValue = valueMapping[heap[left]];
100:         uint256 rightValue = valueMapping[heap[right]];
101: 
102:         if (pos >= (size / 2) && pos <= size) return;
103: 
104:         if (posValue < leftValue || posValue < rightValue) {
105:             if (leftValue > rightValue) {
106:                 swap(pos, left);
107:                 maxHeapify(left);
108:             } else {
109:                 swap(pos, right);
110:                 maxHeapify(right);
111:             }
112:         }
113:     }

For example, if size=2 and pos=0, right = 2 = size holds true. So the heap[right]=heap[size] indicates the value of out-of-bound index which may be not initialized in extractMax function ahead. But in L102 since pos = 0 < (size / 2) = 1 holds true, the function does not return and continue to proceed the below section of function. Thus, abnormal phenomena occurs due to the value that should not be used.

We can verify the above issue by adding and running the following test code to test/max-heap/Updates.t.sol.

    function testExtractUpdateError() public {
        // Insert 3 items with value 20 and remove them all
        maxHeapTester.insert(1, 20);
        maxHeapTester.insert(2, 20);
        maxHeapTester.insert(3, 20);

        maxHeapTester.extractMax();
        maxHeapTester.extractMax();
        maxHeapTester.extractMax(); // Because all of 3 items are removed, itemId=1,2,3 should never be extracted after.

        // Insert 2 items with value 10 which is small than 20
        maxHeapTester.insert(4, 10);
        maxHeapTester.insert(5, 10);
        // Update value to cause maxHeapify
        maxHeapTester.updateValue(4, 5);

        // Now the item should be itemId=5, value=10
        // But in fact the max item is itemId=3, value=20 now.
        (uint256 itemId, uint256 value) = maxHeapTester.extractMax(); // itemId=3 will be extracted again

        require(itemId == 5, "Item ID should be 5 but 3 now");
        require(value == 10, "value should be 10 but 20 now");
    }

As a result of test code, the return value of the last extractMax call is not (itemId, value) = (5, 10) but (itemId, value) = (3, 20) which is error. According to READM.md#L313, the above result must not be forbidden.

Tools Used

Manual Review

Recommended Mitigation Steps

Modify the MaxHeap.sol#extractMax function as follows.

    function extractMax() external onlyAdmin returns (uint256, uint256) {
        require(size > 0, "Heap is empty");

        uint256 popped = heap[0];
        heap[0] = heap[--size];
 ++     heap[size] = 0;
        maxHeapify(0);

        return (popped, valueMapping[popped]);
    }

Since the value of heap[size] is initialized to zero, no errors will occur even though the value of out-of-bound index is used in maxHeapify function.

Assessed type

Math

[c4-pre-sort]

raymondfam marked the issue as insufficient quality report

[c4-pre-sort]

raymondfam marked the issue as sufficient quality report

[c4-pre-sort]

raymondfam marked the issue as primary issue

[raymondfam]

Duplicated submissions come with various POC, but the root cause is the same.

[rocketman-21]

yea this is duplicated from another, but confirmed an issue

[c4-sponsor]

rocketman-21 (sponsor) disputed

[c4-sponsor]

rocketman-21 (sponsor) confirmed

[rocketman-21]

think this should be medium, it requires that we make the values of the maxheap less than they were inserted at, which isn't possible in CultureIndex (which is upvote only)

[c4-sponsor]

rocketman-21 marked the issue as disagree with severity

[MarioPoneder]

This is a tough one. First of all I genuinely appreciate the efforts put into this report and many of its duplicates, clearly an underlying bug is shown.
However, no impacts on the function of protocol as a whole are shown. Therefore, it's hard to justify High/Medium severity for this group of findings.
I have to downgrade to QA for now, but invite the author of this submission or its duplicates to provide a runnable PoC during PJQA which shows impacts through the main entry points of the protocol, i.e. not purely interacting with the MaxHeap contract.

Thank you for your understanding!

[c4-judge]

MarioPoneder changed the severity to QA (Quality Assurance)

[c4-judge]

MarioPoneder marked the issue as grade-a

[mcgrathcoutinho]

Hi @MarioPoneder, here is why I believe this issue should be a valid Medium.

1. The MaxHeap.sol contract is expected to implement its full spec (as confirmed by sponsor here). The issue clearly demonstrates the spec non-conformity.
2. The MaxHeap.sol contract is a data structure which cannot change due to existing past data and ongoing current piece data. This means that if downvoting is introduced in the future version (by upgrading CultureIndex.sol i.e. changing the admin of MaxHeap.sol), the max heap tree would function incorrectly. This would mean that the team would not be able to add downvoting as a feature even if they want to (as stated by sponsor here and in the above link).

Thank you for taking the time to read this.

[NicolaMirchev]

Hello @MarioPoneder,

I'd like to explain why I think this issue should be considered a valid concern.

1. The MaxHeap.sol contract is expected to adhere to its full specification, as confirmed by the sponsor. However, this issue clearly highlights a deviation from the specified behavior.

2. MaxHeap.sol serves as a critical data structure that should remain consistent over time, considering both historical data and ongoing data interactions. If a future version introduces downvoting (possibly by upgrading CultureIndex.sol and changing the admin of MaxHeap.sol), the Max Heap tree could malfunction. This means that even if the team intends to add downvoting as a feature, as mentioned by the sponsor in the provided link, it would be impossible due to this discrepancy. It's essential to emphasize the seriousness of this bug because the data structure should consistently adhere to its standard behavior within its context. Furthermore, as this contract falls within the scope of our responsibilities as auditors, neglecting this issue now may result in MaxHeap.sol being excluded from potential audits in the future. This exclusion could occur because there haven't been any changes, even though a critical bug exists at its core.

3. Additionally, it's crucial for us to address this issue promptly. Neglecting it at this stage may lead to MaxHeap.sol being omitted from future audits, despite the presence of a critical bug at its core. This omission could happen because there are no planned changes to the file, even though a significant issue persists.

4. Furthermore, it's worth noting that the sponsor is aware of this issue and is likely to address it. As a result, future updates may not introduce bugs with root in audited code, and there's a possibility that this contract could be excluded from the scope of future audits. This finding is valuable as it not only saves funds for the client in terms of potential audits for upcoming updates but also eliminates a potential source of critical impact.

Thank you for your time and consideration.

[MarioPoneder]

Thank you for your comments!

As I agree with many of your points there is an even simpler logic behind upgrading this. I judged this contest with a strict baseline for Medium severity findings. However, I was "forced" to accept a view-only ERC-721 violation as valid Medium due to historical precedence on C4. As the present issue is similarly deviating from spec without severe impacts on the functionality of the protocol at its current state, it seems fair and consistent to move forward with Medium severity and therefore appropriately value the effort behind uncovering this very valid bug.

[c4-judge]

This previously downgraded issue has been upgraded by MarioPoneder

[c4-judge]

MarioPoneder marked the issue as satisfactory

[c4-judge]

MarioPoneder marked the issue as selected for report

[bart1e]

@MarioPoneder I would like to add several comments to this discussion:

1. I believe that #41 (and possible its duplicates) is a duplicate as it shares the same root cause (accessing index of of bounds). Both will only be exploitable if downvoting mechanism is introduced in the future as @mcgrathcoutinho correctly pointed out.
2. By the way, I think that the recommended fix is incorrect both here and in the majority of duplicated issues as resetting heap[size] to 0 doesn’t help as there can be an NFT with index 0 and hence valueMapping[0] may not be equal to 0. This doesn’t invalidate these submissions, of course, but I think that the Sponsors should be aware of it.

[MarioPoneder]

Thank you for your comment!

What you wrote aligns with what I've discussed with the sponsor, therefore it is appropriate to duplicate the mentioned group of findings.