Browse Prior Art Database

Program Change Verification Method

IP.com Disclosure Number: IPCOM000050440D
Original Publication Date: 1982-Oct-01
Included in the Prior Art Database: 2005-Feb-10
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR

Abstract

A change in a program is frequently effected, to correct faults or to enhance performance. Any such change is supposed to affect some of the functions of the program and not others. The following description uses the D-algorithm (1) to determine whether or not a given change did affect a not intended output function. It is assumed that the program under consideration is written in a high-level language, such as PL/I or PASCAL. It is further assumed that each effective instruction can be described as a transformation of its functioning input into its output. For simplicity, it is assumed that the change affects exactly one instruction, for a multiplicity of changes can be rendered as a set of solitary changes.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 2

Program Change Verification Method

A change in a program is frequently effected, to correct faults or to enhance performance. Any such change is supposed to affect some of the functions of the program and not others. The following description uses the D-algorithm (1) to determine whether or not a given change did affect a not intended output function. It is assumed that the program under consideration is written in a high-level language, such as PL/I or PASCAL. It is further assumed that each effective instruction can be described as a transformation of its functioning input into its output. For simplicity, it is assumed that the change affects exactly one instruction, for a multiplicity of changes can be rendered as a set of solitary changes.

The first task is to characterize those inputs to these two instructions, the one before and the one after the change, for which the outputs are different. The start of the computation is to select an input pattern for this pair of instructions, the old and the new, for which the outputs are different. These values are arguments of other functions, instructions, which by hypothesis are the same for the old and new program. Some of the outputs of the instructions are primary outputs, that is, give values to variables used as inputs for other programs or, simply, as outputs of the program itself. It will be assumed that the program has exactly one primary output; by the process of segmentation (2) the program may always be so restricted.

The idea of the D-algorithm (1,2), which was developed as a means to generate tests for failures in logic circuits, is to project the differences, determined at the site of the difference, from there to a primary output variable, making assignments of variables to insure the implications that were set up in the 'D-drive' thence driving backwards, justifying the decisions made in the forward drive. The difficulty in adapting this technique to program changes is that some of the processes are recursive, requiring backup through several iterations of the same cycle of instructions.

This same recursion is experienced in hardware and is handled in a variety of ways. The method here prescribed amounts to assuming that the logic is regular- each feedback loop is interposed by a pair of registers gated at different clock times- and iterating the design over several copies, introducing new variables for each of the variables for each of the iterations and assuming that the change (= 'failure') occurs in each of the copies. It has to be decided in which of the copies the 'D-drive' is to take place.

Let us start at the site of the change and initiate 'D-drive'. Assume that the output variable emanating from the change is a vector, of prescribed length, of binary variables. This is no loss of generality. The first step is to construct an input, it must be a systematic selection, at the site of the change for which the outputs of the two instructions DIFFER; it should diff...