Ping ([info]zestyping) wrote,
@ 2007-12-21 21:00:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
The dissertation.
If you're interested, my dissertation is available on my website and also in the Berkeley EECS Technical Reports archive.

Here is the abstract:
I examine the question of how to design election-related software, with particular attention to the threat of insider attacks, and propose the goal of simplifying the software in electronic voting machines. I apply a technique called prerendering to reduce the security-critical, voting-specific software by a factor of 10 to 100 while supporting similar or better usability and accessibility, compared to today's voting machines. Smaller and simpler software generally contributes to easier verification and higher confidence.

I demonstrate and validate the prerendering approach by presenting Pvote, a vote-entry program that allows a high degree of freedom in the design of the user interface and supports synchronized audio and video, touchscreen input, and input devices for people with disabilities. Despite all its capabilities, Pvote is just 460 lines of Python code; thus, it directly addresses the conflict between flexibility and reliability that underlies much of the current controversy over electronic voting. A security review of Pvote found no bugs in the Pvote code and yielded lessons on the practice of adversarial code review. The analysis and design methods I used, including the prerendering technique, are also applicable to other high-assurance software.
It turned out bigger than i expected — 324 pages — but don't let that scare you. That includes 14 pages of front matter, 10 chapter cover pages, 11 pages of bibliography, 102 pages of appendices (31 of which are source code), and 5 pages of the GNU FDL. In short, 182 pages of content and 142 pages of fluff. The content is broken up into little sections in an attempt to make it easier to read.

Many people contributed to the work. The more i learned about things that other graduate students have had to deal with, the more i realized how lucky i was to have Dave Wagner and Marti Hearst as advisors — they got back to me quickly, read drafts carefully, and had lots of well-thought-out and constructive comments to offer. Candy Lopez showed me around the election office in Contra Costa County and patiently explained to me how everything was done in real life. Noel Runyan and Scott Luebking taught me about accessibility, and i appreciate their advice very much even though the dissertation doesn't address accessibility as much as it could; the research didn't include user testing with disabled voters. Matt Bishop, Ian Goldberg, Yoshi Kohno, Mark Miller, Dan Sandler, and Dan Wallach volunteered a huge amount of time to review my source code. Joe Hall has been a great help on questions about election law and policy.

The type is Lucida; i chose it because it has a harmonized family of serif, sans-serif, and fixed-width typefaces. Alas, the original Lucida fonts are unkerned (and the word "Voting" shows up a lot, which makes the lack of kerning more obvious), so i added some kerning pairs by hand. The page design is inspired by Scott Kim's thesis on Viewpoint — he also used Lucida and a wide left margin for small figures and illustrations. It looks like his left margin was chosen to match the first of three equal columns, which would occasionally be used for three equal-sized figures. I moved the left margin so that the vertical edge divides the page in the golden ratio. Just because.

If you're curious about the topic of electronic voting, please check it out. I hope you find it interesting.

Update: Pvote has a website where you can get the source code and documentation, as well as a sample ballot definition file. Also on that site is the assurance document, which is the specification that was used for the Pvote security review, and a report on the results of the security review.


(Post a new comment)


[info]metamouse
2007-12-22 08:42 am UTC (link)
I so appreciate the care you apply to details.

(Reply to this)

No small accomplishment
(Anonymous)
2007-12-22 04:37 pm UTC (link)
Congratulations. I have followed your work for some time and it truly is some of the most promising research in the field. Best of luck to you.

(Reply to this)

Congratulations
(Anonymous)
2007-12-23 06:55 pm UTC (link)
Congrats Ping!

What I've seen reads very clearly and concisely, especially with the small sections. I love to see such solid work presented in such an accessible way!

(I love the font and incorporation of the golden ratio too :)

(Reply to this)

Unimpressed...
(Anonymous)
2007-12-23 08:24 pm UTC (link)
Errr... I want to say this as politely as possible:

You may have only 460 lines of python code, but you have gazillion lines of dependent code beneath your python script, both python library code, c application code, c kernel code, c device driver code, BIOS/ROM code. Now due to the nature of open source systems, in the next election your same 470 lines of python code will probably run on a different set of hardware and whats even worse, a completely different set of system configurations: python libraries and library dependencies. How on earth can you think your 470 lines of code will work without a side effect in exactly the same way in today's open source environments?

Even if you freeze one software configuration, you have a long way to go: there are simply too many dependent methods involved. The only way around that is the reduction of source code dependencies, so that every function in a code can be proved by using formal proofs such as Floyd-Hoare logic. That's the way software in planes is been verified. In your scenario you would have to prove that every dependent API method you are calling works according to spec. Which is the spec btw?

I also see no points mentioning tinkering and manipulation of machines.

I am utterly unimpressed. I can't believe anyone can actually get away with such in a dissertation.

(Reply to this) (Thread)

Re: Unimpressed...
[info]zestyping
2007-12-23 09:56 pm UTC (link)
I invite you to read Chapter 9. It was written specifically to address the set of concerns you express here.

One piece of the argument is that, in every security-critical system, there's an important distinction between application-specific components and general-purpose components. In this case, Pvote's 460 lines constitute the voting-specific trusted software, in direct contrast to the tens or hundreds of thousands of lines of voting-specific trusted software in the Diebold or Sequoia machines.

The specification of the underlying platform is given in the Pvote Assurance Document.

(Reply to this) (Parent)

Comments?
(Anonymous)
2007-12-24 05:40 am UTC (link)
Very nice work. It would be a lot easier to browse the source code if you commented your code though. Why not add your source code notes from the paper as doc strings and comments?

(Reply to this)

the best joke
(Anonymous)
2007-12-29 05:23 pm UTC (link)
>Unlike Windows CE and MFC, Python is a mature open source project,
>distributed with an extensive suite of regression tests.

Hahahaahaa... Python is more "mature" than Windows CE. Especially since python releases are always coming out at a constant rate and always changing.. A completely moving target. Lets re-proove correctness for every SVN HEAD snapshot every day.. And MFC is quite a fixed target for which every windows developer in the world has the complete corresponding sourcecode with his copy of Visual Studio.

(Reply to this) (Thread)

Re: the best joke
(Anonymous)
2007-12-31 10:46 pm UTC (link)
Maybe you're focusing on the wrong thing, here... instead of focusing on "mature", how about "open source" and "extensive suite of regression tests"... makes more sense, no?

(note: I really don't know if WinCE and MFC comes with a full suite of regression tests - does it? don't see why they would...)

I've been using Python professionally for about 8 years now, and have migrated a non-negligible amount of code several times (1.5 -> 2.2 -> 2.3 -> 2.4) with almost no issues, ever... not bad for something that is constantly changing :-)


(Reply to this) (Parent)(Thread)

Re: the best joke
(Anonymous)
2008-01-04 12:54 am UTC (link)
Hmm.. Python is a great language for common programming tasks. But its also the language that changes its semantics if you (wrongly) reindent the code. Its also the programming language where a member variable of a class could exist depending on the program flow. Its very dynamic by design .. and also -thankfully- strongly typed.

(Regression) testing? Software testing != Software verification. If you promote reliability, you want to verify the whole darn code. Hoare calculus. Not PyUnit.

(Reply to this) (Parent)

Cool!
(Anonymous)
2008-01-01 02:26 pm UTC (link)
This is one genius piece of work. I read all of the dissertation and I have no doubt that you will get that PhD in no time.

Good luck

(Reply to this)

Great work
[info]nlgordaz
2008-03-12 10:01 pm UTC (link)
Hello Ping,
I commend you for your efforts to design election-related software. I am a political science undergrad at the University of Arizona and the issue of voter fraud and/or ineffective voting machines is paramount in the political science field today. While I live in Arizona right now, I am originally from Northern California. I know that some counties in California have completely abandoned electronic voting due to various failures in implementing a working and reliable system. It is incredible to me how in the 21st century we are still dependent on the old, punch-card voting systems, which are highly inefficient and unreliable. These old system leave the us very vulnerable to voting fraud and malfunction. I was actually working with a Tucson website design firm that was considering attacking the issue of electronic voting systems due to the HUGE demand for such a system in Arizona.
Best,
Lane - Tucson Website Hosting

(Reply to this)

dNqqAmFziDNgChZ
(Anonymous)
2008-09-28 01:16 am UTC (link)
It's funny goodluck

(Reply to this)


Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…