Matthieu Moy

Parallel Programming with SystemC for Loosely Timed Models: A Non-Intrusive Approach

The SystemC/TLM technologies are widely accepted in the industry for fast system-level simulation. An important limitation of SystemC regarding performance is that the reference implementation is sequential, and the official semantics makes parallel executions difficult. As the number of cores in computers increase quickly, the ability to take advantage of the host parallelism during a simulation is becoming a major concern. Most existing work on parallelization of SystemC targets cycleaccurate simulation, and would be inefficient on loosely timed systems since they cannot run in parallel processes that do not execute simultaneously.

We propose an approach that explicitly targets loosely timed systems, and offers the user a set of primitives to express tasks with duration, as opposed to the notion of time in SystemC which allows only instantaneous computations and time elapses without computation. Our tool exploits this notion of duration to run the simulation in parallel. It runs on top of any (unmodified) Sys-temC implementation, which lets legacy SystemC code continue running as-it-is. This allows the user to focus on the performancecritical parts of the program that need to be parallelized.

I. INTRODUCTION

Systems-on-a-Chip are complex systems involving dedicated hardware components and one or several processors. Because of time to market pressure, it is not possible to wait for the physical chip to develop the software, hence the developers need simulators, or virtual prototypes, earlier in the design flow. These prototypes need to be fast enough to make it possible to run complex applications, and must expose enough details of the hardware to allow non-portable software to run. The RTL level of abstraction is detailed enough, but far too slow, and available too late in the design cycle, hence a new level of abstraction called Transaction Level Modeling (TLM) has been introduced. We are interested in the SystemC [START_REF]IEEE 1666 Standard: SystemC Language Reference Manual, Open SystemC Initiative[END_REF] implementation of TLM.

There are several sub-levels of abstraction within TLM depending on the target usage: if the virtual prototype is meant for performance evaluation, it needs to be precise with respect to timing (either cycle-accurate or approximately timed). On the other hand, if only the functional correctness is important, timing can be relaxed considerably. TLM allows a purely untimed coding style, as well as a loosely timed (LT) coding style where the behavior is timed only if the timing is needed for the functionality. For example, a loosely timed model of a timer will usually be timed properly, but most computations can be considered instantaneous. This paper has been partially supported by the French ANR project HELP (ANR-09-SEGI-006).

Although SystemC represents concurrent systems, it should be noted that timing and concurrency in SystemC are simulated, and the actual execution is usually sequential (The SystemC standard imposes co-routine semantics). Running the simulation in parallel is needed to take advantage of today's machines, and SystemC's sequentiality could become a major performance bottleneck in the future. Many approaches have been proposed for SystemC parallelization, but most of them are only able to run processes that run at the same simulation cycle, and hence apply only on cycle-accurate systems.

As opposed to this, the parallelization approach we propose targets loosely timed systems. We present a programming model in which processes can not only execute instantaneous tasks or wait statements, but also express the notion of duration, i.e. specify the start and end date of the computation and let the scheduler freely spread it across time. These tasks with duration are executed in parallel with the SystemC scheduler.

This approach is implemented in a library, that runs on top of an unmodified SystemC kernel (including proprietary ones that cannot be modified). Also, this means that legacy code will continue running with our approach, although they will not automatically benefit from parallelism. The user can identify performance-critical parts of the system, and focus on them to parallelize the program (adding synchronization as required).

The paper is structured as follows: Section II discusses related works. Section III presents the main contribution: the during tasks principle and implementation, for which Section IV give experimental results. Section V is the conclusion.

II. RELATED WORK

As the official semantics for SystemC is to use co-routine semantics, the natural way to execute a SystemC program is to execute it sequentially. To take advantage of the parallelism of the host machine, it is tempting to run SystemC threads in parallel. The SystemC standard allows this, "provided that the behavior appears identical to the co-routine semantics" [START_REF]IEEE 1666 Standard: SystemC Language Reference Manual, Open SystemC Initiative[END_REF]. This implies two constraints on a parallel implementation:

1) It should not change the order in which processes are allowed to be executed. In particular, the simulated time imposes an order on the execution of processes. 2) It should not introduce new race conditions. For example, two SystemC processes may safely execute x++ on a shared variable, but running two such processes in parallel cannot be allowed.

Approaches for parallel execution of SystemC programs can be classified depending on the way they deal with these constraints: conservative ensure them by construction, while optimistic approaches relax them, ideally with a verification and rollback mechanism to correct them after the fact.

A. Semantics-Preserving Parallelization

An ideal conservative approach would preserve the official semantics completely. To solve problem 1 above, one can introduce parallelism within a δ-cycle (i.e. within one iteration inside a simulation instant), but keep a global synchronization barrier between each δ-cycle. Since the order of execution within an evaluation phase is unspecified in SystemC, it is correct to run processes in any order.

To solve problem 2, one needs to ensure that two processes accessing the same variable will never be run in parallel. This can be done structurally, under the assumption that a process will only access variables declared within its own module. It is then sufficient to ensure that at most one process is running within each module. SystemCASS [START_REF]SystemCASS[END_REF] is an example tool using this assumption to perform a dependency analysis (for static scheduling). Unfortunately, communication using TLM break this assumption: TLM communication channels transport transaction through function calls, hence the code processing a transaction in a target module is executed in the context of the initiator module. In particular, the natural implementation of a RAM makes it a shared array between all components accessing it.

Another option is to statically analyze the code of the processes to detect accesses to shared variables. [START_REF] Bouzouzou | Accélération des simulations de systèmes sur puce au niveau transactionnel[END_REF] proposes an approach to parallelization of SystemC based on a dependency analysis performed on a SystemC-transition (i.e. piece of code executed between two wait statements) basis. [START_REF] Chen | Out-of-order parallel simulation for ESL design[END_REF] applies similar static analysis for SpecC. Scoot [START_REF] Blanc | Race analysis for SystemC using model checking[END_REF] proposes a finer analysis using model-checking (applied to scheduling and model-checking, not to parallelization). These approaches are heavyweight since they require a static analysis of arbitrary C++ code, and require the complete source code of the model to be available. The efficiency of these approaches is disappointing on TLM models for which a few target components create a synchronization bottleneck (back to our RAM example, two processes that may access the RAM never be executed in parallel).

B. Parallelism within δ-cycles

A second category of approaches is to be conservative with respect to problem 1, but to leave it up to the user to deal with problem 2, by avoiding shared variables, and using proper synchronization and locking when needed.

[6] actually distributes the simulation over several machines, running one SystemC scheduler on each node. The first version enforced a global synchronization at each δ-cycle, and further optimizations [START_REF] Combes | Relaxing synchronization in a parallel SystemC kernel[END_REF] allowed relaxing this synchronization by computing the next simulated time locally on each nodes.

Another approach is to modify the SystemC kernel to allow a parallel simulation [START_REF] Schumacher | ParSC: synchronous parallel SystemC simulation on multicore host architectures[END_REF]. The scheduler maintains a set of runnable processes, and several threads run an evaluation phase that pick processes from this set and run them, finishing the evaluation phase with a global synchronization barrier. This work is currently focused on performance, but leaves the responsibility of protecting the atomicity of accesses to shared data-structure to the SystemC processes. Similar work propose some performance optimizations using various load-balancing techniques like work-stealing, work-sharing or manual grouping [START_REF] Chandran | Parallelizing SystemC kernel for fast hardware simulation on SMP machines[END_REF], [START_REF] Khaligh | A dynamic load balancing method for parallel simulation of accuracy adaptive TLMs[END_REF] to improve the cache usage. To avoid having to use a modified SystemC kernel, [START_REF] Huang | Scalably distributed SystemC simulation for embedded applications[END_REF] allows running a distributed simulation on top of SystemC. It runs the δ-cycles one by one, calling sc_start(SC_ZERO_TIME) repeatedly in the main loop of the distributed engine.

C. Parallelism Across Simulated Instants

All the works presented above have in common the fact that they parallelize the content of δ-cycle, but cannot run in parallel processes that should be executed at different simulated times. In other words, they require a simultaneity between processes to take advantage of parallelism. This is appropriate for cycle-accurate simulation, where clock ticks usually wakes up many processes at the same time. But higher levels of abstraction tend to eliminate clock, and deal with quantitative time instead. Figure 1 shows an example modeling a system performing two computations in parallel. Computations that take some time are usually modeled by instantaneous computations followed by a SystemC wait. For example, TLM-2's temporal decoupling [START_REF]IEEE 1666 Standard: SystemC Language Reference Manual, Open SystemC Initiative[END_REF] produces this effect (the call to wait is done when synchronizing a process's local clock with the simulation time). In simulation, this program will run without ever having two processes runnable at the same time. In the presence of loose timing annotations (e.g. wait(X±50%)), the situation is even worse since the argument to wait becomes a random value. For such systems, semantics-preserving approaches are even harder. The scheme proposed in [START_REF] Chen | Out-of-order parallel simulation for ESL design[END_REF] performs a static analysis for processes that may be executed at different instants, but in SystemC/TLM programs with a shared bus, target components will still create conflicts in many cases, and this approach requires the availability of the whole source code. The alternative is to use optimistic approaches, i.e. one processes should be allowed to advance its local time without waiting for other computations to terminate. Maintaining the same execution order as the reference semantics becomes intractable, hence optimistic simulation either (a) requires a violation-detection together with a rollback mechanism or (b) deliberately accepts some order violations, even though it can control them with some logical clock mechanism in addition to the quantitative simulated time. Approaches in category (a) have been successfully applied to VHDL simulations, but the case of SystemC is much harder to deal with: since the user can call arbitrary C++ code and system calls, a rollback mechanism is not implementable in general.

