Journal of Software Engineering and Applications, 2011, 4, 550557 doi:10.4236/jsea.2011.49064 Published Online September 2011 (http://www.SciRP.org/journal/jsea) Copyright © 2011 SciRes. JSEA Towards MultiFaceted Test Cases Optimization Manoj Kumar1, Arun Sharma2, Rajesh Kumar3 1Department of Computer Application, Galgotias University, Greater Noida, India; 2Department of Computer Sc., Krishna Institute of Engineering and Technology (KIET), Ghaziabad, India; 3School of Mathematics & Computer Application, Thapar University, Patiala, India. Email: m_pachariya1@yahoo.com, arunshama2303@gmail.com, rakumar@thapar.edu Received July 20th, 2011; revised August 23rd, 2011; accepted August 31st, 2011. ABSTRACT The target of software engineering is to produce high quality software product at low cost. Software testing is la bourintensive, ambiguous and error prone activity of software development. How to provide costeffective strategies for software test cases op timization problem such as classification , minimization, selection, and prioritization ha s been one of the research focuses in software testing for a long time. Many researchers and academicians have addressed the effectiveness/fitness and optimiza tion of test cases, and obtained many interesting results. However, one issue of para mount importance in softwar e testing i.e. the intrinsic imprecise and uncertain ty of test cases fitness, fitness parameters, multiobjective optimization, is left unaddressed. Test cases fitness depends on several parameters. Vagueness of fitness of test cases and their fitness parameters have created the uncertainty in test cases optimization. Cost and adequacy values are incorpo rated into multifaceted optimization of test cases. This paper argues test cases optimiza tion requires multifaceted optimiza tion in order to adequately cater realistic software testing. In this paper, author s have identified several parameters for test cases fitness and multiple objectives for test cases optimization. In addition above, authors have formulated the test ca ses optimiza tion pro blem in three different wa ys using multifaceted con cept. These formula tions can be us ed in fut u re by au thors and re sea rchers. Keywords: MultiFaceted Optimization, Test Cases, Test Data Adequacy Criteria, Test Case Fitness 1. Introduction Software testing is the process of exercising the pro grams with specific intend of finding errors prior to de liver. Although software testing is a very humaninten sive, time consuming and itself an expensive activity, yet launching of software without proper testing may lead to cost potentially much higher than that of testing, spe cially in systems where human safety is involved [1,2]. Test cases are the inputs to the program under test. A test case is a set of conditions or variables under which a tester will determine whether an application or software system is working correctly or not. Test cases pool may contain some redundant, irrelevant and unfit test cases. Since, testing is very expensive activity, unnecessary execution of redundant, irrelevant and unfit test cases will increase unnecessary burden of cost. The solution is to choose the fittest test cases and removing the unfit, redundant unnecessary ones, which in turn leads to test cases optimization [35]. Measuring fitness of test cases is always a daunting task. The term “fitness” refers to the appropriateness of test cases to check the quality of soft ware. A test suite is a collection of test cases that are intended to be used to test a software program to show that it has some specified set of behaviours. Multicriteria test cases fitness evaluation, multiobjective test cases optimization may be the crucial problem for next genera tion software testing sorority. It requires to device next generation technologies to solve multifaceted test cases optimization problem. The effectiveness of this verifica tion and validation process depends upon the number of errors found and rectified before releasing the system. This, in turn, depends upon the fitness and number of test cases exercised. So, test cases optimization is necessary. An optimization problem is the problem of finding the best solution from all feasible solutions. Multiobjective optimization (MO) also known as multicriteria or multi faceted or multiattribute optimization is the process of simultaneously optimizing two or more conflicting ob jectives subject to certain constraints. The objective of MO optimization is to find the set of acceptable solutions and present them to the decision maker to take decision. Test cases optimization is the problem of finding the best subset (class) of test cases from a pool of test cases to be
Towards MultiFaceted Test Cases Optimization551 audited. It will meet all the objectives of testing concur rently. Most of the researchers evaluated the fitness of test cases only on single parameter fault detecting capa bility. Though, the fitness of test case depends on several parameters but consideration of only one parameter is not appropriate. Though, there are several objectives of test case optimization such as execution time, cost of data, cost of risks, and coveragebility, discussed in details in Section 3. But some objectives of test cases optimization are conflicting in nature, coveragebility of one objective will suffer other objective like cost, fitness of test cases and number of test cases in suite while considering all objectives concurrently. However most of test cases op timization approaches found in the literature are single objective and focused on the problem of maximizing the attainment of adequacy value without taking cost into account. It was not until 2001 that detailed empirical study was presented taking cost into account [6,7]. It was single objective optimization of test cases incorporating coveragebility and cost in ratio. Two objective test case optimization can be solved in such manner. If we want to optimize the test cases for three or more objectives, this approach is not fruitful. So it is not appropriate to estimate fitness of test cases just on single parameter and classify, select, prioritize the test cases on single objective. Single objective formulation of test cases fitness and optimiza tion are not meeting the objectives of testing. Test cases should be optimized in such a way that it will achieve maximum of code coverage, maximum requirements coverage, high fault detecting capability, maximum mu tant killing score and so far. The objective of test cases optimization is to reduce the number of test cases in suite to be audited and improve the effectiveness/fitness of test cases. So, test cases fitness evaluation, classification and selection of test cases should be treated as multifaceted concept. It will surely reduce the cost & efforts of soft ware testing and improve the quality of testing and re duce the number of test cases to be audited also. 2. Single Objective Formulation for Test Cases Optimization This section briefly reviews test cases minimization, se lection, classification, and prioritization, which collec tively form part of the more general topic of test cases optimization. This section formalizes relationship be tween test cases classification, selection, minimization, prioritization and filtration that form the test cases opti mization. Test cases minimization is a selection of smallest subset the test cases from a pool of test cases to be audited for a program. It covers as many program elements as the entire pool does. Test suite reduction seeks to reduce the number of test cases in a test suite while retaining a high percentage of the original suite’s fault detection effectiveness. Test suite minimization techniques seek to reduce the effort required for regres sion testing by selecting an appropriate subset of test suite. Test suite minimization is minimal set cover prob lem, which uses greedy approximation approach to solve it. So, Test suite minimization is NPcomplete problem [8,9]. Peculiar nature problems are those problems which require curious mix of data and knowledge driven ap proach to solve it. In search based software engineering, test cases optimization is a search space problem, which requires hybridization of data driven and knowledge driven approach to find near optimal solution of the problem. Hence, Test cases optimization is also peculiar nature problem [6,10]. Test cases selection is also finding minimal cardinality subset of test cases from the pool of test cases. One major difference between test cases minimization and test case selection is that test case se lection chooses a temporary subset of test cases, whereas test suite minimization reduces the test suite permanently based on some external criterion such as structural cov erage. Test case prioritization techniques try to find an ordering/ranking of test cases, so that some test case adequacy can be maximized as early as possible. Test case prioritization and filtration depend on quality of initial population of test cases. Selection and prioritiza tion of test cases are the two important solutions to the problem of test case optimization. Test case filtration and prioritization are closely related. In fact, test cases can be filtered by selecting the first N ordered test cases. There fore, any test case prioritization algorithm can be used as a test case selection algorithm. Naturally, it is desirable to select those test cases that are most likely to reveal defects in the program under test. When testing a pro gram, software testers have to define the testing objec tives first. A test suite is then constructed to satisfy the all objectives of testing. It is generally agreed that a test suite must achieve maximum coveragebility of all objec tives of testing [11,12]. Usually, the constructed test suite may contain redundant test cases. A test case in a test suite is said to be redundant if the same testing objective can still be satisfied by other test cases of the test suite. Since the execution of test cases and evaluation their results are very expensive, it is of paramount importance to remove redundant test cases within a test suite. How ever, removal of all redundant test cases is practically infeasible because the problem is NPcomplete. However, a weakness of test suite reduction is that the removal of some test cases from the test suite may potentially reduce the fault detecting capability of the test suite too [13,14]. To be worthwhile, the sum of the cost of test cases filtra tion, execution and audit of selected test cases should be less than the cost of that of all of the test cases of the Copyright © 2011 SciRes. JSEA
Towards MultiFaceted Test Cases Optimization 552 original pool. The goal of test cases filtration is to chunk/ filter out irrelevant, redundant and less fit test cases from the test suite. Test cases filtration is to chunk out subset of closely related test cases, so that a large portion of the defects would be found as if the whole test suite was to be used. It is often desirable to filter a pool of test cases for a program in order to identify a subset that will actu ally be executed and audited at a particular time. When it is uncertain that how many test cases can be run and au dited, it is advantageous to order or rank the test cases as per priorities, so that the tester will select the test cases as per their rank or order, which permit tester to start quick, early fixing the most of the defects [11]. Single objective formulation of test cases minimization, selection and prioritization are as follows: Definition 1 (Test Case Mi ni mization): Let T be a set of test cases and R be a set of test objectives. M is a test case minimization of T with respect to R if and only if M is a subset of T that maximizes R(T). Traditionally, R is defined with respect to a set of syntactic elements of the program under test to be covered by the test suite, such that R(X) is de fined to be the number of elements in 12 12 ,, , n rr r ,,, n rr r covered by X. Typically, we seek a set M that is smaller than T, one that is, therefore, a proper subset of T. Ideally, M will be minimal; no other minimized test suite will be smaller. In some approaches, we may seek to cover all elements of , rather than merely maximiz ing their coverage. When R is defined in terms of cover age, test case minimization becomes an instance of the set cover optimization problem. Test cases selection problem can be formulated in terms of test cases mini mization problem. It becomes minimal set cover optimi zation problem. So, test cases minimization is NPCom plete problem. 12 ,,, n rr r Definition 2 (Test Case Selection): Let P0 be a modi fied version of P and let T be a test suite. Let CA be a function which takes a pair of programs and reports the set of program elements of the form A that are different in P0 compared to P. In this context, A plays the role of test adequacy criterion, substituted by values such as <branch adequacy> and <statement adequacy>. Let be the number of elements of 0 ,,RAXP P 0 ,CAPP covered when P0 is executed on X. A test set T0 is an Aadequate test case selection of T with respect to (P, P0) if and only if T0 is a test case minimization with respect to . 00 ,,RA TPP Definition 3 (Test Case Prioritization): Let T be a test suite containing n elements and 123 ,,, , n Tttt t be a sequence on T. Let F be a function from test suite elements to some domain on which the relation ≥ im poses a total order. T’ is a test case prioritization of T with respect to F if and only if for all i, 11in , 1i1 tFt . That is, F is monotonic over T. 3. Sketch of MultiFaceted Test Case Optimization Tester will desire to find the subset of test cases that ac complish multiobjectives concurrently in order to maxi mize the value obtained from inherently expansive proc ess of executing several test cases, investigate the output produced by them. The test problem specification in cludes three main parts, the purpose of testing, test cov erage criteria and the test strategy that will be employed. Testing objectives can be categorized into two classes which fall on adequacy value or fitness value (those to be maximum) and those which fall on cost side (those to be minimum). Minimization objective can usually be in verted to convert it into maximize objective. Some ob jectives have natural fitness function, also known as con straint that delimits the set of valid test cases. In search based engineering, these constraints are treated as objec tives. In most realistic testing scenarios there will be at least one cost side and one valuebased objective. There are several constraints and may be used as test objectives [15]. Review of existing literatures have brought out several parameters for assessing the fitness and objec tives of test cases optimization like maximum number of defect detecting capability, minimum test design efforts/ cost, minimum testing cost/execution cost, maximum coveragebility of client requirements/codes, minimum test execution time/effort, and maximum mutant killing score, etc are objectives and contributing as parameters for assessing the fitness of test cases. These parameters values/scores may be maximum/minimum according to the test objectives category. Details of test cases fitness evaluation parameters are given in Table 2. Contribution of test case parameters towards their fitness is vague and imprecise. Importance of testing objectives is also fuzzy. So, Concurrent consideration of all fuzzy parameters and testing objectives creates uncertainty. All fitness pa rameters/characteristics of test cases are not important for each project and they are not contributing equally to fit ness of test cases. 3.1. Objective and Parameters Identification Existing literatures are the evidence that there are several objectives for test cases optimization and fitness evalua tion, whose details are as following (Table 1). 3.1.1. CostOriented Obj ectives The quality/fitness of the test cases is not only concern but cost is also one of the essential criteria, the whole purpose of test case optimization is to achieve more effi cient testing in terms of the cost. Selection time and exe Copyright © 2011 SciRes. JSEA
Towards MultiFaceted Test Cases Optimization553 Table 1. Multiobjective test cases optimization. S.No. Objective Category Objectives Code coverage Data Flow Based Control Flow Based Fault detection with fault Severity Fault detection Capability Mutation Killing Capability Client Requirement Execution Time Execution Efforts 1 Fitness Oriented Objectives Fault Localization Cost Benefit Analysis Execution Cost Design Cost Data Access Cost Setup Cost 2 Cost Oriented Objectives Third Party Cost Rate of Change in Requirements 3 Project Change Volatility Objectives Increase in Testing Efforts Superiority Concurrency Exclusivity 4 Optimization Constraint Objectives Dependability Table 2. Summary of multiobjective test cases optimization parameters. Parameters SubParameters Error Seeding Mutant Killing ability Fault Detecting Capability Fault Severity Statement Coverage Branch Coverage Path Coverage Loop Coverage Relational Operator Coverage Control Flow Based Adequacy Table/Array Coverage All Definition Criteria Data Flow Based Adequacy All Uses Criteria Total Efforts Design Efforts Selection Efforts Execution Efforts Requirement Change Impact Analysis on Execution Efforts Efforts Efforts Benefits Total Cost Data Access Cost Setup Cost Design Cost Selection Cost Execution Cost Requirement Change Impact Analysis on Execution Cost Cost Cost Benefits/Cost Saving Critical Requirement Coverage Rare Requirement Coverage Least Requirement Coverage Software Test Cases Fitness Evaluation Parameters Requirement Coverage Capability Rate of Change in Requirements cution time are the important factors for test cases opti mization. Software testing cost includes data access cost, third party software cost, technical resources cost, setup and simulation cost [1,2]. Execution time is a natural candidate for test cases optimization. Execution time is one realistic measure of effort. Physical execution time of test cases is hard to measure accurately. Measurement is confounded by many external factors; different hard ware, application software and operating system. Execu tion time is clearly a pressing concern for a tester, given the short build cycles within which they will typically have to perform the testing activities [7,16]. Data access cost concerns to databases software. Access to databases determines the coverage of the application under test. The population of the database will significantly affect the effectiveness of testing. We shall prefer realistic test cases rather than a mocked up version of the database, into which data may be systematically, but nonetheless synthetically added. Such synthetic data can lead to many false positives, because integrity constraints are not han dled by the automated synthetic test generation algorithm. It can also lead to many false negatives. Data access cost includes cost of real data population (Human cost or payment to data provider), data retrieving cost. Some systems interact with third parties software, creating sig nificant testing costs. There may be a price for accessing the systems of a third party. However, without such third party service access, it may not be possible to test the system fully [17]. Embedded systems are tightly coupled with their environment. These systems may consume resources that have a nontrivial cost. Cost of technical resources used in testing, is important cost driver. There may be setup costs associated with certain test cases. Setup cost includes cost of required devices, services, files. However, the setup costs for the test case may be significant in time and other costs. Such setup costs may also introduce dependencies, leading to an interaction between objectives and constraints. Testing automotive software is very expensive and requires simulation. The efforts of developing or deploying a simulation of the real system constitute a significant cost. Cost oriented objectives should be minimized in test case optimization problem [15]. 3.1.2. Adequacy ValueOriented Objectives Software test adequacy criteria are the rules to determine whether a software system has been adequately tested, which points out the central problem of software testing i.e. “what is a test data adequacy criterion?” Number of test data adequacy criteria has been proposed and inves tigated in the literature like code coverage or control flowbased test adequacy criteria, data flow based ade quacy criteria, faultbased adequacy criteria, and er Copyright © 2011 SciRes. JSEA
Towards MultiFaceted Test Cases Optimization 554 rorbased criteria. The controlflow based adequacy cri teria includes statement coverage, branch coverage, path coverage, Lengthi path coverage, loop coverage, rela tional operator coverage, table coverage. Dataflow based adequacy criteria includes all definitions criterion, all uses criterion [18,19]. Fault Sensitive model is used to measure the fault detecting capability with fault severity. Test cases that reveal more likely categories of faults are more likely to be selected or prioritized. Fault History Sensitive model is used to measure the fault detecting capability using fault history. There is no guarantee that past fault revelation confers an ongoing value to test cases. Such previously most faultrevealing test cases may be regarded as “proven star performers”. Fault based adequacy criteria include error seeding and mutant coverage or mutant killing score. So, fault detecting ca pability of test cases is very important and should be in corporated in test cases optimization [11,12,14]. Soft ware testing is humaninteractive activity. Tester, project manager, quality officer and customers are important player for software testing, each having their own ex perience, knowledge, psychology and opinions on testing priorities. Human psychological, sociological, knowledge have high impact on software testing. Business sensitive is highly subjective factor for testing. All features of software are not equally important. There are also more quantifiable business objectives. Business objectives are key concern for test cases optimization problem. Busi ness Value Measurement (BVM) is a measure in which high importance or maximum weight values are assigned to business/customer critical requirement. Importance of business/client requirements are the vital objectives for test cases optimization problem. Test cases belonging to critical business/client requirements should be executed first [2,20]. 3.1.3. Project Change Vol atility (PCV) PCV is based on the how many times consumer is modi fying the project requirements during the software de velopment cycle. PCV is one of the criteria which help to assess the requirement changes after the start of the im plementation. High PCV increases the test efforts sig nificantly and make it difficult to complete the project on time. PCV is also important for test case optimization. Test cases of high PCV value are first executed [12]. 3.1.4. Mul ti O b jective Optimi zation Constraints Most optimization problems involve various factors in fluencing the optimal results. In multiobjective test cases optimization problem, the factors that have an ef fect on the optimal solution are superiority, concurrency, exclusivity, dependability of test cases. In superiority constraint, some test cases have to be performed before others because they establish a system state in which the subsequent test cases become possible, or for which these later tests perform better in some way. We may treat this as an objective. In conjunction constraint, tests cases may be conjoined such that executing one, entails executing another. Such constraints may be soft (it is advantageous to the tester to test these two together) or hard (these two must be executed together). In exclusivity constraint, two test cases may be mutually exclusive. For instance, if one test completely exhausts a resource that is required by another, then these two tests cannot both be performed. Once again, these constraints may be soft or hard, but where they are present, the Test cases optimization proc ess must take them into account. Otherwise, the test case selection and prioritization results produced by test cases optimization may not be viable. In dependence constraint, Inclusion of one test case may affect the cost of another. For instance, if we undertake the work required by a complex setup process for a certain test case, the same setup may be reusable by other test cases. In this way there may be dependence between the cost of one test case and the costs of others. If we include one of the test cases, then the cost of all those that remain will be re duced; they share the same setup procedure and the costs associated with them [21,22]. 3.2. Problem Formulations MultiObjective Optimization is defined as problem of finding the vector of decision variables X which satisfies the constraints and optimizes a vector function whose elements represent the objective functions. Generally it can be described as a vector function that maps a tuple of parameters (decision variables) to a tuple of objectives. The decision vector is also called the parameter space and the objective vector is also called the objective space. Find the vector *** * 12 ,,, n xx xT 0 i gx which will satisfy the m inequality constraints: where 1, 2,,im and the p equality constraints 0 i hx where 1, 2,,ip . Test cases optimization is multiobjective, NPCom plete, peculiar nature problem. Multiobjective test cases optimization is scalable and multimodal optimization problem. It can be scaled to any number of objectives and constraints. Similarly, the multiobjective formula tion of test optimization can be done in various ways. It can be formulated as multiple single objective functions, weighted sum approach, bottomup approach and many others. 3.2.1. Multiple Single Objective Functions First approach is most intuitive one and simple. In this approach, N different singleobjective functions are used Copyright © 2011 SciRes. JSEA
Towards MultiFaceted Test Cases Optimization555 j to construct a multiobjective test cases optimization problem. Different objective functions are simply used as different translation of single objective function. Details of objectives of test cases optimization are given in Ta bles 12. Maximum/Minimum iij CX Maximum 11 j CX Minimum 22 j CX where , and 1, 2, 3,,jm 1, 2,,in . N is the num ber of objectives and M is the number of constraints. Z1 is fault detecting capability and Z2 is execution cost of test case. It lacks Global optimal solution. Since the test case ti optimal for objective function Z1 is not optimal for objective function Z2 and vice versa. It provides local optimal solution. It requires Pareto optimal set of solu tions. Pareto optimal set contains individual optimal so lution of each objective and trade off solutions of all ob jectives. It requires global Pareto optimal solutions. 3.2.2. Weighted Sum Approach Second Weighted Sum Approach is common and simple. A set of n objectives, , and a set of weights 123 can be combined into a single weighted objective (WO), 123 ,,,, n OOOO O ,, n w,,www 112 2 ** * nn WO xwOxwOxwOx where 123 are the weight values test objec tives. Weight Values of test objectives can be estimated by using Fuzzy Logic based approach and will be ex plored in future. Details of objectives can be found in Tables 12. ,,,, n www w 3.2.3. Bottomup Approach In bottomup approach, test cases optimization is consid ered as search space problem. Pareto optimal front is considered in this approach. Mathematical function de scribing Pareto optimal front is assumed in objective space. Pareto optimality is a notion from economics with broad range of applications in game theory and engi neering. Pareto optimality provides a set of test cases not a single test case to be exercised on software under test. Paretooptimal solutions are optimal in some sense. Therefore, like singleobjective optimization problems, there exist possibilities of having both local and global Paretooptimal solutions. Before we define both these types of solutions, we first discuss dominated and non dominated solutions. For a problem having more than one objective func tion (say, Zi, and ). Any two solu tions x(1) and x(2) can have one of two possibilitiesone dominates the other or none dominates other. Solution x(1) is said to be dominate other solution x(2), if both the fol lowing condition are true. 1, 2,, iN 1N 1) The solution x(1) is no worse than x(2) in all objec tives. 2) The solution x(1) is strictly better than x(2) in at least one objective. If any one of above two is violated, solution x(1) does not dominate the solution x(2). It is also true that if x(1) dominates the solution x(2) then we can say x(2) domi nated by the solution x(1) or x(1) is nondominated by x(2) . Between two solutions x(1) is nondominated solu tion. Based on this, the m ultiob jectiv e optimization prob lem can be defined as the problem of finding a vector of decision variables x, which optimize a vector of N ob jec tiv e functions i x where . The ob jectiv e functions are the mathematical description of the optimi zation criteria. Without the loss of generality, it is assumed that the goal is to maximize i 1, 2,,iN where . A decision vector x is said to dominate a decision vector y if and only if their ob jectiv e vectors 1, 2,,iN i x and i y satisfies: 1, 2,,iN , ii xfy and 1, ,iN , ii xfy All decision vectors that are not dominated by any other decision vector are said to form the Pareto optimal set, while the corresponding ob jectiv e vectors are said to form the Pareto frontier. Above concept can be extended to find a nondomi nated set of test cases form the pool of test cases. Con sidering the set of M test cases, each having N (N >= 1) objective function values. In Local Pareto Optimal set, if every member ti in test suite Ts, there exist no test case tj which dominates any member in the test suite Ts, then solution belonging to test suite Ts constitute local Pareto optimal test case. In Global Pareto Optimal set, if there exist no test case ti in test suites space which dominates any member in the test suites space TS, then solution belonging to test suites space TS constitute Global Pareto optimal test case. The size and shape of Pareto Optimal fronts usually depends on number of objective functions and interaction among individual objective functions. If the objective functions are conflicting in nature to each other, resulting Pareto front may span larger than if the objective are more cooperating. However in multiob jective test cases optimization problem, some objectives are conflicting in nature to others. Resulting Pareto opti mal front of multiobjective test cases optimization may contains many solutions, which can be found by using multiobjective optimization algorithm. When we con sider the case of finding a set of nondominated solutions rather than a singlepoint solution, multiobjective Evo lutionary Algorithms (MOEA) have to perform a multi Copyright © 2011 SciRes. JSEA
Towards MultiFaceted Test Cases Optimization 556 modal search for global the Paretooptimal set. Now the multiobjective test cases optimization prob lem can be defined as follows: Definition 4 (MultiFaceted Test Cases Optimiza tion) Given: a vector of decision v ariable s , x, and a set of ob jectiv e functions, i x where 1, 2,,. iN ,,, Problem: Maximize 1N xfx by finding the Pareto optimal set over the feasible set of solutions. The m ultiob jectiv e test suite minimization problem is to select a Pareto efficien t subset of the te s t suite, based on multiple test criteria. It can be defined as follows: Definition 5 (MultiObjective Test Suite Minimiza tion) Given: a test suite, T, a vector of M objective functions, fi, . 1, 2,, iN Problem: to find a subset of T, T0, such that T0 is a Pareto optimal set with respect to the set of objective functions, fi, . The objective functions are the mathematical descriptions of test criteria concerned. A subset t1 is said to dominate t2 when 1, 2,,iN ) 11 1 (,, N tft, the decision vector for t1 dominates that of t2. The multiobjective test case selection problem is to select a Pareto efficient subset of the test suite, based on multiple test criteria. It can be defined as follows: Definition 6 (MultiObjective Test Case Selection) Given: a test suite, T, a vector of N objective functions, fi, . 1, 2,,iN Problem: to find a subset of T, , such that TT is a Pareto optimal set with respect to the objective functions, fi, . The objective functions are the mathe matical descriptions of test criteria concerned. A subset t1 is said to dominate t2 when the decision vector for t1 1, 2, , iN ) 11 1 (,, N tft dominates that of t2. The multiobjective test case prioritization problem is to rank a Pareto efficient subset of the test suite, based on multiple test criteria. It can be defined as follows: Definition 7 (MultiObjective Test Case Prioritiza tion) Given: a test suite, T, a vector of N objective functions, fi, . 1, 2,,iN Problem: to find a ranks of elements of T, such that is a Pareto optimal set with respect to the objective functions, fi, . Let be a test suite con taining n elements and T 1, 2, , iN T 12 3n Tt,,, ,tt t ) be a se quence on T. The objective functions are the mathemati cal descriptions of test criteria concerned. A subset t1 is said to dominate t2 when the decision vector for t1 11 1 (,, N tft dominates that of t2. 4. Conclusion and Future Scope Testing is complex, time consuming, humanintensive, full of uncertainty and expensive activity. Choosing the right fit test cases is an important and critical task in software testing. Literature is evident that there is no direct measure of fault revelation likelihood. There are different parameters for judging the fitness of test cases. Cost is also an important factor for test cases optimiza tion involved in different ways and cannot be ignored. This complex interplay between cost and fitness/ ade quacy value is further compounded by the many addi tional validity constraints. These constraints, cost and fitness value are making test case minimization, selection and prioritization problems as multifaceted optimization problem. The present paper advocacies that such a Multifaceted approach for test cases fitness evaluation and test cases optimization is long overdue. In this paper, authors formulated the multifaceted test cases optimiza tion problem. It will be beneficial for researchers. In fu ture, evolutionary and soft computing techniques will be explored for multifaceted measurement framework for test cases optimization and fitness evaluation. REFERENCES [1] D. S. Alberts, “The Economics of Software,” Proceedings of National Computer Conference on Quality Assurance, Montvale, Vol. 45, 1976, pp. 433442. [2] S. Hema and L. Williams, “On the Economics of Re quirements Based Test Case Prioritization,” ACM SIG SOFT Software Engineering Notes, Vol. 30, No. 4, 2005, pp. 13. [3] Y. Shin and M. Harman, “Pareto Efficient MultiObjec tive Test Case Selection,” Proceedings of the Interna tional Symposium on Software Testing and Analysis (IS STA), London, ACM press, 2007, pp. 140150. [4] D. J. Mala and V. Mohan, “ABC Tester—Artificial Bee Colony Based Software Test Suite Optimization Ap proach,” International Journal of Software Engineering, Vol. 2, No. 2, 2009, pp. 1543. [5] D. J. Mala, V. Mohan, “Quality Improvement and Opti mization of Test Cases—A Hybrid Genetic Algorithm Based Approach,” ACM SIGSOFT Software Engineering Notes, Vol. 35, No. 3, 2010, pp. 114. [6] R. Mohanty, V. Ravi and M. R. Patra, “The Application of Intelligent and SoftComputing Techniques to Soft ware Engineering Problems: A Review,” International Journal of Information and Decision Sciences, Vol. 2, No. 3, 2010, pp. 233272. [7] S. Elbaum, A. G. Malishevsky and G. Rothermel, “In corporating Varying Test Costs and Fault Severities into Test Case Prioritization,” Proceedings of the 23rd Inter national Conference on Software Engineering (ICSE01), IEEE Computer Society, May 2001, pp. 329338. [8] W. E. Wong, J. R. Horgan, A. P. Mathur and A. Pasquini, Copyright © 2011 SciRes. JSEA
Towards MultiFaceted Test Cases Optimization Copyright © 2011 SciRes. JSEA 557 “A Test Set Size Minimization and Fault Detection Effec tiveness: A Case Study in Space Application,” Proceed ings of IEEE 21st Annual International Computer Soft ware and Application Conference (COMPSAC97), IEEE Press, Los Alamitos, 1997, pp. 552528. [9] S. Tallam and N. Gupta, “A Concept Analysis Inspired Greedy Algorithm for Test Suite Minimization,” The Sixth ACM SIGPLANSIGSOFT Workshop on Program Analysis for Software Tools and Engineering, New York, ACM Press, 2005, pp. 3542. [10] P. McMin, “SearchBased Software Test Data Generation: A Survey,” Proceedings in Software Testing, Verification and Reliability, Vol. 14, 2004, pp. 105156. doi:10.1002/stvr.294 [11] J. M. Kim and A. Porter, “A HistoryBased Test Prioriti zation Technique for Regression Testing in Resource Constrained Environments,” Proceedings of the 24th In ternational Conference on Software Engineering, Or lando, 2002, pp. 119129. [12] K.Varun, Sujata and M. Kumar, “Test Case Prioritization Using Fault Severity,” International Journal of Computer Science and Technology (IJCST), Vol. 1, No. 1, Septem ber 2010, pp. 6771. [13] J. A. Jones and M. J. Harrold, “TestSuite Reduction and Prioritization for Modified Condition/Decision Cover age,” IEEE Transactions on Software Engineering, Vol. 29, No. 3, March 2003, pp. 195209. doi:10.1109/TSE.2003.1183927 [14] W. E. Wong, J. R. Horgan, S. London and A. P. Mathur, “Effect of Test Set Size Minimization and Fault Detection Effectiveness,” 17th International Conference on Soft ware Engineering (ICSE’95), Seattle, 2330 April 1995. [15] H. Mark and J. Wegener, “Getting Results with Search Based Software Engineering: Tutorial,” 26th IEEE Inter national Conference and Software Engineering (ICSE 2004), Los Alamitos, 2004, IEEE Computer Society Press, pp. 728729. [16] K. R. Walcott, M. L. Soffa, G. M. Kapfhammer and R. S. Roos, “Time Aware Test Suite Prioritization,” Interna tional Symposium on Software Testing and Analysis (IS STA 06), ACM Press, Portland, 2006, pp. 112. [17] M. Bozkurt, M. Harman and Y. Hassoun, “Testing Web Services: A Survey,” Technical Report TR1001, De partment of Computer Science, King’s College London, April 2010. [18] Z. Hong, “Axiomatic Assessment of Control FlowBased Software Test Adequacy Criteria,” Software Engineering Journal, Vol. 10, No. 5, September 1995, pp. 194204. [19] D. Leon and A. Podgurski, “A Comparison of Coverage Based and DistributionBased Techniques for Filtering and Prioritizing Test Cases,” Proceedings of the 14th In ternational IEEE Symposium on Software Reliability En gineering (ISSRE’03), Denver, 2003, pp. 442453. [20] Y. Shin, M. Harman, P. Tonella and A. Susi, “Clustering Test Cases to Achieve Effective and Scalable Prioritisa tion Incorporating Expert Knowledge,” ACM Interna tional Conference on Software Testing and Analysis (IS STA 09), Chicago, 1923 July 2009, pp. 201212. [21] E. Emelie, P. Runeson and M. Skoglund, “A Systematic Review on Regression Test Selection Techniques,” In formation & Software Technology, Vol. 52, No. 1, 2010, pp. 1430. doi:10.1016/j.infsof.2009.07.001 [22] L. Zheng, M. Harman and R. Hierons, “MetaHeuristic Search Algorithms for Regression Test Case Prioritiza tion,” IEEE Transactions on Software Engineering, Vol. 33, No. 4, 2007, pp. 225237. doi:10.1109/TSE.2007.38
