Why getting voting right is hard, Part V: DREs (spoiler: they’re bad)

This is the fifth post in my series on voting systems (catch up on parts I, II, III and IV), focusing on computerized voting machines. The technical term for these is Direct Recording Electronic (DRE) voting systems, but in practice what this means is that you vote on some kind of computer, typically using a touch screen interface. As with precinct-count optical scan, the machine produces a total count, typically recorded on a memory card, printed out on a paper receipt-like tape, or both. These can be sent back to election headquarters, together with the ballots, where they are aggregated.

Accessibility

One of the major selling points of DREs is accessibility: paper ballots are difficult for people with a number of disabilities to access without assistance. At least in principle DREs can be made more accessible, for instance fitted with audio interfaces, sip-puff devices, etc. Another advantage of DREs is that they scale better to multiple languages: you of course still have to encode ballot definitions in each new language, but you don't need to worry about whether you've printed enough ballot in any given language^[1]

In practice, the accessibility of DREs is not that great:

Noel Runyan is one of the few people who sits at the crossroads of
this debate. He has 50 years of experience designing accessible
systems and is both a computer scientist and disabled. He was dragged
into this debate, he said, because there were so few other people who
had a stake in both fields.

Voting machines for all is clearly not the right position, Runyan
said. But neither is the universal requirement for hand-marked paper
ballots.

The [Americans with Disabilities Act], Hava and decency require that
we allow disabled people to vote and have accessible voting systems,"
Runyan said.

Yet Runyan also believes the voting machines on the market today are
garbage". They neither provide any real sense of security against
physical or cyber-attacks that could alter an election, nor do they
have good user interfaces for voters regardless of disability status.

See also the 2007 California Top-to-Bottom-Review accessibility report for a long catalog of the failings of accessible voting systems at the time, which don't seem to have improved much. With all that said, having any kind of accessiblity is a pretty big improvement. In particular, this was the first time that many visually impaired voters were able to vote without assistance.

DestroyingClarifying Voter Intent

As discussed in previous posts, one of the challenges with any kind of hand-marked ballot is dealing with edge cases where the markings are not clear and you have to discern voter intent. Arguments about how to interpret (or discard) these ambiguous ballots have been important in at least two very high stakes US elections, the 2000 Bush/Gore Florida Presidential contest (conducted on punch card machines) and the 2008 Coleman/Franken Minnesota Senate contest (conducted on optical scan machines). It's traditional at this point to show the following picture of one of the scrutineers" from the Florida recount trying to interpret a punch card ballot^[2]:

In a DRE system, by contrast, all of the interpretation of voter intent is done by the computer, with the expectation that any misinterpretation will be caught by the voter checking the DRE's work (typically at some summary screen before casting). In addition, the DRE can warn users about potential errors on their part (or just make them impossible by forbidding voters from voting for >1 candidate, etc.). To the extent to which voters actually check that the DRE is behaving correctly, this seems like an advantage, but if they do not (see below) then it's just destroying information which might be used to conduct a more accurate election. We have trouble measuring the error rate of DREs in the field - again, because the errors are erased and because observing actual voters while casting ballots is a violation of ballot privacy and secrecy - but Michael Byrne reports that under laboratory conditions, DREs have comparable error rates (~1-2%) to hand-marked optical scan ballots, so this suggests that the outcome is about neutral.

Scalability

DREs have far worse scaling properties than optical scan systems. The number of voters that can vote at once is one of the main limits on how fast people can get through a polling place. Thus, you'd like to have as many voting stations as possible. However, DREs are expensive to buy (as well as to set up), so there's pressure on the maximum number of machines. To make matters worse, you need more machines than you would expect by just calculating the total amount of time people need to vote.

The intuition here is that people don't vote evenly throughout the day, so you need many more machines than you would need to handle the average arrival rate. For instance, if you expect to see 1200 voters over a 12 hour period and each voter takes 6 minutes to vote, you might think you could get by with 10 machines. However, what actually happens is that a lot of people vote before work, at lunch, and after work and so you get a line that builds up early, gradually dissipates throughout the morning, with a lot of machines standing idle, builds up again around lunch, then dissipates, and and then another long line that starts to build up around 5 PM. The math here is complicated, but roughly speaking you need about twice as many machines as you would expect to ensure that lines stay short. In addition, the problem gets worse when there is high turnout.

These problems exist to some extent with optical scan, but the main difference is that the voting stations - typically a table and a privacy shield - are cheap, so you can afford to have overcapacity. Moreover, if you really start getting backed up you can let voters fill out ballots on clipboards or whatever. This isn't to say that there's no way to get long lines with paper ballots; for instance, you could have problems at checkin or a backup at the precinct count scanner, but in general paper should be more resilient to high turnout than DREs. It's also more resilient to failure: if the scanners fail, you can just have people cast ballots in a ballot box for later scanning. If the DREs fail, people can't vote unless you have backup paper ballots.

Security

