{"id":184116,"date":"2005-05-20T00:00:00","date_gmt":"2009-10-31T13:23:33","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/msr-research-item\/model-checking-of-predicate-abstracted-programs-without-bdds\/"},"modified":"2016-09-09T10:01:29","modified_gmt":"2016-09-09T17:01:29","slug":"model-checking-of-predicate-abstracted-programs-without-bdds","status":"publish","type":"msr-video","link":"https:\/\/www.microsoft.com\/en-us\/research\/video\/model-checking-of-predicate-abstracted-programs-without-bdds\/","title":{"rendered":"Model Checking of Predicate Abstracted Programs without BDDs"},"content":{"rendered":"<div class=\"asset-content\">\n<p>In recent years, software model checking has been offered as a viable solution to the &#8220;bug hunt&#8221; in software.  Although only in its infancy, software model checking has shown promise in tackling this very difficult problem.  In this talk, emphasis will be placed on the model checking within the verification process, whereby the abstracted Boolean program (modeled as a finite transition system) undergoes scrutiny.  Conventional BDD-based model checking tools may suffer from space and\/or computational limitations for large state spaces.  Instead, we offer a new model checking paradigm that is based on SAT rather than BDDs.<\/p>\n<p>While there has been some work on SAT-based state space traversal, they have been centered on the concept of &#8220;blocking clauses&#8221;, which is a direct derivation from conflict-driven learning in SAT solvers.  On the other hand, we offer a completely different way of learning, in which knowledge is obtained from successes rather than conflicts.  In our framework, equivalent search spaces form the knowledge base over which learning is performed.  With our approach, significant space and time reductions are achieved, where conflict-driven methods could not.  Our initial findings demonstrated that several orders of magnitude reduction in computation effort can be obtained.<\/p>\n<\/div>\n<p><!-- .asset-content --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In recent years, software model checking has been offered as a viable solution to the &#8220;bug hunt&#8221; in software. Although only in its infancy, software model checking has shown promise in tackling this very difficult problem. In this talk, emphasis will be placed on the model checking within the verification process, whereby the abstracted Boolean [&hellip;]<\/p>\n","protected":false},"featured_media":195327,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr_hide_image_in_river":0,"footnotes":""},"research-area":[],"msr-video-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-session-type":[],"msr-impact-theme":[],"msr-pillar":[],"msr-episode":[],"msr-research-theme":[],"class_list":["post-184116","msr-video","type-msr-video","status-publish","has-post-thumbnail","hentry","msr-locale-en_us"],"msr_download_urls":"","msr_external_url":"https:\/\/youtu.be\/ypV00zzbh90","msr_secondary_video_url":"","msr_video_file":"","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/184116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-video"}],"version-history":[{"count":0,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video\/184116\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/195327"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=184116"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=184116"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=184116"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=184116"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=184116"},{"taxonomy":"msr-session-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-session-type?post=184116"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=184116"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=184116"},{"taxonomy":"msr-episode","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-episode?post=184116"},{"taxonomy":"msr-research-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-theme?post=184116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}