A method for detecting intrusions that employ messages of two or more protocols is disclosed. Such intrusions might occur in Voice over Internet Protocol (VoIP) systems, as well as in systems in which two or more protocols support some service other than VoIP. In the illustrative embodiment of the present invention, a stateful intrusion-detection system is capable of employing rules that have cross-protocol pre-conditions. The illustrative embodiment can use such rules to recognize a variety of VoIP-based intrusion attempts, such as call hijacking, BYE attacks, etc. In addition, the illustrative embodiment is capable of using such rules to recognize other kinds of intrusion attempts in which two or more protocols support a service other than VoIP. The illustrative embodiment also comprises a stateful firewall that is capable of employing rules with cross-protocol pre-conditions.