[POC] Introducing property based testing to Core #8469

Christewart · 2016-08-06T01:48:20Z

This pull request is a proof of concept for introducting property based testing into Bitcoin Core

In QuickCheck the programmer writes assertions about logical properties that a function should fulfill. Then QuickCheck attempts to generate a test case that falsifies these assertions. Once such a test case is found, QuickCheck tries to reduce it to a minimal failing subset by removing or simplifying input data that are not needed to make the test fail.

This has been very useful for a Bitcoin library I've been working on and thought it would be worthwhile to develop a POC for Bitcoin Core. The property based library I am using for C++ is called rapidcheck. Here are the docs.

This pull request currently contains two properties, one testing CKey generation and the other testing serialization symmetry for CKey and CBitcoinSecret. These are rather trivial properties, but useful for illustrating the power of property based testing if there was a bug inside of Core.

I want to solicit some feedback from developers if this is something that would actually be merged into Core. Eventually we could have a large library of generators that would allow us to quickly prototype, test, and reason about the behavior of new code added to Core. Here is an example of a library of generators (in Scala) that could give you a little more of an idea of what I am talking about.

Thoughts?

fanquake · 2016-08-08T02:33:30Z

depends/packages/rapidcheck.mk

+
+$(package)_download_path:https://github.com/Christewart/rapidcheck/releases/download/1.0
+
+$(package)_file_name:rapidcheck-1.0.tar.gz


You should be able to use something like $(package)-$($(package)_version) here.

fanquake · 2016-08-08T02:35:37Z

This needs a rebase/conflicts fixed.

fanquake · 2016-08-08T02:36:35Z

src/test/key_properties.cpp

@@ -0,0 +1,48 @@
+// Copyright (c) 2012-2015 The Bitcoin Core developers


nit: Just 2016

maflcko · 2016-08-08T08:07:19Z

I think this approach of testing is interesting and may render useful for bitcoin. The user guide https://github.com/emil-e/rapidcheck/blob/master/doc/user_guide.md mentions that the API is not finalized, so it may be better to integrate it via a subtree (maybe in /test)?

jonasschnelli · 2016-08-08T08:09:27Z

I think this is useful. I'm not very familiar with property based testing, but this seems to be something that would make sense for consensus and security critical projects.

Some thoughts:

the rapidcheck dependency should probably only be required if one passes --enable-tests.
I think you can remove the changes in src/test/script_tests.cpp and its header.

If others also agree to take this into master, we should probably have a first logical slice of property based tests (maybe serialization).

Needs rebase.

maflcko · 2016-08-18T16:50:27Z

@theuni Can you help here to decide if using depends is fine or a subtree would be cleaner? (I prefer a subtree per my above comment, but I am not familiar with the build system. Input is appreciated)

Christewart · 2016-08-18T17:09:04Z

I would probably need help with the build code to get it production ready. I plan to keep on adding properties to this pull request though when time permits. I'm going to try and get around implementing fanquake's comments and figure out how to do the --enable-test as per jonasschnelli's comment this weekend

maflcko · 2016-08-19T10:52:02Z

depends/packages/rapidcheck.mk

+
+$(package)_version:1.0
+
+$(package)_download_path:https://github.com/Christewart/rapidcheck/releases/download/1.0


Again, I think a subtree is the better choice per my previous comment. Also, I don't think we can have someone verify this binary each time it is bumped, even if it was done deterministically.

Not sure what you mean about the deterministic bump. This is just a source tarball. Verifying would be no different than any of the other depends.

The general rule of thumb, though, is whether builders will be able to use it without any extra work. Since rapidcheck isn't present in any distros (as far as I can see), the answer to that is "no".

So, unless we're willing to require a depends build to run the new tests, a subtree would be easiest. However.

Tests are a bit of a special case. It may be reasonable to keep this in depends for now and let the c-i run it until there's sufficient coverage.

