1 // -*- C++ -*-
2 //===------------------------- fuzzing.cpp -------------------------------===//
3 //
4 // 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
7 //
8 //===----------------------------------------------------------------------===//
9
10 // A set of routines to use when fuzzing the algorithms in libc++
11 // Each one tests a single algorithm.
12 //
13 // They all have the form of:
14 // int `algorithm`(const uint8_t *data, size_t size);
15 //
16 // They perform the operation, and then check to see if the results are correct.
17 // If so, they return zero, and non-zero otherwise.
18 //
19 // 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.
22
23
24
25 #include "fuzzing.h"
26 #include <vector>
27 #include <algorithm>
28 #include <functional>
29 #include <regex>
30 #include <random>
31 #include <cassert>
32 #include <cmath>
33
34 #include <iostream>
35
36 #ifdef NDEBUG
37 #undef NDEBUG
38 #endif
39 #include <cassert>
40 // If we had C++14, we could use the four iterator version of is_permutation and equal
41
42 #ifndef _LIBCPP_VERSION
43 #error These test should be built with libc++ only.
44 #endif
45
46 namespace fuzzing {
47
48 // 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.
50
51 struct stable_test {
52 uint8_t key;
53 size_t payload;
54
stable_testfuzzing::stable_test55 stable_test(uint8_t k) : key(k), payload(0) {}
stable_testfuzzing::stable_test56 stable_test(uint8_t k, size_t p) : key(k), payload(p) {}
57 };
58
swap(stable_test & lhs,stable_test & rhs)59 void swap(stable_test &lhs, stable_test &rhs)
60 {
61 using std::swap;
62 swap(lhs.key, rhs.key);
63 swap(lhs.payload, rhs.payload);
64 }
65
66 struct key_less
67 {
operator ()fuzzing::key_less68 bool operator () (const stable_test &lhs, const stable_test &rhs) const
69 {
70 return lhs.key < rhs.key;
71 }
72 };
73
74 struct payload_less
75 {
operator ()fuzzing::payload_less76 bool operator () (const stable_test &lhs, const stable_test &rhs) const
77 {
78 return lhs.payload < rhs.payload;
79 }
80 };
81
82 struct total_less
83 {
operator ()fuzzing::total_less84 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 }
88 };
89
operator ==(const stable_test & lhs,const stable_test & rhs)90 bool operator==(const stable_test &lhs, const stable_test &rhs)
91 {
92 return lhs.key == rhs.key && lhs.payload == rhs.payload;
93 }
94
95
96 template<typename T>
97 struct is_even
98 {
operator ()fuzzing::is_even99 bool operator () (const T &t) const
100 {
101 return t % 2 == 0;
102 }
103 };
104
105
106 template<>
107 struct is_even<stable_test>
108 {
operator ()fuzzing::is_even109 bool operator () (const stable_test &t) const
110 {
111 return t.key % 2 == 0;
112 }
113 };
114
115 typedef std::vector<uint8_t> Vec;
116 typedef std::vector<stable_test> StableVec;
117 typedef StableVec::const_iterator SVIter;
118
119 // 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
is_permutation(SVIter first1,SVIter last1,SVIter first2)123 bool is_permutation(SVIter first1, SVIter last1, SVIter first2)
124 {
125 size_t xBuckets[256] = {0};
126 size_t xPayloads[256] = {0};
127 size_t yBuckets[256] = {0};
128 size_t yPayloads[256] = {0};
129
130 for (; first1 != last1; ++first1, ++first2)
131 {
132 xBuckets [first1->key]++;
133 xPayloads[first1->key] += first1->payload;
134
135 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;
148 }
149
150 template <typename Iter1, typename Iter2>
is_permutation(Iter1 first1,Iter1 last1,Iter2 first2)151 bool is_permutation(Iter1 first1, Iter1 last1, Iter2 first2)
152 {
153 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), "");
155
156 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;
170 }
171
172 // == sort ==
sort(const uint8_t * data,size_t size)173 int sort(const uint8_t *data, size_t size)
174 {
175 Vec working(data, data + size);
176 std::sort(working.begin(), working.end());
177
178 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;
181 }
182
183
184 // == stable_sort ==
stable_sort(const uint8_t * data,size_t size)185 int stable_sort(const uint8_t *data, size_t size)
186 {
187 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());
192
193 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;
203 }
204
205 // == partition ==
partition(const uint8_t * data,size_t size)206 int partition(const uint8_t *data, size_t size)
207 {
208 Vec working(data, data + size);
209 auto iter = std::partition(working.begin(), working.end(), is_even<uint8_t>());
210
211 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;
215 }
216
217
218 // == partition_copy ==
partition_copy(const uint8_t * data,size_t size)219 int partition_copy(const uint8_t *data, size_t size)
220 {
221 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>());
225 ((void)iter);
226 // The two vectors should add up to the original size
227 if (v1.size() + v2.size() != size) return 1;
228
229 // 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;
232
233 // 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;
254 }
255
256 // == stable_partition ==
stable_partition(const uint8_t * data,size_t size)257 int stable_partition (const uint8_t *data, size_t size)
258 {
259 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>());
264
265 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;
271 }
272
273 // == nth_element ==
274 // use the first element as a position into the data
nth_element(const uint8_t * data,size_t size)275 int nth_element (const uint8_t *data, size_t size)
276 {
277 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());
282
283 // 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 }
297
298 return 0;
299 }
300
301 // == partial_sort ==
302 // use the first element as a position into the data
partial_sort(const uint8_t * data,size_t size)303 int partial_sort (const uint8_t *data, size_t size)
304 {
305 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());
310
311 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;
321
322 return 0;
323 }
324
325
326 // == partial_sort_copy ==
327 // use the first element as a count
partial_sort_copy(const uint8_t * data,size_t size)328 int partial_sort_copy (const uint8_t *data, size_t size)
329 {
330 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());
334
335 // 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;
340
341 // 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;
346 }
347
348 // The second sequence has been "uniqued"
349 template <typename Iter1, typename Iter2>
compare_unique(Iter1 first1,Iter1 last1,Iter2 first2,Iter2 last2)350 static bool compare_unique(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2)
351 {
352 assert(first1 != last1 && first2 != last2);
353 if (*first1 != *first2) return false;
354
355 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 }
366
367 // Still stuff left in the 'uniqued' sequence - oops
368 if (first1 == last1 && first2 != last2) return false;
369
370 // 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;
377 }
378
379 // == unique ==
unique(const uint8_t * data,size_t size)380 int unique (const uint8_t *data, size_t size)
381 {
382 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
387
388 // 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;
416 }
417
418 // == unique_copy ==
unique_copy(const uint8_t * data,size_t size)419 int unique_copy (const uint8_t *data, size_t size)
420 {
421 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
427
428 // 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;
456 }
457
458
459 // -- regex fuzzers
regex_helper(const uint8_t * data,size_t size,std::regex::flag_type flag)460 static int regex_helper(const uint8_t *data, size_t size, std::regex::flag_type flag)
461 {
462 if (size > 0)
463 {
464 #ifndef _LIBCPP_NO_EXCEPTIONS
465 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) {}
472 #else
473 ((void)data);
474 ((void)size);
475 ((void)flag);
476 #endif
477 }
478 return 0;
479 }
480
481
regex_ECMAScript(const uint8_t * data,size_t size)482 int regex_ECMAScript (const uint8_t *data, size_t size)
483 {
484 (void) regex_helper(data, size, std::regex_constants::ECMAScript);
485 return 0;
486 }
487
regex_POSIX(const uint8_t * data,size_t size)488 int regex_POSIX (const uint8_t *data, size_t size)
489 {
490 (void) regex_helper(data, size, std::regex_constants::basic);
491 return 0;
492 }
493
regex_extended(const uint8_t * data,size_t size)494 int regex_extended (const uint8_t *data, size_t size)
495 {
496 (void) regex_helper(data, size, std::regex_constants::extended);
497 return 0;
498 }
499
regex_awk(const uint8_t * data,size_t size)500 int regex_awk (const uint8_t *data, size_t size)
501 {
502 (void) regex_helper(data, size, std::regex_constants::awk);
503 return 0;
504 }
505
regex_grep(const uint8_t * data,size_t size)506 int regex_grep (const uint8_t *data, size_t size)
507 {
508 (void) regex_helper(data, size, std::regex_constants::grep);
509 return 0;
510 }
511
regex_egrep(const uint8_t * data,size_t size)512 int regex_egrep (const uint8_t *data, size_t size)
513 {
514 (void) regex_helper(data, size, std::regex_constants::egrep);
515 return 0;
516 }
517
518 // -- heap fuzzers
make_heap(const uint8_t * data,size_t size)519 int make_heap (const uint8_t *data, size_t size)
520 {
521 Vec working(data, data + size);
522 std::make_heap(working.begin(), working.end());
523
524 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;
527 }
528
push_heap(const uint8_t * data,size_t size)529 int push_heap (const uint8_t *data, size_t size)
530 {
531 if (size < 2) return 0;
532
533 // 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;
538
539 // 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 }
545
546 if (!fuzzing::is_permutation(data, data + size, working.cbegin())) return 99;
547 return 0;
548 }
549
pop_heap(const uint8_t * data,size_t size)550 int pop_heap (const uint8_t *data, size_t size)
551 {
552 if (size < 2) return 0;
553 Vec working(data, data + size);
554 std::make_heap(working.begin(), working.end());
555
556 // 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 }
562
563 return 0;
564 }
565
566
567 // -- search fuzzers
search(const uint8_t * data,size_t size)568 int search (const uint8_t *data, size_t size)
569 {
570 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;
585 }
586
587 template <typename S>
search_helper(const uint8_t * data,size_t size)588 static int search_helper (const uint8_t *data, size_t size)
589 {
590 if (size < 2) return 0;
591
592 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;
602 }
603
604 // These are still in std::experimental
605 // int search_boyer_moore (const uint8_t *data, size_t size)
606 // {
607 // return search_helper<std::boyer_moore_searcher<const uint8_t *>>(data, size);
608 // }
609 //
610 // int search_boyer_moore_horspool (const uint8_t *data, size_t size)
611 // {
612 // return search_helper<std::boyer_moore_horspool_searcher<const uint8_t *>>(data, size);
613 // }
614
615
616 // -- set operation fuzzers
617 template <typename S>
set_helper(const uint8_t * data,size_t size,Vec & v1,Vec & v2)618 static void set_helper (const uint8_t *data, size_t size, Vec &v1, Vec &v2)
619 {
620 assert(size > 1);
621
622 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());
631 }
632
633 enum class ParamKind {
634 OneValue,
635 TwoValues,
636 PointerRange
637 };
638
639 template <class IntT>
GetValues(const uint8_t * data,size_t size)640 std::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
652 enum InitKind {
653 Default,
654 DoubleOnly,
655 VectorDouble,
656 VectorResultType
657 };
658
659
660
661 template <class Dist>
662 struct 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, "");
Createfuzzing::ParamTypeHelper666 static ParamT Create(const uint8_t* data, size_t size, bool &OK) {
667
668 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
673 }
674
DispatchAndCreatefuzzing::ParamTypeHelper675 static ParamT DispatchAndCreate(std::integral_constant<int, 0>, const uint8_t *data, size_t size, bool &OK) {
676 return CreateVectorResult(data, size, OK);
677 }
DispatchAndCreatefuzzing::ParamTypeHelper678 static ParamT DispatchAndCreate(std::integral_constant<int, 1>, const uint8_t *data, size_t size, bool &OK) {
679 return CreateVectorDouble(data, size, OK);
680 }
DispatchAndCreatefuzzing::ParamTypeHelper681 static ParamT DispatchAndCreate(std::integral_constant<int, 2>, const uint8_t *data, size_t size, bool &OK) {
682 return CreateDefault(data, size, OK);
683 }
684
685 static ParamT
CreateVectorResultfuzzing::ParamTypeHelper686 CreateVectorResult(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
CreateVectorDoublefuzzing::ParamTypeHelper702 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
CreateDefaultfuzzing::ParamTypeHelper715 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
730 template <class IntT>
731 struct 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
Createfuzzing::ParamTypeHelper736 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
748 template <class IntT>
749 struct 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
Createfuzzing::ParamTypeHelper754 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
766 template <class IntT>
767 struct 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
Createfuzzing::ParamTypeHelper772 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
783 template <>
784 struct 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
Createfuzzing::ParamTypeHelper789 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
799 template <class Distribution>
random_distribution_helper(const uint8_t * data,size_t size)800 int 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 // FIXME(llvm.org/PR44289):
812 // Investigate why these distributions are returning NaN and decide
813 // if that's what we want them to be doing.
814 //
815 // Make this assert false (or return non-zero).
816 return 0;
817 }
818 return 0;
819 }
820
821 #define DEFINE_RANDOM_TEST(name, ...) \
822 int name(const uint8_t *data, size_t size) { \
823 return random_distribution_helper< std::name __VA_ARGS__ >(data, size); \
824 }
825 DEFINE_RANDOM_TEST(uniform_int_distribution,<std::int16_t>)
826 DEFINE_RANDOM_TEST(uniform_real_distribution,<float>)
827 DEFINE_RANDOM_TEST(bernoulli_distribution)
828 DEFINE_RANDOM_TEST(poisson_distribution,<std::int16_t>)
829 DEFINE_RANDOM_TEST(geometric_distribution,<std::int16_t>)
830 DEFINE_RANDOM_TEST(binomial_distribution, <std::int16_t>)
831 DEFINE_RANDOM_TEST(negative_binomial_distribution, <std::int16_t>)
832 DEFINE_RANDOM_TEST(exponential_distribution, <float>)
833 DEFINE_RANDOM_TEST(gamma_distribution, <float>)
834 DEFINE_RANDOM_TEST(weibull_distribution, <float>)
835 DEFINE_RANDOM_TEST(extreme_value_distribution, <float>)
836 DEFINE_RANDOM_TEST(normal_distribution, <float>)
837 DEFINE_RANDOM_TEST(lognormal_distribution, <float>)
838 DEFINE_RANDOM_TEST(chi_squared_distribution, <float>)
839 DEFINE_RANDOM_TEST(cauchy_distribution, <float>)
840 DEFINE_RANDOM_TEST(fisher_f_distribution, <float>)
841 DEFINE_RANDOM_TEST(student_t_distribution, <float>)
842 DEFINE_RANDOM_TEST(discrete_distribution, <std::int16_t>)
843 DEFINE_RANDOM_TEST(piecewise_constant_distribution, <float>)
844 DEFINE_RANDOM_TEST(piecewise_linear_distribution, <float>)
845
846 } // namespace fuzzing
847