SIFT: a scalable iterative-unfolding technique for filtering execution traces

ABSTRACT

Comparing program execution traces can be useful for numerous purposes, such as software testing, system security analysis, program comprehension, software evolution and other areas of software development. Unfortunately, trace comparison techniques that operate on execution traces containing full execution details are too slow for use in large-scale production system environments. In order to speed up the comparisons, we propose a technique (called SIFT) for "filtering-out" irrelevant traces from a given set so that only the relevant few, residual, traces are then used for comparison. Our solution involves multiple levels of trace compression, each with a different degree of abstraction. These traces are compared iteratively while filtering out dissimilar traces. This paper describes the compression and comparison algorithms. Prototype results from a significant case study show that the SIFT approach is efficient and scalable for use in an industrial software development environment.

REFERENCES

• 1: Avvari, M. V., Chin, P. A., Nandigama, M. K. and Dhanikonda, Software application test coverage analyzer. U.S. Patent #6,978,401, Sun Microsystems, Inc., U.S., (2005).
• 2: Biermann, A. and Feldman, J. On the Synthesis of Finite State Machines from Samples of their Behavior. IEEE Trans. Computers, 21, 6 (1972), 592--597.
• 3: Jonathan E. Cook , Alexander L. Wolf, Discovering models of software processes from event-based data, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.3, p.215-249, July 1998 [doi>10.1145/287000.287001]
• 4: Domenico Cotroneo , Roberto Pietrantuono , Leonardo Mariani , Fabrizio Pastore, Investigation of failure causes in workload-driven reliability testing, Fourth international workshop on Software quality assurance: in conjunction with the 6th ESEC/FSE joint meeting, September 03-04, 2007, Dubrovnik, Croatia [doi>10.1145/1295074.1295089]
• 5: Dallmeier, V., Lindig, C. and Zeller, A. Lightweight Defect Localization for Java. In Proc. European Conference on Object Oriented Programming (2005), 528--550.
• 6: Davison, M., Gittens, M., Godwin, D., Madhavji, N. H., Miranskyy, A. V. and Wilding, M. Improvement of computer software test coverage analysis. U.S. Patent Application # 11/549410, IBM Corp., (2006).
• 7: Sebastian Elbaum , Satya Kanduri , Anneliese Andrews, Trace anomalies as precursors of field failures: an empirical study, Empirical Software Engineering, v.12 n.5, p.447-469, October 2007 [doi>10.1007/s10664-007-9042-8]
• 8: Sebastian Elbaum , Gregg Rothermel , Satya Kanduri , Alexey G. Malishevsky, Selecting a Cost-Effective Test Case Prioritization Technique, Software Quality Control, v.12 n.3, p.185-210, September 2004 [doi>10.1023/B:SQJO.0000034708.84524.22]
• 9: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Journal of Computer and System Sciences, v.51 n.2, p.261-272, Oct. 1995 [doi>10.1006/jcss.1995.1065]
• 10: Fremuth-Paeger, C. and Jungnickel, D. Balanced network flows. VIII. A revised theory of phase-ordered algorithms and the O(sqrt(n) m log(n^2 /m)/log n) bound for the nonbipartite cardinality matching problem. Networks, 41, 3 (2003), 137--142.
• 11: Orla Greevy , Stéphane Ducasse , Tudor Girba, Analyzing Feature Traces to Incorporate the Semantics of Change in Software Evolution Analysis, Proceedings of the 21st IEEE International Conference on Software Maintenance, p.347-356, September 25-30, 2005 [doi>10.1109/ICSM.2005.22]
• 12: Abdelwahab Hamou-Lhadj , Timothy C. Lethbridge, Compression Techniques to Simplify the Analysis of Large Execution Traces, Proceedings of the 10th International Workshop on Program Comprehension, p.159, June 27-29, 2002
• 13: Murali Haran , Alan Karr , Alessandro Orso , Adam Porter , Ashish Sanil, Applying classification techniques to remotely-collected program execution data, ACM SIGSOFT Software Engineering Notes, v.30 n.5, September 2005
• 14: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 15: kBehavior http://www.lta.disco.unimib.it/kbehavior/.
• 16: Adrian Kuhn , Orla Greevy, Exploiting the Analogy Between Traces and Signal Processing, Proceedings of the 22nd IEEE International Conference on Software Maintenance, p.320-329, September 24-27, 2006 [doi>10.1109/ICSM.2006.29]
• 17: Lee, W., Stolfo, S. J. and Chan, P. K. Learning patterns from unix process execution traces for intrusion detection. In Proc. AAAI Workshop: AI Approaches to Fraud Detection and Risk Management (1997), 50--56.
• 18: Levenshtein, V. I. Binary codes capable of correcting deletions, insertions, and reversals (Russian). Doklady Akademii Nauk SSSR, 163, 4 (1966), 845--848.
• 19: Li, M., Ma, B., Kisman, D. and Tromp, J. PatternHunter II: Highly Sensitive and Fast Homology Search. J. of Bioinformatics and Computational Biology, 2, 3 (2004), 417--440.
• 20: Mariani, L. and Pezzè, M. Inference of component protocols by the kBehavior algorithm. University of Milano Bicocca, 2004.
• 21: Leonardo Mariani , Mauro Pezzè, Dynamic Detection of COTS Component Incompatibility, IEEE Software, v.24 n.5, p.76-85, September 2007 [doi>10.1109/MS.2007.138]
• 22: Wes Masri , Andy Podgurski , David Leon, An Empirical Study of Test Case Filtering Techniques Based on Exercising Information Flows, IEEE Transactions on Software Engineering, v.33 n.7, p.454-477, July 2007 [doi>10.1109/TSE.2007.1020]
• 23: Miranskyy, A. V., Gittens, M. S., Madhavji, N. H. and Taylor, C. A. Usage of Long Execution Sequences for Test Case Prioritization. In Proc. Suppl. Proc. of 18th IEEE Int'l Symp. on Softw. Reliability Eng. (2007).
• 24: Miranskyy, A. V., Madhavji, N. H., Gittens, M. S., Davison, M., Wilding, M. and Godwin, D. An Iterative, Multi-Level, and Scalable Approach to Comparing Execution Traces, TR-74.209. IBM Center for Advanced Studies (CAS), Toronto, 2007 (https://www.ibm.com/ibm/cas/publications/index.shtml).
• 25: Johan Moe , David A. Carr, Using execution trace data to improve distribute systems, Software—Practice & Experience, v.32 n.9, p.889-906, July 2002 [doi>10.1002/spe.466]
• 26: Myers, E. An O(ND) Difference Algorithm and Its Variations. Algorithmica, 1, 2 (1986), 251--266.
• 27: Andy Podgurski , David Leon , Patrick Francis , Wes Masri , Melinda Minch , Jiayang Sun , Bin Wang, Automated support for classifying software failure reports, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 28: Steven P. Reiss , Manos Renieris, Encoding program executions, Proceedings of the 23rd International Conference on Software Engineering, p.221-230, May 12-19, 2001, Toronto, Ontario, Canada
• 29: Manos Renieris , Shashank Ramaprasad , Steven P. Reiss, Arithmetic program paths, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 30: Gregg Rothermel , Mary Jean Harrold , Jeffery Ostrin , Christie Hong, An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites, Proceedings of the International Conference on Software Maintenance, p.34, March 16-19, 1998
• 31: Chun Yuan , Ni Lao , Ji-Rong Wen , Jiwei Li , Zheng Zhang , Yi-Min Wang , Wei-Ying Ma, Automated known problem diagnosis with event traces, Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006, April 18-21, 2006, Leuven, Belgium

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management
          Subjects: Software development

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.9 Management

General Terms:
Algorithms