One solution in category (b) is proposed in [START_REF] Mello | Parallel simulation of SystemC TLM 2.0 compliant MPSoC on SMP workstations[END_REF], introducing the TLM with Distributed Time (TLM-DT) abstraction level and the associated parallel simulator. In TLM-DT, processes do not rely on the SystemC simulated time, but manage a local clock, that is synchronized with other components regularly (on every communication, and using null messages when a predefined time quantum elapsed without actual communication). This way, ordering violations can happen only with processes running with a difference of at most the time quantum. This approach does not need simultaneity for parallelization, and relaxes the synchronization barrier, but still enforces it every time quantum (through null messages). It requires a particular modeling style and forbids some SystemC primitives, hence is not applicable on legacy code. It is designed to be efficient on approximately timed model, but not on loosely timed ones.

Another approach relying on the notion of time quantum is presented in [START_REF] Khaligh | Efficient parallel transaction level simulation by exploiting temporal decoupling[END_REF]. It performs a distributed simulation similarly to [START_REF]A conservative approach to SystemC parallelization[END_REF], but instead of performing a synchronization barrier for every δ-cycle, the authors propose to force processes to execute only on a multiple of the quantum.

Tasks and Duration: An experiment of transaction-level modeling outside the SystemC world is jTLM [START_REF] Funchal | jTLM: an experimentation framework for the simulation of transaction-level models of systems-on-chip[END_REF]. The management of simulated time is different in that jTLM provides a notion of "task with duration" [START_REF]Modeling of time in discrete-event simulation of systems-onchip[END_REF]. Instead of modeling such task as an instantaneous computation followed by a wait, the user can specify the duration of the task, and let the scheduler spread the computation over the specified period of time. The example of Figure 1 becomes the one in Figure 2. This notion of duration and overlap is interesting for parallel execution of models with a coarse timing granularity. The coarsest the task are, the less likely it is for their start and end points to be simultaneous, but the most likely it is for them to overlap. Unlike cycle-based approaches, the efficiency will therefore increase with the size of tasks. An obvious limitation of this approach is that jTLM is not compatible with SystemC, hence unable to use legacy SystemC code.

III. TASKS WITH DURATION IN SYSTEMC

None of the approaches mentioned above can parallelize the execution of SystemC programs across instants safely and without changing the code. It does not seem realistic to target fully automatic parallelization for real-life TLM programs. Instead, our contribution is a new programming model that complements the one of SystemC and allows the programmer to solve the parallelization problem by using the new primitives on performance-critical parts of the program. The semantics is inspired from the one of jTLM, but the implementation is made as a library called sc-during (while jTLM implements tasks with a dedicated scheduler). It runs on top of SystemC, without modifying it. The library can be freely downloaded from http://sc-during.forge.imag.fr/.

A. Principle of Tasks with Duration

An example code using sc-during is shown in Figure 3. To use the API, a module derives from the class sc_during. The main primitive is the method during(d, f ) that takes a duration d and a function f to be executed as argument. This function can only be called from an SC_THREAD (i.e. not from an SC_METHOD), as it calls wait internally. The function f is passed using boost::function and can be either a pointer to function, or a method using boost::bind. f may not interact directly with SystemC (i.e. call wait or notify), but section III-B1 will present a way to perform such interactions. P p("p"); Q q("q"); sc_start(); return 1; }

Fig. 3. Parallelism With Duration in SystemC

The execution of this program is illustrated in Figure 4. It starts the normal way, using the SystemC scheduler and global simulated time. Once a call to during is encountered, the execution of the function passed as argument (e.g. P1, at t = 0 line 4) can be delegated to another operating system thread. The simulation will continue with other processes on the SystemC side, in parallel with the execution of P1. SystemC and P1 will join at t = 25 ms, i.e. either the SystemC simulation reaches 25 and waits for P1 to complete, or P1 terminates at t < 25. While executing P1 as a separate task, the SystemC scheduler continues its execution, executes wait(10, SC_MS); and reaches t = 10. Then, it encounters another call to during and launches Q1 in a separate task, just like it did for P1. At this point, the simulation can contain 3 OS threads: one for each task, and one running the SystemC kernel. As P1 and Q1 have an overlap in time, they can be executed in any order, or with any interleaving. On the other hand, the end of task Q1 predates the start of P2, so the scheduler ensures that Q1 is completed before starting Q2.

It is of course possible to have instantaneous computations too. Any code within a SystemC process and outside a call to during will run instantaneously, following the SystemC semantics and independently from the sc-during library (another way to create instantaneous tasks is during(SC_ZERO_TIME, f) which creates a separate task that must complete before the end of the next δ-cycle).

The sc-during library contains 4 different implementation of the notion of task with duration. We first illustrate the idea with the one called THREAD, which is straightforward and unoptimized. Figure 5 shows a simplified version of this implementation (more implementation details are needed to introduce other primitives in section III-B).

B. Synchronization and Time Modeling

The ideas presented up to now allow running a piece of code in parallel with a SystemC simulation, but up to now, the task can hardly communicate with the SystemC thread. In particular, it cannot call SystemC primitives like wait() and notify(), and shared variables between the SystemC thread would create race-conditions. In order to provide a complete programming model to the user, we need to introduce additional synchronization primitives.

1) Full Synchronization with SystemC: sc_call(): A during task may want to execute a piece of code within the context of the SystemC thread. This way, this piece of code will be allowed to execute SystemC primitives (e.g. wait, notify . . . ) the normal way, and to access variables shared with SystemC without specific locking or race condition (like two SystemC processes access shared variables).

The sc_call() API function does this: it is callable from a during task and takes a function as argument. The current task is blocked, and the function is scheduled to be executed next time SystemC allows it. The during task is unlocked once the function has completed its execution.

We provide two implementations for the scheduling of the function to be executed: In SystemC 2.2, we simply record the function to be called, and call it when the call to sc_core::wait associated to the task terminates. In Sys-temC 2.3, we use async_request_update() to schedule the execution during the next δ-cycle.

2) Controlling Time Elapse and Duration: extra_time() and catch_up(): Up to now, the only way to specify the duration of a task is to provide it as argument to the during() method. This is not always possible, since it would require knowing how long the computation done within the task would take, before executing it.

To solve this issue, the sc-during library provides the function extra_time(sc_time t), that can be called from a during task. This function increases the duration of the current task by t. In the implementation of the library, this means the wait statement line 4 in Fig 5 is actually inside a loop along the lines of while (remaining_time) wait(remaining_time);, and extra_time increments remaining_time with proper synchronization. An example is shown in Figure 6. This program will produce an output of the form (output is generated by the trace function defined line 1 which displays the current simulated time and a string): X ms: before extra_time Y ms: after extra_time 17 ms: done The semantics ensures that the duration of the task is the initial duration plus the sum of times accumulated with extra_time(), hence the last line 17 ms: done. Before the call to extra_time, the during task spans only over [START_REF] Blanc | Race analysis for SystemC using model checking[END_REF][START_REF] Khaligh | A dynamic load balancing method for parallel simulation of accuracy adaptive TLMs[END_REF], hence X ∈ [START_REF] Blanc | Race analysis for SystemC using model checking[END_REF][START_REF] Khaligh | A dynamic load balancing method for parallel simulation of accuracy adaptive TLMs[END_REF] is ensured. After calling extra_time, the task spans over [START_REF] Blanc | Race analysis for SystemC using model checking[END_REF][START_REF] Domer | Multi-core parallel simulation of system-level description languages[END_REF], hence Y ∈ [X, 17]. In general, the semantics of during tasks with extra_time is that a piece of code within the task can be executed at a simulated time t ∈ [s, s + d + e] where s is the starting time of the task, d is the initial duration, and e is the sum of the extra-time accumulated up to this point.

By default, time may flow freely during the execution of a during task. This may be problematic if the program relies on some fairness between a during task and the SystemC simulation. Take the example of a polling loop like while (!x) {}. In SystemC, such a loop which doesn't let time elapse will create an infinite loop, and will have to be rewritten while (!x) {wait(t);} (for some time constant t). Within a during task, it is possible to achieve a similar effect with while (!x) {extra_time(t);}. Unfortunately, while this piece of code creates a during task with an unbounded duration, it does not ensure that the SystemC simulated time will actually increase. The catch_up function may be used as follows to ensure fairness:

1 while(!x) { 2 extra_time(10, SC_MS); 3 trace("between"); 4 catch_up(); 5 trace("after"); 6 } If this code is executed starting at t = 0, in a during task whose duration is initially 0, it will produce an output of the form: X 1 ms: between 10 ms: after X 2 ms: between 20 ms: after with X 1 ∈ [0, 10] and X 2 ∈ [START_REF] Khaligh | A dynamic load balancing method for parallel simulation of accuracy adaptive TLMs[END_REF]20]. The simulated time after returning from catch_up is fixed to the duration of the task at this point.

