6023729
Accurately Choosing Execution Runs for Software Fault Localization
Software fault localization involves locating the exact cause of error for a “failing” execution run – a run which exhibits an unexpected behavior. Given such a failing run, fault localization often proceeds by comparing the failing run with a “successful” run, that is, a run which does not exhibit the unexpected behavior. One important issue here is the choice of the successful run for such a comparison. In this paper, we propose a control flow based difference metric for this purpose. The difference metric takes into account the sequence of statement instances (and not just the set of these instances) executed in the two runs, by locating branch instances with similar contexts but different outcomes in the failing and the successful runs. Given a failing run πf and a pool of successful runs S, we choose the successful run πs from S whose execution trace is closest to πf in terms of the difference metric. A bug report is then generated by returning the difference between πf and πs. We conduct detailed experiments to compare our approach with previously proposed difference metrics. In particular, we evaluate our approach in terms of (a) effectiveness of bug report for locating the bug, (b) size of bug report and (c) size of successful run pool required to make a decent choice of successful run.
14256633
Symbolic Execution of Behavioral Requirements
Message Sequence Charts (MSC) have traditionally been used as a weak form of behavioral requirements in software design; they denote scenarios which may happen. Live Sequence Charts (LSC) extend Message Sequence Charts by also allowing the designer to specify scenarios which must happen. Live Sequence Chart specifications are executable; their simulation allows the designer to play out potentially aberrant scenarios prior to software construction. In this paper, we propose the use of Constraint Logic Programming (CLP) for symbolic execution of requirements described as Live Sequence Charts. The utility of CLP stems from its ability to execute in the presence of uninstantiated variables. This allows us to simulate multiple scenarios at one go. For example, several scenarios which only differ from each other in the value of a variable may be executed as a single scenario where the variable is left uninstantiated. Similarly, we can simulate scenarios with an unbounded number of processes. We use the power of CLP to also simulate charts with non-trivial timing constraints. Current works on MSC/LSCs use data/control variables mainly for ease of specification; they are instantiated to concrete values during simulation. Thus, our work advances the state-of-the-art in simulation and checking of MSC based software requirements.
12394125
Using compressed bytecode traces for slicing Java programs
Dynamic slicing is a well-known program debugging technique. Given a program P and input I, it finds all program statements which directly/indirectly affect the values of some variables' occurrences when P is executed with I. Dynamic slicing algorithms often proceed by traversing the execution trace of P produced by input I (or a dependence graph which captures control/data flow in the execution trace). Consequently, it is important to develop space efficient representations of the execution trace. In this paper, we use results from data compression to compactly represent bytecode traces of sequential Java programs. The major space savings come from the optimized representation of data (instruction) addresses used by memory reference (branch) bytecodes as operands. We give detailed experimental results on the space efficiency and time overheads for our compact trace representation. We then show how dynamic slicing algorithms can directly traverse our compact traces without resorting to costly decompression. We also develop an extension of dynamic slicing which allows us to explain omission errors (i.e. why some events did not happen during program execution).
1817451
Automated path generation for software fault localization
Localizing the cause(s) of an observable error lies at the heart of program debugging. Fault localization often proceeds by comparing the failing program run with some "successful" run (a run which does not demonstrate the error). An issue here is to generate or choose a "suitable" successful run; this task is often left to the programmer. In this paper, we present an efficient technique where the construction of the successful run as well its comparison with the failing run is automated. Our method constructs a successful program run by toggling the outcomes of some conditional branch instances in the failing run. If such a successful run exists, program statements for these branches are returned as bug report. In our experiments with the Siemens benchmark suite, we found that the quality of our bug report compares well with those produced by existing fault localization approaches where the programmer manually provides or chooses a successful run.
9564557
An Object-Oriented Approach to Shadow Generation in Computer Graphics
This paper presents an object-oriented shadow generation algorithm for a large number of convex polyhedra (objects) in a 3-D scene. In the past, the shadow volume binary space partitioning (SVBSP) tree algorithm is known to be efficient in a static environment in which the point light source can be changed. However, if a scene consists of many objects and each object consists of many polygons, the time complexity for generating and traversing an SVBSP tree increases rapidly because the SVBSP tree algorithm only deals with polygons which are components of objects. Furthermore, the SVBSP tree algorithm suffers from polygon-splitting problems resulting in a high cost as the number of polygons increases. Our approach is object-oriented in the sense that an object is used as the basic logical unit instead of polygons. In the preprocessing stage the object ordering for shadow generation is determined for all possible light source positions. At the run time, the shadow detection algorithm is executed, and if nec...
18451647
Optimal circuit clustering for delay minimization under a more general delay model
This paper considers the area-constrained clustering of combinational circuits for delay minimization under a more general delay model, which practically takes variable interconnect delay into account. Our delay model is particularly applicable when allowing the back-annotation of actual delay information to drive the clustering process. We present a vertex grouping technique and integrate it with the algorithm (Rajaraman and Wong, 1995) such that our algorithm can be proved to solve the problem optimally in polynomial time.
30326495
Performance-driven channel pin assignment algorithms
In this paper we consider two channel pin assignment problems which take circuit performance into account. The first one is the module implementation selection problem. We are given a net span bound for each critical net and each module has several possible placements of its pins. Our objective is to minimize channel density while satisfying net span constraints. We proved that this problem is NP-complete. For the case when each module has at most 2 pin placements, the problem can be transformed to the 2-SAT problem and hence is polynomial time solvable. We present a heuristic based on this algorithm to solve the general case. The second problem we consider is the module shifting problem. We are given a set of modules whose relative ordering is fixed on each side of the channel but their exact positions are not fixed. We present a polynomial time algorithm to test the feasibility of satisfying the net span constraints by shifting the modules. The algorithm is based on formulating the problem as a special integer linear programming problem which is solvable in polynomial time. We also extend our algorithms to handle multiple channels. >
2771138
Localization with dynamic motion models - determining motion model parameters dynamically in monte carlo localization
An electrical overload circuit breaker utilizes as the current-responsive tripping mechanism a solenoid, the coil of which is constituted by a helical spring of shape memory effect material and which mechanically acts on the armature. There is a non-SME spring which also acts on the armature but in a direction opposing the SME spring. The current is passed through the SME spring and, when it becomes excessive, the armature is urged both mechanically and electromagnetically in a tripping direction.
16865574
On the superiority of DO-RE-ME/MPG-D over stuck-at-based defective part level prediction
Uses data collected from benchmark circuit simulations to examine the relationship between the tests which detect stuck-at faults and those which detect bridging surrogates. We show that the coefficient of correlation between these tests approaches zero as the stuck-at fault coverage approaches 100%. An enhanced version of the MPG-D model, which is based upon the number of detections of each site in a logic circuit, is shown to be superior to stuck-at fault coverage-based defective part level prediction. We then compare the accuracy of both predictors for an industrial circuit tested using two different test pattern sequences.