Data and Applications Security and Privacy XXVIII

Frontmatter

Integrity Assurance for Outsourced Databases without DBMS Modification

Abstract

Database outsourcing has become increasingly popular as a cost-effective solution to provide database services to clients. Previous work proposed different approaches to ensuring data integrity, one of the most important security concerns in database outsourcing. However, to the best of our knowledge, existing approaches require modification of DBMSs to facilitate data authentication, which greatly hampers their adoption in practice. In this paper, we present the design and implementation of an efficient and practical integrity assurance scheme without requiring any modification to the DBMS at the server side. We develop novel schemes to serialize Merkle B-tree based authentication structures into a relational database that allows efficient data retrieval for integrity verification. We design efficient algorithms to accelerate query processing with integrity protection. We further build a proof-of-concept prototype and conduct extensive experiments to evaluate the performance overhead of the proposed schemes. The experimental results show that our scheme imposes a low overhead for queries and a reasonable overhead for updates while ensuring integrity of an outsourced database without special support from server-side DBMSs.

Wei Wei, Ting Yu

Specification and Deployment of Integrated Security Policies for Outsourced Data

Abstract

This paper presents a well-founded language allowing in one hand data owners to easily specify their security and utility requirements over the data to be outsourced and in an another hand to formalize the set of security mechanisms that can be used for the protection of outsourced data. Based on the formalization of security and utility requirements and security mechanisms properties, we formally identify the best mechanisms, and the best way to combine them to get the best trade-off between utility and security.

Anis Bkakria, Frédéric Cuppens, Nora Cuppens-Boulahia, David Gross-Amblard

Optimizing Integrity Checks for Join Queries in the Cloud

Abstract

The large adoption of the cloud paradigm is introducing more and more scenarios where users can access data and services with an unprecedented convenience, just relying on the storage and computational power offered by external providers. Also, users can enjoy a diversity and variety of offers, with the possibility of choosing services by different providers as they best suit their needs. With the growth of the market, economic factors have become one of the crucial aspects in the choice of services. However, security remains a major concern and users will be free to actually benefit from the diversity and variety of such offers only if they can also have proper security guarantees on the services. In this paper, we build upon a recent proposal for assessing integrity of computations performed by potentially untrusted providers introducing some optimizations, thus limiting the overhead to be paid for integrity guarantees, and making it suitable to more scenarios.

Sabrina De Capitani di Vimercati, Sara Foresti, Sushil Jajodia, Stefano Paraboschi, Pierangela Samarati

Privacy-Enhancing Proxy Signatures from Non-interactive Anonymous Credentials

Abstract

Proxy signatures enable an originator to delegate the signing rights for a restricted set of messages to a proxy. The proxy is then able to produce valid signatures only for messages from this delegated set on behalf of the originator. Recently, two variants of privacy-enhancing proxy signatures, namely blank signatures [25] and warrant-hiding proxy signatures [26], have been introduced. In this context, privacy-enhancing means that a verifier of a proxy signature does not learn anything about the delegated message set beyond the message being presented for verification.

We observe that this principle bears similarities with functionality provided by anonymous credentials. Inspired by this observation, we examine black-box constructions of the two aforementioned proxy signatures from non-interactive anonymous credentials, i.e., anonymous credentials with a non-interactive showing protocol, and show that the so obtained proxy signatures are secure if the anonymous credential system is secure. Moreover, we present two concrete instantiations using well-known representatives of anonymous credentials, namely Camenisch-Lysyanskaya (CL) and Brands’ credentials.

While constructions of anonymous credentials from signature schemes with particular properties, such as CL signatures or structure-preserving signatures, as well as from special variants of signature schemes, such as group signatures, sanitizable and indexed aggregate signatures, are known, this is the first paper that provides constructions of special variants of signature schemes, i.e., privacy-enhancing proxy signatures, from anonymous credentials.

David Derler, Christian Hanser, Daniel Slamanig

Privacy-Preserving Multiple Keyword Search on Outsourced Data in the Clouds

