ProvCreator: Synthesizing Graph Data with Text Attributes

Below, we address the specific points raised and clarify our design choices. We are currently running extended evaluations.

1. Motivation for Balancing Classification Training Set: By balancing the training set distribution with synthetic data, we avoid overemphasizing the prior distribution of class labels in the training set. In our classification evaluation, we show that balancing the training distribution with synthetic data improves classification accuracy on a test set that follows the original distribution.

2. Semantic Correctness: We recognize both the necessity and difficulty of measuring the semantic validity of synthetic provenance graphs. While we cannot guarantee the semantic validity for the generated graphs, we can account for simple violations, such as semantically invalid edges (e.g. a file reading another file), which are discarded after generation. Similarly, obviously invalid generated attributes are also removed and replaced with a fallback value. To estimate the semantic validity of the generated node attributes, we developed metrics that incorporate domain-specific notions of correctness, accounting for varying program locations, random high-numbered ports, and random temporary file names. Despite our evaluation efforts, we acknowledge that we are unable to enumerate and measure all the possible ways a graph could become semantically invalid. Still, we observe that the inclusion of synthetic training data improves program classification F1 scores by 16%, indicating that the synthetic graphs are useful.

3. Malware Detection Task Clarification: The malware detection task is unsupervised binary classification between provenance graphs centered on benign and malicious SVCHOST.EXE processes. The training set consists entirely of benign graphs, and the test set consists of an equal number of benign and malicious graphs. We use FLASH (Rehman et al., 2024) as our detection system, which trains a small GCN model to perform node type classification, then compares the node type classification error rate against a threshold to determine if a graph is benign or malicious. We acknowledge that the baseline performance was too strong on the simple malware cases in our evaluation, and we are currently evaluating more diverse program and malware samples.

4. Synthetic Graph Generation: Building off of GDSS (Jo et al., 2022), ProvCreator generates synthetic graphs by iteratively diffusing from random noise. This approach is distinct from variant generation, where transformations are iteratively applied to a real seed graph. While both synthetic graph generation and variant-based graph augmentation are effective methods for improving the performance of graph learning models, we focus on graph synthesis in anticipation of long-term benefits of generative modeling research. As for the evolutionary algorithmic approach, deep learning based approaches have significant advantages in computational cost during the generation phase, and conditional generation improves control over the generated graphs.

5. Adjacency Matrix Clarification: The real number relaxation is necessary for GDSS because the diffusion step operates on the adjacency matrix, requiring it to be differentiable. There do exist other methods that use sparse diffusion steps and do not require the real number relaxation, such as [1]. Intuitively, a real number adjacency value can be interpreted as the probability of the existence of an edge. For example, for a process node $p$ and file node $f$, the entry $A[f, p, read] = 0.98$ indicates that $p$ has read $f$ with high probability.

6. Domain Generalization: We frame ProvCreator in the system provenance domain because that is our area of expertise. While our technique does not make domain-specific assumptions, we wish to avoid overclaiming domain generalization that is not explored in our evaluation. Future works may apply ProvCreator to other graph domains.

