Jump to content

Code property graph

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Suchakra (talk | contribs) at 17:49, 1 September 2022 (Fix citation issues and add list in "See Also"). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, a code property graph (CPG) is a 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/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

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

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:

Code property graph of a sample C code snippet


Implementations

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, JVM 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 JVM 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 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

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

References

  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: 590–604. doi:10.1109/SP.2014.44.
  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): 334–349. doi:10.1109/EuroSP.2017.14.
  3. ^ Li, Song; Kang, Mingqing; Hou, Jianwei; Cao, Yinzhi (2022). "Mining Node.js Vulnerabilities via Object Dependence Graph and Query": 143–160. {{cite journal}}: Cite journal requires |journal= (help)
  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. doi:10.1016/j.cose.2022.102745.
  5. ^ Khodayari, Soheil; Pellegrino, Giancarlo (2021). "JAW: Studying Client-side CSRF with Hybrid Property Graphs and Declarative Traversals": 2525–2542. {{cite journal}}: Cite journal requires |journal= (help)
  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): 13–19. doi:10.1109/CLOUD53861.2021.00014.
  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: 755–766. doi:10.1145/3485447.3512235.
  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): 53–69. doi:10.1109/EuroSP48549.2020.00012.
  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): 60–71. doi:10.1109/ICSE.2019.00024.
  11. ^ Alhuzali, Abeer; Gjomemo, Rigel; Eshete, Birhanu; Venkatakrishnan, V. N. (2018). "NAVEX: Precise and Scalable Exploit Generation for Dynamic Web Applications": 377–392. {{cite journal}}: Cite journal requires |journal= (help)
  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": 1993–2010. {{cite journal}}: Cite journal requires |journal= (help)
  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): 13–19. doi:10.1109/CLOUD53861.2021.00014.
  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.
  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): 250–255. doi:10.1109/ICCWAMTIP53232.2021.9674145.
  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): 457–467. doi:10.1109/ISSRE52982.2021.00054.
  24. ^ Chakraborty, Saikat; Krishna, Rahul; Ding, Yangruibo; Ray, Baishakhi (2021). "Deep Learning based Vulnerability Detection: Are We There Yet". IEEE Transactions on Software Engineering: 1–1. doi:10.1109/TSE.2021.3087402.
  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): 381–388. doi:10.1109/DSC53577.2021.00060.
  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: 145–156. doi:10.1145/3474369.3486866.
  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: 4665–4671. doi:10.24963/ijcai.2019/648.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Code_property_graph&oldid=1107944033"