Alternatively, the user can use the relaxed form catch_up(t), providing as argument a time t and that only ensures that the simulated time will advance until the difference between the current time and the end of the task is at most t.

C. Temporal Decoupling and Duration

Temporal decoupling is a technique standardized by TLM-2 to reduce the number of wait statements executed. The idea is to allow processes to maintain a local lock t local to model the fact that the process is "in advance" with respect to the SystemC time. Instead of using wait(d), processes increase t local by d (function annotate in Figure 7), and periodically call a function to actually perform the wait() statement (function synchronize in Figure 7). This synchronize function can be called whenever t local becomes greater than a predefined time quantum (a call can be inserted in annotate for instance), or before synchronization points [START_REF] Cornet | Separation of functional and non-functional aspects in transactional level models of systems-on-chip[END_REF]. The sc-during library can benefit from temporal decoupling. The primitives of Figure 7 can be re-written as Figure 8 when used inside (possibly unbounded) during tasks. This preserves the property that important actions (i.e. the ones after calling synchronize) are executed at the right SystemC time, and the computations calling annotate are modeled with the right duration.

D. Implementation

We gave in section III-A a sketch of the THREAD implementation for during tasks. The actual implementation is more complex since it needs to manage sc_call, extra_time and catch_up. We also provide several implementation of parallelism: POOL pre-allocates a set of threads and works in a producer-consumer scheme, ONDEMAND creates new threads as needed and re-uses them instead of deleting and re-creating them, and SEQ is a reference sequential implementation.

IV. EXPERIMENTAL RESULTS

A. Experimental Setup and Platform Synchronization

We experimented our approach on a SystemC model of an existing platform containing a CPU, a timer, a GPIO, a RAM and an interrupt controller (ITC), running on an FPGA, and executing an embedded software running Conway's Game of Life (the same C code is running on the FPGA and on the TLM platform). To illustrate parallelization of simulation, we added multi-processing capabilities to the system, adding N additional CPUs and ITCs. CPU0 delegates parts of the computation (slices of the image to compute) to other CPUs. It does so by setting a flag in RAM, and triggering an interrupt using the ITC associated to the CPU. Bus-communication is abstracted with a TLM-2 channel. Transactions (either read or write) are initiated by a component, routed through a Bus module towards a target module.

The most performance-consuming components are the CPUs, on which we are now going to focus. We use a simple ISS, but our approach would work equally well with any other SystemC module provided the approach has some notion of timing (possibly approximate). One ISS step takes a constant amount of time (PERIOD), hence we can basically count the number N of steps, and wait for N *PERIOD when synchronizing with SystemC time. We tried several strategies to choose when and how to synchronize:

The first one is called during_quant and is directly inspired from the notion of quantum. "Packs" of 5000 instructions are executed in a during task of duration d = 5000 * PERIOD. The second one, called during_sync, requires the user to explicitly set the synchronization points of the model (writing to some magic values in the addressmap), and is an application of Section III-C: we start a during task initially empty, call extra_time(5000 * PERIOD) every 5000 ISS steps, and call extra_time(N * PERIOD); N = 0; catch_up() at every synchronization point (i.e. before sending or waiting for an interrupt, within polling loops, . . . ).

The ISS triggers reads and writes on the bus, which triggers execution of handlers in the target modules. When these handlers do not call SystemC primitives, and if the dataaccess they perform are safe, we can let them run in the context of the during task. But for example, writing on ITC component may trigger an e.notify(), which cannot be run from a during task. When triggering a write transaction to such modules, the ISS wraps the bus access in an sc_call, so that the transaction be executed in the context of the SC_THREAD, like in the sequential version. We also wrap wait for interrupts in sc_calls. Most accesses to the bus are performed without synchronization: the bus component itself is thread-safe (no state variable except the addressmap, which is read-only during simulation), and memory access that do not require particular synchronization in the actual system are performed without synchronization in simulation.

B. Speedup and Scalability

We tested the scalability of the approach on two machines. The first one (Figure 9. Both graphs show the benefit of defining explicit synchronization points, as the strategy during_sync always gives a better speedup than the quantum-based one. This also illustrate the fact that sc-during targets loosely timed systems, since coarser granularities models give better performance (unlike most alternative approaches). For low numbers of CPU in the model, the speedup is almost optimal, it does not decrease significantly when parallelizing the model too much (i.e. instantiation more CPU in the model than physical CPUs). With a large number of processors, even on the 48 cores machines, we can notice that the speedup is smaller than the number of processors. While disappointing, this result is not so surprising since the during task need some synchronization with SystemC (some bus accesses being protected with sc_call). We can further optimize the platform by making the ITC component itself threadsafe (by using async_request_update()), and get 13% additional speedup in ONDEMAND implementation and 23% in THREAD implementation, on machine (b) with 60 threads.

It should be noted that the suboptimal speedups are not due to extra computation, but essentially to latency of synchronization. Our experiments show that the CPU time spent in the computation increase by less than 35% even for very loaded simulation (60 CPUs). Unlike approaches using busy-waiting, this means that our parallel simulation will remain efficient on multi-users machines.

The during_quant strategy has a slightly lower speedup when the parallelism is low, but stagnates (and even decreases for the ONDEMAND implementation) with a large number of threads, because OS threads need frequent synchronization with SystemC, which becomes the synchronization bottleneck. This problem can be solved by increasing the quantum. For example, by setting the quantum to 50,000 instructions (i.e. 1 ms) instead of 5000, we speed up the simulation in THREAD implementation by a factor of 3.7. With a quantum of 10 ms, we get back to the same performance as the during_sync version. This illustrates the potential difficulty of choosing the right quantum, and the advantage of explicit synchronizations.

V. CONCLUSION

We presented an approach for parallel execution of SystemC models. A deliberate choice of the approach is that we require the user to use new primitives, as the alternatives would either be inefficient or would break the SystemC semantics for existing code. We showed that our approach allows a significant speedup with a reasonable modeling effort. By providing primitives to express the notion of duration, we allow the user to create more parallelism in the model than cycle-based approach, hence can efficiently parallelize loosely timed systems.

Our approach works with any SystemC scheduler, it is a simple library whose primitives are called directly from the SC_THREAD, hence intrusion in the user code is minimal. We could in theory run our library on top of a parallel implementation of SystemC, although such setup has not been experimented. Running code in a separate OS thread limits the interactions with SystemC, hence the approach applies best to parallelize computation that do not interact with the rest of the simulation, but we also provide primitives to allow synchronizing with SystemC, hence communication with other processes (sc_call, extra_time and catch_up).

Further work include providing more tools for synchronization to the user. For example, we manually wrapped in sc_call some transactions, but the Bus component could do it automatically for user-defined address ranges. This approach can be compared with the SpecC approach, where the language reference allows parallelism within a component, but the communication channels act as monitors [START_REF] Domer | Multi-core parallel simulation of system-level description languages[END_REF].

  void P::compute() { P1(); wait(25, SC_MS); P2(); wait(12, SC_MS); } void Q::compute() { wait(10, SC_MS); Q1(); wait(13, SC_MS); Q2(); wait(11, SC_MS); } Fig. 1. Parallelism Without Simultaneity

void

  P_compute() { consumesTime(25){P1();} consumesTime(12){P2();} } void Q_compute() { awaitTime(10); consumesTime(13){Q1();} consumesTime(11){Q2();} } Fig. 2. Parallelism With Duration in jTLMThis way, tasks P1() and Q1(), although not simultaneous, have an overlap, hence can run in parallel.

Fig. 4 .

 4 Fig. 4. Execution of a Program with During Tasks

Fig. 6 .

 6 Fig. 6. Example Code Using extra_time(), and Execution Trace

1Fig. 8 .

 8 void annotate(sc_time d) { 2 t local = t local + d; Temporal Decoupling API within during Tasks

  (a)) has 4 Intel Xeon cores. The second (Figure 9.(b)) has 4 AMD Opteron-6176 processors, each containing 12 cores (total of 48 cores).

  (a) Execution on a 4 cores machines (b) Execution on a 48 cores machine

Fig. 9 .

 9 Fig. 9. Speedup Compared to SEQ for Different Implementation (average, min and max over 10 runs)


David Powell
email: david.powell@laas.fr

Jean Arlat
email: jean.arlat@laas.fr

Yves Deswarte
email: yves.deswarte@laas.fr

Karama Kanoun
email: karama.kanoun@laas.fr

Tolerance of design faults

Keywords: design-fault, software-fault, vulnerability, fault-tolerance, recovery blocks, N-version programming, N-self-checking components

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Faults introduced into a computing system during its development 1 are a major concern in any critical application. The first defense against design faults is of course to attempt to avoid their the occurrence in the first place by applying the techniques of fault prevention (i.e., "careful design") and fault removal (i.e., "verification and testing"). Such a fault avoidance strategy is the basic tenet of quality management, i.e., of "getting it right the first time" [START_REF] Crosby | Cutting the cost of quality; the defect prevention workbook for managers[END_REF] by building a system with zero defects. This is a laudable objective, but one whose satisfaction is difficult to guarantee with sufficient confidence, at least for non-trivial systems, when the conseqences of failure are extreme in either economic or human terms. In highly-critical applications, it is reasonable to assume that the system will indeed contain residual design faults and then apply fault tolerance (i.e., "diverse redundancy") and fault forecasting (i.e., "dependability evaluation") techniques so that it can be deemed to be dependable despite faults, i.e., to complement fault avoidance by a fault acceptance strategy [START_REF] Avizienis | Basic concepts and terminology of dependable and secure computing[END_REF].

This paper is primarily concerned with the tolerance aspect of fault acceptance, i.e., how to introduce so-called "diverse" redundancy into a system that can be managed in such a way as to decrease the likelihood of system failure due to residual design faults. We first give a brief history of this concept and then describe two contemporary studies concerning:

the tolerance of deficiencies in planning domain knowledge for robotics; -the tolerance of security vulnerabilities in commercial off-the-shelf operating systems for aviation applications.

A Concise History of Design-Fault Tolerance

In this section, we first give a brief overview of the main approaches that have been studied for building systems that can tolerate residual design faults and then summarize the substantial amount of work that had been devoted to evaluating the dependability that such design-fault tolerance techniques can procure.

To illustrate practical applications of the technology, we then describe two critical computer-based systems in which design-fault tolerance has been deployed.

Design-Fault Tolerance Techniques

There exist two radically different approaches to design-fault tolerance according to the goal sought:

to prevent the failure of a task from causing the failure of the whole system, -to maintain service continuity.

In the former case, one tries to detect an erroneous task as early as possible in order to suspend it and prevent propagation of error(s); this approach is often referred to as "fail-fast" [START_REF] Gray | Why do computers stop and what can be done about it?[END_REF][START_REF] Bartlett | Fault tolerance in Tandem computer systems[END_REF]. Error detection is provided by executable assertions relating to the data processed, the intermediate results, or the task outputs. The implementation of these assertions is based on a defensive programming style and error processing is generally implemented through exception handling. The second case supposes that one possesses at least one other component able to perform the task, that has been designed and produced separately from the same specification: the so-called design diversity [START_REF] Avizienis | Fault-tolerance by design diversity: Concepts and experiments[END_REF]. This latter approach is developed further in the following paragraphs.

The copies of a system produced in accordance with the design diversity approach are usually called variants. In addition to the existence of two variants, design-fault tolerance requires a decision maker (often referred to as the adjudicator ) providing a supposedly error-free result from the execution of the variants. The specification common to all variants must explicitly mention the decision points, i.e., a) when the decisions must be taken, and b) the data on which the decisions must be made, hence the data handled by the adjudicator.

