Excessive gas consumption, potential denial-of-service due to slow order insertion.

[c4-bot-9]

Lines of code

https://github.com/code-423n4/2024-03-dittoeth/blob/91faf46078bb6fe8ce9f55bcb717e5d2d302d22e/contracts/libraries/LibOrders.sol#L430-L462 https://github.com/code-423n4/2024-03-dittoeth/blob/91faf46078bb6fe8ce9f55bcb717e5d2d302d22e/contracts/libraries/LibOrders.sol#L448-L449

Vulnerability details

Description

getOrderId function is responsible for finding the correct position to insert an order in the orderbook when an invalid hint is provided. It takes the following inputs:

• orders: The mapping representing the orderbook.
• asset: The address of the asset being traded.
• direction: The direction to search (C.PREV for previous, C.NEXT for next).
• hintId: The ID of the hint to start the search from.
• _newPrice: The price of the order being inserted.
• orderType: The type of the order being inserted.

LibOrders.sol#getOrderId

    /**
     * @notice Helper function for finding and returning id of potential order
     *
     * @param orders the order mapping
     * @param asset The market that will be impacted
     * @param direction int direction to search (PREV, EXACT, NEXT)
     * @param hintId hint id
     * @param _newPrice price of prospective order used to find the id
     * @param orderType which OrderType to verify
     */
    function getOrderId(
        mapping(address => mapping(uint16 => STypes.Order)) storage orders,
        address asset,
        int256 direction,
        uint16 hintId,
        uint256 _newPrice,
        O orderType
    ) internal view returns (uint16 _hintId) {
        while (true) {
            uint16 nextId = orders[asset][hintId].nextId;

            if (verifyId(orders, asset, hintId, _newPrice, nextId, orderType) == C.EXACT) {
                return hintId;
            }

            if (direction == C.PREV) {
                uint16 prevId = orders[asset][hintId].prevId;
                hintId = prevId;
            } else {
                hintId = nextId;
            }
        }
    }

The function iterates through the order list, starting from the provided hintId, and compares the prices using the verifyId function. It continues searching in the specified direction (C.PREV for previous, C.NEXT for next) until it finds the correct position for the order.

Vulnerability Details

When a large number of orders with invalid hints are submitted to the system. Since the getOrderId function falls back to a full search when an invalid hint is provided, it can lead to significant gas consumption and slow down the order insertion process.

The issue lies in the unbounded iteration within the getOrderId function. The function continues to iterate through the order list until it finds the correct position, without any limit on the number of iterations or gas consumed.

The line responsible for the vulnerability is the while (true) loop in the getOrderId function, which allows for unbounded iteration.

When a large number of orders with invalid hints are submitted, the getOrderId function is triggered repeatedly, leading to excessive iteration and gas consumption. The function continues to iterate through the order list, searching for the correct position, even if the hint is far off or the order list is extensive.

I can see this behavior can significantly slow down the order insertion process and potentially lead to a denial-of-service situation, where the system becomes overwhelmed with the computational burden of processing orders with invalid hints.

Impact

The excessive gas consumption caused by orders with invalid hints can slow down or even halt the order insertion process, leading to a denial-of-service situation. This can prevent legitimate orders from being processed in a timely manner.

Proof of Concept

Scenario:

1. Attacker creates a large number of orders with invalid hints.
2. The system processes these orders and falls back to the getOrderId function for each order with an invalid hint.
3. The getOrderId function iterates through the order list without any limit, consuming a significant amount of gas.
4. The excessive gas consumption slows down the order insertion process and potentially leads to a denial-of-service situation.

Recommended Mitigation Steps

1. Limit the number of iterations:
   • Introduce a maximum limit on the number of iterations allowed in the getOrderId function.
   • If the iteration count exceeds the limit, the function should revert or return an error.

function getOrderId(
    // ... function parameters ...
) internal view returns (uint16 _hintId) {
    uint256 iterationCount = 0; <@
    uint256 maxIterations = 1000; // Adjust the limit as needed <@

    while (true) {
        // ... existing code ...

@>        iterationCount++;
@>        if (iterationCount > maxIterations) {
@>            revert("Exceeded maximum iterations");
        }
    }
}

2. Implement a gas limit:
   • Set a maximum gas limit for the getOrderId function to prevent excessive gas consumption.
   • If the gas consumed by the function exceeds the limit, it should revert or return an error.

function getOrderId(
    // ... function parameters ...
) internal view returns (uint16 _hintId) {
@>    uint256 gasLimit = 100000; // Adjust the gas limit as needed

    while (true) {
        // ... existing code ...

@>        if (gasleft() < gasLimit) {
@>            revert("Exceeded gas limit");
        }
    }
}

3. Validate hints before processing:
   • Implement a validation mechanism to check the validity of hints before passing them to the getOrderId function.
   • Reject orders with invalid hints early in the process to avoid unnecessary computation.

function addBid(address asset, STypes.Order memory order, MTypes.OrderHint[] memory orderHintArray) internal {
    // ... existing code ...

    uint16 hintId = 0;
    for (uint256 i = 0; i < orderHintArray.length; i++) {
        if (isValidHint(asset, orderHintArray[i])) {
            hintId = orderHintArray[i].hintId;
            break;
        }
    }

    if (hintId == 0) {
        revert("No valid hint found");
    }

    // ... existing code ...
}

function isValidHint(address asset, MTypes.OrderHint memory hint) internal view returns (bool) {
    // Implement hint validation logic
    // Example: Check if the hint falls within a valid price range
    // Example: Check if the hint is not too far from the current best bid/ask
    // ...
}

Assessed type

DoS

[c4-pre-sort]

raymondfam marked the issue as insufficient quality report

[c4-pre-sort]

raymondfam marked the issue as duplicate of #198

[raymondfam]

The hint system has been in place to circumvent the described issue.

[c4-judge]

hansfriese marked the issue as unsatisfactory: Invalid