Wikipedia

Code property graph

In computer science, a code property graph (CPG) is a computer program representation that captures syntactic structure, control flow, and data dependencies in a property graph. The concept was originally introduced to identify security vulnerabilities in C and C++ system code,[1] but has since been employed to analyze web applications,[2][3][4][5] cloud deployments,[6] and smart contracts.[7] Beyond vulnerability discovery, code property graphs find applications in code clone detection,[8][9] attack-surface detection,[10] exploit generation,[11] measuring code testability,[12] and backporting of security patches.[13]

Definition

edit

A code property graph of a program is a graph representation of the program obtained by merging its abstract syntax trees (AST), control-flow graphs (CFG) and program dependence graphs (PDG) at statement and predicate nodes. The resulting graph is a property graph, which is the underlying graph model of graph databases such as Neo4j, JanusGraph and OrientDB where data is stored in the nodes and edges as key-value pairs. In effect, code property graphs can be stored in graph databases and queried using graph query languages.

Example

edit

Consider the function of a C program: 

void foo() {
  int x = source();
  if (x < MAX) {
    int y = 2 * x;
    sink(y);
  }
}

The code property graph of the function is obtained by merging its abstract syntax tree, control-flow graph, and program dependence graph at statements and predicates as seen in the following figure:

 

Implementations

edit

Joern CPG. The original code property graph was implemented for C/C++ in 2013 at University of Göttingen as part of the open-source code analysis tool Joern.[14] This original version has been discontinued and superseded by the open-source Joern Project,[15] which provides a formal code property graph specification[16] applicable to multiple programming languages. The project provides code property graph generators for C/C++, Java, Java bytecode, Kotlin, Python, JavaScript, TypeScript, LLVM bitcode, and x86 binaries (via the Ghidra disassembler).

Plume CPG. Developed at Stellenbosch University in 2020 and sponsored by Amazon Science, the open-source Plume[17] project provides a code property graph for Java bytecode compatible with the code property graph specification provided by the Joern project. The two projects merged in 2021.

Fraunhofer AISEC CPG. The Fraunhofer Institute for Applied and Integrated Security [de] provides open-source code property graph generators for C/C++, Java, Golang, and Python,[18] albeit without a formal schema specification. It also provides the Cloud Property Graph,[19] an extension of the code property graph concept that models details of cloud deployments.

Galois’ CPG for LLVM. Galois Inc. provides a code property graph based on the LLVM compiler.[20] The graph represents code at different stages of the compilation and a mapping between these representations. It follows a custom schema that is defined in its documentation.

Machine learning on code property graphs

edit

Code property graphs provide the basis for several machine-learning-based approaches to vulnerability discovery. In particular, graph neural networks (GNN) have been employed to derive vulnerability detectors.[21][22][23][24][25][26][27]

See also

edit

References

edit
  1. ^ Yamaguchi, Fabian; Golde, Nico; Arp, Daniel; Rieck, Konrad (May 2014). "Modeling and Discovering Vulnerabilities with Code Property Graphs". 2014 IEEE Symposium on Security and Privacy. pp. 590–604. doi:10.1109/SP.2014.44. ISBN 978-1-4799-4686-0. S2CID 2231082.
  2. ^ Backes, Michael; Rieck, Konrad; Skoruppa, Malte; Stock, Ben; Yamaguchi, Fabian (April 2017). "Efficient and Flexible Discovery of PHP Application Vulnerabilities". 2017 IEEE European Symposium on Security and Privacy (EuroS&P). pp. 334–349. doi:10.1109/EuroSP.2017.14. ISBN 978-1-5090-5762-7. S2CID 206649536.
  3. ^ Li, Song; Kang, Mingqing; Hou, Jianwei; Cao, Yinzhi (2022). Mining Node.js Vulnerabilities via Object Dependence Graph and Query. pp. 143–160. ISBN 9781939133311.
  4. ^ Brito, Tiago; Lopes, Pedro; Santos, Nuno; Santos, José Fragoso (1 July 2022). "Wasmati: An efficient static vulnerability scanner for WebAssembly". Computers & Security. 118: 102745. arXiv:2204.12575. doi:10.1016/j.cose.2022.102745. S2CID 248405811.
  5. ^ Khodayari, Soheil; Pellegrino, Giancarlo (2021). JAW: Studying Client-side CSRF with Hybrid Property Graphs and Declarative Traversals. pp. 2525–2542. ISBN 9781939133243.
  6. ^ Banse, Christian; Kunz, Immanuel; Schneider, Angelika; Weiss, Konrad (September 2021). "Cloud Property Graph: Connecting Cloud Security Assessments with Static Code Analysis". 2021 IEEE 14th International Conference on Cloud Computing (CLOUD). pp. 13–19. arXiv:2206.06938. doi:10.1109/CLOUD53861.2021.00014. ISBN 978-1-6654-0060-2. S2CID 243946828.
  7. ^ Giesen, Jens-Rene; Andreina, Sebastien; Rodler, Michael; Karame, Ghassan; Davi, Lucas. "Practical Mitigation of Smart Contract Bugs | TeraFlow". www.teraflow-h2020.eu.
  8. ^ Wi, Seongil; Woo, Sijae; Whang, Joyce Jiyoung; Son, Sooel (25 April 2022). "HiddenCPG: Large-Scale Vulnerable Clone Detection Using Subgraph Isomorphism of Code Property Graphs". Proceedings of the ACM Web Conference 2022. pp. 755–766. doi:10.1145/3485447.3512235. ISBN 9781450390965. S2CID 248367462.
  9. ^ Bowman, Benjamin; Huang, H. Howie (September 2020). "VGRAPH: A Robust Vulnerable Code Clone Detection System Using Code Property Triplets". 2020 IEEE European Symposium on Security and Privacy (EuroS&P). pp. 53–69. doi:10.1109/EuroSP48549.2020.00012. ISBN 978-1-7281-5087-1. S2CID 226268429.
  10. ^ Du, Xiaoning; Chen, Bihuan; Li, Yuekang; Guo, Jianmin; Zhou, Yaqin; Liu, Yang; Jiang, Yu (May 2019). "LEOPARD: Identifying Vulnerable Code for Vulnerability Assessment Through Program Metrics". 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE). pp. 60–71. arXiv:1901.11479. doi:10.1109/ICSE.2019.00024. ISBN 978-1-7281-0869-8. S2CID 59523689.
  11. ^ Alhuzali, Abeer; Gjomemo, Rigel; Eshete, Birhanu; Venkatakrishnan, V. N. (2018). NAVEX: Precise and Scalable Exploit Generation for Dynamic Web Applications. pp. 377–392. ISBN 9781939133045.
  12. ^ Al Kassar, Feras; Clerici, Giulia; Compagna, Luca; Balzarotti, Davide; Yamaguchi, Fabian. "Testability Tarpits: the Impact of Code Patterns on the Security Testing of Web Applications – NDSS Symposium". NDSS Symposium.
  13. ^ Shi, Youkun; Zhang, Yuan; Luo, Tianhan; Mao, Xiangyu; Cao, Yinzhi; Wang, Ziwen; Zhao, Yudi; Huang, Zongan; Yang, Min (2022). Backporting Security Patches of Web Applications: A Prototype Design and Implementation on Injection Vulnerability Patches. pp. 1993–2010. ISBN 9781939133311.
  14. ^ "Joern - A Robust Code Analysis Platform for C/C++". www.mlsec.org.
  15. ^ "Joern - The Bug Hunter's Workbench". Joern - The Bug Hunter's Workbench.
  16. ^ "Code Property Graph Specification". cpg-spec.github.io.
  17. ^ "Plume". plume-oss.github.io.
  18. ^ "Code Property Graph". Fraunhofer AISEC. 31 August 2022.
  19. ^ Banse, Christian; Kunz, Immanuel; Schneider, Angelika; Weiss, Konrad (September 2021). "Cloud Property Graph: Connecting Cloud Security Assessments with Static Code Analysis". 2021 IEEE 14th International Conference on Cloud Computing (CLOUD). pp. 13–19. arXiv:2206.06938. doi:10.1109/CLOUD53861.2021.00014. ISBN 978-1-6654-0060-2. S2CID 243946828.
  20. ^ "The Code Property Graph — MATE 0.1.0.0 documentation". galoisinc.github.io.
  21. ^ Zhou, Yaqin; Liu, Shangqing; Siow, Jingkai; Du, Xiaoning; Liu, Yang (8 December 2019). "Devign: effective vulnerability identification by learning comprehensive program semantics via graph neural networks". Proceedings of the 33rd International Conference on Neural Information Processing Systems. Curran Associates Inc.: 10197–10207. arXiv:1909.03496.
  22. ^ Haojie, Zhang; Yujun, Li; Yiwei, Liu; Nanxin, Zhou (December 2021). "Vulmg: A Static Detection Solution for Source Code Vulnerabilities Based on Code Property Graph and Graph Attention Network". 2021 18th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP). pp. 250–255. doi:10.1109/ICCWAMTIP53232.2021.9674145. ISBN 978-1-6654-1364-0. S2CID 246039350.
  23. ^ Zheng, Weining; Jiang, Yuan; Su, Xiaohong (October 2021). "Vu1SPG: Vulnerability detection based on slice property graph representation learning". 2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE). pp. 457–467. doi:10.1109/ISSRE52982.2021.00054. ISBN 978-1-6654-2587-2. S2CID 246751595.
  24. ^ Chakraborty, Saikat; Krishna, Rahul; Ding, Yangruibo; Ray, Baishakhi (2021). "Deep Learning based Vulnerability Detection: Are We There Yet". IEEE Transactions on Software Engineering. 48 (9): 3280–3296. arXiv:2009.07235. doi:10.1109/TSE.2021.3087402. S2CID 221703797.
  25. ^ Zhou, Li; Huang, Minhuan; Li, Yujun; Nie, Yuanping; Li, Jin; Liu, Yiwei (October 2021). "GraphEye: A Novel Solution for Detecting Vulnerable Functions Based on Graph Attention Network". 2021 IEEE Sixth International Conference on Data Science in Cyberspace (DSC). pp. 381–388. arXiv:2202.02501. doi:10.1109/DSC53577.2021.00060. ISBN 978-1-6654-1815-7. S2CID 246634824.
  26. ^ Ganz, Tom; Härterich, Martin; Warnecke, Alexander; Rieck, Konrad (15 November 2021). "Explaining Graph Neural Networks for Vulnerability Discovery". Proceedings of the 14th ACM Workshop on Artificial Intelligence and Security. pp. 145–156. doi:10.1145/3474369.3486866. ISBN 9781450386579. S2CID 240001850.
  27. ^ Duan, Xu; Wu, Jingzheng; Ji, Shouling; Rui, Zhiqing; Luo, Tianyue; Yang, Mutian; Wu, Yanjun (August 2019). "VulSniper: Focus Your Attention to Shoot Fine-Grained Vulnerabilities". Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence. pp. 4665–4671. doi:10.24963/ijcai.2019/648. ISBN 978-0-9992411-4-1. S2CID 199466292.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Code_property_graph&oldid=1186115280"