公开(公告)号：US07346486B2

公开(公告)日：2008-03-18

申请号：US11040409

申请日：2005-01-21

申请人： Franjo Ivancic ,  Pranav N. Ashar ,  Malay Ganai ,  Aarti Gupta ,  Zijiang Yang

发明人： Franjo Ivancic ,  Pranav N. Ashar ,  Malay Ganai ,  Aarti Gupta ,  Zijiang Yang

IPC分类号： G06F9/45 ,  G06F7/60 ,  G06F9/44 ,  G06F11/00

CPC分类号： G06F17/504 ,  G06F11/3608

摘要： A system and method is disclosed for formal verification of software programs that advantageously translates the software, which can have bounded recursion, into a Boolean representation comprised of basic blocks and which applies SAT-based model checking to the Boolean representation.

摘要翻译： 公开了一种软件程序的形式验证的系统和方法，其有利地将可以具有有界递归的软件翻译成由基本块组成的布尔表示，并将基于SAT的模型检查应用于布尔表示。

公开(公告)号：US08131532B2

公开(公告)日：2012-03-06

申请号：US11422068

申请日：2006-06-03

申请人： Srihari Cadambi ,  Aleksandr Zaks ,  Franjo Ivancic ,  Ilya Shlyakhter ,  Zijiang Yang ,  Malay Ganai ,  Aarti Gupta ,  Pranav Ashar

发明人： Srihari Cadambi ,  Aleksandr Zaks ,  Franjo Ivancic ,  Ilya Shlyakhter ,  Zijiang Yang ,  Malay Ganai ,  Aarti Gupta ,  Pranav Ashar

IPC分类号： G06F9/45 ,  G06F9/44 ,  G06F9/455

CPC分类号： G06F11/3608

摘要： A system and method is disclosed for formal verification of software programs that advantageously bounds the ranges of values that a variable in the software can take during runtime.

摘要翻译： 公开了用于软件程序的形式验证的系统和方法，其有利地限制了在运行时期间软件中变量可以采用的值的范围。

公开(公告)号：US20050166167A1

公开(公告)日：2005-07-28

申请号：US11040409

申请日：2005-01-21

申请人： Franjo Ivancic ,  Pranav Ashar ,  Malay Ganai ,  Aarti Gupta ,  Zijiang Yang

发明人： Franjo Ivancic ,  Pranav Ashar ,  Malay Ganai ,  Aarti Gupta ,  Zijiang Yang

IPC分类号： G06F17/50

CPC分类号： G06F17/504 ,  G06F11/3608

摘要： A system and method is disclosed for formal verification of software programs that advantageously translates the software, which can have bounded recursion, into a Boolean representation comprised of basic blocks and which applies SAT-based model checking to the Boolean representation.

摘要翻译： 公开了一种软件程序的形式验证的系统和方法，其有利地将可以具有有界递归的软件翻译成由基本块组成的布尔表示，并将基于SAT的模型检查应用于布尔表示。

公开(公告)号：US07693690B2

公开(公告)日：2010-04-06

申请号：US11367665

申请日：2006-03-03

申请人： Chao Wang ,  Aarti Gupta ,  Zijiang Yang ,  Franjo Ivancic

发明人： Chao Wang ,  Aarti Gupta ,  Zijiang Yang ,  Franjo Ivancic

IPC分类号： G06F17/50 ,  G06F13/00

CPC分类号： G06F11/3608 ,  G06F17/504

摘要： A symbolic disjunctive image computation method for software models which exploits a number of characteristics unique to software models. More particularly, and according to our inventive method, the entire software model is decomposed into a disjunctive set of submodules and a separate set of transition relations are constructed. An image/reachability analysis is performed wherein an original image computation is divided into a set of image computation steps that may be performed on individual submodules, independently from any others. Advantageously, our inventive method exploits variable locality during the decomposition of the original model into the submodules. By formulating this decomposition as a multi-way hypergraph partition problem, we advantageously produce a small set of submodules while simultaneously minimizing the number of live variable in each individual submodule. Our inventive method produces a set of disjunctive transition relations directly from the software model, without producing a conjunctive transition relation—as is necessary in the prior art. In addition, our inventive method exploits the exclusive use of live variables in addition to novel search strategies which provide still further benefit to our method.

摘要翻译： 用于软件模型的符号分离图像计算方法，其利用软件模型独特的许多特征。 更具体地，根据本发明的方法，整个软件模型被分解成一个分离的子模块集合，并构建了一组单独的过渡关系。 执行图像/可达性分析，其中原始图像计算被划分为可以独立于任何其他方式对各个子模块执行的一组图像计算步骤。 有利地，本发明的方法在原始模型分解成子模块期间利用可变局部性。 通过将此分解形式作为多路超图分区问题，我们有利地产生一小组子模块，同时最小化每个子模块中的实时变量数量。 我们的创造性方法直接从软件模型产生一组分离过渡关系，而不产生结合过渡关系 - 这在现有技术中是必需的。 此外，除了新颖的搜索策略之外，我们的创造性方法还利用了实时变量的独家使用，这为我们的方法提供了更多的益处。

公开(公告)号：US07203917B2

公开(公告)日：2007-04-10

申请号：US10795384

申请日：2004-03-09

申请人： Malay Ganai ,  Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

发明人： Malay Ganai ,  Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

IPC分类号： G06F17/50

CPC分类号： G06F17/504

摘要： There is provided a method of solving a SAT problem comprising partitioning SAT-formula clauses in the SAT problem into a plurality of partitions. Each of said plurality of partitions is solved as a separate process each, thereby constituting a plurality of processes where each of said process communicates only with a subset of the plurality of processes.

摘要翻译： 提供了一种解决SAT问题的方法，包括将SAT问题中的SAT公式子句分成多个分区。 所述多个分区中的每一个分别被解决为单独的处理，从而构成多个处理，其中每个所述进程仅与多个进程的子集进行通信。

公开(公告)号：US07711525B2

公开(公告)日：2010-05-04

申请号：US10157486

申请日：2002-05-30

申请人： Malay Ganai ,  Lintao Zhang ,  Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

发明人： Malay Ganai ,  Lintao Zhang ,  Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

IPC分类号： G06F17/10

CPC分类号： G06F17/504

摘要： A method for bounded model checking of arbitrary Linear Time Logic temporal properties. The method comprises translating properties associated with temporal operators F(p), G(p), U(p, q) and X(p) into property checking schemas comprising Boolean satisfiability checks, wherein F represents an eventuality operator, G represents a globally operator, U represents an until operator and X represents a next-time operator. The overall property is checked in a customized manner by repeated invocations of the property checking schemas for F(p), G(p), U(p, q), X(p) operators and standard handling of atomic propositions and Boolean operators.

摘要翻译： 一种用于任意线性时间逻辑时间属性的有界模型检查的方法。 该方法包括将与时间运算符F（p），G（p），U（p，q）和X（p）相关联的属性转换成包括布尔可满足性检查的属性检查模式，其中F表示可能性运算符，G表示全局 运算符，U表示直到运算符，X表示下一运算符。 通过重复调用F（p），G（p），U（p，q），X（p）运算符的属性检查模式以及原子命题和布尔运算符的标准处理来检查整体属性。

公开(公告)号：US20070044084A1

公开(公告)日：2007-02-22

申请号：US11367665

申请日：2006-03-03

申请人： Chao Wang ,  Aarti Gupta ,  Zijiang Yang ,  Franjo Ivancic

发明人： Chao Wang ,  Aarti Gupta ,  Zijiang Yang ,  Franjo Ivancic

IPC分类号： G06F9/45 ,  G06F9/44

CPC分类号： G06F11/3608 ,  G06F17/504

摘要： A symbolic disjunctive image computation method for software models which exploits a number of characteristics unique to software models. More particularly, and according to our inventive method, the entire software model is decomposed into a disjunctive set of submodules and a separate set of transition relations are constructed. An image/reachability analysis is performed wherein an original image computation is divided into a set of image computation steps that may be performed on individual submodules, independently from any others. Advantageously, our inventive method exploits variable locality during the decomposition of the original model into the submodules. By formulating this decomposition as a multi-way hypergraph partition problem, we advantageously produce a small set of submodules while simultaneously minimizing the number of live variable in each individual submodule. Our inventive method produces a set of disjunctive transition relations directly from the software model, without producing a conjunctive transition relation—as is necessary in the prior art. In addition, our inventive method exploits the exclusive use of live variables in addition to novel search strategies which provide still further benefit to our method.

摘要翻译： 用于软件模型的符号分离图像计算方法，其利用软件模型独特的许多特征。 更具体地，根据本发明的方法，整个软件模型被分解成一个分离的子模块集合，并且构建了一组单独的过渡关系。 执行图像/可达性分析，其中原始图像计算被划分为可以独立于任何其他方式对各个子模块执行的一组图像计算步骤。 有利地，本发明的方法在原始模型分解成子模块期间利用可变局部性。 通过将此分解形式作为多路超图分区问题，我们有利地产生一小组子模块，同时最小化每个子模块中的实时变量数量。 我们的创造性方法直接从软件模型产生一组分离过渡关系，而不产生结合过渡关系 - 这在现有技术中是必需的。 此外，除了新颖的搜索策略之外，我们的创造性方法还利用了实时变量的独家使用，这为我们的方法提供了更多的益处。

公开(公告)号：US07742907B2

公开(公告)日：2010-06-22

申请号：US10762499

申请日：2004-01-23

申请人： Aarti Gupta ,  Malay Ganai ,  Zijiang Yang ,  Pranav Ashar

发明人： Aarti Gupta ,  Malay Ganai ,  Zijiang Yang ,  Pranav Ashar

IPC分类号： G06F17/50 ,  G06F9/45

CPC分类号： G06F17/504

摘要： A method of obtaining a resolution-based proof of unsatisfiability using a SAT procedure for a hybrid Boolean constraint problem comprising representing constraints as a combination of clauses and interconnected gates. The proof is obtained as a combination of clauses, circuit gates and gate connectivity constraints sufficient for unsatisfiability.

摘要翻译： 使用针对混合布尔约束问题的SAT过程获得基于分辨率的不满足证明的方法，包括将约束表示为子句和互连门的组合。 证明是作为条件，电路门和门连接约束的组合获得的，足以满足不满足性。

公开(公告)号：US06728665B1

公开(公告)日：2004-04-27

申请号：US09693979

申请日：2000-10-23

申请人： Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

发明人： Aarti Gupta ,  Zijiang Yang ,  Pranav Ashar

IPC分类号： G06F710

CPC分类号： G06F17/504

摘要： A method of performing image or pre-image computation for a system is disclosed. The method comprises representing the system by a finite state model; representing state sets using Binary Decision Diagrams (BDDs); performing a satisfiabilty checking (SAT) based backtrack search algorithm, wherein, the SAT decomposes the search over an entire solution space into multiple sub-problems, and wherein a BDD-based image computation is used to solve each sub-problem by enumerating multiple solutions from the solution space. Further, a method for pruning a search space in a SAT procedure is disclosed. The method comprises using BDD Bounding against an implicit disjunction or conjunction of a given set of BDDs; continuing search if a partial assignment of variables satisfies the implicit disjunction or conjunction, and backtracking if a partial assignment of variables does not satisfy the implicit disjunction or conjunction.

摘要翻译： 公开了一种用于系统执行图像或预图像计算的方法。 该方法包括通过有限状态模型表示系统; 使用二进制决策图（BDD）表示状态集; 执行基于可靠性检查（SAT）的回溯搜索算法，其中，SAT将整个解空间的搜索分解成多个子问题，并且其中使用基于BDD的图像计算来通过枚举多个解决方案来解决每个子问题 从解决方案空间。 此外，公开了一种在SAT过程中修剪搜索空间的方法。 该方法包括使用BDD边界抵抗一组给定的BDD的隐式分离或连接; 如果变量的部分分配满足隐式分离或连接，并且如果变量的部分分配不满足隐式分离或连接，则继续搜索。

公开(公告)号：US07926039B2

公开(公告)日：2011-04-12

申请号：US11692421

申请日：2007-03-28

申请人： Chao Wang ,  Zijiang Yang ,  Aarti Gupta

发明人： Chao Wang ,  Zijiang Yang ,  Aarti Gupta

IPC分类号： G06F9/44 ,  G06F9/45

CPC分类号： G06F9/44589

摘要： An improved method for automatically improving the precision of an extrapolation operator used, for example, in software program verification in connection with the static analysis and model checking of the software programs which rely on fix-point computation. In particular, a new extrapolation-with-care-set operator, together with a method for gradually increasing the precision of this operation by tightening the care set.

摘要翻译： 一种改进的方法，用于自动提高外推算子的精度，例如，在依赖于固定点计算的软件程序的静态分析和模型检查的软件程序验证中。 特别地，一种新的外推护理操作器，以及通过收紧护理套件逐渐增加该操作的精度的方法。