previous day
next day
all days

View: session overviewtalk overviewside by side with other conferences

10:45-12:45 Session 138F: Protocol Verification
Location: FH, Hörsaal 6
Decidability for Lightweight Diffie-Hellman Protocols
SPEAKER: unknown

ABSTRACT. Many protocols use the Diffie-Hellman method for key agreement, in combination with certified long-term values or digital signatures for authentication. These protocols aim at security goals such as key secrecy, forward secrecy, resistance to key compromise attacks, and various flavors of authentication. However, analysis of these protocols has been challenging, both in the computational model and in the symbolic model. An obstacle in the symbolic model is the undecidability of unification in many theories such as rings.

In this paper, we develop an algebraic version of the symbolic approach, in which we work directly within finite fields. These are natural structures for the protocols. The adversary, in giving a counterexample to a protocol goal in a finite field, may rely on any identity in that field. He defeats the protocol if there are counterexamples in infinitely many finite fields.

We prove that, even for this strong adversary, security goals for a wide class of protocols are decidable.

Modeling Diffie-Hellman Derivability for Automated Analysis
SPEAKER: unknown

ABSTRACT. Automated analysis of protocols involving Diffie-Hellman key exchange is challenging, in part because of the undecidability of the unification problem in relevant theories. In this paper, we justify the use of a more restricted theory that includes multiplication of exponents but not addition, providing unitary and efficient unification.

To justify this theory, we link it to a computational model of non-uniform circuit complexity through several incremental steps. First, we give a model closely analogous to the computational model, in which derivability is modeled by closure under simple algebraic transformations. This model retains many of the complex features of the computational model, including defining success based on asymptotic probability for a non-uniform family of strategies. We describe an intermediate model based on formal polynomial manipulations, in which success is exact and there is no longer a parametrized notion of the strategy. Despite the many differences in form, we are able to prove an equivalence between the asymptotic and intermediate models by showing that a sufficiently successful asymptotic strategy implies the existence of a perfect strategy. Finally, we describe a symbolic model in which addition of exponents is not modeled, and prove that (for expressible problems), the symbolic model is equivalent to the intermediate model.

Actor Key Compromise: Consequences and Countermeasures
SPEAKER: Marko Horvat

ABSTRACT. Despite Alice’s best efforts, her long-term secret keys may be revealed to an adversary. Possible reasons include weakly generated keys, compromised key storage, subpoena, and coercion. However, Alice may still be able afterwards to communicate securely with other parties. Whether this is possible depends on the protocol used. We call the associated property resilience against Actor Key Compromise (AKC). We formalise this property in a symbolic model and identify conditions under which it can and cannot be achieved. In case studies that include TLS and SSH, we find that many protocols are not resilient against AKC. We implement a concrete AKC attack on the mutually authenticated TLS protocol.

A Sound Abstraction of the Parsing Problem

ABSTRACT. In formal verification, cryptographic messages are often represented by algebraic terms. This abstracts not only from the intricate details of the real cryptography, but also from the details of the non-cryptographic aspects: the actual formatting and structuring of messages.

We introduce a new algebraic model to include these details and define a small, simple language to precisely describe message formats. We support fixed-length fields, variable-length fields with offsets, tags, and encodings into smaller alphabets like Base64, thereby covering both classical formats as in TLS and modern XML-based formats.

We define two reasonable properties for formats. First, they should be un-ambiguous: for a given format, any string can be parsed in at most one way. Second, they should be pairwise disjoint: a string can be parsed as at most one of the formats. We show how to easily establish these properties for many practical formats.

An abstract model is obtained by replacing the formats with free function symbols. This abstract model is compatible with all existing verification tools. We prove that the abstraction is sound for un-ambiguous, disjoint formats: there is an attack in the concrete message model if (and actually only if) there is one in the abstract message model.

13:00-14:30Lunch Break
14:30-16:00 Session 140F: Information Flow 2
Location: FH, Hörsaal 6
Compositional Information-flow Security for Interactive Systems
SPEAKER: unknown

