Dionysis Athanasopoulos

Member, IEEE Apostolos V Zarras
email: zarras@cs.uoi.gr

George Miskos
email: gmiskos@gmail.com

Valerie Issarny
email: valerie.issarny@inria.fr

Member, IEEE Panos Vassiliadis

• D Athanasopoulos

Cohesion-Driven Decomposition of Service Interfaces Without Access to Source Code

Keywords: Cohesion, Decomposition, Service interface !

Software cohesion concerns the degree to which the elements of a module belong together. Cohesive software is easier to understand, test and maintain. Improving cohesion is the target of several refactoring methods that have been proposed until now. These methods are tailored to operate by taking the source code into consideration. In the context of service-oriented development, cohesion refers to the degree to which the operations of a service interface belong together. In this context, we propose an approach for the cohesion-driven decomposition of service interfaces. The very philosophy of services dictates that all that is exported by a service is the service specification. Hence, our approach for the cohesion-driven decomposition of service interfaces is not based on how the services are implemented. Instead, it relies only on information provided in the specification of the service interfaces. We validate the approach in 22 real-world services provided by Amazon and Yahoo. We show the effectiveness of the proposed approach, concerning the cohesion improvement and the size of the produced decompositions. Moreover, we show that the proposed approach is useful, by conducting a user study, where developers assessed the quality of the produced decompositions.

INTRODUCTION

Alice in the Web services world: Alice is an ordinary Java developer. Some time ago, she discovered the benefits of using Web services for developing software. Alice finds them very handy. As it is typically done, the applications that she develops access services via JAX-WS 1 proxies, generated from the WSDL specifications of the services interfaces. A JAX-WS proxy looks much like an ordinary Java class, but its methods delegate calls to service operations and bring the results back to the application.

However, using services also has its drawbacks. Often, new versions of the Web service interfaces are released and Alice spends quite some time to test and maintain her software, when this happens. For instance, one of the projects that Alice is involved relies on the Amazon SQS service 2 (Figure 1). This service provides functionalities for message-based communication. Messages are stored/retrieved to/from message queues, which are allocated on the Amazon Cloud. Apart from the messaging operations, the service provides operations for the management of queue attributes, the management of queue access grants and the management of message visibility timeouts. Since 2007, the main interface of the service Fig. 1.

A client application that relies on the MessageQueue interface. has been changed more than 4 times 3 . Whenever the MessageQueue interface changes, the continuous integration development platform (CIDP) that is used in the project traces that the MessageQueue proxy has changed. Following, the CIDP rebuilds the whole application and retests all the classes since they depend on the changed proxy. This overall process takes too long. Worst, Alice spends much time on checking the built logs and the test results to find out which tasks went right, or wrong.

On the back of her head, Alice has an idea that could save her from this burden. The idea is to split the MessageQueue interface into a set of new interfaces and develop a corresponding set of surrogate classes that implement these interfaces (Figure 2). The methods of the surrogate classes would then call the actual MessageQueue operations, via the MessageQueue proxy. Making the application use the surrogate classes, instead of directly using the 3. aws.amazon.com/articles/Amazon-SQS/1148 Fig. 2. A client application that relies on a cohesive decomposition of the MessageQueue interface.

MessageQueue proxy, will decouple the constituent parts of the application from service operations that are not actually used in these parts. In this setting, changes to the MessageQueue interface shall affect certain surrogate classes. Then, only the parts of the application that use the affected surrogate classes will have to be re-built and re-tested. In fact, this idea would be useful for many others that use Amazon SQS. So, Alice plans to make her new interfaces and the surrogate classes that implement them available as an open source Java API. Alice thinks that the same idea could also be useful in the case of services that provide a large number of operations. Amazon EC2 4 , for instance, provides 87 operations grouped in a single interface. Similarly, the Yahoo KeywordService 5 provides 34 operations, grouped in a single interface. The decomposition of such large interfaces could be used to develop APIs that provide the developers with higher-level views of what the services do.

Having in mind a larger community of developers that could benefit from her idea, puts Alice into deeper thoughts about the proper splitting of service interfaces. The decomposition of service interfaces should be done in a principled way. Alice recalls the the fundamental notion of cohesion. In general, software cohesion refers to the degree to which the elements of a module belong together [START_REF] Stevens | Structured Design[END_REF]. Cohesive software is easier to understand, test and maintain. In the case of Web service interfaces, the splitting should rely on a certain notion of cohesion that reflects the relatedness of the operations which are grouped in the same interface [START_REF] Papazoglou | Service-Oriented Design and Development Methodology[END_REF], [START_REF] Legner | Design Principles for B2B Services -An Evaluation of two Alternative Service Designs[END_REF], [START_REF] Kohlborn | Identification and Analysis of Business and Software Services -A Consolidated Apporach[END_REF], [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF], [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF]. Technical challenge: Unfortunately, Alice cannot obtain her desideratum of splitting a service interface into a set of cohesive interfaces via the state of the art cohesion-driven refactoring methods [START_REF] Tsantalis | Identification of Move Method Refactoring Opportunities[END_REF], [START_REF] Simon | Metrics Based Refactoring[END_REF], [START_REF] Fokaefs | Decomposing Object-Oriented Class Modules Using an Agglomerative Clustering Technique[END_REF], [START_REF] Doval | Automatic Clustering of Software Systems Using a Genetic Algorithm[END_REF], [START_REF] Bois | Refactoring: Improving Coupling and Cohesion of Existing Code[END_REF], [START_REF] Seng | Search-Based Determination of Refactorings for Improving the Class Structure of Object-Oriented Systems[END_REF], [START_REF] Tahvildari | Improving Design Quality Using Meta-Pattern Transformations: A Metric-Based Approach[END_REF], [START_REF] O'keeffe | Search-Based Refactoring for Software Maintenance[END_REF], [START_REF] Bowman | Solving the Class Responsibility Assignment Problem in Object-Oriented Analysis with Multi-Objective Genetic Algorithms[END_REF]. On the one hand, like all Web services, the ones that Alice uses do not expose their internals, i.e., their source code; on the contrary, [START_REF] Kohlborn | Identification and Analysis of Business and Software Services -A Consolidated Apporach[END_REF]. aws.amazon.com/ec2/ 5. developer.searchmarketing.yahoo.com/docs/V6/reference/services/ the very philosophy of Web services dictates that all that is exported by a Web service is the Web service specification. On the other hand, the cohesion-driven refactoring methods are tailored to operate by taking the source code into consideration. To overcome this problem, in this paper we propose an approach that facilitates the cohesion-driven decomposition of service interfaces, without information of how the services are implemented. Contribution: The contributions of this paper are as follows.

First, we define a suite of cohesion metrics that quantify the degree to which the operations of a service interface are related based on interface-level relations, extracted from the service interface specification. The first two metrics, namely the Lack of Message-Level Cohesion (LoC msg ) and the Lack of Conversation-Level Cohesion (LoC conv ), rely on relations between operations that have similar types of inputs/outputs. The third metric, called Lack of Domain-Level Cohesion (LoC dom ), considers relations between operations that are characterized by similar domain-level terms, which are extracted from the names of the operations. The proposed metrics extend our early ideas introduced in [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF].

Second, we propose a cohesion-driven decomposition method that accepts as input a cohesion metric and a service interface. The given interface is progressively split into interfaces that are more cohesive than the given interface. If it is no longer possible to produce more cohesive interfaces, the decomposition stops.

Third, we have validated the proposed approach based on 22 case studies that concern services provided by Amazon and Yahoo. We have evaluated the effectiveness of our approach from a quantitative perspective by assessing the cohesion improvement and the size of the decompositions produced by the proposed approach. Moreover, we have assessed the usefulness of our approach, by conducting a user study, where developers assessed the quality of our method's outcomes, as well as the success of each of the proposed cohesion metrics.

The rest of this paper is structured as follows. In Section 2, we discuss our contribution with respect to the state of the art. In Section 3, we present the cohesion metrics that we employ for the decomposition of service interfaces. In Section 4, we detail the modus operandi of the proposed decomposition method. In Section 5, we discuss the results that we obtained. Finally, in Section 6 we summarize our contribution and discuss the future perspectives of this work.

RELATED WORK

In this section we discuss in further detail the contribution of our approach with respect to the state of the art. More specifically, in Section 2.1 we discuss the relation of our approach with previous efforts on software refactoring. Then, in Section 2.2 we focus on the cohesion metrics that we employ and their relation with cohesion metrics that have been proposed in the object-oriented and the service-oriented paradigms.

Refactoring

Refactoring is a behavior preserving changing process that improves the quality of a software system [START_REF] Opdyke | Refactoring Object-Oriented Frameworks[END_REF]. To this end, several interesting approaches have been proposed, concerning various development paradigms (e.g., object-oriented refactoring [START_REF] Kataoka | Automated Support for Program Refactoring using Invariants[END_REF], [START_REF] Tilevich | Binary Refactoring: Improving Code Behind the Scenes[END_REF], [START_REF] Vidács | From C++ Refactorings to Graph Transformations[END_REF], component-based refactoring [START_REF] Dig | Automated Detection of Refactorings in Evolving Components[END_REF], aspectoriented refactoring [START_REF] Anbalagan | Automated Inference of Pointcuts in Aspect-Oriented Refactoring[END_REF], [START_REF] Binkley | Tool-Supported Refactoring of Existing Object-Oriented Code into Aspects[END_REF], etc.). For an excellent survey on refactoring the interested reader may refer to [START_REF] Mens | A Survey of Software Refactoring[END_REF].

Our approach, is more closely related to metricsdriven refactoring methods, which employ metrics to discover and repair design problems. To achieve this goal, the state of the art methods rely on implementation-level relations, derived from source code (Appendix A, Table 5). Specifically, in [START_REF] Harman | Pareto Optimal Search Based Refactoring at the Design Level[END_REF], Harman & Tratt focus on the improvement of coupling. To this end, they rely on dependencies between classes, quantified based on the well-known CBO metric [START_REF] Chidamber | A Metrics Suite for Object Oriented Design[END_REF]. In [START_REF] Simon | Metrics Based Refactoring[END_REF], [START_REF] Fokaefs | Decomposing Object-Oriented Class Modules Using an Agglomerative Clustering Technique[END_REF] and [START_REF] Tsantalis | Identification of Move Method Refactoring Opportunities[END_REF], the goal is to improve the cohesion of classes, by taking into account relations between class methods and attributes (or other methods), used by the methods. Certain approaches consider the improvement of multiple quality properties. In particular, the methods proposed in [START_REF] Doval | Automatic Clustering of Software Systems Using a Genetic Algorithm[END_REF] and [START_REF] Bois | Refactoring: Improving Coupling and Cohesion of Existing Code[END_REF] focus on both coupling and cohesion. The methods proposed in [START_REF] Seng | Search-Based Determination of Refactorings for Improving the Class Structure of Object-Oriented Systems[END_REF], [START_REF] Tahvildari | Improving Design Quality Using Meta-Pattern Transformations: A Metric-Based Approach[END_REF] account for coupling, cohesion and code complexity. In [START_REF] O'keeffe | Search-Based Refactoring for Software Maintenance[END_REF] the proposed method considers the improvement of coupling, cohesion and code size. Finally, the method proposed in [START_REF] Bowman | Solving the Class Responsibility Assignment Problem in Object-Oriented Analysis with Multi-Objective Genetic Algorithms[END_REF] accounts for coupling, cohesion, code complexity and size.

Concerning their modus operandi, the metrics-driven refactoring methods can be divided in two categories. In the first category, the methods require more involvement from the developer [START_REF] Simon | Metrics Based Refactoring[END_REF], [START_REF] Tahvildari | Improving Design Quality Using Meta-Pattern Transformations: A Metric-Based Approach[END_REF], [START_REF] Tsantalis | Identification of Move Method Refactoring Opportunities[END_REF]. In particular, based on the values of the metrics that are considered, the methods identify possible refactorings that can improve the values of the metrics. Following, the developer is supposed to select and apply the refactoring that suits his/her preferences. In the second category, the methods do more work on behalf of the developer. These methods consider the refactoring as an iterative process. As long as the design of the classes can be improved the refactoring process keeps going. The algorithms that are used to realize the refactoring process vary. We have methods that rely on meta-heuristic optimization algorithms [START_REF] Harman | Search-Based Software Engineering[END_REF], [START_REF] Clarke | Reformulating Software Engineering as a Search Problem[END_REF] (e.g., hill-climbing [START_REF] Harman | Pareto Optimal Search Based Refactoring at the Design Level[END_REF], [START_REF] O'keeffe | Search-Based Refactoring for Software Maintenance[END_REF], simulated annealing [START_REF] O'keeffe | Search-Based Refactoring for Software Maintenance[END_REF], genetic algorithms [START_REF] Seng | Search-Based Determination of Refactorings for Improving the Class Structure of Object-Oriented Systems[END_REF], [START_REF] Bowman | Solving the Class Responsibility Assignment Problem in Object-Oriented Analysis with Multi-Objective Genetic Algorithms[END_REF]). Moreover, we have methods that are based on clustering [START_REF] Fokaefs | Decomposing Object-Oriented Class Modules Using an Agglomerative Clustering Technique[END_REF].

Our approach differs from the state of the art methods in two main points:

• It deals with a novel problem, i.e., the cohesiondriven decomposition of service interfaces, without knowledge of how the services are implemented. • To address this problem, our approach is based on interface-level relations, instead of being based on implementation-level relations.

Cohesion Metrics

In the early 90's Chidamber and Kemerer proposed the well-known LCOM metric (Lack of Cohesion of Methods) for measuring the cohesion of objectoriented software [START_REF] Chidamber | A Metrics Suite for Object Oriented Design[END_REF]. The interested reader may refer to [START_REF] Briand | A Unified Framework for Cohesion Measurement in Object-Oriented Systems[END_REF] and [START_REF] Dallal | A Precise Method-Method Interaction-Based Cohesion Metric for Object-Oriented Classes[END_REF] for two interesting surveys of the cohesion metrics that have been proposed since the seminal work of Chidamber and Kemerer. In the serviceoriented paradigm, cohesion was recognized as an important principle of service design in several interesting approaches that concern the overall serviceoriented development methodology [START_REF] Papazoglou | Service-Oriented Design and Development Methodology[END_REF], [START_REF] Legner | Design Principles for B2B Services -An Evaluation of two Alternative Service Designs[END_REF], [START_REF] Kohlborn | Identification and Analysis of Business and Software Services -A Consolidated Apporach[END_REF]. The first efforts for measuring cohesion have been made in the work of Perepletchikov et al. [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF]. The first study that investigated the issue of cohesion in the case of real-world services is reported in Athanasopoulos & Zarras [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF]. Finally, another interesting work that concerns the cohesion of services is presented in [START_REF] Kazemi | An Information Retrieval Based Approach for Measuring Service Conceptual Cohesion[END_REF].

In the object-oriented paradigm, the majority of the cohesion metrics measure the degree to which the methods of a class are related based on implementation-level relations (Appendix A, Table 6). Two class methods are considered as being related if they use common class attributes (or methods). In the object-oriented paradigm, we also have cohesion metrics that assess the relatedness of methods based on interface-level relations. In these metrics, two methods are considered as being related if they have parameters of the same type.

In the service-oriented paradigm, the SIIC metric [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF] measures the relatedness of service operations, with respect to implementation-level relations. According to SIIC, two operations are related if the use common implementation elements. Similarly, in the SCV metric [START_REF] Kazemi | An Information Retrieval Based Approach for Measuring Service Conceptual Cohesion[END_REF] two operations are considered as being related if they access related business entities, where the term business entity refers to an information entity involved in a particular business process. The SIDC and the SISC metrics [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF] rely on interface-level relations. In particular, in SIDC two operations are considered as being related if they have input (or output) parameters of the same type. In SISC, if the type of an output parameter of one operation satisfies the type of an input parameter of another operation, the two operations are considered as being related. The SIUC metric [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF], also operates at the interfacelevel; two operations are related if they are used by the same service clients.

Concerning the state of the art metrics that we previously discussed and our prior work on cohesion metrics for service interfaces [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF], the added value of this paper is the following:

• LoC msg and LoC conv take into account the structure of input/output data types, instead of considering only relations between operations that have inputs/outputs of the same type. • LoC dom is an additional metric that extends the suite of metrics that we introduced in [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF] and follows a completely different direction for measuring the cohesion of service interfaces, as it relies on relations between operations that are characterized by similar domain-level terms, which are extracted from the names of the operations.

INTERFACE-LEVEL COHESION METRICS

In this section, we focus on the cohesion metrics that we employ for the decomposition of service interfaces. In Section 3.1 we discuss the basic concepts that are shared among the metrics. Then, in Section 3.2 we define the metrics. Finally, in Appendix B we provide an analytic validation of the metrics, with respect to the theoretical framework of Briand et al. [START_REF] Briand | Property-Based Software Engineering Measurement[END_REF].

Basic Concepts

Our overall approach for measuring cohesion is based on a generic view of the notion of service interface, which is given in the following definition. Definition 1: (Service interface) A service interface, si, is characterized by a name and a set of operations, si.O (Table 1(1)). An operation is characterized by a name, an input message and an output message (Table 1(2)). A message is a set of parameters (Table 1(3)). Each parameter has a name and a type, which may be either an XML build-in type, or an XML complex type (Table 1(4)).

To measure cohesion, we further employ the concept of interface-level graph, which represents the interface-level relations between the operations of a given service interface. In general, two operations are related if their properties (e.g., names, parameters) are similar to some extent, according to a particular similarity function. More formally, the definition of the interface-level graph is given below.

Definition 2: (Interface-level graph) An interfacelevel graph, G * si = (V si , E si , OpS * ), for a service interface, si, and a similarity function, OpS * : si.O×si.O → [0, 1] that reflects the degree to which the operations of si are related, is a weighted graph with the following properties (Table 1(5)):

• The nodes, V si , of the graph represent the operations of si. • The edges, E si , of the graph represent interfacelevel relations between pairs of operations. • An edge, (op i , op j ), belongs to E si , iff

OpS * (op i , op j ) > 0; the weight that characterizes the edge is OpS * (op i , op j ).

G * si = (V si , E si , OpS * ) (4)
LoC * (si, OpS * ) = 1 -

∀(op i ,op j )∈E si OpS * (op i , op j ) |V si | * (|V si |-1) 2 (6)
Based on the concept of interface-level graph, the lack of interface-level cohesion is defined as follows.

Definition 3: (Lack of interface-level cohesion) Ideally, a service interface, si, would be fully cohesive if every operation of si is related with all the others and the similarity between every pair of operations is maximum (Figure 3, left). Hence, the ideal interface-level graph G * ideal = (V si , E ideal , OpS * ) for si has two properties: (1) G * ideal is complete; (2) for all, (op i , op j ) ∈ E ideal , OpS * (op i , op j ) = 1. Intuitively, the lack of cohesion for the service interface si measures the amount of transformation that the actual interface-level graph G * si = (V si , E si , OpS * ) of si must withstand to become identical to the ideal graph, G * ideal . This practically amounts to adding the missing edges and complementing the weights of the existing edges to become equal to 1. Formally speaking, the lack of cohesion of si measures the relative difference between G * si and G * ideal , i.e., LoC * (si, OpS * ) =

|E ideal |- ∀(op i ,op j )∈E si (OpS * (opi,opj )) |E ideal | . Given that |E ideal | = |Vsi| * (|Vsi|-1)

2

, with simple algebraic calculations we get the formula that is given in Table 1(6).

Metrics Definitions

The proposed cohesion metrics refine the generic definition of LoC * that was given in Section 3.1. In particular, the definitions of the metrics that we provide in the following paragraphs employ the notion of interface-level graph; the interface-level graph that is used for each metric relies on a different similarity function between operations.

Message-Level Cohesion

The notion of message-level cohesion assumes that two operations are related if their input (respectively, output) messages are similar. To measure the similarity between two messages we employ the notion of message-level graph that is defined below.

Definition 4: (Message-level graph) A messagelevel graph, G m = (V m , E m ), for a message, m, is a generic representation of the structure of m. Specifically, G m consists of 3 layers:

• The first layer, comprises a node, v m ∈ V m , that represents the message itself. • The second layer, comprises a set of nodes, which represent the parameters that constitute m. The edges between the first layer and the second layer nodes represent whole-part relations. • The third layer, details the structure of the types of the parameters that constitute m. Hence, the third layer may contain nodes that represent primitive XML elements, or complex XML elements that consist of further (primitive or complex) XML elements. The edges between the second layer and the third layer nodes represent type-of relations.

M sgS(mi, mj ) = |Vm i ∩m j | |Vm i ∪m j | (1)
OpSmsg(opi, opj ) = M sgS(opi.in, opj .in) 2 + (2)
M sgS(opi.out, opj .out) 2

OpSconv(opi, opj ) = M sgS(opi.in, opj .out) 2 + (3)
M sgS(opi.out, opj .in) 2

OpS dom (opi, opj ) = |Top i ∩ Top j | |Top i ∪ Top j | (4)
Definition 5: (Message similarity) The similarity between the two messages, m i , m j , (Table 2(1)) is measured with respect to the message-level graphs,

G mi , G mj , of m i , m j . Specifically, let G mi∩mj = (V mi∩mj , E mi∩mj ) denote the maximum common subgraph of G mi , G mj that represents a syntacti- cally correct XML schema. Moreover, let G mi∪mj = (V mi∪mj , E mi∪mj ) be the union of G mi , G mj (i.e., V mi∪mj = V mi ∪ V mj and E mi∪mj = E mi ∪ E mj ).
Then, the similarity, M sgS(m i , m j ), between m i and m j is the number of nodes of G mi∩mj , divided by the number of nodes of G mi∪mj . Examples of message-level graphs for MessageQueue.

In general, finding the maximum common subgraph for two graphs is a hard problem to solve. However, solving the problem for two message-level graphs is much easier because the search space is limited to a set of subgraphs that represent the XML types of the parameters that constitute the messages. Typically, the definitions of these XML types are provided in the service descriptions, separately from the specification of the service interfaces (see WSDL 1.1, WSDL 2.0 [START_REF] W3c | Web Services Architecture[END_REF]).

Taking a step further, we define the message-level similarity between two operations as follows.

Definition 6: (Message-level operation similarity) The message-level similarity, OpS msg , between two operations, op i , op j ∈ si.O of a service interface, si, is the average of (Table 2(2)):

1) the similarity between the input messages of op i and op j and 2) the similarity between the output messages of op i and op j . Taking the example of Amazon SQS, Figure 4(a) shows the message-level graph for the input message of the GetQueueAttributes operation. The GetQueueAttributesRequestMsg node represents the message (first layer). The GetQueueAttributes node is a parameter that comprises of sequence of attributes (second layer). The Attribute node represents a primitive XML string element (third layer).

Figure 4(a), further gives the messagelevel graph for the output message of the GetQueueAttributes operation. The GetQueueAttributesResponseMsg node represents the message (first layer). The GetQueueAttributes node represents a parameter that comprises of sequence of attribute value pairs (second layer). The AttributedValue node represents a complex XML element, which consists of two primitive XML string elements, represented by the Attribute and the Value nodes.

Similarly, Figure 4(b) gives the message-level graphs for the input and the output messages of the SetQueueAttributes operation.

The maximum common subgraph for the messagelevel graphs of the two input messages comprises only the Attribute node. The union of the two graphs consists of 7 nodes. Hence, the similarity between the two input messages is 1 7 . On the other hand, the message-level graphs of the two output messages have nothing in common. Thus, the similarity between the two output messages is 0. Overall, the message-level similarity between the two operations is

1 7 +0 2 .
Based on the message-level similarity between operations, we refine the LoC * metric.

Definition 7: (Lack of message-level cohesion) For a service interface, si, the lack of message-level cohesion, LoC msg (si), is an alias for LoC * (si, OpS msg ). Specifically, LoC msg (si) measures the relative difference between the interface-level graph, G msg si = (V si , E si , OpS msg ), defined based on the message-level similarity function, OpS msg , and the ideal interfacelevel graph, G msg ideal .

Fig. 5. G msg M essageQueue for MessageQueue.

In our example, Figure 5, gives the interface-level graph for the MessageQueue interface that is derived with respect to OpS msg . For presentation purposes the edges' width is proportional to the similarity between the operations. We see that the graph is not complete. Moreover, the message-level relations between the operations are weak; the similarities between the operations range from 0.07 to 0.21. Overall, the lack of message-level cohesion is LoC msg (M essageQueue) = 0.98.

Conversation-Level Cohesion

The notion of conversation-level cohesion assumes that an operation is related with another if the former's input (respectively output) message is similar with the latter's output (respectively input) message. More formally, we define the conversation-level similarity between two operations as follows.

Definition 8: (Conversation-level operation similarity) The conversation-level similarity between two operations, op i , op j ∈ si.O, of a service interface, si, is the average of (Table 2(3)):

1) the similarity between the input message of op i and the output message of op j and 2) the similarity between the output message of op i and the input message of op j . Returning to our example, the input message of GetQueueAttributes (Figure 4(a)) and the output message of SetQueueAttributes (Figure 4(b)), have nothing in common. On the other hand, the maximum common subgraph for the output message of GetQueueAttributes and the input message of SetQueueAttributes includes three nodes (AttributedValue, Attribute and Value). Hence, the conversation-level similarity between the two operations is Given the conversation-level similarity between operations, we introduce the following refinement of the LoC * metric.

Definition 9: (Lack of conversation-level cohesion) For a service interface, si, the lack of conversation-level cohesion, LoC conv (si), is an alias for LoC * (si, OpS conv ). In particular, LoC conv (si) measures the relative difference between the interfacelevel graph, G conv si = (V si , E si , OpS conv ), defined with respect to the conversation-level similarity function, OpS conv , and the ideal interface-level graph, G conv ideal . Regarding our example, the interface-level graph that shows the conversation-level relations for the MessageQueue interface is given in Figure 6. As in the case of message-level cohesion, the graph is not ideal. The overall lack of conversation-level cohesion is LoC conv (M essageQueue) = 0.98.

Domain-Level Cohesion

The basic intuition behind the notion of domain-level cohesion is that the names of the operations that are provided by a service reflect what these operations do. More specifically, the names of the operations comprise terms that correspond to certain actions (e.g., set, get) and terms that correspond to concepts of the domain that is targeted by the service (e.g., queue, attribute, message). Based on this intuition, two operations are considered as being related if their names share domain-level terms.

In our approach, we extract the domain-level terms from the names of the operations, based on the naming conventions of the particular coding style that is followed by the service provider. For instance, the Amazon services follow the PascalCase coding style 6 (the names of operations are sequences of terms with the first letter of each term being capitalized). On the other hand, the Yahoo services follow the Java coding style 7 . Then, we measure the domain-level similarity between two operations with the following similarity function.

Definition 10: (Domain-level operation similarity) Let T opi and T opj denote the sets of the domain-level terms that are extracted from the names of two operations, op i , op j ∈ si.O, of a service interface, si. The domain-level similarity between the two operations (Table 2(4)) is the Jaccard similarity for T opi and T opj (i.e., the size of the intersection divided by the size of the union of T opi and T opj ). Getting back to our example, the name of GetQueueAttributes consists of the action term Get, which is related with two domain-level terms, Queue and Attributes. The name of SetQueueAttributes comprises the action term Set, which is also related with Queue and Attributes. Therefore, the domain-level similarity between the two operations is 2 2 . The refinement of the LoC * metric, with respect to the domain-level similarity between two operations, is given below.

Definition 11: (Lack of domain-level cohesion) The lack of domain-level cohesion, LoC dom (si), for a service interface, si, is an alias for LoC * (si, OpS dom ). LoC dom (si) measures the relative difference between the interface-level graph, G dom si = (V si , E si , OpS dom ), defined with respect to the domain-level similarity function, OpS dom , and the ideal interface-level graph, G dom ideal .

Concerning our example, in Figure 7, we have the interface-level graph that shows the domainlevel relations for the MessageQueue interface. As in Figures 5 and7 the graph is not complete. However, the domain-level relations are generally strong; the similarities between operations range from 0.3 to 1. Overall, the lack of domain-level cohesion is LoC dom (M essageQueue) = 0.81.

COHESION-DRIVEN DECOMPOSITION

In this section, we detail the method that exploits the metrics defined in Section 3 for the cohesiondriven decomposition of service interfaces. Moreover, in Appendix C we provide a complementary analysis that concerns the stopping criteria and the complexity of the method.

At a glance, the cohesion-driven decomposition of service interfaces accepts as input a service interface, si, which is progressively split in more cohesive interfaces (Algorithm 1). Note that although we assume as input a single service interface, the method can be easily applied in the case of a service that provides multiple interfaces. In such case, the interfaces of the service can be merged into a single interface. Then, this interface can be given as input to the cohesiondriven decomposition method. As the decomposition proceeds, si is split in several interfaces, all of which are candidates to be further divided. To this end, we employ a queue, Q, which contains the interfaces that are candidates for decomposition (Algorithm 1, line 1). Initially, Q contains only the given interface, si (Algorithm 1, line 3). During each step (Algorithm Q.enqueue(rs) 18.

end if 19. until Q.size() = 0 20. return R I lines 5-20), the method dequeues from Q an intermediate interface r i and checks whether it is possible to improve the cohesion of r i , by removing a set of operations, which form a new interface r s . Hereafter, we use the term splinter interface to refer to r s , while r r denotes the interface that comprises the rest of the operations of r i .

The construction of the splinter interface takes place in two phases. The first phase, called createSplinter, checks if it is possible to improve the cohesion of r i , by removing an operation (Algorithm 1, line 11). If this phase fails to find such an operation, ri is inserted in the results set, R I (Algorithm 1, lines [START_REF] Seng | Search-Based Determination of Refactorings for Improving the Class Structure of Object-Oriented Systems[END_REF][START_REF] Tahvildari | Improving Design Quality Using Meta-Pattern Transformations: A Metric-Based Approach[END_REF]. Otherwise, the splinter interface, r s , that contains the operation is returned as a result of createSplinter, along with the interface r r that contains the remaining operations of r i . The second phase, called populateSplinter, further improves the cohesion of r s and r r , by moving operations from r r to r s (Algorithm 1, line 15). Finally, the two interfaces, r s , r r are inserted in Q (Algorithm 1, lines [START_REF] Opdyke | Refactoring Object-Oriented Frameworks[END_REF][START_REF] Kataoka | Automated Support for Program Refactoring using Invariants[END_REF].

In further detail, the two phases of the decomposition are discussed below.

The createSplinter phase accepts as input the intermediate interface, r i , that is picked from Q (Algorithm 2). Following, it iterates over the operations of r i (lines 9-16). Each iteration checks whether the removal of a single operation, op i , from r i improves the cohesion of the interface (line 12). To this end, the removal of op i is simulated with the help of a temporary interface, r tmp . Moreover, each iteration keeps track of the maximum cohesion improvement, δ max , that can be achieved, and of the operation, op s , Algorithm 2: createSplinter() that should be removed to achieve this improvement (lines [START_REF] Seng | Search-Based Determination of Refactorings for Improving the Class Structure of Object-Oriented Systems[END_REF][START_REF] Tahvildari | Improving Design Quality Using Meta-Pattern Transformations: A Metric-Based Approach[END_REF][START_REF] O'keeffe | Search-Based Refactoring for Software Maintenance[END_REF][START_REF] Bowman | Solving the Class Responsibility Assignment Problem in Object-Oriented Analysis with Multi-Objective Genetic Algorithms[END_REF]. After this iterative process, if δ max > 0, the splinter interface, r s , that contains op s is created, along with the interface, r r that contains the remaining operations of r i (lines [START_REF] Kataoka | Automated Support for Program Refactoring using Invariants[END_REF][START_REF] Tilevich | Binary Refactoring: Improving Code Behind the Scenes[END_REF][START_REF] Vidács | From C++ Refactorings to Graph Transformations[END_REF][START_REF] Dig | Automated Detection of Refactorings in Evolving Components[END_REF][START_REF] Anbalagan | Automated Inference of Pointcuts in Aspect-Oriented Refactoring[END_REF][START_REF] Binkley | Tool-Supported Refactoring of Existing Object-Oriented Code into Aspects[END_REF]. The two new interfaces are returned as the results of createSplinter (line 23). On the other hand, if is not possible to improve the cohesion of r i , by removing an operation (i.e., δ max = 0), the results of createSplinter are null.

The populateSplinter phase accepts as input the intermediate interface, r i , and the newly created interfaces, r s , r r (Algorithm 3). Then, it repeatedly moves operations from r r to r s (lines 9-33) as follows:

• The populateSplinter iterates over the operations of r r (lines 15-28). Each iteration checks if an operation, op i , can be moved from r r to r s . To perform this check, the movement of the operation is simulated with the help of two temporary interfaces, r rtmp , r stmp . In particular, r rtmp is employed to calculate the cohesion improvement, δ rr , that can be achieved for r r , if the operation is moved (lines 16-18). Similarly, r stmp is employed to calculate the cohesion improvement, δ rs , that can be achieved for r s (lines [START_REF] Vidács | From C++ Refactorings to Graph Transformations[END_REF][START_REF] Dig | Automated Detection of Refactorings in Evolving Components[END_REF][START_REF] Anbalagan | Automated Inference of Pointcuts in Aspect-Oriented Refactoring[END_REF]. The operation, op i , is considered as a candidate to be moved if the following conditions hold (line 22): (a) the cohesion of r r , after the move, is improved, i.e., δ rr > 0, (b) the cohesion of r s , after the move, is also improved, i.e., δ rs > 0, and (c) the lack of cohesion of r s , after the move, is smaller than the lack of cohesion of the intermediate interface r i that was picked from Q. Each iteration further keeps track of the total cohesion improvement that can be achieved, by moving op i , from r r to Algorithm 3: populateSplinter() r s . Moreover, it keeps track of the operation op s that maximizes the total cohesion improvement that can be achieved (lines 23-26).

• The operation, op s , that maximizes the total cohesion improvement, δ total , is moved from r r to r s (lines 29-32). • The whole process stops when op s = null (line 33) and the updated r s , r r are returned (line 34).

Back to our example, Figures 8, 9 and 10, give the three different decompositions of MessageQueue that result based on LoC msg , LoC conv and LoC dom , respectively 8 . In particular, the message-level decomposition of MessageQueue consists of 6 interfaces. The average lack of message-level cohesion of the interfaces is 0,92. Hence, an improvement has been made compared to the initial interface (Figure 5), but the improvement is small. This result is anticipated 8. The input to the method was the 2007 version of the interface, aws.amazon.com/articles/Amazon-SQS/1148 because the message-level relations between the operations of MessageQueue are not strong (Figure 5). The conversation-level decomposition consists of 7 interfaces. The average lack of conversation-level cohesion in this case is 0.88. Again, the improvement compared to the initial interface is small, because the conversation-level relations between the operations of MessageQueue are not strong (Figure 6). The domain-level decomposition of MessageQueue consists of 4 interfaces and the average lack of domainlevel cohesion is 0.13. The improvement in this case is high, since the domain-level relations between the operations of MessageQueue are quite strong (Figure 7).

Figure 11, provides an detailed view of the execution of Algorithm 1 in the case of LoC dom . Specifically, in the first step, the general queue management operations (DeleteQueue, SetQueueAttributes and GetQueueAttributes) are removed from MessageQueue. These operations constitute the splinter interface, r s1 (in Figure 2, this interface appears with the name QueueMgt). The remaining operations form r r1 . Overall, the lack of cohesion of r s1 is 0.33, while the lack of co- hesion of r r1 is 0.72. In the second step, r r1 is decomposed. In particular, the timeout management operations (GetVisibilityTimeout and SetVisibilityTimeout) are removed from r r1 , and the splinter interface, r s2 , is formed (in Figure 2, this interface is called TimeoutMgt). The rest of the operations of r r1 , form r r2 . The lack of cohesion of r s2 is 0, while the lack of cohesion of r r2 is 0.61. In the last step, r r2 is decomposed, by removing the access rights management operations (AddGrant, RemoveGrant and ListGrants), which constitute the splinter interface, r s3 (in Figure 2, this interface is named GrantsMgt). The rest of the operations are related to messaging and form r r3 (in Figure 2, this interface appears as MsgMgt). The lack of cohesion of r s3 is 0, while the lack of cohesion of r r3 is 0.2. To sum up, the results of the decomposition of MessageQueue are R I = {r s1 , r s2 , r s3 , r r3 }.

VALIDATION

Amazon and Yahoo are two major service providers that offer a wide variety of Web services. To validate the proposed approach, we selected services that provide interfaces with at least 10 operations. Overall, we used 11 Amazon services and 11 Yahoo services 9 . Hereafter, we use identifiers A1-A11 and Y1-Y11 to refer, respectively, to the interfaces of the Amazon and the Yahoo services that we used. Table 3 provides the mapping between the identifiers and the service interfaces, along with the sizes of the interfaces (i.e., the number of provided operations) and the values of LoC msg , LoC conv and LoC dom for the interfaces.

In the rest of this section we detail our findings. In Section 5.1 we concentrate on the effectiveness of the proposed approach from a quantitative perspective. In Section 5.2, we discuss the usefulness of the 9. The WSDL specifications of the Amazon and the Yahoo services can be found at: www.cs.uoi.gr/˜zarras/WS-Decomp-Material/ approach from the developers' perspective. Finally, in Section 5.3 we discuss threats to validity.

Effectiveness

To assess the effectiveness of the approach from a quantitative perspective we focus on the following research questions:

RQ1:

To what extent is cohesion improved by adopting the proposed method ? RQ2: Is the number of produced interfaces reasonable with respect to the size of the decomposed interface ?

To respond to these questions we decomposed the examined service interfaces, based on the metrics that we defined in Section 3, and the method that we detailed in Section 4. To address RQ1, we measured the cohesion improvement, CI(si), that is achieved for a service interface si. Formally, for a set of interfaces, R I , produced by the proposed method for si, the cohesion improvement is: CI(si) = LoC * (si,OpS * ) * 100%. To address RQ2, we measured the number of interfaces, DS(si) = |R I |, produced by the proposed method for si. We further examined the relation between the number of operations offered by si (the independent variable) and DS(si) (the dependent variable), using ordinary least squares regression (OLS). Hereafter, we use the term, decomposition of si, to refer to the set of interfaces, R I , that is produced by the proposed method for si. Moreover, we use to term, size of decomposition, to refer to DS(si).

RQ1: Figure 12(left col.), gives the values of CI that we obtained for the examined service interfaces. Concerning our first question, the combination of the proposed method with the domain-level cohesion metric (i.e., LoC dom ) was effective in all cases. The cohesion improvement for the domain-level decompositions is medium-high (CI ranges from 38% to 100%). The combination of the proposed method with the message-level cohesion metric (i.e., LoC msg ) was also effective in all cases. The cohesion improvement for the message-level decompositions is medium (CI is up to 41.9%). Finally, the combination of the proposed method with the conversation-level cohesion metric (i.e., LoC conv ) was effective in 77% of the cases. The cohesion improvement for the conversation-level decompositions is low. In 5 cases (A9, Y2, Y4, Y7, Y10), the similarities between the operations of the examined interfaces were such that the conversationlevel cohesion of the initial interfaces could not be further improved.

RQ2: Figure 12(middle col.), gives the values of DS that resulted for the examined interfaces. Moreover, Figure 12(right col.) gives the results of the OLS analysis; in the x-axis of the scatter plots we have the number of the operations that are offered by the examined interfaces, in the y-axis we have the values of DS, and at the lower left corner of the scatter plots we have the regression equations and the values of the R 2 statistic. In general, the values of the R 2 statistic range from 0 to 1; high R 2 values indicate that a regression equation explains well the relationship between the variables involved in the equation. In our analysis, the values of the R 2 statistic are quite high (ranging from 0.71 to 0.89). Thus, the size of the decompositions, produced by the proposed method, linearly increases with the number of operations that are offered by the decomposed interfaces. The regression equations that we obtained for the different cohesion metrics are similar. The maximum value of the regression coefficients that could result from the OLS analysis is 1. A regression coefficient that equals to 1, would mean that the number of interfaces that are produced by the decomposition method equals to the number of operations of the decomposed interface. In our analysis, the regression coefficients are quite small, ranging from 0.33 to 0.35. Hence, the size of the produced decompositions is reasonable, with respect to the number of operations of the decomposed interface. Nevertheless, there are certain cases where the size of the produced decompositions is relatively high -see Fig. 12(middle col.). For instance, for the combination of the decomposition method with the domain-level cohesion metric we have the cases of A3 and Y3. Similarly, for the combination of the decomposition method with the message-level cohesion metric we have the cases of A3 and Y7. Finally, for the combination of the decomposition method with the conversation-level cohesion metric we have the cases of A2 and Y5.

The Developers' Opinions

To evaluate the usefulness of the approach from the developers' perspective we investigate the following research questions: RQ1: Does the proposed approach produce useful results for the developers ? RQ2: What are the developers' preferences (if any) concerning the metrics that are employed ? RQ3: To what extent should the results be refined to fully satisfy the developers' needs ? To address the aforementioned questions we looked for volunteers with the following skills: software development experience; knowledge of the serviceoriented computing paradigm, related technologies and standards. Overall, 10 volunteers participated in our study. The participants had 3 to 15 years experience in software development. They were all familiar with the service-oriented computing paradigm.

We organized the participants in two groups. The first group assessed the decompositions of the Amazon service interfaces, while the second group assessed the decompositions of the Yahoo service interfaces.

In a first meeting with the participants, we explained the overall purpose of the study, without giving any details, concerning the metrics and the method used for the decomposition of the examined service interfaces. Following, we gave to each participant a document 10 that contained the following information for each one of the examined interfaces: (a) • In the first task, the participants had to choose whether a service interface should be decomposed, or remain as is. • In the second task, the participants had to report which of the provided decompositions is closest to their preferences; in this task the participants could also report that none of the provided decompositions is satisfactory. • The third task was to suggest, if necessary, further changes on a selected decomposition.

In a second meeting with each of the participants, we collected the documents and we analyzed the participants' feedback. The participants' feedback is summarized in Figure 13. In this figure we use the following notations that correspond to the possible choices that could be made by a participant for a particular service interface: NO-SPLIT -the participant suggested that the interface should not be decomposed; NONE -none of the provided decompositions was selected by the participant; Msg -the participant selected the message-level decomposition; Conv -the participant selected the conversation-level decomposition; Dom -the participant selected the domain-level decomposition. Figure 13(a), gives for each service the percentage of the participants that made a particular choice. Finally, Figure 13(b) gives for each participant the percentage of the services for which he/she made a particular choice. RQ1: Concerning the first question, the participants suggested to decompose most of the examined interfaces. The only exceptions are Y3, Y6, Y7 and Y11 (Figure 13(a)). For Y3, Y7 and Y11, one of the participants suggested to leave the interface as is, while the others were in favor of decomposing the interface. For Y6, two of the participants suggested to leave the interface as is. For most of the service interfaces, the participants selected decompositions that were among the ones that we provided. In the Amazon services, we have 4 cases (A3, A6, A7, A11 in Figure 13(a)), for which one of the participants was not satisfied by any of the provided decompositions. For A6 and A7, the participants proposed their own decompositions. Specifically, the proposed decomposition for A6 was: "3 interfaces to manage fulfilment, items and shipments". For A7 the suggestion was: "3 interfaces for objects, buckets, access policies". In the Yahoo services, we have the case of Y1 (Figure 13(a)), for which two of the participants were not satisfied by any of the provided decompositions. The participants pointed out that the proposed decompositions do not separate clearly the underlying concepts (keywords, bids, adGroups, optimization guidelines). Moreover, in the Yahoo services we have the case of Y5 (Figure 13(a)), for which one of the participants proposed his own decomposition: "three sets of operations one for the standard accounts, one for the mobile accounts and one for the credit cards".

RQ2: Regarding the second question, the domainlevel cohesion metric worked very well for the participants. Specifically, in 63% of the services, more than 80% of the participants selected the domainlevel decomposition (Figure 13(a)). Concerning each one of the participants, the percentage of the services for which the domain-level decomposition was selected ranges from 36% to 100% (Figure 13(b)). On the other hand, the percentage of the services for which the message-level decomposition was selected ranges from 0% to 36% (Figure 13(b)). Finally, the percentage of the services for which the conversationlevel decomposition was selected ranges from 0% to 9% (Figure 13(b)).

RQ3: Concerning the third question, in several cases the participants did not suggest any changes in the selected decompositions. In the 55 decompositions that have been chosen for the Amazon services (5 participants × 11 services) there were 21 such occurrences; in the 55 decompositions of the Yahoo services this amounted to 18 occurrences. However, we also have several cases for which the participants moved certain operations between interfaces. In the 55 decompositions that have been chosen for the Amazon services there were 20 such occurrences; in the 55 Yahoo decompositions, this amounted to 14 occurrences. Moreover in several cases the participants decreased the size of the decompositions by merging certain interfaces. Specifically, we had 21 occurrences for the Amazon services and 24 occurrences for the Yahoo services. The details of the individual participants suggestions are found in Appendix D.

To conclude this study, we performed a X 2 test, so as to check the statistical significance of the results. The goal of the test was to examine the following null hypothesis: H 0 : The choices that have been made by the participants are not significantly different from the ones that we would have by chance alone.

Table 4 provides the details for the X 2 test that we performed. In particular, the first row of Table 4 gives the percentages of NO-SPLIT, NONE, Msg, Conv and Dom that we observed in the study in the overall 110 choices that have been made by the participants (22 services × 5 participants per service). The second row of Table 4 gives the percentages of NO-SPLIT, NONE, Msg, Conv and Dom, that we would have by chance alone. Based on the squared differences between the expected and the observed percentages, the overall X 2 value that we got is 184.83. Then, according to the X 2 distribution, the probability of having a X 2 as large as 184.83, by chance alone, is too small (ρ ≪ 0.001). Therefore, we rejected H 0 .

Threats to Validity

A possible threat to the internal validity of the results that we obtained from the developers' involved in the validation is the developers' fatigue or boredom [START_REF] Shadish | Experimental and Quasi-Experimental Designs for Generalized Causal Inference[END_REF].

To reduce this threat we arranged our study according to the developers' availability, instead of imposing a strict schedule. To avoid effects caused by interactions between the developers [START_REF] Shadish | Experimental and Quasi-Experimental Designs for Generalized Causal Inference[END_REF], we made clear that the required tasks should not be performed in a collaborative manner. Finally, to avoid learning effects [START_REF] Shadish | Experimental and Quasi-Experimental Designs for Generalized Causal Inference[END_REF], the different decompositions of each interface were provided to the developers in a random order. External validity concerns whether the results of a study can be generalized to a wide population [START_REF] Shadish | Experimental and Quasi-Experimental Designs for Generalized Causal Inference[END_REF]. Regarding external validity, the positive aspects of our validation are the following:

• It is among the very few ones [START_REF] Fokaefs | An Empirical Study on Web Service Evolution[END_REF], [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF] that involve real services. Specifically, we used a representative set of services, provided by two major service providers; the services offer diverse functionalities and their interfaces vary in size and complexity.

• It was based on a representative set of developers that have knowledge of the service-oriented computing paradigm, related technologies and standards. On the other hand, a possible limitation is that the validation was not based on a large number of developers. Nevertheless, the number of developers that we considered is comparable with other similar studies [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF], [START_REF] Fokaefs | Decomposing Object-Oriented Class Modules Using an Agglomerative Clustering Technique[END_REF], [START_REF] Tsantalis | Identification of Move Method Refactoring Opportunities[END_REF].

CONCLUSION

In this paper, we have proposed an approach that enables the cohesion-driven decomposition of service interfaces, without information of how the services are implemented. The proposed approach iteratively decomposes a given service interface in a set of more cohesive interfaces. We validated the approach in 22 real-world services provided by Amazon and Yahoo. Our findings showed that the proposed approach is able to improve cohesion. The number of interfaces produced by the approach linearly increases with the size of the decomposed interface. In general, the developers found the proposed approach useful. As anticipated, the decompositions produced by the method are not perfectly adjusted to the developers' needs. In certain cases the developers would prefer smaller and even more cohesive decompositions. Future work can be pursued towards avoiding unnecessary splits, interactiveness with the user and working with semantically annotated services.

In conversation-level cohesion, the similarity OpS conv (op i , op j ) is also an average of message similarities. Hence:

0 ≤ OpS conv (op i , op j ) ≤ 1 (4)
In domain-level cohesion, the similarity OpS dom (op i , op j ) is measured based on the sets of domain-level terms T opi and T opj . On the one extreme, T opi and T opj may have nothing in common. In this case we have:

|T opi ∩ T opj | = 0 (5)
On the other extreme, T opi and T opj may be identical, in which case we have:

|T opi | = |T opj | = |T opi ∪ T opj | = |T opi ∩ T opj | (6)
(5) and ( 6) imply that:

0 ≤ OpS dom (op i , op j ) ≤ 1 (7)
Theorem 1: For a service interface, si, and the interface-level graph, G * si = (V si , E si ), that represents the interface, 0 ≤ LoC * (si, OpS * ) ≤ 1.

Proof: Based on Lemma 1, for any two operations op i , op j of si we have:

0 ≤ OpS * (op i , op j ) ≤ 1 (8)
From graph theory we further have:

|E si | ≤ |V si | * (|V si | -1) 2 (9)
Based on ( 8) and ( 9) the following holds:

0 ≤ ∀(opi,opj )∈Esi OpS * (op i , op j ) |Vsi| * (|Vsi|-1) 2 ≤ 1 ⇒ 0 ≤ LoC * (si, OpS * ) ≤ 1 (10)
Theorem 2: Let si be a service interface, represented by the interface-level graph,

G * si = (V si , E si ). If E si = ∅, then LoC * (si, OpS * ) = 1.
Proof: Given that E si is empty we have:

E si = ∅ ⇒ ∀(opi,opj )∈Esi OpS * (op i , op j ) = 0 ⇒ LoC * (si, OpS * ) = 1 (
= (V si1 , E si1 ), G * si2 = (V si2 , E si2 ). Let si 1∪2 be the union of si 1 , si 2 , represented by, G * si1∪2 = (V si1∪2 , E si1∪2 ). Then, LoC * (si 1∪2 , OpS * ) ≥ max(LoC * (si 1 , OpS * ), LoC * (si 2 , OpS * )).
Proof: Without loss of generality, we assume that si 2 is more cohesive than si 1 . Based on this assumption, we have: OpS * (op i , op j ) [START_REF] Tahvildari | Improving Design Quality Using Meta-Pattern Transformations: A Metric-Based Approach[END_REF] Given that si 1 , si 2 are unrelated we have that:

∀(op si1 , op si2 ) ∈ V si1 × V si2 ,
OpS * (op si1 , op si2 ) = 0

From ( 14) we derive the following for the interfacelevel graph G * si1∪2 that represents the union of si 1 , si 2 :

V si1∪2 = V si1 ∪ V si2 (15) E si1∪2 = E si1 ∪ E si2 (16)
From ( 15), ( 16) we have that:

LoC * (si 1∪2 , OpS * ) = (17)

1 - Esi 1
OpS * (op i , op j ) + Esi 2 OpS * (op i , op j )

(|Vsi 1 |+|Vsi 2 |) * (|Vsi 1 |+|Vsi 2 |-1) 2
Given [START_REF] Kataoka | Automated Support for Program Refactoring using Invariants[END_REF], to prove the theorem we have to show that the following inequality holds:

1 - Esi 1
OpS * (op i , op j ) + Esi 2 OpS * (op i , op j )

(
From ( 18), with trivial algebraic operations, we derive the following inequality that must hold to prove the theorem: OpS * (op i , op j )

2 * |V si1 | * |V si2 | + (19)
Given that (13) holds, ( 19) is also true.

APPENDIX C DECOMPOSITION METHOD TERMINATION & COMPLEXITY

The analysis of the proposed decomposition method focuses on two issues. First, we prove that the cohesion-driven decomposition of service interfaces terminates. Second, we show that the complexity of decomposing a given interface with the proposed method is, in the worst case, cubic to the number of operations, offered by the given interface. Theorem 5: Given a service interface si, decomposeInterf ace (Algorithm 1) terminates.

Proof: decomposeInterf ace performs a number of iterations, until the size of Q is 0. During each iteration, decomposeInterf ace picks a service interface r i from Q. If the cohesion of r i can not be improved, r i is put in the results set R I . Otherwise, the cohesion of r i is improved by splitting it in two new interfaces r r , r s , which are stored in Q. decomposeInterf ace can not perform infinite splits because:

• The lower bound for the lack of cohesion of a service interface is 0 (Theorem 1). • The lower bound for the number of operations of a service interface is 1. Therefore, the size of Q eventually becomes 0 and decomposeInterf ace terminates.

Theorem 6: In the worst case, the complexity of decomposing a service interface, si, is cubic to the number of operations of si.

Proof: In the worst case scenario, decomposeInterf ace (Algorithm 1) starts with si that provides |si.O| operations and results in |si.O| new interfaces, one per operation. To achieve this, the algorithm starts with si and splits it in two new interfaces r r and r s . The new interfaces are enqueued in Q. In the i-th iteration, one of the intermediate interfaces, r i is chosen and split again. Hence, at the end of the i-th iteration, Q contains i + 1 new interfaces. Once, the size of Q becomes |si.O|, there are another |si.O| iterations to dequeue the interfaces that are held in Q (again in the worst case). Therefore, in the worst case decomposeInterf ace performs 2 * |si.O| iterations.

The two factors that affect the complexity of splitting an intermediate interface r i in two interfaces is the creation (Algorithm 2) and population of the splinter interface r s (Algorithm 3).

• createSplinter performs |r i .O| iterations to find the operation, op s , whose removal maximizes the cohesion improvement of r i . Then, it creates r s that contains op s , and r r that contains the rest of the r i operations. • populateSplinter, takes as input the interfaces r r , r s that result from createSplinter. Hence, |r r .O| = |r i .O| -1 and |r s .O| = 1. To improve the cohesion of the two interfaces populateSplinter moves operations from r r to r s . In the worst case, we can have |r r .O| -1 = |r i .O| -2 operations moved, i.e., the outer loop of populateSplinter performs |r i .O| -1 iterations. To find the first operation, the inner loop of populateSplinter performs |r i .O| -1 iterations. To find the i-th operation, the inner loop of populateSplinter performs |r i .O| -1i + 1 iterations, and so on. Therefore, the overall number of iterations performed is

APPENDIX D INDIVIDUAL PARTICIPANTS' SUGGESTIONS

FOR IMPROVEMENT Tables 7,[START_REF] Simon | Metrics Based Refactoring[END_REF] give a detailed summary of the changes that have been performed by the participants on the decompositions that they selected. In particular, for each one of the examined interfaces and each participant we provide the percentage of the moved operations (over the size of the examined interface) and the percentage of the decomposition size decrease.

Overall, the percentage of moved operations ranged from 1.15% to 15.38% whenever this happened in

Fig. 3 .

 3 Fig. 3. The meaning of LoC * .

  si = (name : string, O) (1) O = {op : operation} operation = (name : string, (2) in : message, out : message) message = {p : parameter} (3) parameter = (name : string, type : anyT ype)

  (a) Messages of the GetQueueAttributes operation. (b) Messages of the SetQueueAttributes operation.

Fig. 4 .

 4 Fig. 4.Examples of message-level graphs for MessageQueue.

Fig. 6 .

 6 Fig. 6. G conv M essageQueue for MessageQueue.

Fig. 7 .

 7 Fig. 7. G dom M essageQueue for MessageQueue.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Decomposition of MessageQueue, based on LoC msg .

Fig. 10 .

 10 Fig. 10. Decomposition of MessageQueue, based on LoC dom .

Fig. 11 .

 11 Fig. 11. Decomposing the MessageQueue interface.

Fig. 12 .

 12 Fig. 12. Effectiveness Assessment

  (a) The choices made for each service. (b) The choices made by each participant.

Fig. 13 .

 13 Fig. 13. Usefulness from the developers' perspective.

LoC * (si 1 , 2 ≥ 2 ⇒ 1

 1221 OpS * ) ≥ LoC * (si 2 , OpS * ) ⇒ (opi,opj )∈Esi 1 OpS * (op i , op j ) |Vsi 1 | * (|Vsi 1 |-1) (opi,opj )∈Esi 2 OpS * (op i , op j ) |Vsi 2 | * (|Vsi 2 |-1) |V si2 | * (|V si2 | -1) * Esi OpS * (op i , op j ) ≥ |V si1 | * (|V si1 | -1) * Esi 2

2 ≥ 1 -

 21 |Vsi 1 |+|Vsi 2 |) * (|Vsi 1 |+|Vsi 2 |-1) (opi,opj )∈Esi 1 OpS * (op i , op j ) |Vsi 1 | * (|Vsi 1 |-1)2

  |V si2 | * (|V si2 | -1) * (opi,opj )∈Esi 1 OpS * (op i , op j ) ≥ |V si1 | * (|V si1 | -1) * (opi,opj )∈Esi 2

|ri.O|- 1 2 .

 12 i=1 |r i .O|-i = |ri.O|-1 i=1 i = |ri.O| * (|ri.O|-1)Based on the previous analysis, in the worst case the complexity of decomposing si is O(|si.O| 3 ).

TABLE 1

 1 Basic concepts.

TABLE 2 Similarity

 2

functions.

  1, Interf ace /* An interface that is decomposed in more cohesive interfaces */ Output: R I = {r : Interf ace} /* The produced set of interfaces */ 1. var Q : Queue /* A queue that stores intermediate interfaces */

	Algorithm 1: decomposeInterf ace()
	2. R I ← ∅
	3. Q.enqueue(si)
	4. repeat
	5.	var ri : Interf ace /* holds an intermediate interface picked from
		the queue Q */
	6.	var rs : Interf ace /* the splinter interface that comprises
		operations removed from ri */
	7.	var rr : Interf ace /* the interface that comprises the remaining
		operations of ri */
	8.	ri ← Q.dequeue()
	9.	rs ← null
	10.	rr ← null
	11.	(rs, rr) ← createSplinter(ri) /* Phase 1: Returns the splinter rs
		and rr. */
	12.	if rs = null then
	13.	R I ← R I ∪ {ri} /* LoC * (ri) can not be further improved. */
	14.	else
	15.	(rs, rr) ← populateSplinter(rs, rr, ri) /* Phase 2: Populate
		rs. */
	16.	Q.enqueue(rr)
	17.

Input: si :

  Input: ri : Interf ace /* An intermediate interface picked from Q */ Output: rs : Interf ace /* The splinter interface that is created */ rr : Interf ace /* The interface that contains the remaining operations of ri */ 1. var ops : Operation /* The operation, whose removal maximizes the cohesion improvement of ri */ 2. var δmax : F loat /* The max cohesion improvement that can be achieved by removing an operation from ri */ 3. var rtmp /* A temporary interface used to simulate the interface that results from the removal of an operation from ri */

	4. rs ← null
	5. rr ← null
	6. δmax ← 0
	7. ops ← null
	8. rtmp ← null
	9. for all opi ∈ ri.O do
	10.	rtmp ← new Interf ace
	11.	rtmp.O ← ri.O -{opi}
	12.	if LoC * (ri) -LoC * (rtmp) > δmax then
	13.	δmax ← LoC * (ri) -LoC * (rtmp)
	14.	ops ← opi
	15.	end if
	16. end for
	17. if δmax > 0 then
	18.	rs ← new Interf ace
	19.	rs.O ← {ops}
	20.	rr ← new Interf ace
	21.	rr.O ← ri.O -{ops}
	22. end if
	23. return (rs, rr)

  The interface that contains the remaining operations of ri */ Output: rs : Interf ace /* The populated splinter interface that comprises operations removed from rr */ rr : Interf ace /* The interface that contains the remaining operations of ri */ 1. var δr r : F loat /* The cohesion improvement that can be achieved by removing an operation from rr */ 2. var δr s : F loat /* The cohesion improvement that can be achieved by adding an operation to rs */ 3. var δ total : F loat /* The total cohesion improvement (δr r + δr s ) that can be achieved by moving an operation from rr to rs */ 4. var ops : Operation /* The operation that is moved from rr to rs */ 5. var rr tmp , rs tmp : Interf ace /* Temporary interfaces used to simulate the interfaces that result after moving an operation from rr to rs */ 6. rr tmp ← null 7. rs tmp ← null 8. /* Move operations from rr to rs */

	9. repeat
	10.	ops ← null
	11. 12. 13.	δr r ← 0 δr s ← 0 δ total ← 0
	14.
		ops ← opi
	26.	end if
	27.	end if
	28.	end for
		/* Move the operation ops */
	29.	if ops = null then
	30.	rr.O ← rr.O -{ops}
	31.	rs.O ← rs.O ∪ {ops}
	32.	end if
	33. until ops = null
	34. return (rs, rr)

Input: ri : Interf ace /* An intermediate interface picked from Q */ rs : Interf ace /* The splinter interface that was created in Phase 1 */ rr : Interf ace /* /* Find the operation ops that improves the cohesion of rr and rs, and maximizes δ total */ 15. for all opi ∈ rr.O do 16. rr tmp ← new Interf ace 17. rr tmp .O ← rr.O -{opi} 18. δr r ← LoC * (rr) -LoC * (rr tmp ) 19. rs tmp ← new Interf ace 20. rs tmp .O ← rs.O ∪ {opi} 21. δr s ← LoC * (rs) -LoC * (rs tmp ) 22. if ((δr r > 0) ∧ (δr s > 0) ∧ (LoC * (rs tmp ) < LoC * (ri))) then 23.

if δr s + δr r > δ total then 24.

δ total ← δr s + δr r 25.

TABLE 3

 3 Amazon & Yahoo case studies.

	(a) Amazon: aws.amazon.com/
		Service Interface
	Name	Size	ID	LoCmsg	LoCconv	LoC dom
	AmazonEC2PortType	87	A1	0.98	0.99	0.94
	MechanicalTurkRequesterPortType	27	A2	0.92	0.84	0.83
	AmazonFPSPortType	27	A3	0.92	0.97	0.96
	AmazonRDSv2PortType	23	A4	0.91	0.96	0.56
	AmazonVPCPortType	21	A5	0.95	0.98	0.82
	AmazonFWSInboundPortType	18	A6	0.93	0.96	0.73
	AmazonS3	16	A7	0.89	0.97	0.75
	AmazonSNSPortType	13	A8	0.96	0.97	0.84
	ElasticLoadBalancingPortType	13	A9	0.93	0.97	0.72
	MessageQueue	13	A10	0.98	0.98	0.81
	AutoScalingPortType	13	A11	0.96	0.98	0.79
	(b) Yahoo:developer.searchmarketing.yahoo.com/docs/V6/reference/
	Service Interface
	Name	Size	ID	LoCmsg	LoCconv	LoC dom
	KeywordService	34	Y1	0.84	0.93	0.91
	AdGroupService	28	Y2	0.84	0.94	0.65
	UserManagementService	28	Y3	0.96	0.97	0.91
	TargetingService	23	Y4	0.74	0.96	0.74
	AccountService	20	Y5	0.92	0.98	0.88
	AdService	20	Y6	0.79	0.89	0.88
	CampaignService	19	Y7	0.83	0.91	0.91
	BasicReportService	12	Y8	0.91	0.99	0.92
	TargetingConverterService	12	Y9	0.84	0.80	0.53
	ExcludedWordsService	10	Y10	0.72	0.81	0.54
	GeographicalDictionaryService	10	Y11	0.79	0.99	0.65

TABLE 4 X

 4 2 test for the overall results.

		NO-SPLIT	NONE	Msg	Conv	Dom
	Observed	4.50%	13.51%	2.70%	73.87%	5.40%
	Expected	20.00%	20.00% 20.00% 20.00%	20.00%
	Squared diffs.	12.00	2.10	14.95	145.11	10.65
	X 2	184.83
	ρ value	6.81E-39

  11) have the same nodes, E si ⊆ E si ′ , and ∀(opi,opj )∈Esi OpS * (op i , op j ) ≤ ∀(opi,opj )∈E si ′ OpS * (op i , op j )), (opi,opj )∈Esi OpS * (op i , op j ) ∈E si ′ OpS * (op i , op j ) Let si 1 , si 2 be two unrelated service interfaces, represented by the interface-level graphs, G *

						Proof:	Given	the	initial	assumptions
						of the theorem for si and si ′ (i.e., G * si and G * si ′
							the	following
						implications hold:
							|Vsi| * (|Vsi|-1)	≤
							2
							∀(opi,opj )∈E si ′ OpS * (op i , op j ) |Vsi| * (|Vsi|-1)	⇒
							2
						1 -	∀(opi,opj )∈Esi OpS * (op i , op j ) |Vsi| * (|Vsi|-1)	≥
							2
						1 -	∀(opi,opj )|Vsi| * (|Vsi|-1)
							2
						si1
	Theorem 3: Let	si,	si ′	be	two	service
	interfaces, represented by the interface-level
	graphs, G *

si = (V si , E si ), G * si = (V si , E si ′ ). G *

si and G * si ′ have the same nodes. Moreover,

E si ⊆ E si ′ and ∀(opi,opj )∈Esi OpS * (op i , op j ) ≤ ∀(opi,opj )∈E si ′ OpS * (op i , op j ).

Then,

LoC * (si, OpS * ) ≥ LoC * (si ′ , OpS * ). ∀⇒ LoC * (si, OpS * ) ≥ LoC * (si ′ , OpS * )

(12)

Theorem 4:

Appendices to: Cohesion-Driven Decomposition of Service Interfaces Without Access to Source Code

Dionysis Athanasopoulos, Apostolos V. Zarras, George Miskos, Valerie Issarny, and Panos Vassiliadis APPENDIX A SUMMARY OF RELATED WORK Table 5, provides a summary of metrics-driven refactoring approaches that have been proposed in the past and highlights the contribution of our approach for the cohesion-driven decomposition of service interfaces. Moreover, Table 6, briefly summarizes the relation between the cohesion metrics that we employ in our approach, the object-oriented cohesion metrics surveyed in [START_REF] Dallal | A Precise Method-Method Interaction-Based Cohesion Metric for Object-Oriented Classes[END_REF], and the service-oriented cohesion metrics that have been proposed in [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF], [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF], [START_REF] Kazemi | An Information Retrieval Based Approach for Measuring Service Conceptual Cohesion[END_REF].

TABLE 5

A summary of metrics-driven refactoring approaches.

Refactoring

Purpose Type of relations Approach [START_REF] Harman | Pareto Optimal Search Based Refactoring at the Design Level[END_REF] Class coupling Implementation-level [START_REF] Tsantalis | Identification of Move Method Refactoring Opportunities[END_REF] Class cohesion Implementation-level [START_REF] Simon | Metrics Based Refactoring[END_REF] Class cohesion Implementation-level [START_REF] Fokaefs | Decomposing Object-Oriented Class Modules Using an Agglomerative Clustering Technique[END_REF] Class cohesion Implementation-level [START_REF] Doval | Automatic Clustering of Software Systems Using a Genetic Algorithm[END_REF] Class coupling, Implementation-level cohesion [START_REF] Bois | Refactoring: Improving Coupling and Cohesion of Existing Code[END_REF] Class coupling, Implementation-level cohesion [START_REF] Seng | Search-Based Determination of Refactorings for Improving the Class Structure of Object-Oriented Systems[END_REF] Class coupling, Implementation-level cohesion, code complexity [START_REF] Tahvildari | Improving Design Quality Using Meta-Pattern Transformations: A Metric-Based Approach[END_REF] Class coupling, Implementation-level cohesion, code complexity [START_REF] O'keeffe | Search-Based Refactoring for Software Maintenance[END_REF] Class coupling, Implementation-level cohesion, code size [START_REF] Bowman | Solving the Class Responsibility Assignment Problem in Object-Oriented Analysis with Multi-Objective Genetic Algorithms[END_REF] Class coupling, Implementation-level cohesion, code size, code complexity

Proposed

Service interfaces Interface-level approach cohesion TABLE 6 A summary of cohesion metrics [START_REF] Dallal | A Precise Method-Method Interaction-Based Cohesion Metric for Object-Oriented Classes[END_REF], [START_REF] Perepletchikov | The Impact of Service Cohesion on the Analyzability of Service-Oriented Software[END_REF], [START_REF] Athanasopoulos | Fine-Grained Metrics of Cohesion Lack for Service Interfaces[END_REF], [START_REF] Kazemi | An Information Retrieval Based Approach for Measuring Service Conceptual Cohesion[END_REF].

Implementation-level Interface-level

APPENDIX B ANALYTIC VALIDATION OF COHESION MET-

RICS

In the 90's, Briand et al. [START_REF] Briand | Property-Based Software Engineering Measurement[END_REF] proposed a mathematical framework for the theoretical validation of cohesion metrics. Here, we rely on this framework for the validation of the metrics that we employ for the cohesion-driven decomposition of service interfaces. Briefly, in [START_REF] Briand | Property-Based Software Engineering Measurement[END_REF], a software system is represented by a graph S = (E, R), where E is the set of elements that constitute the system and R ⊆ E × E is a set of relations between elements. A module of the system is represented by a graph m = (E m , R m ), where E m ⊆ E, and R m ⊆ R. According to Briand et al., a cohesion metric has to satisfy the following properties:

• Nonnegativity and normalization: The cohesion of a module m = (E m , R m ) belongs to a specified interval, i.e., cohesion(m)

For brevity, we focus our validation on LoC * . The three different refinements of LoC * can be validated identically. Differently from [START_REF] Briand | Property-Based Software Engineering Measurement[END_REF], the metrics that we consider measure the lack of cohesion of service interfaces. Moreover, the interface-level graphs that we employ are weighted. Hence, we appropriately adapt the properties that should hold for the proposed metrics. We begin our validation with the proof of a supportive lemma, which concerns the similarity functions that we employ. Then, we prove that LoC * satisfies the properties of the Briand et al. framework.

Lemma 1: The similarity functions that we use for the different notions of cohesion belong to the interval [0, 1].

Proof: In the case of message-level cohesion, the similarity, OpS msg (op i , op j ), between two operations is the average of the similarities between the input/output messages of op i , op j . The similarity, M sgS(m i , m j ), between two messages is measured based on the message-level graphs G mi , G mj of the messages. On the one extreme, the maximum common subgraph G mi∩mj of G mi , G mj may be trivial if G mi , G mj have nothing in common. In this case we have:

On the other extreme, G mi , G mj may be identical, in which case we have:

From ( 1) and ( 2) we have: Amazon services and 03.57% to 25% for the Yahoo services. The percentage of the decomposition size decrease ranged from 3.70% to 25% for Amazon and 11.11% to 33.33% for Yahoo services.