Chrome: Heap buffer overflow in WebP
The original commit in question: <a href="https:&#x2F;&#x2F;github.com&#x2F;webmproject&#x2F;libwebp&#x2F;commit&#x2F;f75dfbf23d1df1be52350b1a6fc5cfa6c2194499">https:&#x2F;&#x2F;github.com&#x2F;webmproject&#x2F;libwebp&#x2F;commit&#x2F;f75dfbf23d1df1...</a><p>The commit that fixes this bug: <a href="https:&#x2F;&#x2F;github.com&#x2F;webmproject&#x2F;libwebp&#x2F;commit&#x2F;902bc9190331343b2017211debcec8d2ab87e17a">https:&#x2F;&#x2F;github.com&#x2F;webmproject&#x2F;libwebp&#x2F;commit&#x2F;902bc919033134...</a><p>The original commit optimizes a Huffman decoder. The decoder uses a well-known optimization: it reads N bits in advance and determines how many bits have to be actually consumed and which symbol should be decoded, or, if it&#x27;s an N-bit prefix of multiple symbols, which table should be consulted for remaining bits.<p>The old version did use lookup tables for short symbols, but longer symbols needed a graph traversal. The new version improved this by using an array of lookup tables. Each entry contains (nbits, value) where `nbits` is # bits to be consumed and `value` is normally a symbol, but if `nbits` exceeds N `value` is interpreted as a table index and `nbits` is reinterpreted as the <i>longest</i> code length in that subtree. So each subsequent table should have `2^(nbits - N)` entries (the root table is always fixed to 2^N entries).<p>The new version calculated the maximum number of entries based on the number of symbols (kTableSize). Of course, the Huffman tree comes from an untrusted source and you can easily imagine the case where `nbits` is very big. VP8 Lossless specifically allows up to 15 bits, so the largest possible table has 2^N + 2^15 entries when every single LUT is mapped to its own secondary table, and doing this doesn&#x27;t need that many symbols (you only need 16-N symbols for each table). Amusingly enough the code itself had a mode where only the table size is calculated (VP8LBuildHuffmanTable called with `root_table == NULL`), but it wasn&#x27;t somehow unused and the fixed maximum size was assumed. So if the Huffman tree was crafted in the way that maximizes the number of entries, it will overflow the allocation.<p>To be fair, I can see why this happened; the Huffman decoding step is one of the most computationally intensive part of many compression format and any small improvement matters. The Huffman decoder optimization described above is well known, but the longer code case is commonly considered less important to optimize because longer code should rarely appear in general. The original commit message refuted this, and was able to be merged. I&#x27;m not even sure that a memory safe language could have prevented this; this is a rare case where you actively want to avoid the overflow check [1].<p>[1] I should note that the memory corruption occurs during the table construction, which is not a tight loop, so a partial overflow check would be very helpful. The actual fix never altered the `ReadSymbol` function at all! But the safety of the tight loop should be still justified, so the wrong justification can ruin everything.