With the recent evolution in the VoIP market, where more and more devices and services are being pushed on a very promising market, assuring their security becomes crucial. Among the most dangerous threats to VoIP, failures and bugs in the software implementation will still rank high on the list of vulnerabilities. In this paper we address the issue of detecting such vulnerabilities using a stateful fuzzer. We describe an automated attack approach capable to self-improve and to track the state context of a target device. We implemented our approach and were able to discover vulnerabilities in market leading and well known equipments and software.