Description
Question 1 (10 points)
For an acyclic graph, does Prime Path Coverage (PPC) subsume Complete Path Coverage (CPC)? Answer yes or no
explicitly and then justify your answer.
Question 2 (20 points)
Compile program sll buggy.c with -g option, execute it with Valgrind to find some bugs, and answer the following
questions:
(a) Run TC1 and report the memory problem you find. Briefly explain the problem. Paste the Valgrind outputs.
Fix the bug, and submit your code “sll fixed.c”. Using comments, e.g., “Fix for Q2 (a)”, to mark the bug fixes
in your program, and explain how you fix the bugs here in the report. (7 Points)
(b) Run TC2 and report the memory problem you find. Briefly explain the problem. Fix the bug, and submit your
code “sll fixed.c”. Using comments, e.g., “Fix for Q2 (b)”, to mark the bug fixes in your program, and explain
how you fix the bug here in the report. (6 Points)
(c) Generate a test case that would cause a new bug, e.g., a buffer overflow bug. Attach the test case, and briefly
explain the problem. Fix the bug, and submit your code “sll fixed.c”. Using comments, e.g., “Fix for Q2 (c)”,
to mark the bug fixes in your program, and explain how you fix the bug here in the report. (7 Points)
Note that you only submit one sll fixed.c file with all the fixes. For instructions on downloading Valgrind and installing
it, please refer to the tutorial slides. You should do this exercise in Unix/Linux. You may find ‘gdb’ very useful. Our
ECE Linux systems (ecelinux.uwaterloo.ca) should have Valgrind installed. If you have any questions regarding the
access to these machines, or the installation of Valgrind, please contact Bernie.
TC 1
i n s e r t >i n s e r t >d e l e t e >e x i t
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : i
e n t e r th e t e l :>100
e n t e r th e name:>Tom
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : i
e n t e r th e t e l :>111
e n t e r th e name:>Mary
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : d
e n t e r th e t e l :>111
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : x
TC 2
i n s e r t >i n s e r t >i n s e r t >e d i t >d e l e t e a l l >e x i t
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : i
e n t e r th e t e l :>100
e n t e r th e name:>Tom
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : i
e n t e r th e t e l :>111
e n t e r th e name:>Mary
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : i
e n t e r th e t e l :>112
e n t e r th e name:>John
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : e
e n t e r th e o l d t e l :>111
e n t e r th e new t e l :>111
e n t e r th e new name:>Mary
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : a
[ ( i ) n s e r t , ( d ) e l e t , d e l e t e ( a ) l l , d ( u ) p l i c a t e , ( e ) d i t , ( p ) r i n t , e ( x ) i t ] : x
2
Question 3 (10 points)
Consider the following binary search function from en.literateprograms.org. Propose two non-stillborn and nonequivalent mutants of this function. Write down test inputs which strongly kill these mutants (syntax doesn’t
matter) and the expected output of your test cases on the original code and on the mutant.
i n t bi n a r y s e a r c h ( i n t a [ ] , i n t low , i n t high , i n t t a r g e t ) {
// bi n a r y s e a r c h f o r t a r g e t i n a [ low , hi gh ]
w hil e ( low <= hi gh ) {
i n t middle = low + ( hi gh − low ) / 2 ;
i f ( t a r g e t < a [ middle ] )
hi gh = middle − 1 ;
e l s e i f ( t a r g e t > a [ middle ] )
low = middle + 1 ;
e l s e
r e t u r n middle ;
}
r e t u r n −1; // r e t u r n −1 i f t a r g e t i s not found i n a [ low , hi gh ]
}
Question 4 (30 points)
(Adapted from the original version by Patrick Lam.)
We will identify test requirements and augment a test suite to achieve prime path coverage of a specific method in
the free Java application SweetHome3D, available at
https://www.sweethome3d.eu.
Download the source code from LEARN (version 3.7). We will work with computeIntersection() in class PlanController.
(a) Creating a CFG (6 points). Draw the control-flow graph for the method computeIntersection(). It will
be unmanageable unless you group together statements into basic blocks. Then draw the CFG again by replacing
the content in the nodes with defs and uses.
(b) Identifying requirements for PPC (4 points). Identify the test requirements for prime path coverage
in computeIntersection().
(c) Identifying requirements for ADC, AUC, ADUPC (7 points). Identify the test requirements for
All-Defs Coverage, All-Uses Coverage, and All-du-paths Coverage in computeIntersection(). Don’t forget about
the paths where the defs and uses of the same variable are in the same node.
(d) Comparing coverage criteria (4 points). Compare the sets of test requirements you’ve collected. Point
out strengths and weaknesses of these criteria, for instance by giving scenarios where one criterion is going to help
you find something that another criterion wouldn’t; discuss whether the additional number of test requirements is
worth it in this case. Simply saying one criterion subsumes another is not enough.
(e) Creating tests (9 points). Create tests which achieve prime path coverage in computeIntersection().
Justify your answer.