| System and method for static analysis using fault paths -> Monitor Keywords |
|
|
 
System and method for static analysis using fault pathsRelated Patent Categories: Data Processing: Software Development, Installation, And Management, Software Program Development Tool (e.g., Integrated Case Tool Or Stand-alone Development Tool), Testing Or Debugging, Including Analysis Of Program ExecutionSystem and method for static analysis using fault paths description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20070016894, System and method for static analysis using fault paths. Brief Patent Description - Full Patent Description - Patent Application Claims
BACKGROUND [0001] 1. Technical Field [0002] The present invention relates to evaluation of program, and more particularly to systems and methods which determine program soundness. [0003] 2. Description of the Related Art [0004] The soundness of analyses and algorithms has been a cornerstone in programming languages. A static analysis is said to be sound when the data flow information that it produces is guaranteed to be true on all program execution. Foundational theories like Meet-Over-All-Paths (MOAP) and Abstract Interpretation are the basis for sound static analysis. [0005] Unfortunately, scalability becomes an issue when implementing precise and sound static analysis. Soundness of static analysis is extremely important for many applications, including code generation and code transformation. On the other hand, there are applications of static analysis where soundness is not very critical, such as for tracking bugs and defects. One can potentially construct a very simple and fast unsound static analysis to compute data flow information. Unfortunately, unsound static analysis can produce misleading data flow information, and in the context of bug finding tools, can potentially generate many false negatives and false positives. [0006] Traditional static analysis based on foundational theories like the Meet-Over-All-Paths (MOAP), Maximal Fixed Point (MFP), and Abstract Interpretation may guarantee soundness of the static analysis. A static analysis is said to be sound when the data flow information that it produces is guaranteed to be true on all program execution. Soundness of static analysis is extremely important and critical for many applications of static analysis, such as code generation and optimization. There are applications of static analysis for which one can sacrifice soundness. For example, one can do away with soundness for finding bugs and defects. [0007] A negative consequence of loosing soundness in such applications is increased reporting of false negatives. In software diagnosis, as in medical diagnosis, there are two kinds of error that can occur. A false positive is when there is no bug, but the results of the diagnosis come back as positive. A false negative is when there is actually a bug, but the results of diagnosis come back as negative. If a static analysis is unsound, the number of false negatives and sometimes even the number of false positives can be increased. [0008] One major stumbling block in (sound) static analysis is the tradeoff between scalability and precision of the analysis. Typically, a scalable analysis is often less precise. Precision of the analysis has direct impact on the number of false positives. Precise static analysis often reduces the number of false positives. [0009] Doing away with the soundness property of static analysis has been proposed to achieve scalability. In one such method, random interpretation is used for solving certain data flow problems and the resulting solution is not necessarily sound with respect deterministic MOAP. Another technique was presented in the context of model checking in SLAM for localizing faults in error traces by exploiting existence of correct traces. Delta debugging uses a correct program and a series of changes to the program to isolate the fault that caused the error. [0010] A static analysis tool called PSE was employed to diagnose software failures. Given minimal information about a particular program failure, PSE automatically reconstructed a set of failing execution traces. PSE requires the specification of the failure in the form of type state information. An unsound pointer analysis was proposed which assumed that pointers passed into a procedure, in parameters, in global variables, and locations reachable from variables are all distinct. [0011] Unsound static analysis techniques have been used on a number of bug patterns in programs for detecting such patterns. Unsound static analysis techniques have also been employed for finding a class of error-handling mistakes that arise from an improper release of resources. [0012] Program slicing is another technique that is useful for detecting bugs and defects. A program slice is a set of all program statements that affect the value of a variable. In dynamic slicing only those statements that affect a particular test case are considered. Slicing focuses on finding statements that affect a particular value of a variable. SUMMARY [0013] The present invention is directed to address the question of how unsound is the data flow information generated by an unsound static analysis, and is it possible to distinguish between what is true from what is false using an unsound analysis. [0014] A system and method for analyzing a program includes determining possible bug paths in a program based on statistical analysis of test cases. A static analysis is then performed only on the possible bug paths. The bugs are then located in the program. [0015] Another method for analyzing a program includes determining a degree of unsoundness that can be tolerated for data flow information in a program and performing a static analysis on less than all possible paths based upon the degree of unsoundness. The data flow information is computed only on those paths that trigger a possible bug or defect, based on statistics, to find the bugs and defects in the program. [0016] In alternate embodiments, the degree of unsoundness may be checked by measuring a distance between reference data and data of the program being considered. The distance may include a hamming distance. The step of performing a static analysis on less than all possible paths may include performing a meet over possible bug paths (mobp) analysis. The step of performing a meet over possible bug paths (mobp) analysis may include determining possible bug paths based on statistics of type and location of bugs in test case programs. The test case programs may include unit tests and/or regression tests. The method may further comprise determining fault locations in the program using a fault localization algorithm. [0017] A system for determining faults in a program, includes a determination module which identifies possible bug paths in a program based on statistical analysis of test cases. A static analysis module performs a static analysis only on the possible bug paths identified by the determination module, and a fault localization module locates the bugs in the program. [0018] These and other objects, features and advantages will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings. BRIEF DESCRIPTION OF DRAWINGS [0019] The disclosure will provide details in the following description of preferred embodiments with reference to the following figures wherein: [0020] FIG. 1 depicts programming code for an illustrative program for demonstrating aspects of the present invention; [0021] FIGS. 2A-2D depict points-to graphs using different techniques for the example program of FIG. 1; Continue reading about System and method for static analysis using fault paths... Full patent description for System and method for static analysis using fault paths Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this System and method for static analysis using fault paths patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like System and method for static analysis using fault paths or other areas of interest. ### Previous Patent Application: Tracking resource usage by applications Next Patent Application: Selective omission of endian translation to enhance emulator performance Industry Class: Data processing: software development, installation, and management ### FreshPatents.com Support Thank you for viewing the System and method for static analysis using fault paths patent info. IP-related news and info Results in 0.13182 seconds Other interesting Feshpatents.com categories: Electronics: Semiconductor , Audio , Illumination , Connectors , Crypto , 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
