Gouw, Stijn de ; de Boer, Frank S. ; Bubel, Richard ; Hähnle, Reiner ; Rot, Jurriaan ; Steinhöfel, Dominic (2017)
Verifying OpenJDK's Sort Method for Generic Collections.
In: Journal of Automated Reasoning
doi: 10.1007/s10817-017-9426-4
Artikel, Bibliographie
Kurzbeschreibung (Abstract)
TimSort is the main sorting algorithm provided by the Java standard library and many other programming frameworks. Our original goal was functional verification of TimSort with mechanical proofs. However, during our verification attempt we discovered a bug which causes the implementation to crash by an uncaught exception. In this paper, we identify conditions under which the bug occurs, and from this we derive a bug-free version that does not compromise performance. We formally specify the new version and verify termination and the absence of exceptions including the bug. This verification is carried out mechanically with KeY, a state-of-the-art interactive verification tool for Java. We provide a detailed description and analysis of the proofs. The complexity of the proofs required extensions and new capabilities in KeY, including symbolic state merging.
| Typ des Eintrags: | Artikel |
|---|---|
| Erschienen: | 2017 |
| Autor(en): | Gouw, Stijn de ; de Boer, Frank S. ; Bubel, Richard ; Hähnle, Reiner ; Rot, Jurriaan ; Steinhöfel, Dominic |
| Art des Eintrags: | Bibliographie |
| Titel: | Verifying OpenJDK's Sort Method for Generic Collections |
| Sprache: | Deutsch |
| Publikationsjahr: | August 2017 |
| Titel der Zeitschrift, Zeitung oder Schriftenreihe: | Journal of Automated Reasoning |
| DOI: | 10.1007/s10817-017-9426-4 |
| URL / URN: | https://doi.org/10.1007/s10817-017-9426-4 |
| Kurzbeschreibung (Abstract): | TimSort is the main sorting algorithm provided by the Java standard library and many other programming frameworks. Our original goal was functional verification of TimSort with mechanical proofs. However, during our verification attempt we discovered a bug which causes the implementation to crash by an uncaught exception. In this paper, we identify conditions under which the bug occurs, and from this we derive a bug-free version that does not compromise performance. We formally specify the new version and verify termination and the absence of exceptions including the bug. This verification is carried out mechanically with KeY, a state-of-the-art interactive verification tool for Java. We provide a detailed description and analysis of the proofs. The complexity of the proofs required extensions and new capabilities in KeY, including symbolic state merging. |
| Fachbereich(e)/-gebiet(e): | 20 Fachbereich Informatik 20 Fachbereich Informatik > Software Engineering |
| Hinterlegungsdatum: | 16 Mai 2018 09:43 |
| Letzte Änderung: | 27 Jul 2021 16:17 |
| PPN: | |
| Export: | |
| Suche nach Titel in: | TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum