Uni-Logo
English       Login
Rechnerarchitektur
        Startseite         |         Institut für Informatik         |         Technische Fakultät
 

Projekte

AVACS: Automatic Verification and Analysis of Complex Systems

Projektbeschreibung

Am "SFB" sind neben IRA die Freiburger Lehrstühle für Künstliche Intelligenz, Softwaretechnik und Betriebssysteme sowie Forschergruppen der Universitäten Oldenburg, Saarbrücken, der Tschechischen Akademie der Wissenschaften in Prag und des Max-Planck-Instituts Saarbrücken beteiligt. Der Projektinhalt ist die Analyse und formale Verifikation komplexer Systeme. Das neue European Train Control Standard wird als Fallstudie zur Erprobung der entwickelten Methoden dienen. Die Wissenschaftler unseres Lehrstuhls werden insbesondere ihre Kompetenz im Bereich der Basistechnologien in den SFB einbringen. Die Genehmigung des SFB für zunächst acht Jahre (mit einer Verlängerungsmöglichkeit für bis zu weiteren vier Jahren) bietet vor allem jungen Forschern eine ausgezeichnete Möglichkeit, strategische Kompetenz in Verifikation von hybriden und Echtzeitsystemen aufzubauen. Wir sehen diesen Vertrauensbeweis seitens der DFG auch als eine Bestätigung unserer bisherigen Forschungsarbeit. Wie kaum ein anderes Gebiet muss sich die Informationstechnik der Herausforderung stellen, dass ihre Artefakte flexibel und mit vergleichsweise geringem Aufwand technisch machbar sind, bei gleichzeitiger Verdoppelung der technischen Leistungsfähigkeit ihrer Basiskomponenten alle 2 Jahre. Dies hat dazu geführt, dass komplexe Computer-basierte Systeme gebaut und flächendeckend eingesetzt werden, von deren korrektem Verhalten man sich zwar durch Testen zu überzeugen versucht, deren Funktionsweise man in ihrer Gesamtheit aber nicht überschaut. Was technisch gemacht wird übersteigt bei weitem das, was man analytisch versteht. Dieses ist nicht nur vom wissenschaftlichen Standpunkt unbefriedigend, es birgt auch ein hohes Risiko für Leib und Leben der Menschen, die diesen Systemen etwa in Haushalt, Auto, Bahn, Flugzeug, Kraftwerken, Industrieanlagen ausgesetzt sind, ganz abgesehen von den hohen ökonomischen Schäden, wenn es durch Fehler zur Zerstörung teurer Anlagen (Ariane V) kommt oder wenn Schadensersatzleistungen anderer Art notwendig werden. Der Transregio SFB AVACS widmet sich besonders den Systemen, die in sicherheitskritischen Bereichen eingesetzt werden und dort physikalische und technische Prozesse kontrollieren und steuern, wie etwa im Transportwesen bei Auto, Eisenbahn und Flugzeug. Die Komplexität der in diesen Anwendungen verwendeten Systeme hat mehrere Ursachen. Erstens, wenn physikalische Prozesse beobachtet und gesteuert werden, kommt es zur Interaktion von diskreten und kontinuierlichen Systemen, die mathematisch besonders komplex sind in ihrer Modellierung und Analyse. Steuerungsvorgänge müssen in vorgegebenen Zeitschranken ablaufen und Steuersignale so berechnen, dass der physikalische Prozess innerhalb des sicheren Bereiches bleibt. Eine zweite Ursache von Komplexität liegt in der Architektur dieser Systeme, wo eine große Anzahl von Komponenten miteinander vernetzt sind, miteinander kommunizieren und in kooperierender Weise die Funktion des Gesamtsystems bestimmen. Drittens sind solche Systeme mobil sowohl im physikalischen, wie im informationstechnischen Sinn. Mobile Computerprogamme und -systeme müssen in ständig wechselnden Umgebungen mit oftmals unbekannten Parametern zuverlässig und fehlertolerant funktionieren. Die für AVACS ins Auge gefassten Forschungsziele beruhen auf der Erkenntnis, dass Systemzuverlässigkeit nur dann flächendeckend entscheidend verbessert werden kann, wenn kritische Eigenschaften sowohl in der Spezifikation wie in der Realisierung mit automatisierten Techniken, also auf Knopfdruck, vom Softwareingenieur analysisert und überprüft werden können. Die kombinatorische Komplexität der Systemzustände ist zu hoch, die mathematischen und logischen Fähigkeiten der Ingenieure oft nicht ausreichend, und der zeitliche Aufwand zu groß, als dass nichtautomatische Methoden in großem Stil einsetzbar wären. Die Vision von AVACS ist es, dass nach Ablauf des Projektes die Zeitanforderungen auch an hochgradig vernetzte Systeme automatisch überprüft werden können, sowohl auf der Modellebene, wie auch für die auf der realen Hardware ablaufenden Maschinenprogramme. AVACS wird dabei in neue Größenordnungen von Systemkomplexität (Anzahl der Systemzustände, Nutzung moderner Hardwarekomponenten, algorithmisch optimierte Controller mit spezialisierten Datenstrukturen) vorstoßen. Bei den hybriden Systemen, wo diskrete Controller kontinuierliche wie diskontinuierliche physikalische Prozesse beobachten und steuern, wird AVACS wesentlich realistischere Systemmodelle als bisher betrachtet beherrschen helfen und gleichzeitig die Differenziertheit der an diesen Modellen automatisch überprüfbaren Aussagen über Stabilität und Sicherheit wesentlich verfeinern. Schließlich wird AVACS Methoden entwickeln, die eine neue Qualität der Analyse des globalen Zusammenspiels von Teilkomponenten komplexer Systeme herstellen. Hierzu zählen Techniken zur Untersuchung der Interaktion von Steuergeräten in Bezug auf die Realisierung einer Gesamtfunktionalität, zur Analyse von Kooperationsmechanismen bei sich dynamisch ändernden Kommunikationstopologien sowie zum formalen Nachweis globaler Verfügbarkeitsanforderungen. Durch die in AVACS geplanten Arbeiten werden Analysen dieser wichtigen Systemeigenschaften zum Teil erstmalig automatisiert und auch für solche Systeme einsetzbar werden, die sich bisher aufgrund ihrer Komplexität entsprechenden Untersuchungen entzogen. Zur Verwirklichung dieser Vision braucht es die Kombination von Methoden der mathematischen Semantik komplexer Systeme (Fundierung) mit algorithmisch-deduktiver Experise (Automatisierung), wie sie im AVACS-Konsortium gegeben ist.

