Reachable assertion in ZSTD_rescaleFreqs (bitCost < scaleLog) when CDict built with optimal-parser strategy + tiny dictionary

[OwenSanzas]

Summary

ZSTD_rescaleFreqs() in lib/compress/zstd_opt.c contains the invariant
assert(bitCost < scaleLog) on the FSE-derived matchlength / literal-length /
offset frequency tables, with scaleLog = 10. When a caller builds a CDict
via the public API ZSTD_createCDict_advanced() from a small custom
dictionary buffer and a ZSTD_compressionParameters configuration that
selects an optimal-parser strategy (ZSTD_btopt, ZSTD_btultra, or
ZSTD_btultra2), the first compression call can reach a state where
FSE_getMaxNbBits() returns tableLog + 1 == 10 for at least one symbol
(documented as the "fake cost" path for zero-frequency symbols in
lib/common/fse.h:474). That value equals scaleLog, so the strict-less-than
assertion fires and abort() is called.

Affected version: zstd 1.6.0 / HEAD 5233c58e6ca0b1c4c6b353ad79649191ed195bdc.

PoC

Trigger file

crash_input — 446 bytes. The harness consumes 11 control bytes from the
tail of the input (flags, level, dict/source selectors, individual
ZSTD_compressionParameters fields). The remaining bytes are split into a
dictionary prefix and a source buffer. For this specific input the harness
ends up calling ZSTD_createCDict_advanced with cParams whose strategy
falls in the optimal-parser range and with a small dictionary buffer; the
first call to ZSTD_compress_usingCDict then enters ZSTD_rescaleFreqs and
aborts.

How to generate

Any test driver that exercises libzstd's public CDict API with:

• a small dictionary buffer (tens to a few hundred bytes is sufficient — the
  point is that the dictionary's encoded FSE NCount has zero-frequency
  symbols within 0..MaxML),
• ZSTD_compressionParameters with strategy in {ZSTD_btopt, ZSTD_btultra, ZSTD_btultra2} (or equivalently compressionLevel >= 19 via
  ZSTD_getCParams()),
• a non-empty source buffer to actually trigger compression.

Equivalent minimal pseudocode:

ZSTD_compressionParameters cp = ZSTD_getCParams(22 /*=btultra2 territory*/,
                                                 /*srcSize=*/ src_len,
                                                 /*dictSize=*/ dict_len);
ZSTD_CDict* cdict = ZSTD_createCDict_advanced(dict, dict_len,
                                              ZSTD_dlm_byCopy, ZSTD_dct_auto,
                                              cp, ZSTD_defaultCMem);
ZSTD_CCtx* cctx = ZSTD_createCCtx();
ZSTD_compress_usingCDict(cctx, dst, dst_cap, src, src_len, cdict);
/* aborts inside ZSTD_rescaleFreqs */

The attached crash_input is a concrete 446-byte realization of this.

---

Trigger Method 1: AGF fuzz harness (libFuzzer driver, reliable repro)

dictionary_loader.c is the harness:

#define ZSTD_STATIC_LINKING_ONLY

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

#include "zstd.h"

#define MAX_DICT_SIZE ((size_t)65536)
#define MAX_SOURCE_SIZE ((size_t)4096)
#define MAX_WINDOW_LOG 17U
#define MAX_TABLE_LOG 17U

static uint8_t readByteFromEnd(const uint8_t *data, size_t *end) {
    if (*end == 0) return 0;
    *end -= 1;
    return data[*end];
}
static unsigned read16FromEnd(const uint8_t *data, size_t *end) {
    unsigned b0 = readByteFromEnd(data, end);
    unsigned b1 = readByteFromEnd(data, end);
    return b0 | (b1 << 8);
}
static size_t minSize(size_t a, size_t b) { return a < b ? a : b; }
static unsigned boundedByte(unsigned v, unsigned lo, unsigned hi) {
    return lo + (v % (hi - lo + 1));
}