Abstract

Honest but curious cloud servers can make inferences about the stored encrypted documents and the profile of a user once it knows the keywords queried by her and the keywords contained in the documents. We propose two progressively refined privacy-preserving conjunctive symmetric searchable encryption (PCSSE) schemes that allow cloud servers to perform conjunctive keyword searches on encrypted documents with different privacy assurances. Our scheme generates randomized search queries that prevent the server from detecting if the same set of keywords are being searched by different queries. It is also able to hide the number of keywords in a query as well as the number of keywords contained in an encrypted document. Our searchable encryption scheme is efficient and at the same time it is secure against the adaptive chosen keywords attack.

Tarik Moataz, Benjamin Justus, Indrakshi Ray, Nora Cuppens-Boulahia, Frédéric Cuppens, Indrajit Ray

Secure and Privacy-Preserving Querying of Personal Health Records in the Cloud

Abstract

Personal Health Records (PHR) are user-friendly, online solutions that give patients a way of managing their own health information. Many of the current PHR systems allow storage providers to access patients’ data. Recently, architectures of storing PHRs in cloud have been proposed. However, privacy remains a major issue for patients. Consequently, it is a promising method to encrypt PHRs before outsourcing. Encrypting PHRs prevents health organizations from analyzing medical data. In this paper, we propose a protocol that would allow health organizations to produce statistical information about encrypted PHRs stored in the cloud. The protocol depends on two threshold homomorphic cryptosystems: Goldwasser-Micali (GM) and Paillier. It executes queries on Kd-trees that are constructed from encrypted health records. It also prevents patients from inferring what health organizations are concerned about. We experimentally evaluate the performance of the proposed protocol and report on the results of implementation.

Samira Barouti, Feras Aljumah, Dima Alhadidi, Mourad Debbabi

Data Leakage Quantification

Abstract

The detection and handling of data leakages is becoming a critical issue for organizations. To this end, data leakage solutions are usually employed by organizations to monitor network traffic and the use of portable storage devices. These solutions often produce a large number of alerts, whose analysis is time-consuming and costly for organizations. To effectively handle leakage incidents, organizations should be able to focus on the most severe incidents. Therefore, alerts need to be prioritized with respect to their severity. This work presents a novel approach for the quantification of data leakages based on their severity. The approach quantifies leakages with respect to the amount and sensitivity of the leaked information as well as the ability to identify the data subjects of the leaked information. To specify and reason on data sensitivity in an application domain, we propose a data model representing the knowledge in the domain. We validate our approach by analyzing data leakages within a healthcare environment.

Sokratis Vavilis, Milan Petković, Nicola Zannone

Toward Software Diversity in Heterogeneous Networked Systems

Abstract

When there are either design or implementation flaws, a homogeneous architecture is likely to be disrupted entirely by a single attack (e.g., a worm) that exploits its vulnerability. Following the survivability through heterogeneity philosophy, we present a novel approach to improving survivability of networked systems by adopting the technique of software diversity. Specifically, we design an efficient algorithm to select and deploy a set of off-the-shelf software to hosts in a networked system, such that the number and types of vulnerabilities presented on one host would be different from that on its neighboring nodes. In this way, we are able to contain a worm in an isolated “island”. This algorithm addresses software assignment problem in more complex scenarios by taking into consideration practical constraints, e.g., hosts may have diverse requirements based on different system prerequisites. We evaluate the performance of our algorithm through simulations on both simple and complex system models. The results confirm the effectiveness and scalability of our algorithm.

Chu Huang, Sencun Zhu, Robert Erbacher

FSquaDRA: Fast Detection of Repackaged Applications

Abstract

