公开(公告)号：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方法或功能正确连接。 程序测试是程序行为的“近似”，抽象是程序的“过近似”。 这种同时测试可以找到达到错误状态的测试用例，或者发现一个抽象表明程序状态空间中的任何路径都不能达到任何错误状态。 如果测试用例达到错误状态，则属性检查器发现违反了安全属性。 相反，如果状态空间中没有路径可以达到任何错误状态，则属性检查器已经证明该程序满足所需的安全属性。

公开(公告)号：US07536606B2

公开(公告)日：2009-05-19

申请号：US10835838

申请日：2004-04-30

申请人： Anthony Dean Andrews ,  Sriram K. Rajamani ,  Jakob Rehob

发明人： Anthony Dean Andrews ,  Sriram K. Rajamani ,  Jakob Rehob

IPC分类号： G06F11/00

CPC分类号： G06F11/0751 ,  G06F11/0709 ,  H04L41/06

摘要： Methods and systems are provided for automatically generating an accurate model of communications processes between disparate computing systems that may be analyzed in an efficient manner for error detection in web services systems. Business Process Execution Language for Web Services (BPEL) descriptions are automatically generated for the BPEL-based executable processes utilized by each communicating computing system in a given web services system. The BPEL abstract process descriptions for each communicating computing system are translated into a combined process model according to a suitable modeling language. The process model is tested by a model checking software application. Communications errors between the disparate computing systems are detected by automatically testing the combined process model according to a variety of potential communications scenarios.

摘要翻译： 提供了方法和系统，用于在不同的计算系统之间自动生成精确的通信过程模型，可以以有效的方式对Web服务系统中的错误检测进行分析。 为每个通信计算系统在给定Web服务系统中使用的基于BPEL的可执行流程自动生成Web服务的业务流程执行语言（BPEL）描述。 每个通信计算系统的BPEL抽象过程描述根据合适的建模语言被转换为组合过程模型。 流程模型通过模型检查软件应用程序进行测试。 通过根据各种潜在通信场景自动测试组合过程模型来检测不同计算系统之间的通信错误。

公开(公告)号：US07509534B2

公开(公告)日：2009-03-24

申请号：US11470066

申请日：2006-09-05

申请人： Sriram K. Rajamani ,  Bhargav Gulavani

发明人： Sriram K. Rajamani ,  Bhargav Gulavani

IPC分类号： G06F11/00

CPC分类号： G06F9/45508 ,  G06F11/28

摘要： A refinement system automatically identifies whether a detected error in a target system during abstract interpretation is a false error or a true error and adjusts the interpretation to prevent the false error. The target system is represented as a transition system with an initial state and state transitions and a specification that the target system is to satisfy. The refinement system iteratively performs steps of the abstract interpretation using a widening operator. When the state of a step does not satisfy the specification, the refinement system identifies a step whose widening operator was the source of the state that did not satisfy the specification and applies a more precise operator that eliminates the problem with the widening. The refinement system then starts re-performing the steps starting at that step.

摘要翻译： 细化系统自动识别在抽象解释期间目标系统中检测到的错误是否为错误或真实错误，并调整解释以防止错误。 目标系统表示为具有初始状态和状态转换的转换系统以及目标系统要满足的规范。 细化系统使用加宽算子迭代地执行抽象解释的步骤。 当步骤的状态不符合规范时，精化系统识别其加宽操作者是不满足规范的状态的来源的步骤，并应用更加精确的操作者，消除了扩大的问题。 细化系统然后开始重新执行从该步骤开始的步骤。

公开(公告)号：US20080034353A1

公开(公告)日：2008-02-07

申请号：US11470066

申请日：2006-09-05

申请人： Sriram K. Rajamani ,  Bhargav Gulavani

发明人： Sriram K. Rajamani ,  Bhargav Gulavani

IPC分类号： G06F9/45

CPC分类号： G06F9/45508 ,  G06F11/28

摘要： A refinement system automatically identifies whether a detected error in a target system during abstract interpretation is a false error or a true error and adjusts the interpretation to prevent the false error. The target system is represented as a transition system with an initial state and state transitions and a specification that the target system is to satisfy. The refinement system iteratively performs steps of the abstract interpretation using a widening operator. When the state of a step does not satisfy the specification, the refinement system identifies a step whose widening operator was the source of the state that did not satisfy the specification and applies a more precise operator that eliminates the problem with the widening. The refinement system then starts re-performing the steps starting at that step.

摘要翻译： 细化系统自动识别在抽象解释期间目标系统中检测到的错误是否为错误或真实错误，并调整解释以防止错误。 目标系统表示为具有初始状态和状态转换的转换系统以及目标系统要满足的规范。 细化系统使用加宽算子迭代地执行抽象解释的步骤。 当步骤的状态不符合规范时，精化系统识别其加宽操作者是不满足规范的状态的来源的步骤，并应用更加精确的操作者，消除了扩大的问题。 细化系统然后开始重新执行从该步骤开始的步骤。

公开(公告)号：US20130251344A1

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

申请号：US13429093

申请日：2012-03-23

申请人： Joseph M. Joy ,  Narendranath Datha ,  Tanuja Abhay Joshi ,  Sriram K. Rajamani ,  Eric J. Stollnitz

发明人： Joseph M. Joy ,  Narendranath Datha ,  Tanuja Abhay Joshi ,  Sriram K. Rajamani ,  Eric J. Stollnitz

IPC分类号： G11B27/00

CPC分类号： G06F16/9535

摘要： Techniques for manipulation of user experience state are described. A user experience can include various types of content that a user may consume, such as video content, images, audio content, text documents, and so on. Further, a “composition” can be created using various combinations of user experiences, such as still images inset to video content, a navigable map presented with images of geographical locations associated with the map, and so on. In implementations, techniques enable user experiences included as part of a composition to interact such that behaviors associated with one user experience can affect another user experience, and vice-versa.

摘要翻译： 描述用于操纵用户体验状态的技术。 用户体验可以包括用户可能消费的各种类型的内容，诸如视频内容，图像，音频内容，文本文档等等。 此外，可以使用诸如静止图像插入到视频内容的用户体验的各种组合，呈现与地图相关联的地理位置的图像的可导航地图等来创建“构图”。 在实现中，技术使得包括作为组合的一部分的用户体验进行交互，使得与一个用户体验相关联的行为可以影响另一个用户体验，反之亦然。

公开(公告)号：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）作为响应，将任意的第二个消息从任意的 - 所有节点到任意子公式节点。

公开(公告)号：US07650595B2

公开(公告)日：2010-01-19

申请号：US11119530

申请日：2005-04-29

申请人： Shaz Qadeer ,  Sriram K. Rajamani ,  Vladimir A. Levin ,  Robert Palmer

发明人： Shaz Qadeer ,  Sriram K. Rajamani ,  Vladimir A. Levin ,  Robert Palmer

IPC分类号： G06F9/44

CPC分类号： G06F8/433 ,  G06F8/456 ,  G06F11/3608

摘要： Described techniques and tools help model checking scale to large programs while reducing missed errors. In particular, described techniques and tools help reduce the state space of concurrent programs without depending on cycle detection and without scheduling execution of postponed threads at all cycles. For example, described techniques and tools use a type of partial-order reduction called transaction-based reduction to reduce program state space. Analysis is performed at commit points to determine whether to schedule delayed threads.

摘要翻译： 描述的技术和工具可帮助模型检查大型程序的规模，同时减少错误的错误。 特别地，所描述的技术和工具有助于减少并发程序的状态空间，而不依赖于周期检测，并且在所有周期内不执行延迟的线程。 例如，所描述的技术和工具使用一种称为基于事务的减少的部分顺序减少来减少程序状态空间。 分析在提交点执行，以确定是否计划延迟的线程。

公开(公告)号：US06904590B2

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

申请号：US09866090

申请日：2001-05-25

申请人： Thomas J. Ball ,  Sriram K. Rajamani

发明人： Thomas J. Ball ,  Sriram K. Rajamani

IPC分类号： G06F11/36 ,  G06F9/44

CPC分类号： G06F11/3608

摘要： Methods are discussed that enhance program analysis. One aspect of the invention includes a method for checking a model of a program. The method includes a control-flow graph having vertices from the model, applying a transfer function to each vertex to form a set of path edges, and analyzing the set of path edges of a vertex. The set of path edges includes valuations that are implicitly represented so as to inhibit an undesired explosion in the valuations that would hinder the act of analyzing.

摘要翻译： 讨论了加强程序分析的方法。 本发明的一个方面包括一种用于检查程序模型的方法。 该方法包括具有来自模型的顶点的控制流程图，对每个顶点应用传递函数以形成一组路径边缘，以及分析顶点的路径边缘集合。 一组路径边缘包括隐含地表示的估值，以便抑制估价中的不期望的爆炸，这将妨碍分析的行为。

公开(公告)号：US08266702B2

公开(公告)日：2012-09-11

申请号：US11555218

申请日：2006-10-31

申请人： Prasad G. Naldurg ,  Sriram K. Rajamani ,  Stefan Schwoon ,  John Lambert

发明人： Prasad G. Naldurg ,  Sriram K. Rajamani ,  Stefan Schwoon ,  John Lambert

IPC分类号： G06F7/04 ,  G06F11/00 ,  G06F21/00

CPC分类号： G06F21/577 ,  G06F2221/034

摘要： A facility is described for analyzing access control configurations. In various embodiments, the facility comprises an operating system having resources and identifications of principals, the principals having access control privileges relating to the resources, the access control privileges described by access control metadata; an access control scanner component that receives the access control metadata, determines relationships between the principals and the resources, and emits access control relations information; and an access control inference engine that receives the emitted access control relations information and an access control policy model, analyzes the received information and model, and emits a vulnerability report. In various embodiments, the facility generates an information flow based on access control relations, an access control mechanism model, and an access control policy model; determines, based on the generated information flow, whether privilege escalation is possible; and when privilege escalation is possible, indicates in a vulnerability report that the privilege escalation is possible.

摘要翻译： 描述了一种用于分析访问控制配置的设施。 在各种实施例中，该设施包括操作系统，该操作系统具有资源和标识符，主体具有与资源相关的访问控制权限，由访问控制元数据描述的访问控制特权; 访问控制扫描器组件，其接收访问控制元数据，确定主体与资源之间的关系，并且发出访问控制关系信息; 以及访问控制推理引擎，其接收发出的访问控制关系信息和访问控制策略模型，分析所接收的信息和模型，并发出漏洞报告。 在各种实施例中，设备基于访问控制关系，访问控制机制模型和访问控制策略模型生成信息流; 根据生成的信息流确定是否有权限升级; 并且当特权升级成为可能时，在漏洞报告中指出可以升级特权。

公开(公告)号：US07757219B2

公开(公告)日：2010-07-13

申请号：US10978989

申请日：2004-11-01

申请人： Thomas J. Ball ,  Sriram K. Rajamani

发明人： Thomas J. Ball ,  Sriram K. Rajamani

IPC分类号： G06F9/44

CPC分类号： G06F11/3608

摘要： Methods are discussed that enhance program analysis. One aspect of the invention includes a method for checking a model of a program. The method includes a control-flow graph having vertices from the model, applying a transfer function to each vertex to form a set of path edges, and analyzing the set of path edges of a vertex. The set of path edges includes valuations that are implicitly represented so as to inhibit an undesired explosion in the valuations that would hinder the act of analyzing.

摘要翻译： 讨论了加强程序分析的方法。 本发明的一个方面包括一种用于检查程序模型的方法。 该方法包括具有来自模型的顶点的控制流程图，对每个顶点应用传递函数以形成一组路径边缘，以及分析顶点的路径边缘集合。 一组路径边缘包括隐含地表示的估值，以便抑制估价中的不期望的爆炸，这将妨碍分析的行为。