1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
|
/*
* 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;
}
|