+**********************************************************************

*

*

*                          Einladung

*

*

*

*                     Informatik-Oberseminar

*

*

*

+**********************************************************************

Zeit:  Donnerstag, 9. Januar 2019, 14.00 Uhr

Ort:   Informatikzentrum, E3, Raum 9222

Referent: Christoph Matheja, M.Sc.

                  Lehrstuhl für Informatik 2 (Software Modeling and Verification)

Thema: Automated Reasoning and Randomization in Separation Logic

Abstract:

We study three aspects of program verification with separation logic:

1. Reasoning about quantitative properties, such as the probability of memory-safe termination, of randomized heap-manipulating programs.

2. Automated reasoning about the robustness of and entailments between formulas in the symbolic heap fragment of separation logic itself.

3. Automated reasoning about pointer programs by combining abstractions based on separation logic with the above techniques and model checking.

Regarding the first item, we extend separation logic to reason about quantities, which evaluate to real numbers, instead of predicates, which evaluate to Boolean values. Based on the resulting quantitative separation logic, we develop a weakest precondition calculus à la Dijkstra for quantitative reasoning about randomized heap-manipulating programs. We show that this calculus is a sound and conservative extension of both separation logic and McIver and Morgan's weakest preexpectations which preserves virtually all properties of classical separation logic. We demonstrate its applicability by several case studies.

Regarding the second item, we develop an algorithmic framework based on heap automata to compositionally check robustness properties, e.g., satisfiability or acyclicity, of symbolic heaps with inductive predicate definitions. We consider two approaches to discharge entailments for fragments of separation logic. In particular, this includes a pragmatic decision procedure with nondeterministic polynomial-time complexity for entailments between graphical symbolic heaps.

Regarding the third item, we introduce Attestor - an automated verification tool for analyzing Java programs operating on dynamic data structures. The tool involves the generation of an abstract state space employing inductive predicate definitions in separation logic. Properties of individual states are defined by heap automata. LTL model checking is then applied to this state space, supporting the verification of both structural and functional correctness properties. Attestor is fully automated, procedure modular, and provides informative visual feedback including counterexamples for violated properties.

Es laden ein: die Dozentinnen und Dozenten der Informatik