Protocol Specification and Testing

Specification and Test Generation for MIL-STD-188-220A


Over the past few years, we have worked with CECOM to develop an Estelle specification for the Datalink and Intranet layers of the MIL-STD-188-220A protocol. Estelle is a language for the formal specification of communication protocols that results in a complete, consistent, concise, and unambiguous protocol description which can help discover and resolve ambiguities in the original English document. Our Estelle specification of 188-220A Datalink and Intranet layers has uncovered more than 50 problems in the original English specification that were reported back to the Combat Net Radio (CNR) Implementation Working Group that is responsible for the evolving standard. In many instances, the 188-220A protocol document was changed by the Working Group to resolve the problems.

Our research has also investigated the use of the Estelle formal specification as input to conformance test generation techniques. Since Estelle makes it possible to create a complete and unambiguous protocol model as an extended Finite State Machine (FSM), the test cases generated from it achieve high fault coverage. We have developed a methodology for deriving test cases from the Estelle specification that involves transforming the extended FSM to a somewhat purer form of an FSM and then the construction of a minimum-cost Chinese postman tour of the transition graph of the FSM for various transition types. We have used this methodology to construct sample test suites for the Type 1 Datalink Layer Service of 188-220A which have been communicated to CECOM. Within this research effort, we encountered and solved several problems concerning controllability and optimization issues that need to be addressed in test cases generation for Type 2 Datalink Layer and Intranet Layer.

For more details, please see Protocol Engineering Laboratory or the web page of Prof. Paul Amer.

(Supported by US Army CECOM and by the Federated Research Laboratory (FRL) Consortium in Advanced Telecommunications/Information Distribution Research Program (ATIRP) sponsored by the Army Research Laboratory (ARL).