Integer underflow in a generated function, leading to CPU-intensive loops

[pictyeye]

We are currently comparing existing several tools proposed to generate binary parsers, and we selected Nail as one of the studied tools.

Our platform includes several specifications and several samples to check the behavior and the correctness of different tools. In particular, we have a simple int-list specification, which can be seen as a list of uint32 integers.

When testing an empty file against the Nail implementation, we hit a loop that made the code hang. We tried to use several variants for the int-list specification:

• the original one:

target = {
  x many uint32
}

• we then tried to force valid files to have at least one element:

target = {
  x many1 uint32
}

• we also added a third version with a prefix field before the repeat parser combinator:

target = {
  uint8 = 'L'
  x many uint32
}

In all three cases, an empty file led to a CPU-intensive loop. In the end, we tried to debug the generated .nail.c file to find an integer underflow in the stream_check generated function:

static int stream_check(const NailStream *stream, unsigned count){ 
  printf ("size=%zd, count=%u, pos=%zd\n", stream->size, count, stream->pos); 
  if(stream->size - (count>>3) - ((stream->bit_offset + count & 7)>>3) < stream->pos) 
                return -1; 
        return 0; 
} 

Indeed, if stream->size is too small (0 in the case of an empty file), the code will substract count in bytes (here, the size of an uint32), which will lead to a huge unsigned integer. Thus, the condition will be true and the code will spin for a very long time, consuming a lot of CPU.

A way to fix this might be to check beforehand that size is greater or equal than count in bytes, but, as we looked at the generated code, it seems Nail produces a lot of potential integer under/overflows (some of them are signaled in comments).

As a side note, using compiler warnings (-Wsign-conversion, -Wcast-qual, etc.) might help discover these potential bugs in a systematic way.

Should you be interested in our test platform, do not hesitate to look at the repository where we store our experiments or drop me a mail.

[pictyeye]

Interestingly, the bug disappears when the nail.c code is compiled with -O3, as proposed in the official repository.