Mutation Driven Testing: When TDD Just Isn’t Good Enough
software.rajivprab.com
software.rajivprab.com
Though it's turned up some testing inadequacies here and there and a substantial performance improvement ( https://twitter.com/pwuille/status/1348835954396516353 ), I don't believe it's yet caught a bug there, but I do feel a lot more confident in the tests as a result.
I've also deployed it to a lesser degree in the Bitcoin codebase and turned up some minor bugs as a result of the tests being improved to pass mutation testing.
The biggest challenge I've seen for most parties to use mutation testing is that to begin with you must have 100% branch coverage of the code you might mutate, and very few ordinary pieces of software reach that level of coverage.
The next issue is that in C/C++ there really aren't any great tools that I'm aware of-- so every effort needs to be homebrewed.
My process is to have some a harness script that:
1. makes a modification (e.g. a python script that does small search and replacements one at a time line by line, or just doing it by hand).
2. attempts to compile the code (if it fails, move on to the next change)
3. Compares the hash of the optimized binary to a collection of already tested hashes and moves onto the next if it's already been seen.
4. Runs the tests and if the tests pass save off the diff.
5. Goto 1.
Then I go back trough the diffs and toss ones that are obviously no meaningful effect, and lob the remaining diffs over to other contributors to figure out if they're false positives or to improve the tests.
I'm looking forward to seeing more people use it, once it has been added to the golang testing tools:
https://go.googlesource.com/proposal/+/master/design/draft-f...
In several of my projects I thought I had good testing, but still found issues within 20 minutes of fuzzing. Wonderful to be able to find them so easily.
Mutation testing alters the system under test to identify under-specified (under-tested) portions, rather than explore the input space.
The bane of mutation testing is equivalent mutants: mutations that aren't actually bugs, because they leave the program correct.
That's one reason I check the hash of the optimized binaries-- often the compiler manages to convert different but equivalent code into the same binary. It's still not enough, but it's an easy filter to apply with no false exclusions.
Have you looked at Mull[1] or Dextool[2]?
[1] https://github.com/mull-project/mull
[2] https://github.com/joakim-brannstrom/dextool/tree/master/plu...
There's lots of great tools that help with mutation testing, though they can be expensive to run (depending on how they work and how many tests you have). In a past life, I wrote my own mutation testing library which run the tests after each mutation and generated a "reverse code coverage" report: essentially a report of which lines/functions/statements/etc. did not cause the tests to fail when mutated. Where code coverage is ideally approaching 100%, the reverse code coverage should have been near 0%. If you take the intersection of a coverage report with a reverse coverage report, you can easily find code that is executed, but whose behavior is not checked.
From the abstract:
> We focus on a code-review based approach and consider the effects of surfacing mutation results on developer attention. The described system is used by 6,000 engineers in Google on all code changes they author or review, affecting in total more than 14,000 code authors as part of the mandatory code review process.
The last 100% test coverage advocate I mentioned it to said it would be a waste of developer effort. I assume they feel that effort would be better spent writing more tests.
Basically what this is is writing tests for your tests. And because the input of tests is functions you need to be able to generate functions. That’s nice but it’s a pain considering the only solution proposed is “just do it manually” which is neither exhaustive nor trustworthy.
Also every single of the author’s exemple is caught by an actually good testing tool like QuickCheck.
I'd be interested to see what a sufficiently strong QuickCheck specification of this problem would look like. I've used it a bit in the past, but not enough that I could reliably get it to produce all the interesting failure modes and know the expected result for each case.
I would write something like this in haskell:
spec :: [Integer] -> Property
spec xs =
length xs <= 2 ==> fun (intercalate "," (map show xs)) == sum xs
This captures the three requirements, but not the implicit fourth requirement that the function throws an exception for other inputs.You could probably generate invalid inputs by taking a list of strings as input. Though of course at that point the property test has to reimplement half the function.
That's an issue I often end up having with property tests: the oracle for interesting properties is as complex as the SUT, so you end up with two of them.
Edit: To elaborate a bit, programming is naturally limited by the programmer's imagination, too. But what alternative is offered is a much more interesting topic than just disregarding something because it isn't a perfect solution.
Testing with mutations is certainly interesting but I never had the opportunity to try it.
True, but in my experience this kind of testing tools do only complement testing. They should never be used to replace proper manually written tests as they are probability based and as long as the input domain is large enough it's quite viable to miss very obvious bugs not just in one rune but repeatedly.
Through if you are under time pressure it can be a good idea to, replace writing some relatively unimportant test with writing generative tests. Just only start doing so after you cover the most important parts with your manual tests.
It's kinda sad but for a lot of applications making the main features in their main use-case work right, and bringing out more main features, is more important then making all features always right but have less of them. In the end a imperfect but reasonable well working product (especially if all the small demo cases work) sells better then a perfect but very constrained product.
Who are the proponents of TDD that promote 100% adherence even when it's not a good match for the situation? I keep coming across this claim, but it's not how I learned TDD, and I wonder if it's a straw man.
As an example. I was taught about object-calisthenics[1] in school. The lecturer treated a straw man version of it, and I thought about this like that for a while. What’s worse, when I later thought it was a good exercise and explained it to others I noticed I always have to reiterate multiple times that this set of rules is meant as an exercise of exploration, not a set of hard rules for whatever piece of code you are going to write next.
TDD is just so easy to turn into a straw man, and I think it has so many hardcore fans that makes it even worse to present the nuanced form of it.
[1] https://williamdurand.fr/2013/06/03/object-calisthenics/
If you know what result you want. It's easy to apply. Assert on the output.
If you don't know what you want, you can't apply it. Because you can't write the asserts.
So you can do exploratory implementation as long as you know the result you're looking for. But I'd also argue you want to have an idea about what you want before you start writing code. So I don't find that many places where it doesn't apply.
One of the few ones where it doesn't apply is tweaking the UI for looks.
Kent Beck recently went through and clarified TDD and he definitely doesn't advocate 100%. https://youtube.com/playlist?list=PLlmVY7qtgT_lkbrk9iZNizp97...
- Writing tests first.
- Have a write test => write code => loop.
But there are some people which are pedantic about how small the loop needs to be or insisting that TDD excludes doing any planing about aspects like how you likely will structure code on a larger picture and similar (i.e. software architecture).
At the same time there are tools/library/framework/language combinations which are testing in generally really hard and can play really bad with TDD. While I believe such tools should be avoided there are situations in which you can not do so and in which you furthermore due to e.g. time constraints are simile not able to do any proper testing including TDD. It's kinda a nightmare situations but it does happen.
EDIT: Yes I realized I responded to the wrong comment :(
While nobody proposes TDD "when it's not a good match", plenty of people overestimate the cases where they think it's a good match.
Plenty of TDD proponents believe you shouldn't write a single line of code without a test first. I've met them, and they believe it's a good match for the situation.
It's not helped by notorious failures like the infamous sudoku puzzle debacle -- a case where it was evidently not suitable, yet Jeffries went ahead and tried it anyway (and failed, predictably). The conclusion that TDD was not suitable for this kind of algorithmic exploratory development was somehow never reached...
My experiences were very similar to the author’s when I first started using it. Even though my test coverage was near 100%, the mutations introduced revealed that in large part my tests were fallible due to assumptions I’d made when writing them.
I’ve incorporated mutation testing as the final step in my CI workflow as a test for my tests. It’s a fair bit of work the first time it’s run (especially with larger libraries), but in my opinion vital as a pairing with tests.
I really like encoding failure types into the type signature of my code (assuming types).
defa(x: str) -> Union[str, AnErrorType]:
That way, it is clear that your code may fail, and so you must test the unhappy path as well. Limits the places you might be able to throw and read/write input, and requires an effect type, but keeping functions total allows for fewer bugs and fewer places to test horrible things happening.In many cases, this isn’t too difficult, but most bugs I encounter are ones that I never would have considered; no matter how much thought I devoted to the matter.
In my experience, there’s just no way to predict all the bugs, and it isn’t helpful to ever assume that my test suites have full coverage, even if I use a scientific approach to writing tests.
The author mentioned one aspect of TDD that has always bothered me: that I can’t “explore.” My basic design philosophy is “Pave The Bare Spots”[0]. This means that I develop the design as I develop the code[1].
Rigid philosophies like TDD spike this methodology. What I tend to do, is rely on test harnesses, as opposed to unit tests[2].
In any case, I definitely support any effort to improve fundamental software quality. I feel as if the classic “rush to MVP at any cost” approach results in enormous tech debt that never gets repaid.
Obligatory XKCD: https://xkcd.com/2030/
[0] https://littlegreenviper.com/miscellany/the-road-most-travel...
[1] https://littlegreenviper.com/miscellany/evolutionary-design-...
[2] https://littlegreenviper.com/miscellany/testing-harness-vs-u...
This is the Nirvana Fallacy, "if it isn't perfect, it's useless". Fine, you can't predict all the bugs. But you can predict some, perhaps many. That is strictly more robust than not predicting at all.
> The author mentioned one aspect of TDD that has always bothered me: that I can’t “explore.” ... Rigid philosophies like TDD spike this methodology.
"Spike" is the word TDD weirdoes like me use to say we are exploring. TDD requires enough knowledge to specify the problem in a way that drives out code. When you don't have that knowledge, you explore first.
I've had codebases where I wrote and discarded untested code multiple times in order to understand what design I needed. Once I began to grok the problem, I backed out and then test-drove my way back in.
But as I explained in [2], I usually (not all the time) tend to write unit tests after the fact. This is something that seems to get TDD folks all hot and bothered.
My development testing is usually done with test harnesses. You can call it "spike," or whatever.
Actually, as I write this, I am taking a break from some fairly significant refactoring of a backend server that I wrote a couple of years ago[0]. It's a layered system, with each layer having a standalone product lifecycle and integrated tests.
I have a plan for the feature that I'm adding, but not a full project timeline. I have already encountered a couple of places where I deviated from my plan, and I'm barely getting started.
At this layer, the tests are more like test harnesses, than complete unit tests. By the time I get to BASALT (the top layer), the tests are pretty much complete unit tests, examining and reporting on results. At this level, my tests basically output runtime data, below an explanation of what we want to see in that data, so that means I need to spend quality time, reviewing the output. By the time I get to BASALT, I can just scan the reports, looking for red and green; which is good, because I run thousands of tests, by then. At this point, I'll be running less than a hundred tests.
So I guess all my tests are "spike" tests.
[0] https://riftvalleysoftware.com/work/open-source-projects/#ba...
Test harnesses are really a different thing and I think they're always a good idea. I like to test "outside-in", I think it's good at preventing low-level assumptions from upsetting the top level. But again, it depends on the code and context.
As an aside, small studies of test-before vs test-after show that in terms of bug yield, there's no major difference. Over the long term I think they diverge. That means that the magic of TDD isn't that it causes you to write better code than writing tests afterwards. It's that it forces you to write tests at all. TDD is eating your vegetables first.
I like that philosophy.
I spent many years, at an insanely quality-driven company. I wanted to strangle the QA folks on many occasions, but they trained me to not accept crap.
According to a lot of people, that disqualifies me from working at startups.
I'll have to let the folks at the startup I'm working with know that. They'll need to shop around for a slob that will work for free.
The idea here is to deliberately inject bugs to see if your tests catches them.
Much less manual work and with more stable results.
Tests are a (very) nice additional benefit, particularly because it has a simple way of ensuring coverage: only allowed to write production code if there is a failing test case, and only enough to make it pass.
I am a little leery of yet another buzzword though. Reading the article just made me think yeah, you should rigorously think about what you're actually specifying, whether it's by formal or informal reasoning. I would actually claim the code the author picked on was in fact correct by definition since it satisfied its tests. It just didn't do what the article author figured it should do. The "mutation" is just a relatively cumbersome way to think through strengthening the specification. It's not clear to me that it's more productive to identify gaps in an implicit specification by breaking one's implementation rather than strengthening the tests, but I wouldn't be surprised if I have done so in some cases where for whatever reason it struck me as more pragmatic.
I have a bad tendency to over complicate things because I often see many of the potential future complications and other aspects of the larger picture which I really should ignore at that point of writing.
In turn a TDD programing approach gives me a nice degree of value at the moment of writing. The larger and more complicate the resulting program will be the more value I get out of it.
> think through strengthening the specification.
Having a weak/incorrect specification is a very common problem on larger projects especially if the projects are writen by one company for a different company (and just them).
Through mutation testing your code won't help there, but similar practices can help in finding gaps and problems with a non-code specification, too.
IMHO this isn't quite right, in my experience it's a programming technique. I.e. a way to approach programming applications. But it's not a technique for designing applications.
Sure sometimes you can "just write" an applications without caring about design. But in many many other cases just doing TDD without any proper designing will make you destined to fail to deliver a well working product. (At least in the field of larger applications which often need interoperability with all kind of other applications.)
You still need to think, for example. And you can't skip the "refactoring" step, because that is where you get to do much of the design that TDD helps you with.
For example. You want a function to test if a number is prime. You write the test: 4 is not prime, 5 is prime, 6 is not, 7 is prime, 8 and 9 are not. Now you write a function: n is prime if it is odd. Fails the tests: because it tells you that 9 is prime. You "fix" the code by checking that the number is not dividable by 3, it passes the tests, done.
Instead of writing code to solve a problem, you write tests to model the problem then you write code to pass the tests, there is an extra level of indirection and something may get lost along the way.
The only significant advantage of TDD I can think of is that you can't "forget" to write tests.
In fact, you are almost doing TDD, but missing the final step: Refactor Mercilessly
http://c2.com/xp/RefactorMercilessly.html
TDD directly helps you with interface design, that is how the pieces fit together. It helps you indirectly with the design of your implementations, because it enables this merciless refactoring."you write tests to model the problem then you write code to pass the tests"
Exactly! And once you have the code that passes the tests, and have written enough of it to have somewhat decent coverage for the problem-space, you can then refactor the implementation.
That is where you can go wild with your ideas, because you are only making changes to code that is already working and protected by a test-suite.
https://stackoverflow.com/questions/78806/refactor-mercilessly-or-build-one-to-throw-away#78844
For me this splitting of the very difficult programming tasks into 3 distinct and much simpler steps is the beauty of TDD:1. Figure out the problem (write a spec as executable tests)
2. Make it work (just write trivial code to get the tests green)
3. Refactor (go wild with your design ideas, make sure tests stay green)