Presentation

 

Research fields

In its broad acceptation, Software Engineering consists in proposing practical solutions, founded on scientific knowledge, in order to produce and maintain software with constraints on costs, quality and deadlines. In this field, it is admitted that the complexity of a software increases exponentially with its size. However on the one hand, the size itself of the software is on average multiplied by ten every ten years, and on the other hand, the economic pressure resulted reducing the durations of development, and in increasing the rates of modifications made to the software.

To face these problems, today's mainstream approaches build on the concept of component based software. The assembly of these components makes it possible to build families of products (a.k.a. product lines) made of many common parts, while remaining opened to new evolutions. As component based systems grow more complex and mission-critical, there is an increased need to be able to represent and reason on such assemblies of components. This is usually done by building models representing various aspects of such a product line, such as for example the functional variations, the structural aspects (object paradigm), of the dynamic aspects (languages of scenarios), without neglecting of course nonfunctional aspects like quality of service (performance, reliability, etc.) described in the form of contracts, or the characteristics of deployment, which become even dominating in the field of reactive systems, which are often distributed and real-time. Model Driven Engineering (MDE) is then a sub-domain of software engineering focusing on reinforcing design, validation and test methodologies based on multi-dimensional models.

Project-team presentation overview

The research domain of the Triskell project is the model driven development of software product lines. Triskell is particularly interested in component based reactive and large scale distributed systems with quality of service constraints, including reliability, performance, timeliness etc.

Triskell's main objective is to develop model-based methods and tools to help the software designer to obtain a certain degree of confidence in the reliability of component assemblies that may include third-party components. This involves, in particular, investigating modeling languages allowing specification of both functional and non-functional aspects and which are to be deployed on distributed systems. It also involves building a continuum of tools which make use of these specification elements, from off-line verifiers, to test environments and on-line monitors supervising the behavior of the components in a distributed application. Since these modeling languages and associated tools appear quite open-ended and very domain specific, there is a growing need for ``tools for building tools for building software''. Triskell is hence developping KerMeta as an original meta-meta modeling approach allowing the user to fully define his modeling languages (including dynamic semantics) and associated environments (including interpreters, compilers, importers/exporters, etc.) within Eclipse.

To avoid the pitfall of developping ``tools for building tools for the sake of it'', the Triskell project also has the goal of explicitly connecting research results to industrial problems through technology transfer actions. This implies, in particular, taking into account the industrial standards of the field, namely the Eclipse Modeling Framework emf, uml, Corba Component Model (ccm), Com+/.Net and Enterprise JavaBeans.

Triskell is at the frontier of two fields of software: the field of specification and formal proof of software, and that of design which, though informal, is organized around best practices (e.g.; Design Patterns or the use of off-the-shelf components). We believe that the use of the techniques that we develop will make it possible to improve the transition between these two worlds, and will contribute to the fluidity of the processes of design, implementation and testing of software.

Scientific foundations

The Triskell project studies new techniques for the reliable construction of software product lines, especially for distributed and reactive software. The key problems are components modeling and the development of formal manipulation tools to refine the design, code generation and test activities. The validation techniques used are based on complex simulations of models building on the standards in the considered domain.

The object-oriented approach to Software Engineering

keywords : Objects, design patterns, frameworks, software components, UML.

The object-oriented approach is now widespread for the analysis, the design, and the implementation of software systems. Rooted in the idea of modeling (through its origin in Simula), object-oriented analysis, design and implementation takes into account the incremental, iterative and evolutive nature of software development [16, 6]: large software system are seldom developed from scratch, and maintenance activities represent a large share of the overall development effort.

In the object-oriented approach, objects are instances of classes. A class encapsulates a single abstraction in a modular way. A class is both closed, in the sense that it can be readily instanciated and used by clients objects, and open, that is subject to modifications through inheritance [22].

