Machine learning models are vulnerable to both security attacks (e.g., adversarial examples) and privacy attacks (e.g., private attribute inference). We take the first step to mitigate both the security and privacy attacks, and maintain task utility as well. Particularly, we propose an information-theoretic framework to achieve the goals through the lens of representation learning, i.e., learning representations that are robust to both adversarial examples and attribute inference adversaries. We also derive novel theoretical results under our framework, e.g., the inherent trade-off between adversarial robustness/utility and attribute privacy, and guaranteed attribute privacy leakage against attribute inference adversaries.

Graph Neural Networks (GNNs) have emerged as powerful models for learning from graph-structured data. However, their widespread adoption has raised serious privacy concerns. While prior research has primarily focused on edge-level privacy, a critical yet underexplored threat lies in topology privacy — the confidentiality of the graph's overall structure. In this work, we present a comprehensive study on topology privacy risks in GNNs, revealing their vulnerability to graph-level inference attacks. To this end, we propose a suite of Topology Inference Attacks (TIAs) that can reconstruct the structure of a target training graph using only black-box access to a GNN model. Our findings show that GNNs are highly susceptible to these attacks, and that existing edge-level differential privacy mechanisms are insufficient as they either fail to mitigate the risk or severely compromise model accuracy. To address this challenge, we introduce Private Graph Reconstruction (PGR), a novel defense framework designed to protect topology privacy while maintaining model accuracy. PGR is formulated as a bi-level optimization problem, where a synthetic training graph is iteratively generated using meta-gradients, and the GNN model is concurrently updated based on the evolving graph. Extensive experiments demonstrate that PGR significantly reduces topology leakage with minimal impact on model accuracy. Our code and full paper are available at https://github.com/JeffffffFu/PGR.

Differentially Private Stochastic Gradient Descent (DP-SGD) is a standard method for enforcing privacy in deep learning, typically using the Gaussian mechanism to perturb gradient updates. However, conventional mechanisms such as Gaussian and Laplacian noise are parameterized only by variance or scale. This single degree of freedom ties the magnitude of noise directly to both privacy loss and utility degradation, preventing independent control of these two factors. The problem becomes more pronounced when the number of composition rounds T and batch size B vary across tasks, as these variations induce task-dependent shifts in the privacy–utility trade-off, where small changes in noise parameters can disproportionately affect model accuracy. To address this limitation, we introduce PLRV-O, a framework that defines a broad search space of parameterized DP-SGD noise distributions, where privacy loss moments are tightly characterized yet can be optimized more independently with respect to utility loss. This formulation enables systematic adaptation of noise to task-specific requirements, including (i) model size, (ii) training duration, (iii) batch sampling strategies, and (iv) clipping thresholds under both training and fine-tuning settings. Empirical results demonstrate that PLRV-O substantially improves utility under strict privacy constraints. On CIFAR-10, a fine-tuned ViT achieves 94.03% accuracy at ∈ ≈ 0.5, compared to 83.93% with Gaussian noise. On SST-2, RoBERTa-large reaches 92.20% accuracy at ∈ ≈ 0.2, versus 50.25% with Gaussian. Source code is available at https://github.com/datasec-lab/plrvo.

Differentially private federated learning (DP-FL) offers a compelling approach to collaborative model training by ensuring robust privacy for clients. Despite its potential, current methods face challenges in effectively balancing privacy, utility, and performance across diverse federated learning scenarios. Addressing these challenges, we introduce UDP-FL, to our knowledge the first DP-FL framework that universally harmonizes any randomization mechanism, including those considered optimal, by employing the Gaussian Moments Accountant (viz. DP-SGD). Central to UDP-FL is the 'Harmonizer,' a dynamic module engineered to intelligently select and apply the most suitable DP mechanism tailored to each client's specific privacy requirements, data sensitivities, and computational capacities. This selection process is driven by the principle of Rényi Differential Privacy, which serves as a crucial mediator for aligning privacy budgets effectively. Our comprehensive evaluation of UDP-FL, benchmarked against established baseline methods, demonstrates superior performance in upholding privacy guarantees and enhancing model functionality. The framework's robustness has been rigorously tested against a broad spectrum of privacy attacks, making it one of the most thorough validations of a DP-FL framework to date.

Deep neural network (DNN) services have been widely deployed for efficient and accurate inferences in many different domains. In practice, a client may send its private data (e.g., images, text messages and videos) to the service to get the inferences with the proprietary DNN models. Significant privacy and security concerns would emerge in such scenarios. Cryptographic inference systems have been proposed to address such privacy and security concerns. However, existing systems are tailored for DNNs on image inferences, but not directly applicable to video inference tasks that operate on the spatio-temporal (3D) features. To address such critical deficiencies, we design and implement the first cryptographic inference system, Crypto3D, which privately and efficiently infers videos with compressed 3D DNNs while ensuring rigorous privacy guarantees. We also update most cryptographic inference systems (designed for images) to support video understanding on 3D features with non-trivial extensions, treating them as baselines. We evaluate Crypt3D and benchmark with baselines utilizing the widely adopted C3D and I3D models on the UCF-101 and HMDB-51 datasets. Our results demonstrate that Crypto3D significantly outperforms existing systems on execution time: 554.68× vs. CryptoDL (3D), 189.21× vs. HEANN (3D), 182.61× vs. MP-SPDZ (3D), 133.56× vs. E2DM (3D), 11.09× vs. Intel SGX (3D), 8.90× vs. Gazelle (3D), 3.71 × vs. Delphi (3D), 12.97 × vs. CryptFlow2 (3D), 1.49× vs. Cheetah (3D); accuracy: 82.4% vs. <80% for all of them. Code is available at https://github.com/datasec-lab/crypto3D

Training text embedding models under differential privacy constraints is challenging due to the high dimensionality of language data and the presence of rare, identifying linguistic features.We propose DPED (Differentially Private Embedding Distillation), a framework that leverages teacher-student distillation with multi-layer noise injection to learn highquality embeddings while providing differential privacy guarantees.DPED trains an ensemble of teacher models on disjoint subsets of sensitive text data, then transfers their knowledge to a student model through noisy aggregation at multiple layers.A rare-word-aware strategy adaptively handles infrequent words, improving privacy-utility trade-offs.Experiments on benchmark datasets demonstrate that DPED outperforms standard differentially private training methods, achieving substantially higher utility at the same privacy budget.Our approach protects individual word usage patterns in training documents, preventing models from memorizing unique linguistic fingerprints while maintaining practical utility

Randomized smoothing is a leading method for achieving certified robustness in deep classifiers against ℓp-norm adversarial perturbations. However, randomized smoothing requires expensive training procedures that tune large models for different Gaussian noise levels from scratch and thus cannot leverage high-performance pre-trained neural networks. In this work, we introduce the certifying adapters framework (CAF) that enables and enhances the certification of classifier adversarial robustness. Our approach makes few assumptions about the underlying training algorithm or feature extractor, and is thus broadly applicable to different feature extractor architectures (e.g., convolutional neural networks or vision transformers) and randomized smoothing algorithms. We show that CAF (a) enables certification in uncertified models pre-trained on clean datasets and (b) substantially improves the performance of classifiers certified using randomized smoothing and SmoothAdv at multiple radii in CIFAR-10 and ImageNet. Classifiers trained with CAF achieve substantially improved certified accuracies compared to random or denoised smoothing methods. Finally, we demonstrate that CAF is insensitive to hyperparameter settings and adapter ensembles enable a single pre-trained feature extractor to defend against a range of noise perturbation scales.

Federated learning (FL) has been widely studied recently due to its property to collaboratively train data from different devices without sharing the raw data. Nevertheless, recent studies show that an adversary can still be possible to infer private information about devices' data, e.g., sensitive attributes such as income, race, and sexual orientation. To mitigate the attribute inference attacks, various existing privacy-preserving FL methods can be adopted/adapted. However, all these existing methods have key limitations: they need to know the FL task in advance, or have intolerable computational overheads or utility losses, or do not have provable privacy guarantees. We address these issues and design a task-agnostic privacy-preserving presentation learning method for FL (TAPPFL) against attribute inference attacks. TAPPFL is formulated via information theory. Specifically, TAPPFL has two mutual information goals, where one goal learns task-agnostic data representations that contain the least information about the private attribute in each device's data, and the other goal ensures the learnt data representations include as much information as possible about the device data to maintain FL utility. We also derive privacy guarantees of TAPPFL against worst-case attribute inference attacks, as well as the inherent tradeoff between utility preservation and privacy protection. Extensive results on multiple datasets and applications validate the effectiveness of TAPPFL to protect data privacy, maintain the FL utility, and be efficient as well. Experimental results also show that TAPPFL outperforms the existing defenses.

Black-box adversarial attacks have demonstrated strong potential to compromise machine learning models by iteratively querying the target model or leveraging transferability from a local surrogate model.Recently, such attacks can be effectively mitigated by state-of-the-art (SOTA) defenses, e.g., detection via the pattern of sequential queries, or injecting noise into the model. To our best knowledge, we take the first step to study a new paradigm of black-box attacks with provable guarantees -- certifiable black-box attacks that can guarantee the attack success probability (ASP) of adversarial examples before querying over the target model. This new black-box attack unveils significant vulnerabilities of machine learning models, compared to traditional empirical black-box attacks, e.g., breaking strong SOTA defenses with provable confidence, constructing a space of (infinite) adversarial examples with high ASP, and the ASP of the generated adversarial examples is theoretically guaranteed without verification/queries over the target model. Specifically, we establish a novel theoretical foundation for ensuring the ASP of the black-box attack with randomized adversarial examples (AEs). Then, we propose several novel techniques to craft the randomized AEs while reducing the perturbation size for better imperceptibility. Finally, we have comprehensively evaluated the certifiable black-box attacks on the CIFAR10/100, ImageNet, and LibriSpeech datasets, while benchmarking with 16 SOTA black-box attacks, against various SOTA defenses in the domains of computer vision and speech recognition. Both theoretical and experimental results have validated the significance of the proposed attack.

Federated graph learning (FedGL) is an emerging federated learning (FL) framework that extends FL to learn graph data from diverse sources without accessing the data. FL for non-graph data has shown to be vulnerable to backdoor attacks, which inject a shared backdoor trigger into the training data such that the trained backdoored FL model can predict the testing data containing the trigger as the attacker desires. However, FedGL against backdoor attacks is largely unexplored, and no effective defense exists.

Federated Learning (FL) is a novel client-server distributed learning framework that can protect data privacy. However, recent works show that FL is vulnerable to poisoning attacks. Many defenses with robust aggregators (AGRs) are proposed to mitigate the issue, but they are all broken by advanced attacks. Very recently, some renewed robust AGRs are designed, typically with novel clipping or/and filtering strategies, and they show promising defense performance against the advanced poisoning attacks. In this paper, we show that these novel robust AGRs are also vulnerable to carefully designed poisoning attacks. Specifically, we observe that breaking these robust AGRs reduces to bypassing the clipping or/and filtering of malicious clients, and propose an optimization-based attack framework to leverage this observation. Under the framework, we then design the customized attack against each robust AGR. Extensive experiments on multiple datasets and threat models verify our proposed optimizationbased attack can break the SOTA AGRs. We hence call for novel defenses against poisoning attacks to FL. Code is available at: https: //github.com/Yuxin104/BreakSTOAPoisoningDefenses.

Federated Learning (FL), a privacy-preserving training approach, has proven to be effective, yet its vulnerability to attacks that extract information from model weights is widely recognized. To address such privacy concerns, Local Differential Privacy (LDP) has been applied to FL: perturbing the weights trained for the local model by each client. However, besides high utility loss on the randomized model weights, we identify a new inference attack to the existing LDP method, that can reconstruct the original value from the noisy values with high confidence. To mitigate these issues, in this paper, we propose the Staircase Randomized Response (SRR)-FL framework, which assigns higher probabilities to weights closer to the true weight, reducing the distance between the true and perturbed data. This minimizes the noise for maintaining the same LDP guarantee, leading to better utility. Compared to existing LDP mechanisms (e.g., Generalized Randomized Response) on the FL, SRR-FL can further provide a more accurate privacy-preserving training model, and enhance the robustness against the inference attack while ensuring the same LDP guarantee. Furthermore, we also use the parameter shuffling method for privacy amplification. The efficacy of SRR-FL has been validated on widely used datasets MNIST, Medical-MNIST and CIFAR-10, demonstrating remarkable performance. Code is available at https://github.com/matta-varun/SRR-FL.

To interpret Vision Transformers, post-hoc explanations assign salience scores to input pixels, providing human-understandable heatmaps. However, whether these inter-pretations reflect true rationales behind the model's output is still underexplored. To address this gap, we study the faithfulness criterion of explanations: the assigned salience scores should represent the influence of the corresponding input pixels on the model's predictions. To evaluate faithful-ness, we introduce Salience-guided Faithfulness Coefficient (SaCo), a novel evaluation metric leveraging essential in-formation of salience distribution. Specifically, we con-duct pair-wise comparisons among distinct pixel groups and then aggregate the differences in their salience scores, resulting in a coefficient that indicates the explanation's degree of faithfulness. Our explorations reveal that cur-rent metrics struggle to differentiate between advanced ex-planation methods and Random Attribution, thereby failing to capture the faithfulness property. In contrast, our pro-posed SaCo offers a reliable faithfulness measurement, es-tablishing a robust metric for interpretations. Furthermore, our SaCo demonstrates that the use of gradient and multi-layer aggregation can markedly enhance the faithfulness of attention-based explanation, shedding light on potential paths for advancing Vision Transformer explainability.

Federated graph learning (FedGL) is an emerging learning paradigm to collaboratively train graph data from various clients. However, during the development and deployment of FedGL models, they are susceptible to illegal copying and model theft. Backdoor-based watermarking is a well-known method for mitigating these attacks, as it offers ownership verification to the model owner. We take the first step to protect the ownership of FedGL models via backdoor-based watermarking. Existing techniques have challenges in achieving the goal: 1) they either cannot be directly applied or yield unsatisfactory performance; 2) they are vulnerable to watermark removal attacks; and 3) they lack of formal guarantees. To address all the challenges, we propose FedGMark, the first certified robust backdoor-based watermarking for FedGL. FedGMark leverages the unique graph structure and client information in FedGL to learn customized and diverse watermarks. It also designs a novel GL architecture that facilitates defending against both the empirical and theoretically worst-case watermark removal attacks. Extensive experiments validate the promising empirical and provable watermarking performance of FedGMark. Source code is available at: https://github.com/Yuxin104/FedGMark.

Streaming data, crucial for applications like crowd-sourcing analytics, behavior studies, and real-time monitoring, faces significant privacy risks due to the large and diverse data linked to individuals. In particular, recent efforts to release data streams, using the rigorous privacy notion of differential privacy (DP), have encountered issues with unbounded privacy leakage. This challenge limits their applicability to only a finite number of time slots ("finite data stream") or relaxation to protecting the events ("event or w-event DP") rather than all the records of users. A persistent challenge is managing the sensitivity of outputs to inputs in situations where users contribute many activities and data distributions evolve over time. In this paper, we present a novel technique for Differentially Private data streaming over Infinite disclosure (DPI) that effectively bounds the total privacy leakage of each user in infinite data streams while enabling accurate data collection and analysis. Furthermore, we also maximize the accuracy of DPI via a novel boosting mechanism. Finally, extensive experiments across various streaming applications and real datasets (e.g., COVID-19, Network Traffic, and USDA Production), show that DPI maintains high utility for infinite data streams in diverse settings. Code for DPI is available at https://github.com/ShuyaFeng/DPI.

