TUM Logo

Program slicing and Friends: Static Analysis Techniques on Code Property Graphs

Program slicing and Friends: Static Analysis Techniques on Code Property Graphs

Supervisor(s): Konrad Weiss, Dr. Julian Schütte
Status: open
Topic: Others
Type of Thesis: Masterthesis Bachelorthesis
Thesis topic in co-operation with the Fraunhofer Institute for Applied and Integrated Security AISEC, Garching

Description

In cooperation with Fraunhofer AISEC

Program slicing and Friends: Static Analysis Techniques on Code Property Graphs

Announcement: Bachelor’s Thesis or Master’s Thesis

Motivation and Topic

A Code Property Graph represents source code in a labelled directed multigraph. Various abstract representations of source code are merged into one supergraph. An Abstract Syntax Tree captures the Codes structure. A Control Flow Graph and Evaluation Order Graph represent the order in which statements or expressions are evaluated. Data Dependency Edges show the conditional and data dependencies between statements. Graph mining techniques allow storing large Code Property Graphs into a database. Graph traversals allow us to search through the supergraph and find patterns of structure and behavior. This allows searching for known security vulnerabilities by expressing them as graph traversal patterns. In contrast to static analysis based on intermediate representations, no compiled binaries are needed, and incomplete code can be analyzed.

Program slicing techniques are used to identify which statements influence the value of a variable at a specific statement. A data flow analysis captures the possible set of values that are calculated at various points of a program by working with data-flow equations for each node of a control flow graph. Static taint analysis is used to analyze whether user-provided input or sensitive data reach critical points in program execution. These and other classical analysis techniques can be performed on the graph or be the source of new subgraphs.

The goal of this thesis is first to research the current state of the art in static analysis and the abstract representations used for Code Property Graphs. The scope will be to implement classical analysis techniques on the CPG and enhance the CPG by new subgraphs and compare the performance of other implementations with the implementation of this thesis. Implementations purely in graph traversals should be explored.

Requirements

Programming skills in Java
An understanding of Java and C++
Interest in static code analysis, graphs, and programming languages

Ability to work self-directed and systematically

The thesis can be written in English or German.

Contact

Fraunhofer Institute for Applied and Integrated Security (AISEC)

Konrad Weiss, Dr. Julian Schütte
E-Mail: konrad.weiss@aisec.fraunhofer.de
Phone: +49 89 32299 86 113