Ilona Bluemke
email: i.bluemke@ii.pw.edu.pl

Artur Rembiszewski

Dataflow testing of Java programs with DFC

Keywords:

The objective of this paper is to present a tool supporting dataflow coverage testing of Java programs. Code based ("white box") approach to testing can be divided into two main types: control flow coverage and data flow coverage methods. Dataflow testing was introduced for structural programming languages and later adopted for object languages. Among many tools supporting code based testing of object programs, only JaBUTi and DFC (Data Flow Coverage) support dataflow testing of Java programs. DFC is a tool implemented at the Institute of Computer Science Warsaw University of Technology as an Eclipse plug-in. DFC finds all definition-uses (def -u) pairs in tested unit and provides also the def -u graph DUG for methods. After the execution of tests the information which def -u pairs were covered is shown. An example of usage of DFC and the comparison with JaBUTi data flow testing tool of Java program is also presented.

Introduction

One of the key issues in developing high quality software systems is effective testing. Popular approaches to testing include "black box" and "white box" [START_REF] Bezier | Software System Testing and Quality Assurance[END_REF][START_REF] Binder | Testing Object Oriented Systems[END_REF]. In white box approach the test cases can be derived from the code of the unit under test. Code based approach can be divided into two main types: data flow coverage methods [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF][START_REF] Harrold | Performing Data Flow Testing on Classes[END_REF][START_REF] Harold | Interprocedural Data Flow Testing[END_REF][START_REF] Vincenzi | Coverage Testing of Java Programs and Components[END_REF][START_REF] Malevris | The Collateral Coverage of Data Flow Criteria When Branch Testing[END_REF] and control flow coverage e.g. [START_REF] Woodward | On the Relationship Between Two Control-flow Coverage Criteria: All JJ-paths and MCDC[END_REF]. In dataflow testing relationships between data are used to select the test cases. This approach was introduced for structural programming languages [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF] and later adopted for object languages [START_REF] Harrold | Performing Data Flow Testing on Classes[END_REF][START_REF] Harold | Interprocedural Data Flow Testing[END_REF][START_REF] Vincenzi | Coverage Testing of Java Programs and Components[END_REF]. Although experiments show [START_REF] Chen | Testing Object-Oriented Programs An Integrated Approach[END_REF] that dataflow testing applied to object programs can be very effective this approach is not widely used for object programs. Among many tools supporting code based testing of object programs, only JaBUTi [START_REF]JaBUTi Homepage[END_REF] supports dataflow testing of Java programs. At the Institute of Computer Science, Warsaw University of Technology, a tool, called DFC -Data Flow Coverage, for dataflow testing of Java program was implemented. DFC is implemented as an Eclipse plug-in so can be used with other testing tools available in Eclipse environment.

The objective of this paper is to present dataflow coverage testing of Java programs supported by DFC. DFC, presented in Section 3, finds all definition-uses (def -u) pairs in tested unit (Section 2) and provides also the def -u graph (DUG) for methods. The basics of dataflow testing are described in Section 2. After the execution of test, the tester is provided with the information which def -u pairs were covered so (he or she) can add new tests for not covered pairs. The tester decides which methods are changing the state of an object. Such approach is novel and not available in other testing tools. In Section 4 an example is used to explain the data flow coverage testing and to show some advantages of DFC. Section 5 contains some conclusions.

Dataflow Testing

Dataflow testing is one of "white box" techniques, it means that the test cases are derived from the source code. In dataflow testing [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF][START_REF] Harrold | Performing Data Flow Testing on Classes[END_REF] the relations between data are the basis to design test cases. Different sub-paths from definition of a variable (assignment) into its use are tested. A definition-use pair (def -u) is an ordered pair (d, u), where d is a statement containing a definition of a variable v, and u a statement containing the use of v or some memory location bound to v that can be reached by d over some program path. Test criteria are used to select particular definition-use pairs. A test satisfies def -u pair, if executing the program with this test causes traversal of a subpath from the definition to the use of this variable v without any v redefinition. A def -u pair is feasible, if there exists some program input that will cause it to be executed. Data-flow testing criteria [START_REF] Bezier | Software System Testing and Quality Assurance[END_REF] use the def -u graph (DUG), which is an extension of the control-flow graph (CFG) with information about the set of variables defineddef () and useduse() in each node/edge of the CFG. Many def -u criteria have been proposed and compared [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF][START_REF] Harrold | Performing Data Flow Testing on Classes[END_REF][START_REF] Vincenzi | Coverage Testing of Java Programs and Components[END_REF]. One criterion, called all-defs states, that for each DUG node i and all variables v, v 2 def (i) (defined in this node) at least one path hi, ji is covered. In node j this variable is used v 2 use(j) and on this path variable v is not redefined.

The first dataflow technique [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF] was proposed to structural programming languages and was not able to detect dataflow interactions that arise when methods are invoked in an arbitrary order. In [START_REF] Harold | Interprocedural Data Flow Testing[END_REF] an algorithm called PLR, was proposed. PLR finds def -u pairs if the variable definition is introduced in one procedure, and the variable usage is in called or calling procedures. The algorithm works on inter-procedural control flow graph built from control flow graphs of dependent procedures. This method can be adapted to global variables, class attributes and referenced method arguments in testing object programs.

For object programs three levels of dataflow testing were proposed in [START_REF] Harrold | Performing Data Flow Testing on Classes[END_REF]:

-Intra-method -testing, based on the basic algorithm [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF], is performed on each method individually; class attributes and methods interactions can not be taken into account.

-Inter-method -tests are applied to public method together with other methods in its class that it calls directly or indirectly. def -u pairs for class attributes can be found in this approach. -Intra-class -interactions of public methods are tested, when they are called in various sequences. Since the set of possible public methods calls sequences is infinite, only a subset of it is tested.

For each of the above described testing levels appropriate def -u pairs were defined i.e. intra-method, inter-method and intra-class.

Related Work

The process of testing software is extremely expensive in terms of labor, time and cost so many tools supporting this process have been developed. Many of these tools are standalone applications e.g. JaBUTi [START_REF]JaBUTi Homepage[END_REF], Emma [START_REF][END_REF], PurifyPlus [START_REF] Purifyplus | IBM Rational[END_REF], some are Eclipse plug-ins e.g.: EclEmma [13], TPTP [START_REF]TPTP: Eclipse Test & Performance Tools Platform Project[END_REF]. Tools supporting "white box" testing are often dedicated to a programming language e.g. to C - [START_REF] Horgan | A Data Flow Coverage Testing Tool for C[END_REF] or to Java - [START_REF][END_REF]. Tools providing information about code coverage are often integrated with CASE tools e.g. RSA (Rational Software Architect version 7.5) [START_REF]Rational Software Architect[END_REF] or with programming environments e.g. Visual Studio C++ [17].

The majority of tools supporting "white box" testing are code (instruction) coverage analyzers (e.g. PurifyPlus, TPTP, RSA, EclEmma, Emma). They provide information about line, methods, class, package, file or even project coverage. The information is hierarchically ordered. Usually not covered code is displayed in red. These tools are able to store information concerning separate test cases and later produce a summary report for whole test suite.

We were able to find only one tool, named JaBUTi (Java Bytecode Understanding and Testing) [START_REF]JaBUTi Homepage[END_REF], supporting dataflow testing of Java programs. This tool is able to analyze code coverage and dataflow coverage as well. JaBUTi analyzes following criteria based on DUG def -u graph:

Control flow coverage:

-All-Nodes-ei -every node of the DUG graph, reachable through an exceptionfree path, is executed at least once. -All-Nodes-ed -every node of the DUG graph, which can be reached only if Java exception was thrown, is covered. -All-Edges-ei -all DUG edges, except edges for which Java exception are called, are covered. -All-Edges-ed -all DUG edges which can be reached only if Java exception was thrown were covered.

Dataflow coverage:

-All-Uses-ei -all-uses criterion is fulfilled, paths throwing Java exception are not covered. -All-Uses-ed -all-uses criterion is dedicated to paths throwing Java exception.

The abbreviations ei and ed mean accordingly exception independent and exception dependent. Fulfilling two criterions: All-Nodes-ei and All-Nodes-ed is equivalent to instruction coverage, fulfilling criterions All-Edges-ei and All-Edges-ed is equivalent to conditions coverage and both All-Uses-ei with All-Uses-ed guarantees all-uses dataflow coverage [START_REF] Vincenzi | Coverage Testing of Java Programs and Components[END_REF].

Dataflow testing of object programs can reveal many errors. An experiment described in [START_REF] Chen | Testing Object-Oriented Programs An Integrated Approach[END_REF], shows, that in testing C++ programs using dataflow methods and information about polymorphism and inheritance, the number of detected errors was four times greater than in other code coverage methods i.e. instructions and conditions coverage. The results of this experiment motivated us to build a tool for dataflow testing of Java programs presented in next section.

DFC -a Tool for Dataflow Testing

Dataflow testing can not be applied in isolation so we decided to implement a tool supporting this approach, DFC -Data Flow Coverage (Fig. 1), as an Eclipse plug-in. In Eclipse Java programming environment and testing tools e.g. JUnit [START_REF]JUnit[END_REF] are available. DFC finds all def -u pairs in testing Java code and after test provides the tester information which def -u pairs were covered. Based on this information tester can decide which coverage criteria should be used and add appropriate test cases. In preparing test cases tester can also use def -u graph (DUG) for a method provided by DFC. In object languages the dataflow testing ideas proposed [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF] for structural languages must be modified. One of the main problems which must be solved is the identification which method is able to modify the object state and which one is using it only. In DFC def -u pairs are intra-method. Definitions of class attributes are located in the first node of DUG graph of tested method. The first node of DUG also contains definitions of arguments of tested method. Definitions of variable x are e.g.:

int x; Object x; x = 5; x = y;

x = new Object(); x = get_object(param); x is an object and a state modifying method is called in its context:

x.method1(); x is an object and one of its attributes is modified: x.a = 5;

An instruction is using a variable x e.g.:

its value is assigned: w = 2 * x; x++; x is an object and an reference is used in an instruction: w = x; method1(x); if (x == null) x is an object and a method using state of this object is called in its context:

x.method1(); x is an object and one of its attributes is used in an instruction: w = 2 * x.a;

In DFC tester may decides which method is defining and which one is using object state. Exemplary screen used while setting methods properties is given in Fig. 2. Initially all methods are assumed as modifying and using object state.

In Fig. 3 the main parts of DFC and its collaboration with Eclipse environment are presented. The modules of DFC are denoted by bold lines. The input for DFC is the 4 -marked methods as modifying/using object state.

Java source code (SRC in Fig. 3). Module Knowledge base analyses the source code and generates the list of classes and methods. On this list tester can mark methods as modifying or using object state (Fig. 2). The module Instrumentation instruments source code (adds extra instructions needed for finding dataflow coverage) and builds def -u graph (DUG). To instrument the code user should press the instrumentation button shown in Fig. 4. Example of instrumented code is given in Table 1. DUG contains information concerning control flow, variable definitions and usage in its nodes. DUG is the input for module Visualization, drawing the graph, and Requirements -finding all def -u pairs. The detailed description how the pairs are being determined is given in [START_REF] Rembiszewski | Data Flow Coverage of Object Programs[END_REF]. The algorithm is not able to deal with variable aliasing. The instrumented code should be compiled and run in Eclipse environment. The extra code added by Instrumentation module sends data concerning the pair coverage to DFC.

Module Analyzing is locating covered and not covered def -u pairs in tests. Results of this module are presented in Fig. 5. Other information on DFC implementation can be found in [START_REF] Rembiszewski | Data Flow Coverage of Object Programs[END_REF].

Example

In this section some functions of DFC are shown on a small example. In Table 2 Java source code calculating x y is given. This implemented algorithm was used by Rapps and Weyuker in [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF] as an example to present the data flow coverage method.

According to introduced in [START_REF] Bezier | Software System Testing and Quality Assurance[END_REF] definitions and usage of variables, for variable pow (code in Table 2) definitions can be found in lines: 15, 18, 24 and for variable z in: 14, 20, 23, 28. DUG graph is presented in Fig. 6.

In Table 3 pairs def -u are given for variables pow and z. These pairs are represented as a pair of numbers (n def , n use ), where n def denotes the number of a line containing variable definition and n use represents the number of line containing the usage of variable. These pairs can be used to find appropriate data flow coverage criterion. In Table 4 the algorithm from Table 2 is rewritten using object variables. Method calculate uses arguments compatible with interface Numb. This interface may be implemented in classes for different types of numbers so the algorithm in class exponent is general. Writing this method we were trying to keep the line numbering as in Table 2 to make the comparison easier. For code in Table 4 the definitions are following: for variable pow -line 15 and for variable z -line 14. These variable definitions were calculated according to dataflow coverage criterion proposed in [START_REF] Harrold | Performing Data Flow Testing on Classes[END_REF]. Such criterion is used in JaBUTi tool. Our DFC tool may be used to find DUG graph. Implicit DFC setting recognizes all methods of Numb interface as not modifying object state and using it. The DUG is presented in Fig. 7 and definition-use pairs for this piece of code are given in Table 5.

Analyzing def -u pairs from Table 5 we can notice that not all such pairs were identified. The state of object (code in Table 4) is modified by calls of methods not only by assignment to an object variable. Instructions in lines 18 and 28 are not treated as definitions of variable pow but as a method call. Assignment to analyzed variables (pow and z) is made only once, so some def -u pairs, with definitions in following lines were not detected. The differences can be observed on DUG graphs in Fig. 7 and8.

JaBUTi identifies set of pairs def -u as shown in Table 5 and above we proved that sometimes this tool is not able to correctly identify all def -u pairs. As variable defini- tions should be treated also the calls of following methods: negate, multiplyBy, invers, decrement, setValue (according to the concept of Numb interface). All def -u pairs for code given in Table 4 will be correctly detected by our DFC tool after setting appropriate options. The above indicated methods should be marked as modifying object state. These methods, except setValue, should be also marked as using the state of object. After setting appropriate methods attributes, described above, DFC will also find definitions for variable pow in lines: 15, 18, 24, and for variable z in lines: 14, 20, 23, 28. Afterwards DFC finds def -u pairs shown in Table 6. It is worth noticing that the definition of variable z in line 14 can not be reached by any usage of this variable. The DUG graph obtained after setting appropriate methods as defining/using object state is presented in Fig. 5 and DFC configuration window in Fig. 2.

Our approach based on setting of methods attributes as modifying/using object state enabled the correct identification of all def -u pairs in the code (Table 4), the same as in structural code given in Table 2. techniques and, to our best knowledge, none of them provides dataflow coverage testing. In DFC tester can design tests to achieve e.g. def -u or all-uses coverage criteria which also guarantee instruction coverage [START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF].

In DFC tester can identify defining and using methods (Fig. 3). However this process is time consuming, we are not going to make it fully automatic. To identify if a method is defining or using object state, the analysis of the source code must be performed. For simple classes this analysis may be automatic but in complex, industry programs, many libraries are used so the access to the source code is limited. Decompilation of the library code, preceding the analysis process, might be a solution. Such approach needs additional code instrumentation and re-execution of test cases and we 4 with marked methods as modifying object state. think it is not worthy to implement it. To simplify the implementation of DFC we also assumed to ignore variable aliasing.

In JaBUTi [START_REF]JaBUTi Homepage[END_REF] (Subsect. 2.1) every call of a method is treated as using object state. In DFC tester can determine methods as modifying or/and using object state. This approach is novel and is not implemented in other data flow testing tools. In Section 4 we have demonstrated by example, that for some programs the identification of methods defining object's state enables to find more errors.

Finally, we outline the direction for our future research. An interesting and important study would be to apply DFC to industry projects to evaluate the cost and benefits of dataflow based criteria in testing Java programs. In addition, we want to extend the intra-method testing criteria to wider, inter-method level, so more errors could be detected.

Fig. 1 .

 1 Fig. 1. DFC menu.

Fig. 2 .

 2 Fig. 2. DFC configuration screen for code from Table4-marked methods as modifying/using object state.

Fig. 3 .

 3 Fig. 3. Process of testing with DFC.

Fig. 4 .

 4 Fig. 4. Make instrumentation button in Eclipse with DFC.

Fig. 5 .

 5 Fig. 5. DFC screen presenting coverage.

Fig. 8 .

 8 Fig. 8. DUG graph for source code from Table4with marked methods as modifying object state.

Table 1 .

 1 Example of instrumented code.

	if (addVat)	44) dfc_runtime_report.add(4);
	bill.add(vatAmount);	45) if (addVat) {
		46)	bill.add(vatAmount);
		47)	dfc_runtime_report.add(5);
		48) }

Table 2 .

 2 Java code for x y calculation.

	11) public class exponent_RW {
	12)
	13) public static double calculate(double x/ * base * /,
		int y/ * exponent * /) {
	14)	double z; //result
	15)	int pow = y;
	16)
	17)	if (y < 0)
	18)	pow = -pow;
	19)
	20)	z = 1;
	21)
	22)	while (pow!=0) {
	23)	z = z * x;
	24)	pow = pow -1;
	25)	}
	26)
	27)	if (y < 0)
	28)	z = 1 / z;
	29)
	30)	return z;
	31) }
	32) }

Table 3 .

 3 def -u pairs for code from Table2.

	variable def-usage pairs
	pow	(15,18), (15,22), (15,24), (18,22), (18, 24), (24,22), (24,24)
	z	(20,23), (20,28), (20,30), (23,23), (23,28), (23,30), (28,30)

Table 4 .

 4 Object code for code in Table2.

	11) public class Exponent_Obj {
	12)
	13) public static Numb calculate(Numb x/ * base * /,
		Numb y/ * exponent * /) {
	14)	Numb z = NumbFactory.createTypeOfResult(
		x.getClass(), y.getClass()); //result
	15)	Numb pow = y.clone();
	16)
	17)	if (y.isNegative())
	18)	pow.negate();
	19)
	20)	z.setValue(1);
	21)
	22)	while (pow.isNotZero()) {
	23)	z.multiplyBy(x);
	24)	pow.decrement();
	25)	}
	26)
	27)	if (y. isNegative())
	28)	z.inverse();
	29)
	30)	return z;
	31) }
	32) }

Table 5 .

 5 def -u pairs for code from Table4, DUG graph in Fig.4.

	variable def-usage pairs
	pow	(15,18), (15,22), (15,24)
	z	(14,20), (14,23), (14,28), (14,30)

Table 6 .

 6 def -u pairs -code from Table4, marked methods modifying object state. Fig.6. DUG graph for source code from Table2. that may not be uncovered by black box testing. The detected errors depend on the test cases designed by a programmer, DFC checks, if specific paths derived from test cases are covered. In Eclipse environment there are other tools available for testing Java programs, some of them are listed in Subsect. 2.1. These plug-ins use different testing

	variable def-usage pairs
	pow	(15,18), (15,22), (15,24), (18,22) , (18,24), (24,22) ,(24,24)
	z	(20,23), (20,28), (20,30), (23,23), (23,28), (23,30), (28,30)
	5 Conclusions
	Many authors e.g. [1] suggest that effective testing can be achieved if different testing
	approaches e.g. functional and structural are used. In the development of high quality
	software systems thorough testing can be the crucial issue. In this paper we present
	DFC, an Eclipse plug-in, designed and implemented at the Institute of Computer Sci-
	ence Warsaw University of Technology, supporting dataflow testing of Java methods.
	By supporting dataflow testing of Java classes we provide opportunities to find error

Fig. 7. DUG graph for source code from Table

4

.

Acknowledgments

The authors would like to acknowledge interesting remarks given by three anonymous reviewers.


Mariusz Bedla
email: m.bedla@tu.kielce.pl

Krzysztof Sapiecha

Scalable Store of Java Objects Using Range Partitioning

Keywords: object store, scalability, SDDS, RP*, Java

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Object Store (OS) is one of the most important components of Object-Oriented Database Management System (OODBMS) [START_REF] Lobry | The VIRTUOSE Distributed Object Store[END_REF]. OS manages physical objects. These are records and may be seen as tables of bytes.

OS should allow for storing and maintaining huge number of objects. As such OS requires powerful and scalable computer platform. A multicomputer could be such a platform. A multicomputer applies parallel architecture shared-nothing [START_REF] Stonebraker | The Case for Shared Nothing[END_REF] which is the most scalable for very large databases [START_REF] Lo | GeMDA: A Multidimensional Data Partitioning Technique for Multiprocessor Database Systems[END_REF]. In such an architecture every computer owns local memory and disk, and acts as a server for data [START_REF] Dewitt | Parallel Database Systems: The Future of High Performance Database Systems[END_REF]. All the computers are connected through a fast network. A communication between the computers is based on message passing.

The question arises how to distribute data among servers of a multicomputer. There are three basic partitioning schemes that might be used [START_REF] Dewitt | Parallel Database Systems: The Future of High Performance Database Systems[END_REF]:

round-robin partitioning where data are partitioned according to function: id mod n, where n is the number of servers, hash partitioning where data are partitioned according to a hash function, and range partitioning where data are partitioned according to their ranges.

SDDS is a file of records, a file which expands on servers of a multicomputer. The main goal of SDDS file is to store a huge number of records and also to make an access to these records fast and dependable for many clients. Records are stored in so called buckets localized in main memories of the servers. A capacity of each of the buckets is limited. If a bucket's load reaches some critical level, it performs a split. A new bucket is created then on another server and typically a half of data from the splitting bucket is moved into a new one.

Distributed Object-Oriented Database Management Systems use fragmentation and allocation schemes. These schemes reduce data transfers, not-local data references, irrelevant data access and increase concurrency [START_REF] Ezeife | Distributed Object-based Design: Vertical Fragmentation of Classes[END_REF][START_REF] Barker | A Graphical Approach to Allocating Class Fragments in Distributed Objectbase Systems[END_REF]. They may rely on many factors like a structure of a class, a frequence and a type of an access, etc. On the contrary in the SDDS a placement of an object depends only on a key of the object.

There are numerous architectures of SDDS file such as RP* [START_REF] Litwin | RP*: A Family of Order Preserving Scalable Distributed Data Structures[END_REF], LH* [START_REF] Litwin | LH*-A Scalable, Distributed Data Structure[END_REF], DDH [START_REF] Devine | Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm[END_REF], etc. The paper concerns a development of object oriented version of RP*N architecture to store Java objects in serialized form (OORP*N). Such an implementation may be used as a part of distributed store of Java objects

The paper is organized as follows. Motivation to this research is given in the next section. An architecture of object-oriented version of RP* (OORP*) is introduced in Section 3. In Section 4 its implementation for Java objects is given. In Section 5 a comparison of the implementation with object serialization on a disk and a main-memory collection are presented. Section 6 concludes the research.

Motivation

Not all SDDS architectures which are suitable for relational databases could be useful for object-oriented databases. These architectures in which it is assumed that a size of every record is the same are useless, because objects can contain tables that can results in various sizes of objects of the same class. Selection of data from a relational database bases on operations on primary and foreign keys. Relations between objects can be more complicated. SDDS usually stores all data in main memory, which is not durable. To achieve persistence of objects a backup on hard drive is required.

On the other side, scalability, high speed of operation and fault tolerance are important advantages of SDDS [START_REF] Litwin | LH*-A Scalable, Distributed Data Structure[END_REF][START_REF] Litwin | RP*: A Family of Order Preserving Scalable Distributed Data Structures[END_REF][START_REF] Litwin | High-Availability LH* Schemes with Mirroring[END_REF][START_REF] Sapiecha | Fault-tolerant Protocols for Scalable Distributed Data Structures[END_REF]. Storing an object-oriented database in SDDS should increase performance of OODBMS and make OODB applications scalable. Developing an architecture preserving all advantages of SDDS but efficiently applicable to store of objects would be very useful.

There are few well known implementations of SDDS:

-AMOS-SDDS: scalable distributed system combining AMOS II and SDDS-2000, object-relational DMBS with RP* file used as an external storage [START_REF] Ndiaye | Scalable Distributed Data Structures for High-Performance Databases[END_REF][START_REF] Diéne | Performance Measurements of RP*: A Scalable Distributed Data Structure For Range Partitioning[END_REF], prototype of LH*g run in a single multi-threaded computer process which uses integers as data [START_REF] Lindberg | A Java Implementation of a Highly Available, Scalable and Distributed Data Structure LH*g[END_REF], -Distributed Dynamic Hashing [START_REF] Devine | Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm[END_REF], -"actor databases" where actors manipulate and store data in SDDS based on CTH* (distributed Compact Trie Hashing) [START_REF] Hidouci | Actor Oriented Databases[END_REF] and others.

However, in none of the above mentioned papers [START_REF] Devine | Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm[END_REF][START_REF] Ndiaye | Scalable Distributed Data Structures for High-Performance Databases[END_REF][START_REF] Diéne | Performance Measurements of RP*: A Scalable Distributed Data Structure For Range Partitioning[END_REF][START_REF] Lindberg | A Java Implementation of a Highly Available, Scalable and Distributed Data Structure LH*g[END_REF][START_REF] Hidouci | Actor Oriented Databases[END_REF] an object-oriented version of RP* architecture was presented.

RP* for Objects

In RP* architecture an address of a bucket where a record should be stored is calculated on the basis of ranges of the buckets [START_REF] Litwin | RP*: A Family of Order Preserving Scalable Distributed Data Structures[END_REF]. Hence, the algorithm for calculation of an address for a record in SDDS file (address of a bucket) is quite simple.

In OORP* architectures an address of the bucket where an object should be stored is calculated on the basis of ranges of the buckets, too. Objects of the same class can contain tables of different sizes what makes their sizes different. Hence, the buckets should store various numbers of objects.

For this reason a split of the bucket should be done when:

1) an object is to insert and a) load factor of the bucket is above threshold for controlled split; the load factor is measured as a quotient of sum of sizes of all objects in the bucket to the capacity of the bucket, b) there is no enough free space for next object for uncontrolled split, or 2) an object is updated. An updated object may change its size. If updated object is bigger then it may happen what follows: a) there is enough free space in the bucket and the updated object can be stored directly in the bucket, or b) there is not enough free space in the bucket and the bucket must split using the same algorithm as during insertion of an object.

If updated object is smaller or has the same size it is stored directly in the bucket. The split algorithm for OORP* (Algorithm 1) [START_REF] Bedla | A Store of Java Objects on a Multicomputer[END_REF] is similar to that for original RP* [START_REF] Litwin | RP*: A Family of Order Preserving Scalable Distributed Data Structures[END_REF] and also quite simple. However, it is assumed that bucketSize maximum(sizeOf (object)). Steps 2, 3, 4 and 6 are as in [START_REF] Litwin | RP*: A Family of Order Preserving Scalable Distributed Data Structures[END_REF]. In OORP* bucketSize must be actualized when an object is added, updated or deleted.

Implementation of RP* for Java Objects

An implementation of OORP* architecture for Java objects should allow for storing, updating, retrieving and deleting individual objects of a class defined by a user, with such restrictions on classes which might be easy accepted (i.e. classes must be serializable).

Objects stored in OORP* are distributed among many servers. Hence, they should have some extra features. This can be achieved in different ways. These are as follows:

modification of a source code of a class, what requires an access to this source code, modification of Java Virtual Machine (JVM), but not all licenses allow to do that, additionally permanent modification of JVM affects other applications, modification of compiled byte code to gain required features, what means that the source code is not necessary and is left unchanged. Copy to bucket M the following content:

-The header with : cm(B); ⇤ ⇤(B); every object from B with c > cm.

5.

Decrease the maximal key in B: ⇤ cm(B); remove objects moved to bucket M, and actualize bucketSize.

6.

Set M M + 1, where:

size and halfBucketSize denote integer variables, o denotes an object variable, -M denotes a number of a new bucket, -bucketSize denotes a sum of sizes of all objects in B, c and cm denote a key and middle key in B respectively, and ⇤ denote minimal and maximal values of keys of B respectively, -nextObject and sizeOf denote a next object in B and a size of an object respectively.

To store objects of some class in OORP* the class must contain some extra methods and attributes. A solution based on inheritance can not be applied here because Java class can only extend one base class. A programmer could probably add these method and attributes manually but it excludes transparency. For these reasons the last from the above options that is byte code modification is chosen.

There are distinguished two types of objects, which can be added to OORP*:

primary objects which can be directly added to OORP*, these are objects of classes created by a user, secondary objects which can be added to OORP* only with primary objects, for example objects of class Integer.

Objects may contain references to other primary or secondary objects organized as a list, for example. Managing a list as one single object may lead to many problems related with performance and dependency of the store. Every time when the first element of the list is required, the whole list would be retrieved. This is very time consuming (and not efficient). To avoid such problems the references to primary objects are treated in special way. When an object is added to OORP* every primary object is added separately. When the object is retrieved from OORP* no other primary object is retrieved. When a field containing reference to primary object is accessed (read or written) an autogenerated method (getter or setter) is invoked. Then the object is retrieved from (stored to) OORP*. A class containing references to primary objects is modified:

autogenerated table with identifiers of the primary objects is added, every access (read or write) to such field is replaced with invocation of autogenerated method (the getter or setter), autogenerated getter and setter for every field containing the references to primary objects are added.

The program called SDDSModifier modifies compiled class and adds all required features. Objects are stored in serialized form. They are converted into tables of bytes, transmitted and then stored in the buckets on servers. Because of its popularity and universality Java collection is chosen as a method of accessing objects. The collections, besides tables, are probably the second primary method of arranging objects. All standard Java collections implement one of the two following interfaces: Collection which is a base for lists and sets, and Map which is used to map keys to values. The interface SDDSCollection, which extends Collection, and class SDDSFile, which implements it were developed. SDDSFile does not support queries based on values of fields of objects, but the objects may be iterated.

Summarizing, the development of scalable, distributed store of Java objects consists of the three following steps:

1. First a programmer develops an application which uses SDDSFile to store objects.

The application may use classes which are stored in OORP* and other classes not related with OORP*. 2. Next, the classes are compiled using a standard Java compiler and then modified by SDDSModifier. 3. Finally, after starting servers the application may be launched. Every server may work in textual or graphical mode.

Performance Evaluation

In the experiment objects were inserted and retrieved from:

a collection (java.util.HashSet) which is stored in main memory, a file which is stored in secondary memory, a RP*N file composed of 4 or 8 servers. The only one client of RP*N file was assumed.

Performances of these operations were measured and compared. During the experiment a class containing tables of bytes (512 kB) was used. The number of stored objects was from 1000 up to 6000 (from about 512 MB up to about 3 GB). All classes used for tests have not overloaded method hashCode(). Every test was repeated three times The OORP*N has almost constant average time of storing and retrieving single objects. It does not depend directly on the number of objects. The difference between maximum and minimum values of the average time is about 44% for OORP*N consisted of 4 servers and about 23% for OORP*N consisted of 8 servers. For serialization into a file this difference is more than 2000% and for objects stored in the main memory is more than 8000%. The serialization into a file is the slowest from evaluated methods if total size of the objects excess 1.5 GB (that is the size of the main memory of the computer used in the experiment). Moreover, the serialized objects in a file must be accessed sequentially.

For OORP*N average time of retrieving objects is almost constant and it is about 17,7 ms. Average time of storing all objects is more variable and varies from about 19,4 ms to 40,6 ms. It is a sum of average time of sending objects to the servers and average time related with splits. Let us assume that average time of sending single object is always the same and equals average time of storing single object when split does not happen. If s is the ratio of the number of objects moved during a split to the number of all objects then average time related with splits can be calculated as arithmetic product of s and some constant value related with a speed of the network. Figure 5 presents ratio of the number of objects moved during a split to the number of all objects. A comparison of theoretical calculations of average time of storing single objects to OORP*N (marked *) with results obtained experimentally is presented on Fig. 6. The curves are almost identical.

Conclusions

The OORP* can be used as a part of distributed object store. It can store Java objects in serialized form. In OORP* addressing algorithm is same as in RP*. However, buckets can store various numbers of objects. The split algorithm must be modified and not based on the number of objects but on the size of objects. The experiments proved that average times of storing and retrieving single objects are more constant for the OORP*N than for the collection and for the file. The difference between maximal and minimal values of the average times is almost twice smaller for OORP*N composed of 4 servers (44%) than for OORP*N composed of 8 servers (23%). Average time of retrieving single objects is almost constant and does not depend on the number of objects or servers. Time of storing all objects is a sum of time of sending objects to servers and time of splits. The time of splits depends on the number of objects moved during a split what, in turn, depends on the size of the bucket. The bigger buckets the better results because less objects are moved. The results from the experiment confirmed theoretical calculations.

Object-oriented versions of other architectures of the SDDS will be the subject of our further research.

Fig. 1 .

 1 Fig. 1. Total time of storing and retrieving all objects.

Fig. 2 .

 2 Fig. 2. Average time of storing and retrieving single objects.

Fig. 3 .

 3 Fig. 3. Time of storing all objects to (S) and retrieving from (R) OORP*N for 4 and 8 servers.

Fig. 4 .

 4 Fig. 4. Average time of storing single objects to (S) and retrieving from (R) OORP*N for 4 and 8 servers.

Fig. 5 .

 5 Fig. 5. Ratio of the number of objects moved during a split (Ns) to the number of all objects (N).

Fig. 6 .

 6 Fig. 6. Comparison of theoretical calculations of average time of storing single objects to OORP*N (marked *) with experimental results.


Alireza Khalilian
email: khalilian@comp.iust.ac.ir

Saeed Parsa
email: parsa@iust.ac.ir

Bi-Criteria Test Suite Reduction by Cluster Analysis of Execution Profiles

Keywords: Software regression testing, testing criteria, test suite minimization, test suite reduction, fault detection effectiveness

The aim has been to minimize regression test suites while retaining fault detection capability of the test suite admissible. An appropriate minimized test suite should exercise different execution paths within a program. However, minimization of test suites may result in significant fault detection loss. To alleviate the loss, a new bi-criteria heuristic algorithm, using cluster analysis of test cases execution profiles is proposed in this paper. Cluster analysis of execution profiles categorizes test cases according to their similarity in terms of exercising a certain coverage criterion. Considering additional coverage criteria the proposed algorithm samples some test cases from each cluster. These additional criteria exercise execution paths, different from those covered by the main testing criteria. Experiments on the Siemens suite manifest the applicability of the proposed approach and present interesting insights into the use of cluster analysis to the bi-criteria test suite reduction.

Introduction

Software regression testing is a critical activity in the development and maintenance of evolving software. A major difficulty with the regression testing is the excessive number of test cases accumulated while generating new test cases to test any new or modified functionality within the program [START_REF] Rothermel | Empirical Studies of Test-Suite Reduction[END_REF]. To resolve the difficulty and to reduce the excessive cost of regression testing, various coverage-based and distribution-based techniques have been proposed [START_REF] Rothermel | An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites[END_REF][START_REF] Harrold | A methodology for Controlling the Size of a Test Suite[END_REF][START_REF] Chen | Heuristics Toward the Optimization of the Size of a Test Suite[END_REF][START_REF] Jones | Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage[END_REF][START_REF] Mcmaster | Call-Stack Coverage for GUI Test Suite Reduction[END_REF][START_REF] Tallam | A Concept Analysis Inspired Greedy Algorithm for Test Suite Minimization[END_REF][START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF]. These techniques attempt to permanently discard redundant test cases and retain the most effective ones to reduce the excessive cost of regression testing [START_REF] Mcmaster | Call-Stack Coverage for GUI Test Suite Reduction[END_REF]. An effective technique for regression testing is to find a minimal subset of test cases which satisfy all the test requirements as the original set does [START_REF] Chen | A Novel Approach for Test Suite Reduction Based on Requirement Relation Contraction[END_REF]. A suitable subset could be found during the test case generation or after creating the test suite. Apparently the less the number of test cases the less time it takes to test the program. This consequently improves the effectiveness of the test process. The technique is commonly known as test suite reduction or test suite minimization in the literature and the resulting suite is called representative set [START_REF] Harrold | A methodology for Controlling the Size of a Test Suite[END_REF].

Almost all the previous test suite reduction techniques could significantly reduce the size of the test suites. But an important issue deals with how well these reduced suites can be compared with their corresponding un-reduced suites using criteria rather than the suite size criterion. Since the purpose of test case execution is to detect faults in the software, one measure of the suite quality is its fault detection capability. In fact, a potential drawback observed in test suite reduction studies is that permanent removal of test cases from a test suite may highly decrease the fault detection effectiveness of the remaining suite. Thus, the tradeoff between the time required to execute and manage test suites and their fault detection effectiveness should be considered when applying test suite reduction techniques [START_REF] Rothermel | An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites[END_REF].

Coverage-based minimization techniques attempt to eliminate redundant test cases while maximizing the code coverage of a program in order to ensure that all different execution paths are exercised and the majority of the faults are revealed. However, test cases considered as redundant in respect with the main testing criterion may be considered as essential test cases with respect to the additional criteria. This is evidenced by the results of the empirical studies presented in [START_REF] Jeffrey | Improving Fault Detection Capability by Selectively Retaining Test Cases during Test Suite Reduction[END_REF]. These results suggest that using several coverage criteria, rather than a single criterion, during test suite reduction is indeed useful in determining test cases which are likely to expose different faults. However, code coverage solely is not a sufficient criterion for selecting representative test cases from the original test suite. This is because high code coverage may be achieved by selecting simple test cases that do not reflect the program execution in real situations [START_REF] Marick | The Craft of Software Testing: Subsystem Testing[END_REF] and the resultant reduced suite may not be efficient in detecting faults.

A number of recent papers have investigated techniques for test suite reduction using execution profiles, applied in distribution-based techniques [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF]. An execution profile generated by a test case identifies the program elements covered by the test case. For example, a profile may indicate which branches or data flow relationships are exercised by a test case. Distribution-based techniques reflect additional information about test cases that can be helpful in determining effective test cases when reducing the original test suite. Distribution-based test suite reduction techniques are examples of observation-based testing [START_REF] Leon | Multivariate Visualization in Observation-based Testing[END_REF]. Observation-based testing is potentially applicable in situations where it is desirable to filter a large amount of test cases identifying a promising subset of test cases for conformance to the requirements [START_REF] Dickinson | Finding Failures by Cluster Analysis of Execution Profiles[END_REF]. Despite the effectiveness in detecting failures, observation based methods do not necessarily provide full coverage [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF]. Moreover, empirical studies [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF] show that the functionality of these methods varies with the size of the test suite. These studies also indicate that coverage-based and distribution-based techniques often do not select similar test cases and are complementary because they find different faults.

To address the limitations of the coverage-based and distribution-based approaches, in this paper a bi-criteria heuristic algorithm is proposed. The algorithm is applied to each cluster of execution profiles of the test cases, iteratively. In each of its iteration, a representative test case enhancing the cumulative coverage of the reduced test suite is selected from each cluster. The selection is based on the two criteria to improve the fault detection effectiveness. In fact, by selecting a test case from each cluster, all test cases that are now redundant with respect to the first criterion, are re-verified. Among such test cases, those that cover the maximum number of unmarked requirements with respect to the second criterion are inserted into the reduced suite. At the end of this process, the reduced suite is verified to be coverage adequate with respect to the second criterion. If not, the described process is repeated considering the second criterion, yielding bi-criteria coverage adequacy of the reduced suite. In order to evaluate the ap-plicability of the proposed approach, we conducted experiments on the Siemens suite. We also implemented the well-known H algorithm [START_REF] Harrold | A methodology for Controlling the Size of a Test Suite[END_REF], to compare the results of reducing suites using our distribution-based heuristic algorithm with those of minimizing test suites using the H algorithm.

The rest of the paper is organized as follows: Section 2 discusses the background of the test suite reduction techniques. Section 3 contains the outline of the proposed approach. Section 4 describes the empirical studies and the obtained results. Finally, conclusions are mentioned in section 5.

Background and Related Work

In this section, first the formal definition of the Test Suite Reduction problem will be introduced. Then, some related studies in this context are described. Afterwards, two general approaches to this problem are presented.

Test Suite Reduction

The first formal definition of test suite reduction problem introduced in 1993 by Harrold et al. [START_REF] Harrold | A methodology for Controlling the Size of a Test Suite[END_REF] as follows:

Given. {t 1 , t 2 , . . . , t m } is test suite T from m test cases and {r 1 , r 2 , . . . , r n } is set of test requirements that must be satisfied in order to provide desirable coverage of the program entities and each subsets {T 1 , T 2 , . . . , T n } from T are related to one of r i s such that each test case t j belonging to T i satisfies r i .

Problem. Find minimal test suite T 0 from T which satisfies all r i s covered by original suite T.

Generally the problem of finding the minimal subset T 0 , T 0 ✓ T which satisfies all requirements of T, is NP-complete [START_REF] Zhong | An Experimental Study of Four Typical Test Suite Reduction Techniques[END_REF], because we can reduce the minimum setcover problem to the problem of test suite minimization in polynomial time. Thus, researches use heuristic approaches to solve this problem. One heuristic method proposed by Harrold et al. [START_REF] Harrold | A methodology for Controlling the Size of a Test Suite[END_REF], tries to find the smallest representative set that provides the same coverage as the entire test suite does.

Related work in the context of test suite reduction can be classified into two main categories: The works in which a new technique is presented [START_REF] Harrold | A methodology for Controlling the Size of a Test Suite[END_REF][START_REF] Chen | Heuristics Toward the Optimization of the Size of a Test Suite[END_REF][START_REF] Jones | Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage[END_REF][START_REF] Chen | A New Heuristic for Test Suite Reduction[END_REF][START_REF] Chen | A Novel Approach for Test Suite Reduction Based on Requirement Relation Contraction[END_REF][START_REF] Mcmaster | Call-Stack Coverage for GUI Test Suite Reduction[END_REF][START_REF] Tallam | A Concept Analysis Inspired Greedy Algorithm for Test Suite Minimization[END_REF], and empirical studies on the previous techniques [START_REF] Rothermel | Empirical Studies of Test-Suite Reduction[END_REF][START_REF] Rothermel | An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites[END_REF][START_REF] Zhong | An Experimental Study of Four Typical Test Suite Reduction Techniques[END_REF][START_REF] Wong | Effect of Test Set Minimization on Fault Detection Effectiveness[END_REF]. The works which propose a new approach commonly include heuristic algorithms [START_REF] Dickinson | Pursuing Failure: the Distribution of Program Failures in a Profile Space[END_REF], genetic algorithm-based techniques [START_REF] Mansour | Simulated Annealing and Genetic Algorithms for Optimal Regression Testing[END_REF] and approaches based on integer linear programming [START_REF] Black | Bi-Criteria Models for All-Uses Test Suite Reduction[END_REF].

Testing criteria are defined in order to help the selection of subsets of the input domain to be covered during testing. For example, a code coverage criterion provides test suite adequacy with respect to coverage of the program entities and also provides a check on its quality. Assuming testing criterion C which satisfies by the test suite T, a test case, t, is redundant if the suite T {t} also satisfies C [START_REF] Jones | Test-Suite Reduction and Prioritization for Modified Condition/Decision Coverage[END_REF]. Therefore, removing those test cases which are redundant with respect to some specific criteria preserves test suite's adequacy with respect to it. In previous empirical studies [START_REF] Zhong | An Experimental Study of Four Typical Test Suite Reduction Techniques[END_REF] researchers commonly apply various code coverage criteria in their reduction techniques. The results of empirical studies [START_REF] Rothermel | An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites[END_REF][START_REF] Wong | Effect of Test Set Minimization on Fault Detection Effectiveness[END_REF] show that the more percentage of the test suite size is reduced the more percentage of faults will be lost.

Coverage-based Techniques

The main purpose of traditional software testing is to achieve the maximum code coverage [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF] and the main idea is that the test suite is capable of exercising the whole program under test. In other words, there must be some test cases per program element (including statement, branch, def-use pair and so on) which can cover it. This is due to unreliability of the uncovered parts of the program during testing. But as mentioned above, code coverage alone is not sufficient for selecting test cases. If the code coverage is the main factor in determining the quality of a test suite, then it is desirable to have the minimal subset of the test suite that covers the program elements the same as the original suite [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF]. Even if the code coverage is not the main factor in test suite quality, it is possible to use it as the first step of other reduction approaches. The main purpose of executing test cases is to expose faults as far as possible. Thus fault detection effectiveness of a test suite is of great importance. On the other hand, due to large amount of test cases and time constraints for retesting the software every time it modifies, it is necessary to keep the size of the test suite manageable [START_REF] Rothermel | An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites[END_REF]. Therefore, there must be some tradeoff between the suite size and its fault detection effectiveness.

Usually a test suite reduction technique attempts to remove redundancy among test cases and retain the most effective ones into the test suite [START_REF] Mcmaster | Call-Stack Coverage for GUI Test Suite Reduction[END_REF]. Effective test cases are those that are capable of satisfying the most requirements as well as exposing the most of the existing faults. Note that the more requirements are satisfied, the more execution paths within the program would be exercised which yields the all kinds of the faults to be exposed. When a reduction algorithm determines some test cases to be redundant, it uses a certain criterion to do this. But redundant test cases which are thrown away during test suite reduction may exercise unique situations in the software with respect to another criterion [START_REF] Jeffrey | Improving Fault Detection Capability by Selectively Retaining Test Cases during Test Suite Reduction[END_REF]. For example, a reduction algorithm may select test cases which cover the most number of branches of a program. During the reduction, some test cases may cover the same branches as covered by test cases in the reduced suite. Hence, such test cases are redundant and will be discarded. However, such test cases may not be redundant with respect to a second criterion such as def-use pair. So they will be preserved from discarding because they cover execution paths which may contain some kind of faults. These results are evidenced by empirical studies in [START_REF] Jeffrey | Improving Fault Detection Capability by Selectively Retaining Test Cases during Test Suite Reduction[END_REF]. Therefore, using multiple criteria during reduction is useful to select test cases that are more likely to expose faults.

Distribution-based Techniques

Distribution-based techniques select test cases according to how their profiles are distributed by dissimilarity metric in the multi-dimension profile space [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF]. Dissimilarity metric is a function that produces a real number for each pair of profiles which shows the degree of their dissimilarity. Distribution-based methods can be described using two closely related techniques: cluster filtering and failure-pursuit. Cluster filtering calls for using automatic cluster analysis to partition the test pool [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF]. The purpose of cluster analysis is to partition the population such that objects with similar attributes are in the same cluster. After clustering, test cases are sampled from each cluster.

Distribution-based test suite reduction techniques are examples of observationbased testing [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF]. It calls for first taking an existing set of test cases (possibly a large amount), and then executing them on an instrumented version of the program under test in order to obtain execution profiles that characterize the executions [START_REF] Dickinson | Finding Failures by Cluster Analysis of Execution Profiles[END_REF]. Next, it analyzes the profiles and selects a subset of test cases for conformance to requirements. The analysis of profiles can be achieved using multivariate data analysis like clustering [START_REF] Leon | Multivariate Visualization in Observation-based Testing[END_REF]. Such kind of analysis can extract additional information from the profile data. In general, observation-based testing is applicable when it is desirable to identify a promising subset of test cases for conformance to requirements as well as filtering legacy test suites. An observation-based testing is defined by determining the following: (1) the type of the execution profile (2) a filtering or reduction technique to select a subset of executions and (3) an optional augmentation procedure. The type of the applied profiling should reflect the runtime events. Software testing research and practice suggest a variety of alternatives such as statement, basic block, branch, all-uses and so on [START_REF] Harrold | An Empirical Investigation of Program Spectra[END_REF].

The distribution-based techniques used for reducing test suites, determine some characteristics of the distribution profile that are likely to detect faults, and apply them during the selection of test cases. For example, clusters that have similar profiles contain redundant test cases and selecting one or a few representatives are sufficient. Also isolated profiles contain test cases that indicate unusual conditions and are likely to detect faults. Test case cluster filtering is defined by selecting clustering algorithm, dissimilarity metric, number of clusters and sampling method [START_REF] Leon | A Comparison of Coverage-Based and Distribution-Based Techniques for Filtering and Prioritizing Test Cases[END_REF].

The Proposed Approach