The notion of software diversity for design-fault tolerance was formulated in the 1970's [START_REF] Elmendorf | Fault-tolerant programming[END_REF][START_REF] Randell | System structure for software fault tolerance[END_REF][START_REF] Avizienis | On the implementation of N-version programming for software fault tolerance during execution[END_REF]. It has been significantly used in critical systems to enhance safety (i.e., to provide a fail-safe behaviour) or availability (i.e., to ensure service continuity).

There exist three basic approaches for design-fault tolerance using design diversity [START_REF] Laprie | Definition and analysis of hardware-and-software fault-tolerant architectures[END_REF]: recovery blocks, N-version programming and N-self-checking software. These approaches can be seen as resulting from the application to the software of three basic types of error processing [START_REF] Avizienis | Basic concepts and terminology of dependable and secure computing[END_REF]]: backward error recovery, fault masking, and error detection and recovery.

In recovery blocks [START_REF] Randell | System structure for software fault tolerance[END_REF][START_REF] Anderson | Fault Tolerance -Principles and Practice[END_REF], variants are referred to as alternates and the adjudicator is an acceptance test applied to the results produced by the alternates. Thus, if the results provided by the primary alternate fail the acceptance test, the secondary alternate is executed and so on, up to the satisfaction of the acceptance test or the exhaustion of the available alternates, in which case the recovery block is considered as globally failed (still, a fail-safe behaviour is enforced).

For N-version programming [START_REF] Avizienis | On the implementation of N-version programming for software fault tolerance during execution[END_REF][START_REF] Avizienis | The N-version approach to fault-tolerant systems[END_REF], variants are referred to as versions, and the adjudicator casts a vote on the results provided by all versions. In this case, the decision is carried out cooperatively among the versions involved, instead of by means of an absolute check with respect to a pre-defined acceptance test.

N-self-checking software [START_REF] Laprie | Definition and analysis of hardware-and-software fault-tolerant architectures[END_REF] can be viewed as a hybrid technique based on the two previous ones. In this case, at least two self-checking software components (SCSC) are executed in parallel. Each SCSC can be made up of either the association of a variant and an acceptance test, or of two variants and a comparison algorithm. In the latter case, only one of the variants (main) is required to implement the expected function, the other variant can either implement the function with reduced accuracy, or compute the reverse function (whenever possible), or even simply operate on some intermediate results of the main variant as in the so-called certification path approach [START_REF] Sullivan | Certification trails for data structures[END_REF].

Recovery blocks and N-version programming have been extensively investigated in the literature and have both prompted numerous variations or combinations, such as consensus recovery blocks [START_REF] Scott | Fault-tolerant software reliability modeling[END_REF], distributed recovery blocks [START_REF] Kim | Distributed execution of recovery blocks: an approach to uniform treatment of hardware and software faults in real-time applications[END_REF] or t/(n-1) variant programming [START_REF] Xu | The t/(n -1)-diagnosability and its applications to fault tolerance[END_REF]. This trend of work has been further developed via the concept of Coordinated Atomic Actions (CA-actions) that provide a unified scheme for coordinating complex concurrent activities and supporting error recovery between multiple interacting components in distributed object systems. CA-actions integrate and extend two complementary concepts: conversations and transactions (e.g., see [START_REF] Randell | From recovery blocks to coordinated atomic actions[END_REF][START_REF] Beder | On applying atomic actions and dependable software architectures for developing complex systems[END_REF]). Although N-self-checking software has been less extensively studied in academic circles, it is nevertheless a rather common approach in operational systems [START_REF] Voges | Software Diversity in Computerized Control Systems[END_REF]. Typical examples will be provided in Section 1.3.

In the previous paragraphs, we have focused on different aspects of software design-fault tolerance. One can equally apply design diversity to provide protection against design faults affecting complex hardware components, such as processors. Accordingly, distinct processors can be used to implement the redundant channels (e.g., see [START_REF] Yeh | Dependability of the 777 primary flight control system[END_REF]).

Another option for coping with design faults is data diversity [START_REF] Amman | Data diversity: An approach to software fault tolerance[END_REF]. The rationale relies on the observation that residual software faults inducing failures during operational life are usually "subtle" faults (also known as Heisenbugs [START_REF] Gray | Why do computers stop and what can be done about it?[END_REF]) whose activation is caused by rare situations corresponding to certain val-ues in the input space (at large) -e.g., operation in a specific range of values, operating system induced memory leaks, etc.) -that are difficult to reproduce. The idea is that such failures could be averted by applying a minor "perturbation" to the input data, that would still be acceptable for the software. A very "extreme" approach is known as environment diversity [START_REF] Jalote | A framework for understanding and handling transient software failures[END_REF], which encompasses several progressive procedures: retry, restart and reboot. A specific form of environment diversity has been popularized under the label software rejuvenation [START_REF] Huang | Software rejuvenation: Analysis, module and applications[END_REF][START_REF] Castelli | Proactive management of software aging[END_REF]. Thus, data diversity works in cases when a single channel (thus relying on time redundancy) or identically-redundant (i.e., non dissimilar) channels are executing on distinct data. It is thus cheaper to implement than design diversity techniques. Data diversity has also been intensively used for coping with the risk of common mode failures resulting from faults affecting hardware components in redundant channels (e.g., see [START_REF] Oh | ED4I: Error detection by diverse data and duplicated instructions[END_REF]). Recently, data diversity has also been proposed as a suitable approach for coping with malicious intrusions (e.g., see [START_REF] Nguyen-Tuong | Security through redundant data diversity[END_REF]).

Design-Fault Tolerance Evaluation

The main objective when using design-fault tolerance approaches is to enhance system dependability attributes (such as safety or availability). However, the development and operation of design-fault tolerant systems: i) usually induce a significant cost overhead, essentially in terms of development and maintenance effort, and ii) for some techniques, give rise to a non-negligible increase in the execution time (i.e., a degradation in performance). It is therefore very important to determine what types of benefits can be expected from using design-fault tolerant systems, and to assess the positive as well as the negative impacts of design-fault tolerance approaches. In this section, we give a global overview of the kind of assessments that have been performed to characterize design-fault tolerance approaches as well as the varieties of results that can be obtained from these assessments. Emphasis is mainly put on their impact on system dependability. This overview is not exhaustive due to the huge amount of literature related to the topic, dating back to the early 1980's .