The language models, especially the basic text classification models, have been shown to be susceptible to textual adversarial attacks such as synonym substitution and word insertion attacks. To defend against such attacks, a growing body of research has been devoted to improving the model’s robustness. However, providing provable robustness guarantees instead of empirical robustness is still widely unexplored. In this paper, we propose Text-CRS, a generalized certified robustness framework for natural language processing (NLP) based on randomized smoothing. To our best knowledge, existing certified schemes for NLP can only certify the robustness against ℓ0perturbations in synonym substitution attacks. Representing each word-level adversarial operation (i.e., synonym substitution, word reordering, insertion, and deletion) as a combination of permutation and embedding transformation, we propose novel smoothing theorems to derive robustness bounds in both permutation and embedding space against such adversarial operations. To further improve certified accuracy and radius, we consider the numerical relationships between discrete words and select proper noise distributions for the randomized smoothing. Finally, we conduct substantial experiments on multiple language models and datasets. Text-CRS can address all four different word-level adversarial operations and achieve a significant accuracy improvement. We also provide the first benchmark on certified accuracy and radius of four word-level operations, besides outperforming the state-of-the-art certification against synonym substitution attacks.1

Top-k frequent items detection is a fundamental task in data stream mining. Many promising solutions are proposed to improve memory efficiency while still maintaining high accuracy for detecting the Top-k items. Despite the memory efficiency concern, the users could suffer from privacy loss if participating in the task without proper protection, since their contributed local data streams may continually leak sensitive individual information. However, most existing works solely focus on addressing either the memory-efficiency problem or the privacy concerns but seldom jointly, which cannot achieve a satisfactory tradeoff between memory efficiency, privacy protection, and detection accuracy. In this paper, we present a novel framework HG-LDP to achieve accurate Top-k item detection at bounded memory expense, while providing rigorous local differential privacy (LDP) protection. Specifically, we identify two key challenges naturally arising in the task, which reveal that directly applying existing LDP techniques will lead to an inferior "accuracy-privacy-memory efficiency" tradeoff. Therefore, we instantiate three advanced schemes under the framework by designing novel LDP randomization methods, which address the hurdles caused by the large size of the item domain and by the limited space of the memory. We conduct comprehensive experiments on both synthetic and real-world datasets to show that the proposed advanced schemes achieve a superior "accuracy-privacy-memory efficiency" tradeoff, saving 2300× memory over baseline methods when the item domain size is 41,270. Our code is anonymously open-sourced via the link.

Ubiquitous microphones on smart devices considerably raise users’ concerns about speech privacy. Since the microphones are primarily controlled by hardware/software developers, profit-driven organizations can easily collect and analyze individuals’ daily conversations on a large scale with deep learning models, and users have no means to stop such privacy-violating behavior. In this article, we propose UniAP to empower users with the capability of protecting their speech privacy from the large-scale analysis without affecting their routine voice activities. Based on our observation of the recognition model, we utilize adversarial learning to generate quasi-imperceptible perturbations to disturb speech signals captured by nearby microphones, thus obfuscating the recognition results of recordings into meaningless contents. As validated in experiments, our perturbations can protect user privacy regardless of what users speak and when they speak. The jamming performance stability is further improved by training optimization. Additionally, the perturbations are robust against noise removal techniques. Extensive evaluations show that our perturbations achieve successful jamming rates of more than 87% in the digital domain and at least 90% and 70% for common and challenging settings, respectively, in the real-life chatting scenario. Moreover, our perturbations, solely trained on DeepSpeech, exhibit good transferability over other models based on similar architecture.

Swift advancements in large language model (LLM) technologies lead to widespread research and applications, particularly in integrating LLMs with auxiliary tools, known as tool-using LLM agents. However, amid user interactions, the transmission of private information to both LLMs and tools poses considerable privacy risks to users. In this paper, we delve into current privacy-preserving solutions for LLMs and outline three pivotal challenges for tool-using LLM agents: generalization to both open-source and closed-source LLMs and tools, compliance with privacy requirements, and applicability to unrestricted tasks. To tackle these challenges, we present PrivacyAsst, the first privacy-preserving framework tailored for tool-using LLM agents, encompassing two solutions for different application scenarios. First, we incorporate a homomorphic encryption scheme to ensure computational security guarantees for users as a safeguard against both open-source and closed-source LLMs and tools. Moreover, we propose a shuffling-based solution to broaden the framework's applicability to unrestricted tasks. This solution employs an attribute-based forgery generative model and an attribute shuffling mechanism to craft privacy-preserving requests, effectively concealing individual inputs. Additionally, we introduce an innovative privacy concept,$t$-closeness in image data, for privacy compliance within this solution. Finally, we implement PrivacyAsst, accompanied by two case studies, demonstrating its effectiveness in advancing privacy-preserving artificial intelligence.

