JP3418544B2 - Automatic test data generator for programs - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an automatic test data generator used for program development support, and more particularly to a technique effectively applied to testing, debugging and diversion development of a source program.

[0002]

2. Description of the Related Art A technique for automatically generating test data of a program is disclosed in Japanese Patent Application No. 8-216 previously proposed by the applicant.
No. 328 (title of the invention; program development support device, program development support method, and program development support storage medium). This is for the purpose of improving the efficiency of retesting, determining valid / invalid instructions in a program, and discarding invalid instructions. It has an automatic test data generation function in terms of improving the efficiency of retesting. There is.

[0003]

However, although the technique described in Japanese Patent Application No. 8-216328 automates the acquisition of test data and significantly reduces the load on the programmer required for the test, it is a target. There is a problem that the number of generated program paths increases rapidly as the size of the program increases.

To solve this problem, in the case of a language having a highly independent group of meanings such as a C language function, the test data is generated for each group, and the number of program paths simultaneously generated. Can be reduced, but the target programming language is PERF outside the COBOL language.
In the case of a language that can describe subroutines with low independence such as procedures called by ORM, it is questionable whether significant test data can be generated even if divided into each subroutine, and such means cannot be used. .

In addition, programmers are often interested in debugging and diversion development in particular variables and processing flows that are considered to cause a problem, and conventional techniques are used for debugging and diversion development. If you try to apply it, you have to find the path of your interest in the huge number of program paths of the whole program and its domains.

Also, in the COBOL language, when a variable has an alias, or when the variable has a structure and an update to a lower variable affects the value of the upper variable, the variable name is replaced. There is a problem that the method of acquiring the program domain by does not support.

An object of the present invention is to solve the above problems and automatically calculate the conditions to be satisfied by a variable and the flow of its processing for a variable designated by the user when debugging or diversion developing a program. Another object of the present invention is to provide a technique for reducing the number of test steps by automatically generating test data based on the test data.

[0008]

In order to achieve the above object, the present invention analyzes a source program of a test data generation object, creates a syntax tree, and has a hierarchical structure and size of variables, aliases, redefinition and subroutines. The parsing means that performs the parsing process that collects the information of the above, and the ripple effect analysis process that specifies the range in which the influence of the value of the variable specified by the user spreads in the source program and extracts the part. Using the effect analysis means and the analysis result obtained by the ripple effect analysis processing, for the variable designated by the user, the condition calculation means for calculating the condition that the variable should satisfy, and the test of the variable applicable to the calculated condition And means for automatically generating data.

Further, using the analysis result obtained by the ripple effect analysis process, a program network creating means for creating a program network for each routine, and a program for creating a program path expression from the program network. Program path expression generation means for executing path expression generation processing, subroutine replacement means for executing subroutine replacement processing for replacing a subroutine call with the program path expression of the called subroutine when the subroutine call is detected, and generated program path Program path expression expanding means for executing expression expansion processing, and program path connection processing for connecting the program paths obtained by division according to the processing flow of the program And a scan connecting means, the condition calculation means, and calculates the condition of the variables for that program passes are performed from the connection program path.

Further, when calculating the condition of the program path,
By converting a variable name into a symbol name using an offset from the beginning of the data area and two numerical values of the size of the area occupied by that variable, multiple variables share an arbitrary storage area. It is characterized in that it has means for calculating the condition that the variable should satisfy even in the case.

[0011]

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of a program test data automatic generation device according to the present invention will be specifically described below with reference to the drawings.

FIG. 1 is a functional block diagram showing an embodiment of the present invention. The test data automatic generation device according to the present exemplary embodiment is a terminal 101 that receives a processing request and displays a result.
The source file 102 to be processed, the syntax analysis unit 103 that performs syntax analysis of the source file 102, and the processing result of the syntax analysis unit 103 are used, and the influence of the value of the variable designated by the user is within the source program. Of the ripple effect analysis unit 104 that performs a ripple effect analysis that specifies the range to be propagated in, a program network creation unit 105 that creates a program network using the processing result of the ripple effect analysis unit 104, and a program network creation unit 105. A program path expression creating unit 106 that creates a program path expression using the processing result, a subroutine replacement unit 107 that replaces a subroutine call included in the processing result of the program path expression creating unit 106 with the contents of the subroutine, and the subroutine replacement unit. Using the processing result of 107, A program path expression expanding unit 108 for expanding a Gram path expression into a program path; a program path connecting unit 109 for connecting the program path expressions found for each routine in consideration of the processing order to generate a program path as a program; Program path domain acquisition unit 1 for obtaining the domain of a program from the program path obtained by the program path connection unit 109
10 and a test data acquisition unit 111 that generates test data from the domain obtained by the program path domain acquisition unit 110.

