Ying Pan

Lei Wu

Shijun Liu

Xiangxu Meng

A Hypergraph Partition Based Approach to Dynamic Deployment for Service-oriented Multi-tenant SaaS Applications

Keywords: service deployment, hypergraph partition, multi-tenant, hierarchical services, SOA

In a service-oriented multi-tenant SaaS application, all tenants share services and user requests of the service change dynamically. In order to provide high-quality web services, we must solve the problem of the load unbalance caused by dynamic user requests' change. This paper proposes an approach based on hypergraph partition to keep load balance for serviceoriented multi-tenant SaaS application. A hypergraph-based service model is used to present hierarchical services and multi-tenant applications. This approach adjusts service distribution on the servers based on hypergraph partition to keep load balance. According to the experiments, this approach effectively solves the problem of load unbalance caused by the change of user requests.

Introduction

Service-Oriented architecture (SOA) has become the standard for enterprise application development and integration. In SOA model, many kinds of computing resources (e.g, applications, services, and servers) are provided as services [START_REF] Newcomer | Understanding SOA with Web Services[END_REF]. It has been considered as an effective solution for enterprise users because of its low cost and rapid reuse [START_REF] Thomas | Service-Oriented Architecture: Concepts, Technology, and Design[END_REF]. SaaS (Software as a Service) providers usually develop and acquire software applications and host them as services to serve specific requests of their clients.

In service component based SaaS applications, each multi-tenant application consists of a series of services while services are shared by multiple tenants. The multi-tenant applications improve profit margin for both service providers and enterprise users through reducing delivery costs and decreasing service subscription. However, it also introduces a noticeable problem that how to guarantee the quality of service (QoS) for multiple tenants who share applications. If the server that services deploy on is overloaded, the QoS for tenants will be sharply down. In the global + To whom correspondence should be addressed. consideration, the QoS for each tenant can be mapped to the loads of services that consist the multi-tenant application, that is to say, we should keep the server balance in order to meet the Qos for tenants. Additionally, the server load changes with user requests dynamically.

Therefore, in this paper we propose an approach based on hypergraph partition to solve the problem of dynamic service deployment under the premise of load balance. The approach is designed to ensure that SaaS providers can deploy and manage the service instances with the dynamic change of multiple tenants' service requests. A hypergraph-based service model is used to represent hierarchical services and these services are divided into several partitions. We propose algorithms that map each hypergraph partition to a server to deploy and balance each partition according to user requests change.

The structure of our paper is organized as follows. In section 2, we outline hypergraph partition-based service deployment. This is followed by section 3 that describes our algorithms for dynamic service deployment. We give some discussions about the overall performance of the approach according to experiments in section 4. Finally, conclusions and future work directions will be shown in the last section.

Hypergraph Partition Based Service Deployment for Multitenant SaaS Applications

Hypergraph-based Service Deployment Model

We consider various business requirements and the dependencies that exist in multitenant applications and services, thus services are divided into three levels in our research [START_REF] Wang | A Dependency-aware Hierarchical Service Model for SaaS and Cloud Services[END_REF]: business-independent level, business-dependent level and composite business level. There are two kinds of dependences between the services, including functional dependency and business dependency. Such dependences widely exist in tenant applications and services, services in different and identical levels. But traditional DAG is hardly able to represent such structure and dynamic change of hierarchical services. Therefore, we introduce hypergraph partition theory into the service deployment. We establish directed hypergraph-based service deployment model to map servers. Definition 1 (service): A service is a tuple S = (sId, subServices, sDes, sLevel), where: sId is the identifier of service; subServices is a finite set of services that the service depends on; subServices = { s 1 , s 2 , … , s m }, where each s i = (target, tRefType), target∈S, tRefTye is the type of dependence which including functional dependency and business dependency; sDes is the description of service; sLevel is the level of service, including business-independent level, business-dependent level and composite business level. Definition 2 (tenant application): A tenant application is a tuple T = (tInfo, Services, tQos , tNonFun), where: tInfo is the basic information of tenant application, including the tenant information and so on; Services = {S 1 , S 2 ,…, S n } is a finite set of services; tQos is the QoS for the tenant; tNonFun is non-functional properties of the tenant. Definition 3: A service deployment directed hypergraph is denoted as SDDG = <V, E>, where:

1) V = {v 1 , v 2 , …, v n } is a finite set, where: each v i (i∈ [1,n]) corresponds to a service s i , while v i = {S, sR, sG, sQos, sGain, sType}.

• S is a service which is rented by multi-tenants.

• sR = {sr 1 , sr 2 , …, sr k } is a finite set of resources that the service need.

• sG = {sg 1 , sg 2 , …, sg k } is a finite set of resource quantities which sg i corresponds to sr i (i∈ [1,k]).

• sQos is the quality of service.

• sGain is the gain value of service. It is the important basis for vertex movement in hypergraph partition. In this paper, sGain represents comprehensive value of resource consumption computed by the resource consumption estimation model. The higher the value, the greater it impacts the partition. It indicates that the vertex has higher priority during the current partition adjustment.

• sType is the type of vertex, including BV and FV. BV is a base vertex, which is chosen to move to another partition. FV is a free vertex except to base vertexes.

2) E = {e 1 , e 2 , …, e m } is a finite set of hyperedges, m = |E| is the number of hyperedges, eq = { sPre, v i },(q∈[1,m])

• sPre is a non-empty subset of vertices v j , which v j ∈V. It indicates that the vertex v i depends on its predecessor vertexes set, that is, the service can be deployed only after the services in its sPre are deployed. sPre = { sv 1 , sv 2 , …, sv k }, k = |sPre| is the number of vertexes which belong to sPre.

• eType is the type of hyperedge, including CH and NCH. CH is a critical hyperedge. It indicates that current hypergragh partitions will be changed if one vertex that belongs to it moves from one partition to another. NCH is a non critical hyperedge except to CH. Definition 4: FB and TB, FB is From Block. FB (v i , e j ) is the source partition that v i which is connected by hyperedge e j belongs to. TB (v i , e j ) is the destination partition.

Hypergraph Partition for Service Deployment

The services are represented by a hypergraph-based model, and we use the properties of hypergraph partition to solve the problem of dynamic service deployment. We divide vertexes in the hypergraph into different partitions on the basis of the balance formulas and map the hypergraph partitions to the servers. Definition 5 (Hypergraph Partition): Hypergraph Partition for Service Deployment PS = {P 1 , P 2 ,…, P k }(as shown in Figure 1) is a final set which includes k subsets of the vertex set V of service deployment directed hypergraph SDDG = <V, E>, where: each P i ∈PS (i∈ [1,k]) is a non-empty, pairwise-disjoint subset of V; Pw = {pw 1 , pw 2 ,…, pw k } is the weight set which pw i corresponds to P i , where pw i is the weight of partition P i ( i∈ [1,k]), k = |PS| is the order of the partitions. Function F(P i ): P i ->S j (i∈ [1,k],j∈ [1,m]) represents the mapping relation between hypergraph partition P i and server j. PS must meet the following conditions:

• , ( , 1, 2,
..., , )

i j i j P P V P P i j k i j         • j i i j v P pw CA    , / i avg i m p PS pw pw RC    
where pw avg is the average of all weight pw i •For each

( [1, ]) i e E i m  
, service i can be deployed only after the services in its source set sPre have been deployed.

•For each ( [1, ]) i v V i n 
 , the quality of service i should be guaranteed.

•Each partition p i is balanced only if it meet the balance formula below:

(1 ) , 0

i avg pw pw      (1)
 is a predetermined maximum load parameters of imbalance deviation.

Algorithms for Hypergraph-partition-based Service Deployment

The algorithms proposed in our paper are based on the hypergraph partition for service deployment. The main idea of the algorithms: Firstly, we initialize the service deployment directed hypergraph SDDG according to parameters. Then, we get the partitions of SDDG on the basis of balance formula. Finally, we map each partition to servers and adjust the hypergraph partitions to keep balance constantly. It mainly includes two parts: First Deployment and Re-partition.

The structure of the main algorithm described as below:

In First Deployment, we initialize the SDDG, get hypergragh partitions of service deployment and deploy the corresponding services on servers.

In Re-partition, we first get actual resource consumptions of every server from the system at regular intervals. Then we adjust the current partitions to keep load balance according to the actual resource consumptions. The resources that are considered include CPU, memory and I/O.

STEP 1 Initialization:

We initialize the service deployment directed hypergraph SDDG on the basis of parameters such as tenants and services. The hypergraph partition is based on the SDDG.

STEP 2 First Deployment:

When the so-called "first deployment", we can't get real-time resource consumptions of services, so we use the multi-tenant resource consumption model to estimate comprehensive resource consumption CA i of each service s i in SDDG. Then we call the function One Partition recursively until each hypergraph partition is balanced according to balance formula [START_REF] Newcomer | Understanding SOA with Web Services[END_REF]. Finally, we map each partition to a server, that is to say, we deploy the services that belong to each partition to the corresponding server.

One partition is a recursive function that belongs to First Deployment. Once called, it will check whether the current partitions are balanced. If they are balanced, function returns. If they are not, it divides the current partitions into two parts and calculates the weight set of new partitions because estimated resource consumptions of services change with the dependence relation among them.

STEP 3 Re-partition Deployment:

The actual resource consumptions of servers change with user requests. When a server is overloaded, we should adjust current hypergraph partitions in order to redeploy services. We can get the actual resource consumptions from server system. If the server s i is overloaded, we select service s i which is deployed on server s i and has the highest sGain and move it t into the server whose load is lowest. Only when the current partitions get balance again, we stop the re-partition.

The main algorithm includes three sub-algorithms: Initialization, First Deployment and Re-partition. There are n services and m servers. The time complexity of algorithm Initialization is O(n) which has a linear relationship with the size of services. The algorithm First Deployment calls algorithm One Partition recursively and its time complexity is O(nlogn). The algorithm Re-partition is related to the size of services and servers and its complexity is O(nm). To sum up, the time complexity of whole algorithm is O(nm)+ O(nlogn)+ O(n) which is service quantity and server number related.

Performance Evaluation

In this section, we present the performance based on an extensive set of experiments to verify the correctness and effectiveness of our algorithms. The experiments are based on the following scene: Twenty services are deployed on five servers. The servers in our experiments are the same. The resource they provide is one unit while the limited load is 0.7 units. We consider three kinds of resource which include CPU, memory and I/O in the experiments of our paper. Experiment 1: To verify whether the algorithm First Deployment can get the hypergraph partitions that ensure balance conditions, we list the weight of P i after first partition of 20 services. Fig. 3. We get the first partitions after the algorithm First Deployment. The weights of every P i (P i ∈PS) are similar and each partition keeps balance on the basis of balance formula [START_REF] Newcomer | Understanding SOA with Web Services[END_REF]. It indicates that the algorithm can get the reasonable hypergraph partitions.

Experiment 2: The system gets the actual loads of 5 servers every day. If servers are overloaded, the system re-partitions the hypergraph according to our algorithm. Then, we adjust the deployment of services to keep server load balance. We compare the actual load of 5 servers before the re-partition with that after the re-partition.

Fig. 4. The blue blocks represent the server loads before the re-partition while the red ones represent the server loads after that. The loads of 5 servers are not balanced before the repartition deployment. Server 1 and server 3 are overloaded. After the adjustment, the loads of 5 servers are balanced again and none of them is overloaded. It indicates that our algorithm is correct and effective. Figure 2 shows the hypergraph partitions before and after the adjustment.

Conclusion and Future Work

In this paper, we study the dynamic deployment with the change of user requests for service-oriented multi-tenant SaaS application. We propose an approach based on hypergraph partition to solve it. The hypergraph partition is used to divide the services into several subsets while each partition is mapped to a server. If the services of every partition are satisfied to the balance formula, it means the corresponding server is not overload, that is, the servers keep balance. From the experiment results, we can conclude that our algorithm works well when we deploy services on the first time and re-deploy them when servers are overloaded.

Although the current approach is good, there are several that need to be improved in future. We plan future work to address the following considerations:

1) We consider the servers are identical and the resources that they provide are equal. In more cases, the servers are different and the resources are not equal. We will consider the differences among them.

2) Sometimes, the loads of some servers are too low, and we can combine the services deployed on them to get more value.

The two points above are not researched deeply in this paper and our future work will be developed around them.

Fig. 1 .

 1 Fig. 1. There are two tenants and fifteen services in the hypergraph model. Hypergraph partition for service deployment PS = {P 1 , P 2 , P 3 , P 4 ,} has four subsets.

Fig. 2 .

 2 Fig. 2. The left part is the twenty service deployment before the hypergraph re-partition while the right part is the deployment after that.

Acknowledgment

The authors would like to acknowledge the support provided by the National High Technology Research and Development Program of China (2011AA040603, 2012AA040904), the National Key Technologies R&D Program of China (2012BAF12B07), the Natural Science Foundation of Shandong Province (ZR2009GM028, ZR2011FQ031) and Independent Innovation Foundation of Shandong University (IIFSDU)


Jin Li

Dechen Zhan
email: dechen@hit.edu.cn

Lanshun Nie

Xiaofei Xu
email: xiaofei@hit.edu.cn

An Approach for Validating Semantic Consistency of Model Transformation Based on Pattern

Keywords: Model transformation, Transformation rule, Transformation pattern

The correctness of model transformation is an import research field in model-driven architecture. Syntactic correctness and semantic consistency are hot topics in the field of model transformation. Syntactic correctness has many mature solutions. However the validation of semantic consistency has some problems. Therefore, how to validate semantic consistency of model transformation is a major problem in model-driven development. In this paper, we propose a validation approach for semantic consistency of model transformation, which is based on pattern. We analyze some patterns in models and make these patterns as transformation pattern. We define transformation rule with transformation pattern and analyze three parts of semantic transformation. We present two theorems to validate semantic consistency of model transformation. Finally, we give a case to illustrate the effectiveness of our approach.

Introduction

The correctness of model transformation is an important research field in modeldriven architecture (MDA) [START_REF] Miller | MDA Guide Version 1.0.1[END_REF][START_REF] Hailpern | Model-driven development: The good, the bad, and the ugly[END_REF]. The research mainly focuses on syntactic correctness and semantic consistency [START_REF] Beydeda | Model-Driven Software Development-Volume of Research and Practice in Software Engineering[END_REF]. Syntactic correctness has some mature solutions [START_REF] Hausmann | Extended model relations with graphical consistency conditions[END_REF], e.g. planning algorithm [START_REF] Varró | Designing the automatic transformation of visual languages[END_REF]. However the validation of semantic consistency has some problems, e.g. effective theory. Therefore, how to validate semantic consistency of model transformation is a major problem in model-driven development of software systems. Model transformation consists of transformation rules which describe how a set of elements of the source model are transformed into a set of elements of the target model through transformation relationships [START_REF] Kleppe | MDA Explained: The Model Driven Architecture: Practice and Promise[END_REF]. Semantic consistency of model transformation is for maintaining consistency between source model and target model in the semantics. So, the validation problem for semantic consistency of model transformation is equivalent to the formulization proof of semantic consistency in the process of model transformation.

Many methods to solve semantic consistency of model transformation have emerged from industrial and academic research. Varró [START_REF] Varró | Automated Formal Verification of Model Transformation[END_REF] defined and validated the model constraints to preserve semantic consistency of model transformation. Jinkui Hou [START_REF] Hou | Semantic Description Framework for Architecture-Centric Model Transformation[END_REF] proposed a semantic description framework, and promoted category theory to describe and validate semantics of model transformation. Caplat [START_REF] Caplat | Model Mapping Using Formalism Extensions[END_REF] extended formal language to describe and validate model semantics. Engles [START_REF] Engels | Consistency-Preserving Model Evolution Trough Transformations[END_REF] provided the relationships of semantic objects of UML-RT to describe the consistency required among models, and proved these relationships through static analysis. XiaoHe [START_REF] He | Extending QVT Relations for business process model transformation[END_REF] extended QVT Relations with three new concepts and discussed the semantics of the mapping pattern and creating model.

Different model transformation methods may need different methods to preserve semantic consistency of model transformation. The paper proposes a validation approach for semantic consistency of model transformation based on pattern. We make some patterns, e.g. sequence pattern, branching pattern and loop pattern, in models as transformation patterns and use these transformation patterns to define transformation rule. There are three parts of the validation process of semantic consistency: (1) the semantic mapping from source model to source transformation pattern; (2) the semantic mapping from source transformation pattern to target transformation pattern; (3) the semantic mapping from target transformation pattern to target model. Then, the validation problem for semantic consistency of model transformation is equivalent to the problem about the three semantic mappings.

