How to add a million bugs to a program, and why you might want to | Hacker News Reader

How to add a million bugs to a program, and why you might want to

moyix.blogspot.com

40 pointsmoyix24 comments

Answer to Question 1: Use our program! Answer to Question 2: To see if your automated bug-testing is finding all the bugs.

I'm not impressed with their answer to the second question. Knowing if your automated bug-finding tools manage to find all of the bugs introduced by this tool tells you very little about whether they will find bugs not introduced by this tool unless we have some assurance that the bugs introduced by this tool are somehow representative of bugs in general -- and I see no such assurance.

Realism is something we're concerned with! Unfortunately there isn't a well-defined way to say how realistic a synthetic bug is, so we had to come up with our own. The ultimate test of whether the bugs are useful is whether they can be used to improve bug detectors, and that remains to be seen.

We attempted in the paper to make an argument based, effectively, on whether the modified program looks like a normal program from the point of view of a bug-finding tool. From that perspective, the control flow in the program is unmodified, and the data flow is exactly the same as in the original program except for a small portion where data from the input file flows through a global variable to the crash site. We show that this section of data flow is usually short (in terms of number of instructions in a dynamic trace); we're also working now on extending it so that the data flow is more "natural" (i.e., it goes through return values and function parameters, rather than through global data). Additionally, we showed that the bugs are distributed throughout the execution lifetime of the programs we tested.

I definitely agree that they do not look like bugs humans most often write. However, to be effective, we just need them to look enough like the kind of bugs we want to catch that bug-finding software will have to reason about the program in the same way.

Regardless, defect seeding is a standard (albeit not common) practice in software quality. Nowadays it's more common to talk about it in the form of mutation testing, which is what this basically is.

There are a number of types of bugs that are significantly more common than others, so it's possible to draw equivalence classes around them and use them as representatives of the whole. That's the basic technical skill around testing in general so isn't terribly scary as part of a SQA process.

Those who are using the JVM platform can use the pitest maven plugin.

It runs the test suite, then introduce bugs and test and at the end compiles a line-by-line summary of what bugs where injected, caught and missed.

I'm not familiar with the tool mentioned in TFA, but "mutation testing" (the technique of introducing bugs to see if your test suite catches them) is not new: https://en.wikipedia.org/wiki/Mutation_testing

It actually sounds reasonable to me. Of course it won't necessarily produce the same bugs as a human programmer, but it's yet another automated quality tool, in this case, a sort of "test of your tests".

You are overly harsh.

In all of testing, proving a negative is futile. But if this tool can create bugs that your bug-finder cannot find, and your real dev process is at all correlated to the bugs this tool creates, then this tool is a useful addition to the toolbox.

But if this tool has detailed ideas about the kinds of bugs it can introduce. If so, the time spent on creating the tool to insert those types of bugs might have been better spent on creating specific test cases for those kinds of bug.

Alternatively, this randomly mutates programs, which means no time was lost thinking of what kinds of bugs to introduce. Then, I cannot see how the bugs introduced are representative of real-world ones. It just, as another commenter said, would be fuzzing your tests. Useful, but it doesn't tell you anything about the number of remaining bugs in your code.

It seems to basically be fuzzing for your automated tests. Fuzzing isn't guaranteed to find every single flaw, but statistically it's pretty good, and a lot better than not fuzzing.

Indeed. What does it tell you if you add a "return" statement right at the beginning of your main function? Yes, your program now contains a bug (or a million of bugs, depending on your view). But with this return statement in place, you will not be able to find any other bugs!

So you think people dedicated to creating bugs in your app are going to do a worse job at creating all possible bug variations than people just looking at developing?

Yea the article is pretty content free. It claims at the end that a future post will contain actual content.

They changed the article, and removed the link to the paper: http://www.ieee-security.org/TC/SP2016/papers/0824a110.pdf

I've seen that pattern a few times lately. I never used to see it. I consider it an absolute "don't bother to read this or the follow-up" indicator.

Thanks for saving my time.

If you want to skip ahead to the full content, you can read the paper :) I also don't think it's fair to say that this is content-free – it's setting up the setting and motivation. It's not immediately clear why someone would want to inject bugs (a common reaction I got when describing the problem to people was "that's evil" or "why would anyone want to do that?!").

I think I recall you're both seeding bugs and running bug-hunters on it. If so, which tools have been finding the most? And, if it takes a combo of them, which combo of the set you've testing have been most effective?

Note: Especially for severe ones that can lead to code injection.

Sorry to disappoint, but we're remaining coy on exactly which tools we tested for now – the evaluation was to demonstrate the initial feasibility, rather than to pick on anyone. We'll be releasing the corpora from the paper soon so people can do their own comparisons. And the code for the bug injection itself should be released a bit after that, so that it can be extended and built upon.

So far some of the things you'd expect hold true: fuzzing doesn't tend to reach bugs deep in the program, symbolic execution has trouble with path explosion and one-way functions, etc. You can see those results in the tables in section VI.D of the paper.

Fair enough. I'll admit that I hadn't read this post when I wrote my comment - you were getting vented on based on my annoyance from another article I had read. (Sorry...)

Don't title your article "How" if the body doesn't explain how.

That's a fair point. Originally the title was meant for the entire series, but the motivation piece got too long and I decided to split them up.

I toyed with this idea a little while back; I wrote some very critical tooling in bash, and wanted to make certain that no matter where in the program I encountered an error, the second try would work (presuming I had diagnosed the error).

My thought was: These scripts are running with set -euxo pipefail. I can insert a 'false' line between any two lines, run the script, then remove it and run it again and I should still get the correct results. I never finished writing this test tool, but I still think it's a good idea I want to get back to.

Didn't Netflix have some programs they'd call "monkeys" that randomly wreak havoc in their codebase / infrastructure? Is that related to this?

Chaos monkey - http://techblog.netflix.com/2012/07/chaos-monkey-released-in...

Nope, not related.

there is a 'fault-injection-framework' available here: https://blitiri.com.ar/p/libfiu/

haven't used it for anything realistic, so not sure how well it pans out in practise.

Reply on news.ycombinator.com