JPH06202905A - Critical slice program debug system - Google Patents

Abstract

(57) [Summary] [Purpose] To extract the statements that cause data errors without waste and without omission, to improve the efficiency and reliability of debugging work. [Structure] A program debug system with extended dynamic slices, along with data and control dependencies.
Instrument part that embeds the code for recording the variable value dependency relationship with the conditional statement that affects the value set for the variable of a certain statement into the program, the variable value dependency relationship embedded in the executed program The variable value dependency recording section that records the data value and the statement that is extracted based on the data dependency relationship and the control dependency relationship, as well as the conditional statement that analyzes the variable value dependency relationship and affects the setting of the value of the variable found as a variable value error. A critical slice acquisition unit for extracting is provided.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a technique for debugging a program written in a general procedural language, and more particularly,
The present invention relates to a critical slice program debug system suitable for efficiently limiting a statement in a program having a bug based on a found data error.

[0002]

2. Description of the Related Art When a program for a computer does not meet the specifications, it is necessary to find and correct the cause of the problem in the source text. This cause is called a bug. A program bug can be classified into a case where a statement description is leaked (sentence description bug), an extra statement description (sentence excess bug), and a statement description error. Furthermore, when there is an error in the statement description, it can be classified into a case where an error of setting a value to another variable is caused (name description error bug) and a case other than that (sentence description error bug). For example, if the name of the variable on the left side is wrong in the assignment statement, it is a name description error bug. It should be noted that the sentence description error bug and the sentence description excess bug are collectively referred to as
It is a description error bug.

If there is a bug in the program, an incorrect value may be set in the variable or the control flow may change. As described above, as a conventional technique for limiting the location of a bug in a program related to a data error in which a value of a certain variable is incorrect at a certain execution point, for example, Mark Weiser, “Progr.
am Slicing, "IEEE Transact
ions on Software Engineer
ing, Vol. SE-10, No4, July 19
84, pp. Static S described in 352 to 357.
Lice (hereinafter, referred to as static slice) technology, and B. Korel and J. Laski, "D
dynamic Program Slicing, ”
Information Processing Le
tters, Vol. 29, No. 10, Oct. 19
88, pp. Dynamic described in 155 to 163.
There is a slice (hereinafter referred to as dynamic slice) technique.

The static slice related to the sentence (S) has the following data dependency (Data Dependence).
ence) and control dependency (Control Depe
It is a set of all the sentences that reach the sentence S by tracing the two dependency relationships of (ndence). Data dependency: There is a data dependency from the sentence (S1) to the sentence (S2) means that a certain variable v in the sentence (S1).
Definition reaches the sentence (S2) using the variable v, that is, the value of the variable v is set in the sentence (S1),
This is a case where the value of the variable v is not reset in the path from the statement (S1) to the statement (S2) and the value of the variable v is referred to in the statement (S2). Control dependency: There is a control dependency from the statement (S1) to the statement (S2), the statement (S1) is a branch statement or a loop statement, and whether the statement (S2) is executed is This is a case where it directly depends on the execution result of S1).

On the other hand, the dynamic slice is a set of executed statements that actually affect the value of a variable at a certain execution time when the program is executed by giving certain input data. Is. A sequence of executed statements including "repetition" is called an execution sequence. In this execution sequence, it is found by tracing the above two dependency relationships of the data dependency relationship and the control dependency relationship. To be

FIG. 4 is a block diagram showing the structure of a conventional program debug system using the dynamic slice technique. A system using this dynamic slicing technique is to compile and link an instrument section 42 in which a code for recording a dependency between sentences is embedded in a source program 41 and an instrument source program 43 in which the code is instrumented. The data dependency relation between the executed compile / link unit 44, the program execution control unit 46 for controlling the execution of the executable program 45 linked with the compile, and the executed statement is recorded as the program execution dependency relation information 47. The data dependency recording unit 46a, the control dependency recording unit 46b which records the control dependency between the executed statements as the program execution dependency information 47, and the statement dependency based on the found data error. Analysis of the data and control dependencies of the Is constituted by a dynamic slice acquisition unit 48 for extracting dynamic slice information 49 is place.

The operation of the conventional program debug system having such a configuration will be described with reference to the following sample program P. Sample program P: “1 get (n, a); 2 s: = a [1]; 3 i: = 2; 4 while i ≦ nloop 5 s: = s + a [i]; 6 i: = i + 1; end loop 7 if s> 10 then 8 if s mod2 ≠ 0 then 9 s: = s + 1; end if; end if; 10 put (s); ”This program P inputs n element values from the array a, The value of the variable s is output, and the value of the variable s is
It is defined by the following formula. s = sum + 1 (when sum> 10 and sum is an odd number) s = sum (at other times)

