Evolutionary generation of test data for EFSM based on irrelevant variable separation
-
摘要:
扩展有限状态机(EFSM)相比于有限状态机(FSM)能够更加精确地刻画系统的动态行为,因而广泛作为各种控制流与数据流系统的测试模型。在EFSM模型的测试中,使用搜索的方法获得触发目标测试路径的测试数据是近年来的一个研究热点。为进一步提高搜索效率,在遗传算法(GA)的基础上提出一种自动分离测试路径中无关输入变量的方法,该方法通过分析模型中变量与迁移间的关系,判定不影响子路径中谓词条件的无关输入变量,进而从个体中将其分离以实现搜索空间的自动缩减,提升测试数据生成效率。对几种具有不同复杂度的基准EFSM模型进行实验后的结果表明,该方法生成有效测试数据的成功率均达到98.2%以上,且与未分离输入变量的遗传算法相比,所需平均迭代次数减少44.7%~85.9%,平均运行时间减少24.1%~85.5%。
Abstract:Extended finite state machine (EFSM), a more accurate test model than finite state machine (FSM), has been widely used to describe dynamic behavior of system, and thus has been taken as the test model of various control flow and data flow systems. For EFSM model test, using search method to obtain test data to trigger a given test path has become a research hotspot in recent years. In order to improve the search efficiency, this paper proposed a method that originates from genetic algorithm (GA) and can automatically separate irrelevant input variables in a test path. By analyzing the relationship between variables and state transitions in EFSM and separating irrelevant input variables from the individual that does not affect the transition's guard in the sub-test path, the new method reduced the search space and enhanced the efficiency of test data generation. The experimental results on various complex benchmark EFSM models show that the success rate of the new method to generate effective test data is larger than 98.2%. Compared to the traditional genetic algorithm, the average number of iterations of the new method is reduced by 44.7%-85.9% and the average running time is reduced by 24.1%-85.5%.
-
表 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 表 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 表 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 表 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)→无; z→t4; w→t17; β1→t21; y→t13 LTP2=[t1, t4, t6, t7, t14, t16, t9, t25, t28] y→无; z→t4; w→t14; β1→t16; (β2, β3, h)→t28 LTP3=[t1, t4, t5, t25, t27, t30, t26] (w, y)→无; z→t4; (β2, β3, h)→t27; β1→t30 LTP4=[t1, t4, t6, t8, t18, t22, t10, t7, t12] (w, β2, β3, h)→无; z→t4; y→t18; β1→t12 -
[1] 苏宁, 郭俊霞, 李征, 等.基于EFSM不定型切片测试用例自动生成的研究[J].计算机研究与发展, 2017, 54(3):669-680. http://d.old.wanfangdata.com.cn/Periodical/jsjyjyfz201703018SU 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.shtmlZHOU 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.012ZHANG 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/dianzixb201205024ZHANG 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.034LIAO 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/jsjxb201403001GONG 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.