Federated Learning (FL) is a promising distributed learning approach that enables multiple clients to collaboratively train a shared global model. However, recent studies show that FL is vulnerable to various poisoning attacks, which can degrade the performance of global models or introduce backdoors into them. In this paper, we first conduct a comprehensive study on prior FL attacks and detection methods. The results show that all existing detection methods are only effective against limited and specific attacks. Most detection methods suffer from high false positives, which lead to significant performance degradation, especially in not independent and identically distributed (non-IID) settings. To address these issues, we propose FLTracer, the first FL attack provenance framework to accurately detect various attacks and trace the attack time, objective, type, and poisoned location of updates. Different from existing methodologies that rely solely on cross-client anomaly detection, we propose a Kalman filter-based cross-round detection to identify adversaries by seeking the behavior changes before and after the attack. Thus, this makes it resilient to data heterogeneity and is effective even in non-IID settings. To further improve the accuracy of our detection method, we employ four novel features and capture their anomalies with the joint decisions. Extensive evaluations show that FLTracer achieves an average true positive rate of over 96.88% at an average false positive rate of less than 2.67%, significantly outperforming SOTA detection methods (https://github.com/Eyr3/FLTracer).

Deep Neural Networks (DNNs) have been proven to be vulnerable to poisoning attacks that poison the training data with a trigger pattern and thus manipulate the trained model to misclassify data instances. In this article, we study the poisoning attacks on video recognition models. We reveal the major limitations of the state-of-the-art poisoning attacks onstealthinessandattack effectiveness: (i) the frame-by-frame poisoning trigger may cause temporal inconsistency among the video frames which can be leveraged to easily detect the attack; (ii) the feature collision-based method for crafting poisoned videos could lack both generalization and transferability. To address these limitations, we propose a novel stealthy and efficient poisoning attack framework which has the following advantages: (i) we design a 3D poisoning trigger as natural-like textures, which can maintain temporal consistency and human-imperceptibility; (ii) we formulate an ensemble attack oracle as the optimization objective to craft poisoned videos, which could construct convex polytope-like adversarial subspaces in the feature space and thus gain more generalization; (iii) our poisoning attack can be readily extended to the black-box setting with good transferability. We have experimentally validated the effectiveness of our attack (e.g., up to$95\%$success rates with only less than$\sim 0.5\%$poisoned dataset).

Accurate and robust localization is crucial for supporting high-level driving automation and safety. Modern localization solutions rely on various sensors, among which GPS has been and will continue to be essential. However, GPS can be vulnerable to malicious attacks and GPS spoofing has been identified as a high threat. With transportation infrastructure becoming increasingly important in supporting emerging vehicle technologies and systems, this study explores the potential of applying infrastructure data for defending against GPS spoofing. We propose an infrastructure-enabled framework using roadside units as an independent, secured data source. A real-time detector, based on the Isolation Forest, is constructed to detect GPS spoofing. Once spoofing is detected, GPS measurements are isolated, and the potentially compromised location estimator is corrected using secure infrastructure data. We test the proposed method using both simulation and real-world data and show its effectiveness in defending against various GPS spoofing attacks, including stealthy attacks that are proposed to fail the production-grade autonomous driving systems.

Property preserving encryption techniques have significantly advanced the utility of encrypted data in data outsourcing. However, while preserving certain properties (e.g., the prefixes or order of the data) in the encrypted data, such encryption schemes are typically limited to specific data types (e.g., IP addresses) or applications (e.g., range queries over order-preserved data), and highly vulnerable to the emerging inference attacks which may greatly limit their applications in practice. In this paper, to the best of our knowledge, we make the first attempt to generalize the prefix-preserving encryption to make it applicable to more general data types (e.g., geo-locations, market basket data, DNA sequences, numerical data and timestamps) and secure against the inference attacks. Furthermore, we present a generalized multi-view outsourcing framework that generates multiple indistinguishable data views in which one view fully preserves the utility for data analysis, and its accurate analysis result can be obliviously retrieved. We empirically evaluate the performance of our outsourcing framework against two common inference attacks on two different real datasets: the check-in location dataset and network traffic dataset. The experimental results demonstrate that our proposed framework preserves both privacy (with bounded leakage and indistinguishable data views) and utility (with 100% analysis accuracy).

These proceedings contain the papers selected for inclusion in the technical program for the 21st ACM Workshop on Privacy in the Electronic Society (WPES 2022), held in conjunction with the 29th ACM Conference on Computer and Communication Security (CCS 2022). This year, WPES is held as a hybrid event (including both in-person and online presentations) on November 7, 2022.

Deep neural network (DNN) services have been widely deployed in many different domains. For instance, a client may send its private input data (e.g., images, texts and videos) to the cloud for accurate inferences with pre-trained DNN models. However, significant privacy concerns would emerge in such applications due to the potential data or model sharing. Secure inferences with cryptographic techniques have been proposed to address such issues, and the system can perform secure two-party inferences between each client and cloud. However, most of existing cryptographic systems only focus on DNNs for extracting 2D features for image inferences, which have major limitations on latency and scalability for extracting spatio-temporal (3D) features from videos for accurate inferences. To address such critical deficiencies, we design and implement the first cryptographic inference system, Crypto3D, which privately infers videos on 3D features with rigorous privacy guarantees. We evaluate Crypto3D and benchmark with the state-of-the-art systems on privately inferring videos in the UCF-101 and HMDB-51 datasets with C3D and I3D models. Our results demonstrate that Crypto3D significantly outperforms existing systems (substantially extended to inferences with 3D features): execution time: 186.89x vs. CryptoDL (3D), 63.75x vs. HEANN (3D), 61.52x vs. MP-SPDZ (3D), 45x vs. E2DM (3D), 3.74x vs. Intel SGX (3D), and 3x vs. Gazelle (3D); accuracy: 82.3% vs. below 70% for all of them.

Location-based services (LBS) have been significantly developed and widely deployed in mobile devices. It is also well-known that LBS applications may result in severe privacy concerns by collecting sensitive locations. A strong privacy model ''local differential privacy'' (LDP) has been recently deployed in many different applications (e.g., Google RAPPOR, iOS, and Microsoft Telemetry) but not effective for LBS applications due to the low utility of existing LDP mechanisms. To address such deficiency, we propose the first LDP framework for a variety of location-based services (namely ''L-SRR''), which privately collects and analyzes user locations with high utility. Specifically, we design a novel randomization mechanism ''Staircase Randomized Response'' (SRR) and extend the empirical estimation to significantly boost the utility for SRR in different LBS applications (e.g., traffic density estimation, and k-nearest neighbors). We have conducted extensive experiments on four real LBS datasets by benchmarking with other LDP schemes in practical applications. The experimental results demonstrate that L-SRR significantly outperforms them.

In this paper, we propose a prefix-preserving encryption based data outsourcing framework which is applicable to multiple different types of data, such as geo-locations, market basket data, DNA sequences, numerical data and timestamps. It enables accurate data analyses on the encrypted data while ensuring strong privacy against inference attacks. The basic idea is to generates multiple indistinguishable data views in which one view fully preserves the utility for data analysis, and its accurate analysis result can be obliviously retrieved. We empirically evaluate the performance of our outsourcing framework against two common inference attacks on two different real datasets: the check-in location dataset and network traffic dataset, respectively. The experimental results demonstrate that our proposed framework preserves both privacy (with bounded leakage and indistinguishability of data views) and utility.

Topic mining extracts patterns and insights from text data (e.g., documents, emails and product reviews), which can be used in various applications such as intent detection. However, topic mining can result in severe privacy threats to the users who have contributed to the text corpus since they can be re-identified from the text data with certain background knowledge. To our best knowledge, we propose the first differentially private topic mining technique (namely TopicDP) which injects well-calibrated Gaussian noise into the matrix output of any topic mining algorithm to ensure differential privacy and good utility. Specifically, we smoothen the sensitivity for the Gaussian mechanism via sensitivity sampling, which addresses the major challenges resulted from the high sensitivity in topic mining for differential privacy. Furthermore, we theoretically prove the differential privacy guarantee under the Rényi differential privacy mechanism and the utility error bounds of TopicDP. Finally, we conduct extensive experiments on two real-word text datasets (Enron email and Amazon Reviews), and the experimental results demonstrate that TopicDP is a model-agnostic framework that can generate better privacy preserving performance for topic mining as compared against other differential privacy mechanisms.

Widely deployed deep neural network (DNN) models have been proven to be vulnerable to adversarial perturbations in many applications (e.g., image, audio and text classifications). To date, there are only a few adversarial perturbations proposed to deviate the DNN models in video recognition systems by simply injecting 2D perturbations into video frames. However, such attacks may overly perturb the videos without learning the spatio-temporal features (across temporal frames), which are commonly extracted by DNN models for video recognition. To our best knowledge, we propose the first black-box attack framework that generates universal 3-dimensional (U3D) perturbations to subvert a variety of video recognition systems. U3D has many advantages, such as (1) as the transfer-based attack, U3D can universally attack multiple DNN models for video recognition without accessing to the target DNN model; (2) the high transferability of U3D makes such universal black-box attack easy-to-launch, which can be further enhanced by integrating queries over the target model when necessary; (3) U3D ensures human-imperceptibility; (4) U3D can bypass the existing state-of-the-art defense schemes; (5) U3D can be efficiently generated with a few pre-learned parameters, and then immediately injected to attack real-time DNN-based video recognition systems. We have conducted extensive experiments to evaluate U3D on multiple DNN models and three large-scale video datasets. The experimental results demonstrate its superiority and practicality.

Vertical Federated Learning (FL) is a new paradigm that enables users with non-overlapping attributes of the same data samples to jointly train a model without directly sharing the raw data. Nevertheless, recent works show that it's still not sufficient to prevent privacy leakage from the training process or the trained model. This paper focuses on studying the privacy-preserving tree boosting algorithms under the vertical FL. The existing solutions based on cryptography involve heavy computation and communication overhead and are vulnerable to inference attacks. Although the solution based on Local Differential Privacy (LDP) addresses the above problems, it leads to the low accuracy of the trained model. This paper explores to improve the accuracy of the widely deployed tree boosting algorithms satisfying differential privacy under vertical FL. Specifically, we introduce a framework called OpBoost. Three order-preserving desensitization algorithms satisfying a variant of LDP called distance-based LDP (dLDP) are designed to desensitize the training data. In particular, we optimize the dLDP definition and study efficient sampling distributions to further improve the accuracy and efficiency of the proposed algorithms. The proposed algorithms provide a trade-off between the privacy of pairs with large distance and the utility of desensitized values. Comprehensive evaluations show that OpBoost has a better performance on prediction accuracy of trained models compared with existing LDP approaches on reasonable settings. Our code is open source.

A private learning scheme TextHide was recently proposed to protect the private text data during the training phase via so-called instance encoding.We propose a novel reconstruction attack to break TextHide by recovering the private training data, and thus unveil the privacy risks of instance encoding.We have experimentally validated the effectiveness of the reconstruction attack with two commonly-used datasets for sentence classification.Our attack would advance the development of privacy preserving machine learning in the context of natural language processing.

Deep learning as a service (DLaaS) has been intensively studied to facilitate the wider deployment of the emerging deep learning applications. However, DLaaS may compromise the privacy of both clients and cloud servers. Although some privacy preserving deep neural network (DNN) techniques have been proposed by composing cryptographic primitives, the challenges on computational efficiency have not been fully addressed due to the complexity of DNN models and expensive cryptographic primitives. In this paper, we propose a novel privacy preserving cloud-based DNN inference framework ("PROUD"), which greatly improves the computational efficiency. Finally, we conduct experiments on two datasets to validate the effectiveness and efficiency for the PROUD while benchmarking with the state-of-the-art techniques.

Divisible double auction enables distributed agents to trade divisible resources (e.g., electricity, mobile data, and cloud resources) by dynamically submitting the bid profiles of both buyers and sellers. In such systems, smart contract can be utilized to ensure transaction consensus among mutually distrustful agents, and strong integrity/availability of its execution on the blockchain. However, severe privacy risks emerge if disclosing the sensitive bid profiles in the transactions. Preserving privacy and consensus by designing cryptographic schemes will result in huge burden to the blockchain. To address such concerns, we design a hybridized TEE-Blockchain system (including both system and auction mechanism) to privately execute the divisible double auction while ensuring privacy, truthfulness and high efficiency.

Abstract Double auction mechanisms have been designed to trade a variety of divisible resources (e.g., electricity, mobile data, and cloud resources) among distributed agents. In such divisible double auction, all the agents (both buyers and sellers) are expected to submit their bid profiles, and dynamically achieve the best responses. In practice, these agents may not trust each other without a market mediator. Fortunately, smart contract is extensively used to ensure digital agreement among mutually distrustful agents. The consensus protocol helps the smart contract execution on the blockchain to ensure strong integrity and availability. However, severe privacy risks would emerge in the divisible double auction since all the agents should disclose their sensitive data such as the bid profiles (i.e., bid amount and prices in different iterations) to other agents for resource allocation and such data are replicated on all the nodes in the network. Furthermore, the consensus requirements will bring a huge burden for the blockchain, which impacts the overall performance. To address these concerns, we propose a hybridized TEE-Blockchain system (system and auction mechanism co-design) to privately execute the divisible double auction. The designed hybridized system ensures privacy, honesty and high efficiency among distributed agents. The bid profiles are sealed for optimally allocating divisible resources while ensuring truthfulness with a Nash Equilibrium. Finally, we conduct experiments and empirical studies to validate the system and auction performance using two real-world applications.

The papers in this special section focus on secure and emerging collaborative computing and intelligent systems. The Internet, coupled with recent advances in computing and information technologies, such as IoT, mobile edge/ cloud computing, cyber-physical-social systems, and artificial intelligence/machine learning/deep learning, have paved the way for creating next-generation smart and intelligent systems and applications that can have transformative impact in our society while accelerating rapid scientific discoveries and innovations. Unprecedented cyber-social and cyber-physical infrastructures and systems that span geographic boundaries are possible because of the Internet and the growing number of collaboration-enabling technologies. With newer technologies and paradigms getting increasingly embedded in the computing platforms and networked information systems/ infrastructures that form the digital foundation for our personal, organizational, and social processes and activities, it is increasingly becoming critical that the trust, privacy, and security issues in such digital environments are holistically addressed to ensure the safety and well-being of individuals as well as our society.

With the rapidly growing deployment of intelligent transportation systems (ITS) and smart traffic applications, vehicle trajectory data are ubiquitously generated, e.g., from GPS navigation systems, mobile applications, and urban traffic cameras. Analyzing such fine-grained data would greatly benefit the development of ITS and smart cities, yet pose severe privacy risks due to the recorded drivers’ visited locations, routes, and driving habits. Recently, some privacy enhancing techniques were proposed to sanitize such data. However, such schemes have some major limitations–they either lack formal privacy notions to quantify and bound the privacy risks, or result in very limited utility, e.g., only a sequence of locations or aggregated information can be released (without retaining the speeds, accelerations and the timestamps of vehicles). In this article, we propose a novel framework to sanitize the fine-grainedvehicle trajectories with differential privacy(VTDP), which provides rigorous privacy protection against adversaries who possess arbitrary background knowledge. Our VTDP technique involves three phases of differentially private sampling, which sequentially generate all the three categories of data (besides a pseudo identity for each vehicle)–position, moving,andtimestamps. It also includes avehicle trajectory interpolationprocedure to further improve the output utility with the properties of fine-grained vehicle trajectory data. We conducted experiments on real vehicle trajectory datasets to validate the performance of our approach.

As network security monitoring grows more sophisticated, there is an increasing need for outsourcing such tasks to third-party analysts. However, organizations are usually reluctant to share their network traces due to privacy concerns over sensitive information, e.g., network and system configuration, which may potentially be exploited for attacks. In cases where data owners are convinced to share their network traces, the data are typically subjected to certain anonymization techniques, e.g., CryptoPAn, which replaces real IP addresses with prefix-preserving pseudonyms. However, most such techniques either are vulnerable to adversaries with prior knowledge about some network flows in the traces or require heavy data sanitization or perturbation, which may result in a significant loss of data utility. In this article, we aim to preserve both privacy and utility through shifting the trade-off from between privacy and utility to between privacy and computational cost. The key idea is for the analysts to generate and analyze multiple anonymized views of the original network traces: Those views are designed to be sufficiently indistinguishable even to adversaries armed with prior knowledge, which preserves the privacy, whereas one of the views will yield true analysis results privately retrieved by the data owner, which preserves the utility. We formally analyze the privacy of our solution and experimentally evaluate it using real network traces provided by a major ISP. The experimental results show that our approach can significantly reduce the level of information leakage (e.g., less than 1% of the information leaked by CryptoPAn) with comparable utility.

Significant developments and advancement pertaining to electric vehicle (EV) technologies, such as extreme fast charging (XFC), have been witnessed in the last decade. However, there are still many challenges to the wider deployment of EVs. One of the major barriers is its availability of fast charging stations. A possible solution is to build a fast charging sharing system, by encouraging small business owners or even householders to install and share their fast charging devices, by reselling electricity energy sourced from traditional utility companies or their own solar grid. To incentivize such a system, a smart dynamic pricing scheme is needed to facilitate those growing markets with fast charging stations. The pricing scheme is expected to take into account the dynamics intertwined with pricing, demand, and environment factors, in an effort to maximize the long-term profit with the optimal price. To this end, this paper formulates the problem of dynamic pricing for fast charging as a Markov decision process and accordingly proposes several algorithmic schemes for different applications. Experimental study is conducted with useful and interesting insights.

Differential privacy (DP) has emerged as a de facto standard privacy notion for a wide range of applications. Since the meaning of data utility in different applications may vastly differ, a key challenge is to find the optimal randomization mechanism, i.e., the distribution and its parameters, for a given utility metric. Existing works have identified the optimal distributions in some special cases, while leaving all other utility metrics (e.g., usefulness and graph distance) as open problems. Since existing works mostly rely on manual analysis to examine the search space of all distributions, it would be an expensive process to repeat such efforts for each utility metric. To address such deficiency, we propose a novel approach that can automatically optimize different utility metrics found in diverse applications under a common framework. Our key idea that, by regarding the variance of the injected noise itself as a random variable, a two-fold distribution may approximately cover the search space of all distributions. Therefore, we can automatically find distributions in this search space to optimize different utility metrics in a similar manner, simply by optimizing the parameters of the two-fold distribution. Specifically, we define a universal framework, namely, randomizing the randomization mechanism of differential privacy (R2DP), and we formally analyze its privacy and utility. Our experiments show that R2DP can provide better results than the baseline distribution (Laplace) for several utility metrics with no known optimal distributions, whereas our results asymptotically approach to the optimality for utility metrics having known optimal distributions. As a side benefit, the added degree of freedom introduced by the two-fold distribution allows R2DP to accommodate the preferences of both data owners and recipients.

Log parsers first convert large-scale and unstructured system logs into structured data, and then cluster them into groups for anomaly detection and monitoring. However, the security vulnerabilities of the log parsers have not been unveiled yet. In this paper, to our best knowledge, we take the first step to propose a novel real-time black-box attack framework LogBug in which attackers slightly modify the logs to deviate the analysis result (i.e., evading the anomaly detection) without knowing the learning model and parameters of the log parser. We have empirically evaluated LogBug on five emerging log parsers using system logs collected from five different systems. The results demonstrate that LogBug can greatly reduce the accuracy of log parsers with minor perturbations in real time.

for all the predefined sensitive objects (e.g., humans and vehicles) in the video, and then propose a video sanitization technique VERRO that randomly generates utility-driven synthetic videos with indistinguishable objects. Therefore, all the objects can be well protected in the generated utility-driven synthetic videos which can be disclosed to any untrusted video recipient. We have conducted extensive experiments on three real videos captured for pedestrians on the streets. The experimental results demonstrate that the generated synthetic videos lie close to the original video for retaining good utility while ensuring rigorous privacy guarantee.

The smart grid incentivizes distributed agents with local generation (e.g., smart homes, and microgrids) to establish multi-agent systems for enhanced reliability and energy consumption efficiency. Distributed energy trading has emerged as one of the most important multi-agent systems on the power grid by enabling agents to sell their excessive local energy to each other or back to the grid. However, it requests all the agents to disclose their sensitive data (e.g., each agent's fine-grained local generation and demand load). In this paper, to the best of our knowledge, we propose the first privacy preserving distributed energy trading framework, Private Energy Market (PEM), in which all the agents privately compute an optimal price for their trading (ensured by a Nash Equilibrium), and allocate pairwise energy trading amounts without disclosing sensitive data (via novel cryptographic protocols). Specifically, we model the trading problem as a non-cooperative Stackelberg game for all the agents (i.e., buyers and sellers) to determine the optimal price, and then derive the pairwise trading amounts. Our PEM framework can privately perform all the computations among all the agents without a trusted third party. We prove the privacy, individual rationality, and incentive compatibility for the PEM framework. Finally, we conduct experiments on real datasets to validate the effectiveness and efficiency of the PEM.

Visual Privacy Attribute Classification (VPAC) identifies privacy information leakage via social media images. These images containing privacy attributes such as skin color, face or gender are classified into multiple privacy attribute categories in VPAC. With limited works in this task, current methods often extract features from images and simply classify the extracted feature into multiple privacy attribute classes. The dependencies between privacy attributes, e.g., skin color and face typically coexist in the same image, are usually ignored in classification, which causes performance degradation in VPAC. In this paper, we propose a novel end-to-end Privacy Attributes-aware Message Passing Neural Network (PA-MPNN) to address VPAC. Privacy attributes are considered as nodes on a graph and an MPNN is introduced to model the privacy attribute dependencies. To generate representative features for privacy attribute nodes, a class-wise encoder-decoder is proposed to learn a latent space for each attribute. An attention mechanism with multiple correlation matrices is also introduced in MPNN to learn the privacy attributes graph automatically. Experimental results on the Privacy Attribute Dataset demonstrate that our framework achieves better performance than state-of-the-art methods for visual privacy attributes classification.

Abstract Massive amounts of videos are ubiquitously generated in personal devices and dedicated video recording facilities. Analyzing such data would be extremely beneficial in real world (e.g., urban traffic analysis). However, videos contain considerable sensitive information, such as human faces, identities and activities. Most of the existing video sanitization techniques simply obfuscate the video by detecting and blurring the region of interests (e.g., faces, vehicle plates, locations and timestamps). Unfortunately, privacy leakage in the blurred video cannot be effectively bounded, especially against unknown background knowledge. In this paper, to our best knowledge, we propose the first differentially private video analytics platform (VideoDP) which flexibly supports different video analyses with rigorous privacy guarantee. Given the input video, VideoDP randomly generates a utility-driven private video in which adding or removing any sensitive visual element (e.g., human, and object) does not significantly affect the output video. Then, different video analyses requested by untrusted video analysts can be flexibly performed over the sanitized video with differential privacy. Finally, we conduct experiments on real videos, and the experimental results demonstrate that VideoDP can generate accurate results for video analytics.

A mutual correlation between trajectories of two users is very helpful to real-life applications such as product recommendation and social media. While providing tremendous benefits, the releasing of correlated trajectories may leak sensitive social relations, due to potential links between mutual correlations and social relations. To the best of our knowledge, we take the first step to propose a mathematically rigorous n-body Laplace framework, satisfying "-differential privacy, which efficiently prevents a social relation inference through the mutual correlation between n-node trajectories of two users. The problem is mathematically formulated by defining a trajectory correlation score to measure the social relation between two users. Then, under the n-body Laplace framework, we propose two Lagrange Multiplier-based Differentially Private (LMDP) approaches to optimize the privacy budgets, for the data utility measured by location distances and the data utility measured by location correlations, i.e., UD-LMDP and UC-LMDP. Also, we present detailed analyses of privacy, data utility, adversary knowledge and the constrained optimizations. Finally, we perform experimental studies with real-life data. Our experimental results show that our proposed approaches achieve better privacy and data utility than the existing approaches.

Microgrids equipped with renewable energy resources have proven to be critical building blocks on the power grid that can greatly improve the grid performance. A promising application would be enabling microgrids to utilize their local energy for further balancing the regional supply and demand at different times - ensuring better system economics and reliability. However, due to the privacy concerns on continuously revealing each microgrid's local data for deriving real-time optimal balancing decisions, the application of such promising cooperative technique is still limited. In this paper, we design an efficient cryptographic protocol for privately balancing the regional supply and demand, as well as each microgrid's local supply and demand in real time. We prove the security of our protocol against both passive and active adversaries. Meanwhile, we implemented a prototype of the Pairing system that integrates cryptographic protocol and the power transmission network. We mount the real smart grid datasets into Pairing in real time for system evaluations. The experimental results demonstrate the practicality of our system by scaling to hundreds of microgrids with high accuracy and efficient system performance.

Data encryption can enhance data privacy but can not prevent privacy leakage completely. Side channels such as memory access pattern can also leak critical information in the program, while encryption cannot help when the access addresses are exposed to the attackers. Oblivious RAM (ORAM) was proposed to eliminate the access pattern leakage, and it can be incorporated with the memory controller to obfuscate and reshuffle memory accesses. Tree-based ORAM, such as Path ORAM and Ring ORAM, is a cost-effective ORAM organization, and it obfuscates the memory access pattern by reading and remapping data blocks along the path. Ring ORAM can achieve a better online data retrieval performance with a read protocol which only reads selective blocks along the path, compared to Path ORAM. However, the read path operation in Ring ORAM does not take the implementation of multi-channel memory system into consideration, which yields a potential bandwidth waste and a slower response time. Therefore, in this work, we investigate the root cause of the bandwidth waste and propose a fast and secure scheduler which balances the read path operation for Ring ORAM. Our scheduling schemes can improve the read operation response time as well as the overall system performance. The experimental results show that the read path latency for data retrieval can be reduced by 33% compared to the baseline Ring ORAM implementation.

To expedite the forensic investigation process in the cloud, excessive and yet volatile data need to be acquired, transmitted, and analyzed in a timely manner. A common assumption for most existing forensic systems is that credible data can always be collected from a cloud infrastructure, which might be susceptible to various exploits. In this paper, we present the design, implementation, and evaluation of LiveForen, a system that enforces a trustworthy forensic data acquisition and transmission process in the cloud, whose computer platforms' integrity has been verified. To fulfill this objective, we propose two secure protocols that verify the fingerprints of the computer platforms, as well as the attributes of the human agents, by taking advantage of the trusted platform module and the attribute-based encryption. To transmit forensic data as a data stream and verify its integrity at the same time, a unique fragile watermark is embedded into the data stream without altering the data itself. The watermark allows not only the data integrity to be verified but also any malicious data manipulation to be localized, with minimum communication overhead. The experimental results demonstrate that LiveForen achieves good scalability and limited performance overhead for authentication, data transmission, and integrity verification in an Infrastructure-as-a-Service cloud environment.

As network security monitoring grows more sophisticated, there is an increasing need for outsourcing such tasks to third-party analysts. However, organizations are usually reluctant to share their network traces due to privacy concerns over sensitive information, e.g., network and system configuration, which may potentially be exploited for attacks. In cases where data owners are convinced to share their network traces, the data are typically subjected to certain anonymization techniques, e.g., CryptoPAn, which replaces real IP addresses with prefix-preserving pseudonyms. However, most such techniques either are vulnerable to adversaries with prior knowledge about some network flows in the traces, or require heavy data sanitization or perturbation, both of which may result in a significant loss of data utility. In this paper, we aim to preserve both privacy and utility through shifting the trade-off from between privacy and utility to between privacy and computational cost. The key idea is for the analysts to generate and analyze multiple anonymized views of the original network traces; those views are designed to be sufficiently indistinguishable even to adversaries armed with prior knowledge, which preserves the privacy, whereas one of the views will yield true analysis results privately retrieved by the data owner, which preserves the utility. We formally analyze the privacy of our solution and experimentally evaluate it using real network traces provided by a major ISP. The results show that our approach can significantly reduce the level of information leakage (e.g., less than 1% of the information leaked by CryptoPAn) with comparable utility.

Energy has been increasingly generated or collected by different entities on the power grid (e.g., universities, hospitals and households) via solar panels, wind turbines or local generators in the past decade. With local energy, such electricity consumers can be considered as “microgrids” which can simultaneously generate and consume energy. Some microgrids may have excessive energy that can be shared to other power consumers on the grid. To this end, all the entities have to share their local private information (e.g., their local demand, local supply and power quality data) to each other or a third-party to find and implement the optimal energy sharing solution. However, such process is constrained by privacy concerns raised by the microgrids. In this paper, we propose a privacy preserving scheme for all the microgrids which can securely implement their energy sharing against both semi-honest and colluding adversaries. The proposed approach includes two secure communication protocols that can ensure quantified privacy leakage and handle collusions.

The smart grid frequently collects consumers' fine-grained power usage data through smart meters to facilitate various applications, such as billing, load monitoring, regional statistics, and demand response. However, the smart meter reading streams may also pose severe privacy threats to the consumers by leaking their appliances' ON/OFF status. In this paper, we first quantitatively measure the information leakage with respect to specific appliances' status from any reading stream, and define a novel privacy notion to bound such information leakage. In addition, we propose a privacy preserving streaming algorithm with different options to effectively convert readings and promptly stream safe readings in different fashions. The output time series readings satisfy our privacy notion while guaranteeing excellent utility, such as extremely low aggregation errors and billing errors. Finally, we experimentally validate the effectiveness and efficiency of our approach using real data sets.

To make the search engine more user-friendly, commercial search engines commonly develop applications to provide suggestion or recommendation for every posed query. Clustering semantically similar queries acts as an essential prerequisite to function well in those applications. However, clustering queries effectively is quite challenging, since they are usually short, incomplete and ambiguous. Existing prevalent clustering methods, such as K-Means or DBSCAN cannot guarantee good performance in such a highly dimensional environment. Through analyzing users’ click-through query logs, hierarchical agglomerative clustering gives good results but is computationally quite expensive. This paper identifies a novel feature for clustering search queries based on a key insight – queries’ top ranked search results can themselves be used to quantify query similarity. After investigating such feature, we propose a new similarity metric for comparing those diverse queries. This facilitates us to develop two very efficient and accurate algorithms integrated in query clustering. We conduct comprehensive experiments to compare the accuracy of our approach against the known baselines along two dimensions: 1) quantifying the cohesion/separation of clustered queries, and 2) justifying the results by real-world Internet users. The experimental results demonstrate that our two algorithms and the similarity metric can generate more accurate results within a significantly shorter time.

