| With the development of software industry, at a time of increasing demands on software quality, cost and schedule, software test is becoming an important part of the software development process. Due to the software static test does not need to execute the program, and also has high coverage, it becomes the primary means of building trusted software. Static test could not be both sound and complete, which might lead to false positives and false negatives. The accuracy of static analysis is a key factor to reduce false positives and false negatives software in static test. Howerver, the accurate analysis will reduce the efficiency. Therefore, how to improve the static analysis precision in the premise of guaranteeing the efficiency has become the critical factor affecting the capability of static analysis techniques, which is also the hot research topic both in domestic and overseas.Funded by the National High-Tech Research and Development Plan of China under Grant "2009AA012404,2012AA011201", and the National Science Foundation of China under Grant "91018002,2010", aiming at improving the static testing precision in the premise of efficiency, three aspects of work are included:(1)Trigram data type abstract modeling based on related memoryStatic analysis cannot obtain variable values in actual operation, because it does not execute source code. It is difficult to detect defect which is related with variable values. In order to get the value range of operands and parameters, we need to tranverse the control flow gragh. According to the information stored in every control flow node in abstract syntax tree, tracking and analyzing every variable to simulate dynamic execution results by interval arithmetic.The binary static analysis model<varible-value> cannot satisfy the demands of point-to and alias analysis. Therefore, the static analysis based on the binary model affects the test accuracy. Based on the theory of symbolic analysis, we propose a new model which has a description of memory. The binary model is extended to trigram model<variable-memory-value>. If we describe all allocated memorys, it will occupy a lot of memory. Considering the features of analysis object in point-to and alias analysis, both binary model and trigram model can be applied in data flow calculation. Only when processing the pointer model, the trigram model will be applied.The main contributions of this part can be summarized as follows.1) Presenting a new trigram data type abstract model which considers memory as symbol to analyze data flow information.2) Presenting a description of abstract syntax which is referred to the statement associated with point-to analysis. According to different abstract syntax, we propose a point-to analysis algorithm.3) Proposing the dataflow calculation algorithm of trigram model, and analyze the complexity of the algorithm.4)Describing the definition of procedure summary. And then, realizing context-sensitive point-to analysis by it.(2) Alias analysis with interval arithmeticIf two or more variables point to a common storage unit or a storage area at the same time (ie. memory addresses of them are the same), we can call them alias for each other. Interval arithmetic in dataflow calculation can describe possible value range of variable or expression. However, it does not consider alias analysis, leading to the dataflow calculation is not accurate.Memory is a kind of calculation object in alias analysis. Therefore the binary static analysis model cannot satisfy the demands of alias analysis. Based on the trigram model proposed in part one, we use a symbol with an interval domain to describe offset in memory block.According to different statement information, we associate every variable with an alias set in which the variables are alias with each other. When updating some variable in the alias set, we update the value of each variable which is alias with it to improve the test accuracy.The main contributions of this part can be summarized as follows.1) Presenting two alias model:value-related model and memory-related model. The algorithm improves both accuracy and efficiency by choosing different model to detect different defects.2) Value-related alias analysis not only can calculate direct alias, but also indirect alias by calculating the offset related with memory model.3) Realizing field-sensitive alias analysis by father region theory.(3) The application of interval arithmetic in software testing based on field-sensitive point-to analysisField-sensitive analysis treats every member variable declared in complex data type as different analysis object. In the domain of software static test, symbolic execution and interval arithmetic are not field-sensitive, because they cannot define an abstract model for member variable. Considering the software static test based on defect mode, defects are usually generated in basic data type. For example, null pointer dereference, memory leak, invalid arithmetic operation, etc. Therefore, independent analysis for every member variable has no effect on testing accuracy, and it guarantees efficiency by ignoring the relevant information of complex data type.Based on the point-to analysis model of steensgaard, we improve it by realzing field-sensitive analysis.The main contributions of this part can be summarized as follows.1) Presenting a new field-sensitive point-to analysis model, which divides complex data type into independent member variable. It not only satisfies the accuracy of defect-oriented test, but also avoids updating and combining dataflow.2) Associating all variables with a trigram abstract set, which describes the procedure runtime execution information and feature condition of finite state machine conservatively.3) Proposing a type derivation algorithm and dataflow combine strategy.4) Designing and implementing a field-sensitive defetct detecting tool which can test both CPP and GCC. Improving the test accuracy in the premise of guaranteeing efficiency. |
PDF Full Text Request