TaPP 2017 Workshop Program

How to use provenance to explain why a query returns a result or why a result is missing has been studied extensively. Recently, we have demonstrated how to uniformly answer these types of provenance questions for first-order queries with negation and have presented an implementation of this approach in our PUG (Provenance Unification through Graphs) system. However, for realistically-sized databases, the provenance of answers and missing answers can be very large, overwhelming the user with too much information and wasting computational resources. In this paper, we introduce an (approximate) summarization technique that generates compact representations of why and why-not provenance. Our technique uses patterns as a summarized representation of sets of elements from the provenance, i.e., successful or failed derivations. We rank these patterns based on their descriptiveness (we use precision and recall as quality measures for patterns) and return only the top-k summaries. We demonstrate how this summarization technique can be integrated with provenance capture to compute summaries on demand and how sampling techniques can be employed to speed up both the summarization and capture steps. Our preliminary experiments demonstrate that this summarization technique scales to large instances of a real-world dataset.

What-if queries predict how the results of an analysis would change based on hypothetical changes to a database. While a what-if query determines the effect of a hypothetical change on a query’s result, it is often unclear how such a change could have been achieved limiting the practical applicability of such queries. We propose an alternative model for what-if queries where the user proposes a hypothetical change to past update operations. Answering such a query amounts to determining the effect of a hypothetical change to past operations on the current database state (or a query’s result). We argue that such historical what-if queries are often easier to formulate for a user and lead to more actionable insights. In this paper, we take a first stab at answering historical what-if queries. We use reenactment, a declarative replay technique for transactional histories, to evaluate the effect of a modified history on the current database state. Furthermore, we statically analyze the provenance dependencies of a history to limit reenactment to transactions and data affected by a hypothetical change.

As the Internet of Things (IoT) continues to proliferate, diagnosing incorrect behavior within increasingly-automated homes becomes considerably more difficult. Devices and apps may be chained together in long sequences of trigger-action rules to the point that from an observable symptom (e.g., an unlocked door) it may be impossible to identify the distantly removed root cause (e.g., a malicious app). We present a platform-centric approach to centralized auditing in the Internet of Things. Our system performs efficient automated instrumentation of IoT apps in order to generate data provenance that provides a holistic explanation of system activities, including malicious behaviors. Here, we prototype our system for the Samsung SmartThings platform, and consider how it can be leveraged to meet the needs of a variety of stakeholders in the IoT ecosystem.

Provenance collection techniques have been carefully studied in the literature, and there are now several systems to automatically capture provenance data. However, the analysis of provenance data is often left “as an exercise for the reader”. The provenance community needs tools that allow users to quickly sort through large volumes of provenance data and identify records that require further investigation. By detecting anomalies in provenance data that deviate from established patterns, we hope to actively thwart security threats. In this paper, we discuss issues with current graph analysis techniques as applied to data provenance, particularly Frequent Subgraph Mining (FSM). Then we introduce Directed Acyclic Graph regular grammars (DAGr) as a model for provenance data and show how they can detect anomalies. These DAGr provide an expressive characterization of DAGs, and by using regular grammars as a formalism, we can apply results from formal language theory to learn the difference between “good” and “bad” provenance. We propose a restricted subclass of DAGr called deterministic Directed Acyclic Graph automata (dDAGa) that guarantees parsing in linear time. Finally, we propose a learning algorithm for dDAGa, inspired by Minimum Description Length for Grammar Induction.

Access control protects security-sensitive operations from access by unauthorized subjects. Unfortunately, access control mechanisms are implemented manually in practice, which can lead to exploitable errors. Prior work aims to find such errors through static analysis, but the correctness of access control enforcement depends on runtime factors, such as the access control policies enforced and adversary control of the program inputs. As a result, we propose to apply provenance tracking to find flaws in access control enforcement. To do so, we track the inputs used in access control decisions to enable detection of flaws. We have developed ACCESSPROV, a Java bytecode analysis tool capable of retrofitting legacy Java applications with provenance hooks. We utilize ACCESSPROV to add provenance hooks at all locations that either may require access control enforcement or may impact access control policy decisions. We evaluate ACCESSPROV on OpenMRS, an open-source medical record system, detecting access control errors while incurring only 2.1% overhead when running the OpenMRS test suite on the instrumented OpenMRS program.

Visual data exploration allows users to analyze datasets based on visualizations of interesting data characteristics, to possibly discover interesting information about the data that users are a priori unaware of. In this context, both recommendations of queries selecting the data to be visualized and recommendations of visualizations that highlight interesting data characteristics support users in visual data exploration. So far, these two types of recommendations have been mostly considered in isolation of one another.

We present a recommendation approach for visual data exploration that unifies query recommendation and visualization recommendation. The recommendations rely on two types of provenance, i.e., data provenance (aka lineage) and evolution provenance that tracks users’ interactions with a data exploration system. This paper presents the provenance data model as well as the overall system architecture. We then provide details on our provenance-based recommendation algorithms. A preliminary experimental evaluation showcases the applicability of our solution in practice.

Computational notebooks have seen widespread adoption among scientists in many fields, and allow users to view interactive graphical results inline, to embed text and code together, to organize code into cells, and to selectively edit and re-execute cells. Because they allow quick and recordable analyses, they play an important role in documenting experiments. However, the reproducibility of notebooks can vary significantly due to the ordering of cells or changes in global state that affect the re-execution of those cells. In addition, in many popular notebook environments, cells are tagged with transient identifiers that change when a cell is re-executed so it is impossible to robustly reference other cells. We introduce dataflow notebooks as a method to allow users to explicitly encode dependencies between cells by adding a unique, persistent identifier to each cell and expanding incode references to results in other cells. In these notebooks, we can both pose and answer provenance queries about dependencies etween cells. This permits new notebook operations like downstream updates which, given a change to one cell, allow users to update all cells that may be impacted by the change while leaving all other cells alone. At the same time, dataflow notebooks increase reproducibility and enable greater reuse by making dependencies clear.