Current network protocol binary software testing methods cannot discover serious vulnerabilities in deep states. This article introduces a novel method based on multi-packet symbolic execution, which can drive the software to deep states, to test the whole network protocol binary software stacks. This article also presents a prototype system, S2EProtocol-multi, upon Selective Symbolic Execution (S2E) platform and evaluates it on real-world network protocol binary software. The results validate that the proposed method can explore deep states and detect vulnerabilities efficiently and effectively.