WebP开源库漏洞影响深远 测试显示微信/钉钉/QQ等多款软件都面临风险 – 蓝点网

霍夫曼编码（Huffman Coding），是一种用于无损数据压缩的熵编码（权编码）算法。

在计算机资料处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码。

变长编码表通过一种评估来源符号出现概率的方法得到，出现概率高的字母使用较短的编码，反之出现概率低的则使用较长的编码。

这可以使编码后的字符串平均长度、期望值降低，从而达到无损压缩数据的目的。

根据范式霍夫曼算法，在构建一个霍夫曼表时，首先会使用一级表，用于查询长度小于 N bit (N 默认为 8) 的霍夫曼编码；随后，若出现了长度超过 N bit 的编码，解码器会为其分配二级表，用于查询超过 N bit 的编码部分。在分配霍夫曼编码表的内存空间时，解码器提前会将所有一级表和二级表的空间一并分配出来，其内存大小是固定的：

#define FIXED_TABLE_SIZE (630 * 3 + 410)static const uint16_t kTableSize[12] = { FIXED_TABLE_SIZE + 654,FIXED_TABLE_SIZE + 656,FIXED_TABLE_SIZE + 658,FIXED_TABLE_SIZE + 662,FIXED_TABLE_SIZE + 670,FIXED_TABLE_SIZE + 686,FIXED_TABLE_SIZE + 718,FIXED_TABLE_SIZE + 782,FIXED_TABLE_SIZE + 912,FIXED_TABLE_SIZE + 1168,FIXED_TABLE_SIZE + 1680,FIXED_TABLE_SIZE + 2704};const int table_size = kTableSize[color_cache_bits];huffman_tables = (HuffmanCode*)WebPSafeMalloc(num_htree_groups * table_size,sizeof(*huffman_tables));

问题在于，解码器默认图片中保存的霍夫曼编码表数据是合理的，因此提前计算了这一情况下能够容纳的最大内存长度。而霍夫曼编码表数据是来自不受信任源的，是可以由攻击者任意构造的，且编码器不会对这些数据进行有效性检查。

// Fill in 2nd level tables and add pointers to root table.for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH;++len, step <<= 1) { num_open <<= 1;num_nodes += num_open;num_open -= count[len];if (num_open < 0) { return 0;}if (root_table == NULL) continue;for (; count[len] > 0; --count[len]) { HuffmanCode code;if ((key & mask) != low) { table += table_size;table_bits = NextTableBitSize(count, len, root_bits);table_size = 1 << table_bits;total_size += table_size;low = key & mask;root_table[low].bits = (uint8_t)(table_bits + root_bits);root_table[low].value = (uint16_t)((table - root_table) - low);}code.bits = (uint8_t)(len - root_bits);code.value = (uint16_t)sorted[symbol++];ReplicateValue(&table[key >> root_bits], step, table_size, code); // overflow herekey = GetNextKey(key, len);}}

因此，如果攻击者能够构造出一个非法的霍夫曼表，包含了大量的长编码，这将导致解码器将分配过多的二级表，使得霍夫曼表的总内存大小超过分配大小，发生堆缓冲区溢出。