Description

queue::remove handles index_to_remove three different ways based on if it is the head, tail, or neither. In the case index_to_remove is neither, there is an assertion that ensures that the node at prev_index is actually before index_to_remove:

assert!(guarded_idx::unguard(prev_node.next) == index_to_remove, EINVALID_REMOVAL);

The same check should occur in the case that index_to_remove is the tail since the previous node is still relevant in this case:

let prev_node = vector::borrow_mut(&mut queue.nodes, *option::borrow(&prev_index));
prev_node.next = guarded_idx::sentinel();

Furthermore, queue::remove cannnot handle a queue of length one. It will set the head to the sentinel value but not the tail. The following operations will bring about this issue:

#[test]
#[expected_failure (abort_code=EQUEUE_MALFORMED)]
fun test_corrupt_queue_with_remove() {
    let queue = new<u64>();

    enqueue(&mut queue, 10);
    // The third argument is irrelevant
    remove(&mut queue, 0, option::some(4));
    enqueue(&mut queue, 1);
}

Subsequent queue operations will notice that the head is a sentinel but the tail is not, causing them to abort.

Next, in queue::has_next, there is an assertion followed by an if statement and a second assertion that will never fail:

assert!(!is_empty(queue), EQUEUE_EMPTY);

if (!is_empty(queue) && guarded_idx::is_sentinel(iter.current)) {
...
} else {
    assert!(!guarded_idx::is_sentinel(iter.current), EITERATOR_DONE);
...
}

The first term of the boolean expression will always evaluate to true and the assert in the else block will never abort. Therefore they are unecessary to add from a gas perspective.

Impact

Each of the points has the potential to corrupt the queue. However, the impact is more limited since book::move is less likely to use the queue in unintended ways.

Recommendations

Modify the implementation of the queue operations described to fix the issues.

• For the first issue, add the assertion to the else if block.

• For the second issue, a queue of length one should be handled as a special case and the queue object should be cleared.

• For the third issue, remove the first term of the boolean expression in the if statement. Also, remove the first assert in the else block.

Remediation

Laminar acknowledged this finding and implemented a fix in commits 0ceb↗, d1aa↗ and 7e01↗.