Role mining is to define a role set to implement the role-based access control (RBAC) system and regarded as one of the most important and costliest implementation phases. While various role mining models have been proposed, we find that user experience/perception – one ultimate goal for any information system – is surprisingly ignored by the existing works. One advantage of RBAC is to support multiple role assignments and allow a user to activate the necessary role to perform the tasks at each session. However, frequent role activating and deactivating can be a tendinous thing from the user perspective. A user-friendly RBAC system is expected to assign few roles to every user. So in this paper we propose to incorporate to the role mining process a user-role assignment constraint that mandates the maximum number of roles each user can have. Under this rationale, we formulate user-oriented role mining as the user role mining problem, where all users have the same maximal role assignments, the personalized role mining problem, where users can have different maximal role assignments, and the approximate versions of the two problems, which tolerate a certain amount of deviation from the complete reconstruction. The extra constraint on the maximal role assignments poses a great challenge to role mining, which in general is already a hard problem. We examine some typical existing role mining methods to see their applicability to our problems. In light of their insufficiency, we present a new algorithm, which is based on a novel dynamic candidate role generation strategy, tailored to our problems. Experiments on benchmark data sets demonstrate the effectiveness of our proposed algorithm.

Severe privacy leakage in the AOL search log incident has attracted considerable worldwide attention. However, all the web users' daily search intents and behavior are collected in such data, which can be invaluable for researchers, data analysts and law enforcement personnel to conduct social behavior study [14], criminal investigation [5] and epidemics detection [10]. Thus, an important and challenging research problem is how to sanitize search logs with strong privacy guarantee and sufficiently retained utility. Existing approaches in search log sanitization are capable of only protecting the privacy under a rigorous standard [24] or maintaining good output utility [25] . To the best of our knowledge, there is little work that has perfectly resolved such tradeoff in the context of search logs, meeting a high standard of both requirements. In this paper, we propose a sanitization framework to tackle the above issue in a distributed manner. More specifically, our framework enables different parties to collaboratively generate search logs with boosted utility while satisfying Differential Privacy. In this scenario, two privacy-preserving objectives arise: first, the collaborative sanitization should satisfy differential privacy; second, the collaborative parties cannot learn any private information from each other. We present an efficient protocol -Collaborative sEarch Log Sanitization (CELS) to meet both privacy requirements. Besides security/privacy and cost analysis, we demonstrate the utility and efficiency of our approach with real data sets.

