• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Formal Methods in Software Engineering

2021/2022
Academic Year
ENG
Instruction in English
10
ECTS credits
Course type:
Compulsory course
When:
1 year, 1-4 module

Instructors

Course Syllabus

Abstract

In computer science and software engineering, formal methods are a particular kind of mathematically based techniques for the specification, development and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the fact that, as in other engineering disciplines, performing appropriate mathematical analysis can contribute to the reliability and robustness of a design. Formal methods are best described as the application of a fairly broad variety of theoretical computer science fundamentals, in particular logic calculi, formal languages, automata theory, and program semantics, but also type systems and algebraic data types to problems in software and hardware specification and verification. Formal methods can: (a) be a foundation for describing complex systems; (b) be a foundation for reasoning about systems; (c) provide support for program development. In contrast to other system design approaches, formal methods use mathematical proof as a complement to system testing in order to ensure correct behavior. As systems become more complicated, and safety becomes a more important issue, the formal approach to system design offers another level of insurance. Formal methods differ from other design methods by the use of formal verification schemes, the basic principles of the system must be proven correct before they are accepted. Traditional system design uses extensive testing to verify behavior, but testing is capable of only finite conclusions. E. Dijkstra and others have demonstrated that tests can help to find fails and bugs, but cannot guarantee their absence. In contrast, once a theorem is proven true it remains true. It is very important to note that formal verification does not obviate the need for testing. Formal verification cannot fix bad assumptions in the design, but it can help identify errors in reasoning which would otherwise be left unverified. In several cases, engineers have reported finding flaws in systems once they reviewed their designs formally.
Learning Objectives

Learning Objectives

  • To learn basic principles of using formal methods for the specification and analysis of software systems
  • To learn how to specify the formal semantics of sequential and concurrent systems
  • To learn how to use formalisms, such as process algebras and Petri nets, and corresponding methods for modeling and analyzing concurrent and distributed systems
  • To learn how to use methods and algorithms for model checking of concurrent systems
  • To master methods and tools of software specification, analysis and verification
Expected Learning Outcomes

Expected Learning Outcomes

  • To apply specific techniques for the analysis and verification of distributed systems;
  • To formulate and prove properties of distributed systems within studied formalisms
  • To interpret and apply the formal languages of the formalisms for modeling distributed systems
  • To model various classes of distributed systems within appropriate formalisms
  • To model various classes of distributed systems within appropriate formalisms;
Course Contents

Course Contents

  • Formal methods as a basis for software reliability
  • Floyd method for verification of sequential programs. Hoare axiomatic semantics for sequential and parallel programs.
  • Finite state machines (FSMs): basic definitions, operational semantics. Categories of FSMs. Extended FSMs. Modeling concurrent systems with communicating FSMs.
  • Petri nets: basic notions, definitions and classification. Modeling distributed systems with Petri nets.
  • Petri nets analysis. Checking structural and behavioral properties.
  • High-level Petri nets. Colored Petri nets and CPNTools.
  • Modeling distributed and concurrent system with process algebras. Structured operational semantics and its formalization (SOS). Algebra CCS: syntax, semantics, modeling technique.
  • The notion and properties of bisimilarity relation.
  • Verifying reactive concurrent systems with CCS. Hennesy-Milner logic and temporal properties. The notion of fixed point and Tarski’s fixed point theorem
  • Transition systems and program graphs. Nondeterminism, parallelism and communication. Peterson algorithm
  • Specifying distributed systems with Promela. Spin model checker.
  • Temporal logics LTL and CTL for specification of behavioral properties of reactive systems.
  • Automata-based approach for verification of LTL formulae.
  • Model checking algorithm for verification of CTL formulae
Assessment Elements

Assessment Elements

  • non-blocking O_accum1
  • non-blocking O_exam1
    Students can be exempted from the exam, if not more than 2 classes are skipped and O_accum1 is greater or equal than 8.
  • non-blocking O_current2
  • non-blocking O_htask2
  • non-blocking O_exam2
    Students can be exempted from the exam in the second semester, if no more than 2 classes are skipped, seminar activity (O_current2), the home assignment (O_htask2), and the interim assessment (in the first semester) were given at least 8 points.
Interim Assessment

Interim Assessment

  • 2021/2022 2nd module
    0.5 * O_accum1 + 0.5 * O_exam1
  • 2021/2022 4th module
    0.4 * O_exam2 + 0.3 * O_current2 + 0.12 * 2021/2022 2nd module + 0.18 * O_htask2
Bibliography

Bibliography

Recommended Core Bibliography

  • Baeten, J. C. M., Reniers, M. A., & Basten, T. G. H. (2010). Process Algebra: Equational Theories of Communicating Processes. Cambridge: Cambridge University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=317653
  • Baier, C., & Katoen, J.-P. (2008). Principles of Model Checking. Cambridge, Mass: The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=226091
  • Fisher, M. (2011). An Introduction to Practical Formal Methods Using Temporal Logic. Chichester, West Sussex, U.K.: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=509889
  • Jensen, K., & Kristensen, L. M. (2009). Coloured Petri Nets : Modelling and Validation of Concurrent Systems. Dordrecht: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=285464

Recommended Additional Bibliography

  • Wan Fokkink, Jan Friso Groote, & Michel Reniers. (2003). Modelling Distributed Systems. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E2E909CB
  • Wil van der Aalst, & Kees van Hee. (2004). Workflow Management: Models, Methods, and Systems. The MIT Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsrep&AN=edsrep.b.mtp.titles.0262720469