Interpolant-based model checking has been shown effective on large verification instances, as it efficiently combines automated abstraction and fixed-point checks. On the other hand, methods based on variable quantification have proved their ability to remove free inputs, thus projecting the search space over state variables. In this paper we propose an integrated approach combining the abstraction power of interpolation with techniques relying on AIG and/or BDD representations of states, supporting variable quantification and fixed-point checks. The underlying idea of this combination is to adopt AIG- or BDD-based quantifications to limit and restrict the search space (and the complexity) of the interpolant-based approach. The exploited strategies, individually well-known, are integrated with a new flavor, specifically designed to improve their effectiveness on large verification instances. Experimental results, oriented to hard-to-solve verification problems, show the robustness of our approach.

Trading off SAT Search and Variable Quantifications for Effective Unbounded Model Checking / Cabodi, Gianpiero; Camurati, Paolo Enrico; Murciano, Marco; GARCIA GALEANO, LUZ AMANDA; Nocco, Sergio; Quer, Stefano. - STAMPA. - (2008), pp. 205-212. (Intervento presentato al convegno FMCAD 2008: Formal Methods in Computer Aided Design tenutosi a Portland, OR, USA nel 17-20 novembre 2008).

Trading off SAT Search and Variable Quantifications for Effective Unbounded Model Checking

CABODI, Gianpiero;CAMURATI, Paolo Enrico;MURCIANO, MARCO;GARCIA GALEANO, LUZ AMANDA;NOCCO, SERGIO;QUER, Stefano
2008

Abstract

Interpolant-based model checking has been shown effective on large verification instances, as it efficiently combines automated abstraction and fixed-point checks. On the other hand, methods based on variable quantification have proved their ability to remove free inputs, thus projecting the search space over state variables. In this paper we propose an integrated approach combining the abstraction power of interpolation with techniques relying on AIG and/or BDD representations of states, supporting variable quantification and fixed-point checks. The underlying idea of this combination is to adopt AIG- or BDD-based quantifications to limit and restrict the search space (and the complexity) of the interpolant-based approach. The exploited strategies, individually well-known, are integrated with a new flavor, specifically designed to improve their effectiveness on large verification instances. Experimental results, oriented to hard-to-solve verification problems, show the robustness of our approach.
2008
9781424427352
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/1847472
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo