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