79

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.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
Joan Venge
  • 1,950
  • 2
  • 18
  • 24
  • 12
    "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
  • I called them top programmers because they were always the few guys that were called on hard problems. Other programmers were also in agreement, so it's not strictly rated but just impressions and titles. – Joan Venge Apr 20 '13 at 23:36
  • 52
    If you don't know that a bug exists yet, is it still a bug? – Blrfl Apr 21 '13 at 02:28
  • 5
    @Blrf: More importantly, If the end user does not know theres a bug, does it exist? – mattnz Apr 21 '13 at 04:37
  • 1
    Are we presuming defect free requirement? – mattnz Apr 21 '13 at 04:46
  • 1
    Thanks yes, it has to be defect free. If you really don't a bug, fair enough but we are assuming we have a system that identifies all bugs for us, literally every single bug that could be conceived. – Joan Venge Apr 21 '13 at 08:13
  • 41
    “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
  • 1
    Issues are only bugs in the context of requirements. So one thing you can do is take an existing system and write a single requirement: *Works like the existing system.* Then, of course, the existing system is bug-free because it works like itself by definition, and it's certainly *possible* (though unlikely) that a new system could be built that perfectly imitates the existing one. Yes, that's a bit silly, but so is your hypothetical "system that identifies all bugs for us, literally every single bug that could be conceived." – Caleb Apr 22 '13 at 19:35
  • 2
    This question is being discussed on our [Meta site](http://meta.programmers.stackexchange.com/questions/5865/why-was-the-question-about-zero-bug-large-scale-software-closed). – yannis Apr 23 '13 at 05:09
  • 1
    Another take on this question would be to discuss if it's possible to reach zero bug state for brand new software that's not yet been written. Bringing the best minds and coming up with the best design that will be self sufficient, and bugs will be isolated in each module, so much that even other modules completely went down, the software will still work without any issues. I believe it's possible to come up with a perfect design. – Joan Venge Apr 23 '13 at 19:44
  • duplicate of [Why is software still released with known bugs?](http://programmers.stackexchange.com/questions/112145/why-is-software-still-released-with-known-bugs) – gnat Apr 28 '13 at 08:36
  • 2
    Voting to reopen. The answers show that the question is quite on topic – BЈовић Jun 05 '13 at 07:30
  • 7
    It is, but a lot of people don't want their fundamental beliefs questioned. – Joan Venge Jun 05 '13 at 14:22
  • As far as verifying a program has no bugs - it is mathematically impossible to write a program that verifies if any other program is a virus (presumably equivalent to detecting a bug). http://security.stackexchange.com/questions/19714/cohens-problem So your bug detector must be custom written. Which means it too may have bugs... – psr Aug 24 '13 at 03:23
  • 3
    Supposedly bug-free can be achieved... though at great cost: https://newsroom.unsw.edu.au/news/science-technology/code-breakthrough-delivers-safer-computing 5 years for 6 people to verify 7500 lines of code only... – Populus Mar 11 '14 at 16:21
  • Perhaps if the code is written in Agda... But chances are your programmers will quit due to frustration before they finish writing that big a program in Agda. – dspyz Apr 18 '14 at 21:52
  • 3
    I would like to add one more thing, as all the points here are valid you need to remember that the actual underlying physical voltage based memory storage is imperfect as well some hazards in the memory may occur causing bug-free program to behave as if it was bugged, this is why even if you will reach absolute zero that wont always prevent your program from failing. – cerkiewny May 16 '14 at 14:22
  • Nothing made by humans is error-free. To fix bug doesn't make more bugs, it produces another behaivor... that could be considered bug by some ppl – Laiv May 28 '16 at 21:03
  • This question seems to mostly be an issue of terminology. If one defines a correct program as one that perfectly meets its specification. It is trivially easy to generate a correct program by writing the specification in a programming language (assuming the language spec or compiler are not also buggy), then compiling and running said program is correct by definition. However it then becomes equally difficult to write the specification as it was to write the software in the first place. But the written software is tautologically correct as it's correctness is defined by itself. – Vality Feb 08 '17 at 00:29

15 Answers15

95

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

Tulains Córdova
  • 39,201
  • 12
  • 97
  • 154
riwalk
  • 7,660
  • 3
  • 29
  • 32
  • 1
    Good points, although I think the OP was talking about the software system itself, not the aspects out the programmers' control. But multi-threaded apps is definitely a 'biggie' - like complex calculations, you can begin to approach 'infinity problems' when considering use cases in a complex multi-threaded app, as you hinted to with your reference to chess games... – Vector Apr 21 '13 at 00:18
  • 9
    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 01:24
  • 7
    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 01:27
  • Well said. Important to be able to understand priorities: what is critical, what is not; what is an outlier-a 'one off'-an 'edge case'. I wrote and maintained a custom TCP-IP app for many years. When I wrote it at first, I considered a lot of 'one off' scenarios and decided not to deal with them. In the course of the years ALL of those 'one offs' did surface - sometimes I dealt with them, sometimes just fixed that data and 'forced it through', knowing that it would probably be another 5 years until it surfaced again - if ever. My boss usually made those decisions about what to fix, what not. – Vector Apr 21 '13 at 01:45
  • 3
    -1 for not knowing that bug-free software HAS been achieved, and insisting that it is impossible. Google "message flow modulator". – John R. Strohm Apr 21 '13 at 17:29
  • 11
    @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
  • 1
    @JohnR.Strohm, it is obvious to anyone who has read the original question that the op was talking about a large scale programming project. Despite that, my points about the potential instability of the systems you are running on still holds, even with your example. – riwalk Apr 21 '13 at 21:25
  • Of course, NASA and the people who write code for some highly safety critical applications would take exception to all this. They'd also know that truly bug-free was still impossible. – quickly_now Apr 22 '13 at 01:08
  • 3
    You have a choice. Either you believe that bug-free code is impossible, or you believe that it is possible. Prior to the message flow modulator delivery, it was widely believed that bug-free code, at ANY size, was impossible. IEFBR14 was widely cited as proof of that assertion. The flip side is this: once a SMALL bug-free program has been delivered, it is now proven that bug-free code is POSSIBLE, and the question becomes how to extend that work to do LARGE bug-free systems. – John R. Strohm Apr 22 '13 at 03:46
  • I will stipulate that typical programmers, using the programming languages and tools that are common today, quite possibly are incapable of producing bug-free code. This is a comment on those programmers and on those languages and tools. – John R. Strohm Apr 22 '13 at 03:51
  • 1
    The comment on latent defects by @quickly_now reminded me of the post [The importance of error code backwards compatibility, over on The Old New Thing](http://blogs.msdn.com/b/oldnewthing/archive/2005/01/18/355177.aspx). – user Apr 22 '13 at 13:55
  • 10
    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
  • What about compilers ? I know they don't have 20-million-LOC, but they are big enough to be relevant to the discussion. I never hear about compiler bugs. Also, it makes sense to design them as "perfect" as possible because EVERYTHING else we write depends on them... – Radu Murzea Apr 22 '13 at 20:51
  • 2
    They have many: http://msdn.microsoft.com/en-us/library/cc713578.aspx – Joan Venge Apr 22 '13 at 21:22
  • 1
    Also here: http://stackoverflow.com/questions/4642665/why-does-capturing-a-mutable-struct-variable-inside-a-closure-within-a-using-sta/4688670#4688670 – Joan Venge Apr 22 '13 at 21:23
  • 1
    Here is a very impressive list for GCC bugs: http://gcc.gnu.org/bugzilla/buglist.cgi?product=gcc&component=c%2B%2B&resolution=--- It's a kilometer long. – Joan Venge Apr 22 '13 at 21:25
  • 4
    @JohnR.Strohm You should read the paper more carefully. They say themselves: `It is important to note, however, that even all of these steps provide no guarantee of absolute security. It is tempting to believe that a formally specified and proved program should be absolutely correct, but there are several reasons why a proved program may not behave exactly as expected.` - meaning, it cannot be proved to be bug free, but rather, less likely to have bugs. Rather like TDD. – Izkata Aug 16 '13 at 18:06
  • @Stargazer712 Consider I am writing an application named X. These issues you are talking about are bugs of a system which is external to the code base of my application X. So, when a bug in lets say, the compiler, or CPU causes my application to misbehave, can you actually attribute it to a bug in code X ? Yes, I may make modifications in my code to try and better support a flaw in another system, but would you consider that a bug of application X ? – Heshan Perera Mar 19 '15 at 07:34
  • @HeshanPerera, and how do you consider libraries? Are those part of "your application" or not? Can you name a single *practical* program you've written that does not use a single library? – riwalk Mar 19 '15 at 15:50
  • I'm mean it's theoretically possible, it's just that it isn't doable by an human. – Ced May 12 '16 at 09:00
  • 1
    Even if you are writing in assembly the assembler may introduce bugs when assembling the machine code. Even if you are writing in machine code, the loader may introduce bugs when copying the code into memory. Even if running perfect code loaded into perfect memory radioactive decay may flip a bit that parity checks fail to detect. Even if quantum ... heisenberg uncertainty ... string theory... Ya know I'm not sure it's doable by God. But I still want a car that drives itself while I sleep in the back seat. – candied_orange May 28 '16 at 06:51
  • Besides any other consideration, any program will always have *one unavoidable bug: its end user.* :-D (BTW, sometimes it is not really a Joke!) – LorenzoDonati4Ukraine-OnStrike Jul 13 '18 at 11:25
  • I would claim that bug free code is possible but only for meaning "the program works per specification in all cases". The problem is that *the specification* will always have bugs or undefined cases. How to create bug free code: write specification in form of automated tests with 100% code coverage *and* run mutation testing forever. If mutation testing cannot mutate the code anywhere without triggering a test, the software is bug free. That will also test libraries and OS code as needed. However, such specification (=automated test for everything) probably doesn't match *the end user intent*. – Mikko Rantalainen Aug 28 '20 at 10:49
  • and add to that if it's a web application. Multiple browsers, unstable browsers, quirky memory issues in browser. So people who think that 'BUG' free software is possible have never coded. – garg10may Apr 08 '21 at 09:49
30

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)

Vector
  • 3,180
  • 3
  • 22
  • 25
  • 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 01: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 01:30
  • I think it should be possible to formulate correctness wrt to some logic formulas. Then, an algorithm that can prove correctness wrt respect to any logic formula would also be able to decide the termination problem (does an arbitrary program on an arbitrary input loop forever?), which is undecidable. I am not sure if the above is correct but I would try to construct an argument in this way. – Giorgio Apr 21 '13 at 09:02
  • 3
    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
  • 7
    @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 05:14
  • @Mikey: What are the odds that a compiler will emit a correct binary for incorrect source, where "correct" in this context means correct for the final product? If your source has bugs, a correct compiler will either detect them and refuse to compile, or it will faithfully reproduce those bugs in the object code. – John R. Strohm Apr 23 '13 at 11:43
  • @JohnR.Strohm:'What are the odds that a compiler will emit a correct binary for incorrect source':Agreed, the odds are not very good.:-) But what does that have to do with the discussion? I skimmed over 2 or 3 papers with that title-all of them contain disclaimers along the lines I mentioned.You can measure the correctness of what a system DOES-but the question is about the things that a system CAN do, do but has NOT YET DONE-to predict them and test them. And the more complex the system, the more difficult that becomes-so 'correctness' is always relative. Can never be mathematically airtight. – Vector Apr 23 '13 at 14:20
  • @Giorgio - yes, I'm quite sure you can establish correctness if you outline certain parameters - a framework-algorithm that constrains the scope of the correctness you're trying establish. That is why/how we test software, no? But that wasn't the OP's question as far as I understand - the question was couched in absolute terms. So they were right to close it as 'not a real question': he's looking for proof of something that potentially extends infinitely. – Vector Apr 23 '13 at 18:07
  • @Mikey: Well, in order to define correctness you have to define with respect to what a program is correct, otherwise the word has no meaning. The point is that even if you define correctness wrt to a very general formalism (logic formulas), you cannot write a program that proves correctness. So you can express correctness in a very general way, but then there is no way to ensure / verify it in general. – Giorgio Apr 23 '13 at 18:23
  • What I mean is that you can write a specification (a logic formula) of what a program should do. But you cannot write a program that given a specification and an implementation can tell you that the implementation is correct. – Giorgio Apr 23 '13 at 18:27
  • @Giorgio -'you cannot write a program that...'. I assume you mean a complex spec (large scale software, as in question) no? If your spec says: 'if value is 0 you should return false, if values is 1 you should return true' it is not hard to prove the validity of a given implementation! – Vector Apr 23 '13 at 20:55
  • 2
    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
  • @Giorgio - agreed - impossible - you can't fight infinity... :-) – Vector Apr 23 '13 at 21:24
  • @Giorgio that's not to say there isn't value for the subset of programs that could be proven correct – jk. Apr 30 '13 at 11:27
  • @jk: Yes, I think such programs have great value. As far as I can remember from my logic course, it should also be possible to write a program that verifies the correctness of a proof (provided one is available), whereas it is trickier (or impossible?) to write a program that finds a proof for each assertion that is valid. – Giorgio Apr 30 '13 at 11:56
  • @Giorgio - after programming in hard core business world for 20 years (not in a college computer lab), I've come to question how much value such programs have: "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." And HUMAN users with ALWAYS manage to find the case that the machine never considered. :-) BESIDES: I think big potential for defects is in systems integration/regressive compatibility:try writing program to test that when adding new module to a trading system running 10 years with 30 sources of I/O. – Vector Apr 30 '13 at 15:44
  • 1
    @Giorgio - so IMO, following good design practices is a lot more important than concerning yourself with mathematical correctness: design your code to ensure that it can be well integrated and compliant with what's already there - and is robust enough to easily handle defects when they come to light (which they will). – Vector Apr 30 '13 at 15:48
  • 1
    @Mikey: I do not agree with you regarding mathematical correctness: a Mathematical proof ensures that something is correct. E.g., Pythagoras' theorem is valid and will be valid 5 billion years from now. If you can prove that a function or module is correct, you have a certainty that no good design practice will ever give you. Good design practices only help you make the code more manageable and more understandable but do not give you 100% certainty. So, being able to use some maths where it is possible it a huge advantage (it saves time and give you more confidence in your code). – Giorgio Apr 30 '13 at 21:59
  • @Giorgio-not saying that mathematical correctness is not important! It is fundamental! Just mean in my field-corporate trading systems-achieving mathematical correctness is NOT the hard part of development, and good design does more than just make code readable: it makes code more robust-easier to fix when those HARD errors crop up and more adaptable to ever changing user requirements. My code has bugs, but I can usually find and fix them quickly because I focus on design principles. Of course it depends on your field - if you're writing code for Wolfram Mathematica it is a bit different. :-) – Vector Apr 30 '13 at 22:12
30

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.

tcrosley
  • 9,541
  • 1
  • 25
  • 41
  • 30
    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
  • 8
    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
  • 4
    +1 Ran without errors for 135 missions from 1981 to 2011 – MarkJ Aug 14 '13 at 15:54
  • 5
    @MarkJ: we probably wouldn't know if the Space Shuttle didn't actually have errors. Every Space Shuttle missions are constantly, heavily monitored by hundreds of people, and any errors in the coding would have been manually corrected/overriden. – Lie Ryan May 21 '16 at 12:27
  • 2
    @LieRyan Which nicely shows one great property of robust systems - if they don't fail catastrophically and always allow manual tweaking, you can use redundant systems (such as the ones at the control center) to do the work instead. Of course, this only makes sense if you have such redundant systems, and if you can actually ensure correctness and consistency. On a typical business application, a crash will often be preferrable to operating on an inconsistent state - it's the difference between an annoyance and, say, sending money to the wrong guy. Or receiving money without it being sent... – Luaan Feb 08 '17 at 09:10
  • One page of documentation per a single line of code sounds about right for a program without bugs. Not many have pockets deep enough to pay for such a thing. – Mikko Rantalainen Aug 28 '20 at 10:53
16

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.
luiscubal
  • 1,517
  • 12
  • 13
  • +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
  • 8
    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 01:36
  • Thanks guys. But I was thinking with all the copy pasting, which is the right thing in this case, one would think that someone could have glanced at the code to see how it works. But if it's a very obscure bug, then fair enough. – Joan Venge Apr 21 '13 at 08:16
  • 4
    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 03:53
15

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.

Viliam Búr
  • 1,052
  • 8
  • 9
  • 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
  • 1
    "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
8

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.

Community
  • 1
mouviciel
  • 15,473
  • 1
  • 37
  • 64
6

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.

Ross Patterson
  • 10,277
  • 34
  • 43
  • 9
    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! – Peopleware Apr 22 '13 at 07:49
  • 5
    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 09:08
  • 1
    The Halting Problem does not say that it is impossible to prove whether a program will run to completion; it says that *there exist* programs for which it is impossible to prove. Regular everyday programs are not in this class. "While Turing's proof shows that there can be no general method or algorithm to determine whether algorithms halt, individual instances of that problem may very well be susceptible to attack. Given a specific algorithm, one can often show that it must halt for any input, and in fact computer scientists often do just that as part of a correctness proof." – endolith Sep 01 '15 at 00:57
3

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.

William Payne
  • 1,161
  • 8
  • 20
  • +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
2

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.

ddyer
  • 4,060
  • 15
  • 18
1

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.

rplantiko
  • 119
  • 3
1

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

AProgrammer
  • 10,404
  • 1
  • 30
  • 45
  • To quote Donald Knuth (from memory): You can prove that a program is bug free, but that doesn't mean it has no bugs :-) – gnasher729 May 21 '16 at 15:34
1

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.

Thomas Carlisle
  • 1,293
  • 9
  • 11
0

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.

Martin Maat
  • 18,218
  • 3
  • 30
  • 57
-2

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

Jonathan Graef
  • 229
  • 1
  • 7
  • It requires effort, but which pays back. – Laurent LA RIZZA May 21 '16 at 12:11
  • 1
    If you leave specification bugs out of the equation, your entire software becomes useless: Specifications are only tools to write down user needs in a relatively formal way, but in the end it is the user that needs to be satisfied, not the specification. And creating the specification is as much part of the software development as writing the code. After all, a complete formal spec would describe the behavior of the system just like the final code does, the spec is just not efficiently executable. – cmaster - reinstate monica May 22 '16 at 07:22
-2

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.

Laurent LA RIZZA
  • 535
  • 3
  • 8