There's also the fact that it uses CMake, which we really don't want to introduce into our build (nothing against CMake, we just don't want to require every build tool under the sun).

Ok, fine with me. Thanks for letting us know.

maflcko · 2016-08-24T10:13:40Z

depends/packages/rapidcheck.mk

+
+$(package)_file_name=$(package)-$($(package)_version).tar.gz
+
+$(package)_sha256_hash=c228dc21ec24618bfb6afa31d622d1f4ea71168f04ee499e1ffcfc63cd5833f4


Can you try to adjust the folder name within the targz to have the version appened?

This may fix the travis issue.

I should note that I did NOT get any of this deterministic build working on my machine, I was trying to copy what I have seen on other other files to no avail -- I just ended up adding rapidcheck to my includes directory on my local machine. I'm fairly new to C++ & it's build systems so I was trying to just hack the pieces together. So I wouldn't be surprised if there are deeper issues than a naming issue although I will try and look at that later today. What exact name are you talking about? Are you talking about line 7? Line 5?

No worries, I don't understand cpp or the build system either. I can take a look later today... I think the issue is within the package you uploaded.

@Christewart Please try to fetch maflcko@befb827 (Mf1608-rapidcheckRework) and push it here. This should fix your compile issues for now.

Please note that travis will likely reject this due to a bug in gcc4.8.x: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55914

maflcko · 2016-08-29T07:55:12Z

@Christewart Do you need help to address the feedback from @jonasschnelli?

Christewart · 2016-08-29T12:42:09Z

@MarcoFalke Yeah I'm not really sure how to get that done

sipa · 2017-01-08T01:46:31Z

src/test/transaction_properties.cpp

+  CDataStream ss(SER_NETWORK, PROTOCOL_VERSION);
+  ss << tx;
+  deserialize_type t; 
+  CTransaction tx2(t,ss);


The intended idiom is just

CTransaction tx2(deserialize, ss);

gmaxwell · 2017-01-08T05:19:45Z

I like this kind of testing-- testing invariants on random test cases--, and we use it extensively in libsecp256k1. It's one of the answers to my irritation with the way many of the unit tests in Bitcoin core have worked in the past: hard-coding the exact behavior. Meaning that if you change anything, the tests all fail and you're left wondering if you broke something important or if the test was just mandating the behavior you were fixing. In either case, updating the test is often more work than the change.

Taking a dependency for it seems unfortunate; but I'm not qualified to judge if it does snazzy things that make generating cases easy. I have had bad experience with test frameworks in the past which had very high overhead making test cases that should have taken seconds take minutes, resulting in less testing. I see in this one that it uses a excessively slow PRNG based on skein, which makes me a bit dubious-- but if thats the only problem it would be easy to fix if we forked it (by replacing it with xorshift128+ or likewise).

Christewart · 2017-01-08T16:45:39Z

It should also be noted that they way the test are currently written they tie in the boost testing framework, if we add rapidcheck as a dependency and decide to remove boost, which #8670 suggests, we will have to rewrite these test cases to be independent of boost.

In terms of speed, you would know more than I would about choosing PRNG. Rapidcheck currently defaults to running 100 test cases against every property you have specified. You can configure this property to be higher or lower depending on the situation. I think it would make sense to configure this to lower value for local development, and a higher value for travis builds to try and exhaustively test our invariants. You can read more about configuration of rapidcheck here.

@jonasschnelli 's comment above was interesting I thought, I'm not super familiar with C++ build systems but only including the rapidcheck dependency if the flag --enable-test flag was given seems to makes sense.

I think the long term value add here is having a library of generators (for various protocol data structures) that we can use to test new protocol changes. I'm going to be adding some properties about creating tx types in the coming weeks. To get an idea of what I'm looking to add, you can look at some of the generators I have created in bitcoin-s.

DrahtBot · 2018-08-05T17:45:32Z

Needs rebase

practicalswift · 2018-08-28T20:18:18Z

@Christewart This is excellent work! Do you have time to rebase this and take it to completion, or do you prefer if someone else takes over this work? It is too good to be left unfinished :-)

Christewart · 2018-08-28T20:23:04Z

Hi @practicalswift it seems like the consensus is moving to #12775 which is a subset of the PR. It includes just the build stuff and a subset of the tests in this PR.

practicalswift · 2018-08-28T20:38:18Z

@Christewart Oh, sorry! That one is rebased and nice! Thanks!

…in Core b2f49bd Integration of property based testing into Bitcoin Core (Chris Stewart) Pull request description: This PR is a subset of the changes in bitcoin#8469. It's meant to be easier to review. This PR contains all of the build instructions needed for travis to pass. It includes one property call `key_properties.cpp` along with a generator file called `crypto_gen.{h,cpp}`. Tree-SHA512: 895c9d9273dcd29f696b1de8dfe1ee843095831bf1f68472844181278850bec36b20f0ba7e51e796112c5cc75cd24759f9f1771906503bbf3af16f627e18c6c9

DrahtBot · 2018-09-09T15:51:50Z

Needs rebase

Empact · 2018-10-08T23:59:33Z

src/test/gen/block_gen.h

+#include <rapidcheck/Gen.h>
+
+
+typedef std::tuple<int32_t, uint256, uint256, uint32_t, uint32_t, uint32_t> BlockHeaderTup;


nit: using?

Empact · 2018-10-09T00:07:14Z

src/test/gen/bloom_gen.cpp

+    });
+}
+
+rc::Gen<unsigned int> Between1And100()


nit: looks like this method is defined with the same name here and in merkleblock_gen.h, how about:

applying static more liberally?

renaming one or the other?

Empact · 2018-10-09T00:30:19Z

Moving my review to #14430, which along with #12775 was extracted from this. @Christewart should this be closed?

fanquake · 2018-10-10T02:39:46Z

