Skip to main content
Erschienen in: International Journal on Software Tools for Technology Transfer 3/2019

18.02.2019 | SPIN 2017

An integrated environment for Spin-based C code checking

Towards bringing model-driven code checking closer to practitioners

verfasst von: Daniel Ratiu, Andreas Ulrich

Erschienen in: International Journal on Software Tools for Technology Transfer | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Model-driven code checking (MDCC) has been successfully used for the verification of functional requirements of C code. An environment model that describes the context, which a program is expected to run in, is defined in Promela, translated to a model checker program by Spin, and linked with the program acting as system under verification. In this article, we summarise the practical advantages of MDCC which motivate its use in an industrial setting and discuss the challenges to its broader adoption. Environment models exhibit heavily intertwined Promela and C code statements, which make them hard to write and understand. We propose a high-level language for verification harness definition which hides the Spin engine under the hood. A small number of language concepts is sufficient to define verification harnesses for commonly encountered C programs. Widening the scope of the approach, we provide means to verify programs that exhibit internal state and extend the set of checked properties beyond classical assertions to those checked by LLVM/Clang code sanitizers. Thus, a user can focus on finding the best solution to combine exhaustive exploration of the environment with testing strategies. Our approach is prototypically integrated into mbeddr development platform. We present its instantiation on real-world code examples and discuss our experiences gained with the verification of software from the railway domain.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Arcuri, A., Iqbal, M.Z., Briand, L.: Random testing: theoretical results and practical implications. IEEE Trans. Softw. Eng. 38(2), 258–277 (2012)CrossRef Arcuri, A., Iqbal, M.Z., Briand, L.: Random testing: theoretical results and practical implications. IEEE Trans. Softw. Eng. 38(2), 258–277 (2012)CrossRef
2.
Zurück zum Zitat Beyer, D.: Reliable and reproducible competition results with benchexec and witnesses report on SV-COMP 2016. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). Springer (2016) Beyer, D.: Reliable and reproducible competition results with benchexec and witnesses report on SV-COMP 2016. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS). Springer (2016)
3.
Zurück zum Zitat Beyer, D., Keremoglu, M.E.: CPAchecker: A tool for configurable software verification. In: Computer Aided Verification (CAV). Springer, Berlin (2011) Beyer, D., Keremoglu, M.E.: CPAchecker: A tool for configurable software verification. In: Computer Aided Verification (CAV). Springer, Berlin (2011)
4.
Zurück zum Zitat Beyer, D., Lemberger, T.: Software verification: testing vs. model checking. In: Hardware and Software: Verification and Testing. Springer, Berlin (2017) Beyer, D., Lemberger, T.: Software verification: testing vs. model checking. In: Hardware and Software: Verification and Testing. Springer, Berlin (2017)
5.
Zurück zum Zitat Brezocnik, Z., Vlaovic, B., Vreze, A.: SpinRCP: the Eclipse rich client platform integrated development environment for the Spin model checker. In: International Symposium on Model Checking of Software (2014) Brezocnik, Z., Vlaovic, B., Vreze, A.: SpinRCP: the Eclipse rich client platform integrated development environment for the Spin model checker. In: International Symposium on Model Checking of Software (2014)
6.
Zurück zum Zitat Campagne, F.: The MPS Language Workbench. CreateSpace Publishing, Scotts Valley (2014) Campagne, F.: The MPS Language Workbench. CreateSpace Publishing, Scotts Valley (2014)
7.
Zurück zum Zitat Clarke, E.M., Kroening, D., Lerda, F.: A tool for checking ANSI-C programs. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2004) Clarke, E.M., Kroening, D., Lerda, F.: A tool for checking ANSI-C programs. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (2004)
8.
Zurück zum Zitat Donaldson, A.F., Gay, S.J.: ETCH: An enhanced type checking tool for Promela. In: Workshop on Model Checking Software (SPIN). Springer (2005) Donaldson, A.F., Gay, S.J.: ETCH: An enhanced type checking tool for Promela. In: Workshop on Model Checking Software (SPIN). Springer (2005)
9.
Zurück zum Zitat Felderer, M., Büchler, M., Johns, M., Brucker, A.D., Breu, R., Pretschner, A.: Security testing: a survey. Adv. Comput. 101, 1–51 (2016)CrossRef Felderer, M., Büchler, M., Johns, M., Brucker, A.D., Breu, R., Pretschner, A.: Security testing: a survey. Adv. Comput. 101, 1–51 (2016)CrossRef
10.
Zurück zum Zitat Garcia-Molina, H.: Elections in a distributed computing system. IEEE Trans. Comput. 31(1), 48–59 (1982)CrossRef Garcia-Molina, H.: Elections in a distributed computing system. IEEE Trans. Comput. 31(1), 48–59 (1982)CrossRef
11.
Zurück zum Zitat Groce, A., Joshi, R.: Random testing and model checking: Building a common framework for nondeterministic exploration. In: International Workshop on Dynamic Analysis (WODA) (2008) Groce, A., Joshi, R.: Random testing and model checking: Building a common framework for nondeterministic exploration. In: International Workshop on Dynamic Analysis (WODA) (2008)
12.
Zurück zum Zitat Groce, A., Pinto, J.: A little language for testing. In: NASA Formal Methods (NFM) (2015) Groce, A., Pinto, J.: A little language for testing. In: NASA Formal Methods (NFM) (2015)
13.
Zurück zum Zitat Holmes, J., Groce, A., Pinto, J., Mittal, P., Azimi, P., Kellar, K., O’Brien, J.: TSTL: the template scripting testing language. STTT 20(1), 57–78 (2018)CrossRef Holmes, J., Groce, A., Pinto, J., Mittal, P., Azimi, P., Kellar, K., O’Brien, J.: TSTL: the template scripting testing language. STTT 20(1), 57–78 (2018)CrossRef
14.
Zurück zum Zitat Holzmann, G.: The SPIN Model Checker: Primer and Reference Manual, 1st edn. Addison-Wesley, Boston (2011) Holzmann, G.: The SPIN Model Checker: Primer and Reference Manual, 1st edn. Addison-Wesley, Boston (2011)
15.
Zurück zum Zitat Holzmann, G., Joshi, R., Groce, A.: Model driven code checking. Autom. Softw. Eng. 15, 283–297 (2008)CrossRefMATH Holzmann, G., Joshi, R., Groce, A.: Model driven code checking. Autom. Softw. Eng. 15, 283–297 (2008)CrossRefMATH
16.
Zurück zum Zitat Holzmann, G.J., Joshi, R.: Model-driven software verification. In: Workshop on Model Checking Software (SPIN) (2004) Holzmann, G.J., Joshi, R.: Model-driven software verification. In: Workshop on Model Checking Software (SPIN) (2004)
17.
Zurück zum Zitat Kuhn, D.R., Bryce, R., Duan, F., Ghandehari, L.S., Lei, Y., Kacker, R.N.: Combinatorial testing: theory and practice. Adv. Comput. 99, 1–66 (2015)CrossRef Kuhn, D.R., Bryce, R., Duan, F., Ghandehari, L.S., Lei, Y., Kacker, R.N.: Combinatorial testing: theory and practice. Adv. Comput. 99, 1–66 (2015)CrossRef
18.
Zurück zum Zitat Lattner, C., Adve, V.: LLVM: A compilation framework for lifelong program analysis and transformation. In: International Symposium on Code Generation and Optimization (2004) Lattner, C., Adve, V.: LLVM: A compilation framework for lifelong program analysis and transformation. In: International Symposium on Code Generation and Optimization (2004)
19.
Zurück zum Zitat Mali, Y., Wyk, E.V.: Building extensible specifications and implementations of Promela with AbleP. In: Workshop on Model Checking Software (SPIN) (2011) Mali, Y., Wyk, E.V.: Building extensible specifications and implementations of Promela with AbleP. In: Workshop on Model Checking Software (SPIN) (2011)
20.
Zurück zum Zitat European Union Agency for Railways: ERTMS/ETCS Baseline 3: System Requirements Specifications. SUBSET-026 (2014). Issue 3.4.0 European Union Agency for Railways: ERTMS/ETCS Baseline 3: System Requirements Specifications. SUBSET-026 (2014). Issue 3.4.0
24.
Zurück zum Zitat McMinn, P.: Search-based software test data generation: a survey. Softw. Test. Verif. Reliab. 14, 105–156 (2004)CrossRef McMinn, P.: Search-based software test data generation: a survey. Softw. Test. Verif. Reliab. 14, 105–156 (2004)CrossRef
25.
Zurück zum Zitat Molotnikov, Z., Völter, M., Ratiu, D.: Automated domain-specific C verification with mbeddr. In: International Conference on Automatic Software Engineering (ASE) (2014) Molotnikov, Z., Völter, M., Ratiu, D.: Automated domain-specific C verification with mbeddr. In: International Conference on Automatic Software Engineering (ASE) (2014)
26.
Zurück zum Zitat Pierre Meyer Richard Chavagnat, F.B.: Computation of the safe emergency braking deceleration for trains operated by ETCS/ERTMS using the monte carlo statistical approach. In: Proceedings of the 9th World Congress of Railway Research (WCRR) (2011) Pierre Meyer Richard Chavagnat, F.B.: Computation of the safe emergency braking deceleration for trains operated by ETCS/ERTMS using the monte carlo statistical approach. In: Proceedings of the 9th World Congress of Railway Research (WCRR) (2011)
27.
Zurück zum Zitat Ratiu, D., Ulrich, A.: Increasing usability of Spin-based C code verification using a harness definition language. In: International SPIN Symposium on Model Checking of Software, SPIN 2017 (2017) Ratiu, D., Ulrich, A.: Increasing usability of Spin-based C code verification using a harness definition language. In: International SPIN Symposium on Model Checking of Software, SPIN 2017 (2017)
28.
Zurück zum Zitat Ratiu, D., Voelter, M., Kolb, B., Schätz, B.: Using language engineering to lift languages and analyses at the domain level. In: NASA Formal Methods Symposium (NFM) (2013) Ratiu, D., Voelter, M., Kolb, B., Schätz, B.: Using language engineering to lift languages and analyses at the domain level. In: NASA Formal Methods Symposium (NFM) (2013)
29.
Zurück zum Zitat Ruys, T.C.: Low-fat recipes for SPIN. In: International Workshop on SPIN Model Checking and Software Verification. Springer (2000) Ruys, T.C.: Low-fat recipes for SPIN. In: International Workshop on SPIN Model Checking and Software Verification. Springer (2000)
30.
Zurück zum Zitat Serebryany, K., Bruening, D., Potapenko, A., Vyukov, D.: Addresssanitizer: A fast address sanity checker. In: Proceedings of the 2012 USENIX Conference on Annual Technical Conference. USENIX Association (2012) Serebryany, K., Bruening, D., Potapenko, A., Vyukov, D.: Addresssanitizer: A fast address sanity checker. In: Proceedings of the 2012 USENIX Conference on Annual Technical Conference. USENIX Association (2012)
31.
Zurück zum Zitat Stepanov, E., Serebryany, K.: Memorysanitizer: fast detector of uninitialized memory use in c++. In: International Symposium on Code Generation and Optimization, CGO ’15. Washington, DC, USA (2015) Stepanov, E., Serebryany, K.: Memorysanitizer: fast detector of uninitialized memory use in c++. In: International Symposium on Code Generation and Optimization, CGO ’15. Washington, DC, USA (2015)
32.
Zurück zum Zitat Stephan Horn, O.P.: Chancen und möglichkeiten der monte-carlo-methode bei der bestimmung der etcs-bremskurven. In: Eisenbahntechnische Rundschau (ETR) (2017) Stephan Horn, O.P.: Chancen und möglichkeiten der monte-carlo-methode bei der bestimmung der etcs-bremskurven. In: Eisenbahntechnische Rundschau (ETR) (2017)
33.
Zurück zum Zitat Sulzmann, M., Zechner, A.: Model checking dsl-generated C source code. In: International Workshop on Model Checking Software (SPIN) (2012) Sulzmann, M., Zechner, A.: Model checking dsl-generated C source code. In: International Workshop on Model Checking Software (SPIN) (2012)
34.
Zurück zum Zitat Voelter, M., Benz, S., Dietrich, C., Engelmann, B., Helander, M., Kats, L., Visser, E., Wachsmuth, G.: DSL Engineering. http://dslbook.org (2013) Voelter, M., Benz, S., Dietrich, C., Engelmann, B., Helander, M., Kats, L., Visser, E., Wachsmuth, G.: DSL Engineering. http://​dslbook.​org (2013)
35.
Zurück zum Zitat Voelter, M., Kolb, B., Szabó, T., Ratiu, D., van Deursen, A.: Lessons learned from developing mbeddr: a case study in language engineering with mps. Softw. Syst. Model. pp. 1–46 (2017) Voelter, M., Kolb, B., Szabó, T., Ratiu, D., van Deursen, A.: Lessons learned from developing mbeddr: a case study in language engineering with mps. Softw. Syst. Model. pp. 1–46 (2017)
36.
Zurück zum Zitat Voelter, M., Ratiu, D., Kolb, B., Schätz, B.: mbeddr: instantiating a language workbench in the embedded software domain. Autom. Softw. Eng. 20, 339–390 (2013)CrossRef Voelter, M., Ratiu, D., Kolb, B., Schätz, B.: mbeddr: instantiating a language workbench in the embedded software domain. Autom. Softw. Eng. 20, 339–390 (2013)CrossRef
37.
Zurück zum Zitat de Vos, B., Kats, L.C.L., Pronk, C.: EpiSpin: an eclipse plug-in for promela/spin using spoofax. In: International Workshop on Model Checking Software (SPIN) (2011) de Vos, B., Kats, L.C.L., Pronk, C.: EpiSpin: an eclipse plug-in for promela/spin using spoofax. In: International Workshop on Model Checking Software (SPIN) (2011)
38.
Zurück zum Zitat Yatake, K., Aoki, T.: Automatic generation of model checking scripts based on environment modeling. In: International Conference on Model Checking Software (SPIN). Springer (2010) Yatake, K., Aoki, T.: Automatic generation of model checking scripts based on environment modeling. In: International Conference on Model Checking Software (SPIN). Springer (2010)
39.
Zurück zum Zitat Yu, L., Lei, Y., Kacker, R.N., Kuhn, D.R.: Acts: a combinatorial test generation tool. In: International Conference on Software Testing, Verification and Validation (2013) Yu, L., Lei, Y., Kacker, R.N., Kuhn, D.R.: Acts: a combinatorial test generation tool. In: International Conference on Software Testing, Verification and Validation (2013)
Metadaten
Titel
An integrated environment for Spin-based C code checking
Towards bringing model-driven code checking closer to practitioners
verfasst von
Daniel Ratiu
Andreas Ulrich
Publikationsdatum
18.02.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
International Journal on Software Tools for Technology Transfer / Ausgabe 3/2019
Print ISSN: 1433-2779
Elektronische ISSN: 1433-2787
DOI
https://doi.org/10.1007/s10009-019-00510-w

Weitere Artikel der Ausgabe 3/2019

International Journal on Software Tools for Technology Transfer 3/2019 Zur Ausgabe