JP4501978B2 - Data processing apparatus, system, program, and method - Google Patents

Description

  The present invention relates to a data processing apparatus, system, program, and method, and more particularly, to a data processing apparatus, system, program, and method in dynamic program verification.

  Dynamic program verification is verification of a program using a technique such as a test for performing verification by giving an input value to a target program and executing the program, or a simulation for performing verification by performing a similar equivalent process. . When performing dynamic program verification, it is necessary to create in advance a set of input values to be given to a program to be verified, or to prepare rules (constraints) for automatically generating input values.

  As a technique for creating a set of input values (test case) in a test, for example, there is an equivalence division (page 52 of Non-Patent Document 1). This technology distinguishes between valid equivalence classes that represent the appropriate input to the program from the constraints on the input values and invalid equivalence classes that represent the improper input, so that the total number of test cases required is minimized. Is a technology to design. However, in practice, there are cases where the constraint condition for the input value cannot be specified sufficiently. When dynamic program verification is performed in a state where the constraint conditions cannot be specified sufficiently, a failure is detected not only due to a bug inherent in the verification target program but also due to an inappropriate set of input values that cannot occur in the actual system. (Test / verification may fail).

  When a failure is detected by dynamic program verification, it is necessary to deal with the following procedure. First, the execution trace when this failure is detected is analyzed, and the conditions for the input value (the range of the input value and the magnitude relationship with other input values) for generating the failure are specified. Then, using the condition, it is determined whether the test / verification has failed due to a bug inherent in the program to be verified, or whether the input value pair has failed, or has failed. In the former case, a bug is found and corrected, and in the latter case, a correct constraint condition for the input value is derived so that the same failure does not occur.

  As a technique for investigating the cause of the failure, for example, a program debugging method including an execution trace generation method is described in Patent Document 1. In this related method, debugging is performed while referring to an execution trace displayed in association with a source program on the screen of the display device. When a condition for an input value for causing a failure is specified by this method, the condition is indicated as one or more sets of specific input values.

