Keywords: transformation, refining, model

Raffinage de modèles à l'aide de transformation de modèle basé sur les règles Résumé : Une partie des langages de transformation de modèle a été définis pour réaliser facilement la traduction syntaxique et sémantique de modèles d'entrée en lecture seule vers des modèles de sortie en écriture seule. Bien que cette approche ai fait ses preuves dans de nombreux cas pratiques, elle n'est pas directement applicable pour les transformations devant modifier leurs modèles d'entrée, comme pour les opérations de refactoring. Dans cet article, on étudie l'adaptation d'un langage de transformation de modèle au problème posés par les transformation en place, en fournissant une approche systématique du problème, en comparant les solutions alternatives et en proposant une sémantique de transformation permettant la résolution de ce problème en ATL.

Mots-clés : transformation, raffinage, modèle

Introduction

Most application scenarios of Model-Driven Engineering require at some point to automatically generate new models from existing ones, a process called model transformation. For a subset of these transformations the output model is mostly identical to the input model, with the exception of a set of changes that is relatively small compared to the model size. In this paper we refer to this special kind of transformations by the term refinement transformations (or simply refinements). An example of such refinement transformations would be any implementation of model refactorings [START_REF] Biermann | Precise Semantics of EMF Model Transformations by Graph Transformation[END_REF][START_REF] Straeten | A Formal Approach to Model Refactoring and Model Refinement[END_REF][START_REF] Judson | A Metamodeling Approach to Model Refactoring[END_REF]. Since models can be considered a particular kind of graphs, a natural way to address model refinement in a rule-based way, is reusing existing graph transformation languages. In such languages the transformation is structured in the recursive application of graph-rewriting rules on the input model. Indeed several approaches make use of graph transformations for model refinements ([19, 7, 1]). While these methods are very powerful and generic, they may look too complicated for practical refinement tasks for a non-expert user. They are based on formal frameworks, and the user needs to have at least a superficial knowledge of the formal background to avoid to incur in theoretical problems like rule conflicts, termination and confluence.

Moreover, graph transformations are natively recursive, meaning that rules are executed over the processed model until a termination state is reached. While recursive rule application can be the natural solution for several problems, several others require a more controlled application, e.g. onestep, of the transformation. Applying graph transformation languages to these problems requires the developer to explicitely disable recursion using technical means (e.g. ad-hoc negative application conditions or the introduction of supporting nodes). These workarounds are not only tedious and error-prone, but they hamper the abstractness in representing the transformation logic. Also, integration of graph transformation tools in popular modeling frameworks like EMF is still limited.

In this paper we propose an alternative solution for rule-based refinement transformations. This solution integrates some of the benefits of graph-transformation approaches on already existing popular Model-to-Model Transformation Languages (M2MTL) to provide designers with an easy and efficient approach for the definition of refinement transformations.

M2MTLs are domain specific languages born to allow the translation, in a simple and abstract way, of one (or more) input models into one (or more) output models. The translation is performed at the same level of abstraction of the manipulated models, by talking about model elements as firstclass citizens. In this way the transformation does not require the encoding of models in specific formalisms like graphs, XML trees or textual serializations. The transformation logic results more abstract, being clean from technical details about the particular representation of the model.

To keep their semantics relatively simple the most popular M2MTLs like the AtlanMod Transformation Language (ATL) [START_REF] Bézivin | First experiments with the ATL model transformation language: Transforming XSLT into XQuery[END_REF] or OMG Query View Transformation (QVT) [START_REF]Object Management Group[END_REF] make strong assumptions on the direction of model parameters, forbidding a model to be both input and output of the transformation. In this way, rules are never applied recursively to their own output. This design choice makes M2MTLs a more natural language to address non-recursive problems, freeing the developer from caring about disabling recursivity when not needed. Moreover this simplification has the benefit of making transformations immune to the rule-conflicts and termination problems of graph transformations. Real-world experience has shown that this simplicity, that appears to reduce the computational power of M2MTLs, does not hamper their practical applicability to common usage scenarios. This is, for example, pointed out by the number of applications in the Eclipse.org ATL transformation Zoo [6].

Nevertheless, the application of these M2MTLs to refinement transformations is not straightforward: refinement transformations do not strictly adhere to the input-or-output assumption of the model-to-model paradigm because they need to modify their own source model. If developers want to use current M2MTLs languages, they can only simulate a model refinement by writing a transformation that 1) copies all the source model elements into a new target model, and 2) makes the small changes while performing the copy. However, in this paper we will show that this naive solution has important drawbacks: 1) The development of the copy rules is tedious, the transformation code unnecessarily bulky, and the change logic is drowned in the copying code, making the refinement transformation difficult to read; 2) The execution time of the refinement increaese, since matching and copying all the unchanged elements is done anyway; and 3) This semantics is incompatible with some important use cases, like the modification of a model for live refactoring. Live refactoring requires to keep the element identifiers unchanged to maintain the live links with the environment. This is only possible by directly operating on the input model, without performing a copy of it.

For these reasons this paper aims to show that a special support to refinement can make M2M transformations more suitable to refinement cases. In the process, we investigate the general problem of applying model-to-model transformation languages to refining transformations. We also provide a prototype implementation of the proposed approach as a novel in-place semantics for the ATL refining mode.

The paper is organized as follows. Section 2 introduces the running case of the paper. Section 3 lists the design dimensions and possible strategies for implementing a refinement support in M2MTLs. Section 4.1 illustrates the different kinds of support that ATL has provided to refinement transformations so far. Section 4.2 describes the new refinement semantics for ATL proposed in this paper. Section 5 investigates the related work and, finally, Section 6 gives some concluding remarks.

Motivating example

As a running example for this paper, we introduce a refining transformation over a simplified version of a Class Diagram, conforming to the metamodel in Figure 1. The ClassDiagram metamodel describes a minimal class diagram, including classes, attributes, operations and datatypes. Each Class contains ordered sets of Attributes and Operations. Attributes are instances of a Class or DataType and Operations have a specific returnType (we omit parameter passing in this example). The scope of Attributes and Operations is defined by the isPrivate boolean attribute.

As an example of refinement we consider the Public2PrivateAndGetter transformation. It is a small refactoring that modifies a public attribute of a given class, by making it private and adding to the class the corresponding getter operation to retrieve its value.

Public2PrivateAndGetter is clearly a simple one-step model transformation, that does not require the recursive structure of a graph transformation language. Therefore, the transformation can be implemented using a traditional M2M transformation language. That way, the initial version of the class diagram will be considered as the input model and the privatized version as the output model. Implementing a refining transformation using the standard M2M semantics requires to explicitely write the code managing the unchanged part of the input model. In a rule-based language this involves writing: 1) simple rules to copy the elements of the types not influenced by the refinement and 2) more complex rules that explicitely match and copy the unchanged elements whose types are involved in the refinement. For example listing 1 shows the standard ATL rules for the Pub-lic2PrivateAndGetter refactoring. In the example:

• The rule PublicAttribute contains all the refactoring logic, matching the public properties that don't have an associated getter and copying them to the output, changing their visibility. The same rule generates a new getter operation setting its name and return type.

• The rules CopyClass, CopyOperation and CopyDataType are simple rules, that copy every property of the matched element.

• The rule CopyAttribute is a copy rule too, but it explicitely matches the attributes not involved in the refactoring, by inverting the guard of PublicAttribute.

However, when using current M2M languages, designers will need to face several problems:

• As shown in the example, even in very simple cases, using the standard transformation semantics for refinement results in long code (at least a rule for each concrete metamodel class) where the refinement logic is mixed with the copying logic. The parts of the transformation that actually perform changes are obfuscated by the rules that are just copying elements. This makes the refinement logic difficult to understand. )

. returnType = s . type ) ) t o t : ClassDiagram ! Attribute ( name <-s . name , owner <-s . owner , isPrivate <-true , type <-s . type ) , getter : ClassDiagram ! Operation ( name <-'get' + s . name . toUpperCase ( ) , owner <-s . owner , isPrivate <-false , returnType <-s . type
t o t : ClassDiagram ! Attribute ( name <-s . name , owner <-s . owner , isPrivate <-s . isPrivate , type <-s . type ) } r u l e CopyOperation { from s : ClassDiagram ! Operation t o t : ClassDiagram ! Operation ( name <-s . name , owner <-s . owner , isPrivate <-s . isPrivate , returnType <-s . returnType ) } r u l e CopyDataType { from s : ClassDiagram ! DataType t o t : ClassDiagram ! DataType ( name <-s . name ) }

INRIA

• The transformation engine has to instantiate a completely new class diagram and perform the explicit copy of all the unchanged elements one by one, with a strong impact over the overall transformation time.

• The creation of a new model as output makes it difficult to integrate the transformation in UML model editors. Indeed, depending on the low-level representation of the model in memory, the copied elements in the newly created output model may not be a perfect clone. They could have some technical differences with respect to the input model, like different identifiers or different element ordering. The diagram editor could not be able to manage these unexpected changes, specially to maintain external references to those elements that now have changed their identifier.

These problems are independent on the M2MTL chosen for implementing the transformations. In the rest of the paper we will focus on the ATL language, but our considerations can be easily extended to similar model-driven languages like QVT/Relations or ETL [START_REF] Kolovos | The epsilon transformation language. Theory and Practice of Model Transformations[END_REF] or, outside MDE, to transformation languages like XSLT. All these languages do not provide an explicit support for refining. While in XSLT the copy rules can be at least made compact by using wildcards in templates, QVT-Relations requires a significant development effort. Moreover, the above-mentioned performance hit affects all the implementations known to us.

Design strategies for refining mode

In the next sections we present two strategies to add an ad-hoc support for refinement in existing M2MTLs, in order to cope with the previous problems.

Copy strategy.

The quality of the transformation code can be significantly improved by introducing a small change in the transformation semantics for refinement mode. The need to write copy rules can be avoided by enforcing an implicit copy for all the elements that are not explicitely matched by any transformation rule. The new strategy differs from the standard one only because of the new default copy operation.

Listing 2 shows the only ATL rule needed by the Public2PrivateAndGetter refactoring in the copy strategy. The example shows that using this strategy the developer has to specify only a minimal set of rules, mirroring exactly the refinement logic.

As a minor drawback, the new default behavior of the copy semantics makes the deletion of part of the source model a delicate operation. The basic approach requires the developer to explicitely override the default copy for the elements to eliminate (e.g. by writing a transformation rule that matches the elements to delete and generates nothing). While the approach is completely sound for a generic M2M language, we will see in Section 4.1 that we decided to provide ATL with a more flexible deletion mechanism, by leveraging its specific resolution algorithm.

The default-copy behavior can be implemented in several ways: by transformation composition: the transformation rules that implement the refinement logic can be factorized in a single transformation to be composed with a base copy transformation.

The refinement rules will be used, by means of a general-purpose composition mechanism, to override the simple copy rules for the elements to modify.

by transformation synthesis: a transformation in the standard semantics can be automatically generated, for instance by a HOT [START_REF] Tisi | On the Use of Higher-Order Model Transformations[END_REF] taking as input a transformation in the copy strategy.

by a modified transformation engine: a modified engine can directly read the refining rules in copy strategy and trigger the default copy behavior when needed.

Whatever implementation means is chosen, it is generally quite easy to adapt existing transformation languages to the copy semantics.

