During the rapid development of mobile computing, IoT, cloud computing, artificial intelligence, etc., many new programming languages and compilers are emerging. Nevertheless, C/C++ is still one of the most popular languages, and the array is one of the most important data structures of C language. It is necessary to check whether the index is within the boundary of the array when it is used to access the element of an array in a program. Otherwise, array index out-of-bounds will happen unexpectedly. When array index out-of-bounds defects are in programs, some serious errors may occur during execution, such as system crash. It is even worse that array index out-of-bounds defects open the doors for attackers to take control of the server and execute arbitrary malicious codes by carefully constructing input and intercepting the control flow of the programs. Existing static methods for array boundary checking cannot achieve high accuracy and deal with complex constraints and expressions, leading to massive false positives. In addition, it will increase the burden of developers. In this study, a static checking method is proposed based on taint analysis. First, a flow-sensitive, context-sensitive, and on-demand pointer analysis is proposed to analyze the range of array length. Then, an on-demand taint analysis is performed for all array indices and array length expressions. Finally, the rules are defined for checking array index out-of-bounds defects and the checking is realized based on backward data flow analysis. During the analysis, in light of complex constraints and expressions, it is proposed to check the satisfiability of the conditions by invoking the constraint solver. If none statement for avoiding array index out-of-bounds is found in the program, an array index out-of-bound warning will be reported. An automatic static analysis tool, Carraybound, has been implemented, and the experimental results show that Carraybound can work effectively and efficiently.
Fengjuan Gao, Yu Wang, Tianjiao Chen, Lingyun Situ, Linzhang Wang, Xuandong Li. Static Checking of Array Index Out-of-Bounds Defects in C Programs Based on Taint Analysis. International Journal of Software and Informatics, 2021,11(2):121~147Copy