Code property graph: Difference between revisions

Revision as of 18:43, 1 September 2022

Revision as of 19:17, 1 September 2022

Line 1:

{{Short description|Representation of a computer program}}

{{Draft topics|stem}}

{{AfC topic|stem}}

{{AfC submission|||ts=20220901184333|u=Suchakra|ns=118}}

{{AfC submission|t||ts=20220831183345|u=Suchakra|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->

In computer science, a '''code property graph''' (CPG) is a program representation that captures [[Abstract syntax tree|syntactic structure]], [[Control-flow graph|control flow]], and [[data dependencies]] in a [[Graph database|property graph]]. The concept was originally introduced to identify security vulnerabilities in C/C++ system code<ref>{{cite journal |last1=Yamaguchi |first1=Fabian |last2=Golde |first2=Nico |last3=Arp |first3=Daniel |last4=Rieck |first4=Konrad |title=Modeling and Discovering Vulnerabilities with Code Property Graphs |journal=2014 IEEE Symposium on Security and Privacy |date=May 2014 |pages=590–604 |doi=10.1109/SP.2014.44}}</ref> but has since been employed to analyze Web applications<ref>{{cite journal |last1=Backes |first1=Michael |last2=Rieck |first2=Konrad |last3=Skoruppa |first3=Malte |last4=Stock |first4=Ben |last5=Yamaguchi |first5=Fabian |title=Efficient and Flexible Discovery of PHP Application Vulnerabilities |journal=2017 IEEE European Symposium on Security and Privacy (EuroS&P) |date=April 2017 |pages=334–349 |doi=10.1109/EuroSP.2017.14}}</ref><ref>{{cite journal |last1=Li |first1=Song |last2=Kang |first2=Mingqing |last3=Hou |first3=Jianwei |last4=Cao |first4=Yinzhi |title=Mining Node.js Vulnerabilities via Object Dependence Graph and Query |date=2022 |pages=143–160 |url=https://www.usenix.org/conference/usenixsecurity22/presentation/li-song |language=en}}</ref><ref>{{cite journal |last1=Brito |first1=Tiago |last2=Lopes |first2=Pedro |last3=Santos |first3=Nuno |last4=Santos |first4=José Fragoso |title=Wasmati: An efficient static vulnerability scanner for WebAssembly |journal=Computers & Security |date=1 July 2022 |volume=118 |pages=102745 |doi=10.1016/j.cose.2022.102745}}</ref><ref>{{cite journal |last1=Khodayari |first1=Soheil |last2=Pellegrino |first2=Giancarlo |title=JAW: Studying Client-side CSRF with Hybrid Property Graphs and Declarative Traversals |date=2021 |pages=2525–2542 |url=https://www.usenix.org/conference/usenixsecurity21/presentation/khodayari |language=en}}</ref>, cloud deployments<ref>{{cite journal |last1=Banse |first1=Christian |last2=Kunz |first2=Immanuel |last3=Schneider |first3=Angelika |last4=Weiss |first4=Konrad |title=Cloud Property Graph: Connecting Cloud Security Assessments with Static Code Analysis |journal=2021 IEEE 14th International Conference on Cloud Computing (CLOUD) |date=September 2021 |pages=13–19 |doi=10.1109/CLOUD53861.2021.00014}}</ref>, and smart contracts<ref>{{cite journal |last1=Giesen |first1=Jens-Rene |last2=Andreina |first2=Sebastien |last3=Rodler |first3=Michael |last4=Karame |first4=Ghassan |last5=Davi |first5=Lucas |title=Practical Mitigation of Smart Contract Bugs {{!}} TeraFlow |journal=www.teraflow-h2020.eu |url=https://www.teraflow-h2020.eu/publications/practical-mitigation-smart-contract-bugs}}</ref>. Beyond vulnerability discovery, code property graphs find applications in code clone detection<ref>{{cite journal |last1=Wi |first1=Seongil |last2=Woo |first2=Sijae |last3=Whang |first3=Joyce Jiyoung |last4=Son |first4=Sooel |title=HiddenCPG: Large-Scale Vulnerable Clone Detection Using Subgraph Isomorphism of Code Property Graphs |journal=Proceedings of the ACM Web Conference 2022 |date=25 April 2022 |pages=755–766 |doi=10.1145/3485447.3512235}}</ref><ref>{{cite journal |last1=Bowman |first1=Benjamin |last2=Huang |first2=H. Howie |title=VGRAPH: A Robust Vulnerable Code Clone Detection System Using Code Property Triplets |journal=2020 IEEE European Symposium on Security and Privacy (EuroS&P) |date=September 2020 |pages=53–69 |doi=10.1109/EuroSP48549.2020.00012}}</ref>, attack-surface detection<ref>{{cite journal |last1=Du |first1=Xiaoning |last2=Chen |first2=Bihuan |last3=Li |first3=Yuekang |last4=Guo |first4=Jianmin |last5=Zhou |first5=Yaqin |last6=Liu |first6=Yang |last7=Jiang |first7=Yu |title=LEOPARD: Identifying Vulnerable Code for Vulnerability Assessment Through Program Metrics |journal=2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE) |date=May 2019 |pages=60–71 |doi=10.1109/ICSE.2019.00024}}</ref>, exploit generation<ref>{{cite journal |last1=Alhuzali |first1=Abeer |last2=Gjomemo |first2=Rigel |last3=Eshete |first3=Birhanu |last4=Venkatakrishnan |first4=V. N. |title=NAVEX: Precise and Scalable Exploit Generation for Dynamic Web Applications |date=2018 |pages=377–392 |url=https://www.usenix.org/conference/usenixsecurity18/presentation/alhuzali |language=en}}</ref>, measuring code testability<ref>{{cite journal |last1=Al Kassar |first1=Feras |last2=Clerici |first2=Giulia |last3=Compagna |first3=Luca |last4=Balzarotti |first4=Davide |last5=Yamaguchi |first5=Fabian |title=Testability Tarpits: the Impact of Code Patterns on the Security Testing of Web Applications – NDSS Symposium |journal=NDSS Symposium |url=https://www.ndss-symposium.org/ndss-paper/auto-draft-206/}}</ref>, and backporting of security patches<ref>{{cite journal |last1=Shi |first1=Youkun |last2=Zhang |first2=Yuan |last3=Luo |first3=Tianhan |last4=Mao |first4=Xiangyu |last5=Cao |first5=Yinzhi |last6=Wang |first6=Ziwen |last7=Zhao |first7=Yudi |last8=Huang |first8=Zongan |last9=Yang |first9=Min |title=Backporting Security Patches of Web Applications: A Prototype Design and Implementation on Injection Vulnerability Patches |date=2022 |pages=1993–2010 |url=https://www.usenix.org/conference/usenixsecurity22/presentation/shi |language=en}}</ref>.

== Definition ==

A code property graph of a program is a graph representation of the program obtained by merging its [[Abstract syntax tree|abstract syntax trees]] (AST), [[Control-flow graph|control flow graphs]] (CFG) and [[Program dependence graph|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:

<syntaxhighlight lang="cpp">

void foo() {

int x = source();

if(x < MAX) {

int y = 2 * x;

sink(y);

}

}

</syntaxhighlight>

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:

[[File:CodePropertyGraph.png|700px|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<ref>{{cite web |title=Joern - A Robust Code Analysis Platform for C/C++ |url=http://www.mlsec.org/joern/index.shtml |website=www.mlsec.org}}</ref>. This original version has been discontinued and superseded by the open-source Joern Project<ref>{{cite web |title=Joern - The Bug Hunter's Workbench |url=https://joern.io |website=Joern - The Bug Hunter's Workbench |language=en}}</ref>, which provides a formal code property graph specification<ref>{{cite web |title=Code Property Graph Specification |url=http://cpg.joern.io/ |website=cpg-spec.github.io |language=en}}</ref> 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<ref>{{cite web |title=Plume |url=https://plume-oss.github.io/plume-docs/ |website=plume-oss.github.io}}</ref> 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 Society|Fraunhofer]] Institute for Applied and Integrated Security provides open-source code property graph generators for C/C++, Java, Golang, and Python<ref>{{cite web |title=Code Property Graph |url=https://github.com/Fraunhofer-AISEC/cpg |publisher=Fraunhofer AISEC |date=31 August 2022}}</ref>, albeit without a formal schema specification. It also provides the Cloud Property Graph<ref>{{cite journal |last1=Banse |first1=Christian |last2=Kunz |first2=Immanuel |last3=Schneider |first3=Angelika |last4=Weiss |first4=Konrad |title=Cloud Property Graph: Connecting Cloud Security Assessments with Static Code Analysis |journal=2021 IEEE 14th International Conference on Cloud Computing (CLOUD) |date=September 2021 |pages=13–19 |doi=10.1109/CLOUD53861.2021.00014}}</ref>, 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<ref>{{cite web |title=The Code Property Graph — MATE 0.1.0.0 documentation |url=https://galoisinc.github.io/MATE/cpg.html |website=galoisinc.github.io}}</ref>. 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 network|graph neural networks]] (GNN) have been employed to derive vulnerability detectors.<ref>{{cite journal |last1=Zhou |first1=Yaqin |last2=Liu |first2=Shangqing |last3=Siow |first3=Jingkai |last4=Du |first4=Xiaoning |last5=Liu |first5=Yang |title=Devign: effective vulnerability identification by learning comprehensive program semantics via graph neural networks |journal=Proceedings of the 33rd International Conference on Neural Information Processing Systems |date=8 December 2019 |pages=10197–10207 |url=https://dl.acm.org/doi/10.5555/3454287.3455202 |publisher=Curran Associates Inc.}}</ref><ref>{{cite journal |last1=Haojie |first1=Zhang |last2=Yujun |first2=Li |last3=Yiwei |first3=Liu |last4=Nanxin |first4=Zhou |title=Vulmg: A Static Detection Solution For Source Code Vulnerabilities Based On Code Property Graph and Graph Attention Network |journal=2021 18th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP) |date=December 2021 |pages=250–255 |doi=10.1109/ICCWAMTIP53232.2021.9674145}}</ref><ref>{{cite journal |last1=Zheng |first1=Weining |last2=Jiang |first2=Yuan |last3=Su |first3=Xiaohong |title=Vu1SPG: Vulnerability detection based on slice property graph representation learning |journal=2021 IEEE 32nd International Symposium on Software Reliability Engineering (ISSRE) |date=October 2021 |pages=457–467 |doi=10.1109/ISSRE52982.2021.00054}}</ref><ref>{{cite journal |last1=Chakraborty |first1=Saikat |last2=Krishna |first2=Rahul |last3=Ding |first3=Yangruibo |last4=Ray |first4=Baishakhi |title=Deep Learning based Vulnerability Detection: Are We There Yet |journal=IEEE Transactions on Software Engineering |date=2021 |pages=1–1 |doi=10.1109/TSE.2021.3087402}}</ref><ref>{{cite journal |last1=Zhou |first1=Li |last2=Huang |first2=Minhuan |last3=Li |first3=Yujun |last4=Nie |first4=Yuanping |last5=Li |first5=Jin |last6=Liu |first6=Yiwei |title=GraphEye: A Novel Solution for Detecting Vulnerable Functions Based on Graph Attention Network |journal=2021 IEEE Sixth International Conference on Data Science in Cyberspace (DSC) |date=October 2021 |pages=381–388 |doi=10.1109/DSC53577.2021.00060}}</ref><ref>{{cite journal |last1=Ganz |first1=Tom |last2=Härterich |first2=Martin |last3=Warnecke |first3=Alexander |last4=Rieck |first4=Konrad |title=Explaining Graph Neural Networks for Vulnerability Discovery |journal=Proceedings of the 14th ACM Workshop on Artificial Intelligence and Security |date=15 November 2021 |pages=145–156 |doi=10.1145/3474369.3486866}}</ref><ref>{{cite journal |last1=Duan |first1=Xu |last2=Wu |first2=Jingzheng |last3=Ji |first3=Shouling |last4=Rui |first4=Zhiqing |last5=Luo |first5=Tianyue |last6=Yang |first6=Mutian |last7=Wu |first7=Yanjun |title=VulSniper: Focus Your Attention to Shoot Fine-Grained Vulnerabilities |journal=Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence |date=August 2019 |pages=4665–4671 |doi=10.24963/ijcai.2019/648}}</ref>

== See also ==

* [[Abstract syntax tree|Abstract Syntax Tree]]

* [[Control-flow graph|Control Flow Graph]]

* [[Program dependence graph|Program Dependence Graph]]

* [[Graph database|Graph Database]]

==References==

{{reflist}}