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