JP2003241998A - Control structure extraction method, log shaping method and program therefor - Google Patents

Abstract

(57) [Summary] [Problem] To extract a control structure from a log to be formatted itself without using external information such as a source program,
A control structure extraction method capable of shaping a log using the information is provided, and a useful log shaping method including such a control structure extraction method is provided. SOLUTION: For a log 10 such as an execution trace, a directed graph expressing connections between elements included in the log 10 is created (S201), and the directed graph is decomposed into strongly connected components to form a loop structure 21. Is extracted (S20
2) The branch structure 22 included in the extracted loop structure 21 is extracted from each extracted loop structure 21 (S203). The log is shaped using the obtained loop structure 21 and branch structure 22 (S204), and the shaped log 30 of "rooted tree structure reflecting the control structure" is obtained. When the shaping log 30 includes a plurality of portions having the same execution pattern of the loop and the recursion, the portions are combined into one to simplify the rooted tree structure.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method of shaping a log such as an execution trace of a program into a rooted tree structure that reflects a control structure such as a loop or a branch included in the log.

[0002]

2. Description of the Related Art When a program is executed, a time-series record of information about which line in the source code the program executed is called a "program execution trace". "Program Execution Trace"
Can be considered as a type of “log” in that the monitored events are recorded in time series, like the system log.

Considering the execution traces obtained from the execution programs obtained by compiling the source program P shown in the following Table 1 under the conditions without optimization and with optimization, for example, 2. The execution traces T1 and T2 as shown in Table 3 are obtained.

[Table 1]

[Table 2]

[Table 3]

These execution traces can be obtained by a conventional method such as inserting probes (additional programs having a function of outputting the line numbers during program execution to a log file) at various places in the source program. As can be seen from these examples, it is difficult to intuitively understand the content of the execution trace as it is, and the analysis cannot be easily performed.

Therefore, conventionally, as a method for expressing the contents of the execution trace of a program in an easy-to-understand manner, for example, roots are prepared for a plurality of given execution traces by the number of traces, and each trace is provided individually. There is a method of generating a rooted tree structure of depth 1 by the number of traces by making it the corresponding root child.

However, it is difficult to understand the contents of each trace by simply expressing each trace with a rooted tree structure of depth 1. Therefore, the source program, which is the source of the execution program, is statically analyzed, the lines included in the loop structure and the branch structure are extracted, and using this information,
There is a method of shaping the execution trace into a form that reflects the control structure. FIG. 19 is a flowchart showing the outline of this method along the data flow.

In this method, a control structure is extracted from the source code 120 of the source program that is the source of the execution program for the execution trace which is the log 110 (S1901). Then, the obtained control structure information 13
By comparing 0 and the execution trace that is a log, it is determined which part in the execution trace corresponds to the control structure such as loop structure, branch structure, etc. To the "rooted tree structure" (S1902), and the shaping log 140 is obtained. here,
"Rooted tree structure that reflects the control structure" means a log with the root of the log and the rooted tree structure with the control structure such as loop structure and branch structure included in the log as the node nodes. To do.

For example, when the source program P shown in Table 1 is statically analyzed, the 3rd to 7th lines and the 8th to 13th lines correspond to the for loop, and the 12th line,
It can be seen that the 13th line corresponds to the if sentence. From the source program P, the initialization part of the for loop, the condition determination part, the repeat part, the line corresponding to the loop body, and the like can be known.

Then, by shaping the execution trace T1 shown in Table 2 using these pieces of information, a rooted tree structure as shown in FIG. 20 is obtained. The execution trace shaped in this way has high readability, and mechanical analysis can be easily performed.

[0010]

However, as described above, the conventional method of extracting the control structure by the static analysis of the source program and shaping the trace has the following problems.

First, in the trace output from the optimized execution program like the execution trace T2 shown in Table 3, information obtained from the source program,
The correspondence with the flow indicated by the trace may not be uniquely determined. In such a case, the above conventional method cannot extract the control structure used for shaping. Moreover, even if the source program itself is not available, the control structure cannot be extracted.

Further, the control structure is extracted for the execution trace of the program whose flow cannot be predicted in advance from the source program such as interrupt and exception processing, and the trace including dynamic information such as variable values being executed. I can't. On the other hand, the control structure cannot be extracted from logs other than the program execution trace, such as the system log and the communication log.

As described above, if the control structure cannot be extracted from the trace or other log to be shaped, the above-mentioned conventional method shapes the log into a "rooted tree structure reflecting the control structure". Can not do it.

Further, in the above-mentioned conventional method, in the case of execution trace of a program including a recursive function, there is no example in which the recursive structure is extracted and shaped into an easy-to-understand rooted tree structure reflecting the recursive structure. Furthermore, when the log structure is complicated, even if the log is shaped by reflecting the control structure, the contents of the shaped log tend to be difficult to understand.

The present invention has been made in order to solve the above-mentioned conventional problems, and an object thereof is to control a control structure from the log itself to be shaped without using external information such as a source program. An object of the present invention is to provide a control structure extraction method capable of extracting and shaping a log using the information, and to provide a useful log shaping method including such a control structure extraction method.

Another object of the present invention is to provide a log shaping method capable of extracting a recursive structure of a log and shaping the log into a rooted tree structure reflecting the recursive structure. Further, another object of the present invention is to provide a log shaping method capable of simplifying a log having a complicated structure, making the contents of the log easy to understand, and reducing the size of the log. .

[0017]

In order to achieve the above object, the present invention utilizes external information such as a source program by extracting a control structure by graphing the connection between each element included in a log. Instead, the control structure is extracted from the log itself to be shaped, and the information can be used to shape the log.

Definitions of important terms in the present invention are as follows. The “log” is a record of monitored events in time series, and is a broad concept including a system log, a communication log, a program execution trace, and the like. As described above, the "rooted tree structure that reflects the control structure" has the form of a rooted tree structure in which the root of the log is the root and control structures such as loop structures and branch structures included in the log are the node nodes. Means log.

According to a first aspect of the present invention, in a control structure extracting method for extracting a control structure contained in a log by using a computer, a connection between respective elements contained in the log stored in the storage unit is expressed. And a control structure extracting step of extracting a control structure from the created directed graph. According to the invention of claim 2, in the control structure extracting method according to claim 1, the control structure extracting step comprises: a loop structure extracting step of decomposing the created directed graph into strongly connected components to extract a loop structure; A branch structure extracting step of extracting a branch structure included in the loop structure from the loop structure.

A third aspect of the present invention is a log shaping method for shaping a log into a rooted tree structure that reflects a control structure included in the log by using a computer.
In addition to the graph creating step and the control structure extracting step in the invention described in (1), it is characterized by including a shaping step for shaping the log using the extracted control structure. The invention of claim 4 is characterized in that, in the log shaping method of claim 3, the control structure extracting step includes the loop structure extracting step and the branch structure extracting step in the invention of claim 2.

A ninth aspect of the present invention is to grasp the third aspect of the invention from the viewpoint of a program, and shapes a log into a rooted tree structure that reflects a control structure included in the log using a computer. In the program for doing so, the computer is made to realize the graph creating function, the control structure extracting function, and the shaping function corresponding to each step in the invention of claim 3.

According to the above-mentioned features, a directed graph is created for the log such as the execution trace of the program, which expresses the connections between the elements included in the log, and a loop is formed from this directed graph by decomposition of strongly connected components. A control structure such as a structure or a branch structure can be easily extracted. Therefore, without using external information such as source programs,
The control structure can be extracted from the log itself to be shaped, and the information can be used to shape the log. for that reason,
Execution traces that do not have a unique correspondence with the information obtained from the source program, execution traces that cannot be obtained by the source program, execution traces whose flow cannot be predicted or contain dynamic information, and system logs other than execution traces. Also for the communication log and the like, the control structure can be extracted to shape the log.

The invention according to claim 5 is the log shaping method according to claim 3 or 4, further comprising a re-shaping step of re-shaping the shaped log by using information of a source program of the log. Is characterized by. According to this feature, the log can be reformatted by using the information of the source program when the additional information obtained from the source program can be obtained after the log is formatted by the information obtained by using only the log. it can.

According to a sixth aspect of the present invention, in a log shaping method for reforming a log shaped into a rooted tree structure that reflects a control structure using a computer, a function included in the log stored in the storage unit. A graph creating step for creating a directed graph that expresses a calling relationship between the two, a recursive structure extracting step for extracting a recursive structure from the created directed graph, and a shaping step for shaping a log using the extracted recursive structure. It is characterized by including. According to this feature, when a log contains a recursive structure, the recursive structure can be extracted and the information can be used to shape the log, so that the rooted tree structure that reflects the recursive structure is easy to understand. can do. In addition, after the log is shaped by using the control structure such as the loop structure or the branch structure by the log shaping method according to the third to fifth aspects, the log can be reformed by using the recursive structure.

According to a seventh aspect of the present invention, in a log shaping method for reshaping a log shaped into a rooted tree structure that reflects a control structure using a computer, information on the source program of the log stored in the storage unit is used. It is characterized by including a recursive structure extraction step for extracting a recursive structure by using and a shaping step for shaping a log by using the extracted recursive structure. According to this feature, when the log includes a recursive structure, if the information of the source program is obtained, the recursive structure is extracted from the source program,
Since the log can be shaped using that information, it can be shaped into an easily understood rooted tree structure that reflects the recursive structure. In addition, after the log is shaped by using the control structure such as the loop structure or the branch structure by the log shaping method according to the third to fifth aspects, the log can be reformed by using the recursive structure.

According to an eighth aspect of the present invention, in a log shaping method for reforming a log shaped into a rooted tree structure that reflects a control structure using a computer, a loop included in the log stored in the storage unit. A pattern determining step for extracting an execution pattern of a structure or a recursive structure to determine whether or not there are a plurality of parts having the same execution pattern, and if there are a plurality of parts having the same execution pattern, one of those parts It is characterized by including a reduction step for reducing the rooted tree structure by merging into. According to this feature, when there are multiple parts with the same loop or recursion execution pattern in the formatted log, it is possible to simplify the rooted tree structure by extracting them and combining them into one. You can make the contents of the log easier to understand and reduce the size of the log.

[0027]

BEST MODE FOR CARRYING OUT THE INVENTION Embodiments of the present invention will be specifically described below with reference to the drawings. However, the embodiments described here do not limit the present invention at all, but merely exemplify one aspect of the present invention.

The present invention is typically implemented by controlling a computer with software. The software in this case realizes the operation and effect of the present invention by physically utilizing the hardware of the computer, and suitable conventional techniques are applied to the portions to which the conventional techniques can be applied. Furthermore, the specific types and configurations of hardware and software that implement the present invention, the range of processing by software, and the like can be freely changed. For example, a program that implements the present invention is one aspect of the present invention.

[1. Outline of Log Shaping Method] FIG. 1 is a flowchart showing an outline of a log shaping method to which the present invention is applied along a data flow. As shown in this FIG.
In the method according to the present embodiment, the log 10 such as execution trace
The control structure such as the loop structure and the branch structure included in the log 10 is extracted by using only this (S101). Then, using the obtained control structure information 20, the log 10 is shaped into a "rooted tree structure reflecting the control structure" (S10
2) Obtain the shaping log 30. Furthermore, when there are a plurality of portions having the same loop or recursion execution pattern in the shaping log 30, these are combined into one to reduce the rooted tree structure (S103), and the reduction log 40 is obtained. Note that the log 10, the control structure information 20, the shaping log 30, the reduction log 40
Data such as is stored in a storage unit such as a memory that constitutes a computer, and is extracted from the storage unit when used.

FIG. 2 is a flowchart showing the flow of control structure extraction / log shaping processing for extracting a control structure and shaping the log into a "rooted tree structure reflecting the control structure" together with the data flow. As shown in FIG. 2, for the log 10 such as the execution trace, a directed graph expressing the connection between the elements included in the log 10 is created (S
201), the directed graph is decomposed into strongly connected components to extract the loop structure 21 (S202), and the branch structure 22 included in the loop is extracted from each extracted loop structure 21 (S203). And the obtained loop structure 2
Format the log using 1 or the branch structure 22 (S20
4), The shaping log 30 of "a rooted tree structure reflecting the control structure" is obtained.

[2. Control Structure Extraction / Log Shaping Processing] The following specifically describes a case where the control structure extraction / log shaping processing of FIG. 2 is performed for a single or a plurality of execution traces obtained by executing the program once or more. To do.

First, a directed graph is created which represents the connections between the elements included in the execution trace to be shaped (S201). This directed graph has nodes corresponding to the respective elements appearing in the trace, and if an element B appears after the element A in the trace, it has an edge of A → B. For example, the trace T in Table 3 above
The directed graph corresponding to 2 is as shown in FIG.

Next, the strongly connected component decomposition is applied to the created directed graph. Then, consider a strongly connected component with two or more nodes included as an element, or a strongly connected component with one element but the node that is an element has an edge toward itself as a loop structure. Thus, the loop structure is extracted (S202). For example, in FIG.
When the strongly connected component is decomposed into the directed graph shown in FIG. 5, five strongly connected components a, b, c, d and e are obtained as shown in FIG. Of these, only the component d has two or more contact elements, so the five nodes 4, 5 included in this component are included.
It can be seen that 7, 12, 13 form a loop.

