Today, some software programs contain one million lines of code (LOC) or more. In order to ensure the reliability of these software programs, the software programs undergo testing before releasing the software programs to consumers. Typically, the testing includes a value flow analysis. Value flow analysis analyzes the software program to determine which memory locations hold a given value at a given program point along a given execution path within the program. The analysis then identifies code that incorrectly uses a value. For example, the analysis may check whether a function call has acquired a lock that was created by a preceding function call, whether a value is valid for a given function call, and the like. Because values created in one portion of the code may be passed to numerous other portions of the code, value flow analysis tracks each execution path for every value.
The current approaches for value flow analysis make a trade-off between precision and scalability. If the value flow analysis is precise, the analysis maintains information about all the values for each execution path. When the software program is very large, this precise value flow analysis can not compute the necessary information in a timely manner. Thus, precise value flow analysis does not scale well to large software programs. In contrast, imprecise value flow analysis does scale well to large software programs. However, imprecise value flow analysis does not keep accurate information. Rather, at certain locations within the program, the information is merged. Because, the imprecise value flow analysis merges some of the information, the results identify some portions of the code as having errors, when in fact those portions do not have errors. This reporting of incorrect errors is commonly referred to as noise. If the imprecise value flow analysis has too much noise, the analysis is not useful. Thus, full-scale reliable value flow analysis of a software program having a large code base has been unattainable.
USPTO Backgrounds
USPTO Backgrounds