Privacy and security concerns often prevent the sharing of users' data or even of the knowledge gained from it, thus deterring valuable information from being utilized. Privacy-preserving knowledge discovery, if done correctly, can alleviate this problem. One of the most important and widely used data mining techniques is that of classification. We consider the model where a single provider has centralized access to a dataset and would like to release a classifier while protecting privacy to the best extent possible. Recently, the model of differential privacy has been developed which provides a strong privacy guarantee even if adversaries hold arbitrary prior knowledge. In this paper, we apply this rigorous privacy model to develop a Naive Bayes classifier, which is often used as a baseline and consistently provides reasonable classification performance. We experimentally evaluate the proposed approach, and discuss how it could be potentially deployed in PaaS clouds.

Web search logs contain extremely sensitive data, as evidenced by the recent AOL incident. However, storing and analyzing search logs can be very useful for many purposes (i.e. investigating human behavior). Thus, an important research question is how to privately sanitize search logs. Several search log anonymization techniques have been proposed with concrete privacy models. However, in all of these solutions, the output utility of the techniques is only evaluated rather than being maximized in any fashion. Indeed, for effective search log anonymization, it is desirable to derive the outputs with optimal utility while meeting the privacy standard. In this paper, we propose utility-maximizing sanitization based on the rigorous privacy standard of differential privacy, in the context of search logs. Specifically, we utilize optimization models to maximize the output utility of the sanitization for different applications, while ensuring that the production process satisfies differential privacy. An added benefit is that our novel randomization strategy maintains the schema integrity in the output search logs. A comprehensive evaluation on real search logs validates the approach and demonstrates its robustness and scalability.

