Embedded Space

Embedded systems sprawl (I hesitate to use the word "lie") at the border of engineering approximations and exact counts. Because embedded systems use seemingly ordinary software to manipulate real-world quantities, their programmers often think of the world as perfectly digital, with the hardware folks having taken care of the approximations.

Suppose, for example, your job is to count and record the number of holes punched at specific spots in a succession of paper sheets. What could be easier?

Getting Punchy

Punched cards date back to Joseph-Marie Jacquard's loom of 1801, wherein a belt of metal cards controlled the weaving pattern. Within 11 years, France recorded 11,000 Jacquard Looms in operation, relegated manual weaving to an artsy-craftsy occupation, and slap-shifted the Industrial Revolution into high gear.

Both Charles Babbage and Herman Hollerith took note of Jacquard's punched cards: Babbage in his Difference Engine and Hollerith in the tabulating machines he invented for the 1890 U.S. Census. Those two branches later rejoined in Hollerith's Tabulating Machine Company, better known after it morphed into the International Business Machines Corporation.

Hollerith used thick, stiff, paper cards and electrical contacts to sense the holes. The U.S. Census Bureau punched one card per person, detailing age, race, occupation, and other numeric quantities. As cards zipped through the tabulating machines, electrical counters recorded the number of matches for specific criteria. Later, more elaborate machines allowed sorting and logical operations based on each card's data fields.

From the beginning, trained operators tapping carefully designed machinery formed the foundation of punched-card processing. If a precision punch and die can poke a hole in heavy steel plates, punching paper ought to be straightforward.

As we saw last year in Florida, that's not always the case.

Going Binary

Because I'm writing before the final election analyses are done, the problem seems to have been an interaction between machine design, user training (or lack thereof), perhaps a bit of wear and tear, and maybe even some down-and-dirty political fraud. The end result: Cards weren't punched according to the spec required for accurate reading.

Arguments went both directions: Either a vote recorded on a mispunched card is invalid on the face of it and should not be counted or election observers must determine what the voter really meant by examining mispunched and misread cards.

Even without delving too deeply into politics and legalities, you should get the puckery sensation that informs you of very slippery footing. Assuming that voting machines can and do correctly tabulate valid punched cards, how should the system handle invalid cards?

A vote may be an inherently binary choice, but the process of voting, as performed in Florida and across much of the U.S., certainly isn't. Worse, the solution isn't an engineering problem.

Checking the Balances

A voting machine forms only one part of the entire election, even if it's the only part most voters see. Results from each machine combine with others in a hierarchy that reaches to the state and national levels, finally determining who won. Accuracy of the final totals depends completely on each step along the way: Any errors in transmitting or recording the numbers will fatally corrupt the results.

At each stage of the election process, observers from (at least) the major parties (are supposed to) have access to all the voting materials, perform inspections to verify that voting machines work correctly, and certify that votes have been accurately counted and reported. By allowing open access to the process, the voting system reduces the opportunity for fraud while preserving the privacy and anonymity of each individual vote.

That process dates back to the days of hand-printed ballots dropped into boxes, with checks-and-balances appropriate to those times. It has evolved to reflect voting machines, both mechanical and electronic, but certainly isn't keeping up with the times. In fact, it's not clear to me that the current system has any meaningful checks and balances at all.

A mechanical voting machine consists of levers on the front panel and digital (mechanical, not electronic!) counters on the back, all interconnected by rods and powered by the same handle that closes and opens a privacy curtain. Election inspectors verify that the dials read zero at the beginning of the election, then record the totals at the end. In principle, the counters accurately record each vote cast during the day.

In practice, all manner of trickery can affect the final tally: Gears can be shaved to skip counts, levers ever-so-slightly bent, and so forth and so on. Our election inspectors are volunteers, few have engineering or forensic training, and anyway, mechanical voting machines aren't torn down for a complete check just before the election. As a result, the inspectors can only verify that the machine seems to be in working order and reads all zeros at the start, and record the indicated numbers at the finish.

All-electronic voting machines, called "Direct-Recording Electronic Voting Machines" in the jargon, are worse: There's nothing to inspect and no way to verify that they operate correctly. Self-test routines can be faked, checksums made up, and any desired validation results produced on the fly. And there's no possibility of a recount independent of the machine, simply because the votes exist only as insubstantial electronic blips stored within the machine.

Opportunities for trickery don't end with the voting machine and, I fear, provide the most opportunity for clandestine manipulation. Because the voting results become progressively more concentrated as they go from precinct to county to state to nation, it should become more difficult to gain access to the computers doing the tallying, the software in those machines should be more open to inspection, and the process should have some verification and cross-checking.

Nothing, it seems, could be further from the truth.

Design Criteria

Unless I miss my guess, a few of you folks have recently been charged with designing a new all-electronic voting system. No paper, no levers, no recounts, no messy analog conversions, no double-punch ambiguity, full digital automation all the way.

What a great opportunity!

Projects always start with a list of specifications, a description of what's to be done. For elections, there's an additional complication: Some rather arcane laws define much of what one can and cannot do. Worse, the laws vary by state, county, and district in no discernible pattern; each precinct may use a different ballot arrangement.

Now, suppose an election held using your machine indicates 15,000 Republicrat votes and 0 (that's zero, as in none at all) for the Democrans. That's a possible but unlikely outcome. How will you demonstrate that your machine correctly counted each voter's choice?

You could record every vote, but because voting must be anonymous, you cannot store the records in sequence, let alone with a name or ID. And, if not stored in order and not on paper (or its physical equivalent), how will you demonstrate your machine functioned correctly?

So you decide your new voting machine will emit a ticket showing a voter's ballot? You'll soon find some jurisdictions that prohibit giving a voter a record, specifically to prevent turning it in as a receipt for voting as instructed and getting paid off.

Pretty much by training, engineers and programmers become used to working with natural laws. In a field with tangled legalisms and the potential for outright fraud, engineers may not have the mindset required for a successful design. If, indeed, we can define "success" with any precision.

Not Fade Away

A worse problem, one that seems to be glossed over when we talk about embedded systems, lies in wait. Figures 1 and 2 show a mechanical voting machine built about 20 years ago. Although it now sits in the lobby of the Dutchess County, New York, Board of Elections, it still works fine.

Set your Wayback Machine for 1980 and look around at then-current computer technology. Hulking personal computers use the S-100 bus and linear voltage regulators, the IBM Personal Computer remains in top-secret development, and you can't buy a color SVGA LCD panel to save your life.

Today, repairing 1980s-vintage electronic equipment requires a hobbyist's dedication and a scrounger's stockpile. Even the skilled machinists required to build and maintain the mechanical voting systems are in short supply; talented kids of the '80s discovered that working with their hands didn't pay nearly as well as programming and engineering (let alone high finance).

Fast-forward 40 years and ask what's the likelihood that anything you design today will be useful, functional, or repairable in 2020? Any computing hardware, doomed by Moore's Law, will become obsolete before it's deployed in large numbers.

One company making electronic voting machines proudly points out that it uses Z80 CPUs, which have been in continuous production since the '80s. Yes, indeed, but if either Zilog or that company goes out of business, election districts across the land wind up in deep trouble.

But, wait, it gets even worse.

Transcendent Attack

The embedded world hasn't had, to my knowledge, much trouble with concerted attacks of the kind that plague the PC world. There simply isn't that much payback for disabling all the elevators using a given embedded controller.

If we establish a single, national standard for electronic voting machines, well, that might provide some motive!

It doesn't require too much imagination to recognize a few groups who might want to influence the outcome of a U.S. Presidential election. Even if those groups don't get along particularly well with each other, spiking a national election might serve as a unifying cause.

If an attacker can deploy the resources of a small country (let alone a kleptocracy), standardized voting machines across the U.S. will be easy pickings. As we well know, straightforward virus attacks using built-in system features propagate remarkably rapidly through the monoculture of Windows machines.

Voting machines spend much of their time under lock and key, powered down between elections. Around here, however, several local officials have recently been prosecuted on corruption charges involving payoffs of perhaps a few tens of kilobucks; while they weren't election officials, there's a clear message.

So much for opportunity.

Embedded systems designers will simplify the method of the crime, too. Machines will certainly feature downloadable updates, revisable features, and online maintenance. Heck, they'll probably even be web enabled. On the hardware side, is there a JTAG connector on the system board? A ROM socket? Flash memory? A serial debugging port?

It should be obvious that displaying one value on an LCD, printing a second on paper, transmitting a third to the central tally, and creating an audit trail with a fourth isn't all that difficult. You cannot verify data using the same circuitry that stores it, digital signatures notwithstanding! If an attacker can replace the program, all things are possible and all checks will balance.

Assume that an attacker has four or eight or twelve years, an unlimited budget, world-class experts on call, sample systems to experiment with, and all the documentation and source code. Think they can pull off an attack? Well, do unfunded groups with low resources bring down nominally high-security systems even today?

Even better, nobody will ever know. The attackers need not force a win by 100.0 percent of the vote: Just a few points one way or the other, not a landslide, and no one will ever be the wiser. Those printed audit records (or whatever safeguards you design into your voting machine) will never be consulted, as there won't be any reason to verify the "obviously correct" results.

Or maybe everybody will know. Suppose every single voting machine in the U.S. crashes at high noon (local or UTC, take your pick) on election day? Or the Webbish vote collection system seizes up under a Denial of Service attack? Or the final tally shows Mickey Mouse as the clear winner?

Need I go on?

Remember, the attackers have an unlimited budget, unlimited expertise, all the source code, complete physical access for years, and may choose any of several desirable (to them) outcomes. Tell me how you'd secure those systems, all the way from the voter's fingertips to the national media.

I don't believe those safeguards will work, not one little bit. Be very afraid.

Reentry Checklist

I probably shouldn't mention the time I poured a box of punchies through the fan blowing over our dorm's shower stalls while my roomie was lathering up. Shower rooms resonate wonderfully to the roar of an enraged human male — but it's hard to chase a perp across the quad when you're clad solely with chad.

Direct-recording electronic voting machines and the controversies surrounding them are not new, despite the massive attention recently paid to them. The Federal Election Commission (http://www.fec.gov/) is root for national voting information, including a list of pointers to companies who manufacture machines. Douglas Jones provides provocative comments and useful links at http://www.cs.uiowa.edu/~jones/voting/index.html. You'll find considerable fuel for the vote-fraud inferno at http://www.votescam.com/ and an excellent discussion of the reasons to not go electronic at http://www.notablesoftware.com/evote.html.

Regular perusal of the moderated comp.risks newsgroup (archived at http://catless.ncl.ac.uk/Risks) will alert you to the foibles of our modern world, while scaring you witless at the same time. You should also subscribe to Bruce Schneier's "Crypto-Gram" (http://www.counterpane.com/) to keep up with security matters.

To begin thinking about failure in a positive light, read Henry Petroski's To Engineer Is Human: The Role of Failure in Successful Design (St. Martin's Press, 1985, ISBN 0-312-80680-9); it's a classic. Follow that with his Design Paradigms: Case Histories of Error and Judgement in Engineering (Cambridge, 1994, ISBN 0-521-46108-1 hardbound, ISBN 0-521-46649-0 softbound) and you'll look at the world in a different light.

The December 13, 2000 Supreme Court ruling on the Florida votes (start at http://www.supremecourtus.gov/ and look under Opinions) should give you some idea of the nontechnical ramifications of your projects. Imagine if your embedded project were subjected to this level of scrutiny. One day, it could happen — design accordingly!

DDJ