A Conversation with Avi Rubin

E-Voting Systems & Software Engineering

When creating a secure system, getting the design right is only part of the battle. The design must then be securely implemented. In this paper, we examine the coding practices and implementation style used to create the Diebold AccuVote-TS 4.3.1 system which was written in C++ and designed to run on a Windows CE device; see Figure 1. (The code also compiles and runs, with slightly different configurations, on regular Microsoft Windows machines, thus enabling us to verify that the code represents a complete system. The 4.3.1 snapshot of the AccuVote-TS tree has 136 .h files totaling 16,414 lines and 120 .cpp files totaling 33,195 lines, for a total of 256 files and 49,609 lines of C++ code.) This type of analysis can offer insights into future versions of the code. For example, if a current implementation has followed good implementation practices but is simply incomplete, one would be more inclined to believe that future, more complete versions of the code would be of a similar high quality. Of course, the opposite is also true, perhaps even more so: It is very difficult to produce a secure system by building on an insecure foundation.

Of course, reading the source code gives only an incomplete view into the actions and intentions of the developers who created that code. Regardless, we can see the overall software design, we can read the comments in the code and, thanks to the CVS repository, we can even look at earlier versions of the code and read the developers' commentary as they committed their changes to the archive.

Inside cvs.tar, we found multiple CVS archives. Two of the archives, AccuTouch and AVTSCE, implement full voting terminals. The AccuTouch code, corresponding to AccuVote-TS Version 3, dates from December 1998 to August 2001 and is copyrighted by "Global Election Systems Inc.," while the AVTSCE code, corresponding to the AccuVote-TS Version 4 system, dates from October 2000 to April 2002 and is copyrighted by "Diebold Election Systems Inc." (Diebold acquired Global Election Systems in September 2001.) Although the AccuTouch tree is not an immediate ancestor of the AVTSCE tree (from the CVS logs, the AVTSCE tree is actually an import of another AccuTouch-CE tree that we do not have), the AccuTouch and AVTSCE trees are related, sharing a similar overall design and a few identical files. From the comments, some of the code, such as the functions to compute CRCs and DES, date back to 1996 and a company later acquired by Global Election Systems called "I-Mark Systems." The same DES key has been hardcoded into the system since at least the beginning of the AccuTouch tree.

While the system is implemented in an unsafe language (C++), the code reflects an awareness of avoiding such common hazards as buffer overflows. Most string operations already use their safe equivalents, and there are comments; for example, "should really use snprintf," reminding developers to change others.

While we are not prepared to claim that there are no exploitable buffer overflows in the current code, there are at the very least no glaringly obvious ones. Of course, a better solution would have been to write the entire system in a safe language, such as Java or Cyclone. In such a language, we would be able to prove that large classes of attacks, including buffer overflows and type-confusion attacks, are impossible assuming a correct implementation of the compiler and runtime system. Overall, the code is rather unevenly commented. While most files have a description of their overall function, the meanings of individual functions, their arguments, and the algorithms within are more often than not undocumented. An example of a complex and completely undocumented function is the CBallotRelSet::Open function (Figure 2) from TSElection/TSElectionSet.cpp.

This block of code contains two nested loops, four complex conditionals, and five debugging assertions, but no comments that explain its purpose. Ascertaining the meaning of even a small part of this code is a huge undertaking. For example, what does it mean for vgroup->KeyId() == -1? That the ID is simply undefined? Or perhaps that the group should be ignored? Such poorly documented code impairs the ability of both internal developers and external security evaluator to assess whether the code is functioning properly or might lead to a security issue.

An important point to consider is how code is added to the system. From the project's CVS logs, we can see that most recent code updates are in response to specific bugs that needed to be fixed. There are, however, no references to tracking numbers from a bug database or any other indication that such fixes have been vetted through any change-control process. Indeed, each of the programmers seem to have completely autonomous authority to commit to any module in the project. The only evidence that we have found that the code undergoes any sort of review comes from a single log comment: "Modify code to avoid multiple exit points to meet Wyle requirements." This refers to Wyle Labs, one of the independent testing authorities charged with certifying that voting machines have met FEC guidelines.

Virtually any serious software engineering endeavor will have extensive design documents that specify how the system functions, with detailed descriptions of all aspects of the system, ranging from the user interfaces through the algorithms and software architecture used at a low level. We found no such documents in the CVS archive, and we also found no references to any such documents in the source code, despite references to algorithms textbooks and other external sources.

There are also pieces of the voting system that come from third parties. Most obviously, a flaw in the operating system, Windows CE, could expose the system to attack since the OS controls memory management and all of the device's I/O needs. In addition, an audio library called "fmod" (http://www.fmod.org/) is used. While the source to fmod is available with commercial licenses, unless this code is fully audited, it might contain a backdoor or an exploitable buffer overflow. Because both the operating system and fmod can access the memory of the voting program, both must be considered part of the trusted computing base (TCB) as a security vulnerability in either that could compromise the security of the voting program itself. The voting terminal's hardware boot instructions should likewise be considered part of the TCB. Due to the lack of comments, the legacy nature of the code and the use of third-party code and operating systems, we believe that any sort of comprehensive, top-to-bottom code review would be nearly impossible.

Not only does this increase the chances that bugs exist in the code, but it also implies that any of the coders could insert a malicious backdoor into the system without necessarily being caught. The current design deficiencies provide enough other attack vectors, however, that such an explicit backdoor is not required to successfully attack the system. Regardless, even if the design problems are eventually rectified, the problems with the coding process may well remain intact.

Since the initial version of this paper was made available on the Internet, Diebold has apparently "developed, documented, and implemented a change control process" (http://www.dbm.maryland .gov/SBE/). The details of this revised process have not been made available to the public, so we are unable to comment on their effectiveness.

While the code we studied implements a full system, the implementors have included extensive comments on the changes that would be necessary before the system should be considered complete. It is unclear whether the programmers actually intended to go back and remedy all of these issues as many of the comments existed, unchanged, for months, while other modifications took place around them. Of course, while the AVTSCE code we examined appears to have been the current codebase in April 2002, we know nothing about subsequent changes to the code. (Modification dates and locations are easily visible from the CVS logs.) These comments come in a number of varieties. For illustrative purposes, we have chosen to show a few such comments from the subsystem that plays audio prompts to visually impaired voters.

• • Notes on code reorganization:
• /* Okay, I don't like this one bit. It's really tough to tell where m AudioPlayer should live. [...] A reorganization might be in order here. */
• • Notes on parts of the code that need cleaning up:
• /* This is a bit of a hack for now. [...] Calling from the timer message appears to work. Solution is to always do a 1ms wait between audio clips. */
• • Notes on bugs that need fixing:
• /* Need to work on exception *caused by audio*. I think they will currently result in double-fault. */

There are, however, no comments that would suggest that the design will radically change from a security perspective. None of the security issues that have been discussed in this paper are pointed out or marked for correction. In fact, the only evidence at all that a redesign might at one point have been considered comes from outside the code: the Crypto++ library (http://www.eskimo.com/~weidai/ cryptlib.html) is included in another CVS archive in cvs.tar. However, the library was added in September 2000, before the start of the AVTSCE AccuVote-TS Version 4 tree, and appears to have never been used. The subsequent SAIC (http://www.dbm.maryland.gov/SBE) and RABA (http://www.raba.com/press/TA_Report_AccuVote.pdf) analyses report that many of the problems we identify are still applicable to recent versions of the AccuVote-TS system, implying that, at least up to the version that SAIC and RABA analyzed, there has not been any radical change to the AccuVote-TS system.

DDJ