The test data automatic generation device of this embodiment can be specifically configured by a computer, and each unit such as the syntax analysis unit 103 can be configured by a program that realizes a corresponding function. . Further, each unit may be configured not only to be provided inside one computer, but also to divide the work among a plurality of computers to generate test data.

FIG. 2 is a flow chart for explaining the processing of the embodiment shown in FIG. The present invention comprises the following processes as shown in FIG.

Step 201: Parsing process 112 This process is executed by the parsing unit 103. When a processing request is issued from the terminal 101, the syntax analysis unit 103 causes the source file 102 (for example, COBOL source file).
3, a syntax tree 121 is generated as shown in FIG. 3, and at the same time, variable information 124 having information for each variable included in the program, a data item information table 122 that represents the variable information 124, and Routine information 125 having information for each appearing routine and a routine information table 123 that represents the routine information 125 are generated. At this time, the include file is expanded if necessary.

Step 202: Ripple effect analysis processing 113
Using the syntax tree 121 and the data item information table 122, the ripple effect analysis is performed on the variable designated by the user. By performing this processing, the number of program paths finally obtained can be reduced.

Step 203: Program network creation process 114 Syntax tree 1 generated up to the ripple effect analysis process 113
21 is followed in the order of precedence, and the program network is generated in units of all routines (main routine and subroutine). The process of network generation itself is performed using the technique described in Japanese Patent Application No. 8-216328. A routine identification number is attached to the program network, and a routine identification table storing the correspondence between the routine identification number and the routine name is generated.

Step 204: Program path formula creating process 115: A program concatenation matrix is acquired from the program network, and a program path formula for each routine is generated from the program concatenation matrix using the program path formula creating process. The generation process is performed using the technique described in Japanese Patent Application No. 8-216328.

Step 205: Subroutine replacement processing 1
16 It is checked whether or not there is a subroutine call in the program path expression, and if there is, a routine identification number is retrieved from the subroutine name of the corresponding subroutine, and the routine identification number is replaced with the corresponding program path expression.

Step 206: Program path expression expansion processing 117 The program path expression processed by the subroutine replacing means is expanded and converted into a program path list for each routine.

Step 207: Program path concatenation processing 118 The program paths for each routine generated in the above processing are concatenated in consideration of the processing order, and all the program paths included in the program are calculated.

Step 208: Program domain acquisition processing 119 Program path is selected from the program path list.
Take one and get the program domain for that program path.

Step 209: Test data acquisition process 1
20. Generate test data contained in the program domain from the program domain.

Until all program paths have been processed
The program domain acquisition process and the test data acquisition process are repeated. The test data generation process is described in Japanese Patent Application No. 8-21.
The technique described in No. 6328 is used.

Next, a technique which characterizes the present invention will be described with reference to the drawings. Note that the processing not described in detail here is performed using the technique described in Japanese Patent Application No. 8-216328.

FIG. 4 shows the structure of the ripple effect analysis means 104 and the flow of data. 5 and 6 show flowcharts of the execution procedure of the ripple effect analysis means 104.

First, a variable designated by the terminal 101 and to be a ripple effect analysis target is set in the variable area 230 (step 501). The syntax tree analysis unit 103 executes the syntax tree analysis process, and the syntax tree 121 and data used by the user.
Acquires the item information table 122 (step 50)
2). In the syntax tree 121, a flag indicating whether the variable is referenced or updated is set in the node corresponding to the variable appearing in the program. Further, in the leaf node of the syntax tree 121, the position of the token possessed by the node on the source file is set.

The data item information table 122 is a table of variable information 124 for each variable. As shown in FIG. 3, the variable name, the size of the variable, the level number, the upper variable information,
It includes information such as lower-level variable information, redefinition information, alias information, and appearance position information.

The size of a variable is the size of the storage area used to store the value of the variable, and the level number is a number for judging the upper and lower relations between variables. A variable with a large level number becomes a lower variable dependent on a variable with a lower level number. The high-order variable information is a pointer that points to the variable information 124 of the high-order variable on which a certain variable is directly dependent, and the low-order variable information is the low-order variable directly included by the certain variable. Is a pointer that points to the variable information 124. The redefinition information is a pointer that points to the variable information 124 of the redefined variable when another variable redefines the area occupied by the variable with another hierarchical structure.

The alias information is a subordinate variable which is directly included in a variable defined as an alias when a plurality of variables adjacent to each other in the occupied storage area are collectively defined as the alias. A pointer that points to variable information 124 of a variable.

Next, the ripple effect analysis means traces the generated syntax tree 121 in the processing order to generate a control structure tree 231 as shown in FIG. 7 (step 503). This tree 2
A sentence identification number 232 is attached to each node of 31 in the search order, and a branch identification number 233 for identifying a branch to which the sentence belongs is attached to a statement nested by a branch instruction.

Next, using the data item information table 122, all the variables registered in the variable area 230 and the variables sharing all or part of the storage area are acquired, and the obtained variables are used as variables. The variables are registered in the variable list 234 together with the variables registered in the area 230 (step 504).

Then, a sentence list 235 in which the elements of the list are empty is prepared (step 505). Next, the sentence list 236 in which the elements of the list are empty is prepared (step 506). Next, one variable is taken out from the variable list 234 and set in the variable area 237 (step 507).

All the sentences in which the variables registered in the variable area 237 are used are acquired by referring to the appearance position information of the variable information 122 and registered in the sentence list 236 (step 508).

All the variables included in the variable list 234 are processed in steps 507 and 508, and the sentence list 236 obtains the sentence in which the variables related to the variables registered in the variable area 230 are used. To do.

Next, all variables sharing the entire storage area of the variables registered in the variable area 230 are acquired and registered in the variable list 238 (step 509).

Next, the sentences contained in the sentence list 236 are sorted in ascending order of sentence identification numbers (step 510). Next, an empty sentence list 239 is prepared (step 51).
1). Next, a sentence to which a variable registered in the variable list 238 is newly assigned is searched from the beginning of the sentence list 236 (steps 512 and 513).

If such a sentence is found as a result of the search,
Among the found sentences, the identification number of the sentence with the smallest identification number is acquired. If there is a branch, the branch identification number is also referred to acquire the identification number of the sentence with the smallest identification number for each branch, and the sentence having the sentence identification number smaller than that is extracted. The extracted sentence is discarded from the sentence list 236 and registered in the sentence list 239 (step 514).

If, as a result of the search, no sentence in which the variable in the variable list 238 is newly assigned is found in the sentence list 236, all the sentences up to the end of the list are extracted. The extracted sentence is discarded from the list 236 and registered in the sentence list 239 (step 515).

Next, the variable list 240 in which the elements of the list are empty is prepared (step 516).

Next, one sentence is read from the sentence list 239 (step 517 in FIG. 6). The variables registered in the variable list 234 are taken out one by one, and the variable area 237
Set to. Then, it is checked whether or not the statement stored in step 516 influences the variables stored in the variable area 237. Variables that are registered in the variable list 234 have an influence on the variables 237.
This includes not only variables that are directly updated by the variables registered in, but also variables that are shared with a part of the storage area with the variables (steps 518 and 519).

If such a variable is included in the extracted sentence, the corresponding variable is registered in the variable list 240 (step 520).

The above steps 517, 518, 519,
The processing of 520 is performed for all the sentences in the sentence list 239.

Next, the contents of the sentence list 239 are changed to the sentence list 2
35 is additionally registered, and the sentence list 239 is discarded (step 521).

Next, it is checked whether the variable list 240 is empty. If it is empty, it is assumed that all variables having a ripple effect in the source file 102 have been searched, and the next step 52
The processing of 3,524 is performed.

First, duplication of sentences in the sentence list 235 is removed (step 523). Next, the subtree of the syntax tree 121 corresponding to the sentence that does not exist in the sentence list 235 is deleted, the sentence list 235 is discarded (step 524), and the ripple effect analysis process is terminated.

If the variable list 240 is not empty,
It is checked whether the statement list 236 is empty (step 52).
5).

If it is not empty, return to step 511 and
For the remaining sentences in the sentence list 236, the search of the spread range is continued.

If it is empty, it is considered that the first-order ripple effect analysis is completed, and preparation is made for the higher-order ripple effect analysis processing. That is, the contents of the variable list 240 are changed to the variable list 2
34, the variable list 240 is discarded, and the process 20
Return to the beginning of the loop of 7,208 (step 526).

In this way, the ripple effect-analyzed syntax tree used in the program network creation processing is generated.

Next, the processing of the subroutine replacing unit 107 will be described.

In the case of the COBOL language which is the object of this embodiment, there is a procedure unit called a paragraph.
Since data items are global, they are not highly independent as compared to C language functions, etc., and it would be impossible to make a meaningful group by themselves, so just extract them like a C language function for testing. It cannot be targeted.

Therefore, in order to support such a language, a program path expression is acquired for each subroutine and connected as needed to generate a program path expression as a program. Therefore, the program path formula generated for each subroutine is
After converting to a character string format like 16328, Lisp
Instead of processing by language, it is obtained as a program path expression tree 302 as shown in FIG. 8A for convenience of replacement.

