Is it possible to reach absolute zero bug state for large scale software?

Question

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.

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.

Answer 1

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=---

Answer 2

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.

Answer 3

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)

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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").

Answer 12

No, because the computers and software environment that the application runs on will continue to change even whilst the code is frozen. The operating system continues to evolve with patches and fixes, as well as the devices and drivers. Just when you think you have reached the point of no known bugs, AMD or nVidia will release a video driver update that impacts how you interact with the video subsystem. Now your application has visual defects (like blinking, flickering, or frame rate reduction) for customers that have a certain video card or configuration (SLI? LOL).

Aside from hardware and OS, there are also a number of middleware products underneath most significant apps that will also evolve beyond your control, and just as you get your code to a zero defect state the layers underneath you get EOL'ed.

Technology evolves, as well as the business that leverages the technology, and the idea of "freeing" code isn't possible or feasible. The business asking for a new feature set isn't going to respond well to "we have the code locked while we chase all known bugs and no one reports a valid software defect in X months". Even if the business buys that line, after X months they will ask how the new features are coming along, and the answer can't be "we decided to extend the freeze because Oracle just release a patch and we need to take X more months to certify that".

No, at some point the business will be looking for a more flexible development team that supports the need to move forward at the speed of technology. This is the fundamental problem that modern development teams face.

Answer 13

Yes but you will never know for sure. The harder you look the more you will find. The heavier the system is used and the more edge cases are used, the more likey you will find another mismatch with the original intent or specification. This implies a bug itself is not an exact thing and will often depend on interpretation, on how bad some individual assesses a perceived anomaly.

It is a fuzzy thing. Few systems are specified out down to the last bit. If a system works well and users have no complaints (they are not bugged by anything) and they are totally adapted to it, you may as well call it bug free.

Answer 14

It is possible to consistently deliver bug-free software, given sufficient discipline and shared team culture. (And well-factored modular code, a comprehensive suite of automated tests, inspecting defects and adapting your process, and a lot of other things that require effort and humility but pay back thousandfold)

But doing this, you don't generally set out to build a 20 MLOC system. If writing bug-free code is not your goal, neither should be building a many MLOC system.

My own reasoning is as follows:

Some person has a need to fulfill. Some person (possibly the same, possibly a different one) has a budget to fulfill the need through writing software. All these people expect to get some benefit for their money.

The person with a budget will pay some people (possibly the same, possibly different) called programmers, so that these programmers will turn some agreed upon amount of their time into software fulfilling the need.

These programmers therefore work at transforming someone else's money into software fulfilling the need. It is their responsibility to put this money at good use.

This has the following implications with regards to your question:

• Given there is a bug in the software, will you fix it at all? You need a programmer to fix a bug, and the programmer will cost money. A programmer cannot decide whether to spend the money to do it. It is the role of the person holding the budget.
• Can I build a 20MLOC software from scratch without leaving unfixed bugs in the end? Well, setting out to build a 20MLOC required intending to spend a tremendous amount of money. This is financially foolish. And it is not built in one day. But software is for today's needs, not tomorrow. There will be a misguided attempt at parallelizing development by hiring lots of programmers. But then, odds are you won't get a shared culture and bugs will ensue, waste and delay will happen, and money will run out to fix them. I haven't seen any bug-free system this size yet. (I have seen bug-free systems and 20MLOC systems, but they were not the same)
• I am in charge of maintaining a 20MLOC system that I did not write. Will I be able to reach zero known bugs? This does not depend on the programmers. They can't decide to fix bugs because it's not their money on the line. Is there enough ROI to fix the remaining bugs? Well, the system has been around for some time now, and users have gotten used to it, and use the quirks of the system to their advantage in their daily work. If you fix bugs by principle, the person with the money might have to pay to redevelop some unspecified feature that disappeared from the system, costing even more money.

It's all about the money, and rightly so.

Answer 15

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 edge cases and flow logic 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