Scalable and accurate mining of control flow from execution logs across distributed systems

• US 10,140,287 B2
• Filed: 09/09/2015
• Issued: 11/27/2018
• Est. Priority Date: 09/09/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dasgupta, Gargi Banerjee, Mandal, Atri, Nandi, Animesh, Neogi, Anindya, Raghavan, Sriram, Subramanian, Suriya
• Primary Examiner(s): Aspinwall, Evan
• Application Number:
  US14/848,970
• Publication Number:
  US 20170068709A1
• Time in Patent Office: 1,175 Days
• Field of Search: 707776
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3082 the data filtering being achieved by aggregating or compressing the monitored data
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 40/186 Templates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Methods and arrangements for efficiently mining a control flow graph from execution logs of a distributed system. Using at least one text clustering technique, two text clusters are generated from the plurality of execution logs. At least one approximate template is generated based on the at least two text clusters. At least one refined template is created via refining the at least one approximate template using multimodal sequencing. The control flow graph is created based on the at least one refined template. An anomaly is detected in the control flow graph.

Claims

1. An apparatus for efficiently mining a control flow graph from execution logs of a distributed system, said apparatus comprising:

at least one processor; and

a computer readable storage medium having computer readable program code embodied therewith and executable by the at least one processor, the computer readable program code comprising;

computer readable program code that receives a plurality of execution logs;

computer readable program code that mines at least one template from the plurality of execution logs in a first-phase, wherein the mining comprises computer readable program code that creates at least one template via a two-stage template mining technique, comprising;

a first stage of the two-stage template mining technique comprising computer readable program code that creates approximate-templates via a dictionary based logline transformation in order to attain scalability; and

a second second-stage of the two-stage template mining technique comprising computer readable program code that refines the mined approximate-templates by leveraging the multimodal (text+temporal-vicinity) signature of each approximate-template; and

computer readable program code that generates the control-flow graph between the mined templates in a second phase via a two-stage technique comprising;

a first-stage of the second phase comprising computer readable program code that creates, for each template, a set of the template'"'"'s temporally co-occurring templates via leveraging a time-series of occurrence of each template; and

a second-stage of the second phase comprising computer readable program code that determines, in a single-pass of the log stream for each template, the template'"'"'s immediate predecessors/successor on the temporally co-occurring templates and computer readable program code that stitches mined successors of each template to construct the control flow graph.

2. A computer program product to efficiently mine a control flow graph from execution logs of a distributed system, said computer program comprising:

at least one processor; and

a computer readable storage medium having computer readable program code embodied therewith and executable by the at least one processor, the computer readable program code comprising;

computer readable program code that receives a plurality of execution logs;

computer readable program code that mines at least one template from the plurality of execution logs in a first-phase, wherein the mining comprises computer readable program code that creates at least one template via a two-stage template mining technique, comprising;

a first stage of the two-stage template mining technique comprising computer readable program code that creates approximate-templates via a dictionary based logline transformation in order to attain scalability; and

a second second-stage of the two-stage template mining technique comprising computer readable program code that refines the mined approximate-templates by leveraging the multimodal (text+temporal-vicinity) signature of each approximate-template; and

computer readable program code that generates the control-flow graph between the mined templates in a second phase via a two-stage technique comprising;

a first-stage of the second phase comprising computer readable program code that creates, for each template, a set of the template'"'"'s temporally co-occurring templates via leveraging a time-series of occurrence of each template; and

a second-stage of the second phase comprising computer readable program code that determines, in a single-pass of the log stream for each template, the template'"'"'s immediate predecessors/successor on the temporally co-occurring templates and computer readable program code that stitches mined successors of each template to construct the control flow graph.

3. The computer program product according to claim 2, wherein the plurality of execution logs comprises raw log lines.

4. The computer program product according to claim 2, further comprising:

computer readable program code that compares the created control flow graph to at least one previously stored control flow graph;

computer readable program code that identifies, based on said comparing, at least one anomaly; and

wherein the at least one identified anomaly is selected from the group consisting of;

a sequence anomaly and a distribution anomaly.

5. The computer program product according to claim 2, wherein said mining comprises computer readable program code that utilizes at least one text-clustering technique selected from the group consisting of:

an edit-distance technique and a dictionary-based logline parameterization.

6. The computer program product according to claim 5, wherein the dictionary-based logline parameterization comprises identifying keywords and parameters for each of the plurality of execution logs.

7. The computer program product according to claim 6, wherein the identifying comprises employing a frequency analysis of words for each of the plurality of execution logs.

8. A method of efficiently mining the control flow graph from execution logs of a distributed system, said method comprising:

utilizing at least one processor to execute computer code that performs the steps of;

receiving a plurality of execution logs;

mining at least one template from the plurality of execution logs in the first-phase;

said mining comprising creating at least one template, via employing a two-stage template mining technique;

said first-stage creating approximate-templates via a dictionary based logline transformation in order to attain scalability and

said second-stage refining the mined approximate-templates by leveraging the multimodal (text+temporal-vicinity) signature of each approximate-template; and

generating the control-flow graph between the mined templates in the second-phase via a two-stage technique;

said first-stage creating for each template, the set of its temporally co-occurring templates, referred to as its Nearest-Neighbor-Group, by leveraging the time-series of occurrence of each template; and

said second-stage, in a single-pass of the logstream, determining for each template, its immediate predecessors/successors by tracking predecessors/successors on the projected logstream on the Nearest-Neighbor group of the template, and stitching the mined successors of each template to construct the desired control flow graph.

9. The method of claim 8, wherein the plurality of execution logs comprises raw log lines.

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

comparing the created control flow graph to at least one previously stored control flow graph;

identifying, based on said comparing, at least one anomaly; and

wherein the at least one identified anomaly is selected from the group consisting of;

a sequence anomaly and a distribution anomaly.

11. The method according to claim 8, wherein said mining comprises utilizing at least one text-clustering technique selected from the group consisting of:

an edit-distance technique and a dictionary-based logline parameterization.

12. The method according to claim 11, wherein the dictionary-based logline parameterization comprises identifying keywords and parameters for each of the plurality of execution logs.

13. The method according to claim 12, wherein said identifying comprises employing a frequency analysis of words for each of the plurality of execution logs.