Spam e-mails have become a serious technological and economic problem. So far we have been reasonably able to resist spam e-mails and use the Internet for regular communication by deploying complementary anti-spam approaches. However, if we are to avert the danger of losing the Internet e-mail service as a valuable, free, and worldwide medium of open communication, anti-spam activities should be performed more systematically than is done in current, mainly heuristic, anti-spam approaches. A formal framework within which the modes of spam delivery, anti-spam approaches, and their effectiveness can be investigated, may encourage a shift in methodology and pave the way for new, holistic anti-spam approaches.

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 modes of spam delivery possible. Finally the effectiveness of anti-spam approaches in terms of coverage of spamming modes is assessed.