Static Structure versus Edge-Order Representation for Drive-by-Download Detection in Linux Audit Graphs: A Reproducible Evaluation

Xinyu Zhang; Jiale Gao; Yinchu Wu

Static Structure versus Edge-Order Representation for Drive-by-Download Detection in Linux Audit Graphs: A Reproducible Evaluation

Authors

Xinyu Zhang Applied Computing, University of Toronto, Toronto, ON, Canada
Jiale Gao Applied Analytics, Columbia University, New York, NY, USA
Yinchu Wu Computer Science, Shanghai Jiao Tong University, Shanghai, China

Keywords:

provenance graphs, audit logs, anomaly detection, edge order

Abstract

The public StreamSpot corpus is widely used to evaluate anomaly detection over Linux audit graphs, yet its released form removes timestamps while retaining the original edge sequence. This study asks whether that residual ordering improves drive-by-download detection beyond static structural frequencies. We compare three representations under one isolation-based detector: static typed-edge frequencies, static features augmented with edge-type transitions, and static features augmented with full typed-edge transitions. The verified corpus contains 600 graphs across five benign activities and one attack activity. Ten stratified repetitions allocate 300 benign graphs to training, 75 to threshold selection, and 125 benign plus all 100 attack graphs to testing. Static features already provide perfect mean ranking performance, with AUPRC and AUROC both equal to 1.0000. Full typed-edge order yields AUPRC 0.9987±0.0017 and AUROC 0.9991±0.0012. Its mean F1 rises from 0.9635 to 0.9689 and its false-positive rate falls from 0.0608 to 0.0520, but paired tests give p=0.375 and p=0.416, respectively. Gmail false positives increase from 0.156 to 0.228. Edge order offers no stable aggregate benefit on this corpus and expands the mean feature space from 121.0 to 3,634.7 dimensions. The result supports simpler static representations for this narrowly controlled setting.

References

Manzoor, E., Milajerdi, S. M., & Akoglu, L. (2016). Fast memory-efficient anomaly detection in streaming heterogeneous graphs. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1035–1044). Association for Computing Machinery. https://doi.org/10.1145/2939672.2939783

Meng, W., Liu, Y., Zhu, Y., Zhang, S., Pei, D., Liu, Y., Chen, Y., Zhang, R., Tao, S., Sun, P., & Zhou, R. (2019). LogAnomaly: Unsupervised detection of sequential and quantitative anomalies in unstructured logs. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (pp. 4739–4745). International Joint Conferences on Artificial Intelligence Organization. https://doi.org/10.24963/ijcai.2019/658

Wang, S., Wang, Z., Zhou, T., Sun, H., Yin, X., Han, D., Zhang, H., Shi, X., & Yang, J. (2022). THREATRACE: Detecting and tracing host-based threats in node level through provenance graph learning. IEEE Transactions on Information Forensics and Security, 17, 3972–3987. https://doi.org/10.1109/TIFS.2022.3208815

Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (Vol. 30, pp. 1024–1034). Curran Associates.

Xu, D., Ruan, C., Korpeoglu, E., Kumar, S., & Achan, K. (2020). Inductive representation learning on temporal graphs. In International Conference on Learning Representations. https://openreview.net/forum?id=rJeW1yHYwH

Pareja, A., Domeniconi, G., Chen, J., Ma, T., Suzumura, T., Kanezashi, H., Kaler, T., Schardl, T. B., & Leiserson, C. E. (2020). EvolveGCN: Evolving graph convolutional networks for dynamic graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 34(4), 5363–5370. https://doi.org/10.1609/aaai.v34i04.5984

Yu, W., Cheng, W., Aggarwal, C. C., Zhang, K., Chen, H., & Wang, W. (2018). NetWalk: A flexible deep embedding approach for anomaly detection in dynamic networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 2672–2681). Association for Computing Machinery. https://doi.org/10.1145/3219819.3220024

Zheng, L., Li, Z., Li, J., Li, Z., & Gao, J. (2019). AddGraph: Anomaly detection in dynamic graph using attention-based temporal GCN. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (pp. 4419–4425). International Joint Conferences on Artificial Intelligence Organization. https://doi.org/10.24963/ijcai.2019/614

Cai, L., Chen, Z., Luo, C., Gui, J., Ni, J., Li, D., & Chen, H. (2021). Structural temporal graph neural networks for anomaly detection in dynamic graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (pp. 3747–3756). Association for Computing Machinery. https://doi.org/10.1145/3459637.3481955

Liu, Y., Pan, S., Wang, Y. G., Xiong, F., Wang, L., Chen, Q., & Lee, V. C. S. (2023). Anomaly detection in dynamic graphs via Transformer. IEEE Transactions on Knowledge and Data Engineering, 35(12), 12081–12094. https://doi.org/10.1109/TKDE.2021.3124061

Tian, S., Dong, J., Li, J., Zhao, W., Xu, X., Wang, B., Song, B., Meng, C., Zhang, T., & Chen, L. (2023). SAD: Semi-supervised anomaly detection on dynamic graphs. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence (pp. 2306–2314). International Joint Conferences on Artificial Intelligence Organization. https://doi.org/10.24963/ijcai.2023/256

Yang, X., Zhao, X., & Shen, Z. (2025). A generalizable anomaly detection method in dynamic graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 39(20), 22001–22009. https://doi.org/10.1609/aaai.v39i20.35508

Li, J., Dani, H., Hu, X., & Liu, H. (2017). Radar: Residual analysis for anomaly detection in attributed networks. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (pp. 2152–2158). International Joint Conferences on Artificial Intelligence Organization. https://doi.org/10.24963/ijcai.2017/299

Peng, Z., Luo, M., Li, J., Liu, H., & Zheng, Q. (2018). ANOMALOUS: A joint modeling approach for anomaly detection on attributed networks. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (pp. 3513–3519). International Joint Conferences on Artificial Intelligence Organization. https://doi.org/10.24963/ijcai.2018/488

Jin, M., Liu, Y., Zheng, Y., Chi, L., Li, Y.-F., & Pan, S. (2021). ANEMONE: Graph anomaly detection with multi-scale contrastive learning. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (pp. 3122–3126). Association for Computing Machinery. https://doi.org/10.1145/3459637.3482057

Liu, Y., Li, Z., Pan, S., Gong, C., Zhou, C., & Karypis, G. (2022). Anomaly detection on attributed networks via contrastive self-supervised learning. IEEE Transactions on Neural Networks and Learning Systems, 33(6), 2378–2392. https://doi.org/10.1109/TNNLS.2021.3068344

Zheng, Y., Jin, M., Liu, Y., Chi, L., Phan, K. T., & Chen, Y.-P. P. (2023). Generative and contrastive self-supervised learning for graph anomaly detection. IEEE Transactions on Knowledge and Data Engineering, 35(12), 12220–12233. https://doi.org/10.1109/TKDE.2021.3119326

Qiao, H., & Pang, G. (2023). Truncated affinity maximization: One-class homophily modeling for graph anomaly detection. In Advances in Neural Information Processing Systems (Vol. 36). Curran Associates.

Qiao, H., Wen, Q., Li, X., Lim, E.-P., & Pang, G. (2024). Generative semi-supervised graph anomaly detection. In Advances in Neural Information Processing Systems (Vol. 37). Curran Associates.

Xu, Y., Peng, Z., Shi, B., Hua, X., Dong, B., Wang, S., & Chen, C. (2025). Revisiting graph contrastive learning on anomaly detection: A structural imbalance perspective. Proceedings of the AAAI Conference on Artificial Intelligence, 39(12), 12972–12980. https://doi.org/10.1609/aaai.v39i12.33415

Static Structure versus Edge-Order Representation for Drive-by-Download Detection in Linux Audit Graphs: A Reproducible Evaluation