18.2.1 Rule-Based Approaches

This class of root cause analysis approaches uses rules to capture the domain knowledge of the monitored IT environment. Such rules are typically of the form <If symptoms then diagnosis>, where symptoms are mapped to root causes. This set of rules is built manually by interviewing system administrators, or automatically by using machine learning methods applied on past data. To find the root cause of an incident, the set of rules is evaluated for matching symptoms. When the conditions of a rule are satisfied, the rule is triggered and a conclusion for the root cause of the failure is derived.

In general, the drawback of the rule-based root cause analysis approaches is that it is hard to have a comprehensive set of rules that cover all the possible cases. Furthermore, the overhead work needed before these approaches can be used in practice is not trivial and requires there to be updating for new incidents. In our work we use goal models to represent cause-effect relationships at a higher level of abstraction, as well as probabilistic rules so that reasoning can be performed with partial or incomplete log data.

18.2.2 Probabilistic Approaches

Traditional root cause analysis techniques assume that interdependencies between system components are fully known a priori and that log information about the monitored system’s state is complete for all diagnostic purposes. Probabilistic approaches aim to model the cause and effect relationships between IT components using probabilities to represent the possible effect of one component on another. An example of using the probabilistic approach is the work of Steinder et al. [9]. They used Bayesian networks to represent dependencies between communication systems and diagnose failures while using dynamic, missing, or inaccurate information about the system structure and state.

Another example is the approach of Al-Mamory et al. [10], who used a history of alarms and resolutions in order to improve future root cause analysis. In particular, they used root cause analysis to reduce the large number of alarms by finding the root causes of false alarms. The approach uses data mining to group similar alarms into generalized alarms and then analyzes these generalized alarms and classifies them into true and false alarms.

18.2.3 Model-Based Approaches

This class of root cause analysis techniques aims at compiling a model representing the normal behavior of the system, and detecting anomalies when the monitored behavior does not adhere to the model. Such models denoting the normal behavior of a system can take various forms. One form is to associate design decisions and components with functional and nonfunctional system properties. For example, these associations can be represented by goal models, antigoal models, or i*-diagrams. A system that uses model-driven engineering combined with run-time information for facilitating root cause analysis is presented in Ref. [11]. More specifically, models denoting system behavior and structure are used to annotate the source code at design time. At run time, logged data are compared with design-time models in order to infer possible root causes. Similarly, a model-based approach facilitating root cause analysis for business process compliance is presented in Ref. [12]. The system allows the specification of models denoting business processes, as well as constraints on/policies for these processes. A run-time monitoring infrastructure allows the collection of system events that are consequently analyzed against the constraints and the policies in the model repository. The analysis yields possible violations, as well as the causes of these violations. Linear temporal logic models were used in Ref. [13] to represent business process compliance constraints in complex service-oriented systems. Symptoms are associated with causes by utilizing current reality trees. An analysis engine allows the current reality trees to be traversed when a symptom is observed, evaluate whether a constraint is violated, and establish possible causes of this violation. Another example of model-based approaches is given in Ref. [7], and is based on the propositional satisfaction of system properties using SAT solvers. Given a propositional formula f, the propositional satisfiability (SAT) problem consists in finding values for the variables of the propositional formula that can make an overall propositional formula evaluate to true. The propositional formula is said to be true if such a truth assignment exists. In Ref. [7] effects (i.e., symptoms or requirement violations) are linked to causes using goal trees. Consequently, goal trees are transformed to propositional formulas. The objective of root cause analysis when a symptom is observed is to identify which combination of goal nodes (i.e., causes) could support or explain the observed violation. One way of solving this problem is by utilizing SAT solvers applied in the logic formula that stems from the goal tree.

Goal models are tree structures that can be used to represent and denote the conditions and the constraints under which functional and nonfunctional requirements of a system can be delivered. In these structures, internal nodes represent goals, while external nodes (i.e., leafs) represent tasks. Edges between nodes represent either AND or OR goal decompositions or contributions.

The AND decomposition of a goal G into other goals or tasks C₁, C₂, …, C_n implies that the satisfaction of each of G’s children is necessary for the decomposed goal to be fulfilled. The OR decomposition of a goal G into other goals or tasks C₁, C₂, …, C_n implies that the satisfaction of one of these goals or tasks suffices for the satisfaction of the parent goal. In Figure 18.3, we show goals g₁ and g₃ as examples of AND and OR decompositions.

