After some more reading, I concluded that authors did think about this possibili...

After some more reading, I concluded that authors did think about this possibility but wrote a wrong code.

I have mentioned that there was the hard-coded maximum number of entries. This is derived from zlib's enough.c [1], which determines the maximum possible size of 2-level table for given number of symbols, N and the maximum allowed bit length (here 15). I've verified that those numbers indeed come from this program:

    for ((color_cache_size = 0; color_cache_size < 12; ++color_cache_size)); do
        # Note that color_cache_size = 0 entirely disables the color cache, so no symbols
        ./enough $((256 + 24 + (($color_cache_size > 0) << $color_cache_size))) 8 15
    done

So at the worst case, there are 256 + 24 + 2^11 = 2328 symbols possible, and the maximum table size is 2704. (Caveat: I couldn't verify values for color_cache_size >= 8 with the current version of enough.c. Probably the value was calculated with an alternative implementation using bigints.) So this bug cannot be found if any randomly constructed Huffman tree was thrown!

But enough.c states that it covers "all possible valid and complete prefix codes". In the other words it assumes that the Huffman tree has been already verified to be correct. If it's not the case, it is very easy to make much worse cases. For example `enough.c 280 8 15` returns 654, which is possible with the following tree:

    Len  Code range                            #         Root entry         Overhead  #
    ---  ------------------------------------  ---       -----------------  --------  ---
    1    0                                     1         0xxxxxxx           0         128
    9    10000000:0 .. 11110110:1              238       10000000-11110110  2^1       119
         11110111:0                            1         11110111           2^2       1
    10   11110111:10 .. 11110111:11            2
         11111000:00 .. 11111110:11            28        11111000-11111110  2^2       7
         11111111:00 .. 11111111:10            3         11111111           2^7       1
    11   11111111:110                          1
    12   11111111:1110                         1
    13   11111111:11110                        1
    15   11111111:1111100 .. 11111111:1111111  4

But the following partial tree should be able to reach 768 entries:

    Len  Code range                            #         Root entry         Overhead  #
    ---  ------------------------------------  ---       -----------------  --------  ---
    9    00000000:0                            1         00000000           2^7       1
    10   00000000:10                           1
    11   00000000:110                          1
    12   00000000:1110                         1
    13   00000000:11110                        1
    14   00000000:111110                       1
    15   00000000:1111110 .. 00000000:1111111  2
         00000001:0000000 .. 00000010:1111111  256       00000001-00000010  2^7       2
         00000011:0000000 .. 00000011:0001111  1         00000011           2^7       1

So the real issue here is that the lack of tree validation before the tree construction, I believe. I'm surprised that this check was not yet implemented (I actually checked libwebp to make sure that I wasn't missing one). Given this blind spot, an automated test based on the domain knowledge is likely useless to catch this bug.

[1] https://github.com/madler/zlib/blob/master/examples/enough.c