The rest of this paper is structured as follows. In Sect. 2, we propose the motivating example which will be used throughout the paper. Section 3 provides the core concepts. Section 4 presents the validation theory of semantic consistency of model transformation. Section 5 illustrates the validation theory. Sect. 6 concludes the paper and further work.

Motivation Example

There are some basic patterns in models, e.g. sequence pattern, branching pattern, and loop pattern, which belong to business process model. The three patterns are shown in Fig. 1 The UADM describes a business process of submitting sale order. The process is: firstly query sale data, secondly fill these data into a sale order, thirdly audit the sale order, and finally submit the sale order. The activity about auditing the sale order has a judging condition, i.e. if the sale data is less than 1000, the sale order should be submitted directly. Otherwise the manager should audit the sale order. If the manager agrees the sale order, he submits the sale order. Otherwise the sale data will be queried again. The UADM contains these three patterns above. For example, the operations of querying sale data and filling the sale order correspond to the sequence pattern; the operation of checking the sale data corresponds to the branching pattern; the operation of auditing the sale order corresponds to the loop pattern, and the auditing loop pattern contains the sequence patter. RelationElement, and Constraint. Constraint has two subclasses: interConstraint and exterConstraint. interConstraint describes the internal relationships of LeftPattern and RightPattern, and exterConstraint describes the external relationships of LeftPattern and RightPattern. interConstraint can be described by OCL, while exterConstraint is described according to the constraint relationships of NodeElement, RelationElement and TransformationPattern. We focus on the semantic information of exterConstraint in the paper. We firstly analyze the external relationships of transformation pattern, which are illustrated in Fig. 3.

Transformation Pattern and Transformation Rule

Fig. 2. Metamodel of transformation rule

In Fig. 3, there are two kinds of constraint relationships: Element-Pattern and Pattern-Pattern. In the first constraint relationship, there is a relationship r 1 between the element n 1 and the transformation pattern TP 1 . The end element of r 1 is one of elements of TP 1 . Because TP 1 contains two elements (n 2 and n 3 ), there are three conditions of the mapping between n 1 and TP 1 : (1) from n 1 to n 2 ; (2) from n 1 to n 3 ; (3) from n 1 to n 2 and n 3 . There needs an external constraint relationship to accurately describe the mapping condition between n 1 and TP 1 . In the second constraint relationship, the identifier r 2 is a relationship between the transformation patterns TP 1 and TP 2 . Because the start element of r 2 comes from TP 3 and the end element of r 2 comes from TP 2 , we divide the constraint relationship (Pattern-Pattern) into two constraint relationships (Element-Pattern): the relationship between r 2 and TP 2 , and the relationship between r 2 and TP 3 . The two relationships are similar to the relationship between r 1 and TP 1 .

We firstly propose the model definition, the definition of transformation pattern with the external constraint relationship, and the definition of transformation rule.

The Validating of Semantic Consistency of Model Transformation

The goal of preserving semantic consistency of model transformation is that the semantics of source and target model is equivalence. During a process of model transformation based on pattern, the semantic transformation process from source model to target model is an implementation process of transformation rules. The processes contain three parts of model semantic mappings: the semantic mapping from left pattern to source model, the semantic mapping from left pattern to right pattern, and the semantic mapping from right pattern to target model. Because the left and right patterns have the equivalent semantics, the problem of preserving model semantic consistency is similar to two the semantic mapping problem: the mapping from left pattern to source model, and the mapping from right pattern to target model. We will propose the theorems to solve the problem.

Semantic Mapping from source transformation pattern to source model

According to the definition 3.3, the left pattern of transformation rule is a set of source transformation patterns. Every element of source transformation pattern is either automatic element or another transformation pattern. So we describe the semantic mapping from left pattern to source model according to two mapping conditions. The identifiers M and TP denote a model and a transformation. If the semantics of M and TP is equivalence, we called the equivalence relationship as TP≌ M. We provide a theorem to validate the semantic consistency of the mapping between transformation pattern and model. Theorem 4.1 Let M be a Model, the node set of M is M.E={ e 1 ,e 2 ,...,e s }, TP is a transformation pattern, the node set of TP is TP.N={n 1 ,n 2 ,...,n p }. TP≌M if and only if Satisfying the following three conditions:

(1) every node n i ∈TP.N, then n i ∈∪meta(M.E);

(2) every relationship r j ∈TP.R, then r j ∈∪meta(M.L);

(3) every external constraint relationship eC∈TP.exterC preserves the semantics. Proof. (

The constraint relationship of transformation pattern satisfies semantic consistency. There are two parts of the constraint relationship: the internal constraint relationship and the external constraint relationship. Preserving the internal constraint relationship can be validated by OCL, while preserving the external constraint relationship is validated according to the definition of the external constraint relationship. There is an external relationship r between the element n i and the transformation patter TP: <i> if n i is an automatic element, there exists an instance element l k (l k ∈M.L) of r and rel(l k )=[e i ,e j ] (e i ,e j ∈M.E). According to ①②, n i satisfies either n i =meta(e i ) or n i =meta(e j ), then the external constraint relationship eC=<r,TP,{n i }> preserves the semantics of r and TP; ④ <ii> if n i is a transformation pattern TP i , according to ②, there exists a sub model M j ' of M, and n i ≌M j ', then a certain element n k of TP i may be the start or end element of r, n k ∈ TP i .N. According to ④, the external constraint relationship eC=<r,TP i ,{n k }> preserves the semantics of r and TP. ⑤

Semantic Mapping from target transformation pattern to target model

In the session, we will propose the construction process from target transformation pattern to target model, and provide a theorem to validate whether the process preserve the semantics.

TP s and TP t are the source and target transformation patterns, and their corresponding mapping models are M s and M t . The construction process from TP t to M t is the following: [START_REF] Miller | MDA Guide Version 1.0.1[END_REF]

Proof.

There are three parts of the semantic transformation of source model: the semantic mapping from M s to TP s , the semantic mapping from TP s to TP t , and the semantic mapping from TP t to M t . According to definition 3.3, the semantics of TP s and TP t is equivalence. According to the theorem 4.1, the semantics of M s and TP s is equivalence. So the preserving semantic problem of M s and M t is equivalent to the preserving semantic problem of TP t and M t . Because M t is constructed by TP t , the preserving semantic problem only validates the semantic equivalence of element and relationship of M t . The validation of preserving the semantic equivalence of element and relationship are the following:

(1) Element equivalence. n t is an element of TP t , n t ∈TP t .N, <i> if n t is an automatic element, according to ⑦, the instance element e i of n t satisfies n t =meta(e i ), then TP

Experiment

We validate the semantic equivalence of UADM and JBPM. There are three parts of the validation process: (1) preserving semantic equivalence of UADM and TP s ; (2) preserving semantic equivalence of TP s and TP t ; (3) preserving semantic equivalence of TP t and JBPM. The validation process is the following:

(1) Preserving semantic equivalence of UADM and TP s The metamodel of UADM contains Activity, Decision, ConstrolFlow, Start and End. There are three basic patterns in UADM: sequence pattern, branching pattern and loop pattern. We firstly define three transformation patterns according to these basic patterns.

(a) A source sequence pattern is composed of querying sale data, filling sale order and their relationship in UADM. It is defined as According to the theorem 4.1, we validate the semantic equivalence of source transformation patterns and UADM. The instance model of TP SS contains the elements querying sale data and filling sale order. When the auditing order is error, the sale data should be queried again. So there is a relationship between TP SS and r s1 . TP SS contains an external relationship eC 1 =<r s1 , TP SS ,{Activity}> to describe the relationship. When the auditing order is ok, there exists a relationship between TP SL and TP SB . Then there is a relationship r 6 between TP SL and TP SB . TP SL contains an external relationship eC 3 =<r 6 , TP SL ,{Activity}> to describe the relationship. So the transformation patterns (TP SS , TP SB , TP SL ) preserve the semantic equivalence of M s .

TP SS =<N SS ,
(2) Preserving semantic equivalence of TP s and TP t

We firstly define three target transformation patterns. JBPM contains TaskNode, DecisionNode, and Transition. The semantics of TP s and TP t is equivalence. This is not the focus of this paper, and therefore, we will not describe it here.

(3) Preserving semantic equivalence of TP t and JBPM M t is constructed by TP t . According to the theorem 4.2, the semantics of the constructed elements and relationships is equivalence is equivalent to the semantics of M s . So the mapping between TP t and M t preserves the semantic equivalence.

As noted above, the semantics of UADM to JBPM is equivalence.

Conclusions and Future Work

In this paper we propose an approach for validating semantic consistency of model transformation. We analyze some basic patterns in models, e.g. sequence pattern, branching pattern, and loop pattern, and use these basic patterns to define transformation rules. Therefore, the semantic transformation of source model has been divided three parts: (1) the semantic mapping from source transformation pattern to source model; (2) the semantic mapping from source transformation pattern to target transformation pattern; (3) the semantic mapping from target transformation pattern to target model. The validation problem for semantic consistency of model transformation is equivalent to the problem about the three semantic mappings. The motivation example illustrates the effectiveness of our approach. Future work is to optimize transformation rules constructed through our approach transformation. For this reason, we plan to analyze the typical business patterns in models and compose some transformation rules using these patterns to improve the efficiency of model transformation.

  (a). We use the model transformation from UML Activity Diagram Model (UADM) to Java Business Process Model (JBPM) to describe how to preserve model semantics during model transformation. The UADM and JBPM are shown in Fig.1(b).

Fig. 1 .

 1 Fig. 1. Motivation example The approaches of model transformation define transformation rules with the patterns. A pattern is either basic pattern or user-defined pattern. The user-defined pattern is generally defined according to domain business requirements. The patterns are called transformation patterns in transformation rules. These transformation patterns can simplify transformation definition, raise transformation efficiency, and improve transformation quality.

Definition 3 . 1 (

 31 Model): A model is defined as M=<E, L, rel, meta> (1) Where -E={e 1 ,e 2 ,...,e s } denotes a finite set of model elements, -L={l 1 ,l 2 ,...,l t } denotes a finite set of the relationships among model elements, rel(l k )=[e i ,e j ] denotes a relational function between model elements, and describes that e i is a start element of l k and e j is an end element of l k , e i ,e j ∈E, 1≤i,j≤s, l k ∈L, 1≤k≤t, meta(e u ) denotes an instance function, and it describes the metamodel of e u , 1≤u≤s. Note that we use "." to describe the element of model, e.g. M.E describes the element set of M, and M.L denotes the relationship set of M.

Fig. 3 .

 3 Fig. 3. The external relationship of transformation pattern Definition 3.2 (Transformation Pattern): A transformation pattern is defined as

  (d) Target sequence pattern contain two TaskNodes and a Transition. Target sequence pattern TP TS =<N TS , R TS , rel TS , interC TS , exterC TS >, where N TS ={TaskNode, Transition}, R TS ={r 10 ,r 11 }, rel TS (r 10 )=[TaskNode, Transition], rel TS (r 11 )=[Transition, TaskNode], exterC TS ={eC 4 }, eC 4 =<r t1 , TP TS ,{TaskNode}> (e) Target branching pattern contain a TaskNode, a DecisionNode, a Transition and a TP TS . It is defined as TP TB =<N TB , R TB , rel TB , interC TB , exterC TB >, where N TB ={TaskNode, DecisionNode, Transition, TP TS }, R TB ={r 12 ,r 13 ,r 14 ,r t1 }, rel TB (r 12 )= [DecisionNode, Transition], rel TB (r 13 )=[TaskNode, Transition], rel TB (r 14 )=[TaskNode, DecisionNode], rel SB (r t1 )=[DecisionNode, TP TS ], exterC TB ={eC 5 }, eC 5 =<r t2 , TP TS , {TaskNode}> (f) Target loop pattern contain two DecisionNodes, a TP TS , and a TaskNode. It is defined as TP TL =<N TL , R TL , rel TL , interC TL , exterC TL >, where N TL ={TaskNode, DecisionNode, Transition, TP TS }, R TL ={r 15 ,r 16 ,r 17 ,r 18 ,r t1 }, rel TL (r 15 )= [DecisionNode, TP TS ], rel TL (r 16 )=[TP TS , TaskNode], relT L (r 17 )= [DecisionNode, TaskNode], rel TL (r 18 )=[TaskNode, DecisionNode], exterC TL ={eC 6 }, eC 6 =<r t3 , TP TL , {TaskNode}>

  -interC={iC 1 ,iC 2 ,...,iC m } denotes a finite set of the internal constraint relationships; -exterC={eC 1 ,eC 2 ,...,eC n } denotes a finite set of the external constraint relationships, eC x =<r,TP, {n x ,n x+1 ,...,n l }> denotes the constraint relationship between r and TP, r ∉R, 1≤x,l≤p. Every element n k is either a start element or an end element of r, n k ∈N, 1≤k≤p. In Fig. 3, the three mapping condition of the constraint relationship between n 1 and TP 1 can be defined as the following: eC 1 =<r,TP,{n 2 }>, eC 2 =<r,TP,{n 3 }>, eC 3 =<r,TP,{n 2 ,n 3 }>. LP={tp s1 ,tp s2 ,...,tp su } denotes left pattern, and it contains a finite set of source transformation patterns, -RP={tp t1 ,tp t2 ,...,tp tv } denotes right pattern, and it contains a finite set of target transformation patterns; -C denotes constraint relationship of LP and RP. The left and right pattern are formed pairs in transformation rule, i.e. if left pattern contain the transformation pattern tp si , right pattern should contain another transformation pattern tp tj . The semantics tp si , is similar to the semantics of tp tj , 1≤i≤u, 1≤j≤v.

	TP=<N, R, rel, interC, exterC> transformation pattern. Therefore, the left and right pattern of transformation rule can (2) Where -contain one or more transformation patterns. Definition 3.3 (Transformation Rule): A transformation rule is defined as TR=<LP, RP, C> (3) Where N={n When a transformation rule contains an element, we make the element as a -

[START_REF] Miller | MDA Guide Version 1.0.1[END_REF]

,n 2 ,...,n p } denotes a finite set of nodes, and its instance element set is M.E; -R={r 1 ,r 2 ,...,r q } denotes a finite set of relationships, and its instance element set is M.L; rel(r k )=[n i ,n j ] denotes an element-relationship function, and describes that n i is a start element of r k and n j is an end element of r k , n i , n j ∈N, 1≤i,j≤p, r k ∈R, 1≤k≤q,

  1) Every node of transformation pattern is a certain metamodel element of model element. n i is an element of TP, 1≤i≤p, <i> if n i is an automatic element, there exists a node e k ∈M.E which satisfies n i =meta(e k ). So n i ∈∪meta(M.E); ① <ii> if n i is a transformation pattern, it should semantic map with a submodel M

i ' of M. The node set of M i ' is a sub set of M nodes, i.e. M i '.E ⊆M.E. Every element n l of n i , there exists a node e o ∈M i '.E and it satisfies n l =meta(e o ). So n i ∈∪meta(M.E); ② (2) Every relationship of transformation pattern is a certain metamodel relationship of model element. r j is a relationship of TP, 1≤j≤q. According to the definition 3.2, rel(r j )=[n j1 ,n j2 ], n j1 and n j2 are the elements of TP, i.e. n j1 ,n j2 ∈TP.N. And according to ①②, because n j1 ,n j2 ∈∪meta(M.E), there exists two elements e u ,e v ∈M.E. They satisfy n j1 =meta(e u ) and n j2 =meta(e v ). To the relationship l w between e u and e v , there exists rel(l w )=[e u , e v ]. So r j ∈∪meta(M.L); ③

