Mohamed Kaâniche
email: mohamed.kaaniche@laas.fr

Yannick Le Guédard

Jean Arlat
email: jean.arlat@laas.fr

Thierry Boyer

Yannick Le Guédart

An investigation on

HAL is

Introduction

Designing cost-effective fault-tolerant computer architectures is today one of the main concerns for the developers of dependable systems in a large segment of industrial control applications. However, besides evaluations based on probabilistic modeling or FMECA (Failure Modes Effects and Criticality Analysis), the consideration in the early phases of the development process of dependability issues encompassing detailed behavioral analysis is still hardly supported in practice in industry, with few exceptions such as [START_REF] Ayache | Formal Methods for the Validation of Fault Tolerance in Autonomous Spacecraft[END_REF][START_REF] Kaâniche | A Hierarchical Approach for Dependability Analysis of a Commercial Cache-based RAID Storage Architecture[END_REF]. Accordingly, we have developed a method to assist fault-tolerant systems designers by incorporating the explicit analysis of the faulty behavior of such systems, in the early phases of the development process. The aim is to support designers in making objective choices among different high-level architectural options and associated fault tolerance mechanisms. The proposed approach is based on the development of a functional and behavioral model of the system, and on the behavioral analysis of the model by means of simulation and fault injection.

Several related studies have addressed the issue of supporting the design of dependable systems by means of simulation ( [START_REF] Boué | MEFISTO-L: A VHDL-based Fault Injection Tool for the Experimental Assessment of Fault Tolerance[END_REF][START_REF] Clark | REACT: A Synthesis and Evaluation Tool for Fault-Tolerant Microprocessor Architectures[END_REF][START_REF] Ghosh | System-Level Modeling in the ADEPT Environment of a Distributed Computer System for Real-Time Applications[END_REF][START_REF] Goswami | DEPEND: A Simulation-Based Environment for System Level Dependability Analysis[END_REF]). Although these approaches are generally supported by efficient tools, these tools are not designed to be included in the design process. Indeed, for cost and efficiency reasons, system designers would like to use the same formalism and tool to carry out preliminary functional and behavioral analyses, and to assess the effect of faults on the model of the system. This is why we have tried to attack this issue from a different perspective, i.e., to study instead how several existing design tools can be enhanced to support such an early dependability validation analysis. In contrast to the work reported in [START_REF] Ayache | Formal Methods for the Validation of Fault Tolerance in Autonomous Spacecraft[END_REF], that dealt with formal techniques (in particular, SDL), we focus here on a more pragmatic approach aimed at elaborating on the modeling and simulation capabilities of system engineering tools used in the industrial world by system designers. Statemate [START_REF] Harel | STATEMATE: A Working Environment for the Development of Complex Reactive Systems[END_REF] and RDD-100 are among the various commercial tools that are currently used in industry. Mainly based on the preliminary experiments we have been carrying out to assess the suitability of both tools to analyze the dependability of systems in the presence of faults [START_REF] Guédart | Functional and Faulty Behavior Analysis: Some Experiments and Lessons Learnt[END_REF], our work is now focused on RDD-100. This paper builds on our work reported in [START_REF] Kaâniche | An Investigation on Mutation Strategies for Fault Injection into RDD-100 Models[END_REF]. It is organized as follows. Section 2 deals with simulation-based fault injection and outlines the main reasons that led us to focus on model mutation. Section 3 summarizes the lessons learnt from the preliminary experiments that we carried out on real-life case studies. In particular, these experiments highlighted the need to define a generic approach to support model mutation. The feasibility of such an approach based on the RDD-100 tool is discussed in Section 4. Two model mutation techniques are considered: the use of dedicated fault injection components called saboteurs, and code mutation. Specific mutation mechanisms are proposed to implement each technique and are analyzed with respect to the fault models to be simulated. A comparison of both techniques is also provided. Finally, Section 5 provides the conclusion to the paper.

Simulation-based fault injection

Starting from the original model (called nominal model) built by the designers to carry out preliminary functional and behavioral analysis of the system under nominal conditions, two main approaches can be considered for analyzing fault effects on the system behavior (e.g., see [START_REF] Arlat | Fault Injection into VHDL Models: The MEFISTO Tool[END_REF]). The first one uses the simulator built-in commands to alter the behavior of the model during the simulation (i.e., without modifying the nominal model). The second one (Figure 1) consists of: a) mutating the nominal model before the simulation by adding dedicated mechanisms for injecting faults and observing their effects, and b) simulating the mutated model to analyze the effects of faults.

For both approaches, the analysis of fault effects is carried out by comparing the traces obtained from simulating the system behavior under nominal conditions and faulty conditions, respectively.

The applicability and efficiency of the first approach, with respect to the types of faults that can be injected and their temporal characteristics, strongly depend on the functionalities offered by the command language of the simulator. However, the second approach can take advantage of the full strength of the modeling formalism, i.e., any fault model that can be expressed within the semantics of the modeling language can be implemented. Moreover, this approach is well suited for the definition of generic fault injection mechanisms that can be included automatically in any model and transparently to the user. For these reasons, we have focused our investigations on the second approach.

Lessons learnt from preliminary experiments

Several tools are used in industry to support functional and behavioral analysis of computer systems based on modeling and simulation, e.g., Statemate and RDD-100. To study the suitability of these tools for analyzing system behavior in the presence of faults, we carried out several experiments on four real-life case studies [START_REF] Guédart | Functional and Faulty Behavior Analysis: Some Experiments and Lessons Learnt[END_REF]. In the sequel, we summarize the characteristics of the four target systems and the main insights gained from this study.

As shown in Table 1, the four target systems were all related to critical applications from distinct fields (nuclear propulsion, ground-based and on-board space systems). The systems architectures were designed to satisfy stringent safety and availability requirements. They include several redundant components using voting and reconfiguration fault tolerance mechanisms. In these experiments, we used RDD-100 and Statemate to:

1) model some critical features of each system (e.g., synchronization, reconfiguration management) based on the specification documents available;

2) inject faults into the models (corrupting data, simulating delays and omissions, etc.);

3) analyze the impact of these faults using the simulation engines integrated in the tool.

These experiments confirmed that significant insights can actually be obtained from the analysis of systems behavior in the presence of faults, early in the design process. For example, a model of a realtime ground-based space subsystem (S2 in Table 1) was developed to analyze the impact of temporal faults on the system behavior. This experiment allowed us to reveal an error detection latency problem that was related to the overlapping of two error detection mechanisms and an incorrect sequencing of recovery actions.

From the point of view of fault injection implementation, these experiments highlighted the need to define a set of generic mechanisms allowing the mutation of system models in a systematic way, rather than on an ad-hoc basis. Indeed, to be applicable to the analysis of complex real-life systems in an industrial context, the following three requirements should be satisfied by the mechanisms dedicated to injecting faults and observing their effects:

1) The mutated model should preserve the behavior and properties of the nominal model if faults are not injected during the simulation. This will ensure that the mutation mechanisms will not alter the behavior of the nominal model in the absence of faults. Also, the comparison of the simulation traces obtained from the mutated and the nominal models will be made easier, as this comparison can be focused on the instants when faults are injected.

2) Model mutation should be based on the semantics of the modeling formalism, and not on the target system model. The objective is to provide generic mutation mechanisms that are applicable to a large set of systems, rather than to a particular system.

3) Model mutation should be performed automatically and transparently to the user. The latter should be involved only in the specification of the faults to be injected and the system properties to be analyzed.

Finally, it is worth pointing out that the experiments carried out allowed us to identify that in most cases, similar behaviors can be described by the features provided by the respective supporting tools.

Still, the use of RDD-100 was found more intuitive than Statemate to describe detailed temporal features. This is mostly due to the fact that the formalism inherits largely from the SDL formalism.

Nevertheless, this alone is not enough to draw a clear-cut preference between Statemate and RDD-100.

Thus, although both Statemate and RDD-100 formalims are widely used in industry, and especially by the three industrial partners involved in this preliminary study, the choice of the RDD-100 formalism made by the industrial partner involved in the conduct of further investigations aimed at the definition of an approach targeting the previously identified requirements was simply based on industrial strategic reasons.

Accordingly, our investigations concerned the two following objectives:

1) The definition of model mutation mechanisms based on the RDD-100 formalism.

