3576620
Cost effective dynamic program slicing
Although dynamic program slicing was first introduced to aid in user level debugging, applications aimed at improving software quality, reliability, security, and performance have since been identified as candidates for using dynamic slicing. However, the dynamic dependence graph constructed to compute dynamic slices can easily cause slicing algorithms to run out of memory for realistic program runs. In this paper we present the design and evaluation of a cost effective dynamic program slicing algorithm. This algorithm is based upon a dynamic dependence graph representation that is highly compact and rapidly traversable. Thus, the graph can be held in memory and dynamic slices can be quickly computed. A compact representation is derived by recognizing that all dynamic dependences (data and control) need not be individually represented. We identify sets of dynamic dependence edges between a pair of statements that can share a single representative edge. We further show that the dependence graph can be transformed in a manner that increases sharing and sharing can be performed even in the presence of aliasing. Experiments show that transformed dynamic dependence graphs explicitly represent only 6% of the dependence edges present in the full dynamic dependence graph. When the full graph sizes range from 0.84 to 1.95 Gigabytes in size, our compacted graphs range from 20 to 210 Megabytes in size. Average slicing times for our algorithm range from 1.74 to 36.25 seconds across several benchmarks from SPECInt2000/95.
3555343
Matching execution histories of program versions
We develop a method for matching dynamic histories of program executions of two program versions. The matches produced can be useful in many applications including software piracy detection and several debugging scenarios. Unlike some static approaches for matching program versions, our approach does not require access to source code of the two program versions because dynamic histories can be collected by running instrumented versions of program binaries. We base our matching algorithm on comparison of rich program execution histories which include: control flow taken, values produced, addresses referenced, as well as data dependences exercised. In developing a matching algorithm we had two goals: producing an accurate match and producing it quickly. By using rich execution history, we are able to compare the program versions across many behavioral dimensions. The result is a fast and highly precise matching algorithm. Our algorithm first uses individual histories of instructions to identify multiple potential matches and then it refines the set of matches by matching the data dependence structure established by the matching instructions. To test our algorithm we attempted matching of execution histories of unoptimized and optimized program versions. Our results show that our algorithm produces highly accurate matches which are highly effective when used in comparison checking approach to debugging optimized code.
3561000
Extended whole program paths
We describe the design, generation and compression of the extended whole program path (eWPP) representation that not only captures the control flow history of a program execution but also its data dependence history. This representation is motivated by the observation that typically a significant fraction of data dependence history can be recovered from the control flow trace. To capture the remainder of the data dependence history we introduce disambiguation checks in the program whose control flow signatures capture the results of the checks. The resulting extended control flow trace enables the recovery of otherwise unrecoverable data dependences. The code for the checks is designed to minimize the increase in the program execution time and the extended control flow trace size when compared to directly collecting control flow and dependence traces. Our experiments show that compressed eWPPs are only 4% of the size of combined compressed control flow and dependence traces and their collection requires 20% more runtime overhead than overhead required for directly collecting the control flow and dependence traces.
3575990
Pruning dynamic slices with confidence
Given an incorrect value produced during a failed program run (e.g., a wrong output value or a value that causes the program to crash), the backward dynamic slice of the value very frequently captures the faulty code responsible for producing the incorrect value. Although the dynamic slice often contains only a small percentage of the statements executed during the failed program run, the dynamic slice can still be large and thus considerable effort may be required by the programmer to locate the faulty code.In this paper we develop a strategy for pruning the dynamic slice to identify a subset of statements in the dynamic slice that are likely responsible for producing the incorrect value. We observe that some of the statements used in computing the incorrect value may also have been involved in computing correct values (e.g., a value produced by a statement in the dynamic slice of the incorrect value may also have been used in computing a correct output value prior to the incorrect value). For each such executed statement in the dynamic slice, using the value profiles of the executed statements, we compute a confidence value ranging from 0 to 1 - a higher confidence value corresponds to greater likelihood that the execution of the statement produced a correct value. Given a failed run involving execution of a single error, we demonstrate that the pruning of a dynamic slice by excluding only the statements with the confidence value of 1 is highly effective in reducing the size of the dynamic slice while retaining the faulty code in the slice. Our experiments show that the number of distinct statements in a pruned dynamic slice are 1.79 to 190.57 times less than the full dynamic slice. Confidence values also prioritize the statements in the dynamic slice according to the likelihood of them being faulty. We show that examining the statements in the order of increasing confidence values is an effective strategy for reducing the effort of fault location.
3597789
Efficient forward computation of dynamic slices using reduced ordered binary decision diagrams
Dynamic slicing algorithms can greatly reduce the debugging effort by focusing the attention of the user on a relevant subset of program statements. Recently, algorithms for forward computation of dynamic slices have been proposed which maintain dynamic slices of all variables as the program executes. An advantage of this approach is that when a request for a slice is made, it is already available. The main disadvantage of using such an algorithm for slicing realistic programs is that the space and time required to maintain a large set of dynamic slices corresponding to all program variables can be very high. In this paper, we analyze the characteristics of dynamic slices and identify properties that enable space efficient representation of a set of dynamic slices. We show that by using reduced ordered binary decision diagrams (roBDDs) to represent a set of dynamic slices, the space and time requirements of maintaining dynamic slices are greatly reduced. In fact, not only can the latest dynamic slices of all variables be easily maintained, but rather all dynamic slices of all variables throughout a program's execution can be maintained. Our experiments show that our roBDD based algorithm for forward computation of dynamic slices can maintain 107-217 million dynamic slices arising during long program runs using only 28-392 megabytes of storage. In addition, the performance of the roBDD based forward computation method compares favorably with the performance of the LP backward computation algorithm.
3566372
Hiding program slices for software security
Given the high cost of producing software, development of technology for prevention of software piracy is important for the software industry. In this paper we present a novel approach for preventing the creation of unauthorized copies of software. Our approach splits software modules into open and hidden components. The open components are installed (executed) on an insecure machine while the hidden components are installed (executed) on a secure machine. We assume that while open components can be stolen, to obtain a fully functioning copy of the software, the hidden components must be recovered. We describe an algorithm that constructs hidden components by slicing the original software components. We argue that recovery of hidden components constructed through slicing, in order to obtain a fully functioning copy of the software, is a complex task. We further develop security analysis to capture the complexity of recovering hidden components. Finally we apply our technique to several large Java programs to study the complexity of recovering constructed hidden components and to measure the runtime overhead introduced by splitting of software into open and hidden components.
17354053
Graphs with fourth Laplacian eigenvalue less than two
In this paper, all connected graphs with the fourth largest Laplacian eigenvalue less than two are determined, which are used to characterize all connected graphs with exactly three Laplacian eigenvalues no less than two. Moreover, we determine bipartite graphs such that the adjacency matrices of their line graphs have exactly three nonnegative eigenvalues.
5639888
Strategies for using additional resources in parallel hash-based join algorithms
Hash-based join is a compute- and memory-intensive algorithm. It achieves good performance and scales well to large datasets, if sufficient memory is available to hold the hash table and the distribution of computing had across nodes is balanced. We compare three adaptive algorithms that start with a partitioning of the hash table across a group of nodes and expand during the hash table building phase to additional resources, when memory on a node is used up. The split-based algorithm partitions the hash table range assigned to the node, on which memory is full, into two segments and assigns one of the segments to a new node in the system. The replication-based algorithm replicates the hash table range on a new node. The hybrid algorithm combines the first and second strategies in order to address each strategy's short comings. We perform an experimental performance evaluation of these algorithms on a PC cluster. Our results show that among the three algorithms, in most cases the hybrid algorithm either performs close to the better of the two or is the best algorithm.
12113641
Neighbor number, valley seeking and clustering
This paper proposes a novel nonparametric clustering algorithm capable of identifying shape-free clusters. This algorithm is based on a nonparametric estimation of the normalized density derivative (NDD) and the local convexity of the density distribution function, both of which are represented in a very concise form in terms of neighbor numbers. We use NDD to measure the dissimilarity between each pair of observations in a local neighborhood and to build a connectivity graph. Combined with the local convexity, this similarity measure can detect observations in local minima (valleys) of the density function, which separate observations in different major clusters. We demonstrate that this algorithm has a close relationship with the single-linkage hierarchical clustering and can be viewed as its extension. The performance of the algorithm is tested with both synthetic and real datasets. An example of color image segmentation is also given. Comparisons with several representative existing algorithms show that the proposed method can robustly identify major clusters even when there are complex configurations and/or large overlaps.
13183312
Wavelet based automatic thresholding for image segmentation
In this paper, a new systematic method to segment possible target areas based on wavelet transforms is presented. We develop an analytic model for the segmentation of targets, which uses a novel multiresolution analysis in concert with a Bayesian classifier to identify the possible target areas. A method is developed which adaptively chooses thresholds to segment targets from background, by using a multiscale analysis of the image probability density function (PDF). We present examples which demonstrate the efficiency of the technique on a variety of targets.
2396831
Mining coherent patterns from heterogeneous microarray data
Microarray technology is a powerful tool for geneticists to monitor interactions among tens of thousands of genes simultaneously. There has been extensive research on coherent subspace clustering of gene expressions measured under consistent experimental settings. However, these methods assume that all experiments are run using the same batch of microarray chips with similar characteristics of noise. Algorithms developed under this assumption may not be applicable for analyzing data collected from heterogeneous settings, where the set of genes being monitored may be different and expression levels may be not directly comparable even for the same gene. In this paper, we propose a model, F-cluster, for mining subspace coherent patterns from heterogeneous gene expression data. We compare our model with previously proposed models. We analyze the search space of the problem and give a naïve solution for it.