Many common protocols: TCP, IPSec, etc., are vulnerable to denial of service attacks, where adversaries maliciously consume significant resources of honest principals, leading to resource exhaustion. We propose a set of cost-based rules that formalize DoS attacks by resource exhaustion and can automate their detection. Our classification separates excessive but legal protocol use (e.g., flooding) from illegal protocol manipulation that causes participants to waste computation time without reaching the protocol goals. We also distinguish simple intruder intervention leading to wasteful execution from DoS attacks proper, which can be repeatedly initiated. Our rules can highlight attacks that are undetectable by the targeted honest agents, or by all protocol participants. We have successfully tested an implementation of the methodology in a validation platform on relevant protocol examples, in what to the best of our knowledge is the first formal automated analysis of DoS attacks.