In several places we do this kind of thing, building up an array of N items using N reallocations:


for (i = 0; remaining > 0; i++) {
     r->count++;
     r->x = talloc_realloc(ndr->current_mem_ctx,
                           r->x,
                           struct whatever, 
                           r->count);
     if (r->x == NULL) {
         return NDR_ERR_UNHAPPY;
     }

     NDR_CHECK(ndr_pull_whatever(ndr,
                                 NDR_SCALARS,
                                 &r->x[i]));

     remaining = ndr->data_size - ndr->offset;
}


When ndr->data_size is big, there will be a lot of reallocs, and the overall effect is quadratic with respect to the data_size, given O(n) memmoves of O(n) items.

In practice, in normal non-malicious traffic, this is insignificant. But fuzzers have a knack of creating packets that take multiple seconds or minutes to parse.

The obvious fix is to allocate more than one item at a time, keeping count of the extra space using another variable. For example 9148f38c203c3481a43ef6d39ea9313dfa1c1bea (fixed in bf16cd72b285662bcb4367cd2bdd6eac7655254f!) uses gentle exponential growth.

BUT while the effect is drastic in the fuzzer (particularly in oss-fuzz), it is hugely exaggerated the overhead of (I think) address sanitiser, which carefully nitpicks every talloc_realloc. I have seen an example that timed out at 60 seconds with address sanitiser take < 2 seconds without it.

This bug is here to point to and from oss-fuzz timeout bugs to remind us of the probable cause and a fix, and to remind us the probably aren't as drastic as they first look, once address sanitiser is turned off.