Assessment is carried out based on: i) statistical modeling approaches, or ii) controlled experiments, or iii) field data related to real-life systems. The latter two approaches are usually referred to as empirical studies. Each kind of approach has its advantages and limitations. Obviously, results based on field data are more significant than those based on experimentation and modeling. Unfortunately, there are few such analyses, because they require the collection of very specific data, most of the time related to (hopefully) very rare events, hence requiring a long period of data collection to lead to meaningful results.

It is well known that the primary causes of N-version programming failures are due to correlated faults in versions and precision problems in the voting components. For recovery-block programming, the main causes of failures correspond to related faults between the variants or between one variant and the acceptance test (see, e. g., [START_REF] Arlat | Dependability modeling and evaluation of software fault-tolerant systems[END_REF] for more details). For self-checking software components, the main cause of failure is due to the inefficiency of the self-checking algorithms.

Not surprisingly, as far as we are aware, all published studies, be they based on modeling or on experimentation, show that the effectiveness of design-fault tolerance techniques is strongly related to: i) the degree of independence of the versions and the effectiveness of the decision or voting mechanism, in the Nversion programming technique, ii) the effectiveness of the acceptance test for the recovery block techniques, and iii) the effectiveness of the error detection and recovery mechanisms in N-self-checking software. However, even though the above general results are agreed on, in some papers they are presented either i) in an optimistic way to show the superiority of design-fault tolerance techniques compared to fault-avoidance techniques, or ii) in a pessimistic way to show their limitations. For example, even if an early experimental work [START_REF] Knight | An experimental evaluation of the assumption of independence in multi-version programming[END_REF] was considered as controversial (and is usually referenced as such), the experimental results confirm the above general conclusions. Moreover, based on the results published in the same paper, but processing the data differently, a subsequent study [START_REF] Hatton | N-version design vs. one good version[END_REF] showed that there is a substantial reliability improvement for the N-version programming system compared to a single software system.

Consequently, the difficulty in quantifying the effectiveness of design-fault tolerance techniques lies on the characterization of the above limiting factors and of their impact on the global system dependability. Modeling has been carried out based on various techniques, such as state graphs or Markov chains [START_REF] Grnarov | On the performance of software faulttolerant strategies[END_REF][START_REF] Laprie | Dependability: Basic concepts and associated terminology[END_REF][START_REF] Laprie | Architectural issues in software fault tolerance[END_REF], fault trees [START_REF] Dugan | Dependability modeling for fault-tolerant software and systems[END_REF], stochastic reward nets [START_REF] Tomek | Analyses using reward nets[END_REF], software execution schema (to identify the combination of fault activations leading to failure) [START_REF] Arlat | Dependability modeling and evaluation of software fault-tolerant systems[END_REF][START_REF] Tai | Performability enhancement of faulttolerant software[END_REF], Bayesian approaches [START_REF] Littlewood | Assessment of the reliability of faulttolerant software: A bayesian approach[END_REF], the derivation of the intensity of coincident errors [START_REF] Eckhardt | A theoretical basis of multiversion software subject to coincident errors[END_REF][START_REF] Nicola | Modeling of correlated failures and community error recovery in multiversion software[END_REF], or the derivation of score functions [START_REF] Popov | Assessing asymmetric fault-tolerant software[END_REF]. These evaluations either compare various design-fault tolerance techniques and give conditions under which one technique is superior to other(s) or to a single version, or concentrate on a single designfault tolerance technique to provide conditions under which this technique is a better strategy than a single version.

Modeling approaches require several assumptions to build tractable models that can be processed to provide usable results. Some assumptions are more realistic than others. Additionally, modeling requires numerical values of some parameters that are not all available from field data. More assumptions are thus needed related to the numerical values of the parameters. Nevertheless, sensitivity analyses with respect to the assumptions as well as to numerical values of the parameters lead to interesting results. Moreover, they allow the identification of the most significant parameters, which should be evaluated accurately to correctly quantify the practical dependability gain induced by design-fault tolerance.

Some controlled experiments have been carried out on software programs developed by professional programmers while, in other experiments, the programs have been developed in academic environments. As far as we are aware, experiments involving professional programmers are rare. They are based on a small number of versions. For example: i) in [START_REF] Anderson | Software fault tolerance: an evaluation[END_REF], only a single software version was developed and the experiments compare the reliability obtained with that single version when fault-tolerance is enabled with that obtained when fault-tolerance is disabled, and ii) in [START_REF] Bishop | Project on diverse software -an experiment in software reliability[END_REF] three versions have been developed to analyze the impact of the N-version programming approach to software-fault tolerance, including back-to-back testing.

Experiments carried out in academic environments have, in general, been applied to relatively small investigational software systems, developed by less experimented programmers (most of the time, by students) because of cost considerations, thus under conditions that are sometimes far from industrial development conditions. Usually these experiments involved a large number of software programs, allowing several analyses to be carried out, based on the combination of several versions, back-to-back testing, fault injection, etc.

Significant sets of experiments have been carried out since the 1980's (see, e.g., [START_REF] Avizienis | DEDIX 87 -a supervisory system for design diversity experiments at UCLA[END_REF][START_REF] Knight | An experimental evaluation of the assumption of independence in multi-version programming[END_REF][START_REF] Kelly | A large scale second generation experiment in multi-version software: description and early results[END_REF][START_REF] Leveson | The use of self checks and voting in software error detection: an empirical study[END_REF][START_REF] Eckhardt | An experimental evaluation of software redundancy as a strategy for improving reliability[END_REF]) and continued until more recently [START_REF] Xia | An experimental evaluation on reliability features of N-version programming[END_REF]. A major advantage of controlled experiments concerns the validation of modeling approaches [START_REF] Scott | Fault-tolerant software reliability modeling[END_REF][START_REF] Xia | An empirical study on reliability modeling for diverse software systems[END_REF] as well as some of the assumptions made by the various conceptual models.

Finally, some analyses addressed cost overhead induced by design-fault tolerance, either based on modeling [START_REF] Migneault | The cost of software fault tolerance[END_REF] or on experimentation (see, e.g., [START_REF] Anderson | Software fault tolerance: an evaluation[END_REF][START_REF] Kanoun | Real-world design diversity: a case study on cost[END_REF]). For example, based on observations of a real-life fault tolerant software system, the latter reference showed that the global cost overhead from functional specifications to system test ranges between 42% to 71%, excluding the requirement specifications phase that is performed only once for the whole software system. This overhead has been estimated to be 60% in [START_REF] Anderson | Software fault tolerance: an evaluation[END_REF].

Design-Fault Tolerance Applications

Modern passenger aircraft, such as the Airbus 320/330/340 family [START_REF] Brière | Airbus A320/A330/A340 electrical flight controlsa family of fault-tolerant systems[END_REF] and the Boeing 777 [START_REF] Yeh | Dependability of the 777 primary flight control system[END_REF], include computers in the main flight control loop to improve overall aircraft safety (through stability augmentation, flight envelope monitoring, windshear protection, etc.) and to reduce pilot fatigue. Of course, these increases in aircraft safety must not be annihilated by new risks introduced by the computing technology itself. For this reason, the flight control systems of these aircraft are designed to be fault-tolerant and accordingly they rely extensively on design diversity. Railway applications are also increasingly relying on computer technology, in particular speed regulation and rail-traffic control. It is clear, here also, that the stringent safety requirements have resulted in the development of fault-tolerant architectures, incorporating hardware redundancy and often also software redundancy (e.g., see [START_REF] Hennebert | SACEM: A fault-tolerant system for train speed control[END_REF][START_REF] Arlat | Dependability of railway control systems[END_REF]). The subsequent paragraphs describe two typical examples in these application domains.

The Airbus 320 Flight Control System. Fault tolerance in the flight control system of the Airbus 320/330/340 family is based on the error detection and compensation technique [START_REF] Avizienis | Basic concepts and terminology of dependable and secure computing[END_REF], using the N-self-checking software approach described in Section 1.1. Each flight control computer is designed to be self-checking, with respect to both physical and design faults, to form a fail-safe subsystem.

Each computer consists of two lanes supporting functionally-equivalent, but diversely-designed programs (Figure 1). Both lanes receive the same inputs, compute the corresponding outputs and check that the other lane agrees. Only the control lane drives the physical outputs. Any divergence in the results of each lane causes the physical output to be isolated. Each flight control axis of the aircraft can be controlled from several such self-checking computers.

The complete set of computers for each axis processes sensor data and executes the control loop functions. However, at any given instant, only one computer in the set (the primary) is in charge of physically controlling the actuators. This computer sends periodic"I'm alive" messages to the other computers in the set, so that they may detect when it fails. Should the primary fail, it will do so in a safe way (thanks to the built-in self-checking) without sending erroneous orders to the actuators. According to a predetermined order, one of the other computers in the set then becomes the new primary and can immediately close the control loop without any noticeable jerk on the controlled surface.

The design diversity principle is also applied at the system level. The set of computers controlling the pitch axis (Figure 2) is composed of four self-checking computers: two Elevator and Aileron Computers (ELACs) and two Spoiler and Elevator Computers (SECs), which are based on different processors and built by different manufacturers. Given that each computer type supports two different programs, there are overall four different pitch control programs.

