基于多項式約束求解的程序路徑測試用例生成研究
發(fā)布時間：2018-08-22 19:58
【摘要】：軟件測試作為軟件工程的基本過程之一,是確保軟件質(zhì)量的重要方法。測試用例自動生成技術(shù)作為軟件測試的重要內(nèi)容之一,能夠增加軟件測試的準確性、有效降低測試成本,具有廣闊的發(fā)展前景。當前最常用的測試用例自動生成技術(shù)之一,就是符號執(zhí)行。然而,基于符號執(zhí)行的測試用例自動生成技術(shù)目前存在明顯的不足之處:在遇到復(fù)雜的非線性浮點約束時其效果并不理想,主要體現(xiàn)在非線性約束的復(fù)雜性導(dǎo)致的求解困難和浮點計算的精度限制導(dǎo)致的求解不準確兩個方面。目前,C語言是應(yīng)用最廣泛的編程語言,能夠?qū)語言程序進行測試用例自動生成具有很高的實用價值。本文給出了一個基于多項式約束求解的測試用例生成方法,并根據(jù)這個方法開發(fā)了一款針對C語言數(shù)值程序的測試用例自動生成工具。本文的具體研究內(nèi)容,包括以下三個方面:●研究符號執(zhí)行技術(shù),選擇支持C語言和浮點數(shù)的符號執(zhí)行工具KLEE-FP,通過符號執(zhí)行技術(shù)提取程序中的路徑約束。進一步,設(shè)計分析路徑約束的方法,將通過KLEE-FP得到的路徑約束轉(zhuǎn)換為多項式約束�！駥τ趶腃語言程序中得到的每一條路徑對應(yīng)的多項式約束,研究如何更快、更準確地求解。一方面,研究了基于低秩矩量矩陣恢復(fù)的多項式系統(tǒng)求解方法,對于含有等式和不等式的復(fù)雜多項式系統(tǒng),該方法求解速度更快、更適合大規(guī)模問題的求解;另一方面,研究了基于區(qū)間分析的驗證算法,通過計算出包含準確實解的區(qū)間并基于該區(qū)間給出測試用例,來有效地避免浮點計算導(dǎo)致的不準確和異常�！駥崿F(xiàn)了一款測試用例自動生成工具ATCase(Automatically generate Test Case),能夠分析C語言數(shù)值程序中的路徑并自動生成滿足該路徑約束的測試用例。總的來說,對于給定的C語言數(shù)值程序,首先通過符號執(zhí)行技術(shù)提取程序路徑約束并轉(zhuǎn)換為多項式約束,然后通過多項式約束求解的可驗證算法得到滿足路徑約束的測試用例。本文根據(jù)這個過程開發(fā)了一款軟件ATCase,并通過實驗驗證了 ATCase的高效性和強健壯性。
[Abstract]:As one of the basic processes of software engineering, software testing is an important method to ensure software quality. As one of the important contents of software testing, automatic test case generation technology can increase the accuracy of software testing and reduce the test cost effectively. It has a broad development prospect. One of the most commonly used test case generation techniques is symbolic execution. However, the automatic test case generation technique based on symbolic execution has some obvious shortcomings: the effect is not satisfactory when complex nonlinear floating point constraints are encountered. It is mainly reflected in two aspects: the difficulty of solving due to the complexity of nonlinear constraints and the inaccuracy caused by the precision limitation of floating-point calculation. At present, C language is the most widely used programming language. It has high practical value to automatically generate test cases for C language programs. In this paper, a test case generation method based on polynomial constraint solution is presented. Based on this method, a test case generation tool for C language numerical programs is developed. The specific research contents of this paper include the following three aspects: research on symbolic execution technology, select symbol execution tool KLEE-FPwhich supports C language and floating-point number, extract path constraints in program by symbolic execution technology. Furthermore, the method of analyzing path constraints is designed to convert the path constraints obtained by KLEE-FP into polynomial constraints. For the polynomial constraints corresponding to each path obtained from C language programs, how to solve them faster and more accurately is studied. On the one hand, the method of solving polynomial systems based on the restoration of low rank moment matrix is studied. For complex polynomial systems with equality and inequality, the method is faster and more suitable for solving large-scale problems. The verification algorithm based on interval analysis is studied. By calculating the interval containing quasi-exact solution, the test cases are given based on the interval. An automatic test case generation tool, ATCase (Automatically generate Test Case), is implemented to analyze the paths in C language numerical programs and automatically generate test cases that meet the path constraints. In general, for a given C language numerical program, the program path constraints are firstly extracted by symbolic execution technique and converted into polynomial constraints, and then the test cases satisfying the path constraints are obtained by a verifiable algorithm for solving polynomial constraints. According to this process, a software ATCase is developed in this paper, and the high efficiency and strong robustness of ATCase are verified by experiments.
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP311.53
本文編號：2198150
[Abstract]:As one of the basic processes of software engineering, software testing is an important method to ensure software quality. As one of the important contents of software testing, automatic test case generation technology can increase the accuracy of software testing and reduce the test cost effectively. It has a broad development prospect. One of the most commonly used test case generation techniques is symbolic execution. However, the automatic test case generation technique based on symbolic execution has some obvious shortcomings: the effect is not satisfactory when complex nonlinear floating point constraints are encountered. It is mainly reflected in two aspects: the difficulty of solving due to the complexity of nonlinear constraints and the inaccuracy caused by the precision limitation of floating-point calculation. At present, C language is the most widely used programming language. It has high practical value to automatically generate test cases for C language programs. In this paper, a test case generation method based on polynomial constraint solution is presented. Based on this method, a test case generation tool for C language numerical programs is developed. The specific research contents of this paper include the following three aspects: research on symbolic execution technology, select symbol execution tool KLEE-FPwhich supports C language and floating-point number, extract path constraints in program by symbolic execution technology. Furthermore, the method of analyzing path constraints is designed to convert the path constraints obtained by KLEE-FP into polynomial constraints. For the polynomial constraints corresponding to each path obtained from C language programs, how to solve them faster and more accurately is studied. On the one hand, the method of solving polynomial systems based on the restoration of low rank moment matrix is studied. For complex polynomial systems with equality and inequality, the method is faster and more suitable for solving large-scale problems. The verification algorithm based on interval analysis is studied. By calculating the interval containing quasi-exact solution, the test cases are given based on the interval. An automatic test case generation tool, ATCase (Automatically generate Test Case), is implemented to analyze the paths in C language numerical programs and automatically generate test cases that meet the path constraints. In general, for a given C language numerical program, the program path constraints are firstly extracted by symbolic execution technique and converted into polynomial constraints, and then the test cases satisfying the path constraints are obtained by a verifiable algorithm for solving polynomial constraints. According to this process, a software ATCase is developed in this paper, and the high efficiency and strong robustness of ATCase are verified by experiments.
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP311.53
【參考文獻】
相關(guān)期刊論文 前1條
1 湯恩義;周巖;歐建生;陳鑫;;面向條件判定覆蓋的線性擬合制導(dǎo)測試生成[J];軟件學(xué)報;2016年03期
相關(guān)重要報紙文章 前1條
1 吳穹;李明富;;銀聯(lián)系統(tǒng)癱瘓的背后[N];計算機世界;2006年
相關(guān)博士學(xué)位論文 前2條
1 郭健;基于智能算法的非線性模型研究及預(yù)測控制[D];華中科技大學(xué);2008年
2 單錦輝;面向路徑的測試數(shù)據(jù)自動生成方法研究[D];國防科學(xué)技術(shù)大學(xué);2002年
相關(guān)碩士學(xué)位論文 前1條
1 諸一駿;多項式系統(tǒng)實根求解的可驗證算法研究以及實現(xiàn)[D];華東師范大學(xué);2014年
，本文編號：2198150
本文鏈接：http://sikaile.net/kejilunwen/ruanjiangongchenglunwen/2198150.html
最近更新
教材專著
