More Web Proxy on the site http://driver.im/

Article

Test coverage for continuous and hybrid systems

Authors:

Thao DangAuthors Info & Claims

CAV'07: Proceedings of the 19th international conference on Computer aided verification

Pages 449 - 462

Published: 03 July 2007 Publication History

Abstract

We propose a novel test coverage measure for continuous and hybrid systems, which is defined using the star discrepancy notion. We also propose a test generation method guided by this coverage measure. This method was implemented in a prototype tool that can handle high dimensional systems (up to 100 dimensions).

References

[1]

Beck, J., Chen, W.: Irregularities of Distribution. Cambridge Univ. Press, Cambridge (1987).

[2]

Dang, T., Nahhal, T.: Randomized simulation of hybrid systems. In: Technical report, Verimag, IMAG (May 2006).

[3]

LaValle, S.M., Branicky, M.S., Lindemann, S.R.: On the relationship between classical grid search and probabilistic roadmaps. Intl. Journal of Robotics Research 23(7-8), 673-692 (2004).

[4]

Branicky, M.S., Curtiss, M.M., Levine, J., Morgan, S.: Sampling-based reachability algorithms for control and verification of complex systems. In: Proc. Thirteenth Yale Workshop on Adaptive and Learning Systems, New Haven, CT (2005).

[5]

Esposito, J.M., Kim, J., Kumar, V.: Adaptive RRTs for validating hybrid robotic control systems. In: Int. Workshop on the Algorithmic Founddations of Robotics (2004).

[6]

Bhatia, A., Frazzoli, E.: Incremental Search Methods for Reachability Analysis of Continuous and Hybrid Systems. In: Alur, R., Pappas, G.J. (eds.) HSCC 2004. LNCS, vol. 2993, pp. 142-156. Springer, Heidelberg (2004).

[7]

Dobkin, D., Eppstein, D.: Computing the discrepancy. In: Proceedings of the Ninth Annual Symposium on Computational Geometry, pp. 47-52 (1993).

Digital Library

[8]

LaValle, S.M., Kuffner, J.J.: Rapidly-exploring random trees: Progress and prospects. In: Algorithmic and Computational Robotics: New Directions, pp. 293- 308. A K Peters, Wellesley, MA (2001).

[9]

Lee, D., Yannakakis, M.: Principles and Methods of Testing Finite State Machines - A Survey. In: Proceedings of the IEEE, vol. 84 (1996).

[10]

Thiémard, E.: An algorithm to compute bounds for the star discrepancy. J. Complexity 17(4), 850 (2001).

[11]

Mitchell, I., Tomlin, C.: Level Set Methods for Computation in Hybrid Systems. In: Lynch, N.A., Krogh, B.H. (eds.) HSCC 2000. LNCS, vol. 1790, Springer, Heidelberg (2000).

Digital Library

[12]

Nahhal, T., Dang, T.: Guided randomized simulation. In: HSCC. LNCS, Springer, Heidelberg (2007).

Digital Library

[13]

Tan, L., Kim, J., Sokolsky, O., Lee, I.: Model-based Testing and Monitoring for Hybrid Embedded Systems. In: IRI, pp. 487-492 (2004).

[14]

Tretmans, J.: Testing Concurrent Systems: A Formal Approach. In: Baeten, J.C.M., Mauw, S. (eds.) CONCUR 1999. LNCS, vol. 1664, Springer, Heidelberg (1999).

Digital Library

[15]

Yershova, A., Jaillet, L., Simeon, T., LaValle, S.M.: Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain. In: Proc. IEEE International Conference on Robotics and Automation, IEEE Computer Society Press, Los Alamitos (2005).

[16]

Zhu, H., Hall, P.A.V., May, J.H.R.: Software Unit Test Coverage and Adequacy. In: ACM Computing Surveys, vol. 29(4), ACM Press, New York (1997).

Digital Library

Cited By

Corso AMoss RKoren MLee RKochenderfer M(2022)A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical SystemsJournal of Artificial Intelligence Research10.1613/jair.1.1271672(377-428)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12716
Yang LOzay N(2021)Synthesis-guided Adversarial Scenario Generation for Gray-box Feedback Control Systems with Sensing ImperfectionsACM Transactions on Embedded Computing Systems10.1145/347703320:5s(1-25)Online publication date: 22-Sep-2021
https://dl.acm.org/doi/10.1145/3477033
Zutshi ASankaranarayanan SDeshmukh JJin XAbate AFainekos G(2016)Symbolic-Numeric Reachability Analysis of Closed-Loop Control SoftwareProceedings of the 19th International Conference on Hybrid Systems: Computation and Control10.1145/2883817.2883819(135-144)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.1145/2883817.2883819
Show More Cited By

