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).
Related Publications
- M.U. Uyar, M.A. Fecko, A.Y. Duale, P.D. Amer, and A.S. Sethi,
``Experience in Developing and Testing Network Protocol
Software Using FDTs.''
Information and Software Technology
Vol. 45, 12 (Sept. 2003), pp. 815-835.
PDF
- P.D. Amer, M.A. Fecko, A.S. Sethi, M.U. Uyar, and A.Y. Duale, ``Formal
Specification and Conformance Testing of Army Communication Protocols.''
In Final Report (1996-2001) Advanced Telecommunications and Information
Distribution Research Program (ATIRP)
(A.J. Tardif and J.W. Gowens (eds.)), pp. 3.1-3.28,
US Army Research Laboratory, 2001.
Postscript
PDF
- M.A. Fecko, M.U. Uyar, A.Y. Duale, P.D. Amer, and A.S. Sethi, ``A Formal
Approach to Development of Network Protocols: Theory and Application to a
Wireless Standard,'' Proc. CPWCSE-2001, Concordia Prestigious Workshop on
Communication Software Engineering, Montreal, Canada (Sept. 2001).
Postscript
PDF
- M.A. Fecko, M.U. Uyar, P.D. Amer, A.S. Sethi, T. Dzik, R. Menell,
and M. McMahon, ``A success story of formal description
techniques: Estelle specification and test generation for
MIL-STD 188-220.''
Computer Communications
Vol. 23 No. 12 (June 2000), pp. 1196-1213.
Postscript
PDF
- M.A. Fecko, M.U. Uyar, P.D. Amer, and A.S. Sethi,
``Conformance Testing in Systems with Semicontrollable Interfaces.''
Annals of Telecommunications
Vol. 55 No. 1 (Jan. 2000), pp. 70-83.
Postscript
PDF
- M.U. Uyar, M.A. Fecko, A.S. Sethi, and P.D. Amer, ``Testing
Protocols Modeled as FSMs with Timing Parameters.''
Computer Networks Vol. 31 No. 18 (Sept. 1999),
pp. 1967-1988.
Postscript
PDF
- M.A. Fecko, M.U. Uyar, P.D. Amer, and A.S. Sethi, ``Using
semicontrollable interfaces in testing Army communications
protocols: Application to MIL-STD 188-220B,'' Proc.
MILCOM '99, IEEE Military Communications Conference, Atlantic
City, NJ (Oct. 1999).
Postscript
PDF
- M.A. Fecko, P.D. Amer, A.S. Sethi, and M.U. Uyar, ``Using
Semicontrollable Interfaces in Testing Army Communication
Protocols: Application to MIL-STD 188-220B,'' Proc. Third ARL/ATIRP
Annual Conference, College Park, MD (Feb. 1999), pp. 189-194.
- M.U. Uyar, M.A. Fecko, A.S. Sethi, and P.D. Amer, ``Generation
of Realizable Conformance Tests under timing constraints,''
Proc. MILCOM '98, IEEE Military Communications Conference,
Boston, MA (Nov. 1998).
Postscript
PDF
- M.A. Fecko, M.U. Uyar, A.S. Sethi, and P.D. Amer, ``Issues in
conformance testing: Multiple semicontrollable interfaces,''
Proc. FORTE/PSTV, IFIP Joint International Conference on Formal
Description Techniques for Distributed Systems and Communication
Protocols and Protocol Specification, Testing and Verification,
Paris, France (Nov. 1998), pp. 111-126.
Postscript
PDF
- P.D. Amer, M.A. Fecko, A.S. Sethi, M.U. Uyar, T.J. Dzik,
R. Menell, and M. McMahon, ``Using Estelle to Evolve
MIL-STD-188-220,'' Proc. Estelle '98, First International
Workshop on the Formal Description Technique
Estelle, Evry, France (Nov. 1998), pp. 55-58.
Postscript
PDF
- M. Fecko, M.U. Uyar, P.D. Amer, and A.S. Sethi, ``Optimum test
sequence generation from Estelle specifications,''
Proc. Estelle '98, First International
Workshop on the Formal Description Technique
Estelle, Evry, France (Nov. 1998), pp. 157-161.
Postscript
PDF
- P.D. Amer, A.S. Sethi, M.A. Fecko, M.U. Uyar, T.Dzik, R. Menell,
and M. McMahon, ``Using Formal Methods to Evolve MIL-STD
188-220,'' Proc. Second ARL/ATIRP
Annual Conference, College Park, MD (Feb. 1998), pp. 276-280.
- M.U. Uyar, M.A. Fecko, A.S. Sethi, and P.D. Amer, ``Generation
of Realizable Conformance Tests Under Timing Constraints,''
Proc. Second ARL/ATIRP
Annual Conference, College Park, MD (Feb. 1998), pp. 281-286.
- M.U. Uyar, M.A. Fecko, A.S. Sethi, and P.D. Amer, ``Minimum-Cost
Solutions for Testing Protocols with Timers,'' Proc.
IPCCC '98, IEEE International Performance, Computing, and
Communications Conference, Phoenix, AZ (Feb. 1998), pp. 346-354.
Also Tech. Rep. 97-17, CIS Dept., Univ. of Delaware.
Postscript
PDF
- M. Fecko, P.D. Amer, A.S. Sethi, M.U. Uyar, T. Dzik,
R. Menell, and M. McMahon, ``Formal Design
and Testing of MIL-STD 188-220A Based on
Estelle.'' Proc. MILCOM '97, IEEE Military
Communications Conference, Monterey, CA (Nov. 1997).
Also Tech. Rep. 97-19, CIS Dept., Univ. of Delaware.
Postscript
PDF
- P. Amer, A.S. Sethi, M. Fecko, and M.U. Uyar, ``Formal Design
and Testing of Army Communication Protocols Based on
Estelle,'' Proc. First ARL/ATIRP
Annual Conference, College Park, MD (Jan. 1997), pp. 107-113.
Postscript
PDF
- P.D. Amer, R.G. Burch, A.S. Sethi, D. Zhu, T. Dzik,
R. Menell, and M. McMahon, ``Estelle
specification of MIL-STD 188-220A Datalink Layer''.
Proc. MILCOM '96, IEEE Military Communications Conference,
McLean, VA (Oct. 1996).
Postscript
PDF
Technical Reports
- M.A. Fecko, M.U. Uyar, P.D. Amer, and A.S. Sethi, ``Embedded
Testing in Systems with Semicontrollable Interfaces,''
Technical Report No. 98-18, Dept. of Computer
and Information Sciences, University of Delaware, Newark, DE
(Aug. 1998).
Back to Research
Adarsh Sethi's Homepage