Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am talking about 20-30+ millions lines of code, software at the scale and complexity of Autodesk Maya for example.

If you freeze the development as long as it needs to be, can you actually fix all the bugs until there is simply not a single bug, if such a thing could be verified by computers? What are the arguments for and against the existence of a bug-free system?

Because there is some notion that every fix you make creates more bugs, but I don't think that's true.

EDIT: By bugs I meant from the simplest typos in the UI, to more serious preventative bugs that has no workaround. For example a particular scripting function calculates normals incorrectly. Also even when there are workarounds, the problem still has to be fixed. So you could say you can do this particular thing manually instead of using the provided function but that function still has to be fixed.

share|improve this question
6  
"was told by a few top programmers" - they don't sound like top programmers to me. They sound like top hackers. One of the PRIMARY RESPONSIBILITIES of a programmer is to understand what their code does and how it impacts the system as a whole. That's why we have TDD, design patterns, etc. If this cannot be done, the system is junk - the development process was done in a chaotic, haphazard, undisciplined, unscientific manner. –  Vector Apr 20 '13 at 22:30
21  
If you don't know that a bug exists yet, is it still a bug? –  Blrfl Apr 21 '13 at 2:28
10  
“There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.” - C.A.R. Hoare –  Andrew Lewis Apr 22 '13 at 18:52
2  
This question is being discussed on our Meta site. –  Yannis Rizos Apr 23 '13 at 5:09
3  
It is, but a lot of people don't want their fundamental beliefs questioned. –  Joan Venge Jun 5 '13 at 14:22

12 Answers 12

up vote 38 down vote accepted

As Mikey mentioned, writing bugless code is not the goal. If that is what you are aiming for, then I have some very bad news for you.

The key point is that you are vastly underestimating the complexity of software.

First things first--You're ignoring the bigger picture of how your program runs. It does not run in isolation on a perfect system. Even the most basic of "Hello World" programs runs on an operating system, and therefore, even the most simple of programs is susceptible to bugs that may exist in the operating system.

The existence of libraries makes this more complex. While operating systems tend to be fairly stable, libraries are a mixed bag when it comes to stability. Some are wonderful. Others ... not so much ... If you want your code to be 100% bug free, then you will need to also ensure that every library you run against is completely bug free, and many times this simply isn't possible as you may not have the source code.

Then there are threads to think about. Most large scale programs use threads all over the place. We try to be careful and write threads in such a way where race conditions and deadlock do not occur, but it simply is not possible to test every possible combination of code. In order to test this effectively, you would need to examine every possible ordering of commands going through the CPU. I have not done the math on this one, but I suspect that enumerating all of the possible games of Chess would be easier.

Things go from hard to impossible when we look at the machine itself. CPU's are not perfect. RAM is not perfect. Hard drives are not perfect. None of the components within a machine are designed to be perfect--they're designed to be "good enough". Even a perfect program will eventually fail due to a hiccup by the machine. There's nothing you can do to stop it.

Bottom line: Can you write "Bug free software"?

NO

Anyone who tells you otherwise is clueless.

Just try to write software that is easy to understand and maintain. Once you've done that, you can call it a day.


EDIT: Some people commented about an excellent point that I had completely overlooked: the compiler.

Unless you are writing in assembly, it is entirely possible that the compiler will mess up your code (even if you prove that your code is "perfect").

A list of bugs in GCC, one of the more commonly used compilers: http://gcc.gnu.org/bugzilla/buglist.cgi?product=gcc&component=c%2B%2B&resolution=---

share|improve this answer
4  
The answer is still "no", because there will always be "bugs" where something works - just not like a customer or product owner would like it work. Some of us might call these feature requests, or requests to change behaviour or add functionality - but to the person who is being annoyed by some "bug" every day, the thing that annoys them is a bug. (That's a long way of saying that some bugs are in the eye of the beholder.) BUG FREE CODE is impossible. Aim for code that is good enough to meet its intended purpose. –  quickly_now Apr 21 '13 at 1:24
2  
I'll go a step further: code can have latent defects, for example, you might have code that does not properly range check an input. If the input is for some lucky reason never out of range, the bug never manifests itself. Then one day during maintenance or feature changes, that piece of code gets called from somewhere else that DOES occasionally exercise it with an out of range value. The bug now manifests itself - but it was there all along. You can have degrees of madness in all this - but elimination of every possibility of wrongness is still impossible. –  quickly_now Apr 21 '13 at 1:27
5  
@JohnR.Strohm I'm not sure why you think the 'message flow modulator' program, a program with 556 lines of code, has anything to with a question regarding a theoretical 20 million line system. Except, perhaps, to demonstrate that however hard it was to prove the correctness of the tiny program, it would be astronomically harder to prove the correctness of a massive one. –  Eric King Apr 21 '13 at 19:33
5  
While the original question didn't do so, I'd like to point out that there's a gigantic difference between 'theoretically possible' and 'practically possible'. While a bug-free 20-million-line code base is arguably theoretically possible, it's almost certainly a practical impossibility, in today's market. Who knows what the future holds. –  Eric King Apr 22 '13 at 15:18
2  
They have many: msdn.microsoft.com/en-us/library/cc713578.aspx –  Joan Venge Apr 22 '13 at 21:22

Mathematically it MIGHT be possible to write 'bugless' software of such complexity, depending on how you define 'bug'. Proving it MIGHT also be mathematically possible, by designing a test system that would exercise every line of code in every possible way - every possible use case. But I am not sure - if you are dealing with a system that does complex calculations, you may run into an 'infinity problem'...

Practically speaking, in a system of the size and scope you are talking about, this is IMPOSSIBLE. It might take a 1000 years to write such a 'bug free' system, and to write a system to prove it would take exponentially more time: you'd have to come up with every possible use case and write a system that would test each one - and I don't believe there is way of determining that you have actually covered every use case in a system of the size and scope you are talking about in anything resembling a reasonable amount of time.

IMO your question is a bit misdirected: Our goal as developers is not to write 'bugless' software. Our goal is to write USABLE, FLEXIBLE, EASILY MAINTAINABLE software.

Usable: The system fulfills the essential requirements it was designed for. There may be bugs - but they will be in 'edge cases' - outliers, or annoyances, not bugs that compromise the fundamentals of the system - robust.

Maintainable: Bugs can be easily isolated and fixed and DON'T create new bugs.

Flexible: Your system is easy to change and expand without significant redesign and downtime: Most changes require simply adding a new class or module that fits in with your already well designed patterns and framework.

Good design practices, good control practices, good teamwork, conscientious developers - that is the formula for GOOD SOFTWARE. (not PERFECT - but GOOD)

share|improve this answer
3  
"Proving it MIGHT also be mathematically possible, by designing a test system that would exercise every line of code in every possible way - every possible use case.": Such a program does not exist in general (and this can be proved!). So a general algorithm for proving correctness does not exist. –  Giorgio Apr 21 '13 at 1:04
    
I agree - I essentially went in that direction, and I suppose it can be proved very easily: you cannot prove what you don't know about - 'proving a negative'. –  Vector Apr 21 '13 at 1:30
1  
Correction: Bug-free software, COMPLETE WITH FORMAL MATHEMATICAL PROOF OF CORRECTNESS, has been achieved. It was done in 1982. Google "message flow modulator". –  John R. Strohm Apr 21 '13 at 17:30
3  
@JohnR.Strohm:Not true. Here's just one quote - there are several papers and several places where they address similar concerns: "A question that frequently comes up is "Have you verified the verifier?" Perhaps surprisingly, this metamathematical question is often asked by engineers not merely by pointy headed academics. Of course, if a machine ever answers the question "Do you ever lie?" the answer will be no more informative than when a human answers the question." –  Vector Apr 22 '13 at 5:14
1  
I meant there is no general algorithm that will work for any input program and any input specification. You can only handle specific cases (e.g. your example). –  Giorgio Apr 23 '13 at 21:15

Essentially, no but you should do your best anyway. I'll explain why (or just skip to the conclusion if you don't have enough patience)

Consider a problem as trivial as the implementation of binary search. One very popular implementation had a bug that went undetected for around two decades. If twenty lines take twenty years to get bug-free being widely used and even supposedly proven correct, can we really expect a huge program to be bug-free?