Now, consider a program Pb in which a sentence description error bug is embedded in the program P. In this program Pb, it is assumed that the sentence (5) is "s: = s-a [i];" instead of "s: = s + a [i];". When this program Pb is given an input and executed, the execution sequence is as follows. Execution time point Execution sequence 1 get (n, a); {n = 2, a = (16,2)} 2 s: = a [1]; {s = 16} 3 i: = 2; {i = 2} 4 i ≦ n {2 ≦ 2} 5 s: = s−a [i]; {s = s−a [2] = 16−2 = 14} 6 i: = i + 1; {i = 3} 7 i ≦ n {3 ≦ 2} 8 s> 10 {14> 10} 9 s mod2 ≠ 0 {14 mod2 ≠ 0} 10 put (s); {put (14)}

Based on this execution sequence, the dynamic slice acquisition unit 48 of FIG. 4 extracts dynamic slices as follows. First, the sentence (5) at the execution time point (5) is extracted by the data dependency as the statement that affects the variable s at the execution time point (10). Next, as a statement that affects the variables s and a [i] at the execution time point (5), the data dependence relationship causes the execution time point (1).
The sentences (1) to (3) of (3) to (3) and the sentence (4) of the aging time (4) are extracted by the control dependency. And
As the statement that affects the variable i at the execution time point (4) (= (7)), the statement (6) at the execution time point (6) is extracted by the data dependency.

On the other hand, when the static slice technique is used, the static slice is extracted based on the above-mentioned program Pb as follows. First, the sentence (9) is extracted as a sentence that affects the variable s in the sentence (10) by the data dependency. Next, as the statement that affects the variable s in this statement (9), the statement (5) is extracted by the data dependency and the statement (8) is extracted by the control dependency. And the variable s of sentence (5),
As the statement that influences a [i], the statements (1) to (3) are given by the data dependency, and the statements are given by the control dependency.
Extract sentence (4). The sentence (6) is extracted as a sentence that affects the variable i of the sentence (4) based on the data dependency. Furthermore, due to the control dependency in sentence (8),
Extract sentence (7).

FIG. 5 shows the difference between the dynamic slice and the static slice thus extracted. FIG. 5 is an explanatory diagram showing static slices and dynamic slices relating to the variable s in the output statement of the program Pb according to the conventional technique. As shown in this figure,
In the static slice, the statements (1) through (1) in the program Pb affect the variable s of the statement (10).
(9), in dynamic slice, sentences (1)-
(6) is extracted. The operator who performs the debugging searches for the sentence (5) that causes the error of the variable of the sentence (10) from the thus extracted sentences.

As described above, in the static slice,
If a data error occurs, you can limit the set of statements that can affect the incorrect value of that variable. However, since the program is statically analyzed, there is a problem that a statement that is not related to an error and is not executed, such as the statement (9), is also extracted. Also, with dynamic slices, it is possible to limit the set of sentences that actually affected the wrong value. However, like sentence (8),
When the value of a variable (here, variable s) is not set due to an error in the branching result of a branching statement, which causes a data error, the branching statement, and However, there is a problem that the whole set of statements on which the branch statement depends leaks from the execution sequence to be verified.

[0013]

The problem to be solved by the present invention is that, in the conventional technology, data that is not related to an error is extracted or data that is set in the branch result of a branch statement is leaked. One of the problems may occur that the extraction of a set of statements that cause an error may be omitted, and debugging work cannot be performed efficiently and with high reliability. An object of the present invention is to solve these problems of the prior art, reduce the load on a debugging worker by extracting a sentence not related to an error, and avoid failure of the debugging work due to omission of extraction of a sentence related to an error. It is to provide a critical slice program debug system that enables highly efficient debugging and improved reliability.

[0014]

