December 16, 2011

An Infinite Loop Bug

In this entry, I'm describing an infinite loop bug caused by integer overflow. The bug involves data stream and erroneous algorithm.

Data stream looks like below.

[size][data] [size][data] ... [size][data]

The stream consists of records. The record consists of the size field followed by the data field.

The problem lies when the algorithm calculates the offset of record like below.

Offset of data plus size. The result of this operation could lead to overflow. If this fields are not properly sanitized, and the result points to previous record, the previous records will be processed again, and again...

I observed that multiple high-profile applications have this weakness during processing similar data structures could lead application hang.

It is possible to detect this algorithm weakness by code review but you certainly have an eye on what you are reviewing.

It is unlikely to detect this weakness by fuzz testing because the result of the overflow must point to previous record. If size is at least 32-bit wide you have a tiny chance to hit any exact result that would point to previous record.

I also call this kind of problem as stream hijacking.
  This blog is written and maintained by Attila Suszter. Read in Feed Reader.