Indrajit Ray
email: indrajit@cs.colostate.edu

Dieudonne Mulamba
email: mulamba@cs.colostate.edu

Indrakshi Ray
email: iray@cs.colostate.edu

Keesook J Han
email: keesook.han@rl.af.mil

A Model for Trust-based Access Control and Delegation in Mobile Clouds

Keywords: access control model, delegation, mobile cloud security, trust

Multi-tenancy, elasticity and dynamicity pose several novel challenges for access control in mobile smartphone clouds such as the Android TM cloud. Accessing subjects may dynamically change, resources requiring protection may be created or modified, and a subject's access requirements to resources may change during the course of the application execution. Cloud tenants may need to acquire permissions from different administrative domains based on the services they require. Moreover, all the entities participating in a cloud may not be trusted to the same degree. Traditional access control models are not adequate for mobile clouds. In this work, we propose a new access control framework for mobile smartphone clouds. We formalize a trust-based access control model with delegation for providing fine-grained access control. Our model incorporates the notion of trust in the Role-Based Access Control (RBAC) model and also formalizes the concept of trustworthy delegation.

Introduction

Smartphones and other mobile devices are increasingly shifting the personal computing model away from traditional desktops and laptops to mobile cloud computing. In this model, cloud computing, mobile devices and networks seamlessly interact with each other to provide newer types of services that were previously not possible (such as location based services). The unique characteristics of mobile cloud computing -namely, multi-tenancy, elasticity, massive scalability [START_REF] Mell | The NIST Definition of Cloud Computing[END_REF], and mobility -introduce novel challenges to authorization and access control. To begin with, multi-tenancy results in the co-residency of machines (virtual machines, database engines etc.) and other resources owned by different clients or tenants at the same privileged position in the cloud with respect to one another. As a result, a guest operating system can exploit vulnerabilities in the hypervisor and run processes on other guests or the host, and security breaches can arise in one smartphone client and propagate to another easily via the cloud. Proper authorization and access control techniques should therefore not only protect tenant resources from un-authorized disclosure and modification from attackers, but also should Approved for Public Release; Distribution Unlimited:88ABW-2013-2127 dated 02 May 2013 allow segregation of tenants from one another, and isolation of computation, storage and network resources of the mobile cloud provider from tenants.

A mobile cloud environment is inherently very dynamic. The accessing entities may change, resources requiring protection may be created or modified, and an entity's access to resources may change during the course of an application execution. Users need to dynamically acquire permissions from different domains based on the services they need. Interactions among entities may occur in ad hoc manners and where the accessrequesting entity may not be known in advance by the access-granting entity. In such situations, traditional identity-based access control models such as Discretionary Access Control (DAC), Mandatory Access Control (MAC) [START_REF]Trusted Computer System Evaluation Criteria[END_REF], or Role-based Access Control (RBAC) [START_REF] Sandhu | Role Based Access Control Models[END_REF][START_REF] Ferraiolo | Proposed NIST Standard for Role-Based Access Control[END_REF], that rely on the access-granter knowing the identity of access requester beforehand and authenticating the requester, can no longer be applied. Last but not least, in a mobile cloud environment resources are often distributed and managed by different service providers and clients move from one service provider to another to obtain the needed service. To support a specific service, there is frequently the need for coordination and interaction between these different providers. A tenant of one service provider may need to access other providers to obtain the relevant service. This is illustrated by the application scenario in Fig. 1. A mobile smartphone user invokes the voice assistant application (VAC) on her smartphone and instructs it to make a reservation for that evening's show at an en-route theater closest to her destination. VAC computes the time to reach the destination by accessing a navigation service (NavC), identifies candidate theaters by consulting a location service (LocC) and selects one from the list, contacts a ticket service provider cloud (TktC) for a reservation and contacts the user's mobile wallet provider (MobWC) to purchase the ticket from TktC.

For accessing different services the authorization sequence can potentially be as follows. The user initially authorizes the VAC for the ticket purchase task; however the VAC cannot carry out the task on its own and therefore needs to pass on the authoriza-tion (or portions thereof) to various other cloud providers. Moreover, if the different service providers are all tenants of one or more infrastructure cloud(s) (as shown in Fig. 1), then each service provider needs to rely on the infrastructure to manage access control to its resources. Delegation of authorization is the principle that allows one service provider to act on behalf of the user to make the user's access rights available to other service providers. There is a need to manage and mediate interactions with distributed resources having distributed administrators. However, authentication of the requesting client (required in conventional access control) may be difficult in mobile smartphone cloud systems. For example, it may not be possible for the VAC to be registered with both the MobWC and the TktC. Hence, delegation may need to proceed without associated authentication. This is further complicated by the fact that often the privilege to delegate may itself need to be delegated.

In this work, we propose a new trust-based access control model that supports complex delegation across different members of the mobile cloud for providing fine-grained access controls. This model is based on extensions to the RBAC model, and adapts concepts from the trust-based access control models proposed earlier by us [START_REF] Chakraborty | TrustBAC: Integrating Trust Relationships into the RBAC Model for Access Control in Open Systems[END_REF][START_REF] Toahchoodee | A Trust-Based Access Control Model for Pervasive Computing Applications[END_REF]. We assume an existing context sensitive non-binary trust model such as the one in [START_REF] Ray | An Interoperable Context Sensitive Model of Trust[END_REF]. For this work, we identify the different trust-based access control model elements that are needed for addressing specific challenges in smartphone clouds (Section 3.1), and the relationships among those elements (Section 3.2). We formalize the model and give the rules of access (Sections 3.3 and 3.4). The smartphone cloud system is very dynamic and allows frequent updates to its RBAC relations. Using traditional RBAC relations to control delegation in such environments is of limited advantage because of the resulting inconsistencies in role hierarchy. We adapt the notion of administrative scope to resolve dynamically any inconsistency involved in controlling delegations (Section 3.5). Finally, we propose algorithms to perform trust-based delegation, including chained delegation (Section 4).

Related Work

Role-Based Access Control (RBAC) is used extensively within organizations for administering and managing privileges and is often considered the de-facto standard for access control.

While the advantages of RBAC are numerous, researchers are increasingly identifying limitations in the model for newer and emerging applications. The biggest limitation is the lack of support for delegation in the standard RBAC model and the failure to support dynamic adaptation of access control policies based on changing needs. Many researchers have extended RBAC to support delegation [START_REF] Barka | Framework for Role-Based Delegation Models[END_REF][START_REF] Barka | A Role-Based Delegation Model and Some Extensions[END_REF][START_REF] Crampton | Delegation in Role-Based Access Control[END_REF][START_REF] Tamassia | Role-Based Cascaded Delegation[END_REF][START_REF] Wainer | A Fine-Grained, Controllable, User-to-User Delegation Method in RBAC[END_REF][START_REF] Zhang | A Rule-Based Framework for Role-Based Delegation and Revocation[END_REF][START_REF] Zhang | A Flexible Delegation Model in RBAC[END_REF]; however these models fail to support the need for ad hoc authorization and ad hoc delegation and thus cannot readily be adapted to the cloud environment. Researchers have also proposed Credential-based or Attribute-based access control models [START_REF] Bonati | A Unified Framework for Regulating Access and Information Release on the Web[END_REF][START_REF] Bobba | Using Attribute-Based Access Control to Enable Attribute-Based Messaging[END_REF] to address the challenges of unknown users in access control. Unfortunately, these models do not allow access control decisions to be dynamically updated or revoked based on the history of the requester, or based on changing requirements of the requester. Recently, researchers have proposed the notion of risk-adaptable access control models [START_REF] Cheng | Fuzzy Multi-Level Security: An Experiment on Quantified Risk-Adaptive Access Control[END_REF][START_REF] Mcgraw | Risk-Adaptable Access Control[END_REF][START_REF] Kandala | An Attribute Based Framework for Risk-Adaptive Access Control Models[END_REF] and trust-based access control models [START_REF] Chakraborty | TrustBAC: Integrating Trust Relationships into the RBAC Model for Access Control in Open Systems[END_REF][START_REF] Bhatti | A Trust-based Context-Aware Access Control Model for Web-Services[END_REF][START_REF] Ya-Jun | An Access Control Model for Ubiquitous Computing Application[END_REF] to facilitate dynamic adaptation of access control policies based on operational needs and situational awareness. A recent work [START_REF] Baracaldo | A Trust-and-Risk Aware RBAC Framework: Tackling Insider Threat[END_REF] combines these two philosophies into one comprehensive model. However, none of these works address the problem of delegation in mobile cloud systems. Nonetheless, these approaches look promising and form the basis of the current model.

SOD

Formal access control model with delegation

The proposed trust-based access control model is defined in terms of a set of elements and relations among those elements with trust-based constraints defined on these relations. We use a modified graph-theoretic approach similar to the one proposed by Chen and Crampton [START_REF] Chen | On Spatio-Temporal Constraints and Inheritance in Role-Based Access Control[END_REF] to express the model semantics. This model is designed to integrate delegation and revocation, with revocation being the reverse process of delegation. The model offers the possibility to perform a single-step as well as a multi-step delegation and revocation. It enables both roles and permissions to be delegated. Fig. 2 provides a schematic overview of the proposed model. We use the access control scenario from Figure 1 to exemplify the model.

Model elements

The model elements are of the following types: user, user properties, role, object, action, permissions, constraints, trust level, session instance, session type, session, and session history. The corresponding element sets are represented by the symbols U, Prop, R, O, Act, P, Const, D, S I , S T , S, S H .

In this model, roles are separated into two broad classes: regular roles and delegatable roles. A user cannot delegate permissions assigned to a regular role, while permissions assigned to a delegatable role can be delegated. The cloud system is responsible for creating each regular role, while each delegatable role is created and owned by an individual user. Therefore, a regular role is a durable role, while a delegatable role is temporary, created and deleted at the user's discretion. In the cloud system, each user owns a set of delegatable roles that form a role hierarchy determined by the user. All user assignment to regular roles relations and all permission assignment to regular roles relations are managed by the cloud system, while each individual user is responsible for managing all user assignment to delegatable roles relations and all permission assignment to delegatable roles relations.

user A user u ∈ U is a human being, a device, an organization or any active agent running on behalf of these. Three categories of users can be found in the cloud, namely, tenant, a tenant-as-provider, and a provider. A tenant is a user that is receiving regular services offered in the cloud, while a tenant-as-provider is a cloud user that is receiving regular services as well as offering regular services. The last category, provider, refers to the cloud provider. To understand these notions, let consider the example of Netflix that uses Amazon's cloud. A Netflix subscriber is a tenant, while Netflix is the tenant-as-provider. The provider in this case is Amazon's cloud. user properties Each user u has a certain set of properties P u , called user properties.

The set Prop = u∈U P u . A user can manifest any subset P u of P u (i.e., P u ∈ 2 P u ) in a particular session. User properties are used in our model to compute trust levels of users (see later in the list). Some examples of elements of user properties are: user credentials, public key certificates, and membership in groups. role The concept of role is the same as in the RBAC model. A role r ∈ R is a job function with some associated semantics regarding the responsibilities conferred to the user. A user assigned to a role specifies the operational needs of the cloud. The set of roles R can be further subdivided into six disjoint subsets as follows:

1. TENANT-REGULAR-ROLE (T RR) -A set of job functions that are relevant for receiving regular services. For example, the human user in our scenario can be an elite member with the mobile wallet service provider that bestows him with certain privileges. In this case "elite member" will be an example of a tenant-regular role. 2. TENANT-DELEGATABLE-ROLE (T DR) -A set of job functions that are relevant for delegating services. Going back to our earlier scenario, the VAC instance working on behalf of the user to purchase tickets needs to have permission at the MobWC to use the user's wallet. Thus, a role such as "wallet user for ticket purchase" which the VAC needs to assume to execute the operation will be an example of tenant-delegatable-role.

TENANT-AS-PROVIDER-REGULAR-ROLE (T PRR)

-A set of job functions that are relevant for receiving regular services as well as offering regular services. The NavC cloud is a provider of navigation services. It uses the infrastructure cloud to provide some of its services (such as the computation needed for the navigation). As a result, we will have a tenant-as-provider-regular-role "navigation computation" at the infrastructure cloud. 4. TENANT-AS-PROVIDER-DELEGATABLE-ROLE (T PDR) -A set of job functions that are relevant for receiving as well as offering delegation services. The VAC will have a tenant-as-provider-delegatable role "make ticket reservation" that will allow it to delegate different components of the ticket reservation. 5. PROVIDER-REGULAR-ROLE (PRR) -A set of job functions that are relevant for providing regular services. The instance of MobWC that will access the user's wallet needs to have permission to debit the wallet to provide the service. Thus, an example of this role will be "debit user wallet" that the instance of MobWC needs to acquire for this task. 6. PROVIDER-DELEGATABLE-ROLE (PDR) -A set of job functions that are relevant for providing delegation services. Assume that the TktC offers the ticketing service by using a database provider cloud to keep record of the transaction. Thus, an instance of the TktC that is performing the ticketing operation for the current user needs to delegate the record update operation to the database provider. A "decrement available seats" role will be an example of a providerdelegatable-role in this scenario. object An object o ∈ O is a data resource as well as a system resource. It can be thought of as a container that contains information. The set O (OBJECTS) is partitioned into three subsets: 1. TENANT-OBJECTS (T O) -Objects from this set are accessed when some services are needed. An example is the user's wallet at the MobWC. 2. TENANT-AS-PROVIDER-OBJECTS (T PO) -Objects from this set are accessed for receiving as well as providing services. An example is the database used by the TktC to keep record of transactions. 3. PROVIDER-OBJECTS (PO) -Objects in this set are accessed purely for providing services. Examples include objects used by the infrastructure cloud such as network objects. action An action a ∈ A is an executable image of a program that operates on some object. The set A (ACTIONS) may have three subtypes ACTIONS: 1. TENANT-ACTIONS (TA) -This set of actions act on objects from the set TENANT-OBJECTS. An example is "debit wallet". 2. TENANT-AS-PROVIDER-ACTIONS (T PA) -This set is comprised of actions that operate on elements of TENANT-AS-PROVIDER-OBJECTS. An example is "update database". 3. PROVIDER-ACTIONS (PA) -This set is comprised of actions that operate on elements of PROVIDER-OBJECTS. An example is "perform read on disk". permission A permission p ∈ P is an authorization to perform a certain task within the system. A permission is assigned to a role. The set P (PERMISSIONS) is partitioned into three subsets as follows:

1 trust level A trust level ∈ D is a real number between 0 and 1, with 0 being the lowest level of trustworthiness and 1 the highest and intuitively encodes the security risk of the access decision. The larger the value of the trust level the less risky it is to grant access to the user. A user u associated with a role r at some instant of time has a trust level. The function T (u, r) gives the trust level of the corresponding user associated with the role r. role trust range A role trust range is an interval [rt min , 1] that is associated with roles.

The role trust range indirectly encodes the situational factors under which the access decision is made. Each role r ∈ R is associated with a role trust range that gives the minimum trust value rt min required for a user to be assigned to the corresponding role. The function L (r) returns the value rt min for the given role r. permission trust range A permission trust range is an interval [pt min , 1] that is associated with permissions. Each permission Perm ∈ P is associated with a permission trust range that gives the minimum trust value pt min required by a role to be assigned the corresponding permission. The function L (Perm) returns the value pt min for the given permission Perm. constraint A constraint ∈ Cons is defined as a predicate which when applied to a relation between two elements returns a value of "acceptable" (True or 1) or "notacceptable" (False or 0). Constraints can be viewed as conditions imposed on the relationships and assignments and encode the situational factors under which access decisions need to be made. session instance A session instance ∈ S I is a 'login' instance of an user. It is the set of roles activated by the user in that login instance. A user can instantiate multiple logins thereby initiating multiple session instances at the same time. A session instance is uniquely identified by a system generated id. session type A session instance is identified with a type that is defined by the set of user properties manifested in that session instance by the user. For a session instance u s activated by a user u with set of properties Prop u (Prop u ⊆ P u ), the session type is prop u . Formally, the set S T = 2 Prop . session A session ∈ S is identified by a session instance with a session type. A session with session instance u s and type Prop u is denoted by the symbol u s prop u . Formally, S = S I × S T . session history A session history ∈ S H is a set of information regarding the user's roles, behavior and trust levels in a previous use of a session of that type.

User-role and permission-role assignment

