WEBVTT 00:00.000 --> 00:01.940 Hi, I'm Philip Stark. 00:01.940 --> 00:05.160 Thank you for coming to this virtual talk. 00:05.180 --> 00:07.780 I'm going to talk about testing ballot marking devices. 00:07.780 --> 00:15.900 This is joint work with an undergraduate student, Ron Shi, who visited Berkeley for the last year and did some research with me. 00:16.980 --> 00:19.320 Why do we need to test ballot marking devices? 00:19.320 --> 00:24.920 Well, they can print votes that differ from what the voter saw on the screen or heard through the audio interface. 00:25.020 --> 00:33.320 The idea of voter verifiability is not really refined enough to capture the security properties that we need in a voting system. 00:33.480 --> 00:44.560 In particular, the ability to catch an error and spoil the ballot and request another opportunity to vote isn't enough to make ballot marking devices safe voting technology. 00:44.580 --> 00:47.140 For example, recent research by Bernard et al. 00:47.140 --> 00:54.860 showed that only 7% of voters notice errors that ballot marking devices have introduced into the printout. 00:55.760 --> 01:03.400 In effect, the security properties of paper are undermined by using ballot marking devices to mark the paper. 01:04.160 --> 01:07.200 There's a problem with the BMD security model in general. 01:07.200 --> 01:13.380 It basically makes voters responsible not only for their own errors, but also for the overall security of the system. 01:13.380 --> 01:16.200 But they don't give voters the tools they need to do that job. 01:16.200 --> 01:24.080 In particular, there's no way for a voter to present any other party, including an election official, with evidence that a BMD misbehaved. 01:24.800 --> 01:37.060 So if a voter complains to a local election official, there's no way for the election official to know whether the complaint reflects an actual malfunction, a voter error, or a cry of wolf trying to undermine the trust election. 01:37.340 --> 01:42.660 As a result of that error or malfeasance could change a lot of votes without raising any kind of alarm. 01:43.180 --> 01:53.660 A number of proponents of BMDs claim that they have benefits such as preventing overvotes, warning about undervotes, eliminating the possibility of ambiguous marks. 01:53.940 --> 01:56.420 I think that there's problems with those arguments. 01:56.420 --> 02:00.280 In particular, they assume that ballot marking devices function correctly. 02:00.280 --> 02:07.460 And there are many recent examples of failures on a wide scale, including in the state of Georgia, Northampton, Pennsylvania, and in Los Angeles. 02:08.440 --> 02:12.380 Precinct count optical scan systems can also protect against overvotes and undervotes. 02:12.380 --> 02:15.400 In fact, that's required under BBSG 1.0. 02:15.700 --> 02:21.360 So how can we figure out whether ballot marking devices actually worked adequately in a given election? 02:21.360 --> 02:28.860 We need to know that whatever errors occurred weren't numerous enough to change the outcome of any contest in the election. 02:28.900 --> 02:32.580 Three different approaches have been proposed to testing ballot marking devices. 02:32.620 --> 02:41.340 One is pre-election logic and accuracy testing, where you look at a machine before election day, run some test patterns through it, and verify that it prints the right thing. 02:41.560 --> 02:52.840 Another approach is passive testing, where you look at something like the spoiled ballot rate and try to detect anomalously high rates of spoiled ballots as a possible signal that the machines are misbehaving and voters are catching it. 02:53.000 --> 03:09.400 And the third approach is parallel or live testing, where testers periodically throughout the day, on election day, or during early voting period, will mark some ballots but not cast them, and verify that what's marked on the printout matches what their intent was. 03:09.440 --> 03:14.000 And the point of our research is to show that none of these, in fact, work in practice. 03:14.380 --> 03:16.580 Now, how much testing do we really need to do? 03:16.580 --> 03:28.260 That depends on how big a problem would make a material difference, and I have argued a long time that a sensible threshold for materiality is enough to change the reported winner of one or more contests. 03:28.260 --> 03:33.500 That is, we'd like to have high confidence that whatever errors occurred, they didn't alter who won. 03:33.740 --> 03:35.420 Many contests in the U.S. 03:35.420 --> 03:39.420 are decided by less than one percent, even statewide contests. 03:39.420 --> 03:53.280 For example, in 2016 presidential election, the margin in statewide contests in Michigan, Rhode Island, Pennsylvania, and Wisconsin were all under one percent, with Michigan being as low as 0.22 percent. 03:54.100 --> 04:01.220 Now, I'm going to frame this as a two-person adversarial game and think about what strategies are available to the two players. 04:01.220 --> 04:06.700 So the evildoer is Mallory, who's trying to alter the outcome of one or more contests in an election. 04:06.800 --> 04:08.580 Mallory doesn't want to be detected. 04:08.580 --> 04:11.160 The point of this isn't to cast fear, uncertainty, and doubt. 04:11.160 --> 04:13.740 It's to get away with altering an election outcome. 04:14.100 --> 04:21.340 Mallory knows how the ballot marking devices will be tested in general because that will be a matter of public record. 04:21.340 --> 04:24.240 That is an action taken by the local election official. 04:25.800 --> 04:30.840 So Mallory knows the state history of the machine. 04:31.320 --> 04:39.440 Mallory knows how voters are interacting with it and knows what votes have been cast earlier in the day, how long each voting session took, and so on. 04:40.020 --> 04:51.020 And Mallory has a good model of voter behavior because Mallory can basically install spyware on voting machines and keep track of how voters interact with those machines in previous elections and on into the future. 04:51.560 --> 04:53.580 In contrast, Pat is our tester. 04:53.580 --> 04:59.380 Pat is trying to make sure that any ballot marking device problem that alters one or more outcomes will be detected. 04:59.800 --> 05:04.220 In contrast to Mallory, Pat has to obey the law, has to protect voter privacy. 05:04.520 --> 05:09.340 Pat doesn't know which contest Mallory will attack nor the strategy Mallory is going to use to attack them. 05:09.340 --> 05:11.520 So this is a very asymmetric problem. 05:12.440 --> 05:24.700 All right, so because the threshold for materiality depends on the number of votes that it takes to alter an election outcome, it's important to keep track of how big or how small elections are in the United States. 05:24.840 --> 05:34.520 The median turnout by county in 2017, not 3017, oh sorry, in the 3017 U.S. 05:34.520 --> 05:39.340 counties that there are in 2018 was a little under 3,000 voters. 05:39.740 --> 05:44.540 There are fewer than 43,000 voters in more than two-thirds of U.S. 05:44.540 --> 05:45.620 jurisdictions. 05:45.980 --> 05:53.560 And in 73 percent of states, more than 50 percent of counties have fewer than 30,000 active voters. 05:53.560 --> 06:02.020 That is, the median size of turnout in a county is 30,000 voters or fewer. 06:02.280 --> 06:06.280 In 92 percent of states, that number is 100,000. 06:06.280 --> 06:11.040 That is, more than 50 percent of counties have fewer than 100,000 active voters. 06:11.140 --> 06:15.000 In 2019, only 317 U.S. 06:15.000 --> 06:21.960 cities had populations of 100,000 or more out of more than 19,000 incorporated places. 06:21.960 --> 06:38.260 So if about 80 percent of the population is a voting age and turnout is about 55 percent, which is roughly what it's been historically, then contests for elected officials in something like 98 percent of incorporated places involve fewer than 44,000 voters. 06:38.260 --> 06:49.160 So we need to think about ways of testing things on contests that involve fewer than 44,000 voters, and many contests will involve even, you know, fewer than 3,000 voters. 06:49.280 --> 06:53.460 The 2019 median population of U.S. 06:53.460 --> 07:02.060 incorporated areas is about 725, so about 50 percent of incorporated places have a turnout of less than 320 voters. 07:03.160 --> 07:13.140 All right, this is just to give an idea how much of the country has a median turnout, had a median turnout in 2018 of less than 30,000 voters. 07:13.140 --> 07:15.640 It's most of the country by area. 07:16.180 --> 07:18.040 So what's Mallory's strategy space? 07:18.040 --> 07:22.760 How can Mallory figure out which transactions or what votes to try to alter? 07:23.040 --> 07:39.660 Mallory basically can pick based on a very large number of state variables in the ballot marking device, the time of day, how long the wait was between voters, how many people have voted on the machine already, how does this particular voter interact with the machine, 07:39.660 --> 07:55.900 including the selections, what contests the voter ignores, how many times the voter revises selections, how long the voter reviews things, whether the voter looks at every page of candidates in a contest, how long the voter reviews selections, inactivity warnings, 07:55.900 --> 08:07.240 BMD settings, font sizes, languages, whether the voter uses the audio interface, the sip and pop interface, all of these things are available to a maldoer, to Mallory, to try hack the election. 08:07.820 --> 08:14.260 Now here are some examples of just how many different possible voting transactions there are. 08:14.520 --> 08:16.560 I'm giving two columns of numbers. 08:16.560 --> 08:20.020 The more realistic number is pretty realistic in the United States. 08:20.200 --> 08:29.100 Many jurisdictions have ballots that contain 20 or more contests, but we're going to use three as basically a lower bound. 08:29.440 --> 08:44.660 And similarly, you can look at different variables that Mallory could use to target these things, from the number of candidates per contest, time of day, number of people that voted, time for selection, the settings that the voter uses, the contrast and saturation of the screen, 08:44.660 --> 08:48.360 font size, audio use, tempo, volume, and so on. 08:48.360 --> 08:57.660 So conservatively, there's on the order of six million different combinations of settings that are likely to have some reasonable probability of being used. 08:58.140 --> 09:05.560 More realistically, there's something over 10 to the 47th, a truly staggering number of possible voting transactions. 09:05.560 --> 09:14.680 There's no way to probe even a microscopic fraction of those using testing, either pre-election logic accuracy or live testing. 09:15.420 --> 09:16.980 So what can Pat do? 09:16.980 --> 09:18.500 That's what Mallory can do. 09:18.500 --> 09:31.260 Pat can monitor voter behavior in a non-invasive, non-privacy invading way, in particular can look for ballot rates, and Pat can try to catch a malfunction by using the BND before, during, or after an election. 09:31.260 --> 09:35.960 That is, doing logic and accuracy testing, or live testing, or post-mortem. 09:35.960 --> 09:40.020 So Pat really does have to test at random in some way. 09:40.020 --> 09:55.880 If Pat tests in a way that's predictable, such as once an hour, or pulls only one machine aside and tests it, or tests only some combinations of votes, only interacts with the machine in some particular way, then because Mallory knows what Pat's strategy is, 09:55.880 --> 09:59.960 Mallory can just avoid changing those transactions and hide. 10:01.220 --> 10:05.040 Similarly, Pat can't just set aside machines on election day for live testing. 10:05.040 --> 10:12.100 Pat needs to test the machines that are actually in use, or malware could detect that the machine is being used in a way that is not typical of voters. 10:13.120 --> 10:23.060 And moreover, because there are so many possible combinations of settings, combinations of ways of transacting a vote, uniform random sampling is doomed. 10:23.060 --> 10:38.020 You really do need to sample more often from those transactions that voters are going to use more often in order to have a reasonable chance of sampling at least once from any set of transactions that contain enough votes to alter the outcome of one or more contests in the election. 10:38.540 --> 10:40.960 So ideal sampling would mimic voter behavior. 10:40.960 --> 10:43.780 It would basically sample from what voters actually do. 10:44.380 --> 10:46.640 So we're going to look at exactly that. 10:46.640 --> 10:58.120 Suppose we could mimic voters perfectly, how many transactions would we actually need to use as tests in order to have a good chance of detecting outcome-changing errors or alterations. 10:58.500 --> 11:11.120 So it's important to know that in a jurisdiction-wide contest, changing the votes on 1% of transactions can typically change the margin by 2%, but if there's undervotes, you can change it by even more than that. 11:11.120 --> 11:19.440 And if the contest is only on a fraction of ballots cast in the election, then you don't need to change even that large of a percentage to change a margin by a much larger percentage. 11:19.440 --> 11:32.400 For instance, if you have a contest that's only on, that only 1 in 10 voters is eligible to vote in, and the undervote rate is 30%, then changing the votes on 1% of transactions could change the margin in that contest by 29%. 11:32.400 --> 11:33.940 That's a lot of leverage. 11:34.940 --> 11:40.260 So passive testing relies on voters noticing errors and spoiling their ballots. 11:40.600 --> 11:55.440 Now in order to know how large a spoilage rate is enough to sound an alarm, we have to have a good idea of how often voters spoil ballots when the machines are functioning correctly, and then we have to know how often they will notice errors if errors happen, 11:55.440 --> 12:03.600 and whether they will report those errors and thereby, you know, request a new ballot and trigger an alarm. 12:03.660 --> 12:10.440 Problem is that kind of training data is unlikely to be available in part because you can't step on the same election twice. 12:10.580 --> 12:21.280 There are all kinds of differences from election to election that are likely to change the spoiled ballot rate, including complexity of the ballot, ballot layout, complexity of the social choice functions, and so on. 12:21.660 --> 12:27.020 So how do we set a threshold for one to sound an alarm if we're using passive auditing, passive testing? 12:27.780 --> 12:34.560 It's going to depend in part on the number of transactions Mallory alters, which votes are affected, which contests are affected, and so on. 12:34.560 --> 12:36.260 And Pat is not going to know any of these things. 12:36.260 --> 12:42.920 Pat needs to test in a way that is going to be sensitive enough to changing the outcome of any contest whatsoever. 12:43.600 --> 12:56.300 So let's make some really optimistic assumptions and work through the numbers and figure out just how much testing Pat would have to do or how many voters would have to be voting in the particular contest so that a change in their spoiled ballot rate would be noticed. 12:56.400 --> 13:05.920 But let's assume in particular that the spoiled ballot rate follows a spoiled ballots follow a Poisson distribution with a known rate if there's no hacking and a different known rate if there is hacking. 13:05.920 --> 13:09.560 Now there's no reason to assume that except it's a common model for things. 13:09.560 --> 13:11.100 This is really just a thought experiment. 13:11.100 --> 13:18.400 It's not intended to be a realistic model of how voters detect and spoil ballots. 13:18.420 --> 13:25.360 We're going to look at contest margins of one to five percent and false positive and false negative rates of five percent and one percent. 13:25.360 --> 13:29.120 So a false positive rate is saying that there's a problem when there really isn't one. 13:29.120 --> 13:35.080 A false negative rate is failing to notice that there's a problem when in fact one or more outcomes have been altered. 13:35.260 --> 13:37.140 Now here's kind of how it plays out. 13:37.140 --> 13:40.720 This is for five percent rate of false negatives and false positives. 13:41.120 --> 14:02.860 If you look at this, going across the top is the base rate of spoiled ballots when things are clean and then as you go from row to row you're really looking at what is the rate of errors in the printouts that would be required to reverse a margin of size one percent, 14:02.860 --> 14:05.320 two percent, three percent, on to five percent. 14:05.580 --> 14:08.880 The detection rate we're assuming is either seven percent or twenty-five percent. 14:08.880 --> 14:11.480 Seven percent is consistent with what Bernard et al. 14:11.480 --> 14:18.160 found in their study of actual voters in an experiment that wasn't an actual election. 14:18.760 --> 14:36.640 So if you look at this to have a five percent false positive and false negative rate, you'd need on the order of half a million ballots or more for a realistic rate of voters detecting errors and spoiling their ballots to protect against altering a contest with a margin of one percent. 14:36.740 --> 14:45.300 That number goes down as the margin gets wider, but as I've already argued there are a very large number of contests that are decided by one percent or less, important contests. 14:45.380 --> 15:03.160 If we make a more stringent threshold of requiring only a one percent rate of false negatives or false positives, then we would need on the order of a million voters or more in the contest in order to be able to detect an alteration to one percent to to enough ballots to alter to reverse a margin of one percent. 15:03.880 --> 15:10.460 So let's think about how big this number half a million or a million is in the context of actual elections. 15:10.460 --> 15:13.180 And so let's I'm going to use California as an example. 15:13.400 --> 15:22.300 41 of California's 58 counties had fewer than 100,000 voters in the 2018 midterm election, so passive auditing would not have worked for any of those. 15:22.300 --> 15:37.600 33 had fewer than 100,000 voters in the 2016 presidential election, so again passive auditing would not have given you an acceptably low false positive and false negative rate, even under these optimistic assumptions that everything follows a Poisson distribution with a known rate. 15:38.340 --> 15:47.260 So passive testing couldn't have protected contests with margins of three percent or smaller in those jurisdictions that have a hundred thousand or fewer voters. 15:47.620 --> 15:59.840 In many California counties turn out so small that there would be no way to detect problems through spoilage rates without having an unacceptably high rate of false alarms would be that invalidating elections left and right. 16:01.420 --> 16:25.660 Okay, so that analysis assumed that votes were being changed more or less at random, that every voter had some chance of having his or her votes altered, but in fact Mallory has access to information to use to target the attack against voters who are less likely to notice problems or less likely to spoil a ballot if there is a problem. 16:25.840 --> 16:52.680 In particular, Mallory could target voters with visual impairments, voters who are blind, that could, if such voters, current ballot marking devices don't provide such voters a technology to check whether the printout actually matches the voters intentions or what the voter was told on the audio output or on the screen in you know in a larger font size. 16:52.680 --> 17:05.500 So if two percent of voters have a visual impairment that would prevent them from checking the printout directly themselves, then Mallory could change the outcomes of jurisdiction-wide contests that have margins of four percent or more without increasing the spoiled ballot rate at all, 17:05.500 --> 17:10.780 because those voters would have no opportunity to notice that there was a problem in the printout. 17:12.540 --> 17:31.140 Voters that have some kind of motor impairments that make it difficult for them to, that limited dexterity that it makes it difficult for them to handle a piece of paper, some ballot marking devices have an accessibility feature that allows a voter to cast the ballot without actually handling it. 17:31.140 --> 17:39.320 In some cases those features don't even print the until the voter has said I want you to cast this for me after you print it. 17:39.320 --> 17:49.660 Now because that doesn't even give the voter the opportunity to look at the piece of paper, the ballot marking device can cheat with impunity on ballots like that. 17:49.660 --> 17:59.700 So if there are enough voters who are using this autocast feature, then relatively wide margins can be altered without any possibility of detection. 18:00.780 --> 18:16.500 Languages other than English voters, if a voter is looking at a ballot on screen in one language but then printing it out in English, the voter might be less likely to check the printout if that's if the voter is not so comfortable in English. 18:16.680 --> 18:38.880 Moreover, if a voter who is a, you know, clearly a native foreign language speaker reports a problem with a ballot, it might be the case that some poll workers would be less likely to believe that the voter actually detected a problem with the device and rather more likely to believe that the voter made a mistake. 18:40.280 --> 18:50.620 There's all kinds of things that Mallory can monitor to try to target the attack by looking at how much attention the voter is paying, whether the voter is in a hurry, whether the voter is reviewing selections and so on. 18:51.640 --> 18:57.160 All right, so there are other problems with passive testing. 18:57.160 --> 19:07.940 Among them, it becomes a really easy way to raise a thud attack through uncertainty and doubt by simply asking voters to spoil their ballots more often than casting doubt on the election. 19:08.720 --> 19:11.500 All right, so let's look at these oracle bounds now. 19:11.500 --> 19:25.480 Suppose that instead of relying on voters to run the tests, we have to, we're going to try something like parallel testing, active testing, or logic and accuracy testing, where we input test patterns and look at what comes out. 19:25.480 --> 19:42.780 So if we had perfect knowledge of voter behavior, that is if basically Pat could pick voters at random and look over their shoulders while they vote and see whether the printout matched what the vote was presented on the screen or in the audio output, 19:42.780 --> 19:52.420 that's kind of a best case scenario that doesn't involve Pat having to figure out the distribution of voter transactions with the BMD. 19:52.420 --> 20:11.560 So even under those circumstances, it takes a fair number of votes in order to, you have to spy on a fair number of voters, have to look over the shoulder of a fair number of voters to have a reasonable chance of noticing a problem in the election. 20:11.560 --> 20:32.360 So for instance, if Mallory alters 15 transactions in a contest that has a little under 3,000 voters, which was the 2018 median jurisdiction turnout, that could change the outcome of the contest by one percent or more, but Pat would need to look over the shoulder of at least 540 voters, 20:32.360 --> 20:35.240 about 18 percent of the capacity of the machine. 20:35.300 --> 20:41.100 That would involve testing each ballot marking device several times an hour, but once an hour would not be enough. 20:41.380 --> 20:56.020 If you're limiting things to once an hour for 13 hours a day, to have a 95 percent chance of catching a problem, you have to have over 6,500 voters in the contest, which is almost triple the median turnout in jurisdictions in the U.S. 20:56.020 --> 21:00.340 and 20 times the median number of active voters in incorporated areas. 21:00.420 --> 21:06.580 In reality, Pat can't shoulder serve, Pat needs to make a model of voter behavior, and that's got to be calibrated to data. 21:06.680 --> 21:14.420 That's going to require monitoring voters in extreme detail, all of the details I mentioned before in relating to voting transactions. 21:14.420 --> 21:20.000 That would compromise voter privacy completely and probably be illegal. 21:20.600 --> 21:28.000 Nonetheless, let's imagine that Pat had a budget of running an infinite number of tests using a particular model. 21:28.000 --> 21:37.920 How many voters would Pat need to observe in order to get a model that was accurate enough to detect an alteration to some fraction of the votes? 21:37.920 --> 21:57.500 To have 99 percent confidence of detecting a change to a half percent of the votes, even if Pat could conduct an infinite number of tests in order to model behavior well enough to detect things at that confidence level, would involve monitoring three and three-quarter million voters in excruciating detail. 21:57.500 --> 22:05.740 Of course, their behavior in one election might not match their behavior in another election, and many jurisdictions that you need to be monitoring aren't big enough. 22:05.740 --> 22:08.100 They just simply don't have that many voters. 22:08.540 --> 22:13.320 As you look at larger margins and lower confidence levels, that bound goes down. 22:13.320 --> 22:21.620 But even from 95 percent confidence of detecting alterations to five percent of the votes, you'd have to observe more than a million voters. 22:21.620 --> 22:23.680 These are very, very conservative bounds. 22:24.620 --> 22:34.540 If you had a test limit of 2,000 tests to conduct, then the number of voters you would need to observe, you need to have an even more accurate model, you would have to observe even more voters. 22:34.540 --> 22:43.540 So the message here is you really have to look at monitor a million voters in excruciating detail, at least in order to have a reasonable chance of picking up outcome-changing errors. 22:44.220 --> 22:47.060 All right, so the situation is really not very good. 22:47.060 --> 22:48.340 I mean, it's actually worse than this. 22:48.340 --> 22:53.260 Even if you were able to do that much testing, if you find a problem , the only remedy is a new election. 22:53.260 --> 22:57.760 You have no idea which transactions were altered, what the right outcome should be. 22:58.780 --> 23:00.880 Margins aren't known before the testing happens. 23:00.880 --> 23:09.000 If it turns out that the margin is smaller than you allocated testing for while the election was going on, there's no way to go back and fix that. 23:09.040 --> 23:16.620 The tests themselves have uncertainty, and that means that you really need to factor that in in deciding who really won. 23:16.620 --> 23:19.640 Is there really strong enough evidence that someone really won? 23:19.640 --> 23:23.580 If there's only a 95% chance you would have seen a problem that big. 23:24.140 --> 23:31.240 Moreover, this is going to require new systems, extra hardware, additional staff, and additional training. 23:31.240 --> 23:35.160 This is a very expensive proposition, even if it could possibly be mounted. 23:35.200 --> 23:53.020 So our conclusion is that also, as I mentioned before, while BMDs are widely touted as helping some groups of voters, in fact BMDs pose an ideal vector for disenfranchising those very same groups of voters because they will interact with the machines in specific ways. 23:53.700 --> 24:04.320 In short, there doesn't really seem to be a way to rescue the trustworthiness of elections if you're casting most of the votes on ballot marking devices, or a substantial fraction of votes on ballot marking devices. 24:04.480 --> 24:17.200 And prudent election administration would involve minimizing the number of voters who use ballot marking devices, really reserving them for their accessibility benefits, where those accessibility benefits really do help particular groups of voters. 24:17.220 --> 24:18.800 Thank you very much for your attention.