3 ms·

Thanks for your explanation. I’m not a C programmer over the past decade+ and was never very good at it anyway. But I was thinking, based on your description,

Thanks for your explanation. I’m not a C programmer over the past decade+ and was never very good at it anyway. But I was thinking, based on your description, I agree that a bounds check would have caught the issue, but I’m also curious if an automated test could have been constructed to catch this sort of thing. I personally work with code where you could factor out some calculations to their own function and test them in isolation. Perhaps that would be tough to do here because of performance; I am really not sure.

danielheath 3y ago
I’m quite surprised coverage-guided fuzzing didn’t find it almost immediately, to the point that I wonder if it had even been set up.
lifthrasiir 3y ago
I believe it is possible to construct a dedicated automated test, but a normal fuzzing wouldn't be very effective in this case because you need some non-trivial logic to construct a Huffman tree with very large LUT. It's like a condition like phi(input) equals to the specific number [1]; you can construct an input by hand, but fuzzers generally have no idea to approach that. I do think this was found by fuzzing, but it is entirely reasonable that fuzzers took much time to trigger the actual memory corruption. That said, this particular bug could have been avoided by a careful coding; VP8LBuildHuffmanTable could have received the maximum size of `root_table`, just like snprintf. It still would have needed much time to find but at least it could never be a security bug. [1] https://math.stackexchange.com/questions/265397/inversion-of-the-euler-totient-function https://math.stackexchange.com/questions/265397/inversion-of...
- avg_dev 3y ago
  I guess my thinking was based off of this: > 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 longest 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). Given that, wouldn't it be only natural to construct a test where nbits exceeds N, so that you exercise the code where `value` was being interpreted as an index, and `nbits` as the longest code length in that subtree? Hmm, I guess that this could have been done and perhaps was done (I took a quick glance at the code and didn't really grok it in a couple mins), and the issue would be that even if you did do what I suggest, you would likely not exceed the maximum fixed size with your crafted test, and thus not catch the bug.
  - lifthrasiir 3y ago
    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 https://github.com/madler/zlib/blob/master/examples/enough.c

danielheath 3y ago

I’m quite surprised coverage-guided fuzzing didn’t find it almost immediately, to the point that I wonder if it had even been set up.

lifthrasiir 3y ago

I believe it is possible to construct a dedicated automated test, but a normal fuzzing wouldn't be very effective in this case because you need some non-trivial logic to construct a Huffman tree with very large LUT. It's like a condition like phi(input) equals to the specific number [1]; you can construct an input by hand, but fuzzers generally have no idea to approach that. I do think this was found by fuzzing, but it is entirely reasonable that fuzzers took much time to trigger the actual memory corruption. That said, this particular bug could have been avoided by a careful coding; VP8LBuildHuffmanTable could have received the maximum size of `root_table`, just like snprintf. It still would have needed much time to find but at least it could never be a security bug. [1] https://math.stackexchange.com/questions/265397/inversion-of-the-euler-totient-function https://math.stackexchange.com/questions/265397/inversion-of...

avg_dev 3y ago
I guess my thinking was based off of this: > 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 longest 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). Given that, wouldn't it be only natural to construct a test where nbits exceeds N, so that you exercise the code where `value` was being interpreted as an index, and `nbits` as the longest code length in that subtree? Hmm, I guess that this could have been done and perhaps was done (I took a quick glance at the code and didn't really grok it in a couple mins), and the issue would be that even if you did do what I suggest, you would likely not exceed the maximum fixed size with your crafted test, and thus not catch the bug.
- lifthrasiir 3y ago
  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 https://github.com/madler/zlib/blob/master/examples/enough.c