Program analysis may refer to:* Program analysis , the process of automatically analysing the behavior of computer programs* Program evaluation, a disciplined way of assessing the merit, value, and worth of projects and programs...
Static program analysis is the analysis of computer software that is performed without actually executing programs built from that software In most cases the analysis is performed on some version of the source code and in the other cases some form of the object code...
technique that discovers and verifies properties of linked, dynamically allocated data structures in (usually imperative
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
) computer programs. It is typically used at compile time to find software bugs or to verify high-level correctness properties of programs. In Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
programs, it can be used to ensure that a sort method correctly sorts a list. For C programs, it might look for places where a block of memory is not properly freed. Although shape analyses are very powerful, they usually take a long time to run. For this reason, they have not seen widespread acceptance outside of universities and research labs (where they are only used experimentally).
Applications
Shape analysis has been applied to a variety of problems:
A memory leak, in computer science , occurs when a computer program consumes memory but is unable to release it back to the operating system. In object-oriented programming, a memory leak happens when an object is stored in memory but cannot be accessed by the running code...
s, including Java-style leaks where a pointer to an unused object is not nulled out
Discovering cases where a block of memory is freed more than once (in C)
Dangling pointers and wild pointers in computer programming are pointers that do not point to a valid object of the appropriate type. These are special cases of memory safety violations....
s (pointers to freed memory in C)
Finding array out-of-bounds errors
Checking type-state properties (for example, ensuring that a file is open before it is read)
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
does not introduce cycles into the list
Verifying that a sort method returns a result that is in sorted order
In computer science pointer analysis, or points-to analysis, is a static code analysis technique that establishes which pointers, or heap references, can point to which variables or storage locations. It is often a component of more complex analyses such as escape analysis...
, although it is more precise than typical pointer analyses. Pointer analyses attempt to determine the set of objects to which a pointer can point (called the points-to set of the pointer). Unfortunately, these analyses are necessarily approximate (since a perfectly precise static analysis could solve the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
). Shape analyses can determine smaller (more precise) points-to sets.
Consider the following simple C++ program.
Item *items[10];
for (int i = 0; i < 10; ++i) {
items[i] = new Item(...); // line [1]
}
process_items(items); // line [2]
for (int i = 0; i < 10; ++i) {
delete items[i]; // line [3]
}
This program builds an array of objects, processes them in some arbitrary way, and then deletes them. Assuming that the process_items function is free of errors, it is clear that the program is safe: it never references freed memory, and it deletes all the objects that it has constructed.
Unfortunately, most pointer analyses have difficulty analyzing this program precisely. In order to determine points-to sets, a pointer analysis must be able to name a program's objects. In general, programs can allocate an unbounded number of objects; but in order to terminate, a pointer analysis can only use a finite set of names. A typical approximation is to give all the objects allocated on a given line of the program the same name. In the example above, all the objects constructed at line [1] would have the same name. Therefore, when the delete statement is analyzed for the first time, the analysis determines that one of the objects named [1] is being deleted. The second time the statement is analyzed (since it is in a loop) the analysis warns of a possible error: since it is unable to distinguish the objects in the array, it may be that the second delete is deleting the same object as the first delete. This warning is spurious, and the goal of shape analysis is to avoid such warnings.
Summarization and materialization
Shape analysis overcomes the problems of pointer analysis by using a more flexible naming system for objects. Rather than giving an object the same name throughout a program, objects can change names depending on the program's actions. Sometimes, several distinct objects with different names may be summarized, or merged, so that they have the same name. Then, when a summarized object is about to be used by the program, it can be materialized--that is, the summarized object is split into two objects with distinct names, one representing a single object and the other representing the remaining summarized objects. The basic heuristic of shape analysis is that objects that are being used by the program are represented using unique materialized objects, while objects not in use are summarized.
The array of objects in the example above is summarized in separate ways at lines [1], [2], and [3]. At line [1], the array has been only partly constructed. The array elements 0..i-1 contain constructed objects. The array element i is about to be constructed, and the following elements are uninitialized. A shape analysis can approximate this situation using a summary for the first set of elements, a materialized memory location for element i, and a summary for the remaining uninitialized locations, as follows:
0 .. i-1
i
i+1 .. 9
pointer to constructed object (summary)
uninitialized
uninitialized (summary)
After the loop terminates, at line [2], there is no need to keep anything materialized. The shape analysis determines at this point that all the array elements have been initialized:
0 .. 9
pointer to constructed object (summary)
At line [3], however, the array element i is in use again. Therefore, the analysis splits the array into three segments as in line [1]. This time, though, the first segment before i has been deleted, and the remaining elements are still valid (assuming the delete statement hasn't executed yet).
0 .. i-1
i
i+1 .. 9
free (summary)
pointer to constructed object
pointer to constructed object (summary)
Notice that in this case, the analysis recognizes that the pointer at index i has not been deleted yet. Therefore, it doesn't warn of a double deletion.
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