How many bugs can we expect a huge program to have anyway? One number I found was "10 defects per 1000 lines" (Code Complete 2nd edition, page 517 - merely used an example, not quoting any data) That gives us around 200 000 to 300 000 bugs in your software. Fortunately, we have ways to improve the quality of the program. Unit testing, code reviews and ordinary manual testing are known to reduce the number of bugs. Still, the number will still be high.

If we could solve 95% of all bugs that'd be incredible. And yet we'd still have 10 000 to 15 000 bugs in the software.

Fortunately, since the software is widely used (and, therefore, widely tested) bugs are going to be found. So we'll gradually get fewer bugs. However, fewer bugs also mean that the remaining ones are harder to find - so don't expect a linear curve in bug fixing. The last few bugs will be really tricky to find and could escape detection for several years (assuming they are ever found).

You also seem to be mistakenly assuming that if the software doesn't change, no new bugs are going to appear. If the software depends on third party libraries, new versions may break some features - introducing new bugs even though the code of the application is still the same. New operating systems can also break an application that previously worked perfectly (see Windows Vista for a popular example). Consider also compiler bugs, etc.

It is unclear whether code proof tools can truly solve the problem of buggy software. It is certainly not possible to solve the halting problem for any program, but it might be possible to prove that a program behaves as specified... But then what? Maybe the proof program has a bug. Maybe the specification itself has a bug.

So clearly, we can greatly reduce the number of bugs, but it's really unlikely we'll ever get to zero.

Because there is some notion that every fix you make creates more bugs, but I don't think that's true.

(emphasis added)

You are correct. This statement is wrong. Here's an example:

int main() {
    int x[10];
    x[10] = 8; //Buffer overflow here
    return 0;
}

Now, let's fix this bug:

int main() {
    int x[11];
    x[10] = 8; //No buffer overflow here
    return 0;
}

See? We fixed a bug and introduced no new ones.

However, it is certainly correct that every time you fix a bug you risk creating a new one, though this risk can be mitigated (e.g. with unit testing).

Let's say that for every 100 bugs that I fix, I accidentally introduce a new one. So if I fix 10 000 bugs, I introduce 100 new bugs. And if I fix those new bugs, I introduce one bug. But so what? The program now has 9 999 fewer bugs, so it's probably better than it was (assuming the new bug is not 10 000 times worst than the previous ones).

Also, fixing a bug can expose new ones. But those bugs can be fixed as well. If you do things right, eventually the software will be in a better state than it started in.

I was old by a few top programmers that it's better not to fix a lot of bugs because of the notion I mentioned in the OP.

This behavior is negligent. If there's a bug and you can fix it. Do it. Of course you should do your best to prevent adding new ones but if I introduce one small bug for every 10 serious bugs I fix, that is not a valid reason to stop fixing bugs. In fact, it is a good reason to keep fixing bugs.

So less bugs you fix, less bugs will come back at you in the future

The fewer bugs you fix, the more bugs will remain in your software, annoying your users. Indeed, they won't "come back at you in the future". They won't come back because they never left in the first place. The notion of "come back" is related to regressions. Again, it is possible to reduce the risk of regressions.

Some bugs can't be fixed because they became so widely used that people started to depend on them and fixing the bug would break the program for those users. It happens. However, can they really be considered bugs in that case?

The "fix a bug, make a bug" mentality might be related to That Horrible Monster - code that is so unreadable and unmaintainable that merely touching it creates bugs. If you have a monster in your code base, you might first need to un-monsterify it before getting anything done.

Finally, if you are a terrible programmer, there's the risk that anything you touch creates new bugs. This would obviously make senior programmers nervous. However, saying "Don't do anything. Don't touch anything. Don't even breath." is probably not the right way to create a healthy work environment. Education is better.

Conclusion:

  • Software that keeps getting tons of new features but no bug fixes will inevitably suck.
  • Software that gets a moderate number of new features but gets its bugs fixed has a better chance of being usable.
  • Those who try to have few bugs have (on average) fewer bugs than those who do not care.
  • It is not reasonable to expect a program to eventually become bug-free.
  • Senior programmers are not necessarily competent.
  • Fix your bugs.
  • Adopt methodologies that improve the quality of your software.
