公开(公告)号：US20120197829A1

公开(公告)日：2012-08-02

申请号：US13018643

申请日：2011-02-01

申请人： Aditya V. Nori ,  Sriram K. Rajamani ,  Rahul Srinivasan ,  Sumit Gulwani

发明人： Aditya V. Nori ,  Sriram K. Rajamani ,  Rahul Srinivasan ,  Sumit Gulwani

IPC分类号： G06F15/18

CPC分类号： G06N7/005

摘要： A quantified belief propagation (QBP) algorithm receives as input an existentially quantified boolean formula (QBF) of existentially quantified boolean variables, universally quantified variables, and boolean operators. A tripartite graph is constructed, and includes (i) there-exists nodes that correspond to and represent the existentially quantified variables, (ii) for-all nodes that correspond to and represent the universally quantified variables, and (iii) sub-formula nodes that correspond to and represent sub-formulas of the QBF. A set of boolean values of the existentially quantified variables is found by (i) passing a first message from an arbitrary sub-formula node to an arbitrary for-all node, and (ii) in response, passing a second message from the arbitrary for-all node to the arbitrary sub-formula node.

摘要翻译： 量化信念传播（QBP）算法接收存在量化的布尔变量，通用量化变量和布尔运算符的存在量化布尔公式（QBF）作为输入。 构建三方图，并且包括（i）存在对应于并表示存在量化变量的节点，（ii）对应于并表示通用量化变量的所有节点，以及（iii）子公式节点 它们对应于并表示QBF的子公式。 通过（i）将第一个消息从任意子公式节点传递到任意的全部所有节点，找到存在量化变量的一组布尔值，并且（ii）作为响应，将任意的第二个消息从任意的 - 所有节点到任意子公式节点。

公开(公告)号：US20130239093A1

公开(公告)日：2013-09-12

申请号：US13415850

申请日：2012-03-09

申请人： Aditya V. Nori ,  Sriram K. Rajamani ,  Rahul Kumar ,  Aws Albarghouthi

发明人： Aditya V. Nori ,  Sriram K. Rajamani ,  Rahul Kumar ,  Aws Albarghouthi

IPC分类号： G06F9/44

CPC分类号： G06F9/44589

摘要： Technologies pertaining to top-down interprocedural analysis of a computer program are described herein. A query is received for processing over a root procedure in the computer program. Responsive to the query being received, the root procedure is explored, and calls to sub-procedures are located. Sub-queries are generated upon encountering the calls to the sub-procedures, and execution of the sub-queries is performed in parallel across multiple computing nodes.

摘要翻译： 本文描述了关于计算机程序的自顶向下过程间分析的技术。 接收到用于在计算机程序中的根过程进行处理的查询。 响应于正在接收的查询，探索根程序，并调用子程序。 子查询是在遇到对子程序的调用时生成的，子查询的执行在多个计算节点之间并行执行。

公开(公告)号：US20090282289A1

公开(公告)日：2009-11-12

申请号：US12115633

申请日：2008-05-06

申请人： Aditya V. Nori ,  Sriram K. Rajamani ,  Robert J. Simmons ,  Nels Beckman

发明人： Aditya V. Nori ,  Sriram K. Rajamani ,  Robert J. Simmons ,  Nels Beckman

IPC分类号： G06F11/36

CPC分类号： G06F11/3608

摘要： A “property checker” uses light-weight symbolic execution to prove that software programs satisfy safety properties by simultaneously performing program testing and program abstraction. A simple example of safety properties includes conditions that must be satisfied for proper program execution, such as whether an application properly interfaces with API methods or functions. Program tests are an “under-approximation” of program behavior, and abstractions are an “over-approximation” of the program. This simultaneous testing either finds a test-case that reaches an error state, or finds an abstraction showing that no path in the state space of the program can reach any error state. If a test-case reaches an error state, the property checker has discovered a violation of the safety property. Conversely, if no path in the state space can reach any error state, the property checker has proved that the program satisfies the desired safety property.

