This invention presents a new "Hit-or-Jump" system and method for embedded testing of components of communication systems that can be modeled by communicating extended finite state machines. It constructs test sequences efficiently with a high fault coverage. It does not have state space explosion, as is often encountered in exhaustive search, and it quickly covers the system components under test without being "trapped", as is experienced by random walks. The algorithm has been implemented and applied to embedded testing of telephone services in an IN architecture, including the Basic Call Service (ECS) as well as other supplementary services.