/*
* Copyright (c) Meta Platforms, Inc. and affiliates.
* All rights reserved.
*
* This source code is licensed under both the BSD-style license (found in the
* LICENSE file in the root directory of this source tree) and the GPLv2 (found
* in the COPYING file in the root directory of this source tree).
* You may select, at your option, one of the above-listed licenses.
*/
/**
* This fuzz target performs a zstd round-trip test by generating an arbitrary
* array of sequences, generating the associated source buffer, calling
* ZSTD_compressSequences(), and then decompresses and compares the result with
* the original generated source buffer.
*/
#define ZSTD_STATIC_LINKING_ONLY
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "fuzz_helpers.h"
#include "zstd_helpers.h"
#include "fuzz_data_producer.h"
#include "fuzz_third_party_seq_prod.h"
static ZSTD_CCtx* cctx = NULL;
static ZSTD_DCtx* dctx = NULL;
static void* literalsBuffer = NULL;
static void* generatedSrc = NULL;
static ZSTD_Sequence* generatedSequences = NULL;
static void* dictBuffer = NULL;
static ZSTD_CDict* cdict = NULL;
static ZSTD_DDict* ddict = NULL;
#define ZSTD_FUZZ_GENERATED_SRC_MAXSIZE (1 << 20) /* Allow up to 1MB generated data */
#define ZSTD_FUZZ_GENERATED_LITERALS_SIZE (1 << 20) /* Fixed size 1MB literals buffer */
#define ZSTD_FUZZ_MATCHLENGTH_MAXSIZE (1 << 18) /* Allow up to 256KB matches */
#define ZSTD_FUZZ_GENERATED_DICT_MAXSIZE (1 << ZSTD_WINDOWLOG_MAX_32) /* Allow up to 1 << ZSTD_WINDOWLOG_MAX_32 dictionary */
#define ZSTD_FUZZ_MAX_NBSEQ (1 << 17) /* Maximum of 128K sequences */
/* Deterministic random number generator */
#define FUZZ_RDG_rotl32(x,r) ((x << r) | (x >> (32 - r)))
static uint32_t FUZZ_RDG_rand(uint32_t* src)
{
static const uint32_t prime1 = 2654435761U;
static const uint32_t prime2 = 2246822519U;
uint32_t rand32 = *src;
rand32 *= prime1;
rand32 ^= prime2;
rand32 = FUZZ_RDG_rotl32(rand32, 13);
*src = rand32;
return rand32 >> 5;
}
/* Make a pseudorandom string - this simple function exists to avoid
* taking a dependency on datagen.h to have RDG_genBuffer().
*/
static char* generatePseudoRandomString(char* str, size_t size, FUZZ_dataProducer_t* producer) {
const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJK1234567890!@#$^&*()_";
uint32_t seed = FUZZ_dataProducer_uint32(producer);
if (size) {
for (size_t n = 0; n < size; n++) {
int key = FUZZ_RDG_rand(&seed) % (int) (sizeof charset - 1);
str[n] = charset[key];
}
}
return str;
}
/* Returns size of source buffer */
static size_t decodeSequences(void* dst, size_t nbSequences,
size_t literalsSize,
const void* dict, size_t dictSize,
ZSTD_sequenceFormat_e mode)
{
const uint8_t* litPtr = literalsBuffer;
const uint8_t* const litBegin = literalsBuffer;
const uint8_t* const litEnd = litBegin + literalsSize;
const uint8_t* dictPtr = dict;
uint8_t* op = dst;
const uint8_t* const oend = (uint8_t*)dst + ZSTD_FUZZ_GENERATED_SRC_MAXSIZE;
size_t generatedSrcBufferSize = 0;
size_t bytesWritten = 0;
for (size_t i = 0; i < nbSequences; ++i) {
/* block boundary */
if (generatedSequences[i].offset == 0)
FUZZ_ASSERT(generatedSequences[i].matchLength == 0);
if (litPtr + generatedSequences[i].litLength > litEnd) {
litPtr = litBegin;
}
memcpy(op, litPtr, generatedSequences[i].litLength);
bytesWritten += generatedSequences[i].litLength;
op += generatedSequences[i].litLength;
litPtr += generatedSequences[i].litLength;
/* Copy over the match */
{ size_t matchLength = generatedSequences[i].matchLength;
size_t j = 0;
size_t k = 0;
if (dictSize != 0) {
if (generatedSequences[i].offset > bytesWritten) { /* Offset goes into the dictionary */
size_t dictOffset = generatedSequences[i].offset - bytesWritten;
size_t matchInDict = MIN(matchLength, dictOffset);
for (; k < matchInDict; ++k) {
op[k] = dictPtr[dictSize - dictOffset + k];
}
matchLength -= matchInDict;
op += matchInDict;
}
}
for (; j < matchLength; ++j) {
op[j] = op[j - generatedSequences[i].offset];
}
op += j;
FUZZ_ASSERT(generatedSequences[i].matchLength == j + k);
bytesWritten += generatedSequences[i].matchLength;
}
}
generatedSrcBufferSize = bytesWritten;
FUZZ_ASSERT(litPtr <= litEnd);
if (mode == ZSTD_sf_noBlockDelimiters) {
const uint32_t lastLLSize = (uint32_t)(litEnd - litPtr);
if (lastLLSize <= oend - op) {
memcpy(op, litPtr, lastLLSize);
generatedSrcBufferSize += lastLLSize;
} }
return generatedSrcBufferSize;
}
/* Returns nb sequences generated
* Note : random sequences are always valid in ZSTD_sf_noBlockDelimiters mode.
* However, it can fail with ZSTD_sf_explicitBlockDelimiters,
* due to potential lack of space in
*/
static size_t generateRandomSequences(FUZZ_dataProducer_t* producer,
size_t literalsSizeLimit, size_t dictSize,
size_t windowLog, ZSTD_sequenceFormat_e mode)
{
const uint32_t repCode = 0; /* not used by sequence ingestion api */
size_t windowSize = 1ULL << windowLog;
size_t blockSizeMax = MIN(ZSTD_BLOCKSIZE_MAX, windowSize);
uint32_t matchLengthMax = ZSTD_FUZZ_MATCHLENGTH_MAXSIZE;
uint32_t bytesGenerated = 0;
uint32_t nbSeqGenerated = 0;
uint32_t isFirstSequence = 1;
uint32_t blockSize = 0;
if (mode == ZSTD_sf_explicitBlockDelimiters) {
/* ensure that no sequence can be larger than one block */
literalsSizeLimit = MIN(literalsSizeLimit, blockSizeMax/2);
matchLengthMax = MIN(matchLengthMax, blockSizeMax/2);
}
while ( nbSeqGenerated < ZSTD_FUZZ_MAX_NBSEQ - 3 /* extra room for explicit delimiters */
&& bytesGenerated < ZSTD_FUZZ_GENERATED_SRC_MAXSIZE
&& !FUZZ_dataProducer_empty(producer)) {
uint32_t matchLength;
uint32_t matchBound = matchLengthMax;
uint32_t offset;
uint32_t offsetBound;
const uint32_t minLitLength = (isFirstSequence && (dictSize == 0));
const uint32_t litLength = FUZZ_dataProducer_uint32Range(producer, minLitLength, (uint32_t)literalsSizeLimit);
bytesGenerated += litLength;
if (bytesGenerated > ZSTD_FUZZ_GENERATED_SRC_MAXSIZE) {
break;
}
offsetBound = (bytesGenerated > windowSize) ? windowSize : bytesGenerated + (uint32_t)dictSize;
offset = FUZZ_dataProducer_uint32Range(producer, 1, offsetBound);
if (dictSize > 0 && bytesGenerated <= windowSize) {
/* Prevent match length from being such that it would be associated with an offset too large
* from the decoder's perspective. If not possible (match would be too small),
* then reduce the offset if necessary.
*/
const size_t bytesToReachWindowSize = windowSize - bytesGenerated;
if (bytesToReachWindowSize < ZSTD_MINMATCH_MIN) {
const uint32_t newOffsetBound = offsetBound > windowSize ? windowSize : offsetBound;
offset = FUZZ_dataProducer_uint32Range(producer, 1, newOffsetBound);
} else {
matchBound = MIN(matchLengthMax, (uint32_t)bytesToReachWindowSize);
}
}
matchLength = FUZZ_dataProducer_uint32Range(producer, ZSTD_MINMATCH_MIN, matchBound);
bytesGenerated += matchLength;
if (bytesGenerated > ZSTD_FUZZ_GENERATED_SRC_MAXSIZE) {
break;
}
{ ZSTD_Sequence seq = {offset, litLength, matchLength, repCode};
const uint32_t lastLits = FUZZ_dataProducer_uint32Range(producer, 0, litLength);
#define SPLITPROB 6000
#define SPLITMARK 5234
const int split = (FUZZ_dataProducer_uint32Range(producer, 0, SPLITPROB) == SPLITMARK);
if (mode == ZSTD_sf_explicitBlockDelimiters) {
const size_t seqSize = seq.litLength + seq.matchLength;
if (blockSize + seqSize > blockSizeMax) { /* reaching limit : must end block now */
const ZSTD_Sequence endBlock = {0, 0, 0, 0};
generatedSequences[nbSeqGenerated++] = endBlock;
blockSize = seqSize;
}
if (split) {
const ZSTD_Sequence endBlock = {0, lastLits, 0, 0};
generatedSequences[nbSeqGenerated++] = endBlock;
assert(lastLits <= seq.litLength);
seq.litLength -= lastLits;
blockSize = seqSize - lastLits;
} else {
blockSize += seqSize;
}
}
generatedSequences[nbSeqGenerated++] = seq;
isFirstSequence = 0;
}
}
if (mode == ZSTD_sf_explicitBlockDelimiters) {
/* always end sequences with a block delimiter */
const ZSTD_Sequence endBlock = {0, 0, 0, 0};
assert(nbSeqGenerated < ZSTD_FUZZ_MAX_NBSEQ);
generatedSequences[nbSeqGenerated++] = endBlock;
}
return nbSeqGenerated;
}
static size_t roundTripTest(void* result, size_t resultCapacity,
void* compressed, size_t compressedCapacity,
const void* src, size_t srcSize,
const ZSTD_Sequence* seqs, size_t seqSize,
unsigned hasDict,
ZSTD_sequenceFormat_e mode)
{
size_t cSize;
size_t dSize;
if (hasDict) {
FUZZ_ZASSERT(ZSTD_CCtx_refCDict(cctx, cdict));
FUZZ_ZASSERT(ZSTD_DCtx_refDDict(dctx, ddict));
}
cSize = ZSTD_compressSequences(cctx, compressed, compressedCapacity,
seqs, seqSize,
src, srcSize);
if ( (ZSTD_getErrorCode(cSize) == ZSTD_error_dstSize_tooSmall)
&& (mode == ZSTD_sf_explicitBlockDelimiters) ) {
/* Valid scenario : in explicit delimiter mode,
* it might be possible for the compressed size to outgrow dstCapacity.
* In which case, it's still a valid fuzzer scenario,
* but no roundtrip shall be possible */
return 0;
}
/* round-trip */
FUZZ_ZASSERT(cSize);
dSize = ZSTD_decompressDCtx(dctx, result, resultCapacity, compressed, cSize);
FUZZ_ZASSERT(dSize);
FUZZ_ASSERT_MSG(dSize == srcSize, "Incorrect regenerated size");
FUZZ_ASSERT_MSG(!FUZZ_memcmp(src, result, srcSize), "Corruption!");
return dSize;
}
int LLVMFuzzerTestOneInput(const uint8_t* src, size_t size)
{
FUZZ_SEQ_PROD_SETUP();
void* rBuf;
size_t rBufSize;
void* cBuf;
size_t cBufSize;
size_t generatedSrcSize;
size_t nbSequences;
size_t dictSize = 0;
unsigned hasDict;
unsigned wLog;
int cLevel;
ZSTD_sequenceFormat_e mode;
FUZZ_dataProducer_t* const producer = FUZZ_dataProducer_create(src, size);
FUZZ_ASSERT(producer);
if (!cctx) {
cctx = ZSTD_createCCtx();
FUZZ_ASSERT(cctx);
}
if (!dctx) {
dctx = ZSTD_createDCtx();
FUZZ_ASSERT(dctx);
}
/* Generate window log first so we don't generate offsets too large */
wLog = FUZZ_dataProducer_uint32Range(producer, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
cLevel = FUZZ_dataProducer_int32Range(producer, -3, 22);
mode = (ZSTD_sequenceFormat_e)FUZZ_dataProducer_int32Range(producer, 0, 1);
ZSTD_CCtx_reset(cctx, ZSTD_reset_session_and_parameters);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_nbWorkers, 0);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_compressionLevel, cLevel);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_windowLog, wLog);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_minMatch, ZSTD_MINMATCH_MIN);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_validateSequences, 1);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_blockDelimiters, mode);
ZSTD_CCtx_setParameter(cctx, ZSTD_c_forceAttachDict, ZSTD_dictForceAttach);
if (!literalsBuffer) {
literalsBuffer = FUZZ_malloc(ZSTD_FUZZ_GENERATED_LITERALS_SIZE);
FUZZ_ASSERT(literalsBuffer);
literalsBuffer = generatePseudoRandomString(literalsBuffer, ZSTD_FUZZ_GENERATED_LITERALS_SIZE, producer);
}
if (!dictBuffer) { /* Generate global dictionary buffer */
ZSTD_compressionParameters cParams;
/* Generate a large dictionary buffer */
dictBuffer = calloc(ZSTD_FUZZ_GENERATED_DICT_MAXSIZE, 1);
FUZZ_ASSERT(dictBuffer);
/* Create global cdict and ddict */
cParams = ZSTD_getCParams(1, ZSTD_FUZZ_GENERATED_SRC_MAXSIZE, ZSTD_FUZZ_GENERATED_DICT_MAXSIZE);
cParams.minMatch = ZSTD_MINMATCH_MIN;
cParams.hashLog = ZSTD_HASHLOG_MIN;
cParams.chainLog = ZSTD_CHAINLOG_MIN;
cdict = ZSTD_createCDict_advanced(dictBuffer, ZSTD_FUZZ_GENERATED_DICT_MAXSIZE, ZSTD_dlm_byRef, ZSTD_dct_rawContent, cParams, ZSTD_defaultCMem);
ddict = ZSTD_createDDict_advanced(dictBuffer, ZSTD_FUZZ_GENERATED_DICT_MAXSIZE, ZSTD_dlm_byRef, ZSTD_dct_rawContent, ZSTD_defaultCMem);
FUZZ_ASSERT(cdict);
FUZZ_ASSERT(ddict);
}
FUZZ_ASSERT(cdict);
FUZZ_ASSERT(ddict);
hasDict = FUZZ_dataProducer_uint32Range(producer, 0, 1);
if (hasDict) {
dictSize = ZSTD_FUZZ_GENERATED_DICT_MAXSIZE;
}
if (!generatedSequences) {
generatedSequences = FUZZ_malloc(sizeof(ZSTD_Sequence)*ZSTD_FUZZ_MAX_NBSEQ);
}
if (!generatedSrc) {
generatedSrc = FUZZ_malloc(ZSTD_FUZZ_GENERATED_SRC_MAXSIZE);
}
nbSequences = generateRandomSequences(producer, ZSTD_FUZZ_GENERATED_LITERALS_SIZE, dictSize, wLog, mode);
generatedSrcSize = decodeSequences(generatedSrc, nbSequences, ZSTD_FUZZ_GENERATED_LITERALS_SIZE, dictBuffer, dictSize, mode);
/* Note : in explicit block delimiters mode,
* the fuzzer might generate a lot of small blocks.
* In which case, the final compressed size might be > ZSTD_compressBound().
* This is still a valid scenario fuzzer though, which makes it possible to check under-sized dstCapacity.
* The test just doesn't roundtrip. */
cBufSize = ZSTD_compressBound(generatedSrcSize);
cBuf = FUZZ_malloc(cBufSize);
rBufSize = generatedSrcSize;
rBuf = FUZZ_malloc(rBufSize);
{ const size_t result = roundTripTest(rBuf, rBufSize,
cBuf, cBufSize,
generatedSrc, generatedSrcSize,
generatedSequences, nbSequences,
hasDict, mode);
FUZZ_ASSERT(result <= generatedSrcSize); /* can be 0 when no round-trip */
}
free(rBuf);
free(cBuf);
FUZZ_dataProducer_free(producer);
#ifndef STATEFUL_FUZZING
ZSTD_freeCCtx(cctx); cctx = NULL;
ZSTD_freeDCtx(dctx); dctx = NULL;
free(generatedSequences); generatedSequences = NULL;
free(generatedSrc); generatedSrc = NULL;
free(literalsBuffer); literalsBuffer = NULL;
#endif
FUZZ_SEQ_PROD_TEARDOWN();
return 0;
}