A method and system for protecting an application that implements a communication protocol against exploitation of a communication-based vulnerability is provided. A protection system provides a protection policy that specifies how to recognize messages that expose a specific vulnerability and specifies actions to take when the vulnerability is exposed. A protection policy specifies the sequence of messages and their payload characteristics that expose a vulnerability. The protection system may specify the sequences of messages using a message protocol state machine. A message protocol state machine of an application represents the states that the application transitions through as it receives various messages. The message protocol state machine of the protection policy may be a portion of the message protocol state machine of the application relating to the vulnerability. The protection system uses the message protocol state machine to track the states that lead up to the exposing of the vulnerability.