64

If every path through a program is tested, does that guarantee finding all bugs?

If not, why not? How could you go through every possible combination of program flow and not find the problem if one exists?

I hesitate to suggest that "all bugs" can be found, but maybe that is because path coverage isn't practical (as it is combinatorial) so it isn't ever experienced?

Note: this article gives a quick summary of coverage types as I think about them.

  • 33
    This is equivalent to the halting problem. – user22815 Mar 29 '15 at 23:28
  • 31
    What if code that should have been there, isn't? – RemcoGerlich Mar 30 '15 at 8:01
  • 6
    @Snowman: No, it is not. It is not possible to solve the halting problem for all programs but for many specific programs it is solvable. For these programs, all code paths can be enumerated in a finite (though possibly long) amount of time. – Jørgen Fogh Mar 30 '15 at 13:08
  • 3
    @JørgenFogh But when trying to find bugs in any program, isn't it a priori unknown whether the program halts or not? Isn't this question about the general method of "finding all bugs in any program via path coverage"? In which case, isn't it similar to "finding whether any program halts"? – Andres F. Mar 30 '15 at 13:42
  • 1
    @AndresF. it is only unknown if the program halts if the subset of the language in which it is written is capable of expressing a non-halting program. If your program is written in C without using unbounded loops/recursion/setjmp etc., or in Coq, or in ESSL, then it must halt and all paths can be traced. (Turing-completeness is seriously overrated) – Leushenko Mar 30 '15 at 15:07

11 Answers 11

128

If every path through a program is tested, does that guarantee finding all bugs?

No

If not, why not? How could you go through every possible combination of program flow and not find the problem if one exists?

Because even if you test all possible paths, you still haven't tested them with all possible values or all possible combinations of values. For example (pseudocode):

def Add(x as Int32, y as Int32) as Int32:
   return x + y

Test.Assert(Add(2, 2) == 4) //100% test coverage
Add(MAXINT, 5) //Throws an exception, despite 100% test coverage

It is now two decades since it was pointed out that program testing may convincingly demonstrate the presence of bugs, but can never demonstrate their absence. After quoting this well-publicized remark devoutly, the software engineer returns to the order of the day and continues to refine his testing strategies, just like the alchemist of yore, who continued to refine his chrysocosmic purifications.

-- E. W. Dijkstra (Emphasis added. Written in 1988. It's been considerably more than 2 decades now.)

  • 7
    @digitgopher: I suppose, but if a program has no input, what useful thing does it do? – Mason Wheeler Mar 29 '15 at 23:27
  • 34
    There's also the possibility of missing integration tests, bugs in the tests, bugs in dependencies, bugs in the build/deployment system, or bugs in the original specification/requirements. You can never guarantee finding all bugs. – Ixrec Mar 29 '15 at 23:27
  • 11
    @Ixrec: SQLite makes a pretty valiant effort, though! But look at what an enormous effort it is! That wouldn't scale well to large codebases. – Mason Wheeler Mar 29 '15 at 23:32
  • 13
    Not only would you not tested all possible values or combinations thereof, you haven't tested all relative timings, some of which could expose race conditions or indeed make your test enter a deadlock, which would make it fail to report anything. It wouldn't even be a fail! – Iwillnotexist Idonotexist Mar 30 '15 at 7:47
  • 14
    My recollection (bolstered by writings such as this) is that Dijkstra believed that in good programming practices, the proof that a program is correct (under all conditions) should be an integral part of the development of the program in the first place. Seen from that viewpoint, testing is like alchemy. Rather than hyperbole, I think this was a very strong opinion expressed in very strong language. – David K Mar 30 '15 at 19:41
71

In addition to Mason's answer, there is also another problem: coverage does not tell you what code was tested, it tells you what code was executed.

Imagine you have a testsuite with 100% path coverage. Now remove all assertions and run the testsuite again. Voilà, the testsuite still has 100% path coverage, but it tests absolutely nothing.

  • 2
    It could make sure that there is no exception when calling the tested code (with the parameters in the test). This is slightly more than nothing. – Paŭlo Ebermann Mar 30 '15 at 11:53
  • 7
    @PaŭloEbermann Agreed, slightly more than nothing. However, it is tremendously less than "finding all bugs" ;) – Andres F. Mar 30 '15 at 13:39
  • 1
    @PaŭloEbermann: Exceptions are a code path. If the code could throw but with certain test data doesn't throw, the test does not achieve 100% path coverage. This isn't specific to exceptions as an error-handling mechanism. Visual Basic's ON ERROR GOTO is also a path, as is C's if(errno). – MSalters Mar 31 '15 at 10:47
  • 1
    @MSalters I'm talking about code which (by specification) should not throw any exception, regardless of input. If it throws any, that would be a bug. Of course, if you have code which is specified to throw an exception, that should be tested. (And of course, as Jörg said, just checking that the code doesn't throw an exception is usually not enough to make sure it does the right thing, even for non-throwing code.) And some exceptions can be thrown by a non-visible code path, like for null pointer dereference or division by zero. Does your path coverage tool catch those? – Paŭlo Ebermann Mar 31 '15 at 11:20
  • 2
    This answer nails it. I would take the claim even further and say that due to this, path coverage never guarantees to find even a single bug. There are metrics that can guarantee at least that changes will be detected, however - mutation testing can actually guarantee that (some) modifications of the code will be detected. – eis Mar 31 '15 at 12:31
