Julia Krämer
email: juliadk@mail.uni-paderborn.de

Heike Wehrheim
email: wehrheim@mail.uni-paderborn.de

A Short Survey on Using Software Error Localization for Service Compositions ⋆

In modern software development, paradigms like componentbased software engineering (CBSE) and service-oriented architectures (SOA) emphasize the construction of large software systems out of existing components or services. Therein, a service is a self-contained piece of software, which adheres to a specified interface. In a model-based software design, this interface constitutes our sole knowledge of the service at design time, while service implementations are not available. Therefore, correctness checks or detection of potential errors in service compositions has to be carried out without the possibility of executing services. This challenges the usage of standard software error localization techniques for service compositions. In this paper, we review state-of-the-art approaches for error localization of software and discuss their applicability to service compositions.

Introduction

Debugging, i.e., the detection, localization and correction of software errors, is one of the most time-intensive tasks in software development. Within this process, error localization is considered the most expensive task [START_REF] Vessey | Expertise in debugging computer programs: An analysis of the content of verbal protocols[END_REF]. In order to support developers in debugging, a lot of research effort has been spent on the deployment of automated error localization methods. Today, existing error localization methods for software are numerous. They can broadly be separated into two categories.

1.) Approaches based on the inspection of test cases. In this category, we find error localization methods like delta debugging introduced by Zeller [START_REF] Zeller | Yesterday, my program worked. today, it does not. why?[END_REF][START_REF] Zeller | Simplifying and isolating failure-inducing input[END_REF][START_REF] Zeller | Isolating cause-effect chains from computer programs[END_REF][START_REF] Cleve | Locating causes of program failures[END_REF] or the approaches underlying the tools Tarantula [START_REF] Jones | Visualization of test information to assist fault localization[END_REF], Pinpoint [START_REF] Chen | Pinpoint: problem determination in large, dynamic internet services[END_REF] or AM-PLE [START_REF] Dallmeier | Lightweight defect localization for java[END_REF].

2.) Approaches based on the computation of dependence information between

program statements. Herein, we locate all techniques based on static program slicing as originally introduced by Weiser [START_REF] Weiser | Program slicing[END_REF] as well as dynamic slicing.

When it comes to a model-driven design approach of service composition (or to model-driven software development in general), the situation is different. On the one hand, a model typically abstracts from details of the final software, thus facilitating the construction of automatic methods and tools for error detection (like being done in numerous settings, for functional as well as QoS requirements, e.g. [START_REF] Becker | Performance prediction of component-based systems: A survey from an engineering perspective[END_REF][START_REF] Engels | Assuring consistency of business process models and web services using visual contracts[END_REF][START_REF] Schäfer | Model-driven development with mechatronic UML[END_REF][START_REF] Mirandola | A reliability model for service component architectures[END_REF]). On the other hand, the localization of errors, once correctness checks have reported it, lacks automated methods and tool support. So far, to the best of our knowledge, automated, tool-based approaches for localizing faults in models of service compositions do not exist, at least when it comes to functional correctness, i.e., the adherence of the model to functional requirements. With respect to performance analysis of systems, feasible approaches to localize components that negatively impact the overall performance of the system, have been devised in the area of performance blame analysis [START_REF] Crnkovic | Component-based development process and component lifecycle[END_REF][START_REF] Brüseke | Pblaman: Performance blame analysis based on palladio contracts[END_REF].

Unfortunately, this lack in tool support cannot easily be amended by applying the abundant existing approaches for standard software development to the service composition approach. The reason is rooted in fact that almost all existing approaches in the standard software setting rely more or less on the availability of execution traces, both faulty and correct, or even the possibility to execute the programs under consideration at will. While this requirement is entirely unproblematic in the software setting, for service composition it is a veritable obstacle, as services, which are offered by external providers and possibly charged for their use, may not be available for execution during design time and fault analysis.

Contribution.

In this paper, we survey existing error localization techniques for software, analyze their applicability to models of service compositions and propose suitable adaptions. Our focus is on functional correctness, more specifically, the adherence of the service composition to specified pre-and postconditions. We assume that services are solely specified in terms of their pre-and postconditions (more precisely, their interface specification) and that no other information is available about services. In particular, no implementation is given and thus, they cannot be arbitrarily executed. In this setting, error localization can be rephrased as the task of locating the precise service call, which is responsible for the service composition to invalidate the postcondition when started in a state satisfying the precondition.

In comparison to existing surveys, such as [START_REF] Wong | A survey of software fault localization[END_REF] and [START_REF] Agarwal | Fault-localization techniques for software systems: A literature review[END_REF], which focus on methods of the first category, we also investigate methods of the second category and thus, include novel methods for error localization, especially formula-based approaches such as [START_REF] Jose | Cause clue clauses: Error localization using maximum satisfiability[END_REF][START_REF] Jose | Cause clue clauses: Error localization using maximum satisfiability[END_REF], [START_REF] Könighofer | Automated error localization and correction for imperative programs[END_REF] and [START_REF] Lamraoui | A formula-based approach for automatic fault localization of imperative programs[END_REF]. In contrast to [START_REF] Wong | A survey of software fault localization[END_REF] and [START_REF] Agarwal | Fault-localization techniques for software systems: A literature review[END_REF], we do not only review existing methods but also examine their applicability to service compositions.

Organization of the Paper. We introduce basic terminology (services and service compositions) in Section 2. In Section 3, we present the most important error localization methods for software and discuss their usability for service compositions in the context of model-based software design. We conclude the paper with a conclusion and future work in Section 4. Services, i.e. self-contained software components, which can be used platform independent, are at the core of Service-Oriented Architectures (SOA). In this section, we introduce service descriptions, which constitute all information about a service, and service composition as depicted in Figure 1. We denote service composition in a textual representation inspired by service effect specifications (SEFFs) of [START_REF] Becker | The palladio component model for modeldriven performance prediction[END_REF] (making some of the notations closer to programming languages), while we still use standard concepts of workflow modelling like sequential composition, decisions and repetition. Possible alternative representations for service compositions include graphical or structural notations for workflow modelling like WS-BPEL [START_REF]Web services business process execution language v2[END_REF]. The following definition specifies our textual representation of services formally. Definition 1. Let Serv be a set of given services, Types be a set of types and Var be a set of variables. The set of all service compositions SC is given by the following grammar in Backus-Naur-form:

SC ∋ φ, ψ ::= Skip | φ; ψ | if B then φ else ψ | while B do φ | T x = S(x 1 , . . . , x n ) | foreach x in Set do φ,
where x, x 1 , . . . , x n ∈ Var , S ∈ Serv, T ∈ Types and Set is a set. B is a predicate in propositional logic with the logical constants true, false and service calls S as atomic formulas.

Please note that we use assignemts in Figure 1, which are not service calls, for example, in Line 1, Line 3 and Line 8. We consider these assignment as very basic service calls usually not offered by an external provider but by the service specification language. Thus, we do not write them down as service call.

1 L o c a t i o n L:= i n p u t ( ) ; 2 Set<R e s t a u r a n t > A:= r e s t a u r a n t s I n ( L ) ; 3 Set<R e s t a u r a n t > B:= emptyset ; 4 f o r e a c h z i n A do 5 i f i s V e g a n ( z ) then 6 R a t i n g y := v a l i d a t e ( z ) ; The service composition GVRes in Figure 1 contains the service restaurantIn that retrieves all restaurants near a given location, the service isVegan, that tests whether a given restaurant offers vegan food, the service validate that provides the rating of a restaurant, and finally, the service isGoodRating, which specifies when a rating is considered a good rating. The purpose of the service composition GVRes is to compute the set B of all vegan restaurants with a good rating near a specific location L provided by the user. However, it is faulty. While the purpose of the foreach-loop is to filter all the restaurants with a good rating, the negation in the second if-statement (Line 7) causes only bad restaurants to be in the set B. At the best, fault localization would precisely indicate the condition of the if-statement !(IsGoodRating(y)) as the location of the error.

7 i f ! ( i s G o o d R
The semantics of single services is cruel to the correctness of a service composition. We specify the semantics using service dscriptions, which include input and output variables as well as pre-and postconditions (or effects, all together typically called IOPE, like in WSDL1 ). The service validate has the input variable z of type Restaurant and the output variable y of type Rating. Its postcondition guarantees that the returned rating is indeed a rating for the given restaurant if the input is indeed a vegan restaurant.

Service compositions are also specified using service description, e.g. the service composition GVRes has the input variable L of type Location, the output variable B of type Set<Restaurant>, the pre-and postcondition

Pre GVRes = true Post GVRes = ∀b ∈ B : isVegan(b) ∧ isGoodRating(validate(b)).
In the following, we say that a service composition is functionally correct with respect to a precondition Pre and a postcondition Post, if we can prove that for each input to a service composition, which satisfies the precondition, the output satisfies the postcondition. We say, that a service composition contains an error, if it is not functionally correct. The service composition in Figure 1 will thus be functionally correct if it ensures that no bad vegan or non-vegan restaurant is returned (which is not the case). It can be proven that a service composition is or is not functionally correct, for example, using the approach in [START_REF] Walther | Knowledge-based verification of service compositions -an smt approach[END_REF].

Survey on Error Localization

So far, error localization in service compositions has been a sparsely researched topic and only few approaches are known. In contrast, many localization methods for standard software (especially for imperative program) are known. Unfortunately, while imperative programs and service compositions are syntactically similar, they differ in their nature. While error location methods for programs can usually safely assume that the whole program can be executed arbitrarily, this is not the case for service compositions. At the time of analysis, the services called in the composition are in general not available for execution. The reason is that services are usually not locally available, but offered by external providers and charged for their usage. Thus, depending on the concrete services, their repeated execution for testing purposes might either not be given at the moment of analysis, or be economically infeasible. Thus, in order to make use of the rich source of error localization methods for standard software for service composition, we need to investigate how these methods can be adapted -if at all. Remark 1. The services and service compositions we discuss cannot be compared to dynamic web services, in the sense of applications written in PHP or JavaScript involving dynamically generated web pages or client-server-interaction. Therefore, our setting is very different from the setting in [START_REF] Minamide | Static approximation of dynamically generated web pages[END_REF][START_REF] Wassermann | Dynamic test input generation for web applications[END_REF][START_REF] Artzi | Directed test generation for effective fault localization[END_REF][START_REF] Artzi | Finding bugs in web applications using dynamic test generation and explicit-state model checking[END_REF][START_REF] Artzi | Fault localization for dynamic web applications[END_REF][START_REF] Artzi | A framework for automated testing of javascript web applications[END_REF] and thus, these approaches are inapplicable in our setting.

In this section, we first establish a set of criteria to evaluate existing automated error localization methods. Subsequently, we present an overview on existing error localization methods of both categories when applied to service compositions as in Definition 1 instead of to software.

Criteria for Error Localization Approaches

In [START_REF] Wong | A survey of software fault localization[END_REF][START_REF] Agarwal | Fault-localization techniques for software systems: A literature review[END_REF], criteria to evaluate error localization methods for software are discussed. We use a subset of these criteria, slightly adapted to the special challenges arising in the context of service compositions.

Number of test cases needed:

In model-driven software design, one cannot execute services at design time. In the best case, few test cases are available in form of input/output pairs witnessing erroneous behavior, for example resulting from a previous model checking analysis.

Our first evaluation criteria is thus the number of (faulty /correct) test cases a technique needs.

Code size reduction:

The second criteria we use is code size reduction, i.e., the percentage of suspicious statements (in which the fault is potentially located) returned by the error localization method with respect to all statements.

Another criterion, which is often used is multiple fault recognition, i.e. the possibility of discovering multiple bugs at once. We do not use it here since service compositions tend to be relatively small, and verification and error localization can thus be executed several times to find several bugs. Detection of faults caused by missing code is not a criterion of primary interest, as the results of existing approaches in general fail w.r.t. multiple bug detection to be specific enough to be of use in a setting where the programs to be analyzed consist of only few lines of code.

Error Localization Approaches in Service Compositions

In the following, we discuss different error localization methods for standard software. We group approaches, which are similar w.r.t. the number of tests cases they need to be applicable. If necessary, we further distinguish methods by their overall approach, for example, whether it relies on statistics or not.

Neither Relying on Test Cases nor on Execution. We start our survey with static slicing, which also was the first error localization method proposed in 1981 by Weiser [START_REF] Weiser | Program slicing[END_REF]. Slicing in general means to cut out statements, which cannot influence a certain variable or a certain property. The "influence" is captured by a number of dependency relations between program statements, e.g., a statement within a branch of a decision depends on the condition of the decision. With respect to error localization this means that the number of statements possibly responsible for the error can be reduced by slicing. Slicing approaches can mainly be divided into static and dynamic slicing. Whereas the first can be obtained without executing the program and thus, does also not rely on any tests, dynamic slicing gathers information during execution. In [START_REF] Zhang | Experimental evaluation of using dynamic slices for fault location[END_REF], it is stated that a static slice definitely contains the bug if it is contained in a Boolean condition or an assignment. Unfortunately, static slices are the largest ones among all slices. Nevertheless, static slicing can easily be modified to be used on service compositions, for example, in [START_REF] Mao | Slicing web service-based software[END_REF], static slicing is discussed for software relying on web services.

Application to Service Compositions. For faulty service compositions, we compute slices with respect to the intended postcondition. The static slice with respect to our postcondition Post GVRes of the service composition in Figure 1 contains all lines except the lines 9 to 12 (which are uninteresting anyway). We see that the gain in this case is close to zero. For finding the error, we still need to inspect the entire service composition. This is an effect, which occurs very often in service compositions because data is passed from one service call to the next, and thus service calls often depend on all prior calls. □

Relying on One Faulty Input. All of the following error localization methods need at least one faulty input, i.e., one input, which itself satisfies the precondition, but leads to an output, which does not satisfy the postcondition.

Dynamic Slicing. Dynamic slicing was originally introduced in 1988 in [START_REF] Korel | Dynamic program slicing[END_REF]. The key idea to dynamic slicing is to collect all relevant information directly during the execution of the program. In the literature, there are mainly three types of dynamic slices: data, full and relevant slices. They differ in the way they take dependencies between program statements into account: data slices just use data dependencies, full slices also control dependencies, and relevant slices in addition partially include static dependencies, i.e., dependencies on program paths, which are not included in the current dynamic execution, but might be if the control-flow is altered. At first, dynamic slicing was considered not useful for error localization [START_REF] Horgan | Dynamic program slicing[END_REF][START_REF] Agrawal | Debugging with dynamic slicing and backtracking[END_REF]. In 2005, an experimental evaluation in [START_REF] Zhang | Experimental evaluation of using dynamic slices for fault location[END_REF] showed that relevant slices are smaller than static slices, but contained all bugs in the experiments performed on the Siemens test suite [START_REF] Hutchins | Experiments on the effectiveness of dataflow-and control-flow-based test adequacy criteria[END_REF].

Application to Service Compositions. For service compositions, an abstract symbolic execution -i.e., an execution, which does not rely on concrete but on symbolic values for variables -could allow us to use dynamic slicing for error localization. Important questions to be investigated are then whether dynamic slices relying on a symbolic execution are smaller than static slices, and whether all faults are covered. For our example, a symbolic execution would -like for the static slice -return the whole service composition except the lines 9 to 12. We conjecture that this will very often be the case due to the tight dependencies between service calls. □ Trace Formula Approaches. In this section, we consider all approaches to error localization, which basically rely on a trace formula. The original idea to use trace formulas for verification was introduced in [START_REF] Clarke | A tool for checking ANSI-C programs[END_REF]. The basic idea therein is to code executions of a program (or even whole programs) as logical formulas, employing either propositional or predicate logic. In [START_REF] Walther | Knowledge-based verification of service compositions -an smt approach[END_REF], this basic principle has been used for the verification of service compositions. We mainly consider the error localization approach presented in [START_REF] Wotawa | Automated debugging based on a constraint model of the program and a test case[END_REF], where a trace formula is encoded as constraint satisfaction problem. In more detail, in [START_REF] Wotawa | Automated debugging based on a constraint model of the program and a test case[END_REF], a test defining inputs and expected outputs together with its symbolic execution trace, is transformed into a constraint satisfaction problem and solved using an existing constraint solver. The solution to the constraint satisfaction problem allows to easily extract a set of suspicious statements, which can be returned to the user. In [START_REF] Jose | Cause clue clauses: Error localization using maximum satisfiability[END_REF][START_REF] Jose | Cause clue clauses: Error localization using maximum satisfiability[END_REF], a similar approach using partial MaxSMT to locate errors in programs has been implemented in the tool BugAssist. MaxSMT is the maximal satisfiability problem, which determines the maximal number of clauses in a logical formula that can be simultaneously made true. MaxSMT instances allow to tag clauses as hard (definitely needs to be true) or soft (candidate for not making it true). With respect to error localization, this allows us to state where the error potential is (or definitely not is) by making this a soft (hard) clause. The test input and the property to be verified (e.g., the postcondition) are encoded as hard clauses, whereas the trace formula representing the program is encoded as soft clause. Using partial MaxSMT, a set of clauses is returned, which can simultaneously be set to true. The complement of this set then serves as set of suspicious statements.

Application to Service Compositions. Although we cannot rely on concrete input and outputs for service compositions, it seems worthwhile to investigate whether the approach can be adapted to work with pre-and postconditions instead of test cases. A verification technique like [START_REF] Walther | Knowledge-based verification of service compositions -an smt approach[END_REF] could for instance be used to generate abstract inputs leading to errors. Abstract input means that we do not have concrete values but just names for values. Given that this is possible, we could for instance get an abstract input like city for L with the following properties (also given via freely chosen names2 ):

restaurantsIn(city) = {res} isVegan(res) rat = validate(res) ¬isGoodRating(rat)
Given such a "test case", the trace formula of the given service composition encoded for MaxSMT may look like this:

L = city input ∧A = {res} ∧ B 0 = ∅ before loop ∧isVegan(res) ∧ y = rat ∧ ¬isGoodRating(rat) ∧ B 1 = B 0 ∪ {res} loop once ∧∀b ∈ B 1 : isVegan(b) ∧ isGoodRating(validate(b)) postcond.
In this example, the underlined clauses are hard clauses, all other clauses are soft. This formula encodes a path through the service composition when "run" on the test case plus the desired postcondition at the end. In order to encode the same trace and the same expected outputs as constraint satisfaction problem (similar to the approach in [START_REF] Wotawa | Automated debugging based on a constraint model of the program and a test case[END_REF]), we introduce a predicate AB i per statement i, which represents whether the statement i is abnormal. Abnormal statements are candidates for the root cause of the error. For instance, the first statement of the service compositions is then encoded as

(¬AB 1 ) ⇒ A = {res}.
Inputs, the precondition and the postcondition are encoded as so-called observations. The encoding of the statements as well as the observations are then given to a constraint solver, which computes valuations for the predicates AB i .

Both the MaxSMT and the constraint satisfaction encoding lead to a candidate root cause at line 7, which is exactly where the fault is located. □

Another formula-based approach are error invariants [START_REF] Ermis | Error invariants[END_REF]. Intuitively, an error invariant is a formula φ at a statement st such that the program input and the trace formula constructed from the beginning to st imply φ, and φ and the trace formula from st to the end of the execution does imply false. Inductive error invariants, i.e. error invariants, which hold for several consecutive statements, allow to identify irrelevant transitions in error traces. Afterwards, they are used as an approach similar to [START_REF] Jose | Cause clue clauses: Error localization using maximum satisfiability[END_REF][START_REF] Jose | Cause clue clauses: Error localization using maximum satisfiability[END_REF][START_REF] Lamraoui | A formula-based approach for automatic fault localization of imperative programs[END_REF] to compute a set of suspicious statements. Application to Service Compositions. A first idea for using error invariants for error localization in service compositions is to split abstract symbolic error traces at every service call, use the precondition of the service as assertion to be proven to hold after the split, and the postcondition of the service as additional initial assumption for the next part. This allows to analyze service calls one by one. Nevertheless, a lot of solver calls are necessary to analyze all parts of a service composition this way, and therefore experimental studies need to examine the performance of such an approach. □

An extension of error invariants in order to make fault localization flow sensitive is done in [START_REF] Christ | Flow-sensitive fault localization[END_REF]. Flow-sensitive trace formulas are used to compute suspicious statements with the help of a software model checker and an interpolating theorem prover. In [START_REF] Lamraoui | A formula-based approach for automatic fault localization of imperative programs[END_REF], a full flow-sensitive trace formula is published, which is again analyzed using partial MaxSMT. Clauses of the trace formula, which belong to the control flow are marked as hard and all others are marked as soft. The push & pop mechanism of the solver Yices [START_REF] Dutertre | Yices 2.2[END_REF] yields an efficient solution, which gives quite the same code size reduction as BugAssist but is faster. As flow-sensitive and standard trace formulas are very similar, we think that these approaches are also applicable to service compositions.

Relying on One Faulty and One Correct Input. Delta debugging [START_REF] Zeller | Yesterday, my program worked. today, it does not. why?[END_REF][START_REF] Zeller | Simplifying and isolating failure-inducing input[END_REF][START_REF] Zeller | Isolating cause-effect chains from computer programs[END_REF] is a divide-and-conquer algorithm to compute the smallest difference between a working and a failing test. In [START_REF] Zeller | Yesterday, my program worked. today, it does not. why?[END_REF], delta debugging is applied to changes introduced between the last correct version of a program and the current faulty version. Intuitively, the algorithm splits all existing changes (if it is not only one) into two non-empty subsets and tests, which changes lead to a successful and which changes to an unsuccessful run of the program. Subsequently, the algorithm recursively computes the faulty change in the set of changes that lead to the error. In [START_REF] Zeller | Simplifying and isolating failure-inducing input[END_REF], a very similar strategy is applied to turn test cases into minimal ones, in [START_REF] Zeller | Isolating cause-effect chains from computer programs[END_REF], the delta debugging approach is applied to program states in order to compute the minimal difference between a working and a failing program. Since we typically do not have different correct and faulty variants of a service composition available, this technique seems less applicable to service compositions.

Relying on Several Faulty Inputs. In [START_REF] Könighofer | Automated error localization and correction for imperative programs[END_REF], all faulty inputs and the respective execution traces are encoded into an instance of SAT. The results are used to compute new right-hand sides to assignments in order to correct the program. In service compositions, the right-hand side of assignments are usually service calls, which cannot be modified, just completely replaced. In addition, the meth-ods perform better if there are several faulty inputs, which we typically cannot provide in our setting.

Relying on Several Faulty and Correct Inputs. In this section, we discuss existing error localization approaches, which use several faulty ad several correct tests in order to generate a set of suspicious statements. For a detailed overview on these error localization methods, we refer the interested reader to [START_REF] Agarwal | Fault-localization techniques for software systems: A literature review[END_REF].

Spectrum-Based and Statistical Methods. Tarantula [START_REF] Jones | Visualization of test information to assist fault localization[END_REF][START_REF] Jones | Empirical evaluation of the tarantula automatic faultlocalization technique[END_REF] is a spectrum-based error localization method, which computes the suspiciousness of a statement by comparing the number of successful and failing test cases, in which the statement has been executed. Different methods to compute the suspiciousness of a statement, for example, using the Jaccard or Ochiai distance are discussed in [START_REF] Abreu | An evaluation of similarity coefficients for software fault localization[END_REF][START_REF] Abreu | On the accuracy of spectrumbased fault localization[END_REF]. Statistical methods such as [START_REF] Liblit | Bug isolation via remote program sampling[END_REF][START_REF] Liblit | Bug isolation via remote program sampling[END_REF][START_REF] Liblit | Scalable statistical bug isolation[END_REF][START_REF] Liblit | Scalable statistical bug isolation[END_REF][START_REF] Chen | Pinpoint: problem determination in large, dynamic internet services[END_REF][START_REF] Dallmeier | Lightweight defect localization for java[END_REF]] also rely on successful and failing test cases, but compute the suspiciousness with statistical methods. For example, Pinpoint [START_REF] Chen | Pinpoint: problem determination in large, dynamic internet services[END_REF] uses data mining methods to correlate successes and faults to determine the most likely faulty component. As we neither have tests nor the implementation of services and thus, cannot rely on multiple faulty and correct test inputs, we do not consider those error localization methods as easily applicable to service compositions.

Set-based Methods. Two very simple and common techniques to error localization are introduced in [START_REF] Renieres | Fault localization with nearest neighbor queries[END_REF] and compared to more effective methods like the cause transition approach in [START_REF] Cleve | Locating causes of program failures[END_REF] and the Tarantula approach [START_REF] Jones | Visualization of test information to assist fault localization[END_REF][START_REF] Jones | Empirical evaluation of the tarantula automatic faultlocalization technique[END_REF] in [START_REF] Zhang | Experimental evaluation of using dynamic slices for fault location[END_REF]. The setunion technique computes a set of suspicious statements by removing all statements, which are executed by all passing tests, from the set of statements, which are contained in at least one failed test case. In contrast, the set-intersection technique computes a set of suspicious statements by removing all statements, which are executed in a single failing test case, from all statements, which are executed by every passed test case. As their effectiveness is already very limited on programs, we do not expect them to perform well in service compositions, especially as we do not have successful test cases at hand.

Relying on Model Checking. In [START_REF] Ball | From symptom to cause: Localizing errors in counterexample traces[END_REF], correct traces produced by a model checker are used to localize the error in existing error traces, more specifically, to report one single error trace per error, and to generate multiple error traces for multiple faults. The core of their method is to find transitions in error traces, which do not occur in any correct execution. With respect to service compositions, it could be worthwhile to examine whether there exists services, which do not occur in a correct execution and then, to add the respective service to the set of suspicious ones.

In [START_REF] Groce | Making the most of bmc counterexamples[END_REF], a SAT-based approach relying on CBMC [START_REF] Clarke | A tool for checking ANSI-C programs[END_REF] to minimize counterexamples of model checkers is published. In [START_REF] Groce | Error explanation with distance metrics[END_REF], the difference (in terms of statements) between a correct and a wrong execution is computed and returned to the user as set of suspicious statements. The approach in [START_REF] Groce | Error explanation with distance metrics[END_REF] on a counterexample and then generates program inputs, which do not violate the specification. Again, we consider it worthwhile to investigate, whether the approach can be adapted to work with service compositions.

Remark 2. In general, one distinguishes between control -and data-flow errors. A control flow error, is an error, which can be corrected by changing the predicate of a branch or a loop. As the control-flow of models of service compositions and of standard software do not widely differ and as our example shows, applying standard error localization methods to find control-flow errors in service compositions seems promising.

A data-flow error is an incorrect variable state, which occurs during execution and is caused by wrong assignments. In service compositions, variables are only used to pass data from one service call to another service call. Therefore, the root cause of the data-flow error is likely the service call prior to the failing call. We thus think that the correction of data-flow errors is more promising to investigate than simply finding data-flow errors.

Conclusion and Future Work

In this paper, we have shown that error localization methods for standard software do not carry over to service compositions easily. Especially, the unavailability or at least the lack of test cases as well as the impossibility to execute service compositions at will, render most error localization methods inapplicable. Figure 3 summarizes our findings. It seems that, in general, approaches in the second category (cf. Section 1) are easier to adapt to the setting of models of service compositions than approaches in the first category. The MaxSMT approach, the fully flow-sensitive trace formula approach and the constraint satisfaction approach are adaptable to the service setting by enhancing the respective trace formula by additional predicates, which stem from the pre-and postcondition of the single services as well as the overall service composition. Thus, the application of trace formula approaches seems worthwhile to investigate as similar encodings of traces are already in use for verification of service compositions. As service compositions tend to be small, we do not think that the application of error invariants drastically improves the performance of error localization although the method is applicable in general. Dynamic slicing as in [START_REF] Zhang | Experimental evaluation of using dynamic slices for fault location[END_REF] gathers information during the execution of programs. As we cannot execute services, but statically compute traces, we suspect dynamic slicing to perform as good as static slicing in our context.

We believe that error localization in service compositions might not only support developers in debugging, but might also be useful to speed up automatic configuration approaches for service compositions. Service compositions tend to be simple. Thus, a systematic approach supporting developers might not be necessary, but when it comes to automatic configuration of service compositions, finding errors will help to only reconfigure erroneous parts and not the overall service composition.

As future work, we plan to examine the proposed modifications to the existing software error localization methods and practically evaluate their effectiveness. Most promising seems to be the use of logical formula-based approaches combined with symbolic executions since the interfaces to services are already given as logical formulas (pre-and postconditions), and the structural aspects of service compositions can easily be encoded by logic.

Figure 1 .

 1 Figure 1. The Service Composition GVRes

  Pre are elements of I and all free variables in Post are elements of I ∪ O.

	Definition 2. A service description SD is a tuple SD = (I, O, Pre, Post) such
	that
	-I and O are disjoint sets of input and output variables,
	-Pre and Post are first-order logic formulas, which describe the precondition
	and the effect (postcondition) of the service, respectively.
	All free variables (i.e. all variables not bound by a quantifier) in

  Criteria for Error Localization Methods and Our Choice

	1. # test cases needed	3. multiple fault recognition
	# faulty test cases	#bugs found
	# successful test cases	#bugs
	2. code size reduction #suspicious statements #statements	4. detection of faults by missing code
	Figure 2.

Overview on Properties of the Presented Error Localization Meth- ods.

  only relies Column ACSR shows the Average Code Size Reduction as stated by the respective authors of the approaches, the column test cases states the number and kind of test cases needed, or if even executable code is required. In column app., we summarize the applicability of the approach for service compositions. Column "category" refers to the category, to which the approach belongs with respect to our classification in Section 1. Note that early works give the code size reduction in "percentage of programs yielding percentage of code size reduction".

		ACSR	test cases	app.	category
	MaxSMT Approach	8%	one faulty	✓	2
	Constraint Satisfaction	-	one faulty	✓	2
	Approach
	Fully Flow-Sensitive TF	11%	one faulty	✓	2
	Static Slicing	≈ 30%	-	✓	2
	Error Invariants	-	one faulty	(✓)	2
	Dynamic Slicing	≈ 30%	execution	(✓)	2
	Set Union	1% yield 10% or less	faulty & correct	f	1
	Set Intersection	5.5% yield 10% or less	faulty & correct	f	1
	Delta Debugging with Cause	35.66% yield 10% or less	faulty & correct	f	1
	Transitions (relevant)
	Figure 3.

⋆ This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Centre "On-The-Fly Computing" (SFB 901).

https://www.w3.org/TR/wsdl

The SMT solver underlying the verification technique in[START_REF] Walther | Knowledge-based verification of service compositions -an smt approach[END_REF] treats all service calls and types as undefined function symbols, and thus returns just some randomly chosen identifier for instance of these symbols.


Kyriakos Kritikos
email: kritikos@ics.forth.gr

Dimitris Plexousakis

Subsumption Reasoning for QoS-based Service Matchmaking

Keywords: service, matchmaking, discovery, QoS, ontology, subsumption

Service-orientation has revolutionized the way applications are constructed and provisioned. To this end, a proliferation of web services is being increasingly available. To exploit such services, an accurate service discovery process is required with a suitable performance focusing both on functional and quality of service (QoS) aspects. In fact, QoS is the main distinguishing factor for the plethora of functionally-equivalent services available in the internet. Accuracy in service discovery comes via exploiting formal techniques and ontologies in particular. Satisfactory performance levels can be reached via using smart methods that intelligently organise the service advertisement space. In this paper, we propose smart ontology-based QoS-aware service discovery algorithms that exploit ontology subsumption as a means of matching QoS requests and offers. These algorithms exploit a variety of methods to structure the service advertisement space. Based on the empirical evaluation conducted, our proposed algorithms outperform the state-of-the-art in certain circumstances. To this end, ontology-based subsumption is indeed a promising technique to realise QoS-based service matchmaking.

Introduction

Service-orientation has revolutionalized the way web applications and processes are constructed, provisioned and evolved. With the advent of cloud computing, which delivers extra advantages, a proliferation of available services has been achieved covering various types of functional capabilities. To exploit such services and rapidly build added-value functionality, there is a need for accurate and fast service discovery algorithms focusing both on functional and quality-of-service (QoS) aspects. The state-of-the-art in functional service discovery exploits either ontology-based [START_REF] Sycara | Dynamic Discovery and Coordination of Agent-Based Semantic Web Services[END_REF], information retrieval [START_REF] Dong | Similarity search for web services[END_REF] or a mixture of such techniques [START_REF] Plebani | URBE: Web Service Retrieval Based on Similarity Evaluation[END_REF] to perform service matching. It has been proven that only when ontology-based techniques are involved [START_REF] Plebani | URBE: Web Service Retrieval Based on Similarity Evaluation[END_REF], higher accuracy levels can be attained.

However, functional service discovery alone cannot enable the service designer to discover those services satisfying all requirement aspects. On the contrary, QoS has been deemed as the aspect enabling the differentiation between the plethora of functionally-equivalent services currently available. In fact, QoS can play a significant role in all phases of the service lifecycle [START_REF] Kritikos | A survey on service quality description[END_REF]. To this end, various types of QoS-based service discovery approaches have been proposed. To increase the accuracy in the service discovery results, some of these types do exploit either ontology-based techniques [START_REF] Zhou | DAML-QoS Ontology for Web Services[END_REF] alone or constraint solving techniques as well [START_REF] Kritikos | Requirements for QoS-Based Web Service Description and Discovery[END_REF]. Those approaches exploiting solely ontology-based techniques use ontology-based subsumption to perform the matching but have relied on wrong ontology constructs to specify QoS-based service specifications. As such, their applicability is quite limited. On the other hand, mixed-based approaches have a wider applicability and have been shown to exhibit much better performance.

In this paper, we propose a pure ontology-based approach which exploits ontologies in a correct way via more suitable constructs enhancing the respective applicability. In addition, we propose smart algorithms which intelligently organise the service offer space so as to perform service matchmaking via ontology subsumption on a subset of all offers. By considering the two main disadvantages of a mixed-based approach which are the ontology to constraint specification transformation and the solving of multiple constraint models to infer the matching between a pair of a service QoS offer and demand, our empirical evaluation shows that our proposed algorithms outperform mixed-based state-of-the-art ones in certain circumstances. This is a proof that ontology subsumption alone can be considered as a promising technique for QoS-based service matchmaking.

The rest of the paper is structured as follows. Section 2 reviews the related work. Section 3 provides background knowledge enabling to better understand the paper propositions. Section 4 analyses the proposed approach and the algorithms realising it. Section 5 discusses the experimental evaluation results. Finally, Section 6 concludes the paper and draws futher research directions.

Related work

QoS-based service description

A plethora of languages have been proposed for describing QoS-based offers and requests. According to the survey in [START_REF] Kritikos | A survey on service quality description[END_REF], these languages can be distinguished according to their formality, expressiveness and complexity. From these languages, OWL-Q [START_REF] Kritikos | Semantic qos metric matching[END_REF], a modular and semantic-based service description language, seems to be the most promising, especially in terms of expressiveness as it covers in a rich manner all possible aspects of QoS-based service description. Based on OWL-Q, a mid-level ontology is available which provides a common vocabulary of QoS terms which can be used to populate QoS-based service specifications, such as domain-independent QoS attributes and metrics (e.g., response time). Due to the above unique advantages, the approach proposed in this paper exploits OWL-Q along with its mid-level ontology.

QoS-based service discovery

Various QoS-based service matchmaking approaches have been proposed that can be categorised in three main types. Ontology-based approaches [START_REF] Zhou | DAML-QoS Ontology for Web Services[END_REF] rely on ontology subsumption to perform the service specification matching. These approaches are able to support only unary-based service specifications, i.e., involving one QoS term per constraint (QoS capability or requirement). Constraintbased approaches [START_REF] Cortés | Improving the Automatic Procurement of Web Services Using Constraint Programming[END_REF] assume the existence of a common QoS term vocabulary through which constraint models can be specified mapping to the actual service QoS offers and requests. Then, they exploit constraint solving techniques and specific matchmaking metrics to perform the matching of the constraint models. In comparison to ontology-based approaches, constraint-based ones operate over n-ary specifications and have a much better performance. Finally, mixed based approaches [START_REF] Kritikos | Requirements for QoS-Based Web Service Description and Discovery[END_REF] attempt to exploit the best of both worlds. This means that they operate over semantic QoS specifications by first aligning them according to their QoS terms and then transforming them into constraint models which can then be matched based on the second type of approaches. In comparison to the former two types, this type can operate on n-ary specifications, it exhibits better accuracy levels due to the alignment of the specifications that goes beyond using subsumption reasoning and exhibits almost equivalent performance levels with respect to the constraint-based approach type.

Apart from the above approach categorisation, recently some new mixed approaches [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF] have been proposed able to speed up the service matching time by cleverly organising the QoS service offer space. These approaches create a QoS offers subsumption hierarchy. As such, when a QoS request subsumes a hierarchy node, it subsumes all its descendants. Thus, these descendants do not have to be matched with the QoS request and matching time gets reduced.

The approach proposed in this paper belongs to the first type. As such, it suffers from the disadvantage of handling only unary constraints. However, this disadvantage is not crucial as most, if not all, of existing QoS service specifications in the real world are unary. Moreover, to speed up the matchmaking time, we propose different algorithms which attempt to similarly organise the offer space as in the recent approaches. In this way, we do not only reduce the matchmaking time but are able to outperform these recent approaches in certain cases for the following two reasons: (a) our approach does not require transforming ontology-based QoS specifications to a different form and (b) ontology subsumption can be faster than constraint-based matching even for a pair of a QoS offer and demand due to the way constraint matching metrics are realised. Thus, the use of pure ontology-based approaches in QoS-based service matching is not only feasible but also quite practical in certain cases. We believe that the prospective practitioners will benefit from the proposal and findings of this paper.

Background

In this section, we first explain why the current realisation of the pure ontologybased approach type is not appropriate and what is our proposal for solving Fig. 1: The example QoS offer in different forms this issue. Then, we highlight what is the process for adding and matching QoS offers for both ontology-based approach types as this paper focuses on their comparison.

Realisation Issues

Suppose we have the example QoS offer in Figure 1.A in QRL [START_REF] Cortés | Improving the Automatic Procurement of Web Services Using Constraint Programming[END_REF]-like syntax indicating that average response time will be less or equal to 10 and greater than 2 seconds while average throughput will be between 100 and 120 requests per second inclusive. In the pure ontology-based approach type, the two metrics will originate from a mid-level ontology specifying domain-independent QoS terms. Indeed, this is the case of the approach in [START_REF] Zhou | DAML-QoS Ontology for Web Services[END_REF] which maps both metrics to subclasses of CompositeMetric, thus connecting the upper-level ontology proposed to the mid-level one. However, the latter approach will then rely on a misuse of OWL cardinality constraints to specify the constraints of the specifications as indicated in Figure 1.B. In particular, it will indicate that the cardinality of the value-based properties (e.g., responseTime) of these metrics will be in accordance to the ranges in Figure 1.A. This wrong QoS constraint modelling has two main disadvantages: (a) only a specific type of QoS terms can be addressed mapping to non-negative integers -as such, terms like availability cannot be catered as their value types map to real numbers; (b) this modelling can also lead to an error that is at maximum one-half of the QoS term unit. Apart from the wrong modelling, the respective QoS ontology language exploited is quite limited with respect to the capabilities and richness of OWL-Q.

The above modelling issue is solved via the rationale in Figure 1.C. While there are again terms mapping to a composite metric class, we actually restrict the range of the value datatype property for them based on the desired limits. As such, we can model different value types for these terms; either concrete XSD 1 types (e.g., integer ) or specialisations of them (e.g., constrained integers). By also exploiting OWL-Q, our QoS modelling is correct, richer and more extensive. Fig. 2: The QoS demand and the 4 matchmaking problems However, there is still a specific issue. Subsumption reasoning caters mainly for positively monotonic QoS terms. This can be understood from the example QoS demand in Figure 2.B which needs to be matched with the aforementioned QoS offer. While it is apparent that the QoS offer is more specific than the QoS demand and there is a match, the average response time is a negatively monotonic metric. As such, any ontology reasoner will never infer that the QoS offer is subsumed by the QoS demand.

The solution to this problem is to negate the constraints on negatively monotonic metrics. This is equivalent to considering a new, positively monotonic term equal to the negation of the original term. In this way, both the QoS offer and demand will be expressed as in Figure 1.D and 2.B and their matching will be derived through an ontology reasoner, like Pellet2 [START_REF] Sirin | Pellet: A practical OWL-DL reasoner[END_REF]. This treatment of QoS specifications has the following alternative concequences: (a) either the modeller should specify the QoS constraints as well as the QoS terms in the newly prescribed way taking special case on negatively monotonic terms or (b) the respective tools enabling the editing of the QoS specifications should be realised to transform internally the modeller constraints in the appropriate format or pre-processing of QoS specification via transformation tools is performed before the actual registration or matching of the specification is performed.

Ontology-based QoS Specification Management Process

In a pure ontology-based approach, the QoS offer management process is quite simple. The existence of a semantic repository is assumed where the support for a specific ontology language like OWL is offered. Obviously, on top of OWL, a QoS-based service description language like OWL-Q lies via which the offers are actually specified. As indicated in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF], a mixed-based approach requires a QoS term (needed for their alignment) and a constraint model repository. As such, extra storage requirements are imposed.

QoS Offer Registration. In an ontology-based approach, QoS offers to be registered are first loaded in order to check whether they are consistent. This maps to creating a small knowledge base (KB) out of this offer and checking with this KB is consistent by evaluating whether any concept is subsumed by OWL Nothing. In a mixed-based approach, apart from consistency checking, the ontology needs first to be realised and validated and then to be transformed into a constraint model. Thus, it is expected that the offer registration time is faster in an ontology-based approach.

By considering the previous sub-section's example, the mixed-based approach will map the QoS offer in Figure 1.B into a constraint model similar to that of Figure 1.A where each unique QoS term will be mapped to a specific variable.

QoS Request Matching. A QoS request passes the same sub-process when issued as it must be checked for consistency. Then, it must be matched with all the QoS offers stored in the respective repository. In the pure ontology-based approach, the QoS request is entered into the existing KB and then classification is performed such that all subsumption relations are discovered between this request and all QoS specifications. As such, the QoS request is matched with all QoS offers that it subsumes. Please note that matchmaking as conformance or subsumption is the main matching metric in all approach types.

For the rest of the approach types, there is a matching of two constraint models mapping to the QoS request and offer when the solution space of the latter is included in the solution space of the former. This is translated in solving one or more constraint problems depending on the constraint arity of the QoS specifications. In case of unary constraints, specification conformance maps to checking M (mapping to the offer's number of constraints) constraint problems constructed by the offer's constraint model and a negation of each demand's constraint. If all problems are infeasible, then there is a match between the QoS offer and request. In case of n-ary constraints, only one constraint problem needs to be solved constructed from the QoS offer and the negation of the QoS demand. A match is inferred if the latter problem is infeasible. In the first case, more steps must be performed with respect to the pure ontology-based approach whose timing depends on the number of constraints involved. In the second case, one complicated step is performed but has no counterpart in the pure ontologybased approach as the latter can address unary constraints only.

In a mixed-based approach, the QoS request of the previous subsection will be first mapped to the constraint model in Figure 2.D. Then, four constraint problems need to be solved as depicted in Figures 2.C and 2.F.

Proposed Approach

Architecture

Figure 3 depicts the proposed approach architecture by visualising both the respective components and their interactions. There are five main components involved. The Semantic Repository is an ontology-based repository able to store Fig. 3: Non-Functional Service Matchmaking System Architecture all QoS offers. The Matcher is a web service (WS) taking as input a QoS request which is then matched with all QoS offers stored. This WS internally realises one or more matching algorithms so it can be configured to operate based on one of them. The Publisher is also a WS enabling service providers to publish their QoS offers in the semantic QoS-based matchmaking system. Similarly to Matcher, it can be configured to operate a specific (de-)publication algorithm mapping to the approach followed for matchmaking. The semantic QoS-based matchmaking system currently operates solely on OWL-Q based specifications. In the future, it will include extra transformation functionality to support original specifications in different QoS-based service specification languages which will be injected in the Transformer 's existing capabilities. Distribution of content will also be examined to cater for better scalability levels. Due to the nature of the proposed algorithms, such distribution is quite easy and natural to realise without any implication on algorithm accuracy.

Algorithms

In the following, we are going to analyse the four main algorithms that we have realised and are included in the capabilities of the Matcher component. We focus on the two main processes supported: QoS offer registration and QoS request matching. For each algorithm, the presentation starts with the main rationale, it then explicates the way the offer space is organised, next the algorithm core is analyzed and finally its complexity analysis is supplied.

Naive Rationale. The main rationale of the algorithm, also justifying its name, is to load all offers on memory when a specific matching request is issued. This facilitates an offer's registration as once its consistency is checked, it is just stored in the repository. However, it is expected that matching time will not be appropriate as it has been proven that subsumption reasoning does not scale well, especially if done in a centralised manner. In fact, as OWL-Q along with its mid-level lies in the SROIQ(D) family of ontologies, any reasoning task is decidable but NExpTime-Hard.

Offer Space Organisation. There is no special offer space organisation. Only one specific hash set is employed to account for the URIs of the offers stored such that they can be immediately located and loaded during request matching.

Algorithm Core. The algorithm's core does not differ with respect to that sketched in Section 3. Initially, a KB is constructed out of all QoS offers and the QoS request and then classification is performed. Finally, a query on the KB is performed to obtain all offers subsumed by the request.

Complexity Analysis. Suppose that a specification usually has 4-5 QoS terms and 4-5 constraints on them, all wrapped into a single class definition. As such, we expect that the specification loading time will be more or less constant and equal to L spec . Thus, the time needed to check the request's consistency (similar as loading) as well as construct a KB out of N offers and 1 QoS request will be O (L spec * (N + 2)). If we further assume that the time to classify N + 1 specifications is S N +1 , such that the classification depends on the specification number, the overall matching time would be O (L spec * (N + 1)) + S N +1 . We expect that usually O (S N +1 ) takes much longer than O (L spec * (N + 2)), especially when the specification number becomes bigger, so we will have a final complexity of O (S N +1 ) for matchmaking. Offer registration, on the other hand, takes O (N * L spec ) time as each offer is just loaded and checked for consistency.

Incremental Rationale. The naive approach does not incrementally build the KB but constructs it on demand. As such, as incremental classifiers are available, it might be better to employ incremental classification to save time when classifying a temporal extension of the KB encompassing the request.

Offer Space Organisation. The previous algorithm's hash set is preserved to account for the offers already stored. KB is the other organisation medium constantly updated. The classification tree constructed contains all possible subsumption connections between the specifications involved.

Algorithm Core. During offer registration we discovered that it is a little bit costly to run classification each time an offer must be registered. As such, we run classification only every X offers, where X is a configuration parameter for the algorithm. In each registration, the offer is loaded, checked for consistency and then stored in the KB.

For request matching, after consistency checking, we temporarily include the request in the KB and then we perform incremental classification. We then query the KB to find the offers subsumed by the request.

Complexity Analysis. Suppose that S Y X is the incremental classification time when X specifications are added to the KB and Y specifications are already loaded. Then, the offer registration time for N offers will be

O L spec * N + N X Y =1 S Y * X X .
On the other hand, the request matching time will take at most O L spec + S N 1 as we will have to check the request consistency and incrementally classify only the temporal addition of the request in the existing KB.

Subsumes Rationale. As a naive approach does not scale well in practice and driven by the fact that even the incremental algorithm might also exhibit similar performance problems, we decided to rely on the method in the SubMIPMM algorithm [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF] and create our own subsumes offer hierarchy to be matched against any issuing request. In such hierarchy, if the request subsumes a node, then it also subsumes its descendants so some comparisons are avoided.

Offer Space Organisation. We do not construct a complete subsumes hierarchy as this requires connecting a new offer to all parents that subsume it and the registration time would be highly increased. The main trick as followed in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF] is to connect the offer to the first tree in the hierarchy forest in which it is matched.

Algorithm Core. The registration process is simple. We first match the new offer with all hierarchy's top offers. In case of a match, we check subsumption direction. If the new offer subsumes one or more top nodes, it becomes a top node itself and the matched nodes its children. If the offer is subsumed by one or more top nodes, we take the first one and check where to place the new offer in its own tree. So, the same matching procedure is followed until either the new offer subsumes some nodes in the selected tree or becomes this tree's leaf.

Concerning request matching, we match the request with all top-nodes in the subsumption hierarchy. In case the request subsumes a top-most node, we add this node along with its descendants in the matching offers set. Otherwise, we need to go down a top-most node's subtree similarly to the way top-matching is performed to find matching offers. The latter is due to the fact even if the request does not match the top-node, as we descend the tree, the offers becomes stricter with a smaller solution space and thus the probability that they finally match the request becomes higher.

For both processes, if pair-wise subsumption reasoning takes less than pairwise constraint-based matching, this algorithm will be faster than SubMIPMM.

Complexity Analysis. Concerning offer registration, we need first to check offer consistency. Then, different cases can occur. In the best case, the offer is equivalent to the first top-most node so we do not need to check anything else. The time complexity will then become: O (L spec + S 2 ). In the worst case, the hierarchy maps to a tree and we have to put the new offer as a child of the rightmost leaf node. This means that we will have to compare the new offer with all offers stored. In this case, the time complexity is O (L spec + N * S 2 ) which can be reduced to O (N * S 2 ). In the average case, B trees more or less balanced will exist and the time complexity will become:

O L spec + N +B 2 2 * B * S 2 which can be reduced to O N +B 2 2 * B * S 2 .
Different cases map to request matching. The best one occurs when the hierarchy maps to a tree and the request subsumes the root node. The time complexity will be: O (L spec + S 2 ). The worst case occurs when the request must be compared with all tree nodes (as it does not subsume any offer or just the rightmost leaf one). The time complexity will be: O (L spec + N * S 2 ) which can be reduced to O (N * S 2 ). In the average case, we assume that P offers will be subsumed and that there will be at least a two-level hierarchy between the subsumed offers. As such, the time complexity will be

O L spec + N * 1 -P 2 * S 2 ) which is reduced to O N * 1 -P 2 * S 2 ) .
SubsumesFrag Rationale. The previous algorithm constructed the hierarchy in an incremental manner and used ontology-based reasoning only when pair-wise comparisons of specifications were performed. As many pair-wise comparisons may have to be made, the current algorithm's rationale is to construct a bigger KB involving C specifications and not just 2 as we expect that this will take less time than having to reason over C -1 KBs of size 2 (if we assume that always the first specification is constant, i.e., the request). Moreover, we use incremental classification to construct the offer hierarchy as this might be deemed better than having to construct this hierarchy in a pair-wise manner. As such, we expect that this algorithm will be faster than the previous one. Algorithm Core. In offer registration, for each X offers stored, we perform incremental classification over the KB and store the classification hierarchy in main memory. Rationale is again that it is better to incrementally do this every time a specific number of incoming offers is issued rather than running incremental classification on-demand for each incoming offer to be registered.

Matchmaking follows a similar rationale as in the previous algorithm. The sole exception lies on the fact that now the classification is more complete but also contains new offers (less than X) that have not yet been classified and are considered top-nodes. Due to the classification completeness, we also need to keep track of the nodes visited so as not to revisit them again. The matching process starts by matching the top-nodes in the classification hierarchy in chunks of C nodes each time (see Rationale paragraph). If a top-node is subsumed, we do not follow its descendants but just add them in the matching offers set. We also mark this node and its descendants as visited. Otherwise, we need to go down the top-node's tree to find matches again similarly to top-node matching.

Complexity Analysis. Offer registration is equivalent to the case of the incremental classification algorithm. Thus, its time complexity is:

O L spec * N + N X Y =1 S Y * X X .
Request matching has 3 cases. In the best case, the request matches a left topnode in the 1st subsumption chunk taking: O (L spec + S C ). In the worst case, we must match the request with all nodes. This takes O L spec + N C * S C , further reduced to O N C * S C . In the average case, we make the same assumptions as in previous algorithm. The time complexity is:

O L spec + N * (1-P 2 ) C * S C , further reduced to O N * (1-P 2 ) C * S C .

Experimental Evaluation

The experimental evaluation aims at comparing the proposed algorithms with the subMIPMM mixed-based one to identify cases that these algorithms prevail. This evaluation relied on the experimental framework in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF]. It also exploits the second real dataset from WS-Dream collection [START_REF] Zhang | WSPred: A Time-Aware Personalized QoS Prediction Framework for Web Services[END_REF] and one randomly constructed in a controlled manner. The main comparison metric is average execution time for both registration and matchmaking. Accuracy has not been considered as all algorithms are perfect in this aspect [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF] by completely realising the matchmaking metric of specification conformance [START_REF] Cortés | Improving the Automatic Procurement of Web Services Using Constraint Programming[END_REF]. In the following, we first shortly explain the way experiments have been performed and then present each experiment's results along with their respective analysis.

Please note that Pellet was used for ontology subsumption in the algorithms while the Ibex constraint solving framework (www.ibex-lib.org/) was exploited for constraint matching in SubMIPMM.

Experiment Set-Up

All experiments were performed in a laptop with a 64bit OS, a 6GB main memory and a multicore CPU of 2.4GHz frequency. For each experiment, we have conducted a series of steps to produce the respective average measurements of the algorithms considered. Each step maps to specific fixed or dynamic values of the control parameters and a series of 30 runs from which the average was calculated in order to alleviate for interferences at the OS level.

Real or randomised input was used in the experiments. In case of WS-Dream dataset, depending on the offer number (given as a control parameter value), we randomly selected an equal number of measurements from around 4500 available ones which were transformed into respective ontology-based offers mapping to the two main terms exploited, i.e., response time and throughput. The corresponding request was randomly selected again from the 4500 measurements. In case of the randomised dataset, the offers were randomly created based on current values of the control parameters. More details about this can be found in [START_REF] Kritikos | Novel Optimal and Scalable Nonfunctional Service Matchmaking Techniques[END_REF]. The respective randomised request was constructed again based on the control parameter values so as to match a specific percentage of offers.

1st Experiment

In this experiment, we exploited the randomised dataset and considered that half of the offers will be matched by each request issued. The number of offers was linearly increasing from 40 to 640 with a step of 100. The respective experiment results are visualised in Figs. 4a and4b.

Concerning matching time, it is clear that SubMIPMM algorithm is the best, followed by Subsumes. SubsumesFrag comes next while in the end we have Incremental and Naive. These matchmaking results were not expected especially between the two ontology-based subsumes algorithms while SubMIPMM prevailance possibly indicates that there is a bound in the variable number always shows registration time results for 1st experiment leading to constraint-based matchmaking being faster than ontology subsumption. Please note that there is a speedup with respect to incremental reasoning which is not great as the removal of a previous request and the addition of a new one (based on the way the experiment was conducted) in the existing KB requires performing subsumption over a great number of offers.

Concerning registration time, it was obvious that Naive will be the best while subMIPMM the last. However, the second expectation was not realised as there is a specific breakpoint in SubsumesFrag performance because incremental reasoning is not efficient due to the nature of specifications and subsumption's exponential complexity. The order change between Subsumes and SubMIPMM is due to the fact that the latter performs two (complex) constraint solvings per comparison in registration in contrast to just one for matchmaking while obviously the former performs just one classification per comparison constantly.

2nd Experiment

In this experiment, we exploited again the randomised dataset with almost similar control parameter values but: (a) the offer number is now constant (300) and (b) we linearly increase the QoS term number in the specifications from 10 to 60 with a step of 10. Our main goal is to show that as the QoS term number increases, the constraint number in each QoS specification also increases; as such the number of constraint problems to be solved by subMIPMM also increases. In this sense, we expect that there will be a specific bound on the QoS term number beyond which subsumption reasoning will be quicker than pair-wise constraint-based matching. Fig. 5 shows the experiment results.

Concerning matching time, the results are in accordance to the previous experiment ones for the same initial variable number. However, as soon as the variable number goes to 20, we clearly see that SubMIPMM 's performance gets worse and less than that of the ontology-based subsumes algorithms whose performance order is not altered throughout the experiment. The order between Naive and Incremental is also not altered with respect to the previous experiment, something quite expected.

Concerning registration time, it is clear that SubMIPMM is the worst algorithm as it has to increasingly solve a much higher number of constraint problems per offer registration when the number of QoS variables and respective constraints increases. The order between the two ontology-based subsumes algorithms is almost the same which is evident also by the theoretical complexity analysis. As in the previous experiment, the order and performance of the rest of the ontology-based algorithms is not modified.

3rd Experiment

In this experiment, we exploit the real dataset and increase the offer number from 100 to 600. So, similar settings as in 1st experiment apply with two exceptions: (a) the QoS term number is 2 and not 10; (b) it is expected that the QoS offer number to be matched is small and thus much more work is expected for all subsumes-based algorithms. The main goal is to stress-test the algorithms in real situations and inspect whether the last algorithm can outperform the rest as it will have to perform less subsumption checking pieces of work. Figs. 6a and 6b visualise the respective results.

Concerning matching time, the results validate the complexity analysis as all subsumes algorithms exhibit a linear behaviour while the rest an exponential one. We also see a difference with respect to the 1st experiment results as a much better algorithm performance is exhibited. This can be possibly due to the fact that the variable number is less so each matchmaking piece of work takes less shows registration time results for 3rd experiment time. In addition, we now see that SubMIPMM is worse than the ontology-based approaches from which Subsumes is still the best. Concerning registration time, the results are expected based on our assumptions as SubsumesFrag is the best among all subsumes algorithms followed by Subsumes and then SubMIPMM. The behaviour of SubsumesFrag and Incremental coincides, as expected. Obviously, the Naive algorithm has constantly the best performance in all experiments according to this aspect.

Two main derivations must be highlighted from the above results: (a) a smart ontology-based approach can outperform a constraint-based one under real circumstances and (b) Subsumes seems to be the best algorithm in the long run for both registration and matchmaking -this can be seen from the breakpoint at 500 in the x-axis for registration beyond which this algorithm is better than SubsumesFrag. The latter also reveals the main weakness of even an incremental reasoner due to the nature of the specifications that it has to address and the exponential complexity in subsumption.

Conclusions

This paper has presented a pure ontology-based approach in QoS-based service matchmaking. This approach is realised by a naive and two clever algorithms which intelligently organise the service advertisement space. The latter two algorithms significantly outperfom the naive one in matching time and even compete with recent state-of-the-art QoS-based service matching algorithms. This is clearly shown in the randomised and realistic experimental evaluation where the cases in which our novel algorithms prevail are detected. Based on our propositions and findings, we showcase that a pure ontology-based approach when assorted with smart algorithms and techniques can really compete with other QoS-based service matching approach types. So, we provide guidance to practitioners under which circumstances an ontology-based approach can be exploited.

Concerning future work, the following directions are planned. First, further investigation of new algorithms which more cleverly organise the advertisement space. Second, checking the modification of the normal subsumption reasoning process in order to cater for: (a) not requiring the modification of negatively monotonic QoS terms to positive ones and (b) for more cleverly matching QoSbased service specifications. Third, performing a more thorough evaluation with the state-of-the-art to detect additional cases where a pure ontology-based approach should be recommended. Fourth, coupling the novel approach proposed with a semantic functional matchmaker in order to realise a complete ontologybased service discovery system. Such coupling could also lead to cleverly and concurrently organising and matching the offer space according to both specification aspects to further speed up the overall matchmaking time.

  Both the Publisher and Matcher exploit two other components: (a) the Transformer which loads the specification and then transforms the constraints for negatively-monotonic terms, when users do not model them as expected; (b) the Reasoner which performs different types of tasks: (a) ontology-based specification validation, (b) pair-wise specification comparison and (c) (incremental) subsumption over full repository content. Invalid specifications are returned back to their issuers with a suitable error message.

Fig. 4 :

 4 Fig. 4: Fig. (a) shows matching time results for 1st experiment while Fig. (b) shows registration time results for 1st experiment

Fig. 5 :

 5 Fig. 5: Fig. (a) shows matching time results for 2nd experiment while Fig. (b) shows registration time results for 2nd experiment

Fig. 6 :

 6 Fig. 6: Fig. (a) shows matching time results for 3rd experiment while Fig. (b) shows registration time results for 3rd experiment

http://www.w3.org/TR/xmlschema11-1/

https://github.com/Complexible/pellet/

Acknowledgments This research has received funding from the European Community's Framework Programme for Research and Innovation HORIZON 2020 (ICT-07-2014) under grant agreement number 644690 (CloudSocket).