Heartbleed, Shellshock and Raymond's Linus's Law

You have probably heard by now that bash, one of the basic tools in the Linux/GNU toolkit, has had a glaring vulnerability for the last, oh, twenty-plus years, now deemed Shellshock.  You've probably also heard of the Heartbleed vulnerability in OpenSSL.  Apart from making international press and raising serious questions about computer security, these two bugs have a number of features in common:

• They're implementation bugs.  Bash, as defined in its documentation, does not allow the sort of behavior that Shellshock allows, and likewise for SSL (the protocol) and OpenSSL (an implementation of SSL).  In both cases, the implementations were doing things they shouldn't have.
• They're basic implementation bugs.  In Shellshock, text which should be ignored or discarded is instead interpreted as a command.  In Heartbleed, a reply message which is supposed to have a given length instead has another.
• No one noticed them for a long time.  In the case of shellshock, a very long time.  Or at least, no one seems to have visibly exploited them.

It's that last item I want to focus on.  In his famous essay The Cathedral and the Bazaar, extolling the virtues of open source development, Eric Raymond claimed that "given enough eyeballs, all bugs are shallow," or in other words, if you had enough people looking at the source code to a system, any serious issues would be flushed out and fixed quickly.  He called this principle Linus's Law, in honor of Linux creator Linus Torvalds (Linus didn't come up with it.  Linus did put forth his own Linus's Law, but it doesn't seem to have garnered much attention).

In any case, despite bash and OpenSSL being two of the most widely used tools in the software world, these basic and serious bugs don't seem to have been flushed out quickly at all.  Now, it is possible that multiple people noticed the problems, shrugged and went on with their lives, or that some entity or another discovered the bugs and exploited them very quietly, but that's not how Raymond's Linus's law is supposed to work.

I think there are two reasons for this.

First, as many have pointed out, there's no convincing evidence that more eyeballs really do mean more bugs found.  Rather, it seems that you quickly hit diminishing returns.  Four people may or may not find about twice as many bugs as two people, but forty people probably won't find twice as many bugs as twenty.  Forty people may not even find twice as many bugs as two.

Exactly why this might be is a good research topic, but I'd guess that a lot of it is because some bugs are easy to find, some aren't, and once you've found the easy bugs throwing more eyeballs at the problem (now there's an image) won't necessarily help find the hard bugs.

One of the sobering implications of Shellshock and Heartbleed is that even simple bugs can be hard to find, but that's not news to anyone who's done much coding.

I think there's a second reason, though, more subtle than the first but worth noting:  There probably aren't really that many eyeballs on the source code to begin with.

In theory, millions of people could have found either of these two bugs.  If you've installed Linux, you have the bash and OpenSSL source code, or if you didn't copy it, you can easily get at it.  Odds are you didn't, though, unless you were actively developing one of those packages.  Why would you?  I use Linux systems all the time.  I don't want to study the source code.  I just want it to work.  I have looked at various parts of the Linux/GNU source, but generally just to see how it worked, not with a particular eye toward finding bugs.  Maybe that makes me a bad net.citizen, but if so, I'm pretty sure I'm in good company.

OK, but there have still been hundreds of contributors to each of those projects.  Surely one of them would have seen the problem code and fixed it?  Not necessarily.  A tool like bash consists of a large number of modules (more or less), and the whole point of breaking things down into modules is that you can work on one without caring (much) about (many of) the others.  Someone who worked on job control in bash would not necessarily have even looked at the environment variable parsing, which is where the problem actually was.

In other words, there might only have been a handful of people who even had the opportunity to find Shellshock or Heartbleed in the source code, and they didn't happen to spot the problems, probably because they were trying to get something else done at the time.


There's another kind of eyeball, though: testers.  Even if only a few people were looking closely at the source, lots of people actually use bash, OpenSSL and other open-source tools.

Fair enough, but again, their attention is not necessarily focused where the bugs are.  Most people logging into a Linux box and using bash are not going to be defining functions in environment variables.  Most script writers aren't either (though git, headed by Linus himself, seems to like to).  It's a moderately tricky thing to do.  Likewise, almost no one using OpenSSL is even going to be in a position to look at heartbeat packets.  Most of us don't even know if we're using OpenSSL or not, though if you've visited an https:// URL, you probably have.

In short, Raymond's implicit assumption that bug-finding is a matter of many independent trials, in the statistical sense, evenly distributed over the space of all possible bugs, looks to be wrong on both counts: "many" and "independent".

[The current Wikipedia article on Linus's law cites Robert Glass's Facts and Fallacies about Software Engineering, which made similar observations in 2003, over a decade before this was posted.  It also no longer seems to mention any version of Linus's law due to Linus himself.  That was removed in this edit  --D.H. Oct 2018]

Revolution OS and thereabouts

OK, so I just watched Revolution OS (on the Roku/Netflix box, of course), which I'd been putting off out of concern it might be more propaganda than information. The opening minute or so did little to allay that, but it turned out to be a pretty good documentary, and as even-handed as you could expect from something that interviewed Open Source folks entirely. It did this by getting in touch with several of the principals, including rms, esr and Linus, and pretty much just letting them talk. This is often a good idea, especially when the principals involved are thoughtful, creative, articulate and intellectually curious.

What emerged was a clear picture of the history of Free Software/Open Source, how "Open Source" came to be the dominant name, and the essential differences between the two: Free Software advocates want all software to be free because it's a Good Thing. Open Source advocates want particular software to be open because it's a Useful Thing. It may not surprise the attentive reader that I tilt toward the latter.

There are ironies along the way, for example a small one in Netscape adopting Open Source not through grassroots activism by engineers -- though this did occur -- but because it was eventually imposed from the top down by management; a large one in that the entire Open Source movement, which is at best indifferent to rms' s central goal of making all software free, depends crucially on GNU code and even more crucially on the GPL [more precisely: on the GPL and licenses directly influenced by it]. Rms himself points this out in his acceptance of the Linus Torvalds award at the 1999 Linux world. Linus's daughters trot back and forth behind him on stage all the while.

If you're looking for a spirited debate over Open Source vs. not-open, you won't find it -- except for an early quote from Bill Gates (who did not directly participate), there are no dissenting voices. If you're looking for knock-down, drag-out Linux vs. Windows, as the marketing collateral implies, you won't find that either. And a good thing. Revolution OS is a much more a chance to put a human face on the names you see floating around and get an idea of what they were thinking. Considered from that point of view, it succeeds nicely.


But I didn't really set out to write a movie review here. I really just wanted to share something amusing I ran across while chasing a link from a link from a page I looked up out of curiosity after watching the movie. This is from Jamie Zawinski, who has done more Open Source development than most of us, I would wager. Zawinski says:

But now I've taken my leave of that whole sick, navel-gazing mess we called the software industry. Now I'm in a more honest line of work: now I sell beer.

Specifically, I own the DNA Lounge nightclub in San Francisco. However, it takes quite a lot of software to keep the place running, because we do audio and video webcasts twenty-four hours a day, and because the club contains a number of anonymous internet kiosks. So all that code is also available.

This all sounds fine and noble, and I like the design decisions, but I have to wonder: Just how anonymous can an internet kiosk be in a nightclub full of webcams? Checking sports scores without having to establish an account anywhere? Sure. Plotting world domination? Maybe not so much.

By the way, this turns out to be post number 300. I made a production of 100 and 200, but from here on out I probably won't until some more significant milestone. Hmm ... 100π is about 314 ...

AJAX and samsara

Of the many aspects of the software biz that never ceases to amaze me is how many things I've learned over the years that Ivan Sutherland already knew before 1970. For example, from esr's Jargon File, aka The Hacker's Dictionary (v. 4.4.7):

wheel of reincarnation

[coined in a paper by T.H. Myer and I.E. Sutherland On the Design of Display Processors, Comm. ACM, Vol. 11, no. 6, June 1968)] Term used to refer to a well-known effect whereby function in a computing system family is migrated out to special-purpose peripheral hardware for speed, then the peripheral evolves toward more computing power as it does its job, then somebody notices that it is inefficient to support two asymmetrical processors in the architecture and folds the function back into the main CPU, at which point the cycle begins again.

Several iterations of this cycle have been observed in graphics-processor design, and at least one or two in communications and floating-point processors. Also known as the Wheel of Life, the Wheel of Samsara, and other variations of the basic Hindu/Buddhist theological idea.

(My understanding is that the graphics world is in the process of turning the wheel another notch with the GPGPU)

To this list we can the thin client/fat client oscillation, and at the moment the pendulum is swinging toward thicker clients. Thus AJAX.

Clearly there isn't one inherently correct solution to these sorts of "where do I put the processing power" questions. The answer at any given moment depends on economics: How much does processing power cost (and how much can you gain by concentrating it in powerful servers)? How much does bandwidth cost? How much do the various models cost to develop, test, deploy and administer?

A related question: How much development effort goes into new products and solutions, and how much goes into adapting existing products and solutions to the pendulum's latest swing?

