Over the past decade, the automated generation of test inputs has made significant advances. Modern fuzzers and test generators easily produce complex input formats that do systematically cover the input and execution space. Testing _protocols_, though, has remained a frontier for automated testing, as a test generator has to _interact_ with the program under test, producing messages that conform to the current state of the system. In this paper, we introduce _language-based protocol testing_, the first approach to specify, automatically test, and systematically cover the full state and input space of protocol implementations. We specify protocols as _interaction grammars_ -- an extension of context-free grammars that tag each message element with the communication party that is in charge of producing it. Interaction grammars embed classical state models by unifying states, messages, and transitions all into nonterminals, and can be used for _producing_ interactions as well as _parsing_ them, making them ideally suited for testing protocols. Additional _constraints_ over grammar elements allow us to specify and test _semantic features_ such as binary message formats, checksums, encodings, and the many ways that message features induce states and vice versa. To evaluate the effectiveness of language-based protocol testing, we have implemented it as part of the FANDANGO test generator. We specify several protocols as interaction grammars, including features such as human-readable interactions (SMTP), bit-level encodings (DNS), and dynamic port assignments (FTP), and use them to test the corresponding protocol implementations. By systematically covering the interaction grammar and solving the associated constraints, FANDANGO achieves comprehensive coverage of the protocol interactions, resulting in high code coverage and a thorough assessment of the program under test.