[發(fā)明專利]基于基路徑的測(cè)試程序控制流路徑集生成方法

無效

• 申請(qǐng)?zhí)枺?/td>: 200810045139.2
• 申請(qǐng)日: 2008-01-09
• 公開（公告）號(hào): CN101216803A
• 公開（公告）日: 2008-07-09
• 發(fā)明（設(shè)計(jì)）人: 李志蜀;金虎;王莉;孫繼榮;陳宇;鄭燕妮;李寶林
• 申請(qǐng)（專利權(quán)）人: 四川大學(xué)
• 主分類號(hào): G06F11/36
• 分類號(hào): G06F11/36
• 代理公司: 成都信博專利代理有限責(zé)任公司
• 代理人: 潘育敏

一、所屬技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)的程序測(cè)試方法，屬結(jié)構(gòu)性測(cè)試中的路徑測(cè)試技術(shù)，特別是被測(cè)試程序控制流路徑有效子集生成方法。

二、背景技術(shù)

作為軟件測(cè)試中廣泛使用的兩類測(cè)試方法之一的結(jié)構(gòu)性測(cè)試方法，由于是基于被測(cè)程序的源代碼而不是基于被測(cè)程序的定義的，使得該方法支持嚴(yán)格定義、數(shù)學(xué)分析和精確度量。這些優(yōu)勢(shì)決定了結(jié)構(gòu)性測(cè)試必然會(huì)在軟件測(cè)試工程中被廣泛采用。而作為結(jié)構(gòu)性測(cè)試中最重要的一種測(cè)試技術(shù)——路徑測(cè)試，以其測(cè)試方法為基礎(chǔ)的各種技術(shù)自20世紀(jì)70年代就已經(jīng)提出，這些方法的提出者已經(jīng)向市場(chǎng)推出了實(shí)現(xiàn)這些技術(shù)的非常成功的工具。但是由于被測(cè)試程序結(jié)構(gòu)的復(fù)雜性，即使是規(guī)模很小的程序，包含的邏輯路徑數(shù)量也是相當(dāng)大的，從而使得完全的路徑測(cè)試在實(shí)際的軟件結(jié)構(gòu)性測(cè)試中并不具有很大的可行性。因此如何找出被測(cè)程序中的所有邏輯路徑的有效路徑子集，以便通過設(shè)計(jì)可覆蓋該有效邏輯路徑子集的用例來發(fā)現(xiàn)程序中盡可能多的錯(cuò)誤，便成了路徑測(cè)試的研究與工程應(yīng)用的核心與難點(diǎn)問題。現(xiàn)有技術(shù)中，被測(cè)試程序控制流路徑有效子集生成方法往往不能滿足路徑覆蓋測(cè)試的需求。尤其是被測(cè)試程序控制流路徑的有效路徑子集的自動(dòng)生成方法還未見報(bào)道。

三、發(fā)明內(nèi)容

本發(fā)明的目的是提供一種路徑測(cè)試中被測(cè)試程序控制流路徑的有效路徑子集的生成方法，該方法不僅實(shí)現(xiàn)了所生成的控制流路徑子集的正確性、有效性和完備性，還實(shí)現(xiàn)了整個(gè)控制流路徑子集生成過程的流程自動(dòng)化。

本發(fā)明的目的是這樣達(dá)到的：一種基于基路徑的測(cè)試程序控制流路徑子集生成方法，其特征在于：在編譯器模塊、控制流圖鄰接矩陣生成模塊和控制流路徑子集生成模塊三模塊中完成測(cè)試程序控制流路徑子集的生成：首先將被測(cè)試源程序片的控制流路徑定義為具有長(zhǎng)度(模)和方向?qū)傩缘南蛄?，則特定程序片斷的控制流路徑集合以及其上可以施加的向量操作便組成了一個(gè)向量空間，其存在必定存在一個(gè)基路徑集合，使用編譯器模塊獲得包含源程序片程序結(jié)構(gòu)信息的數(shù)據(jù)結(jié)構(gòu)，然后通過遍歷該數(shù)據(jù)結(jié)構(gòu)使用控制流路徑生成算法生成基于基路徑的程序控制流路徑子集。其具體的方法是：

