Fog Creek Software
Discussion Board




Bugs as a function of system Size

There has been a lot of discussion on this board about the number of bugs in various pieces of MS software.  The majority of the software under discussion – be it Windows, Word, Access, whatever – is release-based software that has been developed over many years and, as a result, is now extremely large in both functional and code base terms.

While not trying to excuse these specific bugs, I am curious as to whether at least some of the bugs in these systems are due to the sheer size of each system itself.  The number of interactions that even a small application has is very high – user input, validation, database reads, security handling, OS variants, external interfaces, print drivers, to name a few.  It seems likely that the number of such software interactions will grow exponentially with the size of the software (measured either functionally or in code base terms).  As such, there must come a point where the number of interactions the software is making cannot be tracked (and is inconceivable by any human).  I speculate that it is possible that at this point bugs arise in the software due to the chaotic nature of these interactions – chaotic in the mathematical sense that the end-point varies massively for negligible changes in the starting conditions.  Thus a minor change in one part of the whole software environment within which the system resides causes a chaotic knock-on effect resulting in unpredictable behaviour – a bug.  And as the system size increases still further, this effect increases leading to further bugs.

So, my question: is it theoretically possible to write software over a certain size limit that is bug-free, or will it always have bugs just as a function of the system size?

David G
Wednesday, July 14, 2004

yes, theoretically it's possible, as long you can prove mathematically that your program is correct


Wednesday, July 14, 2004

Many 'bugs' are a result of underspecified behaviour. The "shell:" protocol 'bug' that has been associated with Mozilla recently (but applies to Word just as well, and various other pieces of software) is actually a specification problem. Everything works as specified ... is that a bug?

Ori Berger
Wednesday, July 14, 2004

Stands to reason that the bigger a piece of software is and the greater the number of users - the more likely you are to find bugs and security holes. If Mozilla/Linux had as many users as Explorer or Windows then i am sure you would find a lot more of these security issues cropping up with them too.

Fothy
Wednesday, July 14, 2004

Apache has significantly more users than IIS, and a better track record. IE's problems are not _just_ a problem of the numbers of testers.

Ori Berger
Wednesday, July 14, 2004

There have been some studies showing that you can use metrics to determine which modules need more care, feeding and testing. I remember from one of my classes (the prof was really into metrics) on how they managed to determine which modules were more likely to be buggy or be hard to maintain, so that you can spend your time looking at the problems, rather than the modules that are less likely to have them. After all, if the math shows moduleX to be 100 times more likely to be buggy than moduleY, you should spend a lot more time either reworking it, testing it, or reviewing it: spending the same amount of time on both modules would be malpractice.

>So, my question: is it theoretically possible
> to write software over a certain size limit
> that is bug-free, or will it always have bugs
> just as a function of the system size?
I had a professor who claimed yes, and claimed he had the research to show it: you just had to look in the important places and use metrics to find those places. Some of the stuff he worked on involved aircraft and spacecraft avionics (where bugs and blue screens of death could cause fatalities as well as costs in excess of $100,000,000).

There is some math you can do to determine how likely things are to have problems. Some of the math is evil complicated stuff like "principal component analysis" or "eigenvalues." One uses that hard math to reduce 10-100 measurements to 5 or 6 useful ones, since many of the measurements measure similar (yet slightly different) things: you want to get a couple of orthogonal measurements that explain 95% or more of the variability.

Metrics is one of those areas where "ivory tower research" is around 20 years ahead of the industry. Some of the simplest metrics, lines of code (100k lines of code = more work than 100 lines of code), number of paths (something with 1e6 paths will take far more testing than something with 1e2 paths), complexity of linkage between functions are rather obvious measures. I remember from my classes a bunch of others, some of which seem counterintuitive (or just plain silly) that ended up actually measuring something important.

course textbook:
http://www.amazon.com/exec/obidos/tg/detail/-/0534954251/
There were also a lot of handouts and reprints of articles. A number of other useful texts are out of print.

I've never worked at a place that uses metrics, but I believe that you cannot reach CMM5 without using them. The most mature company I worked for would have been CMM3 on a good day, and the vast majority would be rated CMM1 if you were being generous.

A hypothesis I have is: academic research in computer science is between 5 and 20 years ahead of the industry. The gaming industry is more likely to apply theoretical research and usually the first industry to apply it in practice.

Peter
Wednesday, July 14, 2004

It seems that very few bugs come from system internal components talking with each other, compared with the bugs that come from user input.  I think that user input filtering systems (and the system protection that comes from that) should be much more robust than it is in most systems.  People just assume that the user is going to put in something that makes sense.  To get a better picture of what the user input will be like, I would assume monkeys banging on the keyboard, mouse, and other devices simultaneously.

sir_flexalot
Wednesday, July 14, 2004

There was an article a while back that tried to relate prevalence of bugs to revalence of redundant operations (self-assignment, redundant assignment, dead code, and redundant conditionals).  Any chance certain coding conventions might lean into these?

The paper would be:
  Using Redundancies to Find Errors
  by Yichen Xie and Dawson Engler
  at the Computer System Laboratory at Stanford University
  published in ACM SIGSOFT 2002 / FSE-10, Nov 18-22, 2002

Thomas E. Kammeyer
Wednesday, July 14, 2004

You mean conditions like coding to really, really vague specs (or no specs at all), and not testing anything with unit tests? 
... D'OH!

sir_flexalot as "Jim-bo Farm-bo"
Wednesday, July 14, 2004


I would doubt that it's based solely on the size of the system.

I would suspect that it's more closely related to the number of components and the number of interactions within the system.

Then, as one component changes, it has the possibility to cause a ripple effect throughout *all* of the related components and then through their related components, etc.


Of course, simple Unit Tests can decrease *some* of this risk.

KC
Wednesday, July 14, 2004

Certain bug-affecting factors do increase as the system grows. One is if you manually code things, that increases the # of decisions a human makes.

Another problem is when you get near the limits of the machine. Then you increase the potential of running out of resources. Some tools (like IDEs, programmer's apprentices, etc) require an initial amount of resources, like how wealthy people can pay more upfront in order to save money over the long run.

Many engineers have believed the long-term greatest problem is shoehorning everything into a single-paradigm language. The mainstream example is imperative programming, but I'm sure that happens with any single paradigm taken to an extreme. Because as the codebase goes on, it becomes likely that you'll have a subsystem that can't be described well in the pure paradigm.

Tayssir John Gabbour
Wednesday, July 14, 2004

That paper was interesting!

But it was amusing to see this, in a section marked as "Overlay cautious programming style":

if(!(slave && slave->flags & IFF_UP && dev->flags & IFF_UP))

(Presumably this works, so I guess IFF_UP is 1?)

Tom
Wednesday, July 14, 2004

*  Recent Topics

*  Fog Creek Home