The ease of Android applications repackaging and proliferation of application clones in Google Play and other markets call for new effective techniques to detect repackaged code and combat distribution of cloned applications. Today all existing techniques for repackaging detection are based on code similarity or feature (e.g., permission set) similarity evaluation. We propose a new approach to detect repackaging based on the resource files available in application packages. Our tool called FSquaDRA performs a quick pairwise application comparison (full pairwise comparison for 55,000 applications in just 80 hours on a laptop), as it measures how many identical resources are present inside both packages under analysis. The intuition behind our approach is that malicious repackaged applications still need to maintain the “look and feel” of the originals by including the same images and other resource files, even though they might have additional code included or some of the original code removed.

To evaluate the reliability of our approach we perform a comparison of the FSquaDRA similarity scores with the code-based similarity scores of AndroGuard for a dataset of randomly selected application pairs, and our results demonstrate strong positive correlation of the FSquaDRA resource-based score with the code-based similarity score.

Yury Zhauniarovich, Olga Gadyatskaya, Bruno Crispo, Francesco La Spina, Ermanno Moser

‘Who, When, and Where?’ Location Proof Assertion for Mobile Devices

Abstract

In recent years, location of mobile devices has become an important factor. Mobile device users can easily access various customized applications from the service providers based on the current physical location information. Nonetheless, it is a significant challenge in distributed architectures for users to prove their presence at a particular location in a privacy-protected and secured manner. So far, researchers have proposed multiple schemes to implement a secure location proof collection mechanism. However, such location proof schemes are subject to tampering and not resistant to collusion attacks. Additionally, the location authority providing a location proof is assumed to be honest at all times. In this paper, we present the fundamental requirements of any location proof generation scheme, and illustrate the potential attacks possible in such non-federated environments. Based on our observations, we introduce a concept of witness oriented endorsements, and describe a collusion-resistant protocol for asserted location proofs.We provide an exhaustive security analysis of the proposed architecture, based on all possible collusion models among the user, location authority, and witness. We also present a prototype implementation and extensive experimental results to adjust different threshold values and illustrate the feasibility of deploying the protocol in regular devices for practical use.

Rasib Khan, Shams Zawoad, Md Munirul Haque, Ragib Hasan

Design Patterns for Multiple Stakeholders in Social Computing

Abstract

In social computing, multiple users may have privacy stakes in a content (e.g., a tagged photo). They may all want to have a say on the choice of access control policy for protecting that content. The study of protection schemes for multiple stakeholders in social computing has captured the imagination of researchers, and general-purpose schemes for reconciling the differences of privacy stakeholders have been proposed.

A challenge of existing multiple-stakeholder schemes is that they can be very complex. In this work, we consider the possibility of simplification in special cases. If we focus on specific instances of multiple stakeholders, are there simpler design of access control schemes? We identify two design patterns for handling a significant family of multiple-stakeholder scenarios. We discuss efficient implementation techniques that solely rely on standard SQL technology. We also identify scenarios in which general-purpose multiple-stakeholder schemes are necessary. We believe that future work on multiple stakeholders should focus on these scenarios.

Pooya Mehregan, Philip W. L. Fong

Collaboratively Solving the Traveling Salesman Problem with Limited Disclosure

Abstract

With increasing resource constraints, optimization is necessary to make the best use of scarce resources. Given the ubiquitous connectivity and availability of information, collaborative optimization problems can be formulated by different parties to jointly optimize their operations. However, this cannot usually be done without restraint since privacy/security concerns often inhibit the complete sharing of proprietary information. The field of privacy-preserving optimization studies how collaborative optimization can be performed with limited disclosure. In this paper, we develop privacy-preserving solutions for collaboratively solving the traveling salesman problem (TSP), a fundamental combinatorial optimization problem with applications in diverse fields such as planning, logistics and production. We propose a secure and efficient protocol for multiple participants to formulate and solve such a problem without sharing any private information. We formally prove the protocol security under the rigorous definition of secure multiparty computation (SMC), and demonstrate its effectiveness with experimental results using real data.

Yuan Hong, Jaideep Vaidya, Haibing Lu, Lingyu Wang

ELITE: zEro Links Identity managemenT systEm

Abstract

