Signed graphs serve as fundamental data structures for representing positive and negative relationships in social networks, with signed graph neural networks (SGNNs) emerging as the primary tool for their analysis. Our investigation reveals that balance theory, while essential for modeling signed relationships in SGNNs, inadvertently introduces exploitable vulnerabilities to black-box attacks. To showcase this, we propose balance-attack, a novel adversarial strategy specifically designed to compromise graph balance degree, and develop an efficient heuristic algorithm to solve the associated NP-hard optimization problem. While existing approaches attempt to restore attacked graphs through balance learning techniques, they face a critical challenge we term “Irreversibility of Balance-related Information,” as restored edges fail to align with original attack targets. To address this limitation, we introduce Balance Augmented-Signed Graph Contrastive Learning (BA-SGCL), an innovative framework that combines contrastive learning with balance augmentation techniques to achieve robust graph representations. By maintaining high balance degree in the latent space, BA-SGCL not only effectively circumvents the irreversibility challenge but also significantly enhances model resilience. Extensive experiments across multiple SGNN architectures and real-world datasets demonstrate both the effectiveness of our proposed balance-attack and the superior robustness of BA-SGCL, advancing the security and reliability of signed graph analysis in social networks. Datasets and codes of the proposed framework are at the github repositoryhttps://github.com/JialongZhou666/BA-SGCL.git.

Despite the popularity of graph neural networks, perturbed graph data is still a serious threat towards its inherent vulnerabilities. Adversarial examples can still easily manipulate the output of graph neural networks across various attack scenarios. Meanwhile, attacks on graph networks also appear to be crucial, as it can help model designers enhance the robustness of their models. In this study, we propose a sensitivity-oriented poisoning attack for self-supervised graph embedding models through bilevel optimization, which employs different optimization methods at each level. In addition, in order to improve attack effectiveness, we analyze graph structure to identify sensitive nodes and edges that guide attack directions, combining gradient-based and query-based methods to target both edge connections and node attributes. Besides, according to the defects of existing graph masked auto-encoders models, we design the feature sensitivity and feature variance to reduce the feature differentiability, which impairs the performance of the downstream model. Ablation studies validate our operator is effective on three citation datasets. And benchmark-based experiments support the effectiveness of our method on three different graph tasks. Specifically, our approach can achieve an average reduction of 3% in the accuracy of node classification compared to existing methods for attacking neural structures alone. For attacking both graph structures and attributes, our model has even achieved an average reduction of 4.5% for the node classification task, outperforming the existing methods.

To defend against adversarial structural attacks on graphs, we analyze attacks through the lens of mutual information and discover the “pairwise effect". This effect reveals that structural attacks effectively degrade the performance of victim GNNs when these GNNs receive the modified structure paired with the given node attributes as training input. Therefore, we propose a novel defense strategy that renders structural attacks ineffective by disrupting the pairing of modified structures and node attributes during the training of victim GNNs, which we call “disrupting the pairwise effect". To implement this idea, we propose two simple yet effective training strategies: Structural Fine-Tuning (SF) and Progressive Structural Training (PST), which disrupt the pairwise effect through node attributes pre-training followed by structure fine-tuning and progressive structure training, respectively. Compared to existing robust GNNs, our strategies avoid time-consuming techniques, thereby improving the robustness of GNNs while enhancing training speed. Additionally, these strategies can be easily applied to a wide range of commonly used GNNs, including robust GNN variants, making them highly adaptable to different models and applications. We provide theoretical analysis of the proposed training strategies and conduct extensive experiments on various datasets to demonstrate their effectiveness. Datasets and codes of this paper are available at https://github.com/Xing-Ai1003/Revisiting-Adversarial-Robustness-of-GNNs.

Semantic Communication (SC) achieves meaning transmission instead of bitstreams by deep semantic encoding decoding. Since the encoder-decoder contains sensitive and proprietary knowledge, its illicit leakage infringes commercial benefits and copyright, which warrants corresponding protection. However, current SC security paradigms narrowly emphasize transmission data protection while neglecting encoding knowl edge safeguarding. To bridge this gap, we present SemanAegis, the first SC knowledge protection framework. SemanAegisinte grates a built-in-system access control mechanism that remains effective even if the system is stolen, ensuring that unauthorized access attempts yield unacceptable low-fidelity outputs, while credential-embedded inputs from authorized entities are met with accurate responses. Specifically, we establish access control through backdoor implantation, whereby only inputs embedded with credentials activate the backdoor and access system, while source inputs are constrained to generate erroneous results. Moreover, we adopt a synthesizer to generate imperceptible credentials, thus guaranteeing their confidentiality. Additionally, a dedicated contrastive learning strategy is implemented to accelerate the convergence of backdoor implanting. Empirical evaluations across SC systems and benchmark datasets demonstrate SemanAegis precisely rejects unauthorized inputs, effectively mitigates knowledge extractions, and consistently preserves SC regular functionality.

Accurate graph annotation typically requires substantial labeled data, which is often challenging and resource-intensive to obtain. In this paper, we present Crowdsourced Homophily Ties Based Graph Annotation via Large Language Model (CSA-LLM), a novel approach that combines the strengths of crowdsourced annotations with the capabilities of large language models (LLMs) to enhance the graph annotation process. CSA-LLM harnesses the structural context of graph data by integrating information from 1-hop and 2-hop neighbors. By emphasizing homophily ties—key connections that signify similarity within the graph—CSA-LLM significantly improves the accuracy of annotations. Experimental results demonstrate that this method enhances the performance of Graph Neural Networks (GNNs) by delivering more precise and reliable annotations. Codes and data are available at https://github.com/spotpan/CSA-LLM

Graph learning models have been empirically proven to be vulnerable to backdoor threats, wherein adversaries submit trigger-embedded inputs to manipulate the model predictions. Current graph backdoor defenses manifest several limitations: 1) dependence on model-related details, 2) necessitation of additional fine-tuning, and 3) reliance on extra explainability tools, all of which are infeasible under stringent privacy policies. To address those limitations, we propose GraphProt, a certified black-box defense method to suppress backdoor attacks on GNN-based graph classifiers. Our GraphProt operates in a model-agnostic manner and solely leverages graph input. Specifically, GraphProt first introduces designed topology-feature-filtration to mitigate graph anomalies. Subsequently, subgraphs are sampled via a formulated strategy integrating topology and features, followed by a robust model inference through a majority vote-based subgraph prediction ensemble. Our results across benchmark attacks and datasets show GraphProt effectively reduces attack success rates while preserving regular graph classification accuracy.

Linearized Graph Neural Networks (GNNs) have attracted great attention in recent years for graph representation learning. Compared with nonlinear Graph Neural Network (GNN) models, linearized GNNs are much more time-efficient and can achieve comparable performances on typical downstream tasks such as node classification. Although some linearized GNN variants are purposely crafted to mitigate "over-smoothing", empirical studies demonstrate that they still somehow suffer from this issue. In this paper, we instead relate over-smoothing with the vanishing gradient phenomenon and craft a gradient-free training framework to achieve more efficient and effective linearized GNNs which can significantly overcome over-smoothing and enhance the generalization of the model. The experimental results demonstrate that our methods achieve better and more stable performances on node classification tasks with varying depths and cost much less training time.

Adversarial attacks in network security are a growing concern, prompting the need for innovative strategies to enhance both attack and defense mechanisms. This paper explores ways to improve adversarial attacks on the fairness and goodness algorithm (FGA) and review to reviewer (REV2), focusing on predicting trust within signed graphs. Unlike traditional time-based models, FGA and REV2 rely on iterative processes for trust propagation. By analyzing network structures, we identify strong ties and weak ties within FGA and discover preferential paths in REV2 that significantly impact information spread during algorithm iterations. Based on these insights, we propose a new approach called the vicinage attack , which enhances adversarial attacks by strategically targeting edges along these critical pathways. Our work highlights adversarial perturbation patterns that affect trust prediction on signed graphs and emphasizes their wide-reaching impact. These findings not only advance adversarial attack techniques but also deepen our understanding of trust propagation patterns. By clarifying the propagation bias in FGA and REV2, this research provides valuable insights for improving network security and developing better adversarial mitigation techniques in trust prediction.

Android, being one of the most widely used mobile systems, is facing pressing threats from malware. Despite the effectiveness of Android malware detection (AMD) systems, they are still vulnerable to state-of-the-art adversarial attacks. Existing defense methods require the knowledge of target adversaries, such as attack algorithms or obfuscation strategies, which is impractical in real-world scenarios. Additionally, these approaches may adversely affect the performance of the detection model and fail to defend against problem-space attacks, which not only deceive the detection models but also generate executable adversarial software. To address this research gap, we propose a novel interpretable Android guard system, named IADGuard, to help AMD defend against attacks. IADGuard first designs a novel graph explainable method, AGExplainer, to identify suspicious functions and invocations in adversarial malware. With the guidance of AGExplainer, IADGuard develops a rectifier to reverse adversarial modifications on apps’ function invocation relations, which facilitates the detection of adversarial malware by victim AMD. It is noteworthy that IADGuard requires zero knowledge of adversarial models and victim models, thereby preserves the performance of victim AMD. We validate IADGuard over three state-of-the-art problem space attacks that modify apps’ function invocation relations to deceive victim AMD. Experimental results show that IADGuard achieves over 90.5% defense success rate, i.e., helps victim AMD identify adversarial malware. Furthermore, AGExplainer surpasses representative interpreters in identifying essential modifications, helps IADGuard reduce false positives to 1.5%, and improves the detection efficiency by up to 10.4 times.

The graph contrastive learning (GCL) framework has gained remarkable achievements in graph representation learning. However, similar to graph neural networks (GNNs), GCL models are susceptible to graph structural attacks. As an unsupervised method, GCL faces greater challenges in defending against adversarial attacks. Furthermore, there has been limited research on enhancing the robustness of GCL. To thoroughly explore the failure of GCL on the poisoned graphs, we investigate the detrimental effects of graph structural attacks against the GCL framework. We discover that, in addition to the conventional observation that graph structural attacks tend to connect dissimilar node pairs, these attacks also diminish the mutual information between the graph and its representations from an information-theoretical perspective, which is the cornerstone of the high-quality node embeddings for GCL. Motivated by this theoretical insight, we propose a robust graph contrastive learning framework with a learnable sanitation view that endeavors to sanitize the augmented graphs by restoring the diminished mutual information caused by the structural attacks. Additionally, we design a fully unsupervised tuning strategy to tune the hyperparameters without accessing the label information, which strictly coincides with the defender’s knowledge. Extensive experiments demonstrate the effectiveness and efficiency of our proposed method compared to competitive baselines.

The success of graph neural networks stimulates the prosperity of graph mining and the corresponding downstream tasks including graph anomaly detection (GAD). However, it has been explored that those graph mining methods are vulnerable to structural manipulations on relational data. That is, the attacker can maliciously perturb the graph structures to assist the target nodes in evading anomaly detection. In this article, we explore the structural vulnerability of two typical GAD systems: unsupervised FeXtra-based GAD and supervised graph convolutional network (GCN)-based GAD. Specifically, structural poisoning attacks against GAD are formulated as complex bi-level optimization problems. Our first major contribution is then to transform the bi-level problem into one-level leveraging different regression methods. Furthermore, we propose a new way of utilizing gradient information to optimize the one-level optimization problem in the discrete domain. Comprehensive experiments demonstrate the effectiveness of our proposed attack algorithm $\textsf {BinarizedAttack}$ .

Graph Neural Networks (GNNs) are powerful but vulnerable to adversarial attacks, necessitating the research on certified robustness that can provide GNNs with robustness guarantees. Existing randomized smoothing methods struggle with a trade-off between utility and robustness due to high noise levels. We introduce AuditVotes, which integrates randomized smoothing with two components, augmentation and conditional smoothing, aiming to improve data and vote quality. We instantiated AuditVotes with simple strategies, and preliminary results demonstrate its significant promise in enhancing certified robustness, representing a substantial step toward deploying certifiably robust GNNs in real-world applications.

The Fairness and Goodness Algorithm (FGA) is a widely used trust system in signed directed networks. However, attackers can manipulate trust scores on FGA by launching indirect Sybil attacks and exploiting strong ties. In this work, we propose a novel attack method vicinage-attack that formulates the problem as a combination optimization problem for mining candidate attacking edges. Our method constructs perturbation spaces and infers the existence of polymorphic strong ties. To evaluate vicinage-attack, we compare it against several baselines and show the vicinage-attack outperforms them. Overall, our work highlights the potential dangers of indirect Sybil attacks on FGA and offers insight for detecting and mitigating these attacks.

Graph Neural Networks (GNNs) have become widely used in the field of graph mining. However, these networks are vulnerable to structural perturbations. While many research efforts have focused on analyzing vulnerability through poisoning attacks, we have identified an inefficiency in current attack losses. These losses steer the attack strategy towards modifying edges targeting misclassified nodes or resilient nodes, resulting in a waste of structural adversarial perturbation. To address this issue, we propose a novel attack loss framework called the Cost Aware Poisoning Attack (CA-attack) to improve the allocation of the attack budget by dynamically considering the classification margins of nodes. Specifically, it prioritizes nodes with smaller positive margins while postponing nodes with negative margins. Our experiments demonstrate that the proposed CA-attack significantly enhances existing attack strategies.

Graph anomaly detection (GAD) has achieved success and has been widely applied in various domains, such as fraud detection, cybersecurity, finance security, and biochemistry. However, existing graph anomaly detection algorithms focus on distinguishing individual entities (nodes or graphs) and overlook the possibility of anomalous groups within the graph. To address this limitation, this paper introduces a novel unsupervised framework for a new task called Group-level Graph Anomaly Detection (Gr-GAD). The proposed framework first employs a variant of Graph AutoEncoder (GAE) to locate anchor nodes that belong to potential anomaly groups by capturing long-range inconsistencies. Subsequently, group sampling is employed to sample candidate groups, which are then fed into the proposed Topology Pattern-based Graph Contrastive Learning (TPGCL) method. TPGCL utilizes the topology patterns of groups as clues to generate embeddings for each candidate group and thus distinct anomaly groups. The experimental results on both real-world and synthetic datasets demonstrate that the proposed framework shows superior performance in identifying and localizing anomaly groups, highlighting it as a promising solution for Gr-GAD. Datasets and codes of the proposed framework are at the github repository https://github.com/STiL-Team/Topology-Pattern-Enhanced-Unsupervised-Group-level-Graph-Anomaly-Detection.git.

We investigate certified robustness for GNNs under graph injection attacks. Existing research only provides sample-wise certificates by verifying each node independently, leading to very limited certifying performance. In this paper, we present the first collective certificate, which certifies a set of target nodes simultaneously. To achieve it, we formulate the problem as a binary integer quadratic constrained linear programming (BQCLP). We further develop a customized linearization technique that allows us to relax the BQCLP into linear programming (LP) that can be efficiently solved. Through comprehensive experiments, we demonstrate that our collective certification scheme significantly improves certification performance with minimal computational overhead. For instance, by solving the LP within 1 minute on the Citeseer dataset, we achieve a significant increase in the certified ratio from 0.0% to 81.2% when the injected node number is 5% of the graph size. Our paper marks a crucial step towards making provable defense more practical. Our source code is available at https://github.com/Yuni-Lai/CollectiveLPCert.

Deep Graph Learning (DGL) has emerged as a crucial technique across various domains. However, recent studies have exposed vulnerabilities in DGL models, such as susceptibility to evasion and poisoning attacks. While empirical and provable robustness techniques have been developed to defend against graph modification attacks (GMAs), the problem of certified robustness against graph injection attacks (GIAs) remains largely unexplored. To bridge this gap, we introduce the node-aware bi-smoothing framework, which is the first certifiably robust approach for general node classification tasks against GIAs. Notably, the proposed node-aware bi-smoothing scheme is model-agnostic and is applicable for both evasion and poisoning attacks. Through rigorous theoretical analysis, we establish the certifiable conditions of our smoothing scheme. We also explore the practical implications of our node-aware bi-smoothing schemes in two contexts: as an empirical defense approach against real-world GIAs and in the context of recommendation systems. Furthermore, we extend two state-of-the-art certified robustness frameworks to address node injection attacks and compare our approach against them. Extensive evaluations demonstrate the effectiveness of our proposed certificates.1

Random Walks-based Anomaly Detection (RWAD) is commonly used to identify anomalous patterns in various applications. An intriguing characteristic of RWAD is that the input graph can either be pre-existing graphs or feature-derived graphs constructed from raw features. Consequently, there are two potential attack surfaces against RWAD: graph-space attacks and feature-space attacks. In this paper, we explore this vulnerability by designing practical coupled-space (interdependent feature-space and graph-space) attacks, investigating the interplay between graph-space and feature-space attacks. To this end, we conduct a thorough complexity analysis, proving that attacking RWAD is NP-hard. Then, we proceed to formulate the graph-space attack as a bi-level optimization problem and propose two strategies to solve it: alternative iteration (alterI-attack) or utilizing the closed-form solution of the random walk model (cf-attack). Finally, we utilize the results from the graph-space attacks as guidance to design more powerful feature-space attacks (i.e., graph-guided attacks). Comprehensive experiments demonstrate that our proposed attacks are effective in enabling the target nodes to evade the detection from RWAD with a limited attack budget. In addition, we conduct transfer attack experiments in a black-box setting, which show that our feature attack significantly decreases the anomaly scores of target nodes. Our study opens the door to studying the coupled-space attack against graph anomaly detection in which the graph space relies on the feature space.

The robustness of recommender systems under node injection attacks has garnered significant attention. Recently, GraphRfi, a Graph-Neural-Network-based (GNN-based) recommender system, was proposed and shown to effectively mitigate the impact of injected fake users. However, we demonstrate that GraphRfi remains vulnerable to attacks due to the supervised nature of its fraudster detection component, where obtaining clean labels is challenging in practice. In particular, we propose a powerful poisoning attack, MetaC, against both GNN-based and Martix-Faxtorization-based recommender systems. Furthermore, we analyze why GraphRfi fails under such an attack. Then, based on our insights obtained from vulnerability analysis, we design an adaptive fraudster detection module that explicitly considers label uncertainty. This module can serve as a plug-in for different recommender systems, resulting in a robust framework named Posterior-Detection Recommender (PDR). Comprehensive experiments show that our defense approach outperforms other benchmark methods under attacks. Overall, our research presents an effective framework for integrating fraudster detection into recommendation systems to achieve adversarial robustness.

Signed social networks are widely used to model the trust relationships among online users in security-sensitive systems such as cryptocurrency trading platforms, where trust prediction plays a critical role. In this paper, we investigate how attackers could mislead trust prediction by secretly manipulating signed networks. To this end, we first design effective poisoning attacks against representative trust prediction models. The attacks are formulated as hard bi-level optimization problems, for which we propose several efficient approximation solutions. However, the resultingbasic attackswould severely change the structural semantics (in particular, both local and global balance properties) of a signed network, which makes the attacks prone to be detected by the powerful attack detectors we designed. Given this, we further refine the basic attacks by integrating someconflicting metricsas penalty terms into the objective function. Therefined attacksbecome secrecy-aware, i.e., they can successfully evade attack detectors with high probability while sacrificing little attack performance. We conduct comprehensive experiments to demonstrate that the basic attacks can severely disrupt trust prediction but could be easily detected, and the refined attacks perform almost equally well while evading detection. Overall, our results significantly advance the knowledge in designing more practical attacks, reflecting more realistic threats to current trust prediction models. Moreover, the results also provide valuable insights and guidance for building up robust trust prediction systems.

Graph Neural Networks (GNNs) are vulnerable to data poisoning attacks, which will generate a poisoned graph as the input to the GNN models. We present FocusedCleaner as a poisoned graph sanitizer to effectively identify the poison injected by attackers. Specifically, FocusedCleaner provides a sanitation framework consisting of two modules: bi-level structural learning and victim node detection. In particular, the structural learning module will reverse the attack process to steadily sanitize the graph while the detection module provides the “focus” – a narrowed and more accurate search region – to structural learning. These two modules will operate in iterations and reinforce each other to sanitize a poisoned graph step by step. As an important application, we show that the adversarial robustness of GNNs trained over the sanitized graph for the node classification task is significantly improved. Extensive experiments demonstrate that FocusedCleaner outperforms the state-of-the-art baselines both on poisoned graph sanitation and improving robustness.

Anti-malware engines report malware labels to detail malice, typically including tags of family, behavior, and platform classes. This capability has been heavily used by the security community to annotate malware families and build reference datasets, which is referred to as crowdsourcing malware family annotation. However, how to associate tags with their corresponding classes in chaotic malware labels (extract class-determined tags) and how to infer ground truth for weakly-tagged samples that hold controversial tags remain open problems. In this paper, we present a novel annotation pipeline to advance further, which includes an incremental parsing scheme and a maximum likelihood estimation scheme. The incremental parsing scheme treats behavior and platform tags as locators and achieves incremental parsing by introducing and iterating the following two algorithms: location first search, which hits family tags using locators, and co-occurrence first search, which finds new locators by family tags. The maximum likelihood estimating scheme models an engine’s ability to identify different families as a confusion matrix and introduces an expectation-maximization algorithm to estimate the matrix, as well as the unknown truth of samples. Experiments across four benchmark datasets indicate that our pipeline outperforms existing work, improving label-level parsing accuracy by an average of 29%, and improving inferring accuracy on weakly-tagged samples by an average of 9%. Our pipeline decouples parsing and inferring, which would pave the way for research on crowdsourcing malware family annotation.

Graph neural networks (GNNs) have transformed network analysis, leading to state-of-the-art performance across a variety of tasks. Especially, GNNs are increasingly been employed as detection tools in the AIoT environment in various security applications. However, GNNs have also been shown vulnerable to adversarial graph perturbation. We present the first approach for certifying robustness of general GNNs against attacks that add or remove graph edges either at training or prediction time. Extensive experiments demonstrate that our approach significantly outperforms prior art in certified robust predictions. In addition, we show that a noncertified adaptation of our method exhibits significantly better robust accuracy against state-of-the-art attacks that past approaches. Thus, we achieve both the best certified bounds and best practical robustness of GNNs to structural attacks to date.

Centrality measures can rank nodes in a social network according to their importance. However, in many cases, a node may want to avoid being highly ranked by such measures, e.g., as is the case with terrorist networks. In this work, we study a confrontation between the seeker—the party analyzing a social network using centrality measures—and the evader—a node attempting to decrease its ranking according to such measures. We analyze the possible outcomes of modifying, i.e., adding or removing, a single edge by the evader, showing that even without complete knowledge about the network, the effects of the modification on the evader's ranking can often be predicted. We study the computational complexity of finding a set of modifications that reduce the evader's centrality ranking in an optimal way, proving that these decision problems are NP-complete. Moreover, we provide a 2-approximation for the degree centrality, and logarithmic approximation boundaries for the closeness and betweenness centralities. Finally, we define and investigate a Stackelberg game between the seeker and the evader, providing a Mixed Integer Linear Programming formulation of finding an equilibrium. Altogether, we provide a thorough analysis of the strategic aspects of hiding from centrality measures in social networks.

Graph-based Anomaly Detection (GAD) is becoming prevalent due to the powerful representation abilities of graphs as well as recent advances in graph mining techniques. These GAD tools, however, expose a new attacking surface, ironically due to their unique advantage of being able to exploit the relations among data. That is, attackers now can manipulate those relations (i.e., the structure of the graph) to allow some target nodes to evade detection. In this paper, we exploit this vulnerability by designing a new type of targeted structural poisoning attacks to a representative regression-based GAD system termed OddBall. Specifically, we formulate the attack against OddBall as a bi-level optimization problem, where the key technical challenge is to efficiently solve the problem in a discrete domain. We propose a novel attack method termed BinarizedAttack based on gradient descent. Comparing to prior arts, BinarizedAttack can better use the gradient information, making it particularly suitable for solving combinatorial optimization problems. Furthermore, we investigate the attack transferability of BinarizedAttack by employing it to attack other representation-learning-based GAD systems. Our comprehensive experiments demonstrate that BinarizedAttack is very effective in enabling target nodes to evade graph-based anomaly detection tools with limited attacker's budget, and in the black-box transfer attack setting, BinarizedAttack is also tested effective and in particular, can significantly change the node embeddings learned by the GAD systems. Our research thus opens the door to studying a new type of attack against security analytic tools that rely on graph data.

Malware detection techniques achieve great success with deeper insight into the semantics of malware. Among existing detection techniques, function call graph (FCG) based methods achieve promising performance due to their prominent representations of malware's functionalities. Meanwhile, recent adversarial attacks not only perturb feature vectors to deceive classifiers (i.e., feature-space attacks) but also investigate how to generate real evasive malware (i.e., problem-space attacks). However, existing problem-space attacks are limited due to their inconsistent transformations between feature space and problem space.

In this paper, we present a computational analysis of the problem of attacking sign prediction, whereby the aim of the attacker (a network member) is to hide from the defender (an analyst) the signs of a target set of links by removing the signs of some other, non-target, links. The problem turns out to be NP-hard if either local or global similarity measures are used for sign prediction. We propose a heuristic algorithm and test its effectiveness on several real-life and synthetic datasets.

Computation outsourcing is an integral part of cloud computing. It enables end-users to outsource their computational tasks to the cloud and utilize the shared cloud resources in a pay-per-use manner. However, once the tasks are outsourced, the end-users will lose control of their data, which may result in severe security issues especially when the data is sensitive. To address this problem, secure outsourcing mechanisms have been proposed to ensure security of the end-users' outsourced data. In this paper, we investigate outsourcing of general computational problems which constitute the mathematical basics for problems emerged from various fields such as engineering and finance. To be specific, we propose affine mapping based schemes for the problem transformation and outsourcing so that the cloud is unable to learn any key information from the transformed problem. Meanwhile, the overhead for the transformation is limited to an acceptable level compared to the computational savings introduced by the outsourcing itself. Furthermore, we develop cost-aware schemes to balance the trade-offs between end-users' various security demands and computational overhead. We also propose a verification scheme to ensure that the end-users will always receive a valid solution from the cloud. Our extensive complexity and security analysis show that our proposed Cost-Aware Secure Outsourcing (CASO) scheme is both practical and effective.

Public goods games study the incentives of individuals to contribute to a public good and their behaviors in equilibria. In this paper, we examine a specific type of public goods game where players are networked and each has binary actions, and focus on the algorithmic aspects of such games. First, we show that checking the existence of a pure-strategy Nash equilibrium is NP-complete. We then identify tractable instances based on restrictions of either utility functions or of the underlying graphical structure. In certain cases, we also show that we can efficiently compute a socially optimal Nash equilibrium. Finally, we propose a heuristic approach for computing approximate equilibria in general binary networked public goods games, and experimentally demonstrate its effectiveness. Due to space limitation, some proofs are deferred to the extended version1.

Collective learning methods exploit relations among data points to enhance classification performance. However, such relations, represented as edges in the underlying graphical model, expose an extra attack surface to the adversaries. We study adversarial robustness of an important class of such graphical models, Associative Markov Networks (AMN), to structural attacks, where an attacker can modify the graph structure at test time. We formulate the task of learning a robust AMN classifier as a bi-level program, where the inner problem is a challenging non- linear integer program that computes optimal structural changes to the AMN. To address this technical challenge, we first relax the attacker problem, and then use duality to obtain a convex quadratic upper bound for the robust AMN problem. We then prove a bound on the quality of the resulting approximately optimal solutions, and experimentally demonstrate the efficacy of our approach. Finally, we apply our approach in a transductive learning setting, and show that robust AMN is much more robust than state-of-the-art deep learning methods, while sacrificing little in accuracy on non-adversarial data.

Cloud computing has changed the way enterprises store, access and share data. Big data sets are constantly being uploaded to the cloud and shared within a hierarchy of many different individuals with different access privileges. With more data storage needs turning over to the cloud, finding a secure and efficient data access structure has become a major research issue. In this paper, a Privilege-based Multilevel Organizational Data-sharing scheme (P-MOD) is proposed that incorporates a privilege-based access structure into an attribute-based encryption mechanism to handle the management and sharing of big data sets. Our proposed privilege-based access structure helps reduce the complexity of defining hierarchies as the number of users grows, which makes managing healthcare records using mobile healthcare devices feasible. It can also facilitate organizations in applying big data analytics to understand populations in a holistic way. Security analysis shows that P-MOD is secure against adaptively chosen plaintext attack assuming the DBDH assumption holds. The comprehensive performance and simulation analyses using the real U.S. Census Income data set demonstrate that P-MOD is more efficient in computational complexity and storage space than the existing schemes.