In order to achieve the above object, the critical slice program debugging system of the present invention comprises (1) data dependence between statements of a program which is embedded in the executed program in advance. Equipped with a data dependency recording unit that records a relationship and a control dependency recording unit that records a control dependency between program statements, an incorrect value was set for a variable found during program execution. Program debug to analyze the data dependency and control dependency based on the variable value error, extract the statement that actually affected the variable value error as dynamic slice information, and limit the statement with the bug In the system, together with the data dependency and control dependency, the statement of the program and the conditional statement that affects the value set in the variable of this statement A variable value dependency record that records the variable value dependency between the instrument part that is embedded in the program and the statement of this program that is embedded in the executed program Section and the statement to extract based on the data dependency and control dependency, analyze the variable value dependency recorded in this variable value dependency recording section and affect the setting of the value of the variable found as a variable value error. And a critical slice acquisition unit that extracts a conditional statement as critical slice information, the conditional statement extracted by the critical slice acquisition unit is included, and a sentence having a bug is limited.

[0015]

According to the present invention, a critical slice (Critical Sl) that is a minimum set including a sentence that may cause a data error if there is a description error bug.
By acquiring "ice", the location where the description error bug exists is limited. That is, not only the extraction of the statement that actually affected the incorrect value as the dynamic slice, but also that "if the branch path of the branch statement A changes, the value of the variable used in the statement B is affected". It also extracts sentences that may actually affect the wrong values. As a result, even if there is a description error bug and the flow of control changes, the statement that does not affect the value of the output variable, that is, the statement whose value does not change is not extracted, and the description error bug occurs. For example, it is possible to extract only the sentences that may affect the data error.

[0016]

Embodiments of the present invention will now be described in detail with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of a configuration relating to the present invention of a critical slice program debug system of the present invention. In this figure, 1 is a source program written in a general procedural language, and 2 is a source program.
According to the present invention, the instrument unit 3 for embedding the code for recording the dependency relation between the statements of the source program 1 in the source program 1 is an instrument unit in which the code is embedded by the instrument unit 2. Ment source program, 4 is source program 3
Compile and link part that compiles and links
5 is an executable program that has been compiled and linked, 6 is a program execution control unit that controls the execution of the executable program 5, and 6a is a data dependency record that records data dependencies between executed statements. Part, 6b is a control dependency relationship recording part for recording control dependency relationships between executed statements, and 6c is related to the present invention, and is a dependency with a conditional statement that influences setting of the value of a variable of the statement. A variable value dependency relationship recording unit that records the relationship, 7 is program execution dependency relationship information that summarizes each dependency relationship between executed statements, and 8 is data dependency of the program execution dependency relationship information 7 according to the present invention. The critical slice information is extracted by extracting the statement that affected the value of the variable from the relationship and control dependency relationship, and the conditional statement that may affect the value of the variable from the variable value dependency relationship. It is a critical slice acquisition unit for outputting as 9.

With such a configuration, the critical slice program debug system of the present embodiment analyzes the dependency relation between these statements based on the found data error, and detects the statement in the program in which the bug exists. Can be limited without omission and waste, and the work of investigating bugs by the worker can be facilitated. That is, this critical slice
In the program debug system, a critical slice, which is a new type of slice that is an extension of the conventional dynamic slice, is acquired to limit the location of the description error bug. This critical slice is a minimum set that includes statements that may cause a data error if there is a description error bug, and avoids unnecessary statement extraction by static slice and statement extraction omission by dynamic slice. be able to.

The critical slice of this embodiment will be described below.
The operation of the program debug system according to the present invention will be described. As a programming language to be debugged,
Although general procedural languages such as Ada, Pascal, and C are assumed, here, in order to simplify the description, the statements in the program are assignment statements, branch statements, loop statements, function call statements, and It shall consist of input / output statements. In the instrument unit 2, when executing each statement in the program, the source program 1 is embedded with the code necessary to execute the processing described in "processing at the time of statement execution" shown in (b) below. In the program execution control unit 6,
Record the following information.

(B) Information recorded when the program is executed. While executing the executable program 5 to be debugged,
The information to be recorded is shown below. CC: Control flow C (c) at the current execution time point c. That is, a set of branch execution points (execution points of branch statements, loop statements, and function call statements) that determine execution at the current execution point c. This can be obtained by constructing a stack structure whose elements are branch execution points. Then, the operation of pushing down the element c to the stack CC is performed by "pus
hCC (c); ”, and an operation of popping up one element from the stack CC is represented by“ popCC; ”. CDef (x): For each variable x, record the latest execution time point p that defines the variable x. CDefC (x): For each variable x, the control flow C (p) at the latest execution point p in which the variable x is defined. UEXDefV (j): j at each execution time when the branch statement is executed
For, the set of variables that may be defined on the branch path that was not executed. Regarding how to obtain this set, Aiho, Ullman, "Compiler" translated by Doi (1986, published by Baifukan)
Etc.

