Path Predicate Abstraction

Path Predicate Abstraction (PPA) is a formalism suitable for describing the abstraction/refinement relationship between highly abstract models at an Electronic System Level (ESL) and their implementations at the Register Transfer Level (RTL). In such a relationship the properties of the ESL model translate, without further proof, to corresponding properties of the RTL implementation, i.e., the ESL model is sound with respect to the implementation. Thus, verification results obtained based on the much simpler ESL model can be trusted as valid also for the RTL implementation. If the creation of such sound ESL models can be made efficient in practice then the costs for the verification of digital systems can be drastically reduced.

This dissertation contributes the theoretical framework of PPA as well as approaches for applying PPA efficiently in practice, both "bottom up" to create sound abstractions for already existing RTL implementations and as an integrated part of a "top down" design flow. In both approaches the soundness of the abstraction is established by formal property checking. All involved properties are of a specific form facilitating SAT-based proof algorithms that scale well, as shown in experimental results, also for large industrial designs.