Stack-buffer-underflow in FSE_compress2

[hgarrereyn]

Hi, the following testcase causes a stack-buffer-underflow (read) in FSE_compress2.

It's possible that the user-provided tableLog (here 5) is too small fo the alphabet, but in that case I would expect FSE_compress2 to return an error code instead.

See the provided test case and crash report:

testcase.cpp

#include <cstdio>
#include <cstdlib>
#include <cstdint>
extern "C" {
#include "fse.h"
}
int main(){
  // 32 bytes with a large alphabet (includes 254) and some repetitions
  unsigned char data[32] = {
    183, 0, 183, 245, 245, 245, 183, 245, 10, 10, 189, 10, 49, 23, 68, 66,
    152, 59, 79, 76, 206, 206, 210, 210, 94, 210, 210, 210, 210, 190, 158, 254
  };
  size_t srcSize = sizeof(data);
  size_t dstCap = FSE_compressBound(srcSize);
  void* dst = malloc(dstCap);
  // tableLog is small but non-zero; maxSymbolValue=0 (default)
  unsigned tableLog = 5;
  unsigned maxSymbolValue = 0;
  size_t r = FSE_compress2(dst, dstCap, data, srcSize, maxSymbolValue, tableLog);
  // On affected builds, this triggers ASan stack-buffer-underflow in FSE_encodeSymbol
  fprintf(stderr, "r=%zu\n", r);
  free(dst);
  return 0;
}

crash report

