Магистратура
2021/2022
Формальные методы программной инженерии
Статус:
Курс обязательный (Системная и программная инженерия)
Направление:
09.04.04. Программная инженерия
Кто читает:
Департамент программной инженерии
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1-4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Прогр. обучения:
Системная и программная инженерия
Язык:
английский
Кредиты:
10
Контактные часы:
128
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
- 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 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
- 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_exam1Students can be exempted from the exam, if not more than 2 classes are skipped and O_accum1 is greater or equal than 8.
- O_current2
- O_htask2
- O_exam2Students 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
- 2021/2022 2nd module0.5 * O_accum1 + 0.5 * O_exam1
- 2021/2022 4th module0.4 * O_exam2 + 0.3 * O_current2 + 0.12 * 2021/2022 2nd module + 0.18 * O_htask2
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