int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
    size_t end = size;
    uint8_t emptyBuffer[1] = {0};

    unsigned flags            = readByteFromEnd(data, &end);
    unsigned levelByte        = readByteFromEnd(data, &end);
    unsigned dictSelector     = read16FromEnd(data, &end);
    unsigned sourceSelector   = read16FromEnd(data, &end);
    unsigned windowLogByte    = readByteFromEnd(data, &end);
    unsigned hashLogByte      = readByteFromEnd(data, &end);
    unsigned chainLogByte     = readByteFromEnd(data, &end);
    unsigned searchLogByte    = readByteFromEnd(data, &end);
    unsigned minMatchByte     = readByteFromEnd(data, &end);
    unsigned targetLengthByte = readByteFromEnd(data, &end);
    unsigned strategyByte     = readByteFromEnd(data, &end);

    size_t payloadSize     = end;
    size_t dictLimit       = minSize(payloadSize, MAX_DICT_SIZE);
    size_t dictSize        = dictLimit == 0 ? 0 : (size_t)(dictSelector % (unsigned)(dictLimit + 1));
    size_t sourceAvailable = payloadSize - dictSize;
    size_t sourceLimit     = minSize(sourceAvailable, MAX_SOURCE_SIZE);
    size_t sourceSize      = sourceLimit == 0 ? 0 : (size_t)(sourceSelector % (unsigned)(sourceLimit + 1));

    const uint8_t *dict   = data;
    const uint8_t *source = data + dictSize;
    const void *dictPtr   = dictSize   == 0 ? (const void *)emptyBuffer : (const void *)dict;
    const void *sourcePtr = sourceSize == 0 ? (const void *)emptyBuffer : (const void *)source;

    ZSTD_dictLoadMethod_e   dictLoadMethod  = (flags & 1U) ? ZSTD_dlm_byRef : ZSTD_dlm_byCopy;
    ZSTD_dictContentType_e  dictContentType = (ZSTD_dictContentType_e)((flags >> 1) % 3U);

    ZSTD_compressionParameters cParams;
    if ((flags & 8U) != 0) {
        int compressionLevel = (int)(levelByte % 16U) - 3;
        cParams = ZSTD_getCParams(compressionLevel, (unsigned long long)sourceSize, dictSize);
    } else {
        cParams.windowLog    = boundedByte(windowLogByte,    ZSTD_WINDOWLOG_MIN, MAX_WINDOW_LOG);
        cParams.hashLog      = boundedByte(hashLogByte,      ZSTD_HASHLOG_MIN,   MAX_TABLE_LOG);
        cParams.chainLog     = boundedByte(chainLogByte,     ZSTD_CHAINLOG_MIN,  MAX_TABLE_LOG);
        cParams.searchLog    = boundedByte(searchLogByte,    ZSTD_SEARCHLOG_MIN, 6U);
        cParams.minMatch     = boundedByte(minMatchByte,     ZSTD_MINMATCH_MIN,  ZSTD_MINMATCH_MAX);
        cParams.targetLength = targetLengthByte;
        cParams.strategy     = (ZSTD_strategy)(ZSTD_fast + (strategyByte % (unsigned)(ZSTD_btultra2 - ZSTD_fast + 1)));
        cParams = ZSTD_adjustCParams(cParams, (unsigned long long)sourceSize, dictSize);
    }

    ZSTD_CDict *cdict = ZSTD_createCDict_advanced(dictPtr, dictSize,
                                                  dictLoadMethod, dictContentType,
                                                  cParams, ZSTD_defaultCMem);
    if (cdict != NULL) {
        ZSTD_CCtx *cctx = ZSTD_createCCtx();
        if (cctx != NULL) {
            size_t dstCapacity = ZSTD_compressBound(sourceSize);
            void *dst = malloc(dstCapacity);
            if (dst != NULL) {
                (void)ZSTD_compress_usingCDict(cctx, dst, dstCapacity,
                                               sourcePtr, sourceSize, cdict);
                free(dst);
            }
            (void)ZSTD_freeCCtx(cctx);
        }
    }
    (void)ZSTD_freeCDict(cdict);
    return 0;
}

Build (libFuzzer driver, ASan, asserts enabled):

# In the zstd source tree, after building libzstd.a with -DDEBUGLEVEL=1
clang -O1 -g \
      -fsanitize=address,fuzzer \
      -I lib -DZSTD_STATIC_LINKING_ONLY \
      dictionary_loader.c lib/libzstd.a \
      -o fuzz_dict
./fuzz_dict crash_input

Output:

