Research On Static Analysis Of Memory Errors In C Programs

Software has an increasing importance in today's society. It has become indispensable in our daily lives and is increasingly deployed in critical systems such as online banking, air traffic control, health care and so on. The failure of software can make us inconvenie- nt and even cause incalculable loss.As an important programming language, C is intensively used in the developing of system and application softwares. Similar to some other languages, C supports explicit dynamic memory management by pointer manipulations, which increases the expressive- ness of it. However, programming with pointers is a tedious task and can cause a large number of memory errors. Such errors are also hard to detect as it is usually very difficult to reproduce them and to identify the source of them in the program.Static checking is an important technique for finding errors in programs. It finds errors by analyzing the source code and does not require running the program. Because it can offer better coverage, find bugs earlier and require few human efforts, it is often used in error finding tools. This dissertation mainly discusses how to find memory errors in C programs by means of static checking. We also have implemented the algorithms in the SUIF2 compiler infrastructure.Shape analysis is an important technique to determine the heap content of programs with pointers and dynamical allocations. It statically analyzes a program to determine information about the heap-allocated data structures that the program manipulates. The results can be used to understand or verify programs. This dissertation presents a novel method for shape analysis, which can deal with complex expressions in C language. It supports taking addresses of fields and stack variables. The concept of abstract evaluation path (AEP) is proposed. An AEP is generated from an expression in the language. AEP is used to refine the abstract shape graph (ASG) to get a set of more precise ASGs, on which the semantics of the statements can be defined easily. The results can be used to determine the"shape invariants"and detect memory leak errors.Memory leak is one of the most common errors in programs written in C. It can cause memory-intensive and long time running programs to fail. We present a demand-driven approach to detect memory leak errors based on flow- and context- sensitive pointer analysis. The detection algorithm firstly assumes the presence of a memory leak at some program point and then runs a backward analysis to see if this assumption can be disproved. Our algorithm computes the data flow facts of programs based on points-to graphs resulting from the flow- and context- sensitive pointer analysis. Null pointer dereference is also a kind of common errors. If NULL is dereferenced, the program will fail. This dissertation presents a novel algorithm to detect null pointer dereference errors. The algorithm utilizes both the must and may alias information in a compact way to improve the precision of the detection. Using may alias information obtained by a fast flow- and context- insensitive analysis algorithm, we compute the must alias information generated by the assignment statements and the must alias information is also used to improve the precision of the may alias. We can strong update more expressions using the must alias information, which will reduce the false positives of the detection of null pointer dereference.SUIF2 is a compiler infrastructure for researching and developing some compilation techniques. It supports C, C++, Fortran and Java. Programs are transferred into a represe- ntation called SUIF (Stanford University Intermediate Format). It provides a modular environment and interactive passes can be easily developed. We have implemented our algorithms in SUIF2 compiler infrastructure and the experiment results are as expected.