2) The development of a prototype tool that integrates those mechanisms into RDD-100. The rest of this paper summarizes the main results obtained from our study.

Fault injection into RDD-100 models

Two different techniques for model mutation have been investigated. The first one is based on the addition of dedicated fault injection components called "saboteurs" to the RDD-100 nominal model.

The second one is based on the mutation of existing component descriptions in the RDD-100 nominal model. Before describing these two techniques, we provide first a summary of the main concepts of RDD-100 formalism.

RDD-100 main concepts

RDD-100 incorporates a coherent set of formalisms that enable engineers to: 1) define requirements and allocate them to system components according to a hierarchical approach, 2) refine their behavioral description into discrete processes and allocate these to system interfaces, 3) establish system feasibility on the basis of resources and costs, and 4) iterate the engineering design process with increasing levels of detail. Our study focuses on the behavior diagrams formalism (named F-Net) defined within RDD-100 to support the detailed description and simulation of system and components behavior.

A behavior diagram is a graphical representation of the modeled system, composed of a set of concurrent and communicating (SDL-like) extended finite-state machines, called Processes. The finite-state machine is extended in the sense that it has memory and can make decisions about responses to stimuli based upon that memory, and communicating in the sense that it can stimulate other processes by sending messages to them. The behavior of each process can be detailed by describing the set of Functional Modules executed by the process and their interactions. Functional modules whose behavior can be described hierarchically are called TimeFunctions and those that are not further decomposed are called DiscreteFunctions. Three types of items can be input to or output from a function: Global, State, Message. Global items are available to all functions within the model.

State items are available only to the functions of the same process. Messages can be sent only from one process to another. Each function can receive at most one message. However, it can send several messages, one per recipient. RDD-100 provides three constructs or structures (Select, Iterate, and Replicate) allowing for a concise representation of complex behavior diagrams. The Select structure enables to choose among multiple execution paths at the output of a given module depending on conditions specified in the code of that module. The Iterate structure describes the repetitive execution of the sequence of modules that appear between two iteration endpoints. Finally, the Replicate structure allows the representation of equivalent processes by a single abstraction in the model. This structure is particularly useful for the modeling of redundancy in fault tolerant systems.

Fault models

Fault injection requires the definition of fault types, fault activation time and fault duration.

Different types of faults can be injected to alter the value or timing characteristics of behavior diagrams.

In our study, four types of faults are distinguished:

1) data corruption of global items, state items, or messages, that are input to or output from a functional module;

2) delayed execution of a functional module;

3) non activation of a module when triggered; 4) spurious activation of a module; i.e., the module is activated whereas it is not supposed to.

For each fault type, its activation time can be related to the simulation time or to the model state and its duration may be permanent or transient.

Model mutation based on saboteurs

In this approach, each functional module of the RDD-100 nominal model is considered as a black box. Fault injection is carried out by dedicated components associated to the target module, called saboteurs. The saboteurs intercept the inputs or the outputs of the target module and possibly alter their value or timing characteristics to imitate the behavior of the module in the presence of faults.

In the following, we describe the approach that we defined to mutate RDD-100 models based on the insertion of saboteurs. This approach aims at satisfying the requirements listed in Section 3. We first illustrate the mutation of a single functional module, then we discuss how this approach can be applied when the nominal model includes special constructs such as Replicate and Select.

Mutation of a single functional module

For each functional module of the nominal model, we associate two saboteurs: S1 intercepts the inputs of the module and possibly alters their value or timing characteristics, and S2 acts in a similar manner on the outputs of the module. The types of faults to be injected in the target module, as well as their activation time and duration are specified in the functional code of the saboteurs. As illustrated in Figure 3, the mutation consists in transforming the target module F, into three parallel processes, corresponding to the execution of S1, F and S2, respectively. The communication between the saboteurs and F is done through message passing. This mechanism enables the synchronization of the functional module with its associated saboteurs. Indeed, module F execution is initiated when S1

terminates, and S2 is activated after the execution of F. Therefore, the input items sent to F (i. When it is not activated, the behavior of each saboteur is transparent, as if it was not present in the model. The input data are delivered instantaneously to the functional module through S1 without any modification. Similarly, the outputs of the module are made accessible to the model components, through S2. Therefore, the saboteurs remain inactive until a fault is triggered.

4.3.2.Injecting the four types of faults

The injection of the four types of faults defined in Section 4.2 is performed as follows.

• Data corruption can be achieved by substituting new values to the original ones. Any data item or data type defined within a behavior diagram can be modified accordingly.

• A delayed execution of a module is simulated simply by assigning to the saboteur an execution time corresponding to the value of the delay.

The simulation of the non execution of a module when triggered is done by means of S2. S2 intercepts all the module outputs and ensures that the module remains silent during the duration of the fault.

• The simulation of the spurious activation of a module is more problematic. Indeed, to be activated, a module must receive the activation token as well as the input messages expected by the module (if any). Two solutions can be considered to simulate such a behavior. The first one consists in modifying the behavior diagram to ensure that from each node of the behavior diagram there is a link leading to the target module over which the activation token can flow to activate the target module upon the occurrence of the fault. This solution is not practically feasible, especially when we deal with complex behavior diagrams. Also, it requires a significant modification of the internal code of the functional modules to ensure that the resulting model is consistent. For the second solution, we assume that only the modules of the nominal model that receive input messages may exhibit such a behavior. In this case, the spurious activation of the module can be simulated by means of a specific saboteur, designed to send a message to the target module(s) upon the activation of the fault. This solution is illustrated in Figure 4. In this example, the nominal model is composed of two processes corresponding to the activation of modules F and G respectively. To simulate a spurious activation of G at some time t, we create a saboteur that is executed concurrently to modules F and G, and remains active during the simulation. This is ensured by using the iterate structure represented by the @ symbol. When the fault activation time is reached, the saboteur sends a message to the target module (G). This message will be taken into account by G when the token is received.

So far, we did not discuss how to mutate the model when some input data are shared by several modules. In this case, various situations can be distinguished; for instance:

1) The fault affects the input interface of one module only.

2) The fault affects the input interfaces of all the modules, and the same error is produced.

3) The fault affects the input interfaces of all the modules, but different error symptoms are produced each interface; this could correspond for example to the occurrence of Byzantine faults.

The mutation mechanism proposed in Figure 4 reproduces the faulty behavior corresponding to the first situation. Indeed, the saboteurs associated to a given module are designed to alter the execution context of the target module without altering the execution context of the other components of the model. Therefore, if we corrupt an input data that is shared by the target module and other components, the modified input will be propagated to the target module only. The other components will still perceive the original copy of this input. This choice offers more flexibility to the users with respect to the kind of faulty behavior they would like to simulate. In particular, the faulty behaviors corresponding to situations 2) and 3) described above, can be easily simulated associating saboteurs to each component, and specifying the attributes of the faults to be injected in the input saboteur according to the faulty behavior to be simulated (i.e., same error patterns for situation 2 and different error patterns for situation 3).

Modules without input or output messages

In Section 4.3.1, we assumed that the functional module to be mutated has input as well as output messages. However, the nominal model might include some modules that do not have messages either in the input or in the output domain. In this case, we just need to create dummy messages, between S1 and the module, or between the module and S2. Once the messages are created, the mutation is performed according to the approach described in Section 4.3.1. It is noteworthy that the content of the dummy messages is irrelevant, as the only role of these messages is to synchronize the execution of the module and its associated saboteurs.

Functional modules with multiple output messages

An RDD-100 module can receive at most one input message. However, it can send multiple output messages, one per recipient. To mutate a module with multiple output messages, we have to adapt the construction proposed in Figure 3 to ensure that no more than one message is sent to the output saboteur, S2. Two techniques can be considered to satisfy this condition. The first one (Figure 5-b) consists in modifying the internal code of the target module to ensure that only one output message is sent to S2. This can be achieved by transforming all the output messages, but one, into Global items.

The remaining message will be used to trigger the saboteur S2. When the Global items are accessed by S2, they are transformed into messages before being delivered to their recipients. The second technique consists in associating a saboteur to each output message, and coordinating the execution of these saboteurs as illustrated in Figure 5-c. If the number of output messages to be altered is important, this could lead to very complex mutated models. Clearly, the first solution is more practical, even though its implementation requires the modification of the functional code of the target modules.

Mutation of a Replicate structure

