004 Datenverarbeitung; Informatik
Refine
Document Type
- Doctoral Thesis (4)
Has Fulltext
- yes (4)
Is part of the Bibliography
- no (4)
Keywords
- Software Engineering (4) (remove)
Institute
- Mitarbeiter Lehrstuhl/Einrichtung der Fakultät für Informatik und Mathematik (4) (remove)
Program slicing is a technique to identify statements that may influence the computations in other statements. Despite the ongoing research of almost 25 years, program slicing still has problems that prevent a widespread use: Sometimes, slices are too big to understand and too expensive and complicated to be computed for real-life programs. This thesis presents solutions to these problems: It contains various approaches which help the user to understand a slice more easily by making it more focused on the user's problem. All of these approaches have been implemented in the VALSOFT system and thorough evaluations of the proposed algorithms are presented. The underlying data structures used for slicing are program dependence graphs. They can also be used for different purposes: A new approach to clone detection based on identifying similar subgraphs in program dependence graphs is presented; it is able to detect modified clones better than other tools. In the theoretical part, this thesis presents a high-precision approach to slice concurrent procedural programs despite that optimal slicing is known to be undecidable. It is the first approach to slice concurrent programs that does not rely on inlining of called procedures.
Aspect-Oriented Programming (AOP) has been promoted as a solution for modularization problems known as the tyranny of the dominant decomposition in literature. However, when analyzing AOP languages it can be doubted that uncontrolled AOP is indeed a silver bullet. The contributions of the work presented in this thesis are twofold. First, we critically analyze AOP language constructs and their effects on program semantics to sensitize programmers and researchers to resulting problems. We further demonstrate that AOP—as available in AspectJ and similar languages—can easily result in less understandable, less evolvable, and thus error prone code—quite opposite to its claims. Second, we examine how tools relying on both static and dynamic program analysis can help to detect problematical usage of aspect-oriented constructs. We propose to use change impact analysis techniques to both automatically determine the impact of aspects and to deal with AOP system evolution. We further introduce an analysis technique to detect potential semantical issues related to undefined advice precedence. The thesis concludes with an overview of available open source AspectJ systems and an assessment of aspect-oriented programming considering both fundamentals of software engineering and the contents of this thesis.
Diese Arbeit präsentiert eine neue Methode zur Sicherheitsanalyse von Software im Bereich der Manipulationsprüfung und der Einhaltung von Informationsflüssen zwischen verschiedenen Sicherheitsniveaus. Program-Slicing und Constraint-Solving sind eigenständige Verfahren, die sowohl zur Abhängigkeitsbestimmung als auch zur Berechnung arithmetischer Eigenschaften verwendet werden. Die erstmalige Kombination dieser beiden Verfahren mittels Pfadbedingungen liefert nicht nur binäre Abhängigkeitsinformationen wie Slicing, sondern exakte notwendige Bedingungen über die Informationsflüsse zwischen zwei Programmpunkten. Neben der Definition der Grundlagen von Abhängigkeitsgraphen und einfachen Pfadbedingungen werden neue Erweiterungen für kontextsensitive interprozedurale Pfadbedingungen gezeigt und die Integration von domänenspezifischen Verfahren für Arrayfelder und abstrakten Datentypen demonstriert. Der Schwerpunkt der Arbeit liegt in der Realisierung von Pfadbedingungen für echte Programme in echten Programmiersprachen. Hierfür werden Verfahren vorgeschlagen, realisiert und empirisch untersucht, wie Pfadbedingungen für große Programme skalieren. Die zum Einsatz kommenden Techniken sind u.a. Intervallanalyse und Binäre Entscheidungsgraphen, mit denen die generelle exponentielle Komplexität von Pfadbedingungen beherrschbar wird. Fallstudien für den Einsatz von Pfadbedingungen und die empirische Untersuchung mehrerer Verfahren zur Intervallanalyse zeigen, dass Pfadbedingungen für die praktische Programmanalyse und das Programmverstehen geeignet und empfehlenswert sind.
A parallelising compilation consists of many translation and optimisation stages. The programmer may steer the compiler through these stages by supplying directives with the source code or setting compiler switches. However, for an evaluation of the effects of individual stages, their selection and their best order, this approach is not optimal. To solve this problem, we propose the following method. The compilation is cast as a sequence of program transformations. Each intermediate program runs on an Abstract Parallel Machine (APM), while the program generated by the final transformation runs on the target architecture. Our intermediate programs are all in the same language, Haskell. Thus, each program is executable and still abstract enough to be legible, which enables the evaluation of the transformation that generated it. This evaluation is supported by a cost model, which makes a performance prediction of the abstract program for a real machine. Our project, PolyAPM, provides an acyclic directed graph -- usually a tree -- of APMs whose traversal specifies different combinations and orders of transformations. From one source program, several target programs can be constructed. Their run time characteristics can be evaluated and compared. The goal of PolyAPM is not to support the one-off construction of parallel application programs. For the method's overhead to pay off, the project aims rather at supporting the construction and comparison of many similar variations of a parallel program and a comparative evaluation of parallelisation techniques. With the automation of transformations, PolyAPM can also be used to construct semi-automatic compilation systems.