Our approach to test suite reduction has been motivated by combining the two general techniques called distribution-based and coverage-based techniques. These techniques are fully described in the previous section. Distribution-based techniques are capable of determining similar test cases by means of clustering. These techniques cluster test cases within a test suite to determine test cases which exercise similar execution paths within the program. Since all the test cases within a same cluster have almost a same execution profile, most of them are likely to be redundant. Hence, sampling some representatives from each cluster may lead to a selection of distinguished test cases which test different execution paths within the program under test. Therefore, the major benefit of these techniques is to compose a reduced suite of distinct test cases with minimum redundancy. However, despite of covering rather non-overlapping execution paths, distribution based techniques do not necessarily provide full coverage of the execution paths. On the other hand, the coverage-based techniques insist on test suits with full coverage rather than non-overlapping test cases. Therefore, we combined these two techniques to provide a new bi-criteria technique to form full coverage reduced test suites with minimum overlap in the execution profiles of the including test cases.

The more the number of testing criteria the bigger the size of the test suite will be. However, experimental results show that two testing criteria can establish an appropriate tradeoff between the suite size and the fault detection capability of the reduced test suite. The general procedure of our approach is as follows: At the first step, the program is instrumented according to two different coverage criteria. Then, test cases in the test suite are executed over the instrumented version of the program to collect execution profiles. Next, the collected profiles are clustered by means of a clustering algorithm. The clustered test cases and the testing requirements are applied as inputs to run our test suite reduction algorithm. After the reduction, the reduced suite will be coverage adequate with respect to the first criterion. The adequacy of the reduced suite is verified with respect to the second criterion. In the case of inadequacy, a similar algorithm using the second criterion can be applied to augment test cases providing coverage adequacy of the reduced suite with respect to the second criterion.

A detailed pseudocode description of the proposed algorithm is given in Fig. 1 and2. Initially, all the testing requirements are unmarked and the number of unmarked requirements considering each of the two testing criteria is counted for each test case. Then, all the clusters of the test cases are sorted in ascending order of their number of test cases. In the next step, the algorithm keeps looking for representative test cases in each cluster of the sorted list of clusters until the selected representative test cases form a coverage adequate test suite with respect to the first criterion. In each of its iteration of the while-loop in Fig. 1, all the test cases within the next cluster of the test suite are added to a set called list. A function, SelectTest, selects a representative test case from the cluster and augments it to the reduced suite, RS. Each testing requirement satisfied by the selected representative test case is marked as satisfied in two arrays called marked 1 and marked 2 . Each of these marked requirements may be satisfied by a number of test cases. If all the requirements satisfied by each of these test cases are marked with respect to one of the two test criteria, the test case number is augmented to the list of the redundant test cases, redundanti, for the ith criterion. Finally, all those cases which are in the current cluster, list, and their numbers appear in the set {redundant 1 redundant 2 }, are augmented to a set, redundant. The function SelectSomeMoreTest-Cases is then invoked to select some test cases from the set, redundant, and add the selected test cases to the final reduced suite, RS.

The function SelectTest selects a test case from a certain cluster. This function attempts to find a test case with maximum number of unmarked requirements with respect to the first criterion. In case of a tie, the number of unmarked requirements for the second criterion is considered. If tie occurs again, sum of the satisfied requirements with respect to the both criteria is considered, and finally a test case is selected randomly. The function SelectSomeMoreTestCases attempts to find some test cases from redundant that satisfy the maximum number of unmarked requirements with respect to the second criterion. Each time a test case is selected those test cases that become redundant are removed from the redundant set.

Empirical Studies

To evaluate and compare the proposed approach with prior approaches in test suite reduction area, an experiment similar to previous studies has been conducted. This section describes the experiment.

Subject Programs and Measures

We used the Siemens suite as subjects in our experiments. Siemens suite includes seven programs in C language developed by the researchers at Siemens Corporation for exper- iments with control-flow and data-flow test adequacy criteria [START_REF] Rothermel | Software-artifact Infrastructure Repository[END_REF]. These programs are associated with several faulty versions. Each faulty version of each program contains a single fault seeded in it. For each program there is a test pool which contains test cases developed for different black-box and white-box testing objectives.

To investigate the effectiveness of our approach, we measured the following from our experiments:

Clustering and Analysis Tools

In order to cluster execution profiles of test cases, Weka 3.5.8 [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF] has been used. Weka is a java-based tool that provides a uniform interface to many different learning algorithms along with methods for pre and post processing and for evaluating the results of learning schemas on any given dataset. It also provides implementations of the stateof-the-art learning algorithms and has been tested under Linux, Windows and Macintosh operating systems. Besides, we used SAS 9. 1.3 [23] to create boxplots. Boxplot diagrams are commonly used to visualize the empirical results in test suite reduction studies.

Our experiments include a large number of test cases each of which covers a lot of requirements. Thus, a large number of high dimensional data should be clustered. However, fast and effective clustering of such data is extremely difficult because of their large volume and high dimensionality [START_REF] Yang | CLOPE: a Fast and Effective Clustering Algorithm for Transactional Data[END_REF]. On the other hand, clustering algorithms need to set the number of clusters. Selecting the number of clusters affect the separation of test cases. The CLOPE algorithm [START_REF] Yang | CLOPE: a Fast and Effective Clustering Algorithm for Transactional Data[END_REF] is a fast and efficient method for clustering large and high dimensional data. In this algorithm, a value called Repulsion is set which controls level of intra-cluster similarity. The number of clusters changes by varying this value. We felt that as a first step for exploration, using the CLOPE algorithm would lead to a good compromise between fast and effective clustering and a reasonable number of clusters.

Experiment Setup and Results

Our experiments follow a setup similar to that used by Rothermel et al [START_REF] Rothermel | An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites[END_REF]. For each program, we created branch coverage adequate test suites for six different suite ranges named as B, B1, B2, B3, B4 and B5. For each suite range, we first selected X⇤ LOC test cases randomly from the test pool and added to the test suite, where X is 0, 0.1, 0.2, 0.3, 0.4 and 0.5 respectively and LOC is the number of lines of code for each program. Then, randomly-selected test cases are added into the test suite as necessary so long as each test case increased the cumulative branch coverage of the suite, until the test suite becomes adequate with respect to branch coverage. In this way, the developed test suites have various types and varying levels of redundancy exist between them. We created 1000 such branch coverage adequate test suites for each program. In order to gather branch coverage information of test cases, all programs were hand-instrumented.

In our experiments, we used all-uses coverage as the second criterion. We measured alluses coverage using the ATAC tool [START_REF] Horgan | ATAC: A Data Flow Coverage Testing Tool for C[END_REF].

In order to evaluate the effectiveness of our approach, we implemented our algorithm and applied it to the generated suites with branch coverage as first criterion and all-uses as the second criterion. We also implemented the H algorithm [START_REF] Harrold | A methodology for Controlling the Size of a Test Suite[END_REF] and conducted similar experiments on the generated suites with respect to branch coverage. The results of this experiment are shown in the columns labeled H and P in Table 1 for the H algorithm and the proposed algorithm respectively. The values in each row of the table are average values for 1000 suites in each range. In this table , The boxplot in the Fig. 3 shows the distribution of the percentage of size reduction (SR) and percentage fault detection loss (FL) in the largest suite size range (B5) for each program. In this figure, boxes are paired such that, white pair of boxes shows percentage of size reduction and gray pair of boxes shows the percentage of fault detection loss. In each pair, left side box indicates for our algorithm and the right side one indicates for the H algorithm. For all programs, it is observed that the percentage suite size reduction by the proposed algorithm is less than the respective suite size reduction using the H algorithm. This result is expected since our approach selects some additional test cases that are not redundant with respect to the second criterion though they are redundant with respect the first criterion. For all programs, the percentage fault detection loss of the suites reduced by the proposed algorithm is less than the respective suites reduced by the H algorithm. We reason that the reduced suites generated using the proposed algorithm, are more efficient due to two main causes. First, clustering results in partitioning the test cases such that those with different execution profiles are gathered into different clusters. This gives us the opportunity to select as much unique test cases as possible.

Second, using second criterion during reduction may cause to selecting redundant test cases with different coverage of execution path within the program. These are also evidenced by the results of empirical studies.