We propose a graph theoretic semantics for our model. An authorization graph is defined in terms of a set V of vertices and a set E of edges. The set of vertices V = U ∪ T RR ∪ T DR ∪ T PRR ∪ T PDR ∪ PRR ∪ PDR ∪ T P ∪ T PP ∪ PP corresponds to the entities users, tenant-regular-roles, tenant-delegatable-roles, tenant-as-provider-regularroles, tenant-as-provider-delegatable-roles, provider-regular-roles, provider-delegatableroles, tenant-permissions, tenant-as-providers-permissions and provider-permissions respectively. The set of edges E = URRA ∪ UDRA ∪ PRRA ∪ PDRA ∪ RRH a ∪ DRH a ∪ RRH u ∪ DRH u corresponds to the different relationships between the model's entities.

We now define some relationships with roles that form the building block for the access control model, as follows:

Definition 1. User-Regular-Role Assignment (URRA) = (U × T RR) ∪ (U × T PRR) ∪ (U × PRR
) is a many-to-many relationship that provides the regular roles to which different users can be assigned in the cloud. It is represented as a pair of user-regularroles.

Definition 2. User-Delegatable-Role Assignment (UDRA) = (U ×T DR)∪(U ×T PDR) ∪ (U × PDR) is a many-to-many relationship identifying delegatable roles to which different users can be assigned in the cloud. This relationship is represented as a pair of user-delegatable-roles. Definition 3. Permission-Regular-Role Assignment (PRRA) = (T RR × T P) ∪ (T PRR × T PP) ∪ (PRR × PP) is a many-to-many relationship providing the set of permissionregular-roles that indicate to regular roles which permissions they are allowed to acquire.

Definition 4. Permission-Delegatable-Role Assignment (PDRA) = (T DR × T P) ∪ (T PDR × T PP) ∪ (PDR × PP) is a many-to-many relationship providing the set of permission-delegatable-roles identifying the permissions for which delegatable roles are authorized.

The role-hierarchy defines parent-child relationships between different roles. This allows for easy administration of roles by reducing the number of explicit assignments in the URRA, UDRA, PRRA, and PDRA relations. Regular roles are organized in a Regular-Role-Hierarchy while delegatable roles are organized in a Delegatable-Role-Hierarchy with the two hierarchies being disjoint. We define the two hierarchies as follows:

