METHOD FOR ESTIMATING FORMAT OF LOG MESSAGE AND COMPUTER AND COMPUTER PROGRAM THEREFOR

• US 20160063388A1
• Filed: 08/27/2015
• Published: 03/03/2016
• Est. Priority Date: 08/28/2014
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mizutani, Masayoshi
• Granted Patent: US 9,875,171 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 5/048 Fuzzy inferencing

Abstract

A technique for estimating a format of a log message (LM) according to the present invention includes creating a first directed graph structure by dividing a first LM by predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the first LM; creating a second directed graph structure by performing on a second LM the same processing as that performed on the first LM; comparing nodes in the first directed graph structure with nodes in the second directed graph structure to detect nodes other than nodes including a corresponding character string; adding to the first directed graph structure the node detected in the second directed graph structure among the detected nodes as a first branch node; and estimating the format, based on the first directed graph structure including the first branch node added thereto.

Claims

1. A method for use in a computer to estimate a format of a log message, the method comprising:

a creating step of creating a first directed graph structure by dividing a first log message by predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the first log message;

a creating step of creating a second directed graph structure by dividing a second log message by the predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the second log message;

a detecting step of comparing nodes in the first directed graph structure with nodes in the second directed graph structure to detect a node in the first directed graph structure and a node in the second directed graph structure that are nodes other than nodes including a corresponding character string;

an adding step of adding to the first directed graph structure the node detected in the second directed graph structure among the detected nodes as a first branch node; and

an estimating step of estimating the format, based on the first directed graph structure including the first branch node added thereto, wherein the format includes a first portion associated with a node including a corresponding character string, a second portion associated with a node whose appearance tendency of character string is similar between the node detected in the first directed graph structure and the node detected in the second directed graph structure, and, optionally, a third portion associated with a node other than nodes having a similar appearance tendency of character string.

2. The method according to claim 1, further comprising:

a repeating step of repeating the creating step of creating the second directed graph structure, the detecting step, and the adding step.

3. The method according to claim 2, wherein the estimating step is performed based on the directed graph structure created in the adding step performed after the repeating step is performed a predetermined number of times.

4. The method according to claim 1, further comprising:

an integrating step of integrating the nodes having similar appearance tendencies of character strings into one node in the first directed graph structure including the first branch node added thereto,

wherein the estimating step is performed based on the first directed graph structure in which the nodes having similar appearance tendencies of character strings are integrated into one node.

5. The method according to claim 4,

wherein a determination that the appearance tendencies of character strings are similar to each other is performed on the basis of:

a first condition that a percentage of character strings having similar character types is equal to or more than a predetermined value,

a second condition that a character length is equal to or more than a predetermined value,

a third condition that an editing distance between characters is short, or

a fourth condition that at least two of the first to third conditions are satisfied.

6. The method according to claim 4, further comprising:

a repeating step of repeating the creating step of creating the second directed graph structure, the detecting step, the adding step, and the integrating step.

7. The method according to claim 6, wherein the estimating step is performed based on the directed graph structure created in the integrating step performed after the repeating step is performed a predetermined number of times.

8. The method according to claim 4, wherein the first directed graph structure including the first branch node added thereto has a closed path including two nodes including a corresponding character string, at least one node detected in the first directed graph structure, and at least one node detected in the second directed graph structure, and the at least one node detected in the first directed graph structure and the at least one node detected in the second directed graph structure exist between the two nodes including the corresponding character string.

9. The method according to claim 8,

wherein in case that the closed path includes a plurality of closed paths,

the detecting step further includes a determining step of recursively determining, from a smaller closed path of the plurality of closed paths, that the appearance tendencies of character strings are similar to each other.

10. The method according to claim 4, further comprising:

an outputting step of outputting the first directed graph structure in which the nodes having similar appearance tendencies of character strings are integrated into one node as an automaton.

11. The method according to claim 10, further comprising:

a creating step of creating a third directed graph structure by dividing a third log message by the predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the third log message;

a determining step of determining whether a node in the third directed graph structure corresponds to a node in the automaton;

a detecting step of comparing,

in accordance with a node in the third directed graph structure being different from a node in the automaton,

nodes in the first directed graph structure including the first branch node added thereto with nodes in the third directed graph structure to detect a node in the first directed graph structure including the first branch node added thereto and a node in the third directed graph structure that are nodes other than nodes including a corresponding character string; and

an adding step of adding to the first directed graph structure including the first branch node added thereto the node detected in the third directed graph structure among the detected nodes as a second branch node,

wherein the estimating step is performed based on the first directed graph structure including the second branch node added thereto.

12. The method according to claim 11,

wherein the determining step of determining whether the node in the third directed graph structure corresponds to the node in the automaton includes:

a determining step of determining, in accordance with at least one node in the third directed graph structure satisfying a predetermined condition with respect to the integrated node in the automaton, that the node in the third directed graph structure corresponds to the node in the automaton.

13. The method according to claim 1,

wherein the detecting step includes:

a searching step of searching for, in case that a node in the first directed graph structure and a node in the second directed graph structure that include a different character string are found, a subgraph and a path including the largest number of partially corresponding nodes in the found nodes.

14. The method according to claim 13, wherein the searching step is performed using a memorizing recursion technique.

15. The method according to claim 1,

wherein the estimating step includes:

an estimating step of estimating the format, by scanning at least a path passing from an origin node to a terminal node of the first directed graph structure including the first branch node added thereto.

16. The method according to claim 15, wherein in case that the path includes a plurality of paths, the format includes the first portion, the second portion, and, optionally, the third portion, which are associated with nodes in the plurality of paths.

17. The method according to claim 1, wherein the predetermined characters are signs or blank characters.

18. The method according to claim 1, wherein the second portion is a sign representing an arbitrary character string.

19. A computer for estimating a format of a log message, the computer comprising:

directed graph structure creation means for creating a first directed graph structure by dividing a first log message by predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the first log message, and creating a second directed graph structure by dividing the second log message by the predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the second log message;

node detection means for comparing nodes in the first directed graph structure with nodes in the second directed graph structure to detect a node in the first directed graph structure and a node in the second directed graph structure that are nodes other than nodes including a corresponding character string;

directed graph structure change means for adding to the first directed graph structure the node detected in the second directed graph structure among the detected nodes as a first branch node; and

format estimation means for estimating the format, based on the first directed graph structure including the first branch node added thereto, wherein the format includes a first portion associated with a node including a corresponding character string, a second portion associated with a node whose appearance tendency of character string is similar between the node detected in the first directed graph structure and the node detected in the second directed graph structure, and, optionally, a third portion associated with a node other than nodes having a similar appearance tendency of character string.

20. A computer program product for estimating a format of a log message, the computer program product comprising:

one or more computer-readable tangible storage medium and program instructions stored on at least one of the one or more tangible storage medium, the program instructions executable by a processor, the program instructions comprising;

program instructions to create a first directed graph structure by dividing a first log message by predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the first log message;

program instructions to create a second directed graph structure by dividing a second log message by the predetermined characters to define divided portions as nodes and arranging the nodes in order from the beginning of the second log message;

program instructions to compare nodes in the first directed graph structure with nodes in the second directed graph structure to detect a node in the first directed graph structure and a node in the second directed graph structure that are nodes other than nodes including a corresponding character string;

program instructions to add to the first directed graph structure the node detected in the second directed graph structure among the detected nodes as a first branch node; and

program instructions to estimate the format, based on the first directed graph structure including the first branch node added thereto, wherein the format includes a first portion associated with a node including a corresponding character string, a second portion associated with a node whose appearance tendency of character string is similar between the node detected in the first directed graph structure and the node detected in the second directed graph structure, and, optionally, a third portion associated with a node other than nodes having a similar appearance tendency of character string.