基于遗传算法的构件化软件测试用例生成研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
随着软件规模的不断扩大,高效率和高质量的软件开发成为现代软件工程学研究的热点。基于构件的软件工程(Component-Based Software Engineering,简称CBSE)是为了保证高效、优质地进行软件开发应运而生的技术。但是对于构件化软件来说,软件可靠性如何保证也是摆在测试工程师面前的难题,而软件测试正是保证软件可靠性的必要手段。因此构件化软件的测试技术必将受到测试工程师的重视。
     在构件化软件测试技术中,高效的测试用例生成是简化测试工作、提高测试效率、降低测试成本的必要手段。由于最初生成的测试用例数量庞大、测试效率低下,因此需要利用一种强有力的优化算法对最初生成的测试用例进行优化。遗传算法作为一种强健的搜索方法,它在解决大空间、多峰、非线性、全局优化等高复杂度问题时,显示了独特的优势和高效性。但对于局部空间的搜索问题遗传算法不是很有效,个体的多样性减少的很快。为了克服以上缺点,Chun等基于体细胞理论和免疫网络理论提出了一种免疫遗传算法[1]。在这个算法中,将抗原作为目标函数、抗体作为解答、抗原和抗体之间的亲和力作为解答的联合强度,显示了独特的优势和高效性。通过对其算法思想的改进就可以达到优化测试用例的要求。
     本文首先介绍了构件化软件的测试技术和测试用例自动生成技术,接着介绍了免疫遗传算法的主要思想,结合并行性思想、自适应思想提出了一种改进的免疫遗传算法(Improved Immune Genetic Algorithm,简称IIGA)。结合构件的合约检查思想,提出了一种基于改进的免疫遗传算法的构件化软件测试用例生成模型(Model of Test Case Generation of Component-Based Software,简称MTCGCBS),在此基础上详细地介绍了改进的免疫遗传算法的算法思想,并对算法进行了编程实现。在实验型构件化软件达到100%构件接口方法调用覆盖率的情况下,将改进的免疫遗传算法与传统遗传算法和随机算法在生成测试用例数量及生成测试用例运行时间上进行比较,进一步说明了改进的免疫遗传算法在构件化软件测试用例生成及优化中的优越性,同时也验证了MTCGCBS模型的正确性、可行性。
With the development of software scale, high-efficient and high-quality software development becomes the research hotspot of modern software engineering. Component-Based Software Engineering, in short CBSE is the technology to ensure high-efficient and high-quality software development. But for the Component-Based Software, how to ensure the reliability of software becomes the difficult problem for software engineer, software testing is a necessary means of ensuring software reliability. So the testing technology of Component-Based Software will attract the testing engineer’s attention.
     In Component-Based Software testing technologies, efficient test case generation is the necessary means of simplification of software testing, improving testing efficiency and lower testing cost. Because the test case generated as a result of the initial volume, testing inefficient, so it’s requiring the use of a powerful optimization algorithm to optimize test case initially generated. Genetic Algorithm as a strong search method, showing a unique advantage and high efficiency in resolving the problems of high complexity such as: large space, multi-hillside, nonlinear and optimization of the overall. But for the local search space problem Genetic Algorithm is not very effective, reducing the diversity of the individual quickly. To overcome these shortcomings, Chun, based on somatic cell theory and the theory of immune network made an Immune Genetic Algorithm [1]. In this algorithm, target function as antigen and antibody as answer, the affinity between antigen and antibody as a joint intensity of the answer, showing a unique advantage and high efficiency. Through the improvements of the algorithm it can achieve the requirements of optimizing test case.
     This paper first introduces the testing technology and the automatic test case generation technologies of Component-Based Software. Then introduces the basic idea of Immune Genetic Algorithm, combined with concurrent idea and self improve idea suggests an Improved Iimmune Genetic Algorithm (IIGA),Combined with component’s contract checking idea, and suggests a Model of Test Case Generation of Component-Based Software (MTCGCBS) based on the IIGA, introduces the idea of IIGA in detail and realizes it. Through the comparison with Traditional Genetic Algorithm and Random Algorithm of the quantity and the generation efficiency of test case which achieves 100% coverage of the component interface methods for experimental Component-Based Software. IIGA is further proved to be superior in generating and optimizing test case for Component-Based Software, and at the same time, the correctness and feasibility of the MTCGCBS is validated.
