This is demo is an example of variant analysis on a recent bugfix in libjpeg-turbo, an open-source image processing library.

The fix prevents an out-of-bounds access when processing malformed BMP files: when reading a BMP file, the library allocates a colour map based on the number of colours declared in the BMP header. Later on, individual bytes are read from the file and used as indices into this colour map. Previously, this was done without checking whether the byte actually represented a valid colour, which could cause an out-of-bounds access. The fix introduces a field in the same struct as the colour map that records its size, and checks the index against it, aborting with an error if the index is out of range.

A snapshot of libjpeg-turbo from before the fix is here, and one that contains the fix is here.

The first five QL files develop a query that flags exactly the fixed accesses on the former snapshot, and nothing on the latter; the last query is a generalisation that finds a new instance of the same problem. All queries are run on the fixed snapshot, except when stated otherwise.

• 01_find_colormap_index.ql: A simple query to get started; flags all expressions of the form base->colormap[i][j].
• 02a_find_guarded_colormap_index.ql: Refines the previous query to only flag indices into _bmp_source_struct::colormap, and among those only the ones that are guarded by a comparison against _bmp_source_struct::cmap_length. Uses global value numbering to correlate the references to colormap and cmap_length to make sure they are on the same base object, and the guards library to reason about guarding.
• 02b_find_guarded_colormap_index_working.ql: The previous query doesn't actually work, since ERREXIT isn't recognised as being a non-returning macro. This query fixes that.
• 03_find_unguarded_colormap_index.ql: Flipping the logic around, we now look for unguarded indexing. This gives a few false positives in cases where cmap_length isn't used. There is still a guard in these cases, but it's against a parameter that happens to contain the size of the colour map.
• 04_find_unguarded_colormap_no_fps.ql: Add inter-procedural tracking to reason about the flow of colour maps and their sizes. This eliminates the remaining FPs on the fixed snapshot, and gives the expected results on the original snapshot.
• 05_find_unguarded_colormap_generalised.ql: By removing the hardcoded references to _bmp_source_struct, we get a more general query that looks for other unguarded indexes into colour maps. This gives yet more false positives, since there are a few other guarding patterns, but the first three results are actually true positives, which we reported. A snapshot with these results fixed is available here.

Note that the final query is somewhat non-trivial (>100 LoC, uses global value numbering, guards and inter-procedural flow), so it's perhaps best used with an audience that has seen some simple QL before.