Modern day biometric systems, such as those used by governments to issue biometric-based identity cards, maintain a deterministic link between the identity of the user and her biometric information. However, such a link brings in serious privacy concerns for the individual. Sensitive information about the individual can be retrieved from the database by using her biometric information. Individuals, for reasons of privacy therefore, may not want such a link to be maintained. Deleting the link, on the other hand, is not feasible because the information is used for purposes of identification or issuing of identity cards. In this work, we address this dilemma by hiding the biometrics information, and keeping the association between biometric information and identity probabilistic. We extend traditional Bloom filters to store the actual information and propose the SOBER data structure for this purpose. Simultaneously, we address the challenge of verifying an individual under the multitude of traits assumption, so as to guarantee that impersonation is always detected. We discuss real-world impersonation use cases, analyze the privacy limits, and compare our scheme to existing solutions.

Tarik Moataz, Nora Cuppens-Boulahia, Frédéric Cuppens, Indrajit Ray, Indrakshi Ray

Dynamic Workflow Adjustment with Security Constraints

Abstract

Dynamic workflow adjustment studies how to minimally adjust existing user-task assignments, when a sudden change occurs, e.g. absence of users, so that all tasks are being attended and no constraint is violated.In particular, we study two key questions: (i) Will the workflow still be satisfiable given a change? (ii) If the answer is yes, how to find a satisfying assignment with the minimum perturbation to the old system? We consider various types of changes, including absence of a user, addition of a separation-of-duty constraint, addition of a binding-of-duty constraint, and revocation of a user-to-task authorization, study their theoretical properties and formulate them into the well-studied Boolean satisfiability problem, which enables a system engineer without much technical background to solve problems by using standard satisfiability solvers. A step further, towards more efficient solutions for our specific problems, we propose customized algorithms by adapting and tailoring the state-of-art algorithms inside standard solvers. Our work would have implications for business process management, staffing, and cost planning.

Haibing Lu, Yuan Hong, Yanjiang Yang, Yi Fang, Lian Duan

Consistent Query Plan Generation in Secure Cooperative Data Access

Abstract

In this paper, we consider restricted data sharing between a set of parties that wish to provide some set of online services requiring such data sharing. We assume that each party stores its data in private relational databases, and is given a set of mutually agreed set of authorization rules that may involve joins over relations owned by one or more parties. Although the query planning problem in such an environment is similar to the one for distributed databases, the access restrictions introduce significant additional complexity that we address in this paper. We examine the problem of efficiently enforcing rules and generating query execution plans in this environment. Because of the exponential complexity of optimal query planning, our query planning algorithm is heuristics based but produces excellent, if not optimal, results in most of the practical cases.

Meixing Le, Krishna Kant, Sushil Jajodia

Hunting the Unknown

White-Box Database Leakage Detection

Abstract

Data leakage causes significant losses and privacy breaches worldwide. In this paper we present a white-box data leakage detection system to spot anomalies in database transactions. We argue that our approach represents a major leap forward w.r.t. previous work because: i) it significantly decreases the False Positive Rate (FPR) while keeping the Detection Rate (DR) high; on our experimental dataset, consisting of millions of real enterprise transactions, we measure a FPR that is orders of magnitude lower than in state-of-the-art comparable approaches; and ii) the white-box approach allows the creation of self-explanatory and easy to update profiles able to explain why a given query is anomalous, which further boosts the practical applicability of the system.

Elisa Costante, Jerry den Hartog, Milan Petković, Sandro Etalle, Mykola Pechenizkiy

Incremental Analysis of Evolving Administrative Role Based Access Control Policies

Abstract

We consider the safety problem for Administrative Role-Based Access Control (ARBAC) policies, i.e. detecting whether sequences of administrative actions can result in policies by which a user can acquire permissions that may compromise some security goals. In particular, we are interested in sequences of safety problems generated by modifications (namely, adding/deleting an element to/from the set of possible actions) to an ARBAC policy accommodating the evolving needs of an organization. or resulting from fixing some safety issues. Since problems in such sequences share almost all administrative actions, we propose an incremental technique that avoids the re-computation of the solution to the current problem by re-using much of the work done on the previous problem in a sequence. An experimental evaluation shows the better performances of an implementation of our technique with respect to the only available approach to solve safety problems for evolving ARBAC policies proposed by Gofman, Luo, and Yang.

Silvio Ranise, Anh Truong

Mining Attribute-Based Access Control Policies from Logs

Abstract

Attribute-based access control (ABAC) provides a high level of flexibility that promotes security and information sharing. ABAC policy mining algorithms have potential to significantly reduce the cost of migration to ABAC, by partially automating the development of an ABAC policy from information about the existing access-control policy and attribute data. This paper presents an algorithm for mining ABAC policies from operation logs and attribute data. To the best of our knowledge, it is the first algorithm for this problem.

Zhongyuan Xu, Scott D. Stoller

Attribute-Aware Relationship-Based Access Control for Online Social Networks

Abstract

Relationship-based access control (ReBAC) has been adopted as themost prominent approach for access control in online social networks (OSNs), where authorization policies are typically specified in terms of relationships of certain types and/or depth between the access requester and the target. However, using relationships alone is often not sufficient to enforce various security and privacy requirements that meet the expectation fromtoday’sOSN users. In thiswork, we integrate attribute-based policies into relationship-based access control. The proposed attribute-aware Re- BAC enhances access control capability and allows finer-grained controls that are not available in ReBAC. The policy specification language for the user-to-user relationship-based access control (UURAC) model proposed in [6] is extended to enable such attribute-aware access control. We also present an enhanced path-checking algorithm to determine the existence of the required attributes and relationships in order to grant access.

Yuan Cheng, Jaehong Park, Ravi Sandhu

Randomly Partitioned Encryption for Cloud Databases

Abstract

With the current advances in Cloud Computing, outsourcing data has never been so tempting. Along with outsourcing a database comes the privacy versus performance discussion. Order-Preserving Encryption (OPE) is one of the most attractive techniques for database encryption since it allows to execute range and rank queries efficiently without decrypting the data. On the other hand, people are reluctant to use OPE-based techniques in practice because of their vulnerability against adversaries with knowledge of the domain, its frequency distribution and query logs. This paper formally defines three real world driven attacks, called Domain Attack, Frequency Attack and Query Log Attack, typically launched by an honest-but-curious database or systems administrator. We also introduce measures to capture the probability distribution of the adversary’s advantage under each attacker model. Most importantly, we present a novel technique called Randomly Partitioned Encryption (RPE) to minimize the adversary’s advantage. Finally, we show that RPE not only withstands real world database adversaries, but also shows good performance that is close to state-of-art OPE schemes for both, read- and write-intensive workloads.

Tahmineh Sanamrad, Lucas Braun, Donald Kossmann, Ramarathnam Venkatesan

Towards Secure Cloud Database with Fine-Grained Access Control

Abstract

Outsourcing data to cloud environments can offer ease of access, provisioning, and cost benefits, but makes the data more vulnerable to disclosure. Loss of complete control over the data can be offset through encryption, but this approach requires an omniscient third party key authority to handle key management, increasing overhead complexity. We present the ZeroVis framework that provides confidentiality for data stored in a cloud environment without requiring a third party key manager. It combines fine-grained access control with the ability to search over encrypted data to allow existing applications to migrate to cloud environments with very minimal software changes, while maintaining data provider control over who can consume that data.

Michael G. Solomon, Vaidy Sunderam, Li Xiong

Practical Private Information Retrieval from a Time-Varying, Multi-attribute, and Multiple-Occurrence Database

Abstract

We study the problem of privately performing database queries (i.e., keyword searches and conjunctions over them), where a server provides its own database for client query-based access. We propose a cryptographic model for the study of such protocols,by expanding previous well-studied models of keyword search and private information retrieval to incorporate a more practical data model: a time-varying, multi-attribute and multiple-occurrence database table.

