公开(公告)号：US08181163B2

公开(公告)日：2012-05-15

申请号：US11745295

申请日：2007-05-07

申请人： Vladimir Jojic ,  Nebojsa Jojic ,  Sumit Gulwani

发明人： Vladimir Jojic ,  Nebojsa Jojic ,  Sumit Gulwani

IPC分类号： G06F9/45

CPC分类号： G06F11/3624 ,  G06F8/436

摘要： One embodiment is directed to synthesizing code fragments in a software routine using known inputs and corresponding expected outputs. A computer system provides a software routine with known inputs and corresponding expected outputs, infers software routine instructions based on the known inputs and corresponding expected outputs, and synthesizes a correctly functioning code fragment based on the inferred instructions. Another embodiment is directed to automatically resolving semantic errors in a software routine. A computer system provides the software routine with known inputs and corresponding expected outputs for portions of a program fragment where an error has been localized. The computer system learns a correctly functioning program fragment from pairs of input-output descriptions of the program fragment, determines the program statements that can transform given input states into given output states after execution of those program statements, and alters portions of the software routine with the learned program fragments.

摘要翻译： 一个实施例涉及使用已知输入和相应的预期输出来合成软件例程中的代码片段。 计算机系统提供具有已知输入和对应的预期输出的软件例程，基于已知输入和相应的预期输出推断软件程序指令，并且基于推断的指令来合成正确运行的代码片段。 另一个实施例涉及自动解决软件程序中的语义错误。 计算机系统向软件例程提供已知输入和对于已经本地化错误的程序片段的部分的相应的预期输出。 计算机系统从程序片段的输入输出描述中学习正确运行的程序片段，确定在执行这些程序语句之后将给定的输入状态转换为给定的输出状态的程序语句，并且改变软件程序的一部分 学习的程序片段。

公开(公告)号：US20080172650A1

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

申请号：US11622904

申请日：2007-01-12

申请人： Sumit Gulwani ,  Vladimir Jojic ,  Nebojsa Jojic

发明人： Sumit Gulwani ,  Vladimir Jojic ,  Nebojsa Jojic

IPC分类号： G06F9/44

CPC分类号： G06F11/3608

摘要： In one embodiment, a computer system performs a method for verifying the validity or invalidity of a software routine by learning appropriate invariants at each program point. A computer system chooses an abstract domain that is sufficiently precise to express the appropriate invariants. The computer system associates an inconsistency measure with any two abstract elements of the abstract domain. The computer system searches for a set of local invariants configured to optimize a total inconsistency measure which includes a sum of local inconsistency measures. The computer system optimizes the total inconsistency measure for all input/output pairs of the software routine. In one embodiment, the optimization of total inconsistency is achieved by the computer system which repeatedly replaces a locally inconsistent invariant with a new invariant, randomly selected among the possible invariants which are locally less inconsistent with the current invariants at the neighboring program points.

摘要翻译： 在一个实施例中，计算机系统通过在每个程序点学习适当的不变量来执行用于验证软件例程的有效性或无效性的方法。 计算机系统选择足够精确的表示适当不变量的抽象域。 计算机系统将不一致性度量与抽象域的任意两个抽象元素相关联。 计算机系统搜索一组局部不变量，其被配置为优化包括本地不一致性度量的总和的总不一致性度量。 计算机系统优化软件程序的所有输入/输出对的总不一致性测量。 在一个实施例中，总体不一致性的优化是通过计算机系统实现的，该计算机系统在局部地与邻近程序点的当前不变量局部较不一致的可能不变量中随机选择新的不变量来重复地替换局部不一致的不变量。

公开(公告)号：US07729999B2

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

申请号：US11622904

申请日：2007-01-12

申请人： Sumit Gulwani ,  Vladimir Jojic ,  Nebojsa Jojic

发明人： Sumit Gulwani ,  Vladimir Jojic ,  Nebojsa Jojic

IPC分类号： G06F15/18

CPC分类号： G06F11/3608

摘要： In one embodiment, a computer system performs a method for verifying the validity or invalidity of a software routine by learning appropriate invariants at each program point. A computer system chooses an abstract domain that is sufficiently precise to express the appropriate invariants. The computer system associates an inconsistency measure with any two abstract elements of the abstract domain. The computer system searches for a set of local invariants configured to optimize a total inconsistency measure which includes a sum of local inconsistency measures. The computer system optimizes the total inconsistency measure for all input/output pairs of the software routine. In one embodiment, the optimization of total inconsistency is achieved by the computer system which repeatedly replaces a locally inconsistent invariant with a new invariant, randomly selected among the possible invariants which are locally less inconsistent with the current invariants at the neighboring program points.

摘要翻译： 在一个实施例中，计算机系统通过在每个程序点学习适当的不变量来执行用于验证软件例程的有效性或无效性的方法。 计算机系统选择足够精确的表示适当不变量的抽象域。 计算机系统将不一致性度量与抽象域的任意两个抽象元素相关联。 计算机系统搜索一组局部不变量，其被配置为优化包括本地不一致性度量的总和的总不一致性度量。 计算机系统优化软件程序的所有输入/输出对的总不一致性测量。 在一个实施例中，总体不一致性的优化是通过计算机系统实现的，该计算机系统在局部地与邻近程序点的当前不变量局部较不一致的可能不变量中随机选择新的不变量来重复地替换局部不一致的不变量。

公开(公告)号：US20080282108A1

公开(公告)日：2008-11-13

申请号：US11745295

申请日：2007-05-07

申请人： Vladimir Jojic ,  Nebojsa Jojic ,  Sumit Gulwani

发明人： Vladimir Jojic ,  Nebojsa Jojic ,  Sumit Gulwani

IPC分类号： G06F9/44 ,  G06F11/00 ,  G06F15/18

CPC分类号： G06F11/3624 ,  G06F8/436

摘要： One embodiment is directed to synthesizing code fragments in a software routine using known inputs and corresponding expected outputs. A computer system provides a software routine with known inputs and corresponding expected outputs, infers software routine instructions based on the known inputs and corresponding expected outputs, and synthesizes a correctly functioning code fragment based on the inferred instructions. Another embodiment is directed to automatically resolving semantic errors in a software routine. A computer system provides the software routine with known inputs and corresponding expected outputs for portions of a program fragment where an error has been localized. The computer system learns a correctly functioning program fragment from pairs of input-output descriptions of the program fragment, determines the program statements that can transform given input states into given output states after execution of those program statements, and alters portions of the software routine with the learned program fragments.

摘要翻译： 一个实施例涉及使用已知输入和相应的预期输出来合成软件例程中的代码片段。 计算机系统提供具有已知输入和对应的预期输出的软件例程，基于已知输入和相应的预期输出推断软件程序指令，并且基于推断的指令来合成正确运行的代码片段。 另一个实施例涉及自动解决软件程序中的语义错误。 计算机系统向软件例程提供已知输入和对于已经本地化错误的程序片段的部分的相应的预期输出。 计算机系统从程序片段的输入输出描述中学习正确运行的程序片段，确定在执行这些程序语句之后将给定的输入状态转换为给定的输出状态的程序语句，并且改变软件程序的一部分 学习的程序片段。

公开(公告)号：US09659082B2

公开(公告)日：2017-05-23

申请号：US13594883

申请日：2012-08-27

申请人： Sumit Gulwani ,  Geoffrey Gerson Zweig

发明人： Sumit Gulwani ,  Geoffrey Gerson Zweig

IPC分类号： G06F17/30

CPC分类号： G06F17/30672 ,  G06F17/30657 ,  G06F17/30684 ,  G06F17/30696

摘要： Various technologies described herein pertain to executing a mixed query to search a database retained in a data repository. The mixed query includes a regular expression, which is a pattern of elements, and a semantic constraint. The elements in the regular expression include a first wildcard, where the semantic constraint restricts a meaning of the first wildcard. Moreover, the elements in the regular expression include explicit lexical constraint(s) and/or disparate wildcard(s). For instance, semantic constraint(s) can restrict meaning(s) of the disparate wildcard(s). The mixed query is executed to retrieve results that match the pattern of the elements in the regular expression and satisfy the semantic constraint(s).

公开(公告)号：US08752029B2

公开(公告)日：2014-06-10

申请号：US12568710

申请日：2009-09-29

申请人： Sumit Gulwani ,  Florian Franz Zuleger ,  Sudeep Dilip Juvekar

