Why Voting Machines Can't Add Up

Ed Felten is continuing his excellent work exposing the broken state of electronic voting machines. Many people are wondering how such software can have been allowed out by its developers. The discrepancies don't (at the moment) seem to be a result of fraud, just very buggy software.

Voting machines are obviously important, so their development is regulated. I've never worked in the voting machine industry, but I have worked in another kind of federally regulated software: medical devices. So I know how regulated software projects work, and how they don't.

The fundamental problem underlying this is that nobody in the world actually knows how to write software that reliably does what you want. There are quite a lot of people who can write such software, but if you ask them how its done they basically waffle. Most of them agree on a list of steps to take, starting with writing down exactly what the software is supposed to do. Various attempts have been made to codify this list, and they all look pretty similar. The voting machine standards are just another variation on this theme.

However this is all cargo-cult engineering. We know that the people who can summon up the magic cargo planes do it by putting things over their ears and saying magic words, but it doesn't follow that if we put things on our ears and say the same magic words the cargo will appear. So it is with software engineering. You can write Requirements Documents and Class Diagrams and Test Scenario Documents and Test Execution Reports until you run out of paper, but it won't make any difference if you don't have the Quality Without a Name.

Imagine you are managing a development project to build a voting machine. Your mission is to get the thing on the market. You have been given a bunch of programmers, half a human factors person and a quarter of an industrial designer. The time available isn't long enough, but you know its no use complaining about that because its not your boss's fault, or even the CEO's fault. Its the fault of the people at Big Competitor who are planning to release their product just in time to tie up the whole market, so if you don't deliver the product at the same time then its not going to matter who's fault it was, the whole division is going to get laid off anyway. You could get some more people if really wanted, but you know that more people aren't actually going to speed things up.

The Quality Department have downloaded the voting machine regulations and someone has been going through them and writing down a list of the things they say you have to do and the order they have to be done in. This is very good. In fact you send the Head of QA a little note saying how helpful his minion has been to your project, because now you have something to aim at. Project Management is mostly a matter of getting your hoops lined up so that you and your minions can jump through them as quickly as possible, and the QA minion has done the regulatory hoops for you. The regulations boil down to a list of documents that have to be shown to the inspectors (who you are going to hire, but thats another story). Each document has a list of things it must contain, and some of those things have to be traceable to other things. All you need to do now is start allocating people to things on the list and getting them ticked off. The list is long, but you have one big advantage: there is nothing to say how good any of these documents have to be. They don't have to be good, they just have to exist.

One of these documents is called "source code". Of course that one does have some quality requirements on it: its got to pass a bunch of tests. But the tests themselves don't have any quality requirements; like everything else they just have to exist. And passing the tests is the only quality requirement on the code. Once the independent laboratory you hired has run the tests and said "pass" you are over the finishing line and you can start selling these things.

This means that you have a very strong motivation to keep the testing to the minimum you can get away with. The regulations say you have to have a test for each item in the original requirements document, and this test has to be run once. If your software fails a test then you get to fix it, and if the fix was small enough you can get away without repeating all the other tests as well. During this whole time your eyes are fixed on the finishing line: the objective is to get this thing over the line. What happens to it after that is someone else's problem.

When you look at these machines from a project manager's point of view you start to see how they got to be so unreliable. "Quality Assurance" is primarily a matter of making sure you get all the items in the regulations ticked off; it has nothing at all to do with the original meaning of the word "quality". Ironically the regulations may actually do more harm than good because they divert energy from real quality onto generating the required inches of documentation.

Over the years I've spent a lot of time trying to figure out how to fix this problem, and I still don't have an answer. Abolishing private companies is a cure worse than the disease, and it won't cure the disease anyway because it won't abolish projects and the need to manage them. Software Engineering has a bad case of Quality Without A Name, and there is no prospect of it getting better soon.

However in the limited domain of voting machines I believe the best cure is sunlight: we may not be able to define quality in software, but we know it when we see it. The source code for voting machines must be published. The manufacturers will scream and shout about their precious IPR and trade secrets. This is nonsense. Any voting machine must have a well defined version of someone's software running, so any illegal copying will generate a cast-iron audit trail back to the perpetrator. And there are no real trade secrets in voting machines: counting votes is not, when it comes down to it, a particularly complicated problem. The voting machine manufacturers will make just as much money as they do now. In fact they'd probably make more because if the machines were trustworthy then people would learn to trust them. However the first vendor to start publishing their source code will be at a disadvantage because everyone else can pinch bits of it with very little risk of detection (and if they get caught they can just blame a rogue programmer). So the regulations on voting machines should be changed to require the publication of the code (and other design documentation too, while we are about it). That will create a real requirement for quality source code. Until then we are stuck with the current mess.

Why Haskell is Good for Embedded Domain Specific Languages

Domain Specific Languages (DSLs) are attracting some attention these days. They have always been around, of course: Emacs Lisp is a DSL, as are the various dialects of Visual Basic embedded in MS Office applications. And of course Unix hands know YACC (now Bison) and Lex (now Flex).

However creating a full-blown language is a lot of work: you have to write a parser, code generator / interpreter and possibly a debugger, not to mention all the routine stuff that every language needs like variables, control structures and arithmetic types. An embedded DSL (eDSL) is basically a short cut if you can't afford to do that. Instead you write the domain-specific bits as a library in some more general purpose "host" language. The uncharitable might say that "eDSL" is just another name for "library module", and its true there is no formal dividing line. But in a well designed eDSL anything you might say in domain terms can be directly translated into code, and a domain expert (i.e. a non-programmer) can read the code and understand what it means in domain terms. With a bit of practice they can even write some code in it.

This paper describes an eDSL for financial contracts built in Eiffel which worked exactly that way. It doesn't talk about "domain specific language" because the term hadn't been invented back then, but the software engineers defined classes for different types of contracts that the financial analysts could plug together to create pricing models. Its interesting to compare it with this paper about doing the same thing in Haskell.

But eDSLs have problems. The resulting programs are often hard to debug because a bug in the application logic has to be debugged at the level of the host language; the debugger exposes all the private data structures, making it hard for application programmers to connect what they see on the screen with the program logic. The structure of the host language also shows through, requiring application programmers to avoid using the eDSL functions with certain constructs in the host language.

This is where Haskell comes in. Haskell has three closely related advantages over other languages:

1. Monads. The biggest way that a host language messes up an eDSL is by imposing a flow of control model. For example, a top-down parser library is effectively an eDSL for parsing. Such a library can be written in just about any language. But if you want to implement backtracking then its up to the application programmer to make sure that any side effects in the abandoned parse are undone, because most host languages do not have backtracking built in (and even Prolog doesn't undo "assert" or "retract" when it backtracks). But the Parsec library in Haskell limits side effects to a single user-defined state type, and can therefore guarantee to unwind all side effects. More generally, a monad defines a model for flow of control and the propagation of side effects from one step to the next. Because Haskell lets you define your own monad, this frees the eDSL developer from the model that all impure languages have built in. The ultimate expression of this power is the Continuation monad, which allows you to define any control structure you can imagine.
   
2. Laziness. Haskell programmers can define infinite (or merely very large) data structures because at at any given point in the execution only the fragment being processed will actually be held in memory. This also frees up the eDSL developer from having to worry about the space required by the evaluation model. (update: this isn't actually true. As several people have pointed out, while laziness can turn O(n) space into O(1), it can also turn O(1) into O(n). So the developers do have to worry about memory, but lazy evaluation does give them more options for dealing with it.)
   
3. The type system allows very sophisticated constraints to be placed on the use of eDSL components and their relationships with other parts of the language. The Parsec library mentioned above is a simple example. All the library functions return something of type "Parser foo", so an action from any other monad (like an IO action that prints something out) is prohibited by the type system. Hence when the parser backtracks it only has to unwind its internal state, and not the rest of the universe.

There are other programming languages that are good for writing eDSLs, of course. Lisp and Scheme have callCC and macros, which together can cover a lot of the same ground. Paul Graham's famous "Beating the Averages" paper talks about using lots of macros, and together with his patent for continuation-based web serving it is pretty clear that what he and Robert Morris actually created was an eDSL for web applications, hosted in Lisp.

But I still think that Haskell has the edge. I'm aware of the Holy War between static and dynamic type systems, but if I you put a Haskell eDSL in front of a domain expert then you only have to explain a compiler type mismatch message that points to the offending line. This is much easier to grasp than some strange behaviour at run time, especially if you have to explain how the evaluation model of your eDSL is mapped down to the host language. Non-programmers are not used to inferring dynamic behaviour from a static description, so anything that helps them out at compile time has to be a Good Thing. And its pretty useful for experienced coders too.

(Update: I should point out that monads can be done in any language with lambdas and closures, and this is pretty cool. But only in Haskell are they really a native idiom)

Is Comcast's Packet Spoofing a Federal Crime?

The EFF has gathered evidence showing that Comcast is deliberately disrupting P2P traffic by spoofing RST packets to appear to come from the other end of the connection. See the EFF report for the technical details.

The US Criminal Code Title 18 Part 1 Title 47 Section 1030 covers "Fraud and Related Activity In Connection With Computers". I'm not a lawyer, but here is my understanding of the relevant bits of the statute (quotes from the statute are in italics):

Jursidiction: a "Protected Computer" is defined, amongst other things, as any computer "which is used in interstate or foreign commerce or communication, including a computer located outside the United States that is used in a manner that affects interstate or foreign commerce or communication of the United States". In other words if your computer is on the Internet, even if its outside the US, then its a Protected Computer. That includes anything connected via Comcast, and anything that talks to any computer connected via Comcast.

Offence: there are two things to prove here:

1. That someone employed by Comcast "knowingly causes the transmission of a program, information, code, or command, and as a result of such conduct, intentionally causes damage without authorization, to a protected computer". Damage is defined as "any impairment to the integrity or availability of data, a program, a system, or information". A spoof RST packet instructs the receiving computer to drop a TCP connection, so it is a command that impairs the availability of data. I have no direct evidence that these packets were sent knowingly, but I find it difficult to imagine a scenario in which they were sent by accident.
2. That this action caused "loss to 1 or more persons during any 1-year period [...] aggregating at least $5,000 in value". "Loss" is defined as "any reasonable cost to any victim, including the cost of responding to an offense, conducting a damage assessment, and restoring the data, program, system, or information to its condition prior to the offense, and any revenue lost, cost incurred, or other consequential damages incurred because of interruption of service". This is a bit tricky, but people do value their time. $10 per hour is a pretty low wage, and many professionals charge many times that. If failed P2P connections have cost 500 Comcast users 1 hour each in wasted time then this threshold has been reached. You might also be able to make a case purely on the cost of running a computer and keeping it connected via Comcast. The professional IT people who have taken the time to run tests with packet sniffers could certainly count their time at a professional rate as "responding to an offence" and "conducting a damage assessment". There is also some evidence that Comcast inadvertently disrupted other protocols, including Lotus Notes and Windows Remote Desktop. These are used commercially and their disruption would have real financial impact. So while a detailed accounting remains to be done, it certainly looks likely that the $5,000 threshold has been reached.

Penalty: "a fine under this title or imprisonment for not more than 5 years, or both, [if] the offense was committed for purposes of commercial advantage or private financial gain". Comcast's attempts to block P2P protocols are prompted by their desire to keep costs down while seeming to offer an unrestricted service. That counts as "commercial advantage".

So it certainly looks like a Section 1030 offense has been committed that could see someone put in the pen for five years. Any Comcast customers want to call the FBI?

Disruptive Innovation and the Walmart Linux PC

The Everex TC2502 is being sold by Walmart for $200 (no monitor included), assuming it hasn't sold out a second time. Part of the reason its so cheap is that it runs Linux and OpenOffice.org instead of Windows and MS Office. The first run sold out within days, which is a strong clue that it was a lot more popular than expected. This doesn't mean popular in an absolute sense, just more than Walmart and Everex expected when they decided how many to get in stock. But its the relative popularity that counts: Walmart and Everex produced this box because they calculated they would turn a profit on whatever number they expected to sell. So the fact that they sold out fast means two things:

1. A bigger profit than expected, which is nice for Walmart and Everex.
   
2. Cheap Linux-based PCs have a market niche big enough to make them worth-while. Other manufacturers will have taken note. Expect imitators.

Anyone who has read The Innovator's Dilemma will recognise this pattern: a market incumbent listens to its best (i.e. richest and most profitable) customers, and in consequence makes its products bigger, better and progressively more expensive. The incumbent also finds it unprofitable to compete with narrow niche offerings at the bottom, because they are low quality and aimed at poor customers that can't afford the market leader. So it forgoes the bottom end of the market and concentrates on its nice profitable high-end models. However over time the bottom-end offerings improve, and so become a cost-effective choice for more and more customers. Eventually this starts to make serious inroads into the sales of the incumbent. But by then its too late. The incumbent must choose between cutting prices to compete with the newcomer or else continue to see its market share erode. Neither option will bring back the glory days, and historically many such companies went out of business surprisingly fast.

I'm quite sure that Bill Gates and Steve Ballmer have read The Innovator's Dilemma and seen this coming. There is a bit of MBA strategy theory that sums up their position nicely. Plot their product lines on a chart with two axes; market share and growth potential. The high-share-low-growth lines are "cash cows": they should be milked, and the profits put into high-growth lines. Eventually all cash-cows turn into dogs (low-share-low-growth) and these should be killed off. You just have to hope that by then you have some new cash cows to replace them.

Microsoft has two cash-cows (Windows and Office), and Microsoft has indeed been milking them for all they are worth. The money has been ploughed into a bunch of ventures over the years, but none of them look like becoming future cash cows.

Now we may be entering the final act. People have talked about Linux as a disruptive technology for the last decade, and for server operating systems it definitely has been. Its effectively killed off proprietary Unix, and put a serious dent in Windows. Microsoft continues to fight a rearguard action in this market, but its reliance on big corporate customers is becoming more and more obvious as it tries to separate its premium products (which rich big companies will still reliably pay for) from its lower end offerings. But on the desktop Windows and Office have continued to reign supreme.

Now for the first time in a decade a competing office suite is starting to nibble at the toes of the incumbent. Its not going to make a dent in Microsoft's quarterly numbers just yet, but the future can only go one way. Microsoft sells Windows and Office to PC builders for less than the retail prices, but it cannot let Windows and Office go onto a PC that sells for $200 because they would be giving it away: it would actually be cheaper to buy the PC with the software than to buy the software alone at retail prices. But as more people find that bottom-end hardware with Linux and OpenOffice.org makes a perfectly useful home PC at a fraction of the cost of the Microsoft alternative, so the market will grow. Microsoft may try to segment the market by offering a cut-down version of MS Office (maybe Word with a 20 page limit), but they are competing with a fully featured product. No matter what they do to Windows and Office, Linux and OpenOffice.org are going to look like better value to anyone who is on a tight budget.

Initially it will just be cash-strapped consumers who buy these boxes (students in particular are going to love them). But this is a one-way street. Every consumer who buys one of these boxes is a consumer who is never going to buy a Microsoft box again, even when they get rich. Why pay more to learn a different set of software? And they'll tell their friends about how well it works too. The flow of money into multiple vendors coffers will stimulate investment and competition. All the vendors will want a slicker, more fully featured Linux offering with a bigger repository of instantly downloadable free (in both senses) software. The resulting competition will be downright Darwinian, and the offerings are going to get very good very fast. Everybody is going to race up-market as fast as possible because thats where the real money is. At the moment that money is being taken by Microsoft, but not for long.

Add to this the famous network effects. Part of the reason MS Office dominates is that you need it to exchange documents with everyone else. But if that stops being true then another good reason to pay for MS Office disappears as well.

So I predict that Microsoft is going to be in serious trouble, probably within the next few years. Their existing cost base is tuned to making and selling ever bigger and better versions of their cash cows, and there is no way that they can cut this back to compete with Linux and OpenOffice.org on a cost basis. But if they can't compete then their cash cows are going to turn into dogs before they can be replaced. So Microsoft will be left with two dogs, a bunch of ventures that require investment, and no cash flow. Sure they have big cash reserves they can burn through, but thats not going to be enough even if their investors let them do it.

Its the disks that are the problem, not losing them

The UK news this week has been full of stories about the loss of 2 disks (presumably CDs or DVDs) containing all 25 million Child Benefit records. For those outside the UK, Child Benefit is several pounds a week paid to the mother of every child (i.e. under 16) in the UK. In most cases it gets paid directly into a nominated bank account.

This is one of the biggest data losses ever, if not the biggest. The government has been at pains to point out that the disks are probably just mislaid, and they don't contain enough data for criminals to actually use. Meanwhile the Opposition has been alleging government incompetence and calling for them to "get a grip". People are being advised to keep an eye on their bank accounts and not use their childrens' names as passwords.

All this misses the point. The problem was not that a couple of disks got lost, it is that a comparatively junior person could burn the entire database to a couple of disks, apparently on his/her own initiative, and without further controls. There was a time when copying 25 million records would have required substantial resources, such as an overnight run on the mainframe and a boxful of tapes. The sheer volume of data made it physically difficult to copy, or to lose. However Moore's Law has turned that big, slow, expensive job into a few minutes with a CD burner. If those two disks were CDs then the whole lot would also fit on a £10 thumb drive, or even a cell phone. The story referenced above suggests that in the past the National Audit Office (the place where the disks in question never arrived) have made their own copies and sent them to outside auditors. None of the commentators seem to have realised that the most probably route for the data to get into the hands of criminals is not the loss of an authorised copy but the creation and distribution of unauthorised copies.

There are supposed to be procedures in place, but its no surprise that they are not being followed; when was the last time you reached for the Company Procedure Manual to check on the detailed procedure for some simple action? Its also too easy to blame the middle manager who decided that a written procedure was better than implementing a software access control system. Given a choice between implementing costly access controls and writing a procedure for making copies, which would you chose? Now try it again, but imagine that your annual evaluation is going to suffer if you "waste" money doing something that has no positive benefit on your departmental targets.

I would like to think that this incident will be a wake-up call for the civil service to revamp its data control procedures. However I doubt it. A scapegoat has already fallen on his sword (to mix the commonest metaphors). The government is keen to show it is doing something, but mostly to counter the opposition claims of incompetence. And the opposition is more interested in a ministerial scalp than in actually pushing for effective action. What is really needed is an audit of all databases containing UK citizen personal information, followed by a study into the necessary forms of access and the implementation of software-based authorization and logging mechanisms. But nobody in authority seems to be thinking along those lines.

The sad thing is that the Ministry of Defence has had hundreds of years experience in dealing with sensitive and secret data, and they have become quite good at it. Perhaps they should give the rest of the government some lessons.

The Rise of Modern Morality

Every so often I read a letter in a newspaper or some other forum about "the decline of modern morality", in which the writer laments the failing moral standards of private and public life. I'm old enough to have been reading these articles for two or three decades now, and I've seen some samples of the same genre from past times. Elvis Presley caused a moral panic in 1956 by gyrating his hips on stage, and this was cited by commentators at the time as corrupting the morals of young people. Much has been written about the sociology of moral panics and I don't propose to repeat it here. Instead I want to argue that, far from declining, modern morality is actually superior to moralities of the past (and I use the plural deliberately).

• In 1970 in the UK it was not only legal but widely accepted practice to pay a woman less than a man for doing the same job. Women who wanted a life outside of home making and child rearing were seen as aberrant, and often regarded with scorn.
• In 1960 in America many parts of the country segregated public facilities by race, with black people consistently and blatantly short-changed. This invidious system was widely supported by prominent politicians and churchmen.
• Even into the 1970s in Australia aborigine children were forcibly removed from their parents and placed in institutions where they were denied proper education and were terribly vulnerable to physical and sexual abuse. Again, this programme was considered perfectly proper and moral by the standards of the time.
• There was a standing assumption for many years that unmarried mothers should immediately give up their children for adoption. In Ireland they were also incarcerated in the "Magdalene Laundries". Other countries had similar systems. Strangely, the fathers were left to go free.
  
• For most of the 20th century, when it became necessary to remove children from their parents because of neglect or abuse little thought was given to keeping siblings together: they would be split up to suit the convenience of potential adopters or fosterers.
• Until recent years in most Western countries, homosexuals were persecuted and discriminated against, both by the law and by society at large.
• Until the 90s in the UK drink-driving was considered a minor peccadillo. Drivers convicted of the offence were more likely to encounter sympathy at the unfair attitude of the legal system than censure at their reckless disregard for the safety of others.
  

Not all of these evils are completely gone, but in all cases there has been a substantial moral shift. I know that some readers will look at some of this list, especially the tolerance of homosexuality, and regard this as evidence of moral decay rather than ascent. But this brings up another issue I have with the Cassandras of moral decay: their belief in moral absolutism; that right and wrong are entirely self-evident, and that any deviation stems from lack of morality rather than a genuine disagreement over what the moral course is.

The problem with moral absolutism is that (in its commonest form) it asserts that the perfect moral code has already been revealed and the only possible improvement is in closer adherence to that code. However I describe myself as a Liberal Utilitarian (although I confess I haven't actually read any of Mill's work). Hence I see "the greatest good of the greatest number" as a basic moral principle, while at the same time acknowledging that there may be a lot of disagreement about exactly what that means and how to bring that about. Liberal utilitarianism recognizes no absolute moral imperative apart from the general principle that life, liberty and the pursuit of happiness are good things. However by retaining that anchor it avoids the charge often leveled by the Absolutists that those who question their moral code are "relativists" who believe that any moral code is as good as any other. Liberal utilitarianism examines the impact of moral rules on the real people affected by them. If different rules would have a better outcome then those rules are automatically better. I see the arguments (both past and ongoing) about freedom, equal opportunities and tolerance to be a part of this process, and I see a steady improvement through history. Those who object to the current crop of improvements in morality because they contradict their particular absolutist code would do well to read their history books.

Windows Disaster Recovery with Bacula

A few days ago my wife asked me to look at her computer. Programs were taking ages to respond even to a simple mouse click, or just crashed. And the system box kept making odd clicking noises.

I confirmed her diagnosis of a failing hard drive and shut the computer down. The following lunchtime I drove to the nearest PC World and bought a replacement hard drive. I normally buy mail-order, but we wanted the computer back up as soon as possible. That evening I removed the faulty drive and installed the new one, and I also stuck in some extra RAM while I had the case open. Then it was time to find out if my rather sketchy disaster recovery plan was going to work.

I run Fedora on my own box, and both computers are backed up using Bacula. This is designed for backing up lots of computers to tape drives, but it also supports backup to disk drives. I have two USB drives, keep one plugged in, and swap them every month or so. I use the default Bacula backup schedule of a weekly full dump on both machines and nightly incremental dumps. Most of the Bacula components only run on Unix, but there is also a Windows client installed on my wife's computer (which runs Windows XP SP2). Bacula configuration is rather hairy, but if you have more than one computer its well worth the effort.

The big headache for restoring Windows is the Registry. After previous bad experiences with this horrible blob of data I had made sure the registry was backed up by using regedit to dump the registry contents to a file before each Windows backup, so I hoped it would be OK. There are also problems with other files in C:\Windows that are constantly in use and therefore unwritable during system restore.

The Bacula manual pointed me at Bart PE Builder, which generates a Live CD version of Windows XP. It suggested that you might be able to run Bacula in this environment to get around these problems. Bacula ran fine, but I couldn't get the drivers for the network card to install, so that wouldn't work.

Instead I re-installed Windows XP SP1 from the original CD and ran Bacula there. The restore duly dumped copies of C: and D: in C:/temp/restore/c and /d. (The computer has two partitions because it used to have two drives. My wife got used to having C: and D: drives and various programs had been configured to look for data on D:, so I kept the layout even when it went back to a single drive.). Then I booted under the Bart PE disk, deleted the existing contents of C: (except for /temp) and copied the restored contents into the root directories. Then for the big test: would it reboot?

Well, sort of. The login screen came up, but when I tried to log in the computer hung. I tried rebooting in safe mode, and then in "safe mode with console", which seemed to be the bare minimum. That at least got me a command line, so I ran regedit and imported the registry copy that had been created by the last backup. This warned me that some registry keys could not be modified and claimed that the changes had failed. I rebooted again, and this time found that I could log in, but pretty much all the settings had been forgotten. Office wanted to re-install itself, and every time I started Word it asked for my name and initials twice. This suggested that important parts of the registry were not only still not recovered, but also unwritable.

Windows also decided that it was running on new hardware, and badgered me to activate it. So I did. I then tried logging in as a different user and restoring the registry again in the hope that being a different user would lock different bits of registry. This merely overwrote the new activation data and Windows now point blank refused to let me log in at all until I activated it again. So I tried. This time it told me that I had exceeded my activation limit and would have to phone up for activation. So I did. Windows gave me a 36 digit number and a robot on the other end of the phone line told me to type in the number. Then a polite gentleman named "Fred" with an Indian accent asked me how many computers I had Windows installed on and why I needed to activate it. Then he gave me another 36 digit number to type into Windows to activate it. This worked. But when I logged in Windows wasn't behaving any better.

A bit of Googling reminded me of something I should have remembered much earlier: Windows occasionally checkpoints its critical state, including the Registry, and you can wind it back to a previous known good state using the System Restore function. So I located a checkpoint from before all the trouble started, restored Windows to that state and rebooted.

When I tried to log in I got immediate joy: the desktop background had been restored. This suggested that the registry was now intact. But this restore had also overwritten the registration data, and Windows once again demanded to be activated before I could log in. Back to the phone, this time to a polite woman named June with a much stronger Indian accent who asked me the same questions and gave me yet another 36 digit number to type in. This time everything worked. Disaster recovery was completed.

I'd like to thank the authors of Bacula for their excellent backup program. It saved both of us a lot of heartache. In the past I've found it too easy to neglect backups, and sometimes our computers have gone for months without being backed up. When I got it properly configured (not a trivial task) Bacula made backups automatically with minimal intervention by me (basically, swapping USB drives occasionally). That meant I had a good recent backup to work from.

I'd also like to thank Bart Lagerweij, author of Bart PE. I could probably have managed by booting Knoppix and using its NTFS driver capture facility, but having a native Windows environment made life much easier.