test: add script to mutate cpp files

brunoerg commented at 10:26 pm on March 7, 2022: contributor

I’ve been researching mutation testing and how we could use it here since we already have other automated tests. So, I created a Python script to mutate our cpp files. I created these scripts focused on mutating Bitcoin Core, this is not a general cpp one, so it mutates specific Core stuff like CAmount{} and other ones.

In test/mutation/consts.py you can find the operators and you can set what files you’d like to mutate:

0FILES = [
1    "src/wallet/coinselection.cpp",
2    # "src/wallet/spend.cpp",
3    # "src/net.cpp",
4    # "src/wallet/feebumper.cpp",
5    # "src/script/interpreter.cpp"
6]

This script mutates some consts by incresing/decreasing their value, e.g:

0from:
1const CAmount fee = 100;
2
3
4to:
5const CAmount fee = 75;
6or 
7const CAmount fee = 130;

All the mutators are saved in test/mutation/mutators, it generates one file per mutator.

Feel free to suggest anything, NACKs are welcome, I opened this PR because I use it a lot and I think it might be useful here.

DrahtBot added the label Scripts and tools on Mar 7, 2022

maflcko commented at 9:15 am on March 8, 2022: member

I don’t think we can run mutation tests in CI. If they are not deterministic or reproducible, they are of no use (in fact negative use). Moreover they require re-running the whole task, which is CPU intense and thus impossible to do in our current CI setup.

Doing this in a separate repository would probably give more flexibility and allow to move faster.

brunoerg commented at 11:33 am on March 8, 2022: contributor

I don’t think we can run mutation tests in CI. If they are not deterministic or reproducible, they are of no use (in fact negative use). Moreover they require re-running the whole task, which is CPU intense and thus impossible to do in our current CI setup.

Doing this in a separate repository would probably give more flexibility and allow to move faster.

Yeah, you’re right! Just edited the PR description.

laanwj commented at 11:54 am on March 8, 2022: member

Concept ACK on doing mutation testing though, and thanks for working on it, it’s been suggested quite a few times over the life of this project.

brunoerg force-pushed on Mar 9, 2022

maflcko commented at 1:08 pm on March 10, 2022: member

Yes, Concept ACK on mutation testing.

