article

Test sequence generation for controller verification and test with high coverage

Authors:

F. Joel FergusonAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 11, Issue 4

Pages 916 - 938

https://doi.org/10.1145/1179461.1179467

Published: 01 October 2006 Publication History

Abstract

Verification and test are critical phases in the development of any hardware or software system. This article focuses on black box testing of the control part of hardware and software systems. Black box testing involves specification, test generation, and fault coverage. Finite state machines (FSMs) are commonly used for specifying controllers. FSMs may have shortcomings in modeling complex systems. With the introduction of X-machines, complex systems can be modeled at higher levels of abstraction. An X-machine can be converted into an FSM while preserving the level of abstraction. The fault coverage of a test sequence for an FSM specification provides a confidence level. We propose a fault coverage metric for an FSM specification based on the transition fault model, and using this metric, we derive the coverage of a test sequence. The article also presents a method which generates short test sequences that meet a specific coverage level and then extends this metric to determine the coverage of a test sequence for an FSM driven by an FSM network. We applied our FSM verification technique to a real-life FSM, namely, the fibre channel arbitrated loop port state machine, used in the field of storage area networks.

References

[1]

Cheng, K.-T. and Jou, J. Y. 1990. Functional test generation for finite state machines. In Proceedings of International Test Conference. 162--168.]]

[2]

Chockler, H., Kupferman, O., Kurshan, R. P., and Vardi, M. Y. 2001. A practical approach to coverage in model checking. In Proceedings of the International Conference on Computer-Aided Verification. 66--78.]]

[3]

Clarke, E. M. and Emerson, E. A. 1981. Design and synthesis of synchronization skeletons using branching time temporal logic. In Proceedings of the Workshop on Logic of Programs, Lecture Notes in Computer Science, 131, 52--71.]]

[4]

Dahbura, A. T., Uyar, M. Ü., and Yau, C. W. 1989. An optimal test sequence for the JTAG/IEEE P1149.1 test access port controller. In Proceedings of the International Test Conference. 55--62.]]

[5]

Eilenberg, S. 1974. Automata Machines and Languages. Academic Press, Orlando, FL.]]

[6]

Fallah, F., Ashar P., and Devadas, S. 2002. Functional vector generation for sequential HDL models under an observability-based coverage metric. IEEE Trans. VLSI Syst. 10, 919--923.]]

[7]

Ferrandi, F., Macii, E., Poncino, M., and Sciuto, D. 2000. Symbolic optimization of interacting controllers based on redundancy identification and removal. IEEE Trans. Comput.-Aided Des. Integrated Circ. Syst. 19, 760--772.]]

[8]

Ghosh, A., Devadas, S., and Newton, A. R. 1991. Test generation and verification for highly sequential circuits. IEEE Trans. Comput.-Aided Des. Integrated Circ. Syst. 10, 652--667.]]

[9]

Gören S. and Ferguson, F. J. 1999. Checking sequence generation for asynchronous sequential elements. In Proceedings of the International Test Conference. 406--413.]]

[10]

Gören S. and Ferguson, F. J. 2002. Testing finite state machines based On a structural coverage metric. In Proceedings of the International Test Conference. 773--780.]]

[11]

Hennie, F. C. 1964. Fault detecting experiments for sequential circuits. In Proceedings of International Symposium on Switching Circuit Theory and Logic Design. 95--110.]]

[12]

Holcombe, M. 1988. X-Machines as a basis for dynamic system specification. Softw. Eng. J. 3, 69--76.]]

[13]

Ipate, F. and Holcombe, M. 1998. Specification and testing generalized machines: A presentation and a case study. Softw. Test. Verification and Reliability 8, 61--81.]]

[14]

Kembel, R. W. and Truestedt, H. L. 1997. Fibre Channel Arbitrated Loop. Northwest Learning.]]

[15]

Lee, D. and Yannakakis, M. 1996. Principles and methods of testing finite state machines---A survey. Proc. IEEE 84, 1090--1123.]]

[16]

Lichtenstein, O. and Pnueli, A. 1985. Checking that finite state concurrent programs satisfy their linear specification. In Proceedings of the Conference on Principles of Programming Languages. 97--107.]]

[17]

Makar, S. R. 1996. Checking experiments for scan chain latches and flip-flops. Ph.D. Dissertation, Department of Electrical Engineering, Stanford University.]]

[18]

Moore, E. F. 1956. Gedanken Experiments on sequential machines. In Automata Studies. Princeton University Press, 34, 129--153.]]

[19]

Petrenko, A., Bochmann, G. V., and Yao, M. 1996. On fault coverage of tests for finite state specifications. Comput. Netw. ISDN Syst. 29. (Special issue on Protocol Testing), 81--106.]]

[20]

Pomeranz, I. and Reddy, S. M. 1991. On achieving a complete fault coverage for sequential machines using the transition fault model. In Proceedings of the Conference Design Automation Conference. 341--346.]]

[21]

Sentovich, E. M., Singh, K. J., Moon, C. W., Savoij, H., Brayton, R. K., and Sangiovanni-Vincentelli, A. 1992. Sequential circuits design using synthesis and optimization. In Proceedings of the International Conference on Computer Design. 328--333.]]

[22]

Shen, Y.-N., Lombardi, F., and Dahbura, A. T. 1992. Protocol conformance testing using multiple UIO sequences. IEEE Trans. Commun. 40, 1282--1287.]]

[23]

Sidhu, D. P. and Leung, T.-K. 1989. Formal methods for protocol testing: A detailed study. IEEE Trans. Softw. Eng. 15, 413--426.]]

[24]

Sun, X., Shen, Y., Feng, C., and Lombardi. 1997. Protocol Conformance Testing Using Unique Input/Output Sequences. World Scientific Publishing, River Edge, NJ.]]

[25]

Queille, J. P. and Sifakis, J. 1981. Specification and verification of concurrent systems in Cesar. In Proceedings of the International Symposium on Programming, Lecture Notes in Computer Science, 137, 337--351.]]

[26]

Uyar, M.Ü., Fecko, M. A., Duale, A. Y., Amer, P. D., and Sethi, A. S. 2001. A formal approach to development of network protocols: Theory and application to a wireless standard. In Proceedings of the Concordia Prestigious Workshop on Communication Software Engineering.]]

[27]

Yen, C.-C. and Jou, J.-Y. 2004. A divide-and-conquer-based algorithm for automatic simulation vector generation. IEEE Des. Test Comput. 111--120.]]

Cited By

Pomeranz I(2024)Two-dimensional Search Space for Extracting Broadside Tests from Functional Test SequencesACM Transactions on Design Automation of Electronic Systems10.1145/365020729:3(1-13)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3650207
Vogel MKnapik PCohrs MSzyperrek BPueschel WEtzel HFiebig DRausch AKuhrmann M(2021)Metrics in automotive software developmentJournal of Software: Evolution and Process10.1002/smr.229633:2Online publication date: 14-Feb-2021
https://dl.acm.org/doi/10.1002/smr.2296

Index Terms

Test sequence generation for controller verification and test with high coverage
1. Hardware
2. Networks
  1. Network protocols
    1. Protocol correctness
      1. Protocol testing and verification

Recommendations

Constructing test cases for n-wise testing from tree-based test models
SoICT '13: Proceedings of the 4th Symposium on Information and Communication Technology

In our previous work [17], we proposed a model-based combinatorial testing method, called FOT. It provides a technique to design test-models for combinatorial testing based on extended logic trees. In this paper, we introduce pair-wise testing (and by ...
Checking Completeness of Tests for Finite State Machines

In testing from a Finite State Machine (FSM), the generation of test suites which guarantee full fault detection, known as complete test suites, has been a long-standing research topic. In this paper, we present conditions that are sufficient for a test ...
Optimal Synchronizable Test Sequence from Test Segments
QSIC '06: Proceedings of the Sixth International Conference on Quality Software

Finite-state-machine-based conformance testing has been extensively studied in the literature in the context of centralized test architecture. With a distributed test architecture which involves multiple remote testers, the application of a test ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 11, Issue 4

October 2006

177 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1179461

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 October 2006

Published in TODAES Volume 11, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
537
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pomeranz I(2024)Two-dimensional Search Space for Extracting Broadside Tests from Functional Test SequencesACM Transactions on Design Automation of Electronic Systems10.1145/365020729:3(1-13)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3650207
Vogel MKnapik PCohrs MSzyperrek BPueschel WEtzel HFiebig DRausch AKuhrmann M(2021)Metrics in automotive software developmentJournal of Software: Evolution and Process10.1002/smr.229633:2Online publication date: 14-Feb-2021
https://dl.acm.org/doi/10.1002/smr.2296

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents