Re: [EILeg] Cascading Audits

From: Ronald Crane <voting_at_lastland_dot_net>
Date: Fri Dec 15 2006 - 01:24:55 CST

On Thu, 14 Dec 2006 14:51:17 -0600, JerryLobdill wrote
> [snip]

I have not engaged in any personal characterizations here. Pleasefollow suit.

> Your portrayal of yourself as a math challenged person induced me tospend the better part of half a day preparing the tutorial you requested. <

Please read the messages on that topic again. I indicated that Iwould feel better about supporting audited PCOS (as opposed to 100% HCPB) ifthere were a tutorial available on that topic so that the general public couldbetter understand the audit process -- ideally so that it could understand theentire thing. You commendably responded with a tutorial that you asked me toreview. In your response to my review, you indicated that you had gathered frommy comments that I was "math challenged." In partial response, Iindicated that I was "only moderately math-challenged" and can plowthrough the probability theory necessary to verify whether an audit scheme is properly-constructed.(Though I am a bit rusty on probability, and need to hit the books again.)

> Then you wanted to kibbitz even the writing style of that. <

If you don't want review, please don't ask for it. If you want alimited review, say so up front. Your note accompanying your tutorial papersaid:

I'dlike your opinion of the level of detail in this paper and
whatever comments or recommendations you may have.

Itwas clear from your followup to my comments that you didn't want stylecomments, so I haven't sent any more. It's also clear from that and from yourcomments just above that you never wanted style comments. You should have saidso, rather than inviting "whatever comments or recommendations [I] mayhave," and then criticizing me for sending them.

> You haven't responded to that paper in itsfinal form. <

You never posted it here or to me privately, as far as I can tell.Maybe there's a bug in my mail system, but I couldn't find it just now either.

> Now you seem to be responding to Ben† Adida in the manner ofsomeone who has a hell of a lot more extensive knowledge than you hadpreviously implied.† <

Maybe you've pigeonholed me a little too quickly.

> In order that I may know more about what to expect from you in the way oftechnical expertise would you please give me a bit of background onyourself?† <

I'm not sure that it's meaningful to do so. I prefer to correspondon the basis of the quality (or lack thereof) of my work and not on the basisof credentials, though occasionally I have provided them. But since you asked,I am a lawyer admitted to the California Bar. I am also a (somewhat lapsed) softwareengineer. My experience is in the design and implementation of secure operatingsystems (I was an engineer on Steve Lipnerís VAX/SVS team, for those who care),in device drivers, embedded systems, and hardware debugging. I also have experiencein (something of a) distributed system and on many facets of optimization. Someof my software used to help protect a commercial nuclear power plant from terrorists,and still might for all I know.

> See other comments below [beware: multiple levels]

>> [snip]Overkill is not present in my proposal.† You simply assert thatit is without any technical argument. Your argument is based on what electionadministrators want, and that is not a proper stance to take.† < >
> Every proposal for election reform has both technical and practicalaspects. While it is certainly technically defensible -- in terms of maximizingthe likelihood of discovering fraud -- to hand-recount an entire county if asingle precinct exhibits a miscount, such a recount can involve a great deal ofeffort. This possibility will, in turn, motivate some officials to oppose suchan audit proposal, or to shortcut its execution should it actually become law.Imagine you're LA County's ROV, and that the initial audit discovered a 3-votemiscount in one precinct. Under your plan, you'd be faced with hand-recountingover 5,000 other precincts. That's a big, expensive, time-consuming job, andit's not clear that it's justified.

> As usual, you are suggesting an extremeexample. If you are really so rigid in your thinking that you believe that myproposal would allow a single 3 vote miscount in one precinct to precipitate arecount of 5000 precincts you are way off base.† <

If you believe that personalcharacterizations improve your argument, or that they win friends and influencepeople, I have news for you: they do the opposite.

> Let me use your example in responding. Let's suppose that we are dealingwith a county-wide election in LA so that 5000 precincts are involved.†The margin in the race we are auditing is 2%. Suppose further that precinctsize variability and the assumed maximum vote switch percent are such that theminimum number of corrupted precincts that could produce the reversal is 50.Then the audit sample size would be 438 for a 99% confidence level.† Ifthe election was completely honest there would be no precincts that showed voteswitching in favor of the ostensible winner although there might be a number ofrandom errors due to causes not necessarily related to ballot definition filesor other software problems. <

Agreed so far. But it might be difficult to determine, withoutserious investigation, whether a given miscounted precinct was a victim of erroror of fraud.

> These errors can be expected to be small in number <

Probably, except that youíll see a variety of voter errors -- likenot properly filling in the bubbles on opscan ballots.

> and unbiased in their effect on the race. <

On average, but you might not find enough miscounted precincts to usetheir apparent bias (or lack of bias) to determine, without a fullinvestigation, whether they really resulted from errors or from fraud.

> During the audit of the 438 precincts we are looking for at least oneprecinct that has on the order of 7.5% to 20% of the votes switched from theloser to the winner (depending on our assessment of the audacity and anxiety ofthe attacker). <

Ah, I see how you're doing this. This clarifies things.

> Clearly, a 3 vote miscount would not satisfy that criterion. <

I agree, given your thresholding requirement (of which I wasnítaware). But a 15 vote miscount in a precinct of 500 registered voters with aturnout of 40% would satisfy it. I donít have the LA County precinct list tohand, but the average precinct size there is ~775, so there probably are some500-person precincts, and turnouts of 40% are very common (there was a 33.6%turnout in CaliforniaísJune primary.

> However, if one such (7.5-20%) corrupted precinct does show up in the438, the probability that this kind of error is an innocent one is less than0.1%. Why do I say that? (I'm sure you'll ask.)† What do you suppose theprobability is that only one precinct out of 5000 would have this percent ofvotes switched from the announced loser to the announced winner? 1/5000?1/10,000? You'll have a hard time arguing that there's a greater than 1/5000probability of this happening by random error.† So let me admit 1/5000 forthis number. <

I donít really have a good feeling (let alonequantitative data) for how often we should expect a 7.5%-20% switch due toerror as opposed to fraud. It depends upon the kind of voting systems in use(could vary from precinct to precinct), the procedures in use, the pollworkers'expertise and training, the partisan makeup of the voters (e.g., if an errorswitches Libertarian votes to the GOP, it'd make a real difference only inprecincts that have significant numbers of Libertarians), and probably lots ofother factors. Choosing a 1/5000 chance of a miscount being due to error seemswholly arbitrary.

But I donít follow what youíre saying. You seem tobe confounding the probability of error v. fraud and the probability of findingmore than one precinct exhibiting error or fraud.

> Given that frequency of occurrence of this specific kind of error, theprobability of there being one incidence in the 438 precincts audited is438/5000x1/5000. That's 0.00001752 or 0.001752%.† <

Iím not sure what youíre getting at. I think that wewant to calculate the probability (having found a single miscounted precinct ina sample of 438) that the 5000-438 others will not contain any further miscountedprecincts. The presence of a single miscounted precinct in a random sample of 438,of itself and with no more information, seems to indicate a probability of1/438 of miscounting (That itís from a sample of 5000 probably is relevant, butI donít know how to handle that at the moment. Please correct my calculations ifyou know how.). Thus, the probability that the remaining 4562 precincts woníthave any miscounted precincts then would seem to be (1-1/438)^4562 = 3x10^-5,which is very small. But whatís the probability that thereíll be 1, 2, 3, Ömiscounted precincts in the remainder? Letís plot the distribution:

1 precinct †= ((1-1/438)^4561) * (1/438)^1 * nchoosek(4562, 1) = 3.1x10^-4

2 precincts = ((1-1/438)^4560)* (1/438)^2 * nchoosek (4562, 2) = 0.0016

3 precincts = Öyou get the idea Ö †= 0.0056

4 precincts = 0.014

5 precincts = 0.03

6 precincts = 0.05

7 precincts = 0.08

8 precincts = 0.10

9 precincts = 0.12

10 precincts =0.124

11 precincts =0.117

12 precincts = 0.10

13 precincts =0.08

14 precincts = 0.06

15 precincts =0.04

16 precincts = 0.03

17 precincts = 0.017

18 precincts = 0.01

19 precincts = 0.0053

20 precincts = 0.0028


49 precincts =3.09x10^-18†

So, under your plan, we would recount 4562 precinctsto find, on average, only 10 miscounted ones. Given that we assumed that anattacker would have to flip 50 precincts to flip the election, and that P(50miscounted precincts: the first one plus 49 more) is ~3x10^-18, this seems to bea waste of time in terms of detecting election-flipping fraud. Itís still usefulin investigative terms, and, given unlimited resources, Iíd sure like to do it, but we don't have that.

