TU Darmstadt / ULB / TUprints

Scalable Automated Incrementalization for Real-Time Static Analyses

Mitschke, Ralf :
Scalable Automated Incrementalization for Real-Time Static Analyses.
Technische Universität, Darmstadt
[Ph.D. Thesis], (2014)

[img]
Preview
Text
mitschke-phd-thesis.pdf - Accepted Version
Available under Creative Commons Attribution Non-commercial No Derivatives, 2.5.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Title: Scalable Automated Incrementalization for Real-Time Static Analyses
Language: English
Abstract:

This thesis proposes a framework for easy development of static analyses, whose results are incrementalized to provide instantaneous feedback in an integrated development environment (IDE).

Today, IDEs feature many tools that have static analyses as their foundation to assess software quality and catch correctness problems. Yet, these tools often fail to provide instantaneous feedback and are thus restricted to nightly build processes. This precludes developers from fixing issues at their inception time, i.e., when the problem and the developed solution are both still fresh in mind.

In order to provide instantaneous feedback, incrementalization is a well-known technique that utilizes the fact that developers make only small changes to the code and, hence, analysis results can be re-computed fast based on these changes. Yet, incrementalization requires carefully crafted static analyses. Thus, a manual approach to incrementalization is unattractive. Automated incrementalization can alleviate these problems and allows analyses writers to formulate their analyses as queries with the full data set in mind, without worrying over the semantics of incremental changes.

Existing approaches to automated incrementalization utilize standard technologies, such as deductive databases, that provide declarative query languages, yet also require to materialize the full dataset in main-memory, i.e., the memory is permanently blocked by the data required for the analyses. Other standard technologies such as relational databases offer better scalability due to persistence, yet require large transaction times for data. Both technologies are not a perfect match for integrating static analyses into an IDE, since the underlying data, i.e., the code base, is already persisted and managed by the IDE. Hence, transitioning the data into a database is redundant work.

In this thesis a novel approach is proposed that provides a declarative query language and automated incrementalization, yet retains in memory only a necessary minimum of data, i.e., only the data that is required for the incrementalization. The approach allows to declare static analyses as incrementally maintained views, where the underlying formalism for incrementalization is the relational algebra with extensions for object-orientation and recursion. The algebra allows to deduce which data is the necessary minimum for incremental maintenance and indeed shows that many views are self-maintainable, i.e., do not require to materialize memory at all. In addition an optimization for the algebra is proposed that allows to widen the range of self-maintainable views, based on domain knowledge of the underlying data. The optimization works similar to declaring primary keys for databases, i.e., the optimization is declared on the schema of the data, and defines which data is incrementally maintained in the same scope. The scope makes all analyses (views) that correlate only data within the boundaries of the scope self-maintainable.

The approach is implemented as an embedded domain specific language in a general-purpose programming language. The implementation can be understood as a database-like engine with an SQL-style query language and the execution semantics of the relational algebra. As such the system is a general purpose database-like query engine and can be used to incrementalize other domains than static analyses. To evaluate the approach a large variety of static analyses were sampled from real-world tools and formulated as incrementally maintained views in the implemented engine.

Alternative Abstract:
Alternative AbstractLanguage
Diese Arbeit schlägt ein neuartiges System zur einfachen Entwicklung statischer Analysen vor, deren Ergebnismenge inkrementell neu berechnet wird, um eine unmittelbare Rückmeldung der Ergebnisse in einer integrierten Entwicklungsumgebung (IDE) zu ermöglichen. IDEs beinhalten eine Vielzahl an Werkzeugen die mit Hilfe statischer Analysen Probleme in Hinsicht auf die Qualität und Korrektheit von Softwaresystemen aufdecken. Allerdings sind diese Werkzeuge oftmals nicht imstande eine unmittelbare Rückmeldung der Ergebnisse zu liefern. Daher ist der Einsatz dieser Werkzeuge oft auf nächtliche Build-Prozesse beschränkt. Dies verhindert, dass Entwickler Probleme sofort bei deren Auftreten beseitigen können, also zu einem Zeitpunkt, an dem das Problem und die entwickelte Lösung noch gedanklich griffbereit sind. Um eine unmittelbare Rückmeldung zu ermöglichen, bietet sich die Technik der Inkrementalisierung an. Diese Technik nutzt die Tatsache, dass Entwickler meist nur kleine Änderungen am Quelltext der Software vornehmen. Daher können Analyseergebnisse schnell aufgrund dieser kleinen Änderungen neuberechnet werden. Inkrementalisierung erfordert allerdings eine sorgsame Entwickelung der statischen Analysen. Daher ist die manuelle Entwicklung inkrementeller Analysen unattraktiv. Automatisierte Inkrementalisierung hilft dieses Problem zu beseitigen und ermöglicht es den Entwicklern solcher Analysen diese als Abfragen über die Gesamtmenge der Daten zu formulieren, ohne sich Gedanken um die Semantik der Inkrementalisierung zu machen. Existierende Ansätze zur automatisierten Inkrementalisierung nutzen Standardtechnologien, wie deduktive Datenbanken. Diese bieten deklarative Abfragesprachen, benötigen aber auch große Mengen an Arbeitsspeicher, um die Gesamtmenge der Daten vorzuhalten. Diese Menge an Arbeitsspeicher wird permanent durch die Daten der Analyse belegt. Eine andere Standardtechnologie, die besser skaliert da sie wenig Arbeitsspeicher benötigt, sind relationale Datenbanken. Diese persistieren die Daten und nutzen nur wenig Arbeitsspeicher, um aktuelle Berechnungen durchzuführen. Allerdings benötigen relationale Datenbanken viel Zeit für Transaktion, die Auftreten wenn Daten in die Datenbank überführt werden. Die beiden Vorgestellten Technologien sind per-se nicht sonderlich geeignet, um statische Analysen in eine IDE zu integrieren, da die IDE bereits die Gesamtmenge der Daten vorzuhält und verwaltet. Eine Überführung der Daten in ein Fremdsystem ist daher ein unnötiger Arbeitsschritt. Der in dieser Arbeit vorgestellte Ansatz bietet eine deklarative Abfragesprache und automatisierte Inkrementalisierung, benötigt allerdings nur das Minimum an Arbeitsspeicher, welches für die Inkrementalisierung vonnöten ist. Der Ansatz ermöglicht es statische Analysen als inkrementell gewartete Sichten zu deklarieren. Der zugrundeliegende Formalismus zur Inkrementalisierung ist die relationale Algebra mit Erweiterungen für Objektorientierung und Rekursion. Die Algebra erlaubt es das nötige Minimum an Daten zu bestimmen und zeigt auch, dass viele Sichten ohne das Vorhalten von Daten im Arbeitsspeicher wartbar sind. Diese Sichten werden “self-maintainable” (selbstwartbar) genannt. Um Selbstwartbarkeit für eine möglichst große Vielzahl an Sichten zu ermöglichen, wird eine Optimierung innerhalb der Algebra vorgeschlagen. Diese Optimierung nutzt Wissen aus der Domäne der zugrundeliegenden Daten. Die Optimierung arbeitet in ähnlicher Weise wie Primärschlüssel in Datenbanken, d.h., die Optimierung wird mit dem Schema der Daten spezifiziert und definiert welche Daten inkrementell in einem gemeinsamen Bezugsrahmen gewartet werden können. Dieser Bezugsrahmen ermöglicht Selbstwartbarkeit für alle Analysen (Sichten), die nur Daten innerhalb des gemeinsamen Rahmens korrelieren. Der Ansatz ist als domänenspezifische Sprache in eine universelle Programmiersprache eingebettet. Die Implementierung kann als datenbank-ähnliches System aufgefasst werden, welches eine SQL-ähnliche Abfragesprache mit der Ausführungssemantik der relationalen Algebra besitzt. Das System als solches ist universell einsetzbar und nicht auf die Domäne der statischen Analysen beschränkt. Um den Ansatz zu evaluieren wurde eine Vielzahl unterschiedlicher statischer Analysen, aus bestehenden Werkzeugen, mithilfe unseres Systems als inkrementell gewartete Sichten nachimplementiert.German
Place of Publication: Darmstadt
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Software Technology
Date Deposited: 28 May 2014 07:07
Last Modified: 28 May 2014 07:07
URN: urn:nbn:de:tuda-tuprints-38155
Referees: Mezini, Dr.-Ing. Mira and Hähnle, Dr.-Ing. Reiner
Refereed: 26 June 2013
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/3815
Export:
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year