Nikolay Yakovets

Jarek Gryz

Stephanie Hazlewood
email: stephanie@ca.ibm.com

Paul Van Run
email: pvanrun@ca.ibm.com

From MDM to DB2: A Case Study of Security Enforcement Migration

Keywords: Master Data Management, Enterprise Security, Attribute-Based Access Control, Database Security, XACML, DB2

This work presents a case study of a migration of attributebased access control enforcement from the application to the database tier. The proposed migration aims to improve the security and simplify the audit of the enterprise system by enforcing information protection principles of the least privileges and the least common mechanism. We explore the challenges of such migration and implement it in an industrial setting in a context of master data management where data security, privacy and audit are subject to regulatory compliance. Based on our implementation, we propose a general, standards-driven migration methodology.

Introduction

Today's enterprise data is complex and heterogeneous, and users who access it are diverse and belong to multiple domains. The access control models have evolved to fit these requirements. Traditional discretionary (DAC, [START_REF] Van Run | Protection: Principles and Practice[END_REF]) and mandatory (MAC, [START_REF] Jajodia | Toward a Multilevel Secure Relational Data Model[END_REF]) access control models have been replaced by role-based access control (RBAC, [START_REF] Sandhu | Role-based Access Control Models[END_REF]) and, more recently, attribute-based access control (ABAC, [START_REF] Wang | A Logic-based Framework for Attribute Based Access Control[END_REF]). Unlike DAC, MAC and RBAC, the ABAC model defines permissions based on just about any security relevant characteristics of requesters, actions, resources, and environment, known as attributes.

The lack of native ABAC support by conventional DBMS has motivated many enterprise developers to implement access control checks at the application tier, bypassing the native database access control. In such architecture, the database connection is established on behalf of the application and is able to access the entire database, while application program logic itself is used to limit the privileges of the end-user. While this approach allows enforcement of more complex and flexible attribute-based policies, it also introduces several problems. First, because the database connection is at an elevated privilege, the enterprise system is prone to privilege escalation attacks [START_REF] Pfleeger | Safari Tech Books Online[END_REF], such as SQL injection [START_REF] Kc | Countering Code-injection Attacks with Instruction-set Randomization[END_REF]. Second, since the database is not aware of the identity of an end-user issuing the request, it may be difficult for application developers to provide the end-to-end audit trail which is essential to comply with regulations such as SOX [START_REF]United States Code. Sarbanes-Oxley Act of[END_REF], PCI [8], and HIPAA [START_REF] Allender | HIPAA compliance in the OR[END_REF].

In this paper, we describe how to perform a migration of an existing enterprise security enforcement from the application tier to the database tier. In other words, we would like to be able to securely enforce the enterprise security policies at the database, while retaining the flexibility of their management at the application. We see several benefits of such database-level enterprise security enforcement. First, it helps protecting the enterprise system from privilege escalation attacks by complying with information protection principles of the least privileges and the least common mechanism [START_REF] Saltzer | The Protection of Information in Computer Systems[END_REF]. Further, the placement of security controls on the database allows for full end-to-end audit trail as the identity of an end-user is not hidden behind a common authorization ID of an application layer.

We consider our approach in an industrial setting in a context of master data management (MDM) [START_REF] Dreibelbis | Enterprise Master Data Management: An SOA Approach to Managing Core Information[END_REF]. A wide variety of MDM solutions are available on the market today from major vendors such as IBM, Oracle, Microsoft and SAP. Such systems aim to provide a centralized environment for maintaining the master data about customers, suppliers, products and services. Master data plays an important role in both operational and analytical aspects of the organization operation. However, it is also a tempting target for attackers as it is captured by combining, cleansing and enriching highly confidential data across various data sources in the organization. Further, master data also contains personally identifiable information, making MDM solutions subject to regulatory compliance. Since the proposed migration aims to improve the security and simplify the compliance of the enterprise system, we believe it may be useful, in the first place, in the MDM domain.

In collaboration with IBM Centre for Advanced Studies, we used IBM Info-Sphere Master Data Management Server (in short, MDM Server) as an implementation platform. MDM Server is a large scale industrial-grade MDM solution that enforces attribute-based security policies at the application tier while storing the master data in the relational database. This enabled us to implement the proposed migration in MDM Server to prove the feasibility and practical usefulness of our approach.

Lastly, we believe that our MDM Server migration experience may be helpful in similar migration projects in a variety of enterprise applications outside of MDM. To facilitate the implementation of such projects, we propose a general migration methodology that is standards-driven and vendor-independent.

The rest of the paper is organized as follows. Section 2 describes the challenges of the proposed migration, and Section 3 describes our industrial implementation. Section 4 discusses the lessons we learned, and Section 5 presents a general migration methodology. Section 6 discusses some of the related works, and Section 7 concludes.

Challenges

The proposed migration aims to place the security enforcement on the database, while keeping the security administration at the application. This comes with several challenges as both end-user identities and security policies need to be timely and efficiently propagated from the application tier down to the database. The following subsections provide more detail.

Identity Propagation

Request processing often involves the propagation of end-user's identity from one enforcement point to another within the enterprise environment. For example, consider a case where end-user is authenticated at a client tier. Then the identity is sent to an application tier for its own authorization and auditing. The application in turn generates the requests to query a back-end database potentially using yet another identity that is suitable to access a relational database on end-user's behalf.

The scenarios of such identity propagation differ by a degree of knowledge that the relational database has about the end-users. For example, an end-user may be mapped to a system identity -or the identity that is used to represent the application tier. This many-to-one mapping greatly simplifies the deployment topology, but effectively places all of the security controls such as authorization and audit on the application tier, as the relational database has no knowledge about the identity of the end-user.

On the other hand, an end-user may be mapped to a functional identity which can represent user's role or group in the organization. This many-to-many mapping allows placing some of the security controls on the relational database for the price of complicating the deployment topology. In this case, however, the database still does not know who exactly the end-user is. Therefore full end-to-end audit trail is impossible which can cause problems with regulatory compliance.

Lastly, an end-user may be mapped to her corresponding identity in the database. This one-to-one mapping allows the database perform authorization and audit using end-user's identity. This scenario requires the most difficult deployment topology, but allows placing most of the security controls on the relational database. Since this allows for full end-to-end audit trail, it greatly simplifies regulatory compliance of the enterprise system.

The proposed migration involves shifting from many-to-one to one-to-one identity mapping during the enterprise request processing. What makes this challenging is that the complication of the deployment topology that comes with one-to-one mapping is undesirable. Moreover, the identity propagation mechanism would require an identity provisioning component responsible for keeping identities in the database consistent with identities administered at the application. An optimal solution for handling the identity propagation would need to solve the above problems.

Policy Propagation

Application-to-database policy propagation is challenging because the underlying security mechanisms at the application are conceptually different from those at the database. Application-level authorization engine can use either proprietary or standards-driven approach such as OASIS XACML [START_REF]Organization for the Advancement of Structured Information Standards (OASIS[END_REF] to specify, distribute and enforce high-level attribute-based security policies. The flexibility of such policies comes from the ability to define the security rules based on attributes of users, resources and environment. For example, a single rule might permit access for all professors in the department of computer science to files pertaining to courses offered in that department. The access decision is made during the request execution time when the rule attributes are retrieved: the authorization IDs of current CS professors and table names of currently offered CS courses.

Relational database low-level security enforcement mechanisms are based on the assignment of privileges to users or roles. The privileges can be granted or revoked on complete tables and views. For example, a single database authorization might permit access for professor JohnDoe to table CS101. Clearly, such discretionary database policies are less expressive than attribute-based application policies.

The proposed migration would involve linking the security mechanisms at the application and at the database. A consistent mapping should be established between the security policies, such that the database privileges conform to semantics specified by permissions in the application. Mapping of a single application policy would require the understanding how application-level users and resources identified by their attributes translate to database-level authorization IDs and tables. Mapping of multiple application policies would require the understanding of policy combining and conflict resolution algorithms that are used at the application.

It is important to realize that updates to application security policies or to user and resource attributes may alter the established policy mapping in a non-trivial way. Some of the database permissions would need to be granted, while others would need to be revoked. The solution for policy propagation would need to provide the mechanism that will efficiently maintain the consistent relationship between the database permissions and the policies administered in the application.

Implementation

In this section we show how the proposed migration can be implemented in an industrial setting in MDM Server. MDM Server is a large scale enterprise application that runs on WebSphere Application Server (WebSphere) and uses IBM DB2 relational database (DB2) to store master data. First, we describe how the identity of an end-user of MDM Server can be efficiently propagated from WebSphere down to DB2. Next, we talk about how the attribute-based MDM Server security policies can be mapped to discretionary DB2 permissions. Finally, we show how to efficiently maintain the consistency of DB2 permissions when MDM Server policies or attributes are updated.

MDM Server Identity Propagation & DB2 Trusted Context

In MDM Server access control checks are implemented at the application tier, and the application itself is able to access the whole master database by using an administrative system identity. The goal of our migration is to place most of the security controls on DB2, instead of relying on MDM Server to perform the security checks. To make an access decision, the database needs to know the identity of an end-user issuing the request that is effectively "masked" by the administrative system identity of the MDM Server application. One way to solve this problem is to modify the MDM Server application logic in such a way that each database connection is established using the end-user's identity who issued the request instead of the administrative system identity. However, this approach would involve the significant modification of the MDM Server code base, which is undesirable. Another, more efficient approach is to plug in a Java Authentication and Authorization Service (JAAS) login module to propagate the end-user identity to the database server. This approach maintains the enduser identity, but does not support connection pooling that is normally leveraged by MDM Server when many-to-one administrative system identity is used.

In our implementation, we utilize trusted connections instead of the manual mapping or a JAAS mapping. Trusted connections support client identity propagation and can also use connection pooling to reduce the performance penalty of closing and reopening connections with a different identity. Trusted connections leverage the DB2 trusted context object. The DB2 trusted context is an object that the database administrator defines and that contains a system authorization ID and a set of trust attributes. The trust attributes identify characteristics of a connection that are required for the connection to be considered trusted. The relationship between a database connection and a trusted context is established when the connection to the DB2 server is created. After a trusted context is defined, and an initial trusted connection to the DB2 database server is made, the application server can use that database connection from a different user without a full re-authentication. The database authenticates the end-user and then verifies the user authorization to access the database prior to allowing any database requests to be processed on behalf of that user.

When software stack is set up for use of the trusted context, the authorization of the end-user requests is carried out as follows. First, end-user is authenticated to MDM Client 1 , and her identity is sent over to WebSphere which is runnung MDM Server 2 . WebSphere initially establishes the connection to DB2 using underpriviliged "connection-only" user 3 . However, on query execution time, the user identity is switched to the end-user who executes the query 4 . Therefore, the query is executed and audit trail is logged at DB2 with the identity of the end-user 5 .

Fig. 1. Identity Propagation in MDM Server

To provision one-to-one identity propagation, database-level authorization IDs should be kept consistent with identity information stored in MDM Server according to the established one-to-one mapping. We solve this problem by using an LDAP [START_REF] Zeilenga | Lightweight directory access protocol (ldap): Technical specification road map[END_REF] registry common to both MDM Server and DB2. Thus, the use of a trusted context and a centralized user registry allows us to establish an efficient one-to-one identity propagation that does not complicate the deployment topology of the enterprise system.

MDM Server Policy Propagation

To establish application-to-database policy propagation in MDM Server we need to provide a consistent mapping between MDM application security policies and their DB2 counterpart.

In DB2, we consider object-level and content-based authorizations that are granted as primary, secondary or public permissions. Such discretionary permissions are represented as access control lists (ACLs), where each object is associated with a list of subjects coupled with a set of actions they can perform on the object. The object, in this case, can be a table or a view, while the subjects are DB2 users (authorization IDs), user groups, user roles and public (all users). The access operations that subjects are allowed to invoke on objects are SQL operations that can be executed on tables: select, insert, delete, and update.

On the other hand, at the application tier, we have MDM entitlements, which are managed by Rules of Visibility and Persistency Entitlements components of MDM Server. In an entitlement, an accessor, which may be a user or a user group, is entitled to take an action, for example adding, updating, or viewing, on set of business objects or their elements which are identified by the data association resource attribute in the entitlement.

To establish a policy mapping, one should understand the semantics of MDM entitlements in the context of master data stored in the relational database. In MDM, business objects map to database tables and elements that further refine those business objects correspond to the columns of its underpinning database tables. To enable full end-to-end audit, we establish one-to-one mapping between MDM accessors and database users and groups. Finally, MDM data actions are mapped to DB2 data manipulation operations (i.e. update, select, insert and delete).

For example, consider a pair of MDM entitlements shown in Fig. 2. First entitlement permits a particular student to view resources with attribute Data Association = {Course, Grades}. Second entitlement permits all professors updating resources attributed to Grades only. Through corresponding associated objects, COURSE database table is assigned Data Association = {Course, Grades}, and GRADES table has Data Association = {Grades}. According to our policy mapping, the first entitlement is associated with DB2 authorizations 1 , 2 and 3 , while 4 and 5 are associated with the second entitlement.

Fig. 2. Policy Mapping in MDM Server

To accommodate the propagation of MDM entitlements down to DB2 we modify MDM Server application logic by introducing Policy Propagation Point (PPP) component (shown in Fig. 3). Policy propagation is carried out in three steps. First step performs entitlement parsing: PPP interacts with existing MDM Server components (we logically group them as MDM Policy Administration Point (PAP)) to obtain the list of current entitlements. Each fetched entitlement is described by an accessor, a data action and a data association attribute.

Second step performs attribute extraction: PPP interacts with another group of MDM Server components (Policy Information Point (PIP)) to extract the resources that correspond to the attribute values of the parsed entitlements. In this step, data associations are associated with the list of associated objects they contain.

Third, and last, step builds DB2 authorizations and sends them to the database. For each associated object in an entitlement a single DB2 permission is generated in accordance to the established policy mapping. An accessor is mapped to a DB2 user or a group, a data action is mapped to a DB2 data manipulation operation and, lastly, an associated object is mapped to a DB2 table. The generated DB2 permissions are combined according to MDM Server policy combining and conflict resolution algorithms. In MDM Server a union approach between the entitlements is assumed (i.e. if a user belongs to a group which is allowed to see a data then, even though that user belongs to the other groups that are not allowed to see that data, the access will still be granted). No conflict resolution is required because the entitlements can only be granted and cannot be restricted (i.e., there are no negative entitlements) and the default policy is to restrict access unless it is specifically granted. Since DB2 employs the same policy combining and conflict resolution, we combine the generated DB2 permissions simply by issuing them directly to the database.

For each generated database permission, PPP logs all relevant information into the propagation log. This log contains, for each DB2 authorization, the reference to its parent entitlement, accessor, data action, data association and associated object. Information about the status of each DB2 authorization, whether it was issued to the database or was found duplicate, is also stored in this log. For example, for MDM entitlements that are shown in Fig. 2, PPP will generate and log five DB2 authorizations, however, only four of them will be issued to the database as one of the authorizations is a duplicate (assuming that no authorizations were issued for other MDM entitlements before).

Our solution also maintains the consistent relationship between MDM entitlements and DB2 permissions in case when either entitlements or their attributes are updated. A naïve approach to handle this problem would involve manual periodical rebuilding of all DB2 permissions. Our incremental propagation approach aims to rebuild only a subset of DB2 permissions that is affected by the entitlement or the attribute update.

All administrative MDM transactions that deal with entitlements and their attributes are handled by MDM component called Security Transaction Handler (STH) (shown in Fig. 3). We modify this component in such a way that whenever it receives a transaction that deals with either entitlements or their attributes, it triggers PPP to immediately update the affected database permissions.

To illustrate how incremental propagation works consider the following example. Suppose that security administrator updates the data association attribute of the associated object BObj so that it no longer belongs to Grades (Fig. 2).

Fig. 3. Policy Propagation in MDM Server

STH notifies PPP that BObj has been updated. Then, PPP extracts from the transaction log all old DB2 permissions that were built from BObj. In this case, those are 1 and 5 . Next, PPP checks the propagation log to see if there are unissued permissions that are duplicate to 1 and 5 and were not affected by the update. In this example, it finds permission 3 . Therefore, only 5 is revoked and 3 is unmarked as being duplicate. Finally, PPP interacts with PIP and PAP to generate and issue to the database any new permissions resulted from the update.

Discussion

In this section we discuss the lessons that we learned from the implementation of the proposed security enforcement migration in MDM Server.

Integration Footprint

Industrial-scale enterprise applications have hundreds of thousands, sometimes even millions lines of source code. Due its large size a significant recoding of an initial implementation in order to integrate the proposed security enforcement migration is not feasible.

Our identity propagation implementation relies on trusted connections and trusted context features of DB2 and WebSphere. Trusted connections support client identity propagation and can also use connection pooling to reduce the performance penalty of closing and reopening connections with a different identity. Moreover, when WebSphere and DB2 are configured for use of trusted connections, WebSphere, seamlessly for the enterprise application, will propagate end-user identity to DB2 through the trusted data source. Therefore, the existing application code that uses WebSphere APIs to interact with DB2 through configured data sources does not need any modification. Thus, given a properly configured software stack, almost no initial code modifications are needed to implement the identity propagation in our approach, and it also doesn't incur noticeable performance degradation.

Our policy propagation mechanism is encapsulated in a single additional module which integrates seamlessly into the existing application security core architecture. It reuses existing application interfaces to obtain enterprise security policies and attributes. Minor modifications to the initial code base were needed to enable propagation triggering mechanisms in existing application components.

Therefore, our approach has a small integration footprint on the existing code base, which makes it feasible to implement in a large-scale industrial-grade enterprise application such as MDM Server.

Policy Granularity

We can classify attribute-based security policies into two types based on the granularity of the data to which they apply. Specifically, if policy describes objectlevel authorizations, i.e. its resources are mapped to whole database tables, then we call such policy coarse-grained. For example, coarse-grained policy allows students to see all course grades, when course grades are contained in one, or several, database tables. On the other hand, if a policy describes content-based authorizations, i.e. its resources are mapped to specific rows of a table, then we call such policy fine-grained. For example, fine-grained policy allows students to see only their own grades that are contained in specific tuples of a course grades database table.

In our approach, we compile coarse-grained application policies into a set of database permissions. However, a different approach is needed to handle those application policies that are fine-grained, since individual tuples cannot be specified as objects in database authorizations. In theory, SQL standard provides a way to deal with fine-grained access control through view creation. For example, it is possible to create views for specific users, which allow those users access to only selected tuples of table. However, this approach is not scalable, and essentially impractical in systems with thousands or millions of users, since it would require millions of views to be manually created by a policy administrator.

For this reason, for the past several years, there have been much research on alternative solutions for fine-grained access control for databases. Implementations include query rewriting [START_REF] Franzoni | Towards a Fine-Grained Access Control Model and Mechanisms for Semantic Databases[END_REF], parameterized view creation [START_REF] Rizvi | Extending Query Rewriting Techniques for Fine-grained Access Control[END_REF][START_REF] Roichman | Fine-grained access control to web databases[END_REF] and extensions to SQL [START_REF] Stoller | Trust management and trust negotiation in an extension of sql[END_REF][START_REF] Capitani Di Vimercati | Trust management services in relational databases[END_REF][START_REF] Chaudhuri | Fine grained authorization through predicated grants[END_REF]. Hippocratic databases use meta data stored in the database to make access decisions and are able to enforce cell-level policies. However, neither of those implementations are part of current publicly available commercial SQL servers.

The only currently publicly available implementation of fine-grained database access control (FGAC) is Oracle Virtual Private Database (VPD). This approach is based on Truman Models [START_REF] Rizvi | Extending Query Rewriting Techniques for Fine-grained Access Control[END_REF] and attaches predicates to user submitted queries to enforce row-level policies. However, in our implementation, we were limited to IBM software stack and thus were unable to use Oracle VPD. Use of Oracle VPD by switching to Oracle software stack, or a similar IBM offering when it becomes available, to map and synchronize fine-grained policies is a natural next step in our work.

Security vs. Performance

One of the aspects of policy propagation is the amount of time it takes the change in the enterprise policy, its attribute or attribute relationship to propagate from the application to the database tier. If this time interval is relatively long, then the system security may be compromised. This time period is called the of access vulnerability [START_REF] Jahid | MyABDAC: Compiling XACML Policies for Attribute-based Database Access Control[END_REF] which is caused by policy or attribute updates.

The duration of the window of vulnerability is determined by the implementation of policy synchronization engine. Generally, updates to database policies can be either immediate or deferred. In the immediate mode, whenever enterprise policies are updated, the updates to corresponding database policies are handled with the highest priority with no or relatively short delay. On the other hand, in the deferred mode, the updates to database policies are handled with lower priority and, therefore, the delay can be longer. The trade-off between immediate and deferred modes is the performance overhead imposed by the policy synchronization on the enterprise system.

In MDM domain, the confidential nature of master data has required us to handle the policy propagation in the immediate mode, however the implemented mechanism can be configured to operate in the deferred mode in order to help security administrators achieve a balance between security and performance of the system.

Mapping Correctness

It is important to establish application-to-database security policy mapping correctly, such that the permissions that are given in the database as a result of the policy propagation are indeed the permissions intended by a security administrator who defined them in the application. The understanding of privacy semantics of the application security policies is required in order to establish the correct mapping. Specifically, one needs to know both: how to map the individual policies and how to correctly combine them later.

In order to map the individual attribute-based policy to a set of database authorizations one needs to understand how application-level accessors, resources and data actions correspond to database users, database objects (such as tables and views) and SQL operations. Next, to combine the database authorizations that were produced by the compilation, one needs to use the policy combining and conflict resolution algorithms that were attached to the corresponding individual application-level policies.

In our implementation, policy combining was performed according to the union approach between MDM entitlements and MDM default no-access policy, hence no conflict resolution was required. Therefore, in MDM Server, it was sufficient to verify the mapping of individual application policies (which was correct given the object-relational design of MDM Server) in order to establish the correctness of the application-to-database policy mapping.

End-to-End Audit

An audit trail [START_REF] Dreibelbis | Enterprise Master Data Management: An SOA Approach to Managing Core Information[END_REF] is a process of secure recording of key system events and who initiated them in a chronological log. Auditing is used to reconstruct who-didwhat after the fact. Typically, for a complete picture of a transaction on a data, audit information must be collected at every enterprise system component along the transaction path -it is called an end-to-end trail. The ability of an enterprise system to provide end-to-end auditing facilities is essential for regulatory compliance.

When the enterprise security is enforced at the application tier, the requests to a database are made using a system identity -the identity that is used to represent the application layer, instead of the end-user identity. Since the enduser identity is not sent to the database it may be problematic to provide an audit trail at the database tier.

Following the proposed migration, the end-user identity is propagated down to the database tier and all the database requests required to perform a transaction are made using this propagated identity. This allows us to easily reconstruct the events after the fact by using native database auditing facilities instead of programming the application logic to collect the audit trail.

Migration Methodology

As we mentioned before, many application developers today choose to bypass database-level access control due to the lack of a native database ABAC support. Therefore, we believe that there are many enterprise applications out there which may benefit from our proposed application-to-database security enforcement migration.

Based on our case study, we propose a sound, methodological approach by which organizations can tackle migration projects. To keep our methodology as general as possible, we base it on a well-known industry standard for specifying and managing attribute-based policies -OASIS XACML. In addition to the policy language specification, XACML standard includes the description of the policy management architecture and its data flows (presented in Fig. 4a). In our methodology, we propose the necessary changes to XACML reference architecture in order to accomodate the proposed migration and enable database-level enterprise security enforcement (Fig. 4b).

We believe that ideal migration plan should be broken down into three phases. Known as analysis, implementation and integration, we define these phases in detail below. In the analysis phase one should identify if consistent mapping can be established between enterprise attribute-based policies that are consumed by the PDP at the application tier and identity or role-based policies that are consumed by security mechanisms at the relational database. Similar to the migration in MDM Server, this phase might include establishing relations between enterprise data actions and database permission types, enterprise resources (such as business objects, their associations and hierarchies) and database tables, columns and rows, enterprise accessors (such as users, user groups, roles and role hierarchies) and database users, groups and roles.

Then, the core of the PPP is implemented. Given the attribute-based policies, enterprise accessors and resources that correspond to the policy attributes, this component performs policy compilation and incremental updates according to the established mapping. It is important to realize that MDM Server's fairly straightforward and coarse-grained policy mapping and lack of negative authorizations allowed for relatively unproblematic implementation. However, finer-grained policies and presence of negative authorizations may considerably complicate this phase as necessary inconsistency and conflict resolution would have to be implemented.

Finally, the implemented engine is integrated into the enterprise system. Similar to the migration in MDM Server, two optimizations might be performed in order to keep the integration footprint small. First, PIP and PAP interfaces that supplied PDP with enterprise policies and evaluated the attributes are reused with PPP. Second, subject identity propagation is implemented with the help of a novel trusted context feature of an underlying software stack. Such feature are already supported by IBM and Oracle application servers and relational databases, with more vendors surely to follow. Finally, existing PIP and PAP are modified to enable PPP notification mechanisms necessary for timely incremental policy propagation.

The proposed migration has the following business benefits. First, it ensures better data protection in the enterprise as it eliminates the risks that are associated with using common application layer's authorization ID by providing an additional layer of security at the database tier. Second, by complying with the least common mechanism principle of protection of information in computer systems our migration eases end-to-end enterprise audit and, consequently, it eases the organization's regulatory compliance. Finally, it may lower the overall transaction processing times due to efficiency of the database-tier security engine when compared to the application-tier one.

Related Work

In this section we discuss the related works in the areas of enterprise access control systems and attribute-based database access control techniques.

Enterprise access control enforcement has been interpreted in several efforts. Tivoli Access Manager [START_REF] Karjoth | Access Control with IBM Tivoli Access Manager[END_REF] developed by IBM attempts to decouple the authorization logic from the application logic to allow security policy externalization by using a proxy that sits in front of the application server. IBM Tivoli Security Policy Manager [START_REF]Tivoli Security Policy Manager[END_REF] and Axiomatics Policy Server [START_REF]Axiomatics Policy Server[END_REF] build on that work by enabling enterprise architects to centrally define, manage and enforce XACML security policies for applications and data resources within the enterprise. Ladon [START_REF]Ladon XACML enforcement for DB2[END_REF] is Java-based API that enforces access control policies written in XACML by rewriting incoming SQL queries. However, in these products, the security policies are still enforced at the application level and inherit all disadvantages of this approach.

Little work has been done on the database-level attribute-based policy verification. Our work follows the recent work [START_REF] Jahid | MyABDAC: Compiling XACML Policies for Attribute-based Database Access Control[END_REF] which aims to compile attributebased XACML policies into ACLs that are supported by conventional databases. The authors develop a toy prototype based on MySQL relational database to show that such compilation significantly improves attribute-based database access time with a price of reasonable off-line compilation time. Inspired by this work, we realized that such compilation can be used to provide an enhanced security, end-to-end audit and simplified compliance in many existing enterprise systems. Our work builds on this observation by describing the security enforcement migration in existing industrial-grade system and providing standardsdriven migration methodology based on the enterprise software stack that enables database-level attribute-based policy enforcement in existing enterprise systems.

Conclusions

In this work, we presented a case study of migration of access control enforcement from the application to the database tier. This migration aims to overcome the security and audit concerns that are associated with the application-tier security mechanisms in an existing enterprise application. We considered our approach in the context of master data management where data security, privacy and audit are subject to regulatory compliance. We implemented the proposed migration in an industrial-grade MDM system to prove the applicability and usefulness of our idea. Finally, we proposed a general standards-driven and vendor-independent methodology that is designed to tackle similar security enforcement migration projects.

The proposed migration has two positive effects on the overall security and regulatory compliance of the enterprise system. First, our approach enhances the security by eliminating the vulnerability to privilege escalation attacks. Second, our approach eases the enterprise end-to-end audit by enabling native databasetier auditing facilities. Further, our approach has a small integration footprint by effectively reusing existing enterprise security components and novel features of an underlying software stack. Our reference model seamlessly integrates into the existing enterprise security architecture by requiring only minor modifications to the initial enterprise system code base, which makes it feasible to implement in a large-scale enterprise application.

There are two areas of further interest to us in this project. First, as we mentioned in Section 4.2, our approach handles only coarse-grained table-level policies. This is caused by the limitations of an underlying relational database, which in our case was IBM DB2. In the future, we plan to experiment with Oracle software stack to extend the policy propagation engine to handle fine-grained access control (FGAC). We envision that this can dramatically improve the enterprise transaction processing times since the selectivity of FGAC-transformed query is higher than that of the original query due to introduction of policy related predicates. Second, we plan to perform an evaluation of our approach in an actual production enterprise environment. The organization of the protected data and its accessors and the patterns in which the policies or their attributes are changed would help us understand the real effects our approach has on the enterprise system. This information will be invaluable in determining further optimizations to our engine.

Fig. 4 .

 4 Fig. 4. Extended XACML Architecture


Abbas Taheri Soodejani

Mohammad Ali Hadavi
email: mhadavi@ce.

Rasool Jalili
email: jalili@sharif.edu

Andy Hypertension

Andy Med

David Med

C Bob

Bob Med

D David

Sara Flu

Tom Med

X Sara

k-Anonymity-Based Horizontal Fragmentation to Preserve Privacy in Data Outsourcing

Keywords: Data outsourcing, privacy, horizontal fragmentation, k-anonymity Illness Treatment Info

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In fragmentation-based approach, some data columns are separated from each other to hide their sensitive associations, called vertical fragmentation; and also some sensitive tuples are separated from non-sensitive tuples, called horizontal fragmentation.

From the owner involvement in data storage view, fragmentation-based methods fall into two categories: (1) Partial-outsourcing methods [START_REF] Ciriani | Enforcing Confidentiality Constraints on Sensitive Databases with Lightweight Trusted Clients[END_REF][START_REF] Wiese | Horizontal fragmentation for data outsourcing with formula-based confidentiality constraints[END_REF][START_REF] Ciriani | Keep a few: outsourcing data while maintaining confidentiality[END_REF], which store a portion of data at the owner side, (2) Full-outsourcing methods [START_REF] Ciriani | Combining fragmentation and encryption to protect privacy in data storage[END_REF][START_REF] Aggarwal | Two can keep a secret: A distributed architecture for secure database services[END_REF][START_REF] Foresti | Preserving privacy in data outsourcing[END_REF], which completely outsource the data to the external server. Partial-outsourcing methods get involved the owner in data storage and consequently data management, which is largely in contradiction with the goal of outsourcing, i.e., outsourcing data management. On the other hand, full-outsourcing methods outsource all data exploiting data encryption. Consequently, they suffer from the same disadvantages as the encryption-based approach.

Our method is based on horizontal fragmentation. The main idea is to identify and k-anonymize the sensitive tuples. Anonymized tuples are stored as a fragment and non-sensitive tuples are stored as a logically separate fragment, both at the server side.

This paper proposes a full-outsourcing method that unlike the existing fulloutsourcing methods does not use encryption but anonymization to provide privacy. The method is appropriate for scenarios that even encrypting or even not outsourcing the sensitive data cannot guarantee the privacy. In addition, our method inherits some benefits of the horizontal fragmentation in [START_REF] Wiese | Horizontal fragmentation for data outsourcing with formula-based confidentiality constraints[END_REF] such as is consistency with database normalization techniques, content-aware fragmentation, introducing a logical formalism for our fragmentation and controlling inference using data dependencies.

The rest of this paper is organized as follows. Section 2 introduces the basic concepts and definitions. Section 3 presents an algorithm for our fragmentation method. Finally, section 4 concludes the paper.

Basic concepts

Our view of relational databases is the formalism of first-order predicate logic with equality. We describe how to formalize some relational concepts with this formalism.

Relational instance: we view an instance I of a relational database schema  as a set of expressions of the form R(a 1 , a 2 , ... , a n ), where R is an n-ary relation name in  and the a i "s are constants. Such expressions are called ground tuples. ⧠ Database dependency: Database dependencies are domain-specific declarations reflecting the intended meaning of the stored data in a database. Along with the definition of a schema , a set of data dependencies  is defined that consists of tuplegenerating dependencies (TGDs) and equality-generating dependencies (EGDs). Definition 1 (Tuple-generating dependency). A tuple-generating dependency (TGD) is a closed formula of the form ∀𝒙 (ϕ(𝒙) ⟶ ∃𝒚 ψ(𝒙, 𝒚)), where 𝒙 and 𝒚 are vectors of variables; ϕ(𝒙) is a (possibly empty) conjunction of atomic formulas, all with variables among the variables in 𝒙; ψ(𝒙, 𝒚) is a conjunction of atomic formulas, all with variables among the variables in 𝒙 and 𝒚. Definition 2 (Equality-generating dependency). An equality-generating dependency (EGD) is a closed formula of the form ∀𝒙 (ϕ(𝒙) ⟶ ψ(𝒙)), where 𝒙 is a vector of variables; ϕ(𝒙) is a conjunction of atomic formulas, all with variables among the variables in 𝒙; ψ(𝒙) is a conjunction of formulas of the form 𝑥 = 𝑥´, where 𝑥 and 𝑥´are distinct variables in 𝒙.

For a dependency, we call ϕ the body and ψ the head of dependency, respectively. EXAMPLE 2. In our example, set of dependencies  can contain the following formulas: The TGD d

I: I ⊭ ψ(𝒙)[𝒂/𝒙] if d is an EGD).
In other words, a dependency d is said to be violated if there exists a set of ground tuples in I from which the body of d can be instantiated but no tuples exist in I that the head of d can be fully instantiated from.

