Executing program paths outside the ones tested means that the program is executing scenarios not tested before deployment. No existing technique can produce a program that precisely contains an arbitrary set of tested program paths in each procedure of a tested program. This paper presents the first work, a novel technique called OPE, to address this problem. OPE first builds a transformed procedure that contains the target set of tested paths for every procedure in a tested program. It extends the transformed procedure with additional branches and basic blocks of code to include all remaining paths of the given procedure. The resultant transformed program is functionally equivalent to the tested program. OPE achieves an inherent strict separation of the tested paths from the rest ready for deployment or follow-up program testing and analysis tasks. The experiment confirms that OPE generates programs with clean path separations and outperforms the previous state-of-the-art path encoding technique when applied to path profiling.

A concrete service consists of a number of program components, each of which is integrated to the service at either design time or runtime. In testing a concrete service, testers should validate the correctness of each of its components under diverse service consumption scenarios. Analyzing the program executions of these components under different configurations allows developers to compare and pinpoint issues therein. There is surprisingly little work in bridging this gap. In this paper, to the best of our knowledge, we propose the first work in designing dynamic analysis-as-a-service using a multi-virtual machine (multi-VM) approach to dynamic data race detection. Almost all existing work on dynamic data race detection focuses on improving detection precision, efficiency, or coverage of thread interleaving scenarios on the same but single compiled concurrent program component. Our model continually selects VM instances, each hosting a different compiled version of the same program component and running a state-of-the-art detector to detect data races. As such, our model innovatively takes existing race detectors as building blocks and operates at a higher level of abstraction. We have evaluated our proposal through an experiment. The experiment reveals that the multi-VM approach is feasible in monitoring multiple compiled versions and can detect different races both in amount and in detection probability. Under a limited execution budget constraint, the multi-VM approach is also significantly more effective in detecting races than approaches that use single compiled versions only. Some races hidden deeply in one compiled version have been found to be significantly more detectable in some other compiled versions of the same service component.

State-of-the-art hybrid data race detectors combine the happens-before relation and the locking discipline to alleviate the imprecision problem incurred by lockset-based detector and the thread interleaving problem incurred by happens-before detectors. However, they incur high runtime overheads. In this paper, we present HistLock, a novel and sound hybrid dynamic race detector, which attains high precision, low slowdown and memory overheads, and thread insensitivity. It formulates a novel context-based strategy to phrase out non-redundant memory access events and check races to conserve both time and memory computation. It ensures each race warning to be the one violating the locking discipline in the original event history. Our experiment compared HistLock to FastTrack, AccuLock, and MultiLock-HB, which were a precise happens-before race detector, an imprecise hybrid race detector, and a precise hybrid race detector, respectively, on 13 benchmark subjects. HistLock was found to be of higher precision, 156% faster and 33% more memory-efficient than MultiLock-HB. It detected 59 more race warnings than AccuLock, attaining higher effectiveness, but ran slower by 43%. In most cases, in a single run, HistLock reported all the races detected by FastTrack in 100 runs.

Complete dynamic control flow is a fundamental kind of execution profile about program executions with a wide range of applications. Tracing the dynamic control flow of program executions for a brief period easily generates a trace consisting of billions of control flow events. The number of events in such a trace is large, making both path tracing and path querying to incur significant slowdowns. A major class of path tracing techniques is to design novel trace representations that can be generated efficiently, and encode the inputted sequences of such events so that the inputted sequences are still derivable from the encoded and smaller representations. The control flow semantics in such representations have, however, become obscure, which makes implementing path queries on such a representation inefficient and the design of such queries complicated. We propose a novel two-phase path tracing framework— Hierarchical Program Path (HPP)—to model the complete dynamic control flow of an arbitrary number of executions of a program. In Phase 1, HPP monitors each execution, and efficiently generates a stream of events, namely HPPTree, representing a novel tree-based representation of control flow for each thread of control in the execution. In Phase 2, given a set of such event streams, HPP identifies all the equivalent instances of the same exercised interprocedural path in all the corresponding HPPTree instances, and represents each such equivalent set of paths with a single subgraph, resulting in our compositional graph-based trace representation, namely, HPPDAG. Thus, an HPPDAG instance has the potential to be significantly smaller in size than the corresponding HPPTree instances, and still completely preserves the control flow semantics of the traced executions. Control flow queries over all the traced executions can also be directly performed on the single HPPDAG instance instead of separately processing the trace representation of each execution followed by aggregating their results. We validate HPP using the SPLASH2 and SPECint 2006 benchmarks. Compared to the existing technique, named BLPT (Ball-Larus-based Path Tracing), HPP generates significantly smaller trace representations and incurs fewer slowdowns to the native executions in online tracing of Phase 1. The HPPDAG instances generated in Phase 2 are significantly smaller than their corresponding BLPT and HPPTree traces. We show that HPPDAG supports efficient backtrace querying, which is a representative path query based on complete control flow trace. Finally, we illustrate the ease of use of HPPDAG by building a novel and highly efficient path profiling technique to demonstrate the applicability of HPPDAG.

Dynamic concurrency bug detectors predict and then examine suspicious instances of atomicity violations from executions of multithreaded programs. Only few predicted instances are real bugs. Prioritizing such instances can make the examinations cost-effective, but is there any design factor exhibiting significant influence? This work presents the first controlled experiment that studies two design factors, abstraction level and subspace, in partitioning such instances through 35 resultant partition-based techniques on 10 benchmarks with known vulnerability-related bugs. The empirical analysis reveals significant findings. First, partition-based prioritization can significantly improve the fault detection rate. Second, coarse-grained techniques are more effective than fine-grained ones, and using some one-dimensional subspaces is more effective than using other dimensional subspaces. Third, eight previously unknown techniques can be more effective than the technique modeled after a state-of-the-art dynamic detector.

A web-based service consists of layers of programs (components) in the technology stack. Analyzing program executions of these components separately allows service vendors to acquire insights into specific program behaviors or problems in these components, thereby pinpointing areas of improvement in their offering services. Many existing approaches for testing as a service take an orchestration approach that splits components under test and the analysis services into a set of distributed modules communicating through message-based approaches. In this paper, we present the first work in providing dynamic analysis as a service using a virtual machine (VM)-based approach on dynamic data race detection. Such a detection needs to track a huge number of events performed by each thread of a program execution of a service component, making such an analysis unsuitable to use message passing to transit huge numbers of events individually. In our model, we instruct VMs to perform holistic dynamic race detections on service components and only transfer the detection results to our service selection component. With such result data as the guidance, the service selection component accordingly selects VM instances to fulfill subsequent analysis requests. The experimental results show that our model is feasible.

Many two-phase based dynamic concurrency bug detectors predict suspicious instances of atomicity violation from one execution trace, and examine each such instance by scheduling a confirmation run. If the amount of suspicious instances predicted is large, confirming all these instances becomes a burden. In this paper, we present the first controlled experiment that evaluates the efficiency, effectiveness, and cost-effectiveness of reduction on suspicious instances in the detection of atomicity violations. A novel form of reduction technique named ASR is proposed. Our empirical analysis reveals many interesting findings: First, the reduced sets of instances produced by ASR significantly improve the efficiency of atomicity violation detection without significantly compromising the effectiveness. Second, ASR is significantly more cost-effective than random reduction and untreated reduction by 8.5 folds and 60.7 folds, respectively, in terms of mean normalized bug detection ratio. Third, six ASR techniques can be significantly more cost-effective than the technique modeled after a state-of-the-art detector.