Link prediction is one of the fundamental problems in social network analysis. A common set of techniques for link prediction rely on similarity metrics which use the topology of the observed subnetwork to quantify the likelihood of unobserved links. Recently, similarity metrics for link prediction have been shown to be vulnerable to attacks whereby observations about the network are adversarially modified to hide target links. We propose a novel approach for increasing robustness of similarity-based link prediction by endowing the analyst with a restricted set of reliable queries which accurately measure the existence of queried links. The analyst aims to robustly predict a collection of possible links by optimally allocating the reliable queries. We formalize the analyst's problem as a Bayesian Stackelberg game in which they first choose the reliable queries, followed by an adversary who deletes a subset of links among the remaining (unreliable) queries by the analyst. The analyst in our model is uncertain about the particular target link the adversary attempts to hide, whereas the adversary has full information about the analyst and the network. Focusing on similarity metrics using only local information, we show that the problem is NP-Hard for both players, and devise two principled and efficient approaches for solving it approximately. Extensive experiments with real and synthetic networks demonstrate the effectiveness of our approach.

A lot of research has been focused on secure outsourcing of biometric identification in the context of cloud computing. In such schemes, both the encrypted biometric database and the identification process are outsourced to the cloud. The ultimate goal is to protect the security and privacy of the biometric database and the query templates. Security analysis shows that previous schemes suffer from the enrolment attack and unnecessarily expose more information than needed. In this paper, we propose a new secure outsourcing scheme aims at enhancing the security from these two aspects. First, besides all the attacks discussed in previous schemes, our proposed scheme is also secure against the enrolment attack. Second, we model the identification process as a fixed radius similarity query problem instead of the kNN search problem. Such a modelling is able to reduce the exposed information thus enhancing the privacy of the biometric database. Our comprehensive security and complexity analysis show that our scheme is able to enhance the security and privacy of the biometric database and query templates while maintaining the same computational savings from outsourcing.

The proliferation of online biometric authentication has necessitated security requirements of biometric templates. The existing secure biometric authentication schemes feature aserver-centricmodel, where a service provider maintains a biometric database and is fully responsible for the security of the templates. The end-users have to fully trust the server in storing, processing, and managing their private templates. As a result, the end-users’ templates could be compromised by outside attackers or even the service provider itself. In this paper, we propose auser-centricbiometric authentication scheme (PassBio) that enables end-users to encrypt their own templates with our proposed light-weighted encryption scheme. During authentication, all the templates remain encrypted such that the server will never see them directly. However, the server is able to determine whether the distance of two encrypted templates is within a pre-defined threshold. Our security analysis shows that no critical information of the templates can be revealed under both passive and active attacks. PassBio follows a “compute-then-compare” computational model over encrypted data. More specifically, our proposed threshold predicate encryption (TPE) scheme can encrypt two vectors x and y in such a manner that the inner product of x and y can be evaluated and compared to a pre-defined threshold. TPE guarantees that only the comparison result is revealed and no key information about x and y can be learned. Furthermore, we show that TPE can be utilized as a flexible building block to evaluate different distance metrics, such as Hamming distance and Euclidean distance over encrypted data. Such a compute-then-compare computational model, enabled by TPE, can be widely applied in many interesting applications, such as searching over encrypted data while ensuring data security and privacy.

The increasing interest in collecting and publishing large amounts of individuals' data as public for purposes such as medical research, market analysis, and economical measures has created major privacy concerns about individual's sensitive information. To deal with these concerns, many Privacy-Preserving Data Publishing (PPDP) techniques have been proposed in literature. However, they lack a proper privacy characterization and measurement. In this paper, we first present a novel multi-variable privacy characterization and quantification model. Based on this model, we are able to analyze the prior and posterior adversarial belief about attribute values of individuals. We can also analyze the sensitivity of any identifier in privacy characterization. Then, we show that privacy should not be measured based on one metric. We demonstrate how this could result in privacy misjudgment. We propose two different metrics for quantification of privacy leakage, distribution leakage, and entropy leakage. Using these metrics, we analyzed some of the most well-known PPDP techniques such as k-anonymity, l-diversity, and t-closeness. Based on our framework and the proposed metrics, we can determine that all the existing PPDP schemes have limitations in privacy characterization. Our proposed privacy characterization and measurement framework contributes to better understanding and evaluation of these techniques. Thus, this paper provides a foundation for design and analysis of PPDP schemes.

