Method and system for detecting runtime defects in a program by comparing correct and incorrect runs

• US 7,530,056 B1
• Filed: 03/31/2008
• Issued: 05/05/2009
• Est. Priority Date: 03/31/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yaari, Yaakov, Heilper, Andre
• Primary Examiner(s): Kiss; Eric B
• Application Number:
  US12/060,238
• Time in Patent Office: 400 Days
• Field of Search: 717/128, 717/129
• US Class Current: 717/128
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3644 by instrumenting at runtime
• CPC Class Codes: G06F 11/366 using diagnostics G06F11/0703 takes precedence

Abstract

The invention provides an improved method and method for locating the origin of runtime defect in software programs. A differential debugging technique may be implemented to locate the diversion point where two programs start to behave differently. In one approach, the method generally involves running the two programs and generating respective control flow diagrams via a static code analyzer or the like. Tracer and supervisor modules may be used to replace addresses in registers with symbols and/or position-independent offsets, and to locate where differences in the register states occur.

Claims

1. A method for locating where a runtime defect occurs in an updated program, comprising:

(a) generating a first control flow graph (CFG) for an original program, the original program being a predecessor version of the updated program and being free of the runtime defect;

(b) generating a second CFG for the updated program, the first and second CFGs each comprising a plurality of nodes defining a respective tree structure with caller routines in higher hierarchy levels than callee routines;

(c) selecting corresponding first and second paths traversing through nodes at a selected hierarchy level of the first and second CFGs, respectively;

(d) tracing the first and second paths, comprising;

(1) running the original and updated programs on a computing device comprising of a memory and registers;

(2) breaking after each traversed node; and

(3) determining register states before and after each call to the given traversed node;

(e) comparing the register states for the first and second paths, wherein a difference in the register states indicates that the runtime defect has occurred, comprising;

(1) when the original and updated programs include debug information provided by a compiler and a given register contains an address of a variable, replacing the address with a corresponding name of the variable;

(2) when the original and updated programs include a symbol table that maps variable names to addresses and the given register contains a value in the symbol table, replacing the value with the corresponding name; and

(3) when the original and updated programs do not include the debug information or the symbol table and the given register holds a data address, replacing the data address by a position-independent offset;

(f) selecting corresponding first and second paths traversing through nodes at a next selected hierarchy level of the first and second CFGs, respectively, the next selected hierarchy level being lower than any preceding selected hierarchy levels; and

(g) repeating steps (d) through (f) until the difference in the memory register states for the first and second paths occurs.

2. The method of claim 1, further comprising the step of (h) identifying the given traversed node after which the difference in the memory register states for the first and second paths first occurred.