In-place strategy.

In this paper we propose an alternative semantics for M2M transformation languages, that is specifically designed for in-place refinement. The semantics overcomes the limitations of the default-copy approach, by using the model transformation language to perform direct manipulation of models.

While it is not necessary to change the syntax of the transformation language, this programming paradigm is remarkably different from the standard M2M transformation semantics. When using the in-place transformation mode, the user has to abandon the idea of constructing incrementally the target model starting from an empty one. Every in-place transformation rule operates in a preexisting context, the source model, matching and modifying the current elements.

The transformation starts with an initial state constitued by the whole source model. Explicit transformation rules are executed, and every model element that is not explicitely manipulated by these operations is simply kept as it is. A transformation in in-place mode can be translated in a INRIA sequence of basic operations over the source model, with three operation types (mimicking a CRUD operation set): create: builds a new model element from scratch in one of the models.

update: updates a model element in-place in one of the models, by changing one of its features.

delete: deletes explicitely a model element in one of the models.

The implementation of the new semantics over a rule-based transformation language has to be carefully designed, to avoid interaction problems between rules. Since declarative rules in M2M rule-based languages may be matched in any order, an in-place strategy cannot be implemented by incrementally updating the source model of the transformation. The problem in this case is that rules modifying the same model elements would possibly conflict with each other, with undeterministic results.

To avoid rule conflicts we propose a two-step application process for in-place transformation rules. A first application step calculates the effect of these rules on the source model, without concretely changing the model. The second step applies all the modifications at once.

Several technical solutions can be chosen to implement the two-step semantics. One possibility is to mark the modifications on the source model without actually commiting them until the end of the transformation, so that expression evaluation can occur on the original source model by ignoring the modifications. Another possibility is to first compute the set of basic operations to perform, storing this set in an external model representation and then apply all the changes at once. Our prototype implementation of the in-place refining mode follows the second approach.

Figure 2 gives an overview of our strategy for in-place refining. In this figure, we consider a refining transformation for the MMa metamodel that produces a model Ma' from a model Ma. This transformation is represented as a dashed arrow. The two-step process is represented using dotted arrows, and it's divided in:

• Change computation. In a first step, the transformation computes the sequence of internal operations that need to be performed on the model without actually executing them. This set of changes is simply represented as a model called Ma'-Ma, which conforms to the Diff (for difference) metamodel. The Ma'-Ma model contains elements that represent the create, update and delete operations and their arguments.

• Change application. In a second step, operations are applied directly on the source model Ma, which results in the target model Ma'. Note that in this context, Ma' is actually a new version of Ma, not a separate model.

The notion of difference model can be also considered as analogous to the notion of difference file in the Unix world. In this analogy, the second step (i.e., applying changes) is similar to the patch command-line tool. However, in our case we do not compute changes between two source models. We compute the changes required to obtain the target model from a source model according to the transformation program. It has to be noticed that also for the in-place case, the deletion of model elements needs a specific solution. While in the copy strategy, deletion could have been simulated by simply non-transforming some elements, the in-place semantics requires the implementation of an explicit deletion operation (non-transformed elements simply remain unchanged in the transformation output). The implementation details of this operation are dependent on the specific transformation language.

MMM

Comparison

Listing 2 shows that the copy strategy produces a dramatic improvement of the quality of the transformation code. However, the copy strategy does not provide any benefit in performance and integration, since it maintains the general transformation behavior unchanged (apart from the new default operation). In particular:

• The runtime performances are not better than the default mode. In some implementations they are even worse. This happens because the environment has to perform the same overall number of copy operations of the standard mode, with the additional burden of keeping trace of the matched elements and select the unmatched ones for the copying process.

• There is no guarantee about the preservation of identity information in the manipulated model, hampering any integration with model editors.

The in-place strategy maintains the same benefits on code quality than the copy strategy. For instance the code in Listing 2 will still be correct in in-place semantics. In-place mode even allows slightly shorter transformation rules, since the user is relieved from taking care of the correct copying of all the properties and references that are unchanged. For instance, lines 10, 11 and 13 could be omitted from Listing 2 in in-place mode, since these properties would just remain untouched.

INRIA

More importantly, the in-place approach has two big advantages over the previous solutions:

• The possibility of significantly optimize the transformation execution time. The performance of the in-place strategy is generally better with respect to the copying one because it is not necessary to copy model elements of the unchanged part of the source model. When the target is saved in a different file than the source, this is the main benefit, because the serializer still has to traverse the target. When the model stays in memory, an additional benefit is that relatively large models may be processed without actually needing to traverse unchanged parts of the model. Of course, this is especially significant in the case where only small changes are performed on a very large model.

• A natural way of preserving identities for unchanged elements and links with external tools.

While these benefits raise the attractiveness of the in-place strategy for model refinement, they come at the cost of a significant development effort in implementing a new semantics. We will exemplify these implementation issues by describing in the next section the refinement support in ATL.

Refinement transformations in ATL 4.1 Copy strategy in ATL

So far, refinement transformations have been built in ATL using the copy strategy, by exploiting two technical means provided by the ATL environment: rule superimposition and refining mode.

Rule superimposition.

ATL provides a composition mechanism named superimposition. This is performed at runtime by weaving the bytecode of two transformations, so that the rules of the superimposed transformation override the rules with the same name in the other transformation. In [START_REF] Wagelaar | Composition techniques for rule-based model transformation languages[END_REF] this mechanism has already been investigated for implementing refining transformation.

In the Public2PrivateAndGetter example, the user could generate automatically the copy rules for every element of the ClassDiagram metamodel (i.e. CopyClass, CopyDataType... and CopyAttribute). Then he would write a separate, superimposed transformation, containing only the rules related to the refactoring, i.e. PublicAttribute and CopyAttribute. The new CopyAttribute would override the generated one, avoiding to copy all the attributes and allowing the refactoring by Publi-cAttribute.

Refining mode.

The first explicit support for refining transformations in ATL has been added in 2005 in the form of a new transformation execution mode, and is called refining mode. This mode is selected in the ATL language by simply replacing the from keyword by the refining keyword in the transformation header. Obviously, refining mode may only be used for endogeneus transformations, i.e. when source and target model share the same metamodel. Listing 3 shows how the header of a refactoring transformation on the ClassDiagram metamodel may look like. In refining mode the ATL transformation performs as if there were implicit copy rules that would match every element unmatched by explicit (i.e., programmer-written) rules. Such a copy rule creates a target element of the same type as the source element. Then, it initializes all the properties of the new element by copying the values of the properties of the source element. Additionally, it creates a traceability link. During the property initialization process, the ATL resolve algorithm [START_REF] Jouault | Transforming Models with ATL[END_REF] is used to find the target elements corresponding to source elements, navigating these trace links.

The refining mode implements the same algorithm of the traditional mode. The refining-specific behavior is triggered only when no traceability link exists for a source element submitted to the resolve algorithm. When this behavior is triggered, the source element is copied by calling a copy operation (called refiningCopy) added by the compiler into the generated bytecode. Pseudocode of this operation is presented in Listing 4. The refiningCopy operation analyzes the type of the element to copy. If it is a collection, then a recursive call to refiningCopy is performed on every element (lines 3-5). If it is a model element, then a target element of the same type is created (line 7). Then, a loop iterates over the properties of the element (lines 9-12), and copies the values read from the source element to the target element. The resolve algorithm is called (line 11) before assigning the value to the target property. Note that this call to the resolve algorithm is also recursive because refiningCopy is only invoked by the resolve algorithm. This recursion is terminated if no more element are to be traversed. Note that if there is a loop in the model, then the resolve algorithm will not call refiningCopy again for the same element because the trace link has been created (at line 8) before the call to resolve (at line 11).

ATL refining mode provides a means for developers to avoid to transform part of the input model, without extending the ATL language with an explicit delete operation. Because refiningCopy is only called as part of the resolve algorithm, the parts of the model that are not connected to the elements transformed by explicit rules are ignored. This means that, if a developer wants to avoid INRIA copying part of a model, he needs to write transformation rules that eliminate any reference to this part.

It has to be noticed, however, that, to make the mechanism more flexible, the algorithm for copybased refining mode in the latest versions of ATL is slightly different than the one in Listing 4: for properties corresponding to composition associations, the value is actually copied only if the source element is the container. In other words, the copy of a container triggers the copy of its content but not viceversa, a design choice that mirrors the semantics of containment.

Summarizing, in the ATL copy strategy, elements are deleted if:

1. they are not copied by an explicit rule, 2. they are not contained in a copied element, and 3. they are not referenced (non-containement) by a copied element.

In-place strategy in ATL

In this section we introduce a novel semantics for ATL refining mode, natively in-place. This semantic is partially implemented in the latest released version of ATL. A prototype of the complete implementation is freely available on the AtlanMod wiki [2]. The semantics follows the scheme already introduced in Figure 2, and the Diff metamodel internally used by the ATL engine is expanded in Figure 3. In the first step, the transformation engine executes the rules and fills the Diff model with calculated changes. Then the basic operations are reordered and applied. The reordering is possible because in standard ATL every create and update operation is independent, since source elements are matched just once (other languages could require in this phase a different algorithm, sometimes with conflict resolution).

A delete instead can easily generate a conflict with another operation. This happens because we chose to provide delete with a cascade-delete semantics for composition associations (i.e. the deletion of a container triggers the deletion of the contained elements). For this reason the user is allowed to specify that he wants to create a new contained element, and, at the same time, that he wants to delete the container. In this case, and in similar ones, we solve the conflict introducing a default policy that gives to delete a higher priority.

The whole Diff-application algorithm is implemented by first applying all the create operations, then all the modify operations, and finally all the delete operations. It's easy to verify that this reordering satisfies the policy that we described for conflict resolution.

Finally, in our prototype implementation we decided to also extend the ATL syntax, by introducing an ad-hoc keyword for deletion. This step was not strictly necessary, but 1) it provides the user with a more readable code for a destructive operation like delete and 2) it allows to mix in the same rule deletions and other operations. The ATL abstract syntax has been modified, by adding a new statement, called drop, to the ATL metamodel, and the concrete syntax has been updated by extending the parser to recognize the DROP keyword. In the listing 5, we show how to use the new syntax to undo the changes introduced by the motivating example.

INRIA

Comparison

Tables 1 and2 give the results of a comparative benchmark of two implementations of transformation Public2Private: one based on default-copy by superimposition and the other based on in-place refining. Both implementations of the transformations have been executed on large UML models obtained by reverse engineering the Java API (versions 1.2 for Table 1, and version 1.6 for Table 2). The first column gives the transformation execution time, without taking into account model loading and saving. Total time is given in the second column. Note that transformation time is highly relevant in many cases like: in the middle of a chain, when refactoring a model in memory (e.g., in a CASE tool). The total number of executed bytecodes is given in the third column, while the fourth column gives the number of lines in the source program.

The execution time of in-place mode results remarkably lower than the solution based on superimposition. We point out that the third possible implementation, using the default-copy refining mode, would be even slower than superimposition. The reason is that this refining mode uses reflection to perform the copy whereas explicit copy rules directly access and create elements.

Related work