ABSTRACT. To achieve end-to-end security in a system built from parts, it is important to ensure that the composition of secure components is itself secure. This work investigates the compositionality of two popular conditions of possibilistic noninterference. The first condition, progress-insensitive noninterference (PINI), is the security property enforced by practical tools like JSFlow, Paragon, LIO, Jif, FlowCaml, and SPARK Examiner. We show that this condition is not preserved under fair parallel composition: composing a PINI system fairly with another PINI system can yield an insecure system. We explore constraints that allow recovering compositionality for PINI. Further, we develop a theory of compositional reasoning and enforcement for progress-sensitive noninterference (PSNI). Our work is performed within a general framework for nondeterministic interactive systems.

Stateful Declassification Policies for Event-Driven Programs
SPEAKER: unknown

ABSTRACT. We propose a novel mechanism for enforcing information flow policies with support for declassification on event-driven programs. Declassification policies consist of two functions. First, a projection function specifies for each confidential event what information in the event can be declassified directly. This generalizes the traditional security labelling of inputs. Second, a stateful release function specifies the aggregate information about all confidential events seen so far that can be declassified. We provide evidence that such declassification policies are useful in the context of JavaScript web applications. An enforcement mechanism for our policies is presented and its soundness and precision is proven. Finally, we give evidence of practicality by implementing and evaluating the mechanism in a browser.

Additive and multiplicative notions of leakage, and their capacities

ABSTRACT. Protecting sensitive information from improper disclosure is a fundamental security goal. It is complicated, and difficult to achieve, often because of unavoidable or even unpredictable operating conditions that lead to breaches in planned security defences. An attractive approach is to frame the goal as a quantitative problem, and then to design methods that allow system vulnerabilities to be measured in terms of the amount of information that they leak. A consequence of this view is that the precise operating conditions and any assumptions about prior knowledge can play a crucial role in assessing the severity of any measured vunerability.

We develop this theme by concentrating on robustness of vulnerability measurements: we wish to allow general leakage bounds to be placed on a program, whatever its operating conditions and whatever the prior knowledge might be. In particular we propose a theory of channel capacity, generalizing Shannon capacity from information theory, that can apply both to additive- and to multiplicative forms of a recently-proposed measure known as g-leakage. Further, we explore the computational aspects of calculating these capacities: we show that one of these scenarios can be solved efficiently by expressing it as a Kantorovich distance, and that another is NP-complete. We also show capacity bounds for a scenario related to Dalenius's Desideratum.

16:00-16:30Coffee Break
16:30-17:30 Session 143C: Invited Talk
Location: FH, Hörsaal 6
New Directions in Computed-Aided Cryptography
SPEAKER: Gilles Barthe
08:45-10:15 Session 144A: VSL Keynote Talk
Location: EI, EI 7 + EI 9, EI 10 + FH, Hörsaal 1
VSL Keynote Talk: Ontology-Based Monitoring of Dynamic Systems
SPEAKER: Franz Baader

ABSTRACT. Our understanding of the notion "dynamic system" is a rather broad one: such a system has states, which can change over time. Ontologies are used to describe the states of the system, possibly in an incomplete way. Monitoring is then concerned with deciding whether some run of the system or all of its runs satisfy a certain property, which can be expressed by a formula of an appropriate temporal logic. We consider different instances of this broad framework, which can roughly be classified into two cases. In one instance, the system is assumed to be a black box, whose inner working is not known, but whose states can be (partially) observed during a run of the system. In the second instance, one has (partial) knowledge about the inner working of the system, which provides information on which runs of the system are possible.

In this talk, we will review some of our recent research that investigates different instances of this general framework of ontology-based monitoring of dynamic systems. We will also sketch possible extensions towards probabilistic reasoning and the integration of mathematical modelling of dynamical systems.

10:15-10:45Coffee Break
17:30-18:30 Session 146: 5' Talks
Location: FH, Hörsaal 6
19:00-20:00 Session 149A: VSL Public Lecture 2
Location: MB, Kuppelsaal
VSL Public Lecture: Vienna Circle(s) - Between Philosophy and Science in Cultural Context

ABSTRACT. The Vienna Circle of Logical Empiricism, which was part of the intellectual movement of Central European philosophy of science, is certainly one of the most important currents in the emergence of modern philosophy of science. Apart from this uncontested historical fact there remains the question of the direct and indirect influence, reception and topicality of this scientific community in contemporary philosophy of science in general as well as in the philosophy of the individual sciences, including the formal and social sciences. 

First, I will characterize the road from the Schlick-Circle to contemporary philosophy of science. Second, I will refer to "the present situation in the philosophy of science" by identifying relevant impacts, findings, and unfinished projects since the classical Vienna Circle. Third, I will address some specific European features of this globalized philosophical tradition up to the present, and outline future perspectives after the linguistic, historical and pragmatic turns – looking back to the "received view", or standard view of the Vienna Circle.

16:30-19:00 Session 151A: VSL Joint Award Ceremony 2
Location: MB, Kuppelsaal
FLoC Olympic Games Award Ceremony 2

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

  • Fifth Answer Set Programming Competition (ASPCOMP 2014);
  • The 7th IJCAR ATP System Competition (CASC-J7);
  • Hardware Model Checking Competition (HWMCC 2014);
  • OWL Reasoner Evaluation (ORE 2014);
  • Satisfiability Modulo Theories solver competition (SMT-COMP 2014);
  • Competition on Software Verification (SV-COMP 2014);
  • Syntax-Guided Synthesis Competition (SyGuS-COMP 2014);
  • Synthesis Competition (SYNTCOMP 2014); and
  • Termination Competition (termCOMP 2014).
Lifetime Achievement Award

ABSTRACT. Werner "Jimmy" DePauli-Schimanovich is being honored for his contributions to Gödel research, for his efforts towards re-establishing Vienna as a center of logic in the second half of the past century, and for extending the outreach of formal logic and logical thinking to other disciplines. The books about Gödel he authored, co-authored, or edited contain precious contributions of historical, philosophical, and mathematical value. His film on Gödel, and related articles and TV testimonials, attracted the general public to Gödel and his work. Moreover, DePauli-Schimanovich has unceasingly and successfully fought to re-establish logic in Vienna. He has inspired and encouraged a large number of students and young researchers, has organised meetings and social gatherings, and has created an intellectual home for scholars of logic. His activities significantly contributed to filling the intellectual vacuum in logic research that had developed in Austria in the years 1938–1945 and well into the post-war period. He was a main initiator and co-founder of the International Kurt Gödel Society. Jimmy’s research in logic involved criticism of current axiomatisations of set theory and development of new systems of naïve set theory. In informatics, DePauli-Schimanovich was co-founder and co-organiser of EuroCAST, a conference series on computer-assisted systems theory meeting alternatively in Vienna and Las Palmas, Gran Canaria. Finally, Jimmy has furthered implementation of logical ideas in disparate fields such as mechanical engineering, automated game playing, urban planning, and by inventing a number of logical games.

Lifetime Achievement Award
SPEAKER: Mingyi Zhang

ABSTRACT. Zhang Mingyi is a pioneer in Artificial Intelligence and Knowledge Representation in China. He has built up a school of non-monotonic logic in Guiyang and has fostered the exchange between Chinese and Western scientists. He has contributed a large number of results on various forms of non-monotonic reasoning, including default logic, answer set programming, and belief revision. In particular, as early as 1992, he has provided important characterizations of various forms of default logic that paved the way for clarifying their computational properties and for developing algorithms for default reasoning.  Jointly with collaborators, he proposed a characterization of answer sets based on sets of generating rules, and introduced the concept of first-order loop formulas to relate answer set programming to classical logic. Other important results relate to theory revision (for example, the proof of the existence and uniqueness of finest splitting of Horn formulae) and to normal forms for Gödel logics. Many of Zhang Mingyi's former students have become internationally respected researchers.

EMCL Distinguished Alumni Award

ABSTRACT. The Free University of Bozen-Bolzano, the Technische Universität Dresden, the Universidade Nova de Lisboa, the Universidad Politécnica de Madrid (until 2010), the Technische Universität Wien, and Australia's Information Communications Technology Research Centre of Excellence (since 2007) are jointly running the European Master's Program in Computational Logic (EMCL) since 2004. The program is supported by the European Union within Erasmus Mundus and Eramsus+. So far, more than 100 students from 39 different countries have successfully completed the distributed master's program with a double or joint degree.

For the first time, the partner institutions are announcing the EMCL Distinguished Alumni Award for outstanding contributions of EMCL graduates to the field of Computational Logic.


FLoC Closing Week 2
SPEAKER: Helmut Veith