share|improve this answer
    
+1: I was looking for the binary search example myself, was beaten to it ;) If 20 lines of widely discussed and circulated code held a bug for 20 years, how much time would you need for a 20-million line codebase that at most few dozen busy people will ever look at? –  scrwtp Apr 20 '13 at 22:58
    
Thanks. I wonder if that binary search bug (which I've never heard before) is related to people copy pasting a lot of code without thinking much? Also if we have this many bugs that are enough even possible to enumerate, maybe the tools and practices we are using is not optimal? –  Joan Venge Apr 20 '13 at 23:43
1  
@JoanVenge I quoted that example to show how tricky bugs can be to find. In this case copy pasting was actually the right thing to do since it was proven correct and implementation written from scratch would most likely have more bugs. The tools and practices we - as an industry in general - are using is certainly not optimal. Best practices are easy to ignore and bad habits are easy to keep. Ultimately, bugs will always exist because humans are not perfect. But we can reduce the number of bugs by doing our best and insisting on high-quality education. –  luiscubal Apr 20 '13 at 23:57
6  
I think the bug in the binary search code demonstrates how complex this question is. The underlying bug in the search was a potential integer overflow in an addition. Such "errors" are ubiquitous because most folk rely on an implicit (and occasionally incorrect) assumption that inputs will not be big enough to cause an overflow. Is it really a bug or just a poorly documented interface contract? When was that last time that you range checked the summands in an integer addition or checked for overflow after the fact? –  Charles E. Grant Apr 21 '13 at 1:36
3  
Your example servers to highlight a fairly obvious observation about programming language and tool quality. A production-quality compiler for a robust language should have refused to compile your first example, returning instead a fatal compilation error. That it is even POSSIBLE to compile such an abomination tells you everything you need to know about the quality of those tools, and the feasibility of their use for delivering bug-free software. –  John R. Strohm Apr 22 '13 at 3:53

According to this article, the on-board software for the Space Shuttle came very close -- the last three versions of the 420,000 line program had just one error each. The software was maintained by a group of 260 men and women. A large number of these people were verifiers, whose sole purpose was to find errors.

The upgrade of the software to permit the shuttle to navigate with Global Positioning Satellites impacted just 1.5% of the program, or 6,366 lines of code. The specs for that one change ran 2,500 pages. The specs for the overall program filled 30 volumes and ran 40,000 pages, or an average of ten lines of code per page of the spec.

Budget was not a problem -- at $35 milli0n per year, they could afford to do things right.

share|improve this answer
2  
One detected error each. Who knows how many undetected errors? :) –  Andres F. Apr 22 '13 at 21:52
    
40,000 pages of documentation for 400,000 lines of code, with practically unlimited budget, and it still wasn't error free. Multiply that by 50 (to get in the 20-million lines of code range that the question refers to)... I can't imagine the effort it would take to make that kind of code-base bug free. –  Eric King Apr 22 '13 at 23:26
2  
That "one error" was a special case. The Shuttle was originally designed, and the software specified, for two robot arms. The "error" was that there was still code in there to support the second arm. –  John R. Strohm Apr 23 '13 at 11:49
1  
+1 Ran without errors for 135 missions from 1981 to 2011 –  MarkJ Aug 14 '13 at 15:54

No.

David Hilbert proposed his second problem of mathematics back in 1900 that essentially asked the world to prove that the arithmetic worked as intended. He later propsed "the Entscheidungsproblem", which asked something similar in logical terms. Kurt_Gödel's "first incompleteness theorem" proved in 1931 that no theory of elementary arithmetic could be both consistent and complete. Alan Turing's representation of the Entscheidungsproblem as "the halting problem" moved the issue straight to the heart of this question, where he proved that it is impossible to prove whether a program will run to completion or not. Given that undeciability, it is also impossible to prove whether a program has any bugs or not.

None of that frees the practicing programmers among us from striving for no bugs. It merely means that we cannot succeed in general.

