An iterative, multi-level, and scalable approach to comparing execution traces

ABSTRACT

In this paper, we overview a new approach to comparing execution traces. Such comparison can be useful for purposes such as improving test coverage and profiling system's users. In our approach, traces are compressed into different levels of compaction and are then compared iteratively from highest to lowest levels, rejecting dissimilar traces in the process and eventually leaving residual, similar traces. These residual traces form an important feedback for improvement or analysis goals. The preliminary results show that the approach is scalable for industrial use.

REFERENCES

• 1: Avvari, M. V., Chin, P. A., Nandigama, M. K. and Dhanikonda, U. S., Software application test coverage analyzer. In U.S. Patent # 6,978,401, (2005), Sun Microsystems, Inc.
• 2: Jennifer Black , Emanuel Melachrinoudis , David Kaeli, Bi-Criteria Models for All-Uses Test Suite Reduction, Proceedings of the 26th International Conference on Software Engineering, p.106-115, May 23-28, 2004
• 3: 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]
• 4: Fremuth-Paeger, C. and Jungnickel, D. Balanced network flows. VIII. A revised theory of phase-ordered algorithms and the O{√|V||E|log(|V²|/|E|)/log(|V|)} bound for the nonbipartite cardinality matching problem. Networks, 41, 3 (2003), 137--142.
• 5: 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
• 6: 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
• 7: M. Jean Harrold , Rajiv Gupta , Mary Lou Soffa, A methodology for controlling the size of a test suite, ACM Transactions on Software Engineering and Methodology (TOSEM), v.2 n.3, p.270-285, July 1993 [doi>10.1145/152388.152391]
• 8: ILOG CPLEX http://www.ilog.com/products/cplex/.
• 9: Intel. Code-Coverage Tool http://www.intel.com/cd/software/products/asmo-na/eng/compilers/219794.htm.
• 10: 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]
• 11: 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). Also available as Technical Report #686, Department of Computer Science, University of Western Ontario, Canada.
• 12: Offutt, A. J., Pan, J. and Voas, J. M., Procedures for Reducing the Size of Coverage-Based Test Sets. In Proc. 12th International Conference on Testing Computer Software, (1995), 111--123.
• 13: 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
• 14: 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
• 15: 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
• 16: Gregg Rothermel , Sebastian Elbaum , Alexey G. Malishevsky , Praveen Kallakuri , Xuemei Qiu, On test suite composition and cost-effective regression testing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.13 n.3, p.277-331, July 2004 [doi>10.1145/1027092.1027093]
• 17: Gregg Rothermel , Roland J. Untch , Chengyun Chu, Prioritizing Test Cases For Regression Testing, IEEE Transactions on Software Engineering, v.27 n.10, p.929-948, October 2001 [doi>10.1109/32.962562]
• 18: Telcordia. xSUDS http://xsuds.argreenhouse.com/.
• 19: TestWorks TCAT http://www.soft.com/TestWorks/Products/Coverage/.
• 20: W. Eric Wong , Joseph R. Horgan , Aditya P. Mathur , Alberto Pasquini, Test Set Size Minimization and Fault Detection Effectiveness: A Case Study in a Space Application, Proceedings of the 21st International Computer Software and Applications Conference, p.522, August 11-15, 1997
• 21: 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:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

General Terms:
Algorithms, Measurement, Reliability, Verification

Keywords:
code coverage, dynamic information flow analysis, execution traces, software testing, traces comparison