Upper limit of bugs in a given program

Question

Is there an upper limit to the number of bugs contained in a given program? If the number of instructions are known, could one say the program cannot contain more than 'n' bugs? For example, how many bugs could the following function contain?

double calcInterest(double amount) {
    return -O.07 / amount;
}

A parser would count four terms in the function, and I could count these errors:

• wrong number syntax
• wrong interest rate (business requirements error)
• wrong calculation (should be multiply)
• Potential divide by zero

Clearly the number of bugs is not infinite given a finite number of instructions. Alternatively, one could say the function accepts 2^64 inputs, and of those, how many produce the correct output. However, is there any way to formally prove an upper limit?

Answer 1

There is a theoretical upper limit for bugs, but for all but the most trivial programs it is very nearly impossible to calculate, although engines such as Pex do give it the old college try.

Answer 2

Number of instructions have nothing to do with whether the program does what the user wants it to do. I mean, look at how poorly GCC does balancing my check book. Buggy as all get out, down right useless!

Answer 3

This would all depend on how you define a 'bug'.

If you define a program as a function from some input to some output, and a specification as a definition of that function, and a bug as any difference in output from the specification on a given input, then yes, you can conceivably have countably infinite bugs - however this is a somewhat useless definition of a bug.

Answer 4

Law of programming:

"If You will find all compile-time bugs, then n logical ones are still hidden, waiting to surprise You at run-time."

Answer 5

The upper limit is the number of states your program can be in. Since this number is finite on real machines you could number the states from 1 to n. For each state you could label if this state is a bug or not. So yes, but even a small program having 16 bytes of memory has 2^128 states and the problem of analyzing all the different states is intractable.

Answer 6

Depends on how you count bugs, which leads me to say "nope, no limit." I don't know about you, but I can easily write several bugs in the same line of code. For instance, how many bugs are in this Java code? :-P

public int addTwoNumbers(int x, String y)
{{
    z == x + y;
    return y;
}

Answer 7

As little as one if the bug is significant enough.

Answer 8

If bug is "a requirement not met by the program", then there is no limit on the number of bugs (per line or otherwise), since there is no limit on the number of requirements.

print "hello world"

Might contain a million bugs. It doesn't create a pink elephant. I leave it to the reader to come up with 999999 other requirements not satisfied by this program.