François Armand

Jean Berniolles

Julia L Lawall

Gilles Muller

Automating the Porting of Linux to the VirtualLogix Hypervisor using Semantic Patches

Keywords: Linux, virtualization, VLX, automated program transformation

Virtualization is a promising technology for running multiple operating systems (OS's) on a single processor. Preparing an OS for use with virtualization, however, involves making some changes to the OS code, which must be repeated for each version, whether a new release or a client customization. Typically such changes are expressed as patches, but patches are often not portable from one version to another, and thus manual adjustments are needed as well. In this paper, we consider the use of the automated transformation system Coccinelle to perform the changes required to port several versions of Linux to the VLX hypervisor. Coccinelle provides a notion of semantic patches, which are more abstract than standard patches, and thus are potentially applicable to a wider range of OS versions. We have applied this approach in the context of Linux versions 2.6.13, 2.6.14, and 2.6.15, for the ARM architecture.

Introduction

Virtualization is becoming a key technology in embedded systems such as mobile phones and set-top boxes. In this context, virtualization enables hosting several operating systems (OSes) on a single uni-core or multi-core processor via a hypervisor that provides each OS with its own execution environment or virtual machine by partitioning and/or virtualizing hardware resources. The main benefit of this technology is a simpler and less expensive hardware architecture, not requiring multiple dedicated processors, that also reduces energy consumption. However, since most processors for embedded systems do not provide any support for hardware assisted virtualization, one must rely on paravirtualization: guest OSes have to be modified to be run efficiently on top of the hypervisor.

The process of adapting an OS for virtualization is quite similar to that of porting an OS to a new target platform. In particular, virtualizing Linux amounts to changing the interface between the hardware and the lowest part of the OS, known as the Hardware Abstraction Layer (HAL). Not only is such a port time-consuming and error-prone, requiring many changes to the OS source code, but it has to be undertaken each time there is a need to upgrade the OS to a more recent version. In the case of Linux, there is currently a new minor release every three months. Furthermore, in the context of a company like VirtualLogix that develops hypervisors, each client that maintains a Linux version with its own proprietary extensions must itself do the virtualization porting task. Therefore, there is a need for documenting and automating the task of porting Linux.

In recent work, in the context of a French ANR project, we have developed the program transformation tool Coccinelle [START_REF] Padioleau | Documenting and automating collateral evolutions in linux device drivers[END_REF] for documenting and automating evolutions induced by the changes of Linux internal APIs. We refer to such changes as collateral evolutions. Coccinelle offers a language for creating semantic patches that describe modifications to be applied to all the clients of a library, in a generic manner [START_REF] Padioleau | Documenting and automating collateral evolutions in linux device drivers[END_REF]. To this end, a semantic patch is insensitive to variations in spacing and control-flow, and to other code equivalences. Coccinelle has been successfully used to perform evolutions in over 5000 driver files, drawn from Linux 2.5 and 2.6.

In this paper, we report on our experience in using Coccinelle for automating the port of Linux to VLX, the Virtual-Logix hypervisor. Because semantic patches have been designed for expressing interface changes, we conjectured that the HAL induced evolutions could be captured as a set of semantic patches. The result would enable a nearly complete automation of the ports of subsequent Linux subversions. With respect to the code written in C, the Linux 2.6.13 HAL modifications for ARM processors affect 16 files that involve 1800 code sites. Documenting these modifications using semantic patches and applying the transformations automatically using the Coccinelle tool was done in 5 weeks (including the time to learn Coccinelle) by the second author as part of his Masters degree. The semantic patches in total are 2000 lines long and contain 79 rules. To validate the approach, we applied the same set of rules to Linux 2.6.14, and were able to get a running version of Linux within a few days.

The rest of the paper is structured as follows. Section 2 gives an overview of Coccinelle and Section 3 presents the Coccinelle transformation language by example. Sec-

Semantic patch % % K K K K K K Linux C file(

Overview of Coccinelle

Coccinelle is an automated program transformation system. Automated program transformation is now starting to see wide use in the form of the refactoring engines provided by integrated development environments such as Eclipse. Coccinelle, however, diverges from such systems in that the set of transformations is not built-in, and instead must be specified by the programmer, using the semantic patch language SmPL. This requires some investment from the programmer, but provides greater flexibility. SmPL is based on the standard patch syntax [START_REF] Mackenzie | Comparing and Merging Files With Gnu Diff and Patch[END_REF], in which transformations are expressed in terms of code fragments. Initial reactions from Linux developers who have read SmPL code suggest that they find it understandable. 1 Figure 1 illustrates the usage of Coccinelle. Initially, the programmer develops a semantic patch that expresses the desired transformation. The semantic patch may be programmed directly, but in practice it is often useful to derive it from the differences found in some sample files. Specifically, one can update some typical files by hand, apply diff to compute the differences between the old and new versions, and finally generalize the result to create a semantic patch. The semantic patch is then given to the Coccinelle transformation engine along with the files that are to be transformed. The transformation engine applies the semantic patch to the files, and can either modify them in place, create new copies, or produce a record of the changes as a Linux patch, as desired. Coccinelle preserves the coding style of the original files, by preserving the preprocessor code, spacing, and comments, so that the resulting files are amenable to further development and maintenance.

In many of our experiments, we have applied Coccinelle to the entire Linux kernel. Because of the use of indexing, provided by glimpse [START_REF] Manber | GLIMPSE: A tool to search through entire file systems[END_REF], and other related strategies to reduce the amount of code that is considered in detail, this process typically requires only a few minutes. It is also possible to limit the application to a single directory 1 http://www.emn.fr/x-info/coccinelle/#feedback or a set of files if more control is required over where the transformation is performed.

SmPL Samples

In this section, we illustrate SmPL semantic patches through a series of examples. All examples are drawn from collateral evolutions that have been needed in recent versions of Linux.

Basic structure

A semantic patch consists of a sequence of rules, each of which begins with some context information, delimited by a pair of @@s, and then describes a transformation. This structure is based on that of a standard patch, which consists of a sequence of regions, each of which begins with the affected line numbers, delimited by a pair of @@s, and then describes a transformation as a sequence of lines to be added and removed. In the case of a semantic patch, the context information contains a variety of information about how the transformation should be carried out, as described below, and the description of the transformation lists the subterms that should be added and removed, as well as any required relationships between them.

As a first example, we consider the case of a set of interrupt handling flags, which in Linux 2.6.18 received new names. These changes affected over 500 files, including the file drivers/net/tg3.c. Figure 2 shows a standard patch for updating tg3.c accordingly. This patch was created by first making a copy of the file, then making the changes at the various places where it was needed, and finally using the diff tool with appropriate options to capture the differences between the old and new versions. In the resulting patch, each change is indicated by the old and new versions, marked byand +, respectively, of the complete line in which it occurs. Because each line containing a use of the interrupt handling flags is different, the patch consists of many regions, potentially one for every affected statement. The patch is furthermore applicable to only a single file, the file from which it was created.

Figure 3 shows a semantic patch for making the same set of changes. 2 A semantic patch mentions only the specific terms that are affected, i.e., the old interrupt flags and their new counterparts. Because there is no extra code specific to a given Linux file, this semantic patch can apply to any Linux file. Indeed, we can apply this single semantic patch to the entire Linux source tree to update all of the files affected by the collateral evolution, including tg3.c, at once.

A semantic patch is applied to a source file by applying each rule in turn to each of the source file functions and top-level declarations. No inter-procedural analysis is per-2 There are actually 11 interrupt flags that change names; for conciseness, we show only the ones that are relevant to the file tg3.c. The full semantic patch, which is available at our website, is similar.

---drivers/net/tg3.c +++ drivers/net/tg3.c @@ -6702,12 +6702,12 @@ fn = tg3_msi; @@ @@ -SA_SHIRQ + IRQF_SHARED @@ @@ -SA_SAMPLE_RANDOM + IRQF_SAMPLE_RANDOM formed. The transformation indicated by a rule is only applied if the rule matches completely. Furthermore, a rule is never applied to the result of its own application, so termination is guaranteed.

Metavariables and dots

The example of the previous section shows that a semantic patch abstracts away from the specific code surrounding a change site. It is, however, often necessary to abstract away from some of the code contained within the affected terms, as well. For example, in Linux 2.6.23, the function kmem_cache_create lost its last argument. To describe the transformation without being specific about the contents of the other arguments of this function, which may be different at each usage site, we introduce metavariables, E1 through E5, to represent them.

Metavariables are declared between the @@s at the beginning of the semantic patch rule. The declaration of a metavariable describes what kind of term it can match, e.g., identifier, expression, type, etc. In the case of the kmem_cache_create semantic patch, all metavariables represent expressions. The semantic patch is shown in Figure 4.

The semantic patch in Figure 4 removes a complete call to kmem_cache_create and then adds it back. Another approach is to simply remove the last argument, as shown @@ expression E1, E2, E3, E4, E5, E6; @@ -kmem_cache_create(E1, E2, E3, E4, E5, E6) + kmem_cache_create(E1, E2, E3, E4, E5)

Figure 4: Semantic patch for updating calls to kmem_-cache_create @@ expression E1, E2, E3, E4, E5, E6; @@ kmem_cache_create(E1, E2, E3, E4, E5 -, E6 )

Figure 5: Semantic patch for updating calls to kmem_-cache_create, specifying removal only @@ expression E; @@ kmem_cache_create(... -, E )

Figure 6: Semantic patch for updating calls to kmem_-cache_create, specifying only the last argument in Figure 5. It is also possible to specify that the last argument should be dropped without being precise about how many arguments precede it, by using three dots, i.e. "...", as shown in Figure 6. Dots, however, may not appear in added code.

Reusing metavariables

The previous examples merely use metavariables as placeholders. A semantic patch can also use metavariables to ensure that various parts of the code matched by a semantic patch have the same structure.

As an example, we consider the reorganization of the management of work queue structures, as was performed in Linux 2.6.20. A work queue is initialized using the macro INIT_WORK. Prior to Linux 2.6.20, this macro took three arguments: the address of the work structure, a pointer to the function that should be invoked to perform the desired work, and a pointer to the data that this function should use. Starting in Linux 2.6.20, this macro was redefined such that it no longer took the data argument; now the work function was passed the work structure when the work was to be performed. This change implied that not only did all calls to INIT_WORK have to lose their last argument, as for kmem_cache_create, but it was also necessary to store the original data somewhere so that the work function could retrieve it. In one common case, the data is the structure that contains the work structure. In this case, the revised work function can apply the macro container_of to the work structure to retrieve the desired data. The semantic patch of Figure 7 implements the transformations required in this case.

The first rule in Figure 7 detects the case where the work structure passed as the first argument to INIT_WORK is a field of the structure passed in as the data in the @ device_arg @ type struct_type; struct_type *device; identifier fn, fld; @@ INIT_WORK(&device->fld, fn -, device ); @@ identifier dataq, device_arg.fn, device_arg.fld; type device_arg.struct_type; fresh identifier workq; @@ fn ( -struct_type *dataq + struct work_struct *workq ) { + struct_type *dataq = container_of(workq,struct_type,fld); ... } Figure 7: A semantic patch implementing collateral evolutions in the use of a work structure third argument. This rule defines several metavariables: struct_type is an arbitrary type, device is an expression of type pointer to struct_type, fn is an identifier that is the name of the work function, and fld is another identifier that is the name of the field holding the work structure. As in the case of the semantic patch for kmem_cache_create, the transformation part of the rule specifies that the last argument to INIT_WORK should be dropped. The transformation part furthermore specifies that the expression matching device must appear in both the first and third arguments. Note that although INIT_WORK is a macro, it appears without expansion in both the semantic patch and the generated code. Coccinelle does not expand macros or other preprocessor directives, to maintain the code structure.

The second rule in Figure 7 updates the definition of the work function. This rule handles the case where the type of the original parameter dataq of the work function is the same as the type of the data value. The parameter dataq is replaced by a parameter with a fresh name of type work_struct, and dataq, which is likely to be used within the body of the work function, is converted to a local variable, which is initialized using a call to container_of.

This rule again uses "...", here to represent the arbitrary code in the body of the function. In general, "..." can be used whenever there is a region of arbitrary code about which nothing further needs to be specified.

The second rule uses a number of metavariables that were defined in the first rule: fn for the name of the work function, fld for the name of the field containing the work structure, and struct_type for the type of the data argument. To indicate that these metavariables should have the values established by the first rule, we give a name to the first rule, device_arg, within the rule's initial @@s, and then use this name in declaring the fn, fld, and struct_type metavariables in the second rule. In general, the first rule may apply at multiple sites in the file, i.e., if there are multiple calls to INIT_WORK. For each such call, there may be a different work function that must be updated. Coccinelle @@ expression E; @@ -if ((E->flags & (1 << TTY_DO_WRITE_WAKEUP)) -&& (E->ldisc.write_wakeup != NULL) ) { -... when = \( printk(...); \| dbg(...); \) -E->ldisc.write_wakeup(E); } + tty_wakeup(E);

... -wake_up_interruptible(&E->write_wait); The semantic patch shown in Figure 7 addresses only one of many possible cases, depending on where the data for the work function should be stored. The full semantic patch addresses cases where it is stored in a global variable, where it is already a field of an existing structure, where it must be added as a field of an existing structure, etc.

More about dots

In several semantic patches, we have used "..." to represent some arbitrary code. When "..." appears at the top-level in a sequence of statements, it means not an arbitrary block of code, but an arbitrary path in the function's control-flow graph. This path is furthermore the shortest one that has the given endpoints.

As an example, consider the semantic patch shown in Figure 8. In the first four lines, this semantic patch matches a rather complicated conditional. This conditional must then be followed along all execution paths by a call to wake_up_interruptible. The matching of "..." in terms of control-flow paths means that the conditional and the call need not be in a straight-line sequence, but a matching call to wake_up_interruptible must always be executed after the conditional, 3 to ensure that the transformation to use tty_wakeup, which encompasses both the conditional and the call to wake_up_interruptible, preserves the original behavior. Furthermore, the use of the shortest path ensures that when the pattern appears multiple times within a single function, the right conditional is matched up with the right wake_up_interruptible.

The semantic patch in Figure 8 also uses "..." at the statement level in matching the initial conditional. Here "..." is qualified with a when clause requiring that the matched code contain only printing or debugging statements. Because all of this code will be deleted, it is important to ensure that it does not have any effect on the behavior of the rest of the function. It is also possible to specify code that should not appear as a subterm within the code matched by "...", by using when with != rather than =.

Finally, the semantic patch in Figure 8 explicitly compares E->ldisc.write_wakeup to NULL, while Linux code often checks for the non-nullity of a pointer by just testing the value of the pointer itself. In general, for an arbitrary pointer-typed expression X, all of X == NULL, NULL == X, and X are equivalent. Coccinelle abstracts away from these minor syntactic differences by a collection of rules known as isomorphisms. Isomorphisms are specified using a syntax similar to that of semantic patches, and new isomorphisms can be defined by the user.

Assessment

SmPL provides a simple, code-based notation for expressing the kinds of collateral evolutions that are often needed in Linux code. The language is also in the spirit of the standard patch syntax, which is already familiar to Linux developers. We have written over 60 semantic patches implementing collateral evolutions that have been required in recent versions of Linux [START_REF] Padioleau | Documenting and automating collateral evolutions in linux device drivers[END_REF]. These collateral evolutions affect over 5000 files from various Linux versions, and our semantic patches have been sufficient to update over 93% of these files. In addition, we have identified over 150 files in which the human programmer made a mistake in performing the collateral evolution, but the semantic patch performs the transformation correctly. Finally, we have recently submitted several patches to Linux based on our work that complete previous collateral evolutions.

Applying Coccinelle to VLX

We next consider how Coccinelle can be used to perform the changes required to port an existing version of Linux to VLX. The actual porting work was done by a Masters students who had no previous experience with Coccinelle, Linux kernel code, or VLX. This task is, furthermore, quite different from that of the collateral evolutions considered previously. Collateral evolutions entail an API-level change at many places in a single version of the Linux kernel. In the case of porting an OS, our goal is to make many kinds of changes, both high and low level, across multiple versions of the Linux kernel. We find that while the approach is adequate for applying the port to closely related Linux versions, it is not sufficient when the versions start to diverge significantly in functionality.

In the rest of this section, we first briefly describe VLX, then enumerate the kinds of changes that are required to port an existing version of Linux to VLX, and finally describe our results in applying semantic patches derived from Linux 2.6.13 to later versions of Linux. VLX isolates the guest OS's from the underlying hardware. It uses partitioning of resources between the guest OS's and virtualization of resources that cannot be partitioned. Typically, physical memory is partitioned between the guest OS's while the CPU, FPU, MMU and other parts of the system such as the real-time clock and interrupt controller are virtualized.

Partitioned resources such as memory, which will only be used by a single given guest OS, are exclusively owned by that guest OS. Thus, each OS may use its own native mechanisms and policies, such as memory management, without interfering with other guest OS's. Similarly, I/O devices used by a single guest OS are assigned to that guest OS, and thus native device drivers can be re-used without any modification.

Resources that are common to more than one guest OS such as the CPU and real-time clock are virtualized so that they can be shared between those various guest OS's which need to access the resource.

In order to ensure efficiency, VLX employs paravirtualization techniques, meaning that some adaptation of the guest OS kernel is required. These changes are comparable in both effort and scope to porting that OS to a hardware very similar to the underlying one.

VLX virtualizes the CPU, FPU and MMU (if any). The CPU is shared by means of a scheduler which assigns the processor to the selected guest OS and guarantees that a real-time guest OS will get a higher priority. When a guest OS has been granted CPU access, it uses its own native scheduling policies for its applications.

If present, the MMU is virtualized so that each guest OS may use it for its own purposes. Use of the MMU by one guest OS is independent from the use of the MMU by another guest VLX provides each guest OS with synchronization (crossinterrupt) mechanisms, shared access to devices such as disk controllers, network interfaces, serial lines and inter-OS communication mechanisms through virtual devices.

Devices such as an Ethernet controller or a serial line may need to be accessed by more than one guest OS. For such I/O devices, "back-end" device drivers manage the physical hardware devices, virtualize it, and export a virtual view of that device to other guest OS. This approach provides these guest OS's with access to features of each device without actual access to the device.

Communication between the different guest OS's is provided by virtual communication devices. Different types of such devices can be configured depending upon the needs of the communicating applications. For example, a system might use a virtual Ethernet to implement a local private network that is located wholly internally to the machine, and/or it might use a virtual UART device to pass AT modem commands from one guest OS to the other.

Creating semantic patches for VLX

Porting a version of Linux to VLX requires making changes to the assembly code, the C code, and the various configuration and make files. As we are considering only the ARM architecture, these changes primarily affect files in the arch/arm directory. Because Coccinelle only works on C code, the other changes have to be made by hand. We found that between Linux 2.6.13 and 2.6.14 there was no change in the code in the context of the assembly code that needed to be changed, and thus it was possible to simply copy the new assembly code from the 2.6.13 version and to the 2.6.14 version. Updating the configuration and make files was also reasonably straightforward.

In the C code, the main kinds of changes that are required to port a version of Linux to VLX are to add the VLX include files, to add new functions, to insert calls to these new functions, and to augment structure declarations. In particular, the changes are mostly non-intrusive; the main changes required within existing function bodies are to replace a call to a Linux function by a call to its VLX counterpart.

All of the files affected by VLX must include the VLX include files. For this, a semantic patch such as the following was used: @@ @@ #include <asm/memory.h> + #ifdef CONFIG_NKERNEL + #include <asm/nk/f_nk.h> + #endif

The new code is added within ifdefs to maintain the ability to generate both the original and ported implementations. This semantic patch relies on the presence of an include of asm/memory.h in the source file to determine where to perform the modification. In general, however, it may not be the case that there is some existing include file that is common to all of the files that should be modified. SmPL thus also permits only a portion of the name of an include file to be specified, for greater genericity. The following semantic patch specifies that the new include file(s) should be added after the last asm header file include: @@ @@ #include <asm/...> + #ifdef CONFIG_NKERNEL + #include <asm/nk/f_nk.h> + #endif At the function level, 42 function definitions needed to be inserted and 11 deleted. These changes are again made within ifdefs. Adding a function is expressed similarly to adding an include, in terms of existing code that the function should be placed adjacent to: @@ @@ + #ifdef CONFIG_NKERNEL + static inline void nkidle(void) { + // the definition of nkidle + } + #endif cpu_idle(...) { ... }

Removing a function similarly involves adding ifndef around it, as follows:

@@ @@ + #ifndef CONFIG_NKERNEL cpu_idle(...) { ... } + #endif Note that in both cases, we have specified code that should be added before the function definition by indicating that it should appear directly before the function name, without mentioning the return type or other attributes that may be associated with a function declaration. Coccinelle ensures that the added code is placed before the complete function definition and its attributes, thus making the semantic patch insensitive to changes in the set of attributes that are provided. Thirty-two changes were required within existing functions. These were primarily to replace function calls by calls to their just-added VLX counterparts. A typical semantic patch performing such a change is as follows: @@ expression E1, E2; @@ doSomething(type parameter) { <... + #ifdef NKERNEL + nk_action(E1, E2); + #elseif native_action(E1, E2); + #endif ...> } This semantic patch converts calls to native_action to calls to nk_action. Metavariables are used to copy the arguments from the original call to the new one. In general, the new arguments can also be computed from the old ones in some way, e.g., reversing them, dropping some, or constructing a new value based on other information matched in the semantic patch. This semantic patch only converts calls occurring within the function doSomething. The use of <... and ...>, known as a nest, indicates that this transformation should be performed wherever a call to native_action occurs within the function body. The dots, "...", we have used previously would require that every control-flow path from the beginning to the end of the function contain exactly one call to native_action, which in the case of renaming a function is often too constraining.

In nine cases, it was necessary to add or remove a field from a structure type declaration. In this case, the semantic patch has the form of the structure declaration, some lines are specified to be removed using theannotation, and others are specified to be added before or after existing fields.

Finally, in nine cases some other top-level declarations needed to be added. These were done analogously to the insertion of a new include or a top-level function definition.

4.3 Applying the semantic patches to Linux 2.6.14 and Linux 2.6.15

The semantic patches were created from the changes required to port Linux 2.6.13 to VLX. Our goal, however, is not to simply create a patchset that is applicable to a single version of Linux, but instead to create one that can be reused over multiple versions of Linux, including both subsequent versions in the Linux source tree and versions that have been customized by a client. To determine to what extent we have reached our goal, we have applied our semantic patches to Linux 2.6.14 and 2.6.15.

In the case of Linux 2.6.14, we used semantic patches derived from the port of Linux 2.6.13 to two versions of VLX: MH 3.0.1 and MH 3.1. For MH 3.0.1, only two days were necessary to obtain a functioning VLX version of Linux 2.6.14. The main difficulty encountered was to manually fix some erroneous code that resulted from weaknesses in Coccinelle's treatment of preprocessor code. These problems in Coccinelle have subsequently been fixed. For MH 3.1, four days were required. The transformation was more difficult in this case, because it touched the implementation of third-party drivers, which changed in a more drastic way between Linux 2.6.13 and Linux 2.6.14 than ARM code in the Linux kernel source tree. These changes implied that the context code in the semantic patch before or after which the VLX code was to be added did not always have the same form in Linux 2.6.13 and Linux 2.6.14. In many cases, it was possible to make this context code more generic, allowing it to match both the Linux 2.6.13 code and the Linux 2.6.14 code. As an example, when adding one function before another existing function, the existing function can be described with an explicit parameter list or with (...) as the parameter list. The latter encoding is less sensitive to changes in the source code.

The problems encountered in porting Linux 2.6.14 to MH 3.1 persisted and multiplied in trying to port Linux 2.6.15 to MH 3.1. In particular, the memory initialization strategy appears to have changed drastically in Linux 2.6.15, thus making the patches derived from Linux 2.6.13 inadequate to complete a port.

Assessment

The success of our experiment with VLX was only partial; we showed that semantic patch could be applied to a version of Linux other than the one for which they were designed, but we found that the semantic patches were fragile with respect to certain kinds of changes in Linux code.

Indeed, as initially noted, the task of porting a Linux version is somewhat different from performing the collateral evolutions for which Coccinelle was developed. The semantic patches for collateral evolutions described in Section 3 perform localized changes to code directly dependent on generic API functions, and rely heavily on metavariables to provide genericity and to express relationships between disjoint code fragments. The semantic patches for VLX, on the other hand, are dominated by complete functions that are added adjacent to various specific functions in the existing file. There is little use of metavariables, and most semantic patches are applicable at only a single position. The semantic patches are thus not much more abstract than standard patches, and are quite sensitive to changes in the source file across multiple versions. Furthermore, while API changes tend to have an impact that is quite similar across many files, drastic changes can occur when moving from one version of Linux to another, implying that new functionalities have to be introduced in the VLX code. This lead ultimately to the inability to apply the Linux 2.6.13 semantic patches in the Linux 2.6.15 case.

Nevertheless, our experiment with Linux 2.6.14 shows that the use of semantic patches can provide some flexibility, and suggests that the use of semantic patches could be beneficial for porting closely related Linux versions, such as one customized by a client.

Related Work

The program transformation system C4 [START_REF] Fiuczynski | Patch (1) considered harmful[END_REF] is also motivated by the difficulty of keeping multiple versions of systems code up to date. C4 is inspired by aspect-oriented programming [START_REF] Kiczales | An overview of As-pectJ[END_REF], and thus focuses on inserting code before, after, and around standard points of modularity, typically function calls. This degree of expressiveness is sufficient for specifying the transformations that we have carried out in porting Linux to VLX. However, one could consider whether the ability of SmPL to express transformations on any kind of program construct could allow a more fine-grained specification of the transformations required to use VLX, at the statement level rather than the function level. This could reduce the number of lines of code that are affected by the transformation and that thus have to be updated by the client manually, when they affect client customizations. We have not yet explored this issue, but hope to do so in future work. C4 is not currently publicly available.

A number of other program transformation systems have been developed. Among these, JunGL [START_REF] Verbaere | JunGL: a scripting language for refactoring[END_REF] targets the problem of specifying refactorings. The language relies very heavily on library functions to access and manipulate code fragments. In contrast, a SmPL semantic patch is very close to C code. Another well-developed program transformation system is Stratego [START_REF] Visser | Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0[END_REF]. Transformations are expressed in terms of concrete syntax code patterns and the Stratego language. This mix of languages can make it difficult to discern the structure of the affected code. Furthermore, Stratego has no notion of the semantics of the code that is being processed, and thus is restricted to the traversal of abstract syntax trees. Coccinelle, on the other hand, follows control-flow paths, which encode the semantics of control structures, such as loops and conditionals.

Conclusion

Many specialized variants of Linux are becoming available, for virtualization and other purposes. Because Linux is an open source system, clients can adapt these versions to their needs. But there remains the difficulty of keeping such a hybrid version up to date with the many tracks of Linux development, both in the Linux source tree and in the specialized variants. In this paper, we have shown that semantic patches can help with this problem, by providing a specification of code changes that abstracts away from inessential details, and thus is applicable to multiple versions of the system. But we have also seen limitations of the approach, when the changes in the system to be patched are too drastic. We will consider how to address this issue in future work.

Figure 1 :

 1 Figure 1: Using Coccinelle

Figure 2 :

 2 Figure 2: Patch updating tg3.c to use the new interrupt flags

Figure 3 :

 3 Figure 3: Semantic patch for updating any file to use the new interrupt flags

Figure 8 :

 8 Figure 8: A semantic patch introducing the use of tty_wakeup

Figure 9 :

 9 Figure 9: An example use of VLX

Coccinelle relaxes this requirement for control-flow paths identified as error paths.

Acknowledgements

This work has been supported in part by the Agence Nationale de la Recherche (France) and the Danish Research Council for Technology and Production Sciences.

Availability

Coccinelle and associated documentation are available at http://www.emn.fr/x-info/coccinelle/


Thomas Vergnaud

Irfan Hamid

Khaled Barbaria

Elie Najm

Laurent Pautet

Sylvie Vignes

A Thomas Vergnaud

B Irfan Hamid

C Khaled Barbaria1

D Elie Najm

E Laurent Pautet

F Sylvie Vignes

Modeling and Generating Tailored Distribution Middleware for Embedded Real-Time Systems

Keywords: connectors, AADL, Ocarina, middleware, PolyORB, real-time systems

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

1

Introduction The design of distributed real-time embedded (DRE) systems is a very difficult task. The designing process must capture many requirements and constraints. Some are functional, such as algorithms to implement; others are non-functional, such as constraints on memory footprint for each node of the distributed application, or transmission times between nodes. All these parameters are specific to each system. Most distributed systems rely on a middleware to mediate communications. As it is the keystone of the application, the middleware has to satisfy all the requirements regarding both functional and nonfunctional properties of the application.

The best way to achieve these performance and reliability objectives is to build a specifically designed middleware for each application. A general purpose middleware would drag numerous components that are not needed to perform the specific functions of a given application. Conversely, a dedicated middleware would only embed the needed mechanisms and components. However, it is impossible for cost and maintenance reasons to maintain one middleware per application. Therefore, a tailorable middleware [START_REF] Vergnaud | PolyORB: a schizophrenic middleware to build versatile reliable distributed applications[END_REF] is required to ensure flexibility at a reasonable cost. In order to configure the middleware, the designer has to capture the communication and nonfunctional application specifications. Semi-formal methods such as architecture description languages (ADLs) [START_REF] Medvidovic | A Framework for Classifying and Comparing Architecture Description Languages[END_REF] typically address the issues regarding the capture process. The entire distributed system could hence be described using abstract semi-formal methods, thus gathering all information regarding the application requirements. The functional aspects of the systems are a result of the capture of the application requirements; they do not imply any assumption on the actual implementation. On the contrary, non-functional aspects are tightly related to the technical solution used to implement the system. Hence, even if these two aspects are related, they can be addressed at different stages of the design process. The concept of connectors provides a formal support to describe the interactions between the different entities of an application. Since it is a very abstract, high-level notion, it is perfectly suited to capture the mediation functions required by the application. We present a method to model connectors using UML. The abstract model must be injected into a more concrete semi-formal description; such a lower-level description integrates the deployment parameters and non-functional constraints (location of the nodes and network connections, memory footprint, etc.). The concrete description constitutes a preimplementation model: it integrates all the information describing the application. Thus, various tools can process it, to perform verification, simulation on the architecture etc. ADLs such as the AADL are well-suited for these manipulations. The concrete description can then be used to generate the actual system, with respect to the requirements primarily described in the connector definition phase. The generated code needs a runtime that provides communication and execution features (threading and tasking). This runtime has to fulfill the requirements captured in the connector and AADL modeling phases. Therefore, it must rely on a highly tailorable and verifiable middleware. The schizophrenic middleware architecture [START_REF] Vergnaud | PolyORB: a schizophrenic middleware to build versatile reliable distributed applications[END_REF] provides a good solution for such a runtime. In this article we describe our methodology to achieve such a design and generation process. We especially focus on the middleware, as it is the key component of the distributed application. We first describe high-level, abstract modeling techniques that rely on the connector concept. Second, we provide an overview of the AADL, which we use for a pre-implementation, concrete description. We then describe the schizophrenic middleware architecture. This architecture allows the generation of middleware instances as a function of the target application needs; on the other hand, it also allows the reuse of proven components and eases formal verification thereof. We describe PolyORB, our implementation of the schizophrenic architecture. Finally, we explain our approach to automatically generate application source code from AADL descriptions. We describe our application generator, Gaia, which is part of the Ocarina tool suite. It uses PolyORB as a basis for the distribution runtime.

2

Formalizing inter-component interaction During the '90s, the software engineering research community introduced the concept of connectors as elements of the architecture description of a system. Shaw defines a connector as follows [START_REF] Shaw | Procedure Calls Are the Assembly Language of Software Interconnection: Connectors Deserve First-Class Status[END_REF]: "Connectors mediate interactions among components; that is, they establish the rules that govern component interaction and specify any auxiliary mechanisms required" This is, understandably, an abstract definition; concrete examples of connectors that most software practitioners are familiar with are 1. Remote procedure calls 2. Shared variables 3. Pipes In the world of ADLs, the main artifact has been and continues to be the component. But, in the last decade, the architecture research community has been emphasizing the need to make connectors first-class citizens of the architecture description modeling phase. In [START_REF] Mehta | Towards a taxonomy of software connectors[END_REF], Mehta et. al. provide a taxonomy of connectors, classifying them on the basis of the service provided and the type. In [START_REF] Allen | A Formal Basis for Architectural Connection[END_REF], the authors introduce the method of using process algebrae to specify connectors. In [START_REF] Spitznagel | A Compositional Formalization of Connector Wrappers[END_REF], this approach is extended to allow protocol transformations and composability of connectors. The literature generally identifies the end-points of the connector that interact with the components as roles, the corresponding end-points on components are usually called interfaces.

Figure 1: A connector links components together

From figure 1, it is obvious that a connector encapsulates a certain piece of the functionality of a distribution middleware. The roles, and their definitions, can serve to specify formally the legal alphabet of a connector, i.e.: the operations allowed on a connector and their sequence of invocation. We define four different views of connectors 1. Problem statement view 2. Service view 3. Computational view 4. Deployment view Each view corresponds to a different abstraction level of the problem. The problem statement, service and computational views are defined using UML, whereas the deployment view is defined using a dedicated ADL. Our primary objective in using the UML to define connectors is to generate code for them, with an eventual transformation towards an ADL. We take the view of assuming that the underlying distribution middleware provides a set of primitive connectors, on top of which we can build more complex ones. In fact, the ultimate aim is to be able to rapidly build complex real-time services (like consensus) on top of an existing middleware.

Problem Statement View

In this view we are not concerned with how the connector performs its intended function, only what that intended function is. In other words, we are concerned neither with the algorithms involved, nor any artifacts such as interfaces, messages or ports. This view is defined using the UML. We are interested only in describing the effects of the global coordination function of the connector. We can describe these using the OCL (Object Constraint Language), which is a part of the UML.

In figure 2, we represent the class diagram for the problem statement view of a message queue connector (represented as a class). The two roles (the sender and the receiver) are also represented as classes. The classes of the connector are the two roles and the connector itself, these are adorned with stereotypes of <<role>> and <<connector>> respectively. We will use stereotypes such as these to enhance the UML meta-model [START_REF] Atkinson | Rearchitecting the UML Insfrastructure[END_REF] with metaattributes to express properties specific to connectors. Generally, roles will be specified as being an aggregation of the connector in the problem statement view (as shown in figure 2). This implies that the lifetime of the roles may be independent of each other. Note that the message queue connector is simply an example, almost all middleware implementations do provide it as a basic service.

Figure 2: The problem statement view As an example, the constraints on the message queue connector might specify that messages handed over by the sender role must eventually be delivered to the receiver role. Or that the receiver role hands messages over to its associated component following a certain priority scheme rather than in simple FIFO order. Generic OCL does not support timing constraints. But temporal extensions to OCL, such as those proposed in [8], could be used to describe real-time properties of the connector in the problem statement view.

Service View

The service view is where we will describe the connector as a monolithic UML entity. The connector is described as a single UML class in this view, with the roles being represented as ports on that class. The behavior of the connector will be described as the behavior of the connector class (in the form of State-charts). The presence of a distribution middleware is assumed in the service view, as we simply give the centralized algorithm in this view. This view will be used in the early stages of development of the system, as the distributed algorithm may not have been developed or may not have been implemented at this stage.

Computational View

The computational view is where we will split the connector up into distributed entities and attach these to the participating components. The distributed algorithm, if there is one (as in the case of a consensus protocol), will be implemented within the roles which will be attached to the components.

Figure 4: The computational view In case there is no (or a trivial) algorithm, as is the case with our example message queue connector, then the roles will only call upon the functionality provided by the middleware. In figure 4, we provide the composite structure diagram representation of the computational view for the message queue connector. The middleware is abstracted out as the bus object, which we use for simulations. This object provides functions such as broadcast and message transmission. The final goal is to have a UML model for our middleware which we will be able to plug in place of the bus object. The roles, which are now objects themselves, are embedded inside container components (C1 and C2) which contain the application components producer and consumer. The interfaces of these two application components are linked to the corresponding roles. For verification purposes, we can easily see that there must be a kind of observational equivalence between the message traces obtained at the role ports of the service view (figure 3, sender and receiver ports) and the component side ports of the role objects in the computational view, as shown in figure 4. This point is illustrated diagrammatically in figure 5.

Deployment View

This is the final view for the application architecture. It is described using an implementation ADL. The UML components are transformed to ADL components, and the connectors are embedded into these, with dependencies stipulated on the middleware portion of the architecture. ADLs provide constructs to represent standard distribution mechanisms such as shared variables, message queues, and remote procedure calls. These will be used to model the connectors that will be transformed from UML to the ADL. The metaattributes applied to the connectors in UML will become properties of the ADL artefacts such as connections and end-points that will be used to represent them.

3 AADL: a pre-implementation language As we saw in the previous section, the concept of connectors can be used to describe the communication between the components of a given architecture. Before producing source code, we have to describe the actual architecture from a deployment point of view. Thus, there is an intermediate step, in which we will describe the nonfunctional aspects, as memory footprint constraints, execution times etc, and also the actual components to implement within the application. The UML does not quite fit this purpose, since it provides rather fuzzy semantics. The AADL [START_REF]Architecture Analysis & Design Language (AADL)[END_REF] has been defined and standardized by the Society of Automotive Engineers (SAE). It is an architecture description language targeted to describing DRE systems. Thus, it focuses on the definition of clear block interfaces, and separates the implementations from those interfaces. The AADL allows for the description of both software and hardware parts of architectures. It can be expressed using graphical or textual syntaxes; a UML metamodel of AADL is defined which provides the XMI serialization, a UML profile is also available to allow practitioners to define their models using familiar UML tools and notations. To a given component type correspond zero or more implementations. Each of them describes the internals of the component: subcomponents, connections between those subcomponents, etc. Besides that, implementations of threads and subprograms can specify call sequences to other subprograms. Thus it is possible to describe the totality of execution flows in the architecture model. The AADL defines a set of standard properties that are applied to most entities (components, connections, features, etc.). Standard properties are used to specify things such as the clock frequency of a processor, the execution time of a thread, the bandwidth of a bus etc. In addition, it is possible to add user-defined properties to express applicationspecific constraints. The AADL does not allow the description of completely dynamic architectures: all the component instances that are present in the architecture must be described; there are no implicit elements. Yet, it is possible to define modes within each component implementation. AADL modes allow for the description of different component configurations: properties, connections, subcomponents, etc can depend on modes. The AADL syntax also describes the switching conditions between modes. Thus, the AADL provides support for a limited amount of dynamism: architectures can describe sets of known configurations that can be verified; the switching operation between modes is described in the AADL standard. By default, all elements of an AADL description are declared in a global namespace. To avoid possible naming conflicts in the case of a large description, it is possible to gather components within packages. A package can have a public part and a private part; only the elements of the package can access the private part. Packages can contain component declarations. Thus, they can be used to structure the description from a logical point of view. Unlike systems, they do not impact the architecture.

3.2

Using the AADL to model distributed systems Architecture models described with the AADL are semantically precise and concrete; the AADL is meant to model components very accurately. Hence, AADL descriptions represent the actual system structure: deployment information is provided by the execution platform and software components; constraints on the architecture and component characteristics are expressed by properties.

Since the elements of an AADL description are explicitly described, it is possible to perform analysis on the described architecture, such as thread schedulability; or check whether the memory footprint of the application elements are consistent with the constraints of the execution platform.

The AADL syntax provides the ability to describe message passing, remote procedure calls, distributed objects, and distributed memory. Hence, the language can be used to describe most distributed architectures. The AADL is thus able to describe distributed architectures that are subjacent to connector-based functional descriptions.

Figure 6: The deployment view Figure 6 is a graphical representation of one of the possible AADL models that could correspond to the UML model of figure 4. The producer and consumer component objects have been transformed to AADL threads; whereas C1 and C2 have been transformed to AADL processes that contain the threads. They are linked together by event data ports (AADL equivalents of message queues). The message transfer functionality will be provided by a distribution middleware. In case the connector requires algorithmic functionality that is not present in the existing implementation of the middleware, it will be represented as AADL subprograms in our model, the behavior of which will be given by the UML model of the computation view. The AADL can be seen as a "pre-implementation" language, which can be used to describe all the architectural parameters. The description of the algorithms is not in the scope of the AADL, since the language only focuses on architectural concerns. Yet, it is possible to use the AADL properties to host the behavioral descriptions of the components (e.g.: by identifying the piece of source code that implements the algorithm). Therefore, the AADL can be used as a backbone to host all the aspects of the system description, both functional and nonfunctional.

3.3

Requirements for an AADL runtime AADL is precise enough to allow the description of the application structure (using software components) and the deployment information (using the execution platform components). Given a precise enough description, we can then aim to automatically generate and deploy a complete application from its AADL description. Such an application is likely to run on top of a runtime that provides the functionalities required to ensure correct execution. An AADL runtime should at least support the execution of threads. Since we design distributed applications, the AADL runtime should also provide support for the different distribution models that can be described in the AADL. Thus, the AADL runtime is an execution middleware which provides two main services:

• The management of the AADL threads that support the execution of the AADL application on each node

• The management of the communication between the application nodes This underlying middleware has to provide guaranties regarding its reliability and its ability to meet the constraints described in the AADL description (typically memory footprint).

4

Framework for an adaptable AADL runtime An AADL runtime has to provide traditional middleware functionalities such as distribution as well as thread management. Different middleware architectures have been proposed to allow the middleware to be configured as a function of application requirements. In [START_REF] Schmidt | Applying Patterns to Develop Extensible and Maintainable ORB Middleware[END_REF], the authors proposed the means to configure the middleware. In [START_REF] Singhai | Quarterware for Middleware[END_REF], the authors proposed the concept of generic middleware that is configurable and which allows the selection of a distribution model to suit the application. Schizophrenic middleware extends the idea of configurable and generic middleware by defining an adaptable architecture that allows for the verification of middleware properties. The schizophrenic architecture allows the adaptation of the middleware to meet the needs of the target application. The schizophrenic architecture enforces the principle of separation of concerns, and allows for proven code and the reuse of components. Thanks to its clear structure, it lends itself well to formal verification of properties.

producer consumer

C1 C2

4.1 A three-layer architecture

The schizophrenic architecture comes with the concept of personalities and with the notion of canonical middleware services. In this architecture, middleware functions are decoupled into application and protocol level personalities connected to the neutral core, on which all personalities rely. Application personalities constitute the adaptation layer between the application components and the middleware. They provide APIs to register application entities with the neutral core layer.

Application entities can interoperate with the core to allow the exchange of requests with remote entities (like CORBA or DDS APIs).

Protocol personalities handle mapping of requests (representing interactions between application entities) onto messages exchanged through a communication network, according to a specific protocol. The requests are received either from application entities (through an application personality and middleware core), another protocol personality or a node in the middleware instance. The Neutral Core acts as an adaptation layer between application and protocol personalities. It manages execution resources and provides necessary abstractions to transparently pass requests between protocol and/or application personalities in a neutral way. It is completely independent from both application and protocol personalities, enabling the selection of any combination of them. Figure 7 depicts this first view of the schizophrenic architecture.

Building an AADL runtime based on the schizophrenic architecture actually consists of building an application personality. The exact structure of this personality depends on the distribution features used in the AADL architecture model of the application.

Configurability

The neutral layer provides common services that are typically part of all middleware implementations. Seven canonical services are isolated, each of which implements one fundamental aspect of a middleware:

• The addressing service gives a unique identifier within the distributed system to each entity

• The binding service provides mechanisms to associate the interacting objects with the resources supporting this interaction.

• The representation service allows the translation of data into a representation suitable for transmission over the network

• The protocol service allows entities present in different nodes to communicate

• The activation service associates implementing objects to incoming requests

• The execution service assigns execution resources to process incoming requests These services are shown in figure 8. The services defined in the schizophrenic architecture can be reduced to well-known abstractions (mainly pipes and filters). The µBroker coordinates these services. It is in charge of resource allocation, and of data propagation through the middleware. It is the most critical component in the middleware since it manipulates tasks and I/O. All the behavioral properties of the middleware are satisfied in this central component; the services are reactive. The combination of the selected implementations of the services allows for the instantiation of a middleware tailored to the needs of the application. As an example, the activation service can manage incoming requests according to priorities rather than with a simple FIFO protocol. This selection of service implementations impacts non-functional properties such as memory footprint and execution time.

Reliable execution middleware

The schizophrenic middleware architecture allows for proven components and reuse of basic services, and aims to conserve proofs. These components can be separately modeled and generated; the models can be verified using formals methods (e.g.: colored Petri nets). This helps produce a verified, reliable middleware instance. Besides, as the µBroker handles all the behavioral aspects of the middleware, it manages the scheduling and dispatching of threads. Thus, a schizophrenic middleware satisfies the two requirements stipulated for an AADL runtime; namely, that it be a distribution middleware and manage threads. PolyORB 1 is an implementation of the schizophrenic middleware architecture. Thanks to this architecture, 1 http://polyorb.objectweb.org/ PolyORB has been modeled and formally verified using colored Petri nets. They were used to model the µBroker. The work done in [START_REF] Hugues | On the Formal Verification of Middleware Behavioral Properties[END_REF] proved some essential properties such as absence of deadlocks, absence of buffer overflows, and fairness. Figure 8: PolyORB services Thus, PolyORB is a highly tailorable middleware that proposes a canonical architecture and a methodological guide to building a specific distribution platform. CORBA, and also DDS, MOM, DSA and advanced specifications like FT-CORBA and RT-CORBA are already available.

5

From AADL description to application PolyORB constitutes an appropriate basis to implement an AADL runtime. It provides all the required functionalities regarding thread scheduling and communication management. Since it is tailorable, it can thus be instantiated to meet the exact application requirements. Its clear architecture facilitates the verification against different properties such as no deadlocks, no buffer overflows etc. In this section, we explain how to generate an executable application from an AADL description.

Separation of concerns

In the generation process, we must handle two different things:

•

The generation of the application code

•

The generation of a configured AADL runtime to support the execution of the AADL application on each node The AADL subprograms model the application itself, while the AADL threads and processes represent the runtime. Indeed, all communications are described by the thread features; and the thread implementations contain the call sequences that drive the application subprograms. The processes define the application nodes in which the threads are executed. The execution platform components describe the deployment information for the runtime: location of the nodes, constraints on the communications between the nodes, etc. Thus we have a clear separation of concerns in the architecture description. In order to ensure consistency between the AADL description and the actual executable system, the application generator should process the AADL components. In order it is the runtime that controls the application and not the other way round, application components should be enclosed in wrappers. The runtime is the key element of the executable system, since it is the active part-the application is the passive part.

Design of the AADL runtime

In order to set up an appropriate runtime, the generator has to take into account two kinds of parameters:

•

The structure of the application on each node, e.g.: the required communications, the number of AADL threads, etc Thus, the generation of the AADL runtime should be a two-step process (see figure 9): 1. Gather the deployment information in order to select the proper components to use in the execution middleware 2. Generate the middleware by assembling the selected components, and generate an adaptation layer to control the application wrappers There are different ways to perform the component selection. We can rely on the existing configuration process of PolyORB. This allows for the selection of various implementations for the fundamental services and the configuration of the µBroker structure. This approach provides an efficient way to build a prototype of the middleware. We can also model the different parts of the middleware in the AADL. Since the schizophrenic architecture provides a clear and modular structure, it greatly facilitates the AADL modeling process. The middleware is then a set of AADL subprograms that are called by the µBroker. The µBroker itself cannot be described in AADL, since it mainly consists of behavioral elements. Following this approach, the major part of the middleware can be seen as being a part of the application. The µBroker is then the actual AADL runtime. Since the middleware components are modeled in AADL, we can integrate them in the verification and simulation process of the application. Thus, each application node is structured in two parts: a minimal runtime (the µBroker) which is modeled in Petri nets to ensure properties regarding the execution of the local node; and the application, which can be processed to compute worst-case execution times, total memory footprint, etc.

5.3

Gaia, an application generator for AADL

In order to experiment on application generation from AADL descriptions, we created an application generator named Gaia. Gaia is part of the Ocarina tool suite, developed at Télécom Paris . It provides a set of lightweight tools to describe distributed architectures in AADL; the descriptions are then transformed to distributed systems driven by a tailored runtime based on PolyORB. Gaia is structured in two parts: a translator from AADL to programming language and a runtime generator. The translator handles the AADL subprograms and only depends on the target programming language. The runtime generator is to be used in two ways: either to use PolyORB or only the µBroker. In the first case, we generate an AADL application personality and configuration files for PolyORB; this way we use PolyORB as a high level runtime to prototype applications. In the second case, the generator expands AADL threads to create AADL models of the schizophrenic services from the thread properties; thus we have a complete model of the application in AADL. This enables architecture analysis and verification; the architecture can then be transformed to source code, using the µBroker as a runtime.

6

Conclusion Building DRE systems requires the capture of a wide range of requirements, either functional (algorithms to use etc.) or non-functional (execution time constraints etc.). We therefore need a methodology based on a formal approach to assist the design process. We proposed a three-step methodology. We first design the system from a very abstract point of view, to identify the functional properties of the system. Architectural constructs such as connectors provide good support to model interactions between the nodes of a distributed application. They can be described using semi-formal syntaxes such as the UML.

We then have to describe a concrete model of the distributed application in order to capture the nonfunctional aspects of the system design. One of the objectives of our research is to be able to provide rules to automate the transformation of models from UML to AADL. The AADL perfectly matches the requirements of such descriptions: it allows the representation of both software and hardware parts of a system, all entities of the language have clear semantics and properties can be associated to every element of the architecture to capture the system characteristics. Thus, the AADL can be used as a pre-implementation language to have a very concrete representation of the whole system. It is then possible to generate source code from the AADL description. This source code is to be executed by a runtime that handles the communications and the scheduling of the application threads. In order to support the execution of the application, we extended the concept of middleware to consider execution middleware, which can be compared to a virtual machine. The execution middleware schedules application threads and manages communications. In order to build an efficient system, the middleware structure (i.e.: its actual configuration) must fit the application requirements. We introduced the schizophrenic middleware architecture as a solution to tackle the middleware specialization problems. We tested our approach using Gaia and PolyORB to generate distributed applications. Our results have been encouraging in that we have been able to

Figure 3 :

 3 Figure 3: The service view In figure 3, we give the composite structure diagram of the service view of our message queue connector. The connector consists of two roles; sender and receiver, here signified by the ports on the MessageQueue class. The algorithm of

Figure 5 :

 5 Figure 5: Equivalence among viewsFor verification purposes, we can easily see that there must be a kind of observational equivalence between the message traces obtained at the role ports of the service view (figure3, sender and receiver ports) and the component side ports of the role objects in the computational view, as shown in

Figure 7 :

 7 Figure 7: the three-layer schizophrenic architecture

•Figure 9 :

 9 Figure 9: Generation process for the AADL runtime

2

 2

  Subprograms model procedures such as those in C or Ada. Threads model the active part of an application, i.e.: the units of execution; processes are memory spaces that host executing threads. Processors represent microprocessors and a minimal operating system (mainly a scheduler). Memories model hard disks, RAMs, etc. Buses model all kinds of networks, wires, etc. Unlike other components, systems do not represent anything concrete: they actually create building blocks to help structure the description. At the top-level, a system component contains all the component instances that make up the application. Each component has an interface (called component type) that provides features (e.g.: communication ports). Components communicate with each other by connecting their features.

	3.1 An AADL description is made up of components. Overview of the AADL The AADL standard defines software components (data, threads, subprograms, processes…), execution platform components (memories, buses, processors…) and hybrid components (systems). Components model clearly identified elements of the actual architecture. Most components can have subcomponents; thus, an AADL description is hierarchical. Component declarations have to be instantiated as subcomponents of other components in order to model architectures.

http://ocarina.enst.fr/


Pr G Motet

J.-P Seuma Vidal

Jean-Pierre Seuma Vidal

Importance of Certification for Embedded Real-Time Systems

Keywords: certification, safety, real-time systems

Dependability of the LESIA laboratory

1. Statement: Increasing of embedded real-time systems responsibilities 1.1 Quantitative increasing Embedded real-time systems are now integrated in numerous products used everyday: transportation vehicles (aircrafts, cars, trains, etc.), communication means (phones, switchboards, satellites, etc.), medical devices (tele-echography, pacemakers, etc.), systems producing energy (nuclear plants, etc.), consumer goods (robots, etc.) or services (cash dispensers, etc.).

The increasing of the number of such systems is correlated with the increasing of the number of the services they offer. This is mainly due to the software technology which, at first, allowed the improvement of the former functionalities replacing other technologies for implementation. Software is now used to offer functionalities to compensate for inadequacies of the capacities of users or other products, taking charge of new responsibilities. Finally, embedded real-time systems are now completely integrated in global systems and cannot be considered as independent elements. In the following sub-sections, these new characteristics and roles of software technology included in real-time embedded systems are analysed to highlight their consequences.

Improvement of performance and functionalities

The increasing of software technology in real-time embedded systems is at first due to the clients who require more reliability. Indeed, this technology is not prone to ageing. Thus, the electronics systems embedded in cars were developed to manage the ignition of sparks. The executed program takes into account the position of the piston deduced from the position of the driving shaft. This substitution of a software technology for an hardware technology initially allows the ignition system reliability to be increased: no more contact points to be changed or tuned.

Then, the software technology was used as it allows to implement sophistic functions, that is, functions whose behaviour is complex and adaptable to the changing of the environment parameters values. Thus, the functional flexibility offered by the software realisation permits to control dynamically the spark ignition depending on the values of various parameters such as the engine temperature or speed, in order to reduce the consumption, for instance thanks to the ignition advance. The valve opening controlled by a computer instead of a camshaft also increased the engine capabilities (horsepower) taking the environmental characteristics (engine temperature, etc.) into account. Therefore, the software technology improves the performance of functionalities previously offered.

As software allows complex behaviours to be expressed, new services were offered afterwards. The air conditioning control considering inside and outside temperatures, the adaptation of the power steering considering the car speed, or the changing of the shock absorber laws taking the driving style into account are three examples.

However, in all cases, these functionalities provide more comfortable cars but are not absolutely necessary.

These new functionalities were largely distributed thanks to the low production cost but also the relatively low development cost offered by the software technology: implementation is made easier by compilers, prototypes can be quickly designed, etc. These characteristics associated with the flexibility of this technology encouraged designer to imagine new products.

Take charge of shortcomings

More recently but with an increasing importance, embedded real-time systems implemented with software technology aim at overcoming shortcomings not due to these systems but to other elements in their environment. Thus, more and more responsibilities are transferred to these systems.

Responsibilities to take charge of bad use

At first, a part of the responsibilities previously taken by users is now delegated to these systems. In particular, the requirement of the absence of unacceptable effects due to a bad use of the system, is transferred from the user to the system. Hereafter, we mention some examples coming from automotive domain.

The excessive emission is an unacceptable harm which may be due to a bad driving. Such a situation occurs if the driver steps too much on the accelerator when the car climbs up a hill. To handle this bad behaviour of the user, a device analyses the exhaust gas and the accelerator cable is replaced by a numeric transmission allowing the engine control system to limit the pollution, reducing the injected fuel despite the driver action on the accelerator. Thus, the actual engine acceleration is not only due to the driver but partially delegated to the computerised system.

Injuries or deaths due to accidents are a second type of harms. Their prevention is now partially delegated to embedded real-time software applications. For instance, the ESP (Electronic Skid Prevention) prevents skids, maintaining the car on its trajectory when a car is entering a bend too fast. So, this system is a palliative device to a bad driving. The system which pressurises the hydraulic braking circuit when the driver removes quickly his/her foot from the accelerator, or the ABS avoiding the blocking of the wheels are other systems preventing accidents when car speed is too high. The systems controlling the airbags are useful to reduce the effects of these accidents.

Responsibilities to take charge of inadequacies of other technologies

Besides they have to overcome the user failures, the embedded real-time software applications now have to take charge of unacceptable effects of the other technologies used in the product. These effects are due to characteristics of hardware technologies such as the ageing. For instance, the software application has to adapt its behaviour to the deteriorated states, or sometimes the failures, of the external hardware components. For example, to respect acceptable emission levels, embedded programs have to take into account the change of the surrounding elements: deteriorated states of mechanical parts, of the hydraulic circuits, blocking of valves such as the EGR (Exhaust Gaz Recirculation).

Responsibilities to take charge of design faults of other components

To complete this list of new responsibilities, we must mention the fact that embedded software now has to handle design faults of surrounding elements. For instance, a car manufacturer added an ABS with an electronic braking distributor to prevent harms for a car mechanically unstable at braking time.

Responsibilities to act and to take decisions

Thus, more and more responsibilities are transferred to embedded real-time software applications. These delegated responsibilities at first concerned the realisation of actions decided by humans or external devices. Now, certain applications take decisions. In automotive domain, the ABS may release the hydraulic pressure to avoid the blocking of the wheels, despite the action of the driver on the brake pedal.

The complete autonomy to take decision and to realise the associated action is illustrated by the systems opening and controlling the airbags. The preservation of the directional stability of the car is another role delegated to real-time software, previously played by the driver.

Integration

A last significant changing for embedded real-time software concerns the progressive integration of these systems in products. Previously, these software applications were isolated, providing specific and independent functions. Then, they were associated with other elements of a product at first by service relationships (a master using fonctionalities offered by software applications) and finally by cooperation relationships (exchanging data). Therefore, complex interactions now exist with humans, mechanical devices or other real-time software applications.

Again, real-time systems embedded in cars provide numerous examples. They interact with the driver and the environment using sensors (temperature, pressure, position of the drive shaft or of the steering wheel, etc.) and actuators (injector or valve opening, hydraulic braking circuit, etc.). They also interact together exchanging data on the CAN bus. For instance, the system controlling the braking interacts with the engine control system, the power steering control system, the absorber control system, etc., to prevent a car to skid or to overturn. Indeed, it needs to reduce the speed, to modify the wheel direction and to harden the absorbers. This strong coupling between an embedded real-time application and other components increases the harms caused by a failure of this application due to the contamination effects.

2. Requirements: Assurance of absence of risk 2.1 Increase in risks to increase the benefits As described, the embedded real-time systems now have more and more responsibilities. This assignment aims at increasing the benefits thanks to software technology. In automotive domain, these benefits concern the decreasing of the pollution rate, of the accident probability or severity, and of the production costs. Everybody accepts these benefits but also has to wonder about negative effects of the potential failures of these systems.

For instance, nowadays, the steering shaft transmits the rotation of the steering wheel to the wheels. This shaft is at the origin of numerous sever injuries when an impact occurs. The replacement of this mechanical device by a software program detecting the steering wheel movement and acting on the wheels could avoid such harms. It also offers numerous other advantages as the possibility to adapt the effect on the wheels of the orientation of the steering wheel depending on the car speed, making easier the driving in cities. Unfortunately, we also can imagine the harms caused by a dysfunction of such a system, particularly when the car is running fast.

The increasing of the benefits provided by embedded real-time software also implies a harms' severity increasing if a failure occurs.

The harms concern the human injuries but also the trade. In particular, the confidence of the consumers in products may decrease strongly and may court actions against firms.

Requirements for more guarantees

The increasing of the responsibilities transferred to embedded software and the complexity of their coupling with other systems lead the citizens but also the firms, the engineers and the authorities to wonder about the confidence they can attribute to these applications, that is about the absence of the harms they can cause.

The citizens

The citizens use everyday products integrating embedded real-time software. They are bothered by their dysfunction and are worried about the potential harms they can cause on their health, money, etc.

Their confidence in the products realised with conventional technologies is based on a recognised know-how of the manufacturers. For instance, a client buys a car of a given trademark because the reliability of its engine was tested by previously produced models and progressively improved, or because the trademark capabilities in creating new cars are wellknown. Such a situation does not exist for complex real-time software embedded in these products and the previous experiences justify the existing suspicion (car recalls for instance).

The firms

Firms and engineers perceived the benefits which are provided by the software technology: implementation of complex functionalities, reduced costs, etc. They are also aware of the harms which can be caused by the computing systems integrating their products: physical harms to the users and their environment but also trade harms particularly on the brand image of the firm, and financial risks due to high penalities or damages to be paid to displeased clients.

The financial proceedings against Toyota due to a failure of an embedded real-time software have to be studied as they provide a typical example. Coming from USA, we may imagine similar lawsuits in Europe in the near. Beforehand, let us specify that similar issues occurred to other/all manufacturers. However, they were generally not promoted through media. On the contrary, the problems met by Toyota were at the origin of numerous communications.

On September 1998, the ARB (Air Resources Board) of California required of Toyota the recall of 330 000 cars sold in California. The electronic system checking emissions (on-board diagnostic system) may not detect a too important gas emission and so does not signal such a situation to the driver [START_REF] Cepa | California Environmental Protection Agency[END_REF]. This system provides one more time an illustration of the transfer of responsibilities previously mentioned: the exceeding rate of emission has to be detected by a system and not by the car owner. The cost to repair was 250$ per car. Thus, the global cost reached more than 82 millions $. This is probably one of the reasons of the Toyota refusal to recall the cars. Moreover, the firm signalled that the involved systems received an agreement. The case was transmitted to the court of California (Sacramento).

In July 1999, at the US Environmental Protection Agency request, the US Department of Justice repeats the demand at federal level [START_REF] Usdj | [END_REF][START_REF] Olson | CNN Web site[END_REF]. The court records that the failure affects 2.2 millions of cars sold in USA between 1996 and 1998. It also mentions that the failure comes from a program design fault and claims more than 58 Billions $ of civil fine for the harms caused to the environment (pollution) and citizens. Finally, it requires the recall of the cars. The comments of the judgement show that the court considered the transfer of responsibilities from the driver to the software and consequently to the designer: "Companies that take shortcuts with their vehicle pollution-control systems shortchange the consumer and our environment. [...] We will hold them accountable" (Lois Schiffer, Assistant Attorney General for Environmental affairs).

The engineers

Engineers have a quite low confidence in the software they produce. This is shown by the huge duration spent to test their programs (often 40 to 50 % of the total development duration). This duration is, on one hand, due to the time needed to diagnose and to correct detected faults, but also, on the other hand, aims at increasing the assurance that they want to have on the product behaviour correction.

The engineers are aware of the harms which can be caused to the users but also to themselves as the user harms may have strong impacts on their careers. Indeed, the harm caused by the system is often due to a failure of its behaviour. The fault in the program generally comes from a human error of the engineers activities.

The authorities

The highlighted issues also concern the national or international authorities. They are faced with a dilemma.

-The demand of assurance from citizens is very high as the harms caused by embedded software failures may affect the society (pollution, health, transportation, etc.).

-The very high expenditure necessary to provide such assurance may increase the prices of the products whereas a strong concurrency exists. Some court orders may also put a brake on the development of embedded software technology.

Moreover, the non respect for assurance given to the citizens has an important political impact.

Solution: Certification

The Toyota issues show that, even if the harms due to embedded software failures affect each person (respiratory troubles, etc.), they have to be handled by the authorities. They must -determine the harms and their origins to start legal proceedings against the firm, but also -prevent these harms providing a high level of guarantee to the citizens. This guarantee is obtained by the certification of these systems. Certification is defined as [EN4502, 1993] the procedure by which a third-party gives written assurance that a product, process, or service conforms to specified requirement. The requirement may concern various points of view. In this paper, they deal with safety, that is the absence of unacceptable risk [ISO51, 1999].

The product user is the first person interested in certification as he/she is the first affected by the harms caused by these products. Moreover, thanks to the existence of a certificate, he/she does not have to assess him/herself the potential damages these systems can provoke.

For the firms or the designers, the certification does not only provide a trade advantage. It provokes a transfer of a part of their responsibilities to the certification authority. One more time, the legal proceedings against Toyota illustrate this assertion. From 1999, Toyota signals that its failing on-board diagnosis system received a certificate from the Californian Air Resources Board, after experiments in their laboratories. Thus, Jim Orson from Toyota headquarters said in July 1999: "We [...] firmly believe our vehicules comply with the testing procedures as originally written" [START_REF] Olson | CNN Web site[END_REF]. This argument was accepted by the Californian court which decided the 24 February 2000 that the California Air Resources could not require a global recall of the 337 000 cars concerned in California [START_REF] Apsa | APSA (Automotive Parts and Service Alliance)[END_REF]. Implicitly, this decision considered ARB as partially responsible of the pollution due to the oversight of their verification. At the same period, the federal ERA (Environmental Protection Agency) required a national recall.

Finally, in California, a settlement was signed the 7 march 2002. Toyota accepted to pay 7.9 millions $ to finance projects on environment and to increase the duration of the guarantee of their embedded systems from 3 to 14 years or from 50 000 miles to 15 000 miles. Moreover, the court does not require the callback of the 33 000 cars specifying that ARB certified the system but Toyota did not provided certain pieces of information useful to the certification process [START_REF] Usdt | Toyota CARB reach OBD settlement[END_REF]] [CEPA, 2002].

An equivalent settlement occurs at the federal court on the 7 march 2003. Toyota will spent 34 millions $ including 20 millions $ to reduce the emission of 3000 public vehicles (scholar buses, etc.) and was fined 500 000 $ [START_REF] Usdj | United States settles clean air act cases against Toyota[END_REF]. This amount is far from the initial 58 billions $ and the recall of 2.2 millions of vehicles required [ARB 2003]. This moderated judgement is due to the obtained certificate. However, it does not minimise the responsibilities of systems designers. Indeed, the judgement also announces clearly the future consequences if these responsibilities are not taken. Thomas L. Sansonetti of the Environment and National resources Division wrote: "Vehicule manufacturers must make all required disclosures so that EPA [Environmental Protection Agency] can carry out its responsibilities to ensure clean air. [...] This settlement makes clear that we will enforce these requirements vigorously".

Problem handling

The transfer of responsibilities from the user to embedded real-time software applications or the attribution of new responsibilities to these systems, correlated with the assurance required by users may have severe consequences.

-For the designers, these features may reduce innovation: even if the benefits of software technology is well-known, the potential damages also exist. In particular, the use of recent technologies such as Object-Oriented languages arouses suspicions.

-For the firms, these features may strongly increase the cost of the products to provide the required assurance.

-For the certification authorities, these features may increase their requirements and the duration spent to attribute a certificate, to obtain more and more guarantees. This will increase the cost of the products and delayed their availability on the market.

To prevent these drawbacks, most of the proposed solutions -concern separated domains (avionics, space, medical systems, transportation, etc.) whereas the problems are generic, -mainly study the implementation technologies whereas numerous issues concern the system design.

The research activities started in the framework of the project "UML & Certification" aim at -going back to the basic requirements of certification proposing a generic approach based on risk management [IS073, 2002],

-studying the risks associated with the UML modelling technology, -examining how the risks associated with each embedded real-time software application can be expressed and handled using UML, in order to provide to the user, the designer and the authorities assurance of the absence of risk of unacceptable harms.

-22 -23 January 2004