Enabling tracing Of long-running multithreaded programs via dynamic execution reduction

ABSTRACT

Debugging long running multithreaded programs is a very challenging problem when using tracing-based analyses. Since such programs are non-deterministic, reproducing the bug is non-trivial and generating and inspecting traces for long running programs can be prohibitively expensive. We propose a framework in which, to overcome the problem of bug reproducibility, a lightweight logging technique is used to log the events during the original execution. When a bug is encountered, it is reproduced using the generated log and during the replay, a fine-grained tracing technique is employed to collect control-flow/dependence traces that are then used to locate the root cause of the bug. In this paper, we address the key challenges resulting due to tracing, that is, the prohibitively high expense of collecting traces and the significant burden on the user who must examine the large amount of trace information to locate the bug in a long-running multithreaded program. These challenges are addressed through execution reduction that realizes a combination of logging and tracing such that traces collected contain only the execution information from those regions of threads that are relevant to the fault. This approach is highly effective because we observe that for long running multithreaded programs, many threads that execute are irrelevant to the fault. Hence, these threads need not be replayed and traced when trying to reproduce the bug. We develop a novel lightweight scheme that identifies such threads by observing all the interthread data dependences and removes their execution footprint in the replay run. In addition, we identify regions of thread executions that need not be replayed or, if they must be replayed, we determine if they need not be traced. Following execution reduction, the replayed execution takes lesser time to run and it produces a much smaller trace than the original execution. Thus, the cost of collecting traces and the effort of examining the traces to locate the fault are greatly reduced.

REFERENCES

• 1: www.mysql.org
• 2: http://bugs.mysql.com/bug.php?id=110
• 3: http://bugs.mysql.com/bug.php?id=169
• 4: http://bugs.mysql.com - Change Log
• 5: http://www.securityfocus.com/bid/12635
• 6: http://prozilla.genesys.ro/?p=news
• 7: http://www.securityfocus.com/bid/13059
• 8: Sanjay Bhansali , Wen-Ke Chen , Stuart de Jong , Andrew Edwards , Ron Murray , Milenko Drinić , Darek Mihočka , Joe Chau, Framework for instruction-level tracing and analysis of program executions, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1220164]
• 9: Neelam Gupta , Haifeng He , Xiangyu Zhang , Rajiv Gupta, Locating faulty code using failure-inducing chops, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101948]
• 10: Tibor Gyimóthy , Árpád Beszédes , Istán Forgács, An efficient relevant slicing method for debugging, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.303-321, September 06-10, 1999, Toulouse, France
• 11: B. Korel , J. Laski, Dynamic program slicing, Information Processing Letters, v.29 n.3, p.155-163, October 26, 1988 [doi>10.1016/0020-0190(88)90054-3]
• 12: S. Lu, Z. Li, F. Qin, L. Tan, P. Zhou, and Y. Zhou, "BugBench: a benchmark for evaluating bug detection tools", Workshop on the Evaluation of Software Defect Detection Tools, 2005.
• 13: Satish Narayanasamy , Gilles Pokam , Brad Calder, BugNet: Continuously Recording Program Execution for Deterministic Replay Debugging, Proceedings of the 32nd annual international symposium on Computer Architecture, p.284-295, June 04-08, 2005
• 14: Satish Narayanasamy , Cristiano Pereira , Brad Calder, Recording shared memory dependencies using strata, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 15: Robert H. B. Netzer , Mark H. Weaver, Optimal tracing and incremental reexecution for debugging long-running programs, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.313-325, June 20-24, 1994, Orlando, Florida, United States
• 16: Douglas Z. Pan , Mark A. Linton, Supporting reverse execution for parallel programs, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.124-129, May 05-06, 1988, Madison, Wisconsin, United States
• 17: Feng Qin , Joseph Tucek , Jagadeesan Sundaresan , Yuanyuan Zhou, Rx: treating bugs as allergies---a safe method to survive software failures, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 18: Martin Rinard , Cristian Cadar , Daniel Dumitran , Daniel M. Roy , Tudor Leu , William S. Beebee, Jr., Enhancing server availability and security through failure-oblivious computing, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.21-21, December 06-08, 2004, San Francisco, CA
• 19: Michiel Ronsse , Koen De Bosschere , Mark Christiaens , Jacques Chassin de Kergommeaux , Dieter Kranzlmüller, Record/replay for nondeterministic program executions, Communications of the ACM, v.46 n.9, p.62-67, September 2003 [doi>10.1145/903893.903895]
• 20: M. Ronsse, K. De Bosschere, and J. C. de Kergommeaux, "Execution replay and debugging", Fourth Workshop on Automated and Analysis-Driven Debugging, Munich, Germany, August 2000.
• 21: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 22: Yasushi Saito, Jockey: a user-space library for record-replay debugging, Proceedings of the sixth international symposium on Automated analysis-driven debugging, p.69-76, September 19-21, 2005, Monterey, California, USA [doi>10.1145/1085130.1085139]
• 23: Alexandru Salcianu , Martin Rinard, Pointer and escape analysis for multithreaded programs, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.12-23, June 2001, Snowbird, Utah, United States
• 24: J. Seward et al. "Valgrind: A GPL'd system for debugging and profiling x86-linux programs", http://valgrind.ked.org/, 2004.
• 25: Sudarshan M. Srinivasan , Srikanth Kandula , Christopher R. Andrews , Yuanyuan Zhou, Flashback: a lightweight extension for rollback and deterministic replay for software debugging, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.3-3, June 27-July 02, 2004, Boston, MA
• 26: Larry D. Wittie, Debugging distributed C programs by real time reply, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.57-67, May 05-06, 1988, Madison, Wisconsin, United States
• 27: Min Xu , Rastislav Bodik , Mark D. Hill, A "flight data recorder" for enabling full-system multiprocessor deterministic replay, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 28: Min Xu , Mark D. Hill , Rastislav Bodik, A regulated transitive reduction (RTR) for longer memory race recording, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 29: Xiangyu Zhang , Rajiv Gupta, Whole Execution Traces, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.105-116, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.37]
• 30: Xiangyu Zhang , Sriraman Tallam , Rajiv Gupta, Dynamic slicing long running programs through execution fast forwarding, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181786]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Debugging aids

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing; Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms, Measurement, Reliability

Keywords:
checkpointing, control flow, debugging, dependence tracing, event logging, replay