blob: 7e58dba0c27fc5f179e8196b685d74f7d306412e [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
Eric Fiseliere4b1a852019-12-12 15:36:34 -050042#ifndef _LIBCPP_VERSION
43#error These test should be built with libc++ only.
44#endif
45
Marshall Clowbaa6fb32017-10-04 22:23:03 +000046namespace fuzzing {
47
Marshall Clow43ff7d92018-11-04 17:57:25 +000048// This is a struct we can use to test the stable_XXX algorithms.
49// perform the operation on the key, then check the order of the payload.
Marshall Clowbaa6fb32017-10-04 22:23:03 +000050
51struct stable_test {
Marshall Clow43ff7d92018-11-04 17:57:25 +000052 uint8_t key;
53 size_t payload;
54
55 stable_test(uint8_t k) : key(k), payload(0) {}
56 stable_test(uint8_t k, size_t p) : key(k), payload(p) {}
57 };
Marshall Clowbaa6fb32017-10-04 22:23:03 +000058
59void swap(stable_test &lhs, stable_test &rhs)
60{
Marshall Clow43ff7d92018-11-04 17:57:25 +000061 using std::swap;
62 swap(lhs.key, rhs.key);
63 swap(lhs.payload, rhs.payload);
Marshall Clowbaa6fb32017-10-04 22:23:03 +000064}
65
66struct key_less
67{
Marshall Clow43ff7d92018-11-04 17:57:25 +000068 bool operator () (const stable_test &lhs, const stable_test &rhs) const
69 {
70 return lhs.key < rhs.key;
71 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +000072};
73
74struct payload_less
75{
Marshall Clow43ff7d92018-11-04 17:57:25 +000076 bool operator () (const stable_test &lhs, const stable_test &rhs) const
77 {
78 return lhs.payload < rhs.payload;
79 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +000080};
81
82struct total_less
83{
Marshall Clow43ff7d92018-11-04 17:57:25 +000084 bool operator () (const stable_test &lhs, const stable_test &rhs) const
85 {
86 return lhs.key == rhs.key ? lhs.payload < rhs.payload : lhs.key < rhs.key;
87 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +000088};
89
90bool operator==(const stable_test &lhs, const stable_test &rhs)
Marshall Clow43ff7d92018-11-04 17:57:25 +000091{
92 return lhs.key == rhs.key && lhs.payload == rhs.payload;
Marshall Clowbaa6fb32017-10-04 22:23:03 +000093}
94
95
96template<typename T>
97struct is_even
98{
Marshall Clow43ff7d92018-11-04 17:57:25 +000099 bool operator () (const T &t) const
100 {
101 return t % 2 == 0;
102 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000103};
104
105
106template<>
107struct is_even<stable_test>
108{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000109 bool operator () (const stable_test &t) const
110 {
111 return t.key % 2 == 0;
112 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000113};
114
Marshall Clow974677c2017-10-30 19:51:58 +0000115typedef std::vector<uint8_t> Vec;
116typedef std::vector<stable_test> StableVec;
Marshall Clow161681a2018-01-19 03:17:45 +0000117typedef StableVec::const_iterator SVIter;
118
Marshall Clow43ff7d92018-11-04 17:57:25 +0000119// Cheap version of is_permutation
120// Builds a set of buckets for each of the key values.
121// Sums all the payloads.
122// Not 100% perfect, but _way_ faster
Marshall Clow161681a2018-01-19 03:17:45 +0000123bool is_permutation(SVIter first1, SVIter last1, SVIter first2)
124{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000125 size_t xBuckets[256] = {0};
126 size_t xPayloads[256] = {0};
127 size_t yBuckets[256] = {0};
128 size_t yPayloads[256] = {0};
Marshall Clow161681a2018-01-19 03:17:45 +0000129
Marshall Clow43ff7d92018-11-04 17:57:25 +0000130 for (; first1 != last1; ++first1, ++first2)
131 {
132 xBuckets [first1->key]++;
133 xPayloads[first1->key] += first1->payload;
Marshall Clow161681a2018-01-19 03:17:45 +0000134
Marshall Clow43ff7d92018-11-04 17:57:25 +0000135 yBuckets [first2->key]++;
136 yPayloads[first2->key] += first2->payload;
137 }
138
139 for (size_t i = 0; i < 256; ++i)
140 {
141 if (xBuckets[i] != yBuckets[i])
142 return false;
143 if (xPayloads[i] != yPayloads[i])
144 return false;
145 }
146
147 return true;
Marshall Clow161681a2018-01-19 03:17:45 +0000148}
149
150template <typename Iter1, typename Iter2>
151bool is_permutation(Iter1 first1, Iter1 last1, Iter2 first2)
152{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000153 static_assert((std::is_same<typename std::iterator_traits<Iter1>::value_type, uint8_t>::value), "");
154 static_assert((std::is_same<typename std::iterator_traits<Iter2>::value_type, uint8_t>::value), "");
Marshall Clow161681a2018-01-19 03:17:45 +0000155
Marshall Clow43ff7d92018-11-04 17:57:25 +0000156 size_t xBuckets[256] = {0};
157 size_t yBuckets[256] = {0};
158
159 for (; first1 != last1; ++first1, ++first2)
160 {
161 xBuckets [*first1]++;
162 yBuckets [*first2]++;
163 }
164
165 for (size_t i = 0; i < 256; ++i)
166 if (xBuckets[i] != yBuckets[i])
167 return false;
168
169 return true;
Marshall Clow161681a2018-01-19 03:17:45 +0000170}
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000171
Marshall Clow43ff7d92018-11-04 17:57:25 +0000172// == sort ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000173int sort(const uint8_t *data, size_t size)
174{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000175 Vec working(data, data + size);
176 std::sort(working.begin(), working.end());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000177
Marshall Clow43ff7d92018-11-04 17:57:25 +0000178 if (!std::is_sorted(working.begin(), working.end())) return 1;
179 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
180 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000181}
182
183
Marshall Clow43ff7d92018-11-04 17:57:25 +0000184// == stable_sort ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000185int stable_sort(const uint8_t *data, size_t size)
186{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000187 StableVec input;
188 for (size_t i = 0; i < size; ++i)
189 input.push_back(stable_test(data[i], i));
190 StableVec working = input;
191 std::stable_sort(working.begin(), working.end(), key_less());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000192
Marshall Clow43ff7d92018-11-04 17:57:25 +0000193 if (!std::is_sorted(working.begin(), working.end(), key_less())) return 1;
194 auto iter = working.begin();
195 while (iter != working.end())
196 {
197 auto range = std::equal_range(iter, working.end(), *iter, key_less());
198 if (!std::is_sorted(range.first, range.second, total_less())) return 2;
199 iter = range.second;
200 }
201 if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99;
202 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000203}
204
Marshall Clow43ff7d92018-11-04 17:57:25 +0000205// == partition ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000206int partition(const uint8_t *data, size_t size)
207{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000208 Vec working(data, data + size);
209 auto iter = std::partition(working.begin(), working.end(), is_even<uint8_t>());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000210
Marshall Clow43ff7d92018-11-04 17:57:25 +0000211 if (!std::all_of (working.begin(), iter, is_even<uint8_t>())) return 1;
212 if (!std::none_of(iter, working.end(), is_even<uint8_t>())) return 2;
213 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
214 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000215}
216
217
Marshall Clow43ff7d92018-11-04 17:57:25 +0000218// == partition_copy ==
Marshall Clow974677c2017-10-30 19:51:58 +0000219int partition_copy(const uint8_t *data, size_t size)
220{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000221 Vec v1, v2;
222 auto iter = std::partition_copy(data, data + size,
223 std::back_inserter<Vec>(v1), std::back_inserter<Vec>(v2),
224 is_even<uint8_t>());
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500225 ((void)iter);
Marshall Clow43ff7d92018-11-04 17:57:25 +0000226// The two vectors should add up to the original size
227 if (v1.size() + v2.size() != size) return 1;
Marshall Clow974677c2017-10-30 19:51:58 +0000228
Marshall Clow43ff7d92018-11-04 17:57:25 +0000229// All of the even values should be in the first vector, and none in the second
230 if (!std::all_of (v1.begin(), v1.end(), is_even<uint8_t>())) return 2;
231 if (!std::none_of(v2.begin(), v2.end(), is_even<uint8_t>())) return 3;
Marshall Clow974677c2017-10-30 19:51:58 +0000232
Marshall Clow43ff7d92018-11-04 17:57:25 +0000233// Every value in both vectors has to be in the original
234
235// Make a copy of the input, and sort it
236 Vec v0{data, data + size};
237 std::sort(v0.begin(), v0.end());
238
239// Sort each vector and ensure that all of the elements appear in the original input
240 std::sort(v1.begin(), v1.end());
241 if (!std::includes(v0.begin(), v0.end(), v1.begin(), v1.end())) return 4;
242
243 std::sort(v2.begin(), v2.end());
244 if (!std::includes(v0.begin(), v0.end(), v2.begin(), v2.end())) return 5;
245
246// This, while simple, is really slow - 20 seconds on a 500K element input.
247// for (auto v: v1)
248// if (std::find(data, data + size, v) == data + size) return 4;
249//
250// for (auto v: v2)
251// if (std::find(data, data + size, v) == data + size) return 5;
252
253 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000254}
255
Marshall Clow43ff7d92018-11-04 17:57:25 +0000256// == stable_partition ==
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000257int stable_partition (const uint8_t *data, size_t size)
258{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000259 StableVec input;
260 for (size_t i = 0; i < size; ++i)
261 input.push_back(stable_test(data[i], i));
262 StableVec working = input;
263 auto iter = std::stable_partition(working.begin(), working.end(), is_even<stable_test>());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000264
Marshall Clow43ff7d92018-11-04 17:57:25 +0000265 if (!std::all_of (working.begin(), iter, is_even<stable_test>())) return 1;
266 if (!std::none_of(iter, working.end(), is_even<stable_test>())) return 2;
267 if (!std::is_sorted(working.begin(), iter, payload_less())) return 3;
268 if (!std::is_sorted(iter, working.end(), payload_less())) return 4;
269 if (!fuzzing::is_permutation(input.cbegin(), input.cend(), working.cbegin())) return 99;
270 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000271}
272
Marshall Clow43ff7d92018-11-04 17:57:25 +0000273// == nth_element ==
274// use the first element as a position into the data
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000275int nth_element (const uint8_t *data, size_t size)
276{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000277 if (size <= 1) return 0;
278 const size_t partition_point = data[0] % size;
279 Vec working(data + 1, data + size);
280 const auto partition_iter = working.begin() + partition_point;
281 std::nth_element(working.begin(), partition_iter, working.end());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000282
Marshall Clow43ff7d92018-11-04 17:57:25 +0000283// nth may be the end iterator, in this case nth_element has no effect.
284 if (partition_iter == working.end())
285 {
286 if (!std::equal(data + 1, data + size, working.begin())) return 98;
287 }
288 else
289 {
290 const uint8_t nth = *partition_iter;
291 if (!std::all_of(working.begin(), partition_iter, [=](uint8_t v) { return v <= nth; }))
292 return 1;
293 if (!std::all_of(partition_iter, working.end(), [=](uint8_t v) { return v >= nth; }))
294 return 2;
295 if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99;
296 }
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000297
Marshall Clow43ff7d92018-11-04 17:57:25 +0000298 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000299}
300
Marshall Clow43ff7d92018-11-04 17:57:25 +0000301// == partial_sort ==
302// use the first element as a position into the data
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000303int partial_sort (const uint8_t *data, size_t size)
304{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000305 if (size <= 1) return 0;
306 const size_t sort_point = data[0] % size;
307 Vec working(data + 1, data + size);
308 const auto sort_iter = working.begin() + sort_point;
309 std::partial_sort(working.begin(), sort_iter, working.end());
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000310
Marshall Clow43ff7d92018-11-04 17:57:25 +0000311 if (sort_iter != working.end())
312 {
313 const uint8_t nth = *std::min_element(sort_iter, working.end());
314 if (!std::all_of(working.begin(), sort_iter, [=](uint8_t v) { return v <= nth; }))
315 return 1;
316 if (!std::all_of(sort_iter, working.end(), [=](uint8_t v) { return v >= nth; }))
317 return 2;
318 }
319 if (!std::is_sorted(working.begin(), sort_iter)) return 3;
320 if (!fuzzing::is_permutation(data + 1, data + size, working.cbegin())) return 99;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000321
Marshall Clow43ff7d92018-11-04 17:57:25 +0000322 return 0;
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000323}
324
Marshall Clowd84736b2017-10-12 14:48:09 +0000325
Marshall Clow43ff7d92018-11-04 17:57:25 +0000326// == partial_sort_copy ==
327// use the first element as a count
Marshall Clow974677c2017-10-30 19:51:58 +0000328int partial_sort_copy (const uint8_t *data, size_t size)
329{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000330 if (size <= 1) return 0;
331 const size_t num_results = data[0] % size;
332 Vec results(num_results);
333 (void) std::partial_sort_copy(data + 1, data + size, results.begin(), results.end());
Marshall Clowd84736b2017-10-12 14:48:09 +0000334
Marshall Clow43ff7d92018-11-04 17:57:25 +0000335// The results have to be sorted
336 if (!std::is_sorted(results.begin(), results.end())) return 1;
337// All the values in results have to be in the original data
338 for (auto v: results)
339 if (std::find(data + 1, data + size, v) == data + size) return 2;
Marshall Clow974677c2017-10-30 19:51:58 +0000340
Marshall Clow43ff7d92018-11-04 17:57:25 +0000341// The things in results have to be the smallest N in the original data
342 Vec sorted(data + 1, data + size);
343 std::sort(sorted.begin(), sorted.end());
344 if (!std::equal(results.begin(), results.end(), sorted.begin())) return 3;
345 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000346}
347
Marshall Clow43ff7d92018-11-04 17:57:25 +0000348// The second sequence has been "uniqued"
Marshall Clow974677c2017-10-30 19:51:58 +0000349template <typename Iter1, typename Iter2>
350static bool compare_unique(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2)
351{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000352 assert(first1 != last1 && first2 != last2);
353 if (*first1 != *first2) return false;
Marshall Clow974677c2017-10-30 19:51:58 +0000354
Marshall Clow43ff7d92018-11-04 17:57:25 +0000355 uint8_t last_value = *first1;
356 ++first1; ++first2;
357 while(first1 != last1 && first2 != last2)
358 {
359 // Skip over dups in the first sequence
360 while (*first1 == last_value)
361 if (++first1 == last1) return false;
362 if (*first1 != *first2) return false;
363 last_value = *first1;
364 ++first1; ++first2;
365 }
Marshall Clow974677c2017-10-30 19:51:58 +0000366
Marshall Clow43ff7d92018-11-04 17:57:25 +0000367// Still stuff left in the 'uniqued' sequence - oops
368 if (first1 == last1 && first2 != last2) return false;
Marshall Clow974677c2017-10-30 19:51:58 +0000369
Marshall Clow43ff7d92018-11-04 17:57:25 +0000370// Still stuff left in the original sequence - better be all the same
371 while (first1 != last1)
372 {
373 if (*first1 != last_value) return false;
374 ++first1;
375 }
376 return true;
Marshall Clow974677c2017-10-30 19:51:58 +0000377}
378
Marshall Clow43ff7d92018-11-04 17:57:25 +0000379// == unique ==
Marshall Clow974677c2017-10-30 19:51:58 +0000380int unique (const uint8_t *data, size_t size)
381{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000382 Vec working(data, data + size);
383 std::sort(working.begin(), working.end());
384 Vec results = working;
385 Vec::iterator new_end = std::unique(results.begin(), results.end());
386 Vec::iterator it; // scratch iterator
Marshall Clow974677c2017-10-30 19:51:58 +0000387
Marshall Clow43ff7d92018-11-04 17:57:25 +0000388// Check the size of the unique'd sequence.
389// it should only be zero if the input sequence was empty.
390 if (results.begin() == new_end)
391 return working.size() == 0 ? 0 : 1;
392
393// 'results' is sorted
394 if (!std::is_sorted(results.begin(), new_end)) return 2;
395
396// All the elements in 'results' must be different
397 it = results.begin();
398 uint8_t prev_value = *it++;
399 for (; it != new_end; ++it)
400 {
401 if (*it == prev_value) return 3;
402 prev_value = *it;
403 }
404
405// Every element in 'results' must be in 'working'
406 for (it = results.begin(); it != new_end; ++it)
407 if (std::find(working.begin(), working.end(), *it) == working.end())
408 return 4;
409
410// Every element in 'working' must be in 'results'
411 for (auto v : working)
412 if (std::find(results.begin(), new_end, v) == new_end)
413 return 5;
414
415 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000416}
417
Marshall Clow43ff7d92018-11-04 17:57:25 +0000418// == unique_copy ==
Marshall Clow974677c2017-10-30 19:51:58 +0000419int unique_copy (const uint8_t *data, size_t size)
420{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000421 Vec working(data, data + size);
422 std::sort(working.begin(), working.end());
423 Vec results;
424 (void) std::unique_copy(working.begin(), working.end(),
425 std::back_inserter<Vec>(results));
426 Vec::iterator it; // scratch iterator
Marshall Clow974677c2017-10-30 19:51:58 +0000427
Marshall Clow43ff7d92018-11-04 17:57:25 +0000428// Check the size of the unique'd sequence.
429// it should only be zero if the input sequence was empty.
430 if (results.size() == 0)
431 return working.size() == 0 ? 0 : 1;
432
433// 'results' is sorted
434 if (!std::is_sorted(results.begin(), results.end())) return 2;
435
436// All the elements in 'results' must be different
437 it = results.begin();
438 uint8_t prev_value = *it++;
439 for (; it != results.end(); ++it)
440 {
441 if (*it == prev_value) return 3;
442 prev_value = *it;
443 }
444
445// Every element in 'results' must be in 'working'
446 for (auto v : results)
447 if (std::find(working.begin(), working.end(), v) == working.end())
448 return 4;
449
450// Every element in 'working' must be in 'results'
451 for (auto v : working)
452 if (std::find(results.begin(), results.end(), v) == results.end())
453 return 5;
454
455 return 0;
Marshall Clow974677c2017-10-30 19:51:58 +0000456}
457
458
Marshall Clow43ff7d92018-11-04 17:57:25 +0000459// -- regex fuzzers
Marshall Clowd84736b2017-10-12 14:48:09 +0000460static int regex_helper(const uint8_t *data, size_t size, std::regex::flag_type flag)
461{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000462 if (size > 0)
463 {
Eric Fiseliera081edf2019-12-11 16:21:23 -0500464#ifndef _LIBCPP_NO_EXCEPTIONS
Marshall Clow43ff7d92018-11-04 17:57:25 +0000465 try
466 {
467 std::string s((const char *)data, size);
468 std::regex re(s, flag);
469 return std::regex_match(s, re) ? 1 : 0;
470 }
471 catch (std::regex_error &ex) {}
Eric Fiseliera081edf2019-12-11 16:21:23 -0500472#else
473 ((void)data);
474 ((void)size);
475 ((void)flag);
476#endif
Marshall Clow43ff7d92018-11-04 17:57:25 +0000477 }
478 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000479}
480
481
482int regex_ECMAScript (const uint8_t *data, size_t size)
483{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000484 (void) regex_helper(data, size, std::regex_constants::ECMAScript);
485 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000486}
487
488int regex_POSIX (const uint8_t *data, size_t size)
489{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000490 (void) regex_helper(data, size, std::regex_constants::basic);
491 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000492}
493
494int regex_extended (const uint8_t *data, size_t size)
495{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000496 (void) regex_helper(data, size, std::regex_constants::extended);
497 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000498}
499
500int regex_awk (const uint8_t *data, size_t size)
501{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000502 (void) regex_helper(data, size, std::regex_constants::awk);
503 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000504}
505
506int regex_grep (const uint8_t *data, size_t size)
507{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000508 (void) regex_helper(data, size, std::regex_constants::grep);
509 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000510}
511
512int regex_egrep (const uint8_t *data, size_t size)
513{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000514 (void) regex_helper(data, size, std::regex_constants::egrep);
515 return 0;
Marshall Clowd84736b2017-10-12 14:48:09 +0000516}
517
Marshall Clow43ff7d92018-11-04 17:57:25 +0000518// -- heap fuzzers
Marshall Clowa97ab842017-10-23 23:19:30 +0000519int make_heap (const uint8_t *data, size_t size)
520{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000521 Vec working(data, data + size);
522 std::make_heap(working.begin(), working.end());
Marshall Clowa97ab842017-10-23 23:19:30 +0000523
Marshall Clow43ff7d92018-11-04 17:57:25 +0000524 if (!std::is_heap(working.begin(), working.end())) return 1;
525 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
526 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000527}
528
529int push_heap (const uint8_t *data, size_t size)
530{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000531 if (size < 2) return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000532
Marshall Clow43ff7d92018-11-04 17:57:25 +0000533// Make a heap from the first half of the data
534 Vec working(data, data + size);
535 auto iter = working.begin() + (size / 2);
536 std::make_heap(working.begin(), iter);
537 if (!std::is_heap(working.begin(), iter)) return 1;
Marshall Clowa97ab842017-10-23 23:19:30 +0000538
Marshall Clow43ff7d92018-11-04 17:57:25 +0000539// Now push the rest onto the heap, one at a time
540 ++iter;
541 for (; iter != working.end(); ++iter) {
542 std::push_heap(working.begin(), iter);
543 if (!std::is_heap(working.begin(), iter)) return 2;
544 }
Marshall Clowa97ab842017-10-23 23:19:30 +0000545
Marshall Clow43ff7d92018-11-04 17:57:25 +0000546 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
547 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000548}
549
550int pop_heap (const uint8_t *data, size_t size)
551{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000552 if (size < 2) return 0;
553 Vec working(data, data + size);
554 std::make_heap(working.begin(), working.end());
Marshall Clowa97ab842017-10-23 23:19:30 +0000555
Marshall Clow43ff7d92018-11-04 17:57:25 +0000556// Pop things off, one at a time
557 auto iter = --working.end();
558 while (iter != working.begin()) {
559 std::pop_heap(working.begin(), iter);
560 if (!std::is_heap(working.begin(), --iter)) return 2;
561 }
Marshall Clowa97ab842017-10-23 23:19:30 +0000562
Marshall Clow43ff7d92018-11-04 17:57:25 +0000563 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000564}
565
566
Marshall Clow43ff7d92018-11-04 17:57:25 +0000567// -- search fuzzers
Marshall Clowa97ab842017-10-23 23:19:30 +0000568int search (const uint8_t *data, size_t size)
569{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000570 if (size < 2) return 0;
571
572 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
573 assert(pat_size <= size - 1);
574 const uint8_t *pat_begin = data + 1;
575 const uint8_t *pat_end = pat_begin + pat_size;
576 const uint8_t *data_end = data + size;
577 assert(pat_end <= data_end);
578// std::cerr << "data[0] = " << size_t(data[0]) << " ";
579// std::cerr << "Pattern size = " << pat_size << "; corpus is " << size - 1 << std::endl;
580 auto it = std::search(pat_end, data_end, pat_begin, pat_end);
581 if (it != data_end) // not found
582 if (!std::equal(pat_begin, pat_end, it))
583 return 1;
584 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000585}
586
587template <typename S>
588static int search_helper (const uint8_t *data, size_t size)
589{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000590 if (size < 2) return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000591
Marshall Clow43ff7d92018-11-04 17:57:25 +0000592 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
593 const uint8_t *pat_begin = data + 1;
594 const uint8_t *pat_end = pat_begin + pat_size;
595 const uint8_t *data_end = data + size;
596
597 auto it = std::search(pat_end, data_end, S(pat_begin, pat_end));
598 if (it != data_end) // not found
599 if (!std::equal(pat_begin, pat_end, it))
600 return 1;
601 return 0;
Marshall Clowa97ab842017-10-23 23:19:30 +0000602}
603
Marshall Clow43ff7d92018-11-04 17:57:25 +0000604// These are still in std::experimental
Marshall Clowa97ab842017-10-23 23:19:30 +0000605// int search_boyer_moore (const uint8_t *data, size_t size)
606// {
Marshall Clow43ff7d92018-11-04 17:57:25 +0000607// return search_helper<std::boyer_moore_searcher<const uint8_t *>>(data, size);
Marshall Clowa97ab842017-10-23 23:19:30 +0000608// }
Marshall Clow43ff7d92018-11-04 17:57:25 +0000609//
Marshall Clowa97ab842017-10-23 23:19:30 +0000610// int search_boyer_moore_horspool (const uint8_t *data, size_t size)
611// {
Marshall Clow43ff7d92018-11-04 17:57:25 +0000612// return search_helper<std::boyer_moore_horspool_searcher<const uint8_t *>>(data, size);
Marshall Clowa97ab842017-10-23 23:19:30 +0000613// }
614
Marshall Clow974677c2017-10-30 19:51:58 +0000615
Marshall Clow43ff7d92018-11-04 17:57:25 +0000616// -- set operation fuzzers
Marshall Clow974677c2017-10-30 19:51:58 +0000617template <typename S>
618static void set_helper (const uint8_t *data, size_t size, Vec &v1, Vec &v2)
619{
Marshall Clow43ff7d92018-11-04 17:57:25 +0000620 assert(size > 1);
Marshall Clow974677c2017-10-30 19:51:58 +0000621
Marshall Clow43ff7d92018-11-04 17:57:25 +0000622 const size_t pat_size = data[0] * (size - 1) / std::numeric_limits<uint8_t>::max();
623 const uint8_t *pat_begin = data + 1;
624 const uint8_t *pat_end = pat_begin + pat_size;
625 const uint8_t *data_end = data + size;
626 v1.assign(pat_begin, pat_end);
627 v2.assign(pat_end, data_end);
628
629 std::sort(v1.begin(), v1.end());
630 std::sort(v2.begin(), v2.end());
Marshall Clow974677c2017-10-30 19:51:58 +0000631}
632
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500633enum class ParamKind {
634 OneValue,
635 TwoValues,
636 PointerRange
637};
638
639template <class IntT>
640std::vector<IntT> GetValues(const uint8_t *data, size_t size) {
641 std::vector<IntT> result;
642 while (size >= sizeof(IntT)) {
643 IntT tmp;
644 memcpy(&tmp, data, sizeof(IntT));
645 size -= sizeof(IntT);
646 data += sizeof(IntT);
647 result.push_back(tmp);
648 }
649 return result;
650}
651
652enum InitKind {
653 Default,
654 DoubleOnly,
655 VectorDouble,
656 VectorResultType
657};
658
Eric Fiselierd4021252019-12-11 16:36:21 -0500659
660
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500661template <class Dist>
662struct ParamTypeHelper {
663 using ParamT = typename Dist::param_type;
664 using ResultT = typename Dist::result_type;
665 static_assert(std::is_same<ResultT, typename ParamT::distribution_type::result_type>::value, "");
666 static ParamT Create(const uint8_t* data, size_t size, bool &OK) {
667
Eric Fiselierd4021252019-12-11 16:36:21 -0500668 constexpr bool select_vector_result = std::is_constructible<ParamT, ResultT*, ResultT*, ResultT*>::value;
669 constexpr bool select_vector_double = std::is_constructible<ParamT, double*, double*>::value;
670 constexpr int selector = select_vector_result ? 0 : (select_vector_double ? 1 : 2);
671 return DispatchAndCreate(std::integral_constant<int, selector>{}, data, size, OK);
672
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500673 }
674
Eric Fiselierd4021252019-12-11 16:36:21 -0500675 static ParamT DispatchAndCreate(std::integral_constant<int, 0>, const uint8_t *data, size_t size, bool &OK) {
676 return CreateVectorResult(data, size, OK);
677 }
678 static ParamT DispatchAndCreate(std::integral_constant<int, 1>, const uint8_t *data, size_t size, bool &OK) {
679 return CreateVectorDouble(data, size, OK);
680 }
681 static ParamT DispatchAndCreate(std::integral_constant<int, 2>, const uint8_t *data, size_t size, bool &OK) {
682 return CreateDefault(data, size, OK);
683 }
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500684
Eric Fiselierd4021252019-12-11 16:36:21 -0500685static ParamT
Eric Fiselier0aaa3272019-12-11 15:45:48 -0500686CreateVectorResult(const uint8_t *data, size_t size, bool &OK) {
687 auto Input = GetValues<ResultT>(data, size);
688 OK = false;
689 if (Input.size() < 10)
690 return ParamT{};
691 OK = true;
692 auto Beg = Input.begin();
693 auto End = Input.end();
694 auto Mid = Beg + ((End - Beg) / 2);
695
696 assert(Mid - Beg <= (End - Mid));
697 ParamT p(Beg, Mid, Mid);
698 return p;
699}
700
701 static ParamT
702 CreateVectorDouble(const uint8_t *data, size_t size, bool &OK) {
703 auto Input = GetValues<double>(data, size);
704
705 OK = true;
706 auto Beg = Input.begin();
707 auto End = Input.end();
708
709 ParamT p(Beg, End);
710 return p;
711 }
712
713
714 static ParamT
715 CreateDefault(const uint8_t *data, size_t size, bool &OK) {
716 OK = false;
717 if (size < sizeof(ParamT))
718 return ParamT{};
719 OK = true;
720 ParamT input;
721 memcpy(&input, data, sizeof(ParamT));
722 return input;
723 }
724
725};
726
727
728
729
730template <class IntT>
731struct ParamTypeHelper<std::poisson_distribution<IntT>> {
732 using Dist = std::poisson_distribution<IntT>;
733 using ParamT = typename Dist::param_type;
734 using ResultT = typename Dist::result_type;
735
736 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
737 OK = false;
738 auto vals = GetValues<double>(data, size);
739 if (vals.empty() || std::isnan(vals[0]) || std::isnan(std::abs(vals[0])) || vals[0] < 0 )
740 return ParamT{};
741 OK = true;
742 //std::cerr << "Value: " << vals[0] << std::endl;
743 return ParamT{vals[0]};
744 }
745};
746
747
748template <class IntT>
749struct ParamTypeHelper<std::geometric_distribution<IntT>> {
750 using Dist = std::geometric_distribution<IntT>;
751 using ParamT = typename Dist::param_type;
752 using ResultT = typename Dist::result_type;
753
754 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
755 OK = false;
756 auto vals = GetValues<double>(data, size);
757 if (vals.empty() || std::isnan(vals[0]) || vals[0] < 0 )
758 return ParamT{};
759 OK = true;
760 // std::cerr << "Value: " << vals[0] << std::endl;
761 return ParamT{vals[0]};
762 }
763};
764
765
766template <class IntT>
767struct ParamTypeHelper<std::lognormal_distribution<IntT>> {
768 using Dist = std::lognormal_distribution<IntT>;
769 using ParamT = typename Dist::param_type;
770 using ResultT = typename Dist::result_type;
771
772 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
773 OK = false;
774 auto vals = GetValues<ResultT>(data, size);
775 if (vals.size() < 2 )
776 return ParamT{};
777 OK = true;
778 return ParamT{vals[0], vals[1]};
779 }
780};
781
782
783template <>
784struct ParamTypeHelper<std::bernoulli_distribution> {
785 using Dist = std::bernoulli_distribution;
786 using ParamT = typename Dist::param_type;
787 using ResultT = typename Dist::result_type;
788
789 static ParamT Create(const uint8_t *data, size_t size, bool& OK) {
790 OK = false;
791 auto vals = GetValues<double>(data, size);
792 if (vals.empty())
793 return ParamT{};
794 OK = true;
795 return ParamT{vals[0]};
796 }
797};
798
799template <class Distribution>
800int random_distribution_helper(const uint8_t *data, size_t size) {
801
802 std::mt19937 engine;
803 using ParamT = typename Distribution::param_type;
804 bool OK;
805 ParamT p = ParamTypeHelper<Distribution>::Create(data, size, OK);
806 if (!OK)
807 return 0;
808 Distribution d(p);
809 volatile auto res = d(engine);
810 if (std::isnan(res))
811 return 1;
812 return 0;
813}
814
815#define DEFINE_RANDOM_TEST(name, ...) \
816int name(const uint8_t *data, size_t size) { \
817 return random_distribution_helper< std::name __VA_ARGS__ >(data, size); \
818}
819DEFINE_RANDOM_TEST(uniform_int_distribution,<std::int16_t>)
820DEFINE_RANDOM_TEST(uniform_real_distribution,<float>)
821DEFINE_RANDOM_TEST(bernoulli_distribution)
822DEFINE_RANDOM_TEST(poisson_distribution,<std::int16_t>)
823DEFINE_RANDOM_TEST(geometric_distribution,<std::int16_t>)
824DEFINE_RANDOM_TEST(binomial_distribution, <std::int16_t>)
825DEFINE_RANDOM_TEST(negative_binomial_distribution, <std::int16_t>)
826DEFINE_RANDOM_TEST(exponential_distribution, <float>)
827DEFINE_RANDOM_TEST(gamma_distribution, <float>)
828DEFINE_RANDOM_TEST(weibull_distribution, <float>)
829DEFINE_RANDOM_TEST(extreme_value_distribution, <float>)
830DEFINE_RANDOM_TEST(normal_distribution, <float>)
831DEFINE_RANDOM_TEST(lognormal_distribution, <float>)
832DEFINE_RANDOM_TEST(chi_squared_distribution, <float>)
833DEFINE_RANDOM_TEST(cauchy_distribution, <float>)
834DEFINE_RANDOM_TEST(fisher_f_distribution, <float>)
835DEFINE_RANDOM_TEST(student_t_distribution, <float>)
836DEFINE_RANDOM_TEST(discrete_distribution, <std::int16_t>)
837DEFINE_RANDOM_TEST(piecewise_constant_distribution, <float>)
838DEFINE_RANDOM_TEST(piecewise_linear_distribution, <float>)
839
Marshall Clowbaa6fb32017-10-04 22:23:03 +0000840} // namespace fuzzing