blob: d036f0cbb8b8f0b2164988b2f552f793b1a1f4fa [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 {
Eric Fiseliera081edf2019-12-11 16:21:23 -0500460#ifndef _LIBCPP_NO_EXCEPTIONS
Marshall Clow43ff7d92018-11-04 17:57:25 +0000461 try
462 {
463 std::string s((const char *)data, size);
464 std::regex re(s, flag);
465 return std::regex_match(s, re) ? 1 : 0;
466 }
467 catch (std::regex_error &ex) {}
Eric Fiseliera081edf2019-12-11 16:21:23 -0500468#else
469 ((void)data);
470 ((void)size);
471 ((void)flag);
472#endif
Marshall Clow43ff7d92018-11-04 17:57:25 +0000473 }
474 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000475}
476
477
478int regex_ECMAScript (const uint8_t *data, size_t size)
479{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000480 (void) regex_helper(data, size, std::regex_constants::ECMAScript);
481 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000482}
483
484int regex_POSIX (const uint8_t *data, size_t size)
485{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000486 (void) regex_helper(data, size, std::regex_constants::basic);
487 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000488}
489
490int regex_extended (const uint8_t *data, size_t size)
491{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000492 (void) regex_helper(data, size, std::regex_constants::extended);
493 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000494}
495
496int regex_awk (const uint8_t *data, size_t size)
497{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000498 (void) regex_helper(data, size, std::regex_constants::awk);
499 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000500}
501
502int regex_grep (const uint8_t *data, size_t size)
503{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000504 (void) regex_helper(data, size, std::regex_constants::grep);
505 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000506}
507
508int regex_egrep (const uint8_t *data, size_t size)
509{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000510 (void) regex_helper(data, size, std::regex_constants::egrep);
511 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000512}
513
Marshall Clow43ff7d92018-11-04 17:57:25 +0000514// -- heap fuzzers
Marshall Clowa97ab842017-10-23 23:19:30 +0000515int make_heap (const uint8_t *data, size_t size)
516{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000517 Vec working(data, data + size);
518 std::make_heap(working.begin(), working.end());
Marshall Clowa97ab842017-10-23 23:19:30 +0000519
Marshall Clow43ff7d92018-11-04 17:57:25 +0000520 if (!std::is_heap(working.begin(), working.end())) return 1;
521 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
522 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000523}
524
525int push_heap (const uint8_t *data, size_t size)
526{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000527 if (size < 2) return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000528
Marshall Clow43ff7d92018-11-04 17:57:25 +0000529// Make a heap from the first half of the data
530 Vec working(data, data + size);
531 auto iter = working.begin() + (size / 2);
532 std::make_heap(working.begin(), iter);
533 if (!std::is_heap(working.begin(), iter)) return 1;
Marshall Clowa97ab842017-10-23 23:19:30 +0000534
Marshall Clow43ff7d92018-11-04 17:57:25 +0000535// Now push the rest onto the heap, one at a time
536 ++iter;
537 for (; iter != working.end(); ++iter) {
538 std::push_heap(working.begin(), iter);
539 if (!std::is_heap(working.begin(), iter)) return 2;
540 }
Marshall Clowa97ab842017-10-23 23:19:30 +0000541
Marshall Clow43ff7d92018-11-04 17:57:25 +0000542 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
543 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000544}
545
546int pop_heap (const uint8_t *data, size_t size)
547{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000548 if (size < 2) return 0;
549 Vec working(data, data + size);
550 std::make_heap(working.begin(), working.end());
Marshall Clowa97ab842017-10-23 23:19:30 +0000551
Marshall Clow43ff7d92018-11-04 17:57:25 +0000552// Pop things off, one at a time
553 auto iter = --working.end();
554 while (iter != working.begin()) {
555 std::pop_heap(working.begin(), iter);
556 if (!std::is_heap(working.begin(), --iter)) return 2;
557 }
Marshall Clowa97ab842017-10-23 23:19:30 +0000558
Marshall Clow43ff7d92018-11-04 17:57:25 +0000559 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000560}
561
562
Marshall Clow43ff7d92018-11-04 17:57:25 +0000563// -- search fuzzers
Marshall Clowa97ab842017-10-23 23:19:30 +0000564int search (const uint8_t *data, size_t size)
565{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000566 if (size < 2) return 0;
567
568 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
569 assert(pat_size <= size - 1);
570 const uint8_t *pat_begin = data + 1;
571 const uint8_t *pat_end = pat_begin + pat_size;
572 const uint8_t *data_end = data + size;
573 assert(pat_end <= data_end);
574// std::cerr << "data[0] = " << size_t(data[0]) << " ";
575// std::cerr << "Pattern size = " << pat_size << "; corpus is " << size - 1 << std::endl;
576 auto it = std::search(pat_end, data_end, pat_begin, pat_end);
577 if (it != data_end) // not found
578 if (!std::equal(pat_begin, pat_end, it))
579 return 1;
580 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000581}
582
583template <typename S>
584static int search_helper (const uint8_t *data, size_t size)
585{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000586 if (size < 2) return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000587
Marshall Clow43ff7d92018-11-04 17:57:25 +0000588 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
589 const uint8_t *pat_begin = data + 1;
590 const uint8_t *pat_end = pat_begin + pat_size;
591 const uint8_t *data_end = data + size;
592
593 auto it = std::search(pat_end, data_end, S(pat_begin, pat_end));
594 if (it != data_end) // not found
595 if (!std::equal(pat_begin, pat_end, it))
596 return 1;
597 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000598}
599
Marshall Clow43ff7d92018-11-04 17:57:25 +0000600// These are still in std::experimental
Marshall Clowa97ab842017-10-23 23:19:30 +0000601// int search_boyer_moore (const uint8_t *data, size_t size)
602// {
Marshall Clow43ff7d92018-11-04 17:57:25 +0000603// return search_helper<std::boyer_moore_searcher<const uint8_t *>>(data, size);
Marshall Clowa97ab842017-10-23 23:19:30 +0000604// }
Marshall Clow43ff7d92018-11-04 17:57:25 +0000605//
Marshall Clowa97ab842017-10-23 23:19:30 +0000606// int search_boyer_moore_horspool (const uint8_t *data, size_t size)
607// {
Marshall Clow43ff7d92018-11-04 17:57:25 +0000608// return search_helper<std::boyer_moore_horspool_searcher<const uint8_t *>>(data, size);
Marshall Clowa97ab842017-10-23 23:19:30 +0000609// }
610
Marshall Clow974677c2017-10-30 19:51:58 +0000611
Marshall Clow43ff7d92018-11-04 17:57:25 +0000612// -- set operation fuzzers
Marshall Clow974677c2017-10-30 19:51:58 +0000613template <typename S>
614static void set_helper (const uint8_t *data, size_t size, Vec &v1, Vec &v2)
615{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000616 assert(size > 1);
Marshall Clow974677c2017-10-30 19:51:58 +0000617
Marshall Clow43ff7d92018-11-04 17:57:25 +0000618 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
619 const uint8_t *pat_begin = data + 1;
620 const uint8_t *pat_end = pat_begin + pat_size;
621 const uint8_t *data_end = data + size;
622 v1.assign(pat_begin, pat_end);
623 v2.assign(pat_end, data_end);
624
625 std::sort(v1.begin(), v1.end());
626 std::sort(v2.begin(), v2.end());
Marshall Clow974677c2017-10-30 19:51:58 +0000627}
628
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500629enum class ParamKind {
630 OneValue,
631 TwoValues,
632 PointerRange
633};
634
635template <class IntT>
636std::vector<IntT> GetValues(const uint8_t *data, size_t size) {
637 std::vector<IntT> result;
638 while (size >= sizeof(IntT)) {
639 IntT tmp;
640 memcpy(&tmp, data, sizeof(IntT));
641 size -= sizeof(IntT);
642 data += sizeof(IntT);
643 result.push_back(tmp);
644 }
645 return result;
646}
647
648enum InitKind {
649 Default,
650 DoubleOnly,
651 VectorDouble,
652 VectorResultType
653};
654
Eric Fiselierd4021252019-12-11 16:36:21 -0500655
656
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500657template <class Dist>
658struct ParamTypeHelper {
659 using ParamT = typename Dist::param_type;
660 using ResultT = typename Dist::result_type;
661 static_assert(std::is_same<ResultT, typename ParamT::distribution_type::result_type>::value, "");
662 static ParamT Create(const uint8_t* data, size_t size, bool &OK) {
663
Eric Fiselierd4021252019-12-11 16:36:21 -0500664 constexpr bool select_vector_result = std::is_constructible<ParamT, ResultT*, ResultT*, ResultT*>::value;
665 constexpr bool select_vector_double = std::is_constructible<ParamT, double*, double*>::value;
666 constexpr int selector = select_vector_result ? 0 : (select_vector_double ? 1 : 2);
667 return DispatchAndCreate(std::integral_constant<int, selector>{}, data, size, OK);
668
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500669 }
670
Eric Fiselierd4021252019-12-11 16:36:21 -0500671 static ParamT DispatchAndCreate(std::integral_constant<int, 0>, const uint8_t *data, size_t size, bool &OK) {
672 return CreateVectorResult(data, size, OK);
673 }
674 static ParamT DispatchAndCreate(std::integral_constant<int, 1>, const uint8_t *data, size_t size, bool &OK) {
675 return CreateVectorDouble(data, size, OK);
676 }
677 static ParamT DispatchAndCreate(std::integral_constant<int, 2>, const uint8_t *data, size_t size, bool &OK) {
678 return CreateDefault(data, size, OK);
679 }
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500680
Eric Fiselierd4021252019-12-11 16:36:21 -0500681static ParamT
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500682CreateVectorResult(const uint8_t *data, size_t size, bool &OK) {
683 auto Input = GetValues<ResultT>(data, size);
684 OK = false;
685 if (Input.size() < 10)
686 return ParamT{};
687 OK = true;
688 auto Beg = Input.begin();
689 auto End = Input.end();
690 auto Mid = Beg + ((End - Beg) / 2);
691
692 assert(Mid - Beg <= (End - Mid));
693 ParamT p(Beg, Mid, Mid);
694 return p;
695}
696
697 static ParamT
698 CreateVectorDouble(const uint8_t *data, size_t size, bool &OK) {
699 auto Input = GetValues<double>(data, size);
700
701 OK = true;
702 auto Beg = Input.begin();
703 auto End = Input.end();
704
705 ParamT p(Beg, End);
706 return p;
707 }
708
709
710 static ParamT
711 CreateDefault(const uint8_t *data, size_t size, bool &OK) {
712 OK = false;
713 if (size < sizeof(ParamT))
714 return ParamT{};
715 OK = true;
716 ParamT input;
717 memcpy(&input, data, sizeof(ParamT));
718 return input;
719 }
720
721};
722
723
724
725
726template <class IntT>
727struct ParamTypeHelper<std::poisson_distribution<IntT>> {
728 using Dist = std::poisson_distribution<IntT>;
729 using ParamT = typename Dist::param_type;
730 using ResultT = typename Dist::result_type;
731
732 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
733 OK = false;
734 auto vals = GetValues<double>(data, size);
735 if (vals.empty() || std::isnan(vals[0]) || std::isnan(std::abs(vals[0])) || vals[0] < 0 )
736 return ParamT{};
737 OK = true;
738 //std::cerr << "Value: " << vals[0] << std::endl;
739 return ParamT{vals[0]};
740 }
741};
742
743
744template <class IntT>
745struct ParamTypeHelper<std::geometric_distribution<IntT>> {
746 using Dist = std::geometric_distribution<IntT>;
747 using ParamT = typename Dist::param_type;
748 using ResultT = typename Dist::result_type;
749
750 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
751 OK = false;
752 auto vals = GetValues<double>(data, size);
753 if (vals.empty() || std::isnan(vals[0]) || vals[0] < 0 )
754 return ParamT{};
755 OK = true;
756 // std::cerr << "Value: " << vals[0] << std::endl;
757 return ParamT{vals[0]};
758 }
759};
760
761
762template <class IntT>
763struct ParamTypeHelper<std::lognormal_distribution<IntT>> {
764 using Dist = std::lognormal_distribution<IntT>;
765 using ParamT = typename Dist::param_type;
766 using ResultT = typename Dist::result_type;
767
768 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
769 OK = false;
770 auto vals = GetValues<ResultT>(data, size);
771 if (vals.size() < 2 )
772 return ParamT{};
773 OK = true;
774 return ParamT{vals[0], vals[1]};
775 }
776};
777
778
779template <>
780struct ParamTypeHelper<std::bernoulli_distribution> {
781 using Dist = std::bernoulli_distribution;
782 using ParamT = typename Dist::param_type;
783 using ResultT = typename Dist::result_type;
784
785 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
786 OK = false;
787 auto vals = GetValues<double>(data, size);
788 if (vals.empty())
789 return ParamT{};
790 OK = true;
791 return ParamT{vals[0]};
792 }
793};
794
795template <class Distribution>
796int random_distribution_helper(const uint8_t *data, size_t size) {
797
798 std::mt19937 engine;
799 using ParamT = typename Distribution::param_type;
800 bool OK;
801 ParamT p = ParamTypeHelper<Distribution>::Create(data, size, OK);
802 if (!OK)
803 return 0;
804 Distribution d(p);
805 volatile auto res = d(engine);
806 if (std::isnan(res))
807 return 1;
808 return 0;
809}
810
811#define DEFINE_RANDOM_TEST(name, ...) \
812int name(const uint8_t *data, size_t size) { \
813 return random_distribution_helper< std::name __VA_ARGS__ >(data, size); \
814}
815DEFINE_RANDOM_TEST(uniform_int_distribution,<std::int16_t>)
816DEFINE_RANDOM_TEST(uniform_real_distribution,<float>)
817DEFINE_RANDOM_TEST(bernoulli_distribution)
818DEFINE_RANDOM_TEST(poisson_distribution,<std::int16_t>)
819DEFINE_RANDOM_TEST(geometric_distribution,<std::int16_t>)
820DEFINE_RANDOM_TEST(binomial_distribution, <std::int16_t>)
821DEFINE_RANDOM_TEST(negative_binomial_distribution, <std::int16_t>)
822DEFINE_RANDOM_TEST(exponential_distribution, <float>)
823DEFINE_RANDOM_TEST(gamma_distribution, <float>)
824DEFINE_RANDOM_TEST(weibull_distribution, <float>)
825DEFINE_RANDOM_TEST(extreme_value_distribution, <float>)
826DEFINE_RANDOM_TEST(normal_distribution, <float>)
827DEFINE_RANDOM_TEST(lognormal_distribution, <float>)
828DEFINE_RANDOM_TEST(chi_squared_distribution, <float>)
829DEFINE_RANDOM_TEST(cauchy_distribution, <float>)
830DEFINE_RANDOM_TEST(fisher_f_distribution, <float>)
831DEFINE_RANDOM_TEST(student_t_distribution, <float>)
832DEFINE_RANDOM_TEST(discrete_distribution, <std::int16_t>)
833DEFINE_RANDOM_TEST(piecewise_constant_distribution, <float>)
834DEFINE_RANDOM_TEST(piecewise_linear_distribution, <float>)
835
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000836} // namespace fuzzing