Again, please correct me if Iíve made a mistake. Iam a little rusty at probability.

>> Los Angeles County has about 5,000 precincts.Requiring a full recount of that county when something goes wrong in a singleprecinct would be massive overkill. The cascading audit is much moreeconomical, yet still gives us an excellent (p=0.99) chance of detecting atleast one additional miscounted precinct if any such precincts exist. Inconsequence, I think that it would be much more acceptable to officials, andthus more likely actually to make it into law.

> > As seen through the eyes of officials--who don't ever want to do arecount under any circumstances.
I am not here to defend unreasonable officials, but to contrive the bestlegislative proposal I can that satisfies principle and technical requirements,and that I believe has a reasonable chance of actually being enacted.

>...Any corrupted precinct precipitates a full hand recount IN THAT COUNTY. Thereason for this is that a wholesale attack is not spread from county to countyor from the state level to the counties. It is launched independently in eachcounty in which it appears.† < > >
> > This is incorrect. A wholesale attack easily can originate at avendor or at one of a vendor's suppliers, and can therefore affect anyjurisdiction using the affected machines -- potentially the entire nation.

> > Typically it would originate at a county election administrationoffice. Most candidates would not have the inside contacts to attack throughthe vendor.† <
It is entirely possible than an attack originates with a partisan and not acandidate. It is entirely possible that a person or a few people working at avendor (or vendorís OEM) wish, for whatever reason, generally to improve thechances of all candidates belonging to party X, or all candidates belonging toparty X who also are running for specific offices, etc. As described in the Brennan Center's report on voting systemsecurity, it would take only a few (1-3) conspirators to mount most suchattacks. Further, conspirators might be able to parameterize their attacks byembedding commands in ballot definition files or using ďcryptic knocksĒ (Brennandiscusses these two) or by sending commands over network connections or thepower lines (should voting systems have the necessary hardware). Then there arethe ever-present ďpatchesĒ that officials often violate the law to apply.

> They would most likely attack through the contacts they have in theelection district and that would mean that each county's system would have tobe attacked independently. It's, of course, possible that the trojan horse couldbe inserted into a new version of GEMS software (or its equivalent) certifiedby the SoS for use in the state at the precise time required to affect theelection,† <
Parameterized attacks (please read the Brennan Center's report on this) aremuch more flexible than this.

> and therefore promulgated to all users of the vendors' machines. If thatunlikely event happened my audit procedure would catch it anyway, so yourargument is of no effect.† <
It would catch it, but with overkill.

> > There is no overkill. Why don't you tell us why your idea ismathematically supportable.

Gladly. When I have worked it out, Iíll post it hereas I said earlier.

> > ...In my paper I did not specifically debunk the idea that thehypothesis being tested in my audit plan to a 99% confidence level would needfurther supporting auditing before a sufficient level of confidence was reachedto order a recount.† No one had specifically made such a claim at the timeI wrote the paper.† However I did say this: "It is extremely importantto avoid legal language that gives election officials the power to emasculatethe mandatory audit process."

I completely agree with the last sentence. Audits should be mandatory andfully governed by law so that officials are prohibited from short-circuitingthe process. (Of course, this doesnít necessarily prevent officials from doingso, but lawyers (we can be useful) can craft language to help minimize thesekinds of problems).†

>> In my latest paper, written at your suggestion, and I hope by now it isavailable in the files on the EI Leg website, I said,

Ah, thatís where it is. I donít check that site veryoften, since, as of the last time I checked (last week), very little was postedthere.

†>> ÖIf one follows your prescription of cascading audits it appears that youend up auditing all precincts. Isn't that a full recount?† You don't saywhat would prevent that from happening or what the statistics are on eachiteration or why whatever the confidence level is, it's never enough. †<

You could end up auditing all the precincts, andyes, thatís the equivalent, in all but name, of a full recount. But I approachthe process incrementally, re-evaluating at each round of audits whether itísworth spawning another round (the current round found at least one miscountedprecinct) or not (the current round found no miscounted precincts, thus givingus P=0.99 that there arenít enough remaining miscounted precincts to flip theelection).

Of course this needs more solid mathematicaljustification than Iíve given so far, but I noted that when I first proposedit.



OVC-discuss mailing list

= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
Received on Sun Dec 31 23:17:14 2006

This archive was generated by hypermail 2.1.8 : Sun Dec 31 2006 - 23:17:16 CST