公开(公告)号：US07743352B2

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

申请号：US11689906

申请日：2007-03-22

申请人： Malay Ganai ,  Aarti Gupta

发明人： Malay Ganai ,  Aarti Gupta

IPC分类号： G07F17/50

CPC分类号： G06F17/504

摘要： Verification friendly models for SAT-based formal verification are generated from a given high-level design wherein during construction the following guidelines are enforced: 1) No re-use of functional units and registers; 2) Minimize the use of muxes and sharing; 3) Reduce the number of control steps; 4) Avoid pipelines; 5) Chose functional units from “verification friendly” library; 6) Re-use operations; 7) Perform property-preserving slicing; 8) Support “assume” and “assert” in the language specification; and 8) Use external memory modules instead of register arrays.

摘要翻译： 从给定的高级设计生成基于SAT的形式验证的验证友好模型，其中在施工期间执行以下准则：1）不重复使用功能单元和寄存器; 2）最小化使用复用和共享; 3）减少控制步骤的数量; 4）避免管道; 5）从“验证友好”库中选择功能单位; 6）重用操作; 7）进行维护保养切片; 8）在语言规范中支持“假设”和“断言”; 和8）使用外部存储器模块而不是寄存器阵列。

公开(公告)号：US07853906B2

公开(公告)日：2010-12-14

申请号：US11689803

申请日：2007-03-22

申请人： Malay Ganai ,  Aarti Gupta

发明人： Malay Ganai ,  Aarti Gupta

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

CPC分类号： G06F17/504

摘要： An accelerated High-Level Bounded Model Checking method that efficiently extracts high-level information from the model, uses that extracted information to obtain an improved verification model, and applies relevant information on-the-fly to simplify the BMC-problem instances.

摘要翻译： 一种从模型中有效提取高级别信息的加速高级有界模型检查方法，利用提取的信息获取改进的验证模型，并即时应用相关信息，简化BMC问题实例。

公开(公告)号：US07930659B2

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

申请号：US11422069

申请日：2006-06-03

申请人： Franjo Ivancic ,  Aarti Gupta ,  Malay Ganai ,  Himanshu Jain

发明人： Franjo Ivancic ,  Aarti Gupta ,  Malay Ganai ,  Himanshu Jain

IPC分类号： G06F17/50

CPC分类号： G06F11/3608

摘要： A system and method is disclosed for formal verification of software programs that advantageously improves performance of an abstraction-refinement loop in the verification system.

摘要翻译： 公开了用于软件程序的形式验证的系统和方法，其有利地提高了验证系统中的抽象精炼循环的性能。

公开(公告)号：US08005661B2

公开(公告)日：2011-08-23

申请号：US12116668

申请日：2008-05-07

申请人： Malay Ganai ,  Aarti Gupta

发明人： Malay Ganai ,  Aarti Gupta

IPC分类号： G06F9/45 ,  G06F9/455 ,  G06F7/60 ,  G06F12/00 ,  G06F13/00

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

摘要： A computer implemented method for modeling and verifying concurrent systems which uses Satisfiability-Modulo Theory (SMT)-based Bounded Model Checking (BMC) to detect violations of safety properties such as data races. A particularly distinguishing aspect of our inventive method is that we do not introduce wait-cycles in our symbolic models for the individual threads, which are typically required for considering an interleaved execution of the threads. These wait-cycles are detrimental to the performance of BMC. Instead, we first create independent models for the different threads, and add inter-model constraints lazily, incrementally, and on-the-fly during BMC unrolling to capture the sequential consistency and synchronization semantics. We show that our constraints provide a sound and complete modeling with respect to the considered semantics. One benefit of our lazy modeling method is the reduction in the size of the BMC problem instances, thereby, improving the verification performance in both runtime and memory.

摘要翻译： 一种用于建模和验证并发系统的计算机实现方法，其使用基于可信性 - 模理论（SMT）的有界模型检查（BMC）来检测诸如数据竞赛之类的安全属性的违规。 我们的创造性方法的特别区别在于，我们不在针对各个线程的符号模型中引入等待周期，这通常是考虑线程的交错执行所需要的。 这些等待周期对BMC的性能是不利的。 相反，我们首先为不同的线程创建独立的模型，并在BMC展开期间懒洋洋地，逐步地和即时地添加模型间约束，以捕获顺序一致性和同步语义。 我们显示我们的约束提供了一个关于所考虑的语义的完整的建模。 我们的懒惰建模方法的一个好处是减少了BMC问题实例的大小，从而提高了运行时和内存中的验证性能。

公开(公告)号：US08707272B2

公开(公告)日：2014-04-22

申请号：US13343361

申请日：2012-01-04

申请人： Malay Ganai

发明人： Malay Ganai

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

CPC分类号： G06F8/314 ,  G06F11/3604

摘要： A computer implemented testing methodology employing a scenario-driven modeling of specific instances of bug patterns that commonly occur in concurrent programs which encodes these instances in an SMT-based symbolic analysis. Such modeling and encoding advantageously allow the symbolic analysis framework to focus on real bugs, thereby allowing effective utilization of resources. Experimentation determined a number of previously unknown bugs in public benchmarks and advantageously scenario-specific modeling and encoding improves the scalability of symbolic technique and, therefore, improves overall quality of concurrency testing.

摘要翻译： 一种计算机实现的测试方法，采用对基于SMT的符号分析中编码这些实例的并发程序中通常发生的错误模式的特定实例的场景驱动建模。 这种建模和编码有利地允许符号分析框架专注于真实的错误，从而允许资源的有效利用。 实验确定了许多以前未知的公共基准测试中的错误，有利的是场景特定的建模和编码改进了符号技术的可扩展性，从而提高了并发测试的整体质量。

公开(公告)号：US08504330B2

公开(公告)日：2013-08-06

申请号：US12236684

申请日：2008-09-24

申请人： Malay Ganai

发明人： Malay Ganai

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

CPC分类号： G06F9/5066

摘要： A system and method for bounded model checking of computer programs includes decomposing a program having at least one reachable property node for bounded model checking (BMC) into sub-problems by employing a tunneling and slicing-based (TSR) BMC reduction method. The sub-problems of the TSR method are partitioned in a distributed environment, where the distributed environment includes at least one master processing unit and at least one client unit. The sub-problems are solved by each client independently of other clients to reduce communication overhead and provide scalability.

摘要翻译： 一种用于计算机程序的有界模型检查的系统和方法包括：通过采用基于隧道和切片的（TSR）BMC简化方法，将具有至少一个用于有界模型检查（BMC）的可达属性节点的程序分解为子问题。 TSR方法的子问题在分布式环境中进行分区，其中分布式环境包括至少一个主处理单元和至少一个客户端单元。 子问题由每个客户端独立于其他客户端解决，以减少通信开销并提供可扩展性。

公开(公告)号：US20100251222A1

公开(公告)日：2010-09-30

申请号：US12410429

申请日：2009-03-24

申请人： Malay Ganai

发明人： Malay Ganai

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

CPC分类号： G06F8/433

摘要： A computer implemented method for obtaining a completeness threshold (CT) in Bounded Model Checking systems for software programs.

摘要翻译： 一种计算机实现的方法，用于在软件程序的有界模型检查系统中获得完整性阈值（CT）。