Since by definition objects are simple to design and understand, complexity in an object-oriented system is well known to be in the collaboration between objects, and large systems cannot be understood at the level of classes and objects. Still these complex collaborations are made of recurring patterns, called design patterns. The idea of systematically identifying and documenting design patterns as autonomous entities was born in the late 80's. It was brought into the mainstream by such people as Beck, Ward, Coplien, Booch, Kerth, Johnson, etc. (known as the Hillside Group). However the main event in this emerging field was the publication, in 1995, of the book Design Patterns: Elements of Reusable Object Oriented Software by the so-called Gang of Four (GoF), that is Erich Gamma, Richard Helm, Ralph Johnson and John Vlissides [8]. Today, design patterns are widely accepted as useful tools for guiding and documenting the design of object-oriented software systems. Design patterns play many roles in the development process. They provide a common vocabulary for design, they reduce system complexity by naming and defining abstractions, they constitute a base of experience for building reusable software, and they act as building blocks from which more complex designs can be built. Design patterns can be considered reusable micro-architectures that contribute to an overall system architecture. Ideally, they capture the intent behind a design by identifying the component objects, their collaborations, and the distribution of responsibilities.

Frameworks are also closely related to design patterns. An object-oriented software framework is made up of a set of related classes which can be specialized or instantiated to implement an application. It is a reusable software architecture that provides the generic structure and behavior for a family of software applications, along with a context which specifies their collaboration and use within a given domain [1]. A framework differs from a complete application in that it lacks the necessary application-specific functionality. It can be considered as a prefabricated structure, or template, of a working application, where a number of pieces in specific places, called plug-points or hot spots, are either not implemented or given overridable implementations. To obtain a complete application from a framework, one has to provide the missing pieces, usually by implementing a number of call-back functions (that is, functions that are invoked by the framework) to fill the plug-points. In an object-oriented context, this feature is achieved by the dynamic binding: an operation can be defined in a library class but implemented in a subclass in the application specific code. A developer can thus customize the framework to a particular application by subclassing and composing instances of framework classes [8]. A framework is thus different from a classical class library in that the flow of control is usually often bi-directional between the application and the framework (see Figure ??). The framework is in charge of managing the bulk of the application, and the application programmer just provides various bits and pieces. This is similar to programming some event driven applications, when the application programmer usually has no control over the main control logic of the code.

Design patterns can be used to document the collaborations between classes in a framework. Conversely, a framework may use several design patterns, some of them general purpose, some of them domain-specific. Design patterns and frameworks are thus closely related, but they do not operate at the same level of abstraction: a framework is made of software, whereas design patterns represent knowledge, information and experience about software. In this respect, frameworks are of a physical nature, while patterns are of a logical nature: frameworks are the physical realization of one or more software pattern solutions; patterns are the instructions for how to implement those solutions.

The object notion also provides the bases needed to develop the concept of software component, for which Szyperski's definition [30] is now generally accepted, at least in the industry:
A software component is a unit of composition with contractually specified interfaces and explicit context dependencies only. A software component can be deployed independently and is subject to composition by third party.
Components help reducing costs by allowing reuse of application frameworks and components instead of redeveloping applications from scratch (product line approach). But more important, components offer the possibility to radically change the behaviors and services offered by an application by substitution or addition of new components, even a long time after deployment. This has a major impact of software lifecycle, which should now handle activities such as:

It seems clear that empirical methods without real component composition models that have appeared during the emergence of a real component industry (at least in the Windows world) are now the cause of untractable validation and integration problems can not be transposed to more critical systems (see for example the accidental destruction of Ariane 501 [19]).

Providing solutions for formal component composition models and for verifiable quality (notion of trusted components) are especially relevant challenges. Also the methodological impact of component-based development (for example within the maturity model defined by the sei (cmm model)) is also worth attention.

