Attacks like call fraud and identity theft often involve so-phisticated stateful attack patterns which, on top of normal communication, try to harm systems on a higher semantic level than usual attack scenarios. To detect these kind of threats via specially deployed honeypots, at least a minimal understanding of the inherent state machine of a specific service is needed to lure potential attackers and to keep a communication for a sufficiently large number of steps. To this end we propose PRISMA, a method for protocol inspec-tion and state machine analysis, which infers a functional state machine and message format of a protocol from net-work traffic alone. We apply our method to three real-life network traces ranging from 10,000 up to 2 million mes-sages of both binary and textual protocols. We show that PRISMA is capable of simulating complete and correct ses-sions based on the learned models. A case study on malware traffic reveals the different states of the execution, rendering PRISMA a valuable tool for malware analysis.