To determine whether the degradation in fault detection loss observed for the proposed algorithm over the H algorithm is statistically significant, we conducted a hypothesis test for the difference of the two means [START_REF] Freund | Mathematical Statistics[END_REF]. The samples are the number of distinct faults exposed by each of the 1000 reduced test suites for suite size range B5 using the H algorithm and the proposed algorithm. We considered the null hypothesis that there is no difference in the mean number of the exposed faults by the two algorithms. We used a reference table of critical values presented in [START_REF] Freund | Mathematical Statistics[END_REF]. Table 2 shows the resulting z values computed for the hypothesis test along with the percentage confidence with which we may reject the null hypothesis. Note that for z values greater than 4.0, we can reject the null hypothesis with the confidence over than 99.99 percent.

Threats to Validity

In this section, we describe the potential threats to validity of our study. Threats to construct validity. In our study, the measurement for the percent of fault loss assumes simple model for cost which treats all faults as equally severe. But in practice, faults have wide range of severity from less critical to more critical.

Threats to internal validity. The most important issue deals with handinstrumentation of code which we have done for obtaining branch coverage of test cases. To validate the correctness of this process, the instrumentation was re-verified. Another issue is composition of the test suites. However, we utilized the process of creating suites which was employed in previous studies [START_REF] Rothermel | An Empirical Study of the Effects of Minimization on the Fault Detection Capabilities of Test Suites[END_REF].

Threats to external validity. Siemens programs are widely used in software testing studies. However, these programs are limited and their faults are known. Moreover, they are not real programs and the faults are hand-seeded. Space program is a big and real one, used to our case study. But it is one of such a program we used.

Conclusions

We have presented a new approach for test suite reduction that attempts to identify effective test cases in terms of their fault detection effectiveness. This approach is based on the intuition that clustering of the test cases execution profiles, can partition the test suite such that similar test cases in terms of exercising a certain coverage criterion, would be in the same clusters. Hence, determining redundant test cases from essential ones could be done effectively and simply. In order to improve the fault detection effectiveness of the reduced suite, we used two coverage criteria during the reduction process. The results of empirical studies demonstrate the effectiveness of the proposed approach by generating reduced test suites with less fault detection loss.

Fig. 1 .

 1 Fig. 1. Pseudocode description of our proposed heuristic algorithm for test suite reduction.

Fig. 2 .

 2 Fig. 2. Function SelectTest to select a test case from current cluster and function SelectSomeMo-reTestCases to select some test cases from the redundant set into the RS.

1 .

 1 The percentage suite size reduction = |T| |TRed| |T| ⇥ 100, where | T | is the number of test cases in the original test suite and | T Red | is the number of test cases in the reduced test suite. 2. The percentage fault detection loss = |F| |FRed| |F| ⇥ 100, where | F | is the number of distinct faults exposed by original test suite and | F Red | is the number of distinct faults detected by the reduced suite.

  | T | indicates for the original suite size, | F | for the number of faults exposed by the original suite, | T Red | for the reduced suite size, | F Red | for the number of faults exposed by the reduced suite size, %Size Reduction for the percentage suite size reduction and %Fault Loss for the percentage fault detection loss.

Fig. 3 .

 3 Fig. 3. The boxplot for the percentage suite size reduction and percentage fault detection loss.

Table 1 .

 1 The results of the experiments comparing the H algorithm and the proposed algorithm. .53 13.65 15.71 10.85 11.83 40.02 31.13 19.17 11.95 B1 38.36 15.49 13.52 16.11 11.01 12.23 61.15 53.99 29.92 20.22 B2 59.55 17.11 13.40 16.54 10.90 12.44 71.33 65.39 44.79 25.89 B3 84.94 18.64 13.18 16.84 9.97 12.83 78.28 73.24 49.69 29.94 B4 108.98 19.45 12.99 17.02 09.75 12.83 81.67 77.13 52.96 32.51 B5 131.09 20.34 12.82 17.04 08.65 13.11 84.22 80.18 55.99 34..85 5.54 6.34 12.89 13.17 36.97 27.28 6.69 3.84 B1 20.62 14.78 5.46 6.49 11.83 13.62 68.07 60.52 17.71 10.59 B2 36.74 16.11 5.33 6.51 11.91 13.86 78.66 73.68 25.99 17.06 B3 52.50 17.04 5.25 6.37 11.17 13.97 83.43 80.64 31.38 21.40 B4 70.25 17.77 5.20 6.33 10.86 14.10 87.10 83.66 32.09 22.87 B5 86.23 19.37 5.18 6.28 13.00 14.01 88.23 86.22 31.79 22.45

		Suite				% Size	% Fault
	Program	size | T | | F | range	| TRed | H P	| FRed | H P	Reduction H P	H	Loss	P
	printtokens	B	17.79 3.85 8.19 8.48 3.26 3.56 52.86 51.13 9.21 6.39
		B1	29.4 4.01 8.22 8.64 3.23 3.51 69.13 67.66 14.66 10.80
		B2 46.45 4.29 8.15 8.73 3.16 3.56 77.48 76.17 19.31 15.04
		B3 65.48 4.53 8.05 8.72 3.25 3.57 82.58 81.41 23.42 19.08
		B4 84.96 4.68 7.97 8.80 3.03 3.53 85.63 84.51 28.99 22.00
		B5 107.63 4.92 7.98 8.95 3.07 3.61 87.90 86.89 33.97 24.06
	printtokens2 B	13.41 8.47 8.01 8.99 8.17 8.27 39.08 31.62 4.46 2.28
		B1 28.79 8.66 7.63 9.19 8.04 8.37 67.11 61.16 9.96 5.44
		B2 51.68 9.24 7.13 9.40 8.10 8.57 79.47 74.57 12.88 6.99
		B3	75.1 9.39 6.90 9.82 8.12 8.64 84.06 79.65 15.23 7.87
		B4 99.73 9.53 6.64 10.07 8.19 8.75 87.74 83.69 16.78 8.04
		B5 128.01 9.68 6.41 10.32 7.90 8.76 90.76 87.10 18.09 9.36
	replace	B	22.97 1300
	schedule	B	8.73 3.54 6.30 6.8 2.97 3.20 26.65 21.09 14.22 8.39
		B1 18.82 4.57 6.19 7.16 2.89 3.30 60.46 55.05 34.36 25.82
		B2 33.19 5.33 6.01 7.23 2.96 3.39 74.66 70.46 43.03 35.04
		B3 46.76 5.74 5.96 7.32 3.02 3.49 79.81 76.22 46.02 37.87
		B4 61.67 5.97 5.86 7.33 2.92 3.43 83.30 80.12 50.04 41.25
		B5 76.22 6.10 5.84 7.28 2.85 3.38 85.56 82.49 51.91 43.30
	schedule2	B	7.96 2.39 5.35 5.66 2.09 2.15 31.18 27.37 12.65 9.53
		B1 18.06 2.77 5.24 5.77 2.08 2.17 64.17 60.86 21.99 17.97
		B2 32.08 3.44 5.09 5.73 2.10 2.27 77.03 74.46 35.49 29.68
		B3 44.69 3.88 5.00 5.77 2.03 2.39 80.81 78.63 39.96 33.03
		B4 59.86 4.36 4.88 5.68 2.12 2.40 85.24 83.46 45.78 39.71
		B5 74.77 4.86 4.72 5.61 2.06 2.51 87.77 86.04 51.94 43.38
	tcas	B	5.70 7.13 5.00 5.04 6.44 6.59 11.12 10.45 8.32 6.57
		B1	9.22 8.70 5.00 5.10 6.09 6.52 39.53 38.56 26.04 21.48
		B2 15.16 11.21 5.00 5.09 6.37 6.53 57.70 56.97 42.41 35.96
		B3 21.27 13.61 5.00 5.08 6.58 6.68 66.06 65.50 52.95 43.98
		B4 28.29 15.54 5.00 5.06 6.57 6.77 71.99 71.60 61.19 50.08
		B5 35.70 17.28 5.00 5.05 4.74 6.64 76.35 76.05 64.06 55.13
	totinfo	B	9.02 13

Table 2 .

 2 Computed z value and the corresponding percentage of confidence for rejecting the null hypothesis for each program.

	Program Name Computed z value Percentage of confidence for
			rejecting the null hypothesis
	printtokens	15.46	>99.99%
	printtokens2	15.36	>99.99%
	replace	39.45	>99.99%
	schedule	8.82	>99.99%
	schedule2	8.20	>99.99%
	tcas	16.01	>99.99%
	totinfo	7.66	>99.99%