霍夫曼編碼（Huffman Coding），是一種用于無(wú)損數(shù)據(jù)壓縮的熵編碼（權(quán)編碼）算法。

在計(jì)算機(jī)資料處理中，霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)（如文件中的一個(gè)字母）進(jìn)行編碼。

變長(zhǎng)編碼表通過(guò)一種評(píng)估來(lái)源符號(hào)出現(xiàn)概率的方法得到，出現(xiàn)概率高的字母使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼。

這可以使編碼后的字符串平均長(zhǎng)度、期望值降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的。

根據(jù)范式霍夫曼算法，在構(gòu)建一個(gè)霍夫曼表時(shí)，首先會(huì)使用一級(jí)表，用于查詢長(zhǎng)度小于 N bit (N 默認(rèn)為 8) 的霍夫曼編碼；隨后，若出現(xiàn)了長(zhǎng)度超過(guò) N bit 的編碼，解碼器會(huì)為其分配二級(jí)表，用于查詢超過(guò) N bit 的編碼部分。在分配霍夫曼編碼表的內(nèi)存空間時(shí)，解碼器提前會(huì)將所有一級(jí)表和二級(jí)表的空間一并分配出來(lái)，其內(nèi)存大小是固定的：

#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));

問(wèn)題在于，解碼器默認(rèn)圖片中保存的霍夫曼編碼表數(shù)據(jù)是合理的，因此提前計(jì)算了這一情況下能夠容納的最大內(nèi)存長(zhǎng)度。而霍夫曼編碼表數(shù)據(jù)是來(lái)自不受信任源的，是可以由攻擊者任意構(gòu)造的，且編碼器不會(huì)對(duì)這些數(shù)據(jù)進(jìn)行有效性檢查。

// 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);}}

因此，如果攻擊者能夠構(gòu)造出一個(gè)非法的霍夫曼表，包含了大量的長(zhǎng)編碼，這將導(dǎo)致解碼器將分配過(guò)多的二級(jí)表，使得霍夫曼表的總內(nèi)存大小超過(guò)分配大小，發(fā)生堆緩沖區(qū)溢出。