Played around with coverage-guided fuzzing using honggfuzz and Intel BTS/PT a while back. Didn't have much time to fine-tune, but it seemed solid. It'd need a couple of months to properly dial in and see real results. The coverage was increasing, and aligning with the symbol tables, it was hitting the right parts of the kernel.
With coverage guided fuzzing you wont get into the deep states of such protocols. If it's TCP/IP or TLS or similar. You'd really need a client/server simulator, and fuzz this.