DREs are computers and as discussed in Part III, any kind of computerized voting is dangerous because computers can be compromised. This is especially dangerous in a DRE system because the computer completely controls the users experience: it can let the voter vote for Smith - and even show the voter that they voted for Smith - and then record a vote for Jones. In the most basic DRE system, this kind of fraud is essentially undetectable: you simply have to trust the computer. For obvious reasons, this is not good. To quote Richard Barnes, for security people trust' is a bad word."

How to compromise a voting machine

There are a number of ways in which a voting machine might get compromised. The simplest is that someone might with physical access might subvert it (for obvious^[3] reasons, you don't want voting machines to be networked, let alone connected to the Internet). The bad news is that - at least in the past - a number of studies of DREs have found it fairly easy to compromise DREs even with momentary access. For instance, in 2007, Feldman, Halderman, and Felten studied the Diebold AccuVote-TS and found that:

1. Malicious software running on a single voting machine can steal votes
with little if any risk of detection. The malicious software can modify
all of the records, audit logs, and counters kept by the voting machine,
so that even careful forensic examination of these records will find
nothing amiss. We have constructed demonstration software that carries
out this vote-stealing attack.

2. Anyone who has physical access to a voting machine, or to a memory
card that will later be inserted into a machine, can install said
malicious software using a simple method that takes as little as
one minute. In practice, poll workers and others often have
unsupervised access to the machines.

As I said in Part III, most of the work here was done in the 2000s, so it's possible that things have improved, but the available evidence suggests otherwise. Moreover, there are limits to how good a job it seems possible to do here.

As with precinct-count machines, there are a number of ways in which an attacker might get enough physical access to the machine in order to attack them. Anyone who has access to the warehouse where the machines are stored could potentially tamper with them. In addition it's not uncommon for voting machines to be stored overnight at polling places before the election, where you're mostly relying on whatever lock the church or school or whatever has on its doors. It's also not impossible that a voter could exploit temporary physical access to a machine in order to compromise it - remember that there usually will be a lot of machines in a given location so it's hard to supervise them all - but that is a somewhat harder attack to mount.

Viral attacks

However, there is another more serious attack modality: device administration. Prior to each election, DREs need to be initialized with the ballot contents for each context. The details of how this is done vary, for instance one connect them via a cable to the Election Management System (EMS) [-corrected from Server"], or insert a memory stick programmed by the EMS, or sometimes over a local network. In either case, this electronic connection is a potential avenue for attack by an attacker who controls the EMS. This connection can also be an opportunity for a compromised voting machine to attack the EMS. Together, these provide the potential conditions for a virus: an attacker compromises a single DRE and then uses that to attack the EMS, and then uses the EMS to attack every DRE in the jurisdiction. This has been demonstrated on real systems. Here's Feldman et al. again:

3. AccuVote-TS machines are susceptible to voting-machine viruses-computer
viruses that can spread malicious software automatically and invisibly from
machine to machine during normal pre- and post-election activity. We have
constructed a demonstration virus that spreads in this way, installing our
demonstration vote-stealing program on every machine it infects.

It's important to remember that this kind of attack is also potentially possible with precinct-count opscan machines: any time you have computers in the polling place you run this risk. The major difference is that with precinct-count opscan machines, you have the paper ballots available so you can recount them without trusting the computer.

Voter Verifiable Paper Audit Trails (VVPAT)

Because of this kind of concern, some DREs are fitted with what's called a Voter Verifiable Paper Audit Trail (VVPAT). A typical VVPAT is a reel-to-reel thermal printer (think credit card receipts) behind a clear cover that is attached to the voting machine, as in the picture of a Hart voting machine below (the VVPAT is the grey box on the left). [Picture by Joseph Lorenzo Hall].

The typical way this works is that after the voter has made their selections they will be presented with a final confirmation screen. At the same time, the VVPAT will print out a summary of their choices which the voter can check. If they are correct, the voter accepts them. If not, they can go back and correct their choices, and then go back to the confirmation screen. The idea is that the VVPAT then becomes an untamperable - at least electronically - record of the voter's choices and can be counted separately if there is some concern about the correctness of the machine tally. If everyone did this, then DREs with VVPAT would be software independent (recall our discussion of SI in Part III of this series).

The major problem with VVPATs is that voters make mistakes and they aren't very good about checking the results. This means that a compromised machine can change the voter's vote (as if the voter had made a mistake). If the voter doesn't catch the mistake, then the attacker wins, and if they do, they're allowed to correct the mistake.^[4] We do have some data on this from Bernhard et al., who studied Ballot Marking Devices (BMDs), which are like DREs except that they print out optical scan ballots (see below). They found that if left to themselves around 6.5% of voters (in a simulated but realistic setting) will detect ballots being changed, which is pretty bad. There is some good news here, which is that with appropriate warnings by the poll workers" the researchers were able to raise the detection rate to 85.7%, though it's not clear how feasible it is to get poll workers to give those warnings.

Privacy/Secrecy of the Ballot

The DRE privacy/secrecy story is also somewhat disappointing. There are two main ways that the system can leak how a voter voted: via Cast Vote Records (CVRs) and via the VVPAT paper record. A CVR is just an electronic representation of a given voter's ballot stored on the DRE's disk". In principle, you might think that you could just store the totals for each contest, but it's convenient to have CVRs around for a variety of reasons, including post-election analysis (looking for undervotes, possible tabulation errors, etc.) In any case, it's common practice to record them and the Voluntary Voting Systems Guidelines (VVSG) promulgated by the US Election Assistance Commission encourage vendors to do so. This isn't necessarily a problem if CVRs are handled correctly, but it must be impossible to link a CVR back to a voter. This means they have to be stored in a random order with no identifying marks that lead back to voter sequence. Historically, manufacturers have not always gotten this right, as, for instance, the California TTBR found (See Section 4.4.8 and Section 6.8). These problems can also exist with precinct count optical scan systems, but I forgot to mention it in my post on them. Sorry about that. Even if this part is done correctly, there are risks of pattern voting attacks in which the voter casts their ballot in a specific unique way, though again this can happen with optical scan.

The VVPAT also presents a problem. As described above, VVPATs are typically one long strip of paper, with the result that the VVPAT reflects the order in which votes were cast. An attacker who can observe the order in which voters voted and who also has access to the VVPAT can easily determine how each voter voted. This issue can be mostly mitigated with election procedures which cut the VVPAT roll apart prior to usage, but absent those procedures it represents a risk.

Ballot Marking Devices

The final thing I want to cover in this post is what's called a Ballot Marking Device (BMD) [also known as an Electronic Ballot Marker (EBM)]. BMDs have gained popularity in recent years - especially with people from the computer science voting security community - as a design that tries to blend some of the good parts of DREs with some of the good parts of paper ballots. For example, the Voting Works open source machine design is an BMD, as is Los Angeles's new VSAP machine.

A BMD is conceptually similar to DRE but with two important differences:

1. It doesn't have a VVPAT but instead prints out a ballot which can be fed into an optical scanner.
2. Because the actual ballot counting is done by the scanner, you don't need the machine to count votes, so it doesn't need to store CVRs or maintain vote totals.

BMDs address the privacy issues with DREs fairly effectively: you don't need to store CVRs in the machine and the ballots are to some extent randomized in the ballot boxes and handling process. They also partly address the scaling issues: while BMDs aren't any cheaper, if a long line develops you can fall back to hand-marked optical scan ballots without disrupting any of your back-end processes.

It's less clear that they address the security issues: a compromised BMD can cheat just as much as a compromised DRE and so they still rely on the voter checking their ballot. There have been some somewhat tricky attacks proposed on DREs where the attacker controls the printer in a way that fools the user about the VVPAT record and these can't be mounted with a BMD, but it's not clear how practical those attacks are in any case. Probably the biggest security advantage of a BMD is that you don't need to worry about trusting the machine count or the communications channel back from the machine: you just count the opscan ballots without having to mess around with the VVPAT.^[5] And of course because they're fundamentally just a mechanism for printing paper ballots, it's straightforward to fall back to paper in case of failure or long lines.

Up Next: Post-Election Audits

We've now covered all the major methods used for casting and counting votes. That's just the beginning, though: if you want to have confidence in an election you need to be able to audit the results. That's a topic that deserves its own post.

1. For instance, Santa Clara county produces ballots in English, Chinese, Spanish, Tagalog, and Vietnamese, Hindi, Japanese, Khmer, and Korean.
2. Punch cards are an old system with some interesting properties. The voter marks their ballot by punching holes in a punch card. The card itself has no candidates written on it but is instead inserted into a holder that lists the contests and choices. The card itself is then read by a standard punch card reader. This seems like it ought to be fairly straightforward but went wrong in a number of ways in Florida due to a combination of poor ballot design and an unfortunate technical failure mode: it was possible to punch the cards incompletely and as the voting machine filled up with chads (the little pieces of paper that you punched out), it would sometimes become harder to punch the ballot completely. This resulted in a number of ballots which had partially detached (hanging") chads or just dimpled chads, leading to debates about how to interpret them. Wikipedia has a pretty good description of what happened here.
3. At least they should be obvious: It's incredibly hard to write software that can resist compromise by a dedicated attacker who has direct access (this is why you have to keep upgrading your browser and operating system to fix security issues). Given the critical nature of voting machines, you really don't want them attached to the Internet.
4. In principle, this might leave statistical artifacts, such as a higher rate of correcting from Smith -> Jones than Jones -> Smith, but it would take a fair amount of work to be sure that this wasn't just random error.
5. We've touched on this a few times, but one of the real advantages of paper ballots is that they serve as a single common format for votes. Once you have that format, it's possible to have multiple methods for writing (by hand, BMD) and reading (by hand, central count opscan, precinct count opscan) the ballots. That gives you increased flexibility because it means that you can innovate in one area without affecting others, as well as allowing either the writing side (voters) or reading side (election officials) to change its processes without affecting the other. This is a principle with applicability far beyond voting. Interoperable standardized data formats and protocols are a basic foundation of the Internet and the Web and much of what has made the rapid advancement of the Internet possible.

• Previous:

The post Why getting voting right is hard, Part V: DREs (spoiler: they're bad) appeared first on The Mozilla Blog.