Diagnosis of Communicating Systems: Dealing with Incompleteness and Uncertainty

1 Introduction

Problem: One of Hamacher's modelling principles states, "A sequential circuit should be encapsulated into a single component to enable the description of its be­ havior in a temporally coarse way" (1991]. This princi­ ple addresses tractability and is especially appropriate for cases where encapsulated components: form a single replaceable unit ; have a relatively simple external inter­ face; or have input/output behaviour similar to a combi­ national device when viewed in a temporally coarse way (as in Hamacher's example). However, for distributed systems and complex state machines, such encapsulation may not be appropriate and high-level abstraction may offer insufficient detail for diagnosis. The approach pro­ posed here deals with the internal behaviour of complex agents allowing more detailed analysis, but must also ad­ dress the tractability problems incurred. The approach is intended for distributed discrete systems where mod­ els of communication, or protocols, between agents are at least partially available, such as for developing (debug­ ging, conformance testing) or managing (troubleshoot­ ing) tele- and data-communication networks.

·The Swiss PTT provided funding as part of ESPRIT II project #2409 EQUATOR, Environment for Qualitative Temporal Reasoning.

1 Agents a.re protocol executing entities tha.t , together with links, form a. distributed system. This is more general tha.n the network ma.na.gement meaning of "a.gentsn .

Diagnosis of systems with state has been the sub­ ject of much recent investigation, but most attention has been devoted to simple sequential circuits or so­ called physical systems. Although the flexibility, reliabil­ ity and device-independe.nce of model-based approaches are very desirable for the diagnosis of distributed dis­ crete systems, this problem has been addressed by few researchers. Expanding size and power of communica­ tion networks and rising user dependence make network diagnosis an increasingly difficult yet important problem. Error manifestations may be distributed physically and temporally. For example, an agent may incorrectly inter­ pret a request directed to itself and erroneously broad­ cast the request to its neighbours, possibly resulting in a fatal chain reaction. Protocol functioning can not be guaranteed to be error-free because design verification and implementation validation techniques are still lim­ ited, and exhaustive testing of non-trivial implementa­ tions is practically impossible. A protocol may pass con­ formance tests and yet only state "Reason not specified" in all error messages [CCI, 1989, 13.5.3, 13.12.3]. Fur­ thermore, a specified reason may not be correct . New, previously unexperienced problems - for which model­ based diagnosis is particularly useful - arise as compo­ nents are added to the network, are reconfigured, or are revised, such as with new software releases.

Observation of such systems is often incomplete and uncertain. Incompleteness arises because: state may evolve too quickly for detailed real-time diagnosis; dis­ tributed agents may generate too many events for com­ plete storage; internal probing may be inaccessible; and testing may be slow, difficult, or impossible. Uncertainty arises because: observers are distributed and may be erroneous; observed event types may be generated by several agents in various states; observed (external} and actual (internal) event sequences may differ; and univer­ sally synchronous timing cannot be assumed.

Approach: This paper attempts to address the above problems by proposing a model-based algorithm for in­ terpreting observations and diagnosis. A set of observa­ tions OBS is collected from logs of sensors distributed amongst the agents of the system to be diagnosed. For example, an agent could be a protocol executing en­ tity of a network and an observation could be a mes­ sage time-stamped by an external sensor, as in Figure 1. The model, called the system description SD, includes

(possibly extended) finite-state machine (FSM) rules or constraints modelling agent communication behaviour. Initially, each observation is propagated forward in SD to determine the set of externally observable events, called propagations, that could have followed it in the next state of the model. Propagations of one observa­ tion are matched to other, temporally relevant obser­ vations and their propagations having similar message types and overlapping temporal intervals to find a pos­ sible explanation i.e. that one observation predicts the other. Matched observation pairs are used to determine the best possible interpretations of the sequence of tran­ sitions that explain OBS collectively. Weaknesses of ex­ planation in the interpretations are used to suggest sets of constraints in SD that could be modified to form vari­ ants S D; . The algorithm then iterates on these variants to find the best interpretations of OBS. Thus, iterative modification of the base model is performed in order to search for better matchings. The sets of constraints mod­ ified in order to form the models that generate the best interpretations are used to propose plausible diagnoses.

