Detecting anomalous events through runtime verification of software execution using a behavioral model

• US 10,152,596 B2
• Filed: 01/19/2016
• Issued: 12/11/2018
• Est. Priority Date: 01/19/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Pieczul, Olgierd S.
• Primary Examiner(s): Pham, Luu T
• Assistant Examiner(s): Wilcox, James J
• Application Number:
  US15/000,192
• Publication Number:
  US 20170206354A1
• Time in Patent Office: 1,057 Days
• CPC Class Codes: G06F 21/554 involving event detection and direct action
• CPC Class Codes: G06F 21/566 Dynamic detection, i.e. detection performed at run-time, e.g. emulation, suspicious activities
• CPC Class Codes: G06F 2221/033 Test or assess software
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence

Abstract

Runtime verification of software execution events against a behavioral model. For each event, it is verified whether there is a short range correlation of a sequence of the event and preceding event(s) with the behavioral model, and whether there is a long range correlation of a group of the sequences and of an arrangement of groups of the sequences with the behavioral model. After verifying each long range correlation, the arrangement of groups in the behavioral model event is substituted with an intersection of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model. If an event is not covered by a short range correlation or a long range correlation of a group or a long range correlation of an arrangement of groups, the event is indicated as anomalous.

Claims

1. A method comprising:

for each event of a software execution comprising events;

verifying whether the event is covered by a short range correlation of a sequence of the event and one or more events preceding the event with a sequence of two or more events in a behavioral model that comprises one or more n-grams of acceptable short range correlations of a sequence of two or more of the events, one or more groups of acceptable combinations of n-grams, and one or more group arrangements of acceptable combinations of groups;

verifying whether the event is covered by a long range correlation of a group of the sequences with a group of the sequences in the behavioral model;

verifying whether the event is covered by a long range correlation of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model;

after verifying each long range correlation, substituting the arrangement of groups of the sequences in the behavioral model event with an intersection of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model; and

responsive to the event not being covered by at least one of;

the short range correlation, the long range correlation of a group of the sequences, or the long range correlation of an arrangement of groups, indicating that the event is anomalous and halting software execution before execution of the indicated anomalous event.

2. The method of claim 1, wherein the short range correlation of a sequence of events utilizes tri-grams generated from the sequence of events.

3. The method of claim 1, wherein the short range correlation of a sequence of events utilizes tri-grams and bi-grams.

4. A system comprising:

one or more computer processors;

one or more computer-readable storage media;

a system log stored on the one or more computer-readable storage media for recording events generated by a software execution;

a behavioral model, stored on the one or more computer-readable storage media comprising one or more n-grams of acceptable short range correlations of a sequence of two or more events, one or more groups of acceptable combinations of n-grams, and one or more group arrangements of acceptable combinations of groups;

a short range event correlator module, stored on the one or more computer-readable storage media which, when executed by the one or more processors;

verifies whether each event is covered by a short range correlation of a sequence of the event and one or more events preceding the event with a sequence of two or more events in the behavioral model; and

responsive to the event not being covered by a short range correlation, indicates that the event is anomalous, and halts software execution before execution of the indicated anomalous event;

a long range correlator module, stored on the one or more computer-readable storage media which, when executed by the one or more processors;

verifies whether each event is covered by one or more of a long range correlation of;

a group of the sequences with a group of the sequences in the behavioral model;

or an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model; and

responsive to the event not being covered by at least one of the long range correlations, indicates that the event is anomalous, and halts software execution before execution of the indicated anomalous event; and

a transaction arrangement substitutor module, stored on the one or more computer-readable storage media which, when executed by the one or more processors, substitutes, after verifying a long range correlation, the arrangement of groups of the sequences in the behavioral model event with an intersection of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model.

5. The system of claim 4, wherein the short range correlation of a sequence of events utilizes tri-grams generated from the sequence of events.

6. The system of claim 4, wherein the short range correlation of a sequence of events utilizes tri-grams and bi-grams.

7. A computer program product comprising:

a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to;

for each event of a software execution comprising events;

verify whether the event is covered by a short range correlation of a sequence of the event and one or more events preceding the event with a sequence of two or more events in the behavioral model that comprises one or more n-grams of acceptable short range correlations of a sequence of two or more of the events, one or more groups of acceptable combinations of n-grams, and one or more group arrangements of acceptable combinations of groups;

verify whether the event is covered by a long range correlation of a group of the sequences with a group of the sequences in the behavioral model;

verify whether the event is covered by a long range correlation of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model;

after verifying each long range correlation, substituting the arrangement of groups of the sequences in the behavioral model event with an intersection of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model; and

responsive to the event not being covered by at least one of;

the short range correlation, the long range correlation of a group of the sequences, or the long range correlation of an arrangement of groups, indicating that the event is anomalous and halting software execution before execution of the indicated anomalous event.

8. The computer program product of claim 7, wherein the short range correlation of a sequence of events utilizes tri-grams generated from the sequence of events.

9. The computer program product of claim 7, wherein the short range correlation of a sequence of events utilizes tri-grams and bi-grams.

10. A computer system comprising:

one or more computer processors, one or more computer-readable storage media, and program instructions stored on one or more of the computer-readable storage media for execution by at least one of the one or more processors, the stored program instructions comprising;

program instructions, for each event of a software execution comprising events, to;

verify whether the event is covered by a short range correlation of a sequence of the event and one or more events preceding the event with a sequence of two or more events in a behavioral model that comprises one or more n-grams of acceptable short range correlations of a sequence of two or more of the events, one or more groups of acceptable combinations of n-grams, and one or more group arrangements of acceptable combinations of groups;

verify whether the event is covered by a long range correlation of a group of the sequences with a group of the sequences in the behavioral model;

verify whether the event is covered by a long range correlation of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model;

after verifying each long range correlation, substituting the arrangement of groups of the sequences in the behavioral model event with an intersection of an arrangement of groups of the sequences with an arrangement of groups of the sequences in the behavioral model; and

responsive to the event not being covered by at least one of;

the short range correlation, the long range correlation of a group of the sequences, or the long range correlation of an arrangement of groups, indicating that the event is anomalous and halting software execution before execution of the indicated anomalous event.

11. The computer system of claim 10, wherein the stored program instructions for short range correlation of a sequence of events utilize tri-grams generated from the sequence of events.

12. The computer system of claim 10, wherein the stored program instructions for short range correlation of a sequence of events utilize tri-grams and bi-grams.