Learning from graph-structured data is fundamental to many Web applications, such as recommendation systems and social network analysis. While neural networks achieve state-of-the-art performance in these tasks, training them on sensitive graph data poses privacy risks. Node-level differential privacy (node-DP) provides strong protection for individual users represented as nodes; however, achieving node-DP is challenging due to the intricate dependencies among interconnected nodes. These dependencies, in turn, complicate node-level sensitivity analysis, which is a key step in differentially private learning. To bound the sensitivity, existing approaches typically (i) rely on black-box per-sample gradient clipping, which often overestimates sensitivity and introduces an excessive amount of DP noise; and (ii) prune edges from nodes with high degrees, which leads to erroneous privacy proofs.

The prosperity of Ethereum gives rise to a new type of transaction-based phishing scam. Specifically, users are tempted to visit phishing websites and sign phishing transactions that allow scammers to withdraw their tokens. Meanwhile, to accelerate the deployment of phishing websites, scammers have introduced a business model, Drainer-as-a-Service (DaaS). In this model, drainer operators focus on crafting specialized phishing toolkits, named ''wallet drainers'', while drainer affiliates handle the deployment and promotion of phishing websites. After stealing victims' tokens, they will distribute profits. In this paper, we present the first systematic study of DaaS on Ethereum. To begin with, we propose a snowball sampling approach to build the first large-scale DaaS dataset, including 1,910 profit sharing contracts, 56 operator accounts, 6,087 affiliate accounts, and 87,077 profit-sharing transactions. Then, we analyze the scale of DaaS from the perspectives of victims, operators, and affiliates, and perform clustering analysis to uncover dominant DaaS families. Finally, we reported DaaS accounts in the dataset and 32,819 phishing websites deployed with DaaS toolkits to the community. Our work aims to serve as a guide for Ethereum service providers to enhance user protection against DaaS.

Sharing methods of attack and their effectiveness is a cornerstone of building robust defensive systems. Threat analysis reports, produced by various individuals and organizations, play a critical role in supporting security operations and combating emerging threats. To enhance the timeliness and automation of threat intelligence sharing, several standards have been established, with the Structured Threat Information Expression (STIX) framework emerging as one of the most widely adopted. However, generating STIX-compatible data from unstructured security text remains a largely manual, expertdriven process. To address this challenge, we introduce AZERG, a tool designed to assist security analysts in automatically generating structured STIX representations. To achieve this, we adapt general-purpose large language models for the specific task of extracting STIX-formatted threat data. To manage the complexity, the task is divided into four subtasks: entity detection (T1), entity type identification (T2), related pair detection (T3), and relationship type identification (T4). We apply task-specific fine-tuning to accurately extract relevant entities and infer their relationships in accordance with the STIX specification. To address the lack of training data, we compiled a comprehensive dataset with 4,011 entities and 2,075 relationships extracted from 141 full threat analysis reports, all annotated in alignment with the STIX standard. Our models achieved F1-scores of 84.43% for T1, 88.49% for T2, 95.47% for T3, and 84.60% for T4 in real-world scenarios. We validated their performance against a range of open- and closed-parameter models, as well as state-of-the-art methods, demonstrating improvements of 2–25% across tasks.

Internet miscreants increasingly utilize short-lived disposable domains to launch various attacks. Existing detection mechanisms are either too late to catch such malicious domains due to limited information and their short life spans or unable to catch them due to evasive techniques such as cloaking and captcha. In this work, we investigate the possibility of detecting malicious domains early in their life cycle using a content-agnostic approach. We observe that attackers often reuse or rotate hosting infrastructures to host multiple malicious domains due to increased utilization of automation and economies of scale. Thus, it gives defenders the opportunity to monitor such infrastructure to identify newly hosted malicious domains. However, such infrastructures are often shared hosting environments where benign domains are also hosted, which could result in a prohibitive number of false positives. Therefore, one needs innovative mechanisms to better distinguish malicious domains from benign ones even when they share hosting infrastructures. In this work, we build MANTIS, a highly accurate practical system that not only generates daily blocklists of malicious domains but also is able to predict malicious domains on-demand. We design a network graph based on the hosting infrastructure that is accurate and generalizable over time. Consistently, our models achieve a precision of 99.7%, a recall of 86.9% with a very low false positive rate (FPR) of 0.1 % and on average detects 19K new malicious domains per day, which is over 5 times the new malicious domains flagged daily in VirusTotal. Further, MANTIS predicts malicious domains days to weeks before they appear in popular blocklists.

Analyzing common neighbors between node pairs in social networks provides valuable insights into the graph structure and enables a range of network analytics tasks. In this paper, we investigate techniques to publish the histogram of common neighbor counts between all node pairs in a social network under edge-differential privacy. This problem is particularly challenging, since the histogram of common neighbor counts has a high sensitivity of O(n), where n is the number of nodes in a social network. If we inject noise into the histogram in proportion to this sensitivity to achieve edge differential privacy, then the noise would overwhelm the signals of the histogram, since each node pair can have at most n - 2 common neighbors. Existing techniques address this issue by converting the histogram publication problem to an integer partition problem that has sensitivity of O(1), but these techniques tend to yield unsatisfactory data utility as they fail to take into account the characteristics of real social networks.

We propose to identify compromised mobile devices from a network administrator’s point of view. Intuitively, inadvertent users (and thus their devices) who download apps through untrustworthy markets are often lured to install malicious apps through in-app advertisements or phishing. We thus hypothesize that devices sharing similar apps would have a similar likelihood of being compromised, resulting in an association between a compromised device and its apps. We propose to leverage such associations to identify unknown compromised devices using the guilt-by-association principle. Admittedly, such associations could be relatively weak as it is hard, if not impossible, for an app to automatically download and install other apps without explicit user initiation. We describe how we can magnify such associations by carefully choosing parameters when applying graph-based inferences. We empirically evaluate the effectiveness of our approach on real datasets provided by a major mobile service provider. Specifically, we show that our approach achieves nearly 98% AUC (area under the ROC curve) and further detects as many as 6 ~ 7 times of new compromised devices not covered by the ground truth by expanding the limited knowledge on known devices. We show that the newly detected devices indeed present undesirable behavior in terms of leaking private information and accessing risky IPs and domains. We further conduct in-depth analysis of the effectiveness of graph inferences to understand the unique structure of the associations between mobile devices and their apps, and its impact on graph inferences, based on which we propose how to choose key parameters.

Previous security research efforts orbiting around graphs have been exclusively focusing on either (de-)anonymizing the graphs or understanding the security and privacy issues of graph neural networks. Little attention has been paid to understand the privacy risks of integrating the output from graph embedding models (e.g., node embeddings) with complex downstream machine learning pipelines. In this paper, we fill this gap and propose a novel model-agnostic graph recovery attack that exploits the implicit graph structural information preserved in the embeddings of graph nodes. We show that an adversary can recover edges with decent accuracy by only gaining access to the node embedding matrix of the original graph without interactions with the node embedding models. We demonstrate the effectiveness and applicability of our graph recovery attack through extensive experiments.

High-quality intelligence of Internet threat (e.g., malware files, malicious domains, phishing URLs and malicious IPs) are important for both security practitioners and the research community. Given the agility of attackers, the scale of the Internet, and the fast-evolving landscape of threats, one could not rely solely on a single source (such as an anti-malware engine or an IP blacklist) for obtaining accurate, up-to-date, and comprehensive threat analysis. Instead, we need to aggregate the analysis from multiple sources. However, it is non-trivial to do such aggregation effectively. A common practice is to label an indicator (malware, domains, URLs, etc.) as malicious if it is marked by a number of sources above an ad-hoc certain threshold. Often, this results in sub-optimal performance as it assumes that all sources are of similar quality/expertise, independent, and temporally stable, which unfortunately are often not true in practice. A natural alternative is to train a supervised machine learning model. However, this approach needs a sufficiently large amount of manually labeled ground truth, which is time-consuming to collect and has to be updated frequently, resulting in substantial recurring costs. In this paper, we propose SIRAJ, a novel framework for aggregating the detection output of various intelligence sources such as anti-malware engines. SIRAJ is based on the pretrain and fine-tune paradigm. Specifically, we use self-supervised learning-based approaches to learn a pre-trained embedding model that converts multi-source inputs into a high-dimensional embedding. The embeddings are learned through three carefully designed pretext tasks that imbue them with knowledge about dependencies between scanners and their temporal dynamics. The learned embeddings could be used for diverse downstream machine learning tasks. SIRAJ is designed to be general and can be used for diverse domains such as URLs, malware, and IPs. Further, SIRAJ works well even when there is limited to no labeled data available. Through extensive experiments, we show that our learned representations can produce results comparable to supervised methods while only requiring as little as 100 labeled samples. Importantly, the results show that SIRAJ accurately detects threat indicators much earlier than the baseline algorithms, a feat that is critical against short-lived indicators like Phishing URLs.

Ever since the beginning of the outbreak of the COVID-19 pandemic, attackers acted quickly to exploit the confusion, uncertainty and anxiety caused by the pandemic and launched various attacks through COVID-19 themed malicious domains. Malicious domains are rarely deployed independently, but rather almost always belong to much bigger and coordinated attack campaigns. Thus, analyzing COVID-themed malicious domains from the angle of attack campaigns would help us gain a deeper understanding of the scale, scope and sophistication of the threats imposed by such malicious domains. In this paper, we collect data from multiple sources, and identify and characterize COVID-themed malicious domain campaigns, including the evolution of such campaigns, their underlying infrastructures and the different strategies taken by attackers behind these campaigns. Our exploration suggests that some malicious domains have strong correlations, which can guide us to identify new malicious domains and raise alarms at the early stage of their deployment. The results shed light on the emergency for detecting and mitigating public event related cyber attacks.

Autoencoder-based anomaly detection methods have been used in identifying anomalous users from large-scale enterprise logs with the assumption that adversarial activities do not follow past habitual patterns. Most existing approaches typically build models by reconstructing single-day and individual-user behaviors. However, without capturing long-term signals and group-correlation signals, the models cannot identify low-signal yet long-lasting threats, and will wrongly report many normal users as anomalies on busy days, which, in turn, lead to high false positive rate. In this paper, we propose ACOBE, an Anomaly detection method based on COmpound BEhavior, which takes into consideration long-term patterns and group behaviors. ACOBE leverages a novel behavior representation and an ensemble of deep autoencoders and produces an ordered investigation list. Our evaluation shows that ACOBE outperforms prior work by a large margin in terms of precision and recall, and our case study demonstrates that ACOBE is applicable in practice for cyberattack detection.

End-to-end email encryption (E2EE) ensures that an email could only be decrypted and read by its intended recipients. E2EE’s strong security guarantee is particularly desirable for the enterprises in the event of breaches: even if attackers break into an email server, under E2EE no contents of emails are leaked. Meanwhile, E2EE brings significant challenges for an enterprise to detect and filter unwanted emails (spams and phishing emails). Most existing solutions rely heavily on email contents (i.e., email body and attachments), which would be difficult when email contents are encrypted. In this paper, we investigate how to detect unwanted emails in a content-agnostic manner, that is, without access to the contents of emails at all.

The proliferation of mobile devices along with their rich functionalities/applications have made people form addictive and potentially harmful usage behaviors. Though this problem has drawn considerable attention, existing solutions (e.g., text notification or setting usage limits) are insufficient and cannot provide timely recommendations or control of inappropriate usage of mobile devices. This paper proposes a generalized context inference framework, which supports timely usage recommendations using low-power sensors in mobile devices Comparing to existing schemes that rely on detection of single type user contexts (e.g., merely on location or activity), our framework derives a much larger-scale of user contexts that characterize the phone usages, especially those causing distraction or leading to dangerous situations. We propose to uniformly describe the general user context with context fundamentals, i.e., physical environments, social situations, and human motions, which are the underlying constituent units of diverse general user contexts. To mitigate the profiling efforts across different environments, devices, and individuals, we develop a deep learning-based architecture to learn transferable representations derived from sensor readings associated with the context fundamentals. Based on the derived context fundamentals, our framework quantifies how likely an inferred user context would lead to distractions/dangerous situations, and provides timely recommendations for mobile device access/usage. Extensive experiments during a period of 7 months demonstrate that the system can achieve 95% accuracy on user context inference while offering the transferability among different environments, devices, and users.

Malicious domains, including phishing websites, spam servers, and command and control servers, are the reason for many of the cyber attacks nowadays. Thus, detecting them in a timely manner is important to not only identify cyber attacks but also take preventive measures. There has been a plethora of techniques proposed to detect malicious domains by analyzing Domain Name System (DNS) traffic data. Traditionally, DNS acts as an Internet miscreant’s best friend, but we observe that the subtle traces in DNS logs left by such miscreants can be used against them to detect malicious domains. Our approach is to build a set of domain graphs by connecting “related” domains together and injecting known malicious and benign domains into these graphs so that we can make inferences about the other domains in the domain graphs. A key challenge in building these graphs is how to accurately identify related domains so that incorrect associations are minimized and the number of domains connected from the dataset is maximized. Based on our observations, we first train two classifiers and then devise a set of association rules that assist in linking domains together. We perform an in-depth empirical analysis of the graphs built using these association rules on passive DNS data and show that our techniques can detect many more malicious domains than the state-of-the-art.

Many real-world social networks are decentralized in nature, and the only way to analyze such a network is to collect local views of the social graph from individual participants. Since local views may contain sensitive information, it is often desirable to apply differential privacy in the data collection process, which provides strong and rigorous privacy guarantees. In many practical situations, the local view of a participant contains not only her own connections, but also those of her neighbors, which are private and sensitive for the neighbors, but not directly so for the participant herself. We call such information beyond direct connections an extended local view (ELV)</>, and study two fundamental problems related to ELVs: first, how do we correctly enforce differential privacy for all participants in the presence of ELVs? Second, how can the data collector utilize ELVs to obtain accurate estimates of global graph properties?

Crowdsourcing is a new problem-solving paradigm for tasks that are difficult for computers but easy for humans. Since the answers collected from the recruited participants (workers) may contain sensitive information, crowdsourcing raises serious privacy concerns. In this paper, we investigate the problem of protecting user privacy under local differential privacy (LDP), where individual workers randomize their answers independently and send the perturbed answers to the task requester. The utility goal is to ensure high accuracy of the inferred true answers (i.e., truth) from the perturbed data. One of the challenges of LDP perturbation is the sparsity of worker answers (i.e., each worker only answers a small number of tasks). Simple extension of existing approaches (e.g., Laplace perturbation and randomized response) may incur large errors in truth inference on sparse data. Thus we design a new matrix factorization (MF) algorithm under LDP that addresses the trade-off between privacy and utility (i.e., accuracy of truth inference). We prove that our MF algorithm can provide both LDP guarantee and small error of truth inference, regardless of the sparsity of worker answers. We perform extensive experiments on real-world and synthetic datasets and demonstrate that the MF algorithm performs better than the existing LDP algorithms on sparse crowdsourcing data.

Inference based techniques are one of the major approaches to analyze DNS data and detect malicious domains. The key idea of inference techniques is to first define associations between domains based on features extracted from DNS data. Then, an inference algorithm is deployed to infer potential malicious domains based on their direct/indirect associations with known malicious ones. The way associations are defined is key to the effectiveness of an inference technique. It is desirable to be both accurate (i.e., avoid falsely associating domains with no meaningful connections) and with good coverage (i.e., identify all associations between domains with meaningful connections). Due to the limited scope of information provided by DNS data, it becomes a challenge to design an association scheme that achieves both high accuracy and good coverage.