Our first result is a 2-party private database retrieval protocol. Like all previous work in private information retrieval and keyword search, this protocol still satisfies server time complexity linear in the database size.

Our main result is a private database retrieval protocol in a 3-party model where encrypted data is outsourced to a third party (i.e., a cloud server), satisfying highly desirable privacy and efficiency properties; most notably: (1) no unintended information is leaked to clients or servers, and only minimal ‘access pattern’ information is leaked to the third party; (2) for each query, all parties run in time only logarithmic in the number of database records; (3) the protocol’s runtime is practical for real-life applications, as shown in our implementation where we achieve response time that is only a small constant slower than commercial non-private protocols like MySQL.

Giovanni Di Crescenzo, Debra Cook, Allen McIntosh, Euthimios Panagos

LPM: Layered Policy Management for Software-Defined Networks

Abstract

Software-Defined Networking (SDN) as an emerging paradigm in networking divides the network architecture into three distinct layers such as application, control, and data layers. The multi-layered network architecture in SDN tremendously helps manage and control network traffic flows but each layer heavily relies on complex network policies. Managing and enforcing these network policies require dedicated cautions since combining multiple network modules in an SDN application not only becomes a non-trivial job, but also requires considerable efforts to identify dependencies within a module and between modules. In addition, multi-tenant SDN applications make network management tasks more difficult since there may exist unexpected interferences between traffic flows. In order to accommodate such complex network dynamics in SDN, we propose a novel policy management framework for SDN, called layered policy management (LPM). We also articulate challenges for each layer in terms of policy management and describe appropriate resolution strategies. In addition, we present a proof-of-concept implementation and demonstrate the feasibility of our approach with an SDN-based simulated network.

Wonkyu Han, Hongxin Hu, Gail-Joon Ahn

On Minimizing the Size of Encrypted Databases

Abstract

Motivated by applications to maintaining confidentiality and efficiency of encrypted data access in cloud computing, we uncovered an inherent confidentiality weakness in databases outsourced to cloud servers, even when encrypted. To address this weakness, we formulated a new privacy notion for outsourced databases and (variants of) a classical record length optimization problem, whose solutions achieve the new privacy notion. Our algorithmic investigation resulted in a number of exact and approximate algorithms,for arbitrary input distributions, and in the presence of record additions and deletions. Previous work only analyzed an unconstrained variant of our optimization problem for specific input distributions, with no attention to running time or database updates.

Giovanni Di Crescenzo, David Shallcross

Efficient and Enhanced Solutions for Content Sharing in DRM Systems

Abstract

We present a solution to the problem of content sharing in digital rights management (DRM) systems. Users in DRM systems purchase content from content providers and then wish to distribute it between their own devices or to other users. The goal is to allow the sharing of such content, with the control of the content provider, while ensuring that it complies with the content’s usage rules. While most of the previous studies on content sharing in DRM systems assume the existence of authorized domains, ours does not make that assumption. The solutions that we present here are based on Certified Sharing Requests which are used when devices request from the content provider authorization to share content with other devices. Our solutions enhance the usability of DRM, from both the users’ and content provider’s perspective, by supporting on-the-fly sharing, sharing and re-sharing of controlled content, and a pay-per-share business model.

Michal Davidson, Ehud Gudes, Tamir Tassa

A Scalable and Efficient Privacy Preserving Global Itemset Support Approximation Using Bloom Filters

Abstract

Several secure distributed data mining methods have been proposed in the literature that are based on privacy preserving set operation mechanisms. However, they are limited in the scalability of both the size and the number of data owners (sources). Most of these techniques are primarily designed to work with two data owners and extensions to handle multiple owners are either expensive or infeasible. In addition, for large datasets, they incur substantial communication/computation overhead due to the use of cryptographic techniques. In this paper, we propose a scalable privacy-preserving protocol that approximates global itemset support, without employing any cryptographic mechanism. We also present some emperical results to demonstrate the effectiveness of our approach.

Vikas G. Ashok, Ravi Mukkamala

Backmatter