Definition 5. The Role-hierarchy (RH) = ℜ × {a, u}, is a partial order on the set of roles where ℜ = ((T RR × T RR) ∪ (T PRR × T PRR) ∪ (PRR × PRR)) in case role is a regular role. In the same case RH is written RRH to represent a regular role-hierarchy. When considering the case when role is a delegatable role, then (ℜ = ((T DR × T DR) ∪ (T PDR × T PDR) ∪ (PDR × PDR)), and RH becomes DRH to represent a delegatable role-hierarchy. The set {a, u} can be considered as one of these :

the role-activation hierarchy the permission-usage hierarchy Let ≤ a denote the reflexive transitive closure of ℜ a while ≤ u denotes the reflexive transitive closure of ℜ u . Then role-activation hierarchy and permission-usage hierarchy are defined as follows. Definition 6. Role-activation hierarchy (ℜ a ) = {(r, r ) : (r, r , a) ∈ ℜ} is a subset of ℜ such that a user u may activate a role r in a session instance if there exists a role r such that {u, r } ∈ URRA and r ≤ a r if r and r are regular roles, or {u, r } ∈ UDRA and r ≤ a r when r and r are delegatable roles. Definition 7. Permission usage hierarchy (ℜ u ) = {(r, r ) : (r, r , u) ∈ ℜ} such that a user is authorized for permission p if there exists roles r, r such that u may activate r , with (p, r) ∈ PRRA and r ≤ u r in the case r, r are regular roles, or with (p, r) ∈ PDRA and r ≤ u r when r, r are delegatable roles. In the first case ℜ u becomes RRH u , while it becomes DRH u when roles are delegatable.

Evaluating access requests

The cloud security administrator assigns trust constraints in the form of a corresponding trust interval to roles, permissions, and other associations between entities based on different characteristics of each model. Note that in the cloud structure, users, tenants or providers of the senior role can perform the same set of duties as its junior role; hence an entity who will be assigned to the senior role require more trustworthiness than the entity who will be assigned to junior role only. Based on this observation, when we introduce the notion of trust value, we assume that the trust value of the senior role always dominates the trust values of its junior roles.

We have previously proposed the notions of activation path, usage path and access path in [START_REF] Toahchoodee | A Trust-Based Access Control Model for Pervasive Computing Applications[END_REF] to evaluate if an access control request should be denied or granted according to the current policy. We adapt and extend these notions here to determine access request for mobile smartphone clouds. Definition 8. An activation path (or act-path) between two nodes v 1 and v n in the authorization graph is a sequence of vertices v 1 , . . . , v n ∈ E such that either (v 1 , v 2 ) ∈ URRA and (v i-1 , v i ) ∈ RRH a for i = 3, . . . , n on a regular-role hierarchy or (v 1 , v 2 ) ∈ UDRA and (v i-1 , v i ) ∈ DRH a for i = 3, . . . , n on a delegatable-role hierarchy. Definition 9. A usage path (or u-path) between two nodes v 1 and v n in the authorization graph is a sequence of vertices v 1 , . . . , v n ∈ E such that either and(v n-1 , v n ) ∈ PDRA on a delegatable-role hierarchy. Definition 10. An access path (or acs-path) between two nodes v 1 and v n in the authorization graph is a sequence of vertices v 1 , . . . , v n , such that (v 1 , v k ) is an act-path, and

(v i , v i+1 ) ∈ RRH u for i = 1, . . . , n -2, and (v n-1 , v n ) ∈ PRRA on a regular-role hierarchy or (v i , v i+1 ) ∈ DRH u for i = 1, . . . , n -2,
(v k , v n ) is an u-path.
Based on these definitions of usage path, access path and activations we propose three different access control models, namely, the standard model, the strong model and the weak model. The models differ with respect to the trust constraints that must be satisfied by the entities for the authorization to be successful.

The standard model

In the standard model, individual entities are associated with trust values and describe how much the user is trusted to perform a specific role. The role trust range associated with a tenant role, a tenant-as-provider role or a provider role specifies the minimum trust level with respect to that role that the user has to acquire in order to activate the corresponding role. Similarly, the permission trust range associated with a tenantpermission, tenant-as-provider-permission or provider-permission specifies the minimum trust level with respect to the current role of the user, that needs to be acquired in order to invoke these permission.

Let the trust values for the user be specified by a function T :

((U h × R h ) ∪ (U d × R d )) → t ∈ D
and the trust ranges for role and permission by functions L :

(R ∪ P) → [l, 1] ⊆ D.
-For u ∈ U, r ∈ R, T (u, r) denotes the trust value of u with respect to r; -For r ∈ R, L (r) denotes the trust interval in which r is active;

-For p ∈ P, L (p) denotes the trust interval in which p is active.

For any path v 1 , . . . , v n in the graph G = (V, E, T , L ), where E = URRA ∪UDRA ∪ PRRA ∪ PDRA ∪ RRH a ∪ DRH a ∪ RRH u ∪ DRH u , we write L (v 2 , . . . , v n ) = L (v 2 , v n ) ⊆ D to denote n i=2 L (v i ). In other words, L (v 2 , v n ) is the trust interval in which every vertex v i ∈ R ∪ P is enabled.
Authorization in the Standard Model is based on the policy decision point making the following three determinations corresponding to the requested access:

1. Is the role that the user needs to activate in the current session in order to acquire the desired permission, authorized for the permission? 2. Can the user activate the corresponding role? 3. Is the user authorized for the desired permission?

If the policy decision point makes a positive determination for all these conditions a decision to allow the access is made. These three determinations are made based on the following propositions.

Proposition 1. A role v 1 ∈ R is authorized for permission v n ∈ P if and only if there exists an u-path v 1 , v 2 , . . . , v n and L (v 1 ) ⊆ L (v 1 , v n ). Proposition 2. A user v 1 ∈ U may activate role v n ∈ R if and only if there exists an act-path v 1 , v 2 , . . . , v n and T (v 1 , v 2 ) ∈ L (v 2 ).
Proposition 3. A user v 1 ∈ U is authorized for permission v n ∈ P if and only if there exists an acs-path v 1 , v 2 , . . . , v k , . . . , v n such that v k ∈ R for some k, v 1 , . . . , v k is an actpath, v k , . . . , v n is a u-path, v 1 can activate v k , and v k is authorized for v n .

Controlling delegation

A delegation operation temporarily changes the access control state so as to allow the delegatee to use the initial user's access privileges. Delegation operations are classified into two kinds: grant operations and transfer operations [START_REF] Barka | Framework for Role-Based Delegation Models[END_REF]. Grant operations are defined by grant delegation models and allow the delegated access rights to be available to both the delegator and the delegatee, after a successful completion of a delegation operation. Transfer operations, on the other hand, are defined by transfer delegation models to allow the delegated access right to be acquired by the delegatee, while preventing the delegator from continuing to use the delegated access right. Most works done in this field focus on grant operation [START_REF] Barka | Framework for Role-Based Delegation Models[END_REF][START_REF] Barka | A Role-Based Delegation Model and Some Extensions[END_REF][START_REF] Tamassia | Role-Based Cascaded Delegation[END_REF][START_REF] Wainer | A Fine-Grained, Controllable, User-to-User Delegation Method in RBAC[END_REF][START_REF] Zhang | A Rule-Based Framework for Role-Based Delegation and Revocation[END_REF][START_REF] Zhang | A Flexible Delegation Model in RBAC[END_REF]. Crampton and Khambhammettu first introduced the notion of transfer operation in [START_REF] Crampton | Delegation in Role-Based Access Control[END_REF].

Designing a mechanism for delegation control involves specifying under which condition a delegation operation is permitted. This requires resolving, in order, the following two issues: (1) Determine whether or not a given user is authorized to delegate a role or permission available to the user. (2) Determine whether a given role or permission can be delegated to a user.

Relations have been the main way to control delegation [START_REF] Barka | A Role-Based Delegation Model and Some Extensions[END_REF][START_REF] Zhang | A Rule-Based Framework for Role-Based Delegation and Revocation[END_REF][START_REF] Zhang | A Flexible Delegation Model in RBAC[END_REF] in role-based systems. Two principal relations, can delegate and can receive, are used for controlling delegation. Relations are suited to be used in a RBAC system but only where RBAC relations remain static. However, in a cloud system, RBAC relations, such the role hierarchy, are frequently updated. This situation can generate serious inconsistencies in relations can delegate and can receive that specify respectively, who is authorized to delegate access rights, and who is allowed to receive delegated access rights. For this reason, we have opted to use the concept of administrative scope [START_REF] Crampton | Administrative Scope: A Foundation for Role-Based Administrative Model[END_REF] to deal with delegation control. Administrative scope is a concept borrowed from RHA family of administrative models, and is defined as follows [START_REF] Crampton | Administrative Scope: A Foundation for Role-Based Administrative Model[END_REF].

Definition 11. Let r ∈ R. We define σ (r) the administrative scope of a role r as the set σ (r) = {r } such that if a role r ∈ σ (r) then in the graph formed by the role hierarchy, any path starting at r passes through r. Definition 12. Let s be a session activated by a user u. We define σ (s) the administrative scope of a session s as σ (s) = ∪ r∈s σ (r). The idea expressed by this definition is that the administrative scope of a session is simply the union of administrative scopes of all roles activated in the session s by the user u.

The concept of administrative scope provides us with a way to divide a role hierarchy graph into sub-hierarchies that form a natural unit of administration for the role r. Two approaches are the most favored for performing role-based administration, ARBAC97 and administrative scope. Among these two approaches, administrative scope is found to be a more flexible approach [START_REF] Crampton | Administrative Scope: A Foundation for Role-Based Administrative Model[END_REF]. This quality makes it suitable for rolebased delegation in a highly dynamic environment that is the cloud system.

Using administrative scope, a user u is allowed to delegate a role r only if r ∈ σ (s), the administrative scope of the users session. This limits the user to delegate only roles that are within his administrative scope. Administrative scope can be used to regulate who can receive a delegation. A user v is authorized to receive a delegation of a role r from user u if for all r < r such that r / ∈ σ (s), there exists r such that r ≤ r and (v, r ) ∈ UDA. In order words, the delegatee v is authorized to receive the delegation of a role r if v is already authorized for all role r < r. In order for the delegatee to receive a delegation, the idea is to require him to be already assigned to any roles outside the delegators administrative scope that the delegatee will inherit by successfully receiving the delegation.

Chaining Delegation and Transfer

A user that has previously received some access rights through a delegation process may decide to further delegate those rights. This can result in what can be called a chained delegation. In this delegation chain the trustworthiness of users is used by each node as a factor to decide about the level of delegation. These trust values form a trust chain. We use the notion of trust graph expressed in [START_REF] Toahchoodee | Towards Trustworthy Delegation in Role-Based Access Control Model[END_REF] to formalize the notion of trust chain in a given context. A trust graph T = (N, E) is a directed acyclic graph that is defined in terms of a set N of nodes and a set E of edges. Nodes represent entities in the delegation chain, while edges represent trust relationship between these entities. These entities could be either users or roles respectively for user delegation and role delegation.

Using trust graphs node n i trusting node n j can be represented by (n i , n j ). The degree to which an entity n i trusts n j is represented by a weight denoted by w(n i , n j ), 0 < w(n i , n j ) ≤ 1, on the edge (n i , n j ). In order to control the propagation of the access right during a delegation process, every entity puts a constraint on its trust relationship. This trust constraint is denoted by c(n i , n j ) where 0 < c(n i , n j ) ≤ 1. Access rights can be propagated only if c(n i , n j ) ≤ w(n i , n j ). This implies that delegation cannot be carried along every edge of the trust graph. Therefore identifying valid paths to carry on a delegation becomes a challenging problem. We consider the trust graph represented in Fig. 3. The numbers that are within boxes associated with the edges denote the trust values on the corresponding edges of the graph while the numbers that are not inside boxes denote the trust constraints. Assume that the entity J desires to identify all the valid paths it can use to delegate some access rights to entity K. Using the trust values and the trust constraints, first challenge is to determine all valid paths and thereafter to compute the transitive trust value for each of the found valid paths from J to K. We use three operators on trust values -a comparison operator to compare the trust value and the trust constraint, a parallel operator to find the minimum of two trust values, and a sequential operator that gives the product of two trust values. Definition 13. Comparison Operator : [0, 1] × [0, 1] → 0, 1 is a binary operation whose input is a trust value and a trust constraint, and that returns 1 when the trust value is greater or equal to the trust constraint. Otherwise, the operator returns 0. The comparison operator is used to identify all the valid paths in a trust graph. Those valid paths are the ones able to carry on the delegation from J to K. The checking of valid paths may return either multiple valid paths, or a single valid path. In either case, we need to compute the transitive trust value. The parallel operator is used to compute the transitive trust value in case of multiple valid paths while the sequential operator is used for the same purpose but in case of a single valid path.

These operators are used within algorithm 1 to find the transitive trust value. The algorithm works as follows. Using a set of edges of the trust graph given as input, the algorithm uses the comparison operator on each pair of edges that form an arc to compare its trust values to its trust constraint. All arcs whose trust value is at least equal to the trust constraint are retained. If after being linked those arcs form one or more paths from the source node to the destination node, then those paths are considered to be the valid paths. If the algorithm find multiple valid paths, it uses the parallel operator to find the path with the minimum transitive trust value. Otherwise, the algorithm uses the sequential operator to return the transitive trust value of the unique path. In case of multiple valid paths, we made the design decision to choose the path with the minimum transitive trust value in order to be more conservative and more protective. Choosing the path with a maximum transitive trust value is also a valid choice, but is not considered in this work.

To see how the propagation of delegation works, we use the trust graph in Fig. 3 and execute our algorithm in order to find the transitive trust value from node J to node K. Before running the algorithm on the given graph, a processing step is necessary. This preprocessing involves doing a Depth-First Search on the graph in order to collect all the arcs from nodes J to K. The result of the DFS is as follows. DFS(G) = (J,C), (C, D), (D, K), (C, B), (B, K), (J, A), (A, D), (A, B). This list of edges is provided to the algorithm as input.

Given the list of arcs, we run the algorithm as follows.

In this work, we formalized a trust-based access control model for providing finegrained access in smartphone clouds. The model extends traditional RBAC with the notion of trust and also addresses the problem of trustworthy delegations. A lot of work remains to be done. We plan to analyze this model and detect inconsistencies and errors in the policy specification. The access control configuration of the cloud is dynamic in nature. Towards this end, we plan to investigate how to perform access control analysis in real-time to ensure that security breaches do not occur. We also plan to deploy this model in real-world environments and study its impact on the performance and usability of cloud applications.

Fig. 1 .

 1 Fig. 1. Mobile smartphone cloud application illustrating need for delegation

  . TENANT-PERMISSIONS (T P) -The set of all ordered pairs T O, TA where T O ∈ TENANT-OBJECTS and TA ∈ TENANT-ACTIONS; that is, T P = 2 T O×TA . 2. TENANT-AS-PROVIDER-PERMISSIONS (T PP) -The set of all ordered pairs T PO, T PA where T PO ∈ TENANT-AS-PROVIDER-OBJECTS and T PA ∈ TENANT-AS-PROVIDER-ACTIONS; that is, T PP = 2 T PO×T PA . 3. PROVIDER-PERMISSIONS (PP) -The set of all ordered pairs PO, PA where PO ∈ PROVIDER-OBJECTS and PA ∈ PROVIDER-ACTIONS; that is, PP = 2 PO×PA .

Fig. 3 .

 3 Fig. 3. Example of a trust graph

Definition 14 .

 14 Parallel Operator, denoted ⊕ : [0, 1] × [0, 1] → [0, 1], is a binary operator whose inputs are two trust values, and that returns the minimum of the two trust values.Definition 15. Sequential Operator, denoted ⊗ : [0, 1] × [0, 1] → [0, 1], is a binary operator whose inputs are two trust values, and that returns the product of these two trust values.

Acknowledgment

This work was supported in part by a fellowship from AFRL Information Institute under the 2012 Summer VFRP. The authors thank Graniero AFRL/RIB for his support of this research. The views and conclusions are those of the authors, and should not be automatically interpreted as representing official policies, either expressed or implied, of the Air Force Research Laboratory or other federal government agencies.

Algorithm 1 Algorithm to identify all valid paths for delegation propagation Input: edges e 1 , ..., e n Output: set of valid paths and transitive trust on the valid paths valid paths ← {} for all i : trans trust 1 = 0 + 0.6 ⊗ 0.7 ⊗ 0.8 = 0.336 trans trust 2 = 0 + 0.6 ⊗ 0.6 ⊗ 0.7 = 0.252 min = trans trust 1 ⊕ trans trust 2 = 0.336 ⊕ 0.252 trans trust 2 = 0.252 is the minimum transitive trust value. Therefore the valid path J,C,B,K is the one that will be used to propagate the delegation of access rights from J to K.


Liyue Fan

Li Xiong
email: lxiong@mathcs.emory.edu

Vaidy Sunderam

Differentially Private Multi-Dimensional Time Series Release for Traffic Monitoring

Keywords: Traffic Monitoring, Multi-Dimensional Time-Series, Differential Privacy

Sharing real-time traffic data can be of great value to understanding many important phenomena, such as congestion patterns or popular places. To this end, private user data must be aggregated and shared continuously over time with data privacy guarantee. However, releasing time series data with standard differential privacy mechanism can lead to high perturbation error due to the correlation between time stamps. In addition, data sparsity in the spatial domain imposes another challenge to user privacy as well as utility. To address the challenges, we propose a real-time framework that guarantees differential privacy for individual users and releases accurate data for research purposes. We present two estimation algorithms designed to utilize domain knowledge in order to mitigate the effect of perturbation error. Evaluations with simulated traffic data show our solutions outperform existing methods in both utility and computation efficiency, enabling real-time data sharing with strong privacy guarantee.

Introduction

Sharing real-time traffic data is essential to discovering useful and previously unknown knowledge. As illustrated in Figure 1(a): a wireless service provider gathers data from individual users about their locations, speeds, mobility, etc. The aggregated data, e.g. the number of users present at certain locations during a given time period, can be shared with third party researchers to be mined for commercial interest, such as popular places, as well as public interests, such as congestion trends. Figure 1(b) provides a snapshot of aggregated traffic data at a single time stamp. As is shown, the two-dimensional space is partitioned by a 100 × 100 grid. For each cell in the 2D space, Figure 1(b) plots the number of users within its extent at the given time stamp. Since the spatial distribution of wireless users could change over time due to movement, such a snapshot is needed at every time stamp in order to perform real-time data mining tasks. However, the privacy of individual users may be affected if their private data is shared with untrusted third parties. The goal of our work is to enable the server/data holder to share useful multi-location aggregates continuously (multi-dimensional time series) while preserving individual privacy. The current state-of-the-art paradigm for privacy-preserving data publishing is differential privacy [START_REF] Blum | A learning theory approach to noninteractive database privacy[END_REF], denoted as "DP" in Figure 1(a). Differential privacy requires that the aggregate statistics reported by a data publisher be perturbed by a randomized algorithm A, so that the output of A remains roughly the same even if any single tuple in the input data is arbitrarily modified. This ensures that given the output of A, an adversary will not be able to infer much about any single tuple in the input, and thus privacy is protected.

Despite the large number of methods on differentially private data publication [4-6, 10, 11, 15-17], there does not currently exist an approach to sharing multidimensional time series data. We summarize our challenges below:

-Due to the data correlation between time stamps, a straightforward application of the standard differential privacy mechanism at every time stamp leads to an overall perturbation error of Θ(T ) by composition theorem [START_REF] Mcsherry | Privacy integrated queries: an extensible platform for privacypreserving data analysis[END_REF], where T is the length of the time series, which severely limits the utility of the published data when T is large. -Another challenge is data sparsity in the spatial domain. As shown in Fig-ure 1(b), the majority of cells in the 2D space have very low to zero frequency.

In reality, the total number of cells can be very large with respect to the total number of users. The data sparsity poses great challenge for privacypreserving techniques since the perturbation noise is likely to dominate the released value in presence of a small set of users. -Furthermore, the monitoring application requires that private, released data is provided in real-time. Therefore, existing techniques that require timeseries transformation or prohibitive computation time are not applicable to performing real-time tasks.

Our Contributions. In this paper, we propose a real-time framework and two estimation algorithms to address the above challenges in multi-location traffic monitoring with differential privacy. Domain knowledge, such as road network and density, is utilized by our solutions to model the auto-correlation of individual cells over time as well as correlation between neighboring cells. The temporal estimation algorithm establishes an internal time series model for each individual cell and performs posterior estimation to improve the utility of shared aggregate per time stamp. The spatial estimation algorithm builds a spatial indexing structure based on Quadtree to group similar cells together and to reduce the impact of data sparsity. Our solutions provide a strong privacy guarantee.

Both algorithms outperform baseline solution as well as state-of-the-art methods in sharing time series or static multi-dimensional data, providing real-time data release without compromising the utility of shared data. The rest of the paper is organized as follows: Section 2 provides the problem definition, preliminaries on differential privacy, and the baseline solution. Section 3 presents the technical details of our proposed solutions, i.e. temporal estimation and spatial estimation. Section 4 presents a set of empirical results. Section 5 reviews previous works related to data sharing methods with differential privacy. Section 6 concludes the paper and states possible directions for future work.

Problem Statement and Preliminaries

Problem

In the traffic monitoring application we consider, a set of objects are moving in a two-dimensional space and a central server is collecting information about their locations over time. We adopt a fine-grained 2D grid that partitions the space G into w × w cells, where w is a constant number called resolution. We further assume the expected collection time span is T and denote k as the discrete time index where 0 ≤ k < T . For each cell c in G, we define the frequency series of c as X c = {x c k | 0 ≤ k < T }, where x c k represents the number of objects within its extent at time stamp k. A multi-dimensional time series X G can be defined as the set of frequency series of every cell c in G, i.e.

X G = {X c | c ∈ G}. A snapshot of the spatio-temporal database X G k is defined as the set of cell frequencies at time k, i.e. X G k = {x c k | c ∈ G}.
The same terms for the released data set R G can be defined similarly.

Problem 1 Given a multi-dimensional time series X G where G = w × w cells, for each snapshot X G k , release in real-time a sanitized version R G k such that the overall release R G satisfies α-differential privacy, where α is a user-specified privacy level.

Note that sharing R G will enable a variety of data mining tasks. Therefore we use a generic utility metric, i.e. relative error, to measure the usefulness of the released series for each cell c: Definition 1 (Utility Metric). The utility of a published series R c = {r c k } can be measured by the average relative error, denoted as E c , against the original time-series X c ={x c k }.

E c = 1 T T -1 k=0 |r c k -x c k | max{x c k , δ} (1)
where δ is a user-specified constant (also referred to as sanitary bound as in [START_REF] Xiao | ireduct: differential privacy with reduced relative errors[END_REF]) to mitigate the effect of excessively small query results, e.g. 0 s. Here we set δ = 1 throughout the entire time-series for all cells.

Differential Privacy

The privacy guarantee provided by our solutions is differential privacy [START_REF] Blum | A learning theory approach to noninteractive database privacy[END_REF]. Simply put, a mechanism is differentially private if its outcome is not significantly affected by the removal or addition of a single user. An adversary thus learns approximately the same information about any individual user, irrespective of his/her presence or absence in the original database.

Definition 2 (α-Differential Privacy [START_REF] Blum | A learning theory approach to noninteractive database privacy[END_REF]). A non-interactive privacy mechanism A gives α-differential privacy if for any dataset D 1 and D 2 differing on at most one record, and for any possible anonymized dataset

D ∈ Range(A), P r[A(D 1 ) = D] ≤ e α × P r[A(D 2 ) = D] (2)
where the probability is taken over the randomness of A.

The privacy parameter α, also called the privacy budget [START_REF] Mcsherry | Privacy integrated queries: an extensible platform for privacypreserving data analysis[END_REF], specifies the degree of privacy offered. Intuitively, a lower value of α implies stronger privacy guarantee and a larger perturbation noise, and a higher value of α implies a weaker guarantee while possibly achieving higher accuracy. We will examine the privacy-utility tradeoff in the experiment section.

Laplace Mechanism. Dwork et al. [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] show that α-differential privacy can be achieved by adding i.i.d. noise Ñ to each query result q(D):

q(D) = q(D) + Ñ (3) p( Ñ = x) = 1 2λ e -|x|/λ , λ = GS(q)/α (4)
The magnitude of Ñ conforms to a Laplace distribution in Equation (4) where GS(q) represents the global sensitivity [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] of a query q. In the traffic monitoring application, each aggregate value is a count query and GS(count) = 1. Later on in this paper, we denote the Laplace distribution with 0 mean and λ scale as Lap(0, λ).

Composition. The composition properties of differential privacy provide privacy guarantees for a sequence of computations, e.g. a sequence of count queries.

Theorem 1 (Sequential Composition [START_REF] Mcsherry | Privacy integrated queries: an extensible platform for privacypreserving data analysis[END_REF]). Let A i each provide α i -differential privacy. A sequence of A i (D) over the dataset D provides ( i α i )-differential privacy.

Algorithm 1 Laplace Perturbation Algorithm(LPA)

Input: Raw data series X G , privacy budget α Output: Released data series R G

1: for each cell c ∈ G do 2: for each time stamp k do 3:

r c k ← perturb x c k by Lap(0, T α );

Baseline Solution

A baseline solution to sharing differentially private multi-dimensional time series is to apply the standard Laplace perturbation at each time stamp to every frequency series. For any c, if every released aggregate satisfies α/T -differential privacy, by Theorem 1 the released frequency series guarantees α-differential privacy. We summarize the baseline algorithm in Algorithm 1 and Line 3 represents the Laplace mechanism to guarantee α/T -differential privacy for each released aggregate. Empirical studies of the LPA algorithm against our proposed solutions are included in Section 4.

Proposed Solutions

Laplace Perturbation Estimation

Modeling/Aggregation Raw Series Differentially Private Series

Fig. 2. Differentially Private Traffic Monitoring Framework

In this section, we present our proposed solutions for privacy-preserving traffic monitoring. Figure 2 provides a high-level overview of the system framework. At every time stamp, the input multi-dimensional data is perturbed by the Laplace Perturbation mechanism to guarantee differential privacy. Then the perturbed data can be post-processed by the Estimation module to produce a more accurate, released version. Domain knowledge, such as road network and population density, is utilized by Modeling/Aggregation, which in return interacts with the perturbation component as well as the estimation method in use. Below we describe in detail two separate estimation algorithms: one is to perform time-wise estimation for each individual cell, while the other is to perform spatial aggregation and estimation over the entire 2D space.

Temporal Estimation

For each cell c in space G, we can apply our recently proposed filtering-based posterior estimation technique [START_REF] Fan | Real-time aggregate monitoring with differential privacy[END_REF] to the cell frequency series X c . The key idea is to utilize an internal time series model for the frequency series and to estimate the true aggregate values based on the Laplace perturbed values. The additional innovation in this paper is that we model different types of cells according to the domain knowledge on the road networks. Below we briefly show how to model the cell frequency series and refer interested readers to our work [START_REF] Fan | Real-time aggregate monitoring with differential privacy[END_REF] for further implementation details.

Note that the internal model of cell frequencies depends on many factors, such as location, overall population, road network, etc. Here we simply classify each cell as sparse or dense based on road network connections and assume the same internal model for cells within each category. For each cell c, its frequency series X c can be represented by the following process model:

x c k+1 = x c k + ω c , p(ω c ) ∼ N(0, Q c ) (5)
which states that the count values of consecutive time stamps should be consistent except for a white, Gaussian noise ω c . In particular, ω c is called the process noise and it follows a normal distribution. Q c value indicates the level of variation between adjacent time stamps. Intuitively, sparse cells exhibit little variation since very few objects travel within them, therefore we should specify a small Q c value for such cells. On the other hand, higher Q c should be assigned for dense cells since they are visited more frequently in reality. The noisy observation, which is obtained from the Laplace Perturbation mechanism, can be modeled as follows:

z c k = x c k + ν , ν ∼ Lap(0, 1/α 0 ) (6)
where ν, called the measurement noise, corresponds to the Laplace noise and is independent of c. The differential privacy budget for each traffic count is α 0 = α/T , since the overall privacy budget α is uniformly allocated to each time stamp.

For posterior estimation purpose, it is sufficient and computationally attractive to approximate ν by a white Gaussian error according to [START_REF] Fan | Real-time aggregate monitoring with differential privacy[END_REF]:

ν ∼ N(0, R) . (7)
Therefore here we adopt the above Gaussian approximation for every cell and use the Kalman filter based filtering technique [START_REF] Fan | Real-time aggregate monitoring with differential privacy[END_REF] for posterior estimation. The outline of the temporal estimation algorithm is presented in Algorithm 2. For every time stamp k and each cell c, we derive a predicted frequency with the Predict procedure. Upon receiving the noisy observation, we can derive a posterior estimate with the Correct procedure, by linear combination of prediction and observation. The derivation of posterior estimate as well as Predict and Correct steps can be found in [START_REF] Fan | Real-time aggregate monitoring with differential privacy[END_REF] and therefore omitted here for brevity.

Algorithm 2 Temporal Estimation Algorithm

Input: Raw data series X G , privacy budget α Output: Released data series R G 1: for each timestamp k do 2:

for each cell c ∈ G do 3:

prior ← c.Predict(k) ; 4:

z c k ← perturb x c k by Lap(0, T α ); 5: posterior ← c.Correct(k, prior, z c k ); 6: r c k ← posterior;
The advantage of temporal estimation approach is that it utilizes the internal time series model and the observations to form an educated guess, which is shown in [START_REF] Fan | Real-time aggregate monitoring with differential privacy[END_REF] to greatly improve the accuracy of released data per time stamp. As for complexity, we can see that the computation time requirement is O(w 2 ) for every time stamp where w is the spatial resolution, since only O(1) operations are performed for each cell.

Spatial Estimation

When every cell is perturbed individually, data sparsity imposes great utility challenge, i.e. high relative error due to perturbation. We thus are motivated to group similar cells to overcome the data sparsity issue. Considering the spatial correlation among cells, it is very likely that neighboring cells are connected by the same roads therefore are more similar to each other. To utilize this heuristic, we propose to aggregate similar cells into partitions according to spatial vicinity and perform estimation within each partition assuming uniformly distributed objects within the partitions.

We propose a top-down space partitioning approach based on Quadtree due to several considerations. One advantage of Quadtree is its efficiency: it recursively partitions a 2D space into 4 quadrants disregard the actual object distribution in the space. Another advantage of Quadtree is that it doesn't incur any extra privacy cost due to its independence from data. In contrast, the kdTree structure proposed by Cormode et al [START_REF] Cormode | Differentially private spatial decompositions[END_REF] does require extra privacy budget spent on finding the "private median". Since the privacy budget for each time stamp is very limited, we believe that Quadtree is more suitable in the multi-dimensional time series scenario.

We outline the spatial aggregation algorithm based on Quadtree in Algorithm 3. Line 5 checks every node/partition for the splitting condition. Line 6 splits a partition into four equal quadrants. The node.homogeneous() method returns true if all the cells within the partition belong to the same category. Again, each cell is pre-classified as sparse or dense based on domain knowledge. We stop splitting a partition if it is homogeneous. Otherwise, as long as the predefined depth threshold d is not violated, we further split the partition in the hope of reducing the class impurity in each child partition. the aggregation level. Setting d = 0 implies that all cells are aggregated in one partition. Since the uniform assumption within the partition does not hold, high estimation error will be incurred. On the other hand, a higher value of d implies that many partitions will be further split to produce homogeneous regions so as to reduce estimation error. However, due to data sparsity, very few moving objects will fall into each partition when it is small. Therefore, the perturbation error will dominate the released data in that case. Clearly the optimal d value depends on the spatial distribution of cells. We will examine the impact of d in the experiment section.

Once the Quadtree index structure of the space G is established, we assume uniform data distribution within each partition and estimate each cell frequency with average partition frequency. The spatial estimate algorithm is described in Algorithm 4. For each time stamp k, a partition count is aggregated from cells for every partition (Line 4). It is then perturbed by the Laplace mechanism to guarantee differential privacy (Line 5) and the average noisy count is used to estimate the frequency of each cell within the partition (Line 6). The intuition is that the cells within each partition have similar density. Therefore by uniformly distributing the noisy partition count to each cell, we reduce the magnitude of perturbation error applied to each cell without compromising the accuracy.

One advantage of the spatial estimation algorithm is that it relies on simple and practical assumptions. The complexity is also O(w2 ) for each time stamp since every cell is visited O(1) times. Although it takes extra time to build the spatial index for initialization, we see it as a one-time cost which can be done off-line. The runtime of the spatial estimation is reduced because only one perturbation noise is needed for every partition at every k (Line 5). In contrast, both the baseline LPA algorithm and the temporal estimation algorithm will generate one perturbation noise for each cell at every k. We will study their runtime performance in the next section.

Evaluation

We implemented the proposed algorithms as well as alternative methods in Java with JSC1 for simulating the statistical distributions. All experiments were conducted using a 2.90GHz Intel Core i7 PC with 8GB RAM. ),which contains 6,105 nodes and 7,035 edges, and the output is a set of moving objects on the road network. We created the data set with 100 discrete timestamps, with 500,000 objects at the beginning and 25,000 new objects introduced at every time stamp. The starting positions and destinations of the moving objects are selected randomly by the generator (see [START_REF] Brinkhoff | A framework for generating network-based moving objects[END_REF] for detailed network-based techniques). Once an object reaches its destination, it disappears from the map. At the server side, we use a 2D grid with 1024 × 1024 cells to record the locations of the moving objects, with each cell representing approximately 20 × 20 square meters' range in reality. We assign each cell a class label, i.e. sparse or dense, based on the presence of roads within its extent. Roughly 95% cells are labeled sparse, indicating only the rest 5% have been visited by the moving objects. Figure 3(b) visualizes the partition result achieved by the Quadtree-based algorithm with the depth threshold d = 8. It can be seen that spares regions around map edge are contained in larger partitions and densely connected regions in map center are further split into smaller partitions. We will evaluate the set of sparse cells and the set of dense cells separately since they exhibit very different dynamics over time.

Comparison. We compare our proposed solutions against the state-of-the-art methods which are summarized below:

-DFT is the Fourier Perturbation Algorithm recently proposed by Rastogi and Nath [START_REF] Rastogi | Differentially private aggregation of distributed time-series with transformation and encryption[END_REF] for sharing single time series. It first performs the Discrete Fourier Transform on an input time series and retains only the first l DFT coefficients. Those coefficients are then perturbed by the Laplace mechanism to guarantee differential privacy. Finally, the Inverse Discrete Fourier Transform is performed on the perturbed coefficients to produce a released series.

The number of coefficients to preserve, i.e. l, is a user-specified parameter. In our empirical study, we set l = 20 according to their recommendation [START_REF] Rastogi | Differentially private aggregation of distributed time-series with transformation and encryption[END_REF].

-kd-hybrid is proposed by Cormode et al [START_REF] Cormode | Differentially private spatial decompositions[END_REF] as their best method to achieve differentially private space decomposition with static data. Without the help of a grid, kd-hybrid builds a mixture index over the 2D data space that begins with kd-tree and switches to quad-tree at a certain level. They slightly modified the kd-tree algorithm, changing the fanout rate to 4 in order to reduce the privacy budget consumption. According to their studies, kd-hybrid is most reliable among several representative differentially private space partitioning methods. They reported the optimal parameter setting empirically with the height set to 8 and the switch level set to 4.