The expression tree 302 is a binary tree, and each node has a value (label) indicating what the node represents,
It has links to left and right child nodes. In FIG. 8A, the leaf node of the program path expression tree 302 indicates the processing in the source file, and the value of that node is
Each is a label attached to the corresponding process in the target source file. In the intermediate section, a node that has "*" (asterisk) as a node label indicates that there is a concatenation control structure. After the process corresponding to the label of the left child node, the node of the right child node Represents that the process corresponding to the label is executed. In addition, a node having "+" (plus sign) as a node label indicates that there is a control structure for selection, and the process indicated by the label of the left child node or the label of the right child node is indicated. Indicates that either of the processing is executed. Regarding the control structure of the loop, if the number of repetitions is directly given as a numerical value on the source file, the contents of the loop are expanded by the number of times. Otherwise, the contents of the loop are expanded with the number of times specified by the user as the upper limit of loop repetition. For example, when the user specifies the maximum number of iterations as 2, the content of the loop is expanded as a control structure for selecting a process that is never executed, a process that is executed once, and a process that is executed twice. To do.

The subroutine replacement process has a recursive call management stack for preventing infinite expansion of recursive calls.

8 and 9 show how the subroutine is replaced. FIG. 8A shows a program path expression tree 302 including a subroutine call, which corresponds to the program path expression 301 in the figure.
The node 303 is a node corresponding to a subroutine call. FIG. 8B is a program path expression tree 304 of a subroutine called by the node 303. The program path expression tree 305 in FIG. 9 is the program path expression tree 302 after the subroutine has been replaced.

FIG. 10 is a flowchart of the subroutine replacement process.

First, the program path expression tree 302 obtained for each subroutine is searched for in post order .
That is, search in the reverse order) and search for the node of the subroutine call. Next, the label 306 of the node 303 being searched is acquired, and it is checked whether the content represented by the label is a subroutine call (steps 801 and 802).

When the content represented by the label is a subroutine call, first, the contents of the recursive call management stack are examined to check the number of times the label 306 is registered (step 803). If the number of registrations is less than or equal to the number specified by the user, the label 306 is pushed onto the recursive call management stack (steps 804 and 80).
5).

Next, from the routine information table 123 and the routine identification table, the program path expression tree 304 (FIG. 8B) of the sub-routine to be replaced is specified, and a duplicated program path expression tree A (illustration is shown). Prepare) to replace the node 303 (step 80)
6).

The routine information table 123 is a table of the routine information 125 of each routine.
As shown in FIG. 3, 5 includes information such as routine name, routine type, definition position information, belonging routine information, inclusion routine information, callee routine information, and caller routine information.

When the routine has a hierarchical structure of sections and paragraphs as in the COBOL language, the type of routine represents the type of routine whether the routine is a section or a paragraph. The defined position information is information on the position where the routine is defined. The belonging routine information is a pointer to the routine information of a routine in the upper hierarchy to which the own routine belongs, and the included routine information is a pointer to the routine information of a routine in a lower hierarchy of the own routine. The callee routine information is a pointer to the routine information of the routine called by the self routine, and the caller routine information is a pointer to the routine information of the routine that calls the self routine.

The routine identification table contains, for each routine, the program network number of that routine, and
The table having the routine name as an element is searched for the identification number of the program network of the corresponding routine unit from the subroutine name described in the subroutine call instruction, and the program network of the corresponding routine is identified.

Next, the inside of the replaced program path expression tree A (not shown) is searched in place of the node 303, and expansion is continued (step 807). When all the nodes of the tree A (not shown) in the program path expression have been searched and expanded, it is determined that the expansion related to the node 303 is completed, and in processing 315, one element is popped from the recursive call management stack and the node 303 The expansion is completed (step 808).

If the number of times the label 306 of the node 303 is registered exceeds the number of times specified by the user, the node 303 is marked as an invalid node, and the process for the node 303 is performed. This is the end (step 809).

In this way, FIG. 8 (a) and FIG.
(B) As shown in FIG. 9, the program path expression tree corresponding to the called subroutine is replaced with a node of the program path expression tree indicating the subroutine call. Instead of obtaining the program path expression as a character string expression, by using an expression tree, the replacement can be a simple binary tree reconnection.

Next, the processing of the program path type expansion unit 108 will be described.

Since the program path expression obtained by the subroutine replacing unit 107 has the shape of an expression tree,
The program path type expansion unit 108 expands this and acquires all the program paths in the routine to form a list. The expansion is recursively performed based on the search of the binary tree.