Given a set of multi-dimensional points, a k-skyband query retrieves those points dominated by no more than k other points. k-skyband queries are an important type of multi-criteria analysis with diverse applications in practice. In this paper, we investigate techniques to answer k-skyband queries with differential privacy. We first propose a general technique BBS-Priv , which accepts any differentially private spatial decomposition tree as input and leverages data synthesis to answer k-skyband queries privately. We then show that, though quite a few private spatial decomposition trees are proposed in the literature, they are mainly designed to answer spatial range queries. Directly integrating them with BBS-Priv would introduce too much noise to generate useful k-skyband results. To address this problem, we propose a novel spatial decomposition technique k-skyband tree specially optimized for k-skyband queries, which partitions data adaptively based on the parameter k and performs finer partitions on the regions that are likely to contain k-skyband results. We further propose techniques to generate a k-skyband tree over spatial data that satisfies differential privacy, and combine BBS-Priv with the private k-skyband tree to answer k-skyband queries. We conduct extensive experiments based on two real-world datasets and three synthetic datasets that are commonly used for evaluating k-skyband queries. The results show that the proposed scheme significantly outperforms existing differentially private spatial decomposition schemes and achieves high utility when privacy budgets are properly allocated.

A large amount of valuable information resides in decentralized social graphs, where no entity has access to the complete graph structure. Instead, each user maintains locally a limited view of the graph. For example, in a phone network, each user keeps a contact list locally in her phone, and does not have access to other users' contacts. The contact lists of all users form an implicit social graph that could be very useful to study the interaction patterns among different populations. However, due to privacy concerns, one could not simply collect the unfettered local views from users and reconstruct a decentralized social network.

In this paper we investigate on detecting opinion spammer groups through analyzing how users interact with each other. More specifically, our approaches are based on 1) discovering strong vs. weak implicit communities by mining user interaction patterns, and 2) revealing positive vs. negative communities through sentiment analysis on user interactions. Through extensive experiments over various datasets collected from Amazon, we found that the discovered strong, positive communities are significantly more likely to be opinion spammer groups than other communities. Interestingly, while our approach focused mainly on the characteristics of user interactions, it is comparable to the state of the art content-based classifier that mainly uses various content-based features extracted from user reviews. More importantly, we argue that our approach can be more robust than the latter in that if spammers superficially alter their review contents, our approach can still reliably identify them while the content-based approaches may fail.

Malicious domains are key components to a variety of cyber attacks. Several recent techniques are proposed to identify malicious domains through analysis of DNS data. The general approach is to build classifiers based on DNS-related local domain features. One potential problem is that many local features, e.g., domain name patterns and temporal patterns, tend to be not robust. Attackers could easily alter these features to evade detection without affecting much their attack capabilities. In this paper, we take a complementary approach. Instead of focusing on local features, we propose to discover and analyze global associations among domains. The key challenges are (1) to build meaningful associations among domains; and (2) to use these associations to reason about the potential maliciousness of domains. For the first challenge, we take advantage of the modus operandi of attackers. To avoid detection, malicious domains exhibit dynamic behavior by, for example, frequently changing the malicious domain-IP resolutions and creating new domains. This makes it very likely for attackers to reuse resources. It is indeed commonly observed that over a period of time multiple malicious domains are hosted on the same IPs and multiple IPs host the same malicious domains, which creates intrinsic association among them. For the second challenge, we develop a graph-based inference technique over associated domains. Our approach is based on the intuition that a domain having strong associations with known malicious domains is likely to be malicious. Carefully established associations enable the discovery of a large set of new malicious domains using a very small set of previously known malicious ones. Our experiments over a public passive DNS database show that the proposed technique can achieve high true positive rates (over 95%) while maintaining low false positive rates (less than 0.5%). Further, even with a small set of known malicious domains (a couple of hundreds), our technique can discover a large set of potential malicious domains (in the scale of up to tens of thousands).

In local differential privacy (LDP), each user perturbs her data locally before sending the noisy data to a data collector. The latter then analyzes the data to obtain useful statistics. Unlike the setting of centralized differential privacy, in LDP the data collector never gains access to the exact values of sensitive data, which protects not only the privacy of data contributors but also the collector itself against the risk of potential data leakage. Existing LDP solutions in the literature are mostly limited to the case that each user possesses a tuple of numeric or categorical values, and the data collector computes basic statistics such as counts or mean values. To the best of our knowledge, no existing work tackles more complex data mining tasks such as heavy hitter discovery over set-valued data. In this paper, we present a systematic study of heavy hitter mining under LDP. We first review existing solutions, extend them to the heavy hitter estimation, and explain why their effectiveness is limited. We then propose LDPMiner, a two-phase mechanism for obtaining accurate heavy hitters with LDP. The main idea is to first gather a candidate set of heavy hitters using a portion of the privacy budget, and focus the remaining budget on refining the candidate set in a second phase, which is much more efficient budget-wise than obtaining the heavy hitters directly from the whole dataset. We provide both in-depth theoretical analysis and extensive experiments to compare LDPMiner against adaptations of previous solutions. The results show that LDPMiner significantly improves over existing methods. More importantly, LDPMiner successfully identifies the majority true heavy hitters in practical settings.

Outsource encrypted data is a popular trend for storing sensitive data in third party clouds. Many cloud applications need privacy preserving data encryption services with two capabilities: On one hand, they need querying over encrypted data in Web based data hosting services. On the other hand, they also need to keep the query keywords and associated search operations private such that data hosting service providers cannot gain access to unauthorized content or trace and infer sensitive data stored in the third party data hosting servers. In this paper we present a novel service oriented framework for verifiable searchable asymmetric encryption, called PVSAE. PVSAE offers strong support for outsourced encrypted data with two formal security properties in terms of IND-CKA security and search pattern privacy. Our framework supports two concrete PVSAE schemes. The first scheme l-PVSAE is based on the l-dimensional vectors and achieves strong security notions, namely statistical IND-CKA security and statistical search pattern privacy. The second scheme 3-PVSAE is a light-weight version based on 3-dimensional vectors. 3-PVSAE maintains the strong security properties and offers higher efficiency for search over encrypted data compared with existing verifiable searchable asymmetric encryption schemes. We experimentally evaluate the proposed PVSAE schemes and show that they not only offer strong security but also are practical and deployable.

Many data analysis tasks rely on the abstraction of a graph to represent relations between entities, with attributes on the nodes and edges. Since the relationships encoded are often sensitive, we seek effective ways to release representative graphs which nevertheless protect the privacy of the data subjects. Prior work on this topic has focused primarily on the graph structure in isolation, and has not provided ways to handle richer graphs with correlated attributes.

Nowadays, cloud has become a promising multimedia data processing and sharing platform. Many institutes and companies plan to outsource and share their large-scale video and image datasets on cloud for scientific research and public interest. Among various video applications, the discovery of frequent visual patterns over graphical data is an exploratory and important technique. However, the privacy concerns over the leakage of sensitive information contained in the videos/images impedes the further implementation. Although the frequent visual patterns mining (FVPM) algorithm aggregates summary over individual frames and seems not to pose privacy threat, the private information contained in individual frames still may be leaked from the statistical result. In this paper, we study the problem of privacy-preserving publishing of graphical data FVPM on cloud. We propose the first differentially private frequent visual patterns mining algorithm for graphical data, named DPcode. We propose a novel mechanism that integrates the privacy-preserving visual word conversion with the differentially private mechanism under the noise allocation strategy of the sparse vector technique. The optimized algorithms properly allocate the privacy budgets among different phases in FPM algorithm over images and reduce the corresponding data distortion. Extensive experiments are conducted based on datasets commonly used in visual mining algorithms. The results show that our approach achieves high utility while satisfying a practical privacy requirement.

