In order to make model checking applicable to realistic problems, simplification techniques are essential. Models may be simplified eliminating the variables that do not appear in the cone-of-influence (COI) of the properties under verification. Efficient COI computation is thus required. Algorithms based on depth-first visits may become cumbersome when they must be applied several times; for instance, when multiple properties must be verified on the same model. An alternative is to resort to graph-labeling methods, trading-off time for memory. Modeling the problem in terms of graphs, this paper develops a technique based on bitmaps that keeps the amount of memory needed within acceptable limits. The paper also describes a portfolio of optimizations of the original algorithm that allow even more reductions in memory usage. Experimental results show that the basic algorithm and its optimized versions perform very well on standard benchmark circuits used in the model-checking community.

A graph-labeling approach for efficient cone-of-influence computation in model-checking problems with multiple properties / Cabodi, Gianpiero; Camurati, Paolo Enrico; Quer, Stefano. - In: SOFTWARE-PRACTICE & EXPERIENCE. - ISSN 0038-0644. - ELETTRONICO. - 46:4(2016), pp. 493-511. [10.1002/spe.2321]

A graph-labeling approach for efficient cone-of-influence computation in model-checking problems with multiple properties

CABODI, Gianpiero;CAMURATI, Paolo Enrico;QUER, Stefano
2016

Abstract

In order to make model checking applicable to realistic problems, simplification techniques are essential. Models may be simplified eliminating the variables that do not appear in the cone-of-influence (COI) of the properties under verification. Efficient COI computation is thus required. Algorithms based on depth-first visits may become cumbersome when they must be applied several times; for instance, when multiple properties must be verified on the same model. An alternative is to resort to graph-labeling methods, trading-off time for memory. Modeling the problem in terms of graphs, this paper develops a technique based on bitmaps that keeps the amount of memory needed within acceptable limits. The paper also describes a portfolio of optimizations of the original algorithm that allow even more reductions in memory usage. Experimental results show that the basic algorithm and its optimized versions perform very well on standard benchmark circuits used in the model-checking community.
File in questo prodotto:
File Dimensione Formato  
spe.2321.pdf

non disponibili

Tipologia: 2a Post-print versione editoriale / Version of Record
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 1.67 MB
Formato Adobe PDF
1.67 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/2629364
 Attenzione

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