34

Here's a simpler example to round things off. Consider the following sorting algorithm (in Java):

int[] sort(int[] x) { return new int[] { x[0] }; }

Now, let's test:

sort(new int[] { 0xCAFEBABE });

Now, consider that (A) this particular call to sort returns the correct result, (B) all code paths have been covered by this test.

But, obviously, the program does not actually sort.

It follows that coverage of all code paths is not sufficient to guarantee that the program has no bugs.

12

Consider the abs function, that returns the absolute value of a number. Here is a test (Python, imagine some test framework):

def test_abs_of_neg_number_returns_positive():
    assert abs(-3) == 3

This implementation is correct, but it only gets 60% code coverage:

def abs(x):
    if x < 0:
        return -x
    else:
        return x

This implementation is wrong, but it gets 100% code coverage:

def abs(x):
    return -x
  • 2
    Here is another implementation that passes the test (please pardon the non-linebroken Python): def abs(x): if x == -3: return 3 else: return 0 You could possibly elide the else: return 0 part and get 100% coverage, but the function would be essentially useless even though it does pass the unit test. – a CVn Mar 30 '15 at 9:31
7

Yet another addition to Mason's answer, a program's behavior may depend on the runtime environment.

The following code contains a Use-After-Free:

int main(void)
{
    int* a = malloc(sizeof(a));
    int* b = a;
    *a = 0;
    free(a);
    *b = 12; /* UAF */
    return 0;
}

This code is Undefined Behavior, depending on the configuration (release|debug), OS and compiler it will yield different behaviors. Not only path coverage won't guarantee that you will find the UAF, but your test suite will typically not cover the various possible behaviors of the UAF that depend on the configuration.

On another note, even if path coverage were to guarantee finding all bugs, it is unlikely that it can be achieved in practice on any program. Consider the following one:

int main(int a, int b)
{
    if (a != b) {
        if (cryptohash(a) == cryptohash(b)) {
            return ERROR;
        }
    }
    return 0;
} 

If your test-suite can generate all paths for this, then congratulations you're a cryptographer.

  • Easy for sufficiently small integers :) – CodesInChaos Mar 30 '15 at 16:50
  • Without knowing anything about cryptohash, it's a little hard to say what "sufficiently small" is. Maybe it takes two days to complete on a supercalculator. But yeah, int might turn out to be a little short. – dureuill Mar 31 '15 at 6:54
  • With 32 bit integers and typical cryptographic hashes (SHA2, SHA3, etc.) computing this should be quite cheap. A couple of seconds or so. – CodesInChaos Apr 2 '15 at 8:47
7

It's clear from the other answers that 100% code coverage in tests does not mean 100% code correctness, or even that all bugs that could be found by testing, will be found (never mind bugs that no test could catch).

