Fault localization in distributed systems using invariant relationships

• US 9,026,855 B2
• Filed: 07/25/2013
• Issued: 05/05/2015
• Est. Priority Date: 07/26/2012
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Sharma, Abhishek, Chen, Haifeng, Ding, Min, Yoshihira, Kenji, Jiang, Guofei
• Primary Examiner(s): LE, DIEU MINH T
• Application Number:
  US13/950,523
• Publication Number:
  US 20140047279A1
• Time in Patent Office: 649 Days
• Field of Search: 714/37, 714/4.1
• US Class Current: 714/37
• 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/079 Root cause analysis, i.e. error or fault diagnosis in a hardware test environment G06F11/22; in a software test environment G06F11/36
• CPC Class Codes: H04L 41/064 involving time analysis
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 43/0817 by checking functioning

Abstract

A computer implemented method for temporal ranking in invariant networks includes considering an invariant network and a set of broken invariants in the invariant network, assuming, for each time point inside a window W, that each metric with broken invariants is affected by a fault at that time point, computing an expected pattern for each invariant of a metric with assumed fault, said pattern indicative of time points at which an invariant will be broken given that its associated metric was affected by a fault at time t, comparing the expected pattern with the pattern observed over the time window W; and determining a temporal score based on a match from the prior comparing.

Claims

1. A computer implemented method for temporal ranking in invariant networks comprising the steps of:

considering an invariant network and a set of broken invariants in the invariant network;

assuming, for each time point inside a window W, that each metric with broken invariants is affected by a fault at that time point;

computing an expected pattern for each invariant of a metric with assumed fault, said pattern indicative of time points at which an invariant will be broken given that its associated metric was affected by a fault at time t;

comparing the expected pattern with the pattern observed over the time window W; and

determining a temporal score based on a match from the prior comparing, said determining comprises, based on observations up to a current time T, selecting an interval of length w, [T−

w, T], such that an anomaly at any tε

[T−

w, T] can cause a broken invariant at T and using an ARX model setting w=arg max(n, m+k).

2. The method of claim 1, wherein said determining comprises computing an anomaly score assuming that all broken invariants at time t are due to anomalies affecting their corresponding metrics.

3. The method of claim 2, wherein said determining comprises calculating the anomaly score for t as the sum of the score for each metric with broken invariants at time t.

4. The method of claim 3, wherein said determining comprises computing the score for a metric based on a match between expected and observed broken invariant pattern, wherein an overall anomaly score for a time t indicates support for an anomaly occurring at this time while the score for a metric denotes how likely it is abnormal.

5. The method of claim 1, wherein said determining comprises localizing faults in time and ranking abnormal metrics, a time score computation to support that an anomaly occurred at time t, and assuming anomalies happened at time t, assigning a score to a metric m based on the match between an expected temporal pattern of broken invariants and an observed pattern.

6. The method of claim 5, wherein said localizing faults in time and ranking abnormal risks comprises the following steps:

receiving a set of all invariants I, list of broken invariants Lt at each time point tε

[T−

w, T], T;

current time

for all tε

[T−

w, T], do anomalyScore[t]=timeScore(t, T, {Lj;

j2[t, T]}); and

raise alarms for time points t with high anomaly score;

at each of these time points focusing on metrics with high scores for further investigation.

7. The method of claim 5, wherein said time score computation comprises the following steps:

receiving lists of broken invariants {Lj;

j2[t, T]}, set of all invariants I, current time T;

outputting an anomaly score for time t;

for all metric m with broken invariants in Lt, doing score[m]=metricScore(m, {Lj;

j 2[t, T]}, I); and

determining an anomaly Score_t from Σ

m score[m].

8. The method of claim 5, wherein said assigning a score to a metric m includes the following steps:

receiving metric m, set of all invariants I, and list of broken invariants {L_j;

jε

[t, T];

outputting a score for metric m;

initializing a metricScore[m] to 0;

initializing an expectedmetricScore[m] to zero; and

recursively determining metricScore[m] from metricScore[m] divided by expectedMetricScore[m].