Since the DFT algorithm can be only performed with the complete series, it is not compatible to real-time applications. However, we include it in our evaluation since it serves as a good, off-line reference for utility. As for the kd-hybrid algorithm, there are two limitations. One is its high privacy cost since the algorithm iteratively spends budget on finding "private medians" for every data snapshot. The other limitation is its high computation cost: application of the kd-hybrid method requires constructing the index structure at every time stamp. Experiments with the author's provided implementation take hours for each iteration, since the domain size and the number of objects in our data set are extremely large. We conclude that the kd-hybrid method is too expensive for the continuous, real-time applications and therefore do not include the results in the remaining section.

Parameter Impacts

The default parameter setting, unless otherwise noted, is summarized in Table 1.

Note that Q sparse and Q dense , which correspond to Q c in Equation ( 5) for sparse and dense cells, can be chosen by domain users and our default setting may not be optimal. As for R from Equation ( 7), we set its value according to our previous studies [START_REF] Fan | Adaptively sharing time-series with differential privacy[END_REF], which shows that the optimally R is proportional to T 2 /α 2 . We study the impact of the depth threshold d used in Algorithm 3 in terms of utility as defined in Equation (1) and runtime. Intuitively, the larger value d takes, the finer partitions the algorithm results in, especially along the border of sparse and dense regions. However, it also incurs a higher overhead to construct the index as we can expect. Figure 4(a) plots separately the utility of released series for sparse cells and dense cells when varying the depth threshold d. For each class of cells, we plot the median relative error to avoid the extremely small or large values. As we increase the threshold value, the error for sparse cells gradually drops to 0 between d = 0 and d = 4 and remains stable when d value is further increased. This is due to the fact that majority sparse cells are located together (on map edge) and will not take too many splits to be separate from dense cells (in map center). Increasing the d value can help separating those sparse cells on the boarder line. However, the utility of majority sparse cells is not affected since those on the boarder line only count for a very small percentage. On the other hand, dense cells require more splits to achieve optimal separation (d = 8). When further split (d > 8), the perturbation noise greatly impacts their utility due to data sparsity. Figure 4(b) shows the overhead for constructing the aggregation index when varying the d value. It takes at most 0.9 second and we note that it is a one-time cost. As we expect, a higher depth threshold requires more construction time (from d = 0 to d = 6). However, when d > 6 the overhead does not grow since there are only very few partitions that do not meet the homogeneous requirement at depth 6. As can be seen in Figure 3(b), the densely connected areas in the map are split into finer partitions compared to less populous areas on the map edge.

