| Ka-Ping Yee ping@zesty.ca | David Wagner daw@cs.berkeley.edu | Marti Hearst hearst@sims.berkeley.edu | Steven M. Bellovin smb@cs.columbia.edu |
Electronic voting machines have the potential to provide significant improvements in usability and accessibility over paper ballots. For example, they can be designed to help voters detect and correct mistakes; they can provide alternate user interfaces for individuals with disabilities; and they can be programmed with support for more language choices than a typical paper ballot. However, the electronic voting process lacks the transparency of paper voting, the correct functioning of a computer program is difficult to assure, and computer failures are an everyday part of modern life. Moreover, elections are an especially high-profile and potentially rewarding target for attack, and a broad range of parties stand to benefit from influencing their outcome.
The typical challenge in software security is to design software to defend against various threats. However, because the stakes are so high for electronic voting, the threat model must include the possibility of malicious code in the voting system. Even in the absence of deliberate insider fraud, well-intentioned programmers can make mistakes. Thus, our challenge is not only to design a secure voting machine program, but also to design an overall architecture for the election system that lets us confirm that it really is secure.
Though software is involved at many stages of the election process, this work focuses on the software in the voting machine itself. We will explain in Section 3.2 why we believe this to be the most critical software component of the system. Unfortunately, the software in today’s voting machines is far too large to allow automated verification or thorough independent review, given the time and cost constraints of the election equipment certification process. In 2004, Kohno, Stubblefield, Rubin, and Wallach [5] examined the source code for the Diebold AccuVote TS machine and found it to contain many serious design and engineering errors, declaring it “far below even the most minimal security standards applicable in other contexts.” The main AccuVote TS program consists of over 31,000 lines of C++ code and resource scripts, ignoring comments and blank lines. Verifying the correctness of a program this size is overwhelmingly difficult.
We observe that the user interface (UI) is a major contributor to software complexity. By our estimate, the voting UI constitutes about 14,000 lines of the aforementioned source code. The key idea we propose is to construct and verify a prerendered description of the UI before the election. Prerendering the UI yields several significant advantages:
In this work, we focus on producing voting machine software that works correctly and verifying that it works correctly. Other parts of the election system such as absentee ballots, voting by mail, and voter registration are outside of our scope. To run an accurate election, it is also necessary to make sure the machines are actually running the software that was approved and to protect the voting machine and its storage media from tampering. We do not address physical security and chain-of-custody issues in this paper.
However, if the DRE stores votes in anonymous form, its output can be published. In addition, the inputs and outputs of all other components of the system can be published, and so can be checked by result verification. Thus the only part of the process that requires program verification is that part ranging from the input of the voter’s selections to the point where the selections are recorded anonymously.
Therefore, our approach is to minimize the size and complexity of the DRE software (even if it means that other components become more complex) and to publish all of the DRE’s inputs and outputs—except for the votes themselves, until they are anonymized—to enable result verification of the rest of the process (Figure 1).
The ballot definition is published far enough in advance that it can be validated before election day. For instance, the ballot definition might be published on government websites and made available to candidates; anyone would be able to download it and run software on their own computer to see exactly what will be shown to voters on election day. This provides a chance to detect omitted races, misspelled candidate names, layout errors, and other ballot errors. In this way, the published ballot definition is analogous to the paper sample ballot typically mailed to voters before an election.
The anonymized cast vote records from every DRE are published for all to see after the election. Anyone can add up the votes in these files to obtain the election-wide totals and compare them against the official totals to gain confidence that tallying was done correctly. Also, pollworkers and observers might be encouraged to check the summary tapes that are printed at the close of polls against the published electronic vote files to verify that the files were not tampered with while in transit.
The consequence is that neither the ballot layout software nor the vote tallying software need to be verified. The published ballot definitions, DRE software, and anonymous vote records are sufficient to allow members of the public to independently check the accuracy of the election outcome.
The DRE software can be considerably simplified by moving this layout and rendering functionality into a separate pre-election component. Instead of a ballot definition (such as those used by today’s DREs) that lists only essential information about contests and candidates, we propose a ballot definition that describes the entire user interface. For a visual interface, this would include prerendered images of the screen and interface elements exactly as the user will see them; for an audio interface, this would include prerecorded sound clips.
There is some precedent for using prerendered bitmaps in electronic voting machines. For example, the ES&S iVotronic uses bitmap ballots [3], which help provide flexible support for different languages. The ballot definitions we propose contain not just the prerendered images but a complete description of the user interface—the locations where the images will appear, the transitions from screen to screen, how these transitions are triggered, and so on.
Our proposal can be compared to the previously proposed “frog” voting architecture [2]: both are motivated by a similar desire to reduce the size and complexity of the trusted base on which the security of the voting system rests. The frog architecture separates the voting process into two steps: vote generation and vote casting. The voter first selects their votes on the vote-generation machine, which stores them on a “frog” (a storage device). Then the voter puts the frog into the vote-casting machine, which displays the contents of the frog for the voter to check, and upon confirmation, casts the votes.
A key assumption of the frog architecture is that responsibility for security rests on the simpler vote-casting machine; the vote-generation machine will have “no need for high security” [2]. This assumption requires that we rely on voters to check their frogs carefully before casting them. But some voters may give the vote-casting machine only a cursory glance, and most are likely to be influenced by confirmation bias [9], so it remains possible that votes recorded incorrectly by the vote-generation machine would go unnoticed. Even if voters are willing to check their votes carefully, the vote-generation machine remains in a position to influence voters during the selection process. For example, the vote-generation machine could present the options in a biased way; it could change the wording of a ballot measure to make an option seem more appealing or even invert the sense of the question, swapping the implications of “yes” and “no”; it could give misleading instructions to voters, such as telling them to ignore the vote-casting machine or to go to a different polling place.
Our proposed architecture therefore targets a broader security goal: we wish to secure the entire voting user interface including the vote selection process, in order to avoid bias in the election’s measurement of the will of the electorate. Prerendering the UI is not incompatible with a further partitioning of the user interface into two steps as suggested by the frog voting architecture.
As we mentioned in the preceding section, verifying the accuracy and fairness of the user interface is critical, because the user interface of any voting machine is in a position to mislead or otherwise influence voters and hence influence the voter input. The published electronic sample ballot gives the election a verifiable user interface, which can be examined and tested by all voters, members of the disabled community, usability experts, and accessibility experts.
Today, less commonly used ballot designs, such as ballots for voters with disabilities or ballots in alternate languages, receive significantly less attention, as only the election office can compose and check electronic ballots. A recent, rather alarming example of this lack of attention occurred at the June 2006 primary election in Santa Clara County, where pollworkers discovered that there was no “continue” button on one of the Chinese screens [4], which made it impossible to cast the Chinese ballot. A published sample ballot would have increased the chances of catching such an error before the election. Publishing an electronic sample ballot helps to level the playing field for members of minority communities and empowers them to play a role in ensuring that the electronic ballot serves them fairly.
Therefore, we propose a software tool that transforms an electronic sample ballot into a human-readable format that completely describes the user interface. One possible visualization would be a flowchart-like diagram that illustrates the steps of the user interface with the prerendered screen images. Anyone would be able to download the electronic sample ballot, use the program to produce a diagram, print it out, and examine it. This would make possible a new level of assurance: the electronic voting UI could be verified even by non-programmers. The hardcopy of the UI visualization could also be archived in the records of the election. The visualization alone should be sufficient to reconstruct the interface that voters used at the polls.
To protect voter privacy, ballots should be stored without any identifying information. The ballots should also be stored in an order independent of the order in which they were cast, so that someone who observes the sequence of voters entering the polling place cannot correlate the sequence of voters with the sequence of stored ballots.
To prevent coercion, voters must not be allowed to put identifying marks on their ballots. In one possible coercion scenario, the coercing party gives each voter a unique secret phrase to enter as a write-in candidate. For example, suppose Ted tells Alice to vote for Carol for President with “moldy explosion” as write-in for Dogcatcher, and also tells Bob to vote for Carol for President with “wrinkled tourbus” as write-in for Dogcatcher. Then the recorded ballots are no longer publishable because they would enable Ted to confirm, and thus buy, Alice’s and Bob’s votes.
One way to resolve this problem is to store each of the voter’s selections as a separate item instead of the entire ballot as a unit. There has been precedent for such a scheme in some paper elections, where the ballots are perforated so that they can be separated into strips, one for each contest, before being counted. If an individual voter’s selections cannot be associated with each other, then the voter cannot use a specially marked selection to identify the rest of their ballot. Splitting up the ballot would conflict with election rules in some states that require the entire ballot to be recorded intact; on the other hand, it could be argued that a constitutional right to a secret ballot takes priority over state regulations.
A traditional method of recording the voter’s selections is to store a numeric code or a text string identifying each selected candidate. Instead, we store the image containing the candidate’s name exactly as it was shown to the voter, or for a write-in, the sequence of images of the characters selected by the voter, to reduce the risk of confusion.
Our design allows the voter to choose one or more options from a list of options, which is sufficient to emulate any choice that could be expressed by selecting bubbles or arrows on an optical-scan ballot. We discuss ways to support ranking of options in Section 7.5.
Separating the ballot model from the image library reduces the cost and effort of validating changes to the ballot. Replacing the image library is sufficient to adjust the layout or visual style of the ballot, change the display resolution, or translate the interface into another language, all without altering the ballot model. For these kinds of changes, only the new image library needs to be validated, not the entire ballot definition. Comparing two image libraries (for example, to confirm the accuracy of a language translation) is easier than checking the correctness of a ballot model.
 |
 |
A contest is a question being put to the voters, such as a referendum on an issue or the election of a candidate (or several candidates) to a position. Each contest has an integer parameter max_sels specifying the maximum number of selections that a voter may choose (usually 1, but possibly more in contests that allow choosing multiple candidates) and an integer parameter max_chars specifying the maximum number of characters that can be entered for a write-in option.
The page is the basic unit of presentation. For example, a single page might display some instructions, a description of a contest, or a list of available options. At any given moment, one of the pages is the current page. The user interface begins on the first page in the array of pages. When it transitions to the last page, the ballot is cast with the user’s current selections.
Associated with each page are arrays of targets, options, reviews, and write-ins, and any of these elements can be activated by the user. In a touchscreen interface, these elements correspond to rectangular areas of the screen that are activated by touches.
A target is a user-triggered transition to another page. In a touchscreen interface, a target appears as a button that the user can press. Optionally, a target can also trigger one of the following actions:
A write-in is a write-in option. It can be in a selected or unselected state, just like a regular option; when selected, it also has an associated list of entered characters. When a write-in is activated, it triggers a jump to a subpage where the voter can type in the text of the write-in selection.
A review displays the current selections in a particular contest. Activating a review has no effect, though targets can overlap reviews. In a touchscreen interface, a review appears as a screen area (or multiple screen areas) filled in with the option (or options) currently selected in its associated contest. For example, a confirmation page could summarize the voter’s selections by presenting reviews for several contests.
A subpage is a temporary page for entering a write-in. A subpage is like a subroutine call, but only one level deep—the only possible transition is back to the current page. In a touchscreen interface, a subpage provides a text field and an on-screen keyboard for the voter to type in the name of a write-in candidate. The number of subpages is determined by the contests: there is one subpage for each contest that contains a write-in. A subpage contains an array of subtargets.
A subtarget triggers one of these actions:
Because an ACCEPT subtarget only works when there is write-in text present, a write-in cannot be simultaneously empty and selected. The purpose of APPEND2 is to prevent a write-in from appearing empty and yet being selected. For example, if the keyboard’s “space” button is an APPEND2 subtarget, then the write-in text cannot consist of only spaces.
A layout consists of a background image and an array of slots. Each page or subpage corresponds to exactly one layout, and vice versa. A slot is a rectangular region of the screen where a sprite can be pasted or where a touch will have an effect.
A sprite is an image smaller than the screen size that is meant to be pasted into a slot on a background image. The array of sprites contains images of options and write-ins in their selected states, images of characters that can be typed into a write-in, and the image of the text entry cursor shown while entering a write-in. To keep the DRE software as simple as possible, all images are stored uncompressed with 3 bytes per pixel.
In a layout corresponding to a page, the slots correspond to the targets, options, write-ins, and reviews for that page. Each target has one slot, specifying the touch region that activates the target; the image of the target button (or other widget) is part of the background image. Each option has one slot, which specifies both its touch region and also the position for pasting the sprite showing the option in its selected state. The image of the unselected option is part of the background image, and when the option is selected, the sprite is pasted over it. Each write-in also has a sprite for its selected state, which would typically look like a selected option but with space provided for the write-in text. A write-in has one slot for its touch region and for pasting the selected write-in sprite, and max_chars more slots specifying the positions where the entered characters are to be pasted. Each review has max_sels groups of slots (for displaying up to max_sels options selected by the voter). In each group of slots, there is one slot for pasting the selected option sprite and max_chars slots for displaying the write-in text if a write-in is selected.
In the layout corresponding to a subpage, the slots correspond to the subtargets and character slots for the page. Each subtarget has one slot, the touch region that activates it. Additionally there are max_chars slots specifying the positions where the entered characters are to be pasted.
Similarly, the meanings of the slots are determined by their order in the slot array. The slot array for a page contains, in order, one slot for each target, then one slot for each option, then 1 + max_chars slots for each write-in, then max_sels × (1 + max_chars) slots for each review. The slot array for a subpage contains one slot for each subtarget followed by max_chars slots for the entered text.
The sprite array contains one sprite for each option and write-in, in the order they appear among the pages, followed by, for each subpage, a character sprite for each APPEND or APPEND2 subtarget and one cursor image sprite.
Because the ballot definition must be well-formed in order for the VM to read it and operate safely and correctly, a verifier in the voting machine checks for well-formedness before accepting a ballot definition. To be well-formed, a ballot definition must meet the following conditions:
The navigator walks through the pages in the ballot model, always starting on the first page. It keeps track of the current page, the user’s current selections, the current subpage (if any), and the entered characters on the current subpage (if any). The navigator responds to just one message:
The vote recorder records the voter’s selections in non-volatile storage upon receiving a write message from the navigator. The votes are recorded using a tamper-evident, history-independent, subliminal-free storage method. Molnar, Kohno, Sastry, and Wagner have proposed several schemes with these properties [7] for storing ballots on a programmable read-only memory (PROM). Each stored selection includes or indicates its associated ballot definition so that the meaning of the selections is apparent from the storage contents.
The prototype reads the ballot definition from a file named ballot and writes vote records to a file named votes. The ballot file represents read-only media and is opened read-only; the votes file represents a PROM. Each time the program runs, it casts at most one ballot, then enters a terminal state.
Our prototype models the procedures that would take place in a real election as follows. Creating an empty votes file corresponds to opening the polls at the beginning of election day with a blank PROM. Restarting the program corresponds to activating the voting machine for a single voter. We assume that only the pollworker has the ability to restart the machine, so pollworkers can ensure that each voter only votes once. Setting the votes file read-only corresponds to closing the polls and removing the PROM.
The source code for our prototype implementation and a sample ballot definition file are available online at http://zesty.ca/voting/.
The prototype does not include any user interface for selecting which ballot definition to use; instead, it assumes that the appropriate ballot file will be present when the program starts. Different ballot files can be used for different runs.
Note that the selection of a ballot definition can be divided into two parts: choices that have to be authorized by the pollworker (such as choosing which precinct’s ballot to use) and choices that the voter is allowed to make (such as choosing a preferred language). The former type of choice can be implemented by having the pollworker select the ballot file. The latter type of choice can be implemented either by having the pollworker select a ballot definition file at the voter’s request, or by combining multiple ballots into a single ballot definition. For example, a ballot could support both English and French by including all the pages for an English ballot and all the pages for a French ballot, with a starting page to let the user choose between them.
We leave open the question of how the pollworker’s selection would be implemented in hardware. One possibility would be for the ballot definitions to be stored on individual write-protected memory cards; to support voting for multiple precincts, a pollworker would insert the appropriate precinct’s ballot definition card to activate the voting machine for a single voting session. Alternatively, all the ballot definitions could be stored on the machine in advance, and the pollworker would use some other means to choose one when starting each new voting session. In either case, our software prototype models this step simply as having the authorized choice of ballot file be present when the program starts.
For this prototype, we have chosen to store the ballots using a copyover list [7], because it is history-independent, simple to implement, and does not depend on a random number generator. A copyover list is a list of items stored in sorted order; each time we add items to the list, we write a new copy of the entire list in sorted order and erase the old copy by overwriting it with zeroes. Because the items are stored in sorted order, the list does not reveal the order in which the items were added. A copyover list uses O(n2) space in the number of items, but previous analysis [7] shows that only a modest and inexpensive amount of storage would be required to handle all the votes that could be expected to be cast on one machine in one day.
The items in the copyover list are the individual selections within each contest from all the voters. Each item consists of the SHA-1 hash [8] of the ballot definition, the integer index of the contest, and the integer index of the selected option sprite. For a write-in selection, this is followed by the indices of the selected character sprites. All integers are stored as 4-byte unsigned integers. The individual selections are stored as separate items so that the votes file can be published without letting voters mark their ballots to prove how they voted, as explained in Section 3.7.
Because the items in the list can vary in length, the size of the list depends on the contents of the selections. If the new list were stored immediately after the old list, the size of the erased space would reveal something about the size of the old list and hence about the sequence of votes. (For example, if two selections are stored, one with a short write-in and one with a long write-in, then casting the long one first would yield a larger erased space than if they were cast in the opposite order.) Therefore, we always erase the maximum amount of space that would have been required, regardless of the order in which the selections were added to the list.
A flag value is stored at the beginning of each list, and the list is encoded so that it cannot contain the flag value. The first occurrence of the flag in the file is considered to signal the start of the current list of votes. After the new list is written, erasing the flag in front of the old list commits to the new list, as shown in Figure 6. This commitment is atomic, because changing even one bit invalidates the flag.
The second scheme uses very little space, but depends on management of a global namespace of ballot definition identifiers, which might be brittle and error-prone. If a vote record says that it belongs to ballot definition #34 and there is a disagreement about which ballot definition was #34, the vote record becomes meaningless.
We chose the third scheme for our prototype because it is space-efficient, and as long as the hash function is collision-resistant, there can be no ambiguity about which ballot definition is associated with each vote record. However, in order to ascertain the true meaning of a vote, one must otherwise obtain a copy of the ballot definition. Our architecture assumes that the ballot definitions are published, so this is not a serious problem.
The fourth scheme stores the actual ballot definitions, yielding a vote record that is fully self-contained. But in order to store all the definitions on write-once storage, without revealing any information about the order in which they were used, and without using very large amounts of space, all the acceptable ballot definitions must be known in advance. This scheme would make sense for an implementation where the machine provides some way for the pollworker to select which ballot definition to use.
If the list of acceptable ballot definitions is fixed in advance, it would be possible to use just one storage device instead of two. The storage medium would initially contain all the ballot definitions; the machine would both read the ballot definitions from it and append the vote records to it. In such an alternative scheme, vote records could not become inadvertently separated from their ballot definitions, but it might be more difficult to provide a hardware-based guarantee that the ballot definitions are never alterable.
| ballot definition loader and verifier | 126 lines |
| event loop | 13 lines |
| navigator | 94 lines |
| video driver | 22 lines |
| subtotal (user interface) | 255 lines |
| vote recorder | 38 lines |
| total | 293 lines |
Our design does not support an audio interface or a printed record; these are discussed in Section 7. It does not support straight-ticket voting, ranked voting, cross-endorsed candidates, automatic ballot rotation, or generation of audit logs, though it could be extended to include these features.
Our prototype does not provide administrative functions such as viewing vote counts or changing configuration settings. It also does not perform encryption; by design, there is no need to encrypt the stored votes.
The ballot definition loader is responsible for establishing that the ballot definition is well-formed. If the loader is implemented correctly, and if the other modules rely only on the conditions of well-formedness, then the only possible kind of software failure is a failure to load the ballot definition. Successful completion of the loading and verification step assures that software errors cannot occur during the voting session.
It is easy to see by direct inspection of the source code that all modules other than the event loop only react to messages they receive. The event loop is the only module capable of initiating messages, but it is also the smallest and easiest to audit.
The video driver is a passive component, never sending any messages at all. In particular, the video driver does not have the authority to activate slots (that is, it cannot “press buttons” in the interface), which lessens our vulnerability to errors in its implementation.
The navigator has access to only the ballot model and cannot draw arbitrarily on the display. Because it cannot see the image data, it cannot determine the semantics of the user’s selections. Freezing the implementation of the VM before choosing the order of candidates on the ballot would make it difficult for even the author of the navigator to bias the vote for or against a specific candidate. Also, the only input to the navigator is a slot number, which is a small integer, so the navigator can be subjected to exhaustive testing.
The voting machine has no non-volatile storage other than the ballot definition and the cast vote storage. Because the machine is restarted for each new voting session, and because the ballot definition is read-only, the only state retained between voting sessions is the vote storage. Furthermore, the vote recorder module only receives messages and never sends any messages to any other software module, so no information in the vote storage can reach any of the other modules. Consequently, the user interface seen by each voter is determined only by the ballot definition and cannot reveal any information about previous voting sessions. Also, this ensures that all voters using the same ballot definition receive the same voting experience.
By design, our prototype can only cast one ballot each time it runs. It is easy to confirm by inspection of the navigator that the only way to cast a ballot is to arrive at the last page and to see that the last page is a terminal node in the ballot definition.
It is also straightforward to verify that overvoting is impossible, because only the navigator can manipulate the user’s selections, and there are only two places in the code where an item is added to the selection list.
Other election process rules can be verified by examining the ballot definition. For example, to ensure that the voter will be notified of undervotes before casting the ballot, we would check the graph of transitions among pages to see that the voter must proceed through review pages before arriving at any page that can cast the ballot.
One reason that we have less code is our choice of programming language. Our prototype requires a Python interpreter, whereas the AccuVote TS does not. On the other hand, the AccuVote TS software depends on Microsoft Windows CE and builds its user interface using the Microsoft Foundation Classes, which are much larger and more complex that the blit functionality we use from Pygame.
It is not unreasonable to consider running Python on voting machines. Python is widely deployed and vetted and is supported by an active developer community. Unlike Windows CE and MFC, Python is a mature open source project, distributed with an extensive suite of regression tests. As a data point concerning Python’s size, note that Nokia has released a Python interpreter [10] that fits in a 504-kilobyte installation package, which also includes over 40 Python library modules that we do not use.
Alternatively, the Python code could be translated into a compiled language. Although we did use a higher-level language, we have been careful to minimize our use of Python’s library modules and built-in functions, as described in Section 6.2. It is reasonable to expect that translating our code into a compiled language would multiply its size by a factor of 3 or 4, but not by 100.
Despite its small size, our prototype maintains clear boundaries and minimal data flow among its five modules. As described earlier in this section, many of the desired security properties of the voting machine are straightforward to verify in our prototype, due to its design. The AccuVote TS code does not lend itself to similarly easy analysis.
The event loop would handle user input from hardware buttons, and the ballot definition would specify additional targets for handling button presses. Extending the event loop to support hardware buttons would also be a way to support alternate input devices for voters with physical disabilities; the voting machine could provide a standard hardware interface for plugging in a wide variety of switch inputs.
Combined video and audio interfaces can be very helpful for users with impaired vision and we aim to provide synchronized video and audio in our future work on an accessible design.
Although the majority of blind individuals do not use braille, a braille interface would provide access to deafblind voters and improve access for those who prefer braille. This might be implemented with the addition of another ballot definition component containing data to be sent to a braille display.
For a graphical printout, the print driver module would have access only to the image library, and would tell the printer to print the sprites that the user selected.
One way to support a text printout would be to add a dictionary component to the ballot definition that associates each contest and sprite with a string. Only the print driver module would have access to the dictionary; it would send these strings to the printer to describe the user’s selections.
One simple way to obtain a truer representation of voter preferences is approval voting, in which each voter can vote for as many candidates as they want. An approval election is easily conducted with our prototype by setting max_sels equal to the number of candidates.
Other improved election methods, such the Schulze method [13] or the Tideman method [14], use voters’ rankings of the candidates to achieve a fairer result. Our current design does not directly support ranking of options, though ranking could be crudely implemented by repeating the same list of options, as in some paper elections. For example, San Francisco’s ranked ballots show the same list of candidates in each of three columns; voters are instructed to indicate their first choice in the first column, second choice in the second column, and third choice in the third column. However, since our existing prototype knows nothing about the semantics of ranking, it cannot warn the voter about invalid rankings.
To provide proper ranking support, our design could be extended to include images of numbers in the image library and to display numbers next to ranked options. The navigator could initially assign successive rank numbers as the voter makes multiple selections; to reorder the rankings, the voter could clear the contest and start again or press special targets to increment and decrement ranks. Alternatively, a subpage with a numeric keypad could be provided for typing in the rank numbers.
This research was funded in part by NSF CNS-0524252.