JP 05-064434 A Translated by Shin Nagao, Glenford J. Myers, “Software Test Techniques, Second Edition”, Modern Science, July 31, 2006, pp. 52-59

  In Patent Document 1 and Non-Patent Document 1, when dynamic program verification is performed, when a condition for an input value for generating a detected fault is indicated, the generation condition is indicated as a set of one or more specific input values. It was only. For this reason, there was a problem that other input values had to be verified manually.

  For example, a dynamic program verification is performed on the C language program shown in FIG. 2, and in the case of the input value shown in FIG. A violation failure is detected. In this case, when the condition for the input value for generating the failure is extracted based on the execution trace at the time of detecting the failure shown in FIG. 3, a specific input of offset = 4, idx1 = 3, idx2 = 2 The condition that combines the values is indicated as the cause of the failure.

  If idx2 = 2 is an inappropriate value as an input value, the same execution trace as the execution trace when this failure is detected is detected because the value of idx2 is inappropriate from the set of input values used for verification. It is necessary to remove things. However, from the information of idx2 = 2 alone, it is possible to determine under what conditions other than idx2 = 2 (for example, idx2> 0 or idx2 <4) or whether the failure occurs due to the magnitude relationship with other input values. Absent. For this reason, it is necessary to derive a conditional expression for defining an inappropriate value of idx2 manually, which is troublesome.

  The objective of this invention is providing the data processor, system, program, and method which solve the subject mentioned above.

  In the dynamic program verification, the data processing apparatus of the present invention generates a failure determination conditional expression from a failure occurrence instruction on the execution trace at the time of failure detection, a failure content, and a failure determination rule, and the failure occurrence instruction is determined as the failure determination Execution trace correction means for generating a correction trace replaced with a conditional expression, and the conditional expression of the branch instruction in the correction trace or the failure determination conditional expression are rewritten based on the substitution expression in the correction trace, resulting in a failure. Fault occurrence condition extracting means for extracting as a fault occurrence conditional expression defining a range of input values.

  In the dynamic program verification, the system of the present invention generates a failure determination conditional expression from a failure occurrence instruction on the execution trace at the time of failure detection, a failure content, and a failure determination rule. An execution trace correcting means for generating a corrected trace replaced in step (b), and rewriting the conditional expression of the branch instruction in the corrected trace to the failure determination conditional expression based on the assignment expression in the corrected trace, and an input value causing a failure Failure occurrence condition extracting means for extracting as a failure occurrence condition expression defining a range of

  The program of the present invention generates a failure determination conditional expression from a failure occurrence instruction on the execution trace at the time of failure detection, a failure content, and a failure determination rule, and a modified trace in which the failure occurrence instruction is replaced with the failure determination conditional expression. A failure occurrence conditional expression that defines a range of input values that cause a failure by rewriting the processing to be generated and the conditional expression of the branch instruction in the correction trace to the failure determination conditional expression based on the substitution expression in the correction trace The computer executes the process of extracting as

  According to the method of the present invention, the computer generates a failure determination conditional expression from the failure occurrence instruction on the execution trace at the time of failure detection, the failure content, and the failure determination rule, and replaces the failure occurrence instruction with the failure determination conditional expression. A fault occurrence condition that generates a correction trace, rewrites the conditional expression of the branch instruction in the correction trace to the fault determination conditional expression based on the assignment expression in the correction trace, and defines a range of the input value that causes the fault Extract as an expression.

  According to the present invention, it is possible to obtain a condition of an input value that causes a failure as a conditional expression defining a range.

  Next, the present invention will be described in detail with reference to the drawings. FIG. 1 is a block diagram showing the configuration of the first embodiment of the present invention. The first embodiment of the present invention includes a central processing unit 111, an output device 112, and a secondary storage device 113.

  The central processing unit 111 includes an execution trace correcting unit 121 and a failure occurrence condition extracting unit 122.

  The secondary storage device 113 includes a program storage unit 131, an execution trace storage unit 132, a failure content storage unit 133, and a failure determination rule storage unit 134.

  The program storage unit 131 stores a verification target program 141 having a structure shown in FIG. The execution trace storage unit 132 stores an execution trace having the structure shown in FIG. 3 in which a set of instructions executed by verification and variable values referred to at the time of execution of these instructions are stored in a time series. 142 is stored. The failure content storage unit 133 stores the failure content 143 of the structure shown in FIG. 4 (for example, “arrangement boundary (lower bound) violation in a [pos]”) detected by verification and stored by means not shown. ing. The failure determination rule storage unit 134 stores a failure determination rule 144 having a structure shown in FIG. 5 (for example, “array subscript <0”, etc.) stored by means not shown. The failure determination rule 144 is a rule for deriving a conditional expression for determining the occurrence of a failure corresponding to the failure content 143 stored in the failure content storage unit 133.

  The execution trace correcting unit 121 reads the verification target program 141 from the program storage unit 131 after detecting the failure. Then, the execution trace correcting means 121 reads the execution trace 142 from the execution trace storage unit 132 after detecting the failure. Then, the execution trace correcting unit 121 reads the failure content 143 from the failure content storage unit 133 after detecting the failure. Then, the execution trace correcting unit 121 reads the failure determination rule 144 from the failure determination rule storage unit 134 after detecting the failure.

  Then, the execution trace correcting unit 121 derives a failure determination conditional expression from the failure content 143 and the failure determination rule 144. Then, the execution trace correcting means 121 generates a correction trace 152 having the structure shown in FIG. 6 in which the fault determination conditional expression derived from the fault occurrence instruction at the end of the execution trace 142 is replaced.

  The failure occurrence condition extraction unit 122 rewrites the conditional expression or the failure determination conditional expression of the branch instruction in the correction trace 152 delivered from the execution trace correction unit 121 based on the substitution expression in the correction trace 152. Then, the failure occurrence condition extracting unit 122 extracts the rewritten branch instruction conditional expression or failure determination conditional expression as a conditional expression defining a range of input values. Then, the failure occurrence condition extraction unit 122 outputs the extracted conditional expression group to the output device 112 as a failure occurrence condition.

  Next, the operation of the embodiment of the present invention will be described with reference to the drawings. FIG. 7 is a flowchart showing an operation of extracting a failure occurrence condition performed by the central processing unit 111.

  In the central processing unit 111, the execution trace correction unit 121 acquires the execution trace 142 (see the example of FIG. 3) when the failure “hz1” is detected from the execution trace storage unit 132 of the secondary storage device 113. Further, the execution trace correcting unit 121 acquires the failure content 143 from the failure content storage unit 133. Further, the execution trace correcting unit 121 acquires the failure determination rule 144 “rule” corresponding to the failure content 143 from the failure determination rule storage unit 134 (step ST1).

  The execution trace correcting unit 121 derives the failure determination conditional expression “ce” from the failure determination rule 144 “rule” corresponding to the failure content 143 (step ST2). Then, the execution trace correction means 121 creates a correction trace 152 in which the fault occurrence instruction at the end of the execution trace 142 is replaced with the fault determination conditional expression “ce” (step ST3).

  The failure occurrence condition extraction unit 122 sets a set of conditional expressions “C” (hereinafter referred to as failure occurrence conditional expression group “C”) for generating the failure “hz1” as an empty set (step ST4).

  Then, the failure occurrence condition extraction unit 122 performs the processing from step ST6 to step ST14 described below for all branch instructions or failure determination conditional expressions in the correction trace 152 (step ST5, step ST15).

  The failure occurrence condition extraction unit 122 sets the execution time of the branch instruction or the failure determination conditional expression as the execution time “pb” (step ST6). Then, the conditional expression or failure judgment conditional expression of the branch instruction at the execution time “pb” is set as the branch condition “cb”. At this time, if the branch condition “cb” is not satisfied due to the variable value referenced at the execution time “pb” of the correction trace 152, the negative conditional expression of the branch condition “cb” is set as the branch condition “cb”. (Step ST7).

  Subsequently, the failure occurrence condition extraction unit 122 performs the processing from step ST9 to step ST11 described below on the instruction from the execution time point “pb” to the beginning of the correction trace 152 (step ST8, step ST12). .

  The failure occurrence condition extraction unit 122 checks the instruction (step ST9). If the instruction is an assignment instruction (YES in step ST9), the failure condition extraction unit 122 checks whether a variable that is the left-side value of the assignment expression exists as a term in the branch condition “cb” (step ST10). If it exists as a term (YES in step ST10), the failure condition extraction means 122 rewrites the corresponding term in the branch condition “cb” with the expression on the right side of the substitution expression (step ST11).

  Next, the failure occurrence condition extraction unit 122 checks whether or not the branch condition “cb” for which the term has been rewritten includes a variable that becomes an input value (step ST13). Then, when a variable that is an input value is included (YES in step ST13), the failure condition extraction unit 122 adds the branch condition “cb” to the failure condition group “C” (step ST14).

  Then, the failure occurrence condition extraction unit 122 outputs the failure occurrence condition expression group “C” as a failure occurrence condition to the output device 112 (step ST16), and the process ends.

  Next, with reference to the flowchart of FIG. 7, it demonstrates in detail using actual data. As a specific example, it is assumed that the verification is executed by giving the input value shown in FIG. 8 to the C language program 141 shown in FIG. As a result, a failure of “arrangement boundary (lower bound) violation” is detected by the assignment instruction “a [pos] = val” on the 16th line of the program 141, and the execution trace 142 at that time is as shown in FIG. Suppose that

  The execution trace correcting unit 121 acquires an execution trace 142 when a failure is detected from the execution trace storage unit 132 in the secondary storage device 113. Then, the execution trace correcting unit 121 acquires “arrangement boundary (lower bound) violation at a [pos]” as the failure content 143 from the failure content storage unit 133. Furthermore, the execution trace correcting unit 121 acquires the corresponding failure determination rule 144 “rule” “array suffix <0” from the failure determination rule storage unit 134 (step ST1).

  Again, the failure content 143 detected by the substitution instruction “a [pos] = val” on the 16th line is “array boundary (lower bound) violation at a [pos]”. Therefore, the execution trace correcting unit 121 derives a failure determination conditional expression based on the corresponding failure determination rule 144 “rule” “array suffix <0” and sets the failure determination conditional expression “ce” as “pos <0”. (Step ST2). Then, the execution trace correcting unit 121 replaces the failure occurrence instruction at the end of the execution trace 142 “EX” with the failure determination conditional expression “ce” to create the correction trace 152 shown in FIG. 6 (step ST3).

  The failure occurrence condition extraction unit 122 sets the failure occurrence condition expression group “C” as an empty set “{}” (step ST4).

  The failure occurrence condition extraction unit 122 repeatedly executes the processing from step ST6 to step ST14 for all branch instructions or failure determination conditional expressions in the correction trace 152 (loop shown by steps ST5 and ST15).

  First, the first branch instruction or failure determination conditional expression is “idx1 <idx2” at the execution time point “2”. Therefore, the failure condition extraction unit 122 sets the execution time point “pb” to “2” (step ST6). Further, referring to the variable value “idx1 = 3, idx2 = 2” on the correction trace 152, the original conditional expression “idx1 <idx2” is not satisfied. Therefore, the failure occurrence condition extraction unit 122 sets the negative conditional expression “idx1> = idx2” of the original conditional expression as the branch condition “cb” (step ST7).

  Then, the failure condition extraction means 122 performs the processing from step ST9 to step ST11 on the instruction from the execution time point “pb” (= 2) to the head of the correction trace 152 (shown in steps ST8 and ST12). loop). First, since the instruction at the execution time point “pb” (= 2) is not an assignment instruction, the failure condition extraction unit 122 does not perform Step S10 and Step S11 (NO in Step ST9). The instruction at the next execution time point “1” is an assignment instruction (YES in step ST9), but the variable “val” that is the left-side value of the assignment expression does not exist as a term in the branch condition “cb”. The generation condition extraction unit 122 does not perform step S11 (NO in step ST10). Since the execution time point “pb” (= 1) is the head of the correction trace 152, the failure occurrence condition extracting unit 122 ends the repetition from ST8 (step ST12).

  The branch condition “cb” (= “idx1> = idx2”) includes variables idx1 and idx2 that are input values (YES in step ST13). Therefore, the failure occurrence condition extracting unit 122 adds the branch condition “cb” to the failure occurrence conditional expression group “C” and sets C = {“idx1> = idx2”} (step ST14).

  Next, since the branch instruction or failure determination conditional expression next to the branch instruction at the execution time “2” is “pos <0” at the execution time “4 ′”, the failure occurrence condition extracting unit 122 executes the execution time “ pb "is set to" 4 '"(step ST6). Further, the failure occurrence condition extraction unit 122 sets the branch condition “cb” to “pos <0” (step ST7).

  Then, the failure occurrence condition extraction unit 122 performs the processing from step ST9 to step ST11 on the instruction from the execution time point “pb” (= 4 ′) to the head of the correction trace 152 (in step ST8 and step ST12). Loop shown). Since the instruction at the execution time point “pb” (= 4 ′) is not an assignment instruction, the failure occurrence condition extraction unit 122 does not perform Step S10 and Step S11 (NO in Step ST9).

  The next instruction “3” is an assignment instruction (YES in step ST9). Then, the variable “pos” that is the left-side value of the assignment expression “pos = idx2−offset” exists as a term in the branch condition “cb” (YES in step ST10). Therefore, the failure occurrence condition extraction unit 122 rewrites the term “pos” in the branch condition “cb” with the expression “idx2-offset” on the right side of the assignment expression, thereby changing the branch condition “cb” to “idx2-offset <0”. (Step ST11).

  Since the instruction at the next execution time point “2” is not an assignment instruction, the failure occurrence condition extraction unit 122 does not perform Step S10 and Step S11 (NO in Step ST9).

  Further, the instruction at the next execution time “1” is an assignment instruction (YES in step ST9). However, since the variable “val” that is the left-side value of the assignment expression does not exist as a term in the branch condition “cb”, the failure occurrence condition extraction unit 122 does not perform step S11 (NO in step ST10). Since the execution time point “pb” (= 1) is the head of the correction trace 152, the failure occurrence condition extracting unit 122 ends the repetition from ST8 (step ST12).

  The branch condition “cb” (= “idx2−offset <0”) in which the term has been rewritten includes the input value idx2 and offset (YES in step ST13). Therefore, the failure occurrence condition extraction unit 122 adds the branch condition “cb” to the failure occurrence conditional expression group “C”, and sets C = {“idx1> = idx2”, “idx2−offset <0”} (step) ST14).

  Since there are no more branch instructions or failure determination conditional expressions in the correction trace 152, the repetition from step ST5 is terminated (step ST15).

  Thus, the failure occurrence condition extraction unit 122 extracts the failure occurrence condition expression group “C”. Then, the failure occurrence condition extraction unit 122 outputs C = {“idx1> = idx2”, “idx2−offset <0”} to the output device 112 as a failure occurrence condition (step ST16), and ends.

  According to the first embodiment of the present invention, it is possible to prevent an erroneous conditional expression from being derived as a conditional expression that defines a range of input values that cause a failure. The reason is that the conditional expression for the input value is automatically extracted by rewriting the term for the conditional expression of the branch instruction existing in the correction trace based on the assignment instruction in the correction trace.

  Further, according to the first embodiment of the present invention, it is possible to reduce the investigation and analysis work for the failure detected by the dynamic program verification. The reason is that if it is found that the cause of a detected failure is an invalid input value, the condition that causes this failure in the form of a conditional expression that expresses the relationship between the input value range or other input values. It is because it extracts. Thus, a failure caused by another input value that matches the condition can be regarded as a failure detected for the same reason. For this reason, there is no need to conduct another survey / analysis work.

  Further, according to the first embodiment of the present invention, it is possible to reduce the work of refining constraint conditions such as a value range to be satisfied by an input value in dynamic program verification and a magnitude relationship with other input values. The reason is that for a conditional expression representing one or more illegal input values included in the extracted condition, a negative conditional expression of the conditional expression can be used as a correct constraint condition for the input value as it is. is there.

  Next, a second embodiment of the present invention will be described in detail with reference to the drawings. FIG. 9 is a block diagram showing a configuration of the second exemplary embodiment of the present invention.

  The data processing device 120 according to the second exemplary embodiment of the present invention includes an execution trace correcting unit 121 and a failure occurrence condition extracting unit 122. The execution trace correction unit 121 and the failure occurrence condition extraction unit 122 may be realized by hardware, may be realized by software, or may be realized by a mixture of hardware and software.

  The execution trace correction means 121 acquires the program 141 to be verified, the execution trace 142 at the time of failure detection, the detected failure content 143, and the failure determination rule 144 from means not shown. The means (not shown) may be means for an operator to input from an input device (not shown), for example. Then, the execution trace correcting unit 121 generates a failure determination conditional expression from the acquired failure content 143 and the failure determination rule 144, and the replacement is performed by replacing the failure occurrence instruction on the acquired execution trace 142 with the generated failure determination conditional expression. A trace 152 is generated. The failure occurrence condition extraction unit 122 rewrites the conditional expression of the branch instruction in the correction trace 152 to the failure determination conditional expression based on the substitution expression in the correction trace 152, and defines the range of the input value that causes the failure. Extracted as a failure condition expression.

  Thus, the same effect as that of the first embodiment can be obtained.

  Next, a third embodiment of the present invention will be described. FIG. 10 is a block diagram showing the configuration of the third exemplary embodiment of the present invention.

  The third embodiment of the present invention is substantially the same as the first embodiment. The third embodiment of the present invention is different from the first embodiment in that the output device 112 is not provided. Further, the third embodiment of the present invention differs from the first embodiment in that the secondary storage device 113 has a failure occurrence condition storage unit 135.

  The failure occurrence condition extraction unit 122 stores the extracted failure occurrence condition expression group “C” in the failure occurrence condition storage unit 135 of the secondary storage device 113.

  According to the third embodiment of the present invention, it is possible to use a failure occurrence conditional expression that is a constraint condition by means not shown, or on another day or repeatedly. The reason is that the constraint condition is stored in the secondary storage device so that it can be read out when necessary.

  The present invention can be applied to applications such as refinement of constraints on input values in dynamic program verification and analysis of failed test / verification results (categorization of input values).

It is a block diagram which shows the structure of the 1st Embodiment of this invention. It is a figure which shows the structure of the program storage part of the 1st, 3rd embodiment of this invention. It is a figure which shows the structure of the execution trace memory | storage part of the 1st, 3rd embodiment of this invention. It is a figure which shows the structure of the failure content memory | storage part of the 1st, 3rd embodiment of this invention. It is a figure which shows the structure of the failure determination rule memory | storage part of the 1st, 3rd embodiment of this invention. It is a figure which shows the example of the correction trace of the 1st thru | or 3rd embodiment of this invention. It is a flowchart which shows operation | movement of the 1st thru | or 3rd embodiment of this invention. It is an example of the input data at the time of the dynamic program verification implementation of the 1st thru | or 3rd embodiment of this invention. It is a block diagram which shows the structure of the 2nd Embodiment of this invention. It is a block diagram which shows the structure of the 3rd Embodiment of this invention.

Explanation of symbols

111 Central Processing Unit 112 Output Unit 113 Secondary Storage Unit 120 Data Processing Unit 121 Execution Trace Correction Unit 122 Fault Generation Condition Extraction Unit 131 Program Storage Unit 132 Execution Trace Storage Unit 133 Fault Content Storage Unit 134 Fault Determination Rule Storage Unit 141 Target for Verification Program 141 Program 142 Execution trace 143 Failure content 144 Failure judgment rule 152 Correction trace

