Formal Methods in Software Engineering

Master 2020/2021

Type: Compulsory course (System and Software Engineering)

Area of studies: Software Engineering

Delivered by: School of Software Engineering

Where: Faculty of Computer Science

When: 1 year, 1-4 module

Mode of studies: offline

Instructors: Irina A. Lomazova, Roman Nesterov

Master’s programme: Software and Systems Engineering

Language: English

ECTS credits: 10

Contact hours: 128

Full 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

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

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

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

O_accum1
O_exam1
O_current2
O_htask
O_exam2
Письменный экзамен с помощью MS Teams / MS Forms - студенты авторизуются по студенческой почте в домене edu.hse.ru Технические требования: web-камера, микрофон, наушники / колонки

Interim Assessment

Interim assessment (2 module)
0.5 * O_accum1 + 0.5 * O_exam1
Interim assessment (4 module)
0.12 * Interim assessment (2 module) + 0.3 * O_current2 + 0.4 * O_exam2 + 0.18 * O_htask

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

Course Syllabus