Oracle International Corporation

Oracle America, Inc.

Oracle International Corporatiton

Bernhard Friedrich Scholz

Padmanabhan Krishnan

Cristina Nicole Cifuentes

Nicholas John Allen

Raghavendra Kagalavadi Ramesh

Yi Lu

Pavle Subotic

Nathan Robert Albert Keynes

Behnaz Hassanshahi

Till Westmann

Stepan Sindelar

Chenyi Zhang

A method may use a minimal set of indices for an input query including identifying the input query including primitive searches that are accelerated using indices, and computing a minimal set of indices for the input query using a polynomial-time algorithm by constructing a bi-partite graph comprising a first and a second vertex set. The first and the second vertex set may be a set of searches in both partitions of the bi-partite graph. Each edge of the edge set may connect a vertex in the first vertex set and a vertex in the second vertex set. The method may further include identifying an edge set as a strict subset relation between at least two searches of the set of searches showing up in the first and second vertex set of the bi-partite graph, and performing relational data analysis using the minimal set of indices for input queries.

Optimal index selection in polynomial time

A method for performing analysis may use a minimal set of indices for an input query including identifying the input query including primitive searches that are accelerated using indices, computing a minimal set of indices for the input query using an optimal, polynomial-time algorithm, and performing relational data analysis using the minimal set of indices for input queries.

A method for points-to program analysis includes extracting a kernel from a program, performing a fixed object sensitive points to analysis of the kernel to obtain fixed analysis results, and assigning, for a first candidate object in the kernel, a first context depth to the first candidate object. The candidate objects are identified using the fixed analysis results. The method further includes assigning, for a second candidate object, a second context depth to the second candidate object. The second context depth is different than the first context depth. The method further includes performing, to obtain selective analysis results, a selective object sensitive points to analysis using the first context depth for the first candidate object and the second context depth for the second candidate object, and performing an action based on the selective analysis results.

Selective object sensitive points-to analysis

A method and system for staged compilation of a declarative program that includes receiving the declarative program, parsing and semantically checking the declarative program, translating the declarative program into a relational algebra machine (RAM) using a modified semi-na&#xef;ve algorithm, performing a translation of the RAM into code of an imperative programming language to obtain a translated RAM, generating specialized extractor code in the imperative programming language, generating query application programming interface (API) code in the imperative programming language, and compiling the translated RAM, the specialized extractor code, and the query API code to obtain a program analysis module.

Declarative program engine for large-scale program analysis

A method for analyzing a program may include obtaining the program and obtaining a points-to analysis that may include points-to tuples. The method may further include obtaining a result of a query based on the program. The method may further include extracting a data-flow trace specification that includes flow tuples. Each flow tuple may include a source variable defined in a first method and a sink variable defined in a second method. The method may further include adding, in a recursive manner until a termination condition is triggered, a trace edge to a data-flow trace graph for each points-to tuple of a list of points-to tuples. The respective points-to tuple and a first flow tuple may be used to form a first points-to tuple that is added to the list of points-to tuples. The list of points-to tuples may be initialized to the result of the query.

Scalable provenance generation from points-to information

A method, system, and computer-readable medium (CRM) for performing a staged points-to analysis of an object-oriented codebase, including obtaining the codebase and a points-to query, slicing the codebase to obtain a program slice, and performing a type analysis of the program slice to compute a type set. The method, system, and CRM include refining the program slice, after performing the type analysis, by resolving virtual dispatch sites based on the type set, and performing, after refining the program slice, a context-insensitive points-to analysis of the program slice to compute a first points-to set. The method, system, and CRM include re-refining the program slice, after performing the context-insensitive points-to analysis, by resolving the virtual dispatch sites based on the first points-to set, and performing, after re-refining the program slice, a context-sensitive points-to analysis of the program slice to compute a second points-to set, which is provided to a developer.

Staged points-to analysis for large code bases

In general, in one aspect, the invention relates to a method for statically analyzing a library that includes obtaining native method annotations associated with native methods invoked by the library and extracting facts corresponding to the library from the library to obtain library facts. The library is written in a first programming language. The method also includes constructing a type-object lattice, modeling an abstracted heap using the type-object lattice, expressing abstracted heap update operations as heap update rules, and constructing, based on the library, a most general application (MGA) for the library. The method additionally includes analyzing the library using the native method annotations, the library facts, the MGA, the abstracted heap, and the heap update rules to obtain results, storing the results of the analysis, and performing an action based on the results.

Combining type-analysis with points-to analysis for analyzing library source-code

A method for overflow detection using partial evaluations. The method includes obtaining a section of code from a source code file stored on a storage device, analyzing the section of code to identify a buffer with an index, determining a plurality of statements that are statically-computable and dependent on the index of the buffer, and generating a code segment including the plurality of statements. The method further includes replacing an access statement of the plurality of statements with a conditional statement returning true when bounds of the buffer are exceeded, where the access statement uses the index to access the buffer, adding an unconditional statement returning false to the code segment, and executing the code segment on a computer processor to obtain a determination of whether the bounds of the buffer are exceeded.

System and method for overflow detection using partial evaluations

A method for analyzing a set of potential bug statements in source code. The method including obtaining a set of static program analyses; recursively reducing the set of potential bug statements in the source code by: selecting a static program analysis for each recursion from the set of static program analyses in order from least time consuming to most time consuming; evaluating the set of potential bug statements using the static program analysis of the set of static program analyses to determine a subgroup of bug free statements of the set of potential bug statements in each recursion; and removing the subgroup of the bug free statements from the set of potential bug statements to reduce the set of potential bug statements in each recursion; thereby filtering at least one subgroup of bug free statements out of the set of potential bug statements in the source code.

Layered static program analysis framework for software testing

A method for detecting user input dependence in software code. The method including representing the software code with a reachability graph having: a plurality of nodes, where a root node of the plurality of nodes represents an input controlled by a user; a first directed edge connecting a first node of the plurality of nodes and a second node of the plurality of nodes, where the first directed edge represents a data dependency; and a second directed edge connecting a third node of the plurality of nodes and a fourth node of the plurality of nodes, wherein the second directed edge represents a data dependency. The method also includes identifying a fifth node of the plurality of nodes as a reachable node from the root node by traversing the reachability graph from the root node to the reachable node; and marking a portion of the software code represented by the reachable node as user input dependant.

Growing community of inventors

Sydney, Australia

Bernhard Friedrich Scholz