Exploiting Design Patterns for Improved Efficiency In the Testing of Object-Oriented Software by Kenneth Michael Araujo Bachelor of Science Francis Marion College, 1983 Master of Science University of South Carolina, 1986 Bachelor of Science in Engineering University of South Carolina, 1994 Certificate of Graduate Study in Applied Statistics University of South Carolina, 2003 Submitted in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in the Department of Computer Science and Engineering College of Engineering and Information Technology University of South Carolina 2006 - 6 6=, )M „J„ 0h, Hi M@or Professor Chairman, Examining Committee Karetl ⁄ “„.Z JIIRSSIIS/2177e: Committee Member Committee Member LZ (he Committee Member uke FeAmW Dean of The Graduate School UMI Number: 3245380 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction. In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion.
® UMI UMI Microform 3245380 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.
Box 1346 Ann Arbor, MI 48106-1346 Acknowledgements As my time at Carolina draws to a close, my primary expression of graditude is to my Lord and Saviour, Jesus Christ, who provided the opportunity to seek this degree and the strength to complete the process. A debt of gratitude is owed to my advisor, Dr. John Bowles, for his guidance over the years. I appreciate his patience as he endured many Friday afternoon meetings.
My thanks also go to the members of my committee for their willingness to serve. Finally, { must thank my family for putting up with my constant travels to Columbia and the stacks of books scattered throughout the house. I’m sure they’re just as happy as I am to see this task accomplished. ii Abstract The use of design patterns in software development has become more attractive given the rise in popularity of development tools utilizing a model driven architecture (MDA) philosophy.
If a given piece of software is designed from a collection of standard design patterns, we should be able to test that software based on the designer’s intent as captured by those patterns. In testing object oriented software, we must be aware that the state of an object at any time depends on the sequence of messages received by the object up to that point in time. As these messages are passed by method calls, the number of methods calls and the order in which they occur must be given consideration. A metric based on method coverage is suitable in this context.
This dissertation examines the utility of design patterns in the practice of software testing. We employ a metric of method coverage to gauge the efficiency obtained by the inclusion of design patterns in two traditional test procedures, statistical design of experiments and reliability block diagrams. In the process, a new type of software system diagram, the Pattern Block Diagram, is developed. ili Table of Contents Acknowledgemenfs.
cà ll 110 cece ce cece eer e ene nena teen eee ee entre eee ne ec ea eee teen enes iii List of Tables.- ni nh vệ Vv List Of FiBUF€S. co nh nh in vi [ntroductiOn. HH HH HH ng nh kh ng l Il. ch nh vi re 3 Il.
HH» HH HH nh nh nhe nà 11 IV. ch KÝ nhi, 19 Testing Object-oriented Soffwar€. Design Patterns and the Statistical Design of Experiments in the Testing of Object-oriented Software. Design Patterns and Reliability Block Diagrams.
069/050 018 cece eee ee. 114 iv List of Tables Table Page 1 | TABLE 3.1 — Conditions for Path Traversal in White Box Testing 23 2 | TABLE 3.2 — Multiple Condition Criteria 25 3 | TABLE 3.3 — Comparison of Path Coverage Criteria 26 4 | TABLE 3.4 — Guidelines for Equivalence Classes 27 5 | TABLE 4.1 — Which path to follow ifx = 0? 32 6 | TABLE 4.1 — node/edge classifications of Rapps and Weyuker 36 7 | TABLE 4.2 - def/use graph sets of Rapps and Weyuker 37 8 | TABLE 4.3 — CoinBox def/use pairs 42 9 | TABLE 4.4 - Stack class documentation 43 10 | TABLE 4.5 - Object data type matrix 47 11 | TABLE 4.6 — Stack or self data type 47 12 | TABLE 6.1 — Patterns of the Invoice Application 86 13 | TABLE 6.2 — Sample pattern data 88 14 | TABLE 6.3 — Sample pattern averages 88 15 | TABLE 6.4 — Invoice Application data 88 16 | TABLE 6.5 — Patterns, classes, and method counts for the Invoice 97 Application 17 | TABLE 6.6 — Classes and method counts for the composite and decorator | 98 patterns 18 | TABLE 6.7 — Union of the composite and decorator patterns of the 98 Invoice Application 19 | TABLE 6.8 - Union of the observer, strategy, and iterator patterns of the | 98 Invoice Application 20 | TABLE 6.9 — Driver function method counts for the Invoice Application | 99 21 | TABLE 6.10 — Strategy/Iterator union method counts for the Invoice 99 Application 22 | TABLE 6.12 — Conditional probabilities ( Based on data of Table 6.13 — Reduction of the Pattern Block Diagram 106 List of Figures Figure Pa 1 | FIGURE 1.1 — An Inheritance Hierarchy 5 2 | FIGURE |.2—- A Branch of the Banking Hierarchy 6 3 | FIGURE 1.3 — Dynamic binding hierarchy 7 4 | FIGURE 1.4 - Output of bankTest 7 5 | FIGURE 1.5 — Class Associations and Cardinalities 9 6 | FIGURE 1.6 — Aggregation of Objects 10 7 | FIGURE 3.1 — Flowchart for Path Traversal in White Box Testing 21 8 | FIGURE 3.2 — Breakdown of Compound Decisions 24 9 | FIGURE 3.3 — Pseudocode for locating name ‘Smith’ in list 25 10 | FIGURE 4.2 — def/use graph of Rapps and Weyuker 36 11 | FIGURE 4.3 — CoinBox code 40 12 | FIGURE 4.4 — CoinBox class call graph 40 13 | FIGURE 4.5 — CoinBox class call graph frame 41 14 | FIGURE 4.6 — Stack class flow graph 44 15 | FIGURE 4.7 — State following steps 1,2,3 of Mungara’s algorithm 45 16 | FIGURE 4.8 — Mungara’s completed test case for push( ) method 45 17 | FIGURE 5.1 - Varying one factor at a time 51 18 | FIGURE 5.2 - Interaction of factors A and C 51 19 | FIGURE 5.3 —A,C interaction + B effect 52 20 | FIGURE 5.4 - Full factorial design for 3 factors 53 21 FIGURE 5.5 - Response table for 3 factors 54 22 | FIGURE 5.6 — Factor levels for chemical reaction experiment 55 23 | FIGURE 5.7 — Response table for chemical reaction experiment 55 24 | FIGURE 5.8 — Graphical representation of response table or the chemical | 56 reaction experiment 25 | FIGURE 5.9 — Transaction Processor user interface 57 26 | FIGURE 5.10 — Factor levels for the Transaction Processor 58 27 | FIGURE 5.11 - Orthogonal 4-Factor design 59 28 | FIGURE 5.12 - Response table for 4 factors 59 vi Figure Page 29 | FIGURE 5.13 - Transaction Processor class count 60 30 | FIGURE 5.14 - Transaction Processor error log 61 31 | FIGURE 5.15 — Completed response table for the Transaction Processor | 62 32 | FIGURE 5.16 - Graphical representation of response table for the 63 Transaction Processor 33 | FIGURE 5.17 - Determining the AB interaction levels 64 34 | FIGURE 5.18 — Four Factor Interaction Response Table 65 35 | FIGURE 5.19 - Comparison of main effects and most significant 66 interactions 36 | FIGURE 5.20 - AD interaction graph and response table 66 37 | FIGURE 5.21 — Four Factors at Three Levels 67 38 | FIGURE 5.22 - Taguchi Z, design 68 39 | FIGURE 5.23 - Results of Taguchi Z, experiment 69 40 | FIGURE 5.24 - Transaction Processor error log, Taguchi design 69 41 | FIGURE 5.25 - The Internationalization Wizard user interface 72 42 | FIGURE 5.26 - Internationalization Wizard class 73 43 | FIGURE 5.27 - Classes of the Internationalization Wizard 74 44 | FIGURE 5.28 - Proportion of methods covered per experimental run 74 45 | FIGURE 5.29 - Proportion of methods covered discounting initialization | 76 | Functions 46 | FIGURE 5.30 - Comparison of DOE and Facade pattern 78 coverage results on per-run basis.31- Comparison of DOE coverage results based 78 on the estimated average response.32 — Contact Mediator interface 80 49 | FIGURE 5.33 - Classes of the Contact Mediator 81 50 | FIGURE 5.34 - Comparison of coverage results including the Mediator 81 pattern.1 - The Invoice Application interface 83 52 | FIGURE 6.2 - Pattern Block Diagram 84 53 | FIGURE 6.3 — Number of Methods per Pattern Type 90 54 | FIGURE 6.4 — Lines of Code per Method 90 Vil Figure Page 55 | FIGURE 6.5 — Proportion of Methods Covered 90 56 | FIGURE 6.6 — Pattern overlay diagram for the Invoice Application 92 57 | FIGURE 6.7 - Pattern Coupling through shared class 2 93 58 | FIGURE 6.7 — Revised Pattern Block Diagram showing the expected 101 pattern node, pattern coupling, and class node method coverage 59 | FIGURE 6.8 — Distinct pattern clusters 104 60 | FIGURE 6.9 — Parallel/Series Pattern Block Diagram 105 Vili I. Introduction The process of software testing is challenging and may occur at many stages of design and development, from unit testing to integration testing to acceptance testing. Following delivery, additional modifications may call for regression testing.
At each of these levels we may apply a variety of black-box and white-box tests. Regardless of the method chosen, we cannot test every possible combination of inputs. Instead, we are forced to select a subset of possible test cases. The generation of test cases is a problem in itself.
Hopefully the set of test cases we select maximizes the number of errors we discover. Several coverage criteria have been proposed to insure that we exercise all statements, all branches, all conditions, or some combination of these. Adding to the complexity, programs developed under an object-oriented paradigm have characteristics not present in procedural software. The fundamental unit of an object-oriented program is the class.
When we test a class we are actually testing an instantiation of that class which is an object. In testing object-oriented software, we must be aware that the state of an object at any time depends on the sequence of messages received by the object up to that point in time. As these messages are passed by method calls, the number of methods calls and the order in which they occur are an additional consideration. Two coverage metrics useful in the analysis of method calls among classes are control flow and data flow.
Control flow is primarily concerned with the branch and loop structures of a program while data flow focuses on the bindings between variables and their values and how the variables are to be used. These are often referred to as definition/use or DU pairs. Much research has been done pertaining to path selection criteria which are based on control flow or data flow techniques. Of particular interest to researchers are strategies by which the generation of test cases may be automated.
Several such methods are described in this paper and most involve complex algorithms.