We present the INTERSTATE fuzzer to detect security vulnerabilities in VOIP phones which implement Session Initiation Protocol (SIP). INTERSTATE generates an input sequence for a SIP phone which is constructed to reveal common security vulnerabilities. SIP is a stateful protocol so a state machine description of the SIP protocol is used by INTERSTATE to ensure that the entire state space is explored. The input sequence consists of SIP request messages as well as GUI input sequences which are remotely applied to the phone under test. The input sequence is generated to perform a random walk through the state space of the protocol. The application of GUI inputs is essential to ensure that all parts of the state machine can be tested. Faults are injected into SIP messages to trigger common vulnerabilities. INTERSTATE also checks the SIP response messages received from the phone under test against the expected responses described in the state machine. Checking response messages allows for the detection of security bugs whose impact is more subtle than a simple crash. We have used INTERSTATE to identify a previously unknown DoS vulnerability in an existing open source SIP phone. The vulnerability could not have been discovered without exploring multiple paths through the state machine, and applying GUI inputs during the fuzzing process.