They may look and look, yet not see: BMDs cannot be tested adequately

Bugs, misconfiguration, and malware can cause ballot-marking devices (BMDs) to print incorrect votes. Several approaches to testing BMDs have been proposed. In logic and accuracy testing (LAT) and parallel or live testing, auditors input known test patterns into the BMD and check whether the printout matches. Passive testing monitors the rate at which voters ``spoil'' BMD printout, on the theory that if BMDs malfunction, the rate will increase. We provide theoretical lower bounds that show that in practice, these approaches cannot reliably detect outcome-altering problems. The bounds are large because: (i) The number of possible voter interactions with BMDs is enormous, so testing interactions uniformly at random is hopeless. (ii) To probe the space of interactions intelligently requires an accurate model of voter behavior, but because the space of interactions is so large, building that model requires observing an enormous number of voters in every jurisdiction in every election -- more voters than there are in most U.S. jurisdictions. (iii) Even with a perfect model of voter behavior, the required number of tests exceeds the number of voters in most U.S. jurisdictions. (iv) The distribution of spoiled ballots, whether BMDs misbehave or not, is unknown and varies by election and presumably by ballot style: historical data are of limited use. Hence, there is no way to calibrate a threshold for passive testing, e.g., to guarantee at least a 95% chance of noticing that 5% of the votes were altered, with at most a 5% false alarm rate. (v) Even if the distribution of spoiled ballots were known to be Poisson, the vast majority of jurisdictions to not have enough voters for passive testing to have a large chance of detecting problems while maintaining a small chance of false alarms.