In order to extract multiple loops, the following processing may be performed. That is, if there is an edge from the node y outside the p to the node x in the strongly connected component p corresponding to the loop obtained by the loop structure extraction processing, the node x is regarded as the entrance of the loop. , Node x
Cut all edges towards. Then, the strongly connected component decomposition is performed again on the directed graph in the loop p. Then, as in the above loop structure extraction processing, the number of nodes is 2
The above strongly connected component, or the strongly connected component in which the number of elements is 1 but the node that becomes an element has an edge toward itself, is regarded as a loop included in the loop p, and thus the loop structure is obtained. To extract. By repeating the above operation, multiple loops can be extracted.

In the example of FIG. 4, since the edge from the node 3 of the strongly connected component c exists at the node 4 of the loop d, it can be seen that the node 4 is the entrance of the loop d. Therefore, if all the edges toward the node 4 are cut, and then the loop d is decomposed into the strongly connected components, all the nodes of the loop d independently form the strongly connected components. Therefore, it can be seen that the loop is not included inside the loop d.

Then, for each extracted loop structure, a branch structure included in the loop is extracted (S20).
3). Specifically, for example, the following processing is performed. First, all the edges from the nodes inside the loop to the nodes outside the loop are cut. Also, all edges toward the node at the beginning of the loop (select one if there are multiple) are cut off. Next, in order from the node at the beginning of the loop, the nodes to which the edges are directed are examined, the node at which two or more edges exist is interpreted as the start point of the branch, and the node at which all the branched edges join is detected. The node sandwiched between the start node and the junction node of the branch is extracted as a branch structure. It is also possible to extract the branch structure contained in the extracted branch structure in the same manner.

FIG. 5 shows a graph after the edges are cut to extract the branch structure in the example of the loop d in FIG. In FIG. 5, when the nodes are sequentially traced from the entrance 4 of the loop d, it can be seen that the node 12 is the branch start point. The edges branched here finally merge at node 5. Therefore, the node 13 sandwiched between the node 12 and the node 5 independently constitutes a branched structure.
However, in the case of this example, since there is an edge that directly goes from the branch start point 12 to the confluence point 5, a node null "do nothing after branch" may be added to the branch structure.

Finally, by using the information of the loop structure and the branch structure obtained as described above, a given single or a plurality of traces are shaped to have a rooted tree structure reflecting the control structure. A trace is obtained (S204).
Specifically, check the given trace in order from the beginning,
When an element corresponding to a loop structure or a branch structure appears, insert the segment node corresponding to that structure in the trace,
Performs the process of assigning the element that follows the appearing element to the child of the segment node. Note that this shaping method is the same as the shaping method of the related art in which control structure information is extracted from the source program and shaped.

Regarding the trace T2 in Table 3, as shown in FIG. 4, the nodes 4, 5, 7, 12, 13 have a loop structure, and as shown in FIG. 5, the nodes 13, null are in the loop. Formatting will be performed using the information that the branch structure is included. FIG. 6 shows the result of shaping the trace T2 thus performed. Also, FIG.
Shows the shaping result when the same control structure extraction / log shaping processing is performed on the trace T1 in Table 2.

As described above, by performing the control structure extraction / log shaping process as shown in FIG. 2, the loop structure and the branch are obtained by using only the information of the trace itself without using the information obtained from the source program. You can extract control structures, such as structures, and shape the trace. Therefore, even for the execution trace whose correspondence between the information obtained from the source program and the flow shown by the trace is not uniquely determined like the trace T2 in Table 3, the control structure is extracted and controlled by using only the information of the trace itself. It can be shaped into a rooted tree structure that reflects the structure. Similarly, only the information of the log itself is used for the execution trace where the source program is not available, the execution trace that the flow cannot be predicted or contains dynamic information, and the system log and communication log other than the execution trace. To extract the control structure,
It can be shaped into a rooted tree structure that reflects the control structure.

On the other hand, when the additional information obtained from the source program is available, the trace of the trace can be reshaped by using the information of the source program. For example,
Information obtained from the source program P of Table 1, for example, line 3, for the trace shaped as shown in FIG.
It is also possible to obtain a reshaped trace as shown in FIG. 8 by using the conditions that 4 and 5 respectively correspond to the initialization part, the condition part, and the repeat part of the for loop.

However, in the log shaping method of the present invention, a loop structure which cannot be understood from the source code, for example, a loop structure using a goto statement can be extracted. Therefore, regarding the structure of the part that cannot be understood from such source code, FIG.
It is only necessary to format the log using the log shown in.

[3. Recursive Structure Extraction / Log Reshaping Process] In the following, an execution trace obtained by executing a program including a recursive function as shown in Table 4 is once reformed into a rooted tree structure that reflects the control structure, and then recursion is performed. A case where a structure is extracted and reformatted will be specifically described.

[Table 4]

FIG. 9 shows an execution trace of a program including the recursive function shown in Table 4 as a rooted tree structure reflecting the control structure by the control structure extraction / log shaping process and the additional information about the function shown in FIG. It is a rooted tree structure diagram which shows the result of shaping. As shown in FIG. 9, in the execution trace of a program that generally includes a recursive function, the depth of the tree becomes deep and the visibility becomes poor. In order to make it easy to understand such a poor execution trace, it is desirable to extract the recursive structure and reshape the trace reflecting the recursive structure. FIG. 10 is a flowchart showing the flow of the recursive structure extraction / log reshaping process for that purpose together with the data flow.

As shown in FIG. 10, first, in the control structure extraction / log shaping process described above, similarly to the case where a directed graph representing the connection between the elements included in the execution trace is created, the shaped trace is formed. From the (formatted log including the recursive function) 50, a digraph expressing the call relationship between the functions is created (S1001). This directed graph has nodes corresponding to each function, and the function B inside the function A
Is called, it is configured to have an edge of A → B. For example, a directed graph expressing the calling relationship of the functions appearing in the trace of FIG. 9 is as shown in FIG.

Then, the directed graph created in this way is decomposed into strongly connected components, and strongly connected components having two or more elements,
Alternatively, a recursive structure is extracted by regarding a strongly connected component having the number of elements of 1 but having an edge whose node points toward itself as corresponding to the recursive function group (S1).
002). The method for detecting the function corresponding to the entrance in the recursive function group, the recursive function group included in the recursive function group, etc. is also described in the control structure extraction and the loop structure entrance in the extraction of multiple loops in the log shaping process. This is similar to the loop detection method.

In the example of FIG. 11, two strongly connected components {main
()} And {fact ()} exist. Among them, the strongly connected component {fact ()} has an edge whose node points toward itself, and thus independently constitutes a recursive function group.

Next, the log is shaped by using the obtained recursive structure 60 (S1003), and the log 70 reflecting the recursive structure is obtained. In this log shaping, in order to reflect the recursive structure in the trace, the trace with the rooted tree structure is examined in order from the root, and when a function that becomes the entrance of the recursive function group appears, a new segment node " Insert "recursive",
When a function corresponding to the entrance of the same recursive function group appears, the work of moving it below the segment node "recursive" is repeated.

In the trace of FIG. 9, when the node is traced from the root "main ()" toward the leaf, the entrance "fact ()" of the recursive function group first appears. Therefore, this node "fac
The segment node “recursive” and the child node “0th time” are inserted in the part where “t ()” was present, and the node “fact ()” is moved to the child node of the node “0th time” for each descendant. Next, the node "fac
When the process of tracing the node from “t ()” to the leaf is restarted, the node “fact ()” below the “branch” appears again. This is the entrance to the group of recursive functions currently being processed.

Therefore, the node "fact ()" is replaced with the newly created leaf "<fact ()>". On the other hand, the node “first time” is added below the previously created segment node “recursive”, and the original node “fact ()” is moved to the descendants under the node “first time”. By further repeating these processes, a trace having a rooted tree structure that reflects the recursive structure as shown in FIG. 12 is finally obtained.

As described above, after the log such as the execution trace is shaped by using the control structure such as the loop structure or the branch structure, if the log includes the recursive structure, the recursive structure extraction / log reshaping process is performed. By doing so, it is possible to reform the rooted tree structure that reflects the recursive structure and is easy to understand, as shown in FIG. As a modified example, it is also possible to extract the recursive structure using the information of the log source program.

[4. Execution Pattern Judgment / Log Reduction Processing] Hereinafter, a case will be specifically described in which, after shaping a trace that repeats an execution pattern of a loop structure or a recursive structure, portions having the same execution pattern are collectively reduced. FIG. 13 is a flowchart showing the flow of the execution pattern determination / log reduction process in this case together with the data flow.

[4-1. Basic Processing] As shown in FIG. 13, first, an execution pattern of a loop structure or a recursive structure in a shaped trace (a shaping log including repetition of an execution pattern) 80 is extracted, and a plurality of execution patterns having the same execution pattern are extracted. Is determined (S130).
1). Then, when there are a plurality of portions 90 having the same execution pattern of the loop structure or the recursive structure, they are combined into one and made a child node of the segment node “pattern n”, so that the rooted tree structure is (S130
2) Obtain the reduced log 40.

For example, the execution pattern from the 0th time to the 2nd time of the loop structure in the trace of FIG. 6 which is the shaping result of the control structure extraction / log shaping process described above is the same, and only the execution pattern of the 3rd time is different. Therefore, 0
The parts with the same execution pattern from the second time to the second time are grouped as child nodes of the segment node "pattern 0" which is a child node of the node "loop", and the third portion is made a child node of the segment node "pattern 1". be able to. Also, with respect to the branch structure in the loop structure, similarly, portions having the same execution pattern can be put together. By such processing,
The trace of FIG. 6 can be reduced to the trace as shown in FIG.

The 0th execution pattern and the 1st execution pattern of the recursive structure in the trace of FIG. 12, which is the shaping result of the above-mentioned recursive structure extraction / log reshaping process, are the same, and only the second execution pattern is different. Therefore, 0th and 1
The parts with the same execution pattern of the second time are summarized as child nodes of the analysis node “pattern 0” which is a child node of the node “recursive”,
The second part can be a child node of the segment node “Pattern 1”. Similarly, with respect to the branch structure in the recursive structure, portions having the same execution pattern can be put together. By such processing, the trace shown in FIG. 12 can be reduced to the trace shown in FIG.

By the way, as shown in FIG. 14 and FIG.
In the simplified trace, the information about the number of iterations of the series of processing included in the loop structure or the recursive structure is lost, but on the other hand, what kind of loop structure or recursive structure is It is possible to easily grasp at a glance information about whether the pattern is executed, information about which pattern is frequently performed, and information about which pattern is infrequent. In general, the same execution pattern often appears hundreds or thousands of times in the execution trace of a program. Therefore, by performing this process of simplifying them as one pattern, The execution trace size can be very small.

[4-2. Processing when multiple loops or loops are included inside the recursive structure] In addition, when multiple loops are included in the shaped trace, or when loops are included inside the recursive structure, perform the following processing. , Root tree structure is reduced by inserting pattern segment nodes in sequence.

First, the rooted tree structure is examined from the root toward the leaves, and if a "loop or recursion" A appears at the beginning, there is 1 below each of the node nodes (other than a new loop or recursion). Insert pattern segment nodes for one A. When a new "loop or recursion" B appears, two pattern segment nodes for A and B are inserted side by side at the segment nodes below that. In this way, when multiple loops are included by increasing the number of pattern segment nodes inserted side by side each time a new "loop or recursion" appears,
Alternatively, the rooted tree structure can be mechanically reduced even when a loop is included inside the recursive structure.

For example, a trace including a double loop as shown in FIG. 16 has the following characteristics. That is,
The execution pattern of the outer loop A has three types of A0: “3-loop B-4”, A1: “3-loop B”, and A2: “3”. On the other hand, there are two types of execution patterns of the inner loop B, B0: “5-6” and B1: “5”. However, when the execution pattern of the loop A is A0, the loop B executes both patterns of B0 and B1, whereas when the execution pattern of the loop A is A1,
Loop B executes only the pattern of B1.

With respect to the trace of FIG. 16 having such a characteristic, by the above-described processing, below the inner loop B,
Pattern segment node “Pattern ABn” related to Loop A
And the pattern segment node “Pattern B
By inserting two "n" side-by-side, a reduced trace is obtained, as shown in FIG. 17, while preserving the features of the trace of FIG. In addition, in FIG.
“Pattern AB0” and “Pattern AB1” are AB0:
A pattern consisting of a sequence of patterns "B0-B1" and AB1: "B1" is expressed.

However, in such a simplification process, a large number of pattern segment nodes are arranged in the lower portion of the deep loop, and conversely, it may be difficult to understand. This problem can be mitigated by omitting pattern segment nodes that have only one pattern segment node in their children. For example, when such processing is applied to the simplified trace shown in FIG. 17, as shown in FIG. 18, only one pattern segment node “pattern B1” has a pattern segment node “pattern”. By omitting "AB1", the trace can be further simplified.

[5. Effect of Embodiment] According to the log shaping method of the present embodiment as described above, the following effects can be obtained.

First, as shown in the execution trace T2 in Table 3,
Even if the correspondence between the information obtained from the source program and the flow indicated by the trace, such as the trace output from the optimized execution program, cannot be uniquely determined, or even if the source program itself cannot be obtained, As described above, the control structure such as the loop structure or the branch structure can be extracted from the trace itself without using the external information such as the source program. Therefore, it is possible to shape the rooted tree structure that reflects the control structure of the trace itself, that is, the rooted tree structure that is easy to understand and mechanically process.

Also, for the execution trace of a program whose flow cannot be predicted in advance from the source program such as interrupts and exception handling, and the trace including dynamic information such as the variable value being executed, the loop structure from the trace itself. It is possible to extract a control structure such as a branch structure or a branch structure and shape it into a rooted tree structure that reflects the extracted control structure. On the other hand, for logs other than program execution traces, such as system logs and communication logs, extract control structures such as loop structures and branch structures from the logs themselves, and shape them into a rooted tree structure that reflects the extracted control structures. You can

If the additional information obtained from the source program is available after the log is shaped by the information obtained using only the log, the log of the source program may be used to re-format the log. It is possible. In this case, it is possible to obtain the same shaping result as in the conventional technique in which the control structure is extracted from the source program and the log is shaped.

Further, after the log is shaped by using a control structure such as a loop structure or a branch structure, if the log includes a recursive structure, it is reformed into an easy-to-understand rooted tree structure that reflects the recursive structure. can do. Also, if there are multiple parts with the same loop or recursion execution pattern in the formatted log, by combining them into one and simplifying the rooted tree structure, the contents of the log can be easily understood. In addition to making it easier to process mechanically, generally, the size of the log can be made much smaller than that before the reduction.

[6. Other Embodiments] The present invention is not limited to the above-described embodiments, and various other forms can be implemented within the scope of the present invention. For example, in the above-described embodiment, the method of extracting the control structure from the log itself and shaping it into a rooted tree structure that reflects the extracted control structure has been described, but the present invention is a method of extracting the control structure from the log itself. Therefore, the effect of the present invention can be obtained only by performing such control structure extraction processing.

The above-described recursive structure extraction / log reshaping process and execution pattern determination / log reduction process are shaped by the log shaping method according to the present invention such as the control structure extraction / log shaping process shown in FIG. The present invention is not limited to logs and can be similarly applied to logs shaped by conventional techniques.

[0069]

As described above, according to the present invention,
By extracting the control structure by graphing the connection between each element included in the log, the control structure is extracted from the log itself to be shaped without using external information such as the source program, and that information is used. It is possible to provide a control structure extraction method capable of shaping a log by means of a log and a useful log shaping method including such a control structure extraction method.

Further, it is possible to provide a log shaping method capable of shaping the log into a rooted tree structure reflecting the recursive structure by graphing the call relationship between the functions included in the log and extracting the recursive structure. Also, by extracting multiple parts with the same loop or recursion execution pattern from the log and combining them into one, the log having a complicated structure is simplified, and the contents of the log can be easily understood.
It is possible to provide a log shaping method capable of reducing the log size.

[Brief description of drawings]

FIG. 1 is a flowchart showing an outline of a log shaping method to which the present invention is applied along a data flow.

2 is a flowchart showing the flow of control structure extraction / log shaping processing in the log shaping method shown in FIG. 1 together with the flow of data.

FIG. 3 is a directed graph created by the process shown in FIG. 2 to express the connection between the elements included in the trace shown in Table 3.

4 is a graph showing the result of applying strongly connected component decomposition to the digraph shown in FIG. 3 by the processing shown in FIG.

5 is a graph after the edge is cut to extract the branch structure in the loop of the graph shown in FIG. 3 by the process shown in FIG. 2;

FIG. 6 is a rooted tree structure diagram showing a result obtained by extracting a control structure from the trace itself and performing shaping on the trace shown in Table 3 by the processing shown in FIG. 2.

FIG. 7 is a rooted tree structure diagram showing a result of extracting a control structure from the trace itself and performing shaping on the trace shown in Table 2 by the process shown in FIG. 2.

8 is a rooted tree structure diagram showing the result of reshaping the trace shaped as shown in FIG. 6 using the information obtained from the source program of Table 1. FIG.

9 is a rooted tree structure diagram showing a result of shaping the execution trace of the program including the recursive function shown in Table 4 into a rooted tree structure reflecting the control structure by the processing shown in FIG.

FIG. 10 is a flowchart showing a flow of recursive structure extraction / log reshaping processing performed on a shaping log including a recursive function together with a data flow in the log shaping method to which the present invention is applied.

FIG. 11 is a directed graph created to express the calling relationship of the functions appearing in the trace shown in FIG.

12 is a rooted tree structure diagram showing a result of reshaping the trace shown in FIG. 9 using a recursive structure.

FIG. 13 is a flowchart showing a flow of an execution pattern determination / log reduction process to be performed on a shaping log including repetition of a loop or a recursive execution pattern in a log shaping method to which the present invention is applied together with a data flow.