In today's networked world, resource providers and consumers are distributed globally and locally, especially under current cloud computing environment. However, with resource constraints, optimization is necessary to ensure the best possible usage of such scarce resources. Distributed linear progr amming (DisLP) problems allow collaborative agents to jointly maximize profits or minimize costs with a linear objective function while conforming to several shared as well as local linear constraints. Since each agent's share of the global constraints and the local constraints generally refer to its private limitations or capacities, serious privacy problems may arise if such information is revealed. While there have been some solutions raised that allow secure computation of such problems, they typically rely on inefficient protocols with enormous computation and communication cost. In this paper, we study the DisLP problems where constraints are arbitrarily partitioned and every agent privately holds a set of variables, and propose secure and extremely efficient approach based on mathematical transformation in two adversary models – semi-honest and malicious model. Specifically, we first present a secure column generation (SCG) protocol that securely solves the above DisLP problem amongst two or more agents without any private information disclosure, assuming semi-honest behavior (all agents properly follow the protocol but may be curious to derive private information from other agents). Furthermore, we discuss potential selfish actions and colluding issues in malicious model (distributed agents may corrupt the protocol to gain extra benefit) and propose an incentive compatible protocol to resolve such malicious behavior. To address the effectiveness of our protocols, we present security analysis for both adversary models as well as the communication/computation cost analysis. Finally, our experimental results validate the efficiency of our approach and demonstrate its scalability.

