Generative Testing Methods For Compiler Components

As an important system software,compilers are one of the core infrastructures for building other software.A typical compiler can be divided into three components: front-end,middleend,and back-end,which respectively achieves the functions of high-level language processing,code optimization,and target code generation.However,as a type of system software,compilers also contain defects.These defects not only reduce the reliability of compilers,but also bring certain risks and even disasters to software which use the compiler.Therefore,it is crucial to guarantee the quality of compilers.Compiler testing is one of the important ways to guarantee the quality of compilers,which detects compiler defects by generating complex test programs.In recent years,although many test program generation techniques have been proposed in the area of compiler testing,these techniques still cannot generate componentspecific and diverse test programs well.It is an important issue to generate test programs that trigger compiler defects in the area of compiler testing.Therefore,for different components of the compiler,this thesis attempts to study generative testing methods from the perspective of test program generation,so as to better guarantee the quality of compilers.The research work of this thesis mainly includes three aspects,namely the warning testing of compilers’ front-ends,the error recovery testing of compilers’ front-ends,and the correctness testing of compilers’ middle-back-ends.First,in order to efficiently discover warning defects,this thesis proposes a diversity-guided warning testing method for compilers’ front-ends.Secondly,in order to ensure the correctness of the error recovery mechanism in compilers’ front-ends,this thesis proposes a genetic algorithm based error recovery testing method.Finally,in order to ensure the correctness of compiler optimization and translation,this thesis proposes a deep-learning based correctness testing method for compilers’ middle-back-ends.Specifically,the main research contents of this thesis are as follows:(1)A diversity-guided warning testing method for compilers’ front-ends.By analyzing the characteristics of the compiler warning mechanism,this thesis addresses two challenges in warning testing: warning-sensitive structure construction and diverse test program generation.To address these two challenges,63 mutators are firstly designed to mutate the abstract syntax tree of the seed programs,thereby constructing warning-sensitive structures;and then the Markov Monte Carlo method is used to guide the selection of each mutator,so as to generate a variety of test programs.The experimental results on GCC and LLVM show that,compared with the existing advanced methods,this method can effectively improve the detection efficiency of warning defects by 18.93% ～ 76.74%,and detect 8 real warning defects in the front-ends of the development versions of compilers in practice.(2)A genetic algorithm based error recovery testing method for compilers’ front-ends.In order to discover error recovery defects in compilers’ front-end,this method mainly addresses two challenges: diverse test program generation and error recovery defect detection.In order to solve the first challenge,129 mutators are designed to mutate syntax valid seed programs,and then the genetic algorithm is used to combine different mutators to generate diverse test programs.In order to tackle the second challenge,this thesis proposes an alignment algorithm for error recovery diagnostics based on differential testing.The experimental results on GCC and LLVM show that,compared with the existing methods,the method can effectively improve the detection efficiency of compiler error recovery defects by 19.08% ～ 43.08%,and detect 9real error recovery defects in the front-ends of the development versions of compilers in practice.(3)A deep-learning based correctness testing method for compilers’ middle-back-ends.To improve the efficiency of compilers’ middle-back-end testing,this thesis addresses two challenges: syntactically valid and diverse test program generation.Firstly,in order to construct syntactically valid test programs,this thesis proposes a test program generation method based on the Transformer-XL neural network.Secondly,in order to construct diverse test programs,the thesis proposes a historical probability based sampling strategy,thereby ensuring the diversity of test programs.Experiments on GCC and LLVM show that,compared with the existing advanced methods,this method can significantly improve the efficiency of the compilers’ middle-back-end testing by 35.29% ～ 187.50%,and detect 22 real defects in the middle-back-ends of the development versions of compilers in practice.This thesis proposes three effective defect detection methods for different components(including front-end and middle-back-end)of compilers,and has achieved better results in practice,which helps developers better discover compiler defects,and further improves the reliability of compilers.