Logo des Repositoriums

D22 (2021) - Ausgezeichnete Informatikdissertationen

https://dl.gi.de/handle/20.500.12116/39830
Auflistung nach:

Auflistung D22 (2021) - Ausgezeichnete Informatikdissertationen nach Erscheinungsdatum

Zu einem Punkt im Index springen:
1 - 10 von 32
  • Konferenzbeitrag
  • Konferenzbeitrag
    Skalierbare und vertraulichkeitswahrende Off-Chain Berechnungen
    (D22, 2022) Eberhardt, Jacob
    Blockchains erlauben sich gegenseitig mistrauenden Parteien gemeinsame Transaktionen auszuführen und deren Historie unveränderlich zu speichern. Aufgrund ihres technischen Aufbaus leiden Blockchains jedoch unter niedrigem Durchsatz, fehlender Skalierbarkeit und schwachen Datenschutzgarantien. Diese Arbeit adressiert diese Probleme durch das neuartige Konzept des Off- Chainings: Daten und Berechnungen werden von einer Blockchain auf externe Resourcen ausgelagert - jedoch ohne dabei Schlüsseleigenschaften der Blockchain zu komprommittieren. Insbesondere verifizierbare Off-Chain Berechnungen stellen ein mächtiges Werkzeug zur Erhöhung des Durchsatzes und der Gewährleistung von Vertraulichkeit dar. Allerdings fehlen geignete Realisierungsansätze. Unsere Analyse des Designraums identifiziert zk-SNARKs, eine Klasse nicht-interaktiver Protokolle für kryptographische Zero-Knowledge Beweise, als vielversprechenden Ansatz. Allerdings ist die Instanziierung dieser Protokolle komplex und somit wenigen Experten vorbehalten. Geeignete Pro- grammierabstraktionen und softwaretechnische Werkzeuge fehlen. Um dieses Problem zu adressieren, präsentieren wir ZoKrates, die erste höhere Programmiersprache und Sammlung von Softwarewerkzeu- gen zur Übersetzung und Ausführung zk-SNARK-basierter verifizierbarer Off-Chain Berechnungen. Wir demonstrieren Relevanz und Anwendbarkeit an drei dezentralen Applikationen: Peer-to-Peer Energiehandel, Blockchain-Relays und anonyme Token-Transfers. Die im Kontext dieser Arbeit entstandenen Softwarelösungen finden darüber hinaus unabhängige Anwendung in Wissenschaft und Industrie.
  • Konferenzbeitrag
    Stern-Topologie Entkoppelte Zustandsraumsuche
    (D22, 2022) Gnad, Daniel
    Die Zustandsraumsuche ist ein weit verbreitetes Konzept in vielen Bereichen der Informatik. Die Größe der zu durchsuchenden Zustandsräume wächst jedoch typischerweise exponentiell mit der Größe einer kompakten, faktorisierten Modellbeschreibung – das ist das bekannte Problem der Zustandsexplosion. Die Entkoppelte Zustandsraumsuche (entkoppelte Suche) beschreibt einen neuartigen Ansatz um der Zustandsexplosion entgegenzuwirken. Hierfür wird die Struktur des Modells, insbesondere die bedingte Unabhängigkeit von Systemkomponenten in einer Sterntopologie, ausgenutzt. Diese Unabhängigkeit ergibt sich ganz natürlich bei vielen faktorisierten Modellen deren Zustandsräume aus dem Produkt mehrerer Komponenten bestehen. In der Dissertation wird die ent- koppelte Suche in der Planung – als Teil der Künstlichen Intelligenz (KI) – und in der Verifikation mittels Modellprüfung eingeführt. Das Konzept des entkoppelten Zustandsraums wird auf Basis von etablierten Formalismen entwickelt und seine Korrektheit bezüglich der exakten Erfassung der Erreichbarkeit von Modellzuständen bewiesen. Damit kann die entkoppelte Suche mit beliebigen Suchalgorithmen genutzt und mit komplementären Techniken kombiniert werden. In der Dissertation wird gezeigt dass die entkoppelte Suche den Suchaufwand exponentiell stärker reduzieren kann als existierende alternative Ansätze, insbesondere die Reduktion partieller Ordnung, Symmetriereduktion, Entfaltung von Petri-Netzen und symbolische Suche. Empirisch kann die entkoppelte Suche sowohl in der Planung als auch in der Modellprüfung etablierte Systeme deutlich übertreffen.
  • Konferenzbeitrag
    Selbstadaptive Fitness in evolutionären Prozessen
    (D22, 2022) Gabor, Thomas
    Evolutionäre Prozesse modellieren die Entwicklung von Objekten mit zunächst zufälligen Eigenschaften zu Objekten, deren Eigenschaften einer Ordnung oder einem bestimmten Ziel (genannt Fitness) folgen. Evolutionäre Prozesse treten in Software häufig als Optimierungsalgorithmen oder beim maschinellen Lernen auf, wobei ihr Ziel meist extrinsisch durch einen Designer oder Programmierer bestimmt ist. Oft ist es jedoch von Vorteil, wenn besagte Algorithmen ihre Fitnessberechnung während ihrer Ausführung intrinsisch selbst adaptieren können. Wir verfolgen dieses Phänomen zurück auf künstliche Chemiesysteme (artificial chemistry systems), wo Fitness ohne Designer entsteht. Wir untersuchen diversitätsbasierte Fitnessfunktionen in evolutionären Algorithmen und können erstmalig ihre Effektivität begründen, indem wir das theoretische Modell der produktiven Fitness definieren. Schließlich finden wir einen Effektivitätsgewinn auch beim Zusammenspiel von evolutionären Algorithmen und bestärkendem Lernen (reinforcement learning), wobei beide Methoden allein durch eine wechselseitig adaptive Fitness interagieren. Dieses Konzept lässt sich auch als Architekturmuster für Softwaresysteme verallgemeinern.
  • Konferenzbeitrag
    SMC und zeitlich begrenzte Erreichbarkeitsanalyse für HPnGs
    (D22, 2022) Da Silva, Carina
    Sicherheitskritische Systeme stellen einen wichtigen Teil des heutigen Lebens dar. Modellierung und formale Verifikation bieten Ansätze zur Analyse solcher Systeme im Hinblick auf Systemeigenschaften wie beispielsweise Zuverlässigkeit. In meiner Dissertation [Pi21] wird eine Unterklasse stochastischer hybrider Systeme betrachtet, die diskrete, kontinuierliche und stochastische Variablen kombiniert. Es werden neuartige Ansätze für die Evaluation von hybriden Petri-Netzen mit allgemeinen Transitionen (HPnGs) vorgestellt. Diese umfassen statistisches Model Checking für Modelle mit linearen und nichtlinearen kontinuierlichen Verläufen sowie die (zeitlich begrenzte) Erreichbarkeitsanalyse für nichtdeterministische Modelle. Darüber hinaus stellt die Dissertation einen Ansatz für eine Transformation von HPnGs in eine Unterklasse der stochastischen hybriden Automaten vor, die die Anwendung bestehender, für hybride Automaten entwickelter Methoden auf stochastische hybride Modelle ermöglicht. Der resultierende Fehler der vorgestellten Ansätze kann dabei genau charakterisiert werden.
  • Konferenzbeitrag
    Programmaggregation mit algebraischen Entscheidungsdiagrammen
    (D22, 2022) Gossen, Frederik Jakob
    Im Rahmen dieser Dissertation wurde das Potential von algebraischen Entscheidungsdiagrammen (ADDs) als Programmrepräsentation für deren Optimierung untersucht. Dabei wurden domänenspezifische Sprachen, maschinell erlernte Modelle und allgemeine Programmiersprachen betrachtet. Insbesondere die Anwendung auf Random Forests, eine Methode des klassischen maschinellen Lernens, war besonders erfolgreich. Hier konnten nicht nur Beschleunigungen von mehreren Größenordnungen erreicht werden, sondern auch gleich drei wichtige Erklärbarkeitsprobleme gelöst werden. Random Forests, die als nicht interpretierbare Black-Box-Modelle angesehen werden, könen so semantisch aggregiert und verständlicher dargestellt werden. Das Resultat der Ag- gregation kann als semantisch äquivalentes White-Box-Modell angesehen werden. Die Lösung der Erklärbarkeitsprobleme ist beispielsweise in der Medizin oder im Bankensektor von enormer Bedeutung. Hier müssen automatisierte Entscheidungen immer erklärbar sein.
  • Konferenzbeitrag
    Quantitative konfigurierbare und rekonfigurierbare Systeme .
    (D22, 2022) Dubslaff, Clemens
    Die Fülle an Konfigurationsoptionen und der daraus resultierende Reichtum an Systemva- rianten stellen Entwickler von modernen Computersystemen vor großen Herausforderungen. Weitere Systemanforderungen an Adaptivität, Rekonfigurierbarkeit und an quantitative Aspekte wie Zuverläs- sigkeit, Energieverbrauch oder Latenz kommen erschwerend hinzu. Formale Analysen sind daher unabdingbar, um die Auswirkungen von Konfigurationsoptionen und deren Interaktionen einzuschät- zen und fehlerfreie Systeme zu garantieren. Die vorgestellte Dissertation führt ein kompositionelles Modellierungs- und Analyseframework ein, welches alle genannten Herausforderungen adressiert und effektive Lösungen bietet, formale quantitative Analysen auch für bisher unmöglich große konfigurierbare Systeme durchzuführen. An real existierenden Systemen wird dessen Anwendbarkeit demonstriert und mit neuen Methoden zu kausalen Erklärungen von Analyseresultaten ergänzt.
  • Konferenzbeitrag
    Erkennung von Anomalien und Veränderung in Graphsequenzen
    (D22, 2022) Zambon, Daniele
    Wir verzeichnen einen erheblichen Zuwachs an Daten, die von Sensornetzen und sozialen Netzwerken gesammelt werden, verursacht durch technologische Entwicklungen und die Verbreitung sozialer Plattformen. Die Auswertung dieser riesigen Datenströme ist eine wichtige Aufgabe für die Wissenschaft ebenso wie für die Industrie. Da Datenströme von Sensoren (sei es physischen oder virtuellen) in der Regel funktionale Abhängigkeiten aufweisen, erweisen sich Graphen als reichhaltige Strukturen, die in der Lage sind, sowohl Informationen auf der Ebene der Sensoren/Entitäten als auch die komplexen Beziehungen zwischen den Entitäten zu modellieren. Diese graphbasierte Repräsentation wiederum ermöglicht uns, mittels Graph Neural Networks und Geometric Deep Learning, Inferenzen in Bezug auf Graphsequenzen anzustellen. Im Allgemeinen gehen solche Verarbeitungsverfahren allerdings von der Hypothese der Stationarität aus, die nicht immer gegeben ist, z.B. wenn eine Alterung der Sensoren, eine zeitliche Varianz oder eine Veränderungen in den Präferenzen der Nutzer auf sozialen Plattformen vorliegt. In dieser Dissertation befassen wir uns mit dem Problem der Identifizierung von Veränderungen der Stationarität, die durch unbekannte Phänomene im zugrundeliegenden Datenerzeu- gungsprozess verursacht werden und sich in der Sequenz der Graphen zeigen. Die wissenschaftlichen Ergebnisse erlauben es uns, auch das Problem der Erkennung von Anomalien zu behandeln, das in der Tat eine wertvolle Fortsetzung der Forschung darstellt. Wir betrachten eine allgemeine Familie von mit Attributen versehenen Graphen mit nicht-identifizierten Knoten, um ein möglichst breites Spektrum von Anwendungen abzudecken. Der Hauptbeitrag dieser Arbeit besteht in einer Methodik zur Verarbeitung einer Sequenz von Graphen, um unerwartete Ereignisse (Änderungen der Stationaritäten und/oder Auftreten von Anomalien) im Datenerzeugungsprozess zu erkennen. Die Methodik beruht auf der Entwicklung neuartiger Embeddings auf Graphenebene und Methoden zur Erkennung von Veränderungen, die durch ein solides theoretischen Grundgerüst unterstützt werden.
  • Konferenzbeitrag
    Inkrementalisierung Statischer Analysen in Datalog
    (D22, 2022) Szabo, Tamas
    Integrierte Entwicklungsumgebungen verwenden statische Analysen, um den Entwicklern bei der Bearbeitung ihrer Programme ein verwertbares Feedback zu geben. Im Gegenzug können die Entwickler ihren Code überarbeiten und potenzielle Laufzeitprobleme beseitigen, bevor der Code in Produktion geht. Die Entwicklung von Analysen für den Einsatz in IDEs ist ein komplexes Unterfangen, da die Analysen nach einer Programmänderung in Sekundenschnelle Ergebnisse liefern und gleichzeitig das Programmverhalten für alle möglichen Ausführungsarten präzise erfassen müssen. Diese beiden Anforderungen stehen im Widerspruch zueinander und stellen eine komplexe Herausforderung dar. Die vorliegende Dissertation untersucht, wie sich Inkrementalität zur Beschleunigung statischer Analysen nutzen lässt. Als Reaktion auf eine Programmänderung berechnet eine inkrementelle Analyse nur die Ergebnisse neu, die von der Änderung betroffen sind, und verwendet den Rest der vorherigen Ergebnisse wieder. Die Dissertation beschreibt dazu den Entwurf und die Realisierung eines neuen Frameworks, das statische Analysen automatisch inkrementell ausführen kann. Die Dissertation zeigt, dass sich mit diesem Framework erhebliche Leistungsgewinne erzielen lassen und so selbst anspruchsvolle interprozedurale Analysen auf großen Softwaresystemen in wenigen Millisekunden inkrementell ausgeführt werden können.
  • Konferenzbeitrag
    Trace-basierte Erkennung und Analyse von Speicheranomalien
    (D22, 2022) Weninger, Markus
    Moderne Programmiersprachen nutzen automatische Speicherbereinigung, um fehleranfällige manuelle Speicherverwaltung zu vermeiden. Dennoch können Anomalien wie Speicherlecks auftreten, die sich drastisch auf die Leistung einer Anwendung auswirken und sogar Abstürze herbeiführen können. Die meisten modernen Werkzeuge nutzen für ihre Speicheranalysen jedoch leider nur Speicherauszüge, d.h. sie inspizieren den Speicher nur an einem oder wenigen bestimmten Zeitpunkten. Diese bieten aber oft nicht genug Details, um zur Ursache des Problems vorzudringen. Unser Ansatz nutzt daher Traces, kontinuierliche Aufnahmen von Ereignissen wie beispielsweise Allokationen oder Speicherbereinigungsoperationen. Diese Arbeit zeigt, wie Traces genutzt werden können, um die (automatische) Speicherproblemerkennung und -analyse zu verbessern. Sie schlägt unter anderem Algorithmen zur Aufzeichnungsverarbeitung vor und führt neuartige Anomalieanalysen (z.B. die automatisierte Analyse des Wachstums von Datenstrukturen) sowie interaktive Visualisierungstechniken ein. Ferner untersucht sie, wie (unerfahrene) Benutzer sich bei der Speicheranalyse verhalten und wie Werkzeuge verbessert werden können, um diese Nutzer besser zu unterstützen und anzuleiten.