Querying over encrypted data is gaining increasing popularity in cloud-based data hosting services. Security and efficiency are recognized as two important and yet conflicting requirements for querying over encrypted data. In this article, we propose an efficient private keyword search (EPKS) scheme that supports binary search and extend it to dynamic settings (called DEPKS ) for inverted index--based encrypted data. First, we describe our approaches of constructing a searchable symmetric encryption (SSE) scheme that supports binary search. Second, we present a novel framework for EPKS and provide its formal security definitions in terms of plaintext privacy and predicate privacy by modifying Shen et al.’s security notions [Shen et al. 2009]. Third, built on the proposed framework, we design an EPKS scheme whose complexity is logarithmic in the number of keywords. The scheme is based on the groups of prime order and enjoys strong notions of security, namely statistical plaintext privacy and statistical predicate privacy. Fourth, we extend the EPKS scheme to support dynamic keyword and document updates. The extended scheme not only maintains the properties of logarithmic-time search efficiency and plaintext privacy and predicate privacy but also has fewer rounds of communications for updates compared to existing dynamic search encryption schemes. We experimentally evaluate the proposed EPKS and DEPKS schemes and show that they are significantly more efficient in terms of both keyword search complexity and communication complexity than existing randomized SSE schemes.

WaveCluster is an important family of grid-based clustering algorithms that are capable of finding clusters of arbitrary shapes. In this paper, we investigate techniques to perform WaveCluster while ensuring differential privacy.Our goal is to develop a general technique for achieving differential privacy on WaveCluster that accommodates different wavelet transforms.

Mobile platforms, such as Android, warn users about the permissions an app requests and trust that the user will make the correct decision about whether or not to install the app. Unfortunately many users either ignore the warning or fail to understand the permissions and the risks they imply. As a step toward developing an indicator of risk that decomposes risk into several categories, or dimensions, we conducted two studies designed to assess the dimensions of risk deemed most important by experts and novices. In Study 1, semi-structured interviews were conducted with 19 security experts, who also performed a card sorting task in which they categorized permissions. The experts identified three major risk dimensions in the interviews (personal information privacy, monetary risk, and device availability/stability), and a forth dimension (data integrity) in the card sorting task. In Study 2, 350 typical Android users, recruited via Amazon Mechanical Turk, filled out a questionnaire in which they (a) answered questions concerning their mobile device usage, (b) rated how often they considered each of several types of information when installing apps, (c) indicated what they considered to be the biggest risk associated with installing an app on their mobile device, and (d) rated their concerns with regard to specific risk types and about apps having access to specific types of information. In general, the typical users' concerns were similar to those of the security experts. The results of the studies suggest that risk information should be organized into several risk types that can be better understood by users and that a mid-level risk summary should incorporate the dimensions of personal information privacy, monetary risk, device availability/stability risk and data integrity risk.

Differential privacy is widely accepted as a powerful framework for providing strong, formal privacy guarantees for aggregate data analysis. A limitation of the model is that the same level of privacy protection is afforded for all individuals. However, it is common that the data subjects have quite different expectations regarding the acceptable level of privacy for their data. Consequently, differential privacy may lead to insufficient privacy protection for some users, while over-protecting others. We argue that by accepting that not all users require the same level of privacy, a higher level of utility can often be attained by not providing excess privacy to those who do not want it. We propose a new privacy definition called personalized differential privacy (PDP), a generalization of differential privacy in which users specify a personal privacy requirement for their data. We then introduce several novel mechanisms for achieving PDP. Our primary mechanism is a general one that automatically converts any existing differentially private algorithm into one that satisfies PDP. We also present a more direct approach for achieving PDP, inspired by the well-known exponential mechanism. We demonstrate our framework through extensive experiments on real and synthetic data.

PASQL is an extension to SQL that allows users of a distributed database to specify privacy constraints on an SQL query evaluation plan. However, privacy constraints can be difficult for users to specify, and worse yet, all possible situations that could lead to a privacy violation may not be known to the user a priori. To address these challenges, we propose a GUI-based interactive process for detecting such violations and generating appropriate constraints. In this work, we demonstrate two approaches to implementing such a GUI that provide different ways of analyzing and interactively optimizing a PASQL query plan.

No abstract available.

Reputation is a primary mechanism for trust management in decentralized systems. Many reputation-based trust functions have been proposed in the literature. However, picking the right trust function for a given decentralized system is a non-trivial task. One has to consider and balance a variety of factors, including computation and communication costs, scalability and resilience to manipulations by attackers. Although the former two are relatively easy to evaluate, the evaluation of resilience of trust functions is challenging. Most existing work bases evaluation on static attack models, which is unrealistic as it fails to reflect the adaptive nature of adversaries (who are often real human users rather than simple computing agents).

We consider the problem of producing item recommenda-tions that are personalized based on a user’s social network, while simultaneously preventing the disclosure of sensitive user-item preferences (e.g., product purchases, ad clicks, web browsing history, etc.). Our main contribution is a privacy-preserving framework for a class of social recommendation algorithms that provides strong, formal privacy guarantees under the model of differential privacy. Existing mechanisms for achieving differential privacy lead to an unacceptable loss of utility when applied to the social recommendation prob-lem. To address this, the proposed framework incorporates a clustering procedure that groups users according to the natural community structure of the social network and sig-nificantly reduces the amount of noise required to satisfy differential privacy. Although this reduction in noise comes at the cost of some approximation error, we show that the benefits of the former significantly outweigh the latter. We explore the privacy-utility trade-off for several different in-stantiations of the proposed framework on two real-world data sets and show that useful social recommendations can be produced without sacrificing privacy. We also experimen-tally compare the proposed framework with several existing differential privacy mechanisms and show that the proposed framework significantly outperforms all of them in this set-ting. 1.

The declarative nature of SQL has traditionally been a major strength. Users simply state what information they are interested in, and the database management system determines the best plan for retrieving it. A consequence of this model is that should a user ever want to specify some aspect of how their queries are evaluated (e.g., a preference to read data from a specific replica, or a requirement for all joins to be performed by a single server), they are unable to. This can leave database administrators shoehorning evaluation preferences into database cost models. Further, for distributed database users, it can result in query evaluation plans that violate data handling best practices or the privacy of the user. To address such issues, we have developed a framework for declarative, user-specified constraints on the query optimization process and implemented it within PosgreSQL. Our Preference-Aware Query Optimizer (PAQO) upholds both strict requirements and partially ordered preferences that are issued alongside of the queries that it processes. In this paper, we present the design of PAQO and thoroughly evaluate its performance.

Social connections often have a significant influence on personal decision making. Researchers have proposed novel recommender systems that take advantage of social relationship information to improve recommendations. These systems, while promising, are often hindered in practice. Existing social networks such as Facebook are not designed for recommendations and thus contain many irrelevant relationships. Many recommendation platforms such as Amazon often do not permit users to establish explicit social relationships. And direct integration of social and commercial systems raises privacy concerns.

Software-as-a-service (SaaS) cloud systems enable application service providers to deliver their applications via massive cloud computing infrastructures. However, due to their sharing nature, SaaS clouds are vulnerable to malicious attacks. In this paper, we present IntTest, a scalable and effective service integrity attestation framework for SaaS clouds. IntTest provides a novel integrated attestation graph analysis scheme that can provide stronger attacker pinpointing power than previous schemes. Moreover, IntTest can automatically enhance result quality by replacing bad results produced by malicious attackers with good results produced by benign service providers. We have implemented a prototype of the IntTest system and tested it on a production cloud computing infrastructure using IBM System S stream processing applications. Our experimental results show that IntTest can achieve higher attacker pinpointing accuracy than existing approaches. IntTest does not require any special hardware or secure kernel support and imposes little performance impact to the application, which makes it practical for large-scale cloud systems.

There is currently a tug-of-war going on surrounding data releases. On one side, there are many strong reasons pulling to release data to other parties: business factors, freedom of information rules, and scientific sharing agreements. On the other side, concerns about individual privacy pull back, and seek to limit releases. Privacy technologies such as differential privacy have been proposed to resolve this deadlock, and there has been much study of how to perform private data release of data in various forms. The focus of such works has been largely on the data owner: what process should they apply to ensure that the released data preserves privacy whilst still capturing the input data distribution accurately. Almost no attention has been paid to the needs of the data user, who wants to make use of the released data within their existing suite of tools and data. The difficulty of making use of data releases is a major stumbling block for the widespread adoption of data privacy technologies.

BigTable is a distributed storage system that is designed to manage large-scale structured data. Deploying BigTable in a public cloud is an economic storage solution to small businesses and researchers who need to deal with data processing tasks over large amount of data but often lack capabilities to obtain their own powerful clusters. As one may not always trust the public cloud provider, one important security issue is to ensure the integrity of data managed by BigTable running at the cloud. In this paper, we present iBigTable, an enhancement of BigTable that provides scalable data integrity assurance. We explore the practicality of different authenticated data structure designs for BigTable, and design a set of security protocols to efficiently and flexibly verify the integrity of data returned by BigTable. More importantly, iBigtable preserves the simplicity, applicability and scalability of BigTable, so that existing applications over BigTable can interact with iBigTable seamlessly with minimum or no change of code (depending on the mode of iBigTable). We implement a prototype of iBigTable based on HBase, an open source BigTable implementation. Our experimental results show that iBigTable imposes reasonable performance overhead while providing integrity assurance.

Discovering frequent graph patterns in a graph database offers valuable information in a variety of applications. However, if the graph dataset contains sensitive data of individuals such as mobile phone-call graphs and web-click graphs, releasing discovered frequent patterns may present a threat to the privacy of individuals. Differential privacy has recently emerged as the de facto standard for private data analysis due to its provable privacy guarantee. In this paper we propose the first differentially private algorithm for mining frequent graph patterns.

Although the declarative nature of SQL provides great utility to database users, its use in distributed database management systems can result in unintended consequences to user privacy over the course of query evaluation. By allowing users to merely say what data they are interested in accessing without providing guidance regarding how to retrieve it, query optimizers can generate plans that leak sensitive query intension. To address these types of issues, we have created a framework that empowers users with the ability to specify access controls on the intension of their queries through extensions to the SQL SELECT statement. In this demonstration, we present a version of PostgreSQL's query optimizer that we have modified to produce plans that respect these constraints while optimizing user-specified SQL queries in terms of performance.

