A system is used to analyze the implementation of a protocol by a device-under-analysis (DUA). The system includes a source endpoint, a destination endpoint (the DUA), and a message generator. The source endpoint generates an original message and attempts to send it to the DUA. The original message is intercepted by the message generator, which generates a replacement message. The replacement message is then sent to the DUA instead of the original message. The replacement message is deliberately improper so as to analyze the DUA's implementation of the protocol. The message generator includes a structure recognition system and a mutation system. The structure recognition system determines the underlying structure and/or semantics of a message. After the structure recognition system has determined the structure, it creates a description of the structure (a structure description). The mutation system modifies the message based on the structure description to generate a replacement message.