Utility Performance

Utility vs. Privacy. Here we examine the trade-off between utility and privacy. Our proposed solutions, i.e. Kalman and Quadtree, are compared against the baseline LPA and state-of-the-art DFT algorithm, in terms of utility of individual cells. Figure 5(a) and Figure 5(b) plot the utility of sparse cells and dense cells respectively when varying the overall privacy budget, i.e. α value, from [10 -3 , 10 0 ]. As we can see, the baseline LPA algorithm results in highest relative error in both figures. The DFT algorithm results in high relative error with sparse cells even with high privacy cost (α = 1), due to the perturbation and reconstruction error. Our solutions Kalman and Quadtree outperform both LPA and DFT especially with sparse cells, as Quadtree only results in 10% error and Kalman produces 0% error when α = 1. As for the dense cells, both Kalman and Quadtree slightly outperforms DFT, which is supposed to be optimal. When α = 1, DFT results in 83% error due to lack of smoothness in the original frequency series, while our solutions provide comparable utility to DFT and real-time data release. Figure 6(a) and Figure 6(b) provide a closer look at the utility curves within a more practical range of privacy budget α ∈ [0.1, 1]. DFT and LPA are not plotted in one or both figures because the errors they result in are prohibitive. For sparse cells, Kalman provides optimal performance even under small privacy budget (α = 0.1), thanks to the accurate modeling. Quadtree is able to approach 0% error as α value increases. For dense cells, we observe that Quadtree provides the best utility in the same privacy budget range. We conclude that both our proposed solutions outperforms existing methods, allowing for real-time data sharing without compromising the utility. Utility of Range Queries. Here we evaluate our solutions with range queries, where each query is a square window that covers a neighborhood of m × m cells. For each m value, we randomly generate 100 queries of size m × m, evaluate each method with the same set of queries, and plot the average relative error. Note that when m = 1, each set query consists of one cell only and therefore the set query error is equivalent to individual cell error. Our findings are summarized in Figure 7. Our temporal estimation algorithm based on the Kalman filter clearly outperforms Quadtree and LPA with smaller query windows (m ≤ 100). For all three methods, the relative error shows a growing trend to different extent as the query set size increases, mainly due to the data sparsity in the space. When m = 500, we observe that the error of Kalman keeps accumulating while Quadtree and LPA show reduced relative error. We believe that it is because Kalman does not explicitly utilize the spatial correlation between cells. When querying the entire space (m = 1024), both Quadtree and LPA provide good utility because the Laplace noise added to each cell is from a zero-mean distribution and the sum of a large set of such noises is likely to be small. Overall, Quadtree outperforms LPA by making sound estimation within close-to-uniform partitions.

Runtime Performance

Lastly we compare the runtime performance of our solutions against the baseline since computation time is critical to real-time applications. We measure and plot the runtime for releasing the two-dimensional aggregates for 100 timestamps in order to mitigate random disturbance from the operating system. The results are summarized in Figure 8. As we can see, all three methods take less than 35 seconds to release 100 snapshots of 1024 × 1024 cell frequencies with differential privacy guarantee. Note that the state-of-the-art kd-hybrid takes hours to release/evaluate one time stamp. Compared to LPA, our solution Kalman takes roughly 2 more seconds in total to perform prediction and correction at every time stamp. Quadtree turns out to be the most time efficient, even though it has a small overhead in building the spatial index. This is because less perturbation is performed by Quadtree, as at every time stamp we only generate one perturbation noise for each partition rather than for each cell as in LPA.

Related Works

Here we briefly review the most relevant, recent works on differential privacy and time-series data sharing. Dwork et al. [START_REF] Dwork | Calibrating noise to sensitivity in private data analysis[END_REF] established the guideline to guarantee differential privacy for individual aggregate queries by calibrating the Laplacian noise to the global sensitivity of each query. Since then, various mechanisms have been proposed to enhance the accuracy of differentially private data release. Blum et al. [START_REF] Blum | A learning theory approach to noninteractive database privacy[END_REF] proved the possibility of non-interactive data release satisfying differential privacy for queries with polynomial VC-dimension, such as predicate queries. Dwork et al. [START_REF] Dwork | On the complexity of differentially private data release: efficient algorithms and hardness results[END_REF] further proposed more efficient algorithms to release private sanitization of a data set with hardness results obtained. Several recent works [START_REF] Cormode | Differentially private spatial decompositions[END_REF][START_REF] Hay | Boosting the accuracy of differentially private histograms through consistency[END_REF][START_REF] Li | An adaptive mechanism for accurate query answering under differential privacy[END_REF][START_REF] Xiao | Differential privacy via wavelet transforms[END_REF][START_REF] Xiao | Differentially private data release through multidimensional partitioning[END_REF][START_REF] Xu | Differentially private histogram publication[END_REF] study the counting queries on multidimensional data, also referred to as histograms or contingency tables, where the multi-dimensional data can be indexed by a tree structure and each level in the tree is an increasingly fine-grained summary/count. Cormode et al [START_REF] Cormode | Differentially private spatial decompositions[END_REF] propose the class of "private spatial decompositions" and conclude that the hybrid structure kd-hybrid provides an accurate yet efficient solution compared to alternatives. When applied to highly self-correlated time-series data, all the above methods, designed to perturb static data, become problematic because of highly compound Laplace perturbation error.

Rastogi and Nath [START_REF] Rastogi | Differentially private aggregation of distributed time-series with transformation and encryption[END_REF] proposed a Discrete Fourier Transform (DFT) based algorithm which implements differential privacy by perturbing the discrete Fourier coefficients. However, this algorithm cannot provide real-time private release in a streaming environment. The recent works [3] [6] on continuous data streams defined the event-level privacy to protect an event, i.e. one user's presence at a particular time point, rather than the presence of a user. Our previous work [START_REF] Fan | Real-time aggregate monitoring with differential privacy[END_REF] studies the problem of sharing single time-series with user-level differential privacy and we proposed an algorithm with filtering and adaptive sampling to improve the utility of the shared series.

Conclusion

We have proposed a real-time framework and two estimation algorithms to address the challenges of differentially private multi-dimensional time series release with application in traffic monitoring. The temporal estimation algorithm establishes a single time-series model for each cell in the space and performs posterior estimation to improve the utility of each released aggregate. The spatial estimation algorithm builds a spatial index by Quadtree and group similar cells together to overcome data sparsity. Domain knowledge is exploited by both estimation methods and is shown beneficial. We observe that the temporal estimation algorithm is highly accurate especially with sparse cells but requires modeling and slightly more running time. On the other hand, the spatial estimation algorithm relies on practical assumptions, demands less computation time, and provides better utility for dense cells and larger range queries. Compared to alternative methods, our solutions outperform the baseline LPA algorithm as well as stateof-the-art methods in both utility and computation efficiency. Future work may include in-depth study of complex spatial-temporal correlation between locations and timestamps.

Fig. 1 .

 1 Fig. 1. Traffic Data Monitoring

Fig. 3 .

 3 Fig. 3. Overview of Data Set

Fig. 4 .

 4 Fig. 4. Impact of Depth Threshold on Quadtree-based Spatial Estimation

Fig. 5 .

 5 Fig. 5. Utility of Individual Cells: Comparison of All Methods

Fig. 6 .

 6 Fig. 6. Closer Look at α ∈ [0.1, 1]

Fig. 7 .Fig. 8 .

 78 Fig. 7. Utility of Range Queries

  The value of d represents Algorithm 3 QuadTreeAgg Algorithm Raw data series X G , depth threshold d, privacy budget α Output: Released data series R G

	Input: 2D grid G, depth threshold d
	Output: QuadTree index structure QT
	1: QT.root ← G;
	2: queue.add(QT.root) ;
	3: while ! queue.empty() do
	4:	node ← queue.remove() ;
	5:	if ! node.homogeneous() and node.depth < d
	6:	node.split() ;
	7:	queue.add(node.children) ;
	Algorithm 4 Spatial Estimation Algorithm
	4:	p k ← c∈p x c k ;
	5: 6:	pk ← perturb p k by Lap(0, T α ); r c

Input:

1: QT ← QuadTreeAgg(G, d); # initialize the quadtree index 2: for each timestamp k do 3:

for each partition p ∈ QT do k ← pk /p.size(), c ∈ p ;

Table 1 .

 1 Parameter Settings

	Symbol Description	Default Value
	α	Total Privacy Budget	1
	w	Resolution for Each Dimension	1024
	T	Length of Multidimensional Time Series	100
	Qsparse Process Noise for Sparse Cells	10 -2
	Q dense Process Noise for Dense Cells	10 3
	R	Gaussian Measurement Noise	10 6
	d	Depth Threshold for Quadtree	8

http://www.jsc.nildram.co.uk

http://iapg.jade-hs.de/personen/brinkhoff/generator/

Acknowledgments

This research is supported by NSF under grant CNS-1117763 and AFOSR under grant FA9550-12-1-0240.