(B) Processing during statement execution. Let c be the execution point currently being executed. (B-1) When executing the assignment statement and the input statement: If the variable defined in the assignment statement and the input statement is w, CDef (w): = c; CDefC (w): = CC; (b-2) When executing a branch statement, a loop statement, or a function call statement, pushCC (c); The execution time point c is pushed down to the stack CC. (B-3) When ending a branch statement, a loop statement, or a function call statement, popCC; one execution time point is popped up from the stack CC. However, when the loop statement is ended, “popCC;” is executed for the number of times of repetition of the loop statement body.

(B-4) When the value of the variable w is used at the time of executing the sentence, (b-4-1) data dependency recording section D (c, w): = CDef (w); 4-2) Control dependence recording part i: = CDef (w); C (i): = CDefC (w); C (c): = CC; CSC (C, w): = C (i) -C (C); (b-4-3) Variable value dependency relationship recording part i: = CDef (w) OV: = {j | i <j <c, and wεUEXDefV
(J)} C (c): = CC; CSO (c, w): = OV-C (c);

In the critical slice acquisition section 8, the program execution dependency information 7 is set as follows.
Based on, obtain a critical slice. For all execution time points c and the variable w used at the execution time point c, the data dependency recording unit D (c,
w), the control dependency CSC (c, w), and the variable value dependency recording unit CSO (c, w).
The critical slice, CS = CS (t, v), relating to the variable v at the execution time point t is obtained by the procedure described below. Here, “get (S)” means that one execution time point last executed is taken out from the set S of execution time points.
A function that returns it, “Use (t)” is a set of variables used in the statement executed at the execution time point t. Also, {} represents an empty set. “CS: = {}; NCS: = D (t, v) ∪CSO (t, v) ∪CSC (t, v) ∪C (t); while NCS ≠ {} loop i: = get (NCS); CS: = CS∪ {i} NCS: = NCS∪D (i, Use (i)) ∪CSO (i, Use (i)) ∪CSC (i, Use (i)); end loop; "

That is, first, initialization is performed by "CS: = {};", and then, data dependency D (t, v) and control dependency CSC (t, v) regarding the variable v at the execution time t.
v), variable value dependency CSO (t, v), control flow C
Take the union NCS of (t). If the union NCS is empty, the process ends. If it is not empty, the last executed execution time point i is extracted from the union NCS and recorded. Then, next, a set U of variables used in the statement executed at the last execution time point i
Take the union of each dependency found for se (i). Thereafter, this operation is sequentially repeated to acquire the critical slice CS.

Next, the program Pb described in the prior art is used.
The extraction operation of the critical slice regarding the variable s in the output statement (10) in the execution sequence of 1 will be described with reference to FIG. FIG. 2 is an explanatory diagram showing an example of the execution sequence of the program Pb. The execution sequence of the present embodiment is a case where the same inputs as those described in the prior art are given to the program Pb and executed. First, as a statement that affects the variable s of the output statement (10) at the execution time point (10), the statement (5) at the execution time point (5) is changed by the data dependency (D: solid line in the figure). In addition, the statement (4) at the execution time point (4) and the variable value dependency (in the figure, CSC: indicated by a chain line in the figure)
The statement (8) at the execution time point (9) and the statement (4) at the execution time point (7) are extracted as a union NCS by CSO: described by a broken line. Next, the last executed execution time point (9) is extracted from the union NCS, the statement (8) at this execution time point (9) is acquired as a critical slice, and the statement (8) at this execution time point (9) is acquired. The extraction operation of the critical slice for the variable s is performed. Thereafter, this operation is sequentially repeated until the union NCS becomes empty, and the critical slice CS is acquired.

In this way, the critical slice program debug system of this embodiment can also extract the statement (8) at the execution time point (9), which was omitted in the conventional dynamic slice.

FIG. 3 shows a program Pb by the critical slice program debug system in FIG.
FIG. 7 is an explanatory diagram showing a critical slice related to a variable s in the output sentence of FIG. As shown in this figure,
In the static slice, the statements (1) through (1) in the program Pb affect the variable s of the statement (10).
(9), in dynamic slice, sentences (1)-
(6), and in the critical slice according to the present invention, sentences (1) to (6) and (8) are extracted.

