Correctness of trap-based breakpoint implementations

ABSTRACT

It is common for debuggers to implement breakpoints by a combination of planting traps and single stepping. When the target program contains multiple threads of execution, a debugger that is not carefully implemented may miss breakpoints. This paper gives a formal model of a breakpoint in a two-threaded program. The model describes correct and incorrect breakpoint implementations. Automatic search of the model's state space shows that the correct implementation does miss a breakpoint. The results apply even to debuggers like dbx and gdb, which are apparently for single-threaded programs; when the user evaluates an expression containing function calls, the debugger executes the call in the target address space, in effect creating a new thread.

REFERENCES

• 1: Z. Aral , I. Gerther , G. Schaffer, Efficient debugging primitives for multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.87-95, April 03-06, 1989, Boston, Massachusetts, United States
• 2: Bernd Bruegge, Adaptability and portability of symbolic debuggers, 1985
• 3: Caswell, Deborah and David Black. 1990 (January). implementing a Mach debugger for multithreaded applications. In Proceedings of the Winter USENIX Conference, pages 25-39, Washington, DC.
• 4: Digital Equipment Corporation. 1975. DDT--Dynamic Debugging Technique. Maynard, MA.
• 5: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 6: Michael M. Gorlick, The flight recorder: an architectural aid for system monitoring, ACM SIGPLAN Notices, v.26 n.12, p.175-181, Dec. 1991
• 7: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 8: Gerard J. Holzmann, Design and validation of computer protocols, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 9: Peter B. Kessler, Fast breakpoints: design and implementation, ACM SIGPLAN Notices, v.25 n.6, p.78-84, Jun. 1990
• 10: Donald E. Knuth, Literate programming, The Computer Journal, v.27 n.2, p.97-111, May 1984 [doi>10.1093/comjnl/27.2.97]
• 11: Linton, Mark A. 1990 (June). The evolution of Dbx. In Proceeding8 o} the Summer USENIX Conference, pages 211-220, Anaheim, CA.
• 12: Ramsey, Norman. 1992a (August). Literate-programming tools need not be complex. Technical Report CS-TR-351-91, Department of Computer Science, Princeton University. Submitted to IEEE Software.
• 13: 1992b (December). A Retargetable Debugger. PhD thesis, Princeton University, Department of Computer Science. Also Technical Report CS-TR-403-92.
• 14: David D. Redell, Experience with topaz telebugging, ACM SIGPLAN Notices, v.24 n.1, p.35-44, Jan. 1989
• 15: Stallman, Richard M. and Roland H. Pesch. 1991. Using GDB: A guide to the GNU source-level debugger, GDB version 4.0. Technical report, Free Software Foundation, Cambridge, MA.
• 16: Robert Wahbe, Efficient data breakpoints, ACM SIGPLAN Notices, v.27 n.9, p.200-212, Sept. 1992

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Languages, Measurement, Theory