11 Theorem 4.2.

  Constructing element. n t is an element of TP t , n t ∈TP t .N, <i> if n t is an automatic element, according to the instance relationship of the metamodel and model, constructing a new model element e i and make n t =meta(e i ); ⑥ <ii> if n t is a transformation pattern, according to the corresponding element n s of TP s : a) if n s is an automatic element, constructing a new element e i , and make n t =meta(e i );⑦ b) if n s is a transformation pattern, constructing a sub model M t ', and make n t .N=meta(M t '.E);⑧ (2) Constructing relationship. r k is a relationship of TP t , r k ∈TP t .R. There exists two elements (n i ,n j ) and they satisfy rel(r k )=[n i ,n j ], n i ,n j ∈TP t .N, <i> if n i and n j are two automatic elements, according to ①, their instance elements (e ti , e tj ) are the automatic elements of M t . n i and n j satisfy n i =meta(e i and n j are corresponds to the sub model M ti ' and M tj ', and these sub models satisfy M ti '.E={e ti1 ,e ti2 ,…,e tim } and M tj '.E={e tj1 ,e tj2 ,…,e tjn }.According to the external relationships eC 1 =<r,n i ,{e tj1 ,e tj2 ,…,e tjn }> and eC 2 =<r,n j ,{e ti1 ,e ti2 ,…,e tim }>, if there exists two elements e tk and e tk ' in M ti '.E and M tj '.E, constructing a relationship l k from e tk to e tk ', and make rel(l k )=[e tk , e tk ']. ○ Let TP s and TP t be two transformation patterns, if they correspond to the source M s and target model M t , the semantics of M s and M t is equivalence.

ti ) and n j =meta(e tj ). Then, constructing a relationship l tk from e ti to e tj , and make rel(l tk )=[ e ti ,e tj ], l tk ∈M t .L; ⑨ <ii> if n i is a transformation pattern and n j is an automatic element. According to ②,n i corresponds to a sub model M ti ' of M t , M ti '.E={e ti1 ,e ti2 ,…,e tim }. If there exists an external constraint relationship eC=<r,n i ,{e tj }>, the model element e tk will be found in M ti '.E Then constructing a relationship l k from e tk to e tj , and make rel(l k )=[e tk ,e tj ]. In the same way, if n i is an automatic element and n j is a transformation pattern, there exists M tj '.E={e tj1 ,e tj2 ,…,e tjn }. According to the external constraints relationship eC=<r,n j ,{n i }>, there exists an element e tk ' in M tj '.E, constructing a relationship l k ' from e ti to e tk ', make rel(l k ')=[e ti , e tk ']; ⑩ <iii> if n i and n j are two transformation patterns, according to ②, n

  t .N≌M t .E; <ii> if n t is a transformation pattern, according to ⑧, the instance sub model M t ' of n t satisfies n t .N=meta(M t '.E), then TP t .N≌M t .E; (2) Relationship equivalence. r k is a relationship of TP t , r k ∈TP t .R. There exists two elements (n i , n j ) and they satisfy rel(r k )=[n i ,n j ], n i ,n j ∈TP t .N, <i> if n i and n j are two automatic elements, according to ③⑥, their instance elements are e ti and e tj which are two elements of M t . According to ⑨,there exists the instance relationship l tk of l k , and rel(l tk )=[e ti ,e tj ], So TP t .R≌M t .L; <ii> if n i is a transformation pattern and n j is an automatic element. According to ③⑩, there exists an element e tk in the instance model M ti ' of n i , and a relationship l k from e tk to e tj . The relationship satisfies rel(l k )=[e tk ,e tj ], so r k ≌M ti '; In the same way, if n i is an automatic element and n j is a transformation pattern, there exists a relationship l k ', so TP t .R≌M t .L; <iii> if n i and n j are two transformation patterns, according to③○ 11 , if there exists e tk and e tk ', the relationship l k between e tk and e tk ', and rel(l k )=[e tk , e tk '], so TP t .R≌M t .L.

  R SS , rel SS , interC SS , exterC SS >, where N SS ={Activity, ControlFlow}, R SS ={r 1 ,r 2 }, rel SS (r1 )=[Activity, ControlFlow], rel SS (r 2 ) =[ControlFlow, Activity], exterC SS ={eC 1 }, eC 1 =<r s1 , TP SS ,{Activity}>.Note that r s1 is an external relationship, r s1 ∉ rel SS . (b) A source branching pattern is composed of auditing sale order, pass, and TP SS . It is defined asTP SB =<N SB , R SB , rel SB , interC SB , exterC SB >, where N SB ={Activity, Decision, ControlFlow, TP SS }, R SB ={r 3 ,r 4 ,r 5 ,r 6 }, rel SB (r 3 )=[Decision, ControlFlow], rel SB (r 4 )=[ControlFlow, Activity], rel SB (r 5 )=[Activity, ControlFlow], rell SB (r 6 )= [ControlFlow, Decision], exterC SB ={eC 2 }, eC 2 =<r s2 , TP SB ,{ Decision}>Note that r s2 is an external relationship, r s2 ∉ rel SB .(c) A source loop pattern is composed of less 1000, auditing sale order, pass, and TP SS . It is defined as TP SL =<N SL , R SL , rel SL , interC SL , exterC SL >, where N SL ={Activity, Decision, ControlFlow, TP SS }, R SL ={r 7 ,r 8 ,r 9 ,r s1 }, rel SL (r 7 )=[Decision, ControlFlow], rel SL (r 8 )=[ControlFlow,TP SS ], rel SL (r s1 )=[TP SS , ControlFlow], rel SL (r 9 ) =[ ControlFlow, Decision], exterC SL ={eC 3 }, eC 3 =<r 6 , TP SL ,{Activity}>.

Acknowledgments. Research works in this paper are supported by the National Natural Science Foundation of China (60773064, 60904080), the National High-Tech Research and Development Program of China (2009AA04Z153, 2008GG1000401028).


Cui Lizhen

Xu Meng

A QoS-Aware Hyper-Graph Based Method of Semantic Service Composition

Keywords: QoS-aware, Hyper-graph, Service Composition 1

Semantic service composition is an important issue in web service based systems. It is about how to build a new, reusable and value-added service by combining existing semantic web services. In this paper we propose a new hyper-graph based method supporting semantic service composition, which model the service composition problem as a hyper-graph. Then the hyper-graph based service composition algorithm has been implemented and evaluated. The evaluation results have shown that the method can effectively reduce the composition time and has good robustness, especially in the case of large number of web services and concepts.

Introduction

Service-oriented computing (SOC) has been widely accepted as the next generation programming paradigm. The web services are loosely coupled reusable and self-describing software components that encapsulate discrete functionality and are distributed and programmatically accessible over standard internet protocols [START_REF] Tsur | Are Web services the next revolution in e-commerce?[END_REF]. It is an alternative and promising approach to development web-based application or system rapidly to combine the existing Web Services. But with the number of Web Service on the internet over the last few years increasing sharply, it is difficult and time consuming to combine web services manually [START_REF] Lécu | A Formal Model for Semantic Web Service Composition[END_REF]. Therefore, semantic web is introduced into Web Service technologies to support dynamic and automated tasks such as discovery, composition and execution. In recent years, how to composite services automatically have drawn lots of research attentions [START_REF] Canfora | An approach for qos-aware service composition based on genetic algorithms[END_REF][START_REF] Hashemian | A graph-based framework for composition of stateless web services[END_REF][START_REF] Mcilraith | Adapting golog for composition of semantic web services[END_REF][START_REF] Sirin | Htn planning for web service composition using shop2[END_REF][START_REF] Yu | Efficient algorithms for web services selection with endto-end qos constraints[END_REF][START_REF] Zeng | Qos-aware middleware for web services composition[END_REF][START_REF] Zhou | Bits: A binary tree based web service composition system[END_REF].

In this paper we proposed a QoS(Quality of Service)-aware hyper-graph based method for semantic Web Service Composition. We model the service composition problem as two hyper-graphs. And by pruning the vertexes and the link between two hyper-graphs, the composite service is built effectively.

The main contributions of this paper are as follows:

(1) Show how the problem of service composition can be modeled as a hypergraph transversal problem.

(2)Tackle the problem of automatic service composition and QoS-aware service selection problem together with an algorithm that both efficient and 100% precise.

The rest of the paper is organized as follows: Section 2 reviews related work and motivates this work. Section 3 shows how to model the service composition problem as a hyper-graph transversal problem. Section 4 discusses the detail of the approach. Section 5 evaluates the performance of the proposed QoS-aware hyper-graph based method of semantic service composition in this paper, and finally Section 6 concludes.

2

Related Work

Since it is very difficult and time consuming to find composite service manually from huge amount of services, automatic service composition is proposed to enable automatic building composition for a given request. Some approaches, such as [START_REF] Mcilraith | Adapting golog for composition of semantic web services[END_REF][START_REF] Sirin | Htn planning for web service composition using shop2[END_REF], tackle Web service composition problem via AI planning. On the other hand, some other researches [START_REF] Hashemian | A graph-based framework for composition of stateless web services[END_REF][START_REF] Milanovic | Search strategies for automatic web service composition[END_REF] regards it as a graph search problem and solves it by shortest path, A*, etc. algorithms.

To guarantee local or global QoS requirements of service composition, the QoSaware service composition has attracted a lot of attention in recent years. Different from automatic service composition, it assumes that a work plan is predefined and has a set of "abstract" tasks and the objective is to select service for each task from its candidate services to meet local or global QoS constraints. Zeng [START_REF] Zeng | Qos-aware middleware for web services composition[END_REF] uses two service selection approaches based on Multiple Criteria Decision Making. In [START_REF] Yu | Efficient algorithms for web services selection with endto-end qos constraints[END_REF], the authors model the problem as a multi-choice 0-1 knapsack problem or a multi-constraint optimal path problem, and then compute optimal result according to the objective function. In addition, a genetic algorithm is proposed to address the problem in [START_REF] Canfora | An approach for qos-aware service composition based on genetic algorithms[END_REF]. Although it is more inefficient than Integer Programming, it can deal with non-linear constraints.

