VSL 2014: VIENNA SUMMER OF LOGIC 2014
VSTTE ON THURSDAY, JULY 17TH, 2014
Days:
next day
all days

View: session overviewtalk overviewside by side with other conferences

10:15-10:45Coffee Break
10:45-13:00 Session 66AP: Analysis: Understanding and Explanation
Location: FH, Zeichensaal 3
10:45
Finding Security Vulnerabilities in a Network Protocol using Parameterized Systems
SPEAKER: Orna Grumberg

ABSTRACT. This paper presents a novel approach to automatically finding security
vulnerabilities in the routing protocol OSPF -- the most widely used
protocol for Internet routing. We start by modeling  OSPF on (concrete)
networks with a fixed number of routers in a specific topology. By using the
model checking tool CBMC, we found several simple, previously unpublished
attacks on OSPF.

In order to search for attacks in a  family of networks with varied sizes
and topologies, we define the concept of an  abstract network which
represents such a family. The abstract network A has the property that if
there is an attack on A then there is a corresponding attack on each of the
(concrete) networks represented by A.

The attacks we have found on abstract networks reveal security
vulnerabilities in the OSPF protocol, which can harm routing in huge
networks with complex topologies. Finding such attacks directly on the huge
networks is practically impossible. Abstraction is therefore essential.
Further, abstraction enables showing that the attacks are  general. That is,
they are applicable in a large (even infinite) number of networks.
This indicates that the attacks exploit fundamental vulnerabilities, which
are applicable to many configurations of the network.

This is a joint work with Adi Sosnovich and Gabi Nakibly.

11:45
A Model for Capturing and Replaying Proof Strategies

ABSTRACT. Modern theorem provers can discharge a significant proportion of Proof Obligations (POs) that arise in the use of Formal Methods (FMs). Unfortunately, the residual POs require tedious manual guidance. On the positive side, these "difficult" POs tend to fall into families each of which requires only a few key ideas to unlock. This paper outlines a system that can identify and characterise ways of discharging POs of a family by tracking an interactive proof of one member of the family. This opens the possibility of capturing ideas from an expert and/or maximising reuse of ideas after changes to definitions. The proposed system has to store a wealth of meta-information about conjectures, which can be matched against previously learned strategies, or can be used to construct new strategies based on expert guidance. This paper describes this meta-information and how it is used to lessen the burden of FM proofs.

12:10
A Verification Condition Visualizer
SPEAKER: unknown

ABSTRACT. When first encountering data structures such as arrays, records and pointers programmers are often presented with pictorial representations. The use of pictures to describe data structures and their manipulation can help establish basic programming intuitions. The same is true of program proving where pictures are frequently used within the literature to describe program properties such as loop invariants. Here we report on an experimental prototype of a visualization tool that translates verification conditions arising from array based code into pictures. While initially aimed at supporting teaching, we have received positive feedback from users of program proving tools within industry.

12:35
What Gives? A Hybrid Algorithm for Error Explanation
SPEAKER: unknown

ABSTRACT. When a program fails, the cause of the failure is often buried in a long, hard-to-understand error trace. We present a new technique for automatic error localization, which formally unifies prior approaches based on computing interpolants and minimal unsatisfiable cores of failing executions. Our technique works by automatically reducing an error trace to its essential components—a minimal set of statements that are responsible for the error, together with key predicates that explain how these statements lead to the failure. We prove that our approach is sound, and we show that it is useful for debugging real programs.

13:00-14:30Lunch Break
14:30-16:00 Session 75AN: Verification Frameworks and Applications
Location: FH, Zeichensaal 3
14:30
Efficient Refinement Checking in VCC

ABSTRACT. We propose a methodology for carrying out refinement proofs across declarative abstract models and concrete implementations in C, using the VCC verification tool. The main idea is to first do a systematic translation from the top-level abstract model to a ghost implementation in VCC. Subsequent refinement proofs between successively refined abstract models and between abstract and C implementations are carried out in VCC. We propose an efficient technique to carry out these refinement checks in VCC. We illustrate our methodology with a case study in which we verify a simplified C implementation of an RTOS scheduler, with respect to its abstract Z specification. Overall, our methodology leads to efficient and automatic refinement proofs for complex systems that would typically be beyond the capability of tools like Z-Eves or Rodin.

14:55
Formalizing Semantics with an Automatic Program Verifier
SPEAKER: unknown

ABSTRACT. A common belief is that formalizing semantics of programming languages requires the use of a \emph{proof assistant} providing (1) a specification language with advanced features such as higher-order logic, inductive definitions, type polymorphism (2) a corresponding proof environment where higher-order and inductive reasoning can be performed, typically with user interaction.

In this paper we show that such a formalization is nowadays possible inside a mostly-automatic program verification environment. We substantiate this claim by formalizing several semantics for a simple language, and proving their equivalence, inside the Why3 environment.

15:20
The KeY Platform for Verification and Analysis of Java Programs
SPEAKER: Daniel Bruns

ABSTRACT. The KeY system offers a platform of software analysis tools for sequential Java. Foremost, this includes full functional verification against contracts written in the Java Modeling Language. But the approach is general enough to provide a basis for other methods and purposes:

  1. complementary validation techniques to formal verification such as testing and debugging,
  2. methods that reduce the complexity of verification such as modularization and abstract interpretation,
  3. analyses of non-functional properties such as information flow security, and
  4. sound program transformation and code generation.

We show that deductive technology that has been developed for full functional verification can be used as a basis and framework for other purposes than pure functional verification. We use the current release of the KeY system as an example to explain and prove this claim.

15:45
Using Promela in a Fully Verified Executable LTL Model Checker (SHORT)
SPEAKER: René Neumann

ABSTRACT. At CAV'13 we presented an LTL model checker whose code has been completely verified using the Isabelle theorem prover. The intended use of the checker is to provide a trusted reference implementation against which more advanced checkers can be tested. However, for CAV'13 the checker still used an ad-hoc, primitive input language.

In this paper we report on CAVA, a new version of the checker accepting inputs written in Promela. We report on our formalization of the Promela semantics within Isabelle, which is used both to define the semantics and to automatically generate code for the computation of the state space. We report on experiments on standard Promela benchmarks comparing our tool to SPIN.

16:00-16:30Coffee Break
16:30-19:00 Session 79A: VSL Joint Award Ceremony 1
Location: MB, Kuppelsaal
16:30
Foundations and Technology Competitions Award Ceremony

ABSTRACT. The third round of the Kurt Gödel Research Prize Fellowships Program, under the title: Connecting Foundations and Technology, aims at supporting young scholars in early stages of their academic careers by offering highest fellowships in history of logic, kindly supported by the John Templeton Foundation. Young scholars being less or exactly 40 years old at the time of the commencement of the Vienna Summer of Logic (July 9, 2014) will be awarded one fellowship award in the amount of EUR 100,000, in each of the following categories:

  • Logical Foundations of Mathematics,
  • Logical Foundations of Computer Science, and
  • Logical Foundations of Artificial Intelligence

The following three Boards of Jurors were in charge of choosing the winners:

  • Logical Foundations of Mathematics: Jan Krajíček, Angus Macintyre, and Dana Scott (Chair).
  • Logical Foundations of Computer Science: Franz Baader, Johann Makowsky, and Wolfgang Thomas (Chair).
  • Logical Foundations of Artificial Intelligence: Luigia Carlucci Aiello, Georg Gottlob (Chair), and Bernhard Nebel.

http://fellowship.logic.at/

17:30
FLoC Olympic Games Award Ceremony 1

ABSTRACT. The aim of the FLoC Olympic Games is to start a tradition in the spirit of the ancient Olympic Games, a Panhellenic sport festival held every four years in the sanctuary of Olympia in Greece, this time in the scientific community of computational logic. Every four years, as part of the Federated Logic Conference, the Games will gather together all the challenging disciplines from a variety of computational logic in the form of the solver competitions.

At the Award Ceremonies, the competition organizers will have the opportunity to present their competitions to the public and give away special prizes, the prestigious Kurt Gödel medals, to their successful competitors. This reinforces the main goal of the FLoC Olympic Games, that is, to facilitate the visibility of the competitions associated with the conferences and workshops of the Federated Logic Conference during the Vienna Summer of Logic.

This award ceremony will host the

  • 3rd Confluence Competition (CoCo 2014);
  • Configurable SAT Solver Challenge (CSSC 2014);
  • Ninth Max-SAT Evaluation (Max-SAT 2014);
  • QBF Gallery 2014; and
  • SAT Competition 2014 (SAT-COMP 2014).
18:15
FLoC Closing Week 1
SPEAKER: Helmut Veith