There is also considerable functional redundancy between the flight control surfaces themselves. Accordingly, it is possible to survive a complete loss of all computer control of some surfaces, as long as the failed computers fail safely. Furthermore, if all computers should fail, there is still a (limited) manual backup. Similar system-level diversity has been implemented in subsequent planes of the Airbus family; it also encompasses the power supply chains and the hydraulic systems, see [START_REF] Traverse | Airbus fly-by-wire: A total approach to dependability[END_REF]. The ASF Computer Based Interlocking System. We consider the case of the system developed by Ansaldo Segnalamento Ferroviario for the control of rail traffic [START_REF] Mongardi | Dependable computing for railway control systems[END_REF] and that manages the Termini station in Rome. As most systems of this type, the Computer Based Interlocking (CBI) system implements a hierarchical architecture (Figure 3):

level 1 : a control centre equipped with workstations (WS ) for managing the station and supervising the diagnosis and maintenance operations; -level 2 : a central processing unit, or safety nucleus (SN ) of the CBI, in charge of the overall management of the safety operations for the station concerned; -level 3 : a set of remote computers, called trackside units (TU ), intended for data acquisition and application of the orders provided by the SN processors (localisation of the trains, operation of signals and switches).

Various forms of redundancy are used for each level:

-WS : simple dynamic redundancy, -SN : triple modular redundancy (TMR) featuring code and data diversification for each of the replicated sections S i , i = 1..3 -TU : self-checking redundancy (pair of computers).

We focus hereafter on the SN level, which constitutes the backbone of the CBI. The three redundant sections of the SN elaborate a logical decision based SN Fig. 3. The CBI Safety Nucleus (adapted from [START_REF] Mongardi | Dependable computing for railway control systems[END_REF])

on standard majority voting and rely on a self-checking hardware device (exclusion logic) that ensures the exclusion of the TMR module (section) declared as failed. Each section is isolated from the others and has its own power supply. It consists of a logical unit (LU ) and a peripheral unit (PU ). The SN layer thus consists of six processing units interconnected by means of dedicated serial lines, with optical coupling. The software architecture of each module is similar, with the operating system, the applications and the data stored in read-only memory. However, the application software is diversified: distinct programmer teams, dissimilar languages, different coding of the data, storage of the code and data segments at different address locations in each section. In addition, self-testing routines are executed in each section provide a form of "watchdog" monitoring The SN layer is designed to provide both availability (via its TMR structure) and safety (based on a "2-out-of-2 vote" to be described later). The elimination of the first failed section by the exclusion logic scheme removes the risk of common mode failure that could result from the subsequent failure of one of the two remaining operational sections. Furthermore, the isolated section can be readily accessed for diagnosis and maintenance, and later reintegration into the operational system.

The principle of the exclusion logic (EL) device is depicted on Figure 4. It consists of three identical modules that process the analog commands produced by the sections of the SN, after a software-implemented vote. Information concerning the agreement (resp. disagreement) of a section with the two othersactive-level signal (resp. passive-level signal) -is communicated to the EL at the same time as the commands. Each module of the EL checks (sequential AND function) for an agreement between the two corresponding input signals and ac-tivates the enabling signal powering the drivers of the transmission modules of the SN (communication with the WS 's of the control centre and the TU 's). In case of disagreement, the power of the transmission device associated with the failed section is cut off, which isolates it from the other two sections and from the TU 's. In this section, we present a recent study on an application of design-fault tolerance in robotics [START_REF] Lussier | Fault tolerant planning for critical robots[END_REF][START_REF] Lussier | Planning with diversified models for fault-tolerant robots[END_REF]. We consider how diversification can be applied to the declarative domain models that allow robots to autonomously establish a plan of activities to reach specified goals in a partially-unknown environment.

The problem: deficiencies in planning domain models

Fully autonomous systems, such as space rovers, elderly care assistants, museum tour guides, and autonomous vehicles, should be able to choose and execute high-level actions without any human supervision, in practice using planners as a central decisional mechanism. However, one of the major stumbling blocks to the adoption of these techniques in critical applications is the difficulty of predicting and validating the behavior of such decisional software, especially when faced with the open, unstructured and dynamic environments that are their raison d'être.

Planning is the activity of producing a plan to reach a goal (or set of goals) from a given state, using given action models. A planner typically consists of two parts: a) a declarative domain model describing domain objects, possible actions on these objects and the associated constraints, and b) a planning engine, that can reason on the domain model and produce a plan of actions enabling planning goals to be reached. Here, we consider planning carried out by searching in plan space, as carried out by the IxTeT planner [START_REF] Ghallab | Representation and control in IxTeT, a temporal planner[END_REF]. In this approach, CSP (Constraint Satisfaction Problem) solving techniques are used to determine a possible evolution of the system state that satisfies a set of constraints, some of which specify the system goals. This is done by iteratively assigning possible values to each variable and verifying that all constraints remain satisfied.

At the time at which a plan is established, not everything may be known about the environment nor its future evolution. Thus, planners seek to produce flexible plans where as much latitude and scope for adaptation as possible are left in the plan [START_REF] Ghallab | Representation and control in IxTeT, a temporal planner[END_REF][START_REF] Muscettola | IDEA: Planning at the core of autonomous reactive agents[END_REF]. Moreover, adverse situations that appear during plan execution, causing some of its actions to fail, can be tolerated through:

-Re-planning, which consists in developing a new plan from the current system state and still unresolved goals. Depending on the complexity of the planning model, re-planning may require a significant amount of processing.

Other system activities are thus generally halted during re-planning. -Plan repair , which attempts to reduce the time lost in re-planning by salvaging parts of the previous failed plan, and executing them while the rest of the plan is being repaired. However, if reducing the salvaged plan conflicts with unresolved goals, plan repair is stopped and re-planning is initiated.

In this respect, planning and plan execution can be thought of as a generalized form of forward recovery, which will attain the assigned goals if a solution plan exists and if it can be be found in time for it to be executed.

Among the various reasons that can prevent a planner from finding an adequate plan are deficiencies in the heuristics that guide the search process and deficiencies in the domain model that, in fine, dictates what plans the planner can produce. Indeed, the problem of planner validation has received much attention, but it remains notoriously hard [START_REF] Goldberg | Runtime verification for autonomous spacecraft software[END_REF][START_REF] Howey | VAL: Automatic plan validation, continuous effects and mixed initiative planning using PDDL[END_REF][START_REF] Khatib | Mapping temporal planning constraints into timed automata[END_REF][START_REF] Penix | Using model checking to validate AI planner domain models[END_REF]. In the next sub-section, we describe a complementary solution that aims to tolerate residual planner design faults, focussing particularly on the domain model.

A solution: fault-tolerant planning

The general principle of the proposed mechanisms is to execute, sequentially or concurrently, diversified variants of the planner, following approaches similar to recovery blocks [START_REF] Randell | System structure for software fault tolerance[END_REF] and distributed recovery blocks [START_REF] Kim | Distributed execution of recovery blocks: an approach to uniform treatment of hardware and software faults in real-time applications[END_REF]. In particular, diversity is encouraged by forcing the use of different algorithms and variable domains, and different parameters in the models and heuristics of the variants.

Implementing error detection for decisional mechanisms in general, and planners in particular, is difficult [START_REF] Lussier | Fault tolerance in autonomous systems: How and how much?[END_REF]. There are often many different valid plans, which can be quite dissimilar. Therefore, error detection by comparison of redundantly-produced plans is not a viable option2 . Thus, we must implement error detection by independent means. Four complementary error detection mechanisms can be envisaged:

a watchdog timer to detect when the search process is too slow or deadlocked; -a plan analyzer as an acceptance test to check, before execution, that the produced plan satisfies a number of constraints and properties; -a plan failure detector, a classic plan execution control mechanism needed to detect whether a plan action has failed in order to trigger plan repair and/or re-planning; -an on-line goal checker that verifies whether goals are actually satisfied as the plan is executed.

Recovery from detected errors, despite possible planner design-faults, relies on the use of two (or more) planners using diversified knowledge (i.e., search heuristics and/or domain model), managed by a coordinator component (called FTplan) that is sufficiently simple to be shown (or assumed) to be fault-free. Two recovery strategies are possible, differing on whether the planners are executed in sequence (like in classic recovery blocks) or in parallel (like in distributed recovery blocks). For space reasons, we only consider here the sequential strategy (see Algorithm 1).

Basically, each time an error is detected, we switch to another planner until all goals have been reached or until all planners fail in a row from the same initial system state. In the latter case, no models allow the planner to tackle the planning problem successfully: an exception must be raised to inform the operator of mission failure and to allow the system to be put into a safe state (line 29). When all the planners have been used but some goals are still unsatisfied, we revert to the initial set of planners (while block: lines 4 to 32).This algorithm illustrates the use of all four error detection mechanisms: watchdog timer (lines 9 and 25), plan analyzer (line 14), plan failure detector (lines 16 and 18), on-line goal checker (lines 4, 6 and 17).

Until all goals have been achieved, the proposed algorithm reuses planners that may have been previously detected as failed (line 5). This makes sense since (a) a perfectly correct plan can fail during execution due to an adverse environmental situation, and (b) some planners, even faulty, can still be efficient in situations that do not cause fault activation.