share|improve this answer
6  
The undecidability only applies in general - there are programs for which you can prove neither correctness nor incorrectness. But for a given specific program, correctness (or more often: incorrectness) can often be proven. This is assuming you have a formal language specification, and a provably correct compiler - the latter does not exist for any high-level programming language, though CompCert comes close. –  Daniel Apr 21 '13 at 18:18
    
+1 for quoting the relevant theoretical background. I didn't know yet that the "Entscheidungsproblem" is called the same in English as in German! –  Auwald Apr 22 '13 at 7:49
2  
Agree with Daniel. The challenge is about a single instance; the halting problems deals with all possible instances. Trivially int main() { return 0; } halts and is bug-free. –  MSalters Apr 22 '13 at 9:08

The reasons for not writing bug-free programs are mostly economical.

There are mathematical methods to prove the correctness of a program. In a high-quality Computer Science course they will be mentioned. There are programming languages invented especially for this purpose. In theory, programming without bugs is possible.

Yes, there is the imperfect hardware which may sometimes change a bit value because a neutrino fired from a distant supernova millions of years ago just happened to hit your processor at the right place. Okay, every theory has its assumptions and abstractions. But assuming that the processor works as advertized, there are matmematical tools to make sure the program works correctly too.

Some highly voted answers in this topic are misleading. For example, Gödel's incompleteness theorem and halting problem only imply that you can't have e.g. an automated tool which would decide correctness or incorrectness of any program. But we don't want to decide the correctness of any program, we only want a proof of correctness of one specific program.

(Analogically, just because you can't write a program for automatically deciding truth of any mathematical theorem, that does not mean that you can't prove one specific mathematical theorem.)

The problem, instead, is this:

Although it is in theory possible to write a bug-free program, doing so would be very expensive. Writing a code with a proof of its correctness is more complicated than just throwing something at a wall a seeing if it sticks. Even if "seeing if it sticks" is done by unit tests; and many programmers don't bother even doing that. Most programmers wouldn't even know how to do that, which means that as a company you would have to hire more expensive ones.

Considering all costs, a typical customer is more happy with a cheap software which works well 99% of the time (and 99.9% of the time after installing additional updates) than to have perhaps a thousand times more expensive software which works well 100% of the time. Also, the customer wants to have this software now, and not in ten or twenty years.

Therefore, people knowingly produce software which has some chance of bugs, trying to hit the optimal combination where the bugs are not too frequent and not too serious, and the production is fast enough and cheap enough. The combination which provides the most profit in real life. (Sometimes it even means releasing a software full of bugs before your competitors release anything, and only releasing a more decent version 2.0 when your competitors are ready to release their first decent version.)

If you freeze the development as long as it needs to be, can you actually fix all the bugs until there is simply not a single bug, if such a thing could be verified by computers?

Mathematically speaking, you could. Economically speaking, why would anyone do that? It would mean spending perhaps twenty years and a few million dollars. Meanwhile, customers would want new features, and your frozen applications could not provide them. So in the time your perfect version is ready, the market is already taken by your competitors.

Reasoning economically is OK. We live in a world where money and time matter. But just because we don't do something for economical reasons, we shouldn't speak nonsense about how that can't be done even in theory. Who knows... maybe in a few years we will have some new programming languages and tools which could make correctness proving easy.

share|improve this answer
    
Thanks, although I wish most software worked 99% of the time, most large ones I use like the one in OP, is extremely buggy. But I think monopoly, and buying competitors also factor into this. But I see your point. –  Joan Venge Apr 22 '13 at 10:33
    
"Expensive" is relative. Compare the cost of finding and fixing the bugs with the cost of e.g. a radiotherapy machine killing several patients and maiming several others. (Google "Therac 25".) –  John R. Strohm Apr 23 '13 at 11:47

Errare humanum est

Even if you write code with a formal language, like B-method, that you can use to mathematically prove that requirements are met,

Even if you use a formal specification language,

There is always a human step consisting in extracting the user's needs from one or more brains to a computer.

This human step is error-prone, and the worm is in the apple.

share|improve this answer
    
Is it still a bug when a program does what was asked, instead of what was intended? –  MSalters Apr 22 '13 at 9:09
    
