基于谓词抽象的测试用例约简生成方法

doi:1000-436X(2012)03-0035-09

通信学报 ›› 2012, Vol. 33 ›› Issue (3): 35-43.doi: 1000-436X(2012)03-0035-09

基于谓词抽象的测试用例约简生成方法

郭曦¹,张焕国^1,²

¹ 武汉大学计算机学院，湖北武汉 430072
² 武汉大学空天信息安全与可信计算教育部重点实验室，湖北武汉 430072

出版日期:2012-03-25 发布日期:2017-07-18
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;空天信息安全与可信计算教育部重点实验室开放基金资助项目;空天信息安全与可信计算教育部重点实验室开放基金资助项目;湖北省自然基金资助项目;湖北省自然基金资助项目;中央高校基本科研业务费专项资金资助项目;中央高校基本科研业务费专项资金资助项目

Approach for reduced test suite generation based on predicate abstraction

Xi GUO¹,Huan-guo ZHANG^1,²

¹ School of Computer,Wuhan University,Wuhan 430072,China
² Key Laboratory of Aerospace Information Security and Trusted Computing of Ministry of Education,Wuhan University,Wuhan 430072,China

Online:2012-03-25 Published:2017-07-18
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Open Foundation of Key Laboratory of Aerospace Information Security and T Computing of Ministry of Education;The Open Foundation of Key Laboratory of Aerospace Information Security and T Computing of Ministry of Education;The Natural Science Foundation of Hubei Province;The Natural Science Foundation of Hubei Province;Fundamental Research Funds for the Central Universities;Fundamental Research Funds for the Central Universities

摘要/Abstract

摘要：

针对大规模软件系统状态迁移数量庞大，容易导致状态空间爆炸的问题，提出一种基于谓词抽象的测试用例约简生成方法，该方法依据给定的谓词集合对软件系统的状态空间进行等价类划分，通过状态集合之间的映射得到约简的抽象状态，并以抽象状态之间的迁移关系作为测试用例约简生成的基础。实验结果表明，该方法可以有效地对系统状态进行约简，并生成规模较小的测试用例集。

关键词: 谓词抽象, 状态约简, 等价类划分, 测试用例生成

Abstract:

Aim to the problem of status space explosion due to the growing number of status transition of large scale software system,a reduced test suite generation approach based on predicate abstraction was proposed,which divided the status space of the software model according to the gi predicates to get the equivalence classes.The reduced abstract status was settled using the mapping between the status sets,and generated the reduced test suite based on the transition of the status.The results of experiments indicate tha this approach can reduce the status of the model efficiently,and generate smaller size of test suite.

Key words: predicate abstraction, status reduction, equivalence class division, test case generation

郭曦,张焕国. 基于谓词抽象的测试用例约简生成方法[J]. 通信学报, 2012, 33(3): 35-43.

Xi GUO,Huan-guo ZHANG. Approach for reduced test suite generation based on predicate abstraction[J]. Journal on Communications, 2012, 33(3): 35-43.

图/表 5

图1

图2

图3

表1

图4

参考文献 14

[1]	HARROLD M J , GUPTA R , SOFFA M L . A methodology for controlling the size of a test suite[J]. ACM Transactions of Engineering and Methodology, 1993,2(3): 270-285.
[2]	屈婉霞, 李暾, 郭阳 ,等. 谓词抽象技术研究[J]. 软件学报, 2008,19(1): 27-38. QU W X , LI T , GUO Y ,et al. Advances in predicate abstraction[J]. Journal of Software, 2008,19(1): 27-38.
[3]	HONG H S , CHA S D , LEE I ,et al. Data flow testing as model checking[A]. Proceedings of the 25th International Conference on Software Engineering[C]. Portland, 2003, 232-243.
[4]	CHVATAL V . A greedy heuristic for the set-covering problem[J]. Mathematics of Operations Research, 1979,4(3): 233-235.
[5]	CHEN T Y , LAU M F . On the completeness of a test suite reduction strategy[J]. The Computer Journal, 1999,42(5): 430-440.
[6]	LEE J G , CHUNG C G . An optimal representative set selection method[J]. Information and Software Technology, 2000,42(21): 17-25.
[7]	章晓芳, 徐宝文, 聂长海 ,等. 一种基于测试需求约简的测试用例集优化方法[J]. 软件学报, 2007,18(4): 821-831. ZHANG X F , XU B W , NIE C H ,et al. An approach for optimizing test suite based on testing requirement reduction[J]. Journal of Software, 2007,18(4): 821-831.
[8]	程亮, 张阳, 冯登国 . 一种基于安全状态转移的简并测试集生成方法[J]. 软件学报, 2010,21(3): 539-547. CHENG L , ZHANG Y , FENG D G . Approach of degenerate test set generation based on secure state transition[J]. Journal of Software, 2010,21(3): 539-547.
[9]	徐明迪, 张焕国, 严飞 . 基于标记变迁系统的可信计算平台信任链测试[J]. 计算机学报, 2009,32(4): 635-645. XU M D , ZHANG H G , YAN F . Testing on trust chain of trusted computing platform based on labeled transition system[J]. Chinese Journal of Computers, 2009,32(4): 635-645.
[10]	SUSANNE G , HASSEN S . Construction of abstract state graphs with PVS[A]. Proceedings of the 9th International Conference on Computer Aided Verification[C]. Berlin, 1997. 72-83.
[11]	HENZINGER T A , JHALA R , MAJUMDAR R . Lazy abstraction[A]. ACM Symposium on Principles of Programming Language[C]. Oregon, 2002. 58-70.
[12]	DETLEFS D , NELSON G , SAXE J B . Simplify:a theorem prover for program checking[J]. Journal of the ACM, 2005,52(3): 365-473.
[13]	CHEN T Y , LAU M F . A simulation study on some heuristics for test suite reduction[J]. Information and Software Technology, 1998,40(13): 777-787.
[14]	沈昌祥, 张焕国, 冯登国 ,等. 信息安全综述[J]. 中国科学E辑, 2007,37(2): 129-150. SHEN C X , ZHANG H G , FENG D G ,et al. Survey of information security[J]. Science in China,Series E,Information Sciences, 2007,37(2): 129-150.

程序	长度L	可达位置数N-live	不可达位置数N-dead	原始模型状态数	约简模型状态数S’	谓词个数N-prdc	贪心算法T-G	GHS算法T-HGS	GRE算法T-GRE	本文方法T	约简比例Ratio
kbfiltr-5.0.219	5 940	295	80	121	47	116	39	35	36	31	0.21
floppy-1.12	8 567	772	251	251	103	342	125	117	118	109	0.13
cdaudio-3.5.27	8 933	592	359	245	85	257	197	194	193	177	0.12
ping-2.17	1 479	736	65	43	17	43	149	143	142	109	0.27

基于谓词抽象的测试用例约简生成方法

Approach for reduced test suite generation based on predicate abstraction

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 14

相关文章 0

Metrics

推荐阅读 0