The role mining problem has received considerable attention recently. Among the many solutions proposed, the Boolean matrix decomposition (BMD) formulation has stood out, which essentially discovers roles by decomposing the binary matrix representing user-to-permission assignment (UPA) into two matrices-user-to-role assignment (UA) and permission-to-role assignment (PA). However, supporting certain embedded constraints, such as separation of duty (SoD) and exceptions, is critical to the role mining process. Otherwise, the mined roles may not capture the inherent constraints of the access control policies of the organization. None of the previously proposed role mining solutions, including BMD, take into account these underlying constraints while mining. In this paper, we extend the BMD so that it reflects such embedded constraints by proposing to allow negative permissions in roles or negative role assignments for users. Specifically, by allowing negative permissions in roles, we are often able to use less roles to reconstruct the same given user-permission assignments. Moreover, from the resultant roles we can discover underlying constraints such as separation of duty constraints. This feature is not supported by any existing role mining approaches. Hence, we call the role mining problem with negative authorizations the constraint-aware role mining problem (CRM). We also explore other interesting variants of the CRM, which may occur in real situations. To enable CRM and its variants, we propose a novel approach, extended Boolean matrix decomposition (EBMD), which addresses the ineffectiveness of BMD in its ability of capturing underlying constraints. We analyze the computational complexity for each of CRM variants and present heuristics for problems that are proven to be NP-hard.

Clustering of search engine queries has attracted significant attention in recent years. Many search engine applications such as query recommendation require query clustering as a pre-requisite to function properly. Indeed, clustering is necessary to unlock the true value of query logs. However, clustering search queries effectively is quite challenging, due to the high diversity and arbitrary input by users. Search queries are usually short and ambiguous in terms of user requirements. Many different queries may refer to a single concept, while a single query may cover many concepts. Existing prevalent clustering methods, such as K-Means or DBSCAN cannot assure good results in such a diverse environment. Agglomerative clustering gives good results but is computationally quite expensive. This paper presents a novel clustering approach based on a key insight -- search engine results might themselves be used to identify query similarity. We propose a novel similarity metric for diverse queries based on the ranked URL results returned by a search engine for queries. This is used to develop a very efficient and accurate algorithm for clustering queries. Our experimental results demonstrate more accurate clustering performance, better scalability and robustness of our approach against known baselines.

User search query logs have proven to be very useful, but have vast potential for misuse. Several incidents have shown that simple removal of identifiers is insufficient to protect the identity of users. Publishing such inadequately anonymized data can cause severe breach of privacy. While significant effort has been expended on coming up with anonymity models and techniques for microdata, there is little corresponding work for query log data. Query logs are different in several important aspects, such as the diversity of queries and the causes of privacy breach. This necessitates the need to design privacy models and techniques specific to this environment. This paper takes a first cut at tackling this challenge. Our main contribution is to define effective anonymization models for query log data along with proposing techniques to achieve such anonymization. We analyze the inherent utility and privacy tradeoff, and experimentally validate the performance of our techniques.

With the vast increase in collection and storage of data, the problem of data summarization is most critical for effective data management. Since much of this data is categorical in nature, it can be viewed in terms of a Boolean matrix. Boolean matrix decomposition (BMD) has been used to provide concise and interpretable representations of Boolean data sets. A Boolean matrix can be expressed as a product of two Boolean matrices, where the first matrix represents a set of meaningful concepts, and the second describes how the observed data can be expressed as combinations of those concepts. Typically, the combination is only in terms of the set union. In other words, a successful Boolean matrix decomposition gives a set of concepts and shows how every column of the input data can be expressed as a union of some subset of those concepts. However, this way of modeling only incompletely represents real data semantics. Essentially, it ignores a critical component -- the set difference operation: a column can be expressed as the combination of union of certain concepts as well as the exclusion of other concepts. This has two significant benefits. First, the total number of concepts required to describe the data may itself be reduced. Second, a more succinct summarization may be found for every column. In this paper, we propose the extended Boolean matrix decomposition (EBMD) problem, which aims to factor Boolean matrices using both the set union and set difference operations. We study several variants of the problem, show that they are NP-hard, and propose efficient heuristics to solve them. Extensive experimental results demonstrate the power of EBMD.

Telehealth applications can deliver medical services to patients at remote locations using telecommunications technologies, such as the Internet. At the same time, such applications also pose unique security challenges. First, the trust issue becomes more severe due to the lack of visual proofs in telehealth applications. The public key infrastructure (PKI) is insufficient for providing the same kind of trust a patient may attain during a face-to-face service. Second, telehealth services, such as tele-monitoring or tele-consultant, naturally demand a systematic organization of users, roles, resources, and flows of information. Existing access control mechanisms in an e-health system are usually incapable of dealing with such workflow-based services. This paper provides cost-efficient solutions to those issues in the context of a Web-based e-health portal system. First, we propose a PKI-like infrastructure for establishing trust between users using biometrics-based authentication and hierarchies of trust. Second, we develop an access control method for workflow-based telehealth services using a rule-based module already available in the portal system.

Safeguarding patientspsila private information is one of the most challenging issues in the design and implementation of modern e-Health systems. Recent advances in Hippocratic Databases (HDB) show a promising direction towards the enforcement of privacy policies in e-Health systems. This paper tackles issues in applying the HDB design to e-Health systems. More specifically, we design an architecture for integrating APPEL preferences with HDB; we extend the original HDB design to support fine-grained privacy authorizations demanded by patients; we adapt the design to a multi-dimensional model; we also propose a design for hierarchical authorizations. Finally, we discuss implementation issues and justify our designs with experimental results.