zstd_opt.c:195: void ZSTD_rescaleFreqs(...): Assertion `bitCost < scaleLog' failed.
==ERROR: libFuzzer: deadly signal
    #11 ZSTD_rescaleFreqs              lib/compress/zstd_opt.c:195:21
    #12 ZSTD_compressBlock_opt_generic lib/compress/zstd_opt.c:1115:5
    #13 ZSTD_compressBlock_opt2        lib/compress/zstd_opt.c:1451:12
    #14 ZSTD_buildSeqStore             lib/compress/zstd_compress.c:3444:26
    #19 LLVMFuzzerTestOneInput         dictionary_loader.c:138:23

This reproduces on every run.

---

Trigger Method 2: Standalone driver (no libFuzzer)

app.c is a minimal main() that forwards the crash file straight into
LLVMFuzzerTestOneInput:

#include <stdio.h>
#include <stdlib.h>
extern int LLVMFuzzerTestOneInput(const unsigned char*, size_t);
int main(int argc, char**argv) {
    FILE *f = fopen(argv[1], "rb");
    fseek(f, 0, SEEK_END); long n = ftell(f); fseek(f, 0, SEEK_SET);
    unsigned char *b = malloc(n); fread(b, 1, n, f); fclose(f);
    fprintf(stderr, "[*] %ld bytes\n", n);
    LLVMFuzzerTestOneInput(b, (size_t)n);
    fprintf(stderr, "[*] no crash\n");
    return 0;
}

Build (ASan must match how libzstd.a was built — our libzstd.a is
ASan-instrumented, so the standalone driver must be linked with
-fsanitize=address too):

clang -O1 -g \
      -fsanitize=address \
      -I lib -DZSTD_STATIC_LINKING_ONLY \
      dictionary_loader.c app.c lib/libzstd.a \
      -o repro
ASAN_OPTIONS=detect_leaks=0 ./repro crash_input

Output: identical assertion at zstd_opt.c:195. In our environment this
reproduces 10/10 runs.

Honesty note (carried over from VERIFY.md): an earlier internal verification
pass reported this standalone reproducer as intermittent. On a fresh
rebuild we cannot reproduce the intermittence; we believe it was a build /
state artifact. If maintainers see flakiness anyway, the following loop
should reliably surface the crash within a few iterations:

for i in $(seq 1 50); do
    ASAN_OPTIONS=detect_leaks=0 ./repro crash_input && break
done

Suggested Fix

Two complementary options; either alone would resolve the crash, both
together would be the cleanest.

(a) Tighten the guard, or clamp. Inside ZSTD_rescaleFreqs (zstd_opt.c:176-210),
the FSE branches iterate over the full symbol range even though
FSE_getMaxNbBits() is documented to return tableLog + 1 for
zero-frequency symbols. Since the max FSE tableLog is MLFSELog == 9 == scaleLog - 1, that "fake cost" exactly hits scaleLog. The minimal patch
is to clamp:

    for (ml=0; ml<=MaxML; ml++) {
        U32 const scaleLog = 10;
        U32 bitCost = FSE_getMaxNbBits(mlstate.symbolTT, ml);
        /* FSE_getMaxNbBits() returns tableLog+1 as a "fake cost" for
         * zero-frequency symbols; tableLog can be MLFSELog == scaleLog-1,
         * which violates the strict-less-than invariant of this scale. */
        if (bitCost >= scaleLog) bitCost = scaleLog - 1;
        optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1;
        optPtr->matchLengthSum += optPtr->matchLengthFreq[ml];
    }

Apply the same clamp at lines 183 (litLength) and 207 (offCode). The
behavior on bitCost == scaleLog becomes matchLengthFreq[ml] = 1 — i.e.
identical to today's release-build behavior, but now also valid in debug
builds.

(b) Gate the dict-derived FSE path on the per-stream repeat modes, not just HUF.
The outer guard at zstd_opt.c:158 only checks huf.repeatMode == HUF_repeat_valid. The FSE branches should additionally check
fse.matchlength_repeatMode == FSE_repeat_valid (and likewise for litlength
/ offcode) before iterating the FSE table. When the per-stream repeat mode
is FSE_repeat_check (i.e. the dict NCount had zero-frequency entries), the
code should fall through to the "no dictionary stats" branch at line 212
for that specific stream instead of trusting the FSE table to cover the
full symbol range.

Option (b) is the more principled fix because it matches the design intent
of ZSTD_dictNCountRepeat() in zstd_compress.c:5071-5083, which already
labels these tables as "not fully valid" — ZSTD_rescaleFreqs is just
ignoring that label today.

Happy to send a PR for either approach if maintainers indicate a preference.

Credit

Aisle Research (Ze Sheng, Dmitrijs Trizna, Luigino Camastra, Guido Vranken)

[OwenSanzas]

Supplementary: deterministic regenerator for crash_input

To make the PoC fully self-contained (no binary attachment dependency), the
following Python script writes a byte-for-byte copy of the 446-byte
crash_input referenced above. Verified diff-clean against our local
artifact.

#!/usr/bin/env python3
"""
Deterministic generator for crash_input — the 446-byte trigger for the
`assert(bitCost < scaleLog)` failure in `ZSTD_rescaleFreqs`
(lib/compress/zstd_opt.c:195) when the dictionary_loader harness drives
ZSTD_createCDict_advanced with a small custom dict + an optimal-parser
strategy.

File layout (446 bytes total):
  [0..3]     : ZSTD_MAGIC_DICTIONARY (0xEC30A437, little-endian 37 A4 30 EC)
  [4..432]   : zstd dictionary body (header + Huffman + FSE NCount + content).
               The FSE matchlength NCount encoded here has zero-frequency
               symbols inside the 0..MaxML range, which later makes
               FSE_getMaxNbBits() return tableLog+1 == scaleLog.
  [433..445] : 13-byte control tail consumed by dictionary_loader.c from
               end inward. Decoded:
                 flags          = 0x05  (& 1 = dlm_byRef,
                                         (>>1)%3 = 2 = dct_fullDict,
                                         & 8 = 0 -> explicit cParams path)
                 levelByte      = 0x00  (unused on explicit path)
                 dictSelector   = 0x0090
                 sourceSelector = 0x0100
                 windowLogByte  = 0x06
                 hashLogByte    = 0x0A
                 chainLogByte   = 0x0A
                 searchLogByte  = 0x04
                 minMatchByte   = 0x04
                 targetLengthByte / strategyByte: consumed from dict body
                                                  region; ZSTD_adjustCParams
                                                  lands on an optimal-parser
                                                  strategy for this input.

Usage:
    python3 generate_crash_input.py            # writes ./crash_input
    ./fuzz_dict crash_input                    # Trigger Method 1
    ./repro     crash_input                    # Trigger Method 2
"""

CRASH_INPUT_HEX = (
    "37a430ec630000000810001f0f0028e5030300000000000000800f9e0f000024"
    "4080000102040404040404040404de080808080808080808080808080808bce1"
    "4b920eb47b18866118c618638c31c618638c3166666666b66d01000000040000"
    "000800000020736f64616c657320746f72746f7220656c656966656e642e2041"
    "6c6964696374696f6e617279206d617463682061616161616161616469637469"
    "6f6e617279206d6174636820616161616161616164696374696f6e617279206d"
    "6174636820616161616161616164696374617279206d61746368206161616161"
    "61616164696374696f6e617279206d6174636820616161616161616164696374"
    "696f6e6172790808080808080808080808080808080808080808080808080808"
    "080808bce14b920eb47b18866118c618638c31c618637279206d617463682061"
    "616161616179206d6174636820616161616161616164696374696f6e61727920"
    "6d6174636820616161616161616164696374696f6e617279206d617463682061"
    "6161616161616164696374693031323334353334353637383961626364656630"
    "31323300000000000000000b001000026f088004040a0a06010000900005"
)


def main(path: str = "crash_input") -> None:
    data = bytes.fromhex(CRASH_INPUT_HEX)
    assert len(data) == 446, f"expected 446 bytes, got {len(data)}"
    assert data[:4] == b"\x37\xa4\x30\xec", "dict magic mismatch"
    with open(path, "wb") as f:
        f.write(data)
    print(f"wrote {path} ({len(data)} bytes)")


if __name__ == "__main__":
    import sys
    main(sys.argv[1] if len(sys.argv) > 1 else "crash_input")

The hex blob is the libFuzzer minimizer's output of an AGF (AI-Guided
Fuzzing) campaign against dictionary_loader.c. The reason we ship it as
a hex literal rather than reconstructing the dict from a Python-side
training step is that the assertion requires a specific shape of FSE
NCount (at least one zero-frequency symbol within 0..MaxML), and
producing one deterministically from outside the zstd dict format would
mean re-implementing the dict-format encoder in Python. The hex literal
is the smallest verified input — 10/10 reproductions on a fresh ASan +
-DDEBUGLEVEL=1 build.