test: add script to mutate cpp files #24499

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:

FILES = [
    "src/wallet/coinselection.cpp",
    # "src/wallet/spend.cpp",
    # "src/net.cpp",
    # "src/wallet/feebumper.cpp",
    # "src/script/interpreter.cpp"
]

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

from:
const CAmount fee = 100;


to:
const CAmount fee = 75;
or 
const 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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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?

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

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.

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

@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!

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:

1. It mutate comments:

Before

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

After

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

or

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

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

2. It mutates imports

Example:

Before

#include <consensus/amount.h>
#include <policy/feerate.h>
#include <util/check.h>
#include <util/system.h>
#include <util/moneystr.h>

After

#include <consensus/amount.h/
#include <policy/feerate.h>
#include <util/check.h>
#include <util/system.h>
#include <util/moneystr.h>

or

#include <consensus/amount.h>
#include <policy/feerate.h>
#include <util/check.h<
#include <util/system.h>
#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.

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?

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?

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

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

@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

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.

<!--e57a25ab6845829454e8d69fc972939a-->

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

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline for information on the review process.

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

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

No conflicts as of last run.

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/.

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 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!