Assessment

We implemented a prototype version of the FTplan coordinator component and integrated it in the LAAS architecture for autonomous systems [START_REF] Alami | An architecture for autonomy[END_REF], which has been successfully applied to several mobile robots involved in real applications.

Algorithm 1 Sequential Planning Strategy

31:

end while

32:

end while

33: end mission

The FTplan prototype can coordinate a fault-tolerant configuration of two Ix-TeT temporal planners [START_REF] Ghallab | Representation and control in IxTeT, a temporal planner[END_REF]. It implements the sequential planning strategy of Algorithm 1 and includes three of the four error detection mechanisms: watchdog timer, plan failure detector, and on-line goal checker, but not a plan analyzer (the design of which is a research topic in its own right). To evaluate the proposed approach, we used two diverse declarative models (which we call M odel 1 and M odel 2 ) for autonomous planning of the missions of a planetary exploration rover. The missions involve three sets of goals: (a) take photos of a set of science targets (e.g., rocks) located at pre-defined coordinates with respect to the rover's initial position; (2) communicate with an overhead orbiter during predefined communication windows, and (3) return to the initial position. While navigating to the science targets and back to its initial position, the robot must move round any obstacles that it meets on this path. At the plan execution level, the unknown obstacles create uncertainty as regards the outcome of action executions, and can possibly prevent the rover from achieving some of its goals.

In our experiments, M odel 1 was a mature model that had been successfully used several times both indoors and outdoors on a real robot. M odel 2 was a new model, in which diversification with respect to M odel 1 was forced through specific design choices. For example, the rover's position is defined in M odel 1 using Cartesian coordinates whereas M odel 2 uses a symbolic representation, thus implementing fundamentally different algorithms than those of the former. Both models contain action descriptions for:

movement initialization (allowing, in particular, recovery from any earlier navigational errors), -camera initialization, -moving the camera, -taking a photo, -communicating with the orbiter, -moving the rover from point A to point B.

In M odel 1 , the points A and B may be anywhere, whereas in M odel 2 they are specific symbolic points (such as the initial position of the system and the positions of different goals). A second move action is defined with M odel 2 for the case where the rover needs to move from an arbitrary point to a specific one (typically needed when a previous move has failed).

To evaluate the efficacy of the fault-tolerance approach, we compared the behavior of two simulated rovers in the presence of injected faults:

-Robot1 : using M odel 1 in a non-redundant planner -RobotFT : using both M odel 1 and M odel 2 in redundant planners coordinated by FTplan.

Faults were injected into M odel 1 on both robots by means of the Sesame mutation tool [START_REF] Crouzet | The SESAME experience: from assembly languages to declarative models[END_REF] . The rovers were faced with four increasingly complex worlds (set of obstacles): W 1-W 4 and given four increasingly complex missions (sets of photos and communication windows): M 1 -M 4, leading to a total of 16 world × mission combinations. Figure 5 illustrates the most complex combination: W4M4.

The experiments are inherently non-deterministic, due to asynchrony of the various robot subsystems and in the underlying operating systems. Task scheduling differences between similar experiments may degrade into task failures and possibly unsatisfied goals, even in the absence of faults. To address this nondeterminacy, each basic experiment was executed three times, leading to a total of 48 experiments per fault scenario. More repetition would of course be needed for statistical inference on the basic experiments, but this would have led to a total number of experiments higher than that which could have been carried out with our available resources (including initialization and data treatment, each basic experiment lasts about 20 minutes).

The overall results for 28 different mutations are summarized in Figure 6 (for detailed results, see [START_REF] Lussier | Fault tolerant planning for critical robots[END_REF][START_REF] Lussier | Planning with diversified models for fault-tolerant robots[END_REF]). The figure shows bar graphs of the percentages of satisfied goals and missions averaged over all four missions. We give separate averages for the three simpler worlds (W 1 -W 3) and for all four worlds together (W 1 -W 4), since it was often the case that even a fault-free planner was unable to find a solution plan for world W 4, with its numerous long thin obstacles (cf. Figure 5). These results show that, with the considered faultload:

Ø F 0% 50% 100% Photos Ø F 0% 50% 100% Photos Robot 1 Robot FT Ø F 0% 50% 100%
Communications with orbiter

Ø F 0% 50% 100%
Communications with orbiter

Ø F 0% 50% 100%
Returns to base

Ø F 0% 50% 100%
Returns to base

Ø F 0% 50% 100%
Fully-completed missions

Ø F 0% 50% 100%
Fully-completed missions Worlds W1-W3 Worlds W1-W4 Fig. 6. Effectiveness of fault-tolerant planner (RobotFT ) compared to baseline planner (Robot1 ). The bar graphs show the percentages of satisfied goals (photos, communications and returns) and completed missions, without (∅) and with (F) injected faults.

-The redundant diversified models of the fault-tolerant RobotFT provide an notable improvement to dependability in the presence of faults (bar graphs labelled F): in all cases, the proportions of failed goals decrease compared to the non-redundant Robot1. -Even when considering the pessimistic measure of the proportion of failed missions (a mission is considered as failed even if only a single elementary goal is not achieved), the improvement procured by redundant diversified models is appreciable: 41% in worlds W 1 -W 3, 29% when world W 4 is also considered.

Note, however, that in the presence of injected faults, the fault-tolerant RobotFT is less successful than a single fault-free model (compare RobotFT of the bar graphs labelled F, with Robot1 of the bar graphs labelled ∅). This apparent decrease in dependability can be explained by the fact that incorrect plans are only detected when their execution has failed, possibly rendering one or more goals unachievable, despite recovery. This underlines the potential improvement that could be obtained if FTplan were to include a plan analyzer to detect errors in plans before they are executed.

Tolerance of Security Vulnerabilities in COTS Operating Systems

This section presents an ongoing study on the use of design-fault tolerance techniques to ensure security. Specifically, we consider how diversification can be applied to provide protection against security vulnerabilities in commercial operating systems when used in a critical application for the aviation industry.

The problem: operating system vulnerabilities

Nowadays, the main threat against computer security is represented by malicious software (malware) exploiting design flaws of existing commercial off-the-shelf (COTS) operating systems. Indeed, COTS operating systems are too complex to be free from design faults, despite some attempts to apply formal development methods to at least parts of them (e.g., seL4 [START_REF] Klein | sel4: Formal verification of an OS kernel[END_REF]). And even if formal verification methods are applied, it is difficult to prove the absence of vulnerabilities: there is no model suitable for expressing both the desired high-level properties and the implementation of subtle hardware mechanisms (address space control [START_REF] Lacombe | Enforcing kernel constraints by hardware-assisted virtualization[END_REF], interrupt-handling, or hardware management functions such as ACPI (Advanced Configuration and Power Interface) [START_REF] Duflot | ACPI: Design principles and concerns[END_REF], or even protection mechanisms [START_REF] Sang | Exploiting an I/OMMU vulnerability[END_REF]).

For instance, formal approaches that apply successive refinements of models (e.g., the B method [START_REF] Kanoun | The B-Book -Assigning Programs to Meanings[END_REF]) cannot descend to the level of COTS processors [START_REF] Jaeger | A few remarks about formal development of secure systems[END_REF]. Nevertheless, COTS operating systems are attractive, even for moderately critical applications, because they offer advanced facilities at a low cost, enabling the easy development of efficient and high performance applications. They are used in many different environments by very large numbers of people, and their reliability increases with their maturity (design flaws are frequently identified and corrected). On the other hand, the wide distribution of COTS operating systems make it easy for potential attackers to obtain detailed knowledge of their functionalities and vulnerabilities.

As for other design faults, tolerating COTS OS vulnerabilities relies on execution diversity and adjudication of execution results to provide an error-free result or to stop the execution (to provide a fail-safe behaviour). One way to implement OS diversity is to develop diverse variants of applications, executed on different operating systems, running on different hardware platforms [START_REF] Deswarte | Diversity against accidental and deliberate faults[END_REF]. But such an implementation would be more complex than necessary: to tolerate OS vulnerabilities, the same application can be executed on different operating systems. For that, the application needs to be developed as independent of the operating system that will execute it, by interfacing a generic library API, or a generic execution environment. This is the case for instance of Java programs, designed to be run in a Java Virtual Machine (JVM), each operating system implementing its own version of the JVM.

Similarly, it is not necessary to run the different operating systems on different hardware platforms: most hardware platforms (Intel, AMD, ARM, etc.) support several different operating systems. Moreover, in some cases it would be very inconvenient for a user to cope with several independent and redundant human-machine interfaces (screens, keyboards, mice, etc.) while interacting with a single application. A better solution is thus to run a single application software over diverse operating systems run by a single hardware platform. This is possible, thanks to virtualization techniques, as explained in the next subsection.

A solution: OS diversification through virtualization