Contributions: The main contribution of this pa­ per is a novel approach to interpreting and diagnos­ ing distributed discrete agents of non-trivial complex­ ity, in which observations may be incomplete and un­ certain. Standard approaches, such as lde Kleer and Williams, 1987], process all conflicts together in a re­ finement loop and make strong assumptions about ob­ servation availability and certainty when resolving con­ flicts . The HMDP algorithm is derived from this, but addresses the problem domain as follows: internal ac­ cess for observation is assumed to be limited; cost of testing or probing is taken into account; incremental and temporal propagation reduce search; intermediate prop­ agations can fill substantial observation gaps; evaluation of matches and interpretations is based on probabilities and heuristics; the algorithm focuses on finding good in­ terpretations of OBS as a whole in order to resolve con­ flicts and to find plausible candidates; reiteration allows focusing on a small number of conflicts at any time; and optional operator interaction improves focussing. As a second contribution, the paper proposes a flexible and device-independent technique applicable to the impor­ tant task of diagnosing communication protocols.

The following section gives an example problem. The algorithm is then described in detail and applied to the example. Next, issues and related work are dis­ cussed. The ~onclusion briefly discusses an implemen­ tation of a TP4 model [CCI, 1989], current status, and ideas for future investigation. This presentation is con­ cise due to space limitations; a more detailed report is available from the author.

2 ABP Example

The Alternating Bit Protocol (ABP) is one of the sim­ plest communication protocols [Bartlett et al., 1969]. It describes how a Sender and a Replier agent interact to transfer data messages from the former to the lat­ ter. The Sender appends a 1-bit to send a data mes­ sage, awaits an acknowledgement having the same bit from the Replier, sends the next message with a O-bit, and so on. After transmitting a message with a 1-bit, the Sender must either: (I) receive an acknowledgement with a 1-bit; {2) time-out and resend the message with a 1-bit; or {3) receive and ignore redundant acknowl­ edgements having a O-bit. The Replier functions in a complementary manner. A simplification of the ABP is illustrated in Figure 2, where vertex labels correspond to state names, edges to transitions, and edge labels to input {1,0), output {l,O), or internal events (time-outs). Initial states are in bold. In order to represent timing

behaviour, some temporal specifications must be added. For the example, assume that each time-out is set to eight time units 2 . The HMDP algorithm is applied be­ low to the following example problem: given this model and a set of observations, find a specific implementa­ tion error, namely that the time-out transition between states S3 and S4, denoted S4-S3, is set to one time unit instead of eight.

3 The HMDP Algorithm

Brief Overview: In practice, diagnosis is triggered by an operator or an automated monitor, optionally offering rough approximations of the relevant temporal interval and the physical locality of one or more error manifesta­ tions. An initial set OBS is collected from a log and pos­ sibly by probing the Implementation Under Test (IUT, the system diagnosed) . The trigger and OBS are used to determine which entities in the IUT are included in COM PS, the set of components being diagnosed (agents and their components) . Each observation 0; is initially propagated forward through SD. This generates a sub­ set of the propagations that could have immediately fol­ lowed 0; according to the model. Each propagation po, is compared to temporally relevant observations and their propagations. If po, and some observation Oj have similar message types and overlapping temporal inter­ vals, then the pair (0;, Oj) forms a match. This match indicates that the state transitions used for the propaga­ tion give a possible explanation that 0; predicts Oj . A likeliness value is evaluated for each match. Incremen­ tal deepening of propagations is performed selectively. Once all matches have been determined, they can be represented as a directed graph Gsn whose vertices are the members of OBS and whose edges are matches. In­ terpretation! of OBS with respect to any agent can be evaluated by finding acyclic paths in Gsn - If the IUT is faulty, the best interpretations of G sn in the first iteration offer imperfect explanations. The al­ gorithm must determine which constraints in SD may be associated with the weak areas of interpretations ofGsn, possibly due to a specific conflict between the model and the implementation. Sets of constraints are mod­ ified in order to generate variants of SD. The algorithm then loops, propagating OBS through one variant SD; in each iteration to find better interpretations and hence better explanations. Sets of modified constraints corre­ sponding to models having the best interpretations are used to propose plausible diagnoses.

1 More precisely, aasume that: timing is synchronous; Sender and Replier timing parameters a.re equal; external observers time-stamp messages; total transmission and prop­ a.ga.tion time between the a.gents is one time unit; a.nd pro­ cessing time for a.ny sta.te is between zero (plus epsilon) and five time units.

Propagation: The goal of propagation is to find ex­ ternally observable events that could have been received or transmitted by a given state machine before or after a given observation. This is done by searching transition paths extending to and from a starting transition corre­ sponding to the given observation until an observable is found at each path searched. Observables immediately preceding or following a given observation are its pri­ mary propagations, having a depth of one. Secondary propagations go one level deeper and so on. Tables of propagations of transitions can be calculated in advance, allowing near-linear propagation time during diagnosis. Forward propagation corresponds to predicting observ­ ables occurring after the observation, assuming that the starting transition is correct; propagating backward cor­ responds to abductive hypothesis of observables occur­ ring beforehand. Only forward primary propagations are found initially. Observations that subsequently receive poor matching evaluations have not predicted, or are not predicted by, other observations with sufficient plau­ sibility. Propagation of these observations is deepened by incrementing propagation in the direction of match­ ing weakness (forward or backward). Since observations may be aberrant, incremental deepening is only repeated a small number of times.

If not given, rough transition probabilities and tran­ sition times can often be estimated in advance and par­ tially refined by statistical analysis of IUT performance or simulation. Probability estimates are based on heuris­ tics (e.g. time-out are less probable than normal tran­ sitions) and statistical analysis. Timing estimates are based on the function of a transition (e.g. send internal message), on heuristics (e.g. normal processing times may be estimated from timing constraints), or on code execution estimates. Propagation requires estimating time intervals extended from the time associated with the original observation. Time labels must be normalised with respect to the agent being diagnosed.

Consider the propagations in Figure 3, based on ob­ serving a Sender of the ABP protocol 3 . Timing is indi­ cated relative to the Sender. Observation (S 0 20), a

Sender output message having a O-bit observed at time 20, is propagated through the transition constraints of SD to derive primary propagations. Five transitions in Figure 2 correspond to a message with a O-bit se­ quence number originating from the Sender: S3-+ S4, R3-+ R4, R1-+ R1, R2-+ R2, and R4-+ R4. This is the set of agent-tran6ition pairs related to the observation (S 0 20). Consider propagation from transition S3-+S4. The backward propagation (R 1 15-20), labelled a in Figure 3, indicates that, between times 15 and 20 rel­ ative to the Sender, the Replier could have generated a message having a 1-bit in acknowledgement to a previ­ ous Sender message. Forward propagation (R 0 22-27), labelled b, corresponds to a Replier acknowledgement of the observation.

For diagnosis of simple circuits, the signal observed at an input terminal can be precisely correlated to the input parameter of a constraint, and the result of prop­ agation can be correlated to observation of output ter­ minals. In the problem domain treated here, observers are external and cannot measure "terminals" of a tran­ sition, so the correspondence between observations and transitions must be hypothesised using agent-transition pairs, incremental propagation, and matching.

Matching: The goal of matching is to evaluate if, how, and how well each propagation of an observation 0; can be matched to members of OBST ~ OBS \ {0;} and their propagations. With each observation is associated an overall interval T indicating the earliest and latest end-points of the intervals of all of its propagations. Be­ fore propagations are matched, intervals based on T are compared and only overlapping pairs are matched.

Matches are found by comparing messages and time intervals of propagations and observations. Match eval­ uation is initially based on the probabilities of the tran­ sition(s) of related propagations. Consider an example with observations (S 0 20) and (S 1 23) and their prop­ agations as shown in Figure 3. Here, forward propaga­ tion (R 0 22-27), labelled b, and backward propagation

3 For lack of space, some inessential details on probabili­ ties, timing, a.nd less likely propagations involving redundant acknowledgements are not given here.