[1] Sparse Training of Discrete Diffusion Models for Graph Generation (https://arxiv.org/abs/2311.02142)

Below, we address the specific points raised and clarify our design choices. We are currently running extended evaluations.

1. Pipeline Scalability and Overhead: To address concerns about efficiency and resource consumption during training, we outline the computational overhead of our project pipeline as follows:

• Data Pre-processing: Extracting ~120k training graphs takes ~48 hours, performance is limited by storage speed
• Structural Model Training: ~48 hours on 4x 4090
• Attribute Model Training: ~150 hours on 8x A6000
• Generation: ~2 minutes per graph on 4x 4090

2. Below are the detailed input and output of each stage mentioned in Figure 2:

• Graph label: The one-hot encoded labels used in our models are shown in Tables 5 and 6 in Appendix A.1.

• Graph Structure Generator: The graph structure generator takes the POI process’s command with arguments as a condition prompt to generate a synthetic graph structure with only node type information. Examples of generated structure have been added to appendix section A.4.

• Graph Encoder: The graph encoder takes a graph structure as input and creates a 512-wide embedding of for each node. These embeddings will be connected to the input to the transformer model, enabling joint training (Algorithm 1). The graph encoder is trained on real graph structures, but during inference it uses generated graph structures.

• Transformer: For each node, the transformer model takes the node embedding, graph label, node type, and attribute name as input, and outputs an attribute value. Examples of generated structure have been added to appendix section A.4.

3. Our malware detection experiments use an unsupervised anomaly detection approach. While increasing training data variation with synthetic data typically causes anomaly detection models to become more permissive, our baseline detector was too strong, leaving no room to reduce false positives. We are evaluating more challenging malware types to better showcase the value of synthetic provenance data.

Below, we address the specific points raised and clarify our design choices. We are currently running extended evaluations.

1. Text-based Attributes Conditioned on Graph Structure: Node attributes are related to the graph’s structure in many domains. For instance, in biology, text-based attributes describing molecular interactions or protein functions can be generated from molecular interaction networks. Similarly, in knowledge graphs, user-item node attributes significantly influence recommendation decisions.

2. Pipeline Scalability and Overhead: The computational overhead of the project pipeline is structured as follows:

• Data Pre-processing: Extracting ~120k training graphs takes ~48 hours, performance is limited by storage speed
• Structural Model Training: ~48 hours on 4x 4090
• Attribute Model Training: ~150 hours on 8x A6000
• Generation: ~2 minutes per graph on 4x 4090

3. Dynamic Behavior and Temporal Modeling: Provenance graphs capture dynamic runtime behaviors by summarizing low-level system logs, using directed edges to represent information flows between system resources. Temporal modeling may improve the alignment between the graph synthesis framework and the process of capturing real provenance graphs, representing an interesting direction for future work.

4. Dynamic Node Attributes in ProvCreator: Because our evaluation focuses on the system provenance domain, where node attribute sets are determined by the node type, we do not have a practical downstream application for dynamically determined node attribute sets. While ProvCreator’s design is domain-agnostic and dynamic node attribute sets may be important in some domains, this capability is not a core contribution of ProvCreator. Evaluating synthetic graphs with dynamically determined node attribute sets may be explored in future works.

5. Comparison with GDSS: Our work improves GDSS in two key aspects: (1) Backbone Improvements: We leverage a powerful GNN model, GraphTransformer, to improve the representation and generation process; (2) Conditional Generation: We added conditional generation capability so we can specify the type of the graph we want to generate. The types are defined based on the command line of the POI process, detailed in Appendix A.1. These enhancements allow us to address limitations in GDSS while achieving more robust conditioning and attribute synthesis.

Below, we address each of the points raised and provide clarifications regarding our design choices. We also outline ongoing and future efforts to enhance our evaluation and provide more comprehensive evidence.

1. Motivation for Combining Graph Structure and Attribute Generation: The core motivation of this work is to create realistic synthetic system provenance graphs. By combining graph structure with attribute generation, we capture dependencies between node attributes (e.g., program names) and graph structure (e.g., program actions). This way, we enhance the fidelity of the synthetic provenance graphs and improve their applicability to downstream detection tasks.

2. Insufficient Detail on Model Architecture and Joint Loss Function: The detailed model architecture has been added to appendix section A.3. Full source code is also available in anonymous repo https://anonymous.4open.science/r/provcreator-aio-4F83 and will be open sourced. The loss function for joint optimization is cross entropy for masked language modeling (sum of token level cross-entropy while ignoring masked tokens).

3. Evaluation of Baseline Graph Synthesis Techniques: We selected GDSS (Jo et al., 2022) as our structural generation foundation because it has already been shown to beat existing structure-only approaches, such as EDP-GNN and GraphEBM. The core contribution of ProvCreator is the addition of structure-aware textual node attribute generation. The choice of graph structure generation method is orthogonal to our primary contribution. Further, constructing plausible synthetic text attribute baselines beyond sampling real node attributes is nontrivial compared to synthetic numeric or categorical attributes. In the table below, we find that ProvCreator’s synthetic graphs provide comparable performance gains to traditional class imbalance correction methods, demonstrating the effectiveness of class-conditioned targeted synthetic graph generation.

4. Generalization Across Operating Systems and Environments: While our current experiments focus on Windows processes, we are evaluating ProvCreator on provenance graphs from Linux environments and additional reference programs. Preliminary results suggest that ProvCreator easily adapts to OS-specific behaviors.

5. Correlation Between Synthesized Data and Downstream Results: ProvCreator outperforms GDSS due to its ability to incorporate text-based attributes conditioned on graph structure. We are extending our evaluation to include more diverse malware samples. We will also perform a case study of detection results improved by synthetic training data to clarify the influence of synthetic provenance graphs on the malware detection model.