If the instance I violates some dependencies in , a procedure called Chase [START_REF] Beeri | A Proof Procedure for Data Dependencies[END_REF][START_REF] Maier | Testing implications of data dependencies[END_REF] is run on I. Running the chase on I, fixes the violated dependencies. In other words, the result of the chase is an instance, called chased instance, that satisfies all dependencies in . We refer the reader to [START_REF] Wiese | Horizontal fragmentation for data outsourcing with formula-based confidentiality constraints[END_REF][START_REF] Fagin | Data exchange: semantics and query answering[END_REF] for more details about the chase procedure.

Syntax of privacy constraints

Data owner"s privacy requirements are modeled through privacy constraints: Definition 4 (Privacy constraint). Given a database schema = {R 1 , R 2 , ... , R m }, a privacy constraint c is a closed formula of the form ∃𝒙 α(𝒙), where 𝒙 is a vector of variables; α(𝒙) is a conjunction of positive atomic formulas, all with variables among the variables in 𝒙 and constants from the domains of attributes.

In the above definition, α(𝒙) is a conjunction of partial instantiation of R i "s in . Definition 4 states that if there exist tuples in the database instance that yield an instantiation of the formula α(𝒙), then there is a privacy violation, we say a sensitive knowledge is disclosed. The set of tuples that violate a privacy constraint is called the violation set denoted by V. Note that we restrict the syntax of privacy constraints to formulas without negation and with only conjunction as logical connective. EXAMPLE 3. For the database schema  in our example, the set of privacy constraints, denoted by , may contain the following formulas:

c 1 : ∃n Illness(n, Aids) c 2 : ∃d Illness(Sara, d) c 3 : ∃n, nʹ (Illness(n, Cholera) ˄ Treatment(nʹ, Med X) ˄ Treatment (nʹ, Med Y))
where c 1 states that if there exists a tuple with value "Aids" for attribute Disease, a privacy violation occur. In this case, the name of the person who contracted Aids is the sensitive knowledge. Similar interpretation holds for c 2 . The constraint c 3 states that if there exist three tuples, one from relation Illness with name "n" and disease "Cholera" and the other two from relation Treatment with the same name "n´" but one with medicine "Med X" and the other with medicine "Med Y", then these tuples together violate the privacy. Here, the sensitive knowledge is a sensitive association between n and n´, e.g., n´ will be contracted Cholera (say, because Cholera is an infectious disease and all persons in the database live in the same place). ⧠

k-Anonymity

In some scenarios, encrypting or not outsourcing sensitive data may not guarantee the privacy. For example, consider a healthcare database of patients" records. Let the records of the patients that contracted Aids be sensitive. To provide privacy, one may encrypt or not outsource the records of the patients with disease Aids. Alice has disease Aids, hence she has a record in the database. The attacker Bob knows that Alice has a disease but not exactly which kind of disease. He also knows that records with disease Aids are sensitive. He examines the data and observes that there is no record for Alice in the database. Therefore, he can infer that Alice has disease Aids. There are other scenarios that encrypting or suppressing data do not guarantee the privacy.