Last time I was looking into this I used dextool mutate ( https://github.com/joakim-brannstrom/dextool ), which covers C mutations, but no C++ STL ones.

There was also #22690 by @agroce .

Not sure what the shiniest mutation engine is these days, but if we are looking for one, I think we should pick one that makes it easy to categorize the surviving mutants. Some parts of our code are just impossible to reach (belt-and-suspender code, src/util/check.h-failures, …) and it would be good to have a mutation engine that can deal with this. It seems unlikely that we’ll do major refactors to our consensus code to kill mutants, so a mutation engine that can take the fingerprint of mutants and put them in a “harmless”-bucket seems ideal. This would be beneficial because a large part of mutation testing Bitcoin Core is categorizing mutants into harmless/harmful and doing it at most once per mutation allows more time to be spent on “fixing” the harmful ones.

agroce commented at 1:31 pm on March 10, 2022: contributor

UniversalMutator (https://github.com/agroce/universalmutator/tree/master/universalmutator) doesn’t have any special rules for C++ STL code, but they should be easy to add if you have anything in mind. If you have an idea of what would be useful to do to STL code, I imagine I could add it to UM myself.

UM supports annotating a line as DO_NOT_MUTATE permanently, and adding that for file or block of code would be easy (you can actually do it for a block/file now with an annotation marking as “test code” but it’d be nice to not have to claim the un-killable parts are test code).

Downside is UM is fairly slow at generation, and doesn’t inherently do any tricks to speed evaluation of mutants. But I’m not sure a currently working C/C++ tool exists that supports that kind of thing.

maflcko commented at 1:36 pm on March 10, 2022: member

With C++ STL stuff I mean mostly what is added in this pull (std::min<->std::max).

The issue with putting // DO_NOT_MUTATE into the source code in every line is that it makes the code more verbose and hard to follow, especially for consensus code.

agroce commented at 2:21 pm on March 10, 2022: contributor

Right. How about block or file level annotations? Would they be a pain? I assume most things you want to not mutate are entire sections or is it mostly individual lines?

An external, non-source notation for that has to be robust to still apply as the code changes, so I haven’t tackled it yet, but something might not be too hard to work up.

maflcko commented at 2:27 pm on March 10, 2022: member

I wonder if we could simply use the mutation-diff-hunks themselves as fingerprint? This would also make it easier to adjust them during a refactor/rename

agroce commented at 4:50 pm on March 10, 2022: contributor

That’s a pretty good idea, using the diffs. I was thinking it is sensitive to minor changes in the code, but as a method in addition to marking lines/chunks, it makes a lot of sense. And if the code substantially changes, you might want to revisit if it’s ignorable after all…

This kind of question is the engineering side of an NSF grant (https://www.nsf.gov/awardsearch/showAward?AWD_ID=2129446&HistoricalAwards=false) I’m working on with folks at Carnegie Mellon (@kjain and @clegoues, plus my student at NAU, @goutamkalburgi) so we have significant interest in getting this kind of question right for projects.

agroce commented at 4:51 pm on March 10, 2022: contributor

As to the STL, I actually now think that min <-> max and begin <-> end mutants are pretty useful and probably should just be at the any-language level, and so even potentially apply to non-library code. They’re semantic concepts, not just STL-specific. Are there others you have in mind?

agroce commented at 5:09 pm on March 10, 2022: contributor

Ok, min/max and begin/end mutants are in GitHub, will release to pip when I get a chance

https://github.com/agroce/universalmutator/commit/d0548384500bddfbe127d2d1a6bb4257ce731907

brunoerg commented at 6:29 pm on March 10, 2022: contributor

I’ll take a look at universalmutator. I’ve been testing mutate_cpp which is good but it is a complete app (with db, front-end, and so on.. not cool to use in here but as an external tool). This script I added here is simple and it’s more like a tool for devs than a complete test suite at this moment.

agroce commented at 6:31 pm on March 10, 2022: contributor

@brunoerg Universal Mutator is definitely meant to be scriptable; it’s pretty much meant for running inside “experiments” / CI / or other automation.

brunoerg commented at 6:35 pm on March 10, 2022: contributor

@brunoerg Universal Mutator is definitely meant to be scriptable; it’s pretty much meant for running inside “experiments” / CI / or other automation.

Cool, I am taking a look at it. Thanks!

brunoerg commented at 0:12 am on April 13, 2022: contributor

Hello, @agroce

I’ve been testing universalmutator for a time and I thought it very cool, especially because it is scriptable. I created a Python script similar to what I found on your tests folder and it worked very well with Bitcoin Core. I am using the functional tests to analyze the mutations. Compared to other libs I tested with the same proposal, universalmutation is one of my favorites (one of the reasons is the analyze_mutation).

However, since it is a tool for many languages, not 100% focused on C++, it makes some mistakes when mutating c++ files I guess.

Examples:

It mutate comments:

Before

0* The search continues to search for better solutions after one solution has been found. The best
1 * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
2 * spend the current inputs at the given fee rate minus the long term expected cost to spend the
3 * inputs, plus the amount by which the selection exceeds the spending target:
4 *
5 * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
6 *

After

0* The search continues to search for better solutions after one solution has been found. The best
1 * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
2 * spend the current inputs at the given fee rate minus the long term expected cost to spend the
3 * inputs, plus the amount by which the selection exceeds the spending target:
4 /
5 * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
6 *

or

0* The search continues to search for better solutions after one solution has been found. The best
1 * solution is chosen by minimizing the waste metric. The waste metric is defined as the cost to
2 continue; spend the current inputs at the given fee rate minus the long term expected cost to spend the
3 * inputs, plus the amount by which the selection exceeds the spending target:
4 continue;
5 * waste = selectionTotal - target + inputs × (currentFeeRate - longTermFeeRate)
6 *

I think it is considering the * as an operator even though it’s inside a comment block.

It mutates imports

Example:

Before

0#include <consensus/amount.h>
1#include <policy/feerate.h>
2#include <util/check.h>
3#include <util/system.h>
4#include <util/moneystr.h>

After

0#include <consensus/amount.h/
1#include <policy/feerate.h>
2#include <util/check.h>
3#include <util/system.h>
4#include <util/moneystr.h>

or

0#include <consensus/amount.h>
1#include <policy/feerate.h>
2#include <util/check.h<
3#include <util/system.h>
4#include <util/moneystr.h>

I think it’s unnecessary to mutate the includes. It is probably considering the < and > as operators even being in an include. Anyway, universalmutator is very good but needs some improves related to c++. I will create an issue in your repository pointing out some improvements in addition to those mentioned here.

Thanks.

agroce commented at 2:31 am on April 13, 2022: contributor

This is great. C++ rules could definitely use some improving! I’m surprised the “garbage check” rule didn’t avoid the comment changes, I’ll have to investigate. Unless you are turning that off for some reason?

brunoerg commented at 7:27 pm on April 16, 2022: contributor

Unless you are turning that off for some reason?

I don’t think I did it, but how can I check if I did it btw?

agroce commented at 10:33 pm on April 16, 2022: contributor

I think it is just what we noted in the issue: not using a check command to compile

brunoerg marked this as a draft on May 8, 2022

brunoerg force-pushed on May 9, 2022

test: add mutation test b681f21c41

brunoerg force-pushed on May 9, 2022

brunoerg renamed this:
~~test, devtools: add script to mutate cpp files~~
test: add script to mutate cpp files
on May 9, 2022

brunoerg commented at 2:21 pm on May 9, 2022: contributor

Force-pushed changing the approach!

I moved it from devtools to test, added more operators (now it mutates some Core stuff like CAmount) and now it creates one file per mutator and save it on test/mutation/mutators (so we can use analyze_mutators from @agroce`s project to test them).

Btw, I changed the description to fit on this new approach!

Thanks!

cc: @laanwj @MarcoFalke

agroce commented at 3:35 pm on May 9, 2022: contributor

@brunoerg I don’t know if it’s useful, but it’s easy to put those operators in a single custom file and call the tool to just run with those rules, on the set of files you have – don’t know if you want/need that, but it’s supported functionality, you don’t have to use the default rules applied to a file

brunoerg commented at 2:02 pm on May 26, 2022: contributor

I don’t know if it’s useful, but it’s easy to put those operators in a single custom file and call the tool to just run with those rules, on the set of files you have – don’t know if you want/need that, but it’s supported functionality, you don’t have to use the default rules applied to a file

Yeah, I noticed it, but I think it doesn’t cover 100% of the approach I am using here.

DrahtBot commented at 12:51 pm on September 23, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	laanwj, MarcoFalke

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

No conflicts as of last run.

aureleoules commented at 3:03 pm on December 1, 2022: member

I’ve been experimenting with mutation testing on my side as well. I built a tool to generate mutations and run the CI with different workers along with a web interface to sort mutations. I would appreciate any feedback on how to make it better. The code (bit ugly for now) is here https://github.com/aureleoules/bticoin-core-mutuaitons and the UI can be found here https://bcm-ui.aureleoules.com/.

fanquake commented at 3:38 pm on December 6, 2022: member

I think an external repository (as demonstrated above) is going to be a better place for scripting like this. Not only does that allow more frequent updates and new tests to be added, but the same repository can be used to store past/current interesting mutations found etc.

This is an approach already taken by other contributors with external tooling / fuzzers / etc.

brunoerg commented at 3:40 pm on December 6, 2022: contributor

I think an external repository (as demonstrated above) is going to be a better place for scripting like this. Not only does that allow more frequent updates and new tests to be added, but the same repository can be used to store past/current interesting mutations found etc.

This is an approach already taken by other contributors with external tooling / fuzzers / etc.

I agree! I’m working with @aureleoules on it in an external repo, going close this PR!

brunoerg closed this on Dec 6, 2022

bitcoin deleted a comment on Dec 6, 2022

bitcoin locked this on Dec 6, 2023

test: add script to mutate cpp files #24499

Reviews

Conflicts