TU Darmstadt / ULB / TUbiblio

Sound Program Transformation Based on Symbolic Execution and Deduction

Ji, Ran (2014)
Sound Program Transformation Based on Symbolic Execution and Deduction.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

In this thesis, we are concerned with the safety and security of programs. The problems addressed here are the correctness of SiJa (a subset of Java) source code and Java bytecode, and the information flow security of SiJa programs. A lot of research has been made on these topics, but almost all of them study each topic independently and no approach can handle all of these aspects. We propose a uniform framework that integrates the effort of proving correctness and security into one process. The core concept for this uniform approach is sound program transformation based on symbolic execution and deduction. The correctness of SiJa source code is verified with KeY, a symbolic execution based approach. Partial evaluation actions are interleaved during symbolic execution to reduce the proof size. By synthesizing the symbolic execution tree achieved in the source code verification phase, we can generate a program that is bisimilar to, but also more optimized than, the original one with respect to a set of observable locations. The soundness of program transformation is proven. Apply the sound program transformation approach, we can generate a program bisimilar to the original program with respect to the low security level variables. This results in a more precise analysis of information flow security than the approaches based on security type systems. We can also generate Java bytecode from SiJa source code program transformation approach, where the the correctness of the Java bytecode is guaranteed and compiler verification is not necessary.

Typ des Eintrags: Dissertation
Erschienen: 2014
Autor(en): Ji, Ran
Art des Eintrags: Erstveröffentlichung
Titel: Sound Program Transformation Based on Symbolic Execution and Deduction
Sprache: Englisch
Referenten: Hähnle, Prof. Dr. Reiner ; Beckert, Prof. Dr. Bernhard
Publikationsjahr: Juni 2014
Datum der mündlichen Prüfung: 18 Dezember 2013
URL / URN: http://tuprints.ulb.tu-darmstadt.de/4021
Kurzbeschreibung (Abstract):

In this thesis, we are concerned with the safety and security of programs. The problems addressed here are the correctness of SiJa (a subset of Java) source code and Java bytecode, and the information flow security of SiJa programs. A lot of research has been made on these topics, but almost all of them study each topic independently and no approach can handle all of these aspects. We propose a uniform framework that integrates the effort of proving correctness and security into one process. The core concept for this uniform approach is sound program transformation based on symbolic execution and deduction. The correctness of SiJa source code is verified with KeY, a symbolic execution based approach. Partial evaluation actions are interleaved during symbolic execution to reduce the proof size. By synthesizing the symbolic execution tree achieved in the source code verification phase, we can generate a program that is bisimilar to, but also more optimized than, the original one with respect to a set of observable locations. The soundness of program transformation is proven. Apply the sound program transformation approach, we can generate a program bisimilar to the original program with respect to the low security level variables. This results in a more precise analysis of information flow security than the approaches based on security type systems. We can also generate Java bytecode from SiJa source code program transformation approach, where the the correctness of the Java bytecode is guaranteed and compiler verification is not necessary.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

Die vorliegende Arbeit beschäftigt sich mit der technischen Sicherheit (engl. Safety) sowie der Informationssicherheit (engl. Security) von Programmen. Im Speziellen betrachten wir die Korrektheit von SiJa-Programmen, einer Teilmenge von Java, im Quellcode und dem daraus erzeugten Java-Bytecode. In der aktuellen Forschung werden die einzelnen Aspekte fast ausschließlich getrennt behandelt. Das heißt, es wird nur die technische Sicherheit oder nur die Informationssicherheit von Programmen betrachtet und dann entweder nur mit Bezug auf den Quellcode oder nur für das kompilierte Programm. Wir schlagen stattdessen ein Rahmenwerk vor, das die unterschiedlichen Aspekte in einem einzigen Prozess vereint. Die Grundidee des Rahmenwerks ist ein einheitlicher Ansatz zur beweisbar korrekten Programmtransformation unter Anwendung von Techniken aus der Deduktion sowie der symbolischen Programmausführung. Mithilfe von KeY werden die SiJa-Programme (im Quellcode) verifiziert und deren Korrektheit sichergestellt. Die Verifikationstechnik beruht auf symbolischer Ausführung. Um die Korrektheitsbeweise klein zu halten, werden abwechselnd Programmspezialisierungsschritte und symbolische Ausführungsschritte angewendet. Aus dem während der Verifikationsphase konstruierten symbolischen Ausführungsbaum erzeugen wir ein zum Ursprungsprogramm bezüglich des beobachtbaren Programmzustandes äquivalentes und optimiertes transformiertes Programm. Die Korrektheit der Programmtransformation wird in dieser Arbeit bewiesen. Ferner wenden wir diesen Ansatz an, um ein Programm zu generieren, welches bezüglich Variablen mit einer niedrigen Sicherheitsstufe das gleiche Verhalten aufweist wie das ursprüngliche Programm. Damit ist es uns möglich eine präzisiere Informationsflussanalyse zu realisieren als vergleichbare typ-basierte Systeme. Des weiteren erlaubt das Rahmenwerk SiJa-Quellcode in Java-Bytecode zu kompilieren, ohne das dessen Korrektheit bewiesen werden muss, da sie aus der Verifikation des Quellcodes folgt. Insbesondere ist dank unseres Ansatzes eine Verifikation des Compilers nicht notwendig.

Deutsch
URN: urn:nbn:de:tuda-tuprints-40211
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik
Hinterlegungsdatum: 29 Jun 2014 19:55
Letzte Änderung: 29 Jun 2014 19:55
PPN:
Referenten: Hähnle, Prof. Dr. Reiner ; Beckert, Prof. Dr. Bernhard
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 18 Dezember 2013
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen