Description

In the splay_tree::prev_node_idx function, the iterator attempts to iterate down a node's left child (if it exists) while traversing up a tree. The intention is to use the && operator to check the left child _only_ if it is not a sentinel. However, the wrong node is checked, as is shown in the following code snippet:

} else if (!guarded_idx::is_sentinel(maybe_parent_left) && guarded_idx::unguard(maybe_parent_right) == current) {

Impact

Since the iteration aborts in reverse if the tree reaches a certain (still valid) state, several helper functions in dex::book related to asks will fail. This may render an asks book inoperable.

The following is the output of a PoC that has a bid book reach a problematic (still valid) state. An ask is then attempted. The unit test passes if guarded_idx::unguard aborts with the EINVALID_ARGUMENT abort code.

Running Move unit tests
[debug] (&) Making a bid at price level 5000
[debug] (&) Making a bid at price level 4000
[debug] (&) Making a bid at price level 3000
[debug] (&) Making a bid at price level 2000
[debug] (&) Making a bid at price level 1000
[debug] (&) Making a bid at price level 6000
[debug] (&) Attempting to make an ask at price level 1000
[ PASS    ] 0xd::book::test_invalid_ask_book

Based on splay_tree::prev_node_idx, it appears this bug is triggered when the reverse iterator tries to traverse to the left. In the previous example the tree is as follows: 1000 is the root, 2000 is the right child of 1000, 2000 is the right child of 1000, 3000 is the right child of 2000, 4000 is the right child of 3000, and 6000 is the right child of 4000. Finally, 5000 is the left child of 6000. Note that this is a valid state for a binary tree.

When traversing this tree, the loop in the else block of splay_tree::prev_node_idx first reaches 6000. Since 6000 has no right child, it attempts to access the left child but instead unguards the (sentinel) right child of 6000, causing the function to abort.

We have provided the PoC to Laminar for reproduction and remediation.

Recommendations

Change the affected line to

} else if (!guarded_idx::is_sentinel(maybe_parent_left) && guarded_idx::unguard(maybe_parent_left) == current) {

Remediation

Laminar acknowledged this finding and implemented a fix in commit 1566↗