Software Testing, Verification and Validation Karl J. Lieberherr COM 3220 Spring 1998 =========================================================================== Due date: April 7, 1998 This assignment is stored in file $TVV/hw/1 in file assign.txt ================ The course home page is: http://www.ccs.neu.edu/home/lieber/com3220/com3220.html ================ ASSIGNMENT 1 TESTING GRAPH TRAVERSAL ALGORITHMS ============================================================== On CCS Northeastern machines, TVV=/home/lieber/.www/com3220/ On the WWW, TVV = http://www.ccs.neu.edu/home/lieber/com3220 Use the following header for your electronic homework submissions and put it at the top of the message: Course number: COM 3220 Name: Account name: Assignment number: Date: ============================================== Computer use: All the software you test is written in Java and for some of it we have all the source code available. To run the software on college UNIX machines you must use a machine running Solaris (all the UltraSparcs do). If you use your own computer, you have to install the appropriate Java software yourself. It is all provided for free. It is suggested that initially you use the College UltraSparcs before you install the software on your own machine. ============================================== Whenever you have questions about course material, please send e-mail to: mail lieberherr@ccs.neu.edu com3220-grader@ccs.neu.edu ccs.courses.com3220@ccs.n eu.edu All messages which I send to the class are archived in /proj/demsys/logs-lieber/com3220 ========= READING: Read chapters 1 through 4 in the text book. Get a Java book and read about Java. We will do white-box testing of Java programs. For a simple Java program, see: $TVV/hw/1/automata-intersection. Review your course notes on discrete mathematics: graphs and paths and related algorithms. ============= The purpose of this homework is to have a concrete, interesting example where you can apply the testing process described in the text book. Use a black box testing approach (you don't have to look at the source code). Write test requirements test specifications tests (run them) bug reports See page 11 of the text book for an overview. Finding paths in graphs is a very common algorithmic task which appears in many applications. The simplest form of path finding is that you are given a graph G and two nodes A and C and you have to find all the paths Paths(A,C) from A to C in G. This homework is about testing a program which computes paths in a dag (directed acyclic graph). To simplify the problem, we assume that G is a dag and then Paths(A,C) is a finite set. If G could contain cycles then the path set might be infinite. It turns out that path finding algorithms are implemented in Demeter/Java. You don't have to know very much about Demeter/Java to test its path finding algorithms. To make the path finding problem more interesting, we use the following two kinds of path specifications: from A via B to C method f1 from A bypassing B to C method f2 Method f1 will find all the paths from A to C which must go through B. Method f2 will find all the paths from A to C which must not go through B. For those of you who know about automata theory you can view the path finding problem as computing the intersection of two automata. Namely you take the intersection of the automaton corresponding to the path specification and the automaton corresponding to the graph. (More on this later.) In your testing task you keep the two path specifications f1 and f2 fixed but you try them with different graphs with goal of finding bugs in the path finding algorithm. You put your graphs into a file called program.cd A sample program.cd file is: A = B E. B = D E X. D = C. E = C. C = . X = C. // keep the following; do not change Main = . visitors Count_C_Visitor = . endvisitors The graph notation is very simple: On the left of the = sign is a node name and on the right are all the successors. When you run the path finding algorithm, you get an output as follows: : A ( : B ( : D ( : C ( ) ) : E ( : C ( ) ) : X ( : C ( ) ) ) ) method f1 done 3 : A ( : E ( : C ( ) ) ) method f2 done 1 Method f1 found 3 paths from A via B to C. Method f2 found 1 path from A bypassing B to C. The paths traversed are printed, including the count of the total number of paths found. How do you run the path finding algorithm? Since it is written in Java it runs with little effort everywhere. But for now we assume that you use a CCS Solaris machine (an Ultra Sparc, like alnitak). Put /proj/demsys/demjava/bin/ into your path so that you have the command demjava available. You also need the Java Virtual Machine interpreter and compiler: /bin/java and /bin/javac. Make sure /bin is in your path. Note by Doug Orleans: >They also will need javacc, in /share/com/bin. They may need to use >JDK1.1.5 java and javac, which are in /arch/com/packages/jdk-1.1.5/bin; >in particular I think 1.1.5 has a more robust JIT compiler than 1.1.3 >(which is what is in /bin). If they run into JIT bugs (such as >mysterious null pointer exceptions, or bus error/segmentation fault), >they should set the environment variable JAVA_COMPILER to NONE. Since we use Java, you need to specify a class path. Use: .:/proj/demsys/demjava/demjava.jar:/proj/demsys/apstudio/apstudio.jar Having done this set-up, copy the directory: $TVV/hw/1/automata-intersection into one of your own directories and type: demjava test This should produce an output which includes the one shown above. Now your testing job can start: try other graphs so that you find all or almost all bugs. What to turn in: test requirements test specifications tests (run them and show the output) bug reports A description on how to improve and automate the testing. This is an example of a situation where you are not given a complete specification. We have not said what should happen if the input contains some error. It is your task to check whether the program handles those situations reasonably well. If you are eager to do some white box testing, the source code for Demeter/Java is in: http://www.ccs.neu.edu/research/demeter/DemeterJava/use/latest-demjava/ http://www.ccs.neu.edu/research/demeter/DemeterJava/use/latest-demjava/generate/subgraph.beh contains relevant code. In this course you will work with multiple versions of the same software. The software will be updated based on your bug reports. Therefore, please make sure to indicate which version of Demeter/Java you have used. demjava -version is the command which tells you the version which you are using.