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

Contract-based verification of discrete-time multi-rate Simulink models

  • Theme Section Paper
  • Published:
Software & Systems Modeling Aims and scope Submit manuscript

Abstract

This paper presents an approach to modular contract-based verification of discrete-time multi-rate Simulink models. The verification approach uses a translation of Simulink models to sequential programs that can then be verified using traditional software verification techniques. Automatic generation of the proof obligations needed for verification of correctness with respect to contracts, and automatic proofs are also discussed. Furthermore, the paper provides detailed discussions about the correctness of each step in the verification process. The verification approach is demonstrated on a case study involving control software for prevention of pressure peaks in hydraulics systems.

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

Similar content being viewed by others

Notes

  1. Simulink has the notion of virtual and atomic subsystem. Virtual subsystems only syntactically group blocks and do not affect semantics. We discuss only the atomic subsystem where also behaviour is grouped.

  2. The null-space of a matrix A is the set of all vectors q, such that \(Aq=\mathbf {0}\).

  3. https://poseidon.cs.abo.fi/trac/projects/simulinkverktyg/.

References

  1. Abrial, J.-R.: The B-Book: Assigning Programs to Meanings. Cambridge University Press, Cambridge (1996)

    Book  MATH  Google Scholar 

  2. Back, R.-J.R., von Wright, J.: Refinement calculus, part I: sequential nondeterministic programs. In: de Bakker, J.W., de Roever, W.P., Rozenberg, G. (eds.) Stepwise Refinement of Distributed Systems: Models, Formalisms, Correctness, volume 430 of LNCS. Springer, New York (1989)

  3. Back, R.-J.R., von Wright, J.: Refinement Calculus: A Systematic Introduction. Springer, New York (1998)

    Book  MATH  Google Scholar 

  4. Barnett, M., Chang, B.-Y. E., Deline, R., Jacobs, B., Leino, K.R.M.: Boogie: a modular reusable verifier for object-oriented programs. In: de Boer, F.S. et al. (eds.) FMCO’05, volume 4111 of LNCS. Springer, New York (2006)

  5. Barnett, M., Fähndrich, M., Leino, K.R.M., Müller, P., Schulte, W., Venter, H.: Specification and verification: the Spec# experience. Commun. ACM 54(6), 81–91 (2011)

  6. Benveniste, A., Caillaud, B., Passerone, R.: A generic model of contracts for embedded systems. Technical Report 6214, INRIA (2007)

  7. Biernacki, D., Colaço, J.-L., Hamon, G., Pouzet, M.: Clock-directed modular code generation for synchronous data-flow languages. In: LCTES’08. ACM (2008)

  8. Boström, P.: Contract-based verification of Simulink models. In: Qin S., Qiu, Z. (eds.) ICFEM’11, volume 6991 of LNCS. Springer, New York (2011)

  9. Boström, P., Grönblom, R., Huotari, T., Wiik, J.: An approach to contract-based verification of Simulink models. Technical Report 985, TUCS (2010)

  10. Boström, P., Heikkilä, M., Huova, M., Waldén, M., Linjama, M.: Verification and validation of a pressure control unit for hydraulic systems. In: Majzik, I., Vieira, M. (eds.) SERENE’14, volume 8785 of LNCS. Springer, New York (2014)

  11. Burdy, L., Cheon, Y., Cok, D., Ernst, M., Kiniry, J., Leavens, G.T., Leino, K.R.M., Poll, E.: An overview of JML tools and applications. Int. J. Softw. Tools Technol. Transf. 7(3), 212–232 (2005)

  12. Canovas-Dumas, C., Caspi, P.: A PVS proof obligation generator for Lustre programs. In: LPAR’00, volume 1955 of LNAI. Springer, New York (2000)

  13. Caspi, P., Pilaud, D., Halbwachs, N., Plaice, J. A.: LUSTRE: a declarative language for programming synchronous systems. In: POPL’87. ACM (1987)

  14. Cavalcanti, A., Clayton, P., O’Halloran, C.: Control law diagrams in Circus. In: Fitzgerald, J.S., Hayes, I.J., Tarlecki, A. (eds.) FM’05, volume 3582 of LNCS. Springer, New York (2005)

  15. de Moura, L., Bjørner, N.: Z3: an efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS’08, volume 4963 of LNCS. Springer, New York (2008)

  16. Donaldson, A.F., Haller, L., Kroening, D., Rümmer, P.: Software verification using k-induction. In: Yahav, E. (ed.) SAS’11, volume 6887 of LNCS. Springer, New York (2011)

  17. Garoche, P.-L., Kahsai, T., Tinelli, C.: Incremental invariant generation using logic-based automatic abstract transformers. In: Brat, G., Rungta, N., Venet, A. (eds.) NFM’13, volume 7871 of LNCS. Springer, New York (2013)

  18. Hagen, G.: Verifying safety properties of Lustre programs: an SMT-based approach. PhD thesis, The University of Iowa (2008)

  19. Hagen, G., Tinelli, C.: Scaling up the formal verification of Lustre programs with SMT-based techniques. In: FMCAD’08. IEEE (2008)

  20. Halbwachs, N., Lagnier, F., Raymond, P.: Synchronous observers and the verification of reactive systems. In: Nivat, M., Rattray, C., Rus, T., Scollo, G. (eds.) AMAST’93. Springer, New York (1994)

  21. Halbwachs, N., Raymond, P.: Validation of synchronous reactive systems: from formal verification to automatic testing. In: Thiagarajan, P.S., Yap, R. (eds.) ASIAN’99, volume 1742 of LNCS. Springer, New York (1999)

  22. Kahn, G.: The semantics of a simple language for parallel programming. In: Rosenfeld, J.L. (ed.) Information Processing ’74 (1974)

  23. Lee, E.A.: A denotational semantics for dataflow with firing. Technical Report Technical Memorandum UCB/ERL M97/3, Electronics Research Laboratory, Berkeley (1997)

  24. Lee, E.A., Messerschmitt, D.G.: Static scheduling of synchronous data flow programs for digital signal processing. IEEE Trans. Comput. C-36(1), 24–35 (1987)

  25. Lee, E.A., Messerschmitt, D.G.: Synchronous data flow. Proc. IEEE 75(9), 1235–1245 (1987)

  26. Lee, E.A., Parks, T.M.: Dataflow process networks. Proc. IEEE 83(5) (1995)

  27. Leino, K.R.M., Müller, P.: A verification methodology for model fields. In: Sestoft, P. (ed.) ESOP’06, volume 5502 of LNCS. Springer, New York (2006)

  28. Linjama, M., Koskinen, K.T., Vilenius, M.: Accurate tracking control of water hydraulic cylinder with non-ideal on/off valves. Int. J. Fluid Power 4, 7–16 (2003)

  29. Lublinerman, R., Tripakis, S.: Modular code generation from triggered and timed block diagrams. In: RTAS’08. IEEE (2008)

  30. Maraninchi, F., Morel, L.: Logical-time contracts for reactive embedded components. In: EUROMICRO’04. IEEE (2004)

  31. Mathworks Inc., Simulink. http://www.mathworks.com (2015)

  32. Mosterman, P.J., Zander, J., Hamon, G., Denckla, B.: A computational model of time for stiff hybrid systems applied to control synthesis. Control Eng. Pract. 20(1), 2–13 (2012)

  33. Murugesan, A., Whalen, M.W., Rayadurgam, S., Heimdahl, M.P.E.: Compositional verification of a medical device system. In: HILT’13. ACM (2013)

  34. Nuzzo, P., Iannopollo, A., Tripakis, S., Sangiovanni-Vincentelli, A.L.: From relational interfaces to assume-guarantee contracts. Technical Report UCB/EECS-2014-21, EECS/UC Berkeley (2014)

  35. Reicherdt, R., Glesner, S.: Formal verification of discrete-time MATLAB/Simulink models using Boogie. In: Giannakopoulou, D., Salaün, G. (eds.) SEFM’14, volume 8702 of LNCS. Springer, New York (2014)

  36. Roy, P., Shankar, N.: SimCheck: a contract type system for Simulink. Innov. Syst. Softw. Eng. 7(2), 73–83 (2011)

  37. Sheeran, M., Singh, S., Stålmarck, G.: Checking safety properties using induction and a SAT-solver. In: Hunt, W.A., Jr., Johnson, S.D. (eds.) FMCAD’00, volume 1954 of LNCS. Springer, New York (2000)

  38. Tafat, A., Boulmé, S., Marché, C.: A refinement methodology for object-oriented programs. In: Beckert, B., Marché, C. (eds.) FoVeOOS’10, volume 6528 of LNCS. Springer, New York (2011)

  39. Tripakis, S., Bui, D., Geilen, M., Rodiers, B., Lee, E.A.: Compositionality in synchronous data flow: modular code generation from hierarchical SDF graphs. ACM Trans. Embed. Comput. Syst. 12(3), 83:1–83:26 (2013)

  40. Tripakis, S., Lickly, B., Henzinger, T.A., Lee, E. A.: A theory of synchronous relational interfaces. ACM Trans. Program. Lang. Syst. 33(4), 14:1–14:41 (2011)

  41. Tripakis, S., Sofronis, C., Caspi, P., Curic, A.: Translating discrete-time Simulink to Lustre. ACM Trans. Embed. Comput. Syst. 4(4), 779–818 (2005)

  42. Wiik, J.: Contract-based verification of multi-rate Simulink models. Master’s thesis, Åbo Akademi University (2012)

  43. Wiik, J., Boström, P.: Contract-based verification of MATLAB and Simulink matrix-manipulating code. In: Merz, S., Pang, J. (eds.) ICFEM’14, volume 8829 of LNCS. Springer, New York (2014)

Download references

Acknowledgments

This work was partially funded by the EFFIMA program coordinated by Fimecc and the EDiHy Project (No. 140003) funded by the Academy of Finland. We would also like to thank the reviewers for their insightful comments.

Author information

Authors and Affiliations

  1. Åbo Akademi University, Turku, Finland

    Pontus Boström & Jonatan Wiik

Authors
  1. Pontus Boström
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jonatan Wiik
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jonatan Wiik.

Additional information

Communicated by Prof. Einar Broch Johnsen and Luigia Petre.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Boström, P., Wiik, J. Contract-based verification of discrete-time multi-rate Simulink models. Softw Syst Model 15, 1141–1161 (2016). https://doi.org/10.1007/s10270-015-0477-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10270-015-0477-x

Keywords

Search

Navigation