Central to this trusted component notion is the idea of contract. A software contract captures mutual obligations and benefits among stake-holder components, for example between the client of a service and its suppliers (including subclasses). Contracts strengthen and deepen interface specifications. Along the lines of abstract data type theory, a common way of specifying software contracts is to use boolean assertions called pre- and post-conditions for each service offered, as well as class invariants for defining general consistency properties. Then the contract reads as follows: the client should only ask a supplier for a service in a state where the class invariant and the precondition of the service are respected. In return, the supplier promises that the work specified in the postcondition will be done, and the class invariant is still respected. In this way rights and obligations of both client and supplier are clearly delineated, along with their responsibilities. This idea was first implemented in the Eiffel language [23] under the name Design by Contract, and is now available with a range of expressive power into several other programming languages (such as Java) and even in the Unified Modeling Language (UML) with the Object Constraint Language (OCL) [32].

Some prototypes in laboratories provide answers to these problems, but the massive adoption of UML in many industrial domains open new perspectives to make the underlying ideas evolve, scale up, and hence become profitable. Unlike its predecessors, (omt, Booch, etc.), that only proposed a graphical syntax, UML is partially formalized by a meta-model (expressed itself as a UML model) and contains a very sophisticated constraint language called OCL (Object Constraint Language), that can be used indifferently at the model level or at the meta-model level. All this makes it possible to consider formal manipulations of models that capture many aspects of software, both from the technical side, (with the four UML main dimensions : data, functional, dynamic, and deployment) and on the process side, ranging from the expression of requirements and the analysis to design (framework models and design patterns) and test implantation.

Mathematical foundations of distributed software

keywords : Labelled Transition Systems, Partial orders.

Labelled transitions systems are the mathematical structure that characterizes best the foundations of research on software models. This structure was developed 50 years ago. However, models of real systems can be very large, and it is not always possible to build the complete model before performing a formal manipulation. In some cases, it is possible to apply lazy construction methods (also called on the fly). Concurrency is another fundamental aspect that must be considered by models. This is the central concept needed for the analysis of distributed systems.

Labelled Transition Systems
A lts is a directed graph which edges are labelled by letters representing events. A finite state automaton designates a LTS which set of states and edges is finite. This model is the simplest way known to represent behaviors of reactive systems.

Transition systems can be obtained from specifications of systems described with high-level languages such as UML. This is done through a definition of an operational semantics of the language, which is usually formalized as a set of deduction rules. For simple languages such as process algebras, this operational semantics can be defined with a dozen of rules. For a complex language like UML, the definition of rules can take hundreds of pages.

For performance reasons, the operational semantics rules are never used as such, and some simplifications such as state encoding help saving some space. Usually, algorithms inherited from language theory are based on an explicit construction of a transition system. However, for the class of problems that are considered within the Triskell project, and exhaustive representation of the LTS is not always needed, and a lazy construction method can be used: the only part of the specification needed for the algorithm is computed. Similarly, some parts of a LTS under construction can be ``forgotten'', hence saving memory. The combination of these strategies allows the study of real size specifications with reasonable resources.

Non interleaved models
One of the main drawbacks of interleaved models is that concurrency is represented by means of interleavings. Hence, it is sometimes impossible to differentiate concurrency and branching in a specification. Furthermore, representing all possible interleavings of some behaviors is not always necessary to check a given property, and needs a lot of memory space. Partial order models bring a solution to this problem. They can represent concurrency in a more intuitive way: two concurrent events are not causally related.

Several partial order models are frequently used: Petri nets, Pom-sets, event structures, ... It is possible to get back to a transition system representation of a finite partial order representation by considering marking graphs for Petri nets, linearisations of Pom-sets, or configurations of event structures. Within the project, partial orders are seen as the most natural way for providing a semantics to scenarios (MSC, UML sequence diagrams,...).

Application domains

Software for telecommunication

keywords : telecommunication, software engineering, test, UML

The telecommunication world is evolving rapidly. New worldwide infrastructures connecting multiple components are settling. Mobile communications is also a growing sector and new services are constantly developed.

On the software point of view, building a new application from scratch is no longer possible. There is a real need for flexible solutions allowing to deal at the same time with a wide range of needs (product lines modeling and methodologies for managing them), while reducing the time to market (such as derivation and validation tools).