In these scenarios, we exploit the k-anonymity concept to provide privacy. Our method, inspired from the k-anonymity concept [START_REF] Samarati | Generalizing data to provide anonymity when disclosing information[END_REF], aims to provide privacy of degree k. To this aim, some fake tuples is produced in a way that for each sensitive knowledge at least k -1 sensitive but fake knowledge can be inferred from database instance. Thus, the probability of a sensitive knowledge being real is equal to or less than 1/k.

Let c be a violated constraint and V be its violation set. To provide privacy with degree k for c, we produce k -1 (possibly overlapping) violation sets, all violating the same constraint c. Thus, for c, we have k violation sets and the sensitive knowledge of c is anonymized with k -1 fake knowledge.

For the sake of simplicity, for each violated constraint we assume that the number of sensitive tuples in its violation set is one (generalizing the concepts to violation sets with more than one tuple is straightforward). Also, we assume that the sensitive knowledge is the value of an attribute S, called sensitive attribute. With this assumption, the k-anonymity concept in our method is captured by the following principle: Definition 5 (k-anonymity principle). For a violation set of a constraint c with sensitive attribute S, there must be at least k -1 fake violation sets all instantiated from c, and the set of k violation sets contains at least k distinct values for attribute S. EXAMPLE 4. Two tuples Illness(Bob, Aids) and Illness(Sara, Flu) violate the constraints c 1 and c 2 , respectively, from Example 3. Let the attribute Name for c 1 and Disease for c 2 be the sensitive attributes. We produce tuples Illness(Jim, Aids) and Illness(Sara, Influenza) to 2-anonymize these two violation sets, respectively. ⧠

Syntax of anonymization rules

As mentioned in the previous section, the sensitive knowledge inferable from those tuples violating a privacy constraint should be anonymized. For each privacy constraint we define an anonymization rule that states which attribute or combination of attributes (that are sensitive) in which tuples should be anonymized.

Definition 6 (Anonymization rule). An anonymization rule for a privacy constraint c

of the form ∃𝒙 α(𝒙), is a formula of the form ∃𝒙 α(𝒙) → ∃𝒚 β(𝒚), where 𝒙 and α(𝒙) are those defined in Definition 4; 𝒚 is a (possibly empty) vector of variables; β(𝒚) is a conjunction of positive formulas all with free variables, bounded variables, and constants; and k is the k-anonymity parameter.

In Definition 6, α(𝒙) and β(𝒚) are called the body and head of the rule, respectively. According to the head we determine which tuples and, more specifically, which attributes should be anonymized. The above formula states that if there exist tuples that instantiate the body α(𝒙), consequently violating a constraint, then there must exist k -1 fake instantiations for the head β(𝒚). In fact, for a violated constraint, we apply an anonymization rule to achieve the k-anonymity principle in Definition 5. In β(𝒚), constants are values of the attributes, such as name, that their values can identify a sensitive knowledge; free variables represent a set of attributes, such as disease, that their values are sensitive; and bounded variables represent the attributes that have no role in the identification and have no association with the sensitive knowledge. EXAMPLE 5. The set of anonymization rules, denoted by , corresponding to the privacy constraints in Example 3 contains the following rules: The rule r 1 states that to anonymize a tuple that instantiates Illness(n, Aids), violating c 1 , k -1 fake tuples should be produced that are instantiations of Illness FS (n, Aids). In the set of k -1 fake tuples, the attribute Disease should take the value "Aids" and the attribute Name should be anonymized by taking k -1 distinct values. Similar interpretation holds for r 2 . The rule r 3 states that if there exist tuples that instantiate c 3 , the sensitive knowledge can be anonymized by generating 2(k -1) fake tuples; k -1 tuples that instantiate Treatment FS (nʹ, Med X), and k -1 tuples that instantiate Treatment FS (nʹ, Med Y). For the attribute Name in the latter k -1 tuples, we use the same values used in the former k -1 tuples. ⧠

