blob: 284993918aaacd0b953cf9162986880de868620c [file] [log] [blame]
Marshall Clowbaa6fb32017-10-04 22:23:03 +00001// -*- C++ -*-
2//===------------------------- fuzzing.cpp -------------------------------===//
3//
Chandler Carruthd2012102019-01-19 10:56:40 +00004// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
Marshall Clowbaa6fb32017-10-04 22:23:03 +00007//
8//===----------------------------------------------------------------------===//
9
Marshall Clow43ff7d92018-11-04 17:57:25 +000010// A set of routines to use when fuzzing the algorithms in libc++
11// Each one tests a single algorithm.
Marshall Clowbaa6fb32017-10-04 22:23:03 +000012//
Marshall Clow43ff7d92018-11-04 17:57:25 +000013// They all have the form of:
14// int `algorithm`(const uint8_t *data, size_t size);
Marshall Clowbaa6fb32017-10-04 22:23:03 +000015//
Marshall Clow43ff7d92018-11-04 17:57:25 +000016// They perform the operation, and then check to see if the results are correct.
17// If so, they return zero, and non-zero otherwise.
Marshall Clowbaa6fb32017-10-04 22:23:03 +000018//
Marshall Clow43ff7d92018-11-04 17:57:25 +000019// For example, sort calls std::sort, then checks two things:
20// (1) The resulting vector is sorted
21// (2) The resulting vector contains the same elements as the original data.
Marshall Clowbaa6fb32017-10-04 22:23:03 +000022
23
24
25#include "fuzzing.h"
26#include <vector>
27#include <algorithm>
Marshall Clowa97ab842017-10-23 23:19:30 +000028#include <functional>
Marshall Clowd84736b2017-10-12 14:48:09 +000029#include <regex>
Eric Fiselier0aaa3272019-12-11 15:45:48 -050030#include <random>
Marshall Clow294dd862017-11-08 20:25:47 +000031#include <cassert>
Eric Fiselier0aaa3272019-12-11 15:45:48 -050032#include <cmath>
Marshall Clowbaa6fb32017-10-04 22:23:03 +000033
Marshall Clowa97ab842017-10-23 23:19:30 +000034#include <iostream>
35
Eric Fiselier0aaa3272019-12-11 15:45:48 -050036#ifdef NDEBUG
37#undef NDEBUG
38#endif
39#include <cassert>
Marshall Clow43ff7d92018-11-04 17:57:25 +000040// If we had C++14, we could use the four iterator version of is_permutation and equal
Marshall Clowbaa6fb32017-10-04 22:23:03 +000041
42namespace fuzzing {
43
Marshall Clow43ff7d92018-11-04 17:57:25 +000044// This is a struct we can use to test the stable_XXX algorithms.
45// perform the operation on the key, then check the order of the payload.
Marshall Clowbaa6fb32017-10-04 22:23:03 +000046
47struct stable_test {
Marshall Clow43ff7d92018-11-04 17:57:25 +000048 uint8_t key;
49 size_t payload;
50
51 stable_test(uint8_t k) : key(k), payload(0) {}
52 stable_test(uint8_t k, size_t p) : key(k), payload(p) {}
53 };
Marshall Clowbaa6fb32017-10-04 22:23:03 +000054
55void swap(stable_test &lhs, stable_test &rhs)
56{
Marshall Clow43ff7d92018-11-04 17:57:25 +000057 using std::swap;
58 swap(lhs.key, rhs.key);
59 swap(lhs.payload, rhs.payload);
Marshall Clowbaa6fb32017-10-04 22:23:03 +000060}
61
62struct key_less
63{
Marshall Clow43ff7d92018-11-04 17:57:25 +000064 bool operator () (const stable_test &lhs, const stable_test &rhs) const
65 {
66 return lhs.key < rhs.key;
67 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +000068};
69
70struct payload_less
71{
Marshall Clow43ff7d92018-11-04 17:57:25 +000072 bool operator () (const stable_test &lhs, const stable_test &rhs) const
73 {
74 return lhs.payload < rhs.payload;
75 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +000076};
77
78struct total_less
79{
Marshall Clow43ff7d92018-11-04 17:57:25 +000080 bool operator () (const stable_test &lhs, const stable_test &rhs) const
81 {
82 return lhs.key == rhs.key ? lhs.payload < rhs.payload : lhs.key < rhs.key;
83 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +000084};
85
86bool operator==(const stable_test &lhs, const stable_test &rhs)
Marshall Clow43ff7d92018-11-04 17:57:25 +000087{
88 return lhs.key == rhs.key && lhs.payload == rhs.payload;
Marshall Clowbaa6fb32017-10-04 22:23:03 +000089}
90
91
92template<typename T>
93struct is_even
94{
Marshall Clow43ff7d92018-11-04 17:57:25 +000095 bool operator () (const T &t) const
96 {
97 return t % 2 == 0;
98 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +000099};
100
101
102template<>
103struct is_even<stable_test>
104{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000105 bool operator () (const stable_test &t) const
106 {
107 return t.key % 2 == 0;
108 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000109};
110
Marshall Clow974677c2017-10-30 19:51:58 +0000111typedef std::vector<uint8_t> Vec;
112typedef std::vector<stable_test> StableVec;
Marshall Clow161681a2018-01-19 03:17:45 +0000113typedef StableVec::const_iterator SVIter;
114
Marshall Clow43ff7d92018-11-04 17:57:25 +0000115// Cheap version of is_permutation
116// Builds a set of buckets for each of the key values.
117// Sums all the payloads.
118// Not 100% perfect, but _way_ faster
Marshall Clow161681a2018-01-19 03:17:45 +0000119bool is_permutation(SVIter first1, SVIter last1, SVIter first2)
120{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000121 size_t xBuckets[256] = {0};
122 size_t xPayloads[256] = {0};
123 size_t yBuckets[256] = {0};
124 size_t yPayloads[256] = {0};
Marshall Clow161681a2018-01-19 03:17:45 +0000125
Marshall Clow43ff7d92018-11-04 17:57:25 +0000126 for (; first1 != last1; ++first1, ++first2)
127 {
128 xBuckets [first1->key]++;
129 xPayloads[first1->key] += first1->payload;
Marshall Clow161681a2018-01-19 03:17:45 +0000130
Marshall Clow43ff7d92018-11-04 17:57:25 +0000131 yBuckets [first2->key]++;
132 yPayloads[first2->key] += first2->payload;
133 }
134
135 for (size_t i = 0; i < 256; ++i)
136 {
137 if (xBuckets[i] != yBuckets[i])
138 return false;
139 if (xPayloads[i] != yPayloads[i])
140 return false;
141 }
142
143 return true;
Marshall Clow161681a2018-01-19 03:17:45 +0000144}
145
146template <typename Iter1, typename Iter2>
147bool is_permutation(Iter1 first1, Iter1 last1, Iter2 first2)
148{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000149 static_assert((std::is_same<typename std::iterator_traits<Iter1>::value_type, uint8_t>::value), "");
150 static_assert((std::is_same<typename std::iterator_traits<Iter2>::value_type, uint8_t>::value), "");
Marshall Clow161681a2018-01-19 03:17:45 +0000151
Marshall Clow43ff7d92018-11-04 17:57:25 +0000152 size_t xBuckets[256] = {0};
153 size_t yBuckets[256] = {0};
154
155 for (; first1 != last1; ++first1, ++first2)
156 {
157 xBuckets [*first1]++;
158 yBuckets [*first2]++;
159 }
160
161 for (size_t i = 0; i < 256; ++i)
162 if (xBuckets[i] != yBuckets[i])
163 return false;
164
165 return true;
Marshall Clow161681a2018-01-19 03:17:45 +0000166}
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000167
Marshall Clow43ff7d92018-11-04 17:57:25 +0000168// == sort ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000169int sort(const uint8_t *data, size_t size)
170{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000171 Vec working(data, data + size);
172 std::sort(working.begin(), working.end());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000173
Marshall Clow43ff7d92018-11-04 17:57:25 +0000174 if (!std::is_sorted(working.begin(), working.end())) return 1;
175 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
176 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000177}
178
179
Marshall Clow43ff7d92018-11-04 17:57:25 +0000180// == stable_sort ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000181int stable_sort(const uint8_t *data, size_t size)
182{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000183 StableVec input;
184 for (size_t i = 0; i < size; ++i)
185 input.push_back(stable_test(data[i], i));
186 StableVec working = input;
187 std::stable_sort(working.begin(), working.end(), key_less());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000188
Marshall Clow43ff7d92018-11-04 17:57:25 +0000189 if (!std::is_sorted(working.begin(), working.end(), key_less())) return 1;
190 auto iter = working.begin();
191 while (iter != working.end())
192 {
193 auto range = std::equal_range(iter, working.end(), *iter, key_less());
194 if (!std::is_sorted(range.first, range.second, total_less())) return 2;
195 iter = range.second;
196 }
197 if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99;
198 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000199}
200
Marshall Clow43ff7d92018-11-04 17:57:25 +0000201// == partition ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000202int partition(const uint8_t *data, size_t size)
203{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000204 Vec working(data, data + size);
205 auto iter = std::partition(working.begin(), working.end(), is_even<uint8_t>());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000206
Marshall Clow43ff7d92018-11-04 17:57:25 +0000207 if (!std::all_of (working.begin(), iter, is_even<uint8_t>())) return 1;
208 if (!std::none_of(iter, working.end(), is_even<uint8_t>())) return 2;
209 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
210 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000211}
212
213
Marshall Clow43ff7d92018-11-04 17:57:25 +0000214// == partition_copy ==
Marshall Clow974677c2017-10-30 19:51:58 +0000215int partition_copy(const uint8_t *data, size_t size)
216{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000217 Vec v1, v2;
218 auto iter = std::partition_copy(data, data + size,
219 std::back_inserter<Vec>(v1), std::back_inserter<Vec>(v2),
220 is_even<uint8_t>());
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500221 ((void)iter);
Marshall Clow43ff7d92018-11-04 17:57:25 +0000222// The two vectors should add up to the original size
223 if (v1.size() + v2.size() != size) return 1;
Marshall Clow974677c2017-10-30 19:51:58 +0000224
Marshall Clow43ff7d92018-11-04 17:57:25 +0000225// All of the even values should be in the first vector, and none in the second
226 if (!std::all_of (v1.begin(), v1.end(), is_even<uint8_t>())) return 2;
227 if (!std::none_of(v2.begin(), v2.end(), is_even<uint8_t>())) return 3;
Marshall Clow974677c2017-10-30 19:51:58 +0000228
Marshall Clow43ff7d92018-11-04 17:57:25 +0000229// Every value in both vectors has to be in the original
230
231// Make a copy of the input, and sort it
232 Vec v0{data, data + size};
233 std::sort(v0.begin(), v0.end());
234
235// Sort each vector and ensure that all of the elements appear in the original input
236 std::sort(v1.begin(), v1.end());
237 if (!std::includes(v0.begin(), v0.end(), v1.begin(), v1.end())) return 4;
238
239 std::sort(v2.begin(), v2.end());
240 if (!std::includes(v0.begin(), v0.end(), v2.begin(), v2.end())) return 5;
241
242// This, while simple, is really slow - 20 seconds on a 500K element input.
243// for (auto v: v1)
244// if (std::find(data, data + size, v) == data + size) return 4;
245//
246// for (auto v: v2)
247// if (std::find(data, data + size, v) == data + size) return 5;
248
249 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000250}
251
Marshall Clow43ff7d92018-11-04 17:57:25 +0000252// == stable_partition ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000253int stable_partition (const uint8_t *data, size_t size)
254{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000255 StableVec input;
256 for (size_t i = 0; i < size; ++i)
257 input.push_back(stable_test(data[i], i));
258 StableVec working = input;
259 auto iter = std::stable_partition(working.begin(), working.end(), is_even<stable_test>());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000260
Marshall Clow43ff7d92018-11-04 17:57:25 +0000261 if (!std::all_of (working.begin(), iter, is_even<stable_test>())) return 1;
262 if (!std::none_of(iter, working.end(), is_even<stable_test>())) return 2;
263 if (!std::is_sorted(working.begin(), iter, payload_less())) return 3;
264 if (!std::is_sorted(iter, working.end(), payload_less())) return 4;
265 if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99;
266 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000267}
268
Marshall Clow43ff7d92018-11-04 17:57:25 +0000269// == nth_element ==
270// use the first element as a position into the data
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000271int nth_element (const uint8_t *data, size_t size)
272{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000273 if (size <= 1) return 0;
274 const size_t partition_point = data[0] % size;
275 Vec working(data + 1, data + size);
276 const auto partition_iter = working.begin() + partition_point;
277 std::nth_element(working.begin(), partition_iter, working.end());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000278
Marshall Clow43ff7d92018-11-04 17:57:25 +0000279// nth may be the end iterator, in this case nth_element has no effect.
280 if (partition_iter == working.end())
281 {
282 if (!std::equal(data + 1, data + size, working.begin())) return 98;
283 }
284 else
285 {
286 const uint8_t nth = *partition_iter;
287 if (!std::all_of(working.begin(), partition_iter, [=](uint8_t v) { return v <= nth; }))
288 return 1;
289 if (!std::all_of(partition_iter, working.end(), [=](uint8_t v) { return v >= nth; }))
290 return 2;
291 if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99;
292 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000293
Marshall Clow43ff7d92018-11-04 17:57:25 +0000294 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000295}
296
Marshall Clow43ff7d92018-11-04 17:57:25 +0000297// == partial_sort ==
298// use the first element as a position into the data
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000299int partial_sort (const uint8_t *data, size_t size)
300{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000301 if (size <= 1) return 0;
302 const size_t sort_point = data[0] % size;
303 Vec working(data + 1, data + size);
304 const auto sort_iter = working.begin() + sort_point;
305 std::partial_sort(working.begin(), sort_iter, working.end());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000306
Marshall Clow43ff7d92018-11-04 17:57:25 +0000307 if (sort_iter != working.end())
308 {
309 const uint8_t nth = *std::min_element(sort_iter, working.end());
310 if (!std::all_of(working.begin(), sort_iter, [=](uint8_t v) { return v <= nth; }))
311 return 1;
312 if (!std::all_of(sort_iter, working.end(), [=](uint8_t v) { return v >= nth; }))
313 return 2;
314 }
315 if (!std::is_sorted(working.begin(), sort_iter)) return 3;
316 if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000317
Marshall Clow43ff7d92018-11-04 17:57:25 +0000318 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000319}
320
Marshall Clowd84736b2017-10-12 14:48:09 +0000321
Marshall Clow43ff7d92018-11-04 17:57:25 +0000322// == partial_sort_copy ==
323// use the first element as a count
Marshall Clow974677c2017-10-30 19:51:58 +0000324int partial_sort_copy (const uint8_t *data, size_t size)
325{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000326 if (size <= 1) return 0;
327 const size_t num_results = data[0] % size;
328 Vec results(num_results);
329 (void) std::partial_sort_copy(data + 1, data + size, results.begin(), results.end());
Marshall Clowd84736b2017-10-12 14:48:09 +0000330
Marshall Clow43ff7d92018-11-04 17:57:25 +0000331// The results have to be sorted
332 if (!std::is_sorted(results.begin(), results.end())) return 1;
333// All the values in results have to be in the original data
334 for (auto v: results)
335 if (std::find(data + 1, data + size, v) == data + size) return 2;
Marshall Clow974677c2017-10-30 19:51:58 +0000336
Marshall Clow43ff7d92018-11-04 17:57:25 +0000337// The things in results have to be the smallest N in the original data
338 Vec sorted(data + 1, data + size);
339 std::sort(sorted.begin(), sorted.end());
340 if (!std::equal(results.begin(), results.end(), sorted.begin())) return 3;
341 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000342}
343
Marshall Clow43ff7d92018-11-04 17:57:25 +0000344// The second sequence has been "uniqued"
Marshall Clow974677c2017-10-30 19:51:58 +0000345template <typename Iter1, typename Iter2>
346static bool compare_unique(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2)
347{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000348 assert(first1 != last1 && first2 != last2);
349 if (*first1 != *first2) return false;
Marshall Clow974677c2017-10-30 19:51:58 +0000350
Marshall Clow43ff7d92018-11-04 17:57:25 +0000351 uint8_t last_value = *first1;
352 ++first1; ++first2;
353 while(first1 != last1 && first2 != last2)
354 {
355 // Skip over dups in the first sequence
356 while (*first1 == last_value)
357 if (++first1 == last1) return false;
358 if (*first1 != *first2) return false;
359 last_value = *first1;
360 ++first1; ++first2;
361 }
Marshall Clow974677c2017-10-30 19:51:58 +0000362
Marshall Clow43ff7d92018-11-04 17:57:25 +0000363// Still stuff left in the 'uniqued' sequence - oops
364 if (first1 == last1 && first2 != last2) return false;
Marshall Clow974677c2017-10-30 19:51:58 +0000365
Marshall Clow43ff7d92018-11-04 17:57:25 +0000366// Still stuff left in the original sequence - better be all the same
367 while (first1 != last1)
368 {
369 if (*first1 != last_value) return false;
370 ++first1;
371 }
372 return true;
Marshall Clow974677c2017-10-30 19:51:58 +0000373}
374
Marshall Clow43ff7d92018-11-04 17:57:25 +0000375// == unique ==
Marshall Clow974677c2017-10-30 19:51:58 +0000376int unique (const uint8_t *data, size_t size)
377{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000378 Vec working(data, data + size);
379 std::sort(working.begin(), working.end());
380 Vec results = working;
381 Vec::iterator new_end = std::unique(results.begin(), results.end());
382 Vec::iterator it; // scratch iterator
Marshall Clow974677c2017-10-30 19:51:58 +0000383
Marshall Clow43ff7d92018-11-04 17:57:25 +0000384// Check the size of the unique'd sequence.
385// it should only be zero if the input sequence was empty.
386 if (results.begin() == new_end)
387 return working.size() == 0 ? 0 : 1;
388
389// 'results' is sorted
390 if (!std::is_sorted(results.begin(), new_end)) return 2;
391
392// All the elements in 'results' must be different
393 it = results.begin();
394 uint8_t prev_value = *it++;
395 for (; it != new_end; ++it)
396 {
397 if (*it == prev_value) return 3;
398 prev_value = *it;
399 }
400
401// Every element in 'results' must be in 'working'
402 for (it = results.begin(); it != new_end; ++it)
403 if (std::find(working.begin(), working.end(), *it) == working.end())
404 return 4;
405
406// Every element in 'working' must be in 'results'
407 for (auto v : working)
408 if (std::find(results.begin(), new_end, v) == new_end)
409 return 5;
410
411 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000412}
413
Marshall Clow43ff7d92018-11-04 17:57:25 +0000414// == unique_copy ==
Marshall Clow974677c2017-10-30 19:51:58 +0000415int unique_copy (const uint8_t *data, size_t size)
416{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000417 Vec working(data, data + size);
418 std::sort(working.begin(), working.end());
419 Vec results;
420 (void) std::unique_copy(working.begin(), working.end(),
421 std::back_inserter<Vec>(results));
422 Vec::iterator it; // scratch iterator
Marshall Clow974677c2017-10-30 19:51:58 +0000423
Marshall Clow43ff7d92018-11-04 17:57:25 +0000424// Check the size of the unique'd sequence.
425// it should only be zero if the input sequence was empty.
426 if (results.size() == 0)
427 return working.size() == 0 ? 0 : 1;
428
429// 'results' is sorted
430 if (!std::is_sorted(results.begin(), results.end())) return 2;
431
432// All the elements in 'results' must be different
433 it = results.begin();
434 uint8_t prev_value = *it++;
435 for (; it != results.end(); ++it)
436 {
437 if (*it == prev_value) return 3;
438 prev_value = *it;
439 }
440
441// Every element in 'results' must be in 'working'
442 for (auto v : results)
443 if (std::find(working.begin(), working.end(), v) == working.end())
444 return 4;
445
446// Every element in 'working' must be in 'results'
447 for (auto v : working)
448 if (std::find(results.begin(), results.end(), v) == results.end())
449 return 5;
450
451 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000452}
453
454
Marshall Clow43ff7d92018-11-04 17:57:25 +0000455// -- regex fuzzers
Marshall Clowd84736b2017-10-12 14:48:09 +0000456static int regex_helper(const uint8_t *data, size_t size, std::regex::flag_type flag)
457{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000458 if (size > 0)
459 {
460 try
461 {
462 std::string s((const char *)data, size);
463 std::regex re(s, flag);
464 return std::regex_match(s, re) ? 1 : 0;
465 }
466 catch (std::regex_error &ex) {}
467 }
468 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000469}
470
471
472int regex_ECMAScript (const uint8_t *data, size_t size)
473{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000474 (void) regex_helper(data, size, std::regex_constants::ECMAScript);
475 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000476}
477
478int regex_POSIX (const uint8_t *data, size_t size)
479{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000480 (void) regex_helper(data, size, std::regex_constants::basic);
481 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000482}
483
484int regex_extended (const uint8_t *data, size_t size)
485{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000486 (void) regex_helper(data, size, std::regex_constants::extended);
487 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000488}
489
490int regex_awk (const uint8_t *data, size_t size)
491{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000492 (void) regex_helper(data, size, std::regex_constants::awk);
493 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000494}
495
496int regex_grep (const uint8_t *data, size_t size)
497{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000498 (void) regex_helper(data, size, std::regex_constants::grep);
499 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000500}
501
502int regex_egrep (const uint8_t *data, size_t size)
503{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000504 (void) regex_helper(data, size, std::regex_constants::egrep);
505 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000506}
507
Marshall Clow43ff7d92018-11-04 17:57:25 +0000508// -- heap fuzzers
Marshall Clowa97ab842017-10-23 23:19:30 +0000509int make_heap (const uint8_t *data, size_t size)
510{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000511 Vec working(data, data + size);
512 std::make_heap(working.begin(), working.end());
Marshall Clowa97ab842017-10-23 23:19:30 +0000513
Marshall Clow43ff7d92018-11-04 17:57:25 +0000514 if (!std::is_heap(working.begin(), working.end())) return 1;
515 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
516 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000517}
518
519int push_heap (const uint8_t *data, size_t size)
520{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000521 if (size < 2) return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000522
Marshall Clow43ff7d92018-11-04 17:57:25 +0000523// Make a heap from the first half of the data
524 Vec working(data, data + size);
525 auto iter = working.begin() + (size / 2);
526 std::make_heap(working.begin(), iter);
527 if (!std::is_heap(working.begin(), iter)) return 1;
Marshall Clowa97ab842017-10-23 23:19:30 +0000528
Marshall Clow43ff7d92018-11-04 17:57:25 +0000529// Now push the rest onto the heap, one at a time
530 ++iter;
531 for (; iter != working.end(); ++iter) {
532 std::push_heap(working.begin(), iter);
533 if (!std::is_heap(working.begin(), iter)) return 2;
534 }
Marshall Clowa97ab842017-10-23 23:19:30 +0000535
Marshall Clow43ff7d92018-11-04 17:57:25 +0000536 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
537 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000538}
539
540int pop_heap (const uint8_t *data, size_t size)
541{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000542 if (size < 2) return 0;
543 Vec working(data, data + size);
544 std::make_heap(working.begin(), working.end());
Marshall Clowa97ab842017-10-23 23:19:30 +0000545
Marshall Clow43ff7d92018-11-04 17:57:25 +0000546// Pop things off, one at a time
547 auto iter = --working.end();
548 while (iter != working.begin()) {
549 std::pop_heap(working.begin(), iter);
550 if (!std::is_heap(working.begin(), --iter)) return 2;
551 }
Marshall Clowa97ab842017-10-23 23:19:30 +0000552
Marshall Clow43ff7d92018-11-04 17:57:25 +0000553 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000554}
555
556
Marshall Clow43ff7d92018-11-04 17:57:25 +0000557// -- search fuzzers
Marshall Clowa97ab842017-10-23 23:19:30 +0000558int search (const uint8_t *data, size_t size)
559{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000560 if (size < 2) return 0;
561
562 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
563 assert(pat_size <= size - 1);
564 const uint8_t *pat_begin = data + 1;
565 const uint8_t *pat_end = pat_begin + pat_size;
566 const uint8_t *data_end = data + size;
567 assert(pat_end <= data_end);
568// std::cerr << "data[0] = " << size_t(data[0]) << " ";
569// std::cerr << "Pattern size = " << pat_size << "; corpus is " << size - 1 << std::endl;
570 auto it = std::search(pat_end, data_end, pat_begin, pat_end);
571 if (it != data_end) // not found
572 if (!std::equal(pat_begin, pat_end, it))
573 return 1;
574 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000575}
576
577template <typename S>
578static int search_helper (const uint8_t *data, size_t size)
579{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000580 if (size < 2) return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000581
Marshall Clow43ff7d92018-11-04 17:57:25 +0000582 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
583 const uint8_t *pat_begin = data + 1;
584 const uint8_t *pat_end = pat_begin + pat_size;
585 const uint8_t *data_end = data + size;
586
587 auto it = std::search(pat_end, data_end, S(pat_begin, pat_end));
588 if (it != data_end) // not found
589 if (!std::equal(pat_begin, pat_end, it))
590 return 1;
591 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000592}
593
Marshall Clow43ff7d92018-11-04 17:57:25 +0000594// These are still in std::experimental
Marshall Clowa97ab842017-10-23 23:19:30 +0000595// int search_boyer_moore (const uint8_t *data, size_t size)
596// {
Marshall Clow43ff7d92018-11-04 17:57:25 +0000597// return search_helper<std::boyer_moore_searcher<const uint8_t *>>(data, size);
Marshall Clowa97ab842017-10-23 23:19:30 +0000598// }
Marshall Clow43ff7d92018-11-04 17:57:25 +0000599//
Marshall Clowa97ab842017-10-23 23:19:30 +0000600// int search_boyer_moore_horspool (const uint8_t *data, size_t size)
601// {
Marshall Clow43ff7d92018-11-04 17:57:25 +0000602// return search_helper<std::boyer_moore_horspool_searcher<const uint8_t *>>(data, size);
Marshall Clowa97ab842017-10-23 23:19:30 +0000603// }
604
Marshall Clow974677c2017-10-30 19:51:58 +0000605
Marshall Clow43ff7d92018-11-04 17:57:25 +0000606// -- set operation fuzzers
Marshall Clow974677c2017-10-30 19:51:58 +0000607template <typename S>
608static void set_helper (const uint8_t *data, size_t size, Vec &v1, Vec &v2)
609{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000610 assert(size > 1);
Marshall Clow974677c2017-10-30 19:51:58 +0000611
Marshall Clow43ff7d92018-11-04 17:57:25 +0000612 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
613 const uint8_t *pat_begin = data + 1;
614 const uint8_t *pat_end = pat_begin + pat_size;
615 const uint8_t *data_end = data + size;
616 v1.assign(pat_begin, pat_end);
617 v2.assign(pat_end, data_end);
618
619 std::sort(v1.begin(), v1.end());
620 std::sort(v2.begin(), v2.end());
Marshall Clow974677c2017-10-30 19:51:58 +0000621}
622
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500623enum class ParamKind {
624 OneValue,
625 TwoValues,
626 PointerRange
627};
628
629template <class IntT>
630std::vector<IntT> GetValues(const uint8_t *data, size_t size) {
631 std::vector<IntT> result;
632 while (size >= sizeof(IntT)) {
633 IntT tmp;
634 memcpy(&tmp, data, sizeof(IntT));
635 size -= sizeof(IntT);
636 data += sizeof(IntT);
637 result.push_back(tmp);
638 }
639 return result;
640}
641
642enum InitKind {
643 Default,
644 DoubleOnly,
645 VectorDouble,
646 VectorResultType
647};
648
649template <class Dist>
650struct ParamTypeHelper {
651 using ParamT = typename Dist::param_type;
652 using ResultT = typename Dist::result_type;
653 static_assert(std::is_same<ResultT, typename ParamT::distribution_type::result_type>::value, "");
654 static ParamT Create(const uint8_t* data, size_t size, bool &OK) {
655
656 if constexpr (std::is_constructible<ParamT, ResultT*, ResultT*, ResultT*>::value)
657 return CreateVectorResult(data, size, OK);
658 else if constexpr (std::is_constructible<ParamT, double*, double*>::value)
659 return CreateVectorDouble(data, size, OK);
660 else
661 return CreateDefault(data, size, OK);
662 }
663
664
665static ParamT
666CreateVectorResult(const uint8_t *data, size_t size, bool &OK) {
667 auto Input = GetValues<ResultT>(data, size);
668 OK = false;
669 if (Input.size() < 10)
670 return ParamT{};
671 OK = true;
672 auto Beg = Input.begin();
673 auto End = Input.end();
674 auto Mid = Beg + ((End - Beg) / 2);
675
676 assert(Mid - Beg <= (End - Mid));
677 ParamT p(Beg, Mid, Mid);
678 return p;
679}
680
681 static ParamT
682 CreateVectorDouble(const uint8_t *data, size_t size, bool &OK) {
683 auto Input = GetValues<double>(data, size);
684
685 OK = true;
686 auto Beg = Input.begin();
687 auto End = Input.end();
688
689 ParamT p(Beg, End);
690 return p;
691 }
692
693
694 static ParamT
695 CreateDefault(const uint8_t *data, size_t size, bool &OK) {
696 OK = false;
697 if (size < sizeof(ParamT))
698 return ParamT{};
699 OK = true;
700 ParamT input;
701 memcpy(&input, data, sizeof(ParamT));
702 return input;
703 }
704
705};
706
707
708
709
710template <class IntT>
711struct ParamTypeHelper<std::poisson_distribution<IntT>> {
712 using Dist = std::poisson_distribution<IntT>;
713 using ParamT = typename Dist::param_type;
714 using ResultT = typename Dist::result_type;
715
716 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
717 OK = false;
718 auto vals = GetValues<double>(data, size);
719 if (vals.empty() || std::isnan(vals[0]) || std::isnan(std::abs(vals[0])) || vals[0] < 0 )
720 return ParamT{};
721 OK = true;
722 //std::cerr << "Value: " << vals[0] << std::endl;
723 return ParamT{vals[0]};
724 }
725};
726
727
728template <class IntT>
729struct ParamTypeHelper<std::geometric_distribution<IntT>> {
730 using Dist = std::geometric_distribution<IntT>;
731 using ParamT = typename Dist::param_type;
732 using ResultT = typename Dist::result_type;
733
734 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
735 OK = false;
736 auto vals = GetValues<double>(data, size);
737 if (vals.empty() || std::isnan(vals[0]) || vals[0] < 0 )
738 return ParamT{};
739 OK = true;
740 // std::cerr << "Value: " << vals[0] << std::endl;
741 return ParamT{vals[0]};
742 }
743};
744
745
746template <class IntT>
747struct ParamTypeHelper<std::lognormal_distribution<IntT>> {
748 using Dist = std::lognormal_distribution<IntT>;
749 using ParamT = typename Dist::param_type;
750 using ResultT = typename Dist::result_type;
751
752 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
753 OK = false;
754 auto vals = GetValues<ResultT>(data, size);
755 if (vals.size() < 2 )
756 return ParamT{};
757 OK = true;
758 return ParamT{vals[0], vals[1]};
759 }
760};
761
762
763template <>
764struct ParamTypeHelper<std::bernoulli_distribution> {
765 using Dist = std::bernoulli_distribution;
766 using ParamT = typename Dist::param_type;
767 using ResultT = typename Dist::result_type;
768
769 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
770 OK = false;
771 auto vals = GetValues<double>(data, size);
772 if (vals.empty())
773 return ParamT{};
774 OK = true;
775 return ParamT{vals[0]};
776 }
777};
778
779template <class Distribution>
780int random_distribution_helper(const uint8_t *data, size_t size) {
781
782 std::mt19937 engine;
783 using ParamT = typename Distribution::param_type;
784 bool OK;
785 ParamT p = ParamTypeHelper<Distribution>::Create(data, size, OK);
786 if (!OK)
787 return 0;
788 Distribution d(p);
789 volatile auto res = d(engine);
790 if (std::isnan(res))
791 return 1;
792 return 0;
793}
794
795#define DEFINE_RANDOM_TEST(name, ...) \
796int name(const uint8_t *data, size_t size) { \
797 return random_distribution_helper< std::name __VA_ARGS__ >(data, size); \
798}
799DEFINE_RANDOM_TEST(uniform_int_distribution,<std::int16_t>)
800DEFINE_RANDOM_TEST(uniform_real_distribution,<float>)
801DEFINE_RANDOM_TEST(bernoulli_distribution)
802DEFINE_RANDOM_TEST(poisson_distribution,<std::int16_t>)
803DEFINE_RANDOM_TEST(geometric_distribution,<std::int16_t>)
804DEFINE_RANDOM_TEST(binomial_distribution, <std::int16_t>)
805DEFINE_RANDOM_TEST(negative_binomial_distribution, <std::int16_t>)
806DEFINE_RANDOM_TEST(exponential_distribution, <float>)
807DEFINE_RANDOM_TEST(gamma_distribution, <float>)
808DEFINE_RANDOM_TEST(weibull_distribution, <float>)
809DEFINE_RANDOM_TEST(extreme_value_distribution, <float>)
810DEFINE_RANDOM_TEST(normal_distribution, <float>)
811DEFINE_RANDOM_TEST(lognormal_distribution, <float>)
812DEFINE_RANDOM_TEST(chi_squared_distribution, <float>)
813DEFINE_RANDOM_TEST(cauchy_distribution, <float>)
814DEFINE_RANDOM_TEST(fisher_f_distribution, <float>)
815DEFINE_RANDOM_TEST(student_t_distribution, <float>)
816DEFINE_RANDOM_TEST(discrete_distribution, <std::int16_t>)
817DEFINE_RANDOM_TEST(piecewise_constant_distribution, <float>)
818DEFINE_RANDOM_TEST(piecewise_linear_distribution, <float>)
819
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000820} // namespace fuzzing