留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于无关变量分离的EFSM测试数据进化生成

潘雄 郝帅 苑政国 宋凝芳

潘雄, 郝帅, 苑政国, 等 . 基于无关变量分离的EFSM测试数据进化生成[J]. 北京航空航天大学学报, 2019, 45(5): 919-929. doi: 10.13700/j.bh.1001-5965.2018.0531
引用本文: 潘雄, 郝帅, 苑政国, 等 . 基于无关变量分离的EFSM测试数据进化生成[J]. 北京航空航天大学学报, 2019, 45(5): 919-929. doi: 10.13700/j.bh.1001-5965.2018.0531
PAN Xiong, HAO Shuai, YUAN Zhengguo, et al. Evolutionary generation of test data for EFSM based on irrelevant variable separation[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(5): 919-929. doi: 10.13700/j.bh.1001-5965.2018.0531(in Chinese)
Citation: PAN Xiong, HAO Shuai, YUAN Zhengguo, et al. Evolutionary generation of test data for EFSM based on irrelevant variable separation[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(5): 919-929. doi: 10.13700/j.bh.1001-5965.2018.0531(in Chinese)

基于无关变量分离的EFSM测试数据进化生成

doi: 10.13700/j.bh.1001-5965.2018.0531
详细信息
    作者简介:

    潘雄  男, 博士, 高级工程师, 硕士生导师。主要研究方向:软件可靠性、数字系统可靠性

    郝帅  男, 硕士研究生。主要研究方向:软件测试、软件可靠性

    苑政国  男, 博士研究生。主要研究方向:形式验证、软件可靠性

    宋凝芳  女, 博士, 研究员。主要研究方向:惯性技术、空间光电信息系统

    通讯作者:

    潘雄. E-mail:08768@buaa.edu.cn

  • 中图分类号: TP311

Evolutionary generation of test data for EFSM based on irrelevant variable separation

More Information
  • 摘要:

    扩展有限状态机(EFSM)相比于有限状态机(FSM)能够更加精确地刻画系统的动态行为,因而广泛作为各种控制流与数据流系统的测试模型。在EFSM模型的测试中,使用搜索的方法获得触发目标测试路径的测试数据是近年来的一个研究热点。为进一步提高搜索效率,在遗传算法(GA)的基础上提出一种自动分离测试路径中无关输入变量的方法,该方法通过分析模型中变量与迁移间的关系,判定不影响子路径中谓词条件的无关输入变量,进而从个体中将其分离以实现搜索空间的自动缩减,提升测试数据生成效率。对几种具有不同复杂度的基准EFSM模型进行实验后的结果表明,该方法生成有效测试数据的成功率均达到98.2%以上,且与未分离输入变量的遗传算法相比,所需平均迭代次数减少44.7%~85.9%,平均运行时间减少24.1%~85.5%。

     

  • 图 1  ATM的扩展有限状态机模型

    Figure 1.  Extended finite state machine model of ATM

    图 2  EFSM中的一条测试路径

    Figure 2.  A test path in EFSM

    图 3  不同变量间的关系图

    Figure 3.  Relationship diagram among different variables

    图 4  EFSM测试数据生成的实现过程

    Figure 4.  Implementation process of EFSM test data generation

    图 5  不同搜索空间之间的关系

    Figure 5.  Relationship between different search spaces

    图 6  迭代次数对比

    Figure 6.  Iteration number comparison

    表  1  实验模型及相关参数

    Table  1.   Relevant parameters of experimental models

    模型 状态个数 迁移个数 候选路径 实验路径 判定时间/ms
    ATM 10 28 44 43 703
    INRES 7 16 23 18 570
    Cashier 12 20 49 22 713
    下载: 导出CSV

    表  2  不同算法的平均迭代次数与平均运行时间

    Table  2.   Average number of iterations and average running time for different algorithms

    模型 数据范围 平均迭代次数 平均运行时间/ms
    GSS-RA IIVS-RA GSS-GA IIVS-GA GSS-RA IIVS-RA GSS-GA IIVS-GA
    [0, 511] 117292.1 42033.1 533.5 137.7 4119.2 1146.2 1013.3 262.0
    ATM [0, 1023] 166786.7 99062.8 946.7 224.3 4294.9 2534.4 1609.2 602.1
    [0, 2047] 197291.8 106831.6 1649.7 427.3 5072.7 2831.9 2639.8 905.3
    [0, 511] 113718.0 97355.6 4826.7 889.3 12041.5 5275.4 11040.9 2255.5
    INRES [0, 1 023] 163962.1 121408.1 7024.9 2978.3 18129.9 15383.2 16062.7 11007.0
    [0, 2047] 87049.8 227285.3 8193.6 4532.3 7820.7 16493.2 20004.8 15192.9
    [0, 511] 87653.0 24091.4 870.0 122.8 3482.4 915.7 1229.9 211.7
    Cashier [0, 1 023] 77864.8 41564.1 1343.7 220.4 3046.8 1348.6 2807.9 406.6
    [0, 2 047] 32290.5 51415.0 1918.3 327.6 1241.3 1842.8 3624.3 629.7
    下载: 导出CSV

    表  3  不同算法的成功率

    Table  3.   Success rate of different algorithms

    模型 数据范围 成功率/%
    GSS-RA IIVS-RA GSS-GA IIVS-GA
    [0, 511] 91.6 99.4 100.0 100.0
    ATM [0, 1 023] 54.4 97.1 100.0 100.0
    [0, 2 047] 16.4 88.2 100.0 100.0
    [0, 511] 61.4 94.0 98.6 100.0
    INRES [0, 1 023] 56.1 88.8 90.9 100.0
    [0, 2 047] 26.7 74.7 85.0 98.2
    [0, 511] 92.4 98.7 100.0 100.0
    Cashier [0, 1 023] 70.5 98.1 100.0 100.0
    [0, 2 047] 55.2 95.9 100.0 100.0
    下载: 导出CSV

    表  4  目标测试路径与可分离输入变量及其起始分离迁移

    Table  4.   Target test path with its separable input variables and initial separation transitions

    目标测试路径 可分离输入变量及其起始分离迁移
    LTP1=[t1, t4, t5, t8, t17, t21, t10, t7, t13] (β2, β3, h)→无; zt4; wt17; β1t21; yt13
    LTP2=[t1, t4, t6, t7, t14, t16, t9, t25, t28] y→无; zt4; wt14; β1t16; (β2, β3, h)→t28
    LTP3=[t1, t4, t5, t25, t27, t30, t26] (w, y)→无; zt4; (β2, β3, h)→t27; β1t30
    LTP4=[t1, t4, t6, t8, t18, t22, t10, t7, t12] (w, β2, β3, h)→无; zt4; yt18; β1t12
    下载: 导出CSV
  • [1] 苏宁, 郭俊霞, 李征, 等.基于EFSM不定型切片测试用例自动生成的研究[J].计算机研究与发展, 2017, 54(3):669-680. http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201703018

    SU N, GUO J X, LI Z, et al.EFSM amorphous slicing based test case generation[J].Journal of Computer Research & Development, 2017, 54(3):669-680(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201703018
    [2] SAEED A, HAMID S H A.Extended finite state machines-based testing using metaheuristic search-based techniques: Issues, and open challenges[C]//Software Engineering Conference.Piscataway, NJ: IEEE Press, 2016: 25-30.
    [3] ZHAO R, HARMAN M, LI Z.Empirical study on the efficiency of search based test generation for EFSM models[C]//International Conference on Software Testing.Washington, D.C.: IEEE Computer Society, 2010: 222-231.
    [4] KALAJI A S, HIERONS R M, SWIFT S.An integrated search-based approach for automatic testing from extended finite state machine (EFSM) models[J].Information and Software Technology, 2011, 53(12):1297-1318. doi: 10.1016/j.infsof.2011.06.004
    [5] TURLEA A, IPATE F, LEFTICARU R.A hybrid test generation approach based on extended finite state machines[C]//International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, 2016: 173-180.
    [6] LU G, MIAO H.An approach to generating test data for EFSM paths considering condition coverage[J].Electronic Notes in Theoretical Computer Science, 2014, 309(22):13-29. http://www.sciencedirect.com/science/article/pii/S1571066114000875
    [7] 周艺斌, 殷永峰, 李骁丹, 等.基于程序变异的Simulink模型测试方法[J].北京航空航天大学学报, 2015, 41(3):391-397. http://bhxb.buaa.edu.cn/CN/abstract/abstract13178.shtml

    ZHOU Y B, YIN Y F, LI X D, et al.Simulink model testing method based on program mutation[J].Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(3):391-397(in Chinese). http://bhxb.buaa.edu.cn/CN/abstract/abstract13178.shtml
    [8] ZHANG J, YANG R, CHEN Z, et al.Automated EFSM-based test case generation with scatter search[C]//International Workshop on Automation of Software Test.Piscataway, NJ: IEEE Press, 2012: 76-82.
    [9] KAMKIN A, LEBEDEV M, SMOLOV S.An EFSM-driven and model checking-based approach to functional test generation for hardware designs[C]//East-West Design & Test Symposium.Piscataway, NJ: IEEE Press, 2017: 1-4.
    [10] OFFUTT A J, JIN Z, PAN J.The dynamic domain reduction procedure for test data generation[J].Software Practice & Experience, 2015, 29(2):167-193. https://www.researchgate.net/publication/2608021_The_Dynamic_Domain_Reduction_Procedure_for_Test_Data_Generation
    [11] 张涌, 钱乐秋, 王渊峰.基于扩展有限状态机测试中测试输入数据自动选取的研究[J].计算机学报, 2003, 26(10):1295-1303. doi: 10.3321/j.issn:0254-4164.2003.10.012

    ZHANG Y, QIAN L Q, WANG Y F.Automatic testing data generation in the testing based on EFSM[J].Chinese Journal of Computers, 2003, 26(10):1295-1303(in Chinese). doi: 10.3321/j.issn:0254-4164.2003.10.012
    [12] KOREL B.Automated software test data generation[J].IEEE Transactions on Software Engineering, 1990, 16(8):870-879. doi: 10.1109/32.57624
    [13] MCMINN P, HARMAN M, LAKHOTIA K, et al.Input domain reduction through irrelevant variable removal and its effect on local, global, and hybrid search-based structural test data generation[J].IEEE Transactions on Software Engineering, 2012, 38(2):453-477. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=130811e685a34b7596ebe2eee66499a6
    [14] 张岩, 巩敦卫.基于搜索空间自动缩减的路径覆盖测试数据进化生成[J].电子学报, 2012, 40(5):1011-1016. http://d.old.wanfangdata.com.cn/Periodical/dianzixb201205024

    ZHANG Y, GONG D W.Evolutionary generation of test data for path coverage based on automatic reduction of search space[J].Acta Electronica Sinica, 2012, 40(5):1011-1016(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/dianzixb201205024
    [15] 廖伟志.基于路径自动分割的测试数据生成方法[J].电子学报, 2016, 44(9):2254-2261. doi: 10.3969/j.issn.0372-2112.2016.09.034

    LIAO W Z.Test data generation based on automatic division of path[J].Acta Electronica Sinica, 2016, 44(9):2254-2261(in Chinese). doi: 10.3969/j.issn.0372-2112.2016.09.034
    [16] 巩敦卫, 任丽娜.回归测试数据进化生成[J].计算机学报, 2014, 37(3):489-499. http://d.old.wanfangdata.com.cn/Periodical/jsjxb201403001

    GONG D W, REN L N.Evolutionary generation of regression test data[J].Chinese Journal of Computers, 2014, 37(3):489-499(in Chinese). http://d.old.wanfangdata.com.cn/Periodical/jsjxb201403001
    [17] VILKOMIR S, ALLURI A, KUHN D R, et al.Combinatorial and MC/DC coverage levels of random testing[C]//IEEE International Conference on Software Quality, Reliability and Security Companion.Piscataway, NJ: IEEE Press, 2017: 61-68.
    [18] WANG Y, LI Z, ZHAO R. Dependence based model-healing[C]//Computer Software & Applications Conference. Washington, D.C.: IEEE Computer Society, 2015: 556-561.
  • 加载中
图(6) / 表(4)
计量
  • 文章访问数:  629
  • HTML全文浏览量:  116
  • PDF下载量:  324
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-09-07
  • 录用日期:  2018-12-07
  • 网络出版日期:  2019-05-20

目录

    /

    返回文章
    返回
    常见问答