Control flow testing.

Problem

Consider the following code

$1$

$$int binsearch

$($

int X

$,$

$$int V

$[$

$]$

$,$

$$int n

$)$

$2$

$\{$

$3$

$$int low

$,$

$$high

$,$

$$mid

$,$

$$i ;

$4$

$$low

$=$

$0$

;

$5$

$$high

$=$

$$n

$-$

$1$

;

$6$

$7$

$$for

$($

$$i

$=$

$0$

; i

$$

$$high ; i

$+$

$+$

$)$

$8$

$\{$

$9$

$$if

$($

$$V

$[$

$$i

$]$

$>$

$$V

$[$

$$i

$+$

$1$

$]$

$)$

$10$

$$return

$-$

$2$

;

$11$

$\}$

$12$

$13$

$$while

$($

$$low

$$

$=$

$$high

$)$

$14$

$\{$

$15$

$$mid

$=$

$($

$$low

$+$

$$high

$)$

$/$

$2$

;

$16$

$$if

$($

$$X

$$

$$V

$[$

$$mid

$]$

$)$

$17$

$$high

$=$

$$mid

$-$

$1$

;

$18$

$$else

$19$

$$if

$($

$$X

$>$

$$V

$[$

$$mid

$]$

$)$

$20$

$$low

$=$

$$mid

$+$

$1$

;

$21$

$$else

$22$

$$return mid ;

$23$

$\}$

$24$

$$return

$-$

$1$

;

$25$

$\}$

This code takes as input a sorted array V of size n

$,$

$$and an integer X

$,$

$$if X exists in the array it will

return the index of X

$,$

$$else it will return

$-$

$1.$

$1.$

$$Draw a CFG for binsearch

$($

$)$

$.$

$2.$

$$From the CFG

$,$

$$identify a set of entry

$$

exit paths to satisfy the complete statement coverage

criterion.

$1$

$3.$

$$Identify additional paths, if necessary, to satisfy the complete branch coverage criterion.

$4.$

$$For each path identified above, derive their path predicate expressions.

$5.$

$$Solve the path predicate expressions to generate test input and compute the corresponding

expected outcomes.

$6.$

$$Are all the selected paths feasible? If not, select and show that a path is infeasible, if it exists.

$7.$

Can you introduce two faults in the routine so that these go undetected by your test cases

designed for complete branch coverage?

$8.$

Suggest a general way to detect the kinds of faults introduced in the previous step. an example of cfg and the different paths statemen sc and branchSCPath $1,1-2-3($F$)-10($F$)-11-13$

SCPath $2,1-2-3($T$)-4($T$)-5-6($T$)-7($T$)-8-9-3($F$)-10($T$)-12-13$

$4\mathrm{.}5$ PATH SELECTION CRITERIA

$99$

Figure $4\mathrm{.}8$ Dashed arrows represent the branches not covered by statement covering in Table $4\mathrm{.}4.$

TABLE $4\mathrm{.}5$ Paths for Branch Coverage of CFG of Figure $4\mathrm{.}7$

BCPath $11-2-3($F$)-10($F$)-11-13$

BCPath $2,1-2-3($T$)-4($T$)-5-6($T$)-7($T$)-8-9-3($F$)-10($T$)-12-13$

BCPath $3,1-2-3(T)-4(F)-10(F)-11-13$

BCPath $4,1-2-3($T$)-4($T$)-5-6($F$)-9-3($F$)-10($F$)-11-13$

BCPath $5,1-2-3(T)-4(T)-5-6(T)-7(F)-9-3(F)-10(F)-11-13$bc