The rapid growth in the size and scope of datasets in science and technology has created a need for novel foundational perspectives on data analysis that blendthe inferential and computational sciences. That classical perspectives from these fields are not adequate to address emerging problems in Data Science is apparent from their sharply divergent nature at an elementary level—in computer science, the growth of the number of data points is a source of “complexity” that must be tamed via algorithms or hardware, whereas in statistics, the growth of the number of data points is a source of “simplicity” in that inferences are generally stronger and asymptotic results can be invoked. On a formal level, the gap is made evident by the lack of a role for computational concepts such as “runtime” in core statistical theory and the lack of a role for statistical concepts such as “risk” in core computational theory. I present several research vignettes aimed at bridging computation and statistics, including the problem of inference under privacy and communication constraints, and including a surprising cameo role for symplectic geometry.
Machine learning (ML) models, e.g., deep neural networks
(DNNs), are vulnerable to adversarial examples: malicious inputs
modified to yield erroneous model outputs, while appearing unmodified
to human observers. Potential attacks include having malicious content
like malware identified as legitimate or controlling vehicle
behavior. Yet, most existing adversarial example attacks require
knowledge of either the model internals or its training data. We will
describe a black-box attack on ML models. These algorithms yield
adversarial examples misclassified by Amazon and Google at rates of
96.19% and 88.94%. We also find that this black-box attack strategy is
capable of evading defense strategies previously found to make
adversarial example crafting harder.
We consider distributed timed systems that implement leader election
protocols which are at the heart of clock synchronization protocols. We
develop abstraction techniques for parameterized model checking of such
protocols under arbitrary network topologies, where nodes have independently
evolving clocks. We apply our technique for model checking the root election
part of the ﬂooding time synchronisation protocol (FTSP), and obtain
improved results compared to previous work. We model check the protocol for
all topologies in which the distance to the node to be elected leader is
bounded by a given parameter.
Tool prototyping is an essential step in developing novel software verification algorithms and techniques. However, implementing a verifier prototype that can handle real-world programs is a huge endeavor, which hinders researchers by forcing them to spend more time engineering tools, and less time innovating. In this talk, I will present the SMACK software verification toolchain. The toolchain provides a modular and extensible software verification ecosystem that decouples the front-end source language details from back-end verification algorithms. It achieves that by translating from the LLVM compiler intermediate representation into the Boogie intermediate verification language. SMACK benefits the software verification community in several ways: (i) it can be used as an off-the-shelf software verifier in an applied software verification project, (ii) it enables researchers to rapidly develop and release new verification algorithms, (iii) it allows for adding support for new languages in its front-end. We have used SMACK to verify numerous C/C++ programs, including industry examples, showing it is mature and competitive. Likewise, SMACK is already being used in several existing verification research prototypes.
It is known that one can extract Craig interpolants from so-called local derivations. An interpolant extracted from such a derivation is a boolean combination of formulas occurring in the derivation. However, standard complete proof systems, such as superposition, for theories having the interpolation property are not necessarily complete for local proofs.
In this paper we investigate interpolant extraction from non-local proofs in the superposition calculus and prove a number of general results about interpolant extraction and complexity of extracted interpolants. In particular, we prove that the number of quantifier alternations in first-order interpolants of formulas without quantifier alternations is unbounded. This result has far-reaching consequences for using local proofs as a foundation for interpolating proof systems – any such proof system should deal with formulas of arbitrary quantifier complexity.
To search for alternatives for interpolating proof systems, we consider several variations on interpolation and local proofs. Namely, we give an algorithm for building interpolants from resolution refutations in logic without equality and discuss additional constraints when this approach can be also used for logic with equality. We finally propose a new direction related to interpolation via local proofs in first-order theories.
Analyzing and reasoning about safety properties of software systems
becomes an especially challenging task for programs with complex flow
and, in particular, with loops or recursion. For such programs one needs
additional information, for example in the form of loop invariants,
expressing properties to hold at intermediate program points. We study
program loops with non-trivial arithmetic, implementing addition and
multiplication among numeric program variables. In this talk, we present
a new approach for automatically generating all polynomial invariants of
a class of such programs, based on techniques from computer algebra,
which will be explained thoroughly and intuitively.
In our project we are working on a framework that provides holistic security guarantees for web-based systems in which information flows heavily but not all flows should be allowed. As a case study we developed CoCon, a conference management system with verified document confidentiality. In my talk, I will start with a demo of CoCon, show which properties of the system we verified in the interactive theorem prover Isabelle and explain how we technically capture the intuitive idea that an attacker cannot learn any secrets of the system. A discussion of limitations of our approach will follow together with a summary of our experience with deployment of CoCon for real-life conferences. At the end, I will shortly mention future work.
We introduce a graphical syntax for signal flow diagrams based on the language of symmetric monoidal categories. Using universal categorical constructions, we provide a stream semantics and a sound and complete axiomatisation. A certain class of diagrams captures the orthodox notion of signal flow graph used in control theory; we show that any diagram of our syntax can be realised, via rewriting in the equational theory, as a signal flow graph.
We consider data automata in the form of finite automata equipped with variables (counters or registers) ranging over infinite data domains. A trace of such a data automaton is an alternating sequence of alphabet symbols and values taken by the counters during an execution of the automaton. We address the problem of checking the inclusion between the sets of traces (data languages) recognized by such automata. Since the problem is undecidable in general, we give a semi-algorithm based on abstraction refinement, which is proved to be sound and complete modulo termination. Due to the undecidability of the trace inclusion problem, our procedure is not guaranteed to terminate. We have implemented our technique in a prototype tool and show promising results on several non-trivial examples.