Author: marshall
Date: Wed Oct 4 15:23:03 2017
New Revision: 314940
URL: http://llvm.org/viewvc/llvm-project?rev=314940&view=rev
Log:
Initial cut at infastructure for fuzzing support for OSS-fuzz
Added:
libcxx/trunk/fuzzing/
libcxx/trunk/fuzzing/fuzzing.cpp
libcxx/trunk/fuzzing/fuzzing.h
libcxx/trunk/test/libcxx/fuzzing/
libcxx/trunk/test/libcxx/fuzzing/nth_element.cpp
libcxx/trunk/test/libcxx/fuzzing/partial_sort.cpp
libcxx/trunk/test/libcxx/fuzzing/partition.cpp
libcxx/trunk/test/libcxx/fuzzing/sort.cpp
libcxx/trunk/test/libcxx/fuzzing/stable_partition.cpp
libcxx/trunk/test/libcxx/fuzzing/stable_sort.cpp
Added: libcxx/trunk/fuzzing/fuzzing.cpp
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/fuzzing/fuzzing.cpp?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/fuzzing/fuzzing.cpp (added)
+++ libcxx/trunk/fuzzing/fuzzing.cpp Wed Oct 4 15:23:03 2017
@@ -0,0 +1,222 @@
+// -*- C++ -*-
+//===------------------------- fuzzing.cpp -------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// A set of routines to use when fuzzing the algorithms in libc++
+// Each one tests a single algorithm.
+//
+// They all have the form of:
+// int `algorithm`(const uint8_t *data, size_t size);
+//
+// They perform the operation, and then check to see if the results are
correct.
+// If so, they return zero, and non-zero otherwise.
+//
+// For example, sort calls std::sort, then checks two things:
+// (1) The resulting vector is sorted
+// (2) The resulting vector contains the same elements as the
original data.
+
+
+
+#include "fuzzing.h"
+#include <vector>
+#include <algorithm>
+
+#include <iostream>
+
+// If we had C++14, we could use the four iterator version of
is_permutation
+
+namespace fuzzing {
+
+// This is a struct we can use to test the stable_XXX algorithms.
+// perform the operation on the key, then check the order of the payload.
+
+struct stable_test {
+ uint8_t key;
+ uint8_t payload;
+
+ stable_test(uint8_t k) : key(k), payload(0) {}
+ stable_test(uint8_t k, uint8_t p) : key(k), payload(p) {}
+ };
+
+void swap(stable_test &lhs, stable_test &rhs)
+{
+ using std::swap;
+ swap(lhs.key, rhs.key);
+ swap(lhs.payload, rhs.payload);
+}
+
+struct key_less
+{
+ bool operator () (const stable_test &lhs, const stable_test &rhs) const
+ {
+ return lhs.key < rhs.key;
+ }
+};
+
+struct payload_less
+{
+ bool operator () (const stable_test &lhs, const stable_test &rhs) const
+ {
+ return lhs.payload < rhs.payload;
+ }
+};
+
+struct total_less
+{
+ bool operator () (const stable_test &lhs, const stable_test &rhs) const
+ {
+ return lhs.key == rhs.key ? lhs.payload < rhs.payload : lhs.key
< rhs.key;
+ }
+};
+
+bool operator==(const stable_test &lhs, const stable_test &rhs)
+{
+ return lhs.key == rhs.key && lhs.payload == rhs.payload;
+}
+
+
+template<typename T>
+struct is_even
+{
+ bool operator () (const T &t) const
+ {
+ return t % 2 == 0;
+ }
+};
+
+
+template<>
+struct is_even<stable_test>
+{
+ bool operator () (const stable_test &t) const
+ {
+ return t.key % 2 == 0;
+ }
+};
+
+// == sort ==
+
+int sort(const uint8_t *data, size_t size)
+{
+ std::vector<uint8_t> working(data, data + size);
+ std::sort(working.begin(), working.end());
+
+ if (!std::is_sorted(working.begin(), working.end())) return 1;
+ if (!std::is_permutation(data, data + size, working.begin())) return 99;
+ return 0;
+}
+
+
+// == stable_sort ==
+
+int stable_sort(const uint8_t *data, size_t size)
+{
+ std::vector<stable_test> input;
+ for (size_t i = 0; i < size; ++i)
+ input.push_back(stable_test(data[i], i));
+ std::vector<stable_test> working = input;
+ std::stable_sort(working.begin(), working.end(), key_less());
+
+ if (!std::is_sorted(working.begin(), working.end(), key_less()))
return 1;
+ auto iter = working.begin();
+ while (iter != working.end())
+ {
+ auto range = std::equal_range(iter, working.end(), *iter,
key_less());
+ if (!std::is_sorted(range.first, range.second, total_less()))
return 2;
+ iter = range.second;
+ }
+ if (!std::is_permutation(input.begin(), input.end(), working.begin()))
return 99;
+ return 0;
+}
+
+// == partition ==
+
+int partition(const uint8_t *data, size_t size)
+{
+ std::vector<uint8_t> working(data, data + size);
+ auto iter = std::partition(working.begin(), working.end(),
is_even<uint8_t>());
+
+ if (!std::all_of (working.begin(), iter, is_even<uint8_t>())) return 1;
+ if (!std::none_of(iter, working.end(), is_even<uint8_t>())) return 2;
+ if (!std::is_permutation(data, data + size, working.begin())) return 99;
+ return 0;
+}
+
+
+// == stable_partition ==
+
+int stable_partition (const uint8_t *data, size_t size)
+{
+ std::vector<stable_test> input;
+ for (size_t i = 0; i < size; ++i)
+ input.push_back(stable_test(data[i], i));
+ std::vector<stable_test> working = input;
+ auto iter = std::stable_partition(working.begin(), working.end(),
is_even<stable_test>());
+
+ if (!std::all_of (working.begin(), iter, is_even<stable_test>()))
return 1;
+ if (!std::none_of(iter, working.end(), is_even<stable_test>()))
return 2;
+ if (!std::is_sorted(working.begin(), iter, payload_less())) return 3;
+ if (!std::is_sorted(iter, working.end(), payload_less())) return 4;
+ if (!std::is_permutation(input.begin(), input.end(), working.begin()))
return 99;
+ return 0;
+}
+
+// == nth_element ==
+// use the first element as a position into the data
+int nth_element (const uint8_t *data, size_t size)
+{
+ if (size <= 1) return 0;
+ const size_t partition_point = data[0] % size;
+ std::vector<uint8_t> working(data + 1, data + size);
+ const auto partition_iter = working.begin() + partition_point;
+ std::nth_element(working.begin(), partition_iter, working.end());
+
+// nth may be the end iterator, in this case nth_element has no effect.
+ if (partition_iter == working.end())
+ {
+ if (!std::equal(data + 1, data + size, working.begin())) return
98;
+ }
+ else
+ {
+ const uint8_t nth = *partition_iter;
+ if (!std::all_of(working.begin(), partition_iter, [=](uint8_t
v) { return v <= nth; }))
+ return 1;
+ if (!std::all_of(partition_iter, working.end(), [=](uint8_t
v) { return v >= nth; }))
+ return 2;
+ if (!std::is_permutation(data + 1, data + size,
working.begin())) return 99;
+ }
+
+ return 0;
+}
+
+// == partial_sort ==
+// use the first element as a position into the data
+int partial_sort (const uint8_t *data, size_t size)
+{
+ if (size <= 1) return 0;
+ const size_t sort_point = data[0] % size;
+ std::vector<uint8_t> working(data + 1, data + size);
+ const auto sort_iter = working.begin() + sort_point;
+ std::partial_sort(working.begin(), sort_iter, working.end());
+
+ if (sort_iter != working.end())
+ {
+ const uint8_t nth = *std::min_element(sort_iter, working.end());
+ if (!std::all_of(working.begin(), sort_iter, [=](uint8_t v) {
return v <= nth; }))
+ return 1;
+ if (!std::all_of(sort_iter, working.end(), [=](uint8_t v) {
return v >= nth; }))
+ return 2;
+ }
+ if (!std::is_sorted(working.begin(), sort_iter)) return 3;
+ if (!std::is_permutation(data + 1, data + size, working.begin()))
return 99;
+
+ return 0;
+}
+
+} // namespace fuzzing
Added: libcxx/trunk/fuzzing/fuzzing.h
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/fuzzing/fuzzing.h?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/fuzzing/fuzzing.h (added)
+++ libcxx/trunk/fuzzing/fuzzing.h Wed Oct 4 15:23:03 2017
@@ -0,0 +1,33 @@
+// -*- C++ -*-
+//===-------------------------- fuzzing.h --------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_FUZZING
+#define _LIBCPP_FUZZING
+
+#include <cstddef> // for size_t
+#include <cstdint> // for uint8_t
+
+namespace fuzzing {
+
+// These all return 0 on success; != 0 on failure
+ int sort (const uint8_t *data, size_t size);
+ int stable_sort (const uint8_t *data, size_t size);
+ int partition (const uint8_t *data, size_t size);
+ int stable_partition (const uint8_t *data, size_t size);
+
+// partition and stable_partition take Bi-Di iterators.
+// Should test those, too
+
+ int nth_element (const uint8_t *data, size_t size);
+ int partial_sort (const uint8_t *data, size_t size);
+
+} // namespace fuzzing
+
+#endif // _LIBCPP_FUZZING
Added: libcxx/trunk/test/libcxx/fuzzing/nth_element.cpp
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/libcxx/fuzzing/nth_element.cpp?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/test/libcxx/fuzzing/nth_element.cpp (added)
+++ libcxx/trunk/test/libcxx/fuzzing/nth_element.cpp Wed Oct 4 15:23:03 2017
@@ -0,0 +1,38 @@
+// -*- C++ -*-
+//===----------------------- nth_element.cpp
------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// XFAIL
+
+#include "fuzzing.h"
+#include <cassert>
+#include <cstring> // for strlen
+
+const char * test_cases[] = {
+ "",
+ "s",
+ "bac",
+ "bacasf"
+ "lkajseravea",
+ "adsfkajdsfjkas;lnc441324513,34535r34525234"
+ };
+
+const size_t k_num_tests = sizeof(test_cases)/sizeof(test_cases[0]);
+
+
+int main ()
+{
+ for (size_t i = 0; i < k_num_tests; ++i)
+ {
+ const size_t size = std::strlen(test_cases[i]);
+ const uint8_t *data = (const uint8_t *) test_cases[i];
+ assert(0 == fuzzing::nth_element(data, size));
+ }
+ return 0;
+}
Added: libcxx/trunk/test/libcxx/fuzzing/partial_sort.cpp
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/libcxx/fuzzing/partial_sort.cpp?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/test/libcxx/fuzzing/partial_sort.cpp (added)
+++ libcxx/trunk/test/libcxx/fuzzing/partial_sort.cpp Wed Oct 4 15:23:03 2017
@@ -0,0 +1,38 @@
+// -*- C++ -*-
+//===-------------------------- partial_sort.cpp
--------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// XFAIL
+
+#include "fuzzing.h"
+#include <cassert>
+#include <cstring> // for strlen
+
+const char * test_cases[] = {
+ "",
+ "s",
+ "bac",
+ "bacasf"
+ "lkajseravea",
+ "adsfkajdsfjkas;lnc441324513,34535r34525234"
+ };
+
+const size_t k_num_tests = sizeof(test_cases)/sizeof(test_cases[0]);
+
+
+int main ()
+{
+ for (size_t i = 0; i < k_num_tests; ++i)
+ {
+ const size_t size = std::strlen(test_cases[i]);
+ const uint8_t *data = (const uint8_t *) test_cases[i];
+ assert(0 == fuzzing::partial_sort(data, size));
+ }
+ return 0;
+}
Added: libcxx/trunk/test/libcxx/fuzzing/partition.cpp
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/libcxx/fuzzing/partition.cpp?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/test/libcxx/fuzzing/partition.cpp (added)
+++ libcxx/trunk/test/libcxx/fuzzing/partition.cpp Wed Oct 4 15:23:03 2017
@@ -0,0 +1,38 @@
+// -*- C++ -*-
+//===--------------------------- partition.cpp
----------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// XFAIL
+
+#include "fuzzing.h"
+#include <cassert>
+#include <cstring> // for strlen
+
+const char * test_cases[] = {
+ "",
+ "s",
+ "bac",
+ "bacasf"
+ "lkajseravea",
+ "adsfkajdsfjkas;lnc441324513,34535r34525234"
+ };
+
+const size_t k_num_tests = sizeof(test_cases)/sizeof(test_cases[0]);
+
+
+int main ()
+{
+ for (size_t i = 0; i < k_num_tests; ++i)
+ {
+ const size_t size = std::strlen(test_cases[i]);
+ const uint8_t *data = (const uint8_t *) test_cases[i];
+ assert(0 == fuzzing::partition(data, size));
+ }
+ return 0;
+}
Added: libcxx/trunk/test/libcxx/fuzzing/sort.cpp
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/libcxx/fuzzing/sort.cpp?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/test/libcxx/fuzzing/sort.cpp (added)
+++ libcxx/trunk/test/libcxx/fuzzing/sort.cpp Wed Oct 4 15:23:03 2017
@@ -0,0 +1,38 @@
+// -*- C++ -*-
+//===--------------------------- sort.cpp
---------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// XFAIL
+
+#include "fuzzing.h"
+#include <cassert>
+#include <cstring> // for strlen
+
+const char * test_cases[] = {
+ "",
+ "s",
+ "bac",
+ "bacasf"
+ "lkajseravea",
+ "adsfkajdsfjkas;lnc441324513,34535r34525234"
+ };
+
+const size_t k_num_tests = sizeof(test_cases)/sizeof(test_cases[0]);
+
+
+int main ()
+{
+ for (size_t i = 0; i < k_num_tests; ++i)
+ {
+ const size_t size = std::strlen(test_cases[i]);
+ const uint8_t *data = (const uint8_t *) test_cases[i];
+ assert(0 == fuzzing::sort(data, size));
+ }
+ return 0;
+}
Added: libcxx/trunk/test/libcxx/fuzzing/stable_partition.cpp
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/libcxx/fuzzing/stable_partition.cpp?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/test/libcxx/fuzzing/stable_partition.cpp (added)
+++ libcxx/trunk/test/libcxx/fuzzing/stable_partition.cpp Wed Oct 4 15:23:03
2017
@@ -0,0 +1,38 @@
+// -*- C++ -*-
+//===--------------------- stable_partition.cpp
---------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// XFAIL
+
+#include "fuzzing.h"
+#include <cassert>
+#include <cstring> // for strlen
+
+const char * test_cases[] = {
+ "",
+ "s",
+ "bac",
+ "bacasf"
+ "lkajseravea",
+ "adsfkajdsfjkas;lnc441324513,34535r34525234"
+ };
+
+const size_t k_num_tests = sizeof(test_cases)/sizeof(test_cases[0]);
+
+
+int main ()
+{
+ for (size_t i = 0; i < k_num_tests; ++i)
+ {
+ const size_t size = std::strlen(test_cases[i]);
+ const uint8_t *data = (const uint8_t *) test_cases[i];
+ assert(0 == fuzzing::stable_partition(data, size));
+ }
+ return 0;
+}
Added: libcxx/trunk/test/libcxx/fuzzing/stable_sort.cpp
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/test/libcxx/fuzzing/stable_sort.cpp?rev=314940&view=auto
==============================================================================
--- libcxx/trunk/test/libcxx/fuzzing/stable_sort.cpp (added)
+++ libcxx/trunk/test/libcxx/fuzzing/stable_sort.cpp Wed Oct 4 15:23:03 2017
@@ -0,0 +1,38 @@
+// -*- C++ -*-
+//===------------------------ stable_sort.cpp ----------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// XFAIL
+
+#include "fuzzing.h"
+#include <cassert>
+#include <cstring> // for strlen
+
+const char * test_cases[] = {
+ "",
+ "s",
+ "bac",
+ "bacasf"
+ "lkajseravea",
+ "adsfkajdsfjkas;lnc441324513,34535r34525234"
+ };
+
+const size_t k_num_tests = sizeof(test_cases)/sizeof(test_cases[0]);
+
+
+int main ()
+{
+ for (size_t i = 0; i < k_num_tests; ++i)
+ {
+ const size_t size = std::strlen(test_cases[i]);
+ const uint8_t *data = (const uint8_t *) test_cases[i];
+ assert(0 == fuzzing::stable_sort(data, size));
+ }
+ return 0;
+}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