The Triskell project has gained experience in model engineering, and finds here a propitious domain. The increasing software complexity and the reliability and reusability requirements fully justify the methods developed by our project. The main themes studied are reliable software components composition, UML-based developments validation, and test generation from UML models.

The research activity in Triskell focuses at the same time on development efficiency and reliability. The main applications of this research is clearly related to the telecommunication domain, and mainly concern reliable construction of communication software, and object oriented systems testing.

Reliability is an essential requirement in a context where a huge number of softwares (and sometimes several versions of the same program) may coexist in a big telecommunication network. On one hand, software should be able to evolve very fast, as new features or services are frequently added to existing ones, but on the other hand, the occurrence of a fault in a system can be very costly, and time consuming. A lot of attention should then be paid to interoperability, i.e. the ability for software to work properly with other. We think that formal methods may help solving this kind of problems. Note that formal methods should be more and more integrated in an approach allowing system designer to build software globally, in order to take into account constraints and objectives coming from user requirements. These methodologies are in their early years. A good example of such techniques is the object oriented approach, which is becoming more popular in the telecommunication world.

Software testing is another aspect of reliable development. Testing activities mainly consist in ensuring that a system implementation conforms to its specifications. Whatever the efforts spent for development, this phase is of real importance to ensure that a system behaves properly in a complex environment.

Main contributions (1999-2002)

Three main research directions were defined at the creation of Triskell project.

Contract-based design:


One of our objectives was to strengthen the contract based approach for OO designs. In that direction, a new model for contract aware components (based on a 4 level decomposition) has been defined in [5], and now serves as a reference in this domain (for instance it has been adopted by the SEI. See also the citation index for this article). In relationship with the European QCCS IST project ("Quality Controlled Component-based Software"), UML extensions for specifying quality of service properties of UML 2 components have been defined [34, 33]. J.-M. Jézéquel gave a tutorial on ``Model-Driven Engineering with Contracts, Patterns, and Aspects'' at AOSD 2003 (2nd International Conference on Aspect-Oriented Software Development).

Meta-modeling and model-transformation


Many results have been obtained in the fields of meta-modeling and model transformations, and prototyped with the UMLAUT tool [24]. A weaving mechanism within the QCCS weaver and modeler platform, to weave QoS aspects (and especially real-time ones), is now available [15, 14]. Meta-modeling is also addressed, since we have defined ways of expressing design patterns, aspect-oriented mechanisms and more widely frameworks within the UML meta-model [28, 10, 13, 29, 27]. One of the consequences of these definitions is the enhancement of the current work on model transformations to guarantee, during refinement and deployment stages, a stated QoS or any other non functional properties: a first result was obtained with testability [3]. The integration of formal methods (MSCs scenarios, models for true concurrency) to the UML practice, in terms of model transformation has been studied. A model for true concurrency has been properly defined in [7, 17] and is under connection to the Umlaut framework: test generation techniques should be available for deployed systems with deployed embedded testers. Moreover, we have defined how to obtain MSC projections that allow the abstraction of complex interactions [12]. This the first step, in terms of model manipulation and transformation, to allow the creation of behavioral assets (especially in a product-line context).

Model-Based Testing for components and component-based systems


