Beyond Safety: Customized SAT-based Model Checking - Technical Paper from DAC 2005

NEC Laboratories America

Paper by Malay K Ganai, Aarti Gupta and Pranav Ashar.

Model checking of safety properties has taken a significant lead over non-safety properties in recent years. To bridge the gap, we propose dedicated SAT-based model checking algorithms for properties beyond safety. Previous bounded model checking (BMC) approaches have relied on either converting such properties to safety checking, or finding proofs by deriving termination criteria using loop-free path analysis. Instead, our approach uses a customized SAT-based formulation for bounded model checking of non-safety properties, and determines the completeness bounds for liveness using unbounded SAT-based analysis. Our main contributions are: 1) Customized property translations for LTL formulas for BMC, with novel features that utilize partitioning, learning, and incremental formulation. Customized translations not only improve the BMC performance significantly in comparison to standard monolithic LTL translations, but also allow efficient derivation and use of completeness bounds. Though we discuss the translation schemas for liveness, they can be easily extended to handle other LTL properties as well. 2) Customized formulations for determining completeness bounds for liveness using SAT-based unbounded model checking (UMC) rather than using loop-free path analysis. These formulations comprise greatest fixed-point and least fixedpoint computations to efficiently handle nested properties using SAT-based quantification approaches. We show the effectiveness of our overall approach for checking liveness on public benchmarks and several industry designs.


Read the complete story ...


Review Article Be the first to review this article

Featured Video
Editorial
Peggy AycinenaWhat Would Joe Do?
by Peggy Aycinena
H-1B Visa: de Geus’ tragedy looms large
Peggy AycinenaIP Showcase
by Peggy Aycinena
IP for Cars: Lawsuits are like Sandstorms
More Editorial  
Jobs
Technical Support Engineer for EDA Careers at Freemont, CA
ASIC/FPGA Design Engineer for Palo Alto Networks at Santa Clara, CA
Lead Java Platform Engineer IOT-WEB for EDA Careers at San Francisco Area, CA
Technical Support Engineer EU/Germany/UK for EDA Careers at N/A, United Kingdom
Staff Software Engineer - (170059) for brocade at San Jose, CA
CAD/CAM Regional Account Manager (Pacific Northwest) for Vero Software Inc. at Seattle, WA
Upcoming Events
Embedded Systems Conference ESC Boston 2017 at Boston Convention & Exhibition Center Boston MA - May 3 - 4, 2017
2017 GPU Tech Conference at San Jose McEnery Convention Center 150 West San Carlos Street San Jose CA - May 8 - 11, 2017
High Speed Digital Design and PCB Layout at 13727 460 Ct SE North Bend WA - May 9 - 11, 2017
Nanotech 2017 Conference & Expo at Gaylord National Hotel & Convention Center WA - May 14 - 17, 2017
DAC2017



Internet Business Systems © 2017 Internet Business Systems, Inc.
595 Millich Dr., Suite 216, Campbell, CA 95008
+1 (408)-337-6870 — Contact Us, or visit our other sites:
AECCafe - Architectural Design and Engineering TechJobsCafe - Technical Jobs and Resumes GISCafe - Geographical Information Services  MCADCafe - Mechanical Design and Engineering ShareCG - Share Computer Graphic (CG) Animation, 3D Art and 3D Models
  Privacy Policy