PS

Projekte

Forschungsprojekte der Abteilung Programmiersprachen und Übersetzerbau

Das Projekt Bauhaus ist eine Kooperation mit der Universität Bremen und der Firma Axivion GmbH. Während in Stuttgart vor allem Analysen des Programmverhaltens erforscht werden, widmet sich Bremen vorrangig den Architektur-bezogenen Themen. Axivion vermarktet die entwickelten Analysewerkzeuge, die für den kommerziellen Einsatz ausreichend ausgereift sind.

Bauhaus kann auf ganz verschiedenen Ebenen der Programmanalyse eingesetzt werden, z.B. zur Wiedergewinnung von Softwarearchitektur, zur Ermittlung von geklonten Quelltexten, zur Extraktion von Qualitätsmetriken oder zur automatischen Identifikation von Programmierfehlern.

In den letzten Jahren wird in Stuttgart schwerpunktmäßig an der Analyse nebenläufiger Softwaresysteme gearbeitet.
Es wurden verschiedene Analysewerkzeuge entwickelt, die zum automatischen Erkennen von Synchronisationsfehlern innerhalb parallel auszuführender Programmeinheiten eingesetzt werden bzw. die die Migration von Software auf Multicore-Rechner hinsichtlich der sinnvollen Aufteilung von Funktionskomponenten einer Software auf die Multicore-Architektur unterstützen.

SKilL

Ziel des Projekts SKilL ist es, eine Plattform für Werkzeugketten zu schaffen, die die Kommunikation zwischen den einzelnen Werkzeugen möglichst wartungsfrei und effizient gestaltet.

