Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
2006-08-08
2006-08-08
Das, Chameli C. (Department: 2192)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C717S126000, C717S127000, C717S131000
Reexamination Certificate
active
07089537
ABSTRACT:
Described is a method and system for performing path-sensitive value flow analysis on a software program. Concrete state and value alias information is tracked along each statement and each relevant path in an abstract program and is stored as a symbolic state in a symbolic store. The value alias information includes a first set of aliases that identify aliases for a designated value that is being analyzed and a second set of aliases that identify possible aliases for the designated value. The value alias information is obtained using imprecise memory alias analysis. Along each relevant path for each statement, transforms are applied to the sets of aliases to update the first and second sets of aliases. The transforms are applied based on the type of statement being processed. Symbolic states existing at the same location are merged if the value alias information is identical within the symbolic states.
REFERENCES:
patent: 5119290 (1992-06-01), Loo et al.
patent: 5222244 (1993-06-01), Carbine et al.
patent: 6128775 (2000-10-01), Chow et al.
patent: 6202202 (2001-03-01), Steensgaard
patent: 6317134 (2001-11-01), Hagemark et al.
patent: 6327699 (2001-12-01), Larus et al.
patent: 6457023 (2002-09-01), Pinter et al.
patent: 6813761 (2004-11-01), Das et al.
patent: 6970985 (2005-11-01), Moritz
patent: 6986126 (2006-01-01), Kosche et al.
TITLE: An incremental Flow- and Context-sensitive Pointer Aliasing Analysis, author: Yur et al, ACM, 1999.
TITLE: Flow-Sensitive Type Qualifiers, author: Foster et al, ACM, 2002.
Aiken, et al., “Checking and Inferring Local Non-Aliasing”, Proceedings of the ACM SIGPLAN, Conference on Programming Language Design and Implementation, pp. 129-140, 2003.
Bodik, et al., “Path-Sensitive Value-Flow Analysis”, Conference Record of the Twenty-Fifth ACM Symposium on Principles of Programming Languages, pp. 237-251, 1998.
Bozga, et al., “Storeless Semantics and Alias Logic”, Proceedings of the 2003 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pp. 55-65, Jun. 2003.
Bush, et al., “A Static Analyzer for Finding Dynamic Programming Errors”, Software- Practice and Experience, vol. 30, No. 7, pp. 775-802, 2000.
Ball et al., “Automatically Validating Temporal Safety Properties of Interfaces”, Proceedings of SPIN '01, 8th Annual SPIN Workshop on Model Checking of Software, May 2001.
Chatterjee, et al., “Relevant Context Interface”, Conference Record of the Twenty-Sixth ACM Symposium on Principles of Programming Languages, pp. 133-146, 1999.
Manuvir Das, “Unification-Based Pointer Analysis with Directional Assignments”, Proceedings of the ACM SIGPLAN 2000, Conference in Programming Languages Design and Implementation, 2000.
Deline, et al., “Enforcing High-Level Protocols in Low-Level Software”, Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, 2001.
Das, et al., “Estimating the IMpact of Scalable Pointer Analysis on Optimization”, 8th International Symposium on Static Analysis, 2001.
Das, et al., “Esp: Path-Sensitive Porgram Verification in Polynomial Time”, Proceedings of the ACM SIGPLAN 2002 Conference on Programming Langue Design and Implementation, 2002.
Flanagan, et al, “Extended Static Checking for Java”, Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 2002.
Foster, et al., “Flow-Sensitive Type Qualifiers”, Proceedings of teh ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 2002.
Hallem, et al., “A System and Language for Building System-Specific, Statis Analysis”, Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 2002.
Michael Hind, “Pointer Analysis: Haven't We Solved This Problem Yet?”, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools and Engineering (PASTE '01), pp. 54-61, 2001.
Hind et al., “Evaluating the Effectiveness of Pointer Alias Analyses”, Science of Computer Programming, vol. 39, No. 1, pp. 31-55, Jan. 2001.
Horwitz, et al., “Interprocedural Slicing Using Depedence Graphs”, ACM Trans. Program, Lang. Syst., vol. 12, No. 1, pp. 26-60, Jan. 1990.
Heintze, et al., “Ultra-Fast Aliasing Analysis Using CLA” A Million Lines of C Code in a Second, Proceedings of the 2001 ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 254-263, 2001.
Jones, et al., “Flow Analysis and Optimization of LISP-Like Structures”, Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, pp. 244-256, 1979.
Khedkar, et al., “A Generallsed Theory of Bit Vector Data Flow Analysis”, ACM Trans. Program. Lang. Syst., vol. 16, No. 5, pp. 1472-1511, 1994.
Knoop, et al., “Efficient and Optimal Bit-Vector Dataflow Analysis: A Uniform Interprocedural Framework”, Technical Report Bericht Nr. 9309, Instut Fur Informatik und Praktische Mathematik, Christian-Albrechts-Universitat Kiel, Germany, 1993.
Liang, et al., “Reuse-Driven Interprocedural Slicing in the Presence of Pointers and Recursion”, International Conference on Software Maintenance, 1999.
Landi, et al., “Interprocedural Modification Side Effect Analysis with Pointer Aliasing”, Proceedings of the 1993 ACM SIGPLAN Conference on Programming Language Designa nd Implementation, pp. 56-67, 1993.
Milanova, et al., “Precise and Efficient Call Graph Construction for C Programs with Function Pointers”, Journal of Automated Software Engineering, pp. 12, 2004.
Nelson, et al., “Simplification by Cooperating Decision Procedures”, TOPLAS: ACM Transactions on Programming Language and Systems, vol. 1, No. 2, pp. 245-257, 1979.
Pande, et al., “Interprocedural Def-Use Asosciations for C Systems with Single Level Pointers”, IEEE Transactions on Software Engineering, vol. 20, No. 5, pp. 385-403, 1994.
Reps, et al., “Precise Interprocedural Data Flow Analysis via Graph Reachability”, Conference Record on the Twenty-Second ACM Symposium on Principles of Programming Languages, 1995.
Shapiro, et al., “The Effects of the Precision of Pointer Analysis”, LNCS 1302, 4th International Symposium on Static Analysis, Sep. 1997.
Olin Shivers, “Control-Flow Analysis of Higher-Order Languages”, PhD Thesis, Camegie Mellon University, May 1991.
Sagiv, et al., “Parametric Shape Analysis via 3-Valued Logic”, Conference Record of the Twenty-Sixth ACM Symposium on Principles of Programming Languages, 1999.
Bjarne Steensgaard, “Points-to Analysis in Almost Linear Time”, Conference Record of the Twenty-Third ACM Symposium on Principles of Programming Languages, 1996.
Wilson, et al., “Efficient Context-Sensitive Pointer Analysis for C Programs”, Proceedings of the ACM SIGPLAN 95 Conference on Programming Language Design and Implementation, 1995.
Adams Stephen R.
Das Manuvir
Dor Nurit
Das Chameli C.
Lee & Hayes PLLC
Microsoft Corporation
LandOfFree
System and method for performing path-sensitive value flow... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing path-sensitive value flow..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing path-sensitive value flow... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3630479