Einführung von ACER: Ein neues Framework zur Generierung von Call-Graphen

Wir präsentieren ACER, ein Framework, das entwickelt wurde, um Call-Graphs basierend auf abstrakten Syntaxbäumen (ASTs) zu erstellen. Call-Graphs helfen dabei zu analysieren, wie Methoden in einem Programm miteinander interagieren, was bei verschiedenen Aufgaben nützlich sein kann, wie z.B. beim Optimieren von Code oder beim Finden von Sicherheitsproblemen. Unser Fokus liegt auf der Verwendung von ASTs, weil sie in vielen Situationen schnell und einfach verarbeitet werden können.

#Was ist ein Call-Graph?

Ein Call-Graph ist ein Diagramm, das zeigt, welche Methoden welche anderen Methoden in einem Programm aufrufen. In diesem Graphen ist jede Methode ein Punkt (oder Vertex), und jeder Aufruf von einer Methode zu einer anderen ist eine Linie (oder Kante), die diese Punkte verbindet. Zum Beispiel, wenn Methode A Methode B aufruft, gibt es eine gerichtete Linie von A nach B im Call-Graph.

#Bedeutung von Call-Graphs

Call-Graphs sind für viele Zwecke wichtig. Sie können helfen, die Software-Performance zu verbessern, potenzielle Sicherheitsprobleme zu lokalisieren und beim Umstrukturieren oder Refaktorisieren von Code zu unterstützen. Indem sie aufzeigen, wie verschiedene Teile des Codes zusammenarbeiten, können Entwickler bessere Entscheidungen über Änderungen und Verbesserungen treffen.

#Wie Call-Graph-Generatoren funktionieren

Call-Graph-Generatoren analysieren den Quellcode, um diese Graphen zu erstellen. Der Prozess umfasst das Finden, wo Methoden aufgerufen werden, und das Auflösen der Aufrufe zu spezifischen Methoden. Es gibt einige Herausforderungen in diesem Prozess, besonders in Sprachen, die dynamisches Verhalten erlauben.

#Arten von Call-Graph-Generatoren

1. Einfache Generatoren: Diese identifizieren schnell Aufrufe basierend auf Methodennamen, ohne Details wie Methodenempfänger zu berücksichtigen.
2. Kontextunabhängige Generatoren: Diese schauen sich den Code genauer an und analysieren den Kontext der Methodenaurufe, übersehen aber trotzdem einige Details.
3. Kontextsensitive Generatoren: Diese verfolgen den detailliertesten Ansatz und berücksichtigen den gesamten Kontext der Methodenaurufe, um genauere Graphen zu erzeugen.

Generatoren können auch je nach dem Teil der Software, den sie analysieren - nur die Anwendung, die Bibliotheken oder eine Kombination - unterschiedlich sein. Das Quellformat, das während der Analyse verwendet wird, beeinflusst auch, wie gut ein Generator abschneidet.

#Warum wir ASTs verwenden

Unser System stützt sich auf ASTs, weil sie uns ermöglichen, den Code zu analysieren, ohne ihn vollständig kompilieren zu müssen. Das macht den Prozess schneller und auf verschiedene Programmiersprachen anwendbar. ASTs bieten eine vereinfachte Version der Struktur des Codes, die einfacher zu handhaben ist als der rohe Quellcode.

#ACER Framework Übersicht

Das ACER-Framework besteht aus zwei Hauptkomponenten:

1. Tree-sitter: Dies ist eine Bibliothek, die hilft, Code in Baumstrukturen zu parsen. Sie bietet eine Möglichkeit, mit der Syntax verschiedener Programmiersprachen zu arbeiten.
2. Gemeinsame Dienstprogramme: Diese Komponenten enthalten gemeinsame Logik, die für verschiedene Arten von Generatoren nützlich ist, was das Erstellen neuer einfacher macht.

Durch die Kombination dieser beiden Teile zielt ACER darauf ab, eine unkomplizierte Möglichkeit zur Erstellung von Call-Graph-Generatoren zu bieten.

#Erstellung eines Call-Graph-Generators

Um einen Generator mit ACER zu erstellen, können Entwickler bestehende Klassen erweitern und spezifische Methoden implementieren. Eine wichtige Klasse, der Preprocessor, bereitet den Eingabecode für die Analyse vor. Er erstellt Nachschlage-Strukturen, die der Generator nutzen wird, wenn er den Call-Graph erstellt.

Der Generator nimmt dann die vorbereiteten Daten, findet alle Aufrufstellen im Code und bestimmt, welche Methoden aufgerufen werden, basierend auf den Strukturen, die der Preprocessor gebaut hat.

#Herausforderungen bei der Erstellung von Call-Graphs

Das Erstellen genauer Call-Graphs kann knifflig sein, besonders wenn man mit Funktionen von Programmiersprachen wie Polymorphismus (wo eine einzelne Funktion mit verschiedenen Datentypen arbeiten kann) und Mehrdeutigkeit (wo unklar ist, welche Methode basierend auf den verfügbaren Informationen aufgerufen wird) umgeht.

#Beispiele für Mehrdeutigkeit

Ein Beispiel für Mehrdeutigkeit ist, wenn eine Methode überladen ist, was bedeutet, dass es mehrere Methoden mit demselben Namen, aber unterschiedlichen Parameter-Typen gibt. Ohne die gesamte Situation zu analysieren (wie Bibliotheksquellen) kann es für einen Generator unmöglich sein, zu bestimmen, welche Version der Methode aufgerufen wird.

#Werkzeugbeschreibung und Implementierung

Das ACER-Framework besteht aus zwei Hauptkomponenten: dem Preprocessor und dem Generator.

#Preprocessor

Der Preprocessor ist verantwortlich für das Lesen des Eingabecodes und das Erstellen von Strukturen, die der Generator benötigt. Er verwendet Tree-sitter, um den Code in Baumstrukturen zu parsen und erstellt dann ein Methodendictionary, um Methodennamen ihren Definitionen zuzuordnen. Ausserdem erstellt er ein einzigartiges Dictionary, um potenzielle Namenskonflikte zu verwalten.

#Generator

Der Generator nimmt die Ausgabe des Preprocessors und erstellt den Call-Graph. Zuerst identifiziert er die Aufrufstellen, die Punkte im Code sind, an denen Methoden aufgerufen werden. Dann löst er diese Aufrufe zu den tatsächlichen Methoden auf, auf die verwiesen wird. Zum Beispiel, wenn ein Methodenaufruf aussieht wie a.b(), wird der Generator a untersuchen, um zu bestimmen, welcher Typ es ist und zu welcher Methode b() gehört.

#Leistungsevaluation

Wir haben zwei Arten von Generatoren mit ACER implementiert: eine basierend auf einem einfachen Namensauflösungsansatz und eine andere, die eine einfache Klassenhierarchie-Analyse nutzt. Wir haben diese Generatoren gegen bestehende Werkzeuge bewertet, um zu sehen, wie gut sie in Bezug auf Geschwindigkeit und Genauigkeit abschneiden.

Die Ergebnisse zeigten, dass, während einfachere Generatoren viele Kanten (Verbindungen zwischen Methoden) erzeugen konnten, sie oft an Präzision mangelten. Die komplexeren Generatoren neigten dazu, weniger Kanten zu erzeugen, waren jedoch genauer in ihren Verbindungen.

#Zukünftige Pläne

Wir planen, weitere Analysen zur Effizienz unserer Generatoren durchzuführen und an Verbesserungen zu arbeiten, die die Namensauflösung und Methodenauflösung optimieren könnten. Ausserdem möchten wir Generatoren für andere Programmiersprachen erstellen, um die Flexibilität des ACER-Frameworks zu zeigen.

#Fazit

Zusammenfassend ist ACER ein Framework, das darauf abzielt, den Prozess der Generierung von Call-Graphs aus Code zu vereinfachen. Es nutzt ASTs für eine schnelle Analyse und verwendet Tree-sitter für effektives Parsen. Während es Herausforderungen bei der genauen Auflösung von Methodenaufrufen gibt, bietet das Framework die notwendigen Werkzeuge und Strukturen, um zuverlässige Call-Graph-Generatoren zu bauen. Zukünftige Arbeiten werden sich darauf konzentrieren, diese Werkzeuge zu verfeinern und ihre Anwendbarkeit auf mehr Programmiersprachen zu erweitern.