霍夫曼編碼（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);}}因此，如果攻擊者能夠構造出一個非法的霍夫曼表，包含了大量的長編碼，這將導致解碼器將分配過多的二級表，使得霍夫曼表的總內存大小超過分配大小，發生堆緩沖區溢出。
喜歡
討厭