Software test generation based on flow models.

Abstract

Software testing is one of the most widely used quality assurance methodologies. A large software system usually has a hierarchical structure: for example, system, subsystems (programs), subprograms, and procedures, where a subsystem is composed of a number of subprograms, each of which in turn is composed of a number of procedures. Testing of a system can be done at different levels with different emphases. In this thesis, we focus on testing at the two lowest levels, namely procedure and subprogram levels. Until recently, many testing techniques used control flow graph or its variants for selecting the tests. It is known that such a flow model is only capable of capturing the control flow. For data flow oriented testing, the def-use graph is used to represent both control flow and data flow. Based on this model, we propose a class of data flow oriented test selection criteria using input-output and input-predicate relations. These criteria are shown to have certain merits over the existing test selection criteria. However, a def-use graph can be only used to capture control flow and data flow within a procedure. Since control flow and data flow also exist among interacting procedures in a subprogram, a more expressive model is necessary in order to perform testing at subprogram level. Such a model is proposed by extending the def-use graph model. By using this model, the tests generated using a test selection criterion are shown to be more meaningful and, likely, more effective in detecting errors.