Abstract: Denial of service (DoS) is a kind of active attack that aims to prevent authorized user to access services, DoS vulnerabilities with different degrees exist in various of security protocols. A new counter measure based on session identifier and proof of work is presented, and then it is analyzed in a formal way proposed by Meadows originally. In addition, some useful principles are provided in designing network DoS resistant protocols. By using this counter measure, two-party security protocols can be designed or modified against DoS attack in a dynamic way and its security properties will not be lost.