Techniques for efficiently implementing refinement rules have been extensively studied in the Program Transformation field. Examples of transformations languages in this area, with a direct support for in-place transformations are Stratego [START_REF] Visser | Building program optimizers with rewriting strategies[END_REF], ASF+SDF [START_REF] Van Den | Term rewriting with traversal functions[END_REF] and TXL [START_REF] Cordy | The TXL source transformation language[END_REF]. A related survey of possible strategies can be found in [START_REF] Visser | A survey of strategies in rule-based program transformation systems[END_REF]. Our proposal takes inspiration by these works to study the particular problem of adapting pre-existing M2M frameworks to model refinement.

Since the importance of model refinement has been recognized in several MDE approaches, like OMG's MDA [START_REF] Mellor | Model-Driven Architecture[END_REF], other model transformation languages have been adapted to enable it (e.g. [START_REF] Zhang | Generic and Domain-Specific Model Refactoring using a Model Transformation Engine[END_REF]).

In [START_REF] Goldschmidt | Refinement Transformation Support for QVT Relational Transformations[END_REF] the authors add support for default copy rules in QVT. The approach has some similarities with our default-copy refinement semantics, and is implemented by an higher-order transformation.

In the Epsilon family of languages, the main transformation language, ETL [START_REF] Kolovos | The epsilon transformation language. Theory and Practice of Model Transformations[END_REF], does not have a special support for refining transformations (that are called "update transformations in the small"). The family comprises a different language, Epsilon Wizard Language [START_REF] Kolovos | Update Transformations in the Small with the Epsilon Wizard Language[END_REF], specifically designed for this purpose. In this paper we want to help transformation language designers. We propose to do that by implementing a specific refinement support to their M2M languages, instead of developing a new ad-hoc language.

In this work we consider only the technical aspect of refinement and refactoring, as pure manipulations of the abstract syntax. In actual applications, semantic aspects of the refinement transformation have to be taken into account. However, this problem is beyond our scope and we refer the reader to works on semantics of model-to-model transformations ( [START_REF] Biermann | Precise Semantics of EMF Model Transformations by Graph Transformation[END_REF], [START_REF] Straeten | A Formal Approach to Model Refactoring and Model Refinement[END_REF]). For instance, several works target the semantic preservation of a designer-defined refactoring transformation (for example [START_REF] Judson | A Metamodeling Approach to Model Refactoring[END_REF]) to ensure its correctness.

Finally, while the approach we are following investigates the application of a language with a natively separated input and output models to the in-place case, some works in the graph transformation area follow the opposite path. [START_REF] Schurr | Specification of graph translators with triple graph grammars[END_REF] studies how to apply a natively in-place transformation language to efficiently describe translations.

Conclusions and future work

In this paper, we have considered the problem of expressing refining transformations using modelto-model transformation languages initially designed for translational transformations. More specifically, we focus on rule-based M2M transformation languages, that have read-only source model and write-only target model semantics. The paper discusses two main strategies for facilitating refinement transformations (i.e., refining mode) in this kind of model transformational languages : 1) implicit copy of unmatched elements from source to target, or 2) in-place modifications of the source model, resulting in the target model. Trade-offs of both strategies are compared against a set of dimensions like code quality, performance, integrability. An implementation of both strategies in ATL is described.

In future work we want to improve our in-place refinement engine, by adding native support for advanced operations on models, to complement our create-update-delete scheme. Examples of the operations that we are evaluating are transtype (i.e. changing the type of a model element without changing its identity), redirect (i.e. reroute all the references pointing to an element to another one) and clone (i.e. making multiple copies of an element).

We are also going to extend and formalize our comparison of M2M and graph transformation approaches. The intention is to evaluate how these different families of transformation technologies relate to each other in terms of expressivity, complexity and performance.

INRIA

Figure 1 :

 1 Figure 1: Source metamodel: ClassDiagram

