Seda Davtyan
Sotiris Kentros
Aggelos Kiayias
Laurent Michel
Nicolas Nicolaou
Alexander Russell
Andrew See
Narasimha Shashidhar
Alexander A. Shvartsman
Voting Technology Research Center and Computer Science and Engineering Department
University of Connecticut, Storrs, CT 06269, USA
The audits presented in this paper were performed on request of the Office of the Secretary of the State of Connecticut.
We present the process used by the University of Connecticut VoTeR Center (Voting Technology Research Center) to perform the pre-election testing and post-election audits of memory cards for the Accu-Vote Optical Scan (AV-OS) tabulators that were used in the November 2007 Municipal Elections in Connecticut. While the tabulator hardware is identical in all districts using AV-OS systems, custom programming for each district is provided by means of removable memory cards. The process presented in this report includes testing, comparison, and analysis of the data collected during the audit. This paper also briefly outlines the safekeeping steps taken in dealing with the memory cards after receiving them from the districts. These include a strict chain of custody policy with regard to handling the cards, maintaining a log of all transactions and activities, and safekeeping (both physical and electro-magnetic) of the memory cards. In order to enable the audit process, new firmware was developed to speed up the data collection phase, and new (outboard) software was developed to perform analysis and to identify discrepancies in the collected data.
It is important to note that speed is essential for both pre- and post-election audits. Ballots may change up to just a few days before the election, leaving little time to audit the memory cards and address any discovered problems. For post election auditing, speed is also essential as lengthy disputes can directly interfere with governmental continuity.
The paper concludes with several observations based on what was learned during the memory card audit process and offers recommendations aimed at enhancing the integrity of elections. We believe that memory card audits are crucial in providing timely information and maintaining the integrity of the electoral process.
The entire audit, tool development, and re-engineering was conducted by the VoTeR Center without any access to internal vendor documentation for the AV-OS systems, source code, or assistance of any kind.
The VoTeR Center was asked by the Connecticut Secretary of the State (CT SOTS) Office to prepare for and implement memory card audits for the municipal election. We performed both pre-election and post-election audits of memory cards. The primary goal of the pre-election audit was to perform an integrity check of the contents of the memory cards which were to be used in the elections. The goal of the post-election audit was to ensure that the memory cards were in the proper state (``Election Closed" with results printed) in addition to the integrity check (same as used for the pre-election audit) to verify that the memory card programming corresponds to the intended pre-election programming.
The memory cards contain the election data, ballot layout, and bytecode (for custom reporting) for the elections. They also store the tally of ballots cast. In this sense, the memory cards are the electronic analogue of a physical ballot box. In this work, we focus on auditing the AV-OS terminal and therefore make the assumption that all state information is kept on the memory cards. For other machines which contain internal storage there would obviously be a larger class of potential problems and attacks that would require additional steps to audit.
Vendor-supplied election management systems, in our case the system called GEMS, are used to produce custom election software and data for the memory cards. For the State of Connecticut, LHS Associates of Methuen, MA were responsible for programming the memory cards. The data, layout and bytecode are contained in the GEMS database and are loaded onto the memory card using an AV-OS terminal connected to a conventional PC running GEMS. A copy of the GEMS database used to program the cards was provided by LHS Associates prior to the election. Each district received four identical memory cards containing the election information. After testing the cards, each district was directed by the Secretary of the State's Office to randomly select and ship one of the cards to VoTeR Center for the audit procedure.
The audit of a card involves the extraction of the card's image and its comparison against a reference image that the VoTeR Center produced independently from the GEMS database, using GEMS itself and its own auditing tools. Any discrepancy or deviation is logged and analyzed. Specifically, the comparison focuses on deviations in the ballot data and layout, bytecode, the state of the counters, and to some extent the audit logs present on the card. The audit process is automated to the greatest extent feasible. The remainder of the paper describes each of these steps in detail.
<473>>
For the post-election memory cards audit, a total of 100 cards were received and tested by the VoTeR Center. This represents the total number of cards made available (the cards were not selected randomly), and covers over 5% of the cards actually used in the election. Among these, 8% of the cards contained ``junk data'', consequently could not have been used in the election . One card was not programmed for elections. Among the usable cards, about 40% of the cards were used in the election as inferred by the card status. About 47% of the cards were set for election, but not used in the election (these are most likely the redundant cards from the second machine in each district). All of the above (usable) cards contained valid ballot data and the executable code on these cards was the expected code, with no extraneous data or code on the cards.
The overall election system that is the subject of this report consists of two major components [6]: the AccuVote Optical Scan voting terminal (AV-OS) and Global Election Management System (GEMS).
The AV-OS terminal is a computing device responsible for accepting ballots and recording the results of the election. The functionality of the terminal is determined by its firmware which is loaded on an Erasable Programmable Read Only Memory (EPROM). The terminals currently in use in the State of Connecticut contain the firmware version 1.96.6. The major hardware components include an optical scanner, paper-tape dot-matrix printer, LCD display, serial communication port, and built-in modem. Finally, the AV-OS supports a removable 40 pin EPSON memory card that maintains the information regarding the candidates, the results of the elections, and executable code used for reporting. Extensive analysis and discussion of the contents of the memory card appear below.
GEMS is the ballot design and central tabulation system. It is installed and operated from a conventional PC. GEMS consists of several databases that include the data, ballot layout, and bytecode corresponding to the precincts participating in the election. This data is transferred via the serial communication port to (and from) the memory card kept in the AV-OS terminal. (We note that in Connecticut, central tabulation feature of GEMS is not used.)
The EPROM reader was used to read the original firmware from the machine's EPROM and save it on the PC as a binary (hex code) file. This code was processed using a hex editor to gain some understanding of the firmware. The binary image of the firmware was examined as a friendlier human-readable representation with the IDA Pro tool based on the assumption that the code was meant for a 80186 processor1. Note that no decompilation of the code was attempted or performed. All new code needed to perform the audits was developed directly on the firmware image with the help of a simple hexadecimal editor. Deploying the needed audit firmware boiled down to burning a new image onto a programmable EPROM2 and installing the new EPROM into the AV-OS.
The data on the card includes status information, an audit log, ballot description, and counters, described in more detail below. Note that the analysis is performed without any technical documentation from the vendor and in the absence of the firmware source code. Therefore the validity of our findings is based on the systematic analysis of the firmware binary code and by ``eavesdropping" on the communication between GEMS and AV-OS. Our analysis revealed the formatting depicted in Figure 1. Here we summarize briefly the data found in each part of the memory card.
The AccuBasic (AB) bytecode present in the programmed memory cards is responsible for the reporting procedures associated with an election. The code is written in a proprietary symbolic language; though the language explicitly lacks the ability to write to the memory card, it supports traditional control-flow, arithmetic, read-write local variables and procedure calls. AccuBasic programs are compiled to produce bytecode (externally) stored in .abo files. The bytecode provided by LHS Associates for this election was manually analyzed to verify that no extraneous (or malicious) functionality was present. This analysis was performed in part with the help of experiments conducted using the AccuBasic compilers (1.94 and 1.95) publicly available at [1].
In the static analysis phase we describe how to obtain a true image of the contents of the memory cards used in AV-OS terminals. A major obstacle is the absence of readily available card readers in the market, due to the discontinuation of such memory cards. We developed new firmware for the AV-OS terminal in order to use the terminal as a card reader. Having done so, we used one of the AV-OS terminals, equipped with our new firmware, as a card reader/writer and captured the contents of the card with the help of data collection software running on a connected PC. This software was designed to communicate with the modified firmware and save the contents of the cards on the PC for further testing. Below we provide a high level description of the new custom firmware and the data collection software.
Once the data collection tools are described, we go on to describe the testing phase and, in particular, the exact data collected for card evaluation. The data is classified into three categories: (a) Baseline data, (b) Pre-Election Data, (c) Post-Election Data. We discuss below the role and the selection process for each category. Overall the testing phase aims to collect adequate data to ensure the integrity of the memory cards used in the elections and the discovery of any data inconsistencies.
The static analysis phase consists of three parts: analysis and customization of the AV-OS firmware, developing a data collection and comparison tool, and analyzing the bytecode that is used in all districts.
The above issues motivate the need for analyzing the firmware and developing new firmware to eliminate the drawbacks.
Thus our objective here was to transform the AV-OS voting terminal into a simple card reader that would reliably deliver the data from the card so it could be read from the serial port with no side-effects. We emphasize here that this paper contains only the high-level overview of these steps and omits the technical details.
As mentioned in Section 2 the AV-OS terminal's processor is based on an Intel 80186, 16 bit architecture. As a consequence, the firmware stored in the 128K 32 pin EPROM consists of two segments, with the first segment at the beginning of the EPROM's memory space. ``Far'' calls, which reveal the starting address of the second segment, are employed to facilitate the interaction between the two segments. The firmware contains hardware initialization (boot code) and the AV-OS program. In our work we used the original hardware initialization code. To confirm that this code does not alter memory card contents, we performed multiple experiments using cards with known content. The fact that no content alteration was observed, and that the initialization of the terminal does not required the card to be inserted provided evidence that we could safely use the initialization in our auditing procedure.
Our goal was the following: (i) identify the components and the procedures responsible for dumping the contents of the memory card and, (ii) develop new procedures to suit our needs and to produce new firmware to be used in the audit. To hasten the data extraction process we implemented a very simple form of data compression based on run-length encoding (RLE) and used it to transfer the contents of the memory card through the serial line. In this way, our new firmware code transforms the AV-OS terminal into a true card reader that simply delivers the data from the memory card to the serial port without any of the undesirable side-effects seen with the original firmware.
Four main points were taken into account during the production of new firmware:
Again, the findings reported here were obtained by close examination and analysis the firmware's binary file and without any assistance or technical documentation from the vendor.
Memory Card Access: The first challenge is to directly access the data stored in the memory card. For that purpose we identified the memory addresses of different segments on the memory card. With experimentation and tests we verified our ability to read and write from predefined locations of the card. As a result the exact value of each particular byte kept on the card could be obtained.
Serial Port Access: The second objective was to extract the bytes obtained from the card and faithfully place them in the appropriate location so that it could be read on the serial port. We determined that the original firmware was indeed inadequate in performing the audit. We analyzed the code responsible for dumping in the original firmware and (with the help of [16]) identified the procedure responsible for transmitting bytes to the serial port. Our analysis of the code revealed that byte values 11 hex and 13 hex were indeed treated differently and not sent correctly over the wire. Our new firmware transmits the data faithfully, without any filtering. The firmware was tested on the transmission of known contents of the memory card to confirm and verify that no additional bytes were transmitted and that the functionality was as required.
Delivery of the Memory Card data: To dump the entire card, it is sufficient to write a simple routine that transfers all the bytes of the card to the serial port, one at a time. A dedicated program waits on the other side of the wire and collects the data sent. That program saves the received bytes in a file that is used later for evaluation and audit analysis.
Avoid logging on the memory cards: The final task was to ensure that no logging information is added to the memory card during the dumping process - such changes would be unacceptable in a pre-election audit setting. Since our firmware implements the dumping process and controls the execution from the beginning of the boot, we can guarantee that no logging occurs. Thorough testing verified that the unmodified initialization code in the firmware also does not alter the log nor any other portion of the memory card. Thus the entire procedure gets an image of the card and does not alter the card.
1KB/s) of AV-OS,
dumping the contents of the 128KB memory card takes a significant amount of time ( 
2 min).
Inspecting a large number of cards (hundreds or even thousands) would require substantial time.
To solve this problem and to optimize the dumping procedure, we implemented
Run Length encoding to compress the bytestream sent over the wire,
and decompress it on the receiving end. This simple improvement reduces the dump time
to 20
.
(Simple run-length encoding works well here because
several large parts of the memory card are
populated with sequences of identical values.)
The data collection/comparison tool serves two purposes:
The challenge in auditing the memory cards is in managing the large number of data files and automating the tasks. The tool we developed includes a graphical user interface (GUI) to simplify the process. The tool maintains the list of towns and districts, keeping track of the data collected for both baseline and audit cards. It also records data sent from the AV-OS with a single button click, and compares all collected data, reporting any discrepancy. The comparison is done on the basis of our analysis of the memory card layout. The comparison identifies any differences, ignoring those that are not significant (such as timestamps, log entries, and sequence numbers). The tool also generates a table listing all districts with the various memory card states, discussed in Section 3.2.2 below. This allows quick assessment after data collection to identify potential problems.
Having the methodology to extract the data from the memory cards, our next task is to test for potential data inconsistencies and integrity problems of the memory cards used in the elections. To perform this task we need to collect three types of data: (a) Baseline data, (b) Pre-Election Data, and (c) Post-Election Data.
The first concern was to collect a sufficient amount of memory cards in order to create a representative sample for our findings. Each polling center received four programmed memory cards from LHS Associates. There are two AV-OS voting terminals in each polling center. Consequently, two out of the four cards from each precinct were the ``primary" cards, i.e., the cards that would be used in the election, and the remaining two cards were the ``backup" or ``secondary" cards. According to the instructions set up by the Office of Secretary of the State, after receiving four programmed memory cards, poll workers of each district are supposed to put any two out of four cards in the available machines and run a test election on each of them. Once tested the cards should be placed in ``election mode'' and removed from the AV-OS machine. Putting the cards in ``election mode'' resets the counters to zero. Then, the remaining two cards should be tested and placed in ``election mode''. The AV-OS machine should now be sealed and stored in a secure location. Immediately after the testing is complete, they are required to randomly select one memory card per district and send this card to the University of Connecticut VoTeR Center for pre-election audit testing. This card should be chosen from the memory card(s) that are not already sealed in an optical scan voting machine. The procedure for random selection of the memory card(s) described above applies only to precinct based tabulators and does not include central counting absentee ballot tabulators. Given the above procedures, each memory card received for pre-election auditing should be in ``election mode'' with counters set to zero and should have evidence of a pre-election test.
After collecting the necessary cards from the districts we tested the validity of the cards by performing a semantic comparison between the pre-election and the baseline data. The potential problems we are testing for include incorrect ballot data or bytecode, non-zero counters, and incorrect states. Such problems could arise from either malicous attacks, accidents, or failure to follow procedures. By comparing all data on the audited card with baseline data we can detect any such discrepancies.
There are four aspects of interest with respect to the format of a memory card and the state it can be in when audited: (a) Card Format, (b) Card Status, (c) Counter Status, and (d) Election Count.
Figure 2 shows the states of the AV-OS (ovals) and the actions (arrows) that move the machine from one state to another. The states in red, Set for Election with Non-Zero Counters and Results Print Aborted, are ``dangerous'' states for an audited pre or post election card, respectively. States shown in Green, Set For Election and Audit Report Printed, are the ideal states for pre and post election cards, respectively. Gray states, Election Loaded and Election Closed, are safe, though reflect a failure to follow strict procedures. Junk cards are also safe, though it is unclear how they get into this state. Actions in blue are restricted to poll workers with the PIN number.
To summarize: pre-election cards should at least be in the Election Loaded state, and ideally in the Set for Election state, but never Set for Election with non-zero counters. Post election cards should ideally be in the Election Closed state, and ideally with the audit log printed, but never with the Results Aborted or with the election not yet closed. When the election is closed, the results printing is begun automatically and the aborted state is only reached if the printing is cancelled, or if a duplicate copy is begun and aborted. The Audit Report Printed thus indicates that the results and the audit log were both printed. In Section 4 we see that post election cards were never in the audited state since auditing was not yet part of the standard procedures. Because of this, the Election Closed state is the expected state in our analysis.
of all districts, received during the weeks before and after the election. The post-election audit was performed in 100 memory cards, that covered the 5 of the cards used in the election.
We noticed a few differences between the actual procedures followed by the poll workers and the procedures defined by the Office of Secretary of the State, regarding the sampling of the memory cards to be sent to VoTeR Center. Some of those were:
Clearly a better definition of the audit procedure is needed, so that the memory cards are selected from all districts per town. Moreover, we suggest sampling the memory cards uniformly at random and not choosing the backup cards as the ones to send. This would require that all the cards ``look and feel'' the same and the backup cards are not marked differently from the main cards. Greater care should be taken to adhere to the instructions provided by the State. It is important to emphasize that the backup cards were programmed and handled the exact same way as the primary cards during the pre-election procedure from the LHS Associates. Thus the fact that some districts sent us their backup cards does not greatly affect the significance of our statistical results. We expect that future audits would reflect higher reliability and improve statistical strength. The changes in the audit procedures are already being implemented by the CT SOTS Office for future elections.
Table 1 shows the frequency of various states observed on the audited memory cards. The data is presented in four parts:
In the rest of the analysis the percentages are computed for almost 97% of the cards that were properly formatted and contained contained good data, i.e., the cards that did not contain junk data.
Over 8% of the cards were found to be in the Election Closed state, suggesting that the poll workers performed AV-OS testing in the election mode, and this is not the intended procedure. However, for AV-OS machines with such cards to be used on the election day, the cards would need to be reset.
About 43% of the cards had non-zero counters, but were not set for election. This is not the intended state of the counters, however the counters will be zeroed when the machine is going to be set for election.
One card (0.2%) was found in the state where it was set for election with non-zero counters, specifically recording that 19 votes were cast. This is problematic and is due to incorrect pre-election testing procedures. The Poll Workers Guide specifies that when the machine is turned on the day of the election, it should print an election zero report which the poll workers should verify. Any machine that is set for election with zero counters should print such a report when it is turned on. However, if the counters are non-zero, it will not print anything and will instead resume (continue) counting. Therefore, attentive poll workers should be able to detect a card that is in this state by the lack of a zero report (in fact it was confirmed that in Connecticut all districts documented printing the zero report). Nonetheless, if poll workers are unaware of this policy then such a machine could result in incorrect election results.
These observations indicate that proper pre-election testing procedures are either not uniform, or are not communicated effectively.
Table 2 shows the frequency of various states observed on the audited memory cards.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Recall that each district received 4 memory cards. Most of the districts sent one of the cards to the VoTeR Center for pre-election audit, leaving 3 cards in the possession of each district. Among these, it is expected that one card was used in the election. Thus about 33.3% of the cards should have been used in the election. Among the post-election cards we examined, 36% of the cards (36 cards) were used, which is close to what was anticipated. (Some of the audited cards turned out to be unusable (they contained ``junk'' data), so among the usable cards 39.6% were used.)
We present the rest of the results in three parts:
In the rest of the analysis the percentages are computed for the 92% of the cards that were properly formatted, i.e., the cards that did not contain junk data.
No cards with uploaded results were found. No cards with audit report printed were found. These are the expected results.
Of the usable cards, 12% were not set for election. These cards were not used in the election, but they should have been set for election, suggesting that some pre-election protocols were not followed properly.
Over 47% of the cards were Set for Election, which is the desired memory card state for cards that were not used in the election.
Almost 35% of the usable cards (32 cards) were found to be in the Election Closed state. These are the cards that were used in the election.
Another 4.3% (4 cards) were used in the election, but indicate that the printing of the results was aborted. This suggests that the machine was turned off before the complete paper tape was printed. (Perhaps poll workers waited just for the counters to be printed, then turned off the machine. Alternatively, it is possible that the printing of a duplicate tape was aborted.)
Over 47% of the cards were set for election and had zero counters. This is the intended state of the cards that were not used in the election.
About 35% of the cards (32 cards) indicated that election was closed and had non-zero counters. These cards were used in the election.
Over 4% of the cards (4 cards) had non-zero counters and indicated that the printing of the results was aborted (see above). These cards were used in the election.
One card (1.1%) was found in the state where it was set for election with non-zero counters. The counters must be 0 for such a card. This situation is detectable upon the attempt to print the ``zero count" report on the election day.
Having performed and completed the audit, we believe that both pre-election and post-election tests and audits of memory cards (and similar components of voting equipment of various makes) are crucial in providing valuable and timely information necessary to ensure the integrity of our electoral system. Such audits can reveal not only incorrect (or malicious) programming of the customizable software components, but also mistakes or oversights that can occur in preparing voting machines for elections and running the elections using the machines.
For example, one memory card was found to be set for election with non-zero counters. If such a card is carelessly used in an election, the results would reflect the extra votes already on the card. This would have been detected by the failure to produce a zero total report on election day. Additionally, several cards were in states that, although not dangerous, were contrary to the proper state. For example, the pre-election cards tested with in Election Mode or not set for election, or post-election cards with aborted report printing. This serves to highlight the importance of having clear and precise instructions, and poll workers trained to follow them.
There were also a surprising number of ``junk'' cards (3.5% in pre-election audit and 8% in post-election audit). Whether or not these cards were the results of software or hardware failures, or lack of testing at the vendor site, such rates of failure are clearly inadequate for modern electronic systems. Note that such cards will not work in the AV-OS. Indeed, some arrived with messages indicating that they were tested by poll workers and found to be ``broken". We do not believe these cards were damaged in shipping. Consequently, it appears that these cards were either not tested prior to shipping them to districts, or the results of hardware failures of cards themselves or of the voting terminals used to program them. Thus testing the voting equipment before the elections will help avoid problems on election day.
Finally, our examination of the memory cards revealed no incorrect ballot data or bytecode.
Following our participation in the Connecticut Voting technology Standards Board in 2005, the Voting Technology Research (VoTeR) Center was established in 2006 to advise state government in the use of voting technologies, to research, investigate and evaluate voting technology and voting equipment, and to develop and recommend safe use procedures for the computerized voting technology in elections. The personnel of the Center includes several faculty members, graduate students, and staff of the Computer Science and Engineering department at the University Of Connecticut.
The work of VoTeR Center in the State of Connecticut is funded by the Office of the Connecticut Secretary of the State (SOTS), and we function in close contact with the SOTS Office personnel. We offer the State an independent, objective analysis of the voting technologies offered by several vendors, we advise the State on selecting and administering the voting equipment for its election needs, and we are not associated with any of the voting technology vendors. The evaluations of the voting technology are performed at the VoTeR Center Lab at the University of Connecticut. These include hands-on evaluations, exploration of possible attack vectors, physical integrity checks of the terminals and memory cards, and mitigation strategies. It is worth pointing out that the VoTeR center is not involved in the State's policies for choosing a vendor to procure the voting technology, but limited to evaluating these technologies before deployment and use by the State. In this sense the VoTeR center is a third party independent technical consulting resource for the State of Connecticut.
VoTeR Center personnel assisted the State in developing safe use procedures for the Optical Scan terminals for this election. The procedures in place for the election includes strict physical custody policy, tamper-resistant protection of the equipment, and random post-election audits.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -split 0 -show_section_numbers -local_icons -no_navigation evt08-unified.tex
The translation was initiated by on 2008-06-30
![\includegraphics[width=0.95\textwidth]{format}](img1.png)
![\includegraphics[width=0.95\textwidth]{stateDiagram}](img5.png)