Phase-of-moon-dependent bugs suck

I just had a rather hair-raising experience with a phase-of-moon-dependent bug.

I released GPSD 3.11 this last Saturday (three days ago) to meet a deadline for a Debian freeze. Code tested ninety-six different ways, run through four different static analyzers, the whole works. Because it was a hurried release I deliberately deferred a bunch of cleanups and feature additions in my queue. Got it out on time and it’s pretty much all good – we’ve since turned up two minor build failures in two unusual feature-switch cases, and one problem with the NTP interface code that won’t affect reasonable hardware.

I’ve been having an extremely productive time since chewing through all the stuff I had deferred. New features for gpsmon, improvements for GPSes watching GLONASS birds, a nice space optimization for embedded systems, some code to prevent certain false-match cases in structured AIS Type 6 and Type 8 messages, merging some Android port tweaks, a righteous featurectomy or two. Good clean fun – and of course I was running my regression tests frequently and noting when I’d done so in my change comments.

Everything was going swimmingly until about two hours ago. Then, as I was verifying a perfectly innocent-appearing tweak to the SiRF-binary driver, the regression tests went horribly, horribly wrong. Not just the SiRF binary testloads, all of them.

My friends, do you know what it looks like when the glibc detects a buffer overflow at runtime? Pages and pages of hex garble, utterly incomprehensible and a big flare-lit clue that something bad done happened.

“Yoicks!” I muttered, and backed out the latest change. Ran “scons check” again. Kaboom! Same garble. Wait – I’d run regressions successfully on that revision just a few minutes previously, or so I thought.

Don’t panic. Back up to the last revision were the change comment includes the reassuring line “All regression tests passed.” Rebuild. “scons check”. Aaaand…kaboom!

Oh shit oh dear. Now I have real trouble. That buffer overflow has apparently been lurking in ambush for some time, with regression tests passing despite it because the phase of the moon was wrong or something.

The first thing you do in this situation is try to bound the damage and hope it didn’t ship in the last release. I dropped back to the release 3.11 revision, rebuilt and tested. No kaboom. Phew!

These are the times when git bisect is your friend. Five test runs later I found the killer commit – a place where I had tried recovering from bad file descriptor errors in the daemon’s main select call (which can happen if an attached GPS dies under pessimal circumstances) and garbage-collecting the storage for the lost devices.

Once I had the right commit it was not hard to zero in on the code that triggered the problem. By inspection, the problem had to be in a particular 6-line loop that was the meat of the commit. I checked out the head version and experimentally conditioned out parts of it until I had the kaboom isolated to one line.

It was a subtle – and entirely typical – sort of systems-programming bug. The garbage-collection code iterated over the array of attached devices conditionally freeing them. What I forgot when I coded this was that that sort of operation is only safe on device-array slots that are currently allocated and thus contain live data. The test operation on a dead slot – an FD_ISSET() – was the kaboomer.

The bug was random because the pattern of stale data in the dead slots was not predictable. It had to be just right for the kaboom to happen. The kaboom didn’t happen for nearly three days, during which I am certain I ran the regression tests well over 20 times a day. (Wise programmers pay attention to making their test suites fast, so they can be run often without interrupting concentration.)

It cannot be said too often: version control is your friend. Fast version control is damn near your best friend, with the possible exception of a fast and complete test suite. Without these things, fixing this one could have ballooned from 45 minutes of oh-shit-oh-dear to a week – possibly more – of ulcer-generating agony.

Version control is maybe old news, but lots of developers still don’t invest as much effort on their test suites as they should. I’m here to confirm that it makes programming a hell of a lot less hassle when you build your tests in parallel with your code, do the work to make them cover well and run fast, then run them often. GPSD has about 100 tests; they run in just under 2 minutes, and I run them at least three or four times an hour.

This puts out little fires before they become big ones. It means I get to spend less time debugging and more time doing fun stuff like architecture and features. The time I spent on them has been multiply repaid. Go and do thou likewise.

