|
150
|
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
|
|
|
55 stable_test(uint8_t k) : key(k), payload(0) {}
|
|
|
56 stable_test(uint8_t k, size_t p) : key(k), payload(p) {}
|
|
|
57 };
|
|
|
58
|
|
|
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 {
|
|
|
68 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 {
|
|
|
76 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 {
|
|
|
84 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
|
|
|
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 {
|
|
|
99 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 {
|
|
|
109 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
|
|
|
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>
|
|
|
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 ==
|
|
|
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 ==
|
|
|
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 ==
|
|
|
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 ==
|
|
|
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 ==
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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>
|
|
|
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 ==
|
|
|
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 ==
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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>
|
|
|
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>
|
|
|
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>
|
|
|
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, "");
|
|
|
666 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
|
|
|
675 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 }
|
|
|
684
|
|
|
685 static ParamT
|
|
|
686 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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
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
|
|
|
799 template <class Distribution>
|
|
|
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
|
