Study On Pointer Analysis Technology In Static Buffer Overflow Analysis

Pointer analysis aims at approximately identifying the definite or possible targets pointed by pointer variable through static analyzing the program. It is of great importance and a challenging problem in static analysis, which is widely used in program analysis, optimization and validation.The C language allows indirect access memory location by pointer without boundary check, which may cause buffer overflow. Buffer overflow bugs is one of most serious security vulnerability, so detecting buffer overflow bugs in program is a hot topic in information security field now. Static analysis can be used to dectect these bugs before software distribution without degrading the runtime efficiency of software. In order to statically analyze buffer overflow, efficient and precise pointer analysis must be performed to make certain what target buffer a pointer variable point to.Many pointer analysis algorithms have been developed, but the current state-of-the-art pointer analysis algorithms are either too imprecise or too complex to be used for static buffer overflow detection. In this paper, we proposed a flow-insensitive and context-sensitive pointer analysis algorithm formulated as a two-phase computation. The bottom-up phase transforms a program into a form that lacks procedural point-to side effects by traverse call graph in reverse invocation order. The top-down phase computes the actual point-to information using CGBCI (Constraint-Graph-Based Context-Insensitive) pointer analysis algorithm. The advantage of this algorithm is that its accuracy is equivalent to an analysis which completely inlines all procedure calls.Each procedure can be analyzed at most twice, so it won't cause exponential complication.We implement the proposed pointer analysis algorithm prototype in LLVM compiler system, and applying the algorithm in a static buffer overflow analysis tool. The experiment results show that our context-sensitive pointer analysis algorithm can improve the accuracy of static buffer overflow analysis and have higher efficiency.