We present a new approach for conformance testing of protocols specified as a collection of communicating finite state machines (FSMs). Our approach uses a guided random walk procedure. This procedure attempts to cover all transitions in the component FSMs. We also introduce the concept of observers that check some aspect of protocol behavior. We present the result of applying our method to two example protocols: full-duplex alternating bit protocol and the ATM-adaptation-layer-convergence protocol. Applying our procedure to the ATM adaptation layer, 99% of component FSMs edges can be covered in a test with 11692 input steps. Previous approaches cannot do conformance test generation for standard protocols (such as asynchronous transfer mode (ATM) adaptation layer) specified as a collection of communicating FSMs.