Suricata

During fuzzing, an underflow was discovered in ip defragmentation algorithm for the first fragment.

        Frag key = {
            .offset = frag_offset - 1,
        };
        next = RB_NFIND(IP_FRAGMENTS, &tracker->fragment_tree, &key);
        if (next == NULL) {
            prev = RB_MIN(IP_FRAGMENTS, &tracker->fragment_tree);
            next = IP_FRAGMENTS_RB_NEXT(prev);
        } else {
            prev = IP_FRAGMENTS_RB_PREV(next);
            if (prev == NULL) {
                prev = next;
                next = IP_FRAGMENTS_RB_NEXT(prev);
            }
        }

Due to underflow for first fragment search key becomes invalid and thus leads to execution of extra code to find first possible neighbor.

The problem with this code is why actually fragment offset is decreased by one?

By definition RB_NFIND perform inclusive search:
/* Finds the node with the same key as elm */ \
attr struct type * \
name##_RB_FIND(struct name *head, struct type *elm) \

Therefore, searching for an overlapping element that has the same offset as the inserted fragment should lead to the same result as without it.

If the intention is to find fragment that is right before current inserted fragments then there's no point of decreasing just by one, since all fragment offsets are multiples of 8.

Additionally, it’s unclear how the algorithm handles scenarios in which the last fragment arrives while at least three prior fragments with smaller offsets exist, one of which overlaps with the current fragment.

According to algorithm it picks the first two ignoring the one actually overlapping, until all fragments before it will be processed. So this has to be a performance loss.