Software: November 2008 Archives


November 2, 2008

Voting machines (DREs and optical scanners) are computers and like any piece of computer equipment, they can fail in a more or less unlimited number of exciting ways. In this post, we focus on non-malicious failures, i.e., those where no attacker is trying to induce failures. It's useful to divide failures into two categories: voter visible and voter invisible. DRE "Vote flipping" is a classic voter visible error. You plan to vote for Jefferson, but when you press the touchscreen, the checkbox appears next to Burr. But remember that your vote is just being recorded on some memory card and just because the screen says "Jefferson" (and the VVPAT says Jefferson, if there is one) doesn't mean the memory card doesn't say "Burr". That's an invisible error.

We can divide visible failures into two additional categories: vote recording errors and system failures. Both of the errors above are recording errors, but the system can also just fail in some more obvious and crude way. For instance, it might not turn on, or might not respond to input or might crash as soon as you try to cast your vote. This shouldn't surprise you; they're computers after all, and crashing is one of the things that computers do best. [The Diebold AV-TSX actually runs Windows CE, so I suppose there is some chance you could get a Blue Screen of Death.]

Most precinct count optical scanners are fairly opaque devices: you insert your ballot and either it accepts it or rejects it. If it detects an error (overvotes or undervotes, depending on programming), it will generally spit the ballot out with some sort of error message. Even within this range, a variety of visible errors are possible. The machine could accept invalid ballots (though this probably won't be noticed unless the voter deliberately does something wrong); it could reject valid ballots. It could also refuse to accept any ballots at all (i.e., not feed them into the scanner) or jam while processing a ballot. Finally, it could just flat out crash or stop working in some other gross way.

By contrast, vote recording errors with opscan systems tend to be silent, as long as they don't turn into an error that the machine is programmed to check. In principle, the optical scanner could display who you voted for and give you an opportunity to accept or reject, but as far as I can tell, none of the popular scanners actually do this. Indeed, the Sequoia Insight display looks to me to be too small to plausibly display your votes, so it's probably not just a matter of software to add a feature like this.

OurVoteLive's database of voting problems shows another, non-computerized, failure mode of opscan systems: bleeding pens.

DREs have a much fancier UI than opscan systems and so can freak out in a whole bunch of fun ways. The one that gets a lot of attention is "vote flipping", but there are actually a number of different ways in which the votes recorded can be inconsistent with the user's intent. A DRE has (at least) the following values:

  • The user's intended selection.
  • The UI gesture the user makes.
  • The option that the UI displays as selected.
  • The option selected in the summary screen.
  • The option selected in the VVPAT (if any).
  • The option recorded on the memory card.
There are plausible paths that could lead to effectively any combination of values here. The only one of these that voters are really likely to notice is that the option that the UI displays as selected doesn't match their intended vote [Everett reports that most users don't check the summary screen]. And of course, if the recording on the memory card is wrong, that's a silent failure. It's worth noting that the "vote flipping" people complain about seems much more likely to be a bug than an attack, since a plausible attacker would do something more subtle.

Of course, there are lots of kinds of system failures. Pretty much anything you've ever seen on your desktop computer can show up on a DRE. The computer can lock up, skip races on the ballot, crash, etc. One of the big failure modes seems to be the VVPAT printers: when I took Santa Clara county voter training they told us we would have three printers for our one lonely DRE, just in case some broke down.

It's worth mentioning that DRE breakdowns tend to be more serious in terms of impact on voting: if a precinct count scanner breaks down in an obvious way, you just move to paper ballots in a box and scan them later (though some failures, like preferential rejection of votes for certain candidates, may have more serious effects). By contrast, if the DREs break down, people can't vote and if you don't have enough emergency paper ballots on hand, it can actually stop people from voting, or at least create incredibly long lines if just some of them are broken.

Back Office Failures
There are also plenty of failures that can happen after the polls close, either at the precincts or in the back office. For instance, the memory cards used to carry the results can be corrupted. Most of these are recoverable at some level, since the machines print out paper receipts and of course you can recount the paper ballots and the VVPAT (if any). The tabulation software at election central can screw up as well, but that's independently checkable from the precinct tallies.

In addition, the central count scanners can fail in the same ways as the precinct count scanners can fail. Visible failures, like rejected ballots, can be dealt with by manual counting, but there can be invisible failures which can only be caught via audits and recounts, which generally only sample a small fraction of ballots.

Non-Technical Failures
The above partial catalog of technical failures isn't to say that there aren't a huge number of potential non-technical failures. A huge amount of our pollworker training was devoted to the various anomalies we might have to deal with, ranging from voter's address is wrong to voter is a convicted felon. I may get around to talking about those at some later point.

Next: Malicious failure modes.


November 1, 2008

Most elections in the US use what's called first past the post voting. This just means that whoever gets the most votes wins, regardless of if they get a majority of the votes. Some other countries use what's called Instant Runoff Voting (IRV). The idea behind IRV is that voters rank order their choices. Then, if no candidate has a majority of first place votes, the lowest ranked candidate is removed and you then take the highest ranked candidates from each voter who voted for that candidate. Gigabytes of material have been written about the virtues of IRV versus first past the post versus approval voting, and I don't propose to rehash that here. Instead, I want to talk about the impact of IRV on a voting system.

The issue is this: in a FPTP system, the machines can simply record the number of votes for any candidate, since this is sufficient to resolve the contest.1 In an IRV system you need to record the rankings. Here's an example of why:

Let's say we have an election with three candidates, which we'll call Alice, Bob, and Charlie, and denote A, B, C. We have five voters, numbered 1-5. Now, consider the following table of preferences:

A A B B C    --  A:2, B:2, C:1
C C C A B    --  A:1, B:1, C:3
B B A C A    --  A:2, B:2, C:1

In the first round, then A and B are tied, so we cross out C. This has no impact on voters 1-4, but voter 5 now votes for B, so now it's 3-2 for B and B wins.

Now consider the following table of preferences:

A A B B C     -- A:2, B:2, C:1
C B C C A     -- A:1, B:1, C:3
B C A A B     -- A:2, B:2, C:1

This has the same totals as before, but this time, when we cross off C, voter 5 votes for A and now it's 3-2 A and A wins. I.e., totals aren't enough to determine the winner of an IRV contest. (At this point I can hear the approval voting enthusiasts screaming that approval doesn't have this problem. That's true but irrelevant. Take it outside.)

In order to make IRV work, you need to report each voter's preferences. The difficulty here is that this represents a potential threat to voter privacy because it means that election central needs to have access to the voter's ballot information (this is true with central count optical scan, but not with precinct count or DREs). If there is some way to tie the ballot to a voter, you could know how a voter voted, which could be used for vote buying or coercion.

One standard technique for this sort of tying is what's called "pattern voting". The voter is instructed to vote for a specific set of candidates with one race being the one the vote buyer cares about and the other ones being used to encode the voter's identity. Then the attacker looks for that ballot in the reported ballot lists. One natural defense is to disaggregate the contests, so that while you keep the preferences for a given race, they are disconnected from other races. However, when IRV is used, you can encode your information in the ordering of the individual contests, typically without too much impact on the election. This works especially well in races with a large number of candidates, where it doesn't matter too much how big your effect is on the 29th and 30th candidate.

There has been some work on cryptographic techniques for IRV (e.g., [*]), but the uptake of cryptographic voting in general has been minimal.

1.Though it turns out that many DREs actually record the invididual vote results. See, for instance Issue 5.2.19 of the Premier Elections TTBR report.