Description
Question 1 (10 points) Write one simple program that prints out the value of -5 modulo 2 (e.g., -5%2 in C) in at least 4 programming languages (including scripting languages), e.g., C/C++, Java, Perl, and Python (You will write 4 programs in total). Report what you have found, and discuss at least 2 strategies to cope with such a problem. Hint: Think about how to change the developers to write different code, how to change the compilers, and how to change the standard, etc. 1 Question 2 (10 points) Below is a faulty Java program, which includes a test case that results in failure. The if-statement needs to take account of negative values. A possible fix is: if (x[i]%2 != 0) Answer the following questions for this program. (a) If possible, identify a test case that does not execute the fault. (b) If possible, identify a test case that executes the fault, but does not result in an error state. (c) If possible identify a test case that results in an error, but not a failure. (d) For the given test case, identify the first error state. Be sure to describe the complete state. pub l ic s t a t i c in t odd ( in t [ ] x ) { // E f f e c t s : i f x==n u l l throw Nu l lPo in t e rE x c ep t ion , // e l s e r e tu rn t h e number o f e l em en ts in x t h a t a re odd in t count = 0 ; fo r ( in t i =0; i < x . l e n g t h ; i++) { i f ( x [ i ]%2==1) { count++; } } return count ; } // t e s t : x = [ −10 , −9, 0 , 99 , 100 ] // Expected : 2 Question 3 (20 points) (Adapted from the original version by Patrick Lam.) Consider the following (contrived) program: c l a s s M { pub l ic s t a t i c void main ( S t r i n g [ ] argv ) { M ob j = new M( ) ; i f ( argv . l e n g t h > 0 ) ob j .m( argv [ 0 ] , argv . l e n g t h ) ; } pub l ic void m( S t r i n g arg , in t i ) { in t q = 1 ; A o = nu l l ; Im p o s s i b l e n o th in g = new Im p o s s i b l e ( ) ; i f ( i == 0 ) q = 4 ; q++; switch ( a r g . l e n g t h ( ) ) { case 0 : q /= 2 ; break ; case 1 : o = new A( ) ; new B( ) ; q = 2 5 ; break ; case 2 : o = new A( ) ; q = q ∗ 1 0 0 ; de fau l t : o = new B( ) ; break ; } i f ( a r g . l e n g t h ( ) > 0 ) { o .m( ) ; } e l s e { System . out . p r i n t l n ( ” z e r o ” ) ; } n o th in g . happened ( ) ; } } c l a s s A { pub l ic void m( ) { System . out . p r i n t l n ( ” a ” ) ; } } c l a s s B extends A { 2 pub l ic void m( ) { System . out . p r i n t l n ( ”b” ) ; } } c l a s s Im p o s s i b l e { pub l ic void happened ( ) { // ”2 b | | ! 2 b ?” , wha teve r t h e answer no th in g happens he re } } (a) Draw a Control Flow Graph (CFG) for method M.m() and be sure to include it in your a1.pdf. Use basic block CFG. See lecture notes on Structural Coverage and CFG for examples. (b) List the sets of Test Requirements (TRs) with respect to the CFG you drew in part (a) for each of the following coverages: node coverage; edge coverage; edge-pair coverage; and prime path coverage. In other words, write four sets—T RNC , T REC , T REP C , and T RP P C . If there are infeasible test requirements, please list them separately and explain why they are infeasible. (c) Using TestM-skeleton.java as a starting point, write one JUnit Test Class that achieves, for method M.m(), each of the following coverages: (1) node coverage but not edge coverage; (2) edge coverage but not edge-pair coverage; (3) edge-pair coverage but not prime path coverage; and (4) prime path coverage. In other words, you will write four test sets (groups of JUnit test functions) in total: one test set satisfies (1), one satisfies (2), one satisfies (3), and the last satisfies (4). For each test written, provide a simple documentation in the form of a few comment lines above the test function, listing which TR(s) is/are satisfied by the particular test. Consider feasible test requirements only for this part. Our ECE Linux systems (ecelinux.uwaterloo.ca) have JUnit installed (in directory /opt/). If you have any questions regarding the access to these machines, please contact our lab instructor Bernie. If you use your own machine, you can get the JUnit jar file here: https://github.com/downloads/KentBeck/junit/junit-4.8.2.jar. JUnit is included in many standard Java code development environments such as Eclipse. The discussion about JUnit 3 and JUnit 4 may be useful for Q3 and Q4: http://www.ibm.com/developerworks/java/ library/j-junit4.html Question 4 (30 points) (Adapted from the original version by Sarfraz Khurshid) You are to construct a partial1 control-flow graph from the bytecode2 of a given Java class using the ASM framework, version 4.0 (http://asm.ow2.org). You can download http://download.forge.objectweb.org/asm/asm-4.0-bin.zip and use all/asm-all-4.0.jar. If you use ecelinux machines, the jar file is in directory /opt/. To illustrate, consider the following class C: pub l ic c l a s s C { in t max( in t x , in t y ) { i f ( x < y ) { return y ; } e l s e return x ; } } which can be represented in bytecode as (e.g. the output of javap -c): Comp i led from ”C . j a v a ” pub l ic c l a s s e e379k . p s e t 1 .C extends j a v a . l a n g . Ob j e ct { pub l ic C( ) ; Code : 0 : a l o a d 0 1 : i n v o k e s p e c i a l #8; //Method j a v a / l an g / O b j e c t .”< i n i t >” :()V 4 : return in t max( int , in t ) ; Code : 1This assignment ignores the labels that are traditionally annotated on nodes and edges, as well as the edges that correspond to method invocations or jsr[ w] bytecodes. 2http://java.sun.com/docs/books/jvms/second_edition/html/VMSpecTOC.doc.html 3 0 : i l o a d 1 1 : i l o a d 2 2 : i f i c m p g e 7 5 : i l o a d 2 6 : i r e t u r n 7 : i l o a d 1 8 : i r e t u r n } You can easily draw the corresponding control-flow graph. Graph representation of control-flow. Implement the class CFG to model control-flow in a Java bytecode program. A CFG object has a set of nodes that represent bytecode statements and a set of edges that represent the flow of control (branches) among statements. Each node contains: • an integer that represents the position (bytecode line number) of the statement in the method. • a reference to the method (an object of org.objectweb.asm.tree.MethodNode) containing the bytecode statement; and • a reference to the class (an object of class org.objectweb.asm.tree.ClassNode) that defines the method. Represent the set of nodes using a java.util.HashSet object, and the set of edges using a java.util.HashMap object, which maps a node to the set of its neighbors. Ensure the sets of nodes and edges have values that are consistent, i.e., for any edge, say from node a to node b, both a and b are in the set of nodes. Moreover, ensure that for any node, say, n, the map maps n to a non-null set, which is empty if the node has no neighbours. You can find a partial implementation of the CFG class in CFG-skeleton.java. You’ll need to rename it to CFG.java to continue. Your first task is to fill in the implementation of this class. Then you will write JUnit test cases to achieve some coverage criterion. (a) Adding a node (2 points). Implement the method CFG.addNode such that it creates a new node with the given values and adds it to nodes as well as initializes edges to map the node to an empty set. If the graph already contains a node that is .equals to the new node, addNode does not modify the graph. (b) Adding an edge (2 points). Implement the method CFG.addEdge such that it adds an edge from the node (p1, m1, c1) to the node (p2, m2, c2). Your implementation should update nodes to maintain its consistency with edges as needed. If the node does not exist in the graph, add the node. (c) Deleting a node (4 points). Implement the method CFG.deleteNode such that it deletes a node with the given values, and all edges connected to the node, if any. If the graph does not contain a node that is .equals to the new node, deleteNode does not modify the graph. Your implementation should update nodes to maintain its consistency with edges as needed. (d) Deleting an edge (4 points). Implement the method CFG.deleteEdge such that it deletes an edge from the node (p1, m1, c1) to the node (p2, m2, c2). (e) Reachability (6 points). Implement the method CFG.isReachable such that it traverses the control-flow graph starting at the node represented by (p1, m1, c1) and ending at the node represented by (p2, m2, c2) to determine if there exists any path from the given start node to the given end node. If the start node or the end node are not in the graph, the method returns false. (f) Testing (12 points). I have also provided a class CFGTest in CFGTest.java, which exercises your CFG class. Examine this test class. Does it satisfy NC and EC for each of the method you write? Justify your answer. If it does not satisfy either coverage criterion, write additional JUnit test cases to satisfy one of them. 4
