This is known as the oracle problem [14].For example,in Algorithm 1:Cod's process for coverage tool validation compiler testing.it is not easy to verify whether the generated Data:The profiler T under test,the program P,the input i executable code by a compiler is functionally equivalent to the Result:reported bugs given source code.Even if the oracle is available,manually 1 begin checking the oracle results is tedious and error-prone [15]. /Step 1:Extract output and coverage [16].As a matter of fact,the oracle problem has been "one of information the most difficult tasks in software testing"[16]. 2 P:re←-compi1e(P) Metamorphic testing (MT)was coined by T.Y.Chen in 3 getOutput(execute(Pere,i)) 4 C+T.extractCoverage (execute(Pere.i)) 1998 [12],which can be exploited to alleviate the oracle problem.Based on the existing successful test cases (that /Step 2:Generate variants via transformation have not revealed any failure,such as running too long or p← genVariant (P.C) returning abnormal values),MT generates follow-up test cases D xe←compile(P') by making reference to metamorphic relations (MR),which 7 Ogetoutput (execute(Pize i)) are the necessary properties of the target function or algorithm C'T.extractCoverage(execute(Pere,i)) in terms of multiple inputs and their expected outputs.Let us /Step 3:Compare outputs and reports consider a program P implementing function F on domain /First Stage D.Let t be an initial successful test case,i.e.t D and ifO≠O'then reportBug() the execution output P(t)equals to the expected value F(t). /Second Stage MT can be applied to generate a follow-up test case t'D 1 else if inconsistent (C,C')then base on t and a pre-defined MR (i.e.,metamorphic relation). reportBug() For program P,a MR is a property of its target function F.For instance,suppose F(x)=sin(z),then the property /Generate a variant for program P under sin(-x)=sin(z)is a typical MR with respect to F.Hence, coverage C 13 Function genvariant (Program P.Coverage C) given a successful test case,say t =1.2,MT generates its p'←p follow-up test case t'=-1.2,and then runs the program foreach s E getstmts (P)A Cp(s)=0 do over t'.Finally,two outputs (i.e.,P(t)and P(t'))are checked 16 Lp'.delete(s) to see if they satisfy the expected relation P(t)=P(t').If 公 if isCompiable(P')then the identity does not hold,a failure manifests. 18 return p In our work,we apply MT to the validation of code coverage 19 else 20 genvariant(P,C) profilers.Each program becomes a test case fed to the profilers. Given a program P and the code coverage profiler under /Check whether coverages is inconsistent testing,running P with an input i would produce the execution 21 Function inconsistent(Coverage C.Coverage C') output O and a coverage report C from the coverage profiler, 22 foreach s∈CAs∈C'do The coverage report C records which lines of code are executed 23 ifCp(s)≠Cp(s)then (or unexecuted)and how many times are executed exactly. return True Note that this program P is the initial test case according return False to the notions of MT.A follow-up test program p'can be generated based on the following MR: Given a program,the unexecuted code can be eliminated tion of a given test program,(2)generating equivalent variants since these code has no impact with the execution output or based on code coverage report,and (3)comparing the outputs the coverage report specifically for the executed part. and coverage results to uncover bugs. In other words,by taking advantage of the coverage infor- Algorithm I is the main process of Cod.At the first mation C,we generate P,a functionally equivalent variant of place,Cod compiles the program P and profiles the execution P by removing the un-executed code statements of P.We run information with input i to collect:(1)the output O(which p'on the same input i and obtain the output 'and coverage may correspond to a return value or an exit code)and(2)the results C,accordingly.A bug can then be discovered if 1)the code coverage information C(Lines 2-4).It then generates execution output is not equal to the new one O,or 2)there the variant P with respect to program P(Line 5)and collects exists inconsistency between the coverage information for the respective output O'and code coverage C'(Lines 6- executed code inside C and C.Figure 2 shows our framework 8).Finally,it compares the outputs together with the code for the self-validation of code coverage profilers. coverage reports to validate the coverage profiler.A potential bug in 7 is reported if any of them is inconsistent (Lines 9- B.Our Algorithm 12).We discuss each step in details as follows. Based on our formulation,we implemented a tool Cod for Extracting Coverage Information For each test program P, detecting bugs in C code coverage profilers.Cod consists of we first compile it with particular options to generate the three main steps:(1)extracting output and coverage informa- executable binary Pere.The options enables the compiler 82This is known as the oracle problem [14]. For example, in compiler testing, it is not easy to verify whether the generated executable code by a compiler is functionally equivalent to the given source code. Even if the oracle is available, manually checking the oracle results is tedious and error-prone [15], [16]. As a matter of fact, the oracle problem has been “one of the most difficult tasks in software testing” [16]. Metamorphic testing (MT) was coined by T.Y. Chen in 1998 [12], which can be exploited to alleviate the oracle problem. Based on the existing successful test cases (that have not revealed any failure, such as running too long or returning abnormal values), MT generates follow-up test cases by making reference to metamorphic relations (MR), which are the necessary properties of the target function or algorithm in terms of multiple inputs and their expected outputs. Let us consider a program P implementing function F on domain D. Let t be an initial successful test case, i.e. t ∈ D and the execution output P(t) equals to the expected value F(t). MT can be applied to generate a follow-up test case t ∈ D base on t and a pre-defined MR (i.e., metamorphic relation). For program P, a MR is a property of its target function F. For instance, suppose F(x) = sin(x), then the property sin(π−x) = sin(x) is a typical MR with respect to F. Hence, given a successful test case, say t = 1.2, MT generates its follow-up test case t = π − 1.2, and then runs the program over t . Finally, two outputs (i.e., P(t) and P(t )) are checked to see if they satisfy the expected relation P(t) = P(t ). If the identity does not hold, a failure manifests. In our work, we apply MT to the validation of code coverage profilers. Each program becomes a test case fed to the profilers. Given a program P and the code coverage profiler under testing, running P with an input i would produce the execution output O and a coverage report C from the coverage profiler, The coverage report C records which lines of code are executed (or unexecuted) and how many times are executed exactly. Note that this program P is the initial test case according to the notions of MT. A follow-up test program P can be generated based on the following MR: Given a program, the unexecuted code can be eliminated since these code has no impact with the execution output or the coverage report specifically for the executed part. In other words, by taking advantage of the coverage infor￾mation C, we generate P , a functionally equivalent variant of P by removing the un-executed code statements of P. We run P on the same input i and obtain the output O and coverage results C , accordingly. A bug can then be discovered if 1) the execution output O is not equal to the new one O , or 2) there exists inconsistency between the coverage information for executed code inside C and C . Figure 2 shows our framework for the self-validation of code coverage profilers. B. Our Algorithm Based on our formulation, we implemented a tool Cod for detecting bugs in C code coverage profilers. Cod consists of three main steps: (1) extracting output and coverage informa￾Algorithm 1: Cod’s process for coverage tool validation Data: The profiler T under test, the program P, the input i Result: reported bugs 1 begin /* Step 1: Extract output and coverage information */ 2 Pexe ← compile(P) 3 O ← getOutput(execute(Pexe, i)) 4 C←T .extractCoverage(execute(Pexe, i)) /* Step 2: Generate variants via transformation */ 5 P ← genVariant(P, C) 6 P exe ← compile(P ) 7 O ← getOutput(execute(P exe, i)) 8 C ← T .extractCoverage(execute(P exe, i)) /* Step 3: Compare outputs and reports */ // First Stage 9 if O = O then 10 reportBug() // Second Stage 11 else if inconsistent(C, C ) then 12 reportBug() /* Generate a variant for program P under coverage C */ 13 Function genVariant(Program P, Coverage C) 14 P ← P 15 foreach s ∈ getStmts(P) ∧ CP (s)=0 do 16 P .delete(s) 17 if isCompiable(P ) then 18 return P 19 else 20 genVariant(P, C) /* Check whether coverages is inconsistent */ 21 Function inconsistent(Coverage C, Coverage C ) 22 foreach s ∈C∧ s ∈ C do 23 if CP (s) = C P (s) then 24 return True 25 return False tion of a given test program, (2) generating equivalent variants based on code coverage report, and (3) comparing the outputs and coverage results to uncover bugs. Algorithm 1 is the main process of Cod. At the first place, Cod compiles the program P and profiles the execution information with input i to collect: (1) the output O (which may correspond to a return value or an exit code) and (2) the code coverage information C (Lines 2 - 4). It then generates the variant P with respect to program P (Line 5) and collects the respective output O and code coverage C (Lines 6 - 8). Finally, it compares the outputs together with the code coverage reports to validate the coverage profiler. A potential bug in T is reported if any of them is inconsistent (Lines 9 - 12). We discuss each step in details as follows. Extracting Coverage Information For each test program P, we first compile it with particular options to generate the executable binary Pexe. The options enables the compiler 82