Recommendations

Coverage-guided test generation for continuous and hybrid systems

In this paper, we describe a formal framework for conformance testing of continuous and hybrid systems, using the international standard `Formal Methods in Conformance Testing' FMCT. We propose a novel test coverage measure for these systems, which is ...
Program Segmentation for Controlling Test Coverage
ISSRE '97: Proceedings of the Eighth International Symposium on Software Reliability Engineering

In this paper we present a new control-flow based approach to dynamic testing of sequential software. A practicable number of test cases is generated by using the boundary-interior path testing strategy and by dividing the test units into test segments (...
Comparing non-adequate test suites using coverage criteria
ISSTA 2013: Proceedings of the 2013 International Symposium on Software Testing and Analysis

A fundamental question in software testing research is how to compare test suites, often as a means for comparing test-generation techniques. Researchers frequently compare test suites by measuring their coverage. A coverage criterion C provides a set ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CAV'07: Proceedings of the 19th international conference on Computer aided verification

July 2007

562 pages

ISBN:9783540733676

Editors:
Werner Damm
Carl von Ossietzky University Oldenburg, Department of Computer Science, Oldenburg, Germany
,
Holger Hermanns
Saarland University, Department of Computer Science, Saarbrücken, Germany

Sponsors

German Science Foundation
Artist2 Network of Excellence
Cadence Design Systems
Informatik Saarland
IBM: IBM

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 03 July 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
2
Total Downloads

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

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Corso AMoss RKoren MLee RKochenderfer M(2022)A Survey of Algorithms for Black-Box Safety Validation of Cyber-Physical SystemsJournal of Artificial Intelligence Research10.1613/jair.1.1271672(377-428)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12716
Yang LOzay N(2021)Synthesis-guided Adversarial Scenario Generation for Gray-box Feedback Control Systems with Sensing ImperfectionsACM Transactions on Embedded Computing Systems10.1145/347703320:5s(1-25)Online publication date: 22-Sep-2021
https://dl.acm.org/doi/10.1145/3477033
Zutshi ASankaranarayanan SDeshmukh JJin XAbate AFainekos G(2016)Symbolic-Numeric Reachability Analysis of Closed-Loop Control SoftwareProceedings of the 19th International Conference on Hybrid Systems: Computation and Control10.1145/2883817.2883819(135-144)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.1145/2883817.2883819
Zutshi ASankaranarayanan SDeshmukh JKapinski JJin XGirard ASankaranarayanan S(2015)Falsification of safety properties for closed loop control systemsProceedings of the 18th International Conference on Hybrid Systems: Computation and Control10.1145/2728606.2728648(299-300)Online publication date: 14-Apr-2015
https://dl.acm.org/doi/10.1145/2728606.2728648
Abbas HFainekos GSankaranarayanan SIvančić FGupta A(2013)Probabilistic Temporal Logic Falsification of Cyber-Physical SystemsACM Transactions on Embedded Computing Systems10.1145/2465787.246579712:2s(1-30)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1145/2465787.2465797
Ahmadyan SKumar JVasudevan SGroeneveld PSciuto DHassoun S(2012)Goal-oriented stimulus generation for analog circuitsProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228544(1018-1023)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228544
Sankaranarayanan SFainekos GDang TMitchell I(2012)Falsification of temporal properties of hybrid systems using the cross-entropy methodProceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control10.1145/2185632.2185653(125-134)Online publication date: 17-Apr-2012
https://dl.acm.org/doi/10.1145/2185632.2185653
Krupp AMüller WDe Micheli GAl-Hashimi BMueller WMacii E(2010)A systematic approach to the test of combined HW/SW systemsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1870926.1871005(323-326)Online publication date: 8-Mar-2010
https://dl.acm.org/doi/10.5555/1870926.1871005
Nghiem TSankaranarayanan SFainekos GIvancić FGupta APappas GJohansson KYi W(2010)Monte-carlo techniques for falsification of temporal properties of non-linear hybrid systemsProceedings of the 13th ACM international conference on Hybrid systems: computation and control10.1145/1755952.1755983(211-220)Online publication date: 12-Apr-2010
https://dl.acm.org/doi/10.1145/1755952.1755983
Fainekos GPappas G(2009)MTL robust testing and verification for LPV systemsProceedings of the 2009 conference on American Control Conference10.5555/1702715.1702948(3748-3753)Online publication date: 10-Jun-2009
https://dl.acm.org/doi/10.5555/1702715.1702948
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents