From 55608455cbed4234f26f62ed9ff500fe5dbc21c4 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 4 Apr 2020 16:15:18 -0700 Subject: Make a fuzzer-based copy of the prevector randomized test --- src/Makefile.test.include | 7 ++ src/test/fuzz/prevector.cpp | 291 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 298 insertions(+) create mode 100644 src/test/fuzz/prevector.cpp (limited to 'src') diff --git a/src/Makefile.test.include b/src/Makefile.test.include index c3021743f4..82975aadbe 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -58,6 +58,7 @@ FUZZ_TARGETS = \ test/fuzz/parse_numbers \ test/fuzz/parse_script \ test/fuzz/parse_univalue \ + test/fuzz/prevector \ test/fuzz/partial_merkle_tree_deserialize \ test/fuzz/partially_signed_transaction_deserialize \ test/fuzz/pow \ @@ -609,6 +610,12 @@ test_fuzz_parse_univalue_LDADD = $(FUZZ_SUITE_LD_COMMON) test_fuzz_parse_univalue_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) test_fuzz_parse_univalue_SOURCES = test/fuzz/parse_univalue.cpp +test_fuzz_prevector_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) +test_fuzz_prevector_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) +test_fuzz_prevector_LDADD = $(FUZZ_SUITE_LD_COMMON) +test_fuzz_prevector_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) +test_fuzz_prevector_SOURCES = test/fuzz/prevector.cpp + test_fuzz_partial_merkle_tree_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DPARTIAL_MERKLE_TREE_DESERIALIZE=1 test_fuzz_partial_merkle_tree_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_fuzz_partial_merkle_tree_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON) diff --git a/src/test/fuzz/prevector.cpp b/src/test/fuzz/prevector.cpp new file mode 100644 index 0000000000..45452c85c2 --- /dev/null +++ b/src/test/fuzz/prevector.cpp @@ -0,0 +1,291 @@ +// Copyright (c) 2015-2020 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include +#include + +#include +#include + +#include +#include +#include + +namespace { + +template +class prevector_tester { + typedef std::vector realtype; + realtype real_vector; + realtype real_vector_alt; + + typedef prevector pretype; + pretype pre_vector; + pretype pre_vector_alt; + + typedef typename pretype::size_type Size; + bool passed = true; + + template + void local_check_equal(A a, B b) + { + local_check(a == b); + } + + void local_check(bool b) + { + passed &= b; + } + void test() { + const pretype& const_pre_vector = pre_vector; + local_check_equal(real_vector.size(), pre_vector.size()); + local_check_equal(real_vector.empty(), pre_vector.empty()); + for (Size s = 0; s < real_vector.size(); s++) { + local_check(real_vector[s] == pre_vector[s]); + local_check(&(pre_vector[s]) == &(pre_vector.begin()[s])); + local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s)); + local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size())); + } + // local_check(realtype(pre_vector) == real_vector); + local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector); + local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector); + size_t pos = 0; + for (const T& v : pre_vector) { + local_check(v == real_vector[pos++]); + } + for (const T& v : reverse_iterate(pre_vector)) { + local_check(v == real_vector[--pos]); + } + for (const T& v : const_pre_vector) { + local_check(v == real_vector[pos++]); + } + for (const T& v : reverse_iterate(const_pre_vector)) { + local_check(v == real_vector[--pos]); + } + CDataStream ss1(SER_DISK, 0); + CDataStream ss2(SER_DISK, 0); + ss1 << real_vector; + ss2 << pre_vector; + local_check_equal(ss1.size(), ss2.size()); + for (Size s = 0; s < ss1.size(); s++) { + local_check_equal(ss1[s], ss2[s]); + } + } + +public: + void resize(Size s) { + real_vector.resize(s); + local_check_equal(real_vector.size(), s); + pre_vector.resize(s); + local_check_equal(pre_vector.size(), s); + test(); + } + + void reserve(Size s) { + real_vector.reserve(s); + local_check(real_vector.capacity() >= s); + pre_vector.reserve(s); + local_check(pre_vector.capacity() >= s); + test(); + } + + void insert(Size position, const T& value) { + real_vector.insert(real_vector.begin() + position, value); + pre_vector.insert(pre_vector.begin() + position, value); + test(); + } + + void insert(Size position, Size count, const T& value) { + real_vector.insert(real_vector.begin() + position, count, value); + pre_vector.insert(pre_vector.begin() + position, count, value); + test(); + } + + template + void insert_range(Size position, I first, I last) { + real_vector.insert(real_vector.begin() + position, first, last); + pre_vector.insert(pre_vector.begin() + position, first, last); + test(); + } + + void erase(Size position) { + real_vector.erase(real_vector.begin() + position); + pre_vector.erase(pre_vector.begin() + position); + test(); + } + + void erase(Size first, Size last) { + real_vector.erase(real_vector.begin() + first, real_vector.begin() + last); + pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last); + test(); + } + + void update(Size pos, const T& value) { + real_vector[pos] = value; + pre_vector[pos] = value; + test(); + } + + void push_back(const T& value) { + real_vector.push_back(value); + pre_vector.push_back(value); + test(); + } + + void pop_back() { + real_vector.pop_back(); + pre_vector.pop_back(); + test(); + } + + void clear() { + real_vector.clear(); + pre_vector.clear(); + } + + void assign(Size n, const T& value) { + real_vector.assign(n, value); + pre_vector.assign(n, value); + } + + Size size() const { + return real_vector.size(); + } + + Size capacity() const { + return pre_vector.capacity(); + } + + void shrink_to_fit() { + pre_vector.shrink_to_fit(); + test(); + } + + void swap() { + real_vector.swap(real_vector_alt); + pre_vector.swap(pre_vector_alt); + test(); + } + + void move() { + real_vector = std::move(real_vector_alt); + real_vector_alt.clear(); + pre_vector = std::move(pre_vector_alt); + pre_vector_alt.clear(); + } + + void copy() { + real_vector = real_vector_alt; + pre_vector = pre_vector_alt; + } + + void resize_uninitialized(realtype values) { + size_t r = values.size(); + size_t s = real_vector.size() / 2; + if (real_vector.capacity() < s + r) { + real_vector.reserve(s + r); + } + real_vector.resize(s); + pre_vector.resize_uninitialized(s); + for (auto v : values) { + real_vector.push_back(v); + } + auto p = pre_vector.size(); + pre_vector.resize_uninitialized(p + r); + for (auto v : values) { + pre_vector[p] = v; + ++p; + } + test(); + } + + ~prevector_tester() { + assert(passed); + } +}; + +} + +void test_one_input(const std::vector& buffer) +{ + FuzzedDataProvider prov(buffer.data(), buffer.size()); + prevector_tester<8, int> test; + + while (prov.remaining_bytes()) { + switch (prov.ConsumeIntegralInRange(0, 14 + 3 * (test.size() > 0))) { + case 0: + test.insert(prov.ConsumeIntegralInRange(0, test.size()), prov.ConsumeIntegral()); + break; + case 15: + test.erase(prov.ConsumeIntegralInRange(0, test.size() - 1)); + break; + case 1: + test.resize(std::max(0, std::min(30, (int)test.size() + prov.ConsumeIntegralInRange(0, 4) - 2))); + break; + case 2: + test.insert(prov.ConsumeIntegralInRange(0, test.size()), 1 + prov.ConsumeBool(), prov.ConsumeIntegral()); + break; + case 3: { + int del = std::min(test.size(), 1 + prov.ConsumeBool()); + int beg = prov.ConsumeIntegralInRange(0, test.size() - del); + test.erase(beg, beg + del); + break; + } + case 4: + test.push_back(prov.ConsumeIntegral()); + break; + case 16: + test.pop_back(); + break; + case 5: { + int values[4]; + int num = 1 + prov.ConsumeIntegralInRange(0, 3); + for (int k = 0; k < num; ++k) { + values[k] = prov.ConsumeIntegral(); + } + test.insert_range(prov.ConsumeIntegralInRange(0, test.size()), values, values + num); + break; + } + case 6: { + int del = std::min(test.size(), 1 + prov.ConsumeIntegralInRange(0, 3)); + int beg = prov.ConsumeIntegralInRange(0, test.size() - del); + test.erase(beg, beg + del); + break; + } + case 7: + test.reserve(prov.ConsumeIntegralInRange(0, 32767)); + break; + case 8: + test.shrink_to_fit(); + break; + case 17: + test.update(prov.ConsumeIntegralInRange(0, test.size() - 1), prov.ConsumeIntegral()); + break; + case 9: + test.clear(); + break; + case 10: + test.assign(prov.ConsumeIntegralInRange(0, 32767), prov.ConsumeIntegral()); + break; + case 11: + test.swap(); + break; + case 12: + test.copy(); + break; + case 13: + test.move(); + break; + case 14: { + int num = 1 + prov.ConsumeIntegralInRange(0, 15); + std::vector values(num); + for (auto& v : values) { + v = prov.ConsumeIntegral(); + } + test.resize_uninitialized(values); + break; + } + } + } +} -- cgit v1.2.3 From eda8309bfc6a8c94f0b7c076d1cccc86c1011cbc Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 4 Apr 2020 16:26:01 -0700 Subject: Assert immediately rather than caching failure --- src/test/fuzz/prevector.cpp | 57 ++++++++++++++++++--------------------------- 1 file changed, 23 insertions(+), 34 deletions(-) (limited to 'src') diff --git a/src/test/fuzz/prevector.cpp b/src/test/fuzz/prevector.cpp index 45452c85c2..74c1f8d469 100644 --- a/src/test/fuzz/prevector.cpp +++ b/src/test/fuzz/prevector.cpp @@ -25,68 +25,61 @@ class prevector_tester { pretype pre_vector_alt; typedef typename pretype::size_type Size; - bool passed = true; - template - void local_check_equal(A a, B b) - { - local_check(a == b); - } - - void local_check(bool b) - { - passed &= b; - } void test() { const pretype& const_pre_vector = pre_vector; - local_check_equal(real_vector.size(), pre_vector.size()); - local_check_equal(real_vector.empty(), pre_vector.empty()); + assert(real_vector.size() == pre_vector.size()); + assert(real_vector.empty() == pre_vector.empty()); for (Size s = 0; s < real_vector.size(); s++) { - local_check(real_vector[s] == pre_vector[s]); - local_check(&(pre_vector[s]) == &(pre_vector.begin()[s])); - local_check(&(pre_vector[s]) == &*(pre_vector.begin() + s)); - local_check(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size())); + assert(real_vector[s] == pre_vector[s]); + assert(&(pre_vector[s]) == &(pre_vector.begin()[s])); + assert(&(pre_vector[s]) == &*(pre_vector.begin() + s)); + assert(&(pre_vector[s]) == &*((pre_vector.end() + s) - real_vector.size())); } - // local_check(realtype(pre_vector) == real_vector); - local_check(pretype(real_vector.begin(), real_vector.end()) == pre_vector); - local_check(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector); + // assert(realtype(pre_vector) == real_vector); + assert(pretype(real_vector.begin(), real_vector.end()) == pre_vector); + assert(pretype(pre_vector.begin(), pre_vector.end()) == pre_vector); size_t pos = 0; for (const T& v : pre_vector) { - local_check(v == real_vector[pos++]); + assert(v == real_vector[pos]); + ++pos; } for (const T& v : reverse_iterate(pre_vector)) { - local_check(v == real_vector[--pos]); + --pos; + assert(v == real_vector[pos]); } for (const T& v : const_pre_vector) { - local_check(v == real_vector[pos++]); + assert(v == real_vector[pos]); + ++pos; } for (const T& v : reverse_iterate(const_pre_vector)) { - local_check(v == real_vector[--pos]); + --pos; + assert(v == real_vector[pos]); } CDataStream ss1(SER_DISK, 0); CDataStream ss2(SER_DISK, 0); ss1 << real_vector; ss2 << pre_vector; - local_check_equal(ss1.size(), ss2.size()); + assert(ss1.size() == ss2.size()); for (Size s = 0; s < ss1.size(); s++) { - local_check_equal(ss1[s], ss2[s]); + assert(ss1[s] == ss2[s]); } } public: void resize(Size s) { real_vector.resize(s); - local_check_equal(real_vector.size(), s); + assert(real_vector.size() == s); pre_vector.resize(s); - local_check_equal(pre_vector.size(), s); + assert(pre_vector.size() == s); test(); } void reserve(Size s) { real_vector.reserve(s); - local_check(real_vector.capacity() >= s); + assert(real_vector.capacity() >= s); pre_vector.reserve(s); - local_check(pre_vector.capacity() >= s); + assert(pre_vector.capacity() >= s); test(); } @@ -199,10 +192,6 @@ public: } test(); } - - ~prevector_tester() { - assert(passed); - } }; } -- cgit v1.2.3 From 402ad5aaca9509d45d861d77eb6431d6e1944f91 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 6 Apr 2020 14:31:14 -0700 Subject: Only run sanity check once at the end --- src/test/fuzz/prevector.cpp | 19 ++++--------------- 1 file changed, 4 insertions(+), 15 deletions(-) (limited to 'src') diff --git a/src/test/fuzz/prevector.cpp b/src/test/fuzz/prevector.cpp index 74c1f8d469..39320c1216 100644 --- a/src/test/fuzz/prevector.cpp +++ b/src/test/fuzz/prevector.cpp @@ -26,7 +26,8 @@ class prevector_tester { typedef typename pretype::size_type Size; - void test() { +public: + void test() const { const pretype& const_pre_vector = pre_vector; assert(real_vector.size() == pre_vector.size()); assert(real_vector.empty() == pre_vector.empty()); @@ -66,13 +67,11 @@ class prevector_tester { } } -public: void resize(Size s) { real_vector.resize(s); assert(real_vector.size() == s); pre_vector.resize(s); assert(pre_vector.size() == s); - test(); } void reserve(Size s) { @@ -80,56 +79,47 @@ public: assert(real_vector.capacity() >= s); pre_vector.reserve(s); assert(pre_vector.capacity() >= s); - test(); } void insert(Size position, const T& value) { real_vector.insert(real_vector.begin() + position, value); pre_vector.insert(pre_vector.begin() + position, value); - test(); } void insert(Size position, Size count, const T& value) { real_vector.insert(real_vector.begin() + position, count, value); pre_vector.insert(pre_vector.begin() + position, count, value); - test(); } template void insert_range(Size position, I first, I last) { real_vector.insert(real_vector.begin() + position, first, last); pre_vector.insert(pre_vector.begin() + position, first, last); - test(); } void erase(Size position) { real_vector.erase(real_vector.begin() + position); pre_vector.erase(pre_vector.begin() + position); - test(); } void erase(Size first, Size last) { real_vector.erase(real_vector.begin() + first, real_vector.begin() + last); pre_vector.erase(pre_vector.begin() + first, pre_vector.begin() + last); - test(); } void update(Size pos, const T& value) { real_vector[pos] = value; pre_vector[pos] = value; - test(); } void push_back(const T& value) { real_vector.push_back(value); pre_vector.push_back(value); - test(); } void pop_back() { real_vector.pop_back(); pre_vector.pop_back(); - test(); } void clear() { @@ -152,13 +142,11 @@ public: void shrink_to_fit() { pre_vector.shrink_to_fit(); - test(); } void swap() { real_vector.swap(real_vector_alt); pre_vector.swap(pre_vector_alt); - test(); } void move() { @@ -190,7 +178,6 @@ public: pre_vector[p] = v; ++p; } - test(); } }; @@ -277,4 +264,6 @@ void test_one_input(const std::vector& buffer) } } } + + test.test(); } -- cgit v1.2.3 From c2ccadc26a04358b11539097c1aadb8d11b85c21 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 6 Apr 2020 14:37:37 -0700 Subject: Merge and generalize case 3 and case 6 --- src/test/fuzz/prevector.cpp | 14 ++++---------- 1 file changed, 4 insertions(+), 10 deletions(-) (limited to 'src') diff --git a/src/test/fuzz/prevector.cpp b/src/test/fuzz/prevector.cpp index 39320c1216..4154d9c713 100644 --- a/src/test/fuzz/prevector.cpp +++ b/src/test/fuzz/prevector.cpp @@ -189,7 +189,7 @@ void test_one_input(const std::vector& buffer) prevector_tester<8, int> test; while (prov.remaining_bytes()) { - switch (prov.ConsumeIntegralInRange(0, 14 + 3 * (test.size() > 0))) { + switch (prov.ConsumeIntegralInRange(0, 13 + 3 * (test.size() > 0))) { case 0: test.insert(prov.ConsumeIntegralInRange(0, test.size()), prov.ConsumeIntegral()); break; @@ -203,7 +203,7 @@ void test_one_input(const std::vector& buffer) test.insert(prov.ConsumeIntegralInRange(0, test.size()), 1 + prov.ConsumeBool(), prov.ConsumeIntegral()); break; case 3: { - int del = std::min(test.size(), 1 + prov.ConsumeBool()); + int del = prov.ConsumeIntegralInRange(0, test.size()); int beg = prov.ConsumeIntegralInRange(0, test.size() - del); test.erase(beg, beg + del); break; @@ -223,19 +223,13 @@ void test_one_input(const std::vector& buffer) test.insert_range(prov.ConsumeIntegralInRange(0, test.size()), values, values + num); break; } - case 6: { - int del = std::min(test.size(), 1 + prov.ConsumeIntegralInRange(0, 3)); - int beg = prov.ConsumeIntegralInRange(0, test.size() - del); - test.erase(beg, beg + del); - break; - } case 7: test.reserve(prov.ConsumeIntegralInRange(0, 32767)); break; case 8: test.shrink_to_fit(); break; - case 17: + case 14: test.update(prov.ConsumeIntegralInRange(0, test.size() - 1), prov.ConsumeIntegral()); break; case 9: @@ -253,7 +247,7 @@ void test_one_input(const std::vector& buffer) case 13: test.move(); break; - case 14: { + case 6: { int num = 1 + prov.ConsumeIntegralInRange(0, 15); std::vector values(num); for (auto& v : values) { -- cgit v1.2.3 From b1d24d1d031a2b2ce67bf846bafa1c3a499b7553 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 6 Apr 2020 14:51:38 -0700 Subject: Reorder the test instructions by number --- src/test/fuzz/prevector.cpp | 34 +++++++++++++++++----------------- 1 file changed, 17 insertions(+), 17 deletions(-) (limited to 'src') diff --git a/src/test/fuzz/prevector.cpp b/src/test/fuzz/prevector.cpp index 4154d9c713..0e51ee3c95 100644 --- a/src/test/fuzz/prevector.cpp +++ b/src/test/fuzz/prevector.cpp @@ -193,9 +193,6 @@ void test_one_input(const std::vector& buffer) case 0: test.insert(prov.ConsumeIntegralInRange(0, test.size()), prov.ConsumeIntegral()); break; - case 15: - test.erase(prov.ConsumeIntegralInRange(0, test.size() - 1)); - break; case 1: test.resize(std::max(0, std::min(30, (int)test.size() + prov.ConsumeIntegralInRange(0, 4) - 2))); break; @@ -211,9 +208,6 @@ void test_one_input(const std::vector& buffer) case 4: test.push_back(prov.ConsumeIntegral()); break; - case 16: - test.pop_back(); - break; case 5: { int values[4]; int num = 1 + prov.ConsumeIntegralInRange(0, 3); @@ -223,15 +217,21 @@ void test_one_input(const std::vector& buffer) test.insert_range(prov.ConsumeIntegralInRange(0, test.size()), values, values + num); break; } + case 6: { + int num = 1 + prov.ConsumeIntegralInRange(0, 15); + std::vector values(num); + for (auto& v : values) { + v = prov.ConsumeIntegral(); + } + test.resize_uninitialized(values); + break; + } case 7: test.reserve(prov.ConsumeIntegralInRange(0, 32767)); break; case 8: test.shrink_to_fit(); break; - case 14: - test.update(prov.ConsumeIntegralInRange(0, test.size() - 1), prov.ConsumeIntegral()); - break; case 9: test.clear(); break; @@ -247,15 +247,15 @@ void test_one_input(const std::vector& buffer) case 13: test.move(); break; - case 6: { - int num = 1 + prov.ConsumeIntegralInRange(0, 15); - std::vector values(num); - for (auto& v : values) { - v = prov.ConsumeIntegral(); - } - test.resize_uninitialized(values); + case 14: + test.update(prov.ConsumeIntegralInRange(0, test.size() - 1), prov.ConsumeIntegral()); + break; + case 15: + test.erase(prov.ConsumeIntegralInRange(0, test.size() - 1)); + break; + case 16: + test.pop_back(); break; - } } } -- cgit v1.2.3