Laufzeit

Von 01.01.2004 (unbegrenzt)

Projektleitung

Becker B

Publikationen


Jahre: 2016 | 2015 | 2014 | 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007

    2016

    Icon: top nach oben zur Jahresübersicht
    • Karsten Scheibler, Dominik Erb, Bernd Becker
      Accurate CEGAR-based ATPG in Presence of Unknown Values for Large Industrial Designs
      2016 Conf. on Design, Automation and Test in Europe
    • Karsten Scheibler, Dominik Erb, Bernd Becker
      Applying Tailored Formal Methods to X-ATPG
      2016 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”
    • Dominik Erb, Karsten Scheibler, Michael A. Kochte, Matthias Sauer, Hans-Joachim Wunderlich, Bernd Becker
      Mixed 01X-RSL-Encoding for Fast and Accurate ATPG with Unknowns
      2016 21st Asia and South Pacific Design Automation Conference

    2015

    Icon: top nach oben zur Jahresübersicht
    • Karsten Scheibler, Dominik Erb, Bernd Becker
      Improving Test Pattern Generation in Presence of Unknown Values beyond Restricted Symbolic Logic
      2015 to be published at European Test Symposium (ETS)
    • Dominik Erb, Karsten Scheibler, Matthias Sauer, Sudhakar M. Reddy, Bernd Becker
      Multi-Cycle Circuit Parameter Independent ATPG for Interconnect Open Defects
      2015 33rd VLSI Test Symposium (VTS)
    • Karina Gitina, Ralf Wimmer, Sven Reimer, Matthias Sauer, Christoph Scholl, Bernd Becker
      Solving DQBF Through Quantifier Elimination
      2015 Conf. on Design, Automation and Test in Europe
    • Karsten Scheibler, Leonore Winterer, Ralf Wimmer, Bernd Becker
      Towards Verification of Artificial Neural Networks
      2015 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”

    2014

    Icon: top nach oben zur Jahresübersicht
    • Dominik Erb, Karsten Scheibler, Matthias Sauer, Sudhakar M. Reddy, Bernd Becker
      Circuit Parameter Independent Test Pattern Generation for Interconnect Open Defects
      2014 23nd IEEE Asian Test Symposium (ATS)
    • Sven Reimer, Matthias Sauer, Tobias Schubert, Bernd Becker
      Incremental Encoding and Solving of Cardinality Constraints
      2014 International Symposium on Automated Technology for Verification and Analysis, Springer International Publishing, Band: 8837, Seiten: 297 - 313
    • Sven Reimer, Matthias Sauer, Paolo Marin, Bernd Becker
      QBF with Soft Variables
      2014 International Workshop on Automated Verification of Critical Systems (AVOCS)
    • Matthias Sauer, Sven Reimer, Sudhakar M. Reddy, Bernd Becker
      Efficient SAT-based Circuit Initialization for Large Designs
      2014 Int'l Conf. on VLSI Design
    • Dominik Erb, Karsten Scheibler, Matthias Sauer, Bernd Becker
      Efficient SMT-based ATPG for Interconnect Open Defects
      2014 Conf. on Design, Automation and Test in Europe
    • Karsten Scheibler, Bernd Becker
      Implication Graph Compression inside the SMT Solver iSAT3
      2014 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”
    • Dominik Erb, Karsten Scheibler, Michael Kochte, Matthias Sauer, Hans-Joachim Wunderlich, Bernd Becker
      Test Pattern Generation in Presence of Unknown Values Based on Restricted Symbolic Logic
      2014 Int'l Test Conf.
    • Karsten Scheibler, Bernd Becker
      Using Interval Constraint Propagation for Pseudo-Boolean Constraint Solving
      2014 Formal Methods in Computer-Aided Design
    • Sven Reimer, Matthias Sauer, Tobias Schubert, Bernd Becker
      Using MaxBMC for Pareto-Optimal Circuit Initialization
      2014 Conf. on Design, Automation and Test in Europe

    2013

    Icon: top nach oben zur Jahresübersicht
    • Ulrich Loup, Karsten Scheibler, Florian Corzilius, Erika Ábrahám, Bernd Becker
      A Symbiosis of Interval Constraint Propagation and Cylindrical Algebraic Decomposition
      2013 CADE, Springer, Band: 7898, Seiten: 193 - 207
    • Matthias Sauer, Sven Reimer, Stefan Kupferschmid, Tobias Schubert, Paolo Marin, Bernd Becker
      Applying BMC, Craig Interpolation and MAX-SAT to Functional Justification in Sequential Circuits
      2013 RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion
    • Karsten Scheibler, Matthias Sauer, Kohei Miyase, Bernd Becker
      Controlling Small-Delay Test Power Consumption using Satisfibility Modulo Theory Solving
      2013 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
    • Matthias Sauer, Sven Reimer, Tobias Schubert, Ilia Polian, Bernd Becker
      Efficient SAT-Based Dynamic Compaction and Relaxation for Longest Sensitizable Paths
      2013 Conf. on Design, Automation and Test in Europe, Seiten: 448 - 453
    • Karina Gitina, Sven Reimer, Matthias Sauer, Ralf Wimmer, Christoph Scholl, Bernd Becker
      Equivalence Checking for Partial Implementations Revisited
      2013 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, Universität Rostock ITMZ, Seiten: 61 - 70
    • Karina Gitina, Sven Reimer, Matthias Sauer, Ralf Wimmer, Christoph Scholl, Bernd Becker
      Equivalence Checking of Partial Designs using Dependency Quantified Boolean Formulae
      2013 Int'l Conf. on Computer Design, IEEE Computer Society, Seiten: 396 - 403
    • Matthias Sauer, Sven Reimer, Ilia Polian, Tobias Schubert, Bernd Becker
      Provably Optimal Test Cube Generation Using Quantified Boolean Formula Solving
      2013 ASP Design Automation Conf.
    • Karsten Scheibler, Stefan Kupferschmid, Bernd Becker
      Recent Improvements in the SMT Solver iSAT
      2013 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”
    • Der Andere Verlag, Seite: 266
      Über Craigsche Interpolation und deren Anwendung in der formalen Modellprüfung
      ISBN: 978-3-86247-411-0
      Stefan Kupferschmid

    2012

    Icon: top nach oben zur Jahresübersicht
    • Sven Reimer, Florian Pigorsch, Christoph Scholl, Bernd Becker
      Enhanced Integration of QBF Solving Techniques
      2012 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, Seiten: 133 - 143
    • Matthias Sauer, Stefan Kupferschmid, Alexander Czutro, Sudhakar M. Reddy, Bernd Becker
      Analysis of Reachable Sensitisable Paths in Sequential Circuits with SAT and Craig Interpolation
      2012 Int'l Conf. on VLSI Design
    • Matthias Sauer, Stefan Kupferschmid, Alexander Czutro, Ilia Polian, Sudhakar M. Reddy, Bernd Becker
      Functional Justification in Sequential Circuits using SAT and Craig Interpolation
      2012 GI/ITG Workshop “Testmethoden und Zuverlässigkeit von Schaltungen und Systemen”
    • Matthias Sauer, Stefan Kupferschmid, Alexander Czutro, Ilia Polian, Sudhakar M. Reddy, Bernd Becker
      Functional Test of Small-Delay Faults using SAT and Craig Interpolation
      2012 Int'l Test Conf., Seiten: 1 - 8

    2011

    Icon: top nach oben zur Jahresübersicht
    • Stefan Kupferschmid, Bernd Becker
      Craig interpolation in the presence of non-linear constraints
      2011 Formal Modeling and Analysis of Timed Systems, Springer, Seiten: 240 - 255
    • Stefan Kupferschmid, Bernd Becker
      Craigsche Interpolation für Boolesche Kombinationen linearer und nichtlinearer Ungleichungen
      2011 OFFIS-Institut für Informatik, Seiten: 279 - 288
    • Stefan Kupferschmid, Matthew Lewis, Tobias Schubert, Bernd Becker
      Incremental preprocessing methods for use in BMC
      2011 Formal Methods in System Design, Band: 39, Seiten: 185 - 204
    • Sven Reimer, Florian Pigorsch, Christoph Scholl, Bernd Becker
      Integration of Orthogonal QBF Solving Techniques
      2011 Conf. on Design, Automation and Test in Europe, Seiten: 149 - 154
    • Ernst Althaus, Bernd Becker, Daniel Dumitriu, Stefan Kupferschmid
      Integration of an LP solver into interval constraint propagation
      2011 Int'l Conf. on Combinatorial optimization and applications, Springer, Seiten: 343 - 356
    • Stefan Kupferschmid, Bernd Becker, Tino Teige, Martin Fränzle
      Proof Certificates and Non-linear Arithmetic Constraints
      2011 IEEE Design and Diagnostics of Electronic Circuits and Systems, Seiten: 429 - 434
    • Andreas Eggers, Evgeny Kruglov, Stefan Kupferschmid, Karsten Scheibler, Tino Teige, Christoph Weidenbach
      Superposition modulo non-linear arithmetic
      2011 Int'l Symp. on Frontiers of Combining Systems, Springer, Seiten: 119 - 134

    2010

    Icon: top nach oben zur Jahresübersicht
    • Stefan Kupferschmid, Matthew Lewis, Tobias Schubert, Bernd Becker
      Incremental Preprocessing Methods for use in BMC
      2010 Int'l Workshop on Hardware Verification
    • Christian Miller, Stefan Kupferschmid, Bernd Becker
      Exploiting Craig Interpolants in Bounded Model Checking for Incomplete Designs
      2010 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, Band: 13, Seiten: 77 - 86
    • Christian Miller, Stefan Kupferschmid, Matthew Lewis, Bernd Becker
      Encoding Techniques, Craig Interpolants and Bounded Model Checking for Incomplete Designs
      2010 Theory and Applications of Satisfiability Testing, Springer, Seiten: 194 - 208
    • Natalia Kalinnik, Erika Ábrahám, Tobias Schubert, Ralf Wimmer, Bernd Becker
      Exploiting Different Strategies for the Parallelization of an SMT Solver
      2010 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, Fraunhofer Verlag, Seiten: 97 - 106

    2009

    Icon: top nach oben zur Jahresübersicht
    • Natalia Kalinnik, Tobias Schubert, Erika Ábrahám, Ralf Wimmer, Bernd Becker
      Picoso - A Parallel Interval Constraint Solver
      2009 Int'l Conf. on Parallel and Distributed Processing Techniques and Applications, CSREA Press, Seiten: 473 - 479
    • Christoph Scholl, Stefan Disch, Florian Pigorsch, Stefan Kupferschmid
      Computing Optimized Representations for Non-convex Polyhedra by Detection and Removal of Redundant Linear Constraints
      2009 Tools and Algorithms for the Construction and Analysis of Systems, Springer, Band: 5505, Seiten: 383 - 397
    • Andreas Eggers, Natalia Kalinnik, Stefan Kupferschmid, Tino Teige
      Challenges in Constraint-Based Analysis of Hybrid Systems
      2009 Recent Advances in Constraints, Springer, Band: 5655, Seiten: 51 - 65
    • Stefan Kupferschmid, Tino Teige, Bernd Becker, Martin Fränzle
      Proofs of Unsatisfiability for mixed Boolean and Non-linear Arithmetic Constraint Formulae
      2009 GI/ITG/GMM Workshop “Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen”, Seiten: 27 - 36

    2008

    Icon: top nach oben zur Jahresübersicht
    • Christoph Scholl, Stefan Disch, Florian Pigorsch, Stefan Kupferschmid
      Using an SMT Solver and Craig Interpolation to Detect and Remove Redundant Linear Constraints in Representations of Non-Convex Polyhedra
      2008 Int'l Workshop on Satisfiability Modulo Theories, Seiten: 18 - 26
    • Andreas Eggers, Natalia Kalinnik, Stefan Kupferschmid, Tino Teige
      Challenges in Constraint-based Analysis of Hybrid Systems
      2008 ERCIM Workshop on Constraint Solving and Constraint Logic Programming
    • Jochen Eisinger
      Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic
      2008 EACSL Annual Conf. on Computer Science Logic, Springer-Verlag, Seiten: 430 - 444

    2007

    Icon: top nach oben zur Jahresübersicht
    • Bernd Becker, Jochen Eisinger, Felix Klaedtke
      Parallelization of Decision Procedures for Automatic Structures
      2007 Workshop on Omega-Automata