In addition to AND/OR decompositions, two goals may be connected by a contribution edge. A goal may potentially contribute to other goals in four ways—namely, ++S, −−S, ++D and −−D. In this chapter, we adopt the semantics of Chopra et al. [14] for the interpretations of contributions:

$\begin{array}{ll}\hfill ++S/D:& g_s\text{satisfaction/denial implies}{g}_t\hfill \\ \hfill & \mathit{satisfaction}/\mathit{denial},\hfill \\ \hfill --S/D:& g_s\text{satisfaction/denial implies}{g}_t\hfill \\ \hfill & \mathit{denial}/\mathit{satisfaction}.\hfill \end{array}$

18.4.2 Antigoal Models

Similarly to goal models, antigoal models represent the goals and actions of an external agent with the intention to threaten or compromise specific system goals. Antigoal models are also denoted as AND/OR trees built through systematic refinement, until leaf nodes (i.e., tasks) are derived. More specifically, leaf nodes represent tasks (actions) an external agent can perform to fulfill an antigoal, and consequently through the satisfaction of this antigoal to deny a system goal. In this respect, root cause analysis can commence by considering root causes not only due to internal system faults but also due to external actions. Antigoal models were initially proposed by Lamsweerde et al. [15] to model security concerns during requirements elicitation.

An example of antigoal models is the trees with roots ag₁ and ag₂, depicted in Figure 18.3, where the target edges from antigoal ag₁ to tasks a₂ and a₃ as well as from antigoal ag₂ to tasks a₄ and a₆ model the negative impact an antigoal has on a system goal.

18.4.3 Model Annotations

Since a generic goal model is only an abstract description of cause and effect relationships, it is not sufficient on its own to capture whether goals are satisfied on the basis of input from the collected log data. For this reason, we consider three annotations per goal or task node: precondition, postcondition, and occurrence annotations. Precondition annotations denote the structure and contents the log data must have at a particular (logical) time instant for the goal or task be considered for evaluation. Occurrence annotations denote the structure and contents the log data must have at a particular (logical) time instant for the goal to be considered potentially satisfiable. Similarly, postcondition annotations denote the structure and contents the log data must have at a particular (logical) time instant for the goal to be tagged as satisfied. The order of logical time instants and the logical relationship between preconditions, occurrence and postconditions for a given goal or task are presented in Equations 18.9-18.12 for goal models, and Equations 18.17 and 18.18 for antigoal models.

Goal and task node annotations pertaining to preconditions, occurrence, and postconditions take the form of expressions as discussed in Section 18.7.1.2 and illustrated in Equation 18.10. Figure 18.3 depicts an example of annotating goal model nodes with precondition, postcondition, and occurrence expressions. Once goal and antigoal models have been formulated and annotated, they are consequently transformed into collections of Markov logic rules in order to form a diagnostic knowledge base, as will be discussed in the following sections.

In addition to assisting in inferring whether a goal or action node is satisfied, annotations serve as a means for reducing, through information retrieval approaches, the volume of the logs to be considered for the satisfaction of any given node, increasing the overall root cause analysis processing performance. Logs are filtered on a per goal node basis using the metadata annotation information in each node. Log reduction uses LSI and is discussed in more detail in Section 18.5. Other approaches to log reduction that are based on information theory were proposed in Ref. [16]. The reduced logs that are obtained from the running system are also transformed to collections of facts, forming a fact base of observations. The rule base stemming from the goal and antigoal models and the facts stemming from the observed log files form a complete knowledge base to be used for root cause analysis reasoning. Root cause analysis reasoning uses a probabilistic rule engine that is based on the Alchemy tool [17]. In the following sections we discuss in more detail log filtering, reasoning fundamentals using Markov logic, and the application of the framework used for root cause analysis for (a) failures that occur because of internal system errors and (b) failures that occur as a result of external actions.

18.4.4 Loan Application Scenario

Throughout this chapter, as a running example to better illustrate the inner workings of the proposed root cause analysis technique, we use example goal and antigoal models pertaining to a loan application scenario as depicted in Figure 18.3. The scenario is built on a test environment that is composed of a set of COTS application components. As depicted in Figure 18.4, the experimentation environment includes a business process layer and a service-oriented infrastructure. In particular, this test environment includes four subsystems: the front-end application (SoapUI), a middleware message broker, a credit check service, and a database server.