Another way of answering this question is one from practice:

There are, in the real world, and indeed on your own computer, many pieces of software that are developed using a set of tests that give 100% coverage and which yet still have bugs, including bugs that better testing would identify.

An entailed question therefore, is:

What is the point of code coverage tools?

Code coverage tools help to identify areas one has neglected to test. That can be fine (the code is demonstrably correct even without testing) it can be impossible to resolve (for some reason a path cannot be hit), or it can be the location of a great stinking bug either now or following future modifications.

In some ways spell-check is comparable: Something can "pass" spell-check and be misspelled in such a way as to match a word in the dictionary. Or it can "fail" because correct words are not in the dictionary. Or it can pass and be utter nonsense. Spell-check is a tool that helps you identify places you may have missed in your proof-reading, but just as it cannot guarantee complete and correct proof-reading, so code-coverage cannot guarantee complete and correct testing.

And of course the incorrect way to use spell-check is famously to go with every suggestion ewe sea it suggest so the ducking thing becomes worse then if ewe left it a loan.

With code coverage it can be tempting, especially if you've a near-perfect 98%, to fill in cases so that the remaining paths are hit.

That is the equivalent of righting with spell-check sew that it's all words weather or knot it's all the appropriate words. The result is a ducking mess.

However, if you consider what tests the non-covered paths really need, the code-coverage tool will have done its job; not in promising you correctness, but it pointing out some of the work that needed to be done.

  • +1 I like this answer because it's constructive and mentions some of the benefits of coverage. – Andres F. Mar 31 '15 at 16:04
4

Path coverage cannot tell you whether all the required features have been implemented. Leaving out a feature is a bug, but path coverage will not detect it.

  • 1
    I think that depends on the definition of a bug. I don't think missing features or functionality should be regarded as bugs. – eis Mar 31 '15 at 12:21
  • @eis - you don't see a problem with a product whose documentation says that it does X when in fact it doesn't? That's a rather narrow definition of "bug". When I managed QA for Borland's C++ product line we were not that generous. – Pete Becker Mar 31 '15 at 14:47
  • I don't see why would documentation say it does X if that was never implemented – eis Mar 31 '15 at 20:05
  • @eis - if the original design called for feature X the documentation could end up describing feature X. If nobody implemented it, that's a bug, and path coverage (or any other kind of black box testing) won't find it. – Pete Becker Mar 31 '15 at 20:57
  • Oops, path coverage is white box testing, not black box. White box testing can't catch missing features. – Pete Becker Apr 1 '15 at 10:24
4

Part of the issue is that 100% coverage only guarantees that the code will function correctly after a single execution. Some bugs like memory leaks may not be apparent or cause issue after a single execution, but over time will cause problems for the application.

For example, say you have an application which connects to a database. Perhaps in one method the programmer forgets to close the connection to the database when they are done with their query. You could run several tests over this method and find no errors with it's functionality, but your database server may run into a scenario where it is out of available connections because this particular method did not close the connection when it was done and the open connections must now timeout.

  • Agreed that that's part of the issue, but the real issue is more fundamental than that. Even with a theoretical computer with infinite memory and no concurrency, 100% test coverage does not imply the absence of bugs. Trivial examples of this abound in the answers here, but here is another: if my program is times_two(x) = x + 2, this will be fully covered by test suite assert(times_two(2) == 4), but this is still obviously buggy code! No need for memory leaks :) – Andres F. Mar 30 '15 at 18:28
  • 2
    It's a great point and I recognize that it is a bigger/ more fundamental nail in the coffin of the possibility of bug-free applications, but as you say it was already added here and I wanted to add something that wasn't quite covered in existing answers. I have heard of applications which crashed because database connections were not released back into the connection pool when they were no longer needed - A memory leak is a just the canonical example of resource mismanagement. My point was to add that proper management of resources in general can not be entirely tested. – Derek W Mar 30 '15 at 18:48
  • Good point. Agreed. – Andres F. Mar 30 '15 at 19:00
3

If every path through a program is tested, does that guarantee finding all bugs?

As already said, the answer is NO.

If not, why not?