The Replicate structure is a notation used to specify the simultaneous simulation of multiple copies of the same process within a behavior diagram. It is composed of three parts:

1) A replicate branch defining a sequence of functions that represents a process. This process is treated by the simulator as having multiple copies (replicates) that are simulated concurrently.

2) A domain set defining the number of replicates created when the token enters the replicate structure.

3) A coordination branch controlling the execution of the replicated processes. The coordination branch may send messages to and receive messages from the replicated processes, and may create and delete replicate processes. Any message received by a replicate process must be passed through the coordinate branch.

When the simulator encounters a replicate structure (identified by the node &*), it creates a token for each replicate process, just as when entering a parallel structure. In addition, the token continues on the coordination branch. All processes are simulated concurrently. The replicate structure is exited when all the processes on both branches have terminated. Then, the tokens are rejoined into a single token, which is distributed to the next function or structure on the behavior diagram to be simulated.

As illustrated on Figure 6, two targets can be considered for the mutation of a Replicate structure:

the replicated modules and the coordination module. The mutation of each of these targets is performed according to the process presented in previous Subsections, i.e., two saboteurs S1 and S2

are associated to each mutated module. The mutation of a Replicate structure leads to the replication of the saboteurs associated to each module of the structure. In this context the same faults will be injected in each replica. However, it is also possible to access distinctly each mutated replica, and different faults for each mutated module.

The mutation of the coordination module offers to the users several possibilities to alter the global behavior of the replicate structure. Besides altering the content and the timing characteristics of the messages exchanged by the replicas, the mutated coordination module can be used to dynamically remove some replicas from the execution process (e.g., because of failures) or to increase the number of active replicate (e.g., as a result of recovery actions). Thus, this mechanism is particularly useful to analyze the behavior of fault tolerant systems under faulty conditions.

Mutation of a Select structure

The Select structure is represented by the notation (+) and allows for performing selectively either one process or the other, depending on the arrival sequence of messages from other processes. For example, in Figure 7-a, after the execution of module F, the token may be directed to the branch executing F1 or to the branch executing F2 depending on conditions specified in the F user code.

To support fault injection, each module F, F1 and F2, can be mutated according to the process described in Section 4.3.1. For example, Figure 7-b presents the model obtained when only F is mutated. With this model, any modification of module F inputs remains local to that module and does not affect the inputs of F1 or F2. If one wants to reproduce the same perturbation on the inputs of F1 or F2, two alternatives can be considered:

1) Specify the same kind of fault to saboteurs associated to F1 or F2.

2) Modify the mutated model in Figure 7-b to ensure that any modification of an input item shared by F and the modules involved in the select structure (F1, F2) affects all these modules. This can be done by directing the outputs of saboteur S1 associated with F, to the input interfaces of modules F1 and F2. The non activation of a module when triggered can be simulated by ensuring that the outputs of the module are not modified when the fault occurs. If we inject such a fault into module F in Figure 7, its outputs will not be updated when the fault occurs and the token will be directed to either F1 or F2 depending on the system state. Therefore, injecting such a fault does not mean that the whole Select structure is not executed when the fault occurs. If one wants to simulate the latter behavior, it is necessary to modify the internal code of F, i.e., such behavior cannot be simulated simply using saboteurs.

Code mutation

So far, we assumed that each module of the RDD-100 nominal model was a black box and we analyzed how to mutate the model by inserting saboteurs dedicated to injecting faults at the input or output interfaces of the target modules. In this section we analyze how to mutate the internal code of the nominal model by including the code dedicated to fault injection without inserting additional components into the Code mutation offers a variety of possibilities to alter the behavior of the nominal model. Besides altering the data values and timing characteristics of the target modules, any statement of the original code can be corrupted, e.g., substituting operators or variable identifiers; this is similar to the mutation techniques used by the software testing community [START_REF] Demillo | Hints on Test Data Selection: Help for the Practicing Programmer[END_REF][START_REF] Thévenod-Fosse | Statistical Software Testing[END_REF][START_REF] Voas | Software Fault Injection -Inoculating Programs Against Errors[END_REF]. In this paper, we focus only on the fault models defined in Section 4.2.

Data corruption. Any input or output data item (global, state or message) manipulated by a module can be easily accessed. Data corruption consists in substituting to the target items new values corresponding to the faults to be injected. A simple example is presented in Figure 8. The user code of the target module consists in reading two input data items A and B, computing their sum and the result C to the output interface (Figure 8a). The mutated code leading to the corruption of A is given in Figure 8b. The output value C can also be altered using the same process. More generally, to reproduce the same faulty behavior implemented with the saboteurs, we have to ensure that when we modify the value of a data item, any occurrence of this data item in the original code is substituted by the new value. This process can be easily automated. Clearly, this technique is easier to implement and is more efficient than the approach based on the insertion of saboteurs discussed in Section 4.3.

Figure 8 -Data corruption by code mutation

Delays. The simulation of delays can be implemented in two ways: 1) either the execution of the module is delayed by inserting a delay at the beginning of the code, i.e., the input items are read by the target module when the delay specified in the mutated code expires, or 2) the emission of output items to the output interface is delayed. To implement the latter case, we have to identify in the original code each output and insert a delay before the corresponding outputs can be accessed.

Nonactivation of a module when triggered. This kind of behavior can be simulated easily by identifying and deactivating all or selected output statements in the target code.

Spurious activation of a module. The simulation of this behavior requires the identification of the modules that send messages to the target module, and then mutate the corresponding code by inserting a statement that forces the emission of a message to the target module when the activation time of the fault is reached. When more than one module is able to activate the target module, an algorithm must be implemented to decide, which module will be selected to send the triggering message when the fault is activated. Clearly, the implementation of this strategy is complex. The solution presented in Section 4.3.1 that is based on the definition of a saboteur dedicated to the activation of the target module appears thus more suitable to simulate this kind of behavior.

Mutation of Replicate and Select structures.

The code mutation mechanisms discussed above for a single functional module can also be applied to mutate Replicate and Select structures, with the same advantages and limitations. More details are provided in [START_REF] Guédart | Functional and Faulty Behavior Analysis with RDD-100 -Method and Prototype[END_REF].

Comparison and discussion

In this section, we analyze to what extent the two mutation strategies presented in Sections 4.3 and 4.4 satisfy the guidelines defined in Section 3.

Preservation of the nominal model properties

The mutation mechanisms based on the saboteurs or on the modification of the RDD-100 components code are designed to be inactive when faults are not injected during the simulation.

Considering the first mutation approach, the saboteurs are executed instantaneously and the input data as well as the output data are delivered to their recipients without being altered. If we except the additional traces resulting from the modification of the behavior diagram structure due to the insertion of the saboteurs, the outputs provided by the simulation of the mutated model and the nominal model will be identical (in the value and timing domain). Therefore, the properties of the nominal model are preserved by the mutated model when it is simulated without activating faults. These properties are also preserved by the mutated model obtained with code components mutation. Note that no additional traces are produced with the latter approach due to the fact that the model structure is preserved.

Independence with respect to the target systems.

All the mutation mechanisms described in the previous sections were defined based on the characteristics of the RDD-100 behavior diagrams formalism and the SmallTalk language used to implement the code of RDD-100 components. They are generic in the sense that they can be applied to any system model built with the RDD-100 tool. Nevertheless, the specification of the types of faults to be injected and of the properties to be analyzed naturally requires a deep knowledge of the target system.

Transparency

Starting from the nominal model, and the specification of the fault injection campaign to be performed, the generation of the mutated model based on the insertion of saboteurs or on the modification of components code can be carried out automatically. A set of mechanisms integrated within the RDD-100 tool can be developed to support the implementation of the mutation strategy. A prototype tool is currently under development to implement this approach [START_REF] Guédart | Functional and Faulty Behavior Analysis with RDD-100 -Method and Prototype[END_REF].

Comparison of the proposed solutions

The two mutation techniques discussed in the previous sections present some advantages and limitations.

Considering saboteurs, the code dedicated to fault injection is separated from the original code.

This facilitates the analysis of the mutated model. In particular, the graphical representation of the mutated model clearly identifies the components to be altered as well as their characteristics.

