Denial of Service (DoS) attack, especially Distributed Denial of Service (DDoS) attack, is one of the greatest threats to Internet. Much research has been done for it by now, however, it is always concentrated in the behaviors of the network and can not deal with the problem exactly. In this paper, we start from the security of the protocol, then we propose a novel theory for security protocol analysis of Denial of Service in order to deal with the DoS attack. We first introduce the conception of weighted graph to extend the strand space model, then we extend the penetrator model and define the goal of anti-DoS attack through the conception of the DoS-stop protocol, finally we propose two kinds of DoS test model and erect the novel formal theory for security protocol analysis of Denial of Service. Our new formal theory is applied in two example protocols. It is proved that the Internet key exchange (IKE) easily suffers from the DoS attacks, and the efficient DoS-resistant secure key exchange protocol (JFK) is resistant against DoS attack for the server, respectively.