Effective Lifetime Dependency Analysis and Typestate Analysis

Abstract

Disclosed are typestate and lifetime dependency analysis methods for identifying bugs in C++ programs. Disclosed are an abstract representation (ARC++) that models C++ objects and which makes object creation/destruction, usage, lifetime and pointer operations explicit in the abstract model thereby providing a basis for static analysis on the C++ program. Also disclosed is a lifetime dependency analysis that tracks implied dependency relationships between lifetimes of objects, to capture an effective high-level abstraction for issues involving temporary objects and internal buffers, and subsequently used in the static analysis that supports typestate checking for the C++ program. Finally disclosed a framework that automatically genarates ARC++ representations from C++ programs and performs typestate checking to detect bugs that are specified as typestate automata over ARC++ representations.

1 . A method of software program analysis comprising the steps of:
 by a computer:
 automatically generating an abstract representation (ARC++) of a C++ program that captures lifetimes of objects in the program; 
 performing a lifetime dependency analysis that tracks dependency relationships between lifetimes of different objects to discover bugs; 
 outputting an indicia of those bugs. 
   
     
     
         2 . The method of  claim 1  wherein said ARC++ representation models C++ objects along with any new containers and/or pointers introduced by standard libraries utilized by the C++ program. 
     
     
         3 . The method of  claim 2  wherein said ARC++ representation makes object creation/destruction, usage, lifetime, and pointer operations explicit in the abstract model thereby providing a basis for static analysis of the C++ program. 
     
     
         4 . The method of  claim 1  further comprising the step of utilizing a lifetime dependency graph that captures a lifetime relationship between objects such that stale objects are discovered. 
     
     
         5 . The method of  claim 1  further comprising performing a typestate analysis such that bug patterns are specified as typestate automata over the ARC++ representation. 
     
     
         6 . The method of  claim 1  further comprising use of access path clusters in an abstract interpretation framework to capture aliasing between objects in the program. 
     
     
         7 . The method of  claim 1  wherein lifetime dependencies are tracked for temporary objects. 
     
     
         8 . The method of  claim 1  wherein lifetime dependencies are tracked for internal buffers. 
     
     
         9 . A system for performing computer software program analysis, said system comprising a computing device including a processor and a memory coupled to said processor said memory having stored thereon computer executable instructions that upon execution by the processor cause the system to:
 automatically generate an abstract representation (ARC++) of a C++ program that captures lifetimes of objects in the program;   perform a lifetime dependency analysis that tracks dependency relationships between lifetimes of different objects to discover bugs; and   output an indicia of those bugs   
     
     
         10 . The system of  claim 9  wherein said ARC++ representation models C++ objects along with any new containers and/or pointers introduced by standard libraries utilized by the C++ program. 
     
     
         11 . The system of  claim 10  wherein said ARC++ representation makes object creation/destruction, usage, lifetime, and pointer operations explicit in the abstract model thereby providing a basis for static analysis of the C++ program. 
     
     
         12 . The system of  claim 9  wherein said computer executable instructions that upon execution by the processor cause the system to utilize a lifetime dependency graph that captures a lifetime relationship between objects such that stale objects are discovered. 
     
     
         13 . The system of  claim 9  wherein said computer executable instructions that upon execution by the processor cause the system to perform a typestate analysis such that bug patterns are specified as typestate automata over the ARC++ representation. 
     
     
         14 . The system of  claim 9  wherein said computer executable instructions that upon execution by the processor cause the system to use access path clusters in an abstract interpretation framework to capture aliasing between objects in the program. 
     
     
         15 . The system of  claim 9  wherein said computer executable instructions that upon execution by the processor cause the system to track lifetime dependencies for temporary objects. 
     
     
         16 . The system of  claim 9  wherein said computer executable instructions that upon execution by the processor cause the system to track lifetime dependencies for internal buffers. 
     
     
         17 . A system for performing computer software program anaylsis, said system comprising a computing device including a processor and a memory coupled to said processor said memory having stored thereon computer executable instructions that upon execution by the processor cause the system to:
 receive as input a C++ program;   simplifies any complex C++ expressions contained in the C++ program into simpler ones;   clarifies any implicit calls contained in the C++ program into explicit ones;   generate an internal representation of the C++ program (CILPP);   perform an exception analysis of the CILPP and create an interprocedural exception control flow graph (IECFG);   perform an CILPP abstraction such that an abstract representation of the C++ program (ARC++) is generated;   perform an analysis using the IECFG, ARC++, CILPP along with one or more bug patterns such that bugs in the C++program are identified; and   output an indicia of the identified bugs.