Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An integrated environment for Spin-based C code checking

Towards bringing model-driven code checking closer to practitioners

  • SPIN 2017
  • Published:
International Journal on Software Tools for Technology Transfer Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20

Similar content being viewed by others

Notes

  1. http://spinroot.com/spin/whatispin.html.

  2. https://www.jetbrains.com/mps/.

  3. https://sites.google.com/site/ratiud/tools.

  4. https://sites.google.com/site/ratiud/tools.

  5. https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html.

  6. http://statmath.wu.ac.at/software/prng/.

  7. https://www.gnu.org/software/gsl/.

References

  1. Arcuri, A., Iqbal, M.Z., Briand, L.: Random testing: theoretical results and practical implications. IEEE Trans. Softw. Eng. 38(2), 258–277 (2012)

    Article  Google Scholar 

  2. 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. Beyer, D., Keremoglu, M.E.: CPAchecker: A tool for configurable software verification. In: Computer Aided Verification (CAV). Springer, Berlin (2011)

  4. Beyer, D., Lemberger, T.: Software verification: testing vs. model checking. In: Hardware and Software: Verification and Testing. Springer, Berlin (2017)

  5. 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. Campagne, F.: The MPS Language Workbench. CreateSpace Publishing, Scotts Valley (2014)

    Google Scholar 

  7. 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. Donaldson, A.F., Gay, S.J.: ETCH: An enhanced type checking tool for Promela. In: Workshop on Model Checking Software (SPIN). Springer (2005)

  9. Felderer, M., Büchler, M., Johns, M., Brucker, A.D., Breu, R., Pretschner, A.: Security testing: a survey. Adv. Comput. 101, 1–51 (2016)

    Article  Google Scholar 

  10. Garcia-Molina, H.: Elections in a distributed computing system. IEEE Trans. Comput. 31(1), 48–59 (1982)

    Article  Google Scholar 

  11. 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. Groce, A., Pinto, J.: A little language for testing. In: NASA Formal Methods (NFM) (2015)

  13. 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)

    Article  Google Scholar 

  14. Holzmann, G.: The SPIN Model Checker: Primer and Reference Manual, 1st edn. Addison-Wesley, Boston (2011)

    Google Scholar 

  15. Holzmann, G., Joshi, R., Groce, A.: Model driven code checking. Autom. Softw. Eng. 15, 283–297 (2008)

    Article  MATH  Google Scholar 

  16. Holzmann, G.J., Joshi, R.: Model-driven software verification. In: Workshop on Model Checking Software (SPIN) (2004)

  17. 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)

    Article  Google Scholar 

  18. Lattner, C., Adve, V.: LLVM: A compilation framework for lifelong program analysis and transformation. In: International Symposium on Code Generation and Optimization (2004)

  19. Mali, Y., Wyk, E.V.: Building extensible specifications and implementations of Promela with AbleP. In: Workshop on Model Checking Software (SPIN) (2011)

  20. European Union Agency for Railways: ERTMS/ETCS Baseline 3: System Requirements Specifications. SUBSET-026 (2014). Issue 3.4.0

  21. Synopsys, Inc.: Static application security testing (coverity). https://www.synopsys.com/software-integrity/security-testing/static-analysis-sast.html (2018). Accessed 9 Apr 2018

  22. The Clang Team: Clang Compiler User’s Manual (2018). https://clang.llvm.org/docs/UsersManual.html. Accessed 9 Apr 2018

  23. The MathWorks, Inc.: Polyspace – making critical code safe and secure. https://de.mathworks.com/products/polyspace.html (2018). Accessed 9 Apr 2018

  24. McMinn, P.: Search-based software test data generation: a survey. Softw. Test. Verif. Reliab. 14, 105–156 (2004)

    Article  Google Scholar 

  25. Molotnikov, Z., Völter, M., Ratiu, D.: Automated domain-specific C verification with mbeddr. In: International Conference on Automatic Software Engineering (ASE) (2014)

  26. 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. 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. 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. Ruys, T.C.: Low-fat recipes for SPIN. In: International Workshop on SPIN Model Checking and Software Verification. Springer (2000)

  30. 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. 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. Stephan Horn, O.P.: Chancen und möglichkeiten der monte-carlo-methode bei der bestimmung der etcs-bremskurven. In: Eisenbahntechnische Rundschau (ETR) (2017)

  33. Sulzmann, M., Zechner, A.: Model checking dsl-generated C source code. In: International Workshop on Model Checking Software (SPIN) (2012)

  34. Voelter, M., Benz, S., Dietrich, C., Engelmann, B., Helander, M., Kats, L., Visser, E., Wachsmuth, G.: DSL Engineering. http://dslbook.org (2013)

  35. 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. 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)

    Article  Google Scholar 

  37. 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. 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. 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)

  40. Zalewski, M.: American fuzzy lop. http://lcamtuf.coredump.cx/afl/ (2018). Accessed 29 Apr 2018

Download references

Acknowledgements

We would like to thank Dorel Coman for contributing to the implementation of Spin language extensions, Ulrich Hipp for explaining us the technicalities behind the computation of \(K_\mathrm{dry}\) and helping us with performing the verification, and Olivera Pavlovic for feedback.

Author information

Authors and Affiliations

  1. Siemens, Corporate Technology, Munich, Germany

    Daniel Ratiu & Andreas Ulrich

Authors
  1. Daniel Ratiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andreas Ulrich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniel Ratiu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ratiu, D., Ulrich, A. An integrated environment for Spin-based C code checking. Int J Softw Tools Technol Transfer 21, 267–286 (2019). https://doi.org/10.1007/s10009-019-00510-w

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10009-019-00510-w

Keywords

Search

Navigation