80% of the solution in a fraction of the time

As can happen, I set out to write this piece once already, only to end up with a slightly different one. Here's another take, bringing Wikipedia into the picture.

First, let me say I like Wikipedia. A quick scan will show I refer to it all the time. I see it as a default starting point for information on a particular topic (as opposed to a narrowly-focused search for a given document or type of document). I don't see it as definitive, but I don't think that's really its job.

Wikipedia would seem a perfect test case for Eric S. Raymond's formulation of Linus's Law ("Given enough eyeballs, all bugs are shallow). But -- as Wikipedia's page on Raymond dutifully reports -- Raymond himself has said, well, here's how it came out in a New Yorker article:

Even Eric Raymond, the open-source pioneer whose work inspired Wales, argues that “ ‘disaster’ is not too strong a word” for Wikipedia. In his view, the site is “infested with moonbats.” (Think hobgoblins of little minds, varsity division.) He has found his corrections to entries on science fiction dismantled by users who evidently felt that he was trespassing on their terrain. “The more you look at what some of the Wikipedia contributors have done, the better Britannica looks,” Raymond said. He believes that the open-source model is simply inapplicable to an encyclopedia. For software, there is an objective standard: either it works or it doesn’t. There is no such test for truth.

Let's start right there. Software doesn't simply either work or not. You can't even put it on some sort of linear, objective "goodness" scale. Even in cases where you'd think software is cut and dried, it isn't. Did you test that sort routine with all N! combinations of N elements? Of course you didn't. Did you rigorously prove its correctness? How do you know your correctness proof is correct? Don't laugh: Mathematicians routinely find holes in each other's proofs, in some cases even after publication.

But most software is nowhere near this regime. Often we don't even know exactly what we're trying to write when we set out to write it (thus much of the emphasis on "agile" development techniques). In the case of something like a game, or even a website design, most of what we're after is a subjectively good experience, not something objectively testable (though ironically games seem to put a bigger premium on basic correctness, since bugs spoil the illusion).

It's not even completely clear when software doesn't work. If a piece of code is supposed to do X and Y, but in fact does Y and Z, does it work? It does if I need it to do Y or Z. What if it hangs when you try to do X, but there's an easy work-around? What if it hangs at random 10% of the time when you try to do X, but that's tolerable and nothing else does X at all? What if it does X if a coin flip comes up heads, but might not if it doesn't? I'm not making that one up. See this Wikipedia article (of course) for more info. What if it's an operating system and it just plain hangs some of the time? Not that that would ever happen.

All of this to say that I doubt that software and encyclopedia entries make such different demands on their development process. And as a corollary, I think the results are about the same. Namely, there are excellent results in some cases, reasonable but not excellent results in many cases, and occasional out-and-out garbage.

Here's what I think goes on, roughly, in both cases:

• Someone comes up with an idea. That person may be an expert in the field, or may just have what looks like a neat idea.
• The original person produces a first draft, or perhaps just a "stub", or an "enhancement request".
• If no one with the expertise to take it further is persuaded to do so, it stays right there indefinitely, or may even be purged from the system (perhaps to re-appear later).
• If the idea has legs, one or more people take it up and make improvements.
• Typically, one of three stable states is reached:
• It's perfect. Nothing more than minor cosmetic changes can be added. New ideas along the same lines typically become their own projects.
• It's good enough for everyone currently involved. That may not be particularly good, but no one can be persuaded to go further. This may be the case right out of the gate, or after several rounds of fixes by a single originator.
• It's not good enough, but there is no agreement on how to take it further. Work may grind to a halt as competing fixes go in and come out, or the project may split into two similar projects, with better or worse sharing of common material and effort.

Thinking it over, this process is not unique to open source. The magic of the open approach is that the bigger the pool of participants, the bigger the chance that an idea with legs will get supporters and get fleshed out, and the faster it will get to a stable state. In our imperfect world, that stable state is generally short of perfection. Put the two together and you have 80% of the solution in a fraction of the time.

That said, there are some differences between prose and software. I've argued above that software isn't hard and fast. It's soft, in other words. But prose is even softer. As a result, there is greater potential for disagreement on where to go, and in case of disagreement, there looks to be a better chance of thrashing back and forth with competing fixes, as opposed to moving forward but with separate (and to some extent redundant) solutions.

Wikipedia does seem to attract more vandals, but this is not necessarily because it's not software. It may also be because it openly invites frequent edits from a very large pool and changes are moderated after the fact. Open software projects, particularly critical pieces like kernels and basic tools, tend to require changes to pass by a small group of gatekeepers before being checked in. Conversely, some wikis are moderated.

As usual, this is all just my rough "figuring it out as I go along" guess, not anything with actual numbers behind it, but that's my story and I'm sticking to it for now.

Eyeballs and shallow bugs

Eric S. Raymond has asserted that "given enough eyeballs, all bugs are shallow", a principle he calls Linus's law after Linus Torvalds (my fingers want to type "Linux Torvalds").

How many eyeballs are enough? How many eyeballs are available? What does it take to get a "shallow" bug fixed, checked in and tested? What's a bug, anyway? A few meditations:

How many eyeballs are enough? Suppose an excellent kernel hacker has a 90% chance of nailing a given bug. What are the chances that two excellent kernel hackers can nail the bug? Well, it's not 180%. It will range from 90% (if the second doesn't know anything new about the particular problem) to 100% (if the second knows everything the first one doesn't).

If the two are completely independent sources of information there's a 99% chance one or the other will nail it. But what are the odds two people got to be excellent kernel hackers by completely independent routes? Now, what are the odds that a bunch excellent kernel hackers, quite a few more reasonable kernel hackers and a horde of non-specialists could nail the bug? Pretty good, I'd say, but not 100%.

How many are there? I've been doing software for a while now. I've built a few Linux kernels (roughly the equivalent of changing a tire on a car), and I've looked at small portions of the source (roughly the equivalent of opening the hood, pointing and grunting). If some subtle race condition should creep into the next version of the kernel, the odds that I could contribute something useful to the conversation are approximately zero (the automotive equivalent might be, say, being able to help fix a problem in a Formula One engine design).

The most qualified people in such a situation are the small and dedicated core of kernel maintainers and whoever put in the changes that turned up the problem. These may well be the same people. I know a fair bit about software in general, and even a bit about race conditions in general, but I know essentially nothing about the details of the kernel, the design decisions behind particular parts, the hidden pitfalls and so forth.

This being open source, much of that information is available, directly or indirectly. The limiting factor is the ability to absorb all of the above. This takes not only skill but time and dedication. The natural consequence is that, for at least some bugs, there just aren't enough eyeballs available to make them "shallow". Instead, someone will have to expend considerable brain sweat figuring out what happened.

[Another not-infrequent case: Lots of people see a bug, but no one can quite nail down what's causing it, much less suggest a fix. Filing good bug reports takes practice, just like writing good code does. Eliminating all the variables in a typical desktop environment takes time, even for someone with lots of practice. As a result, the people who could fix the bug don't have enough information to go on and probably have bigger fish to fry.]

What does it take to get a shallow bug fixed and tested? Suppose that the broken code in question (kernel or otherwise) has passed by enough eyeballs that someone has said "Hey, that's easy, you just need to ..." That person puts in a fix. Are we done? No. At a minimum, someone needs to test the fix, preferably someone other than the fixer. Someone should also look over the code change and make sure it fits in well with the existing code. And so forth. Open source doesn't remove the need for good software hygiene. If anything, it increases it.

What's a bug, anyway? Suppose not just one person steps up with a fix to some bug. Suppose two or three people do. Unfortunately, they don't exactly agree on the fix. Maybe one wants to patch around the problem, one has a small re-write that may also fix some other problems, and another thinks the application wouldn't have such bugs if it were structured differently. Someone else might even argue that nothing needs to be fixed at all.

Expediency will tend to favor the patch, and expediency is often right. The small re-write has a chance if the proponent can convince enough people that it's a good thing. The re-structured system will probably need to be a whole new project, potentially splitting up the pool of qualified eyeballs.


So does this mean that open source is a crock? Not at all. Most of the problems I've pointed out here aren't open source things. They're software things. Open source offers a number of potential advantages in dealing with them. One I think may be overlooked is that writing a system so that anyone anywhere can check it out and build it, and that several people can work on simultaneously and largely independently, enforces a certain discipline that's useful anyway. If your code's a mess or no one else can build it and run it, you're not going to get as many collaborators.

On the other hand, open source isn't a magical solution to all of life's problems, and there are arguably cases where you just need someone to say "Today we work on X," or "We will not do Y." Strictly speaking, that kind of control is a separate question from whether the source is freely available, but Linus's law assumes that eyeballs are not being commanded to look elsewhere.

So is Linus's law a crock? Not at all. It captures a useful principle. But like most snappy aphorisms, it only captures an ideal in a world that's considerably messier and more intricate.

[A few years later, a couple of striking examples turned up, in the form of Heartbleed and Shellshock -- D.H. Dec 2018]