Abstract
When using formal verification on Simulink or SCADE models, an important question about their certification is how well the specified properties cover the entire model. A method using unsatisfiable cores and inductive model checking called IVC (Inductive Validity Cores) has been recently proposed within modern SMT-based model checkers such as JKind. The IVC algorithm determines a minimal set of model elements necessary to establish a proof and gives back the traceability to the design elements (lines of code) necessary for the proof. These metrics are interesting but are rather coarse grain for certification purposes.
In this paper, we propose to use mutation combined with incremental inductive model checking to give more precision and quality to the traceability process and look inside the lines of code. Our algorithm, based on the result of IVC, mutates the source code to determine which parts inside a line of code have an impact on the properties (killed mutants) and which parts have no impact on the properties (survived mutants). Furthermore, using the incremental feature present in modern SMT-solvers, we observe that mutation can scale up to industrial models. We demonstrate the metrics first on a simple example, then on a complex industrial program and on the JKind benchmark.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
JKind with Mutation on GitHub: https://github.com/v-todorov/jkind.
References
Barrett, C., et al.: The SMT-LIB Standard: Version 2.0. Technical report (2010)
Bendík, J., Ghassabani, E., Whalen, M., Černá, I.: Online enumeration of all minimal inductive validity cores. In: Johnsen, E.B., Schaefer, I. (eds.) SEFM 2018. LNCS, vol. 10886, pp. 189–204. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-92970-5_12
Bendík, J., Černá, I., Beneš, N.: Recursive online enumeration of all minimal unsatisfiable subsets. In: Lahiri, S.K., Wang, C. (eds.) ATVA 2018. LNCS, vol. 11138, pp. 143–159. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01090-4_9
Berryhill, R.: Chasing Minimal Inductive Validity Cores in Hardware Model Checking, October 2019
Bradley, A.R., Manna, Z.: Property-directed incremental invariant generation. Formal Aspects Comput. 20, 379–405 (2008). https://doi.org/10.1007/s00165-008-0080-9
Caspi, P., Pilaud, D., Halbwachs, N., Plaice, J.A.: LUSTRE: a declarative language for real-time programming. In: POPL ’87, pp. 178–188. ACM (1987)
Chockler, H., Kupferman, O., Kurshan, R.P., Vardi, M.Y.: A practical approach to coverage in model checking. In: Berry, G., Comon, H., Finkel, A. (eds.) CAV 2001. LNCS, vol. 2102, pp. 66–78. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44585-4_7
Cimatti, A., Griggio, A., Mover, S., Tonetta, S.: IC3 Modulo Theories via Implicit Predicate Abstraction. CoRR abs/1310.6847 (2013)
Claessen, K.: A coverage analysis for safety property lists. In: Formal Methods in Computer Aided Design (FMCAD 2007), pp. 139–145, November 2007
Een, N., Mishchenko, A., Brayton, R.: Efficient implementation of property directed reachability In: FMCAD ’11, Austin, pp. 125–134 (2011)
Gacek, A., Backes, J., Whalen, M., Wagner, L., Ghassabani, E.: The JKind model checker. In: Chockler, H., Weissenbacher, G. (eds.) CAV 2018. LNCS, vol. 10982, pp. 20–27. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96142-2_3
Ghassabani, E., Whalen, M., Gacek, A., Heimdahl, M.: Inductive validity cores. IEEE Trans. Softw. Eng. 1–1 (2019)
Ghassabani, E., Gacek, A., Whalen, M.W.: Efficient generation of inductive validity cores for safety properties. In: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2016), pp. 314–325. ACM, New York (2016)
Ghassabani, E., Gacek, A., Whalen, M.W., Heimdahl, M.P.E., Wagner, L.: Proof-based coverage metrics for formal verification. In: Proceedings of the 32Nd IEEE/ACM International Conference on Automated Software Engineering, November 2017, Urbana-Champaign, IL, USA, pp. 194–199. ASE: IEEE Press, Piscataway (2017)
Ghassabani, E., Whalen, M., Gacek, A.: Efficient generation of all minimal inductive validity cores. In: Proceedings of the 17th Conference on Formal Methods in Computer-Aided Design (FMCAD 2017), Vienna, Austria, pp. 31–38. FMCAD Inc., Austin, November 2017
Große, D., Kühne, U., Drechsler, R.: Estimating functional coverage in bounded model checking. In: Proceedings of the Conference on Design, Automation and Test in Europe (DATE 2007), Nice, France, pp. 1176–1181. EDA Consortium, San Jose (2007)
Hardin, D., Hiratzka, T.D., Johnson, D.R., Wagner, L., Whalen, M.: Development of security software: a high assurance methodology. In: Breitman, K., Cavalcanti, A. (eds.) ICFEM 2009. LNCS, vol. 5885, pp. 266–285. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10373-5_14
ISO: Road vehicles - Functional safety (2011)
Kahsai, T., Garoche, P.-L., Tinelli, C., Whalen, M.: Incremental verification with mode variable invariants in state machines. In: Goodloe, A.E., Person, S. (eds.) NFM 2012. LNCS, vol. 7226, pp. 388–402. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28891-3_35
Miller, S.P., Whalen, M.W., Cofer, D.D.: Software model checking takes off. Commun. ACM 53(2), 58–64 (2010)
Murugesan, A., Whalen, M.W., Ghassabani, E., Heimdahl, M.P.E.: Complete traceability for requirements in satisfaction arguments. In: 2016 IEEE 24th International Requirements Engineering Conference (RE), pp. 359–364 (2016)
RTCA DO-178C: Software Considerations in Airborne Systems and Equipment Certification. Washington, DC, December 2011
Rushby, J.: Software verification and system assurance. In: 2009 Seventh IEEE International Conference on Software Engineering and Formal Methods, pp. 3–10, November 2009
Das, S., et al.: Formal methods for analyzing the completeness of an assertion suite against a high-level fault model. In: 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, pp. 201–206, January 2005
Sheeran, M., Singh, S., Stålmarck, G.: Checking safety properties using induction and a SAT-solver. In: Hunt, W.A., Johnson, S.D. (eds.) FMCAD 2000. LNCS, vol. 1954, pp. 127–144. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-40922-X_8
Todorov, V., Taha, S., Boulanger, F., Hernandez, A.: Improved invariant generation for industrial software model checking of time properties. In: Proceedings of the 19th IEEE International Conference on Software Quality, Reliability, and Security, pp. 334–341. IEEE, Sofia, Bulgaria, October 2019
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Todorov, V., Taha, S., Boulanger, F. (2020). Specification Quality Metrics Based on Mutation and Inductive Incremental Model Checking. In: Lee, R., Jha, S., Mavridou, A., Giannakopoulou, D. (eds) NASA Formal Methods. NFM 2020. Lecture Notes in Computer Science(), vol 12229. Springer, Cham. https://doi.org/10.1007/978-3-030-55754-6_11
Download citation
DOI: https://doi.org/10.1007/978-3-030-55754-6_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-55753-9
Online ISBN: 978-3-030-55754-6
eBook Packages: Computer ScienceComputer Science (R0)