Several results have been obtained during the last years. First, some of the scientific hard-points have been overcame and a prototype connection of the TGV test generation tool to the Umlaut framework is now effective [9, 26] and validated on real-world case studies (Gemplus, FT R&D). Still, more work is needed both at the conceptual level (e.g.; how to efficiently encode sates made of object graphes), as well as the implementation level to make this prototype usable by third parties. A dedicated test language to specify high level test objectives ---and represent the generated test cases--- using the UML sequence diagrams has been developed: it forms the basis of the UML test profile currently under standardization at OMG [25]. The assembling of components has also been studied and efficient algorithms have been defined and integrated to the Objecteering Case tool. They automate the ordering of integration by minimizing the testing effort (by reducing the creation of stubs during components integration) [31, 21, 11]. Since the first set of test cases provided by testers often lacks of efficiency for 'certifying' the quality of a component, we automated the improvement of test cases by proposing new computational intelligence algorithms. The criterion used for component qualification is the mutation analysis: the approach has been successfully applied on unit components and middle-size systems (for qualifying a system, a new version of mutation analysis has been proposed) [4]. Tools support the whole test enhancement process (for Java and C# programs). To finish with, our design-for-testability approach [18] has been globally studied using software metrics [2] for contracts impact of robustness and diagnosability and for testability [3].

References

[1]
Brad Appleton. Patterns and software: Essential concepts and terminology. Object Magazine Online, May 1997.

[2]
[PDF] B. Baudry, Y. LeTraon, and J.-M. Jézéquel. Robustness and diagnosability of oo systems designed by contracts. In Proceedings of Metrics'01, London, UK, April 2001.

[3]
[PDF] B. Baudry, Y. Le Traon, and G. Sunyé. Testability analysis of UML class diagram. In Proceedings of Metrics02, pages 54--63, Ottawa, Canada, June 2002.

[4]
[PDF] Benoit Baudry, Franck Fleurey, Jean-Marc Jézéquel, and Yves Le Traon. Genes and bacteria for automatic test cases optimization in the .net environment. In Proceedings of ISSRE02 (International Symposium on Software Reliability Engineering), pages 195--206, Annapolis, USA, November 2002.

[5]
[PDF] A. Beugnard, J.-M. Jézéquel, N. Plouzeau, and D. Watkins. Making components contract aware. IEEE Computer, 13(7), July 1999.

[6]
Grady Booch. Object-Oriented Analysis and Design with Applications. Benjamin Cummings, 2nd edition, 1994.

[7]
[PDF] C.Jard. Synthesis of distributed testers from true-concurrency models of reactive systems. Journal of Information and Software Technology, 2002. To appear.

[8]
Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison Wesley, 1995.

[9]
[PDF] Alain Le Guennec. Génie Logiciel et Méthodes Formelles avec UML : Spécification, Validation et Génération de tests. PhD thesis, École doctorale MATISSE, Universite de Rennes 1, June 2001.

[10]
[PDF] Alain Le Guennec, Gerson Sunyé, and Jean-Marc Jézéquel. Precise modeling of design patterns. In Proceedings of UML 2000, volume 1939 of LNCS, pages 482--496. Springer Verlag, 2000.

[11]
Vu Le Hanh. test et modèle UML : stratégie, plan et synthèse de test. PhD thesis, Ecole doctorale MATISSE, Universite de Rennes 1, November 2002.

[12]
Loïc Hélouët. Projections et comparaisons de scénarios. In Proc of AFADL'2003, Approches Formelles dans l'Assistance au Développement de Logiciels, Rennes, France, Jan. 2003.

[13]
[PDF] Wai Ming Ho. Contribution à la Réification d'un Processus de Conception. PhD thesis, Ecole doctorale MATISSE, Universite de Rennes 1, September 2001.

[14]
[PDF] W.M. Ho, J.-M. Jézéquel, F. Pennaneac'h, and N. Plouzeau. A toolkit for weaving aspect oriented UML designs. In Proceedings of 1st ACM International Conference on Aspect Oriented Software Development, AOSD 2002, Enschede, The Netherlands, April 2002.

[15]
W.M. Ho, F. Pennaneac'h, and N. Plouzeau. Umlaut: A framework for weaving UML-based aspect-oriented designs. In Technology of object-oriented languages and systems (TOOLS Europe), volume 33, pages 324--334. IEEE Computer Society, June 2000.

[16]
M.A. Jackson. System Development. Prentice-Hall International, Series in Computer Science, 1985.

[17]
[PDF] C. Jard. Principles of distributed test synthesis based on true-concurrency models. In TESTCOM'2002 : Testing Communicating Systems, Berlin, Germany, March 2002.

[18]
J.-M. Jézéquel, D. Deveaux, and Y. LeTraon. Reliable objects: a lightweight approach applied to java. IEEE Software, 18(4):76--83, July/August 2001.

[19]
J.-M. Jézéquel and B. Meyer. Design by contract: The lessons of Ariane. Computer, 30(1):129--130, January 1997.

[20]
J.-M. Jézéquel, M. Train, and C. Mingins. Design Patterns and Contracts. Addison-Wesley, October 1999. ISBN 1-201-30959-9.

[21]
[PDF] Hanh Vu Le, Akif Kamel, Yves Le Traon, and Jean-Marc Jézéquel. Selecting an efficient OO integration testing strategy: An experimental comparison of actual strategies. In J. L. Knudsen, editor, Proceedings of ECOOP2001, volume 2072 of LNCS, pages 381--400, Budapest, Hungary, June 2001. Springer.

[22]
B. Meyer. Reusability: The Case for Object-Oriented Design. IEEE SOFTWARE, (3):50--64, March 1987.

[23]
B. Meyer. Applying "design by contract". IEEE Computer (Special Issue on Inheritance & Classification), 25(10):40--52, October 1992.

[24]
[PDF] F. Pennaneac'h, J.-M. Jézéquel, J. Malenfant, and G. Sunyé. UML reflections. In Proc. of Reflection 2001, September 2001.

[25]
[PDF] S. Pickin, C. Jard, T. Heuillard, J.-M. Jézéquel, and P. Desfray. A UML-integrated test description language for component testing. In Proceedings UML2001 wkshp: Practical UML-Based Rigorous Development Methods, GI-Edition - Lecture Notes in Informatics (LNI). Bonner Köllen Verlag, October 2001.

[26]
[PDF] S. Pickin, C. Jard, Y. Le Traon, T. Jéron, J.-M. Jézéquel, and A. Le Guennec. System test synthesis from UML models of distributed software. In D. Peled and M. Vardi, editors, Formal Techniques for Networked and Distributed Systems - FORTE 2002, LNCS, Houston, Texas, November 2002.

[27]
G. Sunyé, A. LeGuennec, and J.-M. Jézéquel. Using UML action semantics for model execution and transformation. Information Systems, Elsevier, 27(6):445--457, July 2002.

[28]
[PDF] G. Sunyé, A. Le Guennec, and J.-M. Jézéquel. Design pattern application in UML. In E. Bertino, editor, ECOOP'2000 proceedings, number 1850 in LNCS, pages 44--62. Springer Verlag, June 2000.

[29]
[PDF] Gerson Sunyé, François Pennaneac'h, Wai-Ming Ho, Alain Le Guennec, and Jean-Marc Jézéquel. Using UML Action Semantics for executable modeling and beyond. In Klaus R. Dittrich, Andreas Geppert, and Moira C. Norrie, editors, Advanced Information Systems Engineering --- CAiSE 2001, volume 2068 of LNCS, pages 433--447, Interlaken, Switzerland, June 2001. Springer.

[30]
Clemens Szyperski. Component Software: Beyond Object-Oriented Programming. ACM Press and Addison-Wesley, New York, N.Y., 1998.

[31]
Yves Le Traon, Thierry Jéron, Jean-Marc Jézéquel, and Pierre Morel. Efficient OO integration and regression testing. IEEE Trans. on Reliability, 49(1):12--25, March 2000.

[32]
Jos Warmer and Anneke Kleppe. The Object Constraint Language. Addison-Wesley, 1998.

[33]
T. Weis, N. Plouzeau, K. Geihs, A.-M. Sassen, and J.-M. Jézéquel. New Advances on CBSE, chapter QCCS: Quality Controlled Component-based Software development. Kluwer Academic Pusblishers, 2002.

[34]
Torben Weis, Christian Becker, Kurt Geihs, and Noël Plouzeau. An UML meta model for contract aware components. In Proceedings of UML 2001, volume 2185 of LNCS, pages 442--456. Springer Verlag, 2001.