(R 0 18-23), labelled e, have the same source agent (the Replier) , the same sequence number (zero), and overlap­ ping time intervals. (When data corruption is suspected, such as from a sensor or a transmission link, close but imperfect pattern matches can be retained with lower evaluations.) Because interval estimates widen rapidly as propagation depth increases, the evaluation is divided by a value based on the depth of propagation needed to relate one observation to another. Thus, intermediate missing observations can be hypothesised at the cost of lower evaluation.

Interpretation: The generated matches of SD can be represented as the weighted edges of a directed graph Gsv whose vertices are the members of OBS. An ex­ ample Gsv is summarised on the left of Figure 4, where propagation (R 0 *) is shown explicitly, rather than as part of several edges. Interpretations of OBS are gen­ erated by finding distinct, acyclic paths in Gsv using a heuristic traversal algorithm. For example, if each mem­ ber of OBS predicts exactly one member occurring after it and is predicted by exactly one occurring before it, the interpretation could represent a partial simulation of an agent. Interpretations are evaluated by several factors such as the sum of individual match evaluations, the number of members of OBS included, and the number and lengths of paths. Thus an interpretation can exclude erroneous observations and yet retain a good ranking.

Reiteration: For the first iteration of the main loop, which uses SD, even the best interpretations generated are likely to have imperfect evaluations because SD does not explain observations of the faulty JUT. Information on specific weaknesses of the interpretation of G sD, such as excluded observations or low match evaluations, is used to determine a set C of sets of constraints C; related to poor explanations. With each constraint c; ,j E C; is associated a primitive modification operation m; ,j . Sev­ eral primitive modification operations are related to each type of constraint (and parameters for extended mod­ els) . For example, a state-transition constraint can be modified by a suspension operation (or other operations as in [Bouloutas, 1990]), and a parameter can be set to extrema or qualitatively distinct values (ex. buffer empty, buffer not-empty, buffer full). Once the set C has been initialised at the end of the first iteration, each subsequent iteration i uses C; to determine the model SD; used for propagation, and may add new elements to C. For example, if C1 consists of one transition con­ straint c1,1 whose modification primitive is SUSPEND, then SD1 = SD \Ct. High evaluation of an interpreta­ tion of G SD; means that conflicts have been reduced and that SD; offers a plausible explanation of OBS, soC; is used to propose a diagnosis.

The creation of set C = {C1 , C2 , .. . } is a difficult problem. It could be generated: (1) by brute-force gen­ eration of permutations of relevant constraints; (2) by heuristics associating evaluations with constraints; (3) by use of functional models 4 or fault models [Struss and Dressler, 1989); or ( 4) by operator interaction, as visu­ alisation of interpretations is often very informative for humans. The set C may be partially ordered (e.g. by interacting with the operator) according to the interpre­ tation weaknesses addressed by each C; and the potential value of the corresponding modifications.

'OSI-style service primitives provide a.n excellent basis for protocol functional models.

Flow Control

Step 1: Trigger. Initialise OBS, COM PS.

Step 2: Propagation, matching, interpretation.

Step 3: Costing Additional Observations Any JUT probes and tests requested for completion of an in­ terpretation or for discrimination of candidates are eval­ uated for: potential cost (JUT response time and avail­ ability), potential informative value, and additional com­ putation time.

Step 4: Termination Information has been accumu­ lated about : candidates; potential value of reiteration; and potential cost and value of further observation to improve current interpretations. Termin-ation occurs if candidates acceptable to operator as diagnoses, or if re­ iteration possibilities exhausted.

Step 5: Observing or Reiterating If no more ob­ servations requested or their cost is prohibitive, then re­ iterate with a new SD; at Step 2. Otherwise, perform probing or testing, complete interpretations with new observations, and go to Step 4.

Example: Consider an implementation of the ABP as specified in Section 2. Given a model based on this speci­ fication and sample logs 5 of the JUT as in Table 1, an ex­ ample diagnosis problem is to find a specific implementa~ tion error, namely that the time-out transition S4.-S3 is set to one instead of eight. This means that if the Replier uses its maximum normal processing time, the Sender will time-out often and resend many messages having a O-bit .

The diagnosis session may have been triggered (Step 1) by a monitor indicating that an error manifesta­ tion (excessive traffic) was detected in a physical region including the two agents and between times 0 and 100. The set OBS is initialised by scanning logs for entries originating from or destined for the given region and oc­ curring within the given time interval. COM PSis deter­ mined using the triggering information and explicit (ex. destination) or implicit (ex. transmission path) compo­ nent information in OBS. Propagation and matching (Step 2) are executed.

~Logs are limited to agent output here in order to facilitate comprehension of time labels.

The left half of Figure 4 summarises G s D . The out­ going transition of -observation (S 1 23) in this figure, labelled /, corresponds to the transition with the same la­ bel leading to propagation (R 1 25-30) in Figure 3. This primary propagation matches to observation (R 1 28) in Figure 4. A forward propagation of observation (R 1 16), labelled i, matches to each of the (S 0 *) ob­ servations, but only one of these transitions is possible. Observation (S 0 20) has a transition labelled b in Fig­ ures 3 and 4, corresponding to the primary forward prop­ agation (R 0 22-27). This is marked (R 0 *) in Figure 4 to indicate that other (S 0 *) observations generate sim­ ilar propagations with shifted intervals. After initial propagation, none of the (S 0 *) observations have for­ ward matches, so their forward propagations are incre­ mented to depth two. This allows the secondary forward propagations corresponding to the transition labelled j to match to observation (S 1 23).

Interpretations are evaluated and set Cis initialised. Constraints related to the generation of (S 0 *) messages are modified, because no interpretation path of Gsv in­ cludes more than one of the (S 0 *). An example in­ terpretation is indicated as a transition path in bold on the left half of Figure 4. No additional observations are required (Step 3), and of course no candidates are pro­ posed in the first iteration (Step 4), so the algorithm reiterates (Step 5) on the variant models.

Consider SD;, where the time-out value of transi­ tion S4-S3 is set to one i.e. the absolute value of the time constraint (8 units after) is changed, but the reiative time constraint (after) continues to hold. Gsv, is summarised on the right half of Figure 4. Here, the (S 0 *) observations match by use of transition 54- S3. One interpretation of SD; (in bold) scores a high evalua­ tion because it includes all observations in one transition sequence. Thus the model SD; offers a better explana­ tion of OBS than SD. Interpretation has provided use­ ful information for diagnosis: that the problem is related to O-bit messages generated by Sender, and that plausi­ ble explanations are generated when the time constraint related to S4-+S3 is modified. Note that a missing ob­ servation (R 0 22) has been predicted and included.

One interpretation may include multiple transition sequence paths, where each path explains a distinct subset of OBS ordered over time. Gaps between any two paths have weak explanations, and provide informa­ tion for potential relaxations. One heuristic for rank­ ing different interpretations is to favour those for which the path starting with the earliest members of OBS is long. This heuristic is similar to the following: "The longer a hypothesis survives changing observations, the stronger the evidence supporting that hypothesis. This age-ranking also focuses attention on hypotheses that account for the earliest manifestations of a fault, before other manifestations and corresponding hypotheses ap­ pear." [Dvorak and Kuipers, 1991).

4 Issues and Related Work

Simulation and Tractability Because of the prob­ lem characteristics described, naive simulation would very quickly become intractable. The HMDP algorithm attempts to address tractability by: limiting OBS and agent-transitions pairs used; incrementing propagation; using of temporal information; constraining traversal of Gsv; and using multiple iterations to focus on small numbers of conflicts.

OBS Density When OBS is dense, i.e. when it rep­ resents a high proportion of observable events, obser­ vations tend to require only one forward propagation. Incremental propagation is comparable to opportunis­ tic reasoning techniques that exploit "islands" of infor­ mation. This is generally more efficient under incom­ plete and uncertain conditions than propagation to a fixed depth in a forward direction alone, which creates a larger number of irrelevant propagations. If observa­ tions are too scarce, then evaluations are low, ·reiteration is poorly constrained, and likely diagnoses may not be found .