Listing 1 :

 1 Public2PrivateAndGetter.atl r u l e CopyClass { from s : ClassDiagram ! Class t o t : ClassDiagram ! Class ( name <s . name , attr <s . attr , op <s . op ) } r u l e PublicAttribute { from s : ClassDiagram ! Attribute ( not s . isPrivate and not s . owner . op->exists ( o | o . name = 'get' + s . name . toUpperCase ( ) and o

  CopyAttribute { from s : ClassDiagram ! Attribute ( not ( s . isPrivate and not s . owner . op->exists ( o | o . name = 'get' + s . name . toUpperCase ( ) and o . returnType = s . type ) )

Listing 2 :

 2 Public2PrivateAndGetter.atl r u l e PublicAttribute { from s : ClassDiagram ! Attribute ( not s . isPrivate and not s . owner . op->exists ( o | o . name = 'get' + s . name . toUpperCase ( ) and o . returnType = s . type ) ) t o t : ClassDiagram ! Attribute ( name <s . name , owner <s . owner , isPrivate <true , RR n°7582 type <s . type ) , getter : ClassDiagram ! Operation ( name <-'get' + s . name . toUpperCase ( ) , owner <s . owner , isPrivate <false , returnType <s . type ) }

Figure 2 :

 2 Figure 2: Overview of the in-place refining semantics.

Listing 3 :

 3 ATL header for Public2PrivateAndGetter module Public2PrivateAndGetter ; c r e a t e OUT : ClassDiagram r e f i n i n g IN : ClassDiagram ;

Listing 4 :

 4 Refining mode algorithm implemented in the refiningCopy operation refiningCopy ( sourceElement ) { If sourceElement is a Collection Then ForEach e in sourceElement { refiningCopy ( e ) } Else --sourceElement is a model element targetElement <create new element of same type as sourceElement add trace link from sourceElement to targetElement ForEach property of sourceElement { v <get value of property on sourceElement set property of targetElement to resolve ( v ) } EndIf }

Figure 3 :

 3 Figure 3: Diff Metamodel

Table 1 :

 1

		Public2Private.atl on j2se-1_2-api.uml (6.17MiB)
		Time (s) Transformation Total	Bytecodes Lines of code
	Copy	209	216	24677797	41
	In-place	3.20	11	354364	15
	Ratio	65.3	19.6	69.6	2.7
	Table 2: Public2Private.atl on j2se-1_6-api.uml (13.14MiB)
		Time (s) Transformation Total	Bytecodes Lines of code
	Copy	496	515	52478984	41
	In-place	5.75	25	674874	15
	Ratio	86.3	20.6	77.8	2.7

RR n°7582


Xiaotao Wu

Claude H Moog

L A Marquez-Martinez

Yueming Hu

Modelling and Control of a Complex Buoyancy-Driven Airship ⋆

Keywords: autonomous vehicles, aircraft control, airship, feedback linearization, Minimum-phase systems

The general model for a new generation airship is introduced from the model of an elementary mechanical system which embodies the core of the problem to more complex. It is shown that the basic properties of a suitable two degree of freedom mechanical system are instrumental for the analysis and synthesis of advanced airships. It is shown that the control of the airship mechanical system yields suitable approximations for the control of the airship subject to aerodynamic forces.

INTRODUCTION

A new generation of airships is considered. New energy saving actuators are introduced which consist in a moving ballast and a tuning of buoyancy [START_REF] Purandare | A buoyancy-Propelled Airship, Dissertation for the Doctor Degree of Philosophy[END_REF], Wu, Moog et Hu. [2009], [START_REF] Wu | Nonlinear control of a buoyancy-driven airship[END_REF]. The scheme is inspired from underwater gliders which use similar features to minimize the use of standard propulsors [START_REF] Leonard | Model-based feedback control of autonomous. underwater gliders[END_REF].

An unmanned autonomous airship equipped with standard propulsors was introduced in [START_REF] Gomes | Airship dynamic modeling for autonomous operation[END_REF] for the first time, and it is the standard model of the main stream in the airship research. Inspired by underwater gliders [START_REF] Leonard | Model-based feedback control of autonomous. underwater gliders[END_REF], [START_REF] Purandare | A buoyancy-Propelled Airship, Dissertation for the Doctor Degree of Philosophy[END_REF] designed a new-kind of airship whose main properties are mentioned above. Wu, Moog et Hu. [2009] used an aeronautical way to derive a complete model of this new generation airship and designed a LQR controller for its stabilization. [START_REF] Wu | Nonlinear control of a buoyancy-driven airship[END_REF] designed a nonlinear controller based on input-output linearization of the pitch angle. With the controller in [START_REF] Wu | Nonlinear control of a buoyancy-driven airship[END_REF], the state variables are critically stable.

As done in [START_REF] Wu | Nonlinear control of a buoyancy-driven airship[END_REF], the airship is considered restricted to a planar motion and subject to the single control input by moving ballast in this paper.

The goals in this paper are:

(1) Display the fundamental and elementary structure hidden in the complex full model of the airship. (2) Show how the use of this fundamental structure is instrumental to derive new control schemes!

To reach goal (1), the modelling of the airship is done first from simple special case (with a fixed center of volume) and then to more complex and complete cases. In this way essential ⋆ This work is supported by CSC properties hidden in the model are highlighted and applied to simplify the control problem of the most complete model. The most elementary special case is a simple two degree of freedom mechanical system whose properties are claimed to invariant under the future complexification of the system. Also based on this elementary special case, we set up the complete model through dropping restrictions and adding external forces.

For the goal (2), the most elementary system is controlled by computing a suitable dummy output function which defines a minimum phase system and whose feedback linearization achieves maximal linearization of the considered system, which instructs the way to design the controller for the complete model. The structure of a buoyancy-driven airship is shown in Fig. 1. This kind of airship moves forward by a cyclic change of the net lift of the craft and of the position of ballast. The detail of the mechanism of operating and the traditional modelling way have already been given in some papers [START_REF] Purandare | A buoyancy-Propelled Airship, Dissertation for the Doctor Degree of Philosophy[END_REF], Wu, Moog et Hu. [2009], [START_REF] Wu | Nonlinear control of a buoyancy-driven airship[END_REF].

The paper is organized as follows. Section 2 is devoted to the modelling and control of the most elementary special case of the airship, which represents the airship subject to three assumptions. The airship is liberated in Section 3 by dropping a assumption that the center of the volume O is fixed. In this case, the center of mass of the overall system is subject to a ballistic motion and the controllable subsystem remains similar to the previous elementary system. In Section 4, the airship model is completed with the influence of suitable added masses and Section 5 displays the full model including the aerodynamic forces.

THE AIRSHIP WITH FIXED CENTER OF VOLUME

To derive an elementary special case of the complex airship, the dynamics of the airship are not only restricted to the vertical plane, but it is also assumed that the center of volume O of the airship is fixed, which means that the airship can only rotate round O, but the longitudinal and horizontal translation velocities v 3 and v 1 are zero. It also assumes that there is no inertial force and no aerodynamic force acting on the vehicle.

These assumptions reduce to:

Assumptions: A 3 : The center of the volume O is fixed, the airship have no translational velocities. A 2 : No fluid inertial force.

A 1 : No aerodynamic force.

A mathematic model is derived as follows.

Modelling

Under the situation described above, the airship rotates around O with respect to the forward and backward movements of the ballast, as shown in In this case, the airship is similar to a double pendulum as described in Fig. 4. The rotational joint at point O is not actuated. The joint between the two links of the double pendulum is prismatic and actuated. The double pendulum, inverted or not, has been considered as a classical control example in many references [START_REF] Wie | Space Vehicle Dynamics and Control[END_REF].

Here, the body of the airship except the ballast is denoted by the link 1 which is fixed in the point O, and the ballast is denoted Fig. 4. The airship system with a fixed point by another link which can be moved by a actuator. The position of the center of the mass of the ballast in the non-inertial frame in the vertical plane is (r p1 , r p3 ). The system can swing along with the actuator changing the position of m, which is as same as the operation of the airship. Here, r p3 is constant.

The lagrangian of that simplified airship system is

L = 1 2 J θ2 + 1 2 mv 2 m -mg(r p3 cos θ -r p1 sin θ).
With the Lagrangian, the equations of motion can easily be found as,

θ =ζ 1 = - 1 J + mr 2 p1 ( mr p3 r p1 θ2 + 2 mr p1 ṙp1 θ + mgr p1 cos θ + r p3 u) (1) rp1 =σ 1 = 1 J + mr 2 p1 ((Jr p1 + mr 3 p1 + mr 2 p3 r p1 ) θ2 + 2 mr p3 r p1 ṙp1 θ -(J + mr 2 p1 )g sin θ + mgr p3 r p1 cos θ + ( J m + r 2 p1 + r 2 p3 )u) (2)
where, u is the input denoted the force applied on the ballast along the e 1 axis direction.

Maximal linearization of a minimum phase model

Standard computation Conte et al. [2007], [START_REF] Isidori | Nonlinear Control Systems: An Introduction[END_REF] show that the system is fully accessible and not fully linearizable by static state feedback. It is thus interesting to look for a maximal feedback linearization and to search for output function with the largest relative degree. This is done next. Following the notations in Conte et al. [2007] the following results are obtained. According to the system (1)-( 2).

H ∞ = 0 H 3 = span{dφ 1 , dφ 2
} and H 4 is not integrable. H 3 represents the codistribution which consists of all differential forms whose relative degree is at least 3. Here, φ 1 and φ 2 as follows,

φ 1 = J θ + (r 2 p1 θ + r 2 p3 θ + r p3 ṙp1 ) m φ 2 = θ + r p3 J m + r 2 p3 arctan r p1 J m + r 2 p3
In φ 1 , J θ is the angular momentum of airship's body in the vertical plane, and (r 2 p1 θ +r 2 p3 θ +r p3 ṙp1 ) m is the ballast's angular momentum r p × mv p in the vertical plane (r p and v p are the position and velocity of the ballast in the non-inertial frame respectively). So, φ 1 is the angular momentum of the whole airship around the point O. φ 1 and φ 2 also have the following relation,

φ2 = 1 J + (r 2 p1 + r 2 p3 ) m φ 1 (3)
At this stage, any combination of φ 1 and φ 2 has relative degree 3 and its feedback linearization will yield a linear controllable subsystems of dimension 3 with a one dimensional zero dynamics. The following result shows the possibility to ensure that the system is minimum phase which has a decisive impact on the doability of this control design.

Theorem 1: φ 1 + kφ 2 has stable zero dynamics for k > 0.

Proof: Under this situation, new states are chosen as follows

ξ 1 = φ 1 + kφ 2 (4) ξ 2 = φ1 + k φ2 (5) ξ 3 = φ1 + k φ2 (6) ξ 4 = φ 1 (7)
From the zero dynamics of ξ 2 , φ1 + k φ2 = 0, so φ1 = -k φ2 , and because of the relation (3). The zero dynamics of ξ 4 as follows,

ξ4 = φ1 = -k φ2 = -k 1 J + (r 2 p1 + r 2 p3 ) m φ 1
So, for k > 0, the system is asymptotically stable.

Simulations

The family of outputs y = φ 1 + kφ 2 for a varying real number k is considered now. The special case (1)-( 2) is stabilized through standard input-output linearization according to section 2.2.

From Theorem 1, it is mandatory to pick k > 0 to ensure internal stability of the closed loop system. Its actual value is a tuning parameter which influences the velocity of the zero dynamics. Consider the following desired error equation:

y (3) + λ 2 y (2) + λ 1 y (1) + λ 0 (y -y e ) = 0 (8)
here, y e is the desired value for y. The parameters k = 50,

λ 2 = 2, λ 1 = 2, λ 0 = 1.
Fig. 5 and 6 are simulating results of the dynamics of the θ, r p1 and the control input u under initial errors. From this result, θ and r p1 stabilize at the equilibrium after 30s. In this case, A 3 is dropped and we have the following assumptions.

Assumptions:

A 2 : No fluid inertial force.

A 1 : No aerodynamic force.

Modelling

Newton-Law is used to develop the mathematic model futher. In the inertial frame, the total external force and moment applied on the airship are m 0 gk and mgr s × k, where, m 0 is the net lift, and k is a unit vector along the direction of gravity. So the total external force in the non-inertial frame is,

F t ot al = m 0 gR T 1 k (9) M t ot al = mgR T 1 r s × k (10)
The total external force also can be denoted as follows Wu, Moog et Hu. [2009],

F t ot al = Ω × B + R T f t ot al = Ω × (m s v + B p ) + m s v + u (11
) where, m s v and u are the total external force on the body of the airship and the ballast respectively. Ω × B or Ω × (m s v + B p ) are coriolis forces.

Similarly, the total external moment can be denoted as follows,

M t ot al =Ω × Π + v × B + R T τ total =Ω × (r p × B p + J s Ω) + (v × m s v + (v + ṙp ) × B p ) + (J s Ω + r p × u) (12) where, Ω × Π = Ω × (r p × B p + J s Ω) is the torque of the centrifugal force, v × B = v × m s v + (v + ṙp ) × B p
is the torque of the coriolis force. (J s Ω + r p × u) is the torque respect to the non-inertial frame.

From the relations (9) and ( 21), ( 10) and ( 22), the v and Ω are derived as,

v = m -1 s (m s v + B p ) × Ω + m 0 gR T 1 k -u (13) Ω = J -1 s ((J s Ω + r p × B p ) × Ω + Ω × r p × B p + mgr p × R T 1 k -r p × u) (14)
where, B p = mv p = m(v + ṙp + Ω × r p ) is the momentum of the ballast.

From ( 13) and ( 14), the mathematic model in the vertical plane is as follows,

θ = ζ 2 = ζ 1 + ( v3 -θv 1 ) mr p1 J + mr 2 p1 (15) rp1 = σ 2 = σ 1 + mr p1 r p3 ( θv 1 -v3 ) -(J + mr 2 p1 )( θv 3 + v1 ) J + mr 2 p1 (16) v1 = κ 1 = 1 m s (-m s θv 3 + ( m -m 0 )g sin θ -u) (17) v3 = κ 3 = 1 m s + m ((m s + m) θv 1 + m 0 g cos θ + mr p3 θ2 + 2 mθ ṙp1 + mr p1 θ) (18)
Comparing the elementary special case (1)-( 2) with model ( 15)-( 18), It's easy to find that the elementary case (1)-( 2) is a subsystem of the model ( 15)-( 18), which can be shown by the simulation.

Maximal linearization of a minimum phase model

System ( 15)-( 18) is now subject to a ballistic motion (of point CG) and to be out of the action of the control input. In other words, there exist some non-controllable states besides the controllable or accessible system. Again, following standard computation Conte et al. [2007], one computers the noncontrollable subsystem whose coordinates are denoted by ψ 1 and ψ 2 :

H ∞ = span{dψ 1 , dψ 2 } where ψ 1 = (r p1 θ - m s + m m v 3 ) 2 + (ṙ p1 + r p3 θ + m s + m m v 1 ) 2 ψ 2 = (r p1 θ - m s + m m v 3 ) cos θ + (ṙ p1 + r p3 θ + m s + m m v 1 ) sin θ (m s + m)ψ 1
is the kinetic energy of CG, and ψ 2 denotes the horizontal velocity of CG, which means that the airship includes the ballistic motion of the center of gravity CG. Fig. 9 displays this ballistic motion.

Thus the 6-dimensional state system (15)-( 18) can be decoupled into a 2-dimensional non-controllable subsystem and a 4dimensional subsystem whose structural properties are similar to those of model ( 1)-( 2).

H 3 = span{d φ1 , d φ2 } ⊕ H ∞ where, φ1 = J θ + (r 2 p1 θ + r 2 p3 θ + r p3 ṙp1 ) mm s m + m s φ2 = θ + r p3 m+m s mm s J + r 2 p3 arctan r p1 m+m s mm s J r 2 p3
Here, φ1 is the angular momentum of the airship around the center of the gravity CG as previous. The relation of φ1 and φ1 is as follows,

φ2 = 1 J + (r 2 p1 + r 2 p3 ) mm s m+m s φ1
Theorem 2: φ1 + k φ2 has stable zero dynamics for k > 0.

The way to prove Theorem 2 is the same as in the previous section.

Simulations

The control law and the values of the parameters here is the same as the previous part. The initial values of the states are θ 0 = 41.5, r p10 = -1.15 m, v 10 = 1.8 m/s and v 30 = 0, and also m 0 = 1 kg, m s = 269 kg.

The similar performances of the controller are got,see fig. 78. The inertia of airships with a large Volume/Mass ratio is much more significant in comparison with conventional airplanes, which must be considered. Added mass is designed to represent some of there initial forces.

Assumption A 2 is dropped. But aerodynamic forces are still ignored.

Assumptions:

A 1 : No aerodynamic force.

In this section, the role of the result of previous sections is shown.

Modelling

The matrix M add including these added masses is called the inertia matrix Wu, Moog et Hu. [2009].

M add = M f * * J f
M f is the symmetric 3 × 3 added mass matrix; J f is the added inertia matrix. M f = diag{m 11 m 22 m 33 } and J f = diag{m 44 m 55 m 66 }.

In an ideal fluid, the kinetic energy T add of fluid inertia is

T add = 1 2 6 i=1 6 j=1 m i j ζ i ζ j = 1 2 (m 11 v 2 1 + m 22 v 2 2 +m 33 v 2 3 + m 44 Ω 2 1 + m 55 Ω 2 2 + m 66 Ω 2 3 ) here ζ 1 = v 1 , ζ 2 = v 2 , ζ 3 = v 3 , ζ 4 = Ω 1 , ζ 5 = Ω 2 , ζ 6 = Ω 3 .
The momenta B = (B 1 , B 2 , B 3 ) T and moments of momentum K = (B 4 , B 5 , B 6 ) T of fluid inertia are related to the kinetic energy T add :

B i = ∂T add ∂ζ i (i = 1, 2, • • • , 6) So, B = M f v K = J f Ω
So, the inertial forces F I and moments M I acting on the airship are as follows Comparing with the previous case ( 9)-( 10), the total external force should include inertial forces as follows,

F I = - dB dt = -( d B dt + Ω × B) = -M f v + M f v × Ω (19)
M I = - dK dt = -( d K dt + Ω × K + v × B) = -J f Ω + J f Ω × Ω + M f v × v ( 20
F t ot al = m 0 gR T 1 k + F I (21) M t ot al = mgR T 1 r s × k + M I (22)
Let m 1 = m s + m 11 , m 3 = m s + m 33 and J 2 = J + J 22 , the model of the airship with the effects of the inertial forces is as follows,

θ = ζ 3 = ζ ′ 2 + (m 3 -m 1 )v 1 v 3 J 2 + mr 2 p1 (23) rp1 = σ 3 = σ ′ 2 + (m 3 -m 1 )v 1 v 3 J 2 + mr 2 p1 r p3 (24) v1 = κ ′ 1 (25) v3 = κ ′ 3 (26)
Note that model ( 15)-( 18) reduces to the special case of model ( 23)-( 23) if m 11 = m 11 = J 22 = 0 (no added mass).

In the fluid inertial forces, (m 3m 1 )v 1 v 3 is pitching moment, which will be included in the aerodynamic forces. This is because when measuring the aerodynamic forces of the airship by a wind tunnel test, a part of fluid inertial forces, for instance (m 3m 1 )v 1 v 3 , is already included in the results of wind tunnel test, which is behaved as aerodynamic forces. So, (m 3 -m 1 )v 1 v 3 be ignored in the above model [START_REF] Ouyang | Research on Modeling and Control of an Unmanned Airship[END_REF]. Then, it is as,

θ = ζ 3 = ζ ′ 2 (27) rp1 = σ 3 = σ ′ 2 (28) v1 = κ ′ 1 (29) v3 = κ ′ 3 ( 30
)
All J and m s in ( 15)-( 18) change into J 2 , m 1 and m 3 as follows, other items keep unchanged.

where

ζ ′ 2 = - 1 J 2 + mr 2 p1 ( mr p3 r p1 θ2 + 2 mr p1 ṙp1 θ + mgr p1 cos θ + r p3 u -( v3 -θv 1 ) mr p1 ) σ ′ 2 = 1 J 2 + mr 2 p1
((J 2 r p1 + mr 3 p1 + mr 2 p3 r p1 ) θ2 + 2 mr p3 r p1 ṙp1 θ -(J 2 + mr 2 p1 )g sin θ + mgr p3 r p1 cos θ + (

J 2 m + r 2 p1 + r 2 p3 )u + mr p1 r p3 ( θv 1 -v3 ) -(J 2 + mr 2 p1 )( θv 3 + v1 )) κ ′ 1 = -m 3 θv 3 + ( m -m 0 )g sin θ -u m 1 κ ′ 3 = (m 1 + m) θv 1 + m 0 g cos θ + mr p3 θ2 + 2 mθ ṙp1 + mr p1 θ m 3 + m 4.

Maximal linearization of a minimum phase model

The model ( 27)-( 30) be decoupled into a non-controllable system and a controllable one as it was done for model ( 15)-( 18). The velocities of the center of the gravity CG are not affected by the control input, however their mathematical expressions become a bit more involved.

H ∞ = span{dψ ′ 1 dψ ′ 2 } where ψ 1 = (r p1 θ - m 3 + m m v 3 ) 2 + (ṙ p1 + r p3 θ + m 1 + m m v 1 ) 2 ψ 2 = (r p1 θ - m 3 + m m v 3 ) cos θ + (ṙ p1 + r p3 θ + m 1 + m m v 1 ) sin θ
Surprisingly, there is now only one single independent function φ′ 2 which has relative degree 3 for the model ( 27)-( 30). More precisely, compute H 3 :

H 3 = span{d φ′ 2 ω} ⊕ H ∞ where φ′ 2 = θ + r p3 m 3 (m 1 + m) m 1 (m 3 + m) m+m 1 mm 1 J+r 2 p3 arctan m 3 (m 1 + m) m 1 (m 3 + m) r p1 m+m 1 mm 1 J+r 2 p3
and check those H 3 is no more fully integrable ! Compute H 2 as:

H 2 = span{y ′ 1 y ′ 2 φ′ 1 } ⊕ H ∞ where y ′ 1 = m m 3 + m r p1 θ -v 3 y ′ 2 = m m 1 + m (ṙ p1 + r p3 θ) + v 1 φ′ 1 = ( m + m 1 mm 1 J + m 3 (m 1 + m) m 1 (m 3 + m) r 2 p1 + r 2 p3 ) θ + r p3 ṙp1
As the previous sections, one has the relation involving the angular momentum,

φ′ 2 = 1 m+m 1 mm 1 J + m 3 (m 1 + m) m 1 (m 3 + m) r 2 p1 + r 2 p3 φ′ 1
Despite these diametric changes with section 3, it is now argued that the control scheme which has been computed for the elementary special case in the section 2 is still valid, thanks to some approximation. This is done next!

Simulations

Since φ′ 1 does not have relative degree 3 anymore as φ′ 2 , the Theorem 1 & 2 are not true. But fortunately, the second-time derivative of φ′ 1 has a small coefficient of u, so it is proposed to neglect this coefficient.

More precisely, define again the output y = φ′ 1 + k φ′ 2 , for some k > 0.

Instead of the coordinates (4)-( 7), define

ζ 1 = φ′ 1 + k φ′ 2 (31) ζ 2 = φ′ 1 + k φ′ 2 (32) ζ 3 = φ′ 1 + k φ′ 2 -∆u (33)
ζ 4 = φ′ 1 ( 34
)
where φ′ 1 = Π + ∆u Instead of solving (8), consider the following equation:

ζ3

+ λ 2 ζ 3 + λ 1 y (1) + λ 0 (y -y e ) = 0 (35)
Note that equation ( 35) is strictly the equation ( 8) only if ∆ ≡ 0.

In the following when ∆ is small, then ( 35) is an approximation of (8).

Solving u in the equation ( 35) yields the desired states feedback which is applied now to the model ( 27)-( 30). The corresponding simulation results are displayed accordingly and show that the stability property is unchanged despite the above approximation.

Here where, F a1 = -X a cos α + Z a sin α F a3 = -X a sin α -Z a cos α

X a = 1 2 ρ a ∇ 2/3 v 2 (C x0 + C α x α 2 ) Z a = 1 2 ρ a ∇ 2/3 v 2 (C z0 + C α z α)
M a = 1 2 ρ a ∇v 2 (C m0 + C α m α) X a , Z a are aerodynamic forces along e 1 and e 3 axes, and M a is momentum around e 2 axis. α is the attack angle. Here, d φ′ 1 and d φ′ 2 have the same form as the previous sections, but the values are different. By the same way as the section 4, a advanced nonlinear controller can be derived. The simulation results of this nonlinear controller for the complete system will be presented elsewhere.

CONCLUSION

In this paper, a new way to set up the model for a complex system is denoted. What's more important is that based on that modelling-from the fundamental and elementary mechanical structure to the complex and complete model-a nonlinear controller is designed for that complex airship system. This nonlinear controller is difficult to derive directly from the complex full model.

Even though that nonlinear controller is a precise one, approximation has been done, controller behaves well, which has better performances and larger stable domain of initial conditions than the previous controllers.

Fig. 1 .

 1 Fig. 1. Structure of a Buoyancy-Driven Airship

  Fig 2 and 3, but O does not have any translation velocities.

Fig

  Fig. 2. Positive rotation

Fig. 5 .

 5 Fig. 5. Dynamics of θ and r p1 with initial error 3. THE AIRSHIP WITH LIBERATED CENTER Generally, aircrafts rotate around the center of the mass, not the center of the volume, like helicopters. In the first elementary

Fig. 7 .

 7 Fig. 7. Dynamics of θ and r p1 with initial error

  ) here, dB dt , dK dt denote the time-derivative of momentum B and angular momentum K with respect to the inertial frame, d B dt and d K dt denote the time-derivative in the body frame.

  , m 1 = 400 kg, m 3 = 500 kg and the other parameters have the same values as the previous. Good control performances have been got as displayed in Fig 10 to 12.

Fig. 10 .

 10 Fig. 10. Dynamics of θ and r p1 with initial error

Fig

  Fig. 12. Ballistic motion of CG Compute H 2 as:H 2 = span{dy ′ 1 dy ′ 2 d φ′ 1 dθ; dr p1 }


C Munuera

M Barbier

WET PAPER CODES AND THE DUAL DISTANCE IN STEGANOGRAPHY

Keywords: 2000 Mathematics Subject Classification. 94A60, 94B60 Steganography, Error-correcting codes, wet paper codes, dual distance

In 1998 Crandall introduced a method based on coding theory to secretly embed a message in a digital support such as an image. Later Fridrich et al. improved this method to minimize the distortion introduced by the embedding; a process called wet paper. However, as previously emphasized in the literature, this method can fail during the embedding step. Here we find sufficient and necessary conditions to guarantee a successful embedding by studying the dual distance of a linear code. Since these results are essentially of combinatorial nature, they can be generalized to systematic codes, a large family containing all linear codes. We also compute the exact number of solutions and point out the relationship between wet paper codes and orthogonal arrays.

Introduction

Steganography is the science of transmitting messages in secret, so that no one other than the sender and receiver may detect the existence of hidden data. It is realized by embedding the information into innocuous cover objects, as digital images. To carry out this process, the sender first extracts a sequence c 1 , . . . , c n , of n bits from the image, e.g. the least significant bits of n pixels gray values. The cover vector c = (c 1 , . . . , c n ) is modified according to a certain algorithm for storing a secret message m 1 , . . . , m r . Then c 1 , . . . , c n are replaced by modified x 1 , . . . , x n in the cover image which is sent through the channel. By using the modified vector x the receiver is able to recover the hidden information. The embedding and recovering algorithms form the steganographic scheme of this system. Formally, a steganographic scheme (or stegoscheme) S of type [n, r] over the binary alphabet F 2 is a pair of functions (emb, rec). By using the embedding function emb : F n 2 × F r 2 → F n 2 the secret message m ∈ F r 2 is hidden in the cover vector c ∈ F n 2 as x = emb(c, m) and subsequently recovered by the receiver with the recovering function rec : F n 2 → F r 2 as rec(x) whenever these functions verify that rec(emb(c, m)) = m for all c ∈ F n 2 and m ∈ F r 2 .

Steganographic schemes are closely related to error correcting codes. Given a [n, r] stegoscheme S, for each m ∈ F r 2 we consider the code C m = {x ∈ F n 2 : rec(x) = m}. Then the family {C m : m ∈ F r 2 } gives a partition on F n 2 and for all m ∈ F r 2 the mapping dec m : F n 2 → C m defined by dec m (c) = emb(c, m) is a decoding map for the code C m . Conversely let {C m : m ∈ F r 2 } be a partition of F n 2 and for each m ∈ F r 2 let dec m be a minimum distance decoding map of C m . Consider emb : F n 2 × F r 2 → F n 2 and rec : Since all vectors c and m are in principle equiprobable, it is desirable that all codes C m have the same cardinality. The above equivalence has been extensively exploited to make stegoschemes that minimize the embedding distortion caused in the cover. Crandall [START_REF] Crandall | Some notes on steganography[END_REF] proposed the use of linear codes C and the partition of F n 2 into cosets {x + C : x ∈ F n 2 }. The obtained method is currently known as matrix encoding. If H is a parity check matrix for C and dec is syndrome decoding (see [START_REF] Van Lint | Introduction to Coding Theory[END_REF] as a general reference for all facts concerning error correcting codes), the obtained embedding and recovering maps are emb(c, m) = ccl(cH Tm) and rec(x) = xH T , where cl(z) denotes the leader of the coset whose syndrome is z, that is the element of smallest Hamming weight whose syndrome is z . Matrix encoding has proved to be very efficient to minimize the embedding distortion in the cover, see [START_REF] Brierbrauer | Constructing good covering codes for applications in steganography[END_REF][START_REF] Fontaine | How Reed-Solomon codes can improve steganographic schemes[END_REF][START_REF] Schönfeld | Embedding with syndrome coding based on BCH codes[END_REF][START_REF] Schönfeld | Reducing the complexity of syndrome coding for embedding[END_REF][START_REF] Zhang | Maximizing embedding efficiency by combining Hamming codes and wet paper codes[END_REF].

F n 2 → F r
To reduce the chance of being detected by third parties, the changeable pixels in the cover image should be selected according to the characteristics of the image and the message to hide. In this case the recovering of the hidden data is more difficult, since the receiver does not know what pixels store information. Wet paper codes are designed to lock some components of the cover vector, preventing its modification in the embedding process. Mathematically wet paper codes can be explained as follows: imagine we want to embed a message m = (m 1 , . . . , m r ) ∈ F r 2 into a cover vector c = (c 1 , . . . , c n ) ∈ F n 2 . However, not all of coordinates of c can be used for hiding information: there is a set D ⊆ {1, . . . , n} of δ ≥ r dry coordinates that may be freely modified by the sender, while the other ℓ = nδ coordinates are wet (or locked) and can not be altered during the embedding process. Let W = {1, . . . , n} \ D. The sets D and W are known to the sender but not to the receiver. Using the matrix encoding method we set emb(c, m) = x ∈ F n 2 with

[S] :

xH T = m, x i = c i if i ∈ W
where H is a r × n matrix of full rank r. Locking positions minimize the possibility of detection during transmission but also generates a technical problem, since it is not guaranteed the existence of solutions for [S]. A natural question is to ask for the minimum number of dry coordinates (or equivalently, the maximum number of locked coordinates) necessary (respectively allowed) to make possible this process. We define the wet threshold of H as the minimum number τ of dry coordinates such that the system [S] has a solution for all c ∈ F n 2 , m ∈ F r 2 and W ⊆ {1, . . . , n} with #W ≤ nτ . The number of extra dry symbols beyond r, τr is the strict overhead of the system. It is also of interest to compute the average overhead δr, where δ is the average minimum number of dry coordinates such that [S] has a solution over all possible choices of H, c, m and W. In detail, we want to determine (1) necessary and sufficient conditions to ensure that the system [S] has a solution;

(2) the probability that [S] has a solution for given n, r and δ;

(3) the average overhead δr to have a solution.

These problems have already be treated by several authors. Fridrich, Goljan and Soukal [START_REF] Fridrich | Efficient wet paper codes[END_REF][START_REF] Fridrich | Wet paper codes with improved embedding efficiency[END_REF][START_REF] Fridrich | Steganography via codes for memory with defective cells[END_REF] studied [START_REF] Chai | A Characteristic Set Method for Solving Boolean Equations and Applications in Cryptanalysis of Stream Ciphers[END_REF] and showed that we can take r = δ + O(2 -δ/4 ) as δ → ∞, which gives a first answer to (3). Schönfeld and Winkler [START_REF] Schönfeld | Embedding with syndrome coding based on BCH codes[END_REF] treated the particular case of BCH codes, giving detailed computer results. Barbier, Augot and Fontaine [START_REF] Barbier | Infallible method for Steganography through Syndrome Coding with locked positions[END_REF] gave sufficient conditions for the existence of solutions by slightly modifying the problem [S] for linear codes. The case of Reed-Solomon codes has been treated by Fontaine and Galand in [START_REF] Fontaine | How Reed-Solomon codes can improve steganographic schemes[END_REF]. In some of these works the reader may find a study of the embedding efficiency as well as some implementation issues.

The aim of this article is to take another step in this study. We give exact answers to the questions (1) in section 2 and (3) in section 3 above, relating the wet threshold and overhead to well known parameters of the code having H as parity check matrix, and highlighting the role played by the dual distance. The relation with the weight hierarchy of codes is studied in section 4. Finally in section 5 we extend the matrix encoding method to the broad family of systematic codes, showing the relationship between stegoschemes, resilient functions and orthogonal arrays. We show that wet paper codes arising from systematic nonlinear codes may behave better than the ones coming from linear codes, in the sense that they may require less free positions to ensure the existence of solution. Proof. Since G is a parity check matrix of C ⊥ , a nonzero word in C ⊥ with support contained in W imposes a linear condition on the columns of G W and conversely.

π W (c) ∈ π W (cl(m) + C). Since #π W (F n 2 ) = 2 ℓ ,
More generally, if there exist w independent words of C ⊥ with support in W then we have rank(G W ) = ℓw. This suggests that the weight hierarchy of C also plays a role in the study of the solvability of [S]. This study will be conducted later in section 4. Proof. If δ ≥ nd ⊥ + 1 then #W < d ⊥ and no nonzero codeword of C ⊥ has support contained in W. Conversely, take a codeword of weight d ⊥ and a set W of cardinality n-δ containing its support. Then rank(G W ) < nδ and the homogeneous system Hx t = 0 has no solution for c such that π W (c) is not in the subspace π W (C) spanned by the rows of

G W . When rank(G W ) = n -δ, then the number of solutions is #C/#π W (C) = 2 δ-r .
Then when using a parity check matrix of a [n, n-r] code C, at most n-d ⊥ +1 dry symbols are needed to embed r information symbols. The wet threshold of C is τ = nd ⊥ + 1 and its strict overhead is nd ⊥ + 1r. Remark that according to the Singleton bound applied to C ⊥ we have nd ⊥ + 1 ≥ r. The difference nd ⊥ + 1r is known as the Singleton defect of C ⊥ . Thus, when using a parity check matrix of C to embed information via wet paper codes, the strict overhead is just the Singleton defect of the dual code C ⊥ .

Example 2.4. (1) Consider the binary Hamming code of redundancy s and length n = 2 s -1. The dual distance is d ⊥ = 2 s-1 , hence we can embed s information bits into a cover vector of length n with 2 s-1 ≈ n/2 dry positions. To see that less dry symbols are not enough to have solution with certainty, consider a parity-check matrix whose rows are the binary representations of integers 1, . . . , 2 s -1. When deleting the last 2 s-1 columns of H we obtain a matrix whose last row is 0. Note also that the method proposed in [START_REF] Barbier | Infallible method for Steganography through Syndrome Coding with locked positions[END_REF] allows to embed one information bit for n/2 dry positions modifying one bit of the cover vector. (2) In general it is not simple to construct codes with bounded Singleton defect. An exception are algebraic geometry codes, built from an algebraic curve and two rational divisors, see [START_REF] Munuera | On the generalized Hamming weights of geometric Goppa codes[END_REF]. It is known that the Singleton defect of a code comming from a curve X is bounded by the genus of X . Therefore it is possible to construct wet paper codes with strict overhead as small as desired.

Computing the overhead

Our second task is to compute the average overhead m = δr to have a solution for random C, W, c and m (according with previous notations). Also we obtain an estimate on the probability of having solution. Let us denote by avrank(t, s) the average rank of a random t × s matrix M. Proposition 3.1. For random C, W, c and m as above, the probability that δ dry symbols are enough to transmit r ≤ δ message symbols is

p = 2 avrank(n-r,n-δ)-(n-δ) .
Proof. The probability that the corresponding system [S] have a solution is

p = prob (π W (c) ∈ π W (cl(m) + C)) = #π W (C) 2 n-δ = 2 avrank(G W ) 2 n-δ .
The function avrank(t, s) can be computed using theorem 3.2 below. The rank properties of random matrices have been investigated in coding theory, among other fields, related to codes for the erasure channel, see e.g. [START_REF] Studholme | Random matrices and codes for the erasure channel[END_REF]. As shown in [START_REF] Fridrich | Efficient wet paper codes[END_REF][START_REF] Fridrich | Wet paper codes with improved embedding efficiency[END_REF], these results allow us to give an estimate on the average overhead. Since G W is a (nr) × (nδ) matrix and (nr) -(nδ) = δr, then m can be seen as the minimum number of extra rows beyond nδ required to obtain a matrix of full rank. Let t, m be non negative integers and M t+m,t be a random (t + m) × t matrix with m ≥ 0.

Theorem 3.2. Let M t+m,t be a matrix where the elements of F 2 are equally likely. Then

lim t→∞ prob (rank(M t+m,t ) = t -s) = ∞ j=s+m+1 1 -2 -j /2 s(s+m) s j=1 1 -2 -j .
See [START_REF] Cooper | On the rank of random matrices[END_REF][START_REF] Kolchin | Random Graphs[END_REF][START_REF] Studholme | Random matrices and codes for the erasure channel[END_REF]. It is known that this formula is very accurate even for small t and m. This theorem directly allows us to obtain numerical estimates on the function avrank and consequently on the probability that [S] admits a solution for random C, W, c and m. These estimates can be found in the literature (see [START_REF] Schönfeld | Embedding with syndrome coding based on BCH codes[END_REF] and the references therein) and we will not repeat them here. Also theorem 3.2 can be used to compute the average number of extra rows needed to have full rank. Following [START_REF] Studholme | Random matrices and codes for the erasure channel[END_REF], for any positive m, let

Q m = ∞ j=m+1 1 -2 -j .
According to the theorem, the probability that exactly m extra rows beyond t are needed to obtain a (t + m) × t random matrix of full rank is

Q m -Q m-1 . Since Q m-1 = ((2 m -1)/2 m )Q m we have Q m -Q m-1 = Q m /2 m , so the average number of extra rows is m = ∞ m=1 m(Q m -Q m-1 ) = ∞ m=1 m 2 m Q m .
This series is convergent as it is upper-bounded by a convergent arithmetic-geometric series. Let us remember that from elementary calculus we have

∞ m=1 mx m = x/(1 -x) 2 when |x| < 1. Then m = ∞ m=1 m 2 m Q m < ∞ m=1 m 2 m = 2.
A direct computation shows that m = 1.6067... Then the average overhead is 1.6067 and, for n large enough, δ dry bits are enough to transmit r ≈ δ -1.6 information bits.

Solvability and the generalized Hamming weights

Let C be a linear [n, nr] code and let C ⊥ be its dual. The dual distance d ⊥ can be expressed in terms of C via its weight hierarchy. Let us remember that for 1 ≤ t ≤ nr, the t-th generalized Hamming weight of C is defined as (see [START_REF] Wei | Generalized Hamming weights for linear codes[END_REF])

d t (C) = min{#supp(L) : L is a t-dimensional linear subspace of C} where supp(L) = ∪ x∈L supp(x).
The sequence d 1 (C), . . . , d n-r (C) is the weight hierarchy of C.

Two important properties of the weight hierarchy are the monotonicity

d 1 (C) < d 2 (C) < • • • < d n-r (C) and the duality {d 1 (C), . . . , d n-r (C)} ∪ {n + 1 -d 1 (C ⊥ ), . . . , n + 1 -d r (C ⊥ ) = {1, . . . , n}.
For simplicity we shall write d 1 , . . . , d n-r and d ⊥ 1 , . . . , d ⊥ r . If d n-r = n, we define the MDS rank of C as the least integer t such that d t = r + t (and consequently d s = r + s for all s ≥ t). Note that classical MDS codes are first rank MDS codes. This proposition leads us to consider codes with low MDS rank. MDS codes, and Reed-Solomon codes in particular, were proposed as good candidates in [START_REF] Fontaine | How Reed-Solomon codes can improve steganographic schemes[END_REF]. The main drawback of MDS codes is its small length. So, we may consider codes of higher rank, reaching a balance between length and security in the existence of solutions. In this sense, algebraic geometry codes (defined in example 2.4) can be a good option. It is known that an AG code coming from a curve of genus g has MDS rank at most g + 1a, where a is its abundance, more details in [START_REF] Munuera | On the generalized Hamming weights of geometric Goppa codes[END_REF]. Yet we find again the problem of the length of obtained codes. For example, it has been conjectured that Near MDS codes (codes for which d + d ⊥ = n) over F q have length upper bounded by q + 1 + 2 √ q (observe that codes arising from elliptic curves are either MDS or NMDS). Another option is to extend the ground alphabet. Several strategies have been proposed. One of the more interesting is to consider the Justensen construction with algebraic geometric codes [START_REF] Shen | A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate[END_REF]. The following result extends proposition 2.3 to all generalized Hamming weights.

Proposition 4.2. If d t > δ ≥ r for some t ≥ δ -r, then rank(G W ) ≥ n -r -t + 1 for every set W ⊆ {1, . . . , n} with #W = n -δ. Proof. Consider the code C ⊥ W obtained from C ⊥ by shortening at the positions in D. Since G W is a parity-check matrix for C ⊥ W , we have rank(G W ) = n-δ-dim(C ⊥ W ). If d ⊥ t ≥ n-δ+1 then it holds that dim(C ⊥ W ) ≤ t -1, hence rank(G W ) ≥ n -δ -t + 1. Assume d t > δ. Then n -d t + 1 < n -δ + 1,
and by the duality and monotonicity properties, the interval [nδ + 1, n] contains at least δt + 1 terms of the weight hierarchy of C ⊥ . Thus d ⊥ r-δ+t ≥ nδ + 1 and we get the statement.

A generalization to systematic codes

In this section we extend the matrix embedding construction, and the wet paper method in particular, to the wide family of systematic codes. We show that stegoschemes based on these codes are handled essentially in the same manner as in the case of linear codes. The use of systematic codes was suggested by Brierbauer and Fridrich in [START_REF] Brierbrauer | Constructing good covering codes for applications in steganography[END_REF], where stegoschemes arising from the Nordstrom-Robinson codes are treated in some detail. Here we go deeper into this study, showing the relationships between stegoschemes, orthogonal arrays and resilient functions. We pay special attention to the analogue of proposition 2.3, showing its combinatorial nature.

5.1. Systematic codes. Let us remember that for a set U ⊆ {1, . . . , n} with u = #U, we denote by π U : F 2 n → F 2 u the projection on the coordinates of U. If V = {1, . . . , n} \ U, we shall write a vector x ∈ F n 2 as x = (u, v), where

u = π U (x) ∈ F u 2 and v = π V (x) ∈ F v 2 , v = n -u.
A code C of length n is systematic if there exist u positions that carry the information. More formally, given a set U ⊆ {1, . . . , n}, we say that C is systematic at the positions of U (or simply systematic when the set U is understood) if for every u ∈ F u there exists one and only one codeword x ∈ C such that π U (x) = u. Up to reordering of coordinates we can always assume that U = {1, . . . , u} and V = {u + 1, . . . , n}.

If C is systematic then #C = #F u 2 = 2 u . We say that C is a [n, u] code.
Clearly every [n, u] linear code is systematic of dimension u hence this notation is consistent. Thus systematic codes generalize linear codes. However the family of systematic codes is much greater than the family of linear codes (apart from the advantage of being defined over alphabets other than fields). To see that note that it is fairly simple to construct a systematic code C: just complete each vector in F u 2 to a vector in F n 2 . This completion induces a generator function σ = σ C :

F u 2 → F n-u 2 defined to C = {(u, σ(u)) : u ∈ F u 2 }.
Then C is linear if and only if so is σ. In this there exists a u × (nu) matrix Σ such that σ(u) = uΣ. Then (I u , Σ) is a generator matrix for C and consequently H = (-Σ T , I n-u ) is a parity-check matrix of C. Since every map F u 2 → F 2 can be written as a reduced polynomial, the components σ 1 , . . . , σ n-u of σ are square free reduced polynomials in variables x 1 , . . . , x u .

The family of systematic codes contains some nonlinear codes having excellent parameters. Among these we can highlight the Preparata, Kerdrock, Nodstrom-Robinson and many others. Some of them have also efficient decoding systems (which is the main drawback of nonlinear codes). Other well known example is the following.

Example 5.1. The Nadler code N is a [START_REF] Keinänen | Techniques for solving Boolean equation systems[END_REF][START_REF] Crandall | Some notes on steganography[END_REF] systematic nonlinear code with covering radius ρ = 4 and minimum distance d = 5, [17]. N contains twice as many codewords as any linear code with the same length and minimum distance, see [START_REF] Van Lint | Introduction to Coding Theory[END_REF]. Among the current practical applications of N we can mention its use for the decoder module of SINCGARS radio systems [START_REF] Hamilton | SINCGARS system improvement program (SIP) specific radio improvement[END_REF]. The combinatorial structure of N was shown by van Lint in [START_REF] Van Lint | A new description of the Nadler code[END_REF]; following this article, the 32 codewords of N are shown in Table 1 1, N can be described by the function σ. Up to reordering of coordinates so that N is systematic at positions 1, . . . , 5, we have

σ 6 = x 1 + x 2 + x 3 + (x 1 + x 5 )(x 3 + x 4 ) σ 7 = x 1 + x 2 + x 4 + (x 1 + x 3 )(x 4 + x 5 ) σ 8 = x 1 + x 2 + x 5 + (x 1 + x 4 )(x 3 + x 5 ) σ 9 = x 2 + x 3 + x 4 + x 1 x 4 + x 4 x 5 + x 5 x 1 σ 10 = x 2 + x 3 + x 5 + x 1 x 3 + x 3 x 4 + x 4 x 1 σ 11 = x 1 + x 4 + x 5 + x 1 x 3 + x 3 x 5 + x 5 x 1 σ 12 = x 1 + x 2 + x 3 + x 4 + x 5 + x 3 x 4 + x 4 x 5 + x 5 x 3 .
In order to construct a stegoscheme from a systematic code, we need a partition of F n 2 and a family of decoding maps, one map for each element of the partition.

Proposition 5.2. Let C be a [n, u] systematic code. Then the sets (0, v) + C, v ∈ F n-u 2 ,
are pairwise disjoint and hence the family

((0, v) + C : v ∈ F n-u 2 ) is a partition of F n 2 .
Proof.

If (0, v 1 ) + c 1 = (0, v 2 ) + c 2 for some v 1 , v 2 ∈ F n-u 2 and c 1 , c 2 ∈ F n 2 , then π U (c 1 ) = π U ((0, v 1 ) + c 1 ) = π U ((0, v 2 ) + c 2 ) = π U (c 2 ). Then c 1 = c 2 and consequently v 1 = v 2 .
In general the translates x + C are not pairwise disjoint when x runs over the whole space F n 2 . In that case these sets do not give a partition of F n 2 and they are not useful for decoding purposes. Anyway the partition given by proposition 5.2 allows us to define a syndrome map s :

F n 2 → F n-u 2 as follows: define s(x) = v if x ∈ (0, v) + C.
The systematic property leads us to compute s(x) efficiently: if x = (u, w) then we can write (u, w) = (u, σ(u)) + (0, s(x)) and hence s(x) = wσ(u). If σ is a linear map, and hence the code C is linear, then s(x) = xH T is the usual syndrome for linear codes.

A decoding map for a general code C ⊆ F n 2 is a mapping dec :

F n 2 → C such that for every x ∈ F n 2 , dec(x) is the closest word to x in C.
If more than one of such words exists, simply choose one of them at random.

Proposition 5.3. Let C ⊆ F n 2 be a systematic code and z ∈ F n 2 . If dec is a decoding map for C then dec z (x) = z + dec(x -z) is a decoding map for the code z + C. Proof. Clearly dec z (x) ∈ z + C. If there exists z + c ∈ z + C such that d(x, z + c) < d(x, dec z (x)), then d(x -z, c) < d(x -z, dec(x -z))
, which contradicts that dec is a decoding map for C.

5.2.

Stegoschemes from systematic codes. Let C be a [n, n-u] systematic code and let dec be a decoding map for C. According to propositions 5.2 and 5.3, we obtain a stegoscheme S = S(C) from C, whose embedding and recovering maps are emb :

F n 2 × F u 2 → F n 2 , emb(c, m) = dec (0,m) (c) = (0, m) + dec(c -(0, m)) rec : F n 2 → F u 2 , rec(x) = s(x). By definition of syndrome it holds that rec(emb(c, m)) = s(dec (0,m) (c)) = m for all c ∈ F n 2 and m ∈ F u 2 .
Compare this with the usual expression emb(c, m) = ccl(cH Tm) for linear codes. We note that to perform this embedding it is necessary to have a table with all syndromes and cosets leaders, even if the decoding map used does not require them. Therefore, the systematic formulation can be useful even using linear codes.

Let us study the parameters of S(C) in relation with those of C. The cover length is n and the embedding capacity r = u. To compute its embedding radius and average number of embedding changes we first need to recall some concepts from coding theory. Given a general code D, its covering radius is defined as the maximum distance from a vector

x ∈ F n 2 to D, ρ(D) = max{d(x, D) : x ∈ F n 2 }, where d(x, D) = min{d(x, c) : c ∈ D}. The average radius of D, ρ(D) is the average distance from a vector x ∈ F n 2 to D ρ(D) = 1 2 n x∈F n 2 d(x, D).
If D is linear then both parameters can be obtained from the coset leader distribution of D, that is the sequence α 0 , . . . , α n , where α i is the number of coset leaders of weight i. Clearly α i ≤ n i . When i ≤ t = ⌊(d(D) -1)/2⌋ then all vectors of weight i are leaders hence we get equality, α i = n i . For i > t the computation of α i is a classical problem, considered difficult. For nonlinear D the coset leader distribution may be generalized to the distribution of distances to the code, defined as

α i = 1 #D #{x ∈ F n 2 : d(x, D) = i}
If D is linear then both definitions of α i 's coincide. A similar reasoning as above shows that the property α i ≤ n i with equality when i ≤ t = ⌊(d(D) -1)/2⌋ remains true for all codes. The covering radius of D is the maximum i such that α i = 0 and the average radius is given by ρ D). Thus all the translates ((0, v) + D : v ∈ F u 2 ) have the same distribution of distances to the code and hence the same average radius and covering radius. As a consequence we have the following result, which is well known for stegoschemes comming from linear codes. Then ρ(N ) = 2.296875. The stegoscheme derived from N allows to embed 7 bits of information into a cover vector of 12 bits, by changing 2.296875 of them on average and 4 of them at most. 5.3. Stegoschemes, resilient functions and orthogonal arrays. Systematic codes allows us to make a connection of stegoschemes with two objects of known importance in information theory: resilient functions and orthogonal arrays. A function f : F n 2 → F r 2 is called t-resilient for some integer t ≤ n, if for every T ⊆ {1, . . . , n} such that #T = t and every t ∈ F t 2 , all possible outputs of f (x) with π T (x) = t are equally likely to occur, that is if for all y ∈ F r 2 we have prob(f (x) = y | π T (x) = t) = 1 2 r (see the relation to recovering maps of stegoschemes). Resilient functions play an important role in cryptography, and are closely related to orthogonal arrays [START_REF] Stinson | Resilient functions and large sets of orthogonal arrays[END_REF]. An orthogonal array OA λ (t, n) is a λ2 t × n array over F 2 , such that in any t columns every one of the possible 2 t vectors of F t 2 occurs in exactly λ rows. A large set of orthogonal arrays is a set of 2 n-t /λ arrays OA λ (t, n) such that every vector of F n 2 occurs once as a row of one OA in the set. Then, by considering the rows of these arrays as vectors of F n 2 , a large set of OA gives a partition of F n 2 , see [START_REF] Stinson | Resilient functions and large sets of orthogonal arrays[END_REF]. There is a fruitful connection between orthogonal arrays and codes, see [START_REF] Williams | The theory of error-correcting codes[END_REF] Chapter 5, section 5. If C is a linear [n, nr] code then, according to proposition 2.3, the array having the codewords of C as rows is an OA 2 n-r-d ⊥ +1 (d ⊥ -1, n). Delsarte observed that a similar result holds also for nonlinear codes. Of course if C is not linear then the dual code does not exist, but the dual distance can be defined from the distance distribution of C via the dual transforms as follows [START_REF] Williams | The theory of error-correcting codes[END_REF]: The distance distribution of C is defined to be the sequence A 0 , . . . , A n , where

(D) = #D 2 n n i=0 iα i . If C is [n, n -u] systematic, then for all v ∈ F u 2 and x ∈ F n 2 we have d(x, (0, v) + D) = d(x -(0, v),
A i = 1 #C #{(x, y) ∈ C 2 : d(x, y) = i} i = 0, . . . , n. The dual distance distribution of C is A ⊥ 0 , . . . , A ⊥ n ,
where

A ⊥ i = 1 #C n j=0 A j K i (j)
and K i (x) is the i-th Krautchouk polynomial

K i (x) = i j=0 (-1) j x j n -x i -j . If C is linear then A ⊥ 0 , . . . , A ⊥ n is the distance distribution of C ⊥ . If C is [n, n -
u] systematic, then the array having the codewords of C as rows is an OA

2 n-u-d ⊥ +1 (d ⊥ -1, n).
Furthermore in this case all the translates (0, v) + C have the same distance distribution and hence the same dual distance.

Proposition 5.6. Let C be a systematic [n, nu] code with generator function σ and dual distance d ⊥ . For any v ∈ F u 2 let M v be the array having the words of (0, v) + C as rows. Then (a) The set

{M v | v ∈ F u 2 } is a large set of OA 2 n-u-d ⊥ +1 (d ⊥ -1, n). (b) The syndrome map s(u, w) = w -σ(u) is an (d ⊥ -1)-resilient function.
Proof. Let T ⊆ {1, . . . , n} with #T = d ⊥ -1 and t ∈ F t 2 . (a) According to Delsarte's theorem, every one of the possible 2 t vectors t occurs in exactly 2 n-u-d ⊥ +1 rows of π T (C). Then the same happens in each of the translates (0, v) + C. (b) As a consequence of (a), all possible outputs of s(x) with π T (x) = t are equally likely to occur, [START_REF] Stinson | Resilient functions and large sets of orthogonal arrays[END_REF]. 5.4. Locked positions with systematic codes. Let us return to the problem of embedding with locked positions. Let c ∈ F n 2 be a cover vector and m ∈ F u 2 be the secret we want to embed into c. There is a set W ⊆ {1, . . . , n} of nδ locked positions that cannot be altered during the embedding process. Consider a systematic [n, nu] code C and let s be the syndrome of C defined in section 5.1. As in the case of linear codes, the embedding is obtained as a syndrome, emb(c, m) = x with [SS] :

s(x) = m, x i = c i if i ∈ W
Also as in the case of linear codes we can ask for the minimum possible number of dry (free) positions required to ensure a solution of [SS], the wet threshold of C. Such a solution exists if and only if π Thus the threshold verifies τ ≤ nd ⊥ + 1. If we compare this result with theorem 2.3, we can see a significant difference: in that case the condition δ ≥ nd ⊥ + 1 was also necessary. This is due to the existence of dual when the code C is linear. If C is systematic but not linear, then such dual does not exist and it may happen τ < nd ⊥ + 1 so that we need less free coordinates than the required in the linear case. Let us see an example of this situation.

W (c + (0, m)) ∈ π W (C). In that case, if y ∈ C verifies π W (y) = π W (c + (0, m)), then x = y + (0, m) is a solution.
Example 5.8. The Nadler code has distance distribution 1, 0, 0, 0, 0, 12, 12, 0, 3, 4, 0, 0, 0 and dual distance distribution 1, 0, 0, 4, 18, 36, 24, 12, 21, 12, 0, 0. In particular d ⊥ = 3. When using this code for wet paper purposes, the corresponding system [SS] has a solution with certainty when the number of locked coordinates is ≤ d ⊥ -1 = 2, according to proposition 5.7. A direct inspection shows that for any 4 columns of N , every one of the possible 2 4 vectors of F 4 2 occurs. According to the Bush bound [START_REF] Hedayat | Orthogonal Arrays: Theory and Applications[END_REF] this is the maximum possible number of columns for which this can happen. Then the system [SS] has a solution with certainty when the number of locked coordinates is at most 4. Remark that the minimum distance of a [START_REF] Keinänen | Techniques for solving Boolean equation systems[END_REF][START_REF] Fridrich | Efficient wet paper codes[END_REF] linear code is 4, see [START_REF] Mint | Online database for optimal parameters of (t, m, s)-nets, (t, s)-sequences, orthogonal arrays, linear codes, and OOAs[END_REF], hence the maximum number of coordinates we can lock using linear codes with the same parameters as N is 3.

The above proposition 5.7 and example 5.8 suggest the use of nonlinear systematic codes as wet paper codes. The main drawback of using these codes is in the computational cost of solving [SS]. Solving a system of boolean equations is a classical and important problem in computational algebra and computer science. There exist several methods available, some of which are very efficient when the number of variables is not too large, see [START_REF] Chai | A Characteristic Set Method for Solving Boolean Equations and Applications in Cryptanalysis of Stream Ciphers[END_REF][START_REF] Keinänen | Techniques for solving Boolean equation systems[END_REF] and the references therein. Anyway the computational cost of solving [SS] is always greater than that of solving a system of linear equations. In conclusion, the use of nonlinear systematic codes can be an interesting option when the added security gained through a greater number of locked positions offsets the increased computational cost.

Conclusion

We have obtained necessary and sufficient conditions to make sure the embedding process in the wet paper context. These conditions depend on the dual distance of the involved code. We also gave a sufficient condition in the general case of systematic codes and provided the exact number of solutions. Finally, we showed that systematic codes can be good candidates in the design of wet paper stegoschemes.

2

  defined by emb(c, m) = dec m (c) and rec(x) = m if x ∈ C m . Then S = (emb, rec) is a [n, r] stegoscheme. As a consequence, the following objects are equivalent• a [n, r] stegoscheme S = (emb, rec); • a family {(C m , dec m ) : m ∈ F r 2 } where {C m : m ∈ F r 2 }gives a partition of F n 2 and for every m, dec m is a minimum distance decoding map for C m .

2 .

 2 A necessary and sufficient condition for the existence of solutions Let c, m, H and W as defined in the Introduction and let us study the solvability of the linear equation [S] : xH T = m, x i = c i if i ∈ W. Let C be the [n, n-r] linear code whose parity check matrix is H and let G be a generator matrix of C. Denote by C ⊥ the dual of C and by d ⊥ = d(C ⊥ ) the minimum distance of C ⊥ . For m ∈ F r 2 , we shall denote by cl(m) a leader of the coset {x ∈ F n 2 : xH T = m}. Since xH T can be interpreted as a syndrome, the system [S] has a solution if there exists x ∈ cl(m) + C such that π W (x) = π W (c), where π W is the projection over the coordinates of W. Equivalently [S] has a solution if and only if π W (c) ∈ π W (cl(m) + C). For a matrix M with n columns, let M W be the matrix obtained from M by deleting the columns with indexes in D.

Lemma 2 . 1 .

 21 For all cosets y + C, the projections π W (y + C) have the same cardinality, #π W (y + C) = 2 rank(G W ) . Thus [S] has a solution for general c and m if and only if the matrix G W has full rank, rank(G W ) = ℓ.Proof. π W (y + C) = π W (y) + π W (C), hence #π W (y + C) = #π W (C) and π W (C)is a vector space of dimension rank(G W ). For fixed c and m, [S] has a solution if and only if

Theorem 2 . 3 .

 23 The system [S] has a solution for arbitrary c ∈ F n 2 , m ∈ F r 2 and W ⊆ {1, . . . , n} with #W = nδ, if and only if δ ≥ nd ⊥ + 1. In this case [S] has exactly 2 δ-r solutions.

Proposition 4 . 1 .

 41 If C has MDS rank t and δ ≥ t + r -1, then the corresponding system [S] has a solution for arbitrary c ∈ F n 2 , m ∈ F r 2 and W ⊆ {1, . . . , n} with #W = nδ. Proof. By the duality property C has MDS rank t = n-r-d ⊥ +2 hence n-d ⊥ +1 = t+r-1 and proposition 2.3 implies the result.

Proposition 5 . 4 .

 54 Let C be a [n, n-u] systematic code and let S the stegoscheme obtained from C. Then the embedding radius of S is the covering radius of C and the average number of embedding changes R a (S) is the average radius of C. Proof. By definition of decoding map, the number of changes when embedding a message m into a vector x is d(x, emb(x, m)) = d(x -(0, m), C) and both statements hold. Example 5.5. The Nadler code of Example 5.1 is 2-error correcting, hence α 0 = 1, α 1 = 12, α 2 = 66. Other values of α are obtained by computer search: α 3 = 46, α 4 = 3, and α i = 0 for i = 5, . . . , 12.

Proposition 5 . 7 . 2 .

 572 If δ ≥ nd ⊥ + 1 then the system [SS] has a solution for all c ∈ F n 2 , m ∈ F u 2 and W ⊆ {1, . . . , n} with #W = nδ. In this case, [SS] has exactly 2 δ-u solutions.Proof. There exists a solution all c ∈ F n 2 , m ∈ F u 2 and W ⊆ {1, . . . , n} if and only if π W (C) = F n-δ The statement follows from Delsarte's theorem and proposition 5.6.

  this occurs for all c and m if and only if G W has full rank, rank(G W ) = ℓ. Note that r ≤ δ. Lemma 2.2. G W has full rank if and only if there is no nonzero word of C ⊥ with support contained in W.

Table 1 .

 1 The 32 codewords of the Nadler code It is not hard to check that this code is systematic at positions 1,2,4,7, 10. Besides the exhaustive enumeration given in Table

	.

This work was supported in part by Junta de CyL under grant VA065A07 and by Spanish Ministry for Science and Technology under grants MTM2007-66842-C02-01 and MTM 2007-64704.

1