An approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs) with two parts, pruning and a guided random walk procedure, is presented. First the protocol is pruned to various sets of machines; each set provides only one service. This significantly reduces the test sequence length. Then a guided random walk procedure that attempts to cover all transitions in the component FSMs is used. The results of applying the procedure to the full-duplex alternating bit protocol and the asynchronous transfer mode (ATM) adaptation layer convergence protocol are presented. For the ATM adaptation layer, 99% of component FSMs' edges can be covered in a test with 11692 input steps. Previous approaches cannot generate conformance tests for standard protocols (such as ATM adaptation layer) specified as a collection of communicating FSMs.< >