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

Introducing probabilistic reasoning within Event-B

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

Abstract

Event-B is a proof-based formal method used for discrete systems modelling. Several works have previously focused on the extension of Event-B for the description of probabilistic systems. In this paper, we propose an extension of Event-B that allows designing fully probabilistic systems as well as systems containing both probabilistic and non-deterministic choices. Compared to existing approaches which only focus on probabilistic assignments, our approach allows expressing probabilistic choices in all places where non-deterministic choices originally appear in a standard Event-B model: in the choice between enabled events, event parameter values and in probabilistic assignments. Furthermore, we introduce novel and adapted proof obligations for the consistency of such systems and introduce two key aspects to incremental design: probabilisation of existing events and refinement through the addition of new probabilistic events. In particular, we provide proof obligations for the almost-certain convergence of a set of new events, which is a required property in order to prove standard refinement in this context. Finally, we propose a fully detailed case study, which we use throughout the paper to illustrate our new constructions.

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

Similar content being viewed by others

References

  1. Abrial, J.-R.: Modeling in Event-B: System and Software Engineering. Cambridge University Press, Cambridge (2010)

    Book  MATH  Google Scholar 

  2. Abrial, J.-R., Butler, M., Hallerstede, S., Hoang, T.S., Mehta, F., Voisin, L.: Rodin: an open toolset for modelling and reasoning in event-b. Int. J. Softw. Tools Technol. Transf. 12(6), 447–466 (2010)

    Article  Google Scholar 

  3. Abrial, J.-R., Cansell, D., Méry, D.: A mechanically proved and incremental development of ieee 1394 tree identify protocol. Form. Aspects Comput. 14(3), 215–227 (2003)

    Article  MATH  Google Scholar 

  4. Aouadhi, M.A., Delahaye, B., Lanoix, A.: Moving from event-b to probabilistic event-b. In: Proceedings of the 32nd Annual ACM Symposium on Applied Computing. ACM (2017, to appear)

  5. Audebaud, P., Paulin-Mohring, C.: Proofs of randomized algorithms in coq. Sci. Comput. Program. 74(8), 568–589 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Back, R.-J.: Refinement calculus, part ii: Parallel and reactive programs. In: Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness, pp. 67–93. Springer (1990)

  7. Back, R.J., von Wright, J.: Refinement calculus, part i: Sequential nondeterministic programs. In: Stepwise Refinement of Distributed Systems Models, Formalisms, Correctness, pp. 42–66. Springer (1990)

  8. Baier, C., Katoen, J.-P., et al.: Principles of Model Checking, pp. 2620–2649. MIT Press, Cambridge (2008)

    MATH  Google Scholar 

  9. Barthe, G., Fournet, C., Grégoire, B., Strub, P.-Y., Swamy, N., Zanella-Béguelin, S.: Probabilistic relational verification for cryptographic implementations. In: ACM SIGPLAN Notices, vol. 49, pp. 193–205. ACM (2014)

  10. Bert, D., Cave, F.: Construction of finite labelled transition systems from b abstract systems. In: Integrated Formal Methods, LNCS, vol. 1945, pp. 235–254. Springer (2000)

  11. Bianco, A., De Alfaro, L.: Model checking of probabilistic and nondeterministic systems. In: International Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 499–513. Springer (1995)

  12. BitTorrent description. http://www.bittorrent.com/lang/fr/

  13. Butler, M., Maamria, I.: Practical theory extension in event-b. In: Theories of Programming and Formal Methods, LNCS, vol. 8051, pp. 67–81 (2013)

  14. Chu, W.W., Sit, C.-M.: Estimating task response time with contentions for real-time distributed systems. In Real-Time Systems Symposium, 1988., Proceedings., pp. 272–281. IEEE (1988)

  15. De Roever, W.-P., Engelhardt, K., Buth, K.-H.: Data Refinement: Model-Oriented Proof Methods and Their Comparison, vol. 47. Cambridge University Press, Cambridge (1998)

    Book  MATH  Google Scholar 

  16. Dehnert, C., Gebler, D., Volpato, M., Jansen, D.N.: On Abstraction of Probabilistic Systems, pp. 87–116. Springer Berlin Heidelberg, Berlin (2014)

    MATH  Google Scholar 

  17. Goldreich, O.: Probabilistic proof systems. In: Modern Cryptography, Probabilistic Proofs and Pseudorandomness, pp. 39–72. Springer (1999)

  18. Haghighi, H., Afshar, M.: A z-based formalism to specify Markov chains. Comput. Sci. Eng. 2(3), 24–31 (2012)

    Article  Google Scholar 

  19. Hallerstede, S., Hoang, T.S.: Qualitative probabilistic modelling in event-b. In: Integrated Formal Methods, pp. 293–312. Springer (2007)

  20. He, J., Hoare, C., Sanders, J.W.: Data refinement refined resume. In: ESOP 86, pp. 187–196. Springer (1986)

  21. Hoang, T.S.: The development of a probabilistic B-method and a supporting toolkit. PhD thesis, The University of New South Wales (2005)

  22. Hoang, T.S.: Reasoning about almost-certain convergence properties using event-b. Sci. Comput. Program. 81, 108–121 (2014)

    Article  Google Scholar 

  23. Hurd, J.: Formal verification of probabilistic algorithms. PhD thesis, University of Cambridge, Computer Laboratory (2003)

  24. Hurd, J., McIver, A., Morgan, C.: Probabilistic guarded commands mechanized in hol. Electron. Notes Theor. Comput. Sci. 112, 95–111 (2005)

    Article  MATH  Google Scholar 

  25. Jonsson, B., Larsen, K.G.: Specification and refinement of probabilistic processes. In: Proceedings of Sixth Annual IEEE Symposium on Logic in Computer Science, 1991. LICS’91, pp. 266–277. IEEE (1991)

  26. Katoen, J.-P.: Abstraction of Probabilistic Systems, pp. 1–3. Springer Berlin Heidelberg, Berlin (2007)

    MATH  Google Scholar 

  27. Mayr, R., Henda, N.B., Abdulla, P.A.: Decisive Markov chains. Log. Methods Comput. Sci. 3, 7 (2007)

    MathSciNet  MATH  Google Scholar 

  28. McIver, A., Morgan, C.C.: Abstraction, Refinement and Proof for Probabilistic Systems. Springer, Berlin (2006)

    MATH  Google Scholar 

  29. Morgan, C., Hoang, T.S., Abrial, J.-R.: The challenge of probabilistic event b—extended abstract. In: ZB 2005: Formal Specification and Development in Z and B, pp. 162–171. Springer (2005)

  30. Motwani, R., Raghavan, P.: Randomized Algorithms. Chapman & Hall/CRC, Boca Raton (2010)

    MATH  Google Scholar 

  31. Prism modelchecker description. http://www.prismmodelchecker.org/

  32. Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, New York (2014)

    MATH  Google Scholar 

  33. Sere, K., Troubitsyna, E.: Probabilities in action systems. In: Proceedings of the 8th Nordic Workshop on Programming Theory, pp. 373–387 (1996)

  34. Stoelinga, M.: An introduction to probabilistic automata. Bull. EATCS 78(176–198), 2 (2002)

    MathSciNet  MATH  Google Scholar 

  35. Tarasyuk, A., Troubitsyna, E., Laibinis, L.: Reliability assessment in event-b development. In: NODES 09, p. 11 (2009)

  36. Tarasyuk, A., Troubitsyna, E., Laibinis, L.: Towards probabilistic modelling in event-b. In: Integrated Formal Methods, pp. 275–289. Springer (2010)

  37. Tarasyuk, A., Troubitsyna, E., Laibinis, L.: Integrating stochastic reasoning into event-b development. Form. Aspects Comput. 27(1), 53–77 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  38. Trivedi, K.S., Ramani, S., Fricks, R.: Recent advances in modeling response-time distributions in real-time systems. Proc. IEEE 91(7), 1023–1037 (2003)

    Article  Google Scholar 

  39. Villemeur, A.: Reliability, Availability, Maintainability and Safety Assessment, Assessment, Hardware, Software and Human Factors, vol. 2. Wiley, New York (1992)

    Google Scholar 

  40. Yilmaz, E.: Tool support for qualitative reasoning in Event-B. PhD thesis, Master Thesis ETH Zürich, 2010 (2010)

Download references

Author information

Authors and Affiliations

  1. LS2N UMR CNRS 6004, University of Nantes, Nantes, France

    Mohamed Amine Aouadhi, Benoît Delahaye & Arnaud Lanoix

Authors
  1. Mohamed Amine Aouadhi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Benoît Delahaye
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Arnaud Lanoix
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benoît Delahaye.

Additional information

Communicated by Dr. Juergen Dingel.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Aouadhi, M.A., Delahaye, B. & Lanoix, A. Introducing probabilistic reasoning within Event-B. Softw Syst Model 18, 1953–1984 (2019). https://doi.org/10.1007/s10270-017-0626-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10270-017-0626-5

Keywords

Search

Navigation