Gas bomb on large arrays of orders

[code423n4]

Lines of code

https://github.com/code-423n4/2022-06-infinity/blob/main/contracts/core/InfinityOrderBookComplication.sol#L232 https://github.com/code-423n4/2022-06-infinity/blob/main/contracts/core/InfinityOrderBookComplication.sol#L278

Vulnerability details

Impact

In doItemsIntersect, it checks two orders that should have the same NFT address, and calls doTokenIdsIntersect to check if tokenIds intersect. Deeply nested loop may cause gas bomb if a user want to specify large NFT and large ids. A victim will get gas bomb and be unable to fulfill orders.

Proof of Concept

In doItemsIntersect, it use nested loop to check two orders: https://github.com/code-423n4/2022-06-infinity/blob/main/contracts/core/InfinityOrderBookComplication.sol#L232

Then it call doTokenIdsIntersect to check if tokenIds intersect: https://github.com/code-423n4/2022-06-infinity/blob/main/contracts/core/InfinityOrderBookComplication.sol#L278

If Alice want collection A but she doesn't want id 1000:

[
    {collection: A, tokens: [1 ~ 999, 1001 ~ 5000]},
    {collection: B, tokens: [xxx]},  # other collections
    ...,  # other collections
]

and Bob also have and order with large items array:

[
    ...,  # other collections
    {collection: A, tokens: [1 ~ 4000, 4100 ~ 5000]},
    ...,  # other collections
]

This scenario will cause gas bomb.

Tools Used

None

Recommended Mitigation Steps

Consider using a merkle tree or set to match ids.

[nneverlander]

Assessment low. No fix provided. UI is assumed to prevent scenarios like this.

[HardlyDifficult]

This seems like a reasonable improvement suggestion. But the issue as described doesn't put assets at risk. Lowering and merging with the warden's QA report #232