Sabrina De Capitani

Di Vimercati

Sara Foresti

Privacy of Outsourced Data

Data outsourced to an external storage server are usually encrypted since there is the common assumption that all data are equally sensitive. The encrypted data however cannot be efficiently queried and their selective release is not possible or require the application of specific solutions. To overcome these problems, new proposals have been recently developed, which are based on a fragmentation technique possibly combined with encryption. The main advantage of these proposals is that they limit the use of encryption, thus improving query execution efficiency. In this paper, we describe such fragmentation-based approaches focusing in particular on the different data fragmentation models proposed in the literature. We then conclude the paper with a discussion on some research directions.

Introduction

Data outsourcing is emerging today as a successful paradigm allowing individuals and organizations to exploit external services for storing, managing, and distributing huge collections of possibly sensitive data. Within a data outsourcing architecture, data are stored together with application front-ends at the sites of an external server who takes full charges of their management. Although publishing data on external servers may increase service availability, reducing data owners' burden of managing data, it introduces new privacy and security concerns. As a matter of fact, the outsourced data are no more under the control of their data owners and therefore their privacy as well as their integrity may be put at risk. The protection of the privacy of the data is however of paramount importance and is becoming an emerging problem as it is also testified by a number of recent regulations that require organizations to provide privacy guarantees when storing, processing, and sharing sensitive information (e.g., California Senate Bill 1386 and the Personal Data Protection code -legislative decree no. 196/2003). Existing approaches (e.g., [START_REF] Damiani | Balancing confidentiality and efficiency in untrusted relational DBMSs[END_REF][START_REF] Ceselli | Modeling and assessing inference exposure in encrypted databases[END_REF][START_REF] Hacigümüş | Executing SQL over encrypted data in the database-service-provider model[END_REF][START_REF] Hacigümüş | Providing database as a service[END_REF]) for protecting the privacy of outsourced data assume that an overlying layer of encryption is applied on the data before outsourcing them, which implies that the outsourced data cannot be efficiently queried and that a selective release (i.e., different pieces of information to different parties) is either not possible or require the application of specific solutions based on two layers of encryption [START_REF] Vimercati | Over-encryption: Management of access control evolution on outsourced data[END_REF][START_REF] Vimercati | Encryption policies for regulating access to outsourced data[END_REF]. Recently, novel proposals have been developed, where encryption is not mandatory for ensuring protection [START_REF] Aggarwal | Two can keep a secret: a distributed architecture for secure database services[END_REF][START_REF] Ciriani | Fragmentation and encryption to enforce privacy in data storage[END_REF][START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF]. This introduces a paradigm shift that permits to address the protection issue with a different perspective, thus giving the possibility of designing novel models and techniques where the use of encryption is minimized or is absented. These proposals are based on the observation that often what is sensitive is the association among data more than the data per se. For instance, in a hospital the list of illnesses cured and the list of hospitalized patients could be made publicly available, since what is sensitive is the association of a specific illness to a patient. Although this association must be protected, it is not necessary to encrypt both the list of illnesses and the list of hospitalized patients; it is sufficient to prevent their joint visibility to non authorized users.

In this paper, we illustrate recent proposals for protecting outsourced data that are based on the use of fragmentation possibly combined with encryption. The remainder of this paper is organized as follows. Section 2 introduces the basic scenario and concepts on which all the fragmentation-based proposals rely on. Section 3 describes an approach based on the combination of fragmentation and encryption and where the outsourced data are stored at two non-communicating pair of servers. Section 4 presents an approach where again fragmentation and encryption are used in combination and where outsourced data can be fragmented among multiple unlinkable fragments. Section 5 illustrates a proposal that departs from encryption and where a small portion of the data is stored at the data owner side. Section 6 presents some open issues for the considered scenario. Finally, Section 7 concludes the paper.

Scenario and basic assumptions

We consider the problem of outsourcing data while preserving their privacy. Current approaches in the literature assume that a single relation r over relational schema R(a 1 , . . . , a n ), with a i an attribute on domain D i , i = 1, . . . , n, contains all sensitive information that needs to be protected [START_REF] Aggarwal | Two can keep a secret: a distributed architecture for secure database services[END_REF][START_REF] Ciriani | Fragmentation and encryption to enforce privacy in data storage[END_REF][START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF]. Note however that the techniques that will be described in the following can also work with other data models. The privacy requirements are instead modeled through confidentiality constraints. A confidentiality constraint c over a relational schema R(a 1 , . . . , a n ) is a subset of attributes in R1 (c ⊆ R) meaning that for each tuple in r, the (joint) visibility of the values of the attributes in c is considered sensitive and must be protected. While simple, the definition of confidentiality constraints captures different protection requirements. In particular, depending on the attributes involved, confidentiality constraints can be classified in the following two categories.

-Singleton constraints. A singleton constraint states that the values assumed by the attribute in the constraint are considered sensitive and cannot be released (e.g., the SSN of the patients in a hospital is considered sensitive). -Association constraints. An association constraint states that the association among the values of the attributes in the constraint is considered sensitive and cannot be released (e.g., the association of the name of patients with their illnesses must be protected).

Since the satisfaction of a confidentiality constraint c i implies the satisfaction of any constraint c j such that c i ⊆c j , a set C = {c 1 , . . . , c m } of confidentiality constraints is supposed to be well defined , that is, ∀c i , c j ∈ C, i = j, c i ⊂ c j .

Example 1. Figure 1 illustrates an example of relation (Patient) along with a set of well defined confidentiality constraints, modeling the following privacy requirements:

the list of SSNs of patients is considered sensitive (c 0 ); the association of patients' names with any other information in the relation but the job is considered sensitive (c 1 , . . . , c 4 ); attributes DoB and ZIP can work as a quasi-identifier [START_REF] Samarati | Protecting respondents' identities in microdata release[END_REF] and therefore can be exploited to infer the identity of patients; their associations with both Illness and Physician are then considered sensitive (c 5 and c 6 ); the association between Job and Illness and the association between Job and Physician are considered sensitive (c 7 and c 8 ).

Note also that the association of patients' Name and SSN is sensitive and should be protected. However, such a constraint is redundant, because SSN has been declared sensitive (c 0 ): protecting SSN as an individual attribute implies automatic protection of its associations with any other attribute.

Given a relation r over schema R(a 1 , . . . , a n ) and a set C of confidentiality constraints over R, the goal is to outsource the content of r in such a way that the sensitive associations represented as confidentiality constraints are protected. The approaches proposed in the literature for addressing such a problem are typically based on a possible combination between fragmentation and encoding techniques. Fragmentation consists in partitioning the attributes in R in different subsets (fragments), which are then outsourced in place of R. Formally, a fragment F i of a relation R is defined as a subset of the attributes in R (F i ⊆ R), while a fragmentation F is a set of fragments over R (i.e., F = {F 1 , . . . , F m }). The set of tuples of relation r over R projected on the attributes in F i is a fragment instance over F i . Intuitively, fragmentation protects sensitive associations by breaking them. Encoding means that the values of some attributes are obfuscated to make them readable only by authorized users. Although different encoding techniques can be adopted [START_REF] Aggarwal | Two can keep a secret: a distributed architecture for secure database services[END_REF], we only consider encryption as an encoding technique. The approaches in the literature then differs in how the original relational schema R is fragmented to avoid the joint visibility of attributes involved in constraints and in how and whether encryption is used. In particular, existing approaches for enforcing confidentiality constraints can be partitioned into three different categories:

non-communicating pair of servers, when R is partitioned into two fragments stored on two non-communicating servers and encryption (or another encoding technique) is used for protecting attributes when they cannot be stored in the two fragments without violating the constraints; multiple fragments, when R is partitioned into two or more disjoint fragments, possibly stored on the same server, and encryption is used within each fragment for maintaining in encrypted form all attributes not appearing in the clear; departing from encryption, when R is partitioned into two fragments, one stored at the data owner site and the other one stored at the external server.

The two fragments can be joined by authorized users only and encryption is not used.

In the following, we present these three different strategies in more details. The discussion will focus on the different techniques that can be used to compute a fragmentation that satisfies the privacy requirements. The interested reader can refer to [START_REF] Samarati | Data protection in outsourcing scenarios: Issues and directions[END_REF] for a detailed discussion on additional issues that arise in the data outsourcing scenario.

Non-Communicating Pair of Servers

The first proposal suggesting the use of fragmentation and encryption for outsourcing data while enforcing a set of confidentiality constraints has been presented in [START_REF] Aggarwal | Two can keep a secret: a distributed architecture for secure database services[END_REF]. The basic idea consists in partitioning the original relational schema R into two fragments stored on two non-communicating servers, which do not know each other, thus preventing the joint visibility of attributes in the two fragments. We now describe the data fragmentation model and briefly illustrate how to compute a fragmentation.

Data fragmentation model

A relational schema R is partitioned into two fragments F 1 and F 2 stored at two non-communicating servers in such a way that the attributes involved in a confidentiality constraint cannot appear all together in a fragment. An encoding technique is used whenever an attribute cannot be stored within one of the two fragments without violating a confidentiality constraint. The encoding of an attribute a ∈R consists in representing the values of the attribute with two different attributes a 1 and a 2 included in the two fragments F 1 and F 2 , respectively. The values of attribute a can then be reconstructed only by authorized parties opportunely combining the values of the two corresponding attributes a 1 and a 2 . For instance, if attribute a is encrypted, then a 1 may contain the encrypted values of a and a 2 may contain the key(s) used for encrypting the values of attribute a . A fragmentation F is then defined as a triple F 1 ,F 2 ,E , where E is the set of encoded attributes stored at both servers (i.e., E ⊆ F 1 and E ⊆ F 2 ) and

R=F 1 ∪F 2 . A fragmentation F is correct if ∀c ∈ C conditions c ⊆ F 1 and c ⊆ F 2 are both satisfied. At the physical level, a fragmentation F= F 1 ,F 2 ,E , with F 1 = {a 11 , . . . , a 1n }, F 2 = {a 21 , .
. . , a 2m }, and E = {a e1 , . . . , a e l } translates into two physical fragments with schema F e 1 = {tid, a 1 e1 , . . . , a 1 e l , a 11 , . . . , a 1n } and F e 2 = {tid, a 2 e1 , . . . , a 2 e l , a 21 , . . . , a 2m }, respectively. Attribute tid is the primary key of both physical fragments and guarantees the lossless join property. The lossless join property guarantees that the content of the original relation r over R cal always be reconstructed through the join between the fragment instances over F e 1 and F e 2 . The join operation may be performed on the common attribute tid that can be either: 1) the key attribute of R, if it is not sensitive, or 2) an attribute that is added to both F e 1 and F e 2 during the fragmentation process, otherwise.

With this model, singleton constraints can only be satisfied by encoding the attributes in the constraints. Association constraints can instead be satisfied either by splitting the attributes in the constraints between F 1 and F 2 , or by encoding at least one of the attributes in the constraints. Note however that it is not always possible to satisfy an association constraint via fragmentation. As a matter of fact, since there are only two fragments it may happen that the attributes involved in an association constraint cannot be split between the two fragments without violating another constraint. In these cases, it is necessary to apply an encoding technique on one of the attributes involved in the constraint. Fig. 2. An example of a correct fragmentation in the non-communicating pair of servers scenario

Minimal fragmentation

Given a relational schema R and a set of well defined constraints C over it, there may exist different correct fragmentations. For instance, a fragmentation that encodes all attributes in R is always correct. However, such a fragmentation implies a higher query evaluation cost for authorized users than a fragmentation that minimizes the use of encoding and that resorts to fragmentation whenever possible. The query evaluation cost can be measured in different ways. In [START_REF] Aggarwal | Two can keep a secret: a distributed architecture for secure database services[END_REF] the authors adopt an affinity matrix , which is a matrix with a row and a column for each attribute in R. Each entry M [a i , a j ], with i = j, represents the cost that would be paid in query execution if attributes a i and a j do not belong to the same fragment. Each entry M [a i , a i ], with i = 1, . . . , n, represents the cost that would be paid if attribute a i is encoded. The cost of a fragmentation F is then defined as the sum of the cells M [a i , a j ] in the matrix such that a i ∈F 1 and a j ∈F 2 , and the cells M [a i , a i ] in the matrix such that a i ∈ E.

The problem of computing a fragmentation with minimum cost is NP-hard since, as proved in [START_REF] Aggarwal | Two can keep a secret: a distributed architecture for secure database services[END_REF], the hypergraph coloring problem [START_REF] Garey | Computers and Intractability; a Guide to the Theory of NP-Completeness[END_REF] reduces to it. As a consequence, an algorithm that computes a fragmentation with minimum cost would operate in time exponential with the number of attributes in R. To avoid this inconvenience, in [START_REF] Aggarwal | Two can keep a secret: a distributed architecture for secure database services[END_REF] the authors propose to combine known approximation algorithms used for solving the min-cut and the weighted set cover problems, obtaining three different heuristics working in polynomial time.

Multiple Fragments

The main problem of the approach illustrated in Section 3 is that it is based on the complete absence of communication among the storage servers (which have to be completely unaware of each other). This assumption is however difficult to enforce in practice and a collusion among the servers, or with an authorized user of the system, can breach the privacy of the data. The solution proposed in [START_REF] Ciriani | Fragmentation and encryption to enforce privacy in data storage[END_REF], and refined in [START_REF] Ciriani | Combining fragmentation and encryption to protect privacy in data storage[END_REF][START_REF] Ciriani | Fragmentation design for efficient query execution over sensitive distributed databases[END_REF], removes the need of having two non-communicating pair of servers. Like for the previous solution, we first describe the data fragmentation model and then illustrate how to compute a fragmentation.

Data fragmentation model

The proposal illustrated in [START_REF] Ciriani | Fragmentation and encryption to enforce privacy in data storage[END_REF] uses fragmentation and encryption for enforcing a set C of confidentiality constraints defined over a relational schema R and produces a set of fragments. The resulting fragments can be stored on the same server since they cannot be joined for reconstructing the content of the original relation. A fragmentation F={F 1 . . . F n } is therefore considered correct if the following conditions hold: 1) ∀c ∈ C, ∀F ∈ F, c ⊆ F ; 2) ∀F i , F j ∈ F, i = j, F i ∩ F j = ∅. Condition 1 states that a single fragment cannot contain in the clear attributes that form a confidentiality constraint. Condition 2 states that the fragments are disjoint. At the physical level, a fragmentation F={F 1 . . . F n }, with F i ={a i1 , . . . , a im }, i = 1, . . . , n, translates into a set of physical fragments F e i , i = 1, . . . , n. Each physical fragment F e i contains all the attributes in F i in the clear, while all the other attributes of R are encrypted. The reason for reporting all attributes of R (in either encrypted or clear form) in each of the physical fragment is to guarantee that any query can be executed by querying a single physical fragment. Formally, the schema of a physical fragment F e i corresponding to fragment F i ={a i1 , . . . , a im } is F e i (salt,enc,a i1 , . . . , a im ) where: salt is the primary key of F e i and contains a randomly chosen value; enc contains the encryption of all the attributes of R that do not belong to the fragment (i.e. R -F i ), combined before encryption in a binary XOR (⊕) with a salt; a i1 , . . . , a in correspond to the attributes in fragment F i .

Note that to protect encrypted values from frequency-based attacks [START_REF] Schneier | Applied Cryptography[END_REF], a salt is applied on each encryption. Attribute salt of a physical fragment stores such values that due to their randomness can also be used as primary keys.

Singleton constraints can only be satisfied by encryption, that is, by preventing attributes in singleton constraints to appear in the clear within a fragment. Association constraints can be satisfied by storing the attributes composing the constraint in different fragments. This is always possible because if an attribute cannot be inserted in an existing fragment without violating a confidentiality constraint, then a new fragment can be created and the attribute can be inserted in it. In this way, we maximizes the visibility of the data since encryption is used only for protecting singleton constraints. A fragmentation F that satisfies all the confidentiality constraints and that maximizes data visibility is a fragmentation where each attribute that does not appear in singleton constraints belongs to exactly one fragment in F. Clearly, a solution maximizing visibility permits a more efficient query evaluation.

Example 3. Consider relation Patient in Figure 1(a) and the set of constraints over it in Figure 1(b). An example of a correct fragmentation that maximizes visibility is F={{Name, Job}, {DoB, ZIP}, {Illness, Physician}}. Figure 3 illustrates the fragment instances over the physical fragments corresponding to F. Note that only attribute SSN does not appear in the clear in the fragments since it belongs to a singleton constraint (c 0 ).

Minimal fragmentation

Given a relational schema R and a set C of well defined constraints over it, there may exist different correct fragmentations that maximize visibility. As an example, a fragmentation F composed of singleton fragments, one for each attribute that does not appear in a singleton constraint is a correct fragmentation. Such a fragmentation however makes query execution inefficient. As a matter of fact, queries defined on more than one attribute can be executed only with the involvement of the client. Like for the non communicating pair of servers scenario, it is important to identify, among all the correct fragmentations maximizing visibility, the one that minimizes the cost of query execution for the client. To this purpose, there are different metrics that can be adopted for measuring the quality of a fragmentation. A simple metric is the number of fragments composing a fragmentation F [START_REF] Ciriani | Fragmentation and encryption to enforce privacy in data storage[END_REF]. The rationale is that a low number of fragments implies that more attributes are stored in the clear in the same fragment, thus improving the efficiency in query execution. The problem of computing a fragmentation that minimizes the number of fragments is however NP-hard (the hypergraph coloring problem [START_REF] Garey | Computers and Intractability; a Guide to the Theory of NP-Completeness[END_REF] reduces to this problem). To the aim of efficiently computing a correct fragmentation with a limited, even if not minimum, number of fragments, in [START_REF] Ciriani | Fragmentation and encryption to enforce privacy in data storage[END_REF] the authors introduce a definition of minimality that is based on the representation of a correct fragmentation that maximize visibility through a fragment vector . Given a fragmentation F={F 1 , . . . , F m } of a relational schema R, the fragment vector V F representing F is a vector with an element V F [a ] for each attribute a in m i=1 F i , where V F [a ] is set to F if attribute a belongs to fragment F . Example 4. Consider fragmentation F={{Name, Job}, {DoB, ZIP}, {Illness, Physician}} in Figure 3. The fragment vector representing F is defined as follows.

-V F [Name] = V F [Job] = {Name, Job}; -V F [DoB] = V F [ZIP] = {DoB, ZIP}; -V F [Illness] = V F [Physician] = {Illness, Physician}.
Fragment vectors define a partial order relationship, denoted ≺, among the correct fragmentations maximizing visibility of a relational schema R with respect to a set C of well defined constraints. In particular, a fragmentation

F dominates F, denoted F F , iff V F [a ]⊆V F [a ]
, for all attributes in R that do not belong to singleton constraints. Also, F≺F iff F F and F = F . In other words, a fragmentation F dominates a fragmentation F if F can be obtained by merging two (or more) fragments in F. The problem of computing a fragmentation with a minimal number of fragments consists then in computing a fragmentation F that maximizes visibility and such that there is not a fragmentation F maximizing visibility and correctly enforcing C, such that F≺F . The algorithm proposed in [START_REF] Ciriani | Fragmentation and encryption to enforce privacy in data storage[END_REF] to solve this problem operates in O(n 2 • m), where n is the number of attributes in R, while m is the number of non singleton constraints in C.

Alternative metrics that provide a more precise measure on the quality of a fragmentation are based on the use of an affinity matrix [START_REF] Ciriani | Combining fragmentation and encryption to protect privacy in data storage[END_REF] or on the definition of a specific cost function that models the cost of evaluating a set of representative queries on F [START_REF] Ciriani | Fragmentation design for efficient query execution over sensitive distributed databases[END_REF]. It is interesting to note that both the affinity matrix in [START_REF] Ciriani | Combining fragmentation and encryption to protect privacy in data storage[END_REF] and the cost function in [START_REF] Ciriani | Fragmentation design for efficient query execution over sensitive distributed databases[END_REF] are monotonic with respect to the dominance relationship . This means that the quality of a fragmentation increases with the increase of the the number of attributes represented in the clear in the fragmentation. In [START_REF] Ciriani | Fragmentation design for efficient query execution over sensitive distributed databases[END_REF] the authors exploit this property and propose an exact algorithm for computing a fragmentation with minimum cost, which avoids to visit the whole space of solutions by exploiting relation and the monotonicity of the cost function.

Departing from Encryption

A significant advantage of the solution based on multiple fragments is that it uses encryption only for protecting attributes involved in singleton constraints. However, the efficiency of query execution is still a problem since encryption causes a computational overhead for the client when executes a query, and for the data owner in key management. In [START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF][START_REF] Ciriani | Enforcing confidentiality constraints on sensitive databases with lightweight trusted clients[END_REF] the authors put forward the idea of completely departing from encryption. The proposed solution is based on the assumption that the data owner is willing to store a small portion of the data to guarantee the enforcement of confidentiality constraints.

Data fragmentation model

The proposal illustrated in [START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF] assumes that a subset of the data are stored at the data owner side, while the remaining information is outsourced to an external storage server. The input of the problem is still a relational schema R and a set C of confidentiality constraints defined over R. The result of the fragmentation process is a pair F = F o , F s of fragments, where F o is stored at the data owner side and F s is stored at the storage server. A fragmentation F is considered correct if fragment F s does not violate any constraint in C (i.e., ∀c ∈ C condition c ⊆ F s is satisfied) and all attributes of R appear in at least one fragment to avoid loss of information. Note that fragment F o could possibly violate constraints, since it is stored at the data owner side that is supposed to be trusted and accessible only by authorized users. The solution in [START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF] also assumes that even if the data owner is willing to store a portion of the data, her storage capacity is limited. A first consequence of this assumption is that the information should not be replicated in the two fragments F o and F s . In other words, fragments F o and F s should be disjoint to avoid replication of attributes already stored at the server side also at the data owner side. The only attributes that the two fragments have in common is an identifier that is needed to guarantee the lossless join property. Such an identifier can correspond to the primary key of R, if it is not sensitive, or an attribute that does not belong to the relational schema R and that is added to both the fragments during the fragmentation process, otherwise. At the physical level, a fragmentation F = F o , F s , with F o = {a o1 , . . . .a oi } and F s = {a s1 , . . . .a sj } translates into two physical fragments F e o (tid,a o1 , . . . .a oi ) and F e s (tid,a s1 , . . . .a sj ), respectively, where tid is the common identifier.

Since data are only partially outsourced and data are not encrypted, singleton constraints can only be satisfied by storing the involved attributes at the data owner side. Also, association constraints can be satisfied only by fragmentation, that is, by storing at least one of the attributes in the constraint at the data owner side. Note that, in this case, all the constraints can be enforced by fragmentation, even if F is composed of two fragments only since F o is supposed to be stored at a trusted party.

Minimal fragmentation

Similarly to previous approaches, given a relational schema R and a set of well defined constraints C over it, there may exist different fragmentations that are correct and non-redundant. For instance, a fragmentation where F o =R is obviously correct but it coincides with no outsourcing. Among all possible correct fragmentations, it is necessary to compute a solution that reduces either the storage at the data owner side, or the data owner's intervention in the query evaluation process (or both of them). For computing a fragmentation that minimizes storage and computational burden for the data owner it is necessary to define a metric able to measure the cost of a fragmentation. In [START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF] the authors propose different metrics that depend on the resource whose consumption should be minimized (e.g., the storage space, the bandwidth capacity, the computational power) and on the information available at fragmentation time. For instance, a simple metric corresponds to the number of attributes in F o . The minimization of the number of attributes implies a minimization of the storage space used at the data owner side as well as a minimization of the number of queries that require an involvement of the data owner. If, for example, is also available the information about the size of the attributes in R, then another possible metric consists in the total size of the attributes stored at the data owner side. More sophisticated metrics can be defined when information on the possible query workload is known.

In [START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF] the authors show that independently from the metric adopted to measure the cost of a fragmentation the problem of computing a fragmentation with minimum cost is NP-hard (the minimum hitting set problem [START_REF] Garey | Computers and Intractability; a Guide to the Theory of NP-Completeness[END_REF] reduces to it in polynomial time). Therefore, in [START_REF] Ciriani | Keep a few: Outsourcing data while maintaining confidentiality[END_REF] the authors propose a heuristic algorithm that solves the problem in polynomial time with respect to the number of attributes in R. The main advantage of this algorithm is its flexibility, since it can be adopted with any metric.

Open Issues

The problem of satisfying confidentiality constraints in data outsourcing is becoming of great interest and different solutions have been proposed to the aim of maximizing the advantages of outsourcing, while preventing unauthorized accesses to sensitive information. There are however different issues that require further investigations and that we now briefly describe.

-Multiple relations. Most of the solutions proposed in the literature for privacy protection are based on the assumption that the sensitive information is stored in a single relation. An interesting direction that needs to be explored consists in assuming that data are represented through a set of relations that can be possibly joined.

-Definition of confidentiality constraints. The proposals illustrated in this paper are based on the assumption that confidentiality constraints are defined by the data owner according to her knowledge of the domain. However, the definition of a correct and complete set of confidentiality constraints is a critical and difficult task since it is necessary to consider the relationships among data. In particular, functional dependencies must be taken into account, since otherwise they could be exploited for inference attacks. -Data utility. When publishing data, there are two contrasting needs that have to be taken into consideration: privacy protection and data utility.

The fragmentation-based techniques described in this paper mainly focus on privacy protection and do not consider data utility. It would then be interesting to extend such proposals by exploring novel solutions that will take into consideration not only the privacy requirements but also explicit requests for views over data. These view requirements can be expressed, for example, as associations that have to be preserved during the fragmentation process. -Obfuscated associations. Whenever the association a set of attributes is considered sensitive (and it is therefore modeled as a confidentiality constraint), it is not possible to publish the involved attributes in a fragment, even if the utility of the data would considerably increase. It would be then interesting to define a solution that allows the publication of a sanitized/obfuscated version of sensitive but useful associations. The publication method should carefully handle the tradeoff between data utility, on one side, and association confidentiality, on the other side. -Metrics. The computation of a minimum fragmentation implies the definition of a metric that is used to evaluate the cost of a fragmentation. A metric needs to take into consideration different parameters, such as, the storage at the data owner side, the computational resources required to the client for query evaluation, and the bandwidth occupation necessary for interactions among parties. Also, the metric adopted should be based on information that should be available to the data owner in advance with respect to the fragmentation process and that should be easy to compute. It would then be interesting to define sophisticate metrics able to capture the different parameters that may have an impact on the cost of a fragmentation. -Write operations. A common aspect of all the proposals discussed is that they only support read operations. There are however different contexts where the consideration of read operations only may be a limitation (e.g., within a multi-owner context). It would then be interesting to extend current approaches for supporting write operations.

Conclusions

Fragmentation has been recently investigated as a technique for guaranteeing the protection of outsourced data. In this paper, we described three different solutions presented in the literature that possibly combine fragmentation and encryption and that produce a fragmentation correct with respect to the given privacy requirements. We then concluded the paper with a discussion on some open research challenges.

Fig. 1 .

 1 Fig. 1. An example of relation (a) and of well defined constraints over it (b)

Example 2 .

 2 Consider relation Patient in Figure1(a) and the set of well defined constraints over it in Figure1(b). Suppose also that encryption is used as an encoding technique. Figure2illustrates the fragment instances over the physical fragments corresponding to the correct fragmentation F= {DoB, Illness, Physician}, {DoB, ZIP, Job}, {SSN, Name} . For simplicity, in this figure both encrypted values and corresponding keys are represented with Greek letters. Note that attribute DoB can be replicated without violating any constraint, thus improving query performance. Singleton constraint c 0 is enforced by encrypting attribute SSN. Association constraints c 1 , . . . , c 4 are satisfied by encrypting attribute Name. Finally, association constraints c 5 , . . . , c 8 are satisfied by fragmenting the involved attributes.

ω

  Pneumonia N. Doe

Fig. 3 .

 3 Fig. 3. An example of a correct fragmentation in the multiple fragments scenario

Example 5 .

 5 Consider relation Patient in Figure1(a), the set of constraints over it in Figure1(b), and the following two correct fragmentations that maximize visibility: F 1 ={{Name, Job}, {DoB, ZIP}, {Illness, Physician}} and F 2 ={{Name}, {Job}, {DoB, ZIP}, {Illness, Physician}}. Since F 1 can be obtained by merging fragments {Name} and {Job} in F 2 , F 2 F 1 .

Example 6 .

 6 Consider relation Patient in Figure 1(a) and the set of well defined constraints over it in Figure 1(b). An example of a correct fragmentation is F o ={SSN, Name, ZIP, Job} and F s ={DoB, Illness, Physician}. Figure 4 illustrates the fragment instances over the physical fragments corresponding to F o and F s . Constraint c 0 is satisfied by storing attribute SSN in F o . Constraints c 1 , . . . , c 4 are satisfied by storing attribute Name in F o . Constraints c 5 and c 6 are satisfied by storing attribute ZIP in F o . Constraints c 7 and c 8 are satisfied by storing attribute Job in F o .

Fig. 4 .

 4 Fig. 4. An example of a correct fragmentation in the departing from encryption scenario

1

  Name 1 DoB Illness

					Physician	F e 2 tid SSN 2 Name 1 DoB	ZIP Job
	1	α	ϑ	75/12/22 Pneumonia H. Daily	1	o	τ	75/12/22 22030 Nurse
	2	β	ι	71/03/18 Diabetes	I. Dale	2	π	υ	71/03/18 22045 Employee
	3	γ	κ	65/06/14 Hypertension J. Dooley	3		φ	65/06/14 22021 Manager
	4	δ	λ	51/09/30 Flu	K. Davis	4	ρ	ϕ	51/09/30 22030 Cook
	5	ε	µ	42/08/06 Gastritis	L. Denis	5		χ	42/08/06 22041 Nurse
	6	ζ	ν	82/10/07 Flu	M. Dicks	6	σ	ψ	82/10/07 22020 Nurse
	7	η	ξ	68/04/24 Pneumonia N. Doe	7	ς	ω	68/04/24 22045 Employee

When clear from the context R is used to denote either the relation schema R or the set of attributes in R.

68/04/24 Pneumonia N. Doe

Acknowledgments

The paper is based on joint work with Valentina Ciriani, Sushil Jajodia, Stefano Paraboschi, and Pierangela Samarati. The authors would like to thank Pierangela Samarati her comments, suggestions, and discussions that helped improving the organization of the paper. This work was supported in part by the EU within the 7FP project "PrimeLife" under grant agreement 216483.


Stefan Walraven
email: stefan.walraven@cs.kuleuven.be

Bert Lagaisse
email: bert.lagaisse@cs.kuleuven.be

Eddy Truyen
email: eddy.truyen@cs.kuleuven.be

Wouter Joosen Distrinet

Dynamic Composition of Cross-Organizational Features in Distributed Software Systems

Keywords: Cross-organizational, Feature-oriented, Service engineering, Dynamic composition, AOSD

Companies offering software services to external customer organizations must ensure that the non-functional requirements of all these customer organizations are satisfied. However, in such a cross-organizational context where services are provided and consumed by different organizations, the implementation of features, for example security, is scattered across the services of the different organizations and cannot be condensed into a single module that is applicable to multiple services. In this paper we present an aspect-based coordination architecture for dynamic composition of cross-organizational features in distributed software systems such as systems of systems or service supply chains. The underlying approach of this architecture is to specify the features at a higher level that abstracts the internal mechanism of the organizations involved. A coordination middleware dynamically integrates the appropriate features into the service composition, driven by metadata-based user preferences.

Introduction

A software service is used by several customer organizations simultaneously, possibly each of them with their own end users. Each customer organization may have different -possibly conflicting -requirements with respect to the features provided by the service. As non-functional requirements are often applicationspecific and pervasive, a software service is required to allow on-demand integration of tailorable features. To fit those varying requirements recent trends in service engineering aim to combine the benefits of feature-based and servicebased approaches [START_REF]Proceedings of the First Workshop on Service-Oriented Architectures and Software Product Lines[END_REF][START_REF] Lee | An Approach for Developing Service Oriented Product Lines[END_REF][START_REF] Apel | Research Challenges in the Tension Between Features and Services[END_REF][START_REF] Medeiros | Towards an Approach for Service-Oriented Product Line Architectures[END_REF]. This combination offers a modular and pluggable solution that increases the reusability of services and supports on-demand customization tailored to the user's needs.

The building blocks for these customizations consist of modular features. A feature is a distinctive mark, quality, or characteristic of a software system or systems in a domain [START_REF] Kang | Feature-Oriented Domain Analysis (FODA) Feasibility Study[END_REF]. Features define both common facets of the domain as well as differences between related systems in the domain. They make each system in a domain different from others.

However, services are mostly used in a service composition consisting of services from different organizations. In such a cross-organizational context, service implementations are black boxes, implemented and deployed by different organizations on possibly different service platforms, and only the interface descriptions are publicly available [START_REF] Apel | Research Challenges in the Tension Between Features and Services[END_REF]. In this cross-organizational and heterogeneous context, a problem arises when a feature implementation cannot be contained within the service provider, but crosscuts the service provider and service consumer (see Fig. 1). Because such a logical but distributed feature cannot be condensed into a single feature any more, on-demand service customization tailored to the user's preferences is hard to achieve in a cross-organizational context.

End user

Service consumer

Service provider

Consumer application

Service platform X

Provider application

Service platform Y

Distributed & heterogeneous features {preferences}

Cross-org

Fig. 1. Problem context of cross-organizational feature composition.

A typical example of a cross-organizational crosscutting feature is security in distributed e-finance software, such as online stock trading systems. When implementing an access control concern (authentication and authorization) in such an application, security actions need to be performed for every interaction between the distributed subsystems as presented in Fig. 2. In this cross-organizational context it is difficult to defend that a single feature module encapsulates the implementation of the internal security mechanisms of the organizations involved as well as the global security policy governing how security must be addressed in the overall interaction between different organizations. The latter security policy belongs to a level of abstraction above the internal security mechanism, allowing different implementations.

The problem of cross-organizational customization of services has not been well addressed in the current state-of-the-art. On the one hand, existing coordination architectures for cross-organizational service provisioning (GlueQoS [START_REF] Wohlstadter | GlueQoS: Middleware to Sweeten Quality-of-Service Policy Interactions[END_REF], BCL [START_REF] Milosevic | Inter-Organisational Collaborations Supported by E-Contracts[END_REF], T-BPEL [START_REF] Tai | Transaction Policies for Service-Oriented Computing[END_REF]) focus on dynamically establishing and monitoring agreements for enacting service delivery, but fail to support the coordination and dynamic composition of system-wide software features. On the other hand, stateof-the-art dynamic composition technologies such as dynamic aspect weaving fail to offer the right mechanisms for expressing customizations at the right level of abstraction.

This paper proposes an aspect-based coordination architecture for dynamic composition of cross-organizational features in distributed software systems such as systems of systems or service supply chains. The underlying approach of this architecture is to provide support for cross-organizational service customization by leveraging some of the principles of cross-org coordination architectures. First, a high-level feature ontology is specified to agree about a technology-independent feature model among the organizations within a specific contract domain or service network. Second, service consumers are able to express a desired feature configuration through the specification of a feature policy that is based on the vocabulary of this ontology. Third, each organization has to map their part of the feature ontology to a specific aspect-based implementation platform. The underlying coordination architecture is responsible for managing the feature ontology, its organization-specific mapping to aspects and the deployment of user-specific feature policies within various scopes such as per service binding, per session and per message.

The remainder of this paper is structured as follows. In Sect. 2 we further motivate and illustrate the importance of cross-organizational feature composition in distributed software systems. Section 3 shortly discusses related work. We describe our aspect-based coordination architecture for dynamic composition of cross-organizational features in Sect. 4 and evaluate the performance overhead of our prototype in Sect. 5. Section 6 concludes the paper.

Problem Motivation and Illustration

We present an example in the e-finance domain to further motivate and illustrate the importance of cross-organizational feature composition in distributed software systems (see Fig. 2). Banks offer their customers a stock trading service to inspect, buy and store stock quotes. To be able to provide this service, those banks cooperate with the stock market, which in turn cooperates with a settlement company. Such a cross-organizational service composition allows each participant to take up two roles: service consumer and service provider. For example, the bank company is a server for the bank customers, but consumes the QuotesOrderService of the stock market. Since different clients have different needs, the service providers must ensure that the different and varying non-functional requirements are satisfied, for example security, transaction support, load balancing, priority processing and stepwise feedback. In our example the bank customers can obtain different variants of the stock trading service composition by selecting features tailored to their preferences. For instance, a bank can offer to their customers several signature-based authentication options from which they can choose one, based on the different algorithms (e.g. SHA1withDSA). In the same way the stock market will negotiate with the different bank companies about the message carrier, the used protocols or which trusted third party (TTP) will be used. The stock trading service in Fig. 2 includes a signature-based authentication feature, applied on the connection between the stock market and the settlement company. This feature affects both the service consumer, to sign the messages, and the service provider, to perform the verification of the signatures. This clearly illustrates that a single feature module, consisting of client and server functionality, can affect multiple services in a service composition.

However, each company in a cross-organizational service network has its own IT administration and trust domain, and will not allow external parties to add or update feature implementations. The services provided by the different partners are black boxes, independently maintained by the company's own administrators. This black-box scenario hinders the feature modularization and composition in a cross-organizational context [START_REF] Apel | Research Challenges in the Tension Between Features and Services[END_REF]. Moreover, since the services are loosely-coupled, the different parties can use different service platforms, programming languages and feature composition techniques (e.g. Java and .NET platforms).

Therefore a feature cannot be condensed into a single module any more and should be applied in a distributed and heterogeneous way. Cross-organizational features need to be split up into consumer-and provider-side parts that respectively fulfill the service consumer and service provider responsibilities. A uniform high-level representation of those features is necessary to be able to share them in a cross-organizational and heterogeneous application domain or service network. Further we need a coordination middleware to dynamically activate the appropriate feature implementations throughout the service composition in a consistent way.

Related Work

This paper will tackle the problem statement by combining and improving two bodies of work. On the one hand, the body of work on cross-organizational coordination architectures; on the other hand, dynamic software composition technology in particular aspect-oriented middleware.

Cross-organizational coordination architectures. A core tenet of the body of research on cross-organizational coordination architectures is a multi-layered architecture distinguishing between policy and mechanism. In previous work we have defined a reference model [START_REF] Truyen | A Reference Model for Cross-Organizational Coordination Architectures[END_REF] for classifying the different approaches. In general, a cross-org coordination architecture consists of an agreement language for specifying agreements (either contract-or policy-based) and a coordination middleware for establishing agreements and monitoring these for violations. An agreement between a service consumer and provider specifies the rules of engagement, that must be complied with by service consumer and service provider. For example, agreements specify the flow of interactions and message types to be exchanged (BCL [START_REF] Milosevic | Inter-Organisational Collaborations Supported by E-Contracts[END_REF]), modal constraints (i.e. authorizations, obligations, prohibitions, timings (Ponder [START_REF] Damianou | The Ponder Policy Specification Language[END_REF])), QoS requirements (GlueQoS [START_REF] Wohlstadter | GlueQoS: Middleware to Sweeten Quality-of-Service Policy Interactions[END_REF]), usage of protocols and standards (T-BPEL [START_REF] Tai | Transaction Policies for Service-Oriented Computing[END_REF]). Secondly, the underlying coordination middleware supports establishing agreements between client and server dynamically, and to enforce the agreements or detect violations against it. These architectures, however, are not designed for user-specific customization of shared service instances and the consistent deployment of distributed and heterogeneous software features throughout cross-organizational service compositions.

Aspect-oriented middleware. Aspect-oriented software development (AOSD) [START_REF] Filman | Aspect-Oriented Software Development[END_REF] has been put forward as a possible solution to address the problem of crosscutting (often non-functional) concerns. In addition, AOSD is often applied to enable modularization and composition of features [START_REF] Mezini | Variability Management with Feature-Oriented Programming and Aspects[END_REF][START_REF] Loughran | Framed Aspects: Supporting Variability and Configurability for AOP[END_REF][START_REF] Lee | Combining Feature-Oriented Analysis and Aspect-Oriented Programming for Product Line Asset Development[END_REF].

Aspect-oriented frameworks [START_REF] Pawlak | JAC: A flexible solution for aspect-oriented programming in Java[END_REF][START_REF]JBoss Community[END_REF][START_REF]SpringSource: AOP with Spring[END_REF][START_REF] Lagaisse | True and Transparent Distributed Composition of Aspect-Components[END_REF][START_REF] Söldner | AOCI: Weaving Components in a Distributed Environment[END_REF][START_REF] Rouvoy | Dynamic planning and weaving of dependability concerns for self-adaptive ubiquitous services[END_REF] have played a key role in the modularization of middleware platforms: these have evolved from a monolithic platform with a declarative configuration interface towards an architecture that is able to plug application-specific or user-specific extensions on demand. Current aspect-oriented frameworks also support dynamic aspect weaving in a reliable and atomic manner [START_REF] Nicoarȃ | Dynamic AOP with PROSE[END_REF][START_REF] Truyen | Support for Distributed Adaptations in Aspect-Oriented Middleware[END_REF]. These AO techniques make these platforms therefore ready for deployment in usage contexts where a shared service instance can be dynamically customized to customer-specific requirements by dynamically weaving in desired features. In a cross-organizational context, however, current AO technology fails to offer coordinating mechanisms for deploying multiple aspect modules across multiple organizations and heterogeneous platforms.

Aspect-Based Architecture for Cross-Organizational Composition

This section describes the aspect-based coordination architecture enabling dynamic composition of cross-organizational features. Figure 3 illustrates our approach underlying the architecture. Similarly to the research on cross-organizational coordination architectures, our architecture assumes that a conceptual model for cross-organizational features is agreed upon between all organizations within a particular domain or a specific service network. This conceptual model defines a feature ontology, a feature model [START_REF] Kang | Feature-Oriented Domain Analysis (FODA) Feasibility Study[END_REF] in fact, shared by all organizations involved, for naming and defining the different features and their alternative implementation strategies. Next, the feature ontology is mapped to an aspect-based feature implementation within each organization which can use an AO-technology of its choice. Subsequently, a service consumer can then express user-specific feature preferences when binding to a service provider. An underlying coordination middleware will ensure that the appropriate feature im-plementations are activated dynamically throughout the service composition in a consistent manner at the right moment, driven by metadata. We will now explain the architecture in more detail. First, the high-level, technology-independent feature ontology is presented. Next, we describe the aspect-based feature implementation mapping. Thereafter it is presented how users can specify customization requirements through feature policies. Finally we present the design of our coordination middleware. As a running example we will use the example of dynamically composing security features such as authentication and non-repudiation in the stock trading service composition.

High-level Feature Ontology

The conceptual model in our approach for specifying cross-organizational features consists of a high-level feature ontology. This feature ontology should be abstract and independent from the aspect-based implementation (the computational model) to enable that different organizations in the service network can implement the same features differently depending on their choice of implementation platform and composition technology.

Within a particular domain, for example e-finance domain, a standard for non-functional features (e.g. security) can be agreed upon. Figure 4 presents an example of a feature ontology for security features based on existing standards [START_REF]International Organization for Standardization (ISO): Information Processing Systems -Open Systems Interconnection -Basic Reference Model -Part 2: Security Architecture[END_REF][START_REF]OMG: CORBA Security Services Specification[END_REF][START_REF] Beznosov | Engineering Access Control for Distributed Enterprise Applications[END_REF]. Security protection breakdowns into authentication, authorization, audit, availability, confidentiality, integrity and non-repudiation. We also itemized some possible feature implementation strategies, based on the different algorithms (e.g. SHA1withDSA for signature-based authentication).

A feature node within the ontology consists of a feature identifier, a unique name for referring to that feature, and a high-level, technology-independent feature contract about the intended behavior of the feature and the roles that different parties involved have to play. These roles are described by a name (e.g. Service Consumer) and a set of responsibilities that specify constraints on behavior and interfaces. Furthermore, composition rules can be specified that prescribe which features depend on other features and which features can't be executed during the same request due to feature interference. For example, the SignatureBasedNR non-repudiation feature (see Fig. 4) defines two roles: a service consumer who retrieves the customer account information, and a service provider responsible for securely logging the customer account, the name and arguments of the request, and the cryptographic signature of the message. The service provider role requires a CustomerAccount attribute, which will be provided by the service consumer role. There is also a dependency rule necessary that prescribes that SignatureBasedNR requires the SHA1withDSA authentication feature to provide a Signature attribute.

Currently we have not yet designed a concrete language for representing feature contracts (We expect though that such feature contract language would be based on existing feature modeling techniques for services such as Service Diagrams [START_REF] Harhurin | Service-Oriented Commonality Analysis Across Existing Systems[END_REF].). We do offer a declarative specification language for representing feature identifiers and roles from the ontology and their mapping to specific feature implementations.

Aspect-Based Feature Implementation Mapping

The mapping between the high-level feature ontology and the aspect-based implementations is specified on the level of the internal processes and data, hiding the implementation details for external parties. By capturing the semantics of the features in a high-level feature ontology, the different features can be implemented independently by each of the service providers using their favorite service platform and AO-composition technology. Hence, the different services in the network may have their own optimized aspect-based implementations of the different features, and the most appropriate feature implementation in each service may depend on environmental circumstances. However, the feature implementations have to satisfy certain constraints, enforced by the feature on-tology. In addition, the implementation of the different features and the software composition strategy are open for adaptation by each of the local administrators.

The use of AOSD [START_REF] Filman | Aspect-Oriented Software Development[END_REF] enables a clean separation of concerns, in which the core functionality of a service is separated from any feature behavior. Therefore features are implemented separately from each other as composite entities containing a set of aspect-components, providing the behavior of the features (so called advice). This advising behavior can be dynamically composed on all the components of a service -at consumer-side and at provider-side. The aspectcomponents of the features are composed by means of declarative specifications in the form of AO-compositions: these specify on which elements of the service platform the aspect-components must be applied. Each feature implementation mapping within a specific organization is described by means of a declarative specification that specifies: (i) the feature and role that is implemented and (ii) a set of AO-compositions to integrate the feature into the internal processes and data of the organization. Such an AOcomposition specifies a pointcut and a set of advices to apply. Listing 1.1 presents an example of a feature implementation mapping for the service consumer role of the SHA1withDSA signature-based authentication feature. The AO-composition specifies that this feature imposes on the transport layer of the service platform (pointcut) to digitally sign the messages before sending by means of the SHA1withDSASignature aspect-component (advice).

Expressing User-Specific Preferences Through Feature Policies

The feature ontology is accessible to the end users of the service application and allows them to select the desired set of features. A service consumer selects a set of features by instantiating a feature policy. A feature policy is a declarative configuration that specifies per service binding which features are desired for that particular binding (see Listing 1.2). A service binding simply identifies the URI and interface of the service provider in question. When user-specific preferences dictate that a particular feature must be applied, the feature implementations of the consumer and provider side will be dynamically composed for every message exchanged through that service binding.

Coordination Architecture

In order to process user requests in a consistent manner throughout the crossorganizational service composition, coordination is needed between all participating services. To achieve this coordination, every request is tagged with extra meta information, specifying the set of features corresponding to user-specific preferences. This metadata propagates with the message flow initiated by that user request. As such, knowledge about the desired combination of features travels with the message flow. The coordination middleware also ensures that the appropriate feature implementations are activated dynamically when required. Figure 5 presents our coordination middleware, built on top of an AOframework. The coordination middleware relies on this AO-framework to support dynamic AO-composition. The runtime composition of cross-organizational features throughout service compositions consists of two main phases: selection and activation. These phases are represented in the architecture as modular packages: the Selection and ConsumerActivation package are part of the consumer service platform; the ProviderActivation package is included into the provider service platform. In the rest of this subsection we first explain the selection phase. Then the general structure and operation of the activation phase are described.

Selection of Cross-Organizational Features. The machinery for the selection phase of the coordination middleware consists of the FeatureSelection aspect and the PolicyManager component. FeatureSelection is imposed onto the application layer where it intercepts the requests to remote services that are subject to a certain feature policy (cf. Listing 1.2). The PolicyManager processes the feature policies and stores which features apply to each service binding. These data structures are hash maps with constant access time. The FeatureSelection aspect queries the PolicyManager to determine which features apply for a given service binding, and annotates the intercepted messages with the feature identifiers of the required features. It also keeps track of which service bindings have already been customized: only for new service bindings the PolicyManager is queried for required features.

Activation of Selected Cross-Organizational Features. After the necessary cross-organizational features are selected, those features need to be activated. The activation phase of the coordination middleware consists of the ConsumerActivation and ProviderActivation aspects and the ConsumerFeatureMapping and ProviderFeatureMapping components. The feature mapping components store a hash map of feature implementations and their associated AO-compositions. This allows to query the appropriate feature implementation based on a given feature identifier. ConsumerFeatureMapping and ProviderFeatureMapping handle respectively the service consumer and service provider roles of the features. The consumer-side ConsumerActivation aspect imposes on the consumer service platform; at the server-side the ProviderActivation aspect intercepts all incoming messages. These locations are the first joinpoints -thus the entry points -in the call flow of the remote requests, at the consumer-side middleware stack as well as the provider-side middleware stack.

ConsumerActivation intercepts all messages and checks them for metadata with selected features. The selected features are compared with the features currently applied on the particular service binding to see whether any changes are necessary. If a change is necessary, ConsumerActivation queries the Con-sumerFeatureMapping component for the descriptions of the AO-compositions for the selected features and uses this information to compose the necessary aspect-components. The activation aspect will then send a request to the AOframework to deploy those aspect-components.

The last step in the feature activation mechanism is notifying the providerside about the feature change. This way we ensure the features are applied throughout the service composition in a consistent manner. Therefore the feature updates are added as a piggyback to the message.

At the provider-side, the ProviderActivation aspect intercepts the incoming requests and checks them for feature updates. If necessary, the new features are activated. The activation at the provider-side is analogous to the consumerside. Concretely, ProviderActivation first inspects the currently activated crossorg features of the service binding, then it applies the feature changes using the feature implementation mappings retrieved from ProviderFeatureMapping. Incoming requests are also verified to be compliant with the feature policies: the messages are inspected for unsupported or missing features. These messages are not accepted, and an exception message is returned.

Since the activation aspects check all requests, cross-organizational features can easily be deployed within a per message scope. Therefore the FeatureSelection aspect will need to query the PolicyManager for all intercepted messages. The activation aspects will ensure that features will be applied only once per service binding.

Evaluating the Performance Overhead

The evaluation aims to measure the absolute and relative performance overhead that our coordination architecture introduces on the overall responsiveness of service applications. In particular we want to measure the overhead introduced by the Selection and Activation components. Before we present the evaluation of our architecture, we briefly discuss our prototype implementation.

As a proof of concept, a prototype of the coordination architecture has been implemented as a framework using Java SE 6. It is built on top of our own aspectcomponent framework which offers support for dynamic AO-composition. The Java dynamic proxy technology is used to intercept invocations and call advices. For all declarative specifications we used XML files.

The coordination architecture is developed as an extension to the service platform, enabling the dynamic composition of cross-organizational features in distributed applications. Since it is a modular and aspect-based extension, the coordination middleware can be omitted or removed when needed.

Our current prototype relies on an aspect-component framework that also supports weaving various middleware features in the distribution layer. We measured the roundtrip by comparing a version of our distribution layer where all features are statically composed, against one where all features are dynamically woven using our coordination architecture. In particular we focused on one security feature for the distribution layer: the implementation of a signaturebased authentication feature (for signing and verifying method invocations) as described in the running example of this paper.

We have used a round-trip latency benchmark as presented in [START_REF] Demarey | Benchmarking the Round-Trip Latency of Various Java-Based Middleware Platforms[END_REF] which requires minimal processing time. This way the processing time influences the results as minimal as possible and the results show clearly the worst-case runtime overhead of the coordination architecture. As described in [START_REF] Demarey | Benchmarking the Round-Trip Latency of Various Java-Based Middleware Platforms[END_REF], the benchmark application is composed of two JVM applications: a client and a server. The client invokes a remote service which implements an empty ping method with no arguments and a void return value. The benchmark scenario is configured as follows. The remote service and the client run into two JVMs on different hosts 1 in the same LAN. 100 benchmark series are executed sequentially. For all series, 20000 warmup operations are performed. Next, 20 steps of 5000 invocations are measured. For each step an average execution time is logged. So 2000 average measures (100 series * 20 steps) are obtained for each benchmarked distribution layer, representing 10 million operations.

This benchmark application is extended with the signature-based authentication feature and executed on the two versions of our distribution layer: the default version and the version extended with our coordination architecture. In both cases the authentication feature will be deployed from the beginning.

The results of the round-trip latency benchmark test are presented in Fig. 6(a) and indicate that the overhead introduced by our coordination middleware is negligible. We can achieve these good results because the Selection aspect in our coordination architecture keeps track of which service bindings have already been customized. In addition the feature activation mechanism only notifies the provider-side when there are updates. In the current benchmark setup where the feature is deployed from the beginning, this will result in very few updates.

To measure the relative performance overhead of our coordination architecture, we compared our prototype against standard middleware platforms: Java RMI [START_REF]Java RMI[END_REF] and JBoss Remoting [START_REF]JBoss Community: JBoss Remoting[END_REF], using the default benchmark application (without security features). Java RMI is a minimal distribution layer with almost no customization capabilities. JBoss Remoting is a distribution layer with a standardized interface for pluggable transport and serialization layers. The three middleware platforms all use Java serialization and TCP sockets, but differ in their composition architecture: hard-coded (Java RMI), object-based framework (JBoss Remoting), or aspect-component framework (our approach). The results of the second benchmark are used to calculate the average number of operations per second (see Fig. 6(b)) in the different distribution middlewares. These results show that Java RMI has the best performance (as expected), but more importantly, our coordination architecture and distribution layer introduce a relative overhead (in comparison to Java RMI) that is 6 factors smaller than that of JBoss Remoting. These initial results indicate that the overhead introduced by our coordination middleware is acceptable, especially in a cross-organizational context where long-running and asynchronous interactions more frequently occur than synchronous interactions with timing constraints.

Conclusion

Cross-organizational customization of services has not been well addressed in the current state-of-the-art. In this paper we presented an aspect-based coordination architecture for dynamic composition of cross-organizational features in distributed software systems. A high-level feature ontology specifies for each feature the responsibilities of service consumer and provider. Using this feature ontology we are able to map feature identifiers to aspect-based feature implementations, allowing each organization to implement the features independently using an AOP technology of its choice. The underlying coordination middleware ensures that user-specific feature preferences are processed in a consistent manner throughout the cross-organizational service composition. Our architecture has been validated in a prototype. We have benchmarked this implementation and it shows acceptable performance.

Fig. 2 .

 2 Fig. 2. Illustration of the stock trading service composition including the signaturebased authentication feature as a single module.

Fig. 4 .

 4 Fig. 4. Example of a feature ontology for the stock trading composition.

Listing 1 . 1 .

 11 Example of a feature implementation mapping. featureImplMapping SHA1withDSAImpl { implements : SHA1withDSA ; r o l e : S e r v i c e C o n s u m e r ; ao-c o m p o s i t i o n { i d : SHA1withDSASigning ; pointcut { k i n d : e x e c u t i o n ; componenttype : * ; c o m p o n e n t i n s t a n c e : * ; i n t e r f a c e : I T r a n s p o r t ; method : s e n d M e s s a g e ; } advice { comptype : SHA1withDSASignature ; i n t e r f a c e : I S i g n a t u r e ; method : s i g n ; }}}

Listing 1 . 2 .

 12 Example of a feature policy.

  servicebinding { URI : h t t p : / /www. s t o c k t r a d i n g e x a m p l e . be ; p o r t : S t o c k T r a d i n g S e r v i c e S o a p E n d p o i n t ; f e a t u r e s : SHA1withDSA , SignatureBasedNR ; }

Fig. 5 .

 5 Fig. 5. The coordination middleware architecture.

Fig. 6 .

 6 Fig.[START_REF] Filman | Aspect-Oriented Software Development[END_REF]. Subfigure (a) presents the average time (in ms) needed to execute a ping operation in the two versions of the distribution layer, with the signature-based authentication feature activated. Subfigure (b) shows the average number of minimal method operations per second in the different distribution middlewares. The box plots at the end of the bars represent respectively the minimum, average and maximum during the different benchmarks.

The benchmark tests were performed on systems with an Intel Core

Duo

3.00 GHz processor and 4 GB memory, running Ubuntu 8.04 (hardy) and OpenJDK Runtime Environment version 1.6.0.