# Mutation Testing with Vertigo by Joran Honig

- Speakers: Joran Honig
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2020-10-09
- Duration: 26:16
- Topics: blockchain, smart contracts, distributed ledger, ethereum, ethereum solidity, solidity, solidity summit, language design
- Watch: https://streameth.org/watch/yt-L4npZCDyTr0
- YouTube: https://www.youtube.com/watch?v=L4npZCDyTr0

## Description

An introduction to mutation testing and the tool Vertigo, including a discussion where solc, Truffle, and Vertigo could work together.

## Transcript

All right. So, I'm also going to be talking about testing, um but uh specifically mutation testing, which is kind of a meta subject. Uh so, a little bit of background, um I uh wrote a tool called Vertigo, uh which the implements mutation testing for smart contracts, which I released um about a year ago. Um and uh in this presentation uh I'll first give a little bit of background on mutation testing, a crash course of sorts, and then um I'd like to talk about the features that are currently in uh the mutation testing tool, and the features that I would like to add, and how um kind of other parts of the technology stack can enable uh these features, uh because um the mutation testing tool's kind of built on top of uh um other tools, like uh the Solidity compiler. Um when we talk about mutation testing, uh you almost always first have to talk about code coverage. And um code coverage is this ubiquitous method which is used to evaluate test suites at the moment. Um I think almost all uh people will will use this metric to see whether um their test suite is adequate. Uh but there's a few issues with code coverage. Specifically, it doesn't really tell you anything about the code that you do cover, but it does tell you uh something, namely the code that you do don't cover yet. Um so, it is actually a very useful metric because it it helps you improve it. It tells you where where to change your tests uh to um have a better test suite to have better guarantees. Um mutation testing on the other hand uh tries to improve on this metric uh by telling you exactly how efficient your test suite is at detecting bugs, rather than just telling you which part uh of the code are are covered. Which is great because it allows you to uh improve your test suite even more efficiently. It also gives you a nice measure of the guarantees uh given by your test suite. Uh so kind of to give an overview of mutation testing, uh this is the general strategy. Um we start out by creating a lot of bugs uh which could be introduced in a a Solidity project. Then um we run the test suite for each bug and see if the bug is detected. And then we know something about which where these bugs uh that didn't get detected live and we can improve the test suite. So generating these bugs, how does this happen? So in mutation testing uh we call these bugs mutants uh because they are mutations of the original program and we use so-called mutation operators to take the original project and modify it to get get this um uh um bug in the program. And mutation operators are basically rules. Uh they can be substitution rules which describe how how to inject bugs, basically. And uh for the tool Vertigo, what I did is I looked at existing tools um for the mutation operators used there, also in previous um research. Uh and I implemented some that are somewhat specific to the weaknesses that happen in Solidity smart contracts. As to give you an example um of what mutation operators do is I have a made a little table. Uh so, for example, we swap uh the addition sign uh with a subtraction. Um another one which I really like is the modifier removal mutation operator, uh where we take a look at the source code and um to generate a bug, we remove a modifier. And what I like about this is that it kind of emulates a case where a developer forgets to introduce some authorization and authentication logic, which which generally um is used uh which generally is implemented using modifiers such as the only owner um modifier. Um after having generated a bunch of bugs, uh we we get to a part where we need to evaluate them to know like whether the test we detect some or not, um which is the next next uh step. Um so, kind of the two basic things uh that can happen are the test suite succeeds or it fails. So, if the test the suite succeeds, that means that we were not actually able to find a bug or the bug introduced bug, um in which case the the mutant uh survived, uh and we call the mutant alive. The other case is where the test suite fails, in which case um the mutant is detected and we say it's killed or dead. Um then there's two two additional categories to deal with Uh uh some edge cases. So, for example, what could happen is a mutation operator modifies a piece of code that results in invalid solidity. In which case the compiler will not successfully compile. Um and we cannot even run the test suite. So, in this case we say the mutant is errored. Uh the fourth case is timed out, um which we have included because mutants can also introduce infinite loops. Uh so, what we do, we take a timeout based on the original time that a test suite took, and after this time that has expired, we uh kill the execution of the test suite and we categorize the the mutant as timed out. So, then there's this fifth category, which I put in in brackets because it's not really a category on its own, but rather a specific instance of a live mutant. So, what mutation operators also can do is modify code so that there is a syntactic change while not changing the underlying meaning of the code. So, to give you an example, um I have uh the implementation of the the max function by OpenZeppelin. And as you can see, there's a slight difference here in the comparison operator. However, so the difference lies at a point where A and B are equal. But for the evaluation of the max function, it doesn't really matter which branch you take when A and B are equal because both will be the max number. So, this is an equivalent mutant and we don't really want to account for this as an alive mutant because the test suite um was not insufficient. Um it it it was doing okay because this is actually also correct. Um so, unfortunately, this process is somewhat manual and uh we have I've implemented some feature to automate this a little bit, but it's not possible to automate that in general. Uh so, there will always be some um categorization manual categorization required when you're performing mutation testing. Once we have categorized all the mutants, we can compute the mutation score, which is kind of similar to the the code coverage metric, but in this case, we're talking about the efficiency of detecting bugs of the test suite. So, we actu- we the the mutation score is computed um using this formula and it's basically the rate um at which you detect uh mutants. So, you take total number of mutants that you killed or that were detected and divide it by the total number of valid mutants. So, these are the non-equivalent alive mutants and the killed mutants. We disregard the other ones for the mutation score. So, this gives you a general metric of the quality of your test suite and then the specific uh surviving mutations tell you something uh give you really detailed information about which part of the code you could improve. Or you could improve the test speed for rather. Okay. So, that was kind of a bird's-eye view of mutation testing theory. Right now, I'd like to go over a few of the features that are in Vertigo the tool right now. Then, what's kind of on my wish list, followed by how kind of the foundational technology such as the compiler or test frameworks can enable or support the development of these features. So, first, what do we have today? There's a few features listed here, which which I think are kind of the main ones. And the first one is parallel evaluation, which is pretty straightforward. Instead of running the test speeds sequentially for each mutant, we run them in parallel. Most of the times there's going to be a lot of tests, so we won't run all of them in parallel, but we'll be able to use whatever computational resources your machine might have. The second optimization is mutant sampling, where instead of taking the entire set of mutants we've generated in the first phase, we take a random sample of those. This will give you an estimation of what the original mutation score would have been while drastically reducing the time you need to compute it. And there's a balance here because there's of course an accuracy because you're taking a random sample. Um the third really nice feature what I think is a really nice feature is the support of universal mutator style rules. So, this is a project in for general mutation testing where the authors have designed a method of formulating um mutation rules uh using regex patterns. Um and this will allow you to easily develop and demo uh different mutation rules. But, what it will also do is enable you to write mutation rules specific to a certain project. For example, you might be able to write mutation rules for a specific SafeMath library. And here I have a little example from the universal mutator repository itself, uh which describes some mutation rules for Solidity, specifically uh the time keywords. Uh so, this should give you some idea of uh what this um is capable of. So, lastly, we have compiler equivalence, uh which is enabled by the Solidity compiler, um and this has to do with um these equivalent mutations. So, what Vertigo does is it takes the original program and the mutated program, and it will compile both. It will then compare the generated bytecodes, and if they are equal, conclude that therefore also the source code must have been equal in meaning, and it will disregard um the the mutant entirely. So, it won't even start the testing process. Um this assumes, of course, that the compiler is correct. Um and and let's hope it is. Okay, so what's next? Um there's kind of two categories. Um first is optimizations, the other is usability. Um there's no time to really do a demo, but um these would really help. Um but first, optimization. So, um first is uh incremental evaluation. And um this would be really nice to have um because uh you in in a regular scenario, uh you would be running mutation testing every once in a while, maybe. And between those runs, um you could reuse a a lot of information. So, for example, what you can do is um look at the previous analysis results and look at which um test killed which mutant. And if you see the same mutant again, try to find that test and run specifically that test first instead of running the entire test suite. Um that can save a lot of time. So, maybe 80% of of the mutants will be killed by the same test, and that will save a ton on execution time because you won't have to execute the entire test suite every time. Then, there's uh mutant clustering, and mutant clustering is kind of similar to uh mutant sampling, but instead of taking a sample from the entire set of mutants, we group them first um and take samples from the groups. And this gives a more accurate estimation of the uh mutation score. The third optimization which I really would like to have is test selection based on code coverage. So, what we do is um given detailed information on the coverage, specifically um you'd want to know which tests cover which lines of code, you'd select just those tests um that cover a mutant to to evaluate, rather than the entire test suite. So, assume for example that each mutant will only be covered by 10% of the test suite. Then this optimization will give you a performance improvement of 10 times, which is huge. It takes like a a Well, it's huge. Anyway, so then there's a usability aspect. So I didn't get to show this, but if you set up Vertigo to run parallel evaluation, then you have to instantiate bunch of Ganache networks. Um and well this setup process shouldn't really be necessary, I think. And I think removing that will make setting up a mutation testing a lot easier because you won't have to set up like for example 12 development networks. The other part of this is that I believe Ganache is not made to run the test suite like 500 times. What happened on my machine is that it would create like a few million files, which would use up the inodes on my machine and it would break almost everything. So with dynamic Ganache network creation, you could clean up after a test suite run and prevent this problem from happening. And then we also have framework expansion, which is basically means that I would extend Vertigo to work with other frameworks, which also are commonly used. Because currently we only really support Truffle. So then there's kind of three areas of foundational technology, which support the development of of mutation testing framework in general, but specifically Vertigo. Um and that's the compiler test framework, and then I made a little category of others. So, first the compiler um and So, the the Solidity compiler does actually already does a bunch of things uh right for um mutation testing. So, first where where Vertigo really uh uses the Solidity compiler is in the AST it generates. So, instead of doing manual parsing and analysis of the source code, um we we kind of use the uh Solidity generated AST to find specifically the locations that we want to mutate. Um based on the information in the AST, we determine how we should modify the original file to get to the mutant. Um Since a recent version of Solidity, it's also I think 6.2, um 0.6.2, uh it's also possible to recompile from a modified AST. So, that would make the process even easier. But, on the other hand, it would also likely require some more tight coupling between the mutation testing tool and a test framework because you need to be part of the compilation process. The second part where the compiler really helps out is in the compiler equivalence feature which I mentioned previously. So, so I won't really go into it. Um then we have the test framework, which uh kind of enables almost everything of the mutation testing process because it's our interface uh to the project. So, the first part is um the interaction with the unit tests, which is not optimal at the moment for mutation testing um because it's not as far as I know not easy at least to directly execute single test or maybe a list of tests which I would which the mutation testing framework would want to do. So for example, the test selection optimization and the incremental mutation testing optimization would require this functionality. I do think it's possible to single out specific files to run. So that's already like some improvement over the generic run the entire test week. But I think like a more detailed interface would be super beneficial for mutation testing tools. Then we have the other part which is automation of test network creation and I think this is handled by some of the uh test frameworks or IDE frameworks but to a limited extent because um I guess it's not a common use case to run your test suite in parallel five times. So that's probably why it hasn't been implemented yet to have multiple test networks being created and cleaned up all the time. But this is also a feature that could be handled outside of the test network. And lastly, there's this idea of test evaluation speed um where really any improvement to test evaluation speed. So this could be like a compiler optimization, a VM optimization or some other optimization also reflects in the performance of a a testing tool. And then the last um category uh miscellaneous I put detailed code coverage here because code coverage is currently handled by uh I think by a separate tool called solidity coverage. Um and it's on the issue tracker for this project, but I'm not sure when it's going to be implemented. But this is one thing that would enable the test case selection optimization. Um and I believe some other features outside of mutation testing. Um okay. So that was kind of the the overview of mutation testing theory kind of what the tool does right now and what could be improved and how other people in other parts of the tool stack might um help with the implementation of of these optimizations. And I think there's some time for questions. I would also love to hear any suggestions, maybe improvements on uh like usability or other questions. Yes, thank you for your talk. Um as Yoran already outlined we still have 5 minutes left for questions. So feel free to raise your hand if you have a question and you are attending here in the chat room in the video conference. If you are watching the live stream please put your question in the Gitter chat and we will be patient and wait a bit because we know there's a delay. Any feedback here from the room? Does not seem like it so far, but um, give it a few more minutes to also give the people on the live stream the chance to react to this. In the meantime, just checking in. Leo and Martin, you're both there already, right? Yes, I can see you. And Nicholas wants to say something. Yes, go ahead. Hi John. Uh, we've tried using a couple mutation testings uh, tools in the open Zeppelin contracts like every couple times and the issue always is that the test really so large and the number of contracts so large that running the entire test for a single mutation doesn't make any sense. Um, do you think instead of having the automated uh, like only run what tests need to be run based on coverage, if you could like have a way to very simply say only do mutations on this contract and then only run these tests, which would be a simple as uh, provide a way for the user of the library to write the test command where they could say I'll only run this test, uh, that would make it much more usable. So, that's like for improving usability. Uh, I think you could certainly do that. Uh, so, uh, Certora already uh, supports the inversion of of this. Uh, by allowing you to ignore certain directories. So, I guess what you could do right now is ignore everything except the thing you'd like to test. Um, there's no um, selection of tests uh, implemented yet, but I think I could. Um, Um, but your question is kind of valid about like the duration on a project like yours. Um, and I ran for a go on on well, open Zeppelin and and Aragon OS as well. And it took well, using 16 parallel processes to 2 hours. Uh, or between 2 and 3. Uh, and that's as you said, a really long time. But, I'm I think that given um, these optimizations, for example, the um, test selection and incremental evaluation optimizations, uh, that could be cut down a lot. For example, the test case selection at 10 times speed up would decrease the time to maybe 30 minutes or so. Um, of course, it would have to be evaluated uh, to see if that's actually the speed up that you would get. But, I think with some optimizations, it should certainly become a lot more usable and practical to run in a CI setup or at least frequently. Yeah, that that sounds great. Thanks.