Discrete exponential operation, such as modular exponentiation and scalar multiplication on elliptic curves, is a basic operation of many public-key cryptosystems. However, the exponential operations are considered prohibitively expensive for resource-constrained mobile devices. In this paper, we address the problem of secure outsourcing of exponentiation operations to one single untrusted server. Our proposed secure outsourcing scheme for general exponential (ExpSOS) only requires a very limited number of modular multiplications at local mobile environment, and thus it can achieve significant computational performance gain. ExpSOS also provides a secure verification scheme with probability approximately 1 to ensure that the mobile end users can always receive valid results. The comprehensive analysis as well as the simulation results in real mobile device demonstrates that our proposed ExpSOS can significantly improve the existing schemes in efficiency, security, and result verifiability. We apply ExpSOS to securely outsource several cryptographic protocols to show that ExpSOS can be widely applied to many computation-intensive applications and achieve significant performance improvement.

This paper considers robust CDMA receiver design and jamming evaluation under disguised jamming, where the jammer generates a fake signal using the same spreading code, constellation and pulse shaping filter as that of the authorized signal. First, we analyze the performance of conventional CDMA systems under disguised jamming, and show that due to the symmetricity between the authorized signal and the jamming interference, the receiver cannot really distinguish the authorized signal from jamming, leading to complete communication failure. Second, by exploiting the small time difference between the authorized signal and the jamming interference, the conventional CDMA receiver can be redesigned to achieve robust performance under disguised jamming. More specifically, we propose to estimate the authorized signal, the phase and power level or range of the jamming interference by minimizing the MSE between the received signal and the jammed signal, which is the sum of the authorized signal and the disguised jamming. The effectiveness of the proposed approach is demonstrated through simulation examples. It is shown that with the proposed receiver design, the BER performance of CDMA can be improved significantly under disguised jamming, and an analytical evaluation about jamming can also be obtained.

Cloud computing enables resource-constrained end-users to outsource their computational tasks to the cloud in a flexible manner. One major concern of computation outsourcing is the security of the outsourced data as well as the results. In this paper, we propose a secure outsourcing scheme (SecMul) for one basic and expensive computation in cryptography, that is scalar multiplication of points on elliptic curves. The basic idea of the proposed SecMul is to transfer computations in a finite field to computations in a ring. The scheme is designed in such a way that without the secret key, it is computationally infeasible for the cloud to recover the input and the output. The proposed SecMul is highly efficient in that it enables the end-users to outsource a scalar multiplication at the cost of only a few multiplications. Especially, the performance gain of outsourcing is O(log(s)), where s is the multiplier. Our comprehensive security and complexity analysis demonstrate that the proposed SecMul scheme is both secure and efficient.

Linear computational problems emerge from various fields such as engineering and finance. Due to the large scale of these problems, they are often hard to be processed by resource-constrained devices. Thus, outsourcing becomes a natural solution. In this paper, we propose a Secure OutSourcing scheme (LinSOS) for Linear computations. The proposed scheme (LinSOS) is based on affine mapping and imposes only linear operations at local environment. As a result, the end-users can enjoy impressive computational gains from outsourcing. We also provide a verification scheme such that end-users can always receive valid results. Our extensive security and complexity analysis and performance comparison with existing schemes show that LinSOS is both secure and efficient.

Cloud computing enables data owners to outsource their computationally intensive tasks and store private data to the shared cloud. To enhance the security while preserving the flexibility of data sharing, Attribute Based Encryption (ABE) was introduced to provide a fine-grained access control. A key issue in ABE based systems is the high computational overhead, which could be prohibitive for resource constrained mobile devices. In this paper, we propose a scheme to securely and efficiently outsource the computationally intensive access control operations of ABE to the shared cloud, thus reliving the computational burden of mobile users which can greatly improve the battery lifetime. In a high level view, data owners only need to specify access policies on the encrypted data so that access control can be done automatically by the cloud. Our proposed scheme guarantees that it is computationally infeasible for the untrusted cloud to recover the encrypted file and that the cloud is enforced to complete the full functionality of access control, even in situations where the cloud may be compromised by malicious data users. Our theoretical analysis and experiment results both demonstrate that our scheme can achieve high performance gain for resource constrained mobile devices.

This paper considers robust code division multiple access (CDMA) system design and capacity analysis under disguised jamming, where the jammer generates a fake signal using the same spreading code, constellation, and pulse shaping filter as that of the authorized signal. Unlike Gaussian jamming, which is destructive only when jamming is dominant, disguised jamming can be devastating even if the jamming power is comparable to the signal power. In this paper, first, we analyze the performance of the conventional CDMA under disguised jamming, and show that due to the symmetricity between the authorized signal and the jamming interference, the receiver cannot really distinguish the authorized signal from jamming, leading to complete communication failure. Second, we propose to combat disguised jamming using secure scrambling. Instead of using conventional scrambling codes, we apply advanced encryption standard to generate the security-enhanced scrambling codes. Theoretical analysis based on the arbitrarily varying channel model shows that the capacity of conventional CDMA without secure scrambling under disguised jamming is actually zero; however, secure scrambling can break the symmetricity between the authorized signal and the jamming interference, and hence ensures positive channel capacity under disguised jamming. Numerical examples are provided to demonstrate the effectiveness of secure scrambling in combating disguised jamming.