Provided are systems, methods and techniques for discovering protocols of a network-provided service by initially collecting interaction data that pertain to messages between a plurality of devices across a network. Metrics that indicate frequencies of occurrence for different message sequences within the interaction data are calculated, and a protocol structure based on the interaction data and the metrics is generated. Finally, the protocol structure, which describes permitted conversations for a particular service implemented across the network, is output.