Introduction

The number of test cases required to ensure the quality of a software system grows handin-hand with its complexity, and consequently, the total test execution time increases proportionally. For large software systems, test execution time becomes increasingly critical in automated regression testing, where a large suite of tests is executed frequently on continuous integration servers.

Different approaches like test selection, test prioritization or test case reduction are typically used to speed up test execution, especially in the context of regression testing [YH12]. However, these improvements can be limited for large test suites.

Test suites are trivially parallelizable if tests are independent, that is, if one test does not rely on the system state established by a previous test and it is free of interference from other tests. An example of an interference is when two or more tests require exclusive access to a shared resource such as a database. However, one cannot always assume that these conditions hold and tests that pass when executed in a certain sequence may fail under trivial parallelization. A third, perhaps less obvious but even more important issue is what we refer to as state incompatibility. In this case, one test may leave the system in a state from which another test cannot proceed. One concrete example of this is a test that deletes data from a database that is expected by other tests. While such cases can often be handled by resetting the system under test to a known initial state, resets can be time-consuming and an efficient test execution approach should strive to minimize or even remove the need for system resets.

Although test designers may strive to create independent test cases, recent studies show that in practice tests are often not completely independent [ZJW + 14, BMDK15], while other researchers consider these useful and exploit test dependencies [HM13]. As a conse-quence, there is a need to plan and schedule the execution of complex test suites in order to avoid undesired interactions between tests and time consuming system resets. Although it is possible to create a test schedule manually, this is not viable in practice if the number of tests is large. To address this issue, we propose an approach to build test schedules automatically by analyzing known dependencies among tests and their execution time. The dependencies between the tests can be derived automatically [ZJW + 14] or defined manually [dep]. The scheduler is run before each integration testing while preparing the system under test. We aim to find the best possible groups and order of tests in each group to be distributed between a number of agents which share or do not share the same resources with the objective of reducing the total time that is required for all the tests to be executed. The other objective is to decrease the number of failed tests which are caused by the dependencies between the tests. We define the relations between the tests as a set of constraints in scheduling problems. The first objective of the work is to reduce the tests failing due to their state incompatibilities, interferences or dependencies while executing in parallel. The second objective is to minimize the test execution time of the entire test suite, by searching for the best possible ordering of tests between different agents.

Background and Related Work

Recent work exploits test case dependencies as a means for prioritization of test suites [HM13], online reduction of test suites [AMPW15], or for protocol conformance testing in the context of distributed systems [MGM15]. Other works investigate how test dependencies can be detected in order to improve the independence of test cases [GSHM15] or to shorten the test execution time by minimizing the number of database resets [HKK05]. However, none of these works investigated approaches for executing tests in parallel.

Haftmann et al. propose an approach for running test cases in parallel [HKL05]. The approach involves partitioning the test sequences between test executors and ordering the execution sequence on each executor, as an extension of their work in [HKK05], in which three scheduling strategies were proposed for resolving the test incompatibilities on database applications systems with minimum number of resets.

In the previously mentioned paper, the constraints that are taken into consideration are the incompatibility and interference constraints between the tests. However, we also cover the dependency constraint. Furthermore, the goal of reordering the tests in previous works is to reduce the system reset in order to reduce the test execution time, but we are aiming on generating a near optimal schedule which satisfy the constraint and reduce the total test execution time.

Since test scheduling optimization is a complex combinatorial optimization problem, it is computationally expensive to find an exact solution for a very large number of test cases. Therefore, we formulate it as a search problem and apply a highly adaptive online optimization [HLS + 13] approach called Ant Colony Optimization (ACO) [DG97] to find a nearoptimal solution in polynomial time. There are a number of ant algorithms, such as, Ant System (AS), Max-Min AS (MMAS), and Ant Colony System (ACS) [DDCG99] [DG97]. ACS [DDCG99] was introduced to improve the performance of AS and it is currently one of the best performing ant algorithms. Therefore, in this paper, we apply ACS to the test scheduling optimization problem.

The Test Scheduling Problem

In this section, we represent the problem of test scheduling by defining the dependencies, interference and state incompatibilities between the tests. We assume that we have at our disposal one or more test environments (T E) that can execute test cases. Each T E has a number of agents (AG). Each AG can run one test case at a time, in parallel with the other AGs. The AGs in a given T E have a shared system under test and state (memory, file system, database), while each T E is isolated from the other T Es and cannot collaborate or interfere with each other.

In Figure 2 we represent an abstraction of the problem by having two T Es. The first test environment T E 1 includes two AGs while the second test environment T E 2 contains three AGs. The number of test cases to be executed are 13 and each sequence of tests that are scheduled for each AG are represented in front of the agent with respecting the order. In this example, test 3 depends on test 1 and test 2 while test 9 is dependent on test 1 and test 8 ; and test 8 has interference with test 1 and test 2 . Furthermore, test 10 has state incompatibility with test 6 and interference with test 9 . The maximum execution time represents the time when all tests are completely executed on the AGs. The example constraints between the tests are represented in Figure 1. The notations that are used in Figure 1 are explained later in this section.

