[發(fā)明專利]一種受上下文無關(guān)文法約束的測試用例生成方法

有效

• 申請?zhí)枺?/td>: 201110062021.2
• 申請日: 2011-03-15
• 公開（公告）號: CN102141959A
• 公開（公告）日: 2011-08-03
• 發(fā)明（設(shè)計）人: 張玉清;楊丁寧;劉奇旭
• 申請（專利權(quán)）人: 中國科學(xué)院研究生院
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長江

1.一種受上下文無關(guān)文法約束的測試用例生成方法，其步驟為：

1)建立一包括若干合法測試用例的初始集合I；所述合法測試用例為符合目標(biāo)程序的上下文無關(guān)文法約束、能被程序正確地接受和處理的測試用例；

2)對于I中的每一合法測試用例，利用上下文無關(guān)文法分析其語法結(jié)構(gòu)，得到一解析樹T；

3)遍歷解析樹T中每一內(nèi)結(jié)點n，對于n所對應(yīng)的上下文無關(guān)文法非終結(jié)符N，將N在測試用例中所生成的子串s加入到該非終結(jié)符N對應(yīng)的字符串集合Frag_N中；

4)對所述初始集合I中每一合法測試用例，重復(fù)步驟2)、3)，得到每一非終結(jié)符在所有合法測試用例中所能生成的字符串集合；

5)將I中的合法測試用例作為初始種子測試用例加入到一隊列Q中，并為Q設(shè)定一個測試用例入隊條件P；

6)從隊列Q的隊頭依次取出一個初始種子測試用例c，利用上下文無關(guān)文法分析其語法結(jié)構(gòu)，得到一個解析樹T_c；

7)遍歷解析樹T_c中每一內(nèi)結(jié)點n_c，對于n_c所對應(yīng)的上下文無關(guān)文法非終結(jié)符N_c，查找非終結(jié)符N_c所生成的初始種子測試用例c中的子串s_c；

8)利用4)所得的與該非終結(jié)符N_c名稱相同的集合Frag_N中每個字符串分別替代初始種子測試用例c的子串s_c，每次得到一個新的測試用例c’，如果c’已經(jīng)在集合GEN中出現(xiàn)，則將c’丟棄；否則將c’加入到集合GEN中，并且如果c’滿足Q中入隊條件P，則同時將c’加入隊列Q的隊尾；

9)重復(fù)步驟6)～8)，直到隊列Q中的種子測試用例全部被依次取出，此時將集合GEN中的全部元素作為測試用例輸出。

2.如權(quán)利要求1所述的方法，其特征在于所述初始集合I中的測試用例覆蓋上下文無關(guān)文法所有語法結(jié)構(gòu)。

3.如權(quán)利要求2所述的方法，其特征在采用深度優(yōu)先的方法遍歷解析樹。

4.如權(quán)利要求2所述的方法，其特征在采用廣度優(yōu)先的方法遍歷解析樹。

5.如權(quán)利要求3或4所述的方法，其特征在于遍歷解析樹中同一父結(jié)點下的子結(jié)點時，位于左側(cè)的子結(jié)點先于右側(cè)的子結(jié)點遍歷。

6.如權(quán)利要求1或2所述的方法，其特征在于所述初始種子測試用例為所述初始集合I中的合法測試用例。

7.如權(quán)利要求1或2所述的方法，其特征在于所述入隊條件P為測試用例長度小于一設(shè)定閾值。

8.如權(quán)利要求1或2所述的方法，其特征在于所述合法測試用例為Fuzzing測試用例。

9.如權(quán)利要求1或2所述的方法，其特征在于所述目標(biāo)程序為以受上下文無關(guān)文法約束的數(shù)據(jù)為輸入的軟件或系統(tǒng)。

10.如權(quán)利要求9所述的方法，其特征在于所述軟件包括但不限于：網(wǎng)絡(luò)瀏覽器軟件、數(shù)據(jù)庫服務(wù)器系統(tǒng)軟件。