Combinatorial Interaction Testing

Combinatorial interaction testing (CIT) is a popular approach to detecting faults in highly configurable software systems. The core task is to generate a small test suite called a t-way covering array (CA), where t is the covering strength. Empirical studies suggest that most of the failures in highly-configurable systems are caused by the interaction of a limited number of t options, usually between two and six. These failures can be revealed efficiently and effectively by a t-way CA.
We developed solvers for constrained combinatorial interaction testing, aiming to generate CAs as small as possibles, while consuming reasonable short time.

Solvers for covering array generation

FastCA

A more matual tool based on FastCA can be downloaded here, for information on the tool, please refer to our tool paper:
FastCA: An Effective and Efficient Tool for Combinatorial Covering Array Generation (ICSE 2021)

FastCA is improved from our previous solver TCA by using the lightweight score computation method. Also, it utilizes a gradient descent procedure to explore the search space more intensively. It usually achieves 10 times and sometimes 100 times speed-up over other heuristic search based solvers.

Notably, the lightweight score computation method is a general technique can be used in any meta-heuristic algorithms for combinatorial interaction testing. Its low time complexity opens a door to make more algorithm ideas affordable and thus more elaborate algorithms can be developed.

Papers

  • Jinkun Lin, Chuan Luo, Shaowei Cai, Kaile Su, Dan Hao, and Lu Zhang. "TCA: An efficient two-mode meta-heuristic algorithm for combinatorial test generation (t)." ASE 2015, pp. 494-505.
  • Jinkun Lin, Shaowei Cai, Chuan Luo, Qingwei Lin, and Hongyu Zhang. "Towards more efficient meta-heuristic algorithms for combinatorial test generation." In Proceedings of ESEC/FSE 2019, pp. 212-222.
  • Jinkun Lin, Shaowei Cai, Bin He, Yingjie Fu, Chuan Luo, and Qingwei Lin. "FastCA: An Effective and Efficient Tool for Combinatorial Covering Array Generation." ICSE 2021.

    • Benchmarks

  • Real-world: This benchmark contains six real-world in-stances. Five of them generated by Cohen et al., extracted from Apache, Bugzilla, GCC, SPIN-S and SPIN-V. The other instance is TCAS, which was first introduced by Kuhn and Okun. It is a traffic collision avoidance system from Siemens suite.
  • IBM: This benchmark contains 20 real-world instances generated by or for IBM customers, including banking systems, telecommunications, healthcare, etc.
  • Synthetic: There are 30 instances in this benchmark. They were generated synthetically from the characteristics found in the five real-world instances. These instances were generated by Garvin et al.

    • Results on the real world benchmarks

    FastCA has essentially better performance than the previous state-of-the-art algorithms by other research groups, including the best greedy algorithm ACTS and the two best heuristic algorithms HHSA and CASA. The below table presents the results on real world instances. FastCA can find better solutions even with only 1/10 time limit of other solvers. Please refer to the paper for more results.

    Table 1 Comparing FastCA against state-of-the-art competitors for 3-way CCAG on the Real-world and IBM benchmarks. The time limit is set to 1000 seconds for all solvers, while FastCA is tested also with 100 seconds time limit.
    Instance FastCA (1000s) FastCA (100s) ACTS (1000s) HHSA (1000s) CASA (1000s)
    min (avg) time min (avg) time min time min (avg) time min (avg) time
    apache 133 (134.7) 716.77 141 (142.7) 79.12 173 7.92 -- >1000 245 (247.9) 920.36
    bugzilla 48 (48) 17.35 48 (48) 17.35 68 0.44 60 (60.9) 481.55 61 (64.6) 36.38
    gcc 75 (76.8) 561.74 79 (80.6) 75.44 108 9.48 -- >1000 134 (140) 943.47
    spins 80 (80) 1.17 80 (80) 1.17 98 0.37 80 (85.7) 59.55 94 (100.5) 7.14
    spinv 195 (196) 415.45 196 (197.4) 65.26 286 1.27 -- >1000 224 (233.1) 734.92
    tcas 400 (400) 0.47 400 (400) 0.47 405 0.32 400 (400) 337.88 400 (404.1) 4.27
    Banking1 45 (45) 4.11 45 (45) 4.11 58 2.07 45 (45) 9.9 45 (46.2) 0.09
    Banking2 30 (30) 0.66 30 (30) 0.66 39 0.44 30 (30) 1.1 30 (30.4) 0.35
    CommProto. 41 (41) 16.68 41 (41) 16.68 49 3.22 41 (41) 76.94 41 (42.2) 0.25
    Concurrency 8 (8) 0.31 8 (8) 0.31 8 0.51 8 (8) 7.51 8 (8) <0.01
    Healthcare1 96 (96) 0.8 96 (96) 0.8 105 0.65 96 (96) 53.61 96 (96.6) 0.3
    Healthcare2 50 (50.9) 225.47 50 (51.4) 26.74 67 1.26 51 (52.1) 23.5 53 (55.1) 6.16
    Healthcare3 151 (151.5) 325.85 151 (152.4) 48.69 209 0.92 177 (186.9) 373.89 170 (175) 237.96
    Healthcare4 238 (239) 417.3 240 (240.7) 56.61 294 1.21 320 (346.667) 725.21 278 (286.7) 835.15
    Insurance 6851 (6851) 1.74 6851 (6851) 1.74 6866 0.54 -- >1000 7027 (7156.4) 770.29
    NetworkMg. 1100 (1100) 1.14 1100 (1100) 1.14 1125 0.59 1100 (1100) 440.68 1124 (1136.8) 5.72
    Proc.Comm1 104 (104.8) 160.59 105 (105.3) 32.23 163 0.63 114 (117.6) 90.78 117 (120.7) 111.51
    Proc.Comm2 125 (125.6) 189.36 125 (126.2) 53.81 161 1.64 140 (148.2) 572.5 140 (145) 236.73
    Services 813 (815.2) 685.53 829 (834.2) 81.4 963 10.35 840 (860) 789.42 856 (894) 464.39
    Storage1 25 (25) 2.05 25 (25) 2.05 25 1.52 25 (25) 15.53 25 (25) <0.01
    Storage2 54 (54) 0.09 54 (54) 0.09 74 0.03 54 (54) 15.9 54 (55.8) 0.02
    Storage3 222 (222) 3.43 222 (222) 3.43 239 1.54 224 (225.1) 675.16 241 (245.8) 1.83
    Storage4 910 (910) 3.62 910 (910) 3.62 990 0.76 960 (960) 853.39 926 (951.6) 723.84
    Storage5 1705 (1706.9) 445.17 1707 (1710.3) 72.45 1879 2.93 -- >1000 1877 (1958.3) 971.23
    SystemMg. 45 (45) 1.65 45 (45) 1.65 60 0.49 45 (45.2) 16.6 47 (48.3) 0.3
    Telecom 120 (120) 0.57 120 (120) 0.57 126 0.53 120 (120) 12.4 120 (120.4) 0.37
    Return to homepage.