基于機器學習約束求解的復(fù)雜軟件代碼符號執(zhí)行框架研究
發(fā)布時間：2019-07-02 12:00
【摘要】：如何生成高質(zhì)量的測試用例一直是軟件測試領(lǐng)域的重要研究課題。不同于其他測試用例生成技術(shù),基于符號執(zhí)行的測試用例自動生成技術(shù)在程序執(zhí)行的過程中使用符號化的變量代替具體值的變量,同時維護整個執(zhí)行過程中的路徑約束,當遇到分支語句的時候即調(diào)用底層的約束求解器求解該路徑約束以生成觸發(fā)該分支路徑的測試用例。該技術(shù)經(jīng)過多年發(fā)展已經(jīng)被應(yīng)用到了諸多測試工具,比如jCUTE,KLEE和SPF等。當前基于符號執(zhí)行的測試用例生成技術(shù)在應(yīng)用到真實程序時仍然面臨著不少的挑戰(zhàn)。其中一個最主要的挑戰(zhàn)就是底層約束求解器無法對真實程序中的復(fù)雜路徑約束提供有效支持。造成這個問題主要有兩個方面的原因:一是真實程序中存在著大量復(fù)雜的數(shù)值計算,包括非線性數(shù)值計算,常見的數(shù)學函數(shù)的計算等,現(xiàn)有的約束求解器對這類約束很難提供有效支持;二是真實程序中存在著大量的函數(shù)調(diào)用,現(xiàn)有的約束求解器通常只提供純數(shù)學表達式形式的約束支持,在函數(shù)具體實現(xiàn)細節(jié)無法得知的情況下,約束求解器很難對這類包含函數(shù)調(diào)用的路徑約束進行求解。為了解決以上兩個方面的問題,提高符號執(zhí)行技術(shù)應(yīng)用在真實程序的效率,本文的主要工作如下:·基于機器學習約束求解的符號執(zhí)行框架。不同于傳統(tǒng)的符號執(zhí)行框架,本文提出了一種新的基于機器學習的符號執(zhí)行框架——MLBSE。MLBSE與傳統(tǒng)符號執(zhí)行框架最顯著的區(qū)別就是底層約束求解技術(shù)。針對復(fù)雜路徑約束,MLBSE首先借助約束不滿足程度將路徑約束的滿足性問題轉(zhuǎn)化為優(yōu)化問題,然后使用基于機器學習的優(yōu)化算法RACOS對路徑約束進行求解。借助于這種基于機器學習的約束求解方法的優(yōu)勢,MLBSE能夠更好地支持包含大量復(fù)雜數(shù)值計算和函數(shù)調(diào)用的真實程序�！せ贛LBSE的符號執(zhí)行功能增強。在已有的基于機器學習約束求解的符號執(zhí)行框架MLBSE的基礎(chǔ)上,為了進一步增強MLBSE符號執(zhí)行功能,本文做了包括黑盒執(zhí)行模式,可解置信度報告和基于可解置信度報告的搜索策略三個方面的功能拓展。借助黑盒執(zhí)行模式,MLBSE能更加高效地處理包含函數(shù)調(diào)用的真實程序。通過引入可解置信度報告,MLBSE能夠在計算資源有限的情況下為用戶提供額外參考,幫助用戶判斷是否需要投入更多計算資源在求解失敗的路徑約束上。除此以外,MLBSE還提供了一種基于可解置信度報告的搜索策略�；谠摬呗�,MLBSE能自動為求解失敗且可解置信度高的路徑約束投入更多的計算資源,從而在不影響整體效率的前提下提高符號執(zhí)行的效果。·實現(xiàn)和實驗。在開源符號執(zhí)行引擎SPF的基礎(chǔ)上,本文完整地實現(xiàn)了基于機器學習約束求解的符號執(zhí)行工具MLB。為了驗證MLB在真實程序上執(zhí)行的效果和效率,本文選擇了 19個真實使用的程序作為測試程序,并同4個基于符號執(zhí)行的測試用例自動生成工具做了嚴格的對比實驗。實驗表明,MLB在效率、穩(wěn)定性和生成測試用例的質(zhì)量上都有著更好的表現(xiàn)。除此之外,本文還針對MLB的三個拓展功能做了一系列的實驗。實驗表明,MLB提供的可解置信度報告是具有參考價值的,同時黑盒執(zhí)行模式和基于可解置信度報告的搜索策略能進一步增強符號執(zhí)行的功能。
[Abstract]:How to generate high-quality test cases has been an important research topic in the field of software testing. Unlike other test case generation techniques, the symbol-based test case automatic generation technology replaces the variable of the specific value by using the symbolized variable in the process of program execution, while maintaining the path constraint in the whole execution process, When a branch statement is encountered, the constrained solver of the bottom layer is called to solve the path constraint to generate a test case that triggers the branch path. The technology has been applied to many testing tools, such as jCUTE, KLEE, and SPF, for many years. Currently, the symbol-based test case generation technology still faces many challenges in the application to the real program. One of the most important challenges is that the underlying constraint solver is unable to provide effective support for complex path constraints in the real program. There are two main reasons for this problem: first, there are a lot of complex numerical calculation in the real program, including the non-linear numerical calculation, the calculation of the common mathematical functions, etc., and the existing constraint solver is difficult to provide effective support for such constraints; Second, there is a large number of function calls in the real program, the existing constraint solver usually only provides the constraint support in the form of pure mathematical expression, and in the case where the specific implementation details of the function cannot be known, the constraint solver is difficult to solve the path constraint containing the function call. In order to solve the above two problems, to improve the efficiency of the symbol execution technology in the real program, the main work of this paper is as follows: Different from the traditional symbol execution framework, this paper presents a new symbol execution framework based on machine learning. The most significant difference between MLBSE and traditional symbol execution framework is the underlying constraint solving technique. For complex path constraints, the MLBSE first converts the path constraint satisfaction problem to the optimization problem by means of the constraint dissatisfaction degree, and then uses the machine-based optimization algorithm RACOS to solve the path constraint. With this advantage of a machine-based constrained solution approach, the MLBSE can better support a real program that contains a large number of complex numeric calculations and function calls. 路 The symbol execution function is enhanced based on the MLBSE. On the basis of the existing symbol execution framework MLBSE based on machine learning constraint solution, in order to further enhance the MLBSE symbol execution function, this paper has done the function expansion of three aspects including the black box execution mode, the solvability confidence report and the search strategy based on the solution confidence report. MLBSE can handle the real program with function calls more efficiently with the black box execution mode. By introducing a detest confidence report, the MLBSE is able to provide the user with additional references in the case of limited computing resources to help the user to determine whether more computing resources are required to be placed on the path constraints of the solution failure. In addition, the MLBSE provides a search strategy based on a solvability report. Based on this strategy, MLBSE can put more computational resources into path constraints with failure and high confidence, so as to improve the effect of symbol execution without affecting the overall efficiency. 路 Implement and experiment. On the basis of open source symbol execution engine (SPF), this paper fully implements the symbol execution tool MLB based on machine learning constraint solution. In order to verify the effect and efficiency of MLB's execution on the real program, this paper chooses 19 real-use programs as the test program, and makes a strict contrast experiment with the four symbol-based test case automatic generation tools. The results show that MLB has better performance in terms of efficiency, stability and quality of generating test cases. In addition, this paper has done a series of experiments for the three development functions of MLB. The experiment shows that the solution confidence report provided by the MLB is of reference value, while the black box execution mode and the search strategy based on the solution confidence report can further enhance the function of the symbol execution.
【學位授予單位】：南京大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP311.53
本文編號：2508912
[Abstract]:How to generate high-quality test cases has been an important research topic in the field of software testing. Unlike other test case generation techniques, the symbol-based test case automatic generation technology replaces the variable of the specific value by using the symbolized variable in the process of program execution, while maintaining the path constraint in the whole execution process, When a branch statement is encountered, the constrained solver of the bottom layer is called to solve the path constraint to generate a test case that triggers the branch path. The technology has been applied to many testing tools, such as jCUTE, KLEE, and SPF, for many years. Currently, the symbol-based test case generation technology still faces many challenges in the application to the real program. One of the most important challenges is that the underlying constraint solver is unable to provide effective support for complex path constraints in the real program. There are two main reasons for this problem: first, there are a lot of complex numerical calculation in the real program, including the non-linear numerical calculation, the calculation of the common mathematical functions, etc., and the existing constraint solver is difficult to provide effective support for such constraints; Second, there is a large number of function calls in the real program, the existing constraint solver usually only provides the constraint support in the form of pure mathematical expression, and in the case where the specific implementation details of the function cannot be known, the constraint solver is difficult to solve the path constraint containing the function call. In order to solve the above two problems, to improve the efficiency of the symbol execution technology in the real program, the main work of this paper is as follows: Different from the traditional symbol execution framework, this paper presents a new symbol execution framework based on machine learning. The most significant difference between MLBSE and traditional symbol execution framework is the underlying constraint solving technique. For complex path constraints, the MLBSE first converts the path constraint satisfaction problem to the optimization problem by means of the constraint dissatisfaction degree, and then uses the machine-based optimization algorithm RACOS to solve the path constraint. With this advantage of a machine-based constrained solution approach, the MLBSE can better support a real program that contains a large number of complex numeric calculations and function calls. 路 The symbol execution function is enhanced based on the MLBSE. On the basis of the existing symbol execution framework MLBSE based on machine learning constraint solution, in order to further enhance the MLBSE symbol execution function, this paper has done the function expansion of three aspects including the black box execution mode, the solvability confidence report and the search strategy based on the solution confidence report. MLBSE can handle the real program with function calls more efficiently with the black box execution mode. By introducing a detest confidence report, the MLBSE is able to provide the user with additional references in the case of limited computing resources to help the user to determine whether more computing resources are required to be placed on the path constraints of the solution failure. In addition, the MLBSE provides a search strategy based on a solvability report. Based on this strategy, MLBSE can put more computational resources into path constraints with failure and high confidence, so as to improve the effect of symbol execution without affecting the overall efficiency. 路 Implement and experiment. On the basis of open source symbol execution engine (SPF), this paper fully implements the symbol execution tool MLB based on machine learning constraint solution. In order to verify the effect and efficiency of MLB's execution on the real program, this paper chooses 19 real-use programs as the test program, and makes a strict contrast experiment with the four symbol-based test case automatic generation tools. The results show that MLB has better performance in terms of efficiency, stability and quality of generating test cases. In addition, this paper has done a series of experiments for the three development functions of MLB. The experiment shows that the solution confidence report provided by the MLB is of reference value, while the black box execution mode and the search strategy based on the solution confidence report can further enhance the function of the symbol execution.
【學位授予單位】：南京大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP311.53
【參考文獻】
中國期刊全文數(shù)據(jù)庫 前2條
1 孫志永;;Windows Vista會成功嗎[J];信息系統(tǒng)工程;2007年02期
2 周煜,周國慶,奚文駿;軟件測試技術(shù)概述[J];中國測試技術(shù);2005年03期
，本文編號：2508912
本文鏈接：http://sikaile.net/kejilunwen/ruanjiangongchenglunwen/2508912.html
最近更新
教材專著
