|
Geschrieben von: Dirk Richter
|
|
Veröffentlichung zur European Joint Conferences on Theory and Practice of Software (ETAPS), 7th Workshop on Model-Based Testing in Tallin.
Abstract: Test generation and test data selection are difficult tasks for model based testing. Tests for a program can be meld to a test suite. A lot of research is done to quantify the quality and improve a test suite. Code coverage metrics estimate the quality of a test suite. This quality is fine, if the code coverage value is high or 100%. Unfortunately it might be impossible to achieve 100% code coverage because of dead code for example. There is a gap between the feasible and theoretical maximal possible code coverage value. Our review of the research indicates, none of current research %done in testing is concerned with exact gap computation. This paper presents a framework to compute such gaps exactly in an ISO-C compatible semantic and similar languages. We describe an efficient approximation of the gap in all the other cases. Thus, a tester can decide if more tests might be able or necessary to achieve better coverage.
Download: mbt12.pdf |
|
Geschrieben von: Dirk Richter
|
|
Veröffentlichung im Rahmen des 16. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'11) auf Schloss Raesfeld.
Abstract: Zur Software-Modell-Prüfung, zum modellbasierten Testen und bei der Testdaten- und Codegenerierung sind die Größe und Komplexität von Modellen entscheidende Einflussfaktoren. Aus Quellcode (z.B. C oder Java) gewonnene Modelle in Form von symbolischen Kellersystemen (SPDS) erlauben nicht nur präzisere Ergebnisse, sondern führen auch ohne Modellexplosion bei exakter Nachbildung von Rekursion zu weniger Fehlalarmen als die Modellprüfung endlicher Systeme. Derart gewonnene Modelle beschreiben allerdings viel unwichtiges Verhalten sehr detailliert, was den Zustandsraum unnötig vergrößert und damit Modell-Prüfung, Testen usw. erschwert. Eine Form zur Vermeidung dieses unwichtigen Verhalten in der Modellbeschreibung ist die Abstraktion. Dabei wird das Programm oder komplexe Modell in ein weniger detailliertes Modell überführt. Ziel dieser Arbeit ist es, unwichtige Teile der Modellbeschreibung eines SPDS durch gegebene temporale Formeln selektiv zu identifizieren und davon zu abstrahieren.
Download: kps11.pdf
|
|
Geschrieben von: Dirk Richter
|
|
Veröffentlichung im Rahmen des 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09) in Maria Taferl.
Abstract: Often, it is argued that some problems in data-flow analysis such as e.g. worst case execution time analysis are undecidable (because the halting problem is) and therefore only a conservative approximation of the desired information is possible. In this paper, we show that the semantics for some important real programming languages - in particular those used for programming embedded devices - can be modeled as finite state systems or pushdown machines. This implies that the halting problem becomes decidable and therefore invalidates popular arguments for using conservative analysis.
Download: kps09z.pdf |
|
Geschrieben von: Dirk Richter
|
|
Veröffentlichung im Rahmen des 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09) in Maria Taferl.
Abstract: Intervallanalysen bestimmen zu einem gegebenen Programm konservative oder nicht-konservative Wertebereiche von Variablen. Desto genauer diese Wertebereiche bestimmt werden können, desto präziser sind die darauf basierenden Analysen wie z.B. die Laufzeitschätzung von Programmen bzw. führen zu weniger Fehlalarmen wie z.B. bei der Prüfung auf Feldzugriffe außerhalb zulässiger Indizees (ArrayOutOfBounds). Bei unbeschränkter Rekursion und unbeschränktem Speicher (Heap/Halde) ist das Problem der Bestimmung von Wertebereichen maximaler Genauigkeit (auch als exakte Wertebereiche bezeichnet) unentscheidbar. Im Folgenden wird gezeigt, wie bei unbeschränkter Rekursion und beschränktem Speicher derartige exakte Wertebereiche in polynomieller Zeit (bzgl. Modellgröße) bestimmt werden können.
Download: kps09.pdf |
|
|
Geschrieben von: Dirk Richter
|
|
Veröffentlichung im Rahmen des 26. Workshops "Programmiersprachen und Rechenkonzepte" der Gesellschaft für Informatik Anfang Mai 2009.
Abstract: Symbolische Modelle definieren Zustandssysteme, welche zur Software-Modell-Prüfung, zum Modell basierten Testen und zur Codegenerierung genutzt werden können. Die Größe und Komplexität dieser Modelle sind dabei entscheidende Einflussfaktoren und sollten möglichst vereinfacht werden. Aus Quellcode gewonnene Modelle in Form von symbolischen Kellersystemen (SPDS) erlauben nicht nur präzisere Ergebnisse, sondern führen auch ohne Modellexplosion bei exakter Nachbildung von Rekursion zu weniger Fehlalarmen. Für diese SPDS wurden zwei verschiedene Ansätze verfolgt, die die innere Struktur der Zustände ausnutzen, um den Zustandsraum der Modelle weiter zu verkleinern. Eigene Experimente zeigen, dass diese die Modellprüfung erheblich beschleunigen bzw. die Modellprüfung erst ermöglichen.
Download: rp09.pdf |
|
Geschrieben von: Dirk Richter
|
|
Proc. of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Ecole Polytechnique and CNAM, Paris, France June 2-4, 2009
Abstract: We present two approaches for the Euclidean TSP which compute high quality tours for large instances. Both approaches are based on pseudo backbones consisting of all common edges of good tours. The first approach starts with some precomputed good tours. Using this approach we found record tours for seven VLSI nstances. The second approach is window based and constructs from scratch very ood tours of huge TSP instances, e. g., the World TSP.
Download: ctw09.pdf |
|
Geschrieben von: Dirk Richter
|
|
Proc. of the 4th Workshop on Combinatorial and Algorithmic Aspects of Networking, LNCS 4852, pp. 99-110, Halifax, Canada, Aug 2007 Abstract: Helsgaun has introduced and implemented the lower tolerances (a-values) for an approximation of Held-Karp’s 1-tree with the purpose to improve the Lin-Kernighan’s Heuristic (LKH) for the Symmetric TSP (STSP). The LKH appears to exceed the performance of all STSP heuristic algorithms proposed to date. In this paper we improve the Helsgaun’s LKH based on an approximation of Zhang and Looks’ backbones by tolerances and an extension of double bridges further combined with implementation details by all of which we guide the search process instead of Helsgaun’s α-values. Our computational results are competitive and lead to improved solutions for some of the VLSI instances announced at the TSP homepage. Download: tolerances12.pdf |
|
Geschrieben von: Dirk Richter
|
|
Veröffentlichung im Rahmen des 25. Workshops "Programmiersprachen und Rechenkonzepte" der Gesellschaft für Informatik Anfang Mai 2008. Zur Software-Modell-Prüfung sowie zum Modell basiertem Testen als auch bei der Codegenerierung sind die Größe und Komplexität von Modellen entscheidende influssfaktoren. Ich untersuche Modelle in Form von symbolischen Kellersystemen, da diese in der Lage sind, Rekursion exakt nachzubilden. Für diese symbolischen Kellersysteme abe ich verschiedene Modellanalysen und Modellreduktionstechniken in einem Tool HalSPSI implementiert, welche die Software-Modell-Prüfung in meinen Tests für den Modellprüfer Moped erheblich beschleunigen bzw. die Modellprüfung erst ermöglichen oder sogar erübrigen. Letzteres ist z.B. dann der Fall, wenn durch statische Modellanalysen meines Tool HalSPSI die nicht Erreichbarkeit von Fehlerkonfigurationen nachgewiesen werden kann.
Download: paper_rp08.pdf |
|
|
|
|
|
Seite 1 von 2 |
Veröffentlichungen 
