1. A method of discovering protocols for a network-provided service, comprising: (a) collecting interaction data that pertain to messages between a plurality of devices across a network; (b) calculating metrics that indicate frequencies of occurrence for different message sequences within the interaction data; (c) generating a protocol structure based on the interaction data and the metrics; and (d) outputting the protocol structure, wherein the protocol structure describes permitted conversations for a particular service implemented across the network.