Exploring Motif-based Heterogeneous Graph Learning for ReDoS Detection

Regular expressions (regexes) frequently exhibit super-linear worst-case behavior in regex engines, exposing software to Regex Denial-of-Service (ReDoS) attacks. Detecting such vulnerabilities is challenging, especially for extended features such as lookarounds and backreferences: existing static approaches are efficient but often lack support for extended features, whereas dynamic and hybrid approaches reduce false positives by executing regex matching on real engines, but incur high runtime overhead. To address this trade-off, we propose ReDoS-MotifGNN (RMGNN), a motif-based graph learning framework for ReDoS detection that leverages the low inference latency of graph neural networks (GNNs). RMGNN converts regexes into Heterogeneous Regex Graphs (HRGs) and encodes three ReDoS-related motifs into HRGs to incorporate domain priors, while preserving the syntactic structure and extended features of the input regex. Furthermore, it applies heterogeneous propagation with kernel-guided motif learning to capture multi-scale semantics, which are fused via residual cross-attention for robust prediction. Comprehensive evaluation on four real-world datasets (over 317k regexes) demonstrates that RMGNN outperforms six state-of-the-art baselines in F1-score and achieves an average 244$\times$ speedup over the top F1-performing baseline.

Regular expressions (regexes) are widely used in real-world software to search, validate, and filter text. However, vulnerable regexes may exhibit super-linear worst-case behavior in regex engines when matched against carefully crafted inputs, leading to Regex Denial-of-Service (ReDoS) attacks. We propose an effective graph-based learning method to efficiently identify potentially vulnerable regexes. Our paper presents ReDoS-MotifGNN, which converts real-world regexes into Heterogeneous Regex Graphs (HRGs). This representation preserves the structure of real-world regexes, including extended features commonly used in practice. To incorporate domain knowledge, we further enrich these graphs with ReDoS-related prior information, allowing the model to consider high-level vulnerable structures during learning. The model then learns the HRG representations by jointly modeling local structural information and high-level vulnerable structures through attention-based fusion. Our findings demonstrate the potential of graph-based learning methods for ReDoS detection. They suggest that structure-aware learning can effectively model the structural characteristics of vulnerable real-world regexes, offering a practical way to detect ReDoS vulnerabilities in real-time scenarios.