FIG. 14 is a rooted tree structure diagram showing a result of performing reduction processing on the trace shown in FIG. 6;

FIG. 15 is a rooted tree structure diagram showing a result of performing reduction processing on the trace shown in FIG. 12;

16 is a rooted tree structure diagram showing an example of a trace including a double loop shaped by the processing shown in FIG. 2. FIG.

FIG. 17 is a rooted tree structure diagram showing a result of performing reduction processing on the trace shown in FIG. 16;

FIG. 18 is a rooted tree structure diagram showing the processing contents and the result when further reduction processing is performed on the trace shown in FIG. 17;

FIG. 19 is a flowchart showing an outline of a conventional execution trace shaping method along a data flow.

FIG. 20 is a rooted tree structure diagram showing the result of extracting the control structure from the source program and shaping the trace shown in Table 2 by the method shown in FIG.

[Explanation of symbols]

10 ... Log 20 ... Control structure information 21 ... Loop structure 22 ... Branched structure 30 ... Formatting log 40 ... Simplified log 50 ... Formatting log including recursive function 60 ... Recursive structure 70 ... Formatting log reflecting recursive structure 80 ... Formatting log including repetition of execution pattern 90 ... Multiple parts with the same execution pattern a, b, c, d, e ... strongly connected component

Continued front page    (72) Inventor Wataru Okamoto             1st Komukai Toshiba-cho, Sachi-ku, Kawasaki-shi, Kanagawa             Inside the Toshiba Research and Development Center (72) Inventor Masayuki Hirayama             1st Komukai Toshiba-cho, Sachi-ku, Kawasaki-shi, Kanagawa             Inside the Toshiba Research and Development Center F term (reference) 5B042 GA02 HH30 MA08 MA14 MC13

Claims (9)

[Claims] 1. A control structure extracting method for extracting a control structure contained in a log by using a computer, wherein a directed graph representing a connection between respective elements contained in the log stored in a storage unit is created. A control structure extracting method comprising: a graph creating step; and a control structure extracting step of extracting a control structure from the created directed graph. 2. The control structure extracting step includes: a loop structure extracting step of decomposing the created directed graph into strongly connected components to extract a loop structure; and a branch structure included in the loop from each extracted loop structure. The control structure extraction method according to claim 1, further comprising: a branch structure extraction step of extracting the control structure. 3. A log shaping method for shaping a log into a rooted tree structure that reflects a control structure contained in the log by using a computer, and between the elements contained in the log stored in the storage unit. A graph creating step for creating a directed graph expressing the connection, a control structure extracting step for extracting a control structure from the created directed graph, and a shaping step for shaping a log using the extracted control structure. A characteristic log shaping method. 4. The control structure extracting step includes: a loop structure extracting step of decomposing the created directed graph into strongly connected components to extract a loop structure; and a branch structure included in the loop from each extracted loop structure. 4. The log shaping method according to claim 3, further comprising a branch structure extraction step of extracting 5. A reformatting step of reformatting a reformatted log using information of the source program of the log,
The log shaping method according to claim 3 or 4, further comprising: 6. A log shaping method for reshaping a log shaped into a rooted tree structure reflecting a control structure using a computer, wherein a call relationship between functions included in a log stored in a storage unit is defined. It is characterized by including a graph creating step for creating a directed graph to be expressed, a recursive structure extracting step for extracting a recursive structure from the created directed graph, and a shaping step for shaping a log using the extracted recursive structure. How to format the log. 7. A log reshaping method for reshaping a log shaped into a rooted tree structure that reflects a control structure by using a computer, using a source program information of the log stored in the storage unit to recurse. A log shaping method, comprising: a recursive structure extracting step of extracting a structure; and a shaping step of shaping a log by using the extracted recursive structure. 8. A log shaping method for reforming a log shaped into a rooted tree structure that reflects a control structure using a computer, wherein a log structure or a recursive structure included in a log stored in a storage unit is used. The pattern judgment step that extracts the execution pattern and determines whether there are multiple parts with the same execution pattern, and if there are multiple parts with the same execution pattern, roots by combining these multiple parts into one. A log shaping method comprising: a reduction step of reducing a tree structure; 9. A program for shaping a log into a rooted tree structure that reflects a control structure included in the log by using a computer, between elements included in the log stored in the storage unit. Implements on a computer a graph creation function that creates a directed graph that expresses connections, a control structure extraction function that extracts a control structure from the created directed graph, and a shaping function that shapes the log using the extracted control structure. A program characterized by: