Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

During the system development, developers often must correct wrong behavior in the software---an activity colloquially called program debugging. Debugging is a complex activity, especially in real-time embedded systems because such systems interact with the physical world and make heavy use of interrupts for timing and driving I/O devices.

Debugging interrupts is difficult, because they cause non-linear control flow in programs which is hard to reproduce in software. Record/replay mechanisms have proven their use to debugging embedded systems, because they provide means to recreate control flows offline where they can be debugged.

In this work, we present the data tracing part of the record/replay mechanism that is specifically targeted to record interrupt behavior. To tune our tracing mechanism, we use the observed principle of return address clustering and a formal model for quantitative reasoning about the tracing mechanism. The presented heuristic and mechanisms show surprisingly good results---up to an 800 percent speedup on the selector function and a 300 percent reduction on duplicates for non-optimal selector functions---considering the leanness of the approach.

REFERENCES

• 1: Standard Test Access Port and Boundary-Scan Architecture. IEEE 1149.1 standard, 2001.
• 2: Standard for a Global Embedded Processor Debug Interface, 2003.
• 3: J. Baginski , H. Seiffert, Interaktives Trace- und Debugging- System ALGOL KIEL X 8, 3. Fachtagung über Programmiersprachen, Gesellschaft für Informatik, p.173-188, March 05-07, 1974
• 4: Dan H. Barnes , Larry L. Wear, Instruction tracing via microprogramming, Conference record of the 7th annual workshop on Microprogramming, p.25-27, September 30-October 02, 1974, Pal Alto, California, United States [doi>10.1145/800118.803836]
• 5: Bruno Bouyssounouse , Joseph Sifakis, Embedded Systems Design: The ARTIST Roadmap for Research and Development (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 6: T. A. Cargill , B. N. Locanthi, Cheap hardware support for software debugging and profiling, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.82-83, October 1987, Palo Alto, California, United States
• 7: Paul S. Dodd , Chinya V. Ravishankar, Monitoring and debugging distributed real-time programs, Monitoring and debugging of distributed real-time systems, IEEE Computer Society Press, Los Alamitos, CA, 1995
• 8: Edward A. Fox , Lenwood S. Heath , Qi Fan Chen , Amjad M. Daoud, Practical minimal perfect hash functions for large databases, Communications of the ACM, v.35 n.1, p.105-121, Jan. 1992 [doi>10.1145/129617.129623]
• 9: Antonio Augusto Froehlich. Application-Oriented Operating Systems. Number 17 in GMD Research Series. GMD -- Forschungszentrum Informationstechnik, Sankt Augustin, August 2001.
• 10: M.P. Gallaher and B.M. Kropp. The Economic Impacts of Inadequate Infrastructure for Software Testing. National Institute of Standards & Technologg Planning Report 02--03, May 2002.
• 11: Robert Jenkins. Hash Functions. Dr. Dobb's, September 1997.
• 12: Moonzoo Kim , Mahesh Viswanathan , Sampath Kannan , Insup Lee , Oleg Sokolsky, Java-MaC: A Run-Time Assurance Approach for Java Programs, Formal Methods in System Design, v.24 n.2, p.129-155, March 2004 [doi>10.1023/B:FORM.0000017719.43755.7c]
• 13: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 14: Kyle London, Mastering algorithms with C, O'Reilly & Associates, Inc., Sebastopol, CA, 1999
• 15: J. M. Mellor-Crummey , T. J. LeBlanc, A software instruction counter, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.78-86, April 03-06, 1989, Boston, Massachusetts, United States
• 16: Linda J. Moore , Angelica R. Moya, Non-Intrusive Debug Technique for Embedded Programming, Proceedings of the 14th International Symposium on Software Reliability Engineering, p.375, November 17-21, 2003
• 17: William Omre. Debug and Trace for Multicore SoCs. Technical report, ARM, September 2008.
• 18: Michiel Ronsse , Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.133-152, May 1999 [doi>10.1145/312203.312214]
• 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: D. Sundmark and H. Thane. Pinpointing Interrupts in Embedded Real-Time Systems using Context Checksums. In Proc. of the 13th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), Hamburg, Germany, 2008.
• 21: D. Sundmark, H. Thane, J. Huselius, and A. Pettersson. Replay Debugging of Complex Real-Time Systems: Experiences from Two Industrial Case Studies. In Proc. of the 5th International Workshop on Algorithmic and Automated Debugging (AADEBUG), pages 211--222, Gent, Belgium, September 2003.
• 22: Andrew S. Tanenbaum, Modern Operating Systems, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 23: H. Thane. Monitoring, Testing and Debugging of Distributed Real-Time Systems. PhD thesis, Department of Computer Science and Electronics, Malardalens University, May 2000.
• 24: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 25: J. J. P. Tsai , K.-Y. Fang , H.-Y. Chen , Y.-D. Bi, A Noninterference Monitoring and Replay Mechanism for Real-Time Software Testing and Debugging, IEEE Transactions on Software Engineering, v.16 n.8, p.897-916, August 1990 [doi>10.1109/32.57626]

INDEX TERMS

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

General Terms:
Design, Experimentation

Keywords:
debugging, embedded software, real-time systems, tracing