In one words, all the methods above for automatic service composition or QoSaware service composition only consider one aspect of QoS-aware automatic service composition, which is to search work plans for a given request or to guarantee global QoS requirements. Furthermore, Some researchers have proposed approaches to address the QoS-aware automatic service composition problem, such as [START_REF] Liu | Web services automatic composition based on qos[END_REF][START_REF] Wang | Qos-aware composite services retrieval[END_REF][START_REF] Naseri | Qos-aware automatic composition of web services using ai planners[END_REF]. Peter [START_REF] Bartalos | Semantic web service composition framework based on parallel processing[END_REF] proposes a fast approach by some index tables stored in database to fit the competition CEC'09 [START_REF] Bartalos | Semantic web service composition framework based on parallel processing[END_REF]. But it cannot provide 100% precision and its efficiency are not good enough when the scale of services is big.

In [START_REF] Zhu | Fast Discovery of Interesting Collections of Web Services[END_REF], Zhu modeled the problem of computing cost constrained collections of Web services as a constrained hyper-graph transversal problem. But it only can compute a set of services to fulfill some functions. Out method can find a composite service which can satisfy a user request.

Definition and Problem Model

We now provide the necessary definition about hyper-graphs and the semantic service composition. Then a formal description of the problem will be given.

Definition 1 A hyper-graph H is a pair H = <E, V> where V is a finite set of vertices V = { v 1 , v 2 ,…,v m } and E is a family of (hyper) edges, E ={ e 1 , e 2 ,…, e t } where each e i is a subset of V, 1≤i≤t. We assume V = {∪e i | e i ∈E, 1≤i≤t }.

Definition 2 The candidate service is a service which can be used in the service composition process. The candidate service set is a finite set of services S={s i |s i is a cadidate service}. And s i =<p(s i ) in , p(s i ) out , QoS>, where p(s i ) in is the input parameters set of s i , p(s i ) out is the output parameters set of s i , QoS is the QoS property of s i .

In this paper, we only consider the response time as the QoS property of web service. And the computing method can be find in [START_REF] Ardagna | Adaptive Service Composition in Flexible Processes[END_REF].

Definition 3 The composition request is a request of user which can be represent as R={P in ,P out }, P in is the set of input parameters and P out is the set of output parameters.

We now describe the reduction of the semantic service composition problem to the problem involving hyper-graphs. We will model the problem to two hyper-graphs. One is called output parameters hyper-graph, which is represented by H o . And the other is called input parameters hyper-graph, which is represented by H i . Each Web Service in S is modeled as a vertex both of H o and H i . Furthermore, a virtual service (vertex) is added in H o and H i respectively. The virtual service which is added in H o is called input_service I s ={φ,R.P in , 0} whilst the virtual service which is added in H i is called output_service O s ={R.P out , φ, 0}. Then we will add edges in H o and H i . Each edge in H o (H i ) corresponds to a set of vertices (web services) which have a particular output(input) parameter. The transversals of the two hyper-graphs now correspond to two sets of services that cover all the services requested by the user.

Example 1 Let us consider a example. S={s 1 , s 2 , s 3 , s 4 , s 5 , s 6 }. The input and output parameters of all services are listed in Table 1. The request of user is R={{a,b,e}, {f,g}}.

Hyper-Graph Based Service Composition Algorithm

In this section, we will describe the hyper-graph based service composition algorithm. We will use the example shown in Fig. 1. Response time of every service is shown using superscripts. Fig. 2 illustrates the basic outline of the algorithm.

First, the two hyper-graphs are generated according to the request and candidate service set. During the process of generating hyper-graphs, the complete time is calculated for every service. Then a pruning strategy is applied to delete the useless service and edge. At last, a solution generation algorithm is used to create the composite service.

Input

Pruning Strategy

After the hyper-graphs is generated, they should be pruned to remove the useless vertexes and edges. Fig. 4 shows the pruning strategy. By this way, the search space and the time of composition time can be reduced. Before the pruning strategy is applied, the redundant vertexes of H i should be deleted and the edge order of the H i should be adjusted first. We arrange the edges which contain the service O s at last (line 1-2). By doing this, the pruning strategy can be applied from the last to first of H i . The edges of H i which contain O s should be reserved and all vertexes except O s in the edge should be deleted. On the other hand, the edges of H i which do not contain O s will only reserve the vertex which has the minimal complete time and all other vertexes will be deleted. After the edge of H o is pruned, the edge of H i which has the same subscript will be pruned. Then we will get two pruned hyper-graphs after H o and H i are pruned. Fig. 5 shows the pruned hyper-graphs of Fig. 1

Solution Generation

Solution Generation is used to generate the composite service of the request. After applying the pruning strategy to H o and H i , we get two pruned hyper-graph. The every edge of pruned H o and H i must have and only have one vertex. Furthermore, the number of edges of H o and H i is equal. So we can get the i th edge of H o and the i th edge of H i , and then link the vertexes of two services in the edges. This is an edge in composite service. Combining all edges which we get, the composite service is generated. Fig. 6 shows the solution generating algorithm and Fig. 7

Experiments and Results

To evaluate the performance of our method, we have developed some experiments. And our evaluation consists of two parts. First, we compare SUTB [START_REF] Hashemian | A graph-based framework for composition of stateless web services[END_REF] with our method by the precision and composition time. Then we carry out some experiments on the test sets which are generated by the WSC 2009 Testset Generator to evaluate the method furthermore. This generator has three input parameters: concept number, service number and solution depth. In order to prove the scalability and efficiency of our algorithm in different and even extreme conditions, we generate five groups of test sets which have solution depth 10, 15, 20, 25 and 30 respectively. And each group contains three subgroup of different ratio of concept number and service number. We generate service number of test sets from 4000 to 20000 to make sure that our method has good scalability. Furthermore, we conduct experiments on each test set several times to get the average values. All experiments were performed on a PC platform with a Intel® Core™2 Duo 2.33GHz CPU, Windows XP, and 2 GB RAM and all algorithms were implemented in Java.

5.1

Compare with SUTB

We use the 5 Testsets of WSC'09 [START_REF] Kona | WSC-2009: A Quality of Service-Oriented Web Services Challenge[END_REF] to evaluate the precision and composition time of SUTB and HGSC(Hyper-Graph based Service Composition). The composition time is shown in Fig. 8. The composition time of SUTB is increased sharply from Testset01 toTestset05. But it is not true for HGSC. The composition time of HGSC has little changed. On the other hand, from Table II, the precision of HGSC is 100% while SUTB is only 20%. So we can conclude that HGSC has a better scalability and precision.

Experiments with Other Testsets

We use WSC 2009 Testset Generator to generate more testsets and evaluate HGSC furthermore. Fig. 9 shows the experiment results with different service number (4000-20000), concept number (8000-200000) and solution depth . From Fig. 9, we can find that the maximum composition time of HGSC is less than 180ms. In addition, with the change of service number, concept number and solution depth, the composition time varied little. So the HGSC has good scalability and can be applied in large number of service and concept.

Conclusion and Future Work

To handle QoS-aware service composition automatically and efficiently, a QoSaware hyper-graph based method is proposed in this paper. We show how to model the service composition problem as a hyper-graph and give the algorithms of generating hyper-graph, pruning strategy and solution generating. At last, to address the scalability, precision and performance of our method, some experiments are conducted and results show that our method has good scalability, efficiency and 100% precision.

In future work, we plan to develop the method in a distributed way.

Fig. 3 .

 3 Fig. 3. Hyper-Graph Generating Algorithm

Fig. 4 .Fig. 5 .

 45 Fig. 4. Pruning Algorithm

Fig. 7 .

 7 Fig. 7. Composite Service

Fig. 8 .

 8 Fig. 8. Composition Time of WSC'09 TestSet

Fig. 9 .

 9 Fig. 9. Composition Time of our method

TABLE 1 .

 1 CANDIDATE SERVICESThe request of user is R={{a,b,e},{f,g}}. According to the R, we add two virtual services I s ={{φ,{a,b,e}} and O s ={{f,g}, φ}. Then the H o and H i are drawn in Fig.1.

	Service Name	input	output	QoS
	s1	a, b	c, d	10
	s2	c	g	20
	s3	d, e	f	15
	s4	c	g	25
	s5	c, d	f, g	30
	s6	f, g	h	20
	s7	h, i	j	15

TABLE 2 .

 2 PRICISION OF SUTB AND HGSC

	TestSets	SUTB	HGSC	Optimal QoS
	TestSets01	780	500	500
	TestSets02	2100	1690	1690
	TestSets03	760	760	760
	TestSets04	2070	1470	1470
	TestSets05	4500	4070	4070

Acknowledgment

This work has been supported by the National Natural Science Foundation of China under Grant No. 61003253; the Natural Science Foundation of Shandong Province of China under Grant No. ZR2010FM031,ZR2010FQ010.


Guozhen Ren

Qingzhong Li

Yuliang Shi

Lizhen Cui

A Confidentiality-Guarantee Mechanism for SaaS

Keywords: SaaS, data confidentiality, trusted application server 1

In SaaS Applications, the data of tenants are stored in the untrusted service provider side, this case increases the risk of data leakage, and becomes the brief reason to prevent people and enterprise from taking SaaS mode for their applications. Correspondingly, confidentiality-guarantee has become the key factor of its large scale promotion. In this paper we propose a general secure mechanism that allows the sensitive data of tenants to be stored in encrypted mode, which guarantees data confidentiality on the assumption that application server is trusted, and then put forward the analysis of its security and performance.

Introduction

In software as a service (SaaS) applications, high efficiency of deployment, upgrading, and maintenance are the motivation of its development. But in this case, the data of tenants are stored in the service provider side, which increases the risk of data leakage. No tenants wish to lose data confidentiality in any case, therefore, data confidentiality-guarantee is very important for tenant deciding to adopt SaaS.

In the related research works, the secure problems of SaaS are usually divided into secure access control, data integrity protection, data privacy protection and data confidentiality protection [START_REF] Zwyhun | SaaS Data Security[END_REF]. Some research results focused on secure access control and data integrity had been put forward, and most of them were based on corresponding mechanisms in DAS and Web fields. But in SaaS applications, business logic calculation is executed in the service provider side and multiple tenants share data storage, which is essentially different from traditional applications, such that the traditional data confidentiality control mechanism cannot be directly applied to SaaS confidentiality-guarantee mechanism.

In this paper, we put forward a confidentiality-guarantee mechanism for typical SaaS framework under the trusted application computing environment. In this mechanism, we refer to the remote attestation method for trusted computing environment [START_REF] Dengguo | Research on Attestation Method for Trust Computing Environment[END_REF], and give the key agreements protocols which can transfer the data encryption key to the application server in security, and so the server can transparently encrypt/decrypt the data of tenants through the confidential engine in processing. And this can make the data of tenants to be stored in encrypted mode in database. This mechanism is secure supposing application system is trusted.

In fact, the data leakage events occurred in the data storage is the most of the actual data leakage occurrence. In our mechanism, sensitive data defined by tenants stored in the physical storage are all encrypted, thus to prevent this kind of leakage events completely. So our research work has practical significance. Specifically, this paper makes the following contributions:

1) We propose a confidentiality-guarantee framework supposing the application server is trusted, and point out its practical significance.

2) Design of a confidential-guarantee mechanism under the typical SaaS framework, and this mechanism secures data transparently to application developer.

The rest of this paper is organized as follows. Section 2 introduces the related works. Section 3 analyzes the confidential problem in general SaaS model, and gives the hypothesis and the practical application of the scene of our research. Section 4 address a security framework in SaaS. Section 5 gives the corresponding security protocols and data encryption mechanism of the framework. Section 6 analyzes the security and performance of the mechanism. Experimental results are reported in Section 7. The paper concludes in Section 8 with the summary and future works.

2

Related Work

At present, the research works for data confidentiality-guarantee mechanism for SaaS is in its infancy. In the related area, research works focused on secure access control and integrity of data in SaaS, secure Data As Services (DAS), new encryption algorithms for database and trusted computing etc.

The research works of confidentiality in DAS can be divided into two cases which depend on the data be stored in document or database. For the former, there are key word query mechanism in literature based on document encryption storage [8,9,12,13] . In these mechanisms, documents are switched to cipher before stored to untrusted service center, mechanisms offer key word search when customers use these documents, the inquired content will be decrypted and used after being transferred to client side, which realizes confidentiality protection of document content. And, the literature [START_REF] Hacigumus | Search on Encrypted Data[END_REF] puts forward a multiple key words query mechanism over documents encrypted, in condition of the main document encryption, it storages multiple keywords based on message hidden methods, and gives a multiple key word query mechanism which supports and/or query operation of query builder. Literature [START_REF] Hacigumus | Search on Encrypted Data[END_REF] also give a complete solution about database mode on base of literature [START_REF] Aggarwal | Two Can Keep a Secret: A Distributed Architecture for Secure Database Services In Proc. of CIDR[END_REF][START_REF]GOH Secure Indexes[END_REF][START_REF] Hac~gumug | Encrypted Database Integrity in Database Service Provider Model[END_REF][START_REF] Hacigumug | Providing Database as a Service[END_REF]. Based on order preserving encryption algorithm and fully homomorphic encryption, the mechanism supports basic compare operator and arithmetic operator and SPJ (select-project-join) operations for SQL query, and gives the query optimization mechanism.

With the development of SaaS application, Secure problems quickly become a hot spot in the study of the industry, literature [START_REF] Zwyhun | SaaS Data Security[END_REF][START_REF] Jie | Framework for Native Multi-Tenancy Application Develoment and Management[END_REF] classify secure problems systematically. Now there are dual authentication and RBAC mapping for tenants to answer for problems in secure access control and authorized management [19] . With redundant tuples and digital signature technology, problems are partly solved in data integrity protection. But for data privacy and data confidentiality, Only SSL, AS2, S-FTP are put forward, these mechanisms can only solve data leakage problems in transmission, but can't solve leakage problems in the database level and application service level when sensitive data of tenants are stored in the untrusted service provider side. Literature [START_REF] Jie | Framework for Native Multi-Tenancy Application Develoment and Management[END_REF] puts forward that data confidentiality as a challenge in SaaS.

Research works about trusted platform are abundant, and the remote attestation mechanism under the TCG framework gets closed attention, integrity measure framework IMA [START_REF] Reiner | Design and implementation of a TCG-based intergrety mesurement architecture Proceeding of the 13th Usenix Security Symposium[END_REF] and remote attestation mechanism based on the attribute certificate proposed by IBM research institute are typical in all of the works, in this direction, article [START_REF] Dengguo | Research on Attestation Method for Trust Computing Environment[END_REF] analyzes the problems of dynamic characteristic, concurrency and consistency for multiple remote attestation instance(Multi-RAI) in trusted computing environment, and propose a complete dynamic update attestation mechanism for Multi-RAI in trusted computing environment. This also provides a good reference for solving secure problems in SaaS.

In addition, in order to improve efficiency of data query over the encrypted messages, there are some research works about new practical encryption algorithm such as order preserving encryption. Literature [START_REF] Agrawal | Order Preserving Encryption for Numeric Data[END_REF][START_REF] Zhengfei | Efficient method of querying encrypt data[END_REF] give practical methods and make high efficient query over the integral and string data types, which provides very good help for SaaS confidentiality study.

Confidential Problem Analysis for SaaS

Participators here can be Tenant, SP and Attacker in general. 1) Tenant: Data owner in SaaS, hopes its sensitive information not to be snooped during information storage, transmission, and computational process.

2) SP: Service provider in SaaS, provide data storage and application service.

3) Attacker: Any offensive person or group except data owner, including other Tenant.

Considering data processing procedure in SaaS, the attacks can be classified in 3 cases.

1) Data storage attack: Data stored in SP maybe stolen by attackers who attack the system to get privileges of authority, or obtained by the data administrator who take advantage of the privileges of authority.

2) Data processing attack: Business logic is caculated in the SP application servers. It could be obtained by attackers, or snooped by data administrator.

3) Data transmission attack: In SaaS, data will be transmitted through the Internet, and kinds of attackers may get data though the public network.

Problems in data transmission above are consistent with those in data confidentiality of other applied modals of Web. Many fully developed schemes such as SSL can be employed directly to solve these problems. And for data processing secure problems we can adopt the trusted calculating environment, and this is a assumed condition in this paper.

Our study mainly starts from solving problems of data confidentiality in data storage under the scene of typical SaaS application.

The intrinsic difference of data confidentiality between SaaS and DAS applications is that business logic operations in DAS applications are processed in the Tenant side, while these operations are calculated in SP side. Though the homomorphic encryption had been prompted, but it's still far away from practical application regarding of its efficiency and realization.

Therefore, another new idea is considered based on practical application, namely operating system and application service system selected as the reliable system, database management system selected as the general business system.

Assumed conditions in the passage: 1) Application server cannot be traced, namely based on trusted application system.

2) Database is not reliable, namely the condition that database is easy to suffer attacks and data administrator is not reliable and so on.

These assumed conditions in practical mean that there's no secret divulging in the mechanism even though the whole database was disclosed. It is helpful when SP is averse from divulging data, however, some data administrator may get personal profit by divulging the data, and attackers break though safeguard in the database to get data. So, these assumed conditions do have practical significance.

Main Security Framework

As shown in Fig. 1, our security framework based on a general SaaS application. The Trusted Third Party(TTP) undertakes the key management tasks of our confidential mechanism, in the practical application, it may be Certificate Authority or other Key Management Center based on PKI. Tenant and SP take the same roles defined in section 3.

. Security Framework for SaaS

The mechanism includes key management protocols, secure data encryption key transmission and data encryption/decryption when Tenant taking the operation. Here are the main processes of our mechanism.

1) SP applies for its identity key from TTP. Under the mechanism, SP must get the identity key used in later confidential process before it offers the services to tenants. The detail process is similar to the traditional certificate application, so we will not describe it in detail in this paper.

2) Tenant applies for its identity key and data encryption key from TTP. Tenant should get its identity key and data encryption key before registering in the SP if it wants to protect its data stored at SP.

3) Tenant configures its confidential policy.

Through the configuration services provided by the mechanism Tenant can set up its confidential policy which determines the tables or attributes needs to be encrypted.

4) Key Agreements Protocol. The system will invoke the Key Agreements Protocol when the Tenant login the application server, and the procedure will transfer the data encryption key securely to application server. In practical the data encryption key could be cached, and so get relative high performance.

5) Data Encryption/Decryption. In the processing procedure, data need protected according to the policy will be encrypted transparently by confidential engine before being stored to physical storage, and decrypted from cipher after reading out from database.

Key Agreements and Algorithms

The key management in the initial phase is similar to traditional method under PKI, we will not describe it in detail here, and supposing that Tenant and SP all have obtained their own needed identity keys, and the data encryption key of Tenant here has been generated and stored at TTP. Here are the notations for this paper, in Table 1.

Table 1. Notations used in this paper

Notation

Comments R S Denotes that relation R owned attributes need to be encrypted.

RA e

Denotes that attribute A in R needs to be encrypted. T S Denotes that tuple T owned encrypted attribute value. TA e

Denotes that the attribute value A in T is encrypted. Ek() Encrypt using key k, in symmetric encryption mechanism. Dk() Decrypt using key k, in symmetric encryption mechanism. EPpk() Encrypt using key pk, in asymmetric encryption mechanism. DPsk() Decrypt using key sk, in asymmetric encryption mechanism. Ssk() Sign using key sk, in asymmetric encryption mechanism. Vpk() Verify using key pk ,in asymmetric encryption mechanism.

Data Confidential Configuration Service

ConfidentialConfigure: Data Confidential Configuration Service supported by the mechanism, which tenants can dispose their confidential policy through it, and the confidential engine will protect data transparently base on the policy. The service can be expressed as:

Input: R(A 1 ,…,A n ); Output:
R S (A 1 ,…A i e ,…), at least one attribute nominated to be Encrypted. and the service stores policy: ((R S name1 ,(A 1 e ,…,A m1 e )), …).

Key Agreements Protocol

Without loss of practical nature, we suppose the initial keys used in the protocol had been dispatched to the Tenant, SP and TTP, as described below.

SP: Asymmetric key pair (sksp,pksp), Symmetric key (k sp ) used for encrypting the tenant data encryption key temporary.

Tenant: Asymmetric key pair (skti,pkti) for Tenant i. TTP: Asymmetric key pair (skttp,pkttp), kti for Tenant i, which be used for encrypting data.

Base on the upper notations we give the detail description of the Key Agreements Protocol in Sequence diagram below. See Fig. 2.

Fig. 2. Key Agreements Protocol for kti Transmission

As shown in Fig. 2, the k ti is encrypted by destination public key in the protocol, and this can ensure its safety. The random number r is used to ensure the process' integrity, also to assure the k ti is available after running the protocol. We use Ek tp (k ti ) to substitute EP pksp (k ti ) for higher performance. In the practical applications, the k ti could be cached in the process procedure. This way can keep a higher efficiency.

Data Encryption/Decryption

In this mechanism, as shown in Fig. 1, the encrypt/decrypt runned by the confidential engine automatically, the detail process is transparent to the application, which imply that application developer can get higher developing efficiency under this Framework.

1) Data Encryption Data is encrypted before the system storing it to database, and this also occurring before sending SQL for query to database management. The confidential engine invokes the encryption service according to the confidential configuration to encrypt We designed two experiments to compare the cost between query over cipher and query over plain text, one for accurate query, and another for range query. The symmetric encryption mechanism in experiment is TEA.

The data scale in experiments we designed is in Table 2.

Experiments Configuration

The developing language is Java, the database is Oracle9i, the operating system is Windows Server2003. The memory of computer is 4G, CPU is Intel P8800(2.66GHz). The experiment result shows that, the costs of the accurate query increase not so much, we can say that it is linear increment according to data magnitude. But for the range query, it shows a sharp increase in costs, the main reason is that the cipher has

Experiments

Conclusions and Future Works

In this paper, we give a general confidentiality-guarantee mechanism in practical SaaS applications, the main frame of the mechanism can also be easy used for data integrity protection and data privacy protection. We analyzed the security of our mechanism. The experiments result shows that it keeps high performance when used for the accurate query, but the effectiveness of the mechanism is invalidate when used in range query. Considered the strong security of the symmetric encryption mechanism the mechanism adopted, it fits for the critical and small-scale data, such as metadata and configuration data etc.

We will intend to develop the more practical encryption method in range query, and we will also pay close attention to data integrity and data privacy protection mechanism in our future works.

Fig. 1

 1 Fig. 1. Security Framework for SaaS

  (Tid|r))|EPpkttp(Tid|r) Sskttp(EPpkti(kti|r))| EPpkti(kti|r) Sskti(EPpksp(kti|r))|EPpksp(kti|r) Ekti(r) Get a random r. Send kti request message to TTP Verify the signature,if pass sign and send the encrypted kti|r to Tenant,else failure Sign and send the encrypted kti|r to SP Verify the signature,if pass get kti|r = DPsksp(EPpksp(kt|r)) Encrypt the kti use ktp and send Ekti(r) to Tenant Decrypt x=Dkti(Ekti(r)), if x=r then succees

Fig. 3 .Fig. 4 .

 34 Fig. 3. Costs for Accurate Query

  in traditional encryption we adapt, so we have to decrypt all the rows of table.

Table 2 . Data Scale for Experiments.

 2

	No.	Type	Tenants	Tuples	Result scale
	1	Accurate query	10,10 2 ,10 3	10 3	10
	2	Range query	10 2	10 2 ,10 3 ,10 4	10

Acknowledge

The work is supported by the National Natural Science Foundation of China under Grant No. 61003253; the Natural Science Foundation of Shandong Province of China under Grant No.2009ZRB019YT , ZR2010FM031, ZR2010FQ010 and ZR2010FQ026; Key Technology R&D Program of Shandong Province under Grant No. 2010GGX10105.)

the attribute and substitute corresponding plaintext by the cipher in SQL text. The method is described as follows.

sConfig=

Security Analysis

Considered the Key Agreements Protocol shown in Section 5, the sensitive data are only exposed in the memory of the application server, this case implies that the mechanism can ensure the data safety under the assumption that application services run in the trusted computing environment.

For the data encryption key k ti , Fig 2 shows that the key is encrypted by the public key in asymmetric encryption mechanism in the whole transmission procedure, and only the message receiver can disclose it. Attacker can't get the key only if he can break the asymmetric encryption mechanism.

The sensitive data are encrypted in the physical storage, and the key used for encryption is not stored in physical storage of SP, so the data will be kept safety even if the Attacker can steal the cipher from database.

Above all, the mechanism this paper offered can ensure the sensitive data safety under the hypothesis we defined.