Scalable Techniques for Formal Verification

این کتاب در مورد تأیید رسمی است، یعنی استفاده از استدلال ریاضی برای اطمینان از اجرای صحیح سیستم‌های محاسباتی. با استفاده روزافزون از سیستم های c-puting در برنامه های کاربردی حیاتی و امنیتی، اطمینان از اجرای صحیح آن سیستم ها برای رفاه ما اهمیت فزاینده ای پیدا می کند. در دهه گذشته، راستی‌آزمایی رسمی پیشرفت چشمگیری در تحلیل سیستم‌های صنعتی، به‌ویژه در حوزه تأیید سخت‌افزار داشته است. یک مزیت کلیدی راستی‌آزمایی رسمی این است که تضمینی ریاضی برای صحت آن‌ها (تا دقت مدل‌های رسمی و صحت ابزارهای سنجش صدا) ارائه می‌کند. در این فرآیند، تجزیه و تحلیل می تواند خطاهای ظریف طراحی را آشکار کند. راستی‌آزمایی رسمی به‌ویژه در بررسی اشکالات گوشه‌ای که تشخیص آنها از طریق شبیه‌سازی و آزمایش سنتی دشوار است، مؤثر است. با این وجود، و علیرغم وعده آن، استفاده از تأیید رسمی تاکنون در یک ابزار اعتبارسنجی طراحی صنعتی محدود بوده است. مشکلات در پذیرش در مقیاس بزرگ شامل موارد زیر است (1) تأیید قیاسی با استفاده از اثبات‌کننده‌های قضیه اغلب شامل تلاش دستی غیرممکن و بازدارنده و (2) رویه‌های تصمیم‌گیری خودکار (مثلاً بررسی مدل) می‌تواند به سرعت به مرزهای آن برسد. زمان و حافظه موجود این کتاب پیشرفت‌های اخیر در تکنیک‌های تأیید رسمی را ارائه می‌کند و کاربرد این تکنیک‌ها را در تضمین قابلیت اطمینان سیستم‌های مقیاس بزرگ مورد بحث قرار می‌دهد. ما با راستی‌آزمایی طیف وسیعی از سیستم‌های محاسباتی، از برنامه‌های چندگانه تا پروتکل‌های همزمان و ماشین‌های خط لوله سروکار داریم.

This book is about formal veri?cation, that is, the use of mathematical reasoning to ensure correct execution of computing systems. With the increasing use of c- puting systems in safety-critical and security-critical applications, it is becoming increasingly important for our well-being to ensure that those systems execute c- rectly. Over the last decade, formal veri?cation has made signi?cant headway in the analysis of industrial systems, particularly in the realm of veri?cation of hardware. A key advantage of formal veri?cation is that it provides a mathematical guarantee of their correctness (up to the accuracy of formal models and correctness of r- soning tools). In the process, the analysis can expose subtle design errors. Formal veri?cation is particularly effective in ?nding corner-case bugs that are dif?cult to detect through traditional simulation and testing. Nevertheless, and in spite of its promise, the application of formal veri?cation has so far been limited in an ind- trial design validation tool ?ow. The dif?culties in its large-scale adoption include the following (1) deductive veri?cation using theorem provers often involves - cessive and prohibitive manual effort and (2) automated decision procedures (e. g. , model checking) can quickly hit the bounds of available time and memory. This book presents recent advances in formal veri?cation techniques and d- cusses the applicability of the techniques in ensuring the reliability of large-scale systems. We deal with the veri?cation of a range of computing systems, from - quential programsto concurrentprotocolsand pipelined machines.