JP7761155B2 - Causal model construction device, causal model construction method, and program - Google Patents

Description

The present disclosure relates to a causal model construction device , a causal model construction method , and a program.

For ICT (Information and Communication Technology) providers, it is important to understand the status of abnormalities that occur within ICT systems and to respond quickly to them. In this context, research has been conducted on methods for early detection of abnormalities that occur within ICT systems and methods for estimating the location of abnormalities.

One method proposed for estimating abnormal locations is to use a Bayesian network to model the relationship between the abnormal location and the changes in data (hereinafter also referred to as "observation data") within the ICT system caused by that abnormality as a causal model, and then estimate the abnormal location from the observation data at the time of the abnormality (Non-Patent Documents 1-3). These methods can be categorized as either rule-based or data-driven.

The rule-based approach is a modeling method that follows predefined rules. The rule-based approach primarily uses the knowledge of experts, such as ICT system operators, to model the relationship between abnormal locations and changes in observed data. For example, in Non-Patent Document 1, a rule is created from expert knowledge that states that the normality or abnormality of a router only affects the observed data of adjacent links, and a causal model is constructed using this rule and the adjacent relationships in the ICT system's network topology. Furthermore, Non-Patent Document 2 proposes making it easier to construct causal models by creating abstract rules known as templates.

Data-driven methods are methods of modeling from data. In data-driven methods, observed data from past anomalies is used to model the relationship between the location of the anomaly and changes in the observed data at that time. For example, in Non-Patent Document 3, the relationship between a certain failure and data from multiple past cases is modeled.

Methods for estimating abnormal locations use syslogs and traffic information from ICT systems. However, in recent years, it has become easier to obtain a variety of types of observational data in addition to syslogs and traffic information, such as flow data, telemetry data, and sensor data related to communications equipment. Therefore, it is believed that using these various types of observational data will enable the estimation of abnormal locations with finer granularity.

Srikanth Kandula, Dina Katabi, and Jean-philippe Vasseur. Shrink: A tool for failure diagnosis in IP networks. Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, pages 173-178, 2005. He Yan, Lee Breslau, Zihui Ge, Dan Massey, Dan Pei, and Jennifer Yates. G-RCA: A Generic Root Cause Analysis Platform for Service Quality Management in Large IP Networks. IEEE/ACM Transactions on Networking, 20(6):1734-1747, 2012. Kandula, Srikanth and Mahajan, Ratul and Verkaik, Patrick and Agarwal, Sharad and Padhye, Jitendra and Bahl, Paramvir. Detailed diagnosis in enterprise networks. ACM SIGCOMM Computer Communication Review, vol.39, num.4, pp.243-254, 2009.

However, when constructing a causal model using diverse types of observational data, the following challenges arise:

Challenge 1: Rule-based methods require expert knowledge in advance for modeling, but the number of types of observational data used in conventional technology is very small.In addition, abnormalities that occur in ICT systems have a ripple effect and affect various types of observational data, making it difficult to create rules for each and every relationship between abnormalities that occur in ICT systems and the various types of observational data.

Issue 2: When various types of observational data are input into a Bayesian network, it is necessary to determine whether the value of each piece of observational data obtained from an ICT system is normal or abnormal (this is also known as binarization). Conventional technology deals with a very small number of types of observational data, and is designed for observational data that is easy to binarize (for example, alert information indicating whether an alert has occurred). However, when various types of observational data are input, the normal range for each piece of observational data has its own characteristics, making it difficult to binarize it while taking these into account.

Challenge 3: Data-driven methods require observational data from past anomalies, but anomalies generally do not occur frequently in ICT systems. Furthermore, as the types of observational data become more diverse, the number of patterns that the observational data can take for anomalies increases. For this reason, it is generally difficult to collect enough anomaly cases to compensate for this increase.

Issue 4: Furthermore, in recent years, ICT system virtualization technology has led to increasingly frequent changes in the network topology of ICT systems. Consequently, the observational data acquired from ICT systems also changes frequently. For this reason, it is difficult to create rules for the relationship between anomalies and observational data one by one using rule-based methods, and it is difficult to collect sufficient anomaly cases using data-driven methods.

This disclosure has been made in consideration of the above points and aims to provide a technology that can construct a causal model from network topology information when building a causal model for various types of observation data.