摘要翻译： “属性检查器”使用轻量符号执行来证明软件程序通过同时执行程序测试和程序抽象来满足安全属性。 安全属性的一个简单示例包括必须满足适当程序执行的条件，例如应用程序是否与API方法或功能正确连接。 程序测试是程序行为的“近似”，抽象是程序的“过近似”。 这种同时测试可以找到达到错误状态的测试用例，或者发现一个抽象表明程序状态空间中的任何路径都不能达到任何错误状态。 如果测试用例达到错误状态，则属性检查器发现违反了安全属性。 相反，如果状态空间中没有路径可以达到任何错误状态，则属性检查器已经证明该程序满足所需的安全属性。

公开(公告)号：US20130144812A1

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

申请号：US13308571

申请日：2011-12-01

申请人： Arun Tejasvi Chaganty ,  Akash Lal ,  Aditya V. Nori ,  Sriram Rajamani

发明人： Arun Tejasvi Chaganty ,  Akash Lal ,  Aditya V. Nori ,  Sriram Rajamani

IPC分类号： G06F15/18

CPC分类号： G06N7/005

摘要： Various technologies described herein pertain to approximating an inputted probabilistic model for statistical relational learning. An initial approximation of formulae included in an inputted probabilistic model can be formed, where the initial approximation of the formulae omits axioms included in the inputted probabilistic model. Further, an approximated probabilistic model of the inputted probabilistic model can be constructed, where the approximated probabilistic model includes the initial approximation of the formulae. Moreover, the approximated probabilistic model and evidence can be fed to a relational learning engine, and a most probable explanation (MPE) world can be received from the relational learning engine. The evidence can comprise existing valuations of a subset of relations included in the inputted probabilistic model. The MPE world can include valuations for the relations included in the inputted probabilistic model. The MPE world can be outputted when the input probabilistic model lacks an axiom violated by the MPE world.

摘要翻译： 本文描述的各种技术涉及近似输入的用于统计关系学习的概率模型。 可以形成包括在输入的概率模型中的公式的初始近似，其中公式的初始近似省略包括在输入的概率模型中的公理。 此外，可以构造输入的概率模型的近似概率模型，其中近似概率模型包括公式的初始近似。 此外，近似的概率模型和证据可以被馈送到关系学习引擎，并且可以从关系学习引擎接收到最可能的解释（MPE）世界。 证据可以包括输入的概率模型中包括的关系子集的现有估值。 MPE世界可以包括输入概率模型中包含的关系的估值。 当输入概率模型缺少MPE世界违反的公理时，可以输出MPE世界。

公开(公告)号：US08065565B2

公开(公告)日：2011-11-22

申请号：US12245581

申请日：2008-10-03

申请人： Trishul Chilimbi ,  Krishna Kumar Mehra ,  Benjamin Robert Liblit ,  Aditya V. Nori ,  Kapil Vaswani

发明人： Trishul Chilimbi ,  Krishna Kumar Mehra ,  Benjamin Robert Liblit ,  Aditya V. Nori ,  Kapil Vaswani

IPC分类号： G06F11/00

CPC分类号： G06F11/366

摘要： The method executes the application and if there are no errors from the execution of the application, the method ends. If errors exist, the errors are collected from the execution of the application in an error report. Labeled application paths are created by adding a unique label to individual application paths where the application paths are individual loops and individual functions in the application. An analysis is created of the labeled application paths by executing the application with the labeled paths, reviewing the error report for data related to the labels and if an error is sufficiently related to application paths with labels, storing the path that created the errors in a report. If an error is not sufficient related to the application path with labels, the method is repeated by the creating the analysis again by substituting additional application paths for the application paths.

摘要翻译： 该方法执行应用程序，如果应用程序的执行没有错误，则该方法结束。 如果存在错误，则会在错误报告中从应用程序的执行中收集错误。 标签的应用程序路径是通过向单个应用程序路径添加唯一标签创建的，其中应用程序路径是单个循环和应用程序中的单个功能。 通过使用标记的路径执行应用程序来创建标记的应用程序路径的分析，查看与标签相关的数据的错误报告，并且如果错误与具有标签的应用程序路径充分相关，则将创建错误的路径存储在 报告。 如果与标签的应用程序路径相关的错误不足，则通过将其他应用程序路径替换为应用程序路径，再次创建分析来重复该方法。

公开(公告)号：US20100251221A1

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

申请号：US12410177

申请日：2009-03-24

申请人： Aditya V. Nori ,  Patrice Godefroid ,  Sriram Rajamani ,  Sai Deep Tetali

发明人： Aditya V. Nori ,  Patrice Godefroid ,  Sriram Rajamani ,  Sai Deep Tetali

IPC分类号： G06F11/36

CPC分类号： G06F11/3608

摘要： A method of analyzing a computer application is disclosed. The method may break an application into components and the method may determine if the components have already been analyzed for errors, either through static analysis or by a code analysis. If the component has already been analyzed, the previous analysis may be used and the method may move on to the next code section. If the component has not been analyzed, it may be determined if the component may be reached from a given starting point. If the component cannot be reached from a given starting point, the component may not be analyzed. Both static and code testing tools may be used to determine if errors exist. The fined-grained coupling and alternation of may (universal) and must (existential) summaries allow the method to easily navigate through these code fragments while traditional may-only, must-only or non-compositional may-must al-gorithms are stuck in their specific analyses.

摘要翻译： 公开了一种分析计算机应用的方法。 该方法可以将应用程序分解成组件，并且该方法可以通过静态分析或代码分析来确定组件是否已经被分析了错误。 如果组件已经被分析，可以使用以前的分析，并且该方法可以移动到下一个代码部分。 如果未分析组件，则可以确定是否可以从给定的起点到达组件。 如果从给定的起点无法到达组件，则可能无法分析组件。 可以使用静态和代码测试工具来确定是否存在错误。 可能（通用）和必须（存在）摘要的细粒度耦合和交替允许该方法轻松导航这些代码片段，而传统的只有，必须或非组合的可能必须的算法被卡在 具体分析。

公开(公告)号：US20100088546A1

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

申请号：US12245581

申请日：2008-10-03

申请人： Trishul Chilimbi ,  Krishna Kumar Mehra ,  Benjamin Robert Liblit ,  Aditya V. Nori ,  Kapil Vaswani

发明人： Trishul Chilimbi ,  Krishna Kumar Mehra ,  Benjamin Robert Liblit ,  Aditya V. Nori ,  Kapil Vaswani

IPC分类号： G06F11/36

CPC分类号： G06F11/366

摘要： The method executes the application and if there are no errors from the execution of the application, the method ends. If errors exist, the errors are collected from the execution of the application in an error report. Labeled application paths are created by adding a unique label to individual application paths where the application paths are individual loops and individual functions in the application. An analysis is created of the labeled application paths by executing the application with the labeled paths, reviewing the error report for data related to the labels and if an error is sufficiently related to application paths with labels, storing the path that created the errors in a report. If an error is not sufficient related to the application path with labels, the method is repeated by the creating the analysis again by substituting additional application paths for the application paths.

摘要翻译： 该方法执行应用程序，如果应用程序的执行没有错误，则该方法结束。 如果存在错误，则会在错误报告中从应用程序的执行中收集错误。 标签的应用程序路径是通过向单个应用程序路径添加唯一标签创建的，其中应用程序路径是单个循环和应用程序中的单个功能。 通过使用标记的路径执行应用程序来创建标记的应用程序路径的分析，查看与标签相关的数据的错误报告，并且如果错误与具有标签的应用程序路径充分相关，则将创建错误的路径存储在 报告。 如果与标签的应用程序路径相关的错误不足，则通过将其他应用程序路径替换为应用程序路径，再次创建分析来重复该方法。