We have built the Apply_For_Loan business service, specifying the process of an online user applying for a loan, having the loan application evaluated, and finally obtaining an accept/reject decision based on the information supplied. Technically, the business process is exposed as a Web service. The Apply_For_Loan service starts when it receives a SOAP request containing loan application information. It evaluates the loan request by checking the applicant’s credit rating. If the applicant’s credit rating is “good,” his/her loan application is accepted and a positive reply is sent to the applicant. Otherwise, a loan rejection result is sent to the applicant. If an error occurs during processing, a SOAP fault is sent to the requesting application. The credit rating evaluation is performed via a separate Web service (Credit_Rating). After the credit evaluation terminates, the Credit_Rating service sends a SOAP reply to the calling application containing the credit rating and the ID of the applicant. If an error occurs during the credit evaluation, a SOAP error is sent to the requesting application. During the credit rating evaluation, the Credit_Rating application queries a database table and stores/retrieves the applicants’ details.

18.5.1 Latent Semantic Indexing

Some of the well-known document retrieval techniques include LSI [18], PLSI [19], latent Dirichlet allocation [20], and the correlated topic model [21]. In this context, semantic analysis of a corpus of documents consists in building structures that identify concepts from this corpus of documents without any prior semantic understanding of the documents.

LSI is an indexing and retrieval method to identify relationships among terms and concepts in a collection of unstructured text documents. LSI was introduced by Deerwester et al. [18]. It takes a vector space representation of documents based on term frequencies as a starting point and applies a dimension reduction operation on the corresponding term/document matrix using the singular value decomposition algorithm [22]. The fundamental idea is that documents and terms can be mapped to a reduced representation in the so-called latent semantic space. Similarities among documents and queries can be more efficiently estimated in this reduced space representation than in their original representation. This is because two documents which have terms that have been found to frequently co-occur in the collection of all documents will have a similar representation in the reduced space representation, even if these two specific documents have no terms in common. LSI is commonly used in areas such as Web retrieval, document indexing [23], and feature identification [24]. In this context, we consider each log entry as a document. The terms found in the goal and antigoal node annotation expressions become the search keywords. LSI is then used to identify those log entries that are mostly associated with a particular query denoting a system feature, a precondition, an occurrence, or a postcondition annotation of a goal or antigoal node.

18.5.2 Probabilistic Latent Semantic Indexing

PLSI is a variation of LSI [19] that considers the existence of three types of random variables (topic, word, and document). The three types of class variables are as follows:

(1) An unobserved class variable z ∈ Z = {z₁,z₁,...z_K} that represents a topic

(2) Word w ∈ W = {w₁,w₂,...w_L}, where each word is the location of a term t from the vocabulary V in a document d

(3) Document d ∈ D = {d₁,d₂,...d_M} in a corpus M

PLSI aims to identify the documents d_i in a collection of documents {d₁, d₂, .., d_j} that best relate to a word w (or words), presented as query—that is, to compute P(d_i,w). The major difference of PLSI from LSI is that its model is based on three layers—namely, the documents layer, the latent topics layer, and the words (i.e., query) layer. Each document d_i is associated with one or more concepts c_k (i.e., a latent variable). Similarly, each word is also associated with a concept. The overall objective is to compute the conditional probabilities P(c_k|d_i) and P(w|c_k). By computing the inner product of P(w|c_k) and P(d_i|c_k) over latent variables c_k for each document d in the collection of documents separately, as the “similarity” score between the query w and a document d_i, we can then select the documents that produce the maximum score. Such documents are considered as the most relevant to the query.

18.6.1 Markov Logic Networks

MLNs were recently proposed in the research literature as a framework that combines first-order logic and probabilistic reasoning. In this context, a knowledge base denoted by first-order logic formulas represents a set of hard constraints on the set of possible worlds (i.e., if a world violates one formula, it has zero probability of existing). Markov logic softens these constraints by making a word that violates a formula be less probable, but still possible. The more formulas it violates, the less probable it becomes. A detailed discussion on MLNs can be found in Ref. [25].

Markov network construction. In MLNs, each logic formula F_i is associated with a nonnegative real-valued weight w_i. Every grounding (instantiation) of F_i is given the same weight w_i. In this context, a Markov network is an undirected graph that is built by an exhaustive grounding of the predicates and formulas as follows:

• Each node corresponds to a ground atom x_k which is an instantiation of a predicate.

• If a subset of ground atoms x_{i} = {x_k} are related to each other by a formula F_i with weight w_i, then a clique C_i over these variables is added to the network. C_i is associated with a weight w_i and a feature function f_i defined as follows:

$\begin{array}{l}\hfill f_i(x_{\{i\}})=\left\{\begin{array}{cc}1& F_i(x\{i\})=\mathrm{true},\\ 0& \mathrm{otherwise}.\\ \end{array}\right.\end{array}$

Thus, first-order logic formulas serve as templates to construct the Markov network. In the context of a Markov network, each ground atom, X, represents a binary variable. The overall Markov network is then used to model the joint distribution of all ground atoms. The corresponding global energy function can be calculated as follows:

$\begin{array}{l}\hfill P(X=x)=\frac{1}{Z}exp\left(\sum _i{w}_i{f}_i(x_{\{i\}})\right),\end{array}$

where Z is the normalizing factor calculated as

$\begin{array}{l}\hfill Z=\sum _{x\in X}exp\left(\sum _i{w}_i{f}_i(x_{\{i\}})\right),\end{array}$

where i denotes the subset of ground atoms x_{i}∈ X that are related to each other by a formula F_i with weight w_i and feature function f_i.

Learning. Learning in an MLN consists of two steps: structure learning, or learning the logical clauses, and weight learning, or determining the weight of each logical clause. Structure learning is typically done by heuristically searching the space for models that have a statistical score measure that fits the training data [17]. As for weight learning, Singla et al. [26] extended the existing voted perceptron method and applies it to generate the MLN’s parameters (weights for the logical clauses). This is done by optimizing the conditional likelihood of the query atoms given the evidence.

Inference, Assuming ϕ_i(x_{i}) is the potential function defined over a clique C_i, then $log({\varphi }_i(x_{\{i\}}))=w_i{f}_i(x_{\{i\}})$. We use the Markov network constructed to compute the marginal distribution of events. Given some observations, probabilistic inference can be performed. Exact inference is often intractable, and thus Markov chain Monte Carlo sampling techniques, such as Gibbs sampling, are used for approximate reasoning [25]. The probability for an atom X_i given its Markov blanket (neighbors) B_i is calculated as follows:

$\begin{array}{l}\hfill P(X_i=x_i/B_i=b_i)=\frac{A}{(B+C)},\end{array}$

where

$\begin{array}{l}\hfill A=exp\left(\sum _{f_j\in F_i}{w}_j{f}_j(X_i=x_i,B_i=b_i)\right),\\ \hfill \end{array}$

$\begin{array}{l}\hfill B=exp\left(\sum _{f_j\in F_i}{w}_j{f}_j(X_i=0,B_i=b_i)\right),\\ \hfill \end{array}$

$\begin{array}{l}\hfill C=exp\left(\sum _{f_j\in F_i}{w}_j{f}_j(X_i=1,B_i=b_i)\right).\\ \hfill \end{array}$

F_i is the set of all cliques that contain X_i, and f_j is computed as in Equation 18.2.

The Markov network is used to compute the marginal distribution of events and perform inference. Because inference in Markov networks is #P-complete, approximate inference is proposed to be performed using the Markov chain Monte Carlo method and Gibbs sampling [27].

As already mentioned, the above expressions are used to compute the probability an atom X (i.e., an instantiated predicate in one of the logic formulas stemming from the goal models) belongs to a clique in the Markov network. Intuitively, this probability gives the likelihood this atom is satisfied in the “world” represented by the clique. As an example, consider the first-order logic formula $A\wedge B\to C$. If we have atoms A and B, then we can infer C exists. But if we consider that we have seen a “world” where B and C coexist on their own in 40% of cases without A, then even in the absence of observing A, we can still deduce C exists with a degree of likelihood if we observe B alone without A. In the sections below, we elaborate more on the use of probabilistic reasoning for root cause analysis for failures due to internal system errors or due to external maliciously induced actions.

18.7.1 Knowledge Representation

In the following sections, we discuss in more detail the steps pertaining to modeling a diagnostic knowledge base from a collection of goal models.

18.7.1.5 Generation of ground atoms from filtered system logs

There are two inputs to this process: first, the log data stored in a common database, and second, the goal model for the monitored system with precondition, postcondition, and occurrence patterns annotating each node of the model. The output is a totally timestep-ordered set of literals (ground atoms) of the form literal(node,timestep).

The framework uses pattern expressions that annotate the goal models and applies these annotations as queries to the log data in order to extract evidence for the occurrence of events associated with each goal model node. More specifically, once the logged data have been stored in a unified format, the pattern expressions that annotate the goal and antigoal model nodes (see Figure 18.3) can be used, first, to generate LSI queries that are applied to collect a subset of the logged data pertaining to the analysis and, second, as patterns to satisfy Pre, Occ, and Post predicates for a node. An example of a log data pattern matching expression for the precondition of goal g₁ in Figure 18.3 is shown below:

The truth assignment for the extensional predicates is performed on the basis of the pattern matched log data. We show below a sample subset of the ground atoms for the goal model in Figure 18.3:

pre(g₁,1), pre(a₁,1), occ(a₁,2), post(a₁,3), pre(g₂,3), !pre(a₃,3), ?occ(a₃,4), …, ?post(g₁,15), !satisfied(g₁,15)

The set of literals above represents the observation of one failed loan application session. However, for some of the goals/tasks, there may be no Pre, Occ, or Post supporting evidence, which can be interpreted as either they did not occur, or they were missed from the observation set. We model this uncertainty by adding a question mark (?) before the corresponding ground atoms. In cases where there is evidence that a goal/task did not occur, the corresponding ground atom is preceded by an exclamation mark (!). For example, in Figure 18.3 the observation of the system failure is represented by !satisfied(g₁,15), which indicates top goal g₁ denial, at timestep 15. Note that in the above example, the precondition for task a₃ was denied and the occurrence of a₃ was not observed, leading to the denial of task a₃, which led to goal g₂ not occurring and thus being denied. In turn, the denial of goal g₂ supports goal g₁ not being satisfied.

The filtering of the predicate with timesteps of interest is performed in two steps. First, a list of literals is generated (see the example above) from the nodes annotations (preconditions, occurrences, and postconditions) by depth-first traversing the goal model tree. In the second step, literals are used to initiate searches in the logged data set looking for events containing such literals (and within a certain time interval). The following is an example of the generation of ground atoms. A log entry of the form

(2010-02-05 17:46:44.24 Starting up database eventsDB ... DATABASE)

that matches the pattern of the precondition of goal g₁ represents evidence for the satisfaction of the precondition of g₁. For other logical literals that do not have supporting evidence in the log data that their preconditions, postconditions, or occurrence expressions are matched, a question mark is assigned to these literals. Such a case is illustrated in the precondition of of a₇ (Occ(a₇,5)) in Table 18.2

Table 18.2

Four Scenarios for the Loan Application

Scenario	Observed (& missing) events	Satisfied (a1,3)	Satisfied (a3,5)	Satisfied (a6,7)	Satisfied (a7,9)	Satisfied (a4,11)	Satisfied (a5,13)	Satisfied (a2,15)
1. Successful execution	Pre(g1,1), Pre(a1,1), Occ(a1,2), Post(a1,3), Pre(g2,3), Pre(a3,3), Occ(a3,4), Post(a3,5), Pre(g2,5), Pre(a6,5), Occ(a6,6), Post(a6,7), ?Pre(a7,5), ?Occ(a7,6), ?Post(a7,7), Post(g3,7), Pre(a4,7), Occ(a4,8), Post(a4,9), Pre(a5,9), Occ(a5,10), Post(a5,11), Pre(a2,11), Occ(a2,12), Post(a2,13), Post(g1,13), Satisfied(g1,13)	0.99	0.99	0.99	0.49	0.99	0.99	0.99
2. Failed to update loan database	Pre(g1,1), Pre(a1,1), Occ(a1,2), Post(a1,3), Pre(g2,3), Pre(a3,3), Occ(a3,4), Post(a3,5), Pre(g3,5), Pre(a6,5), Occ(a6,6), Post(a6,7), ?Pre(a7,5), ?Occ(a7,6), ?Post(a7,7), Post(g3,7), Pre(a4,7), ?Occ(a4,8), ?Post(a4,9), ?Pre(a5,9), ?Occ(a5,10), ?Post(a5,11), ?Pre(a2,11), ?Occ(a2,12), ?Post(a2,13), ?Post(g1,13), !Satisfied(g1,13)	0.99	0.99	0.99	0.43	0.45	0.45	0.36
3. Credit database table not accessible	Pre(g1,1), Pre(a1,1), Occ(a1,2), Post(a1,3), Pre(g2,3), Pre(a3,3), Occ(a3,4), Post(a3,5), Pre(g2,5), ?Pre(a6,5), ?Occ(a6,6), ?Post(a6,7), ?Pre(a7,5), ?Occ(a7,6), ?Post(a7,7), Post(g3,7), Pre(a4,7), Occ(a4,8), Post(a4,9), Pre(a5,9), Occ(a5,10), Post(a5,11), Pre(a2,11), Occ(a2,12), Post(a2,12), ?Post(g1,13), !Satisfied(g1,13)	0.99	0.99	0.33	0.32	0.45	0.43	0.38
4. Failed to validate loan application Web service request	?Pre(g1,1), Pre(a1,1), ?Occ(a1,2), ?Post(a1,3), Pre(g2,3), ?Pre(a3,3), ?Occ(a3,4), ?Post(a3,5), Pre(g3,5), Pre(a6,5), ?Occ(a6,6), ?Post(a6,7), Pre(a7,5), ?Occ(a7,6), ?Post(a7,7), ?Post(g3,7), Pre(a4,7), ?Occ(a4,8), ?Post(a4,9), ?Pre(a5,9), ?Occ(a5,10), ?Post(a5,11), ?Pre(a2,11), ?Occ(a2,12), ?Post(a2,13), ?Post(g1,13), !Satisfied(g1,13)	0.48	0.48	0.35	0.36	0.47	0.48	0.46

for scenario 1.

The ground atom generation process is further illustrated through the examples in Figures 18.5 and in 18.6.

18.7.2 Diagnosis

In this section the details of the diagnosis phase are presented in more detail. This phase aims to generate a Markov network based on goal model relationships as described in Section 18.7.1 and then uses the system events obtained to proceed with an inference of the possible root causes of the observed system failure.

18.7.2.1 Markov network construction

In this context, an MLN is constructed using the rules and predicates as discussed in Section 18.6.1. The grounding of the predicates comes from all possible literal values obtained from the log files. For example, in Figure 18.7 the ground predicate t4Connect_to_Credit_Database(DB1), where DB1 is a specific database server, becomes true if there exists a corresponding logged event denoting that there is such a connection to DB1. The Markov network then is a graph of nodes and edges where nodes are grounded predicates and edges connect two grounded predicates if these coexist in a grounded logic formula. Weights w_i are associated with each possible grounding of a logic formula in the knowledge base [17].

18.8.1 Antigoal Model Rules

Here, the goal model rules are similar to the rules applied to detect internal errors and described in Section 18.7.1.4.

As is the case with goal models, antigoal models also consist of AND/OR decompositions; therefore antigoal model relationships with their child nodes are represented using the same first-order logic expressions as for goal models (Equations 18.11 and 18.12). The satisfaction of tasks (leaf nodes) in antigoal models follows the same rule as in Equation 18.9. The satisfaction of antigoals is expressed using the truth assignment of the Satisfied(node) predicates, which in turn is inferred as follows:

$\begin{array}{ll}\hfill & Pre(a{g}_1,t_1)\wedge Occ(a{g}_1,t_2)\wedge Post(a{g}_1,t_3)\Rightarrow \hfill \\ \hfill & Satisfied(a{g}_1,t_3)\hfill \end{array}$

The satisfaction of an antigoal ag_i at timestep t₁ presents a negative impact on the satisfaction of a target task a_j at timestep t₁ + 1.

$\begin{array}{ll}\hfill & Satisfied(a{g}_i,t_1)\wedge Targets(a{g}_i,a_j)\Rightarrow \hfill \\ \hfill & !Satisfied(a_j,t_1+1)\hfill \end{array}$

The outcome of this process is a set of ordered ground atoms that are used in the subsequent inference phase as the dynamic part of the system observation.

18.8.2 Inference

The flowchart in Figure 18.10 represents the process of root cause analysis for failures due to externally induced errors. This process starts when an alarm is raised indicating a system failure, and terminates when a list of root causes of the observed failure is identified. For the diagnostic reasoning process to proceed, we consider that the annotated goal/antigoal models for the monitored systems and their corresponding Markov networks and logical predicates have been generated as described earlier in the chapter. The diagnostic reasoning process is composed of seven steps as discussed in detail below:

Step 1: The investigation starts when an alarm is raised or when the system administrator observes the failure of the monitored service, which is the denial of a goal g.

Step 2: On the basis of the knowledge base, which consists of all goal models and all observations (filtered log data and visual observation of the failure of the monitored service), the framework constructs a Markov network, which in turn is applied to generate a probability distribution for all the Satisfied(node, timestep) predicates for all nodes in the goal tree rooted at the denied goal g and the nodes of all other trees connected to it. This probability distribution is used to indicate the satisfaction or denial of tasks and goals at every timestep in the observation period. More specifically, if the probability of satisfaction of a task a_i at a timestep t is higher than a threshold value thrs, then we conclude that a_i is satisfied at t—that is, Satisfied(a_i, t). Typically the timestep t starts at 0, and thrs is chosen to be 0.5.
An example of the outcome of this step is as follows based on Figure 18.9:

$\left\{\begin{array}{c}Satisfied(a_1,3):0.36\\ Satisfied(a_3,7):0.45\\ \end{array}\right.$

Step 3: The outcome of the previous step is a ranked list of denied tasks/goals, where the first task represents the node that is most likely to be the cause of the failure. In step 3, the framework iterates through the denied list of tasks identified in step 2, and loads the antigoal models targeting each of the denied tasks.

Step 4: For each antigoal model selected in step 3, we generate the observation literals from the log data by applying the ground atom generation process described in Section 18.7.1.5. Note that a task may have zero, one, or multiple antigoal models targeting it. The goal model in Figure 18.9 contains task a₂, which has no antigoal models targeting it, task a₁, which has one antigoal (ag₁) targeting it, and task a₃, which has two antigoals (ag₃ and ag₅) targeting it.

Step 5: This step is similar to step 2, but instead of evaluating a goal model, the framework evaluates the antigoal model identified in step 4 using the log-data-based observation and determines wether the top antigoal is satisfied. This is done by constructing a Markov network based on the antigoal model relationships (see Section 18.8.1) and inferring the probability distribution for the Satisfied(antigoal, timestep) predicate for the nodes in the antigoal model. In particular, we are interested in the probability assigned to Satisfied(ag_j, t) where t represents the timestep at which ag_j is expected to finish. Using the example in Figure 18.9, we see ag₁ takes 11 steps to complete execution, while ag₃ takes seven steps. In this case, we are interested in Satisfied(ag₁,11) and Satisfied(ag₂,7).

Step 6: On the basis of the value of Satisfied(ag_j, t) identified in step 5, we distinguish the following two cases:

(a) If Satisfied(ag_j, t) ≥ thrs (typically thrs = 0.5), this indicates that ag_j is likely to have occurred and caused a_i to be denied. In this case, we add this information (antigoal and its relationship with the denied task) to the knowledge base. This knowledge base enrichment is done at two levels: first, a new observation is added to indicate that antigoal ag_j has occurred, and second, a rule is added on the basis of the pattern in Equation 18.18.

(b) If Satisfied(ag_j, t) < thrs, this indicates that ag_j did not occur; thus we exclude it as a potential cause of failure for a_i.

Before going to next step, the framework checks whether the denied task a_i is targeted by any other antigoal models. If it is, it iterates through the list of other antigoals ag_j that are targeting a_i by going back to step 4. Once all antigoals targeting a denied task a_i have been evaluated, the framework checks whether there are more denied tasks, and if there are, it repeats step 2.

Step 7: On the basis of the new knowledge acquired from evaluating the antigoal models, the satisfaction of tasks based on the enriched knowledge base is reevaluated to produce a new ranking of the denied tasks. The fact that an attack is likely to have occurred targeting a specific task that has failed increases the chances that this task is actually denied because of the intrusion, leading to the overall system failure. This overall process helps improve the diagnosis, but also provides interpretation for the denial of tasks.

18.9.1 Detecting Root Causes due to Internal Faults

The first case study consists of a set of scenarios conducted using the loan application service. These scenarios are conducted from the perspective of the system administrator, where a system failure is reported, and a root cause investigation is triggered.

The normal execution scenario for the system starts with the receipt of a loan application in the form of a Web service request. The loan applicant’s information is extracted and used to build another request, which is sent to a credit evaluation Web service as illustrated in Figure 18.3.

The four scenarios in this study include one success and three failure scenarios (see Table 18.2). Scenario 1 represents a successful execution of the loan application process. Tthe denial of task a₇ does not represent a failure in the process execution, since goal g₃ is OR-decomposed into a₆ (extract credit history for existing clients) and a₇ (calculate credit history for new clients), and the successful execution of either a₆ or a₇ is enough for g₃’s successful occurrence (see Figure 18.3). The probability values (weights) of the ground atoms range from 0 (denied) to 1 (satisfied). During each loan evaluation, and before the reply is sent to the requesting application, a copy of the decision is stored in a local table (a₄ (update loan table)). Scenario 2 represents a failure to update the loan table leading to failure of top goal g₁. Next, as described in Section 18.7.2.3, we identify a₄ as the root cause of the failure. Note that although a₇ was denied ahead of task a₄, it is not the root cause since it is an OR child of g₃, and its sibling task a₆ was satisfied. Similarly, for scenario 3, we identify task a₆ as the root cause of the failure. Scenario 4 represents the failure to validate Web service requests for the loan application. Almost no events are observed in this scenario. Using the diagnosis logic described in Section 18.7.2.3, we identify task a₁ (receive loan application Web service request) as the root cause of the observed failure.

18.9.2 Detecting Root Causes due to External Actions

In this case study, we consider failures of the loan application scenario due to externally induced errors. As in the case of failures due to internal actions, we consider that the logs have the same format and the results are presented to the administrator in the same way—that is, in the form of lists of goal or antigoal nodes that correspond to problems that may be responsible (i.e., causes) for the observed failure. Each node is associated with a probability as this is computed by the reasoning engine as discussed in previous sections.

The experiment is conducted from the perspective of the system administrator, where a system failure is reported and an investigation is triggered. This case study scenario consists in running an attack while executing the credit history service (see the goal model of the credit service in Figure 18.7). The antigoal ag₁ is executed by probing the active ports on the targeted machine, and then the attacker attempts to log in but uses a very long username (16,000 characters), disrupting the service authentication process, and denying legitimate users from accessing the service. Traces of this attack can be obtained in the Windows Event Viewer.

The antigoal ag₂ models an SQL injection attack that aims at dropping the table containing the credit scores. One way to implement such an attack is to send two subsequent legitimate credit history Web service requests that contain embedded malicious SQL code within a data value. For example, to implement this malicious scenario, we embed an SQL command to scan and list all the tables in the data value of the field ID as follows:

$\begin{array}{l}\hfill <ID>12345;selectfromSYSOBJECTSwhereTYPE{=}^{\prime }{U}^{\prime }orderbyNAME</ID>\end{array}$

The system extracts the credential data value (e.g., ID) and uses it to query the database, thus inadvertently executing the malicious code. The scan is followed by a second Web Service request that contains a command to drop the Credit_History table:

$<ID>12345;DropTableCredit\_History</ID>$

Traces of the credit service sessions are found in the SQL Server audit log data and in the message broker (hosting the credit service). The first antigoal ag₁ represents the attacker’s plan to deny access to the credit service by keeping busy the port used by that service. The second antigoal ag₂ aims at injecting an SQL statement that destroys the credit history data.

18.9.3 Performance Evaluation

The third experiment is an evaluation of the processing performance of the framework. We used a set of extended goal models representing the loan application goal model to evaluate the performance of the framework when larger goal models are used. The four extended goal models contained 10, 50, 80, and 100 nodes, respectively. This experiment was conducted using Ubuntu Linux running on an Intel Pentium 2 Duo 2.2 GHz machine. From the experiments conducted, we observed that the matching and ground atom generation performance depends linearly on the size of the corresponding goal model and log data, and thus led us to believe that the process can easily scale for larger and more complex goal models. In particular, we are interested in measuring the impact of larger goal models on the learning and inference aspects of the framework.

Figure 18.11 illustrates that the number of ground atoms/clauses, which directly impacts the size of the resulting Markov model, is linearly proportional to the goal model size. Figure 18.12 illustrates that the running time for the off-line learning of the rule weights increases linearly with the size of the goal model. The learning time ranged from slightly over 10 min for a goal model with 10 nodes, to over 2 h for a model with 100 nodes. The inference time ranged from 5 s for a goal model with 10 nodes to 53 s for a model with 100 nodes. As the initial results indicate, this approach can be considered for applications with sizeable logs, entailing the use of small to medium-sized diagnostic models (approximately 100 nodes).