Testing Tips for Today
Shape analysis (software)
Shape analysis is a static code analysis technique that discovers and verifies properties of linked, dynamically allocated data structures in (usually imperative) computer programs. It is typically used at compile time to find software bugs or to verify high-level correctness properties of programs.
In Java 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).
Shape analysis has been applied to a variety of problems:
- Finding memory leaks, 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)
- Finding dereferences of “dangling pointers” (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())
- Ensuring that a method to reverse a linked list does not introduce cycles into the list
- Verifying that a sort method returns a result that is in sorted order