Mutation Testing by Using Formal Method

Mutation Testing by Using Formal Method Jaspreet Singh Abstract Mutation testing was introduced in 1970’s in the field of software testing as a process of testing the test suites by intentionally seeding errors i.e. mutation operators, into the original program’s source code. Its main purpose is to verify the functionality of the test cases which are executed with the aim of catching the variations between the program and the mutants. It’s extremely essential to improve the efficiency and adequacy of test cases. Hence, the goal is to make the mutant program fail. This paper depends upon the literature survey of mutation testing by using formal methods. Keywords- Mutant, Code, Program, Test cases, Kill, PIMS. I INTRODUCTION Since 1970’s, this technique is used by developers for validating the test cases as well as the test data generation. It’s a well know process to computer scientists for years. But due to heaviness of the method, it demanded huge computational power which reduced its usability. But the advancements in software engineering and the era of increased computational power, has laid it continue to serve as the most powerful method of verifying the functionality and performance of test suites. The objective is to improve the aptness and efficiency of test cases where the programmer will intentionally alter the original program’s source code by injecting a faulty piece of code known as a mutant, into it. The resultant code is referred to as mutated code. The mutation procedure will create many versions of the original program. Each version is known as a mutant. The execution of a mutant will verify the proficiency of the test case. If the output of the original program wi ll vary with that of the mutant one causing each faulty version to fail [1]. The resultant mutant is killed and the test case is saved considering it an adequate one. More the number of mutants killed by a test case, the better is the competency of the test case. Mutation testing is proficient in testing programs at the unit level, integration level and the specification level. It has been applied to many programming languages like C, C++, etc. and is a part of white box test technique [2]. II LITERATURE SURVEY Initial concepts of mutation were introduced by Richard Lipton in a class term paper titled â€Å"Fault Diagnosis of Computer Programs†. The first referred publications were presented in the late 1970’s ; the DeMillo, Lipton. PIMS was one of the first mutation testing tools [3]. It originated the basic procedure typically used in mutation analysis of creating mutants, obtaining test cases from the users, and then executing the them on the mutants to conclude how many mutants were killed. The most widely used tool among researchers was the Mothra mutation toolset [3], which provided an integrated set of tools, each of which performed an individual, separate task to support mutation analysis and testing. Several variants of Mothra were created in the early 1990s, including one that implemented weak mutation [4], and several distributed versions. A compiler-integrated mutation tool for C was also developed [5], and tool that was based on program schemata [6]. However, thes e tools were primarily used by the researchers who developed them and the only widely used system besides the original version of Mothra has been the Proteum mutation system for C [7]. A Formal Methods Formal methods are techniques based on mathematics and formal logic. It supports automated consistency checking and testing specifications. It helps finding defects when applied to good quality software. Such methods allow large number of classes of test cases having finite proof with support least dependence on subjective reasoning [8]. B The benefits of using Formal Methods include: Product-focused measure of correctness: The use is used for the of Formal correctness of a system. Early detection of defects: Formal Methods can be applied to earlier detection and elimination of design defects and associated late cycle rework. Guarantees of correctness: Unlike testing, formal analysis tools go through all possible execution paths through the system. If there is any way to reach a fault condition, a tool will find it. In a multi-threaded system where concurrency is an issue, formal analysis can explore all possible interleavings and event orderings[13]. Fig-1 Formal Methods such as model checking examine more system behaviors for safety violations than testing alone III NOTIONS OF FORMAL PROOF: A Mathematical proof: A formal proof is a complete and convincing mathematical argument, presenting the full logical justification for each proof of set of theorems B Machine-checked proof: A formal proof is evidence accepted by a proof checker showing that a conjecture is a valid consequence of given axioms. C Hilbert proof: A formal proof in a theory is a sequence of formulas, each of which is either an axiom of or a direct consequence of preceding formulas in the sequence by virtue of a rule of inference associated with the underlying formal system[14]. IV TYPES OF MUTANTS We define the following classification of mutants as follows: A Killed Mutant; which was killed by a test case which was specifically written to kill it. The concept behind mutation testing is that modifying the source code of a given unit (or mutating it) should cause the test that operates on that unit to fail. Example : Method and Corresponding Unit Test //original code under test public class Example { public boolean is LessThanThree(int number) { return (number Example : Mutated Method public class Example { public boolean isLessThanThree(int number) { return (number > 3); } } Notice that with this mutation, the method testLessThanThree would fail because the mutated method now returns the boolean number > 3, which in this case would be false and the assert statement is checking to see that the desired result is true. The method TestLessThanThreeFail would not fail, however, because 3 is not greater than 3 and the returned boolean would be false, which is what the assert statement is checking for. Because testLessThanThree failed, this mutant is said to be killed; the mutation caused the test to fail, which means the test is adequately catching this kind of mistake[12]. Dead on Arrival (DOA)- Mutant that was killed by the initial test suite found in the test bed. Ignored Mutant which a study participant encountered but did not kill. Living-Mutant which could not be killed due to time constraints (whether or not the mutant was encountered). Crossfire- Mutant that was killed by a test case intended to kill a different mutant. Stubborn.-Mutant that cannot be killed by a test case due to logical equivalence or language constructs. B Ordering Mutants: Let P be an implemented program and P’ be a first order mutant that differs from P at location l. A test case, t1 can distinguish P form P’ provided the following necessary and sufficient conditions hold on executing P and P’ with starting state t1: This has 3 properties: The execution must reach location l ( ); The evaluation of expressions at location l in P and P’ must result in different values at least once ( ) ; The final states on termination of execution of P and P’ must be different ( ). Properties (a) and (b) follow by observing that the location must be reached and in the case of a c-location the two executions must result in two different states if they are to be distinguished. 1) Process of Mutation Testing NO YES YES NO Fig. 2 Working of Mutation process The process of mutation analysis is shown in fig. 2. Steps are as follows: The program is being fed as an input and is executed. The resultant is checked . If the resultant indicates successful completion of the program, then terminate. If not, then create mutants (mutated code). A mutant, as previously mentioned is an intentionally altered program by the programmer. It is fed by some errors termed as mutation operators. Test cases are created to the system to be executed on the program. Execute the test cases against the mutant. If the output of the mutant is correct, then execute the test case on each version of the mutant. If not, then again the output of the original program is checked. Compare the output of the original source code with that of each version’s. A decision is made after determining the output of the original code with that of the mutated one. If the output differs, then the test is considered to be an adequate one and is executed on each of the mutants of the program The mutant that is detected is marked as dead/killed. Whereas, output being same indicates inadequacy of the test case and the program. 2) Mutation Operators- Taxonomy of mutation operators: 3)Statement Mutations: The mutant is produced by replacing the keywords in the statement, like While to do while While to For Example for Switch statement: Program Switch Statements case 0: i++; case 1: i = 4; Mutant: case 1: i++; case 0: i = 4; Operator Mutations The mutant is produced by changing the operator in the original source code. For ex: a=1, b=0 If (a b) { C=1; } else { C=0;} The condition mutation operator would replace with the mutation operator || and gives us the following mutant: If(a||b) { C=1; } else { C=0;} Variable Mutations Replace each variable with another variable declared in the same scope (variable types should be the same). Constant Mutations In constant mutations, the mutant tends to fail as there is no mutation operator to be replaced Ex: If (1) { printf (â€Å"How are you?†); } Else {printf(â€Å"I am fine.†);} In this case, mutation testing fails. [2] Example Original piece of a code: c=a+b; where a=3and b=2 Putting the values for a and b, it will result in 3+2=5 Now, possible mutants are c=a-b; , c=a/b; and c=a*b; Such mutations are mostly easier for a test suite to recognize if (a == b) { //do something } will be mutated to if (a != b) { // do something } Here, == is replaced by !=. V PROS AND CONS Mutation procedure is widely acceptable as an essential way to determine the fault-detecting effectiveness of the test sets. Now software developers and testers everywhere can enjoy the most powerful error- detection capabilities with the speed and ease of use of an automatic running debugging tool [9]. But, at the same time it pertains some disadvantages also, which are as follows: A PRO’S: Providing the testers with a target- One of the major advantages of mutation testing is that it provides the tester with a target. The tester has to generate a test data with the aim of killing all the generated mutants. Therefore, we can generate an adequate test data set that is capable enough to detect errors in the program.[10] Bringing more confidence in customers and testers- The customer also benefits from this technique , as he receives a more reliable and bug free software. This will increase confidence in them which will profit your company where it matters most. Mutation Testing originated as a means of creating more effective test suites by which the tester can be more confident that his program is adequately tested. It’s a powerful fault-based testing approach for competent programmers. B CON’S: Computationally expensive due to lack of automated tool..Mutation Testing is complicated and time-consuming to perform without an automated tool. Often, there are massive number of mutants that are generated for a original program as number of mutants is directly proportional to the mutation operators applied. Hence it is computationally expensive to run. The test cases on each and every mutant. It is also expensive to compile and execute every mutant [9][10]. An example of this is shown in Table No. 2 given below. Table 2 Increase In Computational Cost Such mutants only contribute in increasing the computational cost as the efforts needed to check if mutants are equivalent or not, can be very high even for small programs against the test cases. [2] Equivalent Mutants, one of the biggest problems- Syntactically different from the original program. But, semantically the same. Consider the example given in Table No. 3 given below: The equivalent mutant is generated by changing the operator Table 3 Equivalent Mutants Manual equivalent mutant detection is quite tedious- The other barrier to more widespread use of mutation testing is the amount of manual labor involved in using this technique. Hence, developing mutation adequate test cases can be very labor-intensive.[2] VI CONCLUSION This paper provides a detailed review of mutation testing .It covers the objective, Analysis of previous mutation systems, Formal Methods, working of mutation testing and efficient test case generation, Taxonomy of mutation operators and its Pro’s and Con’s . Mutation testing has given a great contribution in the field of software testing and provided the testers with a matured and affordable technique in detecting best test suites. Future Scope Our future scope is to develop a more advanced mutation testing approach that minimizes the issue of computational cost up to a certain level with the aim of killing all the possible mutants and thereby generating good test cases. REFERENCES [1] Yue Jia ans Mark Harman. An Analysis and Survey of the Development of Mutation Testing. IEEE Transactions on Software Engineering, King’s College London, Centre for Research on Evolution Search and Testing (CREST), Strand, London, WC2R 2LS, UK, 2010 [2] Hiralal Agrawal , Richard A. DeMillo, Bob Hathaway, William Hsu, Wynne Hsu, E.W. Krauser, R.J. Martin and Aditya P. Mathur, â€Å"Design Of Mutant Operators For The C Programming Language†, Software Engineering Research Centre, Department of Computer Sciences, Purdue University, W. Lafayette, IN 47907, Revision 1.02, March 20, 1989. [3] D. M. S. Andre. Pilot mutation system (pims) user’s manual. Technical report GIT-ICS-79/04, Georgia Institute of Technology, April 1979 [4] A.J Offutt and S.D.Lee. An empirical evaluation of weak mutation. IEEE Transactions on Software Engineering , 20(5): 337-344, May 1994. [5] R.A. DeMillo, E.W.Krauser, and A.P. Mathur. Compiler-integrated program mutation. In Proceedings of the Fifteenth Annual Computer Software and Applications Conference (COMPSAC’ 92), Tokya, Japan, September 1991. Kogakuim University, IEEE Computer Society Press. [6] R. Untch, A.J. Offutt, and M.J. Harrold. Mutation analysis using program schemata. In Proceedings of the 1993 International symposium on Software Testing, and Analysis, pages 139-148, Cambridge MA, June 1993. [7] M.E. Delamaro and J.C. Maldonado. Proteum – A tool for the assessment of test adequacy for C programs. Proceedings of the Conference on Performability in Computing Systems, pages 75-95. July 1996. [8] A. Jefforson Offutt, A practical system for mutation testing: Help for the common programmer, ISSE Department, George Mason University,Fairfax, VA 22030, 1994. [9] S. Madiraju ,S. Ramakrishnan and A.J.Hurst, â€Å"Towards Automated Mutation Testing†, March 2004. [10] A. Jefferson Offutt and Roland H.Untch, Mutation : Uniting the orthogonal, A. Jeerson Offutt ISE Department, George Mason University Fairfax, VA USA, Roland H.Untch, Department of Computer Science Middle Tennessee State University Murfreesboro, 2000. [11] David L. Dill, â€Å"Formal Methods Specification and Verification Guidebook for software and computer systems† Vol. 1, Computer Science Department, Stanford University, Stanford, CA 94305, July 1995. [12] Ben Smith and Laurie Williams, â€Å"Software Engineering†, Department of computer science North Carolina State University. [13] Murali Rangarajan, â€Å"Formal Methods†,Honeywell Laboratories 3660 Technology Drive Minneapolis, MN 55418. [14] James G. Williams and Marshall D. Abrams, â€Å"Formal Methods And Models†.