Collaborative Systems

Преподаватели:

Max Kanovich

Professor of Computer Science, University College London

 

Andre Scedrov

Chair of the Mathematics Department, University of Pennsylvania

 

В курсе рассматриваются следующие темы:

1. Analysis of Network Security Protocols
2. Kerberos Authentication Protocol
3. Bounded Adversary
4. Timed Collaborative Systems 
5. Resource reasoning in timed collaborative systems and program analysis
   • Basics, where the fundamental ideas of the resource logics (linear logic, separation logic) are presented in a semi-formal style.
   • Foundations, where, for general resource models, on one hand, and for concrete heap-like models of practical interest, on the other hand, we get into the formalities, including the semantics of the assertion language and axioms and inference rules. Surprisingly, as for the assertion language of separation logic, even purely propositional separation logic turns out to be undecidable. What is more, whatever concrete heap-like model H we take, it is undecidable whether a purely propositional formula A is valid in this model H.
   • Horn linear logic (a.k.a. multiset rewriting systems), where we research into the computational complexity of planning within real-time collaborative systems. A particular focus is on planning under uncertainty caused by actions with non-deterministic effects and/or quantitatively non-deterministic and continuous delayed effects.
   • `New' logical principles for program analysis. Abduction, the problem of discovering hypotheses that support a conclusion, has mainly been studied in the context of philosophical logic and AI. Recently, the abduction principle — given A and B, find a non-trivial X such that A * X entails B, is one of the powerful practical tools for iterated deduction and hypothesis formation to `dig information out of bare code'. We study the complexity of abduction for a relevant fragment of separation logic over `symbolic heaps' which include a basic `points-to' predicate, and an inductive predicate for describing linked-list segments.

Материалы:

 Symbolic Analysis of Computer Network Security Protocols (PDF, 654 Кб)

 Formal Analysis of Kerberos 5 (PDF, 628 Кб)

Расписание занятий

• 16 декабря, 16:40 – 18.00, Кочновский проезд, д. 3, ауд. 300
• 18 декабря, 16:40 – 18:20, Кочновский проезд, д. 3, ауд. 317
• 19 декабря, 16:40 – 17:50, Кочновский проезд, д. 3, ауд. 402
• 22 декабря, 16:40 – 19:40, Кочновский проезд, д. 3, ауд. 400
• 23 декабря, 16:40 – 18:00, Кочновский проезд, д. 3, ауд. 400
• 25 декабря, 16:40 – 18:00, Кочновский проезд, д. 3, ауд. 317
• 26 декабря, 17:00 – 19:30, Кочновский проезд, д. 3, ауд. 327

В расписании возможны изменения.