Grigory Fedyukovich

Faezeh Labbaf, Tomáš Kolárik, Martin Blicha et al.

We present a novel logic-based concept called Space Explanations for classifying neural networks that gives provable guarantees of the behavior of the network in continuous areas of the input feature space. To automatically generate space explanations, we leverage a range of flexible Craig interpolation algorithms and unsatisfiable core generation. Based on real-life case studies, ranging from small to medium to large size, we demonstrate that the generated explanations are more meaningful than those computed by state-of-the-art.

Andreas Katis, Grigory Fedyukovich, Jeffrey Chen et al.

Diversity in the exhibited behavior of a given system is a desirable characteristic in a variety of application contexts. Synthesis of conformant implementations often proceeds by discovering witnessing Skolem functions, which are traditionally deterministic. In this paper, we present a novel Skolem extraction algorithm to enable synthesis of witnesses with random behavior and demonstrate its applicability in the context of reactive systems. The synthesized solutions are guaranteed by design to meet the given specification,while exhibiting a high degree of diversity in their responses to external stimuli. Case studies demonstrate how our proposed frame-work unveils a novel application of synthesis in model-based fuzz testing to generate fuzzers of competitive performance to general-purpose alternatives, as well as the practical utility of synthesized controllers in robot motion planning problems.

Andreas Katis, Grigory Fedyukovich, Huajun Guo et al.

Automated synthesis of reactive systems from specifications has been a topic of research for decades. Recently, a variety of approaches have been proposed to extend synthesis of reactive systems from proposi- tional specifications towards specifications over rich theories. We propose a novel, completely automated approach to program synthesis which reduces the problem to deciding the validity of a set of forall-exists formulas. In spirit of IC3 / PDR, our problem space is recursively refined by blocking out regions of unsafe states, aiming to discover a fixpoint that describes safe reactions. If such a fixpoint is found, we construct a witness that is directly translated into an implementation. We implemented the algorithm on top of the JKind model checker, and exercised it against contracts written using the Lustre specification language. Experimental results show how the new algorithm outperforms JKinds already existing synthesis procedure based on k-induction and addresses soundness issues in the k-inductive approach with respect to unrealizable results.

Dmitry Mordvinov, Grigory Fedyukovich

The goal of unbounded program verification is to discover an inductive invariant that safely over-approximates all possible program behaviors. Functional languages featuring higher order and recursive functions become more popular due to the domain-specific needs of big data analytics, web, and security. We present Rosette/Unbound, the first program verifier for Racket exploiting the automated constrained Horn solver on its backend. One of the key features of Rosette/Unbound is the ability to synchronize recursive computations over the same inputs allowing to verify programs that iterate over unbounded data streams multiple times. Rosette/Unbound is successfully evaluated on a set of non-trivial recursive and higher order functional programs.

Andreas Katis, Grigory Fedyukovich, Andrew Gacek et al.

The realizability problem in requirements engineering is to determine the existence of an implementation that meets the given formal requirements. A step forward after realizability is proven, is to construct such an implementation automatically, and thus solve the problem of program synthesis. In this paper, we propose a novel approach to pro- gram synthesis guided by k-inductive proofs of realizability of assume- guarantee contracts constructed from safety properties. The proof of re- alizability is performed over a set of forall-exists formulas, and synthesis is per- formed by extracting Skolem functions witnessing the existential quan- tification. These Skolem functions can then be combined into an imple- mentation. Our approach is implemented in the JSyn tool which con- structs Skolem functions from a contract written in a variant of the Lus- tre programming language and then compiles the Skolem functions into a C language implementation. For a variety of benchmark models that already contained hand-written implementations, we are able to identify the usability and effectiveness of the synthesized counterparts, assuming a component-based verification framework.