Claims (10)

In dynamic program verification, a failure determination conditional expression is generated from a failure occurrence instruction on the execution trace at the time of failure detection, a failure content, and a failure determination rule, and a corrected trace in which the failure occurrence instruction is replaced with the failure determination conditional expression The execution trace correcting means to be generated, and the fault that defines the range of the input value that causes the fault by rewriting the conditional expression of the branch instruction in the correction trace to the fault determination conditional expression based on the substitution formula in the correction trace A data processing apparatus comprising failure occurrence condition extraction means for extracting as an occurrence condition expression. The data processing apparatus according to claim 1, further comprising an output device that displays the failure occurrence conditional expression. 3. The data processing apparatus according to claim 1, further comprising means for storing the failure occurrence conditional expression. The has a failure content storage unit for storing the type of the failure, the data processing apparatus according to claim 1 or 3 wherein said execution trace correcting means reads the failure content from the failure content storage unit. Wherein a fault determination rule storage unit that stores the fault determination rules, the data processing apparatus according to claim 1 to 4, wherein said execution trace correcting means reads the fault determination rule from the fault determination rule storage unit. A program storage unit for storing the verified program, data processing apparatus according to claim 1 to 5, wherein and a execution trace storage unit that stores the execution trace. The data processing apparatus according to claim 1 to 6, wherein with a failure condition storage unit for storing a pre-Symbol failure condition.

In dynamic program verification, a failure determination conditional expression is generated from a failure occurrence instruction on the execution trace at the time of failure detection, a failure content, and a failure determination rule, and a corrected trace in which the failure occurrence instruction is replaced with the failure determination conditional expression The execution trace correcting means to be generated, and the fault that defines the range of the input value that causes the fault by rewriting the conditional expression of the branch instruction in the correction trace to the fault determination conditional expression based on the substitution formula in the correction trace A system having failure occurrence condition extraction means for extracting as an occurrence condition expression. Processing for generating a failure determination conditional expression from a failure occurrence instruction on the execution trace at the time of failure detection, a failure content, and a failure determination rule, and generating a correction trace by replacing the failure occurrence instruction with the failure determination conditional expression; Rewriting the conditional expression of the branch instruction in the correction trace to the failure determination conditional expression based on the assignment expression in the correction trace, and extracting the conditional expression as a failure occurrence conditional expression that defines a range of the input value that causes the failure. A program to be executed by a computer. The computer generates a failure determination conditional expression from the failure occurrence instruction on the execution trace at the time of failure detection, the failure content, and the failure determination rule, and generates a correction trace in which the failure occurrence instruction is replaced with the failure determination conditional expression, A method of extracting a conditional expression for a branch instruction in the correction trace or the conditional expression for determining a failure based on an assignment expression in the correction trace, and extracting the conditional expression as a failure occurrence conditional expression defining a range of an input value causing a failure.

Images