  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 votes into the BMD and check the printout. Passive
testing monitors the rate of "spoiled" BMD printout, on the theory that if BMDs
malfunction, the rate will increase noticeably. We show that these approaches
cannot reliably detect outcome-altering problems, because: (i) The number of
possible 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 an accurate model requires observing a huge
number of voters in every jurisdiction in every election--more voters than
there are in most jurisdictions. (iii) Even with a perfect model of voter
behavior, the number of tests needed exceeds the number of voters in most
jurisdictions. (iv) An attacker can target interactions that are expensive to
test, e.g., because they involve voting slowly; or interactions for which
tampering is less likely to be noticed, e.g., because the voter uses the audio
interface. (v) Whether BMDs misbehave or not, the distribution of spoiled
ballots is unknown and varies by election and possibly by ballot style:
historical data do not help much. 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.
(vi) Even if the distribution of spoiled ballots were known to be Poisson, the
vast majority of jurisdictions do not have enough voters for passive testing to
have a large chance of detecting problems but only a small chance of false
alarms.