Distributed Diagnosis The approach presented is capable of finding candidates involving constraints of any of the communicating agents in COM PS. How­ ever, it must perform matching and interpretation of a given model one agent at a time in order to normalise time-stamps and to correlate messages. A more efficient approach would be desirable for practical global diagno­ SIS.

Communications: An approach to diagnosis of FSMs for troubleshooting based on strongly-sequenced struc­ ture estimation is presented in [Bouloutas, 1990]. A pri­ ori knowledge of possible faults is required, and calcu­ lation is substantial even for simple machines (pp85) . Ghedamsi, Bochmann and Dssouli propose a model­ based approach to diagnosis of FSMs for conformance testing in [1993] . This approach offers more certain di­ agnoses than the HMDP algorithm at the cost of depen­ dence on systematic testing. It diagnoses faults involving incorrect outputs or state changes. Zinky and Etkin. im­ plemented a system that uses model-based techniques to diagnose network performance using abstract behaviour models of traffic and queues [Zinky and Etkin, 1992].

Model-Based Reasoning The Mimic system for pro­ cess diagnosis [Dvorak and Kuipers, 1991], the DATMI system for measurement interpretation [DeCoste, 1990], and the HMDP algorithm are related because all three involve reasoning about multiple possible states with in­ complete or uncertain observations. DATMI and Mimic were designed for continuous physical systems where state does not usually evolve as rapidly as communicat­ ing systems. Mimic attempts to propagate observations forward in one model for each currently plausible fault hypothesis during system operation. Tractabilty prob­ lems would arise for such an approach in the described problem domain. The notion of "iterative search based diagnosis" using information about the degree of mis­ match between observations and predictions was first proposed by in [Leitch and Shen, 1991]. This and the HMDP approach share "the important advantage of re­ ducing the sensitivity to modelling errors and to approx­ imate fault models." Both approaches use temporal du­ rations to reduce search. However, the HMDP algorithm is applied to distributed discrete systems, concentrates on incomplete and uncertain conditions, and does not assume that state can be tracked synchronously.

5 Conclusion

Status: Propagation, matching, and interpretation procedures have been implemented and tested on the ABP prototype model. A prototype model of the OSI Transport Protocol Class 4 (TP4 lCCI, 1989]), consid­ ered to be one of the largest and most complex commu­ nication protocols, has been implemented to determine the scalability and applicability of the HMDP algorithm and for troubleshooting scenarios based on a real imple­ mentation of the entire OSI stack. Automated reitera­ tion and practical tractability with the TP4 have not yet been tested at the time of writing.

For implementation independence, the basis for our TP4 model is the standard specification. Such specifi­ cations allow multiple correct implementations, each of which must . be allowed by the diagnosis program. This issue which is related to behaviour modes [de Kleer, 1989 j, increased modelling effort considerably. For exam­ ple, an event may cause multiple optional outputs in an unspecified order. For efficiency, such output sequences must be modelled abstractly rather than extensionally.

Current and Future Work: Practical considerations and prelimi~ary analysis are reported in [Riese, 1993b]. This includes a reformulation of the problem addressed by the HMDP algorithm as a constraint satisfaction problem. We are currently working on using this for­ mulation to extend the algorithm in order to take ad­ vantage of constraints related to variables, timers, guard conditions, and side-effect procedures. Such rich infor­ mation is ignored by most FSM-based approaches, but is available in communication models, and is very useful for reducing search and for corroboration. We plan to experiment on the hypothesis that discrepancy metrics between correct and incorrect interpretations (similar to [Leitch and Shen, 1991]) can be used to guide model modification. Other potential areas for research include the use of reason maintenance, fault models, and hierar­ chical abstraction to improve performance, and the de­ velopment of distributed diagnosis and multiple model techniques (including physical and queueing models) to increase general practicality. More extensive results and analysis will be available in [Riese, 1993a].

Acknowledgements Thanks to Sailesh Chutani, Boi Faltings, Roy Leitch, Beat Liver, Henri Nussbaumer, Pearl Pu, Prasad Raja, Peter Struss, and the referees for helpful discussions or suggestions on an earlier draft .