The smoothing issue in graph learning leads to indistinguishable node representations, posing significant challenges for graph-related tasks. However, our experiments reveal that this problem can uncover underlying properties of node anomaly detection (NAD) that previous research has missed. We introduce Individual Smoothing Patterns (ISP) and Neighborhood Smoothing Patterns (NSP), which indicate that the representations of anomalous nodes are harder to smooth than those of normal ones. In addition, we explore the theoretical implications of these patterns, demonstrating the potential benefits of ISP and NSP for NAD tasks. Motivated by these findings, we propose SmoothGNN, a novel unsupervised NAD framework. First, we design a learning component to explicitly capture ISP for detecting node anomalies. Second, we design a spectral graph neural network to implicitly learn ISP to enhance detection. Third, we design an effective coefficient based on our findings that NSP can serve as coefficients for node representations, aiding in the identification of anomalous nodes. Furthermore, we devise a novel anomaly measure to calculate loss functions and anomalous scores for nodes, reflecting the properties of NAD using ISP and NSP. Extensive experiments on 9 real datasets show that SmoothGNN outperforms the best rival by an average of 14.66% in AUC and 7.28% in Average Precision, with 75x running time speedup, validating the effectiveness and efficiency of our framework. Our code is available at https://github.com/xydong127/SmoothGNN.
论文检索
输入标题、作者或关键词，从 447 篇学术成果中精准定位
Graph anomaly detection plays a crucial role in identifying nodes that deviate significantly from normal patterns within a graph, with applications spanning various domains such as detection of authorship fraud and rumor propagation. Traditional methods primarily focus on aggregating information from neighboring nodes and reconstructing the central node based on these aggregated features. The anomaly degree is then calculated by comparing the reconstructed features with the original ones. Despite their effectiveness, these methods face limitations due to the constraints of device performance and the need to protect user privacy. In reality, graph data is often partitioned and distributed across different local clients, which leads to isolated client subgraphs. This partitioning results in incomplete feature aggregation, as the connections between subgraphs are missing, ultimately reducing the performance of anomaly detection models. To overcome these challenges, a federated graph anomaly detection approach based on disentangled representation learning is proposed. This method separates node features into two distinct components: intrinsic features and subgraph style features. By identifying outliers within the subgraph style features, a set of pseudo-nodes is generated and shared across the entire graph. These pseudo-nodes simulate connections between otherwise isolated subgraphs, which enables more comprehensive aggregation of intrinsic features from neighboring nodes. In addition, conditional variational autoencoders (CVAE) are employed alongside contrastive learning strategies to alleviate class imbalance and achieve effective feature disentanglement. These techniques help ensure that anomalous nodes are detected more accurately despite the inherent challenges of federated graph systems. Extensive experiments conducted on six diverse datasets provide compelling evidence of the proposed method's superior performance in federated graph anomaly detection, highlighting its ability to effectively handle incomplete graph structures while maintaining data privacy.
Subgraph federated learning aims to collaboratively train a global model over distributed subgraphs stored in multiple local clients with strict privacy constraints, which is crucial to a wide range of applications such as healthcare, recommendation systems, and financial crime detection. With the increasing emphasis on the "right to be forgotten," the issue of machine unlearning of subgraph federated models has gained significant importance. However, existing federated unlearning approaches largely focused on unstructured data, overlooking the impact of structural dependency and cross-client interferences in graph-based data. To this end, in this paper, we propose ReGEnUnlearn, a subgraph federated unlearning framework for efficient and comprehensive unlearning of multiple target clients. Specifically, we first propose the Reinforced Federated Policy Sampler (RFPS) to learn optimal sampling strategies that minimize the interference among cross-client subgraphs. By interacting with the federated graph sampling environment, the agent learns to selectively forget an optimal subgraph of target clients, thus preserving the global model utility. Moreover, we propose the Parameter-free Graph Prompt Knowledge Distillation (PGPKD) module, which retains the unique graph knowledge contributed by the target clients, thereby facilitating comprehensive unlearning via a tailored gradient ascent objective. Extensive experiments in various federated settings demonstrate ReGEnUnlearn's superiority over existing federated unlearning methods, offering a speedup of 3.6× to 9× compared to traditional retraining while maintaining model utility within a range of 100%-102%.
Heterophilic Graph Neural Networks (HGNNs) have shown promising results for semi-supervised learning tasks on graphs. Notably, most real-world heterophilic graphs are composed of a mixture of nodes with different neighbor patterns, exhibiting local node-level homophilic and heterophilic structures. However, existing works are only devoted to designing better unified HGNN backbones for node classification tasks on heterophilic and homophilic graphs simultaneously, and their analyses of HGNN performance concerning nodes are only based on the determined data distribution without exploring the effect caused by the difference of structural pattern between training and testing nodes. How to learn invariant node representations on heterophilic graphs to handle this structure difference or distribution shifts remains unexplored. In this paper, we first discuss the limitations of previous graph-based invariant learning methods in addressing the heterophilic graph structure distribution shifts from the perspective of data augmentation. Then, we propose HEI, a framework capable of generating invariant node representations through incorporating Heterophily information, the node's estimated neighbor pattern, to infer latent Environments without augmentation, which are then used for Invariant prediction. We provide detailed theoretical guarantees to clarify the reasonability of HEI. Extensive experiments on various benchmarks and backbones can also demonstrate the effectiveness and robustness of our method compared with existing state-of-the-art baselines.
Facility location problems on graphs are ubiquitous in the real world and hold significant importance, yet their resolution is often impeded by NP-hardness. MIP solvers can find the optimal solutions but fail to handle large instances, while algorithm efficiency has a higher priority in cases of emergency. Recently, machine learning methods have been proposed to tackle such classical problems with fast inference, but they are limited to the myopic constructive pattern and only consider simple cases in Euclidean space. This paper introduces a unified and generalizable approach to tackle facility location problems on weighted graphs with deep reinforcement learning, demonstrating a keen awareness of complex graph structures. Striking a harmonious balance between solution quality and running time, our method stands out with superior efficiency and steady performance. Our model trained on small graphs is highly scalable and consistently generates high-quality solutions, achieving a speedup of more than 2000 times to Gurobi on instances with 1000 nodes. The experiments on Shanghai road networks further demonstrate its practical value in solving real-world problems. The source codes are available at https://github.com/AryaGuo/PPO-swap.
FG-CIBGC: A Unified Framework for Fine-Grained and Class-Incremental Behavior Graph Classification
PDF ↗Learning-based Behavior Graph Classification (BGC) is widely used in Internet infrastructure for partitioning and identifying similar behavior graphs, yet its real-world application faces notable challenges. The challenges are: (i) fine-grained emerging behavior graphs, and (ii) incremental model adaptations. To tackle these issues, we propose to (i) mine semantics in multi-source logs using Large Language Models (LLMs) under In-Context Learning (ICL), and (ii) bridge the gap between Out-Of-Distribution (OOD) detection and class-incremental graph learning. Based on these ideas, we develop the first unified framework termed as Fine-Grained and Class-Incremental Behavior Graph Classification (FG-CIBGC ). It consists of two novel modules, i.e., gPartition and gAdapt, that are used for partitioning fine-grained graphs and performing unknown class detection and adaptation, respectively. To validate FG-CIBGC, we introduce a new benchmark, including a 4,992-graph, 32-class dataset from 8 attack scenarios and a novel Edge Intersection over Union (EIoU) metric. Extensive experiments show FG-CIBGC outperforms baselines on fine-grained class-incremental BGC task and generates behavior graphs which enhance downstream tasks.
The foundation model has heralded a new era in artificial intelligence, pretraining a single model to offer cross-domain transferability on different datasets. Graph neural networks excel at learning graph data, the omnipresent non-Euclidean structure, but often lack the generalization capacity. Hence, graph foundation model is drawing increasing attention, and recent efforts have been made to leverage Large Language Models. On the one hand, existing studies primarily focus on text-attributed graphs, while a wider range of real graphs do not contain fruitful textual attributes. On the other hand, the sequential graph description tailored for the Large Language Model neglects the structural complexity, which is a predominant characteristic of the graph. Such limitations motivate an important question: Can we go beyond Large Language Models, and pretrain a universal model to learn the structural knowledge for any graph? The answer in the language or vision domain is a shared vocabulary. We observe the fact that there also exist shared substructures underlying graph domain, and thereby open a new opportunity of graph foundation model with structural vocabulary. The key innovation is the discovery of a simple yet effective structural vocabulary of trees and cycles, and we explore its inherent connection to Riemannian geometry. Herein, we present a universal pretraining model, RiemannGFM. Concretely, we first construct a novel product bundle to incorporate the diverse geometries of the vocabulary. Then, on this constructed space, we stack Riemannian layers where the structural vocabulary, regard- less of specific graph, is learned in Riemannian manifold offering cross-domain transferability. Extensive experiments show the effectiveness of RiemannGFM on a diversity of real graphs.
SAMGPT: Text-free Graph Foundation Model for Multi-domain Pre-training and Cross-domain Adaptation
PDF ↗Graphs are able to model interconnected entities in many online services, supporting a wide range of applications on the Web. This raises an important question: How can we train a graph foundational model on multiple source domains and adapt to an unseen target domain? A major obstacle is that graphs from different domains often exhibit divergent characteristics. Some studies leverage large language models to align multiple domains based on textual descriptions associated with the graphs, limiting their applicability to text-attributed graphs. For text-free graphs, a few recent works attempt to align different feature distributions across domains, while generally neglecting structural differences. In this work, we propose a novel Structure Alignment framework for text-free Multi-domain Graph Pre-Training and cross-domain adaptation (SAMGPT). It is designed to learn multi-domain knowledge from graphs originating in multiple source domains, which can then be adapted to address applications in an unseen target domain. Specifically, we introduce a set of structure tokens to harmonize structure-based aggregation across source domains during the pre-training phase. Next, for cross-domain adaptation, we design dual prompts, namely, holistic prompts and specific prompts, which adapt unified multi-domain structural knowledge and fine-grained, domain-specific information, respectively, to a target domain. Finally, we conduct comprehensive experiments on seven public datasets to evaluate and analyze the effectiveness of SAMGPT.
Graph Contrastive Learning (GCL) is a widely adopted approach in self-supervised graph representation learning, applying contrastive objectives to produce effective representations. However, current GCL methods primarily focus on capturing implicit semantic relationships, often overlooking the structural commonsense embedded within the graph's structure and attributes, which contains underlying knowledge crucial for effective representation learning. Due to the lack of explicit information and clear guidance in general graph, identifying and integrating such structural commonsense in GCL poses a significant challenge. To address this gap, we propose a novel framework called Structural Commonsense Unveiling in Graph Contrastive Learning (Str-GCL). Str-GCL leverages first-order logic rules to represent structural commonsense and explicitly integrates them into the GCL framework. It introduces topological and attribute-based rules without altering the original graph and employs a representation alignment mechanism to guide the encoder in effectively capturing this commonsense. To the best of our knowledge, this is the first attempt to directly incorporate structural commonsense into GCL. Extensive experiments demonstrate that Str-GCL outperforms existing GCL methods, providing a new perspective on leveraging structural commonsense in graph representation learning.
Broken Access: On the Challenges of Screen Reader Assisted Two-Factor and Passwordless Authentication
PDF ↗In today's technology-driven world, web services have opened up new opportunities for blind and visually impaired people to interact independently. Securing interactions with these services is crucial; however, currently deployed methods of web authentication mainly concentrate on sighted users, overlooking the specific needs of the blind and visually impaired community. In this paper, we address this critical gap by investigating the security and accessibility aspects of these web authentication methods when adopted by blind and visually impaired users. We model web authentication for such users as screen reader assisted authentication and introduce an evaluation framework called Authentication Workflows Accessibility Review and Evaluation (AWARE). Using AWARE, we then systematically assessed popular PC-based and smartphone-based screen readers against different types of deployed web authentication methods, including variants of 2FA and passwordless schemes, to simulate real-world scenarios for blind and visually impaired individuals. We analyzed these screen reader assisted authentication interactions with authentication methods in three settings: using a terminal (PC) with screen readers, a combination of the terminal (PC) and smartphone with screen readers, and smartphones with integrated screen readers. The results of our study underscore significant weaknesses in all of our observed screen reader assisted authentication scenarios for real-life authentication methods. These weaknesses, encompassing specific accessibility issues caused by imprecise screen reader instructions, highlight vulnerability concerning observed scenarios for both real-world and research literature based attacks, including phishing, concurrency, fatigue, cross-service, and shoulder surfing. Broadly, our AWARE framework can be used by authentication system designers as a precursor to user studies which are typically time-consuming and tedious to perform, independently allowing to unfold security and accessibility problems early which designers can address prior to full-fledged user testing of more isolated issues.
In this paper, we systematically evaluate the effectiveness of existing tools for the dynamic security analysis of client-side JavaScript, focusing in particular on information flow control. Each tool is evaluated in terms of: (i) compatibility, i.e., the ability to process and analyze existing scripts without breaking; (ii) transparency, i.e., the ability to preserve the original script semantics when security enforcement is not necessary; (iii) coverage, i.e., the effectiveness in terms of number of detected information flows; (iv) performance, i.e., the computational overhead introduced by the analysis. Our investigation shows that most of the existing analysis tools are incompatible with the modern Web and the compatibility issues affecting them are not easily fixed. Moreover, transparency issues abound and make us question analysis correctness. This is also confirmed by our coverage evaluation, showing that some tools are unable to detect any information flow on real-world websites, while the remaining tools report significantly different outputs. Finally, we observe that the computational overhead of analysis tools may be significant and can exceed 30x. In the end, out of all the evaluated tools, just one of them (Project Foxhound) is effective enough for practical adoption at scale.
Browser APIs such as WebHID, WebUSB, Web Serial, and Web MIDI enable web applications to interact directly with external devices. The support of such APIs in Chromium-based browsers, such as Chrome and Edge, radically changes the threat model for peripherals and increases the attack surface. In the past, devices could assume a trusted host, i.e., the operating system. Now, the host is a potentially malicious website and cannot be trusted. We show how this changed threat model leads to security and privacy problems, up to a complete compromise of the operating system. While the API specifications list initial security considerations, they shift the responsibility to (unprepared) device vendors. We systematically analyze the security implications of external devices exposed by such new APIs. By reverse-engineering peripheral devices of several popular widespread vendors, we show that many vendors allow controlling devices via Web APIs up to reprogramming or even fully replacing the firmware. Consequently, web attackers can reprogram devices with malicious payloads and custom firmware without requiring any physical interaction. To demonstrate the security implications, we build several full-chain exploits, leading to arbitrary code execution on the victim system, circumventing the browser sandbox. Our research shows that browser security should not rely on the secure implementation of third-party hardware.
HOLMES & WATSON: A Robust and Lightweight HTTPS Website Fingerprinting through HTTP Version Parallelism
PDF ↗Website Fingerprinting (WF) is a traffic analysis technique that aims to identify websites visited by users through the analysis of encrypted traffic patterns. Existing approaches often exhibit limited robustness against network variability and concept drift, resulting in significant performance degradation under real-world HTTPS conditions. Moreover, these methods typically require large-scale training datasets and substantial computational resources, which further increases the complexity of deployment. In this paper, we propose HOLMES, a novel approach that exploits HTTP version parallelism to extract enhanced application-layer features. These features, including the number of web resources transmitting in various HTTP versions, expose up to 4.28 bits of information-surpassing 98% of previously reported features and demonstrate increased stability across varying network conditions. Complementary to this, we introduce WATSON, a lightweight classification method based on lazy learning, which substantially reduces the dependency on large training datasets. To further enhance the identification accuracy, we incorporate two fingerprint-specific distance metrics that ensure high intra-class similarity. Our experimental evaluation demonstrates that HOLMES & WATSON significantly enhance both robustness and efficiency, achieving an average accuracy of 87.7% with only a single sample per website, marking an improvement of over 15% compared to state-of-the-art methods.
Beyond Single Tabs: A Transformative Few-Shot Approach to Multi-Tab Website Fingerprinting Attacks
PDF ↗Website Fingerprinting (WF) attacks allow passive eavesdroppers to deduce the websites a user visits by analyzing encrypted traffic, threatening user privacy. While current WF attacks achieve high accuracy, they typically assume single-tab browsing, which is unrealistic as users often open multiple tabs, creating mixed traffic. Existing multi-tab WF approaches require large datasets and frequent retraining due to evolving website content, limiting their practicality. In this paper, we introduce Few-shot Multi-tab Website Fingerprinting (FMWF), a novel approach designed to address the limitations of existing multi-tab WF attacks. FMWF directly tackles the challenges of mixed, overlapping traffic traces generated from multi-tab browsing, leveraging two key innovations: (1) an advanced data augmentation technique that synthesizes realistic multi-tab traffic sequences from easily collected single-tab traces, thereby dramatically reducing the need for large-scale real-world traffic data; and (2) a powerful fine-tuning algorithm based on transfer learning that adapts pre-trained models to new, multi-tab environments with minimal additional data. This two-stage framework enables FMWF to capture the complex effectively, overlapping traffic patterns inherent in multi-tab browsing while maintaining a high level of flexibility and significantly lowering computational and data collection burdens. Our experiments, conducted using real traffic traces collected from three widely-used browsers-Microsoft Edge, Google Chrome, and Tor Browser-highlight the superior performance of FMWF in both closed-world and open-world scenarios. Notably, FMWF achieves a minimum 12.3% improvement in accuracy compared to ARES (SP'23) [7], TMWF (CCS'23) [13], and BAPM (ACSAC'21) [10] in the open-world scenario. The code with related datasets is available at https://github.com/WW-Meng/FMWF.
The Automatic Certificate Management Environment (ACME) protocol automates the issuance and renewal of secure socket layer certificates, simplifying the management of large-scale certificate deployments. To reduce the load on Certificate Authority (CA) servers, ACME employs a caching mechanism that stores domain validation (DV) results for 30 days. However, this mechanism allows attackers to reuse previously authorized results, potentially bypassing the DV process. In this paper, we introduce the ACME Authz Cache Attack, whereby an attacker can obtain fraudulent certificates without domain control. We demonstrate that even the prominent CA, Let's Encrypt, is vulnerable to this attack. To mitigate this, we propose ACME++, an enhanced protocol that binds the client's IP address and a unique identifier to the ACME account, ensuring secure authorization for each new client and effectively preventing the ACME Authz Cache Attack. Our implementation of ACME++ shows that it introduces little overhead to the CA server.
STGAN: Detecting Host Threats via Fusion of Spatial-Temporal Features in Host Provenance Graphs
PDF ↗As the complexity and frequency of cyberattacks, such as Advanced Persistent Threats (APTs) and ransomware, continue to escalate, traditional anomaly detection methods have proven inadequate in addressing these sophisticated, multi-faceted threats. Recently, Host Provenance Graphs (HPGs) have played a crucial role in analyzing system-level interactions, detecting anomalous behaviors, and tracing attack chains. However, existing provenance-based detection methods primarily rely on single-dimensional feature analysis, which fails to capture the dynamic and multi-dimensional patterns of modern APT attacks, resulting in insufficient detection performance. To overcome this limitation, we introduce STGAN, a model that integrates spatial-temporal graphs into host provenance graph modeling. STGAN applies temporal and spatial encoding to dynamic provenance graphs to extract temporal, spatial, and semantic features, constructing a comprehensive feature representation. This representation is further fused and enhanced using a multi-head self-attention mechanism, followed by anomaly detection. Through extensive evaluations on three widely-used provenance graph datasets, we demonstrate that our approach consistently outperforms current state-of-the-art techniques in terms of detection performance. Additionally, we contribute to the research community by releasing our datasets and code, facilitating further exploration and validation.
Governments and regulatory bodies have recognized investment scams as a prevalent form of cryptocurrency fraud. These scams typically use professional-looking websites to lure unsuspecting victims with promises of unrealistically high returns. In this paper, we introduce Crimson, a distributed system designed to continuously detect cryptocurrency investment scam websites as they are created in the wild. During the first 8 months of 2024, Crimson processed approximately 6 billion domain names and classified 43,572 unique cryptocurrency investment scam websites in real-time. Beyond detection, we provide insights into the design and infrastructure of these websites that can help users recognize scam patterns and assist hosting providers in detecting and blocking such sites. Furthermore, we investigate the inclusion of our detected scam websites in block-lists used by popular web browsers and applications, finding that the vast majority of these websites were absent. On the financial side, by analyzing the transactions incoming to scammer wallets on 6.7% of the sites detected by Crimson, we observe an estimated lower bound of 2.04M USD in losses due to cryptocurrency investment scams.
Serial Scammers and Attack of the Clones: How Scammers Coordinate Multiple Rug Pulls on Decentralized Exchanges
PDF ↗We explored the ubiquitous phenomenon of serial scammers, each of whom deployed dozens to thousands of addresses to conduct a series of similar Rug Pulls on popular decentralized exchanges. We first constructed two datasets of around 384,000 scammer addresses behind all one-day Simple Rug Pulls on Uniswap (Ethereum) and Pancakeswap (BSC), and identified distinctive scam patterns including star, chain, and major (scam-funding) flow. These patterns, which collectively cover about 40% of all scammer addresses in our datasets, reveal typical ways scammers run multiple Rug Pulls and organize the money flow among different addresses. We then studied the more general concept of scam cluster, which comprises scammer addresses linked together via direct ETH/BNB transfers or behind the same scam pools. We found that scam token contracts are highly similar within each cluster (average similarities >70%) and dissimilar across different clusters (average similarities <30%), corroborating our view that each cluster belongs to the same scammer/scam organization. Lastly, we analyze the scam profit of individual scam pools and clusters, employing a novel cluster-aware profit formula that takes into account the important role of wash traders. The analysis shows that the existing formula inflates the profit by at least 35% on Uniswap and 24% on Pancakeswap.
With the development of blockchain technology, crypto gambling has gained popularity due to its high level of anonymity. However, similar to traditional casinos, crypto casinos are controlled by a few internal Delegatees, making it impossible for them to achieve complete transparency and fairness. These delegatees are hidden among gamblers and are difficult to identify and distinguish in anonymous and large-scale blockchain transaction networks. This paper proposes an unsupervised dual-stage role identification method to adaptively identify key roles and hidden delegatees in label-sparse crypto casinos. Specifically, inspired by voting-style transaction patterns, we propose a novel voting influence metric for key node identification. This metric is based on one-dimensional structural entropy to capture global dissemination capability. Subsequently, we develop a multi-view graph neural network framework enhanced with two-dimensional global structural entropy minimization and self-supervised contrastive learning to improve the robustness and interpretability of hidden role partitioning. Experiments on real-world cases of the most mainstream blockchains-Ethereum, TRON, and Arbitrum-demonstrate that our proposed method effectively reveals distinct role compositions and collusion patterns, distinguishing between gamblers and delegatees. Our results achieve a higher match with identities confirmed by judicial authorities than existing methods, indicating the effectiveness and generalizability of our approach in enhancing security and regulation oversight.
Harmful Terms and Where to Find Them: Measuring and Modeling Unfavorable Financial Terms and Conditions in Shopping Websites at Scale
PDF ↗Terms and conditions for online shopping websites often contain terms that can have significant financial consequences for customers. Despite their impact, there is currently no comprehensive understanding of the types and potential risks associated with unfavorable financial terms. Furthermore, there are no publicly available detection systems or datasets to systematically identify or mitigate these terms. In this paper, we take the first steps toward solving this problem with three key contributions. First, we introduce TermMiner, an automated data collection and topic modeling pipeline to understand the landscape of unfavorable financial terms. Second, we create ShopTC-100K, a dataset of terms and conditions from shopping websites in the Tranco top 100K list, comprising 1.8 million terms from 8,251 websites. Consequently, we develop a taxonomy of 22 types from 4 categories of unfavorable financial terms---spanning purchase, post-purchase, account termination, and legal aspects. Third, we build TermLens, an automated detector that uses Large Language Models (LLMs) to identify unfavorable financial terms. Fine-tuned on an annotated dataset, TermLens achieves an F1 score of 94.6% and a false positive rate of 2.3% using GPT-4o. When applied to shopping websites from the Tranco top 100K, we find that 42.06% of these sites contain at least one unfavorable financial term, with such terms being more prevalent on less popular websites. Case studies further highlight the financial risks and customer dissatisfaction associated with unfavorable financial terms, as well as the limitations of existing ecosystem defenses.