Logic programming languages such as Datalog have become popular as Domain Specific Languages (DSLs) for solving large-scale, real-world problems, in particular, static program analysis and network analysis. The logic specifications which model analysis problems, process millions of tuples of data and contain hundreds of highly recursive rules. As a result, they are notoriously difficult to debug. While the database community has proposed several data-provenance techniques that address the Declarative Debugging Challenge for Databases, in the cases of analysis problems, these state-of-the-art techniques do not scale. In this paper, we introduce a novel bottom-up Datalog evaluation strategy for debugging: our provenance evaluation strategy relies on a new provenance lattice that includes proof annotations, and a new fixed-point semantics for semi-naive evaluation. A debugging query mechanism allows arbitrary provenance queries, constructing partial proof trees of tuples with minimal height. We integrate our technique into Souffle, a Datalog engine that synthesizes C++ code, and achieve high performance by using specialized parallel data structures. Experiments are conducted with DOOP DaCapo, producing proof annotations for tens of millions of output tuples. We show that our method has a runtime overhead of 1.27x on average while being more flexible than existing state-of-the-art techniques.
Our method also fits into the established frameworks for provenance in Datalog @cite_23 and debugging for Datalog @cite_32 . The proof trees generated by our method are analogous to the computation graphs presented in @cite_32 , and are equally effective for debugging. They can also be seen as an extension of -provenance @cite_27 . However, our hybrid method for generating proof trees is novel, i.e., it permits multiple debugging queries in a single debugging cycle. Hence, our method is especially useful for debugging large Datalog specifications.
@cite_27 @cite_32 @cite_23
2031397756 2148193377 2102902005 2104791905
This paper examines techniques for finding falsifying trajectories of hybrid systems using an approach that we call trajectory splicing. Many formal verification techniques for hybrid systems, including flowpipe construction, can identify plausible abstract counterexamples for property violations. However, there is often a gap between the reported abstract counterexamples and the concrete system trajectories. Our approach starts with a candidate sequence of disconnected trajectory segments, each segment lying inside a discrete mode. However, such disconnected segments do not form concrete violations due to the gaps that exist between the ending state of one segment and the starting state of the subsequent segment. Therefore, trajectory splicing uses local optimization to minimize the gap between these segments, effectively splicing them together to form a concrete trajectory. We demonstrate the use of our approach for falsifying safety properties of hybrid systems using standard optimization techniques. As such, our approach is not restricted to linear systems. We compare our approach with other falsification approaches including uniform random sampling and a robustness guided falsification approach used in the tool S-Taliro. Our preliminary evaluation clearly shows the potential of our approach to search for candidate trajectory segments and use them to find concrete property violations. The natural proof technique for heap verification developed by [32] provides a platform for powerful sound reasoning for specifications written in a dialect of separation logic called Dryad. Natural proofs are proof tactics that enable automated reasoning exploiting recursion, mimicking common patterns found in human proofs. However, these proofs are known to work only for a simple toy language [32]. In this work, we develop a framework called VCDryad that extends the Vcc framework [9] to provide an automated deductive framework against separation logic specifications for C programs based on natural proofs. We develop several new techniques to build this framework, including (a) a novel tool architecture that allows encoding natural proofs at a higher level in order to use the existing Vcc framework (including its intricate memory model, the underlying type-checker, and the SMT-based verification infrastructure), and (b) a synthesis of ghost-code annotations that captures natural proof tactics, in essence forcing Vcc to find natural proofs using primarily decidable theories. We evaluate our tool extensively, on more than 150 programs, ranging from code manipulating standard data structures, well-known open source library routines (Glib, OpenBSD), Linux kernel routines, customized OS data structures, etc. We show that all these C programs can be fully automatically verified using natural proofs (given pre post conditions and loop invariants) without any user-provided proof tactics. VCDryad is perhaps the first deductive verification framework for heap-manipulating programs in a real language that can prove such a wide variety of programs automatically. Consider a Markov chain on an infinite tree T = (V,E) rooted at . In such a chain, once the initial root state ( ) is chosen, each vertex iteratively chooses its state from the one of its parent by an application of a Markov transition rule (and all such applications are independent). Let µj denote the resulting measure for ( ) = j. µj is defined on configurations = ( (x))x2V 2 A V , where A is some finite set. Let µ n denote the restriction of µ to the sigma-algebra generated by the variables (x) where x is at distance exactly n from . Letting n = maxi,j2A dTV (µ n ,µ n ), where dTV denotes total variation distance, we say that the reconstruction problem is solvable if liminfn!1 n > 0. Reconstruction solvability roughly means that the n’th level of the tree contains a non-vanishing amount of information on the root of the tree, as n ! 1. In this paper we study the problem of robust reconstruction. Let be a non degenerate distribution on A and > 0. Let be chosen according to µ n and 0 be obtained from by letting for each node independently (v) = 0 (v) with probability 1 and 0 (v) to be an independent sample from otherwise. We denote by µ n [, ] the resulting measure on 0 . The measure µ n [, ] is a perturbation of the measure µ n . Letting n(, ) = maxi,j2A dTV (µ n [, ],µ n [, ]), we say that the reconstruction problem is -robust-solvable if liminfn!1 n(, ) > 0 for all 0 1, where 2(M) is the second largest eigenvalue of M (in absolute value), then for all non-degenerate , the reconstruction problem is -robust-solvable. We prove a converse and show that the reconstruction problem is not -robust-solvable if B| 2(M)| 2 < 1. This proves a conjecture by the second author and Peres. We also consider other models of noise and general trees. Provenance has been studied extensively in both database and workflow management systems, so far with little convergence of definitions or models. Provenance in databases has generally been defined for relational or complex object data, by propagating fine-grained annotations or algebraic expressions from the input to the output. This kind of provenance has been found useful in other areas of computer science: annotation databases, probabilistic databases, schema and data integration, etc. In contrast, workflow provenance aims to capture a complete description of evaluation - or enactment - of a workflow, and this is crucial to verification in scientific computation. Workflows and their provenance are often presented using graphical notation, making them easy to visualize but complicating the formal semantics that relates their run-time behavior with their provenance records. We bridge this gap by extending a previously-developed dataflow language which supports both database-style querying and workflow-style batch processing steps to produce a workflow-style provenance graph that can be explicitly queried. We define and describe the model through examples, present queries that extract other forms of provenance, and give an executable definition of the graph semantics of dataflow expressions.