Spam e-mails have become a serious technological and economic problem. Up to now, by deploying complementary anti-spam measures, we have been reasonably able to withstand spam e-mails and use the Internet for regular communication. However, if we are to avert the danger of losing the Internet e-mail service in its capacity as a valuable, free and worldwide medium of open communication, anti-spam activities should be performed more systematically than is currently the case regarding the mainly heuristic, anti-spam measures in place. A formal framework, within which the existing delivery routes that a spam e-mail may take, and anti-spam measures and their effectiveness can be investigated, will perhaps encourage a shift in methodology and pave the way for new, holistic anti-spam measures. This paper presents a model of the Internet e-mail infrastructure as a directed graph and a deterministic finite automaton and draws on automata theory to formally derive the spam delivery routes. The most important anti-spam measures are then described. Methods controlling only specific delivery routes are evaluated in terms of how effectively they cover the modeled e-mail infrastructure; methods operating independently of any particular routes receive a more general assessment.