The program path type expansion unit 108 has a branch stack for storing branch positions and a expansion buffer for holding the program path being expanded. In the branch stack, branch position information indicating the position of the node of the branch of the process and branch selection information indicating the proceeding direction are stored.

Flowcharts of the program path type expansion processing are shown in FIGS. The expansion method will be described by taking the program path expression tree of FIG. 8B as an example.

The expansion is performed by searching the expression tree in the order of precedence with the left child node first. While searching, the label of the node is read (step 901), and the label of the leaf node having no invalid mark is written in the expansion buffer (step 905). If the label of the node being searched is "*"
If it is (asterisk) (step 903),
Since this represents the concatenation of processes, the expansion process of the right subtree is performed after the left subtree of the node (step 906).
907). If the node under search has an invalid mark, that node is ignored (step 90).
4). Upon searching up to the node 331 in FIG. 8B, a node representing the control structure for selection is encountered (step 9).
02). Here, it is checked whether or not the information of the node 331 is registered in the branch stack (step 908). However, since the branch stack is still empty, the information of the node 331 has not been registered. Therefore, the node to be searched next is selected from the left and right child nodes, and the label of this node and the selected direction are stored in the branch stack (FIG. 13).
Step 913). In the branch node, the first search is advanced toward the left child node, and the second search is advanced toward the right child node. Here, the node 331 is advanced to the left node, that is, the node 332, and the expansion processing of the subtree having the node 332 as a root is continued (step 914). Similarly, when the first program path expression tree search is completed, the search path becomes 3
21 → 322 → 323 → 324 → 325 → 326 → 32
7 → 328 → 329 → 330 → 331 → 332 → 334
→ 335 → 336, and the branch stack has (331,
It is stored as'L ')-(335,' L '). In the expansion buffer, [s /] [t /] [u /] [v /] [w /]
A program path of [y /] [z /] is generated. Thus, the first expanded program path is obtained (step 915 in FIG. 12).

Further, in order to obtain the next program path, the branch selection information of the element at the top of the branch stack is read (step 916), and it is checked whether or not there is still a direction to go to (step 917). At this time, since the last registered element of the branch buffer is (335, 'L'), the element can still move to the right. Therefore, the expression tree is searched from the root in the same order as the first program path expansion.

After searching up to the node 331, the node representing the control structure for selection is encountered (step 902).
Here, when it is checked whether the information of the node 331 is registered in the branch stack, it is registered, but it is not the last registered element.
Expand the subtree of the left child (step 90 in FIG. 13).
8, 909, 910).

Further, the search is continued, and when the search is performed up to the node 335, a node representing the control structure of selection is encountered (step 902). Here, when it is checked whether the information of the node 335 is registered in the branch stack, the node 3
Since the information of No. 35 is registered in the branch stack and is the last registered element, the branch selection information is rewritten to “R”, and the node 335 proceeds to the right node, that is, the node 337 (step 908). , 909, 91
1,912). Similarly, when the second search of the program path expression tree is completed, the search path is 321 → 322 →
323 → 324 → 325 → 326 → 327 → 328 → 3
29 → 330 → 331 → 332 → 334 → 335 → 33
7, and the branch stack has (331, 'L')-
It is stored as (335, 'R'). In the expansion buffer, the program path [s /] [t /] [u /] [v /]
[W /] [y /] [0. ] Is obtained (step 9 in FIG. 12)
15).

Further, in order to obtain the next program path, the branch selection information of the element registered at the end of the branch stack is read (step 916), and it is checked whether there is a direction to go to (step 917). At this time, the last registered element of the branch buffer is (335, 'R').
However, both of the nodes 335 have already advanced. Therefore, this element is popped (step 918) and removed from the branch stack. Next, when it is checked whether or not the branch stack is empty (step 919), since it is not empty yet, the expression tree is searched from the root in the preceding order in the same manner as the expansion of the first program path.

After searching up to the node 331, a node representing the control structure for selection is encountered (step 902).

Then, when it is checked whether or not the information of the node 331 is registered in the branch stack, it is the last registered element of the branch stack, so that the branch selection information is rewritten to'R ', and the node 331 sends it. Is the right node,
That is, the process proceeds to the node 333 (steps 908 and 90).
9, 911, 912). Similarly, when the third search of the program path expression tree is completed, the search path is 321 →
322 → 323 → 324 → 325 → 326 → 327 → 3
28 → 329 → 330 → 331 → 333 → 334 → 33
5 → 336, and the branch stack has (331,
It is stored as'R ')-(335,' L '). In the expansion buffer, the program path [s /] [t /] [u /]
Obtain [v /] [x /] [y /] [z /] (step 9
15).

Further, in order to obtain the next program path, the branch selection information of the top element of the branch stack is read (step 916), and it is checked whether or not there is still a direction to go to (step 917). At this time, since the top element of the branch buffer is (335, 'L'), it is still possible to move to the right. Therefore, the expression tree is searched from the root in the same order as the first program path expansion.

After searching up to the node 331, a node representing a control structure for selection is encountered (step 902).
Here, when it is checked whether the position of the node 331 is registered in the branch stack, the node 331 is registered in the branch stack, but since it is not the last registered element,
The direction in which the operation was performed last time, that is, the operation proceeds to the left (steps 908, 909, and 910 in FIG. 13).

Further, the search is continued, and when the search is performed up to the node 335, a node representing the control structure for selection is encountered. Here, it is checked whether the position of the node 335 is registered in the branch stack. At this time, since the node 335 is registered at the stack top of the branch stack, the branch selection information is rewritten to “R”, and the node 335 proceeds to the right node, that is, the node 337 (steps 908, 909, 911). , 912). Similarly, 4
When the search for the tree of the program path expression for the second time is completed, the search path is 321 → 322 → 323 → 324 → 325 → 32.
6 → 327 → 328 → 329 → 330 → 331 → 333
→ 334 → 335 → 337, and the branch stack contains
It is stored as (331, 'R')-(335, 'R'). In the expansion buffer, the program path [s /] [t
/] [U /] [v /] [x /] [y /] [0. ] Is obtained (step 915).

Next, the branch selection information at the top of the branch stack is read (step 916), and it is checked whether or not there is still a direction to proceed (step 917). Since both child nodes of the node 335 have been searched, Assuming there is no node to go to, pop one element from the branch stack and discard (step 918). Furthermore, the branch selection information at the top of the branch stack is read to see if there is still a direction to go. Also for the node 331, since both child nodes have already been traced, it is determined that there is no direction to proceed, and one element is popped from the branch stack 401 and discarded (step 918). As a result, since the branch stack is empty, it is judged that all the branches have been searched (step 919), and the expansion work is ended.

Next, the processing of the program path connecting unit 109 will be described.

The program path expression expanding unit 108 expands the program path expression for each routine and obtains it as a program path list for each routine.

In the program path type linking process, the program path list for each routine is linked while considering the jump instruction. Program path connection processing is
It has a concatenation buffer for storing the program path being concatenated. The ligation procedure is shown below.

As shown in FIG. 14, the routine A 501 has l program paths 514, and the routine B 50
2 has m program paths 514 and routine C
It is assumed that there are n program paths 514 in 504.

At this time, if there is no jump instruction between these routines, the path 504 of the routine A501.
→ path 507 of routine B502 → path 509 of routine C503, path 504 of routine A501 → path 507 of routine B502 → path 51 of routine C503
The combined program paths are found by finding all combinations such as 0. If the last label of the program path 514 is an instruction to end the program in the middle of connection, the connection operation of the path is ended there.

In the program path of the routine A501, if the last label of the program path is a jump instruction like the path 505, first, the routine identification number of the routine of the jump destination is set to the routine information table 12.
3. Specify using the routine identification table.

If the routine identification number 513 is larger than the identification number 511 of the routine A501, it means that the jump is forward. Therefore, the path 505 of the routine A501 → the path 509 of the routine C503 and the path 5 of the routine A501.
05 → path 510 of routine C503 is connected.

If the specified routine identification number 525 is smaller than the identification number 527 of the routine A 517 as shown in the lower part of FIG. 14, it is determined to be a backward jump, and in order to prevent infinite connection, Put a check.
That is, the number of labels of the jump instruction detected in the concatenation buffer is counted, and it is checked whether the upper limit value of the repetition specified by the user is reached.

If the upper limit value has been reached, the currently connected program path is discarded and the next program path is expanded. If not, the routine returns to the connection destination routine to continue the connection.

In this way, the program paths of all routines are linked to obtain the program path list as a program.

Next, the program domain acquisition unit 110 will be described.

In the program domain acquisition process, for each program path 620 in the program path list obtained in the program path type concatenation process,
The program domain is acquired by the following procedure according to the flowcharts of FIGS. 15 and 16. Figure 1
7 shows a simple execution example.

First, an expression tree queue 621 is prepared (step 1101). Then, the following processing is repeated until all the program path labels are read.