I think it is.. –  Joan Venge Apr 22 '13 at 10:37
2  
@MSalters - Of course it is. Not from a contractual point of view, but in the end the customer has not his problem solved. Would you fly in a plane whose computers do what asked but not what intended? –  mouviciel Apr 22 '13 at 12:05

A fair proportion of the "bugs" that I have encountered might more properly be described as mismatches between system design and customer expectation.

Now, whether we call these bugs or not is academic, but the fact remains that a good deal of maintenance work arises as a direct result of imperfect communication and shifting customer expectations.

Even if a system is technically, provably "correct" in the sense of meeting a spec, (however improbable that might be for real-world commercial software), then you will still have the problem of matching the software's function to your customer's ever-shifting and poorly defined expectations.

In short:

No.

share|improve this answer
    
+1 A developer and a customer might have widely different views on what defines a 'bug'. –  GrandmasterB Aug 16 '13 at 16:59
    
But what if the developer is also the user? I find generally best software from those people in terms of usability since they know exactly how something should work, etc. –  Joan Venge Aug 16 '13 at 19:14

If you have a sufficiently tight and restricted specification, you might be able to prove a bug-free program, but only based on unprovable assumptions about the correct functioning of everything else in the system. This leaves as a given that there's no way to prove that the specifications would be considered correct by whomever posed the original problem, or by whoever was using the service.

share|improve this answer

Yes.

But as you know, it requires far too much effort to be worth it.

Before I can defend my answer, we must first define what a bug is:

  • A bug is a behavior that is contrary to the specification.
  • However, glitches in the specification (e.g. the 0th law of robotics) do not count as software bugs.
  • Extra features do not count as bugs, unless prohibited by the specification.
  • For the sake of argument, contradictions within the specification do not count as software bugs, either.

Now, as you hopefully already know, good software architectures are modular, so that each module can be unit tested (or manually tested, or whatever) individually. Through discipline and careful testing, it is possible to write individual modules that do not have bugs in them.

"But wait!" I hear you protest, "What if an unexpected (but nonetheless correct) behavior of one module causes a bug in another?" Then the bug is in the second module. Bug-free modules can be treated as APIs, and APIs, as you know, require some care to be used correctly.

Writing bullet-proof code requires extensive knowledge of math, logic, and especially combinatorics on the part of the developer, and most software developers either aren't smart enough to learn or simply don't care. Or more often, they're on a deadline.

"But give me a place to stand, and I will move the world." - Archimedes

share|improve this answer

I found Jim Shore's section No Bugs a very useful reading on this topic. The short form: It's not possible to develop without producing bugs - but we can work in such a way that we detect them as early as possible.

During the production of the code itself. For example by writing and running Unit Tests frequently during development, we constantly assure the code does what it is supposed to do. Also, it is useful to perpetually rewrite existing code in such a way that it most clearly expresses the intended system behaviour.

In your case, however, you are talking about an already existing codebase with millions of lines of code. If you want to get such a system bug free, you first of all have to know what "is a bug" for this system. You could write suites of post-hoc tests assuring the system's functionality (if not yet existing). The web of those tests may serve as an approximate definition for the correct system behaviour. But the more code you have, the more effort is involved in such exercises. Therefore, most companies make a compromise: they live with the imperfect, working with bug lists and maintenance to get the most annoying bugs out of the system.

share|improve this answer

About the verifying by computer part.

There are two ways to verify a program using a computer. One is testing, the other is using proof system.

As soon as exhaustive testing isn't possible, testing becomes unable to show that a program doesn't have bugs, just that it has some. (And you have the issue to show that your tests themselves aren't testing for the presence of bugs).

To use a proof system, you start from formal requirements (and they may themselves have bug, hopefully the language used for the requirements will be more suitable to convince yourself that there is no bug there than with a programming language) and construct/prove with the help of proof systems that the program is bug free (and there is the question of bugs in the proof systems, but they proved themselves correct). The current state of the art is a compiler for a C subset (and the subset isn't academic, "CompCert supports all of the MISRA-C 2004 subset of C, plus many features excluded by MISRA").

share|improve this answer

protected by maple_shaft Aug 14 '13 at 11:01

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.