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 http://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. 3