1、使用編譯器模塊對(duì)被測(cè)試源程序進(jìn)行處理，用以對(duì)被測(cè)試源程序進(jìn)行語(yǔ)義解釋，將被測(cè)試源程序與控制流路徑生成的測(cè)試計(jì)算引擎聯(lián)系起來，形成合理的足以表示被測(cè)程序控制流信息的數(shù)據(jù)結(jié)構(gòu)——抽象語(yǔ)法樹(AST)，編譯器模塊輸出此結(jié)構(gòu)供控制流圖鄰接矩陣生成模塊處理。

2、處理流程進(jìn)入程序控制流圖鄰接矩陣生成模塊，該模塊遍歷抽象語(yǔ)法樹結(jié)構(gòu)，按照語(yǔ)句是否具有條件跳轉(zhuǎn)語(yǔ)義或無條件跳轉(zhuǎn)語(yǔ)義分別調(diào)用條件跳轉(zhuǎn)語(yǔ)句處理函數(shù)和無條件跳轉(zhuǎn)處理函數(shù)進(jìn)行處理并生成程序流圖的鄰接矩陣表示供控制流路徑子集生成模塊進(jìn)行后續(xù)操作。

3、控制流路徑子集生成模塊通過遍歷鄰接矩陣獲得被測(cè)程序控制流信息，采用深度優(yōu)先多次回溯的方式遍歷鄰接矩陣，跟蹤并記錄程序控制流的執(zhí)行到的語(yǔ)句節(jié)點(diǎn)，并對(duì)該信息進(jìn)行處理，生成基于基路徑的程序控制流路徑子集。

所述編譯器模塊對(duì)被測(cè)試源程序進(jìn)行處理，添加了用于保存某些特定信息的域并在編譯過程中嚴(yán)格建立了源碼語(yǔ)句與中間結(jié)構(gòu)AST節(jié)點(diǎn)間的一一對(duì)應(yīng)關(guān)系。

程序控制流圖鄰接矩陣生成模塊使用程序算法自動(dòng)實(shí)現(xiàn)遍歷抽象語(yǔ)法樹結(jié)構(gòu)并生成程序流圖的鄰接矩陣表示過程的基本思想是：通過遍歷抽象語(yǔ)法樹每條語(yǔ)句執(zhí)行時(shí)的靜態(tài)控制流信息，對(duì)具有影響源程序控制流操作語(yǔ)義的控制流語(yǔ)句進(jìn)行特殊處理；其基本流程步驟如下：

步驟1)初始化當(dāng)前處理語(yǔ)句的語(yǔ)句號(hào)i；

步驟2)若語(yǔ)句i為被測(cè)程序片的最后一條語(yǔ)句，則算法結(jié)束。否則執(zhí)行步驟3；

步驟3)若語(yǔ)句i具有條件跳轉(zhuǎn)語(yǔ)義(EQ、GE、GT、LE、LT、NE)，則調(diào)用條件跳轉(zhuǎn)語(yǔ)句處理函數(shù)conjmpproc(i)對(duì)語(yǔ)句i進(jìn)行處理，同時(shí)流程跳轉(zhuǎn)到步驟6；否則執(zhí)行步驟4；

步驟4)若語(yǔ)句i具有無條件跳轉(zhuǎn)語(yǔ)義(JUMP)，則調(diào)用無條件跳轉(zhuǎn)語(yǔ)句處理函數(shù)unconjmpproc(i)函數(shù)對(duì)語(yǔ)句i進(jìn)行處理，同時(shí)流程跳轉(zhuǎn)到步驟6；否則執(zhí)行步驟5；

步驟5)將AdjoiningMatrix[i][i+1]賦值為1；

步驟6)將語(yǔ)句號(hào)i值遞增以處理下一條語(yǔ)句；重復(fù)執(zhí)行步驟2；

程序控制流圖鄰接矩陣生成算法中存在對(duì)條件跳轉(zhuǎn)語(yǔ)句處理函數(shù)conjmpproc(i)和無條件跳轉(zhuǎn)語(yǔ)句處理函數(shù)unconjmpproc(i)的調(diào)用，分別用于對(duì)具有條件跳轉(zhuǎn)語(yǔ)義以及無條件跳轉(zhuǎn)語(yǔ)義的語(yǔ)句i進(jìn)行處理。

所述條件跳轉(zhuǎn)語(yǔ)句處理函數(shù)的具體處理流程步驟是：