Besides what is being said, there are bugs appearing at different levels, which can't be tested with unit tests. Just to mention few :

  • bugs caught with integration tests (unit tests shouldn't use real resources after all)
  • bugs in requirements
  • bugs in design and architecture
2

What does it mean for every path to be tested?

The other answers are great, but I just want to add that the condition "every path through a program is tested" is itself vague.

Consider this method:

def add(num1, num2)
  foo = "bar"  # useless statement
  $global += 1 # side effect
  num1 + num2  # actual work
end

If you write a test that asserts add(1, 2) == 3, a code coverage tool will tell you that every line is exercised. But you haven't actually asserted anything about the global side effect or the useless assignment. Those lines executed, but haven't really been tested.

Mutation testing would help find issues like this. A mutation testing tool would have a list of pre-determined ways to "mutate" the code and see if the tests still pass. For example:

  • One mutation might change the += to -=. That mutation would not cause a test failure, so it would prove that your test doesn't assert anything meaningful about the global side effect.
  • Another mutation might delete the first line. That mutation would not cause a test failure, so it would prove that your test doesn't assert anything meaningful about the assignment.
  • Still another mutation might delete the third line. That would cause a test failure, which in this case, shows that your test does assert something about that line.

In essense, mutation tests are a way to test your tests. But just like you'll never test the actual function with every possible set of inputs, you'll never run every possible mutation, so again, this is limited.

Every test we can do is a heuristic to move toward bug-free programs. Nothing is perfect.

0

Well... yes actually, if every path “through” the program is tested. But that means, every possible path through the entire space of all possible states the program can have, including all variables. Even for a very simple statically compiled program – say, an old Fortran number cruncher – that's not feasible, though it can at least be imaginable: if you have just two integer variables, you're basically dealing with all possible ways to connect points on a two-dimensional grid; it actually looks a lot like Travelling Salesman. For n such variables, you're dealing with an n-dimensional space, so for any real program, the task is completely untractable.

Worse: for serious stuff, you have not just a fixed number of primitive variables, but create variables on the fly in function calls, or have variable-size variables... or anything like that, as possible in a Turing-complete language. That makes the state space infinite-dimensional, shattering all hopes of full coverage, even given absurdly powerful testing equipment.


That said... actually things aren't quite so bleak. It is possible to proove entire programs to be correct, but you'll have to give up a few ideas.

First: it's highly advisable to switch to a declarative languange. Imperative languages, for some reason, have always been by far the most popular, but the way they mix together algorithms with real-world interactions makes it extremely difficult to even say what you mean by “correct”.

Much easier in purely functional programming languages: these have a clear distinction between the real interesting properties of mathematical functions, and the fuzzy real-world interactions you can't really say anything about. For the functions, it is very easy to specify “correct behavior”: if for all possible inputs (from the argument types) the corresponding desired result comes out, then the function behaves correctly.

Now, you say that's still intractable... after all, the space of all possible arguments is in general also infinite-dimensional. True – though for a single function, even naïve coverage testing leads you way further than you could ever hope for in an imperative program! However, there is an incredible powerful tool that changes the game: universal quantification / parametric polymorphism. Basically, this allows you to write functions on very general kinds of data, with the guarantee that if it works for a simple example of the data, it will work for any possible input at all.

At least theoretically. It's not easy to find the right types that are really so general that you can completely proove this – usually, you need a dependently-typed language, and these tend to be rather difficult to use. But writing in a functional style with parametric polymorphism alone already boosts your “security level” enourmously – you won't necessarily find all bugs, but you'll have to hide them quite well so the compiler doesn't spot them!

  • I disagree with your first sentence. Going through every state of the program doesn't, in itself, detect any bugs. Even if you check for crashes and explicit errors you still haven't checked the actual functionality in any way, so you've only covered a small part of the error space. – Matthew Read Apr 2 '15 at 15:16
  • @MatthewRead: if you apply this consequently, then the “error space” is a proper subspace of the space of all states. Of course it's hypothetical because even the “correct” states make up a far too large space to allow any exhaustive tests. – leftaroundabout Apr 2 '15 at 15:25