Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-01-21
2002-04-16
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S440000, C345S215000, C345S215000, C712S011000
Reexamination Certificate
active
06373484
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to tools for the graphic presentation of data structures and to an application thereof for testing software performance.
REFERENCES
Many of the prior art techniques mentioned in the next section are discussed in greater detail in the following publications:
[1] B. Beizer.
Software testing techniques.
Van Nostrand Reinhold, 1990.
[2] F. P. Brooks. The Mythical Man-Month: Essay on Software
Engineering,
Addison-Wesley, 1995.
[3] E. Buchnik and S. Ur. Compacting regression-suites on-the-fly. In
Proceeding of the
4
th Asia Pacific Software Engineering Conference,
pages 385-394, December 1997.
[4] Michael Factor, Eithan Farchi and Shmuel Ur.
Rigorous Testing Using Snapshot.
Israeli Conference on the Theory of Computers and Systems (ISTCS), Herzelia, Israel, May 1997,
[5] C. Kaner. Software negligence and testing coverage, In
Proceedings of the STAR
96: the
Fifth International Conference, Software Testing, Analysis
and
Review,
pages 299-327, June 1996.
[6] H. Levkowitz.
Color Theory and Modeling for Computer Graphics, Visualization, and Multimedia Applications.
Kluwer Academic Publishers, 1997.
[7] B. Marick
The Craft of Software Testing, Subsystem testing Including Object-Based and Object-Oriented Testing.
Prentice-Hall 1998.
[8] Y. S. Maarek, M. Jacovi, M. Shtalhaim, S. Ur, D. Zernik, and I. Z. Ben Shaul, WebCutter: A system for dynamic and tailorable site mapping, In the Proceedings of the Sixth International World Wide Web Conference, Santa-Clara, April 1997.
[9] S. Ur and A. Ziv Of-The-Shelf Vs. Custom Made Coverage models, Which is the One For You, STAR98
[10] U. Yahalom and A. Lichter. White Box Testing of C Programs, yearly software project, Technion.
[11] D. Zernik and G. Zodik. A graph management framework for 3D visualization. IBM Object Technology 97.
BACKGROUND OF THE INVENTION
Data structures may be presented graphically as nodes interconnected by lines or edges. For example, a computer program can be presented graphically by means of many nodes each representative of a program block, interconnected by branches showing control flow between the various program blocks. Generally, graphical representation of such structures is prone to two problems. First, multiple coincident branches cannot be distinguished from one another. This makes it impossible to discern whether two nodes are joined by a single branch or several overlapping branches. Secondly, even if this problem is overcome, it remains impossible to trace a path which spans several nodes, since all edges appear identical. These drawbacks are manifest in graphical tools for program testing.
Testing is one of the biggest problems of the software industry. It has been shown that the cost of testing is usually between 40-80% of the development process as compared with less than 20% for the coding itself. The practice of letting the users find the bugs and fixing them in the next release, is becoming dangerous and costly for three main reasons: reputation and brand-name are harmed; replacing the software can be very costly when there is a large installation base; and there is the danger of litigation if the software error caused harm to the user. Therefore, thorough testing is required and care must be exercised to ensure that testing resources are used efficiently.
Modern software products are increasingly complex and typically offer literally thousands of options. In order to test software in such a manner that bugs can be reliably detected, it is necessary to run the software through each of the possible control paths. In fact, since bugs can be a function of the order in which options are selected, proper testing requires that the order of selecting options be varied accordingly and that the control flow be observed.
The main technique for demonstrating that the testing has been thorough is called test coverage analysis. Simply stated, software testing requires that there be created, in some systematic fashion, a large and comprehensive list of tasks and that some check be initiated to ensure that each task is covered in the testing phase. Coverage can help in monitoring the quality of testing, in creating tests for areas that have not been tested before, and with. forming small, yet comprehensive, regression suites.
Coverage is defined as any metric of completeness with respect to test selection criteria [1]. Many such metrics have been suggested in the past [1] [5], of which statement coverage is the most common. The statement coverage model measures against a set of tests, for each statement, if the statement were executed by one of the tests. When using any coverage model, a metric is created against which the quality and completeness of the testing is measured.
The most commonly used coverage metrics, such as statement coverage and branch coverage are based on the control flow of the program. However, many other metrics exist. Some coverage metrics are based on the data flow of variables, like define-use [1], while others are based not on the program code but on the inputs or the specifications [10].
Assessing coverage results is a difficult task. One of the main problems is that there are many details and, as a result, it is hard “to see the wood for the trees”. For example, it may occur that many statements are not covered owing to a single cause, but superficial analysis will show only a list of statements not covered without showing their interrelationship. Amongst the most commonly used coverage models are statement coverage and branch coverage, whilst more recently proposed is forward path as described by Factor et al. [4]. All of these models define criteria for dealing with the control flow of the program.
Coverage results, whether of branch coverage, statement coverage or path coverage, produce a vast amount of information. Known methods for presenting this information are in textual form, such as a list or table. These suffer from several drawbacks. First, global analysis of the coverage information is difficult since textual information can cover many pages. Furthermore, presenting a one to many relation is cumbersome in textual format, as basic blocks can only be presented one after the other. As a result, such approaches militate against an intuitive perception of the flow of control.
It is therefore known to use two-dimensional graphical images to represent coverage results so as to provide a more intuitive global view than can be achieved textually. McCabe and Associates, Inc. of Columbia, U.S.A. offer a software testing tool known as “Visual Testing Toolkit” allowing two-dimensional graphical display of a structure chart of a system. Modules are shown as blocks which are interconnected via control paths. The modules are color-coded based on whether or not they have been tested so that untested areas may be quickly identified. Viewing the entire control graph allows points of interest, such as the most frequently used basic block etc., to be pinpointed and provides a clear view of the flow of control during the program's execution. Those paths in the program which have yet to be tested are shown both graphically and in the form of a listing.
Nontrivial programs have large and complex control graphs. Presenting coverage information as a graph in two dimensions not only requires substantial space but might become incomprehensible due to many intersecting edges. Both factors militate against achieving an intuitive global view.
FIG. 1
shows a 2-D graphical representation of a segment of a control graph describing a “case” statement. It will be appreciated that this segment is but one small component of the complete control graph, and yet requires significant area for its effective display. Clearly, to display a 2-D representation of the entire control graph would require a display medium of such large size, that it cannot be done.
It thus emerges that notwithsta
Karni Zachi
Orell Dror
Ur Shmuel
Zernick Dror
Browdy and Neimark
Nguyen Kimbinh T.
Zimmerman Mark
LandOfFree
Method and system for presenting data structures graphically does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for presenting data structures graphically, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for presenting data structures graphically will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2886549