The schedule for two different tests running in the same agent cannot overlap. Furthermore, in the case of test interference, we cannot schedule two tests interfering simultaneously in the same TE. We represent the test interference as a relation G inf where G inf = (T C, E inf ) where T C is the set of tests and E inf ⊆ T C × T C. It is assumed that tests share resources if they are executed on the same test environment.

(t 1 , t 3 ) ∈ E dep , (t 2 , t 3 ) ∈ E dep (t 1 , t 9 ) ∈ E dep , (t 8 , t 9 ) ∈ E dep (t 1 , t 9 ) ∈ E inc , (t 10 , t 9 ) ∈ E inf (t 1 , t 8 ) ∈ E inf , (t 2 , t 8 ) ∈ E infAG 1 AG 2 AG 3 AG 4 AG 5 T E 1 T E 2 0 tG inc = (T C, E inc ) , E inc ⊆ T C × T C.

To optimise the test execution time, we need to minimise the maximum execution time of tests on the agents. Given the defined constraints the goal is to minimise the finishing time of each test which cause the minimum ending time of all the tests in each agent. This value is described as T ET or overall test execution time. By minimising T ET , we actually minimise our objective which is the maximum execution time of tests.

ACS-Based Test Scheduling Optimization Algorithm

In this section, we present our ACS-based Test Scheduling Optimization algorithm (ACS-TSO). ACO is a multi-agent approach to difficult combinatorial optimization problems, such as, traveling salesman problem and network routing [DDCG99]. It is inspired by the foraging behavior of real ant colonies. While moving from their nest to the food source and back, ants deposit a chemical substance on their path called pheromone. Other ants can smell pheromone and they tend to prefer paths with a higher pheromone concentration. Thus, ants behave as agents who use a simple form of indirect communication called stigmergy to find better paths between their nest and the food source. It has been shown experimentally that this simple pheromone trail following behavior of ants can give rise to the emergence of the shortest paths [DDCG99]. It is important to note here that although each ant is capable of finding a complete solution, high quality solutions emerge only from the global cooperation among the members of the colony who concurrently build different solutions.

In the context of test case schedule, each test case is allocated to an agent. Therefore, ACS-TSO makes a set of tuples T , where each tuple t ∈ T consists of two elements: test case tc, and agent ag t := (tc, ag)

The output of the ACS-TSO algorithm is a test case schedule plan Ψ, which, when enforced, would result in a reduced overall test execution time. Thus, the objective function for the proposed ACS-TSO algorithm is

minimize f (Ψ) := max s ∈ ag {T ET s } (2)

where Ψ is the test case schedule plan and T ET s is the test execution time on ag. Since the main objective of test case schedule is to minimize the overall test execution time, the objective function is primarily defined in terms of test execution time T ET on each ag.

Each of the nA ants uses a state transition rule to choose the next tuple to traverse. According to the following rule, an ant k chooses a tuple s to traverse next by applying

s := arg max u ∈ T k {[τ u ] • [η u ] β } (3)

where τ denotes the amount of pheromone and η represents the heuristic value associated with a particular tuple. β is a parameter to determine the relative importance of the heuristic value with respect to the pheromone value. The expression arg max returns the tuple for which [τ ] • [η] β attains its maximum value. T k ⊂ T is the set of tuples that remain to be traversed by ant k. The heuristic value η s of a tuple s is defined as

η s :=      (T ET ag ) −1 • ∝ tc , if |D tc | = 0 |D tc |/|D all |• ∝ tc , if T ET ag = 0 |D tc |/|D all | • (T ET ag ) −1 • ∝ tc else (4) ∝ tc := T ET tc tc ∈ T C T ET tc (5)

where D tc is the set of dependencies of test case tc in tuple s and T ET ag is the current test execution time of ag in tuple s. The heuristic value η is based on the product of the number of dependencies of the test case and the multiplicative inverse of the current test execution time of the agent in tuple s. Therefore, the tuples in which the test case has a higher number of dependencies and the agent has a shorter current test execution time receives the highest heuristic value. Moreover, in the calculation of heuristic value, we consider the execution time of each test in proportion of the execution time of all the tests, in which a test with higher execution time will get a higher heuristic value. The heuristic value favors dependent test cases over independent test cases. Therefore, a test case with a higher number of dependencies receives higher heuristic value than a test case with fewer dependencies. Similarly, the main reason for favoring agents with a shorter current test execution time is to minimize the overall test execution time.

Pheromone Distribution

The stochastic state transition rule in (3) prefers tuples with a higher pheromone concentration which leads in a reduced overall test execution time. ( 3) is called exploitation [DG97].

It chooses the best tuple that attains the maximum value of [τ ] • [η] β . In addition to the stochastic state transition rule, ACS also uses a global and a local pheromone trail evaporation rule. The global pheromone trail evaporation rule is applied towards the end of an iteration after all ants complete their test suite schedule plans. It is defined as

τ s := (1 − α) • τ s + α • ∆ + τs , if s / ∈ Violations (1 − 3 * α) • τ s + α • ∆ + τs , if s ∈ Violations (6)

where ∆ + τs is the additional pheromone amount that traditionally is given only to those tuples that belong to the global best test schedule plan Ψ + in order to reward them. However, we only add the additional pheromone to the subset of tuples that contribute to the global best test schedule plan and did not violate the constraints. Moreover, we define another global updating rule for the violated tuples to have higher decay pheromone in compared to the tuples that were not existed in the solution. The additional pheromone is defined as

∆ + τs := f (Ψ + ), if s ∈ Ψ + ∧ s / ∈ Violations 0, otherwise(7)

α ∈ (0, 1] is the pheromone decay parameter, and Ψ + is the global best test schedule plan from the beginning of the trial.

The local pheromone trail update rule is applied on a tuple when an ant traverses the tuple while making its test schedule plan. It is defined as

τ s := (1 − ρ) • τ s + ρ • τ 0(8)

where ρ ∈ (0, 1] is similar to α and τ 0 is the initial pheromone level, which is computed as the multiplicative inverse of the execution time of all the test cases. The pseudocode of the proposed ACS-TSO algorithm is given in Figure 4. The algorithm makes a set of tuples T using (1) and sets the pheromone value of each tuple to the initial pheromone level τ 0 by using (9) (line 2). Then, it iterates over nI iterations (line 3), where each iteration i ∈ nI creates a new generation of nA ants that concurrently build their test schedule plans (lines 4-24). Each ant k ∈ nA iterates its loop until all test cases in T C are allocated (lines 6-23).

τ 0 := ( tc ∈ T C T ET tc ) −1 (9)Ψ + := ∅, P := ∅ 2: ∀t ∈ T |τt := τ 0 3: for i ∈ [1, nI] do 4: for k ∈ [1, nA] do 5: Ψ k := ∅ 6: while all tc ∈ T C

Afterwards, based on the state transition rule in (3) each ant chooses a tuple t to traverse next (line 7). The local pheromone trail update rule in (8) and ( 9) is applied on t (line 8).

If ant k has not already allocated tc in t and tc is an independent test case, t is added to the ant-specific test schedule plan Ψ k if it cause no incompatibility and no interference in the solution and the test execution time of agent ag in t, T ET ag , is updated to reflect the impact of the test case schedule (line 18-21). However, if tc in t is a dependent test case (line 10), it is essential to allocate all test cases on which tc is dependent on the same test environment before allocating tc on ag in t. Therefore, the algorithm uses the set of test cases on which tc in t is dependent denoted as D tc from (4)(line 11-16).

However, to prevent multiple scheduling of the same test cases on the same test environment, the algorithm removes any test cases from D tc which are already allocated to ag in t (line 12). Then, it adds all tuples to the ant-specific test schedule plan Ψ k where tc is in D tc and ag is the same as in t (line 13). At this point, it is possible that a test case in D tc may be allocated to more than one server. Such a situation may arise when more than one dependent test cases are dependent on the same test case(s). (line 18-21).

Afterwards, when all complete their test schedule plans, all ant-specific test schedule plans are added to the set of test schedule plans P (line 24-26), each test schedule plan Ψ k ∈ P is evaluated by applying the objective function in (2), the thus far global best test schedule plan Ψ + is selected (line 28), and the global pheromone trail update rule in (6) and ( 7) is applied on all tuples (line 29). Finally, when all iterations i ∈ nI complete, the algorithm returns the global best test schedule plan Ψ + (line 31).

Conclusions and Future Work

In this paper, we presented a novel approach for scheduling tests in parallel. The aim is to optimize the execution time of the tests in a test suite while satisfying incompatibility, dependency and interference constraints between the tests. In order to decrease the execution time we are looking for the best possible partitioning of tests in a number of groups and reordering of tests in each group to reduce the false positive and false negative test execution results. Since computing the exact solution is impractical for a large number of tests, we proposed a metaheuristics based approach to achieve an approximate solution in polynomial time. The time complexity of our proposed algorithm is not linear, however, the algorithm can be parallelised to accelerate the execution time. Currently, we require the algorithm to be run before each integration to take the possible modification of tests into consideration. We implemented the proposed algorithm in a Java based framework.

There is a difference between scheduling the tests and the traditional resource constrained scheduling that required us to propose a more general scheduling strategy rather than using one of the known algorithms. There is no notion of state in performing the tasks in resource constrained scheduling. If a task has been performed once, it will not be necessary to be performed again. However, in test scheduling, the state achieved on a test environment is important for the other tests. In this case, it is not enough that test has been executed before on another environment.

In the proposed approach, we defined the interference and incompatibility as hard constraints in which should be satisfied while the solution is constructed, and the dependency constraint as a soft constraint in which we aim at reducing in the next cycles. Moreover, we define the objective function to reduce the execution time of tests. For the future work, we may focus on incorporating SMT (Satisfiability Modulo Theories) solvers to tackle the problem to achieve an optimal schedule.