Implementasi parser dekompresi Huffman tanpa validasi batas rentan terhadap serangan Denial-of-Service (DoS) melalui konsumsi memori tak terbatas (OOM) dan lonjakan utilisasi CPU (algorithmic complexity attack). Penyerang dapat menyusun payload dengan struktur pohon tak simetris, bit sequence yang mengarah ke siklus tak berujung, atau spesifikasi panjang kode ekstrem untuk mengeksploitasi parser yang naif.

Mitigasi DoS dekompresi Huffman: validasi bound prefix tree berfokus pada empat mekanisme pertahanan: pembatasan panjang kode kanonikal (canonical code lengths), batasan alokasi tabel transisi berukuran tetap, eliminasi rekursi saat tree traversal, dan pemutusan stream deterministik saat bitstream menyimpang dari tabel simbol.

1. Vektor Kerentanan pada Parsing Huffman

Pohon Huffman standar memetakan bitstream berpanjang variabel menjadi simbol berpanjang tetap. Kerentanan muncul dari tiga aspek utama implementasi parser:

  • Deep/Degenerate Tree Exploitation: Penyerang mendefinisikan kode simbol dengan kedalaman mendekati jumlah simbol (misal $N=256$ menghasilkan kedalaman 255), memicu stack overflow pada parser berbasis rekursi atau latensi traversal ekstrem.
  • Memory Exhaustion via Dynamic Allocations: Parser yang mengalokasikan node pohon berbasis pointer secara dinamis (malloc per bit node) dapat dipaksa mengalokasikan memori melebihi batas payload payload yang diizinkan saat membangun pohon parsial berulang kali.
  • Infinite Loop / Bit Sink: Bitstream yang sengaja dibuat corrupt atau tidak diterminasi menyebabkan pembacaan bit terus menerus jika parser tidak memvalidasi status leaf node terhadap akhir stream data.

2. Validasi Batas Panjang Kode Kanonikal (Canonical Bounds)

Pohon Huffman kanonikal mendefinisikan representasi bit sequence hanya berdasarkan daftar panjang bit untuk setiap simbol. Algoritma kompresi seperti DEFLATE menetapkan batas panjang kode maksimum secara ketat (misalnya 15 bit untuk kode literal/length dan 7 bit untuk kode jarak). Aturan Kraft-McMillan inequality harus dipatuhi untuk memastikan pohon valid dan lengkap:

$$\sum_{i=1}^{N} 2^{-l_i} \le 1$$

Jika jumlah total melampaui nilai 1, himpunan kode tersebut oversubscribed (ambigu). Jika kurang dari 1, himpunan kode tersebut undersubscribed (tidak lengkap), yang umumnya harus ditolak kecuali untuk kasus trivial (simbol tunggal).

3. Implementasi Lookup Table Statis dan Traversal Iteratif

Pendekatan aman menggantikan node berbasis pointer dan rekursi dengan alokasi tabel tetap di stack atau arena memori berukuran terprediksi. Contoh implementasi parser kanonikal aman dalam bahasa C berikut memvalidasi batas kode, membatasi ukuran memori tabel secara ketat, dan memproses bitstream secara iteratif.

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>

#define MAX_BITS 15
#define MAX_SYMBOLS 288
#define ERROR_INVALID_STREAM -1
#define ERROR_CORRUPT_CODE   -2

// Representasi node tabel datar; tidak ada pointer heap dinamis
typedef struct {
    uint16_t symbol;
    uint8_t  bits;
    bool     is_leaf;
} DecodeEntry;

typedef struct {
    DecodeEntry table[1 << MAX_BITS];
    uint16_t count_per_len[MAX_BITS + 1];
} HuffmanDecoder;

bool init_canonical_bounds(HuffmanDecoder *dec, const uint8_t *lens, size_t n_symbols) {
    if (n_symbols > MAX_SYMBOLS) return false;

    for (size_t i = 0; i <= MAX_BITS; i++) dec->count_per_len[i] = 0;
    for (size_t i = 0; i < n_symbols; i++) {
        if (lens[i] > MAX_BITS) return false; // Enforce canonical max depth
        dec->count_per_len[lens[i]]++;
    }

    // Validasi Kraft-McMillan inequality
    uint32_t total = 0;
    for (size_t i = 1; i <= MAX_BITS; i++) {
        total = (total << 1) + dec->count_per_len[i];
        if (total > (1U << i)) return false; // Oversubscribed tree
    }
    
    // Generate tabel lookup terindeks bit prefix langsung
    uint16_t next_code[MAX_BITS + 1];
    uint16_t code = 0;
    for (int bits = 1; bits <= MAX_BITS; bits++) {
        code = (code + dec->count_per_len[bits - 1]) << 1;
        next_code[bits] = code;
    }

    for (size_t i = 0; i < n_symbols; i++) {
        uint8_t len = lens[i];
        if (len == 0) continue;
        uint16_t c = next_code[len]++;
        dec->table[c] = (DecodeEntry){ .symbol = (uint16_t)i, .bits = len, .is_leaf = true };
    }
    return true;
}

int decode_symbol_bounded(const HuffmanDecoder *dec, const uint8_t *stream, size_t stream_bits, size_t *bit_offset) {
    uint16_t current_code = 0;
    for (uint8_t len = 1; len <= MAX_BITS; len++) {
        if (*bit_offset >= stream_bits) {
            return ERROR_INVALID_STREAM; // EOF tercapai sebelum simbol valid selesai
        }

        size_t byte_idx = (*bit_offset) / 8;
        size_t bit_idx = (*bit_offset) % 8;
        uint8_t bit = (stream[byte_idx] >> bit_idx) & 1;
        (*bit_offset)++;

        current_code = (current_code << 1) | bit;
        
        DecodeEntry entry = dec->table[current_code];
        if (entry.is_leaf && entry.bits == len) {
            return entry.symbol;
        }
    }
    // Prefix tidak terdaftar di dalam tree kanonikal
    return ERROR_CORRUPT_CODE;
}

4. Pemutusan Stream Instan (Fail-Fast Bit Processing)

Pola anti-pattern pada implementasi dekompresor adalah mencatat status kegagalan dan tetap membaca bit hingga akhir blok. Penyerang memanfaatkan loop parsing tanpa batas ini untuk menyedot siklus CPU.

Aturan Keamanan: Setiap kali bit sequence melampaui MAX_BITS tanpa menghasilkan simbol valid, stream harus dinyatakan invalid seketika. Parser wajib melepaskan konteks dekompresi tanpa memproses byte berikutnya.

Langkah deteksi instan:

  1. Periksa batas buffer masukan (bound check) sebelum setiap ekstraksi bit atau byte.
  2. Hindari transisi fallback bertingkat jika kode tidak ditemukan dalam tabel prefix tree.
  3. Segera kembalikan sinyal kegagalan ke layer transport untuk menutup koneksi atau membuang paket korup.

5. Evaluasi Trade-Off Desain

Menggunakan lookup table berukuran tetap dengan batas MAX_BITS = 15 membutuhkan memori 32768 * sizeof(DecodeEntry) (sekitar 128 KB hingga 256 KB). Ini lebih besar dibandingkan representasi pointer-tree minimal (sekitar beberapa kilobyte). Namun, pendekatan lookup table datar mencegah alokasi dinamis berulang, menghilangkan risiko heap fragmentation, dan menjamin operasi pembacaan berkecepatan konstan $O(1)$ untuk level lookahead decoding.