引文
【1】王凌著 智能优化算法及其应用[M] 清华大学出版社,2003
    【2】D.Bird and C.Munoz. Automatic generation of random self-checking test cases[J]. IBM System J.vol.22,NO.3.1983:229-245
    【3】C.V.Ramamoorthy, S.Ho. and W.Chen. On the automated generation of program test data[J]. IEEE Trans. Software Eng. vol.SE-2,NO.1.1981:117-127
    【4】Ramamoorthy C.V. On the automated generation of program test data[J].IEEE Trans on Software Eng,1976,4:215-222
    【5】P.D.Coward. Symbolic execution and testing[J]. Information and Software Technology. 1991,2:53-64
    【6】Bogdan Korel Automated Software Test Data Generation[J].IEEE Transactions on software engineering. Vol.16.NO.8,1990,8:870-879
    【7】Neelam Gupta,Aditya P. Mathur, Mary Lou Soffa. Generating test data from branch coverage[C]. The Fifteenth IEEE International Conference on Automated Software Engineering(ASE’00). September 11-15,2000,Grenoble,France
    【8】Harmen-Hinrich Sthamer, “The Automatic Generation of Software Test Data using Genetic Algorithms,” A thesis submitted in partial fulfilment of the requirements of the University of Glamorgan / Prifvsgol Morgannwg for the degree of a Doctor of Philosophy. November 1995
    【9】Roger Ferguson and Bogdan Korel. Software Test Data Generation using the Chaining Approach[C]. IEEE International Test Conference. 1995,703-709
    【10】Phil McMinn. Search-based Software Test Data Generation A Survey[J]. Software Tseting, Verification and Reliability,14(2),pp.105-156,June 2004
    【11】Christoph Michael and Gary McGraw. Automated Software Test Data Generation for Complex Programs. Reliable Software Technologies.21515 Ridgetop Circle,Suite 250 Sterling,VA 20166.
    【12】B.F.Jones,H.-H.Sthamer and D.E.Eyres. Automatic structural testing using geneticalgorithms[J]. Software Engineering Journal September 1996:299-306
    【13】D.Berndt,J.Fisher,L.Johnson,J.Pinglikar,and A.Watkins. Breeding Software Test Cases with Genetic Algorithms[C]. Proceedings of the 36th Hawaii International Conference on System Sciences(HICSS’03)
    【14】荚伟,高仲仪.基于遗传算法的软件结构测试数据生成技术研究[J].北京航空航天大学学报 Vol.23
    No.1 1997.23(1):36-40
    【15】汪浩,谢军凯,高仲仪.遗传算法及其在软件测试数据生成中的应用研究[J].计算机工程与应用
    2001.37(12):64-68
    【16】单锦辉、王戟、马晓冬等. 面向路径的测试数据自动生成工具及其图形界面的Tcl/Tk设计[J].计
    算机工程与应用.2002.36(1):74-77
    【17】景志远. 遗传K-均值算法在软件测试算例自动生成中的应用研究[J]. 油气田地面工程 2003.22(4):15-16
    【18】Ye Wu.Dai Pan and Mei-Hwa Chen. Techniques for Testing Component-Based Software[C]. Proceedings of the Seventh International Conference on Engineering of Complex Computer Systems(ICECCS’01)
    【19】古乐 史九林编著. 软件测试技术概论[M]. 北京:清华大学出版社 2004
    【20】Ron Patton著,周予滨、姚静等译. 软件测试[M]. 北京:机械工业出版社. 2002
    【21】Edward Kit著,李新华、陈丽容、马立群等译. 软件测试过程改进[M]. 北京:机械工业出版社,2003
    【22】Rex Black著,天宏工作室译. 测试流程管理[M]. 北京:北京大学出版社,2001
    【23】Myers G.J. 计算机软件测试技巧(中文版)[M].北京:清华大学出版社.1987
    【24】B. Meyer. Object-oriented software construction [M]. Prentice Hall, 1997
    【25】Yoonsik Cheon, Gary T. Leavens. A Runtime Assertion Checker for the Java Modeling Language (JML) [J], In Software Engineering Research and Practice (SERP'02):322--328. CSREA Press, June 2002.
    【26】王磊,焦李成 免疫进化计算理论及应用[D] 西安:西安电子科技大学 2001年9月
    【27】王小平,曹立明著 遗传算法-理论、应用与软件实现[M],西安交通大学出版社 2004
    【28】韩学东,洪炳熔,孟伟 基于疫苗自动获取与更新的免疫遗传算法[J] 计算机研究与发展2005.42(5):740-745
    【29】聂长海,徐宝文.一种最小测试用例集生成方法[J] 计算机学报 2003.26(12):1690-1695
    【30】Srinivas M,Patnaik L M. Adaptive probabilities of Crossover and Mutation in GA[J]. IEEE Trans on Systems, Man and Cybernetics. 1994,24(4):656~667
    【31】Jorgensen P C著.韩柯等译.软件测试[M].北京:机械工业出版社,2003
    【32】乐鑫喜,刘清,周新民 基于退火遗传算法的测试用例自动生成[D] 武汉:武汉理工大学 2005年6月
    【33】尚绪全,张毅坤 构件化软件集成测试研究[D] 西安:西安理工大学 2005年3月
    【34】赵明、张毅坤、沈建雄、崔杜武、高海岭 基于遗传算法的测试用例生成工具研究[J].计算机工程2005.31(13):151-153
    【35】S. Beydeda and V. Gruhn. An integrated testing technique for component-based software (accepted). In AICCSA ACS/IEEE International Conference on Computer Systems and Applications (Beirut, Lebanon, June 26--29), 2001
    【36】Ye Wu, Mei-Hwa Chen, and Jeff Offutt UML-Based Integration Testing for Component-Based Software, to appear in Proceedings of 2nd International Conference on COTS-Based Software Systems, Ottawa, Canada, Feb. 10 - 12, 2003
    【37】荚伟,谢军,奚红宇,高仲仪.遗传算法在软件测试数据生成中的应用[J].北京航空航天大学学报 1998. 24(4):434-437
    【38】荚伟,高仲仪. 用遗传算法实现软件结构测试数据的自动生成[J].计算机与数字工程,1996.24(1):7-14
    【39】冯杰,赵文耘,杨明华.基于构件的软件性能模型及评估技术研究[J].计算机工程与应用,2004.40(14):99-101
    【40】毛晓光,邓勇进.基于构件化软件的可靠性通用模型[J].软件学报,2004.15(1)
    【41】殷脂,曹渠江.构件软件的自适应测试[J].计算机应用,2005.25(12):417-420
    【42】马臻,张毅坤,梁荣等.基于免疫遗传算法的构件化软件测试用例生成方法研究[J].计算机工程.2007 年 1 月
    【43】张毅坤,马臻,解建仓. 一种改进的遗传算法在构件化软件测试用例优化中的应用研究[C]. 2005中国计算机大会(2005 China National Computer Conference, CNCC 2005)论文集. 北京:清华大学出版社,2005
    【44】邢传玉,张毅坤,马臻. 基于 XML 的构件化软件集成测试方法研究[J]. 计算机工程与应用.2006年 8 月
    【45】张毅坤,叶涛.基于合约检查的构件化软件集成测试框架[J].计算机工程.2006 年 11 月
    【46】 Adrita Bhor.Software Component Testing Strategies. URL http://www1.ics.uci.edu/-abhor/ics221/comp_test.htm
    【47】Sudipto Ghosh,Aditya P Mathur.Issues in Testing Distributed Component-Based Systems[C].In:Proc First International ICSE Workshop on TESTING DISTRIBUTED COMPONENT-BASED SYSTEM,1999:54-66
    【48】Alan W Brown,Kurt C Wallnau. The Current State of CBSE[J].IEEE software,1998:15(5)36-46.
    【49】 Ugo Buy,Carl Ghezzi,Alessandro Orso,et al. A Framework for Testing Object-Oriented Components[A].Proc First International ICSE Workshop on TESTING DISTRIBUTED COMPONENT-BASED SYSTEM,1999:84-92.
    【50】Fenton N E. Software Metrics: A Rigorous Approach[M].London: Chapman and Hall,1991.
    【 51 】 Sun Chang-ai,Liu Chao,Jin Mao-zhong et al.Architecture Framework for Software Test Tool[C].In:Proc 36th International Conference on Technology of Object-Oriented Languages and Systems,2000:40-47
    【52】Jerry Gao,Eugene Y Zhu,Simon Shim et al.Monitoring Software Components and Component-Based Software[C]In:Proc 24th Annual International Conference on Computer Software and Applications,2000:403-412
    【53】Hoijin Yoon,Byoungju Choi,Jin-OK Jeon.A UML-base Test Model for Component Integration Test[C].In:Proceeding of Workshop on Software Architecture and componentWSAC,URL http://selab.ewha.ac.kr/HoijinYoon/PAPERS/wsac.pdf,2000
    【54】景涛,白成刚,胡庆培,蔡开元.构件软件的测试问题综述[J].计算机工程与应用.2002.38(24):1-6
    【55】贾瑞生,孙红梅,郑永果,齐润泉.基于构件技术的软件测试问题探讨[J].山东科技大学学报(自然科学版).2004.23(4):105-107
    【56】万琳.路径测试用例自动生成中的搜索算法分析[J].计算机工程.2006.32(1):74-76

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700