### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

# MICAI 2012

A Post-Optimization strategy for CT

by

Tweet## Loreto Gonzalez-Hernandez

on 17 May 2013#### Transcript of MICAI 2012

A Post-Optimization strategy for Combinatorial testing:

test suite reduction through the identification of wild cards and merge of rows Loreto Gonzalez-Hernandez, Jose Torres-Jimenez, Nelson Rangel-Valdez and Josue Bracho-Rios Information Technology Laboratory, CINVESTAV-Tamaulipas

Km 5.5 Carretera Cd. Victoria-Soto la Marina, 87130

Cd. Victoria Tamps. Mexico Most of the enterprises nowadays depend on software systems, thus a failure on them can lead to large losses, therefore is essential to carry out the testing stage appropriately. Software Systems How is a software system constitute? Software System Software component Parameter Input value It will be ideal to test all possible inputs cases (exhaustive approach), but most times is infeasible due to time and budget.

Interaction testing is an alternative to carry out the software testing, it is based on empirical studies which showed that failures of software systems of different kinds were triggered by the interactions of a few parameters. Approaches for Software Testing Interaction testing uses combinatorial objects to indicate the test suite, a Covering Array is one of the mostly used. Interaction Testing Advantages Suppose that we need to test the functionality of a platform for smart phone cellphones apps (ANDROID), which has 8 parameters, two of them with 5 values, four with 4 y two with 3. It would required: 172,800 Interaction Testing 29 Test cases 5 x 5 x 4 x 4 x 4 x 4 x 3 x 3 = } Exhaustive Approach (interactions of size 2) = ∃ Overview Cumulative percentage of failures triggered by interactions between t parameters (Kuhn, et al., 2011). Figure When a combination in a t-tuple is covered more than once, there is the possibility to change some symbols arbitrarily such that the CA does not lose its level of coverage, these symbols are refered as wild cards. Wild Cards 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 Combinations that must appear (at least once) 2x2=4 0 0

0 1

1 0

1 1 { 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 t-tuples: (C1,C2) (C1,C3) ... (C3,C4) C1 C2 C3 C4 ... CA(6;2,4,2) { C1 C2 C3 C4 C1 C2 C3 C4 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

* * * * C1 C2 C3 C4 This matrix is still a CA, all combinations appears at least once in every pair of columns. CA(5;2,4,2) } Fixing Process 1) Wild Card Identification Algorithm (wcCA)

2) Reduction Algorithm Using Wild Cards (FastRedu) 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 ... 1 1 1 0

1 1 0 1

F F 1 1

0 1 1 1

F F 0 0

0 1 0 0 1 1 1 0

F 1 F 1

F F 1 1

F 1 F 1

F F 0 0

0 1 0 0 ... F U F F

F U F F

F F F F

F U F F

F F F F