Although the declarative nature of SQL provides great utility to database users, its use in distributed database management systems can leave users unaware of which servers in the system are evaluating portions of their queries. By allowing users to merely say what data they are interested in accessing without providing guidance regarding how to retrieve it, query optimizers can generate plans with unintended consequences to the user (e.g., violating user privacy by revealing sensitive portions of a user's query to untrusted servers, or impacting result freshness by pulling data from stale data stores). To address these types of issues, we have created a framework that empowers users with the ability to specify constraints on the kinds of plans that can be produced by the optimizer to evaluate their queries. Such constraints are specified through an extended version of SQL that we have developed which we call PASQL. With this proposal, we aim to demonstrate PAQO, a version of PostgreSQL's query optimizer that we have modified to produce plans that respect constraints specified through PASQL while optimizing user-specified SQL queries in terms of performance.

Privacy is one of the major concerns when publishing or sharing social network data for social science research and business analysis. Recently, researchers have developed privacy models similar to k-anonymity to prevent node reidentification through structure information. However, even when these privacy models are enforced, an attacker may still be able to infer one's private information if a group of nodes largely share the same sensitive labels (i.e., attributes). In other words, the label-node relationship is not well protected by pure structure anonymization methods. Furthermore, existing approaches, which rely on edge editing or node clustering, may significantly alter key graph properties. In this paper, we define a k-degree-l-diversity anonymity model that considers the protection of structural information as well as sensitive labels of individuals. We further propose a novel anonymization methodology based on adding noise nodes. We develop a new algorithm by adding noise nodes into the original graph with the consideration of introducing the least distortion to graph properties. Most importantly, we provide a rigorous analysis of the theoretical bounds on the number of noise nodes added and their impacts on an important graph property. We conduct extensive experiments to evaluate the effectiveness of the proposed technique.

Reputation mechanisms represent a major class of techniques for managing trust in decentralized systems. Quite a few reputation-based trust functions have been proposed in the literature for use in many different application domains. However, in many situations, one cannot always obtain all of the information required by the trust evaluation process. For example, access control restrictions or high collection costs might limit one's ability to gather every possible feedback that could be aggregated. Thus, one key question is how to analytically quantify the quality of reputation scores computed using incomplete information.

Differential privacy has recently emerged as the de facto standard for private data release. This makes it possible to provide strong theoretical guarantees on the privacy and utility of released data. While it is well-understood how to release data based on counts and simple functions under this guarantee, it remains to provide general purpose techniques to release data that is useful for a variety of queries. In this paper, we focus on spatial data such as locations and more generally any multi-dimensional data that can be indexed by a tree structure. Directly applying existing differential privacy methods to this type of data simply generates noise. We propose instead the class of "private spatial decompositions'': these adapt standard spatial indexing methods such as quad trees and kd-trees to provide a private description of the data distribution. Equipping such structures with differential privacy requires several steps to ensure that they provide meaningful privacy guarantees. Various basic steps, such as choosing splitting points and describing the distribution of points within a region, must be done privately, and the guarantees of the different building blocks composed to provide an overall guarantee. Consequently, we expose the design space for private spatial decompositions, and analyze some key examples. A major contribution of our work is to provide new techniques for parameter setting and post-processing the output to improve the accuracy of query answers. Our experimental study demonstrates that it is possible to build such decompositions efficiently, and use them to answer a variety of queries privately with high accuracy.

Uncertainties in data can arise for a number of reasons: when data is incomplete, contains conflicting information or has been deliberately perturbed or coarsened to remove sensitive details. An important case which arises in many real applications is when the data describes a set of possibilities, but with cardinality constraints. These constraints represent correlations between tuples encoding, e.g. that at most two possible records are correct, or that there is an (unknown) one-to-one mapping between a set of tuples and attribute values. Although there has been much effort to handle uncertain data, current systems are not equipped to handle such correlations, beyond simple mutual exclusion and co-existence constraints. Vitally, they have little support for efficiently handling aggregate queries on such data. In this paper, we aim to address some of these deficiencies, by introducing LICM (Linear Integer Constraint Model), which can succinctly represent many types of tuple correlations, particularly a class of cardinality constraints. We motivate and explain the model with examples from data cleaning and masking sensitive data, to show that it enables modeling and querying such data, which was not previously possible. We develop an efficient strategy to answer conjunctive and aggregate queries on possibilistic data by describing how to implement relational operators over data in the model. LICM compactly integrates the encoding of correlations, query answering and lineage recording. In combination with off-the-shelf linear integer programming solvers, our approach provides exact bounds for aggregate queries. Our prototype implementation demonstrates that query answering with LICM can be effective and scalable.

User obligations are actions that the human users are required to perform in some future time. These are common in many practical access control and privacy and can depend on and affect the authorization state. Consequently, a user can incur an obligation that she is not authorized to perform which may hamper the usability of a system. To mitigate this problem, previous work introduced a property of the authorization state, accountability, which requires that all the obligatory actions to be authorized when they are attempted. Although, existing work provides a specific and tractable decision procedure for a variation of the accountability property, it makes a simplified assumption that no cascading obligations may happen, i.e., obligatory actions cannot further incur obligations. This is a strong assumption which reduces the expressive power of past models, and thus cannot support many obligation scenarios in practical security and privacy policies. In this work, we precisely specify the strong accountability property in the presence of cascading obligations and prove that deciding it is NP-hard. We provide for several special yet practical cases of cascading obligations (i.e., repetitive, finite cascading, etc.) a tractable decision procedure for accountability. Our experimental results illustrate that supporting such special cases is feasible in practice.

The idea of using one's behavior with a pointing device, such as a mouse or a touchpad, as a behavioral biometric for authentication purposes has gained increasing attention over the past decade. A number of interesting approaches based on the idea have emerged in the literature and promising experimental results have been reported; however, we argue that limitations in the past experimental evaluations of these approaches raise questions about their true effectiveness in a practical setting. In this paper, we review existing authentication approaches based on mouse dynamics and shed light on some important limitations regarding how the effectiveness of these approaches has been evaluated in the past. We present the results of several experiments that we conducted to illustrate our observations and suggest guidelines for evaluating future authentication approaches based on mouse dynamics. We also discuss a number of avenues for additional research that we believe are necessary to advance the state of the art in this area.

Though a variety of cloud storage services have been offered recently, they have not yet provided users with transparent and cost-effective personal data storage. Services like Google Docs offer easy file access and sharing, but tie storage with internal data formats and specific applications. Meanwhile, services like Drop box offer general-purpose storage. Yet they have not been widely utilized, partly due to their fee-charging nature and long-term service availability concerns. Web-based email services, on the other hand, have been offering growing email storage capacity, reliable service, and powerful search capability, making them appealing as storage resources. In this paper, we examine the efficacy of leveraging web-based email services to build a personal storage cloud. We present EMFS, which aggregates back-end storage by establishing a RAID-like system on top of virtual email disks formed by email accounts. In particular, by replicating data across accounts from different service providers, highly available storage services can be constructed based on already reliable, cloud-based email storage. This paper discusses the design and implementation of EMFS, focusing on unique challenges and opportunities associated with utilizing email services for file transfer and storage, such as email based data organization, metadata format and management, and handling provider-imposed anti-spam usage restrictions. We evaluated EMFS extensively with multiple benchmarks, and compared its performance with NFS, AFS, and a non-free cloud storage service built upon Amazon S3. Our results indicate that while EMFS cannot match the performance of highly optimized distributed file systems with dedicated servers, it performs quite closely to the commercial cloud storage solution.

This paper is part of a project investigating authorization systems that assign obligations to users. We are particularly interested in obligations that require authorization to be performed and that, when performed, may modify the authorization state. In this context, a user may incur an obligation she is unauthorized to perform. Prior work has introduced a property of the authorization system state that ensures users will be authorized to fulfill their obligations. We call this property accountability because users that fail to perform authorized obligations are accountable for their non-performance. While a reference monitor can mitigate violations of accountability, it cannot prevent them entirely. This paper presents techniques to be used by obligation system managers to restore accountability. We introduce several notions of dependence among pending obligations that must be considered in this process. We also introduce a novel notion we call obligation pool slicing, owing to its similarity to program slicing. An obligation pool slice identifies a set of obligations that the administrator may need to consider when applying strategies proposed here for restoring accountability. The paper also presents the system architecture of an authorization system that incorporates obligations that can require and affect authorizations.

Cloud computing needs to provide integrity assurance in order to support security sensitive application services such as critical dataflow processing. In this paper, we present a novel RObust Service Integrity Attestation (ROSIA) framework that can efficiently verify the integrity of stateful dataflow processing services and pinpoint malicious service providers within a large-scale cloud system. ROSIA achieves robustness by supporting stateful dataflow services such as windowed stream operators, and performing integrated consistency check to detect colluding attacks. We have implemented ROSIA on top of the IBM System S dataflow processing system and tested it on the NCSU virtual computing lab. Our experimental results show that our scheme is feasible and efficient for large-scale cloud systems.

Cloud computing has emerged as a multi-tenant resource sharing platform, which allows different service providers to deliver software as services in an economical way. However, for many security sensitive applications such as critical data processing, we must provide necessary security protection for migrating those critical application services into shared open cloud infrastructures. In this paper, we present RunTest, a scalable runtime integrity attestation framework to assure the integrity of dataflow processing in cloud infrastructures. RunTest provides light-weight application-level attestation methods to dynamically verify the integrity of data processing results and pinpoint malicious service providers when inconsistent results are detected. We have implemented RunTest within IBM System S dataflow processing system and tested it on NCSU virtual computing lab. Our experimental results show that our scheme is effective and imposes low performance impact for dataflow processing in the cloud infrastructure.

Despite a plethora of recent research regarding trust management approaches to authorization, relatively little attention has been given to exactly how these technologies can be effectively deployed. In this paper, we investigate one way in which well-established logical trust management systems described in the literature can be deployed within enterprise environments. Specifically, we develop a framework within which logical trust management policies can be managed using a relational DBMS. We describe a correct and complete procedure for compiling CTM credentials into dynamic views within a database, and show how the resulting system can be used to perform role membership checks or to enumerate the members of a given role. We then propose a hybrid algorithm that leverages the logical ruleset and the underlying DBMS to efficiently enumerate the capabilities ascribed to a given user. We also present an evaluation of a prototype implementation of our framework that demonstrates the practicality of our approach. As CTM extends the RT family of trust management languages---which are representative of a large class of Datalog-based trust management systems---our work is likely generalizable to other trust management approaches.

Many authorization system models include some notion of obligation. Little attention has been given to user obligations that depend on and affect authorizations. However, to be usable, the system must ensure users have the authorizations they need when their obligations must be performed. Prior work in this area introduced accountability properties that ensure failure to fulfill obligations is not due to lack of required authorizations. That work presented inconclusive and purely theoretical results concerning the feasibility of maintaining accountability in practice. The results of the current paper include algorithms and performance analysis that support the thesis that maintaining accountability in a reference monitor is reasonable in many applications.

This paper presents MAPS - a personalized Multi-Attribute Probabilistic Selection framework - to estimate the probability of an item being a user's best choice and rank the items accordingly. The MAPS framework makes three original contributions in this paper. First, we capture the inter-attribute t

Although policy compliance testing is generally treated as a binary decision problem, the evidence gathered during the trust management process can actually be used to examine these outcomes within a more continuous space. In this paper, we develop a formal model that allows us to quantitatively reason about the outcomes of the policy enforcement process in both absolute (i.e., user to ideal case) and relative (i.e., user to user) terms. Within this framework, it becomes possible to quantify, e.g., the robustness of a user's proof of authorization to possible perturbations in the system, how close an unauthorized user is to satisfying a particular policy, and relative “top-k” style rankings of the best users to carry out a particular task. To this end, we explore several interesting classes of scoring functions for assessing the robustness of authorization decisions, and develop criteria under which these types of functions can be composed with one another. We further show that these types of functions can be extended to quantify how close unauthorized users are to satisfying policies, which can be a useful risk metric for decision making under unexpected circumstances.

MapReduce has become increasingly popular as a powerful parallel data processing model. To deploy MapReduce as a data processing service over open systems such as service oriented architecture, cloud computing, and volunteer computing, we must provide necessary security mechanisms to protect the integrity of MapReduce data processing services. In this paper, we present SecureMR, a practical service integrity assurance framework for MapReduce. SecureMR consists of five security components, which provide a set of practical security mechanisms that not only ensure MapReduce service integrity as well as to prevent replay and denial of service (DoS) attacks, but also preserve the simplicity, applicability and scalability of MapReduce. We have implemented a prototype of SecureMR based on Hadoop, an open source MapReduce implementation. Our analytical study and experimental results show that SecureMR can ensure data processing service integrity while imposing low performance overhead.

During their everyday decision making, humans consider the interplay between two types of trust: vertical trust and horizontal trust. Vertical trust captures the trust relationships that exist between individuals and institutions, while horizontal trust represents the trust that can be inferred from the observations and opinions of others. Although researchers are actively exploring both vertical and horizontal trust within the context of distributed computing (e.g., credential-based trust and reputation-based trust, respectively), the specification and enforcement of composite trust management policies involving the flexible composition of both types of trust metrics is currently an unexplored area.

Before sharing to support ad hoc aggregate analyses, microdata often need to be anonymized to protect the privacy of individuals. A variety of privacy models have been proposed for microdata anonymization. Many of these models (e.g., t -closeness) essentially require that, after anonymization, groups of sensitive attribute values follow specified distributions. To support such models, in this paper we study the problem of transforming a group of sensitive attribute values to follow a certain target distribution with minimal data distortion. Specifically, we develop and evaluate a novel methodology that combines the use of sensitive attribute permutation and generalization with the addition of fake sensitive attribute values to achieve this transformation. We identify metrics related to accuracy of aggregate query answers over the transformed data, and develop efficient anonymization algorithms to optimize these accuracy metrics. Using a variety of data sets, we experimentally demonstrate the effectiveness of our techniques.

Though a user's privileges are often granted based on the tasks that the user is expected to fulfill, the concept of tasks is usually not explicitly modeled in access control. We propose a system where tasks are the central concept that associates users to privileges. Ideally a user should be able to utilize these privileges and fulfill his tasks, but not to take harmful actions. To ensure this, a system often specifies a high-level security property to restrict the sequence of actions that a user can perform. In this paper, we propose a general model of access control in task-based system. This model considers the permissions a user as well as their temporal availability. Based on this model, we investigate the problem of enforcing security properties both statically (i.e., when tasks are assigned) and dynamically (i.e., when actions are performed). We study the complexity of static enforcement, and design efficient dynamic enforcement algorithms that avoiding unnecessary history tracking.

Private data often comes in the form of associations between entities, such as customers and products bought from a pharmacy, which are naturally represented in the form of a large, sparse bipartite graph. As with tabular data, it is desirable to be able to publish anonymized versions of such data, to allow others to perform ad hoc analysis of aggregate graph properties. However, existing tabular anonymization techniques do not give useful or meaningful results when applied to graphs: small changes or masking of the edge structure can radically change aggregate graph properties. We introduce a new family of anonymizations, for bipartite graph data, called ( k, l )-groupings. These groupings preserve the underlying graph structure perfectly, and instead anonymize the mapping from entities to nodes of the graph. We identify a class of "safe" ( k, l )-groupings that have provable guarantees to resist a variety of attacks, and show how to find such safe groupings. We perform experiments on real bipartite graph data to study the utility of the anonymized version, and the impact of publishing alternate groupings of the same graph data. Our experiments demonstrate that ( k, l )-groupings offer strong tradeoffs between privacy and utility.

Sensor networks are often subject to physical attacks. Once a node's cryptographic key is compromised, an attacker may completely impersonate it and introduce arbitrary false information into the network. Basic cryptographic mechanisms are often not effective in this situation. Most techniques to address this problem focus on detecting and tolerating false information introduced by compromised nodes. They cannot pinpoint exactly where the false information is introduced and who is responsible for it. In this article, we propose an application-independent framework for accurately identifying compromised sensor nodes. The framework provides an appropriate abstraction of application-specific detection mechanisms and models the unique properties of sensor networks. Based on the framework, we develop alert reasoning algorithms to identify compromised nodes. The algorithm assumes that compromised nodes may collude at will. We show that our algorithm is optimal in the sense that it identifies the largest number of compromised nodes without introducing false positives. We evaluate the effectiveness of the designed algorithm through comprehensive experiments.

Privacy is a serious concern when microdata need to be released for ad hoc analyses. The privacy goals of existing privacy protection approaches (e.g., k-anonymity and l-diversity) are suitable only for categorical sensitive attributes. Since applying them directly to numerical sensitive attributes (e.g., salary) may result in undesirable information leakage, we propose privacy goals to better capture the need of privacy protection for numerical sensitive attributes. Complementing the desire for privacy is the need to support ad hoc aggregate analyses over microdata. Existing generalization-based anonymization approaches cannot answer aggregate queries with reasonable accuracy. We present a general framework of permutation-based anonymization to support accurate answering of aggregate queries and show that, for the same grouping, permutation-based techniques can always answer aggregate queries more accurately than generalization-based approaches. We further propose several criteria to optimize permutations for accurate answering of aggregate queries, and develop efficient algorithms for each criterion.

Traditional security policies largely focus on access control requirements, which specify who can access what under what circumstances. Besides access control requirements, the availability of services in many applications often further imposes obligation requirements, which specify what actions have to be taken by a subject in the future as a condition of getting certain privileges at present. However, it is not clear yet what the implications of obligation policies are concerning the security goals of a system.In this paper, we propose a formal metamodel that captures the key aspects of a system that are relevant to obligation management. We formally investigate the interpretation of security policies from the perspective of obligations, and define secure system states based on the concept of accountability. We also study the complexity of checking a state's accountability under different assumptions about a system.

XML is widely recognized as the data interchange standard of tomorrow because of its ability to represent data from a variety of sources. Hence, XML is likely to be the format through which data from multiple sources is integrated. In this article, we study the problem of integrating XML data sources through correlations realized as join operations. A challenging aspect of this operation is the XML document structure. Two documents might convey approximately or exactly the same information but may be quite different in structure. Consequently, an approximate match in structure, in addition to content, has to be folded into the join operation. We quantify an approximate match in structure and content for pairs of XML documents using well defined notions of distance. We show how notions of distance that have metric properties can be incorporated in a framework for joins between XML data sources and introduce the idea of reference sets to facilitate this operation. Intuitively, a reference set consists of data elements used to project the data space. We characterize what constitutes a good choice of a reference set, and we propose sampling-based algorithms to identify them. We then instantiate our join framework using the tree edit distance between a pair of trees. We next turn our attention to utilizing well known index structures to improve the performance of approximate XML join operations. We present a methodology enabling adaptation of index structures for this problem, and we instantiate it in terms of the R-tree. We demonstrate the practical utility of our solutions using large collections of real and synthetic XML data sets, varying parameters of interest, and highlighting the performance benefits of our approach.

Automated trust negotiation is an approach which establishes trust between strangers through the bilateral, iterative disclosure of digital credentials. Sensitive credentials are protected by access control policies which may also be communicated to the other party. Ideally, sensitive information should not be known by others unless its access control policy has been satisfied. However, due to bilateral information exchange, information may flow to others in a variety of forms, many of which cannot be protected by access control policies alone. In particular, sensitive information may be inferred by observing negotiation participants' behavior even when access control policies are strictly enforced.In this paper, we propose a general framework for the safety of trust negotiation systems. Compared to the existing safety model, our framework focuses on the actual information gain during trust negotiation instead of the exchanged messages. Thus, it directly reflects the essence of safety in sensitive information protection. Based on the proposed framework, we develop policy databases as a mechanism to help prevent unauthorized information inferences during trust negotiation. We show that policy databases achieve the same protection of sensitive information as existing solutions without imposing additional complications to the interaction between negotiation participants or restricting users' autonomy in defining their own policies.

In file-sharing P2P networks, a fundamental problem is that of identifying databases that are relevant to user queries. This problem is referred to as the location problem in P2P literature. We propose a scalable solution to the location problem in a data-sharing P2P network, consisting of a network of XML database nodes and XML router nodes, and make the following contributions. We develop the internal organization and routing protocols for the XML router nodes, to enable scalable XPath query and update processing, under the open and the agreement cooperation models between nodes. Since router nodes tend to be memory constrained, we facilitate a space/performance tradeoff by permitting aggregated routing states, and developing algorithms for generating and using such aggregated information. We experimentally demonstrate the scalability of our approach, and the performance of our query and update protocols, using a detailed simulation model, varying key design parameters.

XML is the undisputed standard for data representation and exchange. As companies transact business over the Internet, letting authorized customers directly access, and even modify, XML data offers many advantages in terms of cost, accuracy, and timeliness. Given the complex business relationships between companies, and the sensitive nature of information, access must be provided selectively, using sophisticated access control specifications. Using the specification directly to determine if a user has access to an XML data item can be extremely inefficient. The alternative of fully materializing, for each data item, the users authorized to access it can be space-inefficient. In this article, we introduce a compressed accessibility map (CAM) as a space- and time-efficient solution to the access control problem for XML data. A CAM compactly identifies the XML data items to which a user has access, by exploiting structural locality of accessibility in tree-structured data. We present a CAM lookup algorithm for determining if a user has access to a data item that takes time proportional to the product of the depth of the item in the XML data and logarithm of the CAM size. We develop an algorithm for building an optimal size CAM that takes time linear in the size of the XML data set. While optimality cannot be preserved incrementally under data item updates, we provide an algorithm for incrementally maintaining near-optimality. Finally, we experimentally demonstrate the effectiveness of the CAM for multiple users on a variety of real and synthetic data sets.

XML data integration tools are facing a variety of challenges for their efficient and effective operation. Among these is the requirement to handle a variety of inconsistencies or mistakes present in the data sets. We study the problem of integrating XML data sources through index assisted join operations, using notions of approximate match in the structure and content of XML documents as the join predicate. We show how a well known and widely deployed index structure, namely the R-tree, can be adopted to improve the performance of such operations. We propose novel search and join algorithms for R-trees adopted to index XML document collections. We also propose novel optimization objectives for R-tree construction, making R-trees better suited for this application.

Automated trust negotiation is an approach to establishing trust between strangers through iterative disclosure of digital credentials. In automated trust negotiation, access control policies play a key role in protecting resources from unauthorized access. Unlike in traditional trust management systems, the access control policy for a resource is usually unknown to the party requesting access to the resource, when trust negotiation starts. The negotiating parties can rely on policy disclosures to learn each other's access control requirements. However a policy itself may also contain sensitive information. Disclosing policies' contents unconditionally may leak valuable business information or jeopardize individuals' privacy. In this paper we propose UniPro, a unified scheme to model protection of resources, including policies, in trust negotiation. UniPro improves on previous work by modeling policies as first-class resources, protecting them in the same way as other resources, providing fine-grained control over policy disclosure, and clearly distinguishing between policy disclosure and policy satisfaction, which gives users more flexibility in expressing their authorization requirements. We also show that UniPro can be used with practical negotiation strategies without jeopardizing autonomy in the choice of strategy, and present criteria under which negotiations using UniPro are guaranteed to succeed in establishing trust.

Business and military partners, companies and their customers, and other closely cooperating parties may have a compelling need to conduct sensitive interactions on line, such as accessing each other's local services and other local resources. Automated trust negotiation is an approach to establishing trust between parties so that such interactions can take place, through the use of access control policies that specify what combinations of digital credentials a stranger must disclose to gain access to a local resource. A party can use many different strategies to negotiate trust, offering tradeoffs between the length of the negotiation, the amount of extraneous information disclosed, and the computational effort expended. To preserve parties' autonomy, each party should ideally be able to choose its negotiation strategy independently, while still being guaranteed that negotiations will succeed whenever possible---that the two parties' strategies will interoperate. In this paper we provide the formal underpinnings for that goal, by formalizing the concepts of negotiation protocols, strategies, and interoperation. We show how to model the information flow of a negotiation for use in analyzing strategy interoperation. We also present two large sets of strategies whose members all interoperate with one another, and show that these sets contain many practical strategies. We develop the theory for black-box propositional credentials as well as credentials with internal structure, and for access control policies whose contents are (respectively are not) sensitive. We also discuss how these results fit into TrustBuilder, our prototype system for trust negotiation.

XML is widely recognized as the data interchange standard for tomorrow, because of its ability to represent data from a wide variety sources. Hence, XML is likely to be the format through which data from multiple sources is integrated.In this paper we study the problem of integrating XML data sources through correlations realized as join operations. A challenging aspect of this operation is the XML document structure. Two documents might convey approximately or exactly the same information but may be quite different in structure. Consequently approximate match in structure, in addition to, content has to be folded in the join operation. We quantify approximate match in structure and content using well defined notions of distance. For structure, we propose computationally inexpensive lower and upper bounds for the tree edit distance metric between two trees. We then show how the tree edit distance, and other metrics that quantify distance between trees, can be incorporated in a join framework. We introduce the notion of reference sets to facilitate this operation. Intuitively, a reference set consists of data elements used to project the data space. We characterize what constitutes a good choice of a reference set and we propose sampling based algorithms to identify them. This gives rise to a variety of algorithmic approaches for the problem, which we formulate and analyze. We demonstrate the practical utility of our solutions using large collections of real and synthetic XML data sets.

Automated trust negotiation is an approach to establishing trust between strangers through the exchange of digital credentials and the use of access control policies that specify what combinations of credentials a stranger must disclose in order to gain access to each local service or credential. We introduce the concept of a trust negotiation protocol, which defines the ordering of messages and the type of information messages will contain. To carry out trust negotiation, a party pairs its negotiation protocol with a trust negotiation strategy that controls the exact content of the messages, i.e., which credentials to disclose, when to disclose them, and when to terminate a negotiation. There are a huge number of possible strategies for negotiating trust, each with different properties with respect to speed of negotiations and caution in giving out credentials and policies. In the autonomous world of the Internet, entities will want the freedom to choose negotiation strategies that meet their own goals, which means that two strangers who negotiate trust will often not use the same strategy. To date, only a tiny fraction of the space of possible negotiation strategies has been explored, and no two of the strategies proposed so far will interoperate. In this paper, we define a large set of strategies called the disclosure tree strategy (DTS) family. Then we prove that if two parties each choose strategies from the DTS family, then they will be able to negotiate trust as well as if they were both using the same strategy. Further, they can change strategies at any point during negotiation. We also show that the DTS family is closed, i.e., any strategy that can interoperate with every strategy in the DTS family must also be a member of the DTS family. We also give examples of practical strategies that belong to the DTS family and fit within the TrustBuilder architecture and protocol for trust negotiation.

Article Free Access Share on PRUNES: an efficient and complete strategy for automated trust negotiation over the Internet Authors: Ting Yu Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.Springfield Ave., Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.Springfield Ave., Urbana, ILView Profile , Xiaosong Ma Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.Springfield Ave., Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.Springfield Ave., Urbana, ILView Profile , Marianne Winslett Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.Springfield Ave., Urbana, IL Department of Computer Science, University of Illinois at Urbana-Champaign, 1304 W.Springfield Ave., Urbana, ILView Profile Authors Info & Claims CCS '00: Proceedings of the 7th ACM conference on Computer and Communications SecurityNovember 2000 Pages 210–219https://doi.org/10.1145/352600.352633Published:01 November 2000Publication History 50citation960DownloadsMetricsTotal Citations50Total Downloads960Last 12 Months37Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF