The Multimedia Messaging Service (MMS) is becoming more popular, as mobile phones integrate audio and video recording functionality. Multimedia messages are delivered to users through a multi-step process, whose end-points are the MMS User Agents that reside on the users? mobile phones. The security of these components is critical, be- cause they might have access to private information and, if compromised, could be leveraged to spread an MMS-based worm. Unfortunately, the vulnerability analysis of these components is made more difficult by the fact that they are mostly closed-source and the testing has to be performed through the mobile phone network, which makes the testing time-consuming and costly. This paper presents a novel approach to the security testing of MMS User Agents. Our approach takes into account the effects of the infrastructure on the delivery of MMS messages and then uses a virtual infrastructure to speed up the testing process. Our testing approach was able to identify a number of previously unknown vulnerabilities, which, in one case, allowed for the execution of arbitrary code.