U U U U This step looks for those combinations that are covered only once in every t-tuple { { { (C1,C2) t-tuple (C1,C3) (C3,C4) Unfixed Symbols 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 (C1,C2) F U F F

F U F F

F F F F

F U F F

F F F F

U U U U (C1,C2) 1 1 2 R1 R2 t-tuple combination #rows rows (C1,C2) 0 1 2 R4 R6 (C1,C2) 1 1 2 R1 R2 Note:

Only symbols marked as UNFIXED in the fixing process can be wild cards

For each t-tuple

For each combination that has not been covered for FIXED symbols

Stored the rows that cover such combination |ß| Merging Compatible Rows GREEDY SOLUTION R4 R1 01 11 { 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 F F F F

F U F F

F F F F

F F F F

F F F F

U U U U wild cards: 5 R1

R2

R3

R4

R5

R6 Tests every combination of two rows (r , r )

If they are compatible then

they are merge Thanks Post-optimization process

A post-optimization strategy to reduce test suites (CAS) which includes two algorithms was presented:

wcCA algorithm (Identification of wild cards)

FastRedu algorithm (Merge of rows) Results

The post-optimization process was tested with 667 CAs constructed by the state-of-the-art algorithm IPOG-F. The results show a reduction in 347 CAs (52% of the instances).

Introduction Background Proposed Approach Experimental Results Conclusions The experiment included 667 CAs previously created by the greedy algorithm IPOG-F, which are available in the NIST' repository. These CAs were subject to the reduction process. agonzalez@tamps.cinvestav.mx, jtj@cinvestav.mx, nrangelv@upv.edu.mx, jbracho@tamps.cinvestav.mx F U F F

F U F F

F F F F

F F F F

F F F F

U U U U F F F F

F U F F

F F F F

F F F F

F F F F

U U U U { |ß| A Covering Array (CA) denoted by CA(N; t, k, v) is an N x k matrix consisting of N vectors of length k with entries from {0,1,...,v-1} such that every one of the v possible vectors of size t occurs at least once in every possible selection of t columns.

The minimum number of rows required to construct a CA for an specific value of v, k and t is called Covering Array Number (CAN) which is defined by CAN = min {N | CA(N;t,k,v)} E t The proposed strategy for the reduction of a test suite

involves the use of two algorithms Test Suite Reduction Problem To address the test-suite reduction problem, researchers have investigated the use of test-suite reduction algorithms, which identify a reduced test suite that provides the same coverage for a software component according to some criterion as the original test suite. Different strategies have been implemented in order to construct Covering Arrays (CAs), but they do not guarantee optimal solutions, so many of them can be reduced by a post-optimization process. wcCA algorithm wcCA algorithm FastRedu algorithm i j Two rows are compatible if for each column they have the same symbol (or a wild card) 0 1 1 0 1

0 1 1 0 1

0 1 1 0 1 0 1 1 0 1

0 1 1 * 1

0 1 1 0 1 0 1 1 0 *

0 1 1 0 *

0 1 1 0 1 If a row only contains wild cards then

it is unnecessary, so it is deleted wcWA

& FastRedu 667 CAs 347 CAs were reduced reduction process The test suite reduction problem focuses on obtaining a reduced test suite that provides the same coverage for a software component according to some criterion as the original test suite. CA(57;2,8,6) Results

The CA(57;2,8,6) reduced its size by 15 rows, an impressive reduction if we consider that the new CA(42;2,8,6) is the best upper bound so far.

Full transcripttest suite reduction through the identification of wild cards and merge of rows Loreto Gonzalez-Hernandez, Jose Torres-Jimenez, Nelson Rangel-Valdez and Josue Bracho-Rios Information Technology Laboratory, CINVESTAV-Tamaulipas

Km 5.5 Carretera Cd. Victoria-Soto la Marina, 87130

Cd. Victoria Tamps. Mexico Most of the enterprises nowadays depend on software systems, thus a failure on them can lead to large losses, therefore is essential to carry out the testing stage appropriately. Software Systems How is a software system constitute? Software System Software component Parameter Input value It will be ideal to test all possible inputs cases (exhaustive approach), but most times is infeasible due to time and budget.

Interaction testing is an alternative to carry out the software testing, it is based on empirical studies which showed that failures of software systems of different kinds were triggered by the interactions of a few parameters. Approaches for Software Testing Interaction testing uses combinatorial objects to indicate the test suite, a Covering Array is one of the mostly used. Interaction Testing Advantages Suppose that we need to test the functionality of a platform for smart phone cellphones apps (ANDROID), which has 8 parameters, two of them with 5 values, four with 4 y two with 3. It would required: 172,800 Interaction Testing 29 Test cases 5 x 5 x 4 x 4 x 4 x 4 x 3 x 3 = } Exhaustive Approach (interactions of size 2) = ∃ Overview Cumulative percentage of failures triggered by interactions between t parameters (Kuhn, et al., 2011). Figure When a combination in a t-tuple is covered more than once, there is the possibility to change some symbols arbitrarily such that the CA does not lose its level of coverage, these symbols are refered as wild cards. Wild Cards 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 Combinations that must appear (at least once) 2x2=4 0 0

0 1

1 0

1 1 { 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 t-tuples: (C1,C2) (C1,C3) ... (C3,C4) C1 C2 C3 C4 ... CA(6;2,4,2) { C1 C2 C3 C4 C1 C2 C3 C4 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

* * * * C1 C2 C3 C4 This matrix is still a CA, all combinations appears at least once in every pair of columns. CA(5;2,4,2) } Fixing Process 1) Wild Card Identification Algorithm (wcCA)

2) Reduction Algorithm Using Wild Cards (FastRedu) 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 ... 1 1 1 0

1 1 0 1

F F 1 1

0 1 1 1

F F 0 0

0 1 0 0 1 1 1 0

F 1 F 1

F F 1 1

F 1 F 1

F F 0 0

0 1 0 0 ... F U F F

F U F F

F F F F

F U F F

F F F F

U U U U This step looks for those combinations that are covered only once in every t-tuple { { { (C1,C2) t-tuple (C1,C3) (C3,C4) Unfixed Symbols 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 (C1,C2) F U F F

F U F F

F F F F

F U F F

F F F F

U U U U (C1,C2) 1 1 2 R1 R2 t-tuple combination #rows rows (C1,C2) 0 1 2 R4 R6 (C1,C2) 1 1 2 R1 R2 Note:

Only symbols marked as UNFIXED in the fixing process can be wild cards

For each t-tuple

For each combination that has not been covered for FIXED symbols

Stored the rows that cover such combination |ß| Merging Compatible Rows GREEDY SOLUTION R4 R1 01 11 { 1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

0 0 0 0

0 1 0 0 F F F F

F U F F

F F F F

F F F F

F F F F

U U U U wild cards: 5 R1

R2

R3

R4

R5

R6 Tests every combination of two rows (r , r )

If they are compatible then

they are merge Thanks Post-optimization process

A post-optimization strategy to reduce test suites (CAS) which includes two algorithms was presented:

wcCA algorithm (Identification of wild cards)

FastRedu algorithm (Merge of rows) Results

The post-optimization process was tested with 667 CAs constructed by the state-of-the-art algorithm IPOG-F. The results show a reduction in 347 CAs (52% of the instances).

Introduction Background Proposed Approach Experimental Results Conclusions The experiment included 667 CAs previously created by the greedy algorithm IPOG-F, which are available in the NIST' repository. These CAs were subject to the reduction process. agonzalez@tamps.cinvestav.mx, jtj@cinvestav.mx, nrangelv@upv.edu.mx, jbracho@tamps.cinvestav.mx F U F F

F U F F

F F F F

F F F F

F F F F

U U U U F F F F

F U F F

F F F F

F F F F

F F F F

U U U U { |ß| A Covering Array (CA) denoted by CA(N; t, k, v) is an N x k matrix consisting of N vectors of length k with entries from {0,1,...,v-1} such that every one of the v possible vectors of size t occurs at least once in every possible selection of t columns.

The minimum number of rows required to construct a CA for an specific value of v, k and t is called Covering Array Number (CAN) which is defined by CAN = min {N | CA(N;t,k,v)} E t The proposed strategy for the reduction of a test suite

involves the use of two algorithms Test Suite Reduction Problem To address the test-suite reduction problem, researchers have investigated the use of test-suite reduction algorithms, which identify a reduced test suite that provides the same coverage for a software component according to some criterion as the original test suite. Different strategies have been implemented in order to construct Covering Arrays (CAs), but they do not guarantee optimal solutions, so many of them can be reduced by a post-optimization process. wcCA algorithm wcCA algorithm FastRedu algorithm i j Two rows are compatible if for each column they have the same symbol (or a wild card) 0 1 1 0 1

0 1 1 0 1

0 1 1 0 1 0 1 1 0 1

0 1 1 * 1

0 1 1 0 1 0 1 1 0 *

0 1 1 0 *

0 1 1 0 1 If a row only contains wild cards then

it is unnecessary, so it is deleted wcWA

& FastRedu 667 CAs 347 CAs were reduced reduction process The test suite reduction problem focuses on obtaining a reduced test suite that provides the same coverage for a software component according to some criterion as the original test suite. CA(57;2,8,6) Results

The CA(57;2,8,6) reduced its size by 15 rows, an impressive reduction if we consider that the new CA(42;2,8,6) is the best upper bound so far.