Virtualization techniques were introduced for the first time by IBM in the seventies [START_REF] Varian | VM and the VM community: Past, present, and future[END_REF] to emulate for a software component the operation of the underlying hardware. Over the last decade, these techniques have been studied and developed to offer standardized layers of virtualization. For instance, in a multitask operating system, every task has a "virtualized view" of the hardware layer, since every task considers that it is running alone on the hardware. For operating system diversification, we are interested in the notion of "system virtual machine" [START_REF] Smith | Virtual Machines: Versatile Platforms for Systems and Processes[END_REF], which allows many operating systems to be used in parallel on the same physical machine (cf. Figure 7). A type 2 VMM is installed as an application on a host system, which can then launch and manage different operating systems. One example of such a type 2 VMM would be, for example, the use of VMWare on Linux to run a Windows operating system, but this does not help to tolerate vulnerabilities of the host operating system (here Linux). More recently, type 1 VMM 's (known also as hypervisors) have been developed to support different operating systems while running directly over the bare hardware. One example of such hypervisors is Xen [START_REF] Barham | Xen and the art of virtualization[END_REF].

The hypervisor technique offers complete isolation between the different virtual machines, and also a means to control the virtual machines and their interactions with input-output devices. In particular, when performing the same application task simultaneously in two or more virtual machines with different operating systems, the hypervisor can intercept all outputs from the different virtual machines, compare them and decide which copy is to be transmitted to the hardware outputs. Similarly, all inputs can be replicated by the hypervisor before sending one copy to each virtual machine. This virtualization technique has been proposed to implement aircraft maintenance tasks on a laptop [START_REF] Laarouchi | Connecting commercial computers to avionics systems[END_REF]. Maintenance operations present an important economic challenge for airline companies since these operations determine the time needed by ground technicians to authorize take-off of the concerned aircraft. The shorter this time, the more profitable the aircraft for the company. Aircraft maintenance is ensured by operators who, using procedures set out in maintenance manuals, analyze the aircraft flight reports and launch tests on the components detected as potentially faulty. Currently, many maintenance manuals are still not electronic, and even the electronic ones are prohibited from interacting directly with the aircraft in order to prevent any risk of corruption of critical components. The presence of a human operator is currently the only guarantee that maintenance operations follow a safe procedure that does not corrupt critical systems.

For future aircraft, it is envisaged that the manuals will be stored on a Maintenance Laptop (ML), which could be connected to the aircraft through Ethernet or wireless connections. The maintenance operator would use the ML and move freely in and around the aircraft. He would inspect directly the components identified as faulty in flight reports, follow the procedures indicated on the ML, and launch directly from the ML the set of tests that he formerly launched from specific embedded devices. For this application, the main security focus is communication between the maintenance laptop (running diversified COTS operating systems) and the aircraft. In particular, the aircraft components should be protected from illicit modification due to a compromised operating system. Similarly, the human-machine interface (HMI ) should be protected from falsification by a compromised operating system.

An ML prototype has been developed, using the Xen hypervisor. The prototype consists of two identical copies of the maintenance task (written in Java), respectively Task 1 and Task 1', each running on its own virtual machine (VM ) with a different OS, and a human-machine interface, called MLI (ML Interface) in Domain0 of Xen. Domain0 also supports result adjudication by a validation object (VO) that compares the outputs from Task 1 and Task 1' (see Figure 8). The MLI can be described as follows:

-MLI provides the same GUI (Graphic User Interface) as in Task 1 and Task 1' programs. MLI has the same graphical components, with the same graphic charter. -MLI does not implement any function of Task 1 or Task 1'. It captures, through an AspectJ wrapper, all ML inputs (keyboard, mouse, etc.) and forwards them to the COTS VM 's (cf. (1) ( 2) and (3) on Figure 8.

Once these inputs are forwarded to the COTS VM 's, Task 1 and Task 1' process the inputs. Their results, consisting of graphic outputs and data to be sent to the aircraft, are then captured (4) and forwarded to VO (5) for comparison. If there is a difference between the two results, this would mean that at least one VM is potentially corrupted, and is not generating the output it should. In this case, both COTS VM 's are stopped and an alert (6") is displayed to the maintenance operator (the operator would then reboot the ML, change his laptop, or give up using a laptop and use the traditional on-board maintenance equipment). If no difference is detected, the result is forwarded to MLI if it is a graphic display output [START_REF] Arlat | Dependability of railway control systems[END_REF], or to the aircraft otherwise (6'). The validated graphic output is then displayed by the MLI (7).

Assessment

A proof-of-concept prototype of the maintenance laptop has been developed. It aims to demonstrate the application of OS diversity within a single computer to tolerate COTS OS vulnerabilities. The idea is that when the same laptop is used for tasks other than maintenance (e.g., browsing the Internet), it can be contaminated by malware (e.g., Trojan Horses, viruses, worms, etc.) that can compromise a COTS operating system. We claim that:

1. It is much more difficult to develop a malware able to compromise several operating systems than one able to compromise a single OS. 2. Even if a malware was able to corrupt both operating systems running the two copies Task 1 and Task 1', it would have a different effect on Task 1 and Task 1' outputs, and thus the errors would be detected.

This claim has been validated by various OS attack experiments on the ML prototype, e.g., changing the values to be displayed on the screen or the parameters sent to or received from the aircraft. However, such an implementation would not tolerate a malware corruption of the hypervisor (here, Xen and its Domain0 ). We claim that it would be much more difficult to compromise such a hypervisor than an operating system:

1. A hypervisor is usually much simpler than an operating system, and thus much easier to validate. Green Hill Integrity 178B and Polixene are examples of separation kernels and hypervisors that have been evaluated respectively at EAL6 and EAL5 according to Common Criteria [START_REF]Common criteria for information technology security evaluation[END_REF]. 2. For this kind of application, the hypervisor is only active during maintenance operations: before a maintenance operation, the laptop is booted in a secure way to launch first the hypervisor and then create the virtual machines that each load its own operating system. The hypervisor itself is protected from a corrupted VM by its protection and separation mechanisms. When the laptop is used for non-critical operations (e.g., for Internet browsing), it is booted in the standard way, with a COTS operating system, which can be compromised but cannot access the hypervisor.

Conclusion

The pioneering work of Elmendorf, Randell, Avizienis and Chen in the 1970's [START_REF] Elmendorf | Fault-tolerant programming[END_REF][START_REF] Randell | System structure for software fault tolerance[END_REF][START_REF] Avizienis | On the implementation of N-version programming for software fault tolerance during execution[END_REF], on the notion of diversity to allow tolerance of design faults, laid the foundations for over four decades of research. Despite the debate as to whether it is cost-effective and worthwhile [START_REF] Knight | An experimental evaluation of the assumption of independence in multi-version programming[END_REF][START_REF] Hatton | N-version design vs. one good version[END_REF][START_REF] Xia | An experimental evaluation on reliability features of N-version programming[END_REF], we claim that design-fault tolerance is not only beneficial, but well nigh indispensable when verification and testing cannot be carried out with a degree of confidence that is commensurate with the criticality of the considered applications. The industrial applications described in Section 1.3 of this paper, and the recent research described in Sections 2 and 3, give credence to this claim. We also claim that "info-diversity", like biodiversity, will be a necessary condition for survival of the human species in an ever-changing world in which so many aspects of our lives are now fullydependent on information technology.

Fig. 2 .

 2 Fig.2. Sketch of the Airbus 320 pitch control (adapted from[START_REF] Traverse | Airbus fly-by-wire: A total approach to dependability[END_REF])

Fig. 4 .

 4 Fig. 4. Principle of the exclusion logic (adapted from [57])

6 : 20 :

 620 while candidates = ∅ ∧ attainable goals = ∅ do 7:choose new planner k such that (k ∈ candidates) ∧ (k / ∈ f ailed planners) ∧ [(k = exec f ailure) ∨ (k ∪ f ailed planners = candidates)] 8: candidates ← candidates\k9: init watchdog(max duration) 10: send (plan request) to k 11: wait {for either of these two events} 12: receive (plan f ound) from k end if {if the plan fails, then attainable goals = ∅ and the on-line goal checker will loop to line 3 or line 4} if f ailed planners = planners then 29: raise exception 'no remaining planners' {the mission has failed} 30: end if

Fig. 5 .

 5 Fig. 5. World W4M4. The mission starts and ends in the center of a 12m × 12m grid. The robot should visit the 5 science photo locations, send data to the orbiter during the 4 communication windows and avoid the 5 long thin obsacles. The dotted line indicates a possible robot itinerary ignoring obstacles.

Fig. 7 .

 7 Fig. 7. Type 1 and Type 2 Virtual Machine Monitors

Figure 7

 7 Figure 7 represents two types of Virtual Machine Monitors (VMM 's). Type 2 VMM 's are widespread. A type 2 VMM is installed as an application on a host system, which can then launch and manage different operating systems. One example of such a type 2 VMM would be, for example, the use of VMWare on Linux to run a Windows operating system, but this does not help to tolerate vulnerabilities of the host operating system (here Linux). More recently, type 1 VMM 's (known also as hypervisors) have been developed to support different operating systems while running directly over the bare hardware. One example of such hypervisors is Xen[START_REF] Barham | Xen and the art of virtualization[END_REF].

Fig. 8 .

 8 Fig. 8. Maintenance Laptop Implementation

Development faults can be introduced during specification, design or implementation. In accordance with common usage, we generically refer to such faults as design faults.

For the same reason, N-version programming was excluded as a possible design-fault tolerance option