发明人： Sumit Gulwani ,  Florian Franz Zuleger ,  Sudeep Dilip Juvekar

IPC分类号： G06F9/44

CPC分类号： G06F11/302 ,  G06F11/3089 ,  G06F11/3604

摘要： A system that facilitates computing a symbolic bound with respect to a procedure that is executable by a processor on a computing device is described herein. The system includes a transition system generator component that receives the procedure and computes a disjunctive transition system for a control location in the procedure. A compute bound component computes a bound for the transition system, wherein the bound is expressed in terms of inputs to the transition system. The system further includes a translator component that translates the bound computed by the compute bound component such that the bound is expressed in terms of inputs to the procedure.

摘要翻译： 这里描述了有助于计算相对于计算设备上的处理器可执行的过程的符号约束的系统。 系统包括一个过渡系统发生器组件，该组件接收该过程并计算该过程中控制位置的分离过渡系统。 计算边界分量计算过渡系统的边界，其中边界以过渡系统的输入表示。 该系统还包括翻译器组件，其翻译由计算绑定组件计算的绑定，使得该界限以该过程的输入来表示。

公开(公告)号：US20140013299A1

公开(公告)日：2014-01-09

申请号：US13542975

申请日：2012-07-06

申请人： Lucas Julien Bordeaux ,  Sumit Gulwani ,  Youssef Hamadi ,  Yi Wei

发明人： Lucas Julien Bordeaux ,  Sumit Gulwani ,  Youssef Hamadi ,  Yi Wei

IPC分类号： G06F9/44

CPC分类号： G06F8/30 ,  G06F8/36

摘要： Generalization and/or specialization of code fragments is described, for example, as part of a tool for software developers. In an embodiment, a developer inserts natural language expressing a programming task into code he or she is developing in an integrated development environment; a program synthesizer obtains relevant (possibly non-compiling) code fragments for the task, merges those together to form a snippet, specializes the snippet for the context of the code and inserts the specialized snippet into the code. For example, a pair of code fragments are obtained from a search engine and are merged by discarding statements which are not common to each of the pair. In examples, pairs of code fragments are selected using search engine ranks, user input, or frequency. In embodiments, placeholders replace variable names in the merged fragments. An example takes a syntax tree of the code being developed and uses that to specialize snippets.

摘要翻译： 例如，作为软件开发人员工具的一部分，描述了代码片段的泛化和/或专业化。 在一个实施例中，开发人员将表达编程任务的自然语言插入他或她正在集成开发环境中开发的代码; 一个程序合成器获得相关的（可能是非编译的）代码片段的任务，将这些代码段合并在一起形成一个代码段，专门为代码的上下文提供了一个代码段，并将专门的代码段插入到代码中。 例如，从搜索引擎获得一对代码片段，并且通过丢弃对于每个对不常见的语句来合并。 在示例中，使用搜索引擎排名，用户输入或频率来选择代码片段对。 在实施例中，占位符替换合并的片段中的变量名。 一个例子是正在开发的代码的语法树，并使用它来专门化代码段。

公开(公告)号：US08402439B2

公开(公告)日：2013-03-19

申请号：US12147908

申请日：2008-06-27

申请人： Sumit Gulwani ,  Saurabh Srivastava ,  Ramarathnam Venkatesan

发明人： Sumit Gulwani ,  Saurabh Srivastava ,  Ramarathnam Venkatesan

IPC分类号： G06F9/44

CPC分类号： G06F8/49

摘要： Described is a technology by which program analysis uses rich invariant templates that may specify an arbitrary Boolean combination of linear inequalities for program verification. Also described is choosing a cut-set that identifies program locations, each of which is associated with an invariant template. The verification generates second-order constraints, converts second-order logic formula based on those constraints into first-order logic formula, then converts the first-order logic formula into a quantifier-free formula, which is then converted into a Boolean satisfiability formula. Off-the-shelf constraint solvers may then be applied to the Boolean satisfiability formula to generate program analysis results. Various templates may be used to convert the second-order logic formula into the first-order logic formula. Further described are interprocedural analysis and the determination of weakest precondition and strongest postcondition with applications to termination analysis, timing bounds analysis, and generation of most-general counterexamples for both termination and safety properties.

摘要翻译： 描述了一种技术，程序分析使用丰富的不变模板，可以为程序验证指定线性不等式的任意布尔组合。 还描述了选择一个标识程序位置的剪辑，每个程序位置与不变模板相关联。 验证产生二阶约束，将基于这些约束的二阶逻辑公式转换为一阶逻辑公式，然后将一阶逻辑公式转换为无量词的公式，然后将其转换为布尔可满足公式。 现在可以将现成的约束求解器应用于布尔可满足公式以生成程序分析结果。 可以使用各种模板来将二阶逻辑公式转换成一阶逻辑公式。 进一步描述的是过程间分析以及最弱前提条件和最强后置条件的确定，适用于终止分析，时序界限分析，以及针对终端和安全属性生成大多数一般的反例。

公开(公告)号：US20120011152A1

公开(公告)日：2012-01-12

申请号：US12834031

申请日：2010-07-12

申请人： Sumit Gulwani ,  David P. Walker

发明人： Sumit Gulwani ,  David P. Walker

IPC分类号： G06F17/30

CPC分类号： G06F17/30569 ,  G06F8/51

摘要： A program generation system is described that generates a program based on a plurality of input-output examples. The input-output examples include input items and corresponding output items. The program generation system can include three component modules. A parsing module processes the input items and output items to provide a plurality of input parts and output parts, respectively. A transformation module determines, for each output part, whether the output part can be produced from a corresponding input part using one or more converter modules selected from a collection of candidate converter modules. A formatting module generates formatting instructions that transform selected output parts into a form specified by the output items. These three modules provide a generated program that embodies logic learned from the input-output examples; the generated program can be subsequently used to transform new input items into new respective output items.

摘要翻译： 描述了基于多个输入输出示例生成程序的程序生成系统。 输入输出示例包括输入项和相应的输出项。 程序生成系统可以包括三个组件模块。 解析模块分别处理输入项目和输出项目以分别提供多个输入部分和输出部分。 变换模块针对每个输出部分确定是否可以使用从候选转换器模块的集合中选择的一个或多个转换器模块从相应的输入部分产生输出部分。 格式化模块生成格式化指令，将选择的输出部分转换为由输出项指定的形式。 这三个模块提供了一个生成的程序，体现了从输入输出示例中学到的逻辑; 生成的程序可以随后用于将新的输入项变换成新的相应的输出项。

公开(公告)号：US20090326907A1

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

申请号：US12147908

申请日：2008-06-27

申请人： Sumit Gulwani ,  Saurabh Srivastava ,  Ramarathnam Venkatesan

发明人： Sumit Gulwani ,  Saurabh Srivastava ,  Ramarathnam Venkatesan

IPC分类号： G06F9/45 ,  G06F7/60

CPC分类号： G06F8/49

摘要： Described is a technology by which program analysis uses rich invariant templates that may specify an arbitrary Boolean combination of linear inequalities for program verification. Also described is choosing a cut-set that identifies program locations, each of which is associated with an invariant template. The verification generates second-order constraints, converts second-order logic formula based on those constraints into first-order logic formula, then converts the first-order logic formula into a quantifier-free formula, which is then converted into a Boolean satisfiability formula. Off-the-shelf constraint solvers may then be applied to the Boolean satisfiability formula to generate program analysis results. Various templates may be used to convert the second-order logic formula into the first-order logic formula. Further described are interprocedural analysis and the determination of weakest precondition and strongest postcondition with applications to termination analysis, timing bounds analysis, and generation of most-general counterexamples for both termination and safety properties.

摘要翻译： 描述了一种技术，程序分析使用丰富的不变模板，可以为程序验证指定线性不等式的任意布尔组合。 还描述了选择一个标识程序位置的剪辑，每个程序位置与不变模板相关联。 验证产生二阶约束，将基于这些约束的二阶逻辑公式转换为一阶逻辑公式，然后将一阶逻辑公式转换为无量词的公式，然后将其转换为布尔可满足公式。 现在可以将现成的约束求解器应用于布尔可满足公式以生成程序分析结果。 可以使用各种模板来将二阶逻辑公式转换成一阶逻辑公式。 进一步描述的是过程间分析以及最弱前提条件和最强后置条件的确定，适用于终止分析，时序界限分析，以及针对终端和安全属性生成大多数一般的反例。