Muhammad Rabee

Lydie Du Bousquet

Survey of source code metrics for evaluating testability of object oriented systems

Keywords: D.2.8 [Software Engineering]: Metrics software testing, software testability, testability evaluation, source-code based metrics, object oriented program analysis

Software testing is costly in terms of time and funds. Testability is a software characteristic that aims at producing systems easy to test. Several metrics have been proposed to identify the testability weaknesses. But it is sometimes difficult to be convinced that those metrics are really related with testability. This article is a critical survey of the source-code based metrics proposed in the literature for object-oriented software testability. It underlines the necessity to provide testability metrics that are proved to be intuitive and adequate for the testing cost prediction.

INTRODUCTION

Software testing is the process of executing a program with the intent of finding errors [START_REF] Myers | The Art Of Software Testing[END_REF]]. It has emerged as one of the major techniques to evaluate the implementation reliability. Unfortunately, testing is usually an expensive process. It can represent more than 40% of the total cost of the software development [START_REF] Salem | Prediction of software failures through logistic regression[END_REF]. For this reason, being able to characterize and to produce systems easy to test (i.e. testable systems) has become a preoccupation more and more important.

Testability denotes the ability of a system to be tested. Originally, testability was defined for hardware components. In this context, testability is often characterized through observability and controllability. To test a (hardware) component, one must be able to control its inputs and observe its outputs. When a component is embedded, the presence of other components can make impossible to directly access to its inputs and outputs. The additional effort required to build test for the em-bedded component partly depends on the architectural design. This is represented by the controllability and the observability.

For software systems, the notion of testability is becoming more and more popular because test is one of the most used way to valid a system and it is an (very) expensive process. Several studies were carried out to identify software testability characteristics. For instance, controllability and observability have been adapted for software programs, and several specific definitions of software testability were proposed. In [START_REF] Bache | Measures of testability as a basis for quality assurance[END_REF], testability is defined as the effort needed for testing. For Binder, testability is the relative ease and expense of revealing software faults [START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. Other definitions allow a quantitative evaluation of the testing effort. For IEEE, it is also considered as "the degree to which a system or component facilitates the establishment of test criteria and the performance of tests to determine whether those criteria have been met" [of [START_REF] Electrical | IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries[END_REF]. In [START_REF] Bertolino | On the use of testability measures for dependability assessment[END_REF], the testability is the probability that a test of the program on an input drawn from a specified probability distribution of the input is rejected, given a specified oracle and given that the program is faulty. In other words, it is the probability to observe an error at the next execution if there is a fault in the program.

From these definitions, lots of metrics have been proposed for software testability evaluation. These metrics can be evaluated at different moment in the development phase (i.e. model or code). They evaluate the complexity or the scope of testing, or both [START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. The scope evaluates how many test cases have to be produced. The complexity indicates how much it is difficult to produce a test. For some cases, lots of test cases may be required, but it could be easy to identify them; or few tests may be required but it could be very difficult to design them.

Most of these metrics focus on source code analysis. The main reason is that testability is often evaluated at this level in the industry. It is not done for improvement purposes: it is too late (and thus too expensive) to deeply modify the system and thus its testability. Evaluating testability at the source code level is mainly done for planning and resource management. Moreover, in industry, the source code is often the first artefact enough formal to make possible an automatic analysis.

For this reason, our article provides a survey of the proposed source-based testability metrics. We focus on for object-oriented systems. This work is an extension of the survey proposed by Binder in [START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. It presents more than 40 metrics which were declared in the literature to be testability relevant. The reason why there are so many metrics is that there are many strategies for test data selection/generation. Test data selection is based on the code or on the specification, at different phases (unit, integration and system testing), and with different purposes (among which achieving different coverage criteria). Moreover, there are different ways to understand what the cost of testing is. For instance, it can be the number of test cases, the size of test cases, the number of stubs, or the time spent to produce the tests.

Surprisingly, few metrics were really usable for testability evaluation. Some of them are hardly computable. Few are included in case tools. And few studies did formal or experimental validation that these metrics represent the scope or the • 3 complexity of the test.

In the following, we first present scope-oriented metrics (section 2). Sections 3, 4 and 5 focus on complexity metrics. Section 4 is dedicated to observability and controllability related metrics, and metrics presented in section 5 are related to the probability to reveal the next error. Section 6 focuses on works carried out for validating testability metrics. Section 7 concludes and draws some perspectives.

SCOPE-ORIENTED TESTABILITY METRICS

Methods

Methods may be considered separately during unit-testing. Several sets of criteria defined for non object-oriented programs can then be used. They are generally defined with respect to the control-flow graph or the data-flow graphs [START_REF] Myers | The Art Of Software Testing[END_REF][START_REF] Binder | Testing Object-Oriented Systems: Models, Patterns, and Tools[END_REF][START_REF] Gu | On testing of classes in object-oriented programs[END_REF][START_REF] Ntafos | A Comparison of Some Structural Testing Strategies[END_REF][START_REF] Frankl | An applicable family of data flow testing criteria[END_REF]. Classical control-flow graph criteria are statement, branch or decision, condition, MC/DC (Modified Condition/Decision Coverage), path. For data-flow graph, classical criteria are all-paths, all-du-paths, all-uses, all-c-uses, all-defs-uses, all-p-uses .

In [START_REF] Bache | Measures of testability as a basis for quality assurance[END_REF]] and [START_REF] Yeh | Software testability measurements derived from data flow analysis[END_REF]], two families of metrics have been proposed to evaluate the number of elements which has to be covered with respect to the control-flow and data-flow graph testing strategies : respectively allpaths, visit-each-loop-paths, simple paths, structured, branches, statements, and p-uses, defs, uses, d-u-paths and dominating paths. By definition, those metrics predict the scope of the associated testing strategies, i.e the minimum number of required tests to reach the coverage criteria.

Similarly, the Cyclomatic Complexity (CC), named also McCabe's complexity, [McCabe 1976;[START_REF]Design complexity measurement and testing[END_REF][START_REF] Watson | Structured testing: A testing methodology using the cyclomatic complexity metric[END_REF] is equal to the number of decision statements (or individual conditions) plus one. Mathematical analysis has shown that CC gives the recommended number of tests needed to test every decision point in a program [START_REF] Watson | Structured testing: A testing methodology using the cyclomatic complexity metric[END_REF]. Thus, it predicts the scope of the branch coverage testing strategy.

In [START_REF] Bainbridge | Defining testability metrics axiomatically[END_REF]], two flow graph metrics were defined axiomatically: Number of Trails metric which represents the number of unique simple paths through a flowgraph (path with no repeated nodes), and Mask [k=2] metric, which stands for "MAximal Set of K-Walks", where a k-walk is a walk through a flowgraph that visits no node of the flowgraph more than k times. Mask reflects a sequence of increasingly exhaustive loop-testing strategies. These two metrics measure the structural complexity of the code. One of the main benefits of defining these testability metrics axiomatically is that flowgraphs can be measured easily and efficiently with tools such as QUALMS [START_REF] Bainbridge | Defining testability metrics axiomatically[END_REF]].

Classes

The class is an essential concept in object oriented programming. A class groups attributes of an object and the operations on these attributes. Classes can also be considered during unit-testing.

Weighted Methods per Class (WMC) metric belongs to the Chidamber and Kemerer OO metrics suite [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. For a class C with methods M 1 , M 2 ...M n , let c 1 , c 2 , .., c n be the complexity of these methods.

W M C = i=n i=1 c i
Complexity was deliberately not defined in the original paper in order to allow a general application of this metric. If all method complexities are considered to be unity, then WMC 1 = n represents the number of methods. WMC 1 can be used to evaluate the number of test cases to achieve the method coverage [START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. This criterion is one of the simplest OO code-coverage coverage criteria (corresponding to function coverage). It requires each method to be executed at least once. A similar metric to WMC 1 is Number Of Methods (NOM) representing explicitly the number of methods of a class [START_REF] Binder | Design for testability in object-oriented systems[END_REF]].

When cyclomatic complexity is used as complexity measure to compute WMC (WMC CC ), it evaluates the number of the test cases required to test all the methods of the class to reach the decision coverage criteria.

Stubs

Stubs may be required during unit or integration testing. A stub is an extra routine that is provided by the tester, to imitate another part of the system.

The Fan Out (FOUT) of method A is the number of local flows from method A plus the number of data structures which A updates [START_REF] Henry | Software structure metrics based on information flow[END_REF]. In other words FOUT estimates the number of methods to be stubbed, to carry out a unit testing of method A Binder proposes to use Response For Class (RFC) metric to evaluate how many stubs has to be produced for unit testing at class level [START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. RFC is one of the Chidamber and Kemerer metrics suite [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. It is defined as the count of the methods defined in a class, in addition to the methods that are called directly by a method of this class. The number of methods to be stubbed corresponds to the number of calls of methods defined outside the class/subsystem under test. Since RFC counts also the number of methods defined within the class, RFC only provides an approximation of the number of methods to be stubbed, to carry out a unit testing of a class.

RF C = |RS| where RS = {M } ∪ ∀i {R i }
where {R i } is the set of methods called by method i, and {M } is a set of all methods in the class.

A class is coupled to another if one of them acts on the other, i.e. a method of a class uses methods or instance variables of the other. There are several definitions for the coupling between objects. One of them was proposed by Chidamber and Kemerer in [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]: Coupling Between Objects (CBO) of a class is the number of other classes to which it is coupled. CBO can be used to evaluate the number of classes to be stubbed, in order to carry out a unit testing Source code metrics for OO system testability • 5 of a class [START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. Eight different levels of coupling were ordered by Jones [ [START_REF] Page-Jones | The practical guide to structured systems design: 2nd edition[END_REF]. These levels influence the different quality factors of a unit such as reusability, maintainability, understandability...etc. An extension to these levels was made to become 12 levels [Jin and [START_REF] Offutt | Coupling-based criteria for integration testing[END_REF]]. These levels evaluate the software system designs complexity, and a relatioship between these levels and the number of faults [START_REF] Troy | Measuring the quality of structured designs[END_REF].

Class Fan Out (Class FOUT) represents the number of classes on which a given class depends [START_REF] Schroeder | A practical guide to object-oriented metrics[END_REF]]. This metric could be used to estimate the number of classes to be stubbed. When some strategies are used to schedule intelligently the test of the different classes in order to decrease the number of subs required to be produced, CBO or Class FOUT may be not relevant. In [START_REF] Kung | A test strategy for objectoriented programs[END_REF], authors show that 400 stubs would be required to test 122 classes individually (without any strategy) against 8 when an optimal test order is used. In [START_REF] Jungmayr | Identifying test-critical dependencies[END_REF]], S. Jungmayr proposes a testability metric in the context of static dependencies within objectoriented systems. A dependency of a component A on a component B exists if A requires B to compile or to function correctly. If A inherits from B or if it uses method(s) or attribute(s) of B then A depends on B. Dependency relation is transitive. A dependency graph may contain cycles. Such cycles can be broken by removing some dependencies. The set of removed dependencies are called Feedback Dependency Set.

Number of Stubs needed to Break Cycles (NSBC) evaluates the number of stubs required to be built with an integration testing strategy.

N SBC = |C F b | where C is the set of all components, C F b a feedback component set (C F b ⊂ D),
and D is the set of all dependencies. Finding a smallest feedback component set is NP-complete. To identify a small feedback component set S. Jungmayr proposed an algorithm based on both Tarjan and greedy algorithms [START_REF] Jungmayr | Identifying test-critical dependencies[END_REF]].

Inheritance

Inheritance is one of the main features of object-oriented programming paradigm.

Since it has been demonstrated that inheritance may be abused in many ways [START_REF] Armstrong | Uses and abuses of inheritance[END_REF], one may expect that several testing criteria would have been dedicated to inheritance testing. Surprisingly, few testing methods/criteria deal with inheritance [START_REF] Harrold | Incremental testing of object-oriented class structures[END_REF][START_REF] Perry | Adequate testing and object-oriented programming[END_REF][START_REF] Cheatham | Testing object-oriented software systems[END_REF][START_REF] Fiedler | Object-oriented unit testing[END_REF][START_REF] Chung | Integration object-oriented software testing and metrics[END_REF]]. Most of them restrict testing to validate changes in the inherited features (methods and attributes).

In [START_REF] Binder | Testing Object-Oriented Systems: Models, Patterns, and Tools[END_REF]], all inherited methods should be retested. In [START_REF] Harrold | Incremental testing of object-oriented class structures[END_REF][START_REF] Perry | Adequate testing and object-oriented programming[END_REF][START_REF] Cheatham | Testing object-oriented software systems[END_REF][START_REF] Fiedler | Object-oriented unit testing[END_REF]], it is suggested to re-test only (modified) inherited features (attributes or methods). Since, the number of inherited methods is considered to be generally proportional to the Depth of Inheritance Tree (DIT) [START_REF] Chidamber | A metrics suite for object oriented design[END_REF][START_REF] Binder | Design for testability in object-oriented systems[END_REF]], DIT is considered as a way to estimate the testing effort. But it does not provide an estimation of how many test cases have to be produced [START_REF] Shaheen | Relation between depth of inheritance tree and number of methods to test[END_REF]. A class with a small inheritance tree may have more inherited methods than a class with a large inheritance tree.

When a class inherits the same property of an ancestor via multiple paths in the hierarchy, there is repeated inheritance. Repeated inheritance is not allowed in several OO languages, such as Java, C#, or VB .Net. Overuse of repeated inheritance increases software error [START_REF] Chung | Integration object-oriented software testing and metrics[END_REF]]. That's why C.-M. Chung et al. propose a testing method to search for errors caused by the repeated inheritance. Each class concerned by repeated inheritance has to be tested in the context of its inheritance sub-trees. Authors introduce the notion of U RI (Unit Repeated Inheritance) as a specific inheritance sub-graph, where the number of nodes equals the number of edges (G = (V, E) where |V | = |E|). Repeated inheritance tree can be decomposed as a set of basic U RIs. For an inheritance tree, let t be the number of terminal classes (classes with no out-edges) and U i be the set of URI related to the terminal class i. The complexity of the repeated inheritance is defined as | ∪ t i=1 U i |. This complexity corresponds to the number of repeated inheritance sub-tree to be examined. Here again, it does not predict how many test cases have to be produced for each of them.

GENERAL COMPLEXITY METRICS

As we have seen previously, the Cyclomatic Complexity (CC) gives the recommended number of tests needed to test every decision point in a program [START_REF] Watson | Structured testing: A testing methodology using the cyclomatic complexity metric[END_REF]. Thus, it predicts the scope of the branch coverage testing strategy. It is also considered as an indication of the complexity of testing. Indeed, a method with a CC greater than 50 is considered to be untestable 1 . By extension, WMC CC could also be considered as an indication how difficult it is to test the class. However, it could be difficult to interpret: WMC CC indicates that a class A with 60 very simple methods (c i = 1) will require more testing than a class B with one method having a complexity of 50. When analyzing CC for each method, B will be more difficult to test (since a method with a complexity of 50 is supposed to be untestable) and 60 simple methods will require 60 simple tests. The authors in [START_REF] Michura | Metrics suite for class complexity[END_REF] Using the 4 metrics as opposed to WMC CC alone allows distinguishing between certain types of classes and therefore interprets the results accordingly.

Cohesion

Cohesion is an extension to the definition of similarity which was proposed by Bunge [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. The similarity σ() of two things is the intersection 1 http://www.sei.cmu.edu/str/descriptions/cyclomatic_body.html ACM Transactions on Computational Logic, Vol. , No. , 20.

Source code metrics for OO system testability • 7 of the sets of properties of the two things.

σ(X, Y ) = P (X) ∩ P (Y ) Cohesion has been considered to be a factor influence the cost of testing [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. Having lack of cohesion in a class C means that this class has many functionalities which are not related to each other, and as a result the class C will behave in less predictable way than a class of a fewer functionalities.

Lack of Cohesion of a Method (LCOM) is the 6th measure of the Chidamber and Kemerer metrics suite [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. LCOM measures the degree of similarity between the class's methods. The more methods share the same attributes, the larger is cohesion. LCOM metric has been redefined several times [START_REF] Briand | A unified framework for cohesion measurement in object-oriented systems[END_REF]]. We give here the definition of LCOM4, given by Hitz and Montazer. Let G x = (V, E) be a graph representing calls between class methods. V is the set of vertices, which represents the method names. E is the set of edges.

E = {(m, n) ∈ V × V |∃i ∈ I x : (m accesses i) ∧(n accesses i) ∧ (m calls n) ∧ (n calls m)
} where I x is the set of the attributes. LCOM 4 = |E| LCOM has been proposed as a testability metric by Binder in [START_REF] Binder | Design for testability in object-oriented systems[END_REF]], because high LCOM means more states that have to be tested to prove the absence of side effect among the methods. 1998] as the most cohesive form if each class's method has interaction with all of instance variables (special methods such as set and get are excluded).

Tight Class Cohesion

Polymorphism

It is an important feature in OO programming, defined as a characteristic of being able to have multiple forms. To test software that uses polymorphism, one should test all possible bindings of receiver classes and target methods at different call points. The authors in [START_REF] Lin | A new method for estimating the testability of polymorphism in class hierarchy[END_REF]] define a testability of polymorphism metric in inheritance hierarchy, based on the descendant paths. Also a polymorphism factor (PF or POF) was defined to represent the actual number of possible different polymorphic situations[e [START_REF] Abreu | Evaluating the impact of object-oriented design on software quality[END_REF]. A very high POF value (above 10%) will reduce the benefits of polymorphism.

Other metrics have been proposed in [START_REF] Binder | Design for testability in object-oriented systems[END_REF]] to measure the complexity as a result of the polymorphism such as percent of Dynamic calls (DYN), percent of non-over loaded calls (OVR), number of yo-yo paths visible to CUT (Bounce-C), and number of yo-yo paths in SUT (Bounce-S). Although these metrics have not been evaluated [START_REF] Binder | Design for testability in object-oriented systems[END_REF]], they were proposed as an indicator of the opportunities for faults.

Inheritance

Inheritance influences the scope of testing as previously indicated. Binder indicates that it also influences the complexity of testing. Like DIT, several other measures were proposed for inheritance tree complexity evaluation. Class Fan-In (FIN) is the number of parent classes of a subclass. It is applied only in multiple inheritance languages. A high Class FIN value increases the possibility of incorrect bindings [START_REF] Binder | Design for testability in object-oriented systems[END_REF]].

Number Of Children (NOC) is the number of classes that inherit directly from a class [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. It is the number of immediate subclasses subordinated to a class in the class hierarchy. It indicates how many derived classes will be affected by some modification in the parent class. So if a modification in the parent class affects the derived classes, it is required to retest the methods in the children. The higher NOC is, the more tests should be produced.

In [START_REF] Brito E Abreu | Object-oriented software engineering: Measuring and controlling the development process[END_REF], authors propose a set of measures called MOOD set, for object-oriented design quality evaluation. This set includes Method Inheritance Factor (MIF) and Attribute Inheritance Factor (AIF). They compute the number of the inherited methods/attributes in all classes divided by the number of available methods/attributes (inherited and defined) for all classes. Those factors are defined to evaluate the inheritance complexity of the whole system. They could be adapted to evaluate MIF and the AIF for each class (instead of for all classes together).

Encapsulation

Encapsulation is defined as "a software development technique that consists of isolating a system function or a set of data and operations on those data within a module and providing precise specifications for the module" [IEE 1990]. Using the encapsulation makes private data inaccessible directly during testing. An encapsulation factor (EF) metric for a class was proposed to measure the encapsulation level of a class. EF was defined as a function of two parameters privacy and unity, where privacy is based on the private data members (the data visibility),

• 9 and unity is the cohesion between the attributes and methods [START_REF] Saini | Enhancing mood metrics using encapsulation[END_REF].

COMPLEXITY METRICS RELATED TO OBSERVABILITY AND CONTROLLA-BILITY

Originally, testability was defined for hardware components. In this context, testability is often characterized through observability and controllability. To test a component, one must be able to control its inputs and observe its outputs. When a component is embedded, its controllability and observability can be decreased. This partly depends on the architectural design. Observability and controllability notions were adapted from hardware to software systems.

Domain Testability

Two Domain Testability metrics have been proposed by Freedman for non-OO software and based on these concepts [START_REF] Freedman | Testability of software components[END_REF]]. A procedure F is observable if distinct outputs are generated from distinct inputs, and an expression procedure F is controllable if the set of all evaluations of F covers all values in the range (codomain of F ). Observability and controllability extensions are the input/output variables required to achieve the definitions of observability and controllability.

The observability (Ob) and the controllability (Ct) according to the domain size of the added inputs/outputs.

Ob = log 2 (|ID 1 | * .... * |ID n |) Ct = log 2 (|OD 1 | * .... * |OD m |)
where ID i is the domain of the ith added input and OD j is the domain of the jth added output. A limit of these metrics is that the cardinality of certain types cannot be calculated (i.e. vector, array, object, etc). Moreover, one important feature in object-oriented paradigm is that objects preserve states. So attributes could be used as implicit input/output for a method. Therefore, the notion of observability an controllability extensions have to be adapted to OO features.

Observability and Controllability of Component

In [START_REF] Washizaki | A metrics suite for measuring reusability of software components[END_REF]], five metrics were proposed as reusability measure of software component. Two of them are related to observability and one to controllability. The Rate of Component Observability (RCO) represents the percentage of readable attributes in all fields implemented within the Façade class of a component. If the value of RCO is in [0.17, 0.42] (confidence interval) the height of the observability is supposed to be appropriate [START_REF] Washizaki | A metrics suite for measuring reusability of software components[END_REF]]. It is a variation of percent Public And Protected (PAP) defined in [START_REF] Binder | Design for testability in object-oriented systems[END_REF]].

RCO(c) = P r (c)/A(c) when(A(c) > 0), 0 otherwise where P r (c) is the number of readable properties in the component c, and A(c) is the number of fields in c's Façade class.

The Self-Completeness of Component's Return value (SCCr) is the percentage of business methods without any return value in all business methods implemented within a component c. It can be extended to non business methods and allows to detect the absence of return values, which decreases observability. However, observability is not limited to the existence of return values.

SCCr(c) = B v (c)/B(c) when(B(c) > 0), 1 otherwise
where B v (c) is the number of business methods without return value in c, and B(c) the number of all business methods in c.

The Self completeness of component's parameter (SCCp) is the percentage of business methods without any parameters in all business methods implemented within a component c. SCCp can be extended to other application layers (i.e. non business methods). Since it can be easier to test methods which have no input parameter (see Category and Partition [START_REF] Ntafos | On random and partition testing[END_REF]]), classes with high SCCp may be easier to test than some with low SCCp. One limit of SCCp is that it is independent from the difficulty to test methods with parameters. Let A be a class of several methods each of them has one parameter, (SCCp(A) = 0). Let B be a class of two methods, one with several methods and the other without any parameter, (SCCp(B) > 0). A is probably easier to test than B. Moreover SCCp does not capture the situation where methods have implicit parameters (attributes).

SCCp(c) = B p (c)/B(c) when(B(c) > 0), 1 otherwise
where B p is the number of business methods without parameters in c.

System Testability -STA

System Testability (STA) of an object-oriented software is defined as mathematical mean of all the objects testability obtained in the system [START_REF] Wang | On testable object-oriented programming[END_REF].

ST A = 1 n m j=1 OT A j
where OT A j is the object testability defined as the product of its test controllability and observability. Controllability of an object is the ability to control all the basic control structures within the object. Observability of an object is the ability to indicate the values of any variables within the path(s) sensitised by the current test case. STA is the average of its component testability values. This definition does not take into account the architecture of the system, which is quite unusual. It is usually expected that the architecture influences the observability and the controllability.

TESTABILITY METRICS RELATED TO ERROR LIKELIHOOD

Testing aims at finding errors [START_REF] Myers | The Art Of Software Testing[END_REF]]. The easier it is to find errors, the easier testing is. One definition of software testability given by A. Bertolino is "the probability that a test of the program on an input drawn from a specified probability distribution of the input is rejected, given a specified oracle and given that the program is faulty" [START_REF] Bertolino | On the use of testability measures for dependability assessment[END_REF]. In other words, it is the probability to observe an error at the next execution if there is a fault in the program. Several metrics are related to this definition.

• 11

Propagation Infection Execution -PIE

Propagation Infection Execution (PIE) analysis is a well-known metric proposed for testability. It has been proposed by Voas [START_REF] Voas | PIE: A dynamic Failure-Based Technique[END_REF][START_REF] Voas | Software Testability : the new Verification[END_REF]. PIE measure aims at computing the sensitivity of individual locations in a program. The sensitivity of a program location refers to the minimum likelihood that a fault at that location will produce incorrect output, under a specified input distribution. This measure has its origin in the RELAY model used for error detection [START_REF] Morell | A theory of fault-based testing[END_REF]]. It relies on the fact that for discovering a fault in a program, three conditions should be met. First the statement that contains the fault should be executed.

Secondly the state of the variable should be infected. And at last, it should be propagated to an output. Testability of a software statement T (s) = Re(s) * Ri(s) * Rp(s) where Re(s) is the probability of the statement execution, Ri(s) the probability of internal state infection and Rp(s) the probability of error propagation. PIE analysis determines the probability of each fault to be revealed. PIE original metric requires sophisticated calculations. It does not cover object-oriented features such as encapsulation, inheritance, polymorphism, etc.

In [START_REF] Lo | A preliminary testability model for object-oriented software[END_REF]], authors propose an adaptation of PIE analysis to compute the testability of a class t(C). Based on t(C), the testability of the class is derived with respect to different factors: cohesion, communication and inheritance.

Domain-Range Ratio -DRR and Visibility Component -VC

A simplification of sensitivity analysis has been proposed with the Domain-Range Ratio (DRR). DRR of a specification is the ratio between the cardinality of the domain to the cardinality of the range. DRR depends only on the number of values in the domain and the range, not on the relative probabilities that individual elements may appear in these sets [START_REF] Voas | Semantic Metrics for Software Testability[END_REF].

For a program, when the input domain is larger than the output domain, information about the internal states may not be communicated in the outputs. This information may have included evidence that internal states were incorrect. This loss suggest a lower testability. For instance, let us consider two functions F (x) = x mod 2 and G(x) = 2 * x. F has a domain on all R and a range on {0,1}. For such function, it is difficult to predict if the result is really the one that corresponds exactly to the given input: it has an unlimited and infinite set of inputs produce the same result (output). G has a domain on all R, and the range also on all R. Any two different inputs will produce two different outputs. Detecting an error for G(x) is easier than detecting an error on F (x). DRR evaluates how much an application is supposed to hide faults. It is a priori information, which can be considered as a rough approximation of testability. J. McGregor and S. Srinivas proposed an extension of DRR for object-oriented programs called Visibility Component (VC) [START_REF] Mcgregor | A measure of testing effort[END_REF]. VC is the cardinality of possible outputs (including the exceptions) divided by the cardinality of possible inputs. Two types of parameters for a method are considered: implicit and explicit ones. Like domain testability measures, cardinality of certain types cannot be calculated (i.e. vector, array, object, etc) by DRR or VC. This is major drawback makes impossible to use DRR or VC practically.

VALIDATION OF THE METRICS

In [START_REF] Kaner | Software engineering metrics: What do they measure and how do we know?[END_REF], C. Kaner and W.P. Bond question the construct validity of software engineering metrics, as several other authors before them. The general question is "how we know that we are measuring the attribute that we think we are measuring?" Same question can be asked for all the metrics presented here: how we know that those metrics really correspond to testability?

Several frameworks or methodologies were proposed in the literature for measurement and metrics validation [237 1993;[START_REF] Kitchenham | Towards a framework for software measurement validation[END_REF][START_REF] Sheppard | Formal specification of testability metrics in ieee p1522[END_REF][START_REF] Schneidewind | Methodology for validating software metrics[END_REF]Mendonça and Basili 2000;[START_REF] Harrison | An evaluation of the mood set of object-oriented software metrics[END_REF][START_REF] Weyuker | Evaluating software complexity measures[END_REF]]. Among them, the standard IEEE 1061 [237 1993] proposes a methodology to define metrics where the fifth step is Validation. Predictive metrics results are compared to the direct metrics results to determine whether the predictive metrics accurately measure their associated quality factor. Moreover, the standard lays out six validation criteria: correlation, tracking, consistency, predictability, discriminative power and reliability. Another draft standard for testability and diagnosability characteristics and metrics was developed by (D&MC), a subcommittee of IEEE [START_REF] Sheppard | Formal specification of testability metrics in ieee p1522[END_REF], the purpose of this standard was to provide formal and unambiguous definition of testability, where this definition should be independent of specific test, diagnosis process and system under test.

In [START_REF] Mouchawrab | A measurement framework for objectoriented software testability[END_REF], the authors introduced a generic measurement framework for OO software testability, which is based on a theory expressed as a set of operational hypotheses. They identified 20 hypotheses, 4 of these hypotheses are related to inheritance concept (i.e inherited features, operation rule...etc), which could be identified, more or less, as a result of the metric DIT. Other hypotheses are related to number of paths, coupling, dependency cycles, cohesion, complexity of pre/post conditions and invariants...etc. Although this framework is introduced for a high level design, the most of these hypotheses correspond to certain metrics presented in Table I. A future work could be done to associate formally these hypotheses to existed metrics.

A large amount of empirical studies have been carried out to establish the relation between OO metrics and fault-proneness of classes [START_REF] Basili | A validation of object-oriented design metrics as quality indicators[END_REF][START_REF] Briand | Investigating quality factors in object-oriented designs: An industrial case study[END_REF][START_REF] Tang | An empirical study on object-oriented metrics[END_REF][START_REF] Briand | Exploring the relationships between design measures and software quality in object-oriented systems[END_REF][START_REF] Briand | Replicated case studies for investigating quality factors in object-oriented designs[END_REF][START_REF] Emam | The confounding effect of class size on the validity of object-oriented metrics[END_REF][START_REF] Yu | Predicting fault-proneness using oo metrics: An industrial case study[END_REF][START_REF] Gyimóthy | Empirical validation of object-oriented metrics on open source software for fault prediction[END_REF][START_REF] Zhou | Empirical analysis of object-oriented design metrics for predicting high and low severity faults[END_REF]. Classical metrics such as WMC, LCOM, DIT, RFC, and CBO were considerate. But the studies were not correlated to testability. In [START_REF] Bruntink | An empirical study into class testability[END_REF], authors have evaluated the correlation between a set of OO source code metrics (among which DIT) and their capabilities to predict the effort needed for testing, expressed as dLOCC (Lines Of Code for Class) and dNOTC (Number of Test Cases). Somewhat surprisingly, DIT was not correlated to dNOTC. This was explained by the fact that inherited methods were probably not systematically re-tested. However, if all inherited methods are re-tested, it was expected that the number of test cases should increase with respect to DIT, as it has been shown after in [START_REF] Shaheen | Relation between depth of inheritance tree and number of methods to test[END_REF].

• 13

The validation of testability is a hard work, especially for the complexity metrics. The main difficulty relies on the fact that the effort to test is subjective and depends on the point of view. For instance, let us consider the Rate of Component Observability (RCO) [START_REF] Washizaki | A metrics suite for measuring reusability of software components[END_REF]] and the percent Public And Protected (PAP) [START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. They both represent the percentage of readable attributes, but are used differently with respect to the testability analysis: if a high RCO is supposed to ease testing because observability is increased [START_REF] Washizaki | A metrics suite for measuring reusability of software components[END_REF]], a high PAP is supposed to increase the difficulty of testing, because there are more opportunities for side effects. A challenge is thus to propose some definition(s) for what could be the effort to test.

The validation of scope metrics seems to be easier. By definition, scope metrics predict the number of tests to produce with respect to a testing approach (see Table I). To validate those metrics empirically, one can compare the expected number of test cases given by the metric and the effective one when applying the testing method. The possible differences can be due to the impossibility to reach the associated coverage criteria because of the infeasible execution paths for instance. If empirically, a scope metric prediction is very different from the effective number of test cases, it may be error-prone and thus should not be used.

CONCLUSION AND PERSPECTIVES

Since testing is expensive, predicting testability is important to organize test and/or to build easy-to-test systems. However, software testability is a concept difficult to capture and formalize. Lots of factors can effect testability [START_REF] Mouchawrab | A measurement framework for objectoriented software testability[END_REF][START_REF] Binder | Design for testability in object-oriented systems[END_REF]]. Lots of metrics have been proposed to predict testability, and especially at the source code level. Evaluating testability at the source-code level helps testers to detect parts of the system supposed to be difficult to test. It allows organizing and planning testing work

In this paper, we have collected more than 40 metrics, classified in scope and complexity testability metrics. Scope metrics predict how many tests cases are required by some testing strategies. Complexity metrics predict how difficult it will be to generate test cases. The complexity can be evaluated with respect to the structure of the system, the observability and the controllability attributes, or the probability to find the next error. Our work is an extension of the one done by Binder in [START_REF] Binder | Design for testability in object-oriented systems[END_REF]], which presents 21 metrics which can be evaluated on code.

It is really surprising to notice how few of these metrics are really usable. Less than one half of them are implemented in classical metrics tools (see Table II). Moreover testability metrics have been rarely validated neither formally nor empirically.

As a perspective for software testability, if we want to help practitioner to produce easy-to-test software programs, we should be able to offer a validated, meaningful and easy-to-understand set of metrics. From this survey, we are hardly convinced that a set of metrics is necessary, because (1) existing metrics are too ambitious by trying to obtain a large amount of information through a single number [START_REF] Michura | Metrics suite for class complexity[END_REF]] and (2) there are many different testing approaches and ways to evaluate the testing cost. [START_REF] Chidamber | A metrics suite for object oriented design[END_REF][START_REF] Binder | Design for testability in object-oriented systems[END_REF]] # of TC to achieve the method coverage yes 5 NOM [START_REF] Binder | Design for testability in object-oriented systems[END_REF]] # of TC to achieve the method coverage yes 6 WMC CC [START_REF] Chidamber | A metrics suite for object oriented design[END_REF][START_REF] Binder | Design for testability in object-oriented systems[END_REF]] # of TC to achieve the branch coverage at the class level yes 7 RFC [START_REF] Chidamber | A metrics suite for object oriented design[END_REF][START_REF] Binder | Design for testability in object-oriented systems[END_REF]] # of methods to be stubbed yes 8 CBO [START_REF] Chidamber | A metrics suite for object oriented design[END_REF][START_REF] Binder | Design for testability in object-oriented systems[END_REF]] # of classes to be stubbed (no integration strategy) yes 9 FOUT [START_REF] Henry | Software structure metrics based on information flow[END_REF] # of methods to be stubbed (no integration strategy) yes 10 NSBC [START_REF] Jungmayr | Identifying test-critical dependencies[END_REF] # of classes to be stubbed (with an integration strategy) no 11 DIT [START_REF] Chidamber | A metrics suite for object oriented design[END_REF][START_REF] Binder | Design for testability in object-oriented systems[END_REF] proportional to # of TC (when inheritance is re-tested) yes 12 Complexity of the repeated inheritance [START_REF] Chung | Integration object-oriented software testing and metrics[END_REF] # of repeated inheritance sub-tree to examine no Table I. Scope source-code testability-related metrics ACM Transactions on Computational Logic,Vol. ,No. ,20.

  proposes to use WMC CC with three other metrics: Mean Method Complexity (MMC), Standard Deviation Method Complexity (SDMC) and Number of Trivial Methods (NTM).

  (TCC) is the percentage of pairs of public methods of the class which are directly connected [Bieman and Kang 1995]. T CC = N DC/N P where N P = N * (N -1)/2 where: -N the number of methods -N P represents the number of possible connections -N DC number of indirect connections Loose Class Cohesion (LCC) considers the pairs connected directly or indirectly [Bieman and Kang 1995]. LCC = (N DC + N IC)/N P where N IC represents the number of indirect connections. Information CoHesion (ICH) was proposed by Lee et al. [Lee et al. 1995]. It is based on the information flow. It considers the cohesion of a method m implemented in a class c as the number of the invocations to other non-inherited methods of class c, weighted by the number of the parameters of the invoked methods. Cohesion between calling and called methods is stronger if the latter has more parameters more information is passed. Most Cohesive Component (MCC) is introduced in [Seok Chae and Rae Kwon

  graph metric suite [Bache and Mullerburg 1990] # of TC for control-flow graph coverage no 2 Data-flow graph metric suite [Yeh and Lin 1998] # of TC for data-flow graph coverage no 3 CC [McCabe 1976; J. and W. 1989; Watson and McCabe 1996] # of TC for branch coverage (decision point) yes 4 WMC 1

ACM Transactions on Computational Logic, Vol. , No. , 20, Pages 1-0??.

ACM Transactions on Computational Logic, Vol. , No. , 20.


Lydie Du Bousquet
email: lydie.du-bousquet@imag.fr

Mutation analysis to evaluate Lustre program specifications in the context of model-checking

Mutation analysis is a technique used to evaluate the adequacy of a test set with respect to a fault model. This approach is mainly used for unit testing evaluation. It is also used to produce new test data.

In this paper, we apply mutation analysis in order to evaluate the accuracy of a specification in the context of reactive program verification by model-checking.

Introduction

A primary purpose for testing is to detect software failures so that defects may be uncovered and corrected. It implies running the software item in predetermined conditions (input selection), analyzing the obtained results, and identifying errors [START_REF] Myers | The Art Of Software Testing[END_REF]. Testing can never completely establish the correctness of a program. For this reason, several methods have been proposed to increase confidence with respect to the test set provided, among which code coverage analysis or mutation analysis. Code coverage describes the degree to which the source code of a program has been tested. There are a number of coverage criteria, among which statement coverage, condition coverage, path coverage, def-use chains coverage [START_REF] Howden | Reliability of the Path Analysis Testing Strategy[END_REF][START_REF] Rapps | Selecting Software Test Data Using Data Flow Information[END_REF][START_REF] Ntafos | A Comparison of Some Structural Testing Strategies[END_REF].

Mutation analysis has been introduced by DeMillo in 1978 [START_REF] Demillo | Hints on test data selection: Help for the practicing programmer[END_REF]. Its main purpose is to evaluate the quality/adequacy of a test set with respect to a fault model. It is mainly used for unit testing evaluation. Since 1978, mutation analysis has been widespread, improved and evaluated. Is has been adapted for several programming languages [START_REF] Demillo | An extended overview of the mothra software testing environment[END_REF][START_REF] Agrawal | Design of Mutant Operators for the C Programming Language[END_REF][START_REF] Ma | Mujava: a mutation system for java[END_REF][START_REF] Offutt | Mutation Operators for Ada[END_REF]. Andrews et al. have demonstrated that mutants can provide a good indication of the fault detection ability of a test suite [START_REF] Andrews | Is mutation an appropriate tool for testing experiments?[END_REF]. Mutation analysis has also been applied to evaluate model-checking. To prove that a system satisfies a property, a model-checker explores the state space of the system, and check that a property is true in all the accessible states. If it is not the case, a counter-example is provided. The verification by model-checking is exhaustive in the sense that all accessible states are explored. However, the verification is limited by the properties to be checked: if the property set does not cover all behaviors of the system, some faults may remain. In order to evaluate how a set of properties fully verifies a model, T.-C. Lee and P.-A. Hsiung have proposed to use mutation analysis [START_REF] Lee | Mutation coverage estimation for model checking[END_REF]. The work have been carried out on timed automata. Six fault models were used and six associated mutation scores (called mutation coverage) were defined.

In the following, we focus on the validation of LUSTRE programs by model-checking. LUSTRE is one of the synchronous languages [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF][START_REF] Halbwachs | Programmation et Vérification des Systèmes Réactifs : le langage LUSTRE[END_REF]. During the last two decades, the growing interest in synchronous languages from large companies has initiated significant contributions to the practical validation problem of synchronous software [START_REF] Benveniste | The synchronous languages 12 years later[END_REF].

Section 2 presents mutation analysis for test and illustrate how mutation analysis can be used for modelchecking. Section 3 is dedicated to the presentation of LUS-TRE language and illustrates the use of mutation-analysis in the context of model-checking. In section 4, we analyze some examples and discuss of the approach. Section 5 concludes.

Mutation analysis

General principles for test set evaluation

Mutation analysis consists in introducing a small syntactic change in the source code of a program in order to produce a mutant [START_REF] Demillo | Hints on test data selection: Help for the practicing programmer[END_REF] (for instance, replacing one operator by another or altering the value of a constant). Then the mutant behavior is compared to the original program. If a difference can be observed, then the mutant is marked as killed. If the mutant has exactly the same observable behavior as the original program, it is equivalent with respect to the fault model.

The original aim of the mutation analysis is the evaluation of a test set. To do that, one has to produce all mutants corresponding to a predefined fault model. If the test set can kill all non-equivalent mutants, the test set is declared mutation-adequate. This means that the tests are able to discriminate the behaviors of the faulty programs from the original program.

Adequacy of the test set is evaluated thanks to the mutation score (also called adequacy score). The mutation score is the percentage of non-equivalent mutants that are killed. A test set is mutation-adequate if the mutation score is equals to one. Andrews et al. have demonstrated that mutation analysis can provide a good indication of the fault detection ability of a test suite [START_REF] Andrews | Is mutation an appropriate tool for testing experiments?[END_REF].

Mutation analysis is usually used to evaluate the adequacy of test set produced during unit testing. It has been adapted for several programming languages such as ADA, Java, C, VHDL, Petri-Nets, Final State Machine (FSM), Statecharts, and Estelle [START_REF] Wong | Mutation Testing for the New Century[END_REF][START_REF] Demillo | An extended overview of the mothra software testing environment[END_REF][START_REF] Offutt | Mutation Operators for Ada[END_REF][START_REF] Ma | Mujava: an automated class mutation system[END_REF][START_REF] Agrawal | Design of Mutant Operators for the C Programming Language[END_REF][START_REF] Nguyen | Mutation Testing Applied to Hardware: the Mutants Generation[END_REF][START_REF] Fabbri | Mutation Testing applied to Validate Specifications Based on Statecharts[END_REF][START_REF] Do | Mutation testing applied to estelle specifications[END_REF].

Using mutation for specification analysis

Classical mutation analysis compares the mutant outputs to the original program outputs to decide if a mutant is killed or not by a test set. This allows evaluating how the test-set is good to detect small syntactical changes. When a specification is available, it is also possible to compare the mutant output to this specification in order to check that the specification is acute enough to detect the same types of faults.

In the case of model-checking, the specification is composed of a set of properties. A model-checker verifies if the properties hold in all accessible states of the program. But, even if it is the case, some errors may remain: the properties may not cover all the program. For instant, demonstrating that the program satisfies the true property does not bring useful feedback on the program correctness.

Using mutation analysis to evaluate how much a set of properties covers the program was originally proposed by T.-C. Lee and P.-A. Hsiung [START_REF] Lee | Mutation coverage estimation for model checking[END_REF]. It was evaluated on timed automata. Hereafter is a short presentation of this work.

When a mutant does not satisfy the specification, it is said to be covered. The fraction of mutations detected by a specification determines its completeness. Some coverage metrics can be defined for the differents fault models. Its value is computed by the ratio of the number of covered mutations to the total number of non-equivalent mutations obtained with the chosen fault model.

In [START_REF] Lee | Mutation coverage estimation for model checking[END_REF], six fault models were used and six mutation coverage metrics were deduced. Each fault model characterizes a different aspect of a system state graph and identifies different characteristic of the properties (expressed in TCTL). The mutation fault models are (1) mutated initial (concerns the initial state), (2) delayed transition (to delay a mode transition), (3) shuttering mode (to add self-loop transition to a mode), (4) skipped mode (to make a non-initial mode unreachable), [START_REF] Demillo | An extended overview of the mothra software testing environment[END_REF] removed transition (deletes a transition from the state graphe), (6) mutated invariant (invariant of mode is changed).

In the following, we are going to use the same vocabulary than traditional mutation analysis. We will say that a mutant is killed by the specification if the mutant does not satisfy the specification (instead of covered). By extension, the mutation-score of a specification is the number of non-equivalent mutants that does not satisfy the specification (instead of coverage metric). Thus, if all mutants are killed by the specification, we can say that the specification is mutation-adequate.

LUSTRE program: validation and verification

3.1 Brief presentation of LUSTRE language LUSTRE [START_REF] Halbwachs | The Synchronous Data Flow Programming Language LUSTRE[END_REF][START_REF] Halbwachs | Programmation et Vérification des Systèmes Réactifs : le langage LUSTRE[END_REF] is a synchronous declarative data flow language. The synchronous hypothesis considers the program reaction time to be negligible with respect to the reaction time of its environment.

The synchronous data flow approach consists in presenting a temporal dimension into the data flow model. A flow or stream (basic entity) includes two parts: a sequence of values of a given type, and a clock representing a sequence of instants (on the discrete temporal scale).

A LUSTRE description, structured in a network of nodes, represents the relations between the inputs and the outputs of a system. These relations are expressed by means of operators (nodes or basic operators), of intermediate variables and of constants.

A node is defined by a set of equations. Any local variable or output must be defined by one and only one equation. The equations can be written in any order without changing the behaviors of the program.

LUSTRE offers usual arithmetic, boolean and conditional operators and two specific operators: pre, the "previous" operator, and -> the followed-by operator 1 . Fig. 1 gives a LUSTRE program implementing a simple stopwatch node chrono (raz : bool) returns (n : int); let n = 0 -> if raz then 0 else (pre(n)+1); tel;

t 0 t 1 t 2 t 3 t 4 t 5 raz 0 0 0 1 1 0 n 0 1 2 0 0 1 Figure 2.
An execution trace for chrono

Running Example: a temperature control system

Let us consider the following example of a temperature control system given in [START_REF] Atlee | State-Based Model Checking of Event-Driven System Requirements[END_REF]. This system is composed of one heater, one air conditioner, some temperature sensors and one ON/OFF switch. The program has four inputs:

• Running is a signal active when the ON/OFF switch of the device is to the ON position.

• BelowDesiredTemp, TempOk and AboveDesiredTemp are signals issued by the temperature sensors. They are active when the current temperature is respectively lower, equal or higher than the desired temperature.

The program has four outputs, which are mutually exclusive signals. They set the current mode of the system:

• OFF, meaning that the system is turned off.

• INACTIVE, meaning that the system is on but neither the heater nor the air conditioner is on.

• HEAT and AC, meaning that either the heater or the air conditioner, respectively, is on and controlling the temperature.

The assumption made here on the environment is that exactly one of the three inputs BelowDesiredTemp, TempOK and AboveDesiredTemp is true at the same time. Another one is that the temperature cannot raise (resp. fall) from a value below (resp. above) the desired temperature to a value above (resp. below) it without reaching in the meantime the desired temperature.

It is possible to express the environment assertions and the expected safety properties of a system in LUSTRE, since it is also considered a temporal logic of the past. For the environment properties, the two assertions can be formalized as where # is a built-in logical operator ensuring that no more than one of the boolean expressions in its argument list is true at the same time. once from to(A,B,C) is a user-defined temporal operator returning a true value when the event A has occurred at least once between two subsequent occurrences of B and C. Similarly always from to(A,B,C) returns a true value when the event A continuously occurs between two subsequent occurrences of B and C. The definition of such temporal operators in LUSTRE can be found in [START_REF] Halbwachs | Programming and Verifying Real-Time Systems by Means of the Synchronous Data-Flow Programming Language LUSTRE[END_REF]. A LUSTRE program for controlling that system is presented in [START_REF] Lakehal | Models for synchronous software testing[END_REF] and illustrated Fig 3.

Lesar, a model-checker for Lustre

LESAR is a model-checker for LUSTRE. Given a program P and a safety property S, LESAR checks that S is true in all states of the program P under some assumptions (expressed by an assertion A). The problem thus reduces to proving that the only boolean output of P is always true during any execution of the program which permanently satisfies the assertion A. The verification is performed on a finite state abstraction of the program. Any numerical computation is deliberately ignored, and boolean expressions depending on numerical variables (e.g., comparisons) are considered nondeterministic.

LESAR takes a verification program as input (see Fig. 4). It is written in LUSTRE. It has the same inputs than the original program and only one boolean output. This output is equal to the safety property to be proved. The assert operator allows to restrict the verification to the inputs satisfying the environment constraints.

For instance, for the temperature control system, one can express the following safety properties: • The system is off only when the appliance is off.

implies(OFF, not Runnning)

• The system is inactive only if the appliance is on and if the current temperature is equal to the desired temperature. implies(INACTIVE, Runnning and TempOk)

• The system is heating only if the appliance is on and if the current temperature is below than the desired temperature. implies(OFF, Runnning and BelowDesiredTemp)

• The system is cooling only if the appliance is on and if the current temperature is lower than the desired temperature. implies(OFF, Runnning and AboveDesiredTemp)

LESAR can prove that the program Clim satisfies the given properties, in less than a second. But it is difficult to determine if the properties describes all the program behaviors or only a part of them.

Mutation analysis for LUSTRE

Alien-V2 is a tool we built for mutating LUSTRE nodes [START_REF] Bousquet | Mutation analysis for lustre programs: Fault model description and validation[END_REF]. This tool was produced within collaboration between LSR (team VASCO) and LCIS (team VALSYS). The multilanguage mutant generator for VHDL and C developed by LCIS (Alien) [START_REF] Nguyen | Mutation Testing Applied to Hardware: the Mutants Generation[END_REF] was extended to LUSTRE.

Alien-V has a mutation operator table as input. It is possible to adapt it to define specific mutation operators. Arithmetic/Logical/Relational Operator Replacement are defined by default. CSR (Constant for Scalar variable Replacement) and SCR (Scalar for Constant Replacement) have to be manually parameterized for each program.

LESAR can be used to detect equivalent mutants produced for a LUSTRE program. The verification program should carry out the comparison of the mutant and original program. When some environment assertions are provided with the original program, it is possible to consider the mutant-equivalency with respect to the environment description (using the assert operator) or without considering environment (unconditional equivalence).

For the program Clim, Alien-V produces 193 mutants. Clim uses 8 boolean variables (input or output). There are 17 "instances" of these variables inside the program where a changed can be done 3 . Each of them can be replaced by the 7 other variables, the true value, the false value and the negation of the variable (170 mutants). There are also 11 instances of a logical operator, which can be replaced by two other operators (22 mutants). Among those 193 mutants, 12 of them are syntactically incorrect. 4 mutants are equivalent without considering environment (unconditional equivalence) and 18 of them are equivalent with respect to the environment description.

As presented previously, the Clim specification is composed of 4 safety properties. Clim satisfies those properties under the environment constraints. We use the LESAR model-checker in order to check if the 163 non-equivalent mutants satisfy or not those properties. The verification program proposed Fig. 4 was used with the mutated implementations of Clim. 86 non-equivalent mutants satisfy the 4 safety properties under the environment constraints. This means that those mutants were not killed by the specification. The mutation score of the specification is thus 86/163=0.52.

In fact, the specification provided for the temperature control system is composed two other properties: if the appliance is on, as soon as the current temperature goes below (resp. above) the expected temperature, the system will start heating (resp. cooling). These properties are expressed in LUSTRE with respect to the previous step.

• implies(pre (Runnning and BelowDesiredTemp),HEAT)

• implies(pre (Runnning and AboveDesiredTemp), AC or pre AC)

If the mutation analysis is carried out against the complete specification, we obtain that all mutants are killed (they do not satisfy the properties). The mutation score of the complete specification is thus 1.

Case studies and discussion

Case studies

We have applied this approach on three examples: a subway U-turn section (UMS) [START_REF] Halbwachs | Programming and Verifying Real-Time Systems by Means of the Synchronous Data-Flow Programming Language LUSTRE[END_REF], a water supplying system (Supplying) [START_REF] Duc | Conception et modélisation objet des systèmes temps réel[END_REF], a mouse controller (Mouse) [START_REF] Bousquet | Expressing and implementing operational profiles for reactive software validation[END_REF]. The results are detailed hereafter and a summary is presented tables 1 and 2. For this 3 simple programs, the specification mutation score is low (below 0.5).

The Mouse program is an interface between a 3-button device and an application program. It transforms "physical clicks" on a mouse into "logical clicks" usable by the application program. A physical click corresponds to the action of clicking one button. A logical click is defined by a couple of values. A logical click is simple, double or triple. A triple click can occur only during a specified time lap. A triple click results from three clicks on the same button in a row in less than T ticks. A double (resp. simple) click is obtained when the same button is pressed twice (resp. once) in a row in less than T ticks. A triple click has a priority over simple and double clicks. A double click has a priority over a simple click.

The inputs of the conversion program are the button numbers. The outputs of the conversion program are couples of values the click type and the button number. Three safety properties were expressed, stating that (1) a logical click can only be simple, double or triple. ( 2) a logical click correspond to only one button number and (3) a type of logical clic is always associated to a button number (and respectively). The environment assertions state only that it is not possible to press two (physical) buttons simultaneously.

The property set is incomplete since the time lap is not specified. Moreover, the output values are not specified with respect to the input ones. The reason why is that Lesar carry out an abstraction an integer value is used to compute the time elapsed between a physical and the associated logical click. It then provides "false" counter-examples due to this abstraction for any properties dealing with the computation of the time lap. This has been confirmed by the mutation analysis. 492 mutants were produced with ALien-V, among which 478 are not equivalent. Only 214 are killed by the properties, which represents a mutation score of 0.44.

The UMS program controls the U-turn section of a subway. A U-turn section allows trains to switch from one track to the other, and to go back in the opposite direction. A U-turn section is composed of three tracks A, B, C, and a switch S. Assuming the entering track is A and the exiting track is C, trains switching from A to C must first wait for S to connect A with B, then transit on B and wait again for S to connect B with C before going back on C. The UMS Lustre program has 5 inputs and 4 outputs. It is a combinatorial node, composed of 6 equations. The specification is composed of 4 safety properties and 8 environment assertions. The code of the verification program is preproduced Fig. 5. Alien-V produces 174 syntactically correct mutants. 171 of them are not-equivalent (under the environment assertions). Among these, 80 are killed by the properties under the environment assertions. This means that the mutation score is 0.46. This result may appear surprising: the program is very simple, the environment assertions are quite restrictive and all outputs are expressed in the properties. However, properties mostly state what should not be done (specification of some incorrect outputs) but do not specify what should be done (specification of the required behavior). For instance, a system that does "nothing" is safe. That is the case for 60 mutants that have at least one output always false and satisfy the properties. In this case, the property have been chosen to allow implementation freedom.

The water supplying system

The water supplying system is composed of a artesian well, a tank, and two pumps. The second pump is used to distribute water in the building. It is started when at least one tap is turned on. It is stopped when all taps are turned off. The first pump is used to fill the tank when the water level in the tank is too low. Both pumps are equipped with temperature sensor. If a rise in temperature is observed, pump should be stopped. An information board, inside the building, is composed of 4 warming lamps. A green lamp indicates that the system is OK. Two red lamps indicate if the first or the second pump are off. A last red lamp indicates if the tank low level is reached.

The system has to control the pumps and the information broad. Its inputs consist of 9 booleans: the 3 levels of the tanks, the temperature sensors of the two pumps the manual commands for re-activation the sensor to detect dry pumping and an input indicates if one tap is open. The outputs consist of 6 booleans: the commands for the 2 pumps and the 4 lights. There are 4 environment assertions indicating the initial state of the pump and the evolution of the water level. 4 safety properties were defined.

Alien-V produces 285 mutants syntactically correct. 226 mutants were not equivalent. Among these, only 52 kill the specification (the mutation score is 0.23). Two situations can be observed. First, some parts of the system are not specified. For instance, 60 non-equivalent mutants deal with the values of the 4 lights. None of them are killed since the safety properties are not concerned by the values of the light. Second, some parts of the system (the control of the pumps) are specified as it is done for the U-Turn: incorrect behaviors are specified but not the correct ones. Here again, this choice was done to allow implementation freedom.

Discussions

The application of the approach proposed by [START_REF] Lee | Mutation coverage estimation for model checking[END_REF] on these 4 examples help us to identify some elements missing in the different specifications. Several types of situations were observed. Some properties were not described, because 1. they were simply forgotten (possibly for the demonstration purposes), 2. they concerned outputs that were judged to be noncritical, 3. they are not provable by the model-checker (here, they concerned liveness and abstraction on the integers), 4. some implementation freedom was left.

In order to detect situations such as the first one, it is interesting to apply mutation analysis. Admittedly, it is expensive but it provides a real feedback.

About the second point, not specifying non-critical outputs is often done on purpose. If it is the case, one may want to drop mutation analysis for those parts. In order to do that, we would like to couple mutation analysis with a "slicing" approach. The idea would be to extract only critical parts (here equations) of the application out of the total code and restrict the mutation analysis on these parts. Typically, for the Supplying example, the critical parts deal with the control of the pumps. Being able to provide mutations on the associated equations would result to study less mutants (3/4 in this case).

For the third point, if properties that can not be proved are required, test can be applied. The mutation analysis can thus be applied at two steps. It will first help to identify the lacks of the specification. It will then help to evaluate the relevance of the test data. The advantage here is that the same mutants are used.

Finally, for the fourth point, when the specification allows some implementation freedom, the mutation analysis will provide possibly a low mutation score. The user may try to increase the mutation score by completing the specification in a wrong way, for instance, by duplicating the code. This could have been done for the U-Turn example, since the code is very "simple".

Conclusion and perspectives

Mutation analysis has been proposed to evaluate the adequacy of a test set with respect to a fault model. It has been proposed also to evaluate how much a specification "covers" a program in the context of verification by modelchecking. The original work concerned timed automata specified in TCTL. Here, we have applied the same idea for Lustre programs. We have studied 4 programs and their specification published in the litterature. The specifications are safety properties also expressed in LUSTRE (which can be considered as a temporal logic of the past) and proved with the LESAR model-checker.

This work allows us to drive the following conclusion. Yes, mutation analysis help to discover some lack in the specification: for three of the studied programs the mutation score of the specification is very low, due to missing properties. But, safety properties are sometime introduced with the idea to let some implementation freedom (several implementations can be accepted). In this situation, mutation score should be used carefully. It could be easy to add properties that are a copy of the code, just to increase the mutation score. Such a practice would improve superficially the confidence within the software, without improving its quality.

Our perspective of this work is to couple the mutation analysis with a slicing approach, in order to restrict the analysis only on parts that are concerned with the properties. This would decrease the cost of the mutation analysis (by reducing the time spent in the analysis) and provide a more precise verdict about the specification relevance. Moreover, it will reduce the risk to artificially over-specified noncritical parts.

Figure 1 .

 1 Figure 1. A simple LUSTRE program

2 .

 2 1. (AboveDesiredTemp or BelowDesiredTemp or Tem-pOK) and #(AboveDesiredTemp, BelowDesiredTemp, TempOK) once from to(TempOK, BelowDesiredTemp, Above-DesiredTemp) and once from to(TempOK, AboveDesiredTemp, BelowDesiredTemp)

Figure 4 .

 4 Figure 4. A verification program for the temperature control system

Figure 5 .

 5 Figure 5. The U-turn system: assertions, code and safety properties together

Table 1 . Quantitative elements about the pro- grams

 1

	Program	# node	# input	# output	# env.	# safety
	Conditioner	1	4	4	4	6
	UMS	1	5	4	8	4
	Supplying	8	9	6	4	4
	Mouse	1	3	6	1	3
	Program	Conditioner	UMS Mouse	Supplying
	# mutants		181	174	492	285
	# eqv (under env. assertions)	18	3	14	59
	# killed		163	80	214	52
	Score		1	0.46	0.44	0.23

Table 2 . Quantitative elements about the mu- tants

 2

Let E and F be two expressions of the same type denoting the sequences (e 0 , e 1 , ..., en...) and (f 0 , f 1 , ..., fn, ...); pre(E) denotes the sequence (nil, e 0 , e 1 , ..., e n-1 ...) where nil is an undefined value. E -> F denotes the sequence (e 0 , f 1 , ..., fn...).

Lustre also means "5 years long" in French.

A mutation of the variables on the left side of the equal signe is not done since it produce syntaxtical incorrect programs.


Cyril Labbé

Franc ¸ois Portet

Towards an Abstractive Opinion Summarisation of Multiple Reviews in the Tourism Domain

Keywords: Review summarisation, Opinion mining, Natural language generation

Since the arrival of Web 2.0, there is an increasing amount of on-line Reviews and Ratings about diverse products or services. The reviews contain general comments as well as highly personal elements or opinions about the customers' experience with the product. Other customers or companies are facing the problem of extracting the relevant information from this mass of reviews. In this paper, we present a comparative study of three different summarisation techniques for reviews analysis. From this study, we propose a general architecture which relies on a customisable abstractive summarisation approach making use of domain knowledge and temporal analysis. The paper ends by identifying research directions for improving the efficiency of review summarisation methods.

Introduction

Since the arrival of Web 2.0, costumers of any kind of products or services produce a large amount of on-line Reviews, almost only present as text, and Ratings as ordinal variable. While these reviews have largely contributed to the success of the e-commerce, the problem for a costumer to construct her/his own opinion and to make an informed decision is to make sense of this mass of reviews that contains not only general comments about product features but also highly idiosyncratic information such as opinions or sentiments. Reviews are not only useful for potential costumers but also represent precious information for companies about their own products. A major challenge for society is to make possible an automatic analysis of sets of reviews in order to produce a coherent summary that can be quickly and easily assimilated by humans.

In this paper, we study the problem of review summarisation in the accommodation domain. Automatic summarisation is the process of drawing out the most relevant information from a source to produce a condensed version sometimes biased towards particular users and tasks. Summarisation approaches are generally categorised as: extractive when content reduction is addressed by selection or abstractive when compression is done by generalisation of what is relevant in the source [START_REF]Advances in Automatic Text Summarization[END_REF]. While summarisation of technical structured contents is a well implanted technique in industry, summarisation of reviews is a much more recent trend. In this context, the task must face poorly structured contents from a large number of authors (e.g., age, sex, literacy level, etc.) full of subjective matters expressed via opinion, metaphor, or cultural references. The excerpts (table 1) from an existing database illustrate the variety of reviews for a same hotel.

The hotel was well serviced by friendly staff. Great bathroom with a flat floor shower...... no bath! Mini kitchenette was really handy, great not to have to use the vanity basin as a kitchen sink! While there are no retail shops close by, there is a convenience store next door.Two food courts that have huge variety and restaurants in the Casino to suit any taste & wallet.... are less than 10 min walk away.

The staff from Front Desk to cleaners could not be faulted... friendly and helpful, making us feel like welcome guests.

Booked by work for it's location this was a rather expensive XXX YYY stay. Wifi was provided by an external provider with very expensive rates. This is not great for people on business. The room was nothing special with a standard shower and mediocre bed. Clean but pretty bog standard. Nothing to rave about and equally nothing terrible to report. In this context, sentiment analysis must play a major role when summarising reviews. Sentiment analysis task can be decomposed in several steps. As a first step, analysis of small texts (phrases, tweets, SMS messages) gives the trend of the conveyed sentiment (commonly refereed to as polarity) generally classified as: positive, negative or neutral. Further steps are needed to summarise the global sentiments. The main difficulty is to give a fair and non-biased picture of the global feeling emerging from individual sentiments. This global picture can consist in a set of numbers (tables, charts, graph. . . ) or in a short text that gives the global sentiment in a concise way.

In this study, we propose to compare three approaches to summarisation in order to draw out their current limitations and advantages for this task. This comparison is described in Section 3. Based on this comparison, we propose in Section 4 a new architecture for review summarisation which relies on an abstractive approach making use of domain knowledge and temporal analysis. We conclude the paper with an description of research directions for improving the efficiency of review summarisation methods.

Related Research

Summarising opinions reviews into texts can be done in several ways. The most straightforward being the use of a general summariser. Other approaches proposed to produce a tailored "voice summary" of a set of the most extreme restaurants reviews [START_REF] Mahajan | Summarization of multiple user reviews in the restaurant domain[END_REF]. In the tailored-summariser ReSum [START_REF] Kokkoras | Summarization of multiple, metadata rich, product reviews[END_REF] the target are reviews on products sold on-line. Re-Sum outputs two summaries, one for the positive reviews, one for the negative reviews. These summaries are composed of sentences extracted from the positive (or negative) reviews according to a strategy involving redundancy elimination and domain-feature depend criteria such as technical level or Time of Ownership. Here and in the following, features refer to domain characteristics. For instance, in the accommodation domain, quality of beds or cleanness of the room are domain features (or aspects). While these approaches provide interesting summaries they do not consider opinions in a systematic way, hence the need for a sentiment analysis module in the summarisation framework.

Sentiment summarisation involves several steps (for a detailed review the reader is referred to [START_REF] Tang | A survey on sentiment detection of reviews[END_REF]). The first step aims at determining the sentiment express by each individual reviews. Representative examples of this step are [START_REF] Martín-Wanton | Opinion polarity detection -using word sense disambiguation to determine the polarity of opinions[END_REF] and [START_REF] Salvetti | Automatic opinion polarity classification of movie reviews[END_REF]. [START_REF] Martín-Wanton | Opinion polarity detection -using word sense disambiguation to determine the polarity of opinions[END_REF] proposes a method for determining opinion polarity using WordNet, SentiWordNet and the General Inquirer (to detect polarity shifter). In [START_REF] Salvetti | Automatic opinion polarity classification of movie reviews[END_REF], The probability P (+/rv) (resp P (-/rv)) of a movie review rv of being a review of positive (resp. negative) polarity is estimated through the use of Naive Bayes and Markov Model techniques. Each individual review is then scored and this score is used to retrieve the most extreme reviews. However, the method does not capture the global sentiment emerging from the reviews.

The global sentiment of a set of reviews can be abridged as numbers or charts. For example, [START_REF] Popescu | Extracting product features and opinions from reviews[END_REF] summarises hotel reviews through automatic features extractions and polarity measure. For each review, if a feature is identified, its polarity is computed. The global sentiment for each feature is then computed. In [START_REF] Rahayu | Web services for analysing and summarising online opinions and reviews[END_REF], reviews are summarised in a similar manner but using a domain ontology for features identification. An important advantages of this approach is that it proposes to highlight positive (reps. negative) comments within negative (resp. positive) reviews arguing that opinions about features are more interesting when extracted from a review containing contrasted opinions.

The next section gives a more detailed focus on "pro" and "cons" associated to three methods for the summarisation of the global sentiment emerging from hotel reviews.

Comparative studies of three approaches

Three different approaches used to summarise the overall opinion emerging from a set of hotel reviews are presented. The reviews were all collected from the Tripadvisor website. The first experiment concerns the use of a general summariser. The second one shows results obtained when sentences extraction is guided by domain features. The third one consists in the Reviews and Ratings (RnR) system described in [START_REF] Rahayu | Web services for analysing and summarising online opinions and reviews[END_REF].

Open Text Summarizer

Open Text Summarizer (OTS) is an open source tool for summarising texts of any domain [START_REF] Rotem | Open text summarizer (ots)[END_REF]. Its content selection is based on the TF-IDF measure with some re-weighting based on the structure of the document (e.g., title and paragraph). The experiment with OTS consisted in feeding it with a whole set of reviews about the same hotel and checking the output. Figure 2 shows an output when OTS was applied with a 1% compression ratio. It can be noticed that no relevant information about the hotel appears before the fourth sentences. As with any extractive summariser, some referring expressions are impossible to understand (e.g.,"This appeared from the unlocked. . . "). Moreover, there is no way for the summariser to filter out irrelevant information for the decision making task such as with information about booking experience (e.g., "booking was done at very last minute. . . ", "I did a lot of research. . . "). This is due to the high frequency of personal booking experiences that biased the system towards this kind of irrelevant information. It appears from this short example, that purely frequency-based content selection without the involvement of some domain and/or task knowledge is unpromising.

Hotel booking was done at very last minute by the friendly staff at the International Airport. I did a lot of research in advance -most of it on Tripadvisor -and it was ranked very highly. This appeared from the unlocked office behind reception -I was told this was more secure -I wondered but all was ok. Location is what this hotel has going for it -you're on holidays, you want to be in the centre of things, near good restaurants [...] Fig. 2. Beginning of the output of OTS at 1% compression rate (2500 to 17 sentences).

Features-based Selection Extraction

In this approach, the main idea is to extract relevant information related to a particular word. In [START_REF] Labbé | How to measure the meanings of words? Amour in Corneille's work[END_REF], an approach to better understand the particular meaning associated to a word in the mind of a particular author was proposed. We proposed to use this technique to capture the global opinion given by a set of users on a particular domain feature. Figure 3 shows the outline of the proposed method. Let denote by f a word type representing a particular feature under study (BED for example). The set of sentences containing f is a sub-corpus denoted by U f and is called the lexical universe of f . For each word type i of the global corpus (C) under consideration two frequencies can be observed:

p U f (i) is the observed frequency of type i in U f the lexical universe of f . -p C (i) is the frequency of type i in the whole corpus.

Using the hypergeometric law, an expected value E U f (i) for p U f (i) can be computed. Given a confidence level (5% or 1%) it is then possible to tell if the observed value p

U f (i) is too far from E U f (i), either because p U f (i) << E U f (i) or because p U f (i) >> E U f (i).
So each word type i of the whole corpus C can be classified, with regards to f as being:

neutral, this is a set of words that do not have a special interaction with f . There frequency in the lexical universe of f is acceptable with regards to their frequency in the whole corpus; attracted (if p U f (i) >> E U f (i)), this is the set of words that are over-represented in the lexical universe of f . They can be seen as being attracted by f and it can be inferred that they are characterizing the global opinion on f ; repulsed (if p U f (i) << E U f (i)), this is the set of words that are under-represented in the lexical universe of f . They can be seen as being repulsed by f and it can be inferred that they are not reflecting the global opinion on f ;

Given a feature f it is then possible to build two sets. U + f the set of words that mostly characterize f and U - f the set of words that are mostly repulsed by f . These sets are used to score each sentences of the whole corpus C so to select the set of sentences that characterize the best the opinion associated to a particular feature.

Figure 4 shows the most relevant sentences for the feature BED. It can be noticed that the most relevant and condense sentences are the best rated. However, there is a high redundancy in this list and contrasted reviews are not fetched by the method. 0.647 A comfortable double bed, couch and coffee table, plus a small desk with two chairs. 0.615 The room was spacious with a queen sized bed and a sofa bed. 0.412 The hotel rooms were a good size with a double bed and a fould out sofa bed. 0.378 Queen sized bed ( with small side shelfs), little couch and coffee table for persons, a basic table with chairs, a flat screen tv, and a dresser with a couple of drawers. 0.370 The rooms were quite large -we had a queen room which consisted of a queen bed, small lounge, small table and chairs and kitchenette. 0.364 The room was quite large with a couch, desk and amp ; coffee table as well as the queen size bed. . . .

RnR system

In [START_REF] Rahayu | Web services for analysing and summarising online opinions and reviews[END_REF], an RnR system1 for extracting rationale from on-line reviews/ratings is presented. The system captures and summarises the key rationale for positive and negative opinions expressed in a corpus of reviews and highlights the negative features among positive reviews and vice versa. One of the main contribution of the work is the techniques that have been designed to leverage support metric in conjunction with a domain ontology. This results in improved computational overheads associated with sentiment identification. In term of presentation, the system outputs the summary for each hotel in a four-quarter screen presented in Figure 5. The top left quarter shows the general/summarised overview of the hotel, top right column contains the time based performance chart, and the two bottom sections give details of each positive (left hand side) and negative (right hand side) groups of reviews. Though the RnR output provides the useful global picture of the reviews, it is lacking a fundamental dimension which is the temporal dimension. The rating chart does indeed give trends but is of little interest when the tend is flat as it the case in Figure 5. So there is no way for the costumer to know the latest positive and negative features of the hostel nor to know what are the positive and negative constants of it. Furthermore, tabular and keyword presentation might not be the best way of presenting a summarisation of the reviews as every pieces of information is presented in an out-of-context way. A more elegant approach to present such information both with respect to the temporal and contextual perspectives is to use Natural Language Generation (NLG).

4 Towards an abstractive summarisation system NLG systems has been used for decade to present numerical and linguistic information in a condense and efficient way. Recently, NLG has been applied to summarise large volumes of heterogeneous temporal data to short texts in the medical domain [START_REF] Portet | Automatic generation of textual summaries from neonatal intensive care data[END_REF]. This system was experimented at the hospital and has shown that a textual-only output can led to better decision from the medical staff than a classical graphical-only presentation. Among the properties, emphasised by the authors [START_REF] Gatt | From data to text in the neonatal intensive care unit: Using NLG technology for decision support and information management[END_REF], that textual summarisation offers compared with the graphical presentation are : the capacity to present data in the same sentence at multiple time resolution or period (e.g., "the hotel had always been praised for its good beds", "in summer, the hotel is found to be badly ventilated"), the natural ability to handle vagueness and uncertainty (e.g., "the hotel seems to be close to public transport"), the capacity to insert genuine citations (e.g., "the hotel could not even offer us a hand towel!"), the possibility to aggregate features (e.g., "close station(90); free tram(44); close train(33);" → "close public transport and free tram") and the capacity to contrast features (e.g., "even the negatives reviews reports that the bathroom is generally clean and large").

To address the above limitations and progress beyond the state of the art in this domain, we plan to build an approach based on the work of Rahayu et al. [START_REF] Rahayu | Web services for analysing and summarising online opinions and reviews[END_REF] and Portet at al. [START_REF] Portet | Automatic generation of textual summaries from neonatal intensive care data[END_REF]. This approach combines a sentiment analyses and domain-specific text processing approaches to represent the data in a high level representation (e.g., in the form of an ontology) with a natural language generation system to generate a textual user-tailored review of an hostel. The intended system is depicted Figure 6. User requests a summary of a specific hostel. In some cases, she can also specify which features are the most important for her so that features belonging to her preferences are given more weight. The system then fetches all the opinions about this hotel (e.g., trip advisor) and extract the features describing each reviews. Once the features extractions is performed, a sentiment analysis layer extracts polarity affecting each phrases of interest. These phrases are then abstracted into facts in a database backed by an ontology which represent the hotel and customer's concepts. Using the ratings, a time series segmentation [START_REF] Charbonnier | A self-tuning adaptive trend extraction method for process monitoring and diagnosis[END_REF] is performed to identify the main periods of the hotel (decrease, increase, stable). Another segmentation is performed at the feature level to detect specific evolutions of the hotel's services. Once the opinions have been analysed all the data is summarised through an NLG approach.

Conclusion

Although human summaries are typically abstracts, most existing systems produce extracts, due to several studies reporting better results of the latter [START_REF]Advances in Automatic Text Summarization[END_REF]. This is due to the complexity the process that involves concepts extraction, reasoning at the semantic level and natural language generation. This makes it a time consuming task. However, review summarisation is a very different application than documents considered in classical summarisation. The high number of authors, style, subjectivity and the temporal dimension calls for the reconsideration of the abstractive approaches to perform a deep analysis to better condense the information present in the reviews. Our approach by considering these aspect while aiming for a modular architecture, is a step towards addressing this challenge. Another important challenge is the evaluation of such technology. This is delicate given that no gold standard summary exists in this domain for automatic scoring (such as with BLEU or ROUGE) and because users will often disagree on what constitutes the best content and quality for the summary. A more relevant measure would be to perform some task-based experiments to assess the effectiveness of the summariser in searching for an hotel. We plan to investigate the techniques used in different domains to propose a formal evaluation strategy which would make it possible to assess the progress of the method.

Fig. 1 .

 1 Fig. 1. Example of reviews containing poorly structured content, subjective sentiments and opinions, metaphor, or cultural references.

Fig. 3 .

 3 Fig. 3. Diagram of the extractive system

Fig. 4 .

 4 Fig. 4. Example of extracted sentences for the feature BED.

Fig. 5 .

 5 Fig. 5. RnR output.

Fig. 6 .

 6 Fig. 6. Diagram of the abstractive system

The RnR system is accessible at http://rnrsystem.com/RnRSystem