A causal model construction device according to one aspect of the present disclosure includes a collection unit configured to acquire network topology information representing the network topology of an ICT system for which an abnormality location is to be estimated, and a model construction unit configured to use the network topology information to construct a causal model for estimating the abnormality location from observation data when an abnormality occurs in the ICT system.

When building causal models for various types of observational data, technology is provided that can build causal models from network topology information.

FIG. 1 is a diagram illustrating an example of a hardware configuration of an abnormality location estimation device according to an embodiment of the present invention. FIG. 2 is a diagram illustrating an example of a functional configuration of an abnormality location estimation device according to the present embodiment. 10 is a flowchart illustrating an example of a causal model construction process according to the present embodiment. 10 is a flowchart illustrating an example of an abnormality location estimation process according to the present embodiment.

An embodiment of the present invention will now be described. In the following embodiment, an anomaly location estimation device 10 will be described that constructs a causal model from network topology information of an ICT system and uses this causal model to estimate anomaly locations in the ICT system from various types of observation data. The anomaly location estimation device 10 of this embodiment has a "model construction phase" in which a causal model is constructed from network topology information of the ICT system, and an "anomaly location estimation phase" in which this causal model is used to estimate anomaly locations from observation data at the time of an anomaly occurrence. The anomaly location estimation device 10 in the model construction phase may be referred to as, for example, a "model construction device." Network topology information is information that represents the network topology of an ICT system. Network topology information is, for example, information that represents a graph structure in which various devices (e.g., routers, servers, etc.) that make up the ICT system are represented as nodes and communication paths between the nodes are represented as links.

<Theoretical structure>
First, the theoretical configuration of the causal model construction in the model construction phase and the abnormality location estimation in the abnormality location estimation phase will be described.

Let i∈{1,...,N} denote the devices that make up the ICT system for which a causal model is constructed and anomaly locations are to be identified, and let x _i ∈{0,1} denote the state of device i. Here, N represents the number of devices, and x _i = 0 indicates a normal state and 1 indicates an abnormal state.

Furthermore, let the observed data be j∈{1, ..., M}, and the state of the observed data j be y _j ∈{0, 1}. Here, M represents the number of observed data, and y _j represents a normal state when it is 0 and an abnormal state when it is 1. Note that examples of the observed data j include various data that can be obtained from devices that make up the ICT system (e.g., syslog, traffic information, flow data, telemetry data, sensor data, etc.).

A representative node kε{1, ..., N} is introduced for each device i, and the state of representative node k is defined as r _k ε{0, 1}, where r _k is 0 when it represents a normal state and 1 when it represents an abnormal state.

It should be noted that x _i , y _j and r _k may not be binary, 0 or 1, but may be multi-valued, ternary or more.

Each device i has one representative node k. Representative node k is a node that represents the state of observation data that can be obtained from the corresponding device i. The state r _k of representative node k is determined based on the contribution of the observation data to an anomaly (described later). In this embodiment, a causal model of r _k that represents the state of observation data that can be obtained from device i that corresponds to state x _i (that is, a causal model related to the state r _k of representative node k) is constructed.

Below, we will explain how to construct a causal model and how to estimate the location of an anomaly, and then explain how to determine the contribution to the anomaly and the state of the representative node.

- Method for constructing a causal model and method for estimating anomaly locations A causal model is constructed by specifying the prior probability P(X = _x1 , ..., _xN | α) and the conditional probability P(R = _r1 , ..., _rN | X, β, φ). The prior probability is the probability that each device is likely to enter an abnormal state, and is specified as follows:

Here, α is a hyperparameter that indicates the likelihood of the device going into an abnormal state, and takes a value between 0 and 1.

Next, conditional probability is defined. Conditional probability represents the causal relationship between a device and a representative node and its degree. Furthermore, when a certain device i has a causal relationship with a certain representative node k, the causal relationship is expressed by adding an edge e _i,k between x _i and r _k . Here, the causal relationship between device X and representative node R is defined as follows using network topology information:

Here, neig(i) is a set of indices of nodes adjacent to device i.

Then, if the set of all edges between device X and representative node R is E and the parameter representing the index of edge e _i,k is φ _i,k , then the following holds:

In this case, the conditional probability is defined as follows using φ _i,k :

Here, β is a hyperparameter that indicates the degree of causality and takes a value between 0 and 1. Also, δ(·) is a delta function that returns 1 when the input is true and 0 when it is false.

Finally, given the state of the representative node, the anomaly location is estimated by solving the following using the prior probability and conditional probability:

The above equation can be solved, for example, by belief propagation (Reference 1). In the text of this specification, the estimated result of the abnormality location will be represented as "^X".

As described above, causal models can be constructed for various types of observed data using only network topology information.

Method for Determining the Contribution to an Anomaly and the State of a Representative Node Next, a method for determining the contribution to an anomaly and the representative node will be described. Let c be an M-dimensional vector, and each vector element _cj represents the contribution of observation data j to the anomaly. Here, the contribution to an anomaly is a value that represents the extent to which each observation data item contributes to the anomaly. Therefore, observation data acquired from devices closer to an abnormal device will have a higher contribution than observation data acquired from devices farther from the abnormal device. In this way, by using the contribution as an input rather than directly using the observation data value, it is possible to assume that an abnormal device only affects the observation data acquired from its nearby devices. Furthermore, because the contribution to an anomaly represents the extent to which each observation data item contributes to the anomaly, there is no need to consider the diversity of the characteristics of each observation data item, and it is possible to set the binarization threshold based solely on the magnitude of the contribution.

The contribution to anomalies can be calculated by applying the methods described in, for example, References 3 and 4 to an AutoEncoder (Reference 2) trained using M-dimensional normal observation data.

For example, let the loss function used in training the AutoEncoder be L(v) = ∥v - ^v∥. Here, v is the input to the AutoEncoder, and ^v is the output from the AutoEncoder. In this case, the contribution c can be calculated as c = argmin _γ L(v + γ) + λ|γ|. Here, λ is a preset constant. This means finding a γ that reduces the value of L(v) (i.e., reduces the degree of anomaly). This is because the found γ is considered to reduce the degree of anomaly, that is, to contribute to anomalies. Note that the second term in the above equation for calculating the contribution c is a penalty term to ensure that γ satisfies sparsity.

Next, a method for determining the state of the representative node will be described. Let _Ds be a set of the top s values, sorted in descending order by the absolute value of each element of the contribution c to the anomaly. Here, the value of s can be determined arbitrarily, but it could be, for example, the integer part of 1% of the number M of types of observed data. Then, let _Ωs be a set of element numbers of elements of c that correspond to the values included in _Ds . That is, let _Ωs = {j|| _cj | _∈Ds }.

Then, the state r _k of the representative node is determined by the following equation.

Here, f is a function that returns a set of indices of observation data acquired from device k.

That is, f(k) is calculated for each kε{1, . . . , N}, and if at least one element of Ω _s is included in the index set representing the calculation result, r _k =1; otherwise, r _k =0.

<Example of hardware configuration of abnormality location estimation device 10>
An example of the hardware configuration of an abnormality location estimation device 10 according to this embodiment is shown in Fig. 1. As shown in Fig. 1, the abnormality location estimation device 10 according to this embodiment includes an input device 101, a display device 102, an external I/F 103, a communication I/F 104, a random access memory (RAM) 105, a read only memory (ROM) 106, an auxiliary storage device 107, and a processor 108. These pieces of hardware are connected to each other via a bus 109 so as to be able to communicate with each other.

The input device 101 is, for example, a keyboard, a mouse, a touch panel, a physical button, etc. The display device 102 is, for example, a display, a display panel, etc. Note that the abnormality location estimation device 10 does not necessarily have to have at least one of the input device 101 and the display device 102.

The external I/F 103 is an interface with external devices such as a recording medium 103a. The abnormality location estimation device 10 can read and write data from and to the recording medium 103a via the external I/F 103. Examples of the recording medium 103a include a flexible disk, a CD (Compact Disc), a DVD (Digital Versatile Disk), an SD memory card (Secure Digital memory card), and a USB (Universal Serial Bus) memory card.

The communication I/F 104 is an interface for connecting the anomaly location estimation device 10 to a communication network. The RAM 105 is a volatile semiconductor memory (storage device) that temporarily stores programs and data. The ROM 106 is a non-volatile semiconductor memory (storage device) that can store programs and data even when the power is turned off. The auxiliary storage device 107 is a storage device (storage device) such as an HDD (Hard Disk Drive), SSD (Solid State Drive), or flash memory. The processor 108 is an arithmetic device such as a CPU (Central Processing Unit) or GPU (Graphics Processing Unit).

The anomaly location estimation device 10 according to this embodiment has the hardware configuration shown in FIG. 1, and is therefore capable of performing the causal model construction process and the anomaly location estimation process described below. Note that the hardware configuration shown in FIG. 1 is merely an example, and the hardware configuration of the anomaly location estimation device 10 is not limited to this. For example, the anomaly location estimation device 10 may have multiple auxiliary storage devices 107 or multiple processors 108, may not have some of the hardware shown in the figure, or may have various hardware components other than the hardware shown in the figure.

<Example of functional configuration of abnormality location estimation device 10>
An example of the functional configuration of the anomaly location estimation device 10 according to this embodiment is shown in Fig. 2. As shown in Fig. 2, the anomaly location estimation device 10 according to this embodiment includes a collection unit 201, a causal model construction unit 202, a contribution degree calculation unit 203, an estimation unit 204, and a user interface unit 205. Each of these units is realized, for example, by processing in which one or more programs installed in the anomaly location estimation device 10 are executed by the processor 108 or the like. The anomaly location estimation device 10 according to this embodiment also includes an ICT system data DB 301, a causal model DB 302, and a contribution degree DB 303. Each of these DBs is realized, for example, by the auxiliary storage device 107 or the like.

The collection unit 201 collects network topology information and each observation data j from the ICT system. The network topology information and each observation data j collected by the collection unit 201 are stored in the ICT system data DB 301.

The causal model construction unit 202 constructs a causal model (i.e., the prior probability P(X= _x1 , ..., _xN |α) shown in the above equation 1 and the conditional probability P(R= _r1 , ..., _rN |X, β, φ) shown in the above equation 4) using network topology information stored in the ICT system data DB 301. The causal model constructed by the causal model construction unit 202 is stored in the causal model DB 302.

When estimating the location of an anomaly, the contribution calculation unit 203 calculates the contribution c to the anomaly using each observation data j stored in the ICT system data DB 301. The contribution c calculated by the contribution calculation unit 203 is stored in the contribution DB 303.

The estimation unit 204 estimates the abnormality location ^X using the causal model stored in the causal model DB 302 and the contribution c stored in the contribution DB 303. That is, the estimation unit 204 determines the state r _k of the representative node k from the contribution c, and then estimates the abnormality location ^X according to the above equation 5 using the state r _k of the representative node k.

The user interface unit 205 presents the abnormality location ^X estimated by the estimation unit 204 to a user (e.g., an operator of an ICT system).

<Causal model construction process>
The causal model construction process according to this embodiment will be described below with reference to Fig. 3. The causal model construction process is a process executed in the model construction phase. In the following, it is assumed that the network topology information collected by the collection unit 201 is stored in the ICT system data DB 301.

The causal model construction unit 202 inputs network topology information stored in the ICT system data DB 301 (step S101).

Next, the causal model construction unit 202 constructs a causal model (the prior probability P(X = _x1 , ..., _xN | α) shown in the above equation 1 and the conditional probability P(R = _r1 , ..., _rN | X, β, φ) shown in the above equation 4) using the network topology information input in the above step S101 (step S102).

Then, the causal model construction unit 202 stores the causal model constructed in step S102 above in the causal model DB 302 (step S103).

<Abnormal location estimation process>
The abnormality location estimation process according to this embodiment will be described below with reference to Fig. 4. The abnormality location estimation process is executed in the abnormality location estimation phase. In the following, it is assumed that some abnormality has occurred in the ICT system, and that each piece of observation data j at that time has been collected by the collection unit 201 and stored in the ICT system data DB 301.

The contribution calculation unit 203 inputs each observation data j at the time the abnormality occurred (step S201).

Next, the contribution calculation unit 203 calculates the contribution c to the anomaly using each piece of observation data j input in step S201 (step S202). That is, the contribution calculation unit 203 calculates the contribution c by c = argmin _γ L(v + γ) + λ|γ|, where L(v) = ∥v - ^v∥ is the loss function used in learning the AutoEncoder, for example.

Next, the contribution calculation unit 203 stores the contribution c calculated in step S202 above in the contribution DB 303 (step S203).

Next, the estimation unit 204 estimates the abnormality location ^X using the causal model stored in the causal model DB 302 and the contribution c stored in the contribution DB 303 (step S204). That is, the estimation unit 204 determines the state r _k of the representative node k from the contribution c using the above equation 6, and then estimates the abnormality location ^X using the above equation 5 using the state r _k of the representative node k.