First, the processing corresponding to the label of the program path is examined with reference to the syntax tree 121 (FIG. 3), and it is determined whether the processing is a data transfer, a calculation instruction, or a conditional judgment expression (step 1102). 1103). If so, the expression tree 622 of the assignment expression and the conditional expression corresponding to the processing as shown in FIG. 17 is created (step 1104). At this time, an instruction that is not directly described in the form of an assignment expression, such as a COBOL language instruction, is analyzed according to the grammar of the language and converted into a single or multiple assignment expressions to create an expression tree. To do. In addition, even if the conditional judgment expression is written using the condition name, the expression tree is created after converting it into the conditional expression that is actually judged. If the negation operator is included in the conditional expression, the logical operator or the comparison operator is appropriately converted to a conditional expression that does not include the negation operator. If the enumeration constant name is used, it is converted to the constant value indicated by it.

Further, if a variable is searched for in the generated expression tree 622 and a variable is detected, the variable name is used as a variable by using the information in the data item information table 122. Is converted into a symbol name 623 using an offset from the beginning of the data area in which is allocated and two numerical values of the size of the storage area occupied by the variable (step 1105).

Thereafter, the expression tree generated in steps 1104 and 1105 is stored in the expression tree queue 621 (step 1106).

It should be noted that items other than the labels representing the data transfer, the operation command, and the condition determination expression as the processing content are ignored.

Next, the domain of the program path is acquired from the obtained expression tree queue 621.

First, from the expression tree queue 621 to the expression tree 6
One 22 is taken out (step 1107). The procedure of the process performed when the extracted expression tree is an assignment statement is shown below.

First, the symbol name 623 (FIG. 17) on the left side of the fetched assignment statement is acquired (step 110).
9).

Next, the expression tree queue 621 is pre-read without dequeuing, and the expression tree 624 in which all or part of the storage area occupied by the variable represented by the symbol name 623 is updated first. (FIG. 17) is specified (step 111)
0, 1111). At this time, it is determined whether the updated variable in the expression tree 624 shares all or part of the storage area with the variable represented by the symbol name 623.
The offset value in the symbol name of the variable being updated is
It is determined whether or not it is included in the storage area occupied by the variable represented by the symbol name 623.

Next, the expression trees from the head of the queue to the expression tree 624 are read one by one, and the symbol name 623 or the symbol is inserted in the right side of the assignment expression or the conditional expression represented by the expression tree. It is checked whether there is a symbol name of a variable that shares the entire storage area occupied by the variable represented by the name 623, and if there is, it is replaced with the right side of the expression tree 624 of the assignment statement (step 1112).

If the expression tree 624 is not found,
In process 611, the above-described check and replacement are performed in order from the beginning for the expression trees of the entire expression tree queue 621 (step 1113).

After replacement, the expression tree 62 of the assignment statement
2 is discarded (step 1114).

Next, if the extracted expression tree is a condition determination expression, it is discarded from the expression tree queue 621 as a domain restriction condition in addition to the restriction condition list 625 (step 1115).

When the above steps 1107 to 1115 are repeated until the queue 621 of the expression tree becomes empty, the constraint condition set stored in the constraint condition list 625 becomes
Give one of the domains of the program of interest.

Furthermore, one constraint condition expression is read from the constraint condition list 625 (step 1116 in FIG. 16), and the extracted constraint condition expression is evaluated (steps 1117 and 111).
8).

If the evaluation result is true or non-evaluable for all constraint conditions, it is registered as a valid path (step 1120). If even one evaluated result is false, the path is discarded as a path having a contradictory constraint condition (step 1121).

The above processing is performed for each program path in the program path list, and for each program path in the program path list, the constraint condition for executing the path is obtained, and the domain of the program is obtained. .

18 and 19 are diagrams showing examples of the source program before analysis, and FIG. 20 is a diagram showing the contents of the source program after the ripple effect analysis process. Also,
21 to 23 are diagrams in which the source program after the ripple effect analysis processing is read by a certain spreadsheet software and summarized in a table format, and it is shown that a program path as shown by an arrow in FIG. 21 exists. ing.

[0112]

As described above, according to the present invention,
By performing the ripple effect analysis on the variables specified by the user, it is possible to identify the range related to the data of interest to the user, analyze the related program path of the data in terms of data and processing, and It is possible to automatically generate test data that meets the condition of the variable specified by. As a result, it is possible to obtain an excellent effect that it is possible to facilitate the understanding of the program at the time of debugging or diversion development, facilitate the determination of the test data, and reduce the man-hour required for the test.

[Brief description of drawings]

FIG. 1 is a functional configuration diagram showing an embodiment of a test data automatic generation device of the present invention.

FIG. 2 is a flowchart of an execution procedure of processing of the present invention.

FIG. 3 is a diagram showing an outline of data generated by a syntax analysis unit.

FIG. 4 is a configuration diagram of a ripple effect analysis unit 104.