Fragmentation

In this section, we first define the requirements of a correct horizontal fragmentation. Then, we introduce an algorithm to produce a correct fragmentation.

Fragmentation correctness

A fragmentation is correct if it satisfies three requirements: completeness, nonredundancy, and privacy. The completeness requirement states that we must be able to reconstruct the original database instance from its corresponding fragments. The non-redundancy requirement states that the fragments should not have common tuples and/or attributes (depending on the fragmentation method). The privacy requirement states that the fragmentation must satisfy the privacy constraints so that no sensitive knowledge can be inferred from the fragments. The completeness and privacy are two mandatory requirements that any fragmentation method must satisfy them, while the non-redundancy requirement can be considered optional as it is not applicable to all methods. We define fragmentation correctness in our method as follows: Definition 7 (Fragmentation correctness). Let  be a database schema with a set of dependencies . Let  be a set of privacy constraints and k be the k-anonymity parameter. Also let  = {F NS , F S } be a fragmentation for instance I of , where F S and F NS are sensitive and non-sensitive fragments, respectively.  is a correct fragmentation with respect to  iff both the following conditions hold:

1. I ∩ (F NS ∪ F S ) = I (Completeness requirement), 2. ∀c i ∊ : (F NS ∪ F S ) ∪  ⊭ c i , otherwise P(c i ) ≤ 1/k (Privacy requirement).
According to Definition 7, a fragmentation is complete if taking the union of the fragments and removing the fake tuples, yields the original instance I. Also, it preserves privacy if applying the dependencies, as deduction rules, to the tuples in F NS and F S , as ground tuples, does not imply a privacy constraint. Otherwise, the probability of the knowledge inferable from the constraint should be equal to or less than 1/k.

k-Anonymity-based horizontal fragmentation algorithm

Based on Definition 7, we present an algorithm that produces a correct fragmentation. The general scheme of our method is showed in Figure 2. First, we identify those tuples in I that instantiate some privacy constraints (step 1). These tuples are called explicitly sensitive tuples and move them to F S (step 2). We also identify the tuples in I that do not explicitly violate any constraint but implicitly violate some constraints, i.e., by applying dependencies. These tuples are called implicitly sensitive tuples and move them to F S (step 2). By this step, all explicitly and implicitly sensitive tuples are moved to F S but there may be some tuples that can be used to gain extra information about the sensitive tuples. Consider the tuples that their existence depends only on the existence of other tuples, i.e., produced by only applying dependencies to other tuples. These tuples are called dangling tuples and move them to F S (step 2). After step 2, all remaining tuples in I are non-sensitive (because all sensitive tuples have been moved to F S ) and move them to F NS (step 3). For the explicitly sensitive tuples in step 1, we produce some fake tuples (k -1 violation sets) to k-anonymize their respective sensitive knowledge and place them in F S (step 4). In addition to the fake violation sets, some other fake tuples is produced and placed in F S (step 4), c.f. Section 3.3. Subsequently, we chase F S to satisfy all dependencies (step 5, not shown in Figure 2).

Fig. 2. General scheme of the proposed method

For each sensitive tuple in step 2 a metadata, e.g., a tuple id, is produced and placed in F S along with that tuple (step 2´). These metadata are also stored at the owner side and used to recognize the real tuples in the future accesses to F S .

Cascading tuples

Consider tuples t 1 , t 2 , … , t n , where tuple t n is generated by applying dependency d n-1 to tuple t n-1 and t n-1 itself is generated by applying dependency d n-2 to tuple t n-2 , … , finally tuple t 2 is generated by applying dependency d 1 to tuple t 1 . We call this phenomenon cascading tuples. Let tuple t n be explicitly sensitive. Therefore, tuples t 1 , t 2 , … , t n-1 are implicitly sensitive. According to the previous section, t n is anonymized with some fake tuples and moved to F S . Tuples t 1 , t 2 , … , t n-1 are also moved to F S . The attacker observes that t 1 , t 2 , … , t n-1 are not explicitly sensitive but they are in F S and if dependencies d 1 , d 2 , … , d n-1 be applied consecutively to these tuples, then t n will be generated. Thus, s/he infers that t 1 , t 2 , … , t n-1 are implicitly sensitive tuples and consequently real tuples. Based on this observation, s/he infers that t n is also a real tuple with probability 1 that is greater than value 1/k in Definition 7, violating the privacy requirement. To thwart this inference, we propose the following solution: For a set ∑ of TGDs we construct a directed graph, called dependency graph, denoted by DG, as follows: 

For each TGD ∀𝒙 (ϕ(𝒙) ⟶ ∃𝒚 ψ(𝒙, 𝒚)): for the set of atoms a 1 , a 1 , … , a n in ϕ, add a new node to DG, if it does not already exist.



For each TGD ∀𝒙 (ϕ(𝒙) ⟶ ∃𝒚 ψ(𝒙, 𝒚)): add an edge from the node corresponding to ϕ to the node that contain atom b of ψ. Let t n be anonymized with k -1 fake tuples f 1 , f 2 , … , f k-1 . For each f i (i=1, …, k -1) we find a node in DG from which f i can be instantiated. Then, proceed downwards to a leaf node and instantiate with fake values (values from domains of attributes) all the nodes on the path to that leaf. In this way, the probability of the tuples f 1 , f 2 , … , f k-1 , and t n and their respective implicitly sensitive tuples being real, is equal to or less than 1/k. Therefore, for each explicitly sensitive real tuple we produce some fake tuples in the above way to prevent from inferences about the real tuples.

Sensitive tuples identification k-Anonymization

k-Anonymity-based horizontal fragmentation algorithm

The proposed algorithm consists of the following steps:

Step 1. Initially, fragments F S and F NS are empty. A temporary set fake_tuples is considered that will contain the fake tuples used to anonymize the sensitive tuples.

Step 2. The purpose of this step is to identify the explicitly sensitive tuples and move them to F S . For each constraint α(𝒙)[𝒂/𝒙] in , we identify vectors of constants 𝒂 such that the instantiation α(𝒙)[𝒂/𝒙] of variables 𝒙 with constants 𝒂 holds in the input instance I, i.e., I ⊨ ϕ(𝒙)[𝒂/𝒙]. This implies that I explicitly violates the constraint (as a result, a sensitive knowledge can be inferred from I). To prevent this explicit inference, we remove from I and move to F S the tuples participating in the instantiation of (𝒙)[𝒂 𝒙 ⁄ ], i.e., the violation set of the constraint. Also, we anonymize these tuples with some fake tuples. The fake tuples are moved to fake_tuples.

Step 3. The purpose of this step is to identify the implicitly sensitive and dangling tuples and move them to F S . By removing the explicitly sensitive tuples from I, some dependencies may be violated by I, helping the attacker to gain extra information about the sensitive tuples. To prevent this, for each TGD ∀𝒙 (ϕ(𝒙) ⟶ ∃𝒚 ψ(𝒙, 𝒚)) we identify those tuples of constants 𝒂 such that the instantiations (𝒙)[𝒂 𝒙 ⁄ ] and ψ(𝒙, 𝒚)[𝒂/𝒙, /𝒚] of variables 𝒙, 𝒚 with constants 𝒂 hold in the union of the input instance and sensitive fragment. If both of the body and head are only in I or only in F S , no inference can be done. Otherwise, the following inferences may be possible: Inference type 1: The TGD body is in I and the TGD head is in F S : I ⊨ ϕ(𝒙)[𝒂/𝒙], I ⊭ ψ(𝒙, 𝒚)[𝒂/𝒙, /𝒚], F S ⊨ ψ(𝒙, 𝒚)[𝒂/𝒙, /𝒚] In this case, an attacker can apply the TGD, produce its head, and implicitly infer about some sensitive tuples, i.e., the head of TGD, in F S . To prevent this implicit inference, all parts of the TGD body must be moved to F S . Inference type 2: The TGD body is in F S and the head is in I:

F S ⊨ ϕ(𝒙)[𝒂/𝒙] , F S ⊭ ψ(𝒙, 𝒚)[𝒂/𝒙, /𝒚], I ⊨ ψ(𝒙, 𝒚)[𝒂/𝒙, /
𝒚] In this case, an attacker observes that there exist some tuples that are generated by the TGD in I but the tuples in the TGD body are missing in I (dangling tuples), because they are moved to F S . To prevent this inference, all parts of the TGD head must be moved to F S . Inference type 3: Some parts of the body are in I and some parts of the head are in F S : I ∪ F S ⊨ ϕ(𝒙)[𝒂/𝒙], I ∪ F S ⊨ ψ(𝒙, 𝒚)[𝒂/𝒙, /𝒚] This case is a general type of the two previous types. In this case, all parts of the body and all parts of the head that are in I must be moved to F S .

If any tuple is moved to F S in this step, we will repeat this step until there exists no tuple that can be used for one or more of the above three types of inferences.

Step 4. By this step, there is no tuple in I that can be used for inference. Now, we move the remaining tuples, i.e., non-sensitive tuples, to F NS .

Step 5. We add the fake tuples produced in Step 1, i.e., tuples in fake_tuples, to F S . The newly added tuples may cause F S violating some dependencies. In this case, we chase F S with the dependencies and produce a chased fragment satisfying all dependencies. In the newly generated tuples, we replace the "labeled nulls" (see [START_REF] Fagin | Data exchange: semantics and query answering[END_REF]) with some fake values (values from domains of attributes). This prevents the attacker from knowing that they are produced from some fake tuples.

Step 6. Finally, fragmentation  consisting of F S and F NS is returned as the result of the fragmentation algorithm.

Illness_FNS

Conclusion

We presented a horizontal fragmentation that outsources all data but do not use encryption to provide privacy. Also, an algorithm presented that produces a correct fragmentation. The main application of the method is for scenarios where even encrypting or suppressing the sensitive data cannot guarantee the privacy. Several issues remain: our method, to achieve k-anonymity, produces k -1 fake violation sets for each violated constraint. This may result in high storage and bandwidth overheads for large volumes of sensitive data and large values of k. The adoption of other ways, such as a probabilistic approach, to provide privacy with degree k but with less than k -1 fake violation sets, can be investigated as a future work. In this paper, we employed a version of the chase, called standard chase, which put some restrictions on the dependencies and constrains, such as being positive and conjunctive. Investigating the applicability of other versions of the chase in the method can be studied further. The anonymity principle of our method has some similarities to the l-diversity privacy model [START_REF] Machanavajjhala | l-diversity: Privacy beyond k-anonymity[END_REF]. Investigating other privacy models, such as t-closeness [START_REF] Ninghui | t-Closeness: Privacy Beyond k-Anonymity and l-Diversity[END_REF], to provide a stronger privacy model for the proposed method can be valuable.

Fig. 1 .

 1 Fig. 1. An instance (I) of a database schema

d 1 :

 1 ∀n, d (Illness(n, d) ⟶ ∃b, z Info(n, b, z)) d 2 : ∀n, m (Treatment(n, m) ⟶ ∃d Illness(n, d)) d 3 : ∀n (Treatment(n, Med D) ∧ Treatment(n, Med E) ⟶ Illness(n, Aids)) d 4 : ∀n, d, z, d´, z´ (Info(n, d, z) ∧ Info(n, d´, z´) ⟶ (d = d´ ∧ z = z´))

r 1 :

 1 ∃n Illness(n, Aids) → Illness FS (n, Aids) r 2 : ∃d Illness(Sara, d) → Illness FS (Sara, d) r 3 : ∃n, nʹ (Illness(n, Cholera) ˄ Treatment(nʹ, Med X) ˄ Treatment(nʹ, Med Y)) → (Treatment FS (nʹ, Med X) ˄ Treatment FS (nʹ, Med Y)) Relation names above with subscripted FS indicate relations in the fragment F S .

Fig. 3 . 1 EXAMPLE 6 .

 316 Fig. 3.A fragmentation for instance I in Figure1EXAMPLE 6. Consider the instance I, the set of dependencies , the set of privacy constraints , and the set of anonymization rules , from Examples 1-5, respectively. We fragmented I using our algorithm. The result is shown in Figure3. Attribute values in bold represent the tuples produced for cascading tuples. Attribute values in italic represent the labeled nulls replaced with fake values; the chase applied the dependency d 3 to the fake tuple Illness(Jim, Aids) and generated Info(Jim, labeled_null 1 , labeled_null 2 ) and replaced them with values 1959/02/15 and 78452, respectively. ⧠