Then, the user interface unit 205 outputs the abnormal location ^X estimated in step S204 above to a display device 102 such as a display and presents it to the user (step S205).

<Summary>
As described above, in the model construction phase, the anomaly location estimation device 10 according to this embodiment constructs a causal model (Bayesian network) for the state r _k of the representative node k using only network topology information under the assumption that "when an abnormality occurs in a certain device, it will affect the observation data of that device and its adjacent devices." Furthermore, in the anomaly location estimation phase, the anomaly location estimation device 10 according to this embodiment can estimate the anomaly location through the causal model (Bayesian network) using the contribution c calculated from each piece of observation data j at the time of the anomaly occurrence. As a result, the anomaly location estimation device 10 according to this embodiment can solve the above problems 1 to 4.

In other words, the anomaly location estimation device 10 according to this embodiment solves problem 1, that "anomalies spread and affect various types of observation data," by using data called "contribution to the anomaly," and solves problem 1, that "it is difficult to create rules for the relationships between anomalies and various types of observation data one by one," by introducing a node called a representative node into the Bayesian network.

In addition, by using data called "contribution to anomalies," there is no need to consider the normal state of each observation data j; it is possible to binarize based solely on the magnitude of the contribution value, thereby resolving problem 2. Furthermore, problem 4 is resolved because a causal model can be constructed from network topology information alone, and problem 3 is not an issue because past anomaly data is not used.

As a result, the anomaly location estimation device 10 of this embodiment solves the above-mentioned problems 1 to 4 and makes it possible to estimate anomaly locations in an ICT system using a causal model for various types of observation data that can be obtained from the ICT system.

The present invention is not limited to the specifically disclosed embodiments above, and various modifications, alterations, and combinations with known technologies are possible without departing from the scope of the claims.

[References]
Reference 1: Kazuyuki Tanaka, [Tutorial Lecture] Fundamentals of Probabilistic Information Processing and Belief Propagation Algorithms, IEICE Technical Report, 2004.
Reference 2: M. Sakurada and T. Yairi, "Anomaly detection using autoencoders with nonlinear dimensionality reduction," in Proc. MLSDA, ser. MLSDA'14, 2014, p. 4-11.
Reference 3: Y. Ikeda, K. Tajiri, Y. Nakano, K. Watanabe, and K. Ishibashi, "Estimation of contributing dimensions to detected anomalies with variational autoencoders," arXiv preprint arXiv:1811.04576, 2018.
Reference 4: Scott Lundberg, Su-In Lee, "A Unified Approach to Interpreting Model Predictions," in Proc. NIPS 2017.

10 Abnormality location estimation device 101 Input device 102 Display device 103 External I/F
103a Recording medium 104 Communication I/F
105 RAM
106 ROM
107 Auxiliary storage device 108 Processor 109 Bus 201 Collection unit 202 Causal model construction unit 203 Contribution calculation unit 204 Estimation unit 205 User interface unit 301 ICT system data DB
302 Causal Model DB
303 Contribution DB

Claims (3)

a collection unit configured to acquire network topology information representing a network topology of an ICT system in which an abnormality location is to be estimated;
a model construction unit configured to construct a causal model for estimating the location of an anomaly from observation data when an anomaly occurs in the ICT system, using the network topology information; and
and
The model construction unit
A causal model construction device configured to construct a Bayesian network as the causal model, which is defined by a priori probability representing the likelihood of an equipment constituting the ICT system falling into an abnormal state, and a conditional probability representing the causal relationship between the equipment and the state of a representative node representing the state of the observation data obtained from the equipment, and the degree of the causal relationship. a collection procedure for acquiring network topology information representing the network topology of an ICT system in which an anomaly location is to be estimated;
a model construction step of constructing a causal model for estimating the location of an anomaly from observation data when an anomaly occurs in the ICT system, using the network topology information;
The computer executes
The model building procedure includes:
A causal model construction method in which a Bayesian network is constructed as the causal model, which is defined by a priori probability representing the likelihood of an equipment constituting the ICT system falling into an abnormal state, and a conditional probability representing the causal relationship between the equipment and the state of a representative node representing the state of the observation data obtained from the equipment, and the degree of the causal relationship. A program for causing a computer to execute the causal model building method according to claim 2 .