FIG. 5 is a flowchart of a ripple effect analysis process.

FIG. 6 is a flowchart showing a continuation of FIG.

FIG. 7 is an example of a control structure tree generated by the ripple effect analysis means.

FIG. 8 is an example of a program path expression tree.

FIG. 9 is an example of a program path expression tree.

FIG. 10 is a flowchart of a subroutine replacement process.

FIG. 11 is a flowchart of a program path type expansion process.

FIG. 12 is a flowchart showing a continuation of FIG. 11.

FIG. 13 is a flowchart showing a sequel to FIG. 12;

FIG. 14 is a diagram illustrating a program path linking process.

FIG. 15 is a flowchart of a program path domain acquisition process.

16 is a flowchart showing a continuation of FIG.

FIG. 17 is a diagram showing a simple example of program domain acquisition processing.

FIG. 18 is a diagram showing an example of a source program before analysis.

FIG. 19 is a view showing a sequel to FIG. 18;

FIG. 20 is a diagram showing an example of a source program after the ripple effect analysis.

FIG. 21 is a diagram showing a part of a result obtained by implementing the present invention read into a certain spreadsheet software.

FIG. 22 is a view illustrating a sequel to FIG. 21;

FIG. 23 is a view illustrating a sequel to FIG. 22;

[Explanation of symbols]

101 ... Terminal, 102 ... Source file, 103 ... Syntax analysis unit, 104 ... Ripple effect analysis unit, 105 ... Program network creation unit, 106 ... Program path expression creation unit, 107 ... Subroutine replacement unit, 108 ... Program path expression expansion unit , 109 ... Program path connection unit, 110
... program domain acquisition unit, 111 ... test data acquisition unit, 121 ... syntax tree, 122 ... data item information table, 123 ... routine information table, 124 ... variable information, 125 ... routine information, 230 ... ripple effect specified by user Area for storing variables as the starting point of analysis, 231, ... Tree of control structure, 232 ... Sentence identification number, 233 ... Branch identification number, 234 ... Variable area 23
A list of variables that share a storage area with variables in 0, 2
35 ... a list of sentences included in the spread range, 240 ... a list of variables affected by the variables in the variable list 234, 3
01 ... Program path expression, 302 ... Tree of program path expression 306 ... Label, 621 ... Calculation from program path,
Queue that takes out substitution and conditional judgment expressions and turns them into expression trees, 6
22 ... Expression tree 623 included in expression tree queue 621
A symbol name in which a data name is represented by an offset from the head of the data area and a size, 625 ... A list of conditions that the input data must satisfy to execute a certain program path.

Front Page Continuation (72) Inventor Kenji Arai 6-81 Onoe-cho, Naka-ku, Yokohama-shi, Kanagawa Hitachi Software Engineering Co., Ltd. (56) References JP-A-2-17547 (JP, A) JP-A-5 -181655 (JP, A) (58) Fields investigated (Int.Cl. ⁷ , DB name) G06F 11/28-11/34 JISST file (JOIS)

Claims (2)

(57) [Claims] Claim: What is claimed is: 1. An apparatus for analyzing a source program and automatically generating test data, analyzing a source program of a test data generation target, creating a syntax tree, and hierarchical structure and size of variables and aliases, redefinition,
The parsing means that performs the parsing process that collects the information of the subroutine and the range in which the influence of the value of the variable specified by the user spreads in the source program are specified, and the ripple effect analysis process that takes out that part is performed. Using the ripple effect analysis means and the analysis result obtained by the ripple effect analysis processing, for the variable designated by the user,
Condition calculating means for calculating the condition that the variable should satisfy,
Means to automatically generate test data of variables that apply to the calculated conditions, and to obtain by the ripple effect analysis process
The analysis result is used to program the program network for each routine.
A program that creates a network
Program network creation means and the program network
Program path that generates a program path expression from the network
Program path expression generating means for executing the expression generation processing,
If a subroutine call is detected, call it
Replaced by the program path expression of the subroutine
Subroutine replacement means for executing routine replacement processing, and
A program path expression that expands the created program path expression
Program path type expansion means for executing expansion processing, and division
The program path obtained by
Perform program path linking process to link according to this
And a program path connecting means for
A column is the program path from the linked program path.
It is characterized by calculating the condition of variables for execution
Automatic test data generation device for programs. 2. When a program path condition is calculated, a variable name is converted into a symbol name using an offset from the beginning of a data area and two numerical values of the size of the area occupied by the variable, thereby making a plurality 2. The program test data automatic generation device according to claim 1, further comprising means for calculating a condition to be satisfied by the variable even when the variable shares an arbitrary storage area.