2 * Copyright (c) Meta Platforms, Inc. and affiliates.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
12 * This fuzz target performs a zstd round-trip test by generating an arbitrary
13 * array of sequences, generating the associated source buffer, calling
14 * ZSTD_compressSequences(), and then decompresses and compares the result with
15 * the original generated source buffer.
18 #define ZSTD_STATIC_LINKING_ONLY
25 #include "fuzz_helpers.h"
26 #include "zstd_helpers.h"
27 #include "fuzz_data_producer.h"
28 #include "fuzz_third_party_seq_prod.h"
30 static ZSTD_CCtx* cctx = NULL;
31 static ZSTD_DCtx* dctx = NULL;
32 static void* literalsBuffer = NULL;
33 static void* generatedSrc = NULL;
34 static ZSTD_Sequence* generatedSequences = NULL;
36 static void* dictBuffer = NULL;
37 static ZSTD_CDict* cdict = NULL;
38 static ZSTD_DDict* ddict = NULL;
40 #define ZSTD_FUZZ_GENERATED_SRC_MAXSIZE (1 << 20) /* Allow up to 1MB generated data */
41 #define ZSTD_FUZZ_GENERATED_LITERALS_SIZE (1 << 20) /* Fixed size 1MB literals buffer */
42 #define ZSTD_FUZZ_MATCHLENGTH_MAXSIZE (1 << 18) /* Allow up to 256KB matches */
43 #define ZSTD_FUZZ_GENERATED_DICT_MAXSIZE (1 << ZSTD_WINDOWLOG_MAX_32) /* Allow up to 1 << ZSTD_WINDOWLOG_MAX_32 dictionary */
44 #define ZSTD_FUZZ_MAX_NBSEQ (1 << 17) /* Maximum of 128K sequences */
46 /* Deterministic random number generator */
47 #define FUZZ_RDG_rotl32(x,r) ((x << r) | (x >> (32 - r)))
48 static uint32_t FUZZ_RDG_rand(uint32_t* src)
50 static const uint32_t prime1 = 2654435761U;
51 static const uint32_t prime2 = 2246822519U;
52 uint32_t rand32 = *src;
55 rand32 = FUZZ_RDG_rotl32(rand32, 13);
60 /* Make a pseudorandom string - this simple function exists to avoid
61 * taking a dependency on datagen.h to have RDG_genBuffer().
63 static char* generatePseudoRandomString(char* str, size_t size, FUZZ_dataProducer_t* producer) {
64 const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJK1234567890!@#$^&*()_";
65 uint32_t seed = FUZZ_dataProducer_uint32(producer);
67 for (size_t n = 0; n < size; n++) {
68 int key = FUZZ_RDG_rand(&seed) % (int) (sizeof charset - 1);
69 str[n] = charset[key];
75 /* Returns size of source buffer */
76 static size_t decodeSequences(void* dst, size_t nbSequences,
78 const void* dict, size_t dictSize,
79 ZSTD_sequenceFormat_e mode)
81 const uint8_t* litPtr = literalsBuffer;
82 const uint8_t* const litBegin = literalsBuffer;
83 const uint8_t* const litEnd = litBegin + literalsSize;
84 const uint8_t* dictPtr = dict;
86 const uint8_t* const oend = (uint8_t*)dst + ZSTD_FUZZ_GENERATED_SRC_MAXSIZE;
87 size_t generatedSrcBufferSize = 0;
88 size_t bytesWritten = 0;
90 for (size_t i = 0; i < nbSequences; ++i) {
92 if (generatedSequences[i].offset == 0)
93 FUZZ_ASSERT(generatedSequences[i].matchLength == 0);
95 if (litPtr + generatedSequences[i].litLength > litEnd) {
98 memcpy(op, litPtr, generatedSequences[i].litLength);
99 bytesWritten += generatedSequences[i].litLength;
100 op += generatedSequences[i].litLength;
101 litPtr += generatedSequences[i].litLength;
103 /* Copy over the match */
104 { size_t matchLength = generatedSequences[i].matchLength;
108 if (generatedSequences[i].offset > bytesWritten) { /* Offset goes into the dictionary */
109 size_t dictOffset = generatedSequences[i].offset - bytesWritten;
110 size_t matchInDict = MIN(matchLength, dictOffset);
111 for (; k < matchInDict; ++k) {
112 op[k] = dictPtr[dictSize - dictOffset + k];
114 matchLength -= matchInDict;
118 for (; j < matchLength; ++j) {
119 op[j] = op[j - generatedSequences[i].offset];
122 FUZZ_ASSERT(generatedSequences[i].matchLength == j + k);
123 bytesWritten += generatedSequences[i].matchLength;
126 generatedSrcBufferSize = bytesWritten;
127 FUZZ_ASSERT(litPtr <= litEnd);
128 if (mode == ZSTD_sf_noBlockDelimiters) {
129 const uint32_t lastLLSize = (uint32_t)(litEnd - litPtr);
130 if (lastLLSize <= oend - op) {
131 memcpy(op, litPtr, lastLLSize);
132 generatedSrcBufferSize += lastLLSize;
134 return generatedSrcBufferSize;
137 /* Returns nb sequences generated
138 * Note : random sequences are always valid in ZSTD_sf_noBlockDelimiters mode.
139 * However, it can fail with ZSTD_sf_explicitBlockDelimiters,
140 * due to potential lack of space in
142 static size_t generateRandomSequences(FUZZ_dataProducer_t* producer,
143 size_t literalsSizeLimit, size_t dictSize,
144 size_t windowLog, ZSTD_sequenceFormat_e mode)
146 const uint32_t repCode = 0; /* not used by sequence ingestion api */
147 size_t windowSize = 1ULL << windowLog;
148 size_t blockSizeMax = MIN(ZSTD_BLOCKSIZE_MAX, windowSize);
149 uint32_t matchLengthMax = ZSTD_FUZZ_MATCHLENGTH_MAXSIZE;
150 uint32_t bytesGenerated = 0;
151 uint32_t nbSeqGenerated = 0;
152 uint32_t isFirstSequence = 1;
153 uint32_t blockSize = 0;
155 if (mode == ZSTD_sf_explicitBlockDelimiters) {
156 /* ensure that no sequence can be larger than one block */
157 literalsSizeLimit = MIN(literalsSizeLimit, blockSizeMax/2);
158 matchLengthMax = MIN(matchLengthMax, blockSizeMax/2);
161 while ( nbSeqGenerated < ZSTD_FUZZ_MAX_NBSEQ - 3 /* extra room for explicit delimiters */
162 && bytesGenerated < ZSTD_FUZZ_GENERATED_SRC_MAXSIZE
163 && !FUZZ_dataProducer_empty(producer)) {
164 uint32_t matchLength;
165 uint32_t matchBound = matchLengthMax;
167 uint32_t offsetBound;
168 const uint32_t minLitLength = (isFirstSequence && (dictSize == 0));
169 const uint32_t litLength = FUZZ_dataProducer_uint32Range(producer, minLitLength, (uint32_t)literalsSizeLimit);
170 bytesGenerated += litLength;
171 if (bytesGenerated > ZSTD_FUZZ_GENERATED_SRC_MAXSIZE) {
174 offsetBound = (bytesGenerated > windowSize) ? windowSize : bytesGenerated + (uint32_t)dictSize;
175 offset = FUZZ_dataProducer_uint32Range(producer, 1, offsetBound);
176 if (dictSize > 0 && bytesGenerated <= windowSize) {
177 /* Prevent match length from being such that it would be associated with an offset too large
178 * from the decoder's perspective. If not possible (match would be too small),
179 * then reduce the offset if necessary.
181 const size_t bytesToReachWindowSize = windowSize - bytesGenerated;
182 if (bytesToReachWindowSize < ZSTD_MINMATCH_MIN) {
183 const uint32_t newOffsetBound = offsetBound > windowSize ? windowSize : offsetBound;
184 offset = FUZZ_dataProducer_uint32Range(producer, 1, newOffsetBound);
186 matchBound = MIN(matchLengthMax, (uint32_t)bytesToReachWindowSize);
189 matchLength = FUZZ_dataProducer_uint32Range(producer, ZSTD_MINMATCH_MIN, matchBound);
190 bytesGenerated += matchLength;
191 if (bytesGenerated > ZSTD_FUZZ_GENERATED_SRC_MAXSIZE) {
194 { ZSTD_Sequence seq = {offset, litLength, matchLength, repCode};
195 const uint32_t lastLits = FUZZ_dataProducer_uint32Range(producer, 0, litLength);
196 #define SPLITPROB 6000
197 #define SPLITMARK 5234
198 const int split = (FUZZ_dataProducer_uint32Range(producer, 0, SPLITPROB) == SPLITMARK);
199 if (mode == ZSTD_sf_explicitBlockDelimiters) {
200 const size_t seqSize = seq.litLength + seq.matchLength;
201 if (blockSize + seqSize > blockSizeMax) { /* reaching limit : must end block now */
202 const ZSTD_Sequence endBlock = {0, 0, 0, 0};
203 generatedSequences[nbSeqGenerated++] = endBlock;
207 const ZSTD_Sequence endBlock = {0, lastLits, 0, 0};
208 generatedSequences[nbSeqGenerated++] = endBlock;
209 assert(lastLits <= seq.litLength);
210 seq.litLength -= lastLits;
211 blockSize = seqSize - lastLits;
213 blockSize += seqSize;
216 generatedSequences[nbSeqGenerated++] = seq;
221 if (mode == ZSTD_sf_explicitBlockDelimiters) {
222 /* always end sequences with a block delimiter */
223 const ZSTD_Sequence endBlock = {0, 0, 0, 0};
224 assert(nbSeqGenerated < ZSTD_FUZZ_MAX_NBSEQ);
225 generatedSequences[nbSeqGenerated++] = endBlock;
227 return nbSeqGenerated;
230 static size_t roundTripTest(void* result, size_t resultCapacity,
231 void* compressed, size_t compressedCapacity,
232 const void* src, size_t srcSize,
233 const ZSTD_Sequence* seqs, size_t seqSize,
235 ZSTD_sequenceFormat_e mode)
241 FUZZ_ZASSERT(ZSTD_CCtx_refCDict(cctx, cdict));
242 FUZZ_ZASSERT(ZSTD_DCtx_refDDict(dctx, ddict));
245 cSize = ZSTD_compressSequences(cctx, compressed, compressedCapacity,
248 if ( (ZSTD_getErrorCode(cSize) == ZSTD_error_dstSize_tooSmall)
249 && (mode == ZSTD_sf_explicitBlockDelimiters) ) {
250 /* Valid scenario : in explicit delimiter mode,
251 * it might be possible for the compressed size to outgrow dstCapacity.
252 * In which case, it's still a valid fuzzer scenario,
253 * but no roundtrip shall be possible */
258 dSize = ZSTD_decompressDCtx(dctx, result, resultCapacity, compressed, cSize);
260 FUZZ_ASSERT_MSG(dSize == srcSize, "Incorrect regenerated size");
261 FUZZ_ASSERT_MSG(!FUZZ_memcmp(src, result, srcSize), "Corruption!");
265 int LLVMFuzzerTestOneInput(const uint8_t* src, size_t size)
267 FUZZ_SEQ_PROD_SETUP();
273 size_t generatedSrcSize;
279 ZSTD_sequenceFormat_e mode;
281 FUZZ_dataProducer_t* const producer = FUZZ_dataProducer_create(src, size);
282 FUZZ_ASSERT(producer);
285 cctx = ZSTD_createCCtx();
289 dctx = ZSTD_createDCtx();
293 /* Generate window log first so we don't generate offsets too large */
294 wLog = FUZZ_dataProducer_uint32Range(producer, ZSTD_WINDOWLOG_MIN, ZSTD_WINDOWLOG_MAX);
295 cLevel = FUZZ_dataProducer_int32Range(producer, -3, 22);
296 mode = (ZSTD_sequenceFormat_e)FUZZ_dataProducer_int32Range(producer, 0, 1);
298 ZSTD_CCtx_reset(cctx, ZSTD_reset_session_and_parameters);
299 ZSTD_CCtx_setParameter(cctx, ZSTD_c_nbWorkers, 0);
300 ZSTD_CCtx_setParameter(cctx, ZSTD_c_compressionLevel, cLevel);
301 ZSTD_CCtx_setParameter(cctx, ZSTD_c_windowLog, wLog);
302 ZSTD_CCtx_setParameter(cctx, ZSTD_c_minMatch, ZSTD_MINMATCH_MIN);
303 ZSTD_CCtx_setParameter(cctx, ZSTD_c_validateSequences, 1);
304 ZSTD_CCtx_setParameter(cctx, ZSTD_c_blockDelimiters, mode);
305 ZSTD_CCtx_setParameter(cctx, ZSTD_c_forceAttachDict, ZSTD_dictForceAttach);
307 if (!literalsBuffer) {
308 literalsBuffer = FUZZ_malloc(ZSTD_FUZZ_GENERATED_LITERALS_SIZE);
309 FUZZ_ASSERT(literalsBuffer);
310 literalsBuffer = generatePseudoRandomString(literalsBuffer, ZSTD_FUZZ_GENERATED_LITERALS_SIZE, producer);
313 if (!dictBuffer) { /* Generate global dictionary buffer */
314 ZSTD_compressionParameters cParams;
316 /* Generate a large dictionary buffer */
317 dictBuffer = calloc(ZSTD_FUZZ_GENERATED_DICT_MAXSIZE, 1);
318 FUZZ_ASSERT(dictBuffer);
320 /* Create global cdict and ddict */
321 cParams = ZSTD_getCParams(1, ZSTD_FUZZ_GENERATED_SRC_MAXSIZE, ZSTD_FUZZ_GENERATED_DICT_MAXSIZE);
322 cParams.minMatch = ZSTD_MINMATCH_MIN;
323 cParams.hashLog = ZSTD_HASHLOG_MIN;
324 cParams.chainLog = ZSTD_CHAINLOG_MIN;
326 cdict = ZSTD_createCDict_advanced(dictBuffer, ZSTD_FUZZ_GENERATED_DICT_MAXSIZE, ZSTD_dlm_byRef, ZSTD_dct_rawContent, cParams, ZSTD_defaultCMem);
327 ddict = ZSTD_createDDict_advanced(dictBuffer, ZSTD_FUZZ_GENERATED_DICT_MAXSIZE, ZSTD_dlm_byRef, ZSTD_dct_rawContent, ZSTD_defaultCMem);
335 hasDict = FUZZ_dataProducer_uint32Range(producer, 0, 1);
337 dictSize = ZSTD_FUZZ_GENERATED_DICT_MAXSIZE;
340 if (!generatedSequences) {
341 generatedSequences = FUZZ_malloc(sizeof(ZSTD_Sequence)*ZSTD_FUZZ_MAX_NBSEQ);
344 generatedSrc = FUZZ_malloc(ZSTD_FUZZ_GENERATED_SRC_MAXSIZE);
347 nbSequences = generateRandomSequences(producer, ZSTD_FUZZ_GENERATED_LITERALS_SIZE, dictSize, wLog, mode);
348 generatedSrcSize = decodeSequences(generatedSrc, nbSequences, ZSTD_FUZZ_GENERATED_LITERALS_SIZE, dictBuffer, dictSize, mode);
350 /* Note : in explicit block delimiters mode,
351 * the fuzzer might generate a lot of small blocks.
352 * In which case, the final compressed size might be > ZSTD_compressBound().
353 * This is still a valid scenario fuzzer though, which makes it possible to check under-sized dstCapacity.
354 * The test just doesn't roundtrip. */
355 cBufSize = ZSTD_compressBound(generatedSrcSize);
356 cBuf = FUZZ_malloc(cBufSize);
358 rBufSize = generatedSrcSize;
359 rBuf = FUZZ_malloc(rBufSize);
361 { const size_t result = roundTripTest(rBuf, rBufSize,
363 generatedSrc, generatedSrcSize,
364 generatedSequences, nbSequences,
366 FUZZ_ASSERT(result <= generatedSrcSize); /* can be 0 when no round-trip */
371 FUZZ_dataProducer_free(producer);
372 #ifndef STATEFUL_FUZZING
373 ZSTD_freeCCtx(cctx); cctx = NULL;
374 ZSTD_freeDCtx(dctx); dctx = NULL;
375 free(generatedSequences); generatedSequences = NULL;
376 free(generatedSrc); generatedSrc = NULL;
377 free(literalsBuffer); literalsBuffer = NULL;
379 FUZZ_SEQ_PROD_TEARDOWN();