Kern des Projekts ist ein formal spezifiziertes, auf Änderungstoleranz und Ausleseeffizienz optimiertes Binärformat. Dieses kann von Werkzeugen effizient in eine Graphdarstellung ihrer individuellen Sicht auf das Zwischenformat abgebildet werden. Besonderer Wert wird auf leichte Bedienbarkeit der Serialisierungsschnittstelle gelegt. So werden Datentypen in einer Java-ähnlichen Sprache formal spezifiziert und dokumentiert. Daraus kann für eine frei wählbare Programmiersprache eine Implementierung generiert werden, die es Programmierern erlaubt, über ein sprachspezifisches API den zu einer Datei korrespondierenden Graphen zu bearbeiten und in eine Datei zu speichern. Von der frei verfügbaren Implementierung (siehe:https://github.com/skill-lang/skill) werden derzeit die Sprachen Ada, C++, Java und Scala unterstützt.

Gegenüber existierenden Lösungen bietet SKilL insbesondere weitreichende Änderungstoleranz, die es erlaubt, übliche evolutionsbedingte Formatänderungen zu kompensieren. Hierbei ist es zumeist nicht einmal notwendig, ein existierendes Tool nach einer Spezifikationsänderung neu zu übersetzen. Trotzdem ist das Format so gestaltet, dass Dateien mit inkompatiblem Inhalt nicht gelesen werden, wodurch Typsicherheit auf Formatebene gewährleistet wird. Des Weiteren ermöglicht es SKilL, neue Daten an bestehende Dateien anzuhängen, wodurch insbesondere bei kleinen Werkzeugen ein erheblicher Teil des Serialisierungsaufwands eingespart werden kann. Außerdem können Daten partiell, verzögert und parallel geladen werden, wodurch sich die Reaktionszeit von Werkzeugen deutlich verbessert.

Schwerpunkt der aktuellen Forschung an SKilL ist die Integration in die Bauhaus-Werkzeugkette. Hierdurch sollen theoretische Erkenntnisse in einem praxisnahen Szenario überprüft werden.

Bei Interesse an studentischen Arbeiten oder Forschungskooperationen wenden Sie sich an Timm Felden.

Simulation und Visualisierung von Real-Time-Systemen

 SAVORS ist eine in Java geschriebene Eclipse-RCP (Rich Client Platform) und dient zur synchronen Simulation und Visualisierung von Single- und Multi-Core-Scheduling-Algorithmen. Es ist ein zeitdiskretes, ereignisgetriebenes Simulationssystem, für dessen Entwicklung EMF (Eclipse Modeling Framework) und GEF (Graphical Editing Framework) eingesetzt werden.

SAVORS unterstützt unter anderem folgende Single-Core-Algorithmen:

  • Statische Priorität
    • Präemptives prioritätsbasiertes Scheduling
    • DMS (deadline monotonic scheduling)
    • RMS (rate monotonic scheduling)
  • Dynamische Priorität
    • EDF (earliest deadline first)

U. a. werden folgende Multi-Core-Scheduling-Algorithmen (für periodisch wiederkehrende und sporadische Aufgaben) unterstützt:

  • Global:
    • die proportional faire Gruppe von Algorithmen: (Pfair, PD, PD², PD²*, ER-Fair)
    • die an Grenzen faire Gruppe von Algorithmen: (Bfair and BF²)
    • die aus EDF hergeleiteten Algorithmen: unfaires EDF (U-EDF), globales EDF , GSN-EDF und PSN-EDF
  • Partitioniert:
    • partitioniertes EDF: P-EDF

Neben diesen Scheduling-Algorithmen unterstützt der Simulator auch die folgenden Ressourcenzuweisungsprotokolle, um die Synchronisierung gemeinsam genutzter Ressourcen zu ermöglichen und dadurch das Risiko unvorhersehbaren Verhaltens abzumildern:

  • Für Single-Core-Architekturen:
    • Einfaches und transitives Vererben der Priorität
    • die Ceiling Priority Protokolle OCPP und ICCP
    • das Stack-Resource-Protokoll SRP
    • Bakers EDF-Protokoll
  • Für Multi-Core-Architekturen:
    • Flexibles Multiprocessor-Locking-Protokoll FMLP

Die Ausgabe von SAVORS ist der anhand des Simulationsmodells erstellte Ablaufplan, der in einer interaktiven GUI präsentiert wird.
SAVORS wird kontinuierlich erweitert und bei ISTE/PS sowohl in der Forschung als auch in der Lehre eingesetzt.

Erkennung stark verschleierter Programmcodeplagiate

Das Plagiieren urheberrechtlich geschützter Dokumentteile beschränkt sich nicht auf natürlichsprachliche Texte, sondern geschieht auch bei der Software-Entwicklung durch Übernahme fremden Programmcodes. In diesem Projekt untersuchen wir, wie sich die eigentlich rechtliche Frage nach der Erkennung von Plagiaten durch algorithmische Verfahren unterstützen lässt. Im Gegensatz zu Plagiaten natürlichsprachlicher Texte können Programmcodeplagiate stark verschleiert sein, da äquivalente Programmsemantik durch eine Vielzahl unterschiedlicher Codierungen ausgedrückt werden kann. Verschleierungen entstehen durch Anpassungen des plagiierten Programmcodes an die Umgebung, in die er übernommen wird, oder auch durch bewusste Verschleierungsmaßnahmen, die das Aufspüren der Plagiate durch automatische Plagiatserkenner erschweren sollen. Das Problem des automatischen Aufspürens von Programmcodeplagiaten ist dem der Codeklonerkennung verwandt. Insbesondere erfordert die automatische Erkennung stark verschleierter Programmcodeplagiate eine partielle Lösung des im Allgemeinen unlösbaren Problems der Erkennung semantischer Codeklone.

Unser Ansatz, der Codeverschleierung entgegenzuwirken, basiert auf partiellen Normalisierungen des zu untersuchenden Programmcodes, um den Code möglichst weitgehend zu seiner "semantischen Essenz" zu abstrahieren. Dazu setzen wir auf dem Programmanalysen-Framework Bauhaus auf und greifen auf bekannte Compilerbau- und Programmanalysentechniken zurück. Zur Abstraktion der Datenflüsse von unterschiedlichen Kontrollflussvariationsmöglichkeiten verwenden wir Programmabhängigkeitsgraphen (engl. program dependency graph, PDG). Ausdrücke werden durch algebraische Transformationen in eine normalisierte Form überführt. Ferner werden Schleifen und Fallunterscheidungen durch Codeoptimierungstechniken (z. B. Verschiebung schleifeninvarianten Codes) normalisiert. In der normalisierten Repräsentationsform des Programmcodes werden semantische Übereinstimmungen durch strukturelle Teilgraphvergleiche aufgespürt. Da Originalcode und plagiierter Code unterschiedlich in Prozeduren aufgeteilt sein können, führen wir diese Vergleiche interprozedural durch.