Statistical Program Slicing: a Hybrid Slicing Technique for Analyzing Deployed Software

Despite significant improvements over the past decades, dynamic program slicing is still unsuited for analyzing production failures (ernst19, ; devecsery18, ). In particular, developers face two main challenges in the context of today’s modern software.

The first is related to the increasing difficulty of recovering faulty inputs in order to accurately reproduce production bugs offline. Recent studies (zhang17, ; cui18, ; kasikci17, ) show that for an increasing number of user-site bugs, failure-inducing inputs are difficult to record either due to the high cost of capturing context and environment information (zhang17, ; cui18, ), or because of privacy concerns (kasikci17, ).

The second is associated with the high cost of the underlying control and data flow instrumentation for computing full dynamic slices which is unsuited for production use (devecsery18, ; kasikci17, ). When failures cannot be reproduced offline because of missing or incomplete faulty inputs, developers default on runtime monitoring. This, in turn, creates a tension between deploying low-cost instrumentation and recording enough program behavior to reconstruct informative failure paths (orso15, ; parnin11, ; ernst19, ).

We believe it is worthwhile to revisit dynamic slicing at its core and design algorithms that yield useful program slices at low (production-grade) cost, without burdening developers to obtain failure-inducing inputs.

In this paper, we propose statistical program slicing, a hybrid dynamic-static program slicing technique that explores the trade-offs between runtime overhead and slice accuracy. The key insight of our technique is that we can reconstruct dynamic slices incrementally from observed program behavior through a combination of cooperative dynamic analysis and static program analysis. Our approach is lightweight, with minimal effect on program execution; transparent, tracing executions without changes to the target binary; and, crucially, requires no knowledge of the faulty input.

We implement statistical program slicing in a prototype called Wok (section 3). Wok relies on Intel Processor Trace (intel17, )—an efficient branch recording extension available on modern hardware—to collect precise control flow from faulty runs. Since Intel PT lacks memory tracing capabilities, Wok further performs data flow analysis by using pointer tagging to strategically sample and track a subset of heap-allocated objects across multiple regular runs. Finally, Wok relies on offline static alias analysis to complement dynamic data flow collection.

Conceptually, Wok reconstructs an unsound approximation of the traditional program dependency graph (Horwitz1990, ) in an incremental fashion. For brevity, we call this new program abstraction an observed dependency graph.

Although distributing data flow monitoring reduces the overhead to under $5\%$ (see section 5), aggregating data dependencies over multiple runs poses an additional challenge: We cannot reliably compare memory accesses between two distinct runs due to program relocation techniques (e.g., address space layout randomization). To mitigate this issue, we discard memory address information and keep data dependencies as pairs of static program statements instead (similar to (agrawal90, )). We later partially recover control flow sensitivity by relying on the precise control flow from the faulty run collected by Intel PT and pruning data dependencies unrelated to the failure. As a consequence, our slices represent a projection of the dynamic slice on static code. Thus, conceptually, statistical slices dwell in the space between static and dynamic slices.

We use Wok to reconstruct dynamic slices for $\nrBugs$ bugs from $\nrApps$ widely used open source applications. We compare Wok’s output against Giri, a state-of-the-art program slicing tool (swarup13, ). Specifically, we (1) measure how many program statements of the original dynamic slice can our tool recover, (2) the size of our resulting statistical slices, as well as (3) the accuracy of the recovered failure path (i.e., the set of instructions between the fault and the root cause). Our evaluation (section 5) shows that Wok recovers $\woktAvgRRsliceT$ of the unique program statements of the dynamic slice with only $5\%$ runtime overhead. Overall, statistical slices are, on average, $89\%$ larger than original dynamic slices. However, the corresponding failure paths are, on average, only $21\%$ larger. We consider this is an acceptable trade-off between over-approximation and low overhead (i.e., $\leq 5\%$) that makes our technique suitable for production use.

To summarize, we make the following contributions:

• —

  We present statistical program slicing, a hybrid dynamic–static slicing technique that leverages efficient hardware support for runtime monitoring combined with a customized static alias analysis to improve slice accuracy (section 3);

• —

  We develop a novel technique for runtime data flow analysis by relying on pointer tagging and distributing memory tracing across multiple runs of the same program (section 3.1);

• —

  We evaluate our approach on $\nrBugs$ failures from $\nrApps$ widely deployed applications and show its usefulness for bug diagnosis. On average, we recover $\woktAvgRRsliceT$ of the program statements present on the corresponding dynamic slice with only $\wokAvgOverhead$ instrumentation overhead (section 5).

The virtual address space on x86-64 architectures can accommodate up to $2^{64}$ addresses (i.e., $16$ exabytes) which far exceeds the memory needs of modern applications This far exceeds the needs of modern applications as current memory management implementations use only $48$ bits to represent memory addresses (intel17, ). Current systems us only $48$ bits to represent addresses. The reminder high order $16$ bits are either all $0$ or $1$. Departing from this specification makes the pointers uncanonical which raises a protection fault interrupting normal execution (intel17, ; kumar13, ).

Wok intercepts protection faults to peak at the current state of the execution. Specifically, Wok records the program counter, memory location and type of memory access. This information allows Wok to infer data dependencies between instructions that write and read the same address. Wok preserves tags for the entire life time of the corresponding object in order to ensure continuous monitoring and preserve memory consistency. Removing tags could further force us to maintain two versions of the same pointer— tagged and un-tagged—and ensure compiler optimizations such as direct pointer comparisons work correctly.

The benefits of pointer poisoning are two-fold. First, it allows us to trace memory virally: if $p$ is poisoned, its tag propagates whenever a new pointer is derived from $p$. Second, unlike traditional hardware breakpoints that can trace a limited number of bytes at a time, poisoning enables coarse grain memory monitoring at the object level with potentially unlimited number of watchpoints.

The drawback is the associated overhead penalty incurred by each protection fault.

To avoid under-sampling infrequent code paths and increase coverage, we rely on an adaptive sampling strategy that ensures objects are sampled inversely proportional to their access frequency. We rely on calling context (i.e., callstack) which is proven to be an effective predictor of objects with similar runtime behavior (hauswirth04, ; novark09, ; sumner08, ) to differentiate between allocation contexts and re-adjust sampling rates. Specifically, our policy oscillates between two phases:

• —

  low frequency: starting from $1.0$ (i.e., indiscriminate pointer poisoning), the sampling rate decreases exponentially if no memory accesses that lead to new data dependencies are being observed;

• —

  high frequency: once new memory accesses occur the sampling rate gets reset to $1.0$ and the process repeats.

We argue this best-effort strategy yields a reasonable approximation of the set of data dependencies executed during a faulty run and becomes more accurate with the number of runs observed. Intuitively, memory objects are often accessed from a limited number of places in the source code (barr13, ) (e.g., a linked list is accessed through dedicated member functions). Prior work has found that for short-running programs the set of memory accessing instructions is small and for long-running programs that set is mostly stable across different phases of the execution (novark09, ; chilimbi02, ). For this reason, we expect the number of data dependencies between instructions accessing memory objects to eventually converge.

We observe similar behavior when analyzing memory access patterns for our evaluations (section 5). Figure 3 illustrates the cumulative distribution of data dependencies collected as a function of the number of runs. As the number of runs increases, data dependency coverage begins to stabilize. And a little over half the inputs account for $\sim$$80\%$ of the data dependencies for $5$ out of $\nrApps$. SQLite’s behavior is an artifact of the available test suite that include numerous inputs designed to maximize branch coverage and test functionality in isolation (th3, ).

We rely on Intel PT for runtime control flow tracing with low overhead. Intel PT is an extension of the Intel PMU architecture available on Broadwell and Skylake CPU families (intel17, ). Intel PT records control flow information in a highly compressed format ($\sim$$0.5$ bits per retired assembly instruction (intel17, )) which encodes all branches executed by the program. Compressed traces are available for offline decoding to precisely recover the execution. Moreover, Intel PT incurs a modest overhead of $3$-$4\%$ (intel17, ; zhang17, ; kasikci15, ; kasikci17, ; ge2017, ).

In our usage model (Fig. 2), Wok decodes Intel PT traces on the server-side. Our tool uses this information to reconstruct precise control flow for the fault currently under investigation. Precise control flow is a necessary ingredient for computing program slices. Knowing which instructions executed during the faulty run helps Wok improve the accuracy of final slices in two ways. First, it allows our tool to filter data flow collected in aggregate at runtime (i.e., in step , Fig. 2) by pruning data dependencies that were not exercised during the faulty execution. Second, it improves the precision of static alias analysis by restricting the scope of the procedure to executed code only (i.e., step , Fig. 2).

The main source of imprecision when computing statistical program slices comes from sampling. In addition, the data flow analysis described in section 3.1 focuses on heap memory (i.e., by tracking pointers) and, up until now, ignores data dependencies that can be inferred statically (e.g., those related to stack variables).

We mitigate these shortcomings by using inter-procedural, flow-insensitive static alias analysis (andersen94, ). Static alias analysis is known to be imprecise, especially in the presence of pointers (weiser81, ; Korel1988, ; mock05, ; zhang05, ; kasikci13, ; nainar10, ; liblit03, ). To improve precision we restrict the scope of the procedure to code executed during the faulty run and retain only must aliases. Specifically, we use the PT trace to prune must aliasing pairs not exercised by the failure ( , Figure 2) when iteratively computing points-to sets. This allows us to perform an otherwise unscalable inter-procedural analysis using control flow information recorded by Intel PT for the faulty execution.

By disregarding may aliases, our procedure can potentially miss data dependencies for heap memory locations. We take this conservative approach in order to preserve soundness with respect to observed program execution. However, we will show that this restriction minimally impacts statistical slice accuracy in our evaluation (section 5).

Wok aggregates data dependencies collected cooperatively over multiple runs and combines them with the precise control flow information from the failing run to form an observed dependency graph. Wok transforms each program statement into a node and each control and data dependency observed at runtime into an arc. To account for data dependencies potentially missed during sampling, Wok further complements this graph with must aliases arcs computed by the execution-driven static alias analysis described above (3.3). Finally, Wok performs a backward traversal on the observed dependency graph starting from the seed instruction (horwitz98, ).

We discard dynamic instance information for data dependencies since we cannot reliably order memory accesses from multiple runs. Typically, “flattening” program flow can potentially lead to a significant size increase for the final slice size (agrawal90, ; zhang05, ). However, we mitigate most of these effects by pruning spurious data flow not exercised during the target execution (section 5).

Algorithm 1 describes how Wok computes statistical program slices. Initially, our prototype adds the $seed$ to a queue. At each step it pops an unprocessed element from the queue and adds the relevant dependencies from the complemented observed dependency graph. Using LLVM conventions (lattner2004llvm, ) these dependencies can be either a conditional clause (e.g., if-then-else), a function call/return, a function argument, or a memory access.

We compare Wokagainst textbook static and dynamic program slices generated by Giri, a state-of-the-art program slicing tool (swarup13, ). We evaluate our technique in terms of recovery rate, slice size and the ability to faithfully reconstruct failure paths.

We evaluate the accuracy of our technique on three different levels:

Our evaluation works in three stages. First, we run each test program against the training workloads described above. Second, we compute statistical slices for each tested bug using the failing program statements as slice seeds. Finally, we compare the output against the program slices produced by Giri.

Typically, we expect Wok to be configured in an environment where it tracks a large and diverse set of inputs before computing slices. For completeness, we also consider a different, albeit less frequent scenario where a failure with the same symptoms is encountered repeatedly (liblit05, ; kasikci15, ; ChilimbiLMNV09Holmes, ; kasikci13, ). Thus, instead of observing program behavior during normal utilization, we track data flow statistically from a particular faulty execution.

Note that our central findings, discussion and conclusions focus on the former, workload-driven scenario, rather than the latter. However, allowing Wok to monitor the same faulty execution repeatedly is not without merit. Intuitively, our algorithm performs best when reconstructing slices using the minimal set of data dependencies necessary to compute precise dynamic slices. Therefore, such a setup provides us with an “upper bound” on the accuracy and a “lower bound” on the size of statistical slices. This also helps strengthen the hypothesis that as bug-related program flow coverage increases, Wok is able to better approximate dynamic slices (see Table 2).

Table 1 compares program slices, recovery rates and root cause diagnosis capabilities between Wok and Giri. We break measurements down into slice sizes (columns labeled ‘Slice’) and distance to the root cause (columns labeled ‘Root cause’). Recovery rates between statistical and dynamic slices are reported in brackets and calculated using the $\mu$ ratio described above. For each failure, we instruct Wok to operate in both the workload-driven and failure only scenarios descried above. Columns labeled ‘Wok — cooperative’ report numbers after collecting data flow information over the entire set of training inputs. Columns labeled ‘Wok — failure only’ show measurements when operating exclusively over the set of data dependencies exercised during the failing run. Finally, we compare those against the program slices generated by Giri (columns ‘Giri — static’ and ‘Giri — dynamic’).

Wok recovers $\woktAvgRRsliceT$ of the program statements present on a precise dynamic slice (i.e., ‘Wok — cooperative’ columns). Wok further recovers an average of $92\%$ of the instructions linking the symptom to the root cause. In terms of slice sizes, Wok’s output is, on average, $89\%$ larger than that of Giri. This is still $21\times$ smaller when compared to static slices. While larger than textbook dynamic slices, we argue this is an acceptable trade-off between over-approximation and a $\wokAvgOverhead$ runtime overhead (section 5.3).

Our evaluation further reveals that having data flow exclusively from the faulty run enables Wok to recover almost $100\%$ of the corresponding dynamic slices. As expected, having $100\%$ failure-related data flow coverage translates into near-perfect dynamic slice recovery rate. The few program statements missed are stack variable declarations which Wok is unable to detect through static program analysis. We plan to mitigate such side effects by switching to a more powerful alias analysis.

In part, missing program statements are caused by sampling. The other cause is the quality of the static program analysis which is inherently imprecise (devecsery18, ; kasikci17, ). A close inspection revealed that the current alias analysis implementation excludes some stack variable allocation instructions. However, we believe these to be the least critical components of a slice which developers can easily infer from the control flow portion of a statistical slice.

Ultimately, reconstruction accuracy is influenced by the ability of our tool to collect enough relevant data dependencies. As coverage increases, our prototype is able to better approximate dynamic slices.

Program slices are dependent upon the seed statements for which slicing is performed (zhang03, ), potentially impacting measurements in Table 1. To mitigate biases, we also devise a slice-independent evaluation and measure recovery rates between sets of data dependencies. This is further motivated by the fact that the data flow instrumentation is the main source of approximation for statistical slices.

Table 2 compares the set of dynamic data dependencies constructed by Wok and Giri respectively. On average, Wok recovers $82\%$ of the data dependencies located on the precise dynamic slices, while the recovery rate for full slices goes up to $\woktAvgRRsliceT$. This increase can be attributed to the number of program dependencies linking two statements (typically, $1$-$4$ in our measurements). Consequently, Wok needs only to capture only one of them to include the two instructions.

Figure 4 shows the runtime penalty incurred by Wok. The overhead decreases with the sampling rate from $2.05\times$, $1.30\times$, $1.08\times$, to $1.05\times$ (geometric average). Assuming an overhead budget of $\leq 5\%$, we chose an optimal sampling rate between $\tfrac{1}{10,000}$ (i.e., $1$ in $10,000$ pointers allocated) and $\tfrac{1}{100,000}$.

At higher sampling rates, the “lion’s share” of the overhead is due to the hardware interrupts triggered by dereferencing poisoned pointers. On average, Wok incurs a penalty of $1.8$ $\mu$seconds per dereference. At a close inspection we discovered that $50\%$ of the time is spent in kernel space, inside Linux’s signal handling mechanism (do_signal – $6.5\%$, sys_rt_sigreturn – $3.3\%$, and general_protection – $2.7\%$).

At lower sampling rates, the overhead is dominated by Intel PT. Intel PT incurs $5.8\%$ geometrical average slowdown with slight performance degradation for short running tasks (i.e., $\leq 1.0$ seconds). This is due to the start-up and tear-down costs that cannot be amortized by the branch tracing itself.

Developers using our tool can perform a similar sensitivity analysis to determine which sampling rate to use. The overhead of pointer poisoning for a given workload can be computed analytically as

where $orig\_time$ is the running time of the application without instrumentation, $avg\_trap\_cost$ is the average cost of handling a single interrupt, and $exp\_hmem\_acc$ is the expected number of heap memory accesses for the current workload.