Moreover, the saboteurs can be defined as reusable components. Thus, the implementation of model mutation algorithms can be simplified significantly. However, a major problem with this technique is 20 related to the dramatic increase of the complexity of the mutated model due to the insertion of additional components. As regards the fault modeling capacity of this technique, we have identified some situations that cannot be easily handled simply by using saboteurs and without modifying the original code of the target modules (e.g., functional module with multiple output messages). This is related to the fact that the saboteurs have a restricted view of the target components, i.e., fault injection can be performed only the input or the output interfaces of these components.

The code mutation technique does not have such limitation. Indeed, any fault model can be simulated, provided it can be expressed within the RDD-100 formalism. Generally, for simple fault models we only need to add a few statements to the target code to support fault injection. Conversely, there are some situations where it is more suitable to use saboteurs to describe the faulty behavior to be simulated. This is the case for example of the simulation of the spurious activation of a target module (See Section 4.4).

Clearly, the above discussion shows that the combined use of saboteurs and code mutation provides a more comprehensive and flexible approach for mutating RDD-100 models. A prototype tool implementing such an approach has been developed. The prototype is implemented in Perl and performs the following tasks (Figure 9): The analysis task consists in parsing the textual description of the nominal model and identifying all the model components (processes, TimeFunctions and DiscreteFunctions), the inputs and outputs associated to each component (State items, Global items, Messages) and the interactions between these components (data flow and control flow). The outcome of this analysis is a list of potential targets for fault injection. Based on this list, the user can select the components on which fault injection will be carried out and specify the kind of faults to be injected with their activation time and duration. Based on this specification, the mutated model is automatically generated by the prototype.

Code mutation is used to simulate data corruptions, delays, and non activation of modules when triggered. The simulation of a spurious activation of a module is carried out by using a dedicated saboteur. More details about this prototype are given in [START_REF] Guédart | Functional and Faulty Behavior Analysis with RDD-100 -Method and Prototype[END_REF].

Conclusion

The main objective of our study consists in integrating fault injection mechanisms into system engineering tools actually used in industry by system designers. By doing so, dependability analyses can be fully integrated early in the development process of dependable systems. techniques showed that a more practical and flexible approach should combine both techniques, instead of using either one or the other. In particular, code mutation can be used to simulate data corruptions, delays, and non activation of components when triggered, while saboteurs are more suitable to simulate a spurious activation of some target components.

Figure 1 -

 1 Figure 1 -Fault injection based on model mutation

Figure 2

 2 Figure 2 presents a simple example of a behavior diagram composed of two concurrent processes: Process 1, composed of module F, and Process 2, composed of module G. Concurrency is represented by the node (&). At the beginning of the model execution, a token is produced by the simulator. The token flow through the model structure describes different execution scenarios. When a token reaches the top node of a parallel branch, the simulator creates a new token for each process. The simulator treats each process concurrently. When the tokens of all processes reach the bottom node (&), the simulator recombines them into a single token and advances the token to the next node on the diagram.

Figure 2 -

 2 Figure 2 -Example of a behavior diagram

  e., messages, Global and State items) may be altered by S1 according to the fault model specified in S1, before execution of F. The analysis of the outputs delivered by the module will allow the designers to analyze the impact of the simulated faults on the module behavior as well as on the system. Similarly, faults can be injected on the module outputs to assess to what extent such faults can be tolerated by the system. If the fault activation time is conditioned upon some Global or State items that are not included in the inputs to module F, an additional input to S1 and S2 is added to include these items as illustrated on Figure3-b. All this process can be performed automatically.

Figure 3 -

 3 Figure 3-Mutation of a single module

Figure 4 -

 4 Figure 4-Spurious activation of a module: Example

Figure 5 -

 5 Figure 5-Mutation of a module with multiple output messages

Figure 6 -

 6 Figure 6-Mutation of a Replicate structure

Figure 7 -

 7 Figure 7 -Mutation of a Select structure

1) Analysis of the nominal model 2 )

 2 Set up of fault injection campaign 3) Generation of the mutated model Tasks 1 and 3 are performed automatically without any interaction with the user.

Figure 9 -

 9 Figure 9 -Synoptic of the main tasks performed by the prototype tool

  This paper focused on the development of a systematic method for integrating simulation-based fault injection mechanisms into RDD-100 models to support system designers in computer systems dependability analysis. Starting from the functional and behavioral model developed by the designers, the proposed approach consists in mutating the model by including mechanisms aimed at injecting faults, and simulating the mutated model to analyze the impact of injected faults on the system behavior. Two mutation techniques have been studied: the first one consists in adding fault injection components called saboteurs, that are designed to alter the input or output interfaces of the target components, and the second is based on the code mutation of original model components. Four types of fault models have been considered (data corruption, delay, non activation of a module when triggered, and spurious activation of a module) and specific mechanisms have been proposed for each mutation technique to simulate the corresponding fault models. The comparative analysis of

Table 1 : Target systems and experiments Target system Dependability requirements Main architectural features Aim of the experiment

 1

	S1 (submarine nuclear propulsion system control)	Safety and Availability (a submarine is considered lost should the propulsion system fail)	Recurrent architecture pattern consisting in an active triple modular redundant (TMR) architecture with majority voting (2/3) on the logical outputs.	Study to what extent the simulation approach could help system designers in tuning the functional and structural features of the architecture
			A dual redundant architecture
	S2 (ground-based space system aimed to transmit critical commands to a launcher)	Safety (protect populations that could be endangered by the launcher) and Availability	with two self controlled switch between the two channels operating in semi-active mode, and a TMR architecture implementing the configuration module aimed to	Assess the ability of the Statemate and RDD-100 tools in handling critical timing issues
			channels.
	S3 (ground-based		Five identical processing units	Model the algorithm for electing
	space system aimed to	Availability (in order to	(active redundancy). Choice of	the master processing unit of the
	help navigation among	offer a continuous signal	the operational unit is made by	system, and observing model
	a wide range of users:	to the users)	another system using dual	behavior upon the occurrence of
	aircraft, boats, cars,…)		redundancy.	faults
	S4 (on-board space sub-system, devoted to the monitoring and management of reconfigurations for the rest of the system)	Availability and Error confinement (no propagation of local errors to the rest of the system)	Four identical computing units detection) (hot redundancy) and three identical I/O units (cold redundancy), N-version programming, executable assertion (on-line software error	Analyze potential links, overlaps and complementarities between FMECA and the simulation under faulty behavior method.

Acknowledgments. Yannick Le Guédart was supported by Technicatome. This work was carried out at the Laboratory for Dependability Engineering (LIS). Located at LAAS, LIS was a cooperative laboratory gathering five industrial companies (Astrium France, Airbus France, Électricité de France, Technicatome, and THALES) and LAAS-CNRS.


Karima Sedki
email: karima.sedki@irisa.fr

Louis Bonneau
email: louis.bonneau@agrocampus-ouest.fr

Cognitive Maps and Bayesian Networks for Knowledge Representation and Reasoning

Cognitive maps are powerful graphical models for knowledge representation. They offer an easy means to express individual's judgments, thinking or beliefs about a given problem. However, drawing inferences in cognitive maps, especially when the problem is complex, may not be an easy task. The main reason of this limitation in cognitive maps is that they do not model uncertainty with the variables. Our contribution in this paper is twofold : we firstly enrich the cognitive map formalism regarding the influence relation and then we propose to built a Bayesian causal map (BCM) from the constructed cognitive map in order to lead reasoning on the problem. A simple application on a real problem is given, it concerns fishing activities.

I. INTRODUCTION

To solve a given decision problem, there is often need to firstly provide knowledge and judgment analysis of the problem. This task is not easy, especially when the elicitation process includes several domain experts where each one has his own view of the problem. The difficulty appears namely in used variables (factors, events, etc.), the type of relationships between variables (dependencies, causality, correlation, etc.), the nature of data (uncertain, incomplete, etc.), etc. So, it is important to choose a model that allows to respond to the targeted objective. Graphical Models, such as cognitive maps (CMs) [START_REF] Eden | Cognitive mapping -a user's guide[END_REF], Bayesian networks (BNs) [START_REF] Finn | Bayesian Networks and Decision Graphs[END_REF], are powerful models for representing domain knowledge. They have been widely used for solving various problems [START_REF] Delcroix | Bayesian networks versus other probabilistic models for the multiple diagnosis of large devices[END_REF], [START_REF] Comes | Decision maps: A framework for multi-criteria decision support under severe uncertainty[END_REF], [START_REF] Klein | Cognition maps on decision workers in complex games[END_REF].

In this paper, the studied problem concerns the analysis of shells fishing activity in the west region of France (rade de Brest). The objective consists to study the views of fishermen about their activity. Namely, the goal is to determine the variables or factors that may impact fishermen in their activity and environment (for example, analyze the impact of environmental conditions, material and human means in the fishing activity). We first use a cognitive map (CM) formalism to represent the perception of the interviewed actors. CM is a directed graph which represents variables and causal relations between the variables in a decision problem. They have the advantage to describe and capture the decision makers knowledge in a more comprehensive and less time-consuming manner than other methods [START_REF] Nadkarni | A causal mapping approach to constructing bayesian networks[END_REF].

As we mentioned above, the elicitation step is important for solving and modeling decision problems. However, another important step is also required. It concerns inference process which consists in obtaining new facts or conclusions from other information. However, drawing inferences in CMs, especially when the problem is complex, may not be an easy task [START_REF] Laukkanen | Comparative cause mapping of organizational cognition[END_REF]. The first reason of this limitation in CMs is that they do not model uncertainty with the variables. In addition, the variables in cognitive maps are represented in a static way. Namely, the way in which the beliefs of decision-makers about some target variables change when they learn additional information about the concepts of the map is not represented.

In the other hand, although BNs are a well-established method for reasoning under uncertainty and making inferences, the elicitation of the structure and parameters of the network in complex domains can be a tedious and time-consuming task. Moreover, the notion of probability is often not perceived or understood by domain experts. The task is therefore more tedious and time-consuming for generating conditional probabilities.

It is clear that in our problem, using the cognitive map model is not sufficient to analyze and understand the impact of the different variables of the problem and using the Bayesian network (BN) for generating the conditional probabilities from fishermen is not also an easy task. However, despite the limitations of each model (BN and CM), combining them is possible. The combined model is called Bayesian causal map (BCM) [START_REF] Shenoy | A bayesian network approach to making inferences in causal maps[END_REF]. To construct a BCM, the procedure consists firstly in constructing a cognitive map and then convert it into a Bayesian causal map. In [START_REF] Shenoy | A bayesian network approach to making inferences in causal maps[END_REF], the authors use the initial CM only to construct the structure of the BCM. They define the parameters (local probabilities) of the BCM from experts knowledge. This means that domain experts are in a first step solicited for the construction of the CM and second in the definition of the conditional probabilities.

In this paper, our proposition consists firstly in an extension of the CM formalism by enriching the causal relation with additional information (for example, information about the influence of each causal concept when the premise variable increases and decreases). Secondly, we propose to transform the constructed CM into BCM. Concerning the structure of the BCM, we follow the procedure described in [START_REF] Shenoy | A bayesian network approach to making inferences in causal maps[END_REF]. Concerning the parameters of the BCM, we propose to take into account the causal values associated to the relations of the constructed CM. Namely, the elicitation step of the BCM will be less tedious since the structure and the parameters of the BCM are defined from the constructed CM. Finally, we propose to built a BCM in order to analyze the problem of shells fishing activity. The CM is constructed from judgments and beliefs of several actors (fishermen) and then we transform it into a BCM following the proposed approach.

The rest of the paper is organized as follows: In section II, we present some important issues related to BNs and CMs. In Section III, we present the new CM formalism. Section IV proposes a procedure to construct a Bayesian causal map. Section V presents the studied problem with some simulation cases. Section VI concludes the paper.

II. COGNITIVE MAPS AND BAYESIAN NETWORKS

In this section, we provide a brief description of cognitive maps and Bayesian networks.

A. Cognitive maps

A cognitive map, also called causal map, is a directed graph that represents the knowledge of decision makers. It expresses individual's judgments, thinking or beliefs about a given problem [START_REF] Eden | Cognitive mapping -a user's guide[END_REF], [START_REF] Chaib-Draa | Causal maps : Theory, implementation and practical applications in multiagent environments[END_REF]. Figure 1 gives an example of a CM. We distinguish three principal components in a CM 1) Concepts: A node in a cognitive map represents a concept which corresponds to a variable (attributes, factors or events) of the studied problem. 2) Causal relations: An arc between two concepts in a cognitive map represents a causal relation. It depicts a cause-effect (or cause-consequence) relation between two concepts. If we have a causal relation from concept A towards a concept B, then A is called a causal concept and B is called an effect concept. We distinguish two forms of causal relations: a) A positive relation between two concepts indicates that an increase in the causal concept leads to an increase in the effect concept.

b) A negative relation indicates that an increase in the causal concept leads to a decrease in the effect concept or decrease in the causal concept leads to increase in the effect concept. For example, in Figure 1, a causal relation between Number of fishermen (NF) and Quantities of shells fished (QSF) is positive which denotes that the higher the NF, the higher will be the QSF. On the other hand, the causal relation between the concept Importation (Imp) and Quantities of shells fished is negative, it establishes that the higher the Imp, the lower the QSF.

3) Causal values: Each positive or negative relation can be associated with a numerical value, called a causal value. It represents the strength of the causal relation.

When the continuous values of the CM are in the interval [-1, +1], they represent fuzzy cognitive maps [START_REF] Kosko | Fuzzy cognitive maps[END_REF]. In this paper, the considered causal value can be Low (-1 or +1) (resp. M edium (-2 or +2 ), High (-3,+3), N ull (0)). These values are used in drawing CMs since this is easier and more intuitive for elicitation.

CM allows only deductive reasoning (predicting an effect given a cause). Thus, we can get responses about the effects of a given cause but we can't answer why effects are produced.

B. Bayesian Networks

Bayesian networks [START_REF] Finn | Bayesian Networks and Decision Graphs[END_REF] are widely used in decision making mainly for problems that contain uncertain information. They are probabilistic models specified by two components:

1) A qualitative component: It represents independence relations by a directed acyclic graph (DAG), where each node x i represents a variable, and arcs represent the corresponding relationships between these variables. 2) A quantitative component: It quantifies the uncertainty of the relationships between variables. Each variable contains the states of the event that it represents and a conditional probability table (CP T ). The CP T of a variable contains probabilities of the variable being in a specific state given the states of its parents. The joint probability distribution for X = {x 1 , x 2 , ..., x n } is given by the chain rule :

P (x 1 , x 2 , ..., x n ) = i=1...n P (X i |P a i ) (1)
where P a i represents the parents of x i .

In Figure 2, we have an example of a BN which contains four variables (B, S, D and P ). B has two states (No, Yes) and has no parents. S and B are two parents of D which is a parent of P . For each variable, there is need to specify a conditional probability distribution table. In Figure 2, we observe these tables: P(B), P(S), P(D | S, B) and P(P | D). In Figure 2, there is no arc between the variables B and S, so these two variables are independent; there is arc from B and S to D, this denotes that D is dependent of B and S. There is also no arc between B and P and no arc between S and P , this means that P is conditionally independent of B and S given D (conditional independence assumption in BNs). Another important notion in BN is the one of probabilistic inference. It allows to compute the probability of any variable given some observed variables. Inference in BN is based on the notion of propagating evidence. We can use BN to perform abductive reasoning (diagnosing a cause given an effect) and deductive reasoning (predicting an effect given a cause).

III. THE NEW FORMALISM OF COGNITIVE MAP

In the original cognitive map formalism, each positive or negative relation is assigned with only one value which can be positive or negative. The causal relation is symmetric, this means that an increase of the causal concept has symmetric impact on the effect concept than decreasing of the same causal concept. For example, in case where the causal relation between two concepts x and y is negative, if an increase of the causal concept x causes high decreasing in the effect concept y, then decreasing of x causes high increasing of y. In the example of Figure 1, increasing of ASP causes high decreasing of QSF (-3). The influence of decreasing of ASP is supposed to be symmetric, namely it causes high increasing of QSF (+3) which is not correspond to judgment of fishermen. In this paper, we propose to enrich the formalism by assigning two values to each causal relation. Namely, the new formalism informs us about the impact of increasing and decreasing of the causal concept which is not necessarily symmetric. So, in the new formalism:

• Each causal relation is assigned two values represented by [V 1 , V 2 ]. • V 1 represents
the influence degree on the effect concept when the causal concept increases. • V 2 represents the influence degree on the effect concept when the causal concept decreases. • V 1 and V 2 are numerical values, each one can be either positive, negative or null. Each of V 1 and V 2 can be Low (-1 or +1) (resp. M edium (-2 or +2 ), High (-3,+3), N ull (0). • V 1 is positive if the increase of the causal concept causes increasing in the effect concept.

• V 1 is negative if increasing the causal concept causes decreasing in the effect concept. • V 1 is null if increasing the causal concept has no impact on the effect concept. • V 2 is positive if decreasing the causal concept causes increasing in the effect concept. • V 2 is negative if decreasing the causal concept causes decreasing in the effect concept. • V 2 is null if decreasing the causal concept has no impact on the effect concept. The difference between the new formalism and the original one is that the causal relation is not necessarily symmetric in the extended formalism. For example, in the new formalism, if increasing the causal concept leads to increasing in the effect concept (suppose that the impact is high), then decreasing of the causal concept can lead to increasing or decreasing the effect concept (the impact can be low, medium or high), the influence on the effect concept can have also no impact on the effect concept. An example of the new formalism is given in Figure 3. The information [+2, -3] between the causal concept N umber of f ishermen (N F ) and the effect concept Quantities of shells f ished (QSF ) means that an increase of N F causes an increase of QSF (+2) and decreasing of N F causes a decrease of QSF (-3). The information [-3, 0] between the causal concept ASP and the effect concept QSF means that an increase of ASP causes a decrease of QSF (-3) and decreasing of ASP has no impact on QSF (0) (while in the original formalism as observed in Figure 1 increasing of ASP causes decreasing of QSF (-3) and decreasing of ASP causes increasing of QSF (as the relation is symmetric, the value is by default equal to +3)).

IV. FROM A COGNITIVE MAP INTO A BAYESIAN CAUSAL

MAP

As mentioned previously, CMs have the advantage to describe and capture the decision makers knowledge in a comprehensive manner, hence the modeling is closer to natural language. However their limitation is that they do not model uncertainty with variables. So, they allow only limited forms of causal inferences. On the other hand, defining the conditional probabilities in BNs from experts is not an easy task, especially when the domain of variables is large. Thus, in order to reduce the complexity of the elicitation step to solve a decision problem and make inferences in the model, we propose to use the new cognitive map formalism for the elicitation step and to transform it into a Bayesian causal map (BCM) for the reasoning step. To construct the BCM, the procedure is the following:

1) Derive the CM of the concerned problem. In the studied problem, the CM is derived from the judgments and beliefs of several actors (fishermen) following the new formalism. 2) Construct the structure (Qualitative component) of the BCM which should be a directed acyclic graph (DAG).

As the semantic of the arcs in the two models is the same, the structure of the BCM is based on the constructed cognitive map. 3) Define the associated parameters (Quantitative component) which correspond to probability distributions. This step requires some operations in order to capture the semantic of causal values. We describe the procedure to construct the structure and parameters of the BCM in the following two subsections.

A. Construction of the structure of the BCM

The structure of the BCM describes the relationships between the variables of the problem. It is represented by a DAG. As we construct the BCM from a cognitive map, its structure corresponds to the structure of the CM with some modifications. The authors in [START_REF] Shenoy | A bayesian network approach to making inferences in causal maps[END_REF] proposed a procedure to obtain the structure of the BCM from a cognitive map. This procedure concerns particularly the following points:

1) Conditional independencies: In a CM, the existence of a relation between two variables induces that these variables are dependent. However, the absence of a relation between two variables does not imply independence (i.e., lack of dependence) between these two variables. In BN, the absence of a relation between variables induces that some variables are conditionally independent on other variables. If we have a sequence of variables, an absence of an arrow from a variable to its successors in the sequence implies conditional independence between the variables. Thus, when defining the structure of the BCM from the constructed CM, it is important to ensure the nature of relations between variables of the studied decision problem because this allows to specify the relevant information in making inferences.

2) Direct and indirect relationships: Generally, experts draw direct links between concepts even if they are influenced through another concept. Namely, they take into account the fact that the concepts are linked but not how (this is also observed in our problem where fishermen use often direct links). In BN, a relationship between variables is direct if they are directly linked with an arrow and is indirect if the variables are conditionally independent. So, distinguishing between direct and indirect relationships is important namely in order to determine the conditional independencies between variables of the problem. If a given variable affects a second variable only through a third variable, then an arrow from the first variable to the second is redundant and increases the complexity of the representation.

3) Circular relations: Contrary to BNs, which are acyclic graphs, in a CM, the relations can be circular. The existence of circular relations can be due to two main reasons [START_REF] Ackermann | Making Strategy[END_REF], [START_REF] Nadkarni | A causal mapping approach to constructing bayesian networks[END_REF]. First, they may represent mistakes that need to be corrected (in this case, users are reasoning deductively, i.e. from causal to effect concepts and abductively on some concepts, i.e. form effects to causal concepts). Second, they may represent a dynamic structure of the map. Namely, they represent dynamic relations between variables over time. The solution in such cases consists to separate the variables into two different time frames. Namely, some relations in the cycle (or loop) belong to the present time frame while others belong to a future time frame [START_REF] Nadkarni | A causal mapping approach to constructing bayesian networks[END_REF]. In Section V, we give some examples concerning theses elements when we define the structure of the BCM of the case study.

B. Constructing the parameters of the BCM (generating CPT)

Once the structure of the BCM is defined, we have to build the conditional probabilities tables (CPT) associated for each variable. In [START_REF] Nadkarni | A causal mapping approach to constructing bayesian networks[END_REF], the authors ask experts about the elicitation of the CPTs. They do not consider the causal values of the CM and therefore requires another elicitation step from experts. In this paper, we propose to take advantage of the causal values in the CM to generate directly the probabilities of the BCM. Avoiding a time consuming and tedious work especially as the notion of probability may be not intuitive of understand. Deriving the conditional probabilities tables from causal values requires some operations in order to keep the semantic of these later on the one hand and to respect the conditions of probability theory on the other hand. Assume that Z is an effect concept and X, Y are the causes ones, i.e., X and Y are the parents of Z. When defining the CPT of the BCM, the semantic of the causal values should be preserved. For example if the positive effect of parents of Z is greater than the negative one, this should be traduced as P (Z = + | X, Y )> P (Z = -| X, Y ). The proposed procedure is described in the following: 1) Associate to each variable in the BCM its corresponding states: This consists in determining the domain of each variable. In our case, we consider that each variable has two states (Decrease (-), Increase (+)). Theses two states allow to represent the negative or positive causal relation given in the constructed cognitive map. Namely, the objective in the BCM is to compute the probability that an effect variable (or child variable) increases or decreases given the cause variable (or parent variable) decreases or increases.

2) Associate a priori probabilities to variables without parents: If we have informations about the problem, we can introduce them in the model and they will be represented as probabilities. In our case, as there is two states for each variable, the associated a priori probability for each state is 0.5 by default (there is no reason to specify another distribution). In addition, although we do not associate any distribution, there is no impact on the inference process since regarding theses variables, we can introduce any observations.

3) Building CPT for variables having parents: In our method, causal values of the cognitive map are elicited from the experts. Thus, we directly use these values to obtain the CPT. The procedure is described in the following:

Let x a variable for which we compute the CPT and let y ij the parents of x. For each configuration (for example, the variable having 3 parents, the corresponding CPT contains 8 configurations):

• y i-: are parents with a negative effect. E -corresponds to the sum of the negative effects concerning y i-. • y j+ : are parents with a positive effect. E + corresponds to the sum of positive effects concerning y j+ .

To Example 1: Let us consider the cognitive map of Figure 1 where the variable QSF has three parents (ASP , Imp and N F ). The aim is to generate CPT of QSF regarding its parent variables. Namely, we have to compute the probability that QSF increases or decreases given the 8 possible configurations of ASP , Imp, and N F (for example, the configuration where ASP , Imp, N F all increase or all decrease). We illustrate the calcul with the configuration ASP , Imp and N F all increase. So, we have to compute P (QSF |ASP =+, Imp=+, N F =+). Namely, we compute P (QSF =+|ASP =+, Imp=+, N F =+) and

P (QSF =-|ASP =+, Imp=+, N F =+).
Concerning this configuration (i.e. ASP , Imp and N F all increase), we have y i-= (ASP , IM P ) and The results concerning the CP T of variable QSF concerning the 8 configurations are given in Table I.

y j+ = (N F ). So, E -= -3 +-2 = -5 and E + = +2. We obtain | E -| > | E + |, hence P (QSF = - |ASP =+, Imp=+, N F =+) > P (QSF = + |ASP =+,

V. THE CASE STUDY: SHELLS FISHING PROBLEM

In this section, we apply our approach on a real problem which concerns the shells fishing activities. We firstly give the constructed CM and then we transform it into a BCM following the proposed procedure.

A. A cognitive map for the shells fishing problem

In order to construct the CM, interviews are conducted with fishermen. These latter are asked to identify the concepts that might influence negatively or positively the fishing activities. The CM concerning this problem is given in Figure 4. The map contains 15 variables representing fishing activities (Shellfish stock (QSS), Quantities of fished shells (QSF), Hatchery Policy (HP), Hatchery Activity (HA) which appears to be an important parameter for the dredging activity, Fishing Activity (FA)), environmental factors (Quality of Water), Fishing Conditions (Fishing Material, Quality of relationship between fishermen, Importation, Number of Fishermen, Control, Respect of Regulation) and other variables as Fraud, Selling Price and the presence of a toxin called Amnesic Shellfish Poisoning (ASP) which influences negatively the fishing activity in general.

B. Construction of the BCM for the studied problem

In order to analyze and study the impact of the variables on the fishing activities, the original map, shown in Figure 4, was used to construct a BCM. We first explain how the structure (i.e., the qualitative component) of the BCM is obtained and then we provide the final BCM with associated conditional probabilities tables to variables.

1) The structure of the BCM: As we observe in Figure 4, the constructed CM contains some circular relations, direct and indirect relations, etc. In order to construct a BCM from this CM, some relations are added and others are removed. We give here some examples of relations that are changed in the constructed BCM (Figures 5 and6).

The first example of change concerns direct and indirect relationships between variables which implies that an arc between two variables in the network should represent a direct cause-effect relation only. Hence, in the constructed BCM, we consider that the variables Control, Fraud and Respect of Regulation do not have a direct effect on Quantities of fished shells. We modify this relation where Control has a direct effect on Fraud, which affects Respect of Regulation and then Quantities of fished shells. In the original map, Importation affects directly Quantities of fished shells and there is also a direct link from Selling Price to Quantities of fished shells. In the modified cognitive map (see Figure 5), the relation between Importation and Quantities of fished shells is indirect since the influence is obtained through Selling Price. Thus, the arrow from Importation to Quantities of fished shells is removed.

The second example of change concerns conditional independencies: in the constructed BCM (see Figures 5,[START_REF] Finn | Bayesian Networks and Decision Graphs[END_REF], the arrow between Hatchery Activity and Number of Fishermen is removed. This implies that Hatchery Activity impacts Number of Fishermen through Shellfish stock. Number of Fishermen is conditionally independent on Hatchery Activity given Quantities of shells in stock. If we have complete information about shellfish stock, any additional information on Hatchery Activity would be relevant in making inferences for Number of Fishermen. We have also the same change concerning the variable Quality of relationships where the arrow from this variable to Fishing Activity is removed because the influence between these two variables is presented through Quantities of fished shells. The arrow from ASP to Fishing Activity is also removed, they are considered as conditionally independent variables given Quantities of fished shells. Another example of change concerns circular relations where a new concept (Shellfish stock (t+1)) was added to the constructed BCM in order to solve the problem of circularity and represent the dynamic relations between the variables across time frames. The dynamic relation is represented from Shellfish stock (t) to Quantities of fished shells and then to Shellfish stock (t+1).

As we observe in the BCM of Figure 5, some variables are also added (Fishing conditions) in order to simplify generating the CPTs. But we point out that this do not change the result if these variables are not added.

Once the map is modified and re-organized, the conditional probability tables have to be determined. The CPT were generated using the weight (negative or positive) of links in the CM by applying the procedure described in Subsection IV-B. We use Netica software [START_REF] Norsys | Netica application, norsys software corp[END_REF] to construct the model, introduce the probabilities associated with each variable and make probabilistic inferences. Figures 5 and6 show the constructed BCM with different observations for each case.

C. Some scenarios analysis

The objective of building the BCM consists firstly to evaluate the fishing activities by analyzing the state of some variables (for example Quantities of fished shells, Shellfish stock, Hatchery Activity) regarding observations about some facts (for example Fishing conditions, existence or no of ASP, Importation, Quality of relationships between fishermen, etc.). And secondly to diagnose causes given an effect. For example, what are the factors that cause increase or decrease in Fishing Activity.

First scenario: Figure 5 shows the first scenario regarding some observations (variables on grey color). Applying propagation in the BCM, the probabilities of the rest of variables are updated.

Results of the first scenario show that when ASP and Importation increase and Hatchery Policy decreases, the probability that all the variables related to Fishing Activity (i.e., Quantities of fished shells (QFS), Fishing Activity (FA), Hatchery Activity (HA), shellfish stock (QSS(t) and QSS(t+1)) decreases is more than 0.5. Which explains the importance of these variables in the Fishing Activity. The obtained result in the BCM means that the impact concerning these observations is negative on some variables (the probability of each of the influenced variable decreases is more than 0.5) which is also represented in the original cognitive map (when ASP increases, the impact on some variables is negative (-3), when Imp increases, the impact is also negative (-2), and when HA decreases, the impact is also negative (-2)).

Second scenario: In the second scenario which concerns the diagnosing case. We introduce only one observation about the Fishing Activity where P (F ishing Activity=Decrease)=1. The probabilities of the rest of variables are updated (see Figure 6).

As it is shown in Figure 6, the probabilities associated to the state (Increase) of all the variables that influence negatively on most variables are greater than 0.5. And the probabilities associated to the state (decrease) of all the variables that influence positively on most variables are greater than 0.5. For example, when ASP increases, it influences negatively (-3) on Hatchery Activity and Quantity of shells fishing. After introducing observation about Fishing Activity, we obtain P (ASP = increase) >0.5, which confirms that the higher the ASP the lower the Quantity of fishing shells. This shows that the constructed BCM represents the initial judgments of the cognitive map, and it allows reasoning (diagnosis, inference).

Introducing different observation in the model regarding some variables as ASP, Importation, the model seems well established. We conclude that the proposed method is efficient, and this allows to analyze and understand the impact of the different variables.

VI. CONCLUSION

Solving a given decision problem using the CM or BN requires expert knowledge and judgements to determine the variables of the problem and influences between theses variables. However, using a CM to construct the model seems more natural than using BN because the modeling process consists only in providing the list of variables and the nature of influence (positive or negative). Using a BN requires more efforts from experts since they should take into account the uncertainty concerning the states of variables and the probabilistic nature of influences. Once the model is built even if we use the CM or BN, the objective is reasoning about the problem. BNs are a well established method and they offer efficient algorithm's for applying inferences, learning and tools for the construction of the network. However, CMs present some limitations since they allow only some forms of inferences because of not modeling uncertainty.

In order to facilitate of the modeling process and making inferences, we propose in this paper to take advantage benefits of the two models, i.e., BNs for the reasoning process and CMs for the elicitation process. We propose to firstly build the CM and then transform it into a BCM which combines causal modeling techniques and Bayesian probability theory. The structure of the obtained BCM corresponds to the one of the constructed CM from experts with some modification regarding the direct, indirect relations, circular relation and dependency between variables. The parameters of the BCM are obtained from the associated causal values in the CM.

We illustrated the proposed approach on a real decision problem which concerns the analysis of shells fishing problem. We conclude that using cognitive map is important because it allows to have the perception of fishermen. However, concerning the reasoning process, the BCM allows to analyze their perception. BCM also allows to revise the model in terms of variables, their influences and acquire some experience for elicitation. A future work concerns the fusion of cognitive maps because in our studied problem, several fishers can be interviewed about the same problem and each one has its own view about it.

Fig. 1 .

 1 Fig. 1. A simple example of cognitive map.

Fig. 2 .

 2 Fig. 2. An example of Bayesian Network.

Fig. 3 .

 3 Fig. 3. An example of the new cognitive map formalism.

  Imp=+, N F =+) and α = 2/5 = 0.4. P (QSF = -| ASP = +, Imp = +, N F = +) = 1/(1+0.4) = 0.71 and P (QSF = + | ASP = +, Imp = +, N F = +) = 1-0.71=0.29.

Fig. 4 .

 4 Fig. 4. The cognitive map for the shells fishing problem.


Michele Trevisiol

Jonathan Delhumeau
email: jonathan.delhumeau@inria.fr

Hervé Jégou
email: herve.jegou@inria.fr

Guillaume Gravier
email: guillaume.gravier@irisa.fr

In this paper, we describe our approaches and their results as part of the MediaEval 2012 Placing Task evaluation. We present two different tag-based techniques. Both first preselect one or several geographic area of interest and then perform a deeper analysis inside the selected area(s) to return the coordinates more likely to be related with the input tags. In addition, we also implement a content-based method that uses aggregated local images descriptors (VLAD) to find the video's visual nearest neighbors and infer its coordinates. In this work we do not use gazetteers or any other external information.

INTRODUCTION

The goal of the Placing Task of MediaEval 2012 Benchmark [START_REF] Adam | Working notes for the placing task at mediaeval[END_REF] is to retrieve as accurately as possible the location, in terms of latitude and longitude, of a set of Flickr videos. We can exploit information such as visual content, metadata, social information, users' social graph and users' previously uploaded content. For this purpose, a large trainingset of geo-annotated Flickr images and videos is available.

METHODOLOGY

Our approach uses all the available information, however, our method relies mostly on tags analysis. Our idea is to identify tags that are geographically descriptive, discarding the ones likely to be irrelevant. First, we apply a preprocessing step in order to filter out the noise commonly present in the tags. Then, two different techniques were implemented: one based on simple text matching, and one based on a weighting scheme. We apply different methods in cascade: if a method does not find predictions, the following may be able to do it. a) system tags technique (Sec. 2.2 and 2.3), b) user's upload history, social information or home town (Sec. 2.4), c) content-based matching (Sec. 2.5), d) prior-location (Sec. 2.4).

Tags Pre-Processing

In order to work with a clean set of tags (T ctrain), we perform a few pre-processing steps. First standard steps such as removal of spaces, accents, etc. We also discard all the numeric tags (almost never relevant) and remove numeric char-MediaEval 2012 Workshop, October 4-5, 2011, Pisa, Italy acters from the alphanumeric tags. Then we built a basic stop-word dictionary containing common words (e.g. travel, birthday, cat, geotag) and names about the device with which the photos were taken (e.g. camera, iPhone, Canon). Some videos are annotated with machine tags (mtags)1 , i.e. one or more tags that Flickr recognized as a location (usually a country name, sometimes also the city name). We extract all of them in order to exploit their information separately in our tags techniques.

Basic Method (1st run)

For the first method, we filter the tags based on their geographic spread. For each tag ti we compute the term frequency tft i among all the tags, and the average Haversine distance avgDt i among all the coordinates of the video/image in which it appears. We filter out all the tags that do not respect the following condition:

∀ti ∈ Ttrain, ti ∈ T ctrain ⇐⇒ tft i ≤ 50, avgDt i ≥ 200.
We consider the problem as a classic Word-Document task in information retrieval. We consider each training datum, image or video, as a geo-annotated document made up with tags instead that words (in this step we are considering only training data with tags). We merge all the documents associated with the same set of tags, collecting all the associated coordinates. This way we obtain for each document a list of coordinates with frequency. A test-set video is represented by Vi = {mi}, {ti}, ui where {mi} is the set of mtags, {ti} is the set of tags and ui the user id. If the video contains mtags we retrieve all the documents where there is at least one common mtag, otherwise we do the same with tags. Then, we count how many time individual (m)tags appear in each document. Finally, we obtain a ranked list of documents, each of them with a list of candidate coordinates. We select the document with the highest score (if there is more than one with this score, we pick all of them), and we choose the medoid of all the associated coordinates (i.e. the coordinates minimising the average distance to all the others).

Weighted Method (2nd run)

This method directly analyses the relationship between tags and coordinates, taking into account the weight of each tag. The idea is to first determine the approximate area in which the video is likely to belong, then to find the most probable coordinates from the known locations in that area. To do that, first we define the areas and divide up the training set by quantifying the coordinates on a square grid of 0.1 • . We then compute a weighted co-occurrence matrix associating each tag with the areas it appears in (allowing us to select the most likely areas). For each area we also compute another weighted matrix associating the tags with coordinates (allowing us to select the most likely coordinates).

The initial tag weights are determined using a method similar to the one in Section 2.2, but instead of discarding tags we assign them one out of four levels of importance. We manually defined the following thresholds identifying how geo-descriptive a tag is. ∀ti ∈ Ttrain: To improve performance, we then re-weighted the tags with a feature weighting algorithm. After testing both TF-IDF and BM25, we chose the latter which performed better (confirming the results of Whissell et al. [START_REF] Whissell | Improving document clustering using okapi bm25 feature weighting[END_REF]). Those new weights are smoothed using signed SQRT (generalizing to textual features the results of Jégou and Chum [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF] on visual features). Finally, we normalize the weights with L2-norm and apply a whitening step in order to make the data less redundant (also described in [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF]). Each query vector is first multiplied by the weighted tagarea matrix to find the most probable area (if several have the same score, we keep them all). Then the query vector is multiplied by the weighted tag-coordinates matrix for this area to find the most probable location. In case of tied scores at this point, we choose the medoid.

wt i =        -1 if tft i > 100K or avgDt i < 0.

User-Based Location Estimation

For some test video no relevant tags were associated. To handle these cases we implemented different solutions. For each user with images/videos in the training-set, we pick a pre-computed user location, i.e. the most frequent location for his content (or the medoid of the most frequent ones). For the others, we go through all of his social connections to find the user locations of all of his contacts and choose the medoid. If this information is not available either, we use his home town. If all else fails, we choose the prior location which is the medoid of all the coordinates in Ttrain.

Content-Based Method (4th run)

This method is based solely on the visual content. For this purpose, and for each the provided keyframes, we first compute our own descriptors, selected for their good results for image retrieval. Those descriptors are based on normalised and whitened (local) SIFT descriptors [START_REF] Jain | Hamming Embedding Similarity-based Image Classification[END_REF] aggregated into a (global) VLAD descriptor [START_REF] Jégou | Aggregating local image descriptors into compact codes[END_REF], which are further dimensionally reduced, whitened and normalised [START_REF] Jégou | Negative evidences and co-occurrences in image retrieval: the benefit of PCA and whitening[END_REF]. The descriptors for each of the keyframes in the training videos are indexed using Product Quantization [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF]. We then do an approximate nearest neighbours search for all the test video keyframes. From this frame-to-frame list of nearest neighbours we deduce a video-to-video list of potential matches by keeping only the best scores for each video. Finally, from this list of candidate videos we get the corresponding list of coordinates and keep the medoid.

EXPERIMENTS

The results of our experiments are shown in Figure 1 and in Table 1. The algorithm described in Section 2.3 is outperforming all the others in all the evaluation radius except for the first kilometer. Indeed, for the smaller radius the most accurate method is the one presented in Section 2.2.

CONCLUSIONS AND FUTURE WORK

One reason for the bad start of the method in run2, may be due to the coordinates partitioning method, as selecting the wrong area in the first step makes it hard to find a coordinates closer than 1km. Therefore performance in the smaller radius might be improved by partitionnig the coordinates by a clustering technique like K-Means. Integrating a gazetteer might also help improve overall performance.

Figure 1 :

 1 Figure 1: Cumulative correctly detected locations: rate of video founds in a radius of x km.

  2 10 if tft i ≥ 200 and 10 ≤ avgDt i ≤ 50 5 if tft i ≥ 150 and avgDt i ≤ 70 1 otherwise

Table 1 :

 1 Percentages of correctly detected locations.

	radius(km)	run1(%)	run2(%)	run4(%)
	1	23.36	17.22	0.74
	10	34.51	38.28	1.29
	100	41.37	49.86	2.15
	1000	56.10	65.95	18.22
	10000	89.22	93.07	85.53

http://www.flickr.com/groups/api/discuss/72157594497877875/

ACKNOWLEDGMENTS

This work was partially funded by OSEO, French state agency for innovation, in the framework of the Quaero project and by Grant TIN2009-14560-C03-01 of the Ministry of Science and Innovation of Spain. Furthermore, we would like to thank Vincent Claveau for his helpful suggestions.