PS

Projects

Research projects of the Programming Languages and Compilers Group

The Project Bauhaus has evolved from a cooperation of the ´Programming Languages and Compiler Group´ at the University of Stuttgart with the University of Bremen and the Axivion GmbH.

While the focus of the research at the University of Stuttgart lies on the analyzation of software execution behaviour, the University of Bremen focuses on the description of software architecture and software reengineering.

Finally all well-engineered Bauhaus tools are vended by the Axivion Gmbh.

Bauhaus tools can be applied to analyze programs on several levels and in different fields of application, for example to regain an understanding of the architecture of software, to detect cloned software parts, to extract software metrics or to identify programming errors.

In recent years the researchers in Stuttgart especially work on analyzing tools designated for concurrent software systems. They developed tools e.g. for detecting synchronization errors - which can occur between programming units, when they are carried out simultaneously.

They also conceptualize tools supporting the migration of software on a multicore plattform. These tools are specialized in partitioning the functional components, so that they can be intelligently distributed among the multicore architecture.

SKilL

The Programming Languages and Compiler Group created the project SKilL. The goal of the project is to provide a platform for efficient intra-toolchain communication with a minimum of maintenance.

The heart of the project is a binary file format that has a formal specification and offers change tolerance as well as high decoding speed.
Tools can map it to an efficient graph representation matching their individual view onto the common intermediate representation. Special effort has been put into the design of the serialization interface.
We want to enable the user to access data via a generated API that is based on the tool's specification.
That way, we try to eliminate a significant amount of training required for new co-workers or students.
The format specification is a Java-like language that is used by the code generator to create a graph representation that feels natural in the target language. An open source implementation currently supporting Ada, C++, Java and Scala is available at https://github.com/skill-lang/skill.

In contrast to existing solutions, SKilL can deal with specification changes common in toolchain evolution. In most cases, it is not even necessary to recompile tools after a change of specification.
Nonetheless, files containing data incompatible with the specified type system will not be readable, leading to type-safety on the intermediate representation level. Furthermore, SKilL has the ability to append new data to existing files, thus reducing the amount of IO-time significantly.
Additionally, SKilL was designed with modern hardware architectures in mind, resulting in capabilities of parallel and lazy evaluation of files. Thus, response times of tools using only a small fraction of an intermediate representation can be increased significantly.

The current focus lies on migrating the Bauhaus toolchain to SKilL.
Doing so, we will prove theoretical results in a real-world scenario.

If you are interested in a research cooperation, talk to Timm Felden.

Simulation and Visualization of Real-time Systems

SAVORS is an Eclipse RCP (Rich Client Platform), written in Java, which supports the synchronous simulation and visualization of single and multi-core scheduling algorithms. It is a discrete-time, event-driven, simulation framework developed using the Eclipse Modelling Framework (EMF) and the Graphical Editing Framework (GEF).
Some of the single-core algorithms supported by SAVORS are:

  • Static priority:
    • Fixed priority preemptive scheduling
    • DMS (deadline monotonic scheduling)
    • RMS (rate monotonic scheduling)
  • Dynamic priority:
    • EDF (earliest deadline first)

Some of the multi-core scheduling algorithms (for periodic and sporadic tasks) supported are:

  • Global:
    • the proportionate fair group of algorithms (Pfair, PD, PD2, PD2*, ER-Fair)
    • the boundary fair group of algorithms (Bfair and BF2)
    • the algorithms based on EDF: the unfair algorithm (U-EDF), global EDF, GSN-EDF and PSN-EDF
  • Partitioned:
    • P-EDF (partitioned EDF)

In addition to these scheduling algorithms, the simulator supports the following resource allocation protocols to enable the synchronization of shared resources, thereby mitigating the risk of unpredictable performance:

  • Single core:
    • Simple and transitive priority inheritance
    • SRP (Stack Resource Protocol)
    • OCPP and ICPP: the ceiling priority protocols
    • Baker’s protocol
  • Multi-core:
    • FMLP (Flexible Multiprocessor Locking Protocol)

The output of SAVORS is the schedule produced from the simulation model, which is presented in an interactive GUI.
SAVORS is continuously enhanced and used both for teaching and research by ISTE/PS.

 

Detection of Heavily Obfuscated Program Code Plagiarism

Plagiarising parts of documents protected by copyright does not only occur in natural-language texts but also during software development by adopting external program code. In this project we explore how the basically juridical question how to detect plagiarism can be supported by algorithmic means. In contrast to plagiarism of natural-language texts, program code plagiarism may be heavily obfuscated because equivalent program semantics can be expressed by a multitude of different codings. Obfuscation results from adapting the plagiarised program code to the context in which it is integrated or from malicious obfuscation steps designed to prevent automatic plagiarism detectors from detecting the plagiarism. The problem of automatically detecting program code plagiarism is similar to code clone detection. I.e., the automatic detection of heavily obfuscated program code plagiarism requires a partial solution of the generally unsolvable problem of detecting semantic code clones.

Our approach to thwart code obfuscation is based on partial normalizations of the program code under consideration, in order to abstract the code to its "semantic essence" as far as possible. For that purpose we make use of the program analysis framework Bauhaus and apply common compiler construction and program analysis techniques. We use program dependency graphs (PDG) to abstract dataflows from different control-flow variation possibilities. Expressions are converted into a normalized form by algebraical transformations. Furthermore, loops and conditional statements are normalized using code optimization techniques (e.g. loop invariant code motion). Semantical matches are detected by structural subgraph comparisons in the normalized representation of the program code. The original code and the plagiarized code may be split into multiple procedures in different ways; therefore, the subgraphs are compared interprocedurally.