Optimization Techniques For Interprocedual Abstract Interpretation Analysis

Numerical properties are an important class of properties that arise with the numerical(integer,floating-point)variables and the corresponding numerical operations in programs.Numerical properties focus on the numerical relationships between numerical variables and can be used to find and locate numerical defects in programs such as division by zero,integer overflows,floating point overflows,and array overruns.Abstraction interpretation is the underlying theory of static program analysis,which provides a reliable abstraction of program semantics and an analytical framework for automatically deriving the numerical properties of programs.In real-world program analysis,the analysis of function calls is essential,and interprocedural analysis is often used to achieve cross-process information transfer analysis.Function inlining is an easy to implement and semantically complete interprocess analysis method.However,its code substitution is likely to generate a large number of intermediate variables,resulting in an increase in the dimensionality of program variables,which greatly increases the time and space of the analysis process.The function inlining approach also suffers from the inability to analyze recursive function.In this paper,we consider the shortcomings of the interprocess analysis method using function inlining in the abstract interpretation framework and propose the corresponding optimization methods.In the abstract interpretation framework,the size of the program environment(the set of variables at each program point)has a significant impact on the time and space overhead of program analysis.In order to reduce the analysis overhead,this paper proposes and implements a dimensionality reduction optimization method for inline function blocks.The method analyzes the program code after inlining functions and determines the program environment to be maintained at different program points,instead of sharing the same global program environment at all program points.This method is used to reduce the dimensionality of the program environment by eliminating variables under the premise of semantic equivalence.Context insensitivity is one of the ways to achieve recursive function call analysis.In this paper,we optimize the existing context-insensitive interprocedural analysis methods to meet the needs of C program analysis.The corresponding optimization strategies include using type conversions for complex data types such as pointers,arrays,structures,constructing in-function environments and global variable program environments to reduce the loss of analysis efficiency and accuracy,and propose a selectable context-sensitivity interprocedural analysis and make a compromise between analysis accuracy and efficiency.In this paper,we implement a static program analysis tool DRIP based on the abstract interpretation theory framework,and use DRIP to verify on WCET Benchmarks.The experimental results show that the program environment reduction optimization method can effectively perform variable elimination,thus reducing the time and space consumption of the analysis process.Meanwhile,this paper implements a tool DRIP++ based on DRIP and chooses the same test set for validation.The experimental results show that the context-insensitive interprocedural analysis optimization method can effectively analyze recursively called programs with high analysis efficiency,and its analysis accuracy is consistent with the function inlining method when the function is called only once.