That is, there is a relation of dynamic slice⊆critical slice⊆static slice between the static slice or dynamic slice which is a conventional technique and the critical slice provided with the acquisition method of the present invention. The dynamic slice is the smallest set, but misses some sentences (8) affecting the wrong values. However, the critical slice is a minimum set that includes statements that may cause a data error if there is a description error bug, and by acquiring this critical slice, the location where the description error bug exists can be limited. it can. As a result, the operator who debugs can more reliably and efficiently carry out the work of investigating the bug, as compared with the conventional technique.

As described above, in the critical slice, if a statement in the critical slice has a description error bug, it may affect a data error, and a statement other than the critical slice may be described in the description error bug. Even if there is, it has the property of not affecting the data error. For example, in FIG. 3, if there is a description error bug in the statements (1) to (6) and (8) in the critical slice, it may affect the data error.
A sentence description error bug exists in sentence (5). On the contrary, even if there is a description error bug in the statement other than the critical slice, it does not affect the data error. In fact, sentences (7), (9)
Even if there is an error in the value and the control flow changes, the value of the variable s in the output sentence (10) is not affected, that is, the value does not change.

As described above with reference to FIGS. 1 to 3, in the critical slice program debugging system of the present embodiment, the minimum set including statements that may cause a data error if there is a description error bug. By acquiring the critical slice that is, it is possible to limit the statement in the program where the description error bug exists,
This makes it easier to find bugs. The present invention is not limited to the embodiment described with reference to FIGS. For example, in the present embodiment, as a result, the dynamic slice is more efficient in narrowing down the sentence (5) having the character description error bug that has affected the data error. By applying it to a large-scale program, it is possible to obtain advantages over conventional wasteful sentence extraction by static slice and omission of target sentence extraction by dynamic slice.

[0030]

As described above, according to the present invention, it is possible to avoid extraction of unexecuted statements that are not related to an error, such as static slices. Also, like dynamic slices, branching results of a branching statement of a branch statement can be avoided. It is possible to avoid leaking from the execution sequence of statements that occurs when a value is not set for a variable due to an error, which causes a data error, and reduce the load on the debug worker. Therefore, it is possible to improve the efficiency and reliability of the debugging work.

[0031]

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of a configuration according to the present invention of a critical slice program debug system of the present invention.

FIG. 2 is an explanatory diagram showing an example of an execution sequence of a program Pb.

3 is an explanatory diagram showing a critical slice related to a variable s in an output statement of a program Pb by the critical slice program debug system in FIG. 1 and a static slice and a dynamic slice according to a conventional technique.

FIG. 4 is a block diagram showing a configuration of a program debug system using a conventional dynamic slice technique.

FIG. 5 is an explanatory diagram showing static slices and dynamic slices regarding a variable s in an output statement of a program Pb according to a conventional technique.

[Explanation of symbols]

 1 Source Program 2 Instrument Part 3 Instrument Source Program 4 Compile and Link Part 5 Executable Program 6 Program Execution Control Part 6a Data Dependency Record Part 6b Control Dependency Record Part 6c Variable Value Dependency Record Part 7 Program Execution Dependency Part Information 8 Critical slice acquisition section 9 Critical slice information 41 Source program 42 Instrument section 43 Instrument source program 44 Compile link section 45 Executable program 46 Program execution control section 46a Data dependency recording section 46b Control dependency recording section 47 Program Execution dependency information 48 Dynamic slice acquisition unit 49 Dynamic slice information

Claims (1)

[Claims] 1. A data dependency relationship recording means for recording data dependency relationships between statements of the program, which is embedded in an executed program in advance, and a control dependency for recording control dependency relationships between statements of the program. A relationship recording means, and based on a variable value error in which an incorrect value is set in a variable, which is found by executing the program, analyzes the data dependency and the control dependency, and outputs the variable value error. In a program debug system that extracts the statement that actually affected the statement as dynamic slice information and limits the statement in which a bug exists, the statement of the program and the variable of the statement together with the data dependency and the control dependency Instrument means for embedding a code for recording a variable value dependency between a conditional statement that affects the value set in A variable value dependency relationship recording means for recording variable value dependency relationships between statements of the program that are embedded in the executed program in advance, and a statement to be extracted based on the data dependency relationship and the control dependency relationship, A critical slice acquisition means for analyzing the variable value dependency recorded by the variable value dependency recording means and extracting, as critical slice information, a conditional statement affecting setting of the value of the variable found as the variable value error. Be equipped with
A critical slice program debug system including a conditional statement extracted by the critical slice acquisition means and limiting the statement in which the bug exists.