Background
Test case selection
Search-based test case selection
Multi-objective optimization TC selection
Overview of the developed work
Methods
Problem formulation
The BMOPSO-CDR algorithm
The BCMOPSO-CDRHS algorithm
Results and discussion
Structural testing
Program | Lines of code | Test suite size |
---|---|---|
Flex | 15,297 | 567 |
Grep | 15,633 | 806 |
Gzip | 8889 | 213 |
Sed | 19,737 | 370 |
Space | 6199 | 160 |
Functional testing
Metrics
Parameter study
The NGC parameter
NGC | 1 | 10 | 15 | 20 | 30 | |
---|---|---|---|---|---|---|
Flex | HV | 0.836 |
0.846
|
0.848
|
0.848
|
0.848
|
(0.004) |
(0.004)
|
(0.004)
|
(0.003)
|
(0.004)
| ||
GD | 0.003 |
0.002
|
0.002
|
0.001
|
0.001
| |
(4.6E-4) |
(4.2E-4)
|
(5.3E-4)
|
(4.8E-4)
|
(3.8E-4)
| ||
IGD | 0.003 | 0.002 |
0.001
|
0.001
|
0.001
| |
(5.3E-4) | (3.7E-4) |
(3.8E-4)
|
(3.0E-4)
|
(3.3E-4)
| ||
C |
1.0
|
0.998
|
0.996
|
0.996
|
0.996
| |
(0.0)
|
(0.006)
|
(0.012)
|
(0.046)
|
(0.018)
| ||
Grep | HV | 0.772 | 0.782 | 0.782 |
0.785
|
0.786
|
(0.005) | (0.006) | (0.004) |
(0.004)
|
(0.004)
| ||
GD | 0.002 |
0.001
|
0.001
|
0.001
|
0.001
| |
(4.2E-4) |
(3.0E-4)
|
(3.6E-4)
|
(2.6E-4)
|
(3.2E-4)
| ||
IGD | 0.002 |
0.001
|
0.001
|
0.001
|
0.001
| |
(3.6E-4) |
(4.3E-4)
|
(4.9E-4)
|
(3.3E-4)
|
(3.7E-4)
| ||
C |
1.0
|
0.999
|
0.999
|
0.996
|
0.991
| |
(0.0)
|
(0.005)
|
(0.004)
|
(0.010)
|
(0.024)
| ||
Gzip | HV | 0.953 |
0.961
|
0.963
|
0.961
|
0.963
|
(0.003) |
(0.003)
|
(0.003)
|
(0.003)
|
(0.004)
| ||
GD | 0.004 |
0.002
|
0.002
|
0.002
|
0.002
| |
(6.6E-4) |
(7.4E-4)
|
(6.3E-4)
|
(8.1E-4)
|
(0.001)
| ||
IGD | 0.004 | 0.003 |
0.002
| 0.003 |
0.002
| |
(7.2E-4) | (8.6E-4) |
(8.4E-4)
| (0.001) |
(0.001)
| ||
C |
1.0
|
0.994
|
0.986
|
0.995
|
0.996
| |
(0.0)
|
(0.018)
|
(0.035)
|
(0.022)
|
(0.013)
| ||
Sed | HV | 0.847 |
0.862
| 0.861 |
0.863
|
0.864
|
(0.004) |
(0.006)
| (0.004) |
(0.005)
|
(0.004)
| ||
GD | 0.004 |
0.003
|
0.003
|
0.002
|
0.002
| |
(0.001) |
(0.001)
|
(0.002)
|
(0.001)
|
(0.001)
| ||
IGD | 0.005 |
0.002
| 0.003 | 0.003 |
0.002
| |
(6.6E-4) |
(7.7E-4)
| (6.5E-4) | (7.6E-4) |
(5.9E-4)
| ||
C | 1.0 | 1.0 | 1.0 |
0.988
|
0.998
| |
(0.0) | (0.0) | (0.0) |
(0.043)
|
(0.009)
| ||
Space | HV | 0.938 |
0.949
|
0.949
|
0.949
|
0.949
|
(0.004) |
(0.004)
|
(0.003)
|
(0.002)
|
(0.003)
| ||
GD | 0.002 |
0.001
|
0.001
|
9.2E-4
|
9.1E-4
| |
(2.2E-4) |
(2.8E-4)
|
(3.2E-4)
|
(1.5E-4)
|
(1.8E-4)
| ||
IGD | 0.002 |
0.001
|
0.001
|
0.001
|
0.001
| |
(8.8E-4) |
(7.8E-4)
|
(7.2E-4)
|
(9.2E-4)
|
(7.7E-4)
| ||
C | 1.0 |
0.994
|
0.991
|
0.989
|
0.996
| |
(0.0) |
(0.010)
|
(0.012)
|
(0.019)
|
(0.007)
| ||
IS | HV | 0.714 |
0.719
|
0.719
|
0.719
|
0.719
|
(0.001) |
(7.0E-4)
|
(6.4E-4)
|
(5.8E-4)
|
(7.1E-4)
| ||
GD | 2.6E-4 |
1.5E-4
|
1.5E-4
|
1.4E-4
|
1.5E-4
| |
(2.4E-5) |
(1.4E-5)
|
(1.5E-5)
|
(1.1E-5)
|
(1.3E-5)
| ||
IGD | 6.1E-4 |
3.1E-4
|
3.0E-4
|
2.8E-4
|
2.7E-4
| |
(2.3E-4) |
(1.0E-4)
|
(1.1E-4)
|
(8.2E-5)
|
(9.0E-5)
| ||
C | 0.979 |
0.857
|
0.870
|
0.849
|
0.854
| |
(0.012) |
(0.040)
|
(0.036)
|
(0.049)
|
(0.047)
| ||
RS | HV | 0.910 |
0.912
|
0.912
|
0.912
|
0.912
|
(0.001) |
(3.7E-4)
|
(4.1E-4)
|
(4.2E-4)
|
(3.4E-4)
| ||
GD | 2.9E-4 | 1.8E-4 |
1.5E-4
| 1.8E-4 |
1.4E-4
| |
(5.8E-5) | (3.7E-5) |
(4.5E-5)
| (4.8E-5) |
(4.6E-5)
| ||
IGD | 0.001 |
4.1E-4
|
3.8E-4
|
3.3E-4
|
3.8E-4
| |
(7.8E-4) |
(2.2E-4)
|
(2.7E-4)
|
(1.2E-4)
|
(2.8E-4)
| ||
C | 0.781 | 0.493 |
0.417
|
0.450
|
0.439
| |
(0.099) | (0.086) |
(0.098)
|
(0.072)
|
(0.081)
|
NGC | 1 | 10 | 15 | 20 | 30 | |
---|---|---|---|---|---|---|
Flex | HV |
0.833
|
0.832
|
0.833
|
0.832
|
0.833
|
(0.003)
|
(0.003)
|
(0.003)
|
(0.002)
|
(0.002)
| ||
GD |
0.001
|
0.001
|
0.001
|
0.001
|
0.001
| |
(4.2E-4)
|
(4.5E-4)
|
(4.4E-4)
|
(2.7E-4)
|
(5.2E-4)
| ||
IGD |
0.001
|
0.001
|
0.001
|
0.001
|
0.001
| |
(2.2E-4)
|
(1.7E-4)
|
(2.2E-4)
|
(1.4E-4)
|
(2.1E-4)
| ||
C | 0.995 |
0.984
| 0.998 | 0.998 | 0.997 | |
(0.018) |
(0.027)
| (0.006) | (0.007) | (0.011) | ||
Grep | HV | 0.770 | 0.770 |
0.772
|
0.771
|
0.773
|
(0.003) | (0.003) |
(0.004)
|
(0.004)
|
(0.004)
| ||
GD |
0.001
|
0.001
|
0.001
|
0.001
|
0.001
| |
(3.6E-4)
|
(4.4E-4)
|
(4.5E-4)
|
(4.7E-4)
|
(3.3E-4)
| ||
IGD |
0.001
|
0.001
|
0.001
|
0.001
|
0.001
| |
(2.3E-4)
|
(2.7E-4)
|
(2.1E-4)
|
(2.7E-4)
|
(2.7E-4)
| ||
C |
0.992
|
0.995
|
0.996
|
0.996
|
0.995
| |
(0.015)
|
(0.013)
|
(0.013)
|
(0.009)
|
(0.010)
| ||
Gzip | HV |
0.941
|
0.943
|
0.941
|
0.942
|
0.941
|
(0.003)
|
(0.003)
|
(0.002)
|
(0.003)
|
(0.003)
| ||
GD |
0.003
|
0.003
|
0.003
|
0.003
|
0.003
| |
(9.0E-4)
|
(0.001)
|
(0.001)
|
(0.001)
|
(0.001)
| ||
IGD |
0.002
|
0.002
|
0.002
|
0.002
|
0.002
| |
(2.9E-4)
|
(3.4E-4)
|
(3.5E-4)
|
(4.2E-4)
|
(3.4E-4)
| ||
C |
1.0
|
0.996
|
0.994
|
0.990
|
0.994
| |
(0.0)
|
(0.012)
|
(0.017)
|
(0.027)
|
(0.021)
| ||
Sed | HV |
0.837
| 0.835 |
0.836
|
0.837
|
0.836
|
(0.004)
| (0.003) |
(0.004)
|
(0.005)
|
(0.004)
| ||
GD |
0.002
|
0.002
|
0.002
|
0.002
|
0.002
| |
(6.0E-4)
|
(8.5E-4)
|
(6.5E-4)
|
(9.3E-4)
|
(8.0E-4)
| ||
IGD |
0.009
|
0.009
|
0.007
|
0.009
|
0.008
| |
(0.003)
|
(0.003)
|
(0.004)
|
(0.003)
|
(0.004)
| ||
C |
0.998
|
0.996
|
0.992
|
0.990
|
0.994
| |
(0.007)
|
(0.012)
|
(0.021)
|
(0.048)
|
(0.016)
| ||
Space | HV |
0.948
| 0.946 |
0.947
|
0.947
| 0.946 |
(0.002)
| (0.002) |
(0.003)
|
(0.003)
| (0.002) | ||
GD |
0.001
|
0.001
| 0.002 |
0.001
|
0.001
| |
(2.0E-4)
|
(1.8E-4)
| (2.2E-4) |
(1.9E-4)
|
(1.3E-4)
| ||
IGD | 0.002 | 0.002 | 0.002 |
0.001
|
0.001
| |
(7.4E-4) | (7.6E-4) | (9.1E-4) |
(7.9E-4)
|
(8.2E-4)
| ||
C |
0.994
|
0.993
|
0.992
|
0.994
|
0.997
| |
(0.013)
|
(0.016)
|
(0.019)
|
(0.007)
|
(0.007)
| ||
IS | HV |
0.714
|
0.715
|
0.715
|
0.714
|
0.715
|
(0.001)
|
(0.001)
|
(0.001)
|
(0.001)
|
(0.001)
| ||
GD |
2.2E-4
|
2.1E-4
|
2.2E-4
|
2.2E-4
|
2.2E-4
| |
(2.4E-5)
|
(1.4E-5)
|
(1.5E-5)
|
(1.1E-5)
|
(1.3E-5)
| ||
IGD |
4.1E-4
|
4.0E-4
|
3.8E-4
|
4.0E-4
|
3.8E-4
| |
(1.4E-4)
|
(1.2E-4)
|
(1.0E-4)
|
(1.3E-4)
|
(1.4E-4)
| ||
C |
0.733
| 0.760 |
0.749
| 0.764 | 0.774 | |
(0.041)
| (0.028) |
(0.034)
| (0.034) | (0.038) | ||
RS | HV |
0.912
|
0.912
|
0.912
|
0.912
|
0.912
|
(5.1E-4)
|
(2.5E-4)
|
(1.9E-4)
|
(2.3E-4)
|
(1.9E-4)
| ||
GD |
2.0E-4
|
1.8E-4
|
2.0E-4
|
2.0E-4
| 2.1E-4 | |
(5.0E-5)
|
(4.5E-5)
|
(9.2E-5)
|
(4.8E-5)
| (4.2E-5) | ||
IGD |
1.9E-4
|
1.9E-4
|
1.9E-4
|
2.0E-4
|
2.0E-4
| |
(3.9E-5)
|
(3.8E-5)
|
(2.3E-5)
|
(2.8E-5)
|
(3.6E-5)
| ||
C |
0.493
|
0.515
|
0.488
|
0.486
|
0.503
| |
(0.079)
|
(0.073)
|
(0.067)
|
(0.076)
|
(0.070)
|
The HMCR and PAR parameters
Main experiment
Results
BMOPSO-CDR | BMOPSO-CDRHS | MBHS | NSGA-II | ||
---|---|---|---|---|---|
Flex | HV | 0.736 |
0.888
| 0.882 | 0.791 |
(0.004) |
(0.004)
| (0.004) | (0.013) | ||
GD | 0.026 |
0.001
| 0.006 | 0.012 | |
(0.003) |
(4.1E-4)
| (0.001) | (0.003) | ||
IGD | 0.023 |
0.001
| 0.003 | 0.017 | |
(7.8E-4) |
(4.5E-4)
| (7.3E-4) | (0.002) | ||
C | 1.0 |
0.955
| 1.0 | 1.0 | |
(0.0) |
(0.104)
| (0.0) | (0.0) | ||
Grep | HV | 0.657 |
0.821
|
0.823
| 0.712 |
(0.006) |
(0.004)
|
(0.004)
| (0.016) | ||
GD | 0.028 |
0.001
| 0.003 | 0.004 | |
(0.003) |
(4.1E-4)
| (5.7E-4) | (0.001) | ||
IGD | 0.023 |
0.002
|
0.002
| 0.015 | |
(0.001) |
(5.1E-4)
|
(3.1E-4)
| (2.4E-4) | ||
C | 1.0 |
0.963
| 0.990 | 1.0 | |
(0.0) |
(0.058)
| (0.027) | (0.0) | ||
Gzip | HV | 0.821 |
0.976
| 0.973 | 0.888 |
(0.008) |
(0.003)
| (0.002) | (0.019) | ||
GD | 0.030 |
0.001
| 0.003 | 0.010 | |
(0.004) |
(3.3E-4)
| (6.3E-4) | (0.003) | ||
IGD | 0.026 | 0.005 |
0.004
| 0.016 | |
(0.001) | (0.002) |
(0.001)
| (0.002) | ||
C | 1.0 |
0.963
| 0.998 | 1.0 | |
(0.0) |
(0.056)
| (0.006) | (0.0) | ||
Sed | HV | 0.698 |
0.908
|
0.905
| 0.769 |
(0.008) |
(0.005)
|
(0.006)
| (0.023) | ||
GD | 0.050 |
0.002
| 0.007 | 0.017 | |
(0.006) |
(0.002)
| (0.002) | (0.006) | ||
IGD | 0.034 |
0.002
|
0.002
| 0.022 | |
(0.001) |
(0.001)
|
(4.5E-4)
| (0.003) | ||
C | 1.0 |
0.957
| 0.995 | 1.0 | |
(0.0) |
(0.071)
| (0.015) | (0.0) | ||
Space | HV | 0.809 |
0.965
| 0.947 | 0.856 |
(0.008) |
(0.001)
| (0.002) | (0.017) | ||
GD | 0.019 |
7.0E-4
| 0.003 | 0.002 | |
(0.003) |
(7.7E-5)
| (0.001) | (7.4E-4) | ||
IGD | 0.018 | 0.003 |
0.001
| 0.018 | |
(0.001) | (0.001) |
(3.9E-4)
| (0.001) | ||
C | 1.0 |
0.968
| 0.983 | 0.991 | |
(0.0) |
(0.024)
| (0.018) | (0.031) | ||
IS | HV | 0.600 |
0.719
| 0.591 | 0.649 |
(0.005) |
(4.0E-4)
| (0.008) | (0.012) | ||
GD | 0.007 |
2.0E-4
| 0.002 | 8.4E-4 | |
(4.2E-4) |
(4.5E-4)
| (4.4E-4) | (2.7E-4) | ||
IGD | 0.005 |
1.9E-4
| 0.005 | 0.005 | |
(5.5E-4) |
(1.9E-5)
| (5.4E-4) | (0.001) | ||
C | 1.0 | 0.835 |
0.655
| 0.972 | |
(0.0) | (0.030) |
(0.054)
| (0.058) | ||
RS | HV | 0.802 |
0.912
| 0.846 | 0.843 |
(0.005) |
(3.7E-4)
| (0.009) | (0.017) | ||
GD | 0.012 |
2.2E-4
| 0.002 | 0.001 | |
(0.001) |
(5.0E-5)
| (7.0E-4) | (7.6E-4) | ||
IGD | 0.010 |
2.4E-4
| 0.002 | 0.012 | |
(0.001) |
(4.0E-5)
| (2.5E-4) | (0.002) | ||
C | 1.0 |
0.667
|
0.661
| 0.982 | |
(0.0) |
(0.070)
|
(0.050)
| (0.048) |