Recent paradigm shifts in distributed computing such as the advent of cloud computing pose new challenges to the analysis of distributed executions. One important new characteristic is that the management staff of computing platforms and the developers of applications are separated by corporate boundaries. The net result is that once applications go wrong, the most readily available debugging aids for developers are the visible output of the application and any log files collected during their execution. In this paper, we propose the concept of task graphs as a foundation to represent distributed executions, and present a low overhead algorithm to infer task graphs from event log files. Intuitively, a task represents an autonomous segment of computation inside a thread. Edges between tasks represent their interactions and preserve programmers’ notion of data and control flows. Our technique leverages existing logging support where available or otherwise augments it with aspect-based instrumentation to collect events of a set of predefined types. We show how task graphs can improve the precision of anomaly detection in a request-oriented analysis of field software and help programmers understand the running of the Hadoop Distributed File System (HDFS).

Traditional dynamic program slicing techniques are code-centric, meaning dependences are introduced between executed statement instances, which gives rise to various problems such as space requirement is decided by execution length; dependence graphs are highly redundant so that inspecting them is labor intensive. In this paper, we propose a data-centric dynamic slicing technique, in which dependences are introduced between memory locations. Doing so, the space complexity is bounded by memory footprint instead of execution length. Moreover, presenting dependences between memory locations is often more desirable for human inspection during debugging as redundant dependences are suppressed. Our evaluation shows that the proposed technique supersedes traditional dynamic slicing techniques in terms of effectiveness and efficiency.

Execution indexing uniquely identifies a point in an execution. Desirable execution indices reveal correlations between points in an execution and establish correspondence between points across multiple executions. Therefore, execution indexing is essential for a wide variety of dynamic program analyses, for example, it can be used to organize program profiles; it can precisely identify the point in a re-execution that corresponds to a given point in an original execution and thus facilitate debugging or dynamic instrumentation. In this paper, we formally define the concept of execution index and propose an indexing scheme based on execution structure and program state. We present a highly optimized online implementation of the technique. We also perform a client study, which targets producing a failure inducing schedule for a data race by verifying the two alternative happens-before orderings of a racing pair. Indexing is used to precisely locate corresponding points across multiple executions in the presence of non-determinism so that no heavyweight tracing/replay system is needed.

Capturing dynamic control dependence is critical for many dynamic program analysis such as dynamic slicing, dynamic information flow, and data lineage computation. Existing algorithms are mostly a simple runtime translation of the static definition, which fails to capture certain dynamic properties by its nature, leading to inefficiency. In this paper, we propose a novel online detection technique for dynamic control dependence. The technique is based upon a new definition, which is equivalent to the existing one in the intraprocedural case but it enables an efficient detection algorithm. The new algorithm naturally and efficiently handles interprocedural dynamic control dependence even in presence of irregular control flow. Our evaluation shows that the detection algorithm slows down program execution by a factor of 2.57, which is 2.54 times faster than the existing algorithm that was used in prior work.

We present a new concurrency control abstraction for real-time systems called preemptible atomic regions (PARs). PARs a transactional mechanism that improves upon lock-based mutual exclusion in several ways. First, and foremost, PARs provide strong correctness guarantees. Any sequence of operations declared atomic will not suffer interference from other threads, even in the presence of programmer errors. In spite of this, PARs can be preempted by high priority tasks; this is essential to the minimization of blocking times. We have implemented PARs in a uniprocessor real-time Java virtual machine and evaluated their utility on a number of programs. The results suggest that programs that use PARs, depending on their semantics, can run faster and experience less jitter than those that use locks