This was superseded by #12775 and #14430.

8276e70 Adding assert to avoid a memory access violation inside of PartialMerkleTree::CalcHash() (Chris Stewart) Pull request description: Fixing a possible memory access violation in CPartialMerkleTree::CalcHash(). This can happen if we some how a merkle tree with zero txids. I don't think this can happen in practice as we only send merkle block messages on the p2p network as of now -- we cannot receive them. This was found with bitcoin#8469, specifically using this [generator](https://github.com/Christewart/bitcoin/blob/rapidcheck/src/test/gen/merkleblock_gen.h#L52-L77) which will cause a memory access violation on [this test case](https://github.com/Christewart/bitcoin/blob/rapidcheck/src/test/merkleblock_properties.cpp#L48). Tree-SHA512: b95904ec45ea3f082c7722161d93ee06b24c706fbffa909a6e995ed14788aed2830f91b626da6f0347660c45874a0735dab61c9440b59c949c690af4165c83fb

fanquake reviewed Aug 8, 2016
View reviewed changes

src/test/key_properties.cpp Outdated

@@ -0,0 +1,48 @@

// Copyright (c) 2012-2015 The Bitcoin Core developers

Copy link

Member

fanquake Aug 8, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: Just 2016

jonasschnelli added Feature Tests and removed Feature labels Aug 8, 2016

maflcko reviewed Aug 19, 2016
View reviewed changes

Christewart force-pushed the rapidcheck branch 4 times, most recently from b735c19 to 0a658bb Compare August 21, 2016 23:58

maflcko reviewed Aug 24, 2016
View reviewed changes

Christewart mentioned this pull request Sep 7, 2016

Replacing Boost Test Framework #8670

Closed

sipa reviewed Jan 8, 2017

View reviewed changes

Christewart mentioned this pull request Mar 12, 2017

Fix mem access violation merkleblock #9980

Merged

Christewart force-pushed the rapidcheck branch 2 times, most recently from 70042aa to 6c929c0 Compare April 7, 2017 15:52

This was referenced Jul 22, 2018

Add aarch64 qt depends support for cross compiling bitcoin-qt #13696

Merged

[build] Add risc-v support to gitian #13665

Merged

Christewart mentioned this pull request Jul 24, 2018

Bugfixes for BIP 174 combining and deserialization #13721

Merged

DrahtBot added the Needs rebase label Aug 5, 2018

maflcko removed the Needs rebase label Sep 9, 2018

DrahtBot added the Needs rebase label Sep 9, 2018

Christewart mentioned this pull request Oct 8, 2018

Add more property based tests for basic bitcoin data structures #14430

Closed

Empact reviewed Oct 8, 2018

View reviewed changes

Empact reviewed Oct 9, 2018

View reviewed changes

fanquake closed this Oct 10, 2018

fanquake removed the Needs rebase label Oct 10, 2018

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021


		$(package)_download_path:https://github.com/Christewart/rapidcheck/releases/download/1.0

		$(package)_file_name:rapidcheck-1.0.tar.gz

		@@ -0,0 +1,48 @@
		// Copyright (c) 2012-2015 The Bitcoin Core developers


		$(package)_version:1.0

		$(package)_download_path:https://github.com/Christewart/rapidcheck/releases/download/1.0


		$(package)_file_name=$(package)-$($(package)_version).tar.gz

		$(package)_sha256_hash=c228dc21ec24618bfb6afa31d622d1f4ea71168f04ee499e1ffcfc63cd5833f4

		#include <rapidcheck/Gen.h>


		typedef std::tuple<int32_t, uint256, uint256, uint32_t, uint32_t, uint32_t> BlockHeaderTup;

[POC] Introducing property based testing to Core #8469

[POC] Introducing property based testing to Core #8469

Uh oh!

Conversation

Christewart commented Aug 6, 2016 • edited by DrahtBot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

fanquake commented Aug 8, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

maflcko commented Aug 8, 2016 via email

Uh oh!

jonasschnelli commented Aug 8, 2016

Uh oh!

maflcko commented Aug 18, 2016

Uh oh!

Christewart commented Aug 18, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

maflcko commented Aug 29, 2016

Uh oh!

Christewart commented Aug 29, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gmaxwell commented Jan 8, 2017

Uh oh!

Christewart commented Jan 8, 2017

Uh oh!

DrahtBot commented Aug 5, 2018

Uh oh!

practicalswift commented Aug 28, 2018

Uh oh!

Christewart commented Aug 28, 2018

Uh oh!

practicalswift commented Aug 28, 2018

Uh oh!

DrahtBot commented Sep 9, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Empact commented Oct 9, 2018

Uh oh!

fanquake commented Oct 10, 2018

Uh oh!

Uh oh!

Christewart commented Aug 6, 2016 •

edited by DrahtBot

Loading

Christewart commented Aug 18, 2016 •

edited

Loading