61 comments

  1. I think the first suspicion in phase-of-moon bugs should be finding if you are using uninitialized memory…

    BTW. did you use test suite (or test from test suite) to check if commit is good with git-bisect? Did it always crash on bad commits when bisecting? Did you use (or know) any technique to make phase-of-moon bugs more likely?

    1. >I think the first suspicion in phase-of-moon bugs should be finding if you are using uninitialized memory…

      Probably not the problem here. The device array is static, thus initially zeroed. FD_ISSET() shouldn’t blow up on a zero file descriptor. I think it ended up with random data because it wasn’t zeroed when deallocated.

      >BTW. did you use test suite (or test from test suite) to check if commit is good with git-bisect? Did it always crash on bad commits when bisecting?

      Yes and yes. The usefulness of a fast test suite was supposed to be the major point of the post.

      >Did you use (or know) any technique to make phase-of-moon bugs more likely?

      I did not.

  2. Besides the obvious “run as many tests as you can as often as you can and automate those tests as fully as you can,” that is the main thrust of this post, is there anything else a programmer can do to find such tricky phase-of-moon-dependent bugs?

    1. > is there anything else a programmer can do to find such tricky phase-of-moon-dependent bugs?

      I think fuzz testing could be useful for this. Feed it random inputs and watch what happens.

  3. I am impressed. No commercial software project on which I have worked would have had anywhere near the test suite needed to pin down a bug like that in 45 minutes.

    These were applications, not system programs, and I haven’t done any commercial programming since 2001.

    Either testing is far more sophisticated today than 15 years ago, or open source is far ahead of commercial development, or both.

    1. >Either testing is far more sophisticated today than 15 years ago, or open source is far ahead of commercial development, or both.

      I think it’s both. The concept of formalized unit testing is not quite 15 years old IIRC, and it has had a really galvanizing effect on the open-source community in the last five years or so. I’ve been a bit ahead of the curve on this, but not out of sight of the median.

      Also, the sheer speed of git helps a lot. If I’d been trying to simulate git bisection using (say) Subversion, the process would have taken a hell of a lot longer simply because, by comparison, Subversio checkouts are dog-slow. That in turn changes how you use the tool.

      An economic problem is that even with good tools available, many commercial-project managers won’t budget the time for building a decent test suite.

  4. “The first thing you do in this situation is try to bound the damage and hope it didn’t ship in the last release. I dropped back to the release 3.11 revision, rebuilt and tested. No kaboom. Phew!”

    It might be just me, but that doesn’t guarantee that it didn’t ship in the release – the phase of the moon could have been different in that build.

    1. >It might be just me, but that doesn’t guarantee that it didn’t ship in the release – the phase of the moon could have been different in that build.

      Yeah…but once I knew what the kaboom was, I could be certain. The bad code wasn’t introduced until after 3.11.

    1. >Does GPSD use test framework?

      No. The main test tool is a Python program called ‘gpsfake’ which wraps gps in a simulation environment, feeding it known sentences through ptys.

  5. Ever vigilant. There’s no such thing as perfect code anymore. Kinda like when DNA got to be more that an few thousand base pairs.

  6. Just as an FYI, this is one of the reasons I am not a fan of that whole “be liberal in what you accept, strict in what you receive.” It tends to lead to difficult unpredictable bugs of this kind. By being liberal in what you accept, you are saying you accept inputs that you haven’t entirely planned for, and consequently the code might or might not work.

    My view is that you should be extremely strict on what you accept, code brittleness has the advantage that it breaks early when the problem arises, not late when the breakage point is a mile away from the true cause.

    In the specific case you mentioned, it would be great had the debug version of the library done an expensive check for the validity of the fd before closing it. Then you would not have got a slew of hex-babble, but rather a debug assertion that you had passed an invalid fd to the isset func, which is precisely the data you need.

    Of course you turn off all those checks in a production version (which you also regression test.)

    It is why code that I write is littered with asserts for very strict restrictions on input parameters, output parameters and state. I want my code to break as soon as it is in a situation that I have not anticipated.

    It is also why I am a fan of libraries that behave in ways that are strictly correct, but not the obvious path. For example in Windows the debug version of malloc used to write garbage into the alloc-ed block, and the free used to write garbage over the free-d block. These are valid implementations but they cause code to break when subtle but incorrect assumptions are in the calling code.

    In fact something like this would have helped here (not exactly because I know you aren’t using malloc-ed memory, but something similar in your home grown garbage collector), if the data is sometimes zero or sometimes garbage you will get a phase of the moon bug. But if it is always garbage unless it is being used, then it will always break, not capriciously break.

    I’d recommend you considered adding that debug version randomization to your code, because the only thing worse than finding a “phase-of-the-moon” bug in your code is that bug re-emerging after you think you have tested it. So ideally you need to add some sort of regression test to recreate the circumstances and validate the defect is corrected.

    It is also why, as I have previously advocated here, I think it would be awesome if compilers came with a -weird flag. When turned on the compiler chooses very strange but valid choices. For example, a C compiler might use 44 bit integers in the opposite endian-ness of the native system. Of course it wouldn’t make for fast or acceptable executables, but it would shake out most portability bugs.

    BTW, in my world we call these types of defects “heisenbugs” which I always though was amusing.

    1. >BTW, in my world we call these types of defects “heisenbugs”

      Ah, so that bit of hacker slang has made it to you, eh? Good. Do you use “Bohr bug” and “Schroedinbug” too?

    1. >Is this the sort of thing valgrind might have caught?

      No. I use valgrind; it’s part of my pre-release checks.

  7. > Just as an FYI, this is one of the reasons I am not a fan of that whole “be liberal in what you accept, strict in what you receive.” It tends to lead to difficult unpredictable bugs of this kind. By being liberal in what you accept, you are saying you accept inputs that you haven’t entirely planned for, and consequently the code might or might not work.

    By a strict definition, any language which separates tokens by arbitrary whitespace counts – you might receive a sequence of whitespace bytes you haven’t entirely planned for.

    You just have to know the code and make sure the test cases cover all code paths.

  8. P.S. I will mention, by the way, that there was recently an issue of precisely that nature in the timezone database code: The language of zoneinfo files has always been defined as consisting of tokens separated by arbitrary whitespace, but all actual files contained values separated by tabs (or spaces in certain contexts), with extra leading tabs on one particular kind of statement. A file was checked in with an extra ‘stray’ tab, or spaces or something, which caused no problems for the tools it shipped with, but there were complaints from the author of a third-party tool, which parsed the files by splitting on tab characters.

    I would ask both esr and Jessica Boxer: Who do you think was in the right, here? Should the language have been defined with strict whitespace requirements for easy parsing, or is arbitrary whitespace separation (for easy editing in a plain text editor and understanding what’s going on with the Mk.1 Eyeball) the correct way to go? This is a microcosm of being liberal in what you accept… and as for being strict in what you send, code generation tools often strictly follow style guides.

    1. >arbitrary whitespace separation (for easy editing in a plain text editor and understanding what’s going on with the Mk.1 Eyeball) the correct way to go?

      I think so. Cases like this are an excellent demonstration of why it is best to be liberal in what whitespace you except, even if you buy Jessica’s strict-checking in other contexts.

  9. @Random832: Apparently the Mr. Third-Party Tool Author failed to RTFM. Here is what it says:

    Input lines are made up of fields. Fields are separated from one
    another by any number of white space characters. Leading and trailing
    white space on input lines is ignored. An unquoted sharp character (#)
    in the input introduces a comment which extends to the end of the line
    the sharp character appears on. White space characters and sharp char?
    acters may be enclosed in double quotes (“) if they’re to be used as
    part of a field. Any line that is blank (after comment stripping) is
    ignored. Nonblank lines are expected to be of one of three types: rule
    lines, zone lines, and link lines.

    If the author can’t read plain English, that’s his problem, not the authors of zic.

  10. I was initially intrigued as I started to read a blog post about software that processes position data received from a fleet of satellites orbiting the Earth when said blog post has the words “phase of moon” in the headline.

    Questions spun in my mind: Does the big round silent satellite have some subtle effect on the fleet of little noisy ones? Was there a bug in almanac data processing? Did the USAF accidentally DoS a bunch of consumer GPS receivers with a corrupted almanac stream? (aside: wait, does gpsd even work with this layer of GPS signal? That would be interesting too!) Is there a new variant on the week-1024 GPS receiver bug that involves our planet’s largest satellite in some way (but not that specific bug, since it’s only week 783 or so right now)? Did we find some previously unreported but severe GPS position error proportional to tidal forces or orbital precession? Or both?

    Nah, the whole post was about memory lifecycle bugs and the importance of testing. Nothing to do with the phase of the moon in any literal sense at all. ;)

  11. > @Random832: Apparently the Mr. Third-Party Tool Author failed to RTFM. Here is what it says

    I was there, you know.

  12. >Cases like this are an excellent demonstration of why it is best to be liberal in what whitespace you except, even if you buy Jessica’s strict-checking in other contexts.

    Depends on how strictly you can nail down the definition of “whitespace” (does \xc2\xa0 or   count?).

    “[\n\t ]” is better than “whitespace character” in that the former removes one opportunity for creatively correct but incompatible implementation–but now the spec is so specific that a correct implementation has no room for “liberal.”

    It helps when the spec defines how to get whitespace to not be a field delimiter–that half of the spec is often missing when people try to specify a file format, and then everyone invents their own quoting rules.

  13. Cases like this are an excellent demonstration of why it is best to be liberal in what whitespace you except, even if you buy Jessica’s strict-checking in other contexts.

    The LANGSEC folks are the ones who really get this stuff right on a philosophical level. Every interface that a component exposes to the outside world is a formal language, and you should always think of it as such. If this language is ill-specified, then you cannot have a correct program or even define what it means for the program to be correct. Ideally, the language should belong to some tractable and well-understood class (e.g. regular or context-free). The simpler the language, the easier it is to write a recognizer for it and therefore reject all illegal inputs. Being liberal about what whitespace you accept is perfectly consistent with LANGSEC principles, because doing so won’t make your language appreciably more complex. A regular language with liberalized whitespace is probably still regular, and the change probably won’t impact the structure of the AST at all.

  14. @Random832
    > By a strict definition, any language which separates tokens by arbitrary whitespace counts

    I guess I wasn’t clear. There is a different between strict and inflexible.

    For example, HTML requires an HTML element containing a head element and a body element. Inside the body you can have a variety of elements, and put whatever whitespace you want between them. However, browsers went all Postel on the HTML, and now we have a dreadful mess where at least 90% of HTML pages out there are ambiguous crap.

    Browsers are full of heuristic pragmatism to get all this garbage to vaguely resemble the intended output, and no two browsers render exactly the same. Where I work, some places the applications they have only run on IE 8 compatibility mode, some only run in non compatibility mode, some only run in modern browsers, some only run in older browsers. It is a support nightmare (third party apps that is, mine all use clean HTML.)

    However, if browsers had always been strict in their input parsing rules we would have clean HTML everywhere, because if it wasn’t clean, it wouldn’t run anywhere. That notwithstanding the fact that the creators of the HTML can still space and indent the elements however they think visually appealing, or name their element ids and classes in whatever form they want.

  15. @Random832
    With respect to the zone info file, I think two things. First of all, the third party vendor was in the wrong. If his code didn’t meet the spec, shame on him, and it is pure chutzpah to complain.

    As to whether the zone info file *should* allow that, I’m not really sure because I don’t know how those files are created. If they are created by humans manually, then yes, humans find it hard to distinguish between one space an an arbitrary whitespace string, so that should be strictly defined and allowed. If it is machine generated, absolutely not. It should have a strict format.

    Note here that I would accept a more liberal input from a human than a machine, nonetheless that liberal input needs to be strictly defined even if flexible, and that strictness enforced in the software.

  16. @esr: You need to use the Star Trek method:

    A couple of bit players enter the turbolift and one casually mentions “the Heisenbug compensators” to the other. Problem solved.

    (You can have them wearing red shirts so you can kill them off later in the episode,)

  17. > “An economic problem is that even with good tools available, many commercial-project managers won’t budget the time for building a decent test suite.”

    Manager: Look, we don’t have time for that. We need to ship by the end of the quarter. Just get it done. We can do all that “nice to have” stuff later when we have more time.

    Who hasn’t heard some variation of that! One of the big advantages of Open Source over the commercial world, IMHO, is that development is not dominated by schedules or marketing promises.

  18. @esr
    >An economic problem is that even with good tools available, many commercial-project managers won’t budget the time for building a decent test suite.

    i think your assessment is right, but the underlying assumptions made (by the putative managers) is entirely wrong. Test suites increase time to market, for the most part anyway. The irony of software quality is that it is actually a negative cost, the more you have the less the project costs overall.[*]
    However, this is not something that is widely understood in the standard project management methodologies and so the negative cost is not taken. It is actually true, I think, because of the intense flexibility of software. Without extensive test suites you couldn’t build a complex integrated circuit, without testing you can’t build a bridge. But software is flexible enough to code and fix, and so the idea of testing gets lost in the rush to add features. “It works on my machine” is the curse of modern software development.

    [*] Note quality is a negative cost up to a point. Once you get to a certain level of quality the cost for more skyrockets. That level of quality is rarely needed except in certain types of high risk software like life critical for example. So outside of those all practical levels of quality on projects of any significant length is essentially free or negative cost.

  19. @Jessica Boxer: What’s your opinion of the error recovery rules in HTML 5? Even something like [b]bold[i]both[/b]italic[/i] is well-defined in HTML 5 – not just in its visual appearance but also in the DOM tree it generates (Consisting of one bold element and two italic elements, one inside the bold and one outside it). It seems like the problem isn’t in being liberal in what one accepts, but rather in not being rigorously defined (and therefore the details of how exactly one liberally accepts things differing from version to version and from implementation to implementation).

  20. “…quality is a negative cost up to a point. Once you get to a certain level of quality the cost for more skyrockets.”

    Jessica Boxer +6

    Before I retired, GE went all out for Six Sigma. I made myself very unpopular by pointing out that, if they would just buck it down to Five Sigma, they’d save millions of dollars and nobody would notice.

  21. >>Does GPSD use test framework?

    >No. The main test tool is a Python program called ‘gpsfake’ which wraps gps in a simulation environment, feeding it known sentences through ptys.

    Perhaps shell-script based test “framework” used by Git would be of use? It produces TAP (Test Anything Protocol) output, so you can use it with tools like Smoker or ‘prove’ (which allows such things as saving state and running only those tests that failed).

    1. >t produces TAP (Test Anything Protocol) output, so you can use it with tools like Smoker or ‘prove’ (which allows such things as saving state and running only those tests that failed).

      I considered implementing TAP, and decided that in this case the hassle cost would exceed the benefits.

  22. Random832
    > What’s your opinion of the error recovery rules in HTML 5?

    I have never heard of it, so I have no opinion. Based on the vignette you give it sounds like a messy hack, but in fairness, version 5 of just about any protocol includes a few messy hacks.

    > It seems like the problem isn’t in being liberal in what one accepts, but rather in not being rigorously defined

    That is part of it, another important part is cohesiveness of function. And another important part is what you do when unexpected input is received. The Postel rule seems to be “try to deal with it as best you can, interpret the unexpected data in a manner that approximates valid data.” I say don’t do that at all. When you receive unexpected data, your program should break, because the unexpected data is a bug, and you need to stop for bugs as soon as they appear so that the cause is as close to the effect as possible.

  23. The other problem for web browsers in particular*, and the reason there was such an arms race to make something reasonable-looking out of bad markup is: If your competitor can display every website, even imperfectly, and all you can display is a giant yellow error screen, guess which browser people are going to use.

    It’s also a bad idea to crash in response to something being wrong with untrusted input – by doing so you’ve giftwrapped a denial of service vulnerability.

    *Though it can be probably generalized to other broadly similar types of software. Probably one of the common themes is “The user is not responsible for the data and cannot fix it.”, which applies to GPSD.

  24. @Jessica
    > Just as an FYI, this is one of the reasons I am not a fan of that whole “be liberal in what you accept, strict in what you receive.”

    But this is in no way a refutation of that rule; if anything, it’s a reinforcement of it.

    When you’re testing a program like GPSD that has to accept data streams from other sources, you should act as if those streams come from Russian and/or Chinese cyber-warfare teams that are actively trying to crash your program and pwn your machine. You should throw deliberately-malformed data at it as a matter of course in your automated testing. That means dead slots filled with garbage should be fed to it, and it should properly deal with them.

    It’s precisely because GPSD was not able to accept the dead slot that hadn’t been zeroed out that this bug hit it. ESR’s fault lay in the unwarranted assumption that the array was structured correctly for his code to work, when no such guarantee was in force. He “got away with” that assumption for a long time out of sheer luck. Whether that was good luck or bad luck is a matter of interpretation.

    Your practice of testing for things others would ASS|U|ME to be true is admirable. I try whenever possible to put such sanity checks in my programs as well. The decision has to be made on a case-by-case basis about whether failing loudly is the right move, however. For a program that is only supplying information, attempting to display as much information as possible, is a reasonable approach.

    For a browser-type program, the model historically is that you’re just displaying a document, not taking any kind of potentially-destructive action. As browsers have evolved to include form-submission and client-side scripting elements, that model is no longer accurate. Any problem in parsing, say, a Javascript code block, should be dealt with by entirely disabling scripting for the page, rather than by trying to execute some code but not the defective portion.

  25. @Monster
    Looks like I am not making myself clear. I am not saying you should assume anything, on the contrary I am saying your should enforce your assumptions.

    When it comes to data coming from uncontrolled sources like humans and the KGB infiltrated GPS device that you just plugged in your computer, you must be even more rigorous enforcing your assumptions. You need to look at the data and validate that it exactly matches your expectations and if not “break”. In the case of a daemon program like GPSD “break” doesn’t mean “crash”. In that case it would most likely mean, “log the error and give a generic error response to the caller.”

    The problem with Postel is that it liberality would try to take data that didn’t follow the assumptions to the letter and try to interpret it. That is a recipe for disaster when the data is potentially an attack vector.

    I haven’t seen the specific nature of the GPSD bug, but trying to understand what happened, it looks like an internal error. That is to say an error with a data structure holding a file descriptor. When it comes to internal inconsistencies you need to be even more aggressive in demanding the satisfaction of your assumptions. There is no reason for internally generated data to not match the program’s assumptions, and so when it doesn’t it is almost certainly a bug, and you need to break as soon as possible so that the error report is as close to the error cause as possible.

    I don’t mean to sound critical of Jon Postel. He was a man whose immense skill and productivity made the internet possible, and we all owe him a debt of gratitude. However, the eponymous rule is not, IMHO, a good one. And I am sure Jon, open minded scientist as he was, would be happy to hear and discuss a different point of view.

  26. @Jessica:
    >Note here that I would accept a more liberal input from a human than a machine, nonetheless that liberal input needs to be strictly defined even if flexible, and that strictness enforced in the software.

    I would say that it’s also generally good to be exceedingly liberal in what you accept when it is to immediately be piped to a human.

    Gedit had a misfeature a few years back in which it was strict in what it accepted as far as text encodings. If a file contained control characters for the selected encoding, it would refuse to open the file and present an encoding selection dialog. Of course, a garbled text file might contain control characters in any encoding the user might select. This prevented the user from viewing a file that might be almost entirely readable.

  27. @Jon Brase
    > Gedit had a misfeature a few years back in which it was strict in what it accepted as far as text encodings. If a file contained control characters for the selected encoding

    How should the editor display a backspace character or a \r character or 0x01? If you open a file containing the string “hello\bthere” is it displayed as “hellthere” or “hello there” or some other variant? The problem here is not it strictness, it is that the developers didn’t think through properly how to deal with these issues. In fact their strictness brought to the surface a defect in their code that needed to be fixed.

  28. Oh and just to be clear, I am not saying that they even need to specify what happens specifically with a \b. It might be equally acceptable to have a rule that said “All non printable characters are displayed as a space.” This adds flexibility without decreasing strictness.

    Honestly, who would write a text editor and not think about what to do with non printable characters?

  29. @Jessica

    >Honestly, who would write a text editor and not think about what to do with non printable characters?

    Microsoft. Try looking at non-printable characters in Notepad sometime.

    I think the main difference we’re having on Postel’s rule is one of =how= to “break”. I’m not saying the program should “crash”, but for certain things it should emit an error message and exit to the calling program/shell, and for others it should slip something into the output like that <?> character used to indicate “There’s a character here I can’t render correctly”. The most extreme case of a program halting is a kernel panic, a situation so bad that the kernel code that would otherwise be used to write to a log file cannot be trusted to do so without hosing critical system files.

  30. Viz. the strictness / how to interpret dodgy input debate, would it be possible for software to have a setting in the config file telling it what to do?
    Something along the lines of: Interpret, Crash, Ignore, Ignore & Log, Prompt (ask the user what to do).

  31. @Lambert, I’d like to see that as well as command-line and environment variable options. When you’re doing your regression testing for your program that produces data, you should set the options for the other processes in the pipeline to at least log all errors, so that you can include them in what the test suite examines.

  32. @ The Monster:
    I wasn’t particularly talking about testing, although it would be an application: I was thinking more about setting up config to suit a particular purpose, e.g. halting on bad input for security-critical uses; prompting if a human is available; interpreting if, above all else, the software should just *try*, and bad output is not too important.

  33. @Lambert
    > halting on bad input for security-critical uses

    That is in and of itself context-dependent. For instance, if I’m browsing a simple HTML document that happens to be malfomed in some way, it’s perfectly safe to configure the browser to just stick a <?> tag in the document to show me “there’s a problem rendering this bit”. But if I’m on my bank’s page managing my accounts, I want =any= error parsing the page to be a deal-breaker (because those errors could cause serious problems with client-side scripting). There’s no easy way to explain this distinction in a config file other than by defining “zones”, so that I can say “It’s ok to allow scripting here, but in exchange, I want strict rendering.”)

    [ultra-high security]
    mybank.com
    myjob.com

  34. @Lambert
    I believe it was Joel Spolsky who said that the options dialog (or config file) is a list of all the decisions that the programmers were afraid to make.

    Which is hyperbole for sure, but nonetheless, poignant.

  35. When Eric mentioned “phases of the moon”, I thought he meant calculations of the effects of the moon’s gravity on GPS satellites dependent on its orbital position and direction to the sun and earth.

  36. @Jessica Boxer

    They have every right to feel afraid to make decisions that can heavily impact usability, when they do not know the circumstances under which the software will be run.
    The configurability & customisability of Linux as a result of its modular architecture is, IHMO, one of its greatist advantages.

  37. I know little about systems programming and C, so I may be talking out of my butt, but is testing really the best approach to such problems, instead of trying to prevent them from happening?

    To me simply hoping a test catches it means working with probability instead of causality and as a general, philosophical approach to life, I like causality more. Even when a little Nassim Taleb in the back of my head is screaming “No!”, still. If I need a coin flip to show heads at least once, I would feel better about constructing a machine that always flips it to heads, rather than just flipping it 100 times and trusting probability will deliver at least one heads to me.

    I mean if the keyword is “I forgot”, then it should be, theoretically, possible to make checklists (“In situation X, don’t forget Y, Z, N”, similarly to what airline pilots do. Checklists for every type of system programming function could be built into EMACS so you could press Ctrl-Meta-whatever, enter a number or mnemonic or something, and have the checklist yanked in in the form of a comment. For example, it could be possible to make it a habit to write a comment for every single function that says in what cases is it supposed to be safe, and make it semantic, like, adding an XML tag around it and having a Perl script collect all function names with their SafetyConstraint tagged comments and reading through that would indicate if a constraint is too optimistic. Or something. Wouldn’t that be better than to just hope that with a large number of fast, automated eyeballs, there will be a high probability of every bug being shallow?

  38. @Lambert
    > The configurability & customisability of Linux as a result of its modular architecture is, IHMO, one of its greatist advantages.

    And one of its greatest challenges, especially for non technical users.

  39. @esr:

    I think fuzz testing could be useful for this. Feed it random inputs and watch what happens.

    Hardware designers often use constrained random testing. You should have good justification for the chosen constraints (why A and B cannot happen together, or why you don’t care if they do). In a comment on one of your earlier posts, I described testing a multiplier:

    http://esr.ibiblio.org/?p=5211&cpage=1#comment-422610

    In that instance, after I applied the constraints, I did an exhaustive (within the constrained values) test. But sometimes, even after constraints are added, exhaustive tests would not finish until sometime after the heat death of the universe. In those cases, you need to fall back on random testing, but constraints are still highly useful, working in concert with the randomization to increase the testing efficiency.

    The concept of formalized unit testing is not quite 15 years old IIRC

    I’d need to see a cite on that, or clarification on what your definition of those is. I can maybe believe that “write the test first” is only 15 years old, but formalized unit tests have been used for several decades for both hardware and software. Look at the diagram on the 9th page of this article from 1984 and you’ll even see the phrase “continuous integration (post build, regression, and floor release validation)”.

    @Jessica Boxer:

    My view is that you should be extremely strict on what you accept, code brittleness has the advantage that it breaks early when the problem arises, not late when the breakage point is a mile away from the true cause.

    For certain classes of programs, I agree completely with this. However, when you make statements like this, it really puzzles me why you have such a problem with Python. I do this all the time in Python, and it’s really easy…

    BTW, in my world we call these types of defects “heisenbugs”

    Yeah, that’s pretty standard. However, a few months ago, I ran across what, for lack of a better term, I’m calling an “anti-Heisenbug”. Perhaps someone here can come up with a better name for it.

    This bug affected a new chip. Some percentage of the chips didn’t always wake up (the internal regulator did not come on.) Whenever they wouldn’t wake up they stayed dead — the internal regulator would never come on after any reset, but if you somehow forced them on (e.g. by injecting a voltage on the regulator pin), they they would keep waking up OK.

    When I dug in, I figured out that the bug existed because sometimes a switch could power up in the wrong state, and a cascade of events led to the switch being locked in that state, even during reset. This switch is not for regular operation — it merely allows an internal node of the regulator to be viewed on an external pin for device debugging.

    In other words, unlike a bug that goes away when you look at it, this bug only exists because somebody added hardware specifically to allow looking for bugs …

    However, if browsers had always been strict in their input parsing rules we would have clean HTML everywhere, because if it wasn’t clean, it wouldn’t run anywhere.

    The Postel rule seems to be “try to deal with it as best you can, interpret the unexpected data in a manner that approximates valid data.” I say don’t do that at all. When you receive unexpected data, your program should break, because the unexpected data is a bug…

    I’ll echo what Random832 said: “If your competitor can display every website, even imperfectly, and all you can display is a giant yellow error screen, guess which browser people are going to use.”

    There is always a tension between standards and the real world. Especially if you’re in a competitive situation like the browsers were. Are customers going to choose the browser that shows them the most webpages in a reasonable fashion, or the browser that tells them “sorry, you should contact the maintainers of foo.bar.com and let them know that this page is non-compliant”?

    The subsequent discussion of the text editor issues is highly relevant here. Yes, I can always drop back to hexdump, but if all other things are equal, guess whether I choose the editor that tells me on some files “I’m sorry, Dave” or the editor where the designers said “You know what? Any possible collection of bytes is a file that some user is going to want to look at and extract meaning from.”

    Browsers are in the same boat — when a user clicks on a link, he expects to extract some useful information from what happens next.

    Now, that isn’t to say that it wouldn’t be useful for the browsers to add a display that says “Here’s my best guess, but this website was coded by people too clueless to run a validator, and my guess might be garbage.” That sort of gentle guidance to adhere better to the standards would probably help out a lot.

    The configurability & customisability of Linux as a result of its modular architecture is, IHMO, one of its greatist advantages.

    And one of its greatest challenges, especially for non technical users.

    Maybe so, couldn’t say. What I can say is that various Windows products which allow you to completely change the look of the interface without knowing how you did it or how to revert it are a royal pain in the ass. And it’s not just the application programs — one of the technicians has this problem where, every time he uses a remote screen viewer to show people a board layout in a conference room, it screws up every icon on his screen.

    @Shenpen:

    I know little about systems programming and C, so I may be talking out of my butt, but is testing really the best approach to such problems, instead of trying to prevent them from happening?

    There is no question that quality cannot be tested in. This is why aesthetics count — during both development and maintenance, code will be read many, many times, and it is much easier to read code that is not ugly.

    But it’s also extremely easy to write something that is beautiful, yet wrong. For things that really matter, that do not have an exponential blow-up of state, sometimes formal methods, such as theorem proving and model checking are used. These are important, yet difficult enough to get right, that their utility is limited. The biggest use of these methods in the hardware world is formal equivalence checking, which helps to prove that every subsequent representation of a design (e.g. gates, transistors, polygons) is logically equivalent to the original source design.

    Of course, major portions of the source design are usually written by humans, and those make mistakes. So, although testing cannot make a bad design into a good design, it can often help to make sure that a good design doesn’t fail miserably in the real world because of stupid little mistakes.

  40. Forgot to mention that in that 1984 shuttle article, on the fourth page, under the section “Requirements Implementation Planning”, they described a methodology that I would characterize as “release early; release often.”

    Of course, because the first release was in 1977, they had to apologize because it wasn’t the way you were “supposed” to do software engineering back then:

    Due to the size, complexity, and evolutionary nature of the program, it was recognized early that the ideal software development cycle (Figure 3) could not be strictly applied and still satisfy the objectives. However, an implementation approach was devised for STS-1, which met the objectives by applying the ideal cycle to small elements of the overall software package on an iterative basis (Figure 4).

    There are a lot of other good nuggets in there, too, and it reminded me that I seem to recall seeing an interview with Kent Beck where he stated that he got a lot of his ideas from an earlier source.

  41. @Shenpen
    > so I may be talking out of my butt, but is testing really the best approach to such problems, instead of trying to prevent them from happening?

    Quality software assurance is a multi-layered thing. Unit testing is only one of the layers, and it serves two distinct purposes:

    1. To exercise the code while being created to verify the programmer’s expectations
    2. To regression test the code so that subsequent changes in the software don’t break existing functionality already known to work.

    What goes hand in hand with unit testing is code coverage analysis, which is to say a measure of who many code paths the unit tests actually exercise. Unit testing is particularly important in agile style development because it is a prerequisite for successful refactoring, something that is absolutely central to the whole concept of agile programming.

    BTW, good unit testing is very dependent on the underlying language. In some languages it is much harder, maybe even two orders of magnitude harder, to create unit tests than in others. Some languages and frameworks are specifically designed to support unit testing, and testability is actually an important measure (in my opinion) of software quality. For example, it is vastly easier to write unit tests in Python, C# and AngularJS than it is in C, C++ and jQuery.

    Unit testing is not adequate to quality software, there are lots of other pieces of the puzzle, but it is perhaps one of the most neglected tools, especially when, as I have argued earlier the cost of adding unit tests is negative.

    (Up to a point of course. If you want to see exemplary unit testing, you should check out what they do in SQLite. It is absolutely amazing the level of testing they do on that product.)

  42. @Jessica Boxer:
    Customisability is not a problem to non-technical users so long as there are sensible defaults.
    (Linux install could probably do with a ‘Noob Install’ that just asks the user to name the computer and set up the first user, and does the default/reccomended action without prompts elsewhere.)

  43. > Customisability is not a problem to non-technical users so long as there are sensible defaults.

    And as long as configuration settings are about choosing between reasonable alternatives (e.g. choosing which printer is the default), as opposed to entering the special magic codes needed to get things to work at all (e.g. getting the system to recognize that the printers exist).

  44. @Patrick Maupin
    > it really puzzles me why you have such a problem with Python.

    It is for the very reason we are discussing. Python’s type system is very much of the Postel model. My bottom line problem with Python is that I think explicitly stated types provide exactly the benefit I am talking too. Explicit type systems are brittle, they break at compile time rather than at run time. And that is all round a better way to do it, notwithstanding the fact that they are somewhat more verbose and less flexible.

    However, if you want to challenge me on the particulars I’ll have to take a pass. I made a serious attempt to like Python several years ago by writing some Web app with Python and Django. I found it very frustrating, not as bad as Javascript, but the same type of frustration as one feels with JS. I spent probably six months with my head in it. However it is long enough ago that I can’t really give any specific examples.

    BTW, it is utterly beyond my comprehension that people are actually choosing to write their server side code in Javascript. I really cannot think of a single reason why someone would choose to do that.

  45. I really cannot think of a single reason why someone would choose to do that.

    Golden-Hammer Syndrome. The people I see raving about Node are mostly cowboy types who’ve used only PHP or *maybe* Ruby on Rails on the server side and see no change in the type theory but reduction down to one vaguely-typed language.

    This is one of the reasons I’m really coming to like Groovy; it has about as much runtime type flexibility as Ruby or JavaScript, but you can turn on either compile-time type analysis or fully statically-typed compilation, allowing you to explicitly choose how rigorous it makes sense to make a particular section of a program.

  46. As it happens, Eric, you and I discussed this subject long ago, in much more philosophical terms via email – back then I advocated that more tracers (as open source provides – “more eyes”) meant that someone would likely get a lucky lottery ticket and have a short trace; so they’d find the bug (quickly, before giving up.) Advantage open source.

    I might suggest that in cases like the one you describe, you might actually want to *start* using uninitialized memory, or better randomly initialized memory in order to make the buffer overflow or loose pointer more visible; by making it more likely to be destructive, so the bug becomes more frequent and just maybe, the trace shorter.

    Back when I was a real programmer who could rewrite my bios twice in a week with ease (on a bad week); I would salt an incredible number of asserts into my most difficult, closest-to-the-metal programs so that I could almost always get a short trace. Expected variable ranges, and relationships between variable values, that sort of thing. I also compiled and quick-tested with enormous frequency. Two-thirds of my debugging instances were errors in the asserts (false warning lights) that were usually quickly fixed, but my debugging time was still much reduced overall, plus few bugs went a very long time without detection. I’d put a list of asserts just after entry, and just before the exit, of every function. An exhaustive list for key or bottleneck functions that were frequently visited.

    Does that sound like using training wheels? The state of software suggests we could all use a few more training wheels, frankly. None of us are really ready for the open road.

    This curious practice had a few bonuses: It’s a form of documentation. Active documentation, and I think “active documentation” is in our future, bigtime. When you go back to maintain that code one day, you can test your understanding of the code by seeing whether you’d have written those particular asserts now, and whether you understand why they’re true – before you start twitching that old code around. If you do something unusual to the code without realizing how unusual it is, an assert is likely to complain to you about that – which is a very active form of documentation, indeed.

    It also educated me about my code as I wrote the asserts. Fixing false warning lights frequently corrected my insufficiently-sophisticated understanding of what I’d written, before those misconceptions could lead to subtle tragedies such as phase-of-the-moon errors.

    I look forward to Nim letting us leverage and modulate this sort of approach to the max.

  47. Jessica Boxer et al: “Unit testing is not adequate to quality software, there are lots of other pieces of the puzzle, but it is perhaps one of the most neglected tools, especially when, as I have argued earlier the cost of adding unit tests is negative.”

    Let’s not be too naive. It’s a managerial economy. It’s not in the (esp middle) manager’s interest to find more bugs that aren’t obvious. It’s in their interest to take eventually-catastrophic risks and be in another job when the company crashes, a la Wall Street crap debentures and reinsurance offerings, etc, etc that caused the crash/robbery of 2007/ 2008. Take away the financial rewards or most of them, with open source and as ESR relates, suddenly testing is much better.

Leave a Reply to Daniel Franke Cancel reply

Your email address will not be published. Required fields are marked *