{
  "Date": "2025-09-29T16:52:48.123916+00:00",
  "Uname": "Linux 4b0d4e790e43 5.15.0-156-generic #166-Ubuntu SMP Sat Aug 9 00:02:46 UTC 2025 x86_64 x86_64 x86_64 GNU/Linux",
  "OS": "Ubuntu",
  "OSRelease": "22.04",
  "Architecture": "amd64",
  "ExecutablePath": "/tmp/tmpsuh3ily9/reproducer",
  "ProcEnviron": [
    "PREFIX=/fuzz/install",
    "LIBAFL_EDGES_MAP_SIZE=800000",
    "PWD=/fuzz/workspace",
    "CXX=gf_libafl_cxx",
    "GRAPHFUZZ_USE_ASAN=1",
    "HOME=/root",
    "ASAN_OPTIONS=hard_rss_limit_mb=1024:detect_leaks=0",
    "TERM=xterm-256color",
    "SHLVL=1",
    "LD_LIBRARY_PATH=/fuzz/install/lib",
    "PATH=/root/.cargo/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin",
    "CC=gf_libafl_cc",
    "DEBIAN_FRONTEND=noninteractive",
    "OLDPWD=/fuzz/src",
    "_=/usr/local/bin/agfi"
  ],
  "ProcCmdline": "/tmp/tmpsuh3ily9/reproducer",
  "Stdin": "",
  "ProcStatus": [],
  "ProcMaps": [],
  "ProcFiles": [],
  "NetworkConnections": [],
  "CrashSeverity": {
    "Type": "NOT_EXPLOITABLE",
    "ShortDescription": "stack-buffer-underflow(read)",
    "Description": "Stack buffer underflow",
    "Explanation": "The target reads from a buffer using buffer access mechanisms such as indexes or pointers that reference memory locations prior to the targeted buffer."
  },
  "Stacktrace": [
    "    #0 0x55555565fcea in FSE_encodeSymbol /fuzz/src/lib/fse.h:520:23",
    "    #1 0x55555565fcea in FSE_compress_usingCTable_generic /fuzz/src/lib/fse_compress.c:602:13",
    "    #2 0x5555556602bd in FSE_compress_usingCTable /fuzz/src/lib/fse_compress.c",
    "    #3 0x5555556602bd in FSE_compress_wksp /fuzz/src/lib/fse_compress.c:668:9",
    "    #4 0x55555566058c in FSE_compress2 /fuzz/src/lib/fse_compress.c:692:12",
    "    #5 0x55555565b4e3 in main /tmp/tmpsuh3ily9/reproducer.cpp:19:14",
    "    #6 0x7ffff7a6dd8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16",
    "    #7 0x7ffff7a6de3f in __libc_start_main csu/../csu/libc-start.c:392:3",
    "    #8 0x5555555802e4 in _start (/tmp/tmpsuh3ily9/reproducer+0x2c2e4) (BuildId: cd36094e7abfbd8c575bbfca0f3de3ccc2ce7d30)"
  ],
  "Registers": {},
  "Disassembly": [],
  "Package": "",
  "PackageVersion": "",
  "PackageArchitecture": "",
  "PackageDescription": "",
  "AsanReport": [
    "==156==ERROR: AddressSanitizer: stack-buffer-underflow on address 0x7ffff640001c at pc 0x55555565fceb bp 0x7fffffffe800 sp 0x7fffffffe7f8",
    "READ of size 2 at 0x7ffff640001c thread T0",
    "    #0 0x55555565fcea in FSE_encodeSymbol /fuzz/src/lib/fse.h:520:23",
    "    #1 0x55555565fcea in FSE_compress_usingCTable_generic /fuzz/src/lib/fse_compress.c:602:13",
    "    #2 0x5555556602bd in FSE_compress_usingCTable /fuzz/src/lib/fse_compress.c",
    "    #3 0x5555556602bd in FSE_compress_wksp /fuzz/src/lib/fse_compress.c:668:9",
    "    #4 0x55555566058c in FSE_compress2 /fuzz/src/lib/fse_compress.c:692:12",
    "    #5 0x55555565b4e3 in main /tmp/tmpsuh3ily9/reproducer.cpp:19:14",
    "    #6 0x7ffff7a6dd8f in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16",
    "    #7 0x7ffff7a6de3f in __libc_start_main csu/../csu/libc-start.c:392:3",
    "    #8 0x5555555802e4 in _start (/tmp/tmpsuh3ily9/reproducer+0x2c2e4) (BuildId: cd36094e7abfbd8c575bbfca0f3de3ccc2ce7d30)",
    "",
    "Address 0x7ffff640001c is located in stack of thread T0 at offset 28 in frame",
    "    #0 0x55555566042f in FSE_compress2 /fuzz/src/lib/fse_compress.c:688",
    "",
    "  This frame has 1 object(s):",
    "    [32, 14372) 'scratchBuffer' (line 689) <== Memory access at offset 28 underflows this variable",
    "HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork",
    "      (longjmp and C++ exceptions *are* supported)",
    "SUMMARY: AddressSanitizer: stack-buffer-underflow /fuzz/src/lib/fse.h:520:23 in FSE_encodeSymbol",
    "Shadow bytes around the buggy address:",
    "  0x7ffff63ffd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff63ffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff63ffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff63fff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff63fff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "=>0x7ffff6400000: f1 f1 f1[f1]00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff6400080: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff6400100: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff6400180: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff6400200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "  0x7ffff6400280: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00",
    "Shadow byte legend (one shadow byte represents 8 application bytes):",
    "  Addressable:           00",
    "  Partially addressable: 01 02 03 04 05 06 07",
    "  Heap left redzone:       fa",
    "  Freed heap region:       fd",
    "  Stack left redzone:      f1",
    "  Stack mid redzone:       f2",
    "  Stack right redzone:     f3",
    "  Stack after return:      f5",
    "  Stack use after scope:   f8",
    "  Global redzone:          f9",
    "  Global init order:       f6",
    "  Poisoned by user:        f7",
    "  Container overflow:      fc",
    "  Array cookie:            ac",
    "  Intra object redzone:    bb",
    "  ASan internal:           fe",
    "  Left alloca redzone:     ca",
    "  Right alloca redzone:    cb",
    "==156==ABORTING"
  ],
  "MsanReport": [],
  "UbsanReport": [],
  "LuaReport": [],
  "PythonReport": [],
  "GoReport": [],
  "JavaReport": [],
  "RustReport": [],
  "JsReport": [],
  "CSharpReport": [],
  "CrashLine": "/fuzz/src/lib/fse.h:520:23",
  "Source": [
    "    516        FSE_symbolCompressionTransform const symbolTT = ((const FSE_symbolCompressionTransform*)(statePtr->symbolTT))[symbol];",
    "    517        const U16* const stateTable = (const U16*)(statePtr->stateTable);",
    "    518        U32 const nbBitsOut  = (U32)((statePtr->value + symbolTT.deltaNbBits) >> 16);",
    "    519        BIT_addBits(bitC, statePtr->value, nbBitsOut);",
    "--->520        statePtr->value = stateTable[ (statePtr->value >> nbBitsOut) + symbolTT.deltaFindState];",
    "    521    }",
    "    522    ",
    "    523    MEM_STATIC void FSE_flushCState(BIT_CStream_t* bitC, const FSE_CState_t* statePtr)",
    "    524    {",
    "    525        BIT_addBits(bitC, statePtr->value, statePtr->stateLog);"
  ]
}