霍夫曼编码（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 here
key = GetNextKey(key, len);
}
}

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