Search

Your search keyword '"Brinkmann, Raik"' showing total 12 results
Start Over Author "Brinkmann, Raik"
12 results on '"Brinkmann, Raik"'

4. A normalization method for arithmetic data-path verification

Author

Wedler, Markus, Stoffel, Dominik, Brinkmann, Raik, and Kunz, Wolfgang

Subjects
Microprocessor, Microprocessor upgrade, Circuit designer, Integrated circuit design, Bit manipulation -- Analysis, Central processing units -- Design and construction, Microprocessors -- Design and construction, Circuit design -- Research
Published
2007

6. A Formal Approach for Detecting Vulnerabilities to Transient Execution Attacks in Out-of-Order Processors.

Author

Fadiheh, Mohammad Rahmani, Müller, Johannes, Brinkmann, Raik, Mitra, Subhasish, Stoffel, Dominik, and Kunz, Wolfgang

Subjects
CYBERTERRORISM, COMPUTER security, TELECOMMUNICATION, COMPUTER programming, DATA analysis
Abstract

Transient execution attacks, such as Spectre and Meltdown, create a new and serious attack surface in modern processors. In spite of all countermeasures taken during recent years, the cycles of alarm and patch are ongoing and call for a better formal understanding of the threat and possible preventions. This paper introduces a formal definition of security with respect to transient execution attacks, formulated as a HW property. We present a formal method for security verification by HW property checking based on extending Unique Program Execution Checking (UPEC) to out-of-order processors. UPEC can be used to systematically detect all vulnerabilities to transient execution attacks, including vulnerabilities unknown so far. The feasibility of our approach is demonstrated at the example of the BOOM processor, which is a design with more than 650,000 state bits. In BOOM our approach detects a new, so far unknown vulnerability, called Spectre-STC, indicating that also single-threaded processors can be vulnerable to contention-based Spectre attacks. [ABSTRACT FROM AUTHOR]

Published
2020

8. Vorverarbeitung für die Überprüfung von Eigenschaften Sequentieller Schaltungen auf der Register-Transfer-Ebene

Author

Brinkmann, Raik

Subjects
Model checking, Zugesicherte Eigenschaft, RTL, Permutationsäquivalenz, Symmetriebrechung, bitvector, Symmetrie, System-on-Chip, bounded model checking, Vorverarbeitung, satisfiability, Verifikation, property cheking, ddc:620, Erfüllbarke, Bitvektor, verification, preprocessing, sequential circuit, Schaltwerk, symmetry
Abstract

As the sustained trend towards integrating more and more functionality into systems on a chip can be observed in all fields, their economic realization is a challenge for the chip making industry. This is, however, barely possible today, as the ability to design and verify such complex systems could not keep up with the rapid technological development. Owing to this productivity gap, a design methodology, mainly using pre designed and pre verifying blocks, is mandatory. The availability of such blocks, meeting the highest possible quality standards, is decisive for its success. Cost-effective, this can only be achieved by formal verification on the block-level, namely by checking properties, ranging over finite intervals of time. As this verification approach is based on constructing and solving Boolean equivalence problems, it allows for using backtrack search procedures, such as SAT. Recent improvements of the latter are responsible for its high capacity. Still, the verification of some classes of hardware designs, enjoying regular substructures or complex arithmetic data paths, is difficult and often intractable. For regular designs, this is mainly due to individual treatment of symmetrical parts of the search space by backtrack search procedures used. One approach to tackle these deficiencies, is to exploit the regular structure for problem reduction on the register transfer level (RTL). This work describes a new approach for property checking on the RTL, preserving the problem inherent structure for subsequent reduction. The reduction is based on eliminating symmetrical parts from bitvector functions, and hence, from the search space. Several approaches for symmetry reduction in search problems, based on invariance of a function under permutation of variables, have been previously proposed. Unfortunately, our investigations did not reveal this kind of symmetry in relevant cases. Instead, we propose a reduction based on symmetrical values, as we encounter them much more frequently in our industrial examples. Let \(f\) be a Boolean function. The values \(0\) and \(1\) are symmetrical values for a variable \(x\) in \(f\) iff there is a variable permutation \(\pi\) of the variables of \(f\), fixing \(x\), such that \(f|_{x=0} = \pi(f|_{x=1})\). Then the question whether \(f=1\) holds is independent from this variable, and it can be removed. By iterative application of this approach to all variables of \(f\), they are either all removed, leaving \(f=1\) or \(f=0\) trivially, or there is a variable \(x'\) with no such \(\pi\). The latter leads to the conclusion that \(f=1\) does not hold, as we found a counter-example either with \(x'=0\), or \(x'=1\). Extending this basic idea to vectors of variables, allows to elevate it to the RTL. There, self similarities in the function representation, resulting from the regular structure preserved, can be exploited, and as a consequence, symmetrical bitvector values can be found syntactically. In particular, bitvector term-rewriting techniques, isomorphism procedures for specially manipulated term graphs, and combinations thereof, are proposed. This approach dramatically reduces the computational effort needed for functional verification on the block-level and, in particular, for the important problem class of regular designs. It allows the verification of industrial designs previously intractable. The main contributions of this work are in providing a framework for dealing with bitvector functions algebraically, a concise description of bounded model checking on the register transfer level, as well as new reduction techniques and new approaches for finding and exploiting symmetrical values in bitvector functions. Die Arbeit beschreibt einen neuen Ansatz zur Vereinfachung von aussagenlogischen Beweisproblemen, wie sie beim Bounded-Model-Cheking (BMC) üblicherweise auftreten. Dieser Ansatz ermöglicht es, bisher unlösbare Beweisaufgaben aus dem BMC in der industriellen Praxis zu lösen, sowie bereits lösbare Beweisaufgaben wesentlich effizienter zu bewältigen. Eine Beweisaufgabe besteht darin, zu überprüfen, ob eine Bool'sche Funktion konstant wahr ist, bzw. ob eine diese Funktion repräsentierende aussagenlogische Formel allgemein gültig ist. Derartige Überprüfungen lassen sich zwar mit Techniken wie Bool'scher Erfüllbarkeit (SAT) oder Binären Entscheidungsdiagrammen (BDDs) im Prinzip lösen, doch stoßen diese Verfahren in der industriellen Praxis regelmäßig an Grenzen. Ziel der Arbeit ist es, diese Grenzen zu erweitern. Dies wird erreicht, indem das Beweisproblem vor einem Beweisversuch auf eine neuartige Weise reduziert wird. Die Reduktion findet auf einer dem Ursprungsproblem nahen Repräsentation der Bool'schen Funktion als sog. Bitvektor-Term statt, da dies eine besonders effiziente und weitreichende Reduktion begünstigt. Die Reduktion basiert einerseits darauf, die Term-Repräsentation zu vereinfachen, andererseits auf einer speziellen Zerlegung des Beweisproblems in Co-Faktoren der repräsentierten Funktion. Diese Co-Faktoren werden jeweils einzeln vereinfacht und wenn möglich durch automatische Symmetriebetrachtungen zu Äquivalenzklassen zusammengefasst. In vielen Fällen gelingt das Zusammenfassen zu einer einzigen Äquivalenzklasse. Es ist im Folgenden ausreichend, aus jeder Äquivalenzklasse einen beliebigen Repräsentanten auszuwählen und für diesen den Beweis durchzuführen. Alternativ können die Repräsentanten ihrerseits weiter zerlegt, vereinfacht und zu neuen Äquivalenzklassen zusammengefasst werden. Auf diese Weise werden nacheinander Variable eliminiert, und die resultierenden Beweisprobleme massiv vereinfacht. Reduktion und Zusammenfassung basieren auf Heuristiken und Semi-Entscheidungsverfahren für Äquivalenz und Permutationsäquivalenz von Bitvektortermen bzw. den repräsentierten Bool'schen Funktionen. Diese Verfahren beruhen ihrerseits auf Term-Rewriting- und Graphenalgorithmen. Die vorgestellte Reduktionsmethode ermöglicht bereits in einer prototypischen Implementierung die Demonstration messbarer Verbesserungen der Gesamtperformanz für BMC in praktisch relevanten Beispielen um ein bis zwei Größenordnungen. Weitere Steigerung durch Verbesserung der Implementierung und der Heuristiken scheinen durchaus möglich, bedürfen jedoch eines gewissen Implementierungsaufwandes, der den Rahmen dieser Arbeit gesprengt hätte.

Published
2003

9. Preprocessing for Property Checking of Sequential Circuits on the Register Transfer Level

Author

Brinkmann, Raik and Brinkmann, Raik

Abstract

As the sustained trend towards integrating more and more functionality into systems on a chip can be observed in all fields, their economic realization is a challenge for the chip making industry. This is, however, barely possible today, as the ability to design and verify such complex systems could not keep up with the rapid technological development. Owing to this productivity gap, a design methodology, mainly using pre designed and pre verifying blocks, is mandatory. The availability of such blocks, meeting the highest possible quality standards, is decisive for its success. Cost-effective, this can only be achieved by formal verification on the block-level, namely by checking properties, ranging over finite intervals of time. As this verification approach is based on constructing and solving Boolean equivalence problems, it allows for using backtrack search procedures, such as SAT. Recent improvements of the latter are responsible for its high capacity. Still, the verification of some classes of hardware designs, enjoying regular substructures or complex arithmetic data paths, is difficult and often intractable. For regular designs, this is mainly due to individual treatment of symmetrical parts of the search space by backtrack search procedures used. One approach to tackle these deficiencies, is to exploit the regular structure for problem reduction on the register transfer level (RTL). This work describes a new approach for property checking on the RTL, preserving the problem inherent structure for subsequent reduction. The reduction is based on eliminating symmetrical parts from bitvector functions, and hence, from the search space. Several approaches for symmetry reduction in search problems, based on invariance of a function under permutation of variables, have been previously proposed. Unfortunately, our investigations did not reveal this kind of symmetry in relevant cases. Instead, we propose a reduction based on symmetrical values, as we encounter them m, Die Arbeit beschreibt einen neuen Ansatz zur Vereinfachung von aussagenlogischen Beweisproblemen, wie sie beim Bounded-Model-Cheking (BMC) üblicherweise auftreten. Dieser Ansatz ermöglicht es, bisher unlösbare Beweisaufgaben aus dem BMC in der industriellen Praxis zu lösen, sowie bereits lösbare Beweisaufgaben wesentlich effizienter zu bewältigen. Eine Beweisaufgabe besteht darin, zu überprüfen, ob eine Bool'sche Funktion konstant wahr ist, bzw. ob eine diese Funktion repräsentierende aussagenlogische Formel allgemein gültig ist. Derartige Überprüfungen lassen sich zwar mit Techniken wie Bool'scher Erfüllbarkeit (SAT) oder Binären Entscheidungsdiagrammen (BDDs) im Prinzip lösen, doch stoßen diese Verfahren in der industriellen Praxis regelmäßig an Grenzen. Ziel der Arbeit ist es, diese Grenzen zu erweitern. Dies wird erreicht, indem das Beweisproblem vor einem Beweisversuch auf eine neuartige Weise reduziert wird. Die Reduktion findet auf einer dem Ursprungsproblem nahen Repräsentation der Bool'schen Funktion als sog. Bitvektor-Term statt, da dies eine besonders effiziente und weitreichende Reduktion begünstigt. Die Reduktion basiert einerseits darauf, die Term-Repräsentation zu vereinfachen, andererseits auf einer speziellen Zerlegung des Beweisproblems in Co-Faktoren der repräsentierten Funktion. Diese Co-Faktoren werden jeweils einzeln vereinfacht und wenn möglich durch automatische Symmetriebetrachtungen zu Äquivalenzklassen zusammengefasst. In vielen Fällen gelingt das Zusammenfassen zu einer einzigen Äquivalenzklasse. Es ist im Folgenden ausreichend, aus jeder Äquivalenzklasse einen beliebigen Repräsentanten auszuwählen und für diesen den Beweis durchzuführen. Alternativ können die Repräsentanten ihrerseits weiter zerlegt, vereinfacht und zu neuen Äquivalenzklassen zusammengefasst werden. Auf diese Weise werden nacheinander Variable eliminiert, und die resultierenden Beweisprobleme massiv vereinfacht. Reduktion und Zusammenfassung basieren auf Heuristiken und

10. Preprocessing for Property Checking of Sequential Circuits on the Register Transfer Level

Author

Brinkmann, Raik and Brinkmann, Raik

Abstract

As the sustained trend towards integrating more and more functionality into systems on a chip can be observed in all fields, their economic realization is a challenge for the chip making industry. This is, however, barely possible today, as the ability to design and verify such complex systems could not keep up with the rapid technological development. Owing to this productivity gap, a design methodology, mainly using pre designed and pre verifying blocks, is mandatory. The availability of such blocks, meeting the highest possible quality standards, is decisive for its success. Cost-effective, this can only be achieved by formal verification on the block-level, namely by checking properties, ranging over finite intervals of time. As this verification approach is based on constructing and solving Boolean equivalence problems, it allows for using backtrack search procedures, such as SAT. Recent improvements of the latter are responsible for its high capacity. Still, the verification of some classes of hardware designs, enjoying regular substructures or complex arithmetic data paths, is difficult and often intractable. For regular designs, this is mainly due to individual treatment of symmetrical parts of the search space by backtrack search procedures used. One approach to tackle these deficiencies, is to exploit the regular structure for problem reduction on the register transfer level (RTL). This work describes a new approach for property checking on the RTL, preserving the problem inherent structure for subsequent reduction. The reduction is based on eliminating symmetrical parts from bitvector functions, and hence, from the search space. Several approaches for symmetry reduction in search problems, based on invariance of a function under permutation of variables, have been previously proposed. Unfortunately, our investigations did not reveal this kind of symmetry in relevant cases. Instead, we propose a reduction based on symmetrical values, as we encounter them m, Die Arbeit beschreibt einen neuen Ansatz zur Vereinfachung von aussagenlogischen Beweisproblemen, wie sie beim Bounded-Model-Cheking (BMC) üblicherweise auftreten. Dieser Ansatz ermöglicht es, bisher unlösbare Beweisaufgaben aus dem BMC in der industriellen Praxis zu lösen, sowie bereits lösbare Beweisaufgaben wesentlich effizienter zu bewältigen. Eine Beweisaufgabe besteht darin, zu überprüfen, ob eine Bool'sche Funktion konstant wahr ist, bzw. ob eine diese Funktion repräsentierende aussagenlogische Formel allgemein gültig ist. Derartige Überprüfungen lassen sich zwar mit Techniken wie Bool'scher Erfüllbarkeit (SAT) oder Binären Entscheidungsdiagrammen (BDDs) im Prinzip lösen, doch stoßen diese Verfahren in der industriellen Praxis regelmäßig an Grenzen. Ziel der Arbeit ist es, diese Grenzen zu erweitern. Dies wird erreicht, indem das Beweisproblem vor einem Beweisversuch auf eine neuartige Weise reduziert wird. Die Reduktion findet auf einer dem Ursprungsproblem nahen Repräsentation der Bool'schen Funktion als sog. Bitvektor-Term statt, da dies eine besonders effiziente und weitreichende Reduktion begünstigt. Die Reduktion basiert einerseits darauf, die Term-Repräsentation zu vereinfachen, andererseits auf einer speziellen Zerlegung des Beweisproblems in Co-Faktoren der repräsentierten Funktion. Diese Co-Faktoren werden jeweils einzeln vereinfacht und wenn möglich durch automatische Symmetriebetrachtungen zu Äquivalenzklassen zusammengefasst. In vielen Fällen gelingt das Zusammenfassen zu einer einzigen Äquivalenzklasse. Es ist im Folgenden ausreichend, aus jeder Äquivalenzklasse einen beliebigen Repräsentanten auszuwählen und für diesen den Beweis durchzuführen. Alternativ können die Repräsentanten ihrerseits weiter zerlegt, vereinfacht und zu neuen Äquivalenzklassen zusammengefasst werden. Auf diese Weise werden nacheinander Variable eliminiert, und die resultierenden Beweisprobleme massiv vereinfacht. Reduktion und Zusammenfassung basieren auf Heuristiken und

Catalog

Books, media, physical & digital resources
See catalog results