Memory Safety analysis with CheckPointer™
Semantic Designs provides CheckPointer, a family of tools for diagnosing memory access errors in languages (such as C) that have explicit pointers, memory allocation and deallocation primitives. This page discusses why memory access errors are often difficult to locate, and tools that can detect them effectively.
Memory Access Errors
Programs with pointers can commit a variety of errors in accessing memory:
- Illegal access: Dereference (read/write/call thru) a bad pointer. The pointer may be null, uninitialized, or be computed incorrectly from an arbitrary source.
- Deallocation error: Perform an erroneous free operation. Here the pointer may be bad, the storage already freed ("double free"), or may point to a global variable, into the middle of any variable (heap allocated or not), or into a stack frame, or the length being deallocated is incorrect.
- Buffer Overrun: Perform an array access beyond the legal bounds of an array or string. A index value is used that is outside the current bounds of storage allocated to the array. This occurs if the array subscript is advanced past the actual end of the array. This is particularly insidious with languages such as C where dynamic arrays are constructed by extending a fixed array at the end of a heap-allocated struct.
- Temporal error: Access via pointer to an (invalid) memory block that was formerly valid. This happens if the storage referenced by a pointer has been freed, including accesses to freed heap storage or to local variables that have gone out of scope (e.g., when a function returns). An especially nasty case occurs when that freed storage has been recycled, either reallocated for another purpose, or for many implementations of local variables, reuse of the underlying stack space for other locals.
Memory access errors sometimes cause immediate, determininistic program failure; in this case standard debugging methods can locate the point of the error quickly. However, in many cases the program does not fail deterministically (due to access to storage containing essentially random values) or catastrophically but instead continues down some unexpected execution path, resulting in a variety of random bizarre results, or worse, a long delayed random bizarre result. As an example, stores to freed blocks often produce no immediate symptom, but may damage arbitrary memory and thus produce strange failures at places arbitrarily far from the point of error. Tracking down the point of the error is usually difficult because the symptoms are not only surprising, but they occur far from the point of error; there is no obvious connection from the symptom to the code causing the error. These errors can be among the most frustrating errors to find in a complex application.
An additional class of error is failure to release storage. This may cause a program to eventually run out of space, even though enough space was actually available. This can affect program "correctness" for larger inputs or more complex calculations.
Detecting Memory Access Errors
As a practical matter, programmers write code that contains access errors and such errors are hard to find by manual inspection. Tools are needed.
Static Analysis: good when it is right
Ideally, static analysis tools would inspect your code and diagnose the precise location of all errors, including memory safety errors. Such tools can diagnose many kinds of errors well, and that makes them useful tools and are thus widely recommended.
When a static analyzer can demonstrate that all paths through a program leading to a memory access must produce an access error, it can identify that case and the benefit to the programmer is immediate. She can start considering how to solve a real problem. (Compilers diagnosing access to unitialized variables are special case of this).
However, as practical matter, static analysis simply cannot always do this analysis reliably, because the static analyzer can only reason to a limited extent about the conditions in code. In this C code:
char prev*=0;
while (...)
{ if (Turing(...,prev))
{ prev=exp;
}
...
... *prev ... // indirect access
...
}
a static analyzer cannot, in theory, know if the indirect access to prev will be erroneous or not, because it must reason about a Turing machine. What most static analyzers do in this case is indicate the the access may be problematic. If the programmer inspects the code and decides the analyzer is wrong, a false positive diagnosis has been made and the programmer's time wasted, and she will remember her time was wasted. In a large program, a static analyzer can produce many such may complaints; a programmer will ignore the analyzer's result if the number of false positives exceeds her (typically small) tolerance, negating the value of the tool.
Dynamic Analysis: works where Static Analysis does not
The only way to avoid producing false positives, is to never emit a complaint about a may case, but this would leave the programmer with a problem if her code contains a tricky memory safety error such as the example above. The only remaining alternative is check the program at runtime, at each memory access, to verify that memory access is not erroneous, and raise an immediate error if it is. If no memory error occurs, the program runs normally (modulo the extra time to check for safety). If a memory safety error occurs, the check notices and halts the program immediately with a diagnostic including the location of the error. This converts a potentially difficult debugging problem with delayed bizarre symptoms back into the deterministic, easy case and so the programmer can focus on fixing the problem rather than trying to discover where it occurs.
The CheckPointer dynamic analysis tool instruments the original application code with runtime checks of the validity of each pointer access (including arrays in languages such as C), producing an instrumented version. The instrumented version is compiled an executed normally and exercised to the maximum extent possible (unit testing is a good way to do this). During execution, every pointer access is checked, and if invalid, the program is stopped and the access location and failure is noted. By definition, this is the first place the access could have been detected. The instrumented program is discarded after testing is completed.
A key problem is having information at runtime that enables the pointer access to be checked; this information is called (pointer) metadata. Such metadata contains information such as, "this pointer is (not) valid" or "points into a allocated block at X of size Y". What the tool must do is is modify the code to:
- associate accurate metadata with each pointer. This means the instrumented code must track the initial metadata status of each pointer, and for every pointer update (assignment, new, free, ...), cause the capture of new, correct metadata state for that pointer. If a pointer is copied (assignment, passed as a parameter), the metadata must travel along with it.
- look up the corresponding metadata for each pointer access, and check for validity
- do both of the above fast, to keep checking overhead acceptably low
The basic implementation is not hard. The following code shows conceptually how the above program is instrumented using metadata{x} to represent the code for accessing metadata associated with x:
metadata{prev}=uninitialized;
char prev*=0;
metadata{prev}=null;
while (...)
{ if (Turing(...,prev,metadata{prev}))
{ prev=exp;
metadata{prev}=metadata{exp};
}
...
if (metadata{prev}!=valid) abort();
... *prev ... // indirect access
...
}
What is hard is catching all the cases where pointer accesses occur (e.g., printf("abc%sdef",charptr)), propagating all the meta data correctly (notice the change to Turing's signature, and the implied change to Turing's content), as well as optimizing the result to keep overhead low. Various optimizations are applied to minimize the amount of metadata update/checking needed. For instance, metadata{prev}=uninitialized; isn't needed, as the value of that updated metadata is never inspected. The location of the metadata must also be carefully chosen to maximize performance; e.g., metadata for local pointer variables should also be kept as local variables.
You can see an example of buggy C code and its execution with and without CheckPointer.
Because erroneous values for pointers may come from arbitrary places in the software, the analysis process must generally provide some means to check the standard compiler libraries used by the application, and a way to check libraries provided as part of the application.
Ideally, one would use static analysis to detect must memory access errors, and dynamic analysis to detect may errors when they occur. However, in the absence of a static analysis tool, a dynamic analysis tool will still diagnose the statically detectable errors; if a block of code containing a statically-detectable error is executed, then that error will be reported by dynamic checking. Good test coverage helps ensure that such errors are spotted.
Other Dynamic Memory error detection tools
It should be clear that using a traditional debugger to find this kind of error is very hard. Valgrind is a popular Linux tool that can detect some of these errors; what it cannot detect are array access errors, errors in which a freed block becomes reallocated for another use and a stale pointer is used, or errors with pointers into stack frames. Purify is another popular tool, but it cannot detect any errors in accesses to local variables, accesses outside of an array in a structure, accesses outside the guard band around dynamically allocated objects, or improper access to a reallocated block. CheckPointer can detect all of these.
CheckPointer
Semantic Designs provides a family of (memory) safety checking tools. These tools detect various kinds of memory access faults, including buffer overruns, array access errors, and bad pointer dereferences.
Typical Features
- Instruments application code to detect memory safety errors
- Provides list of unfreed storage at end of execution
- Metadata access optimized to minimize execution time overhead
- Some static analysis to diagnose certain failures directly, or to eliminate provably unnecessary dynamic checks
- Custom language runtime library containing dynamic checks
- Available for most dialects of the language of interest
- Not dependent on any particular compiler or object formats
- Works with tens of thousands of files
- Consistent style and operation across different languages
- Probe installer operates on Windows 2003/XP/Vista/7/8/10/Linux
- Application may run on any platform, including custom embedded systems
Here you can read about a comparison of the CheckPointer with similar memory safety checking tools.
Available for the following languages
Unusual Requirements?
Your language not listed, runs in an unusual environment, or you have some custom need? SD can configure a memory safety tool for you! These tools are based on DMS, and inherit DMS's language agility and scalability.
Semantic Designs also provides a variety of other tools.
