Points to analysis java

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Souffle: Tutorial for a Java Points-To Analysis

souffle-lang/java-pts

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Java Points-To Analysis for Soufflé

This repository contains a modified DOOP extractor and a modified points-to specifications for Soufflé. Currently there are two points-to analyses implemented in form of logical specifications: context-insensitive with call-graph construction on the fly and context-sensitive (2-Heap + 1-Object).

The extractor can be build by typing

The extractor can be invoked by typing

java -jar build/lib/extractor.jar -lsystem -d

where is the jar file for which the fact files are produced and is the directory where the fact files are written to.

More information about DOOP can be found here: http://doop.program-analysis.org/

The modified DOOP points-to analysis has been provided by Oracle Labs: https://github.com/oracle/souffle/tree/master/samples

How to install and run the Soufflé can be found here: http://github.com/souffle-lang/souffle

About

Souffle: Tutorial for a Java Points-To Analysis

Источник

Points-to Analysis Reports

The points-to analysis produces two kinds of reports: analysis call tree and image object tree. This information is produced by an intermediate step in the image building process and represents the static analysis view of the call graph and heap object graph. These graphs are further transformed in the image building process before they are AOT compiled into the image and written into the image heap, respectively.

Call tree

The call tree is a a breadth-first tree reduction of the call graph as seen by the points-to analysis. The points-to analysis eliminates calls to methods that it determines cannot be reachable at runtime, based on the analysed receiver types. It also completely eliminates invocations in unreachable code blocks, e.g., blocks guarded by a type check that always fails. The call tree report is enabled using the -H:+PrintAnalysisCallTree option. It produces a file with the structure:

VM Entry Points ├── entry ├── directly calls @bci= │ │ └── │ ├── virtually calls @bci= │ │ ├── is overridden by │ │ └── │ │ └── is overridden by id-ref= │ └── interfacially calls @bci= │ ├── is implemented by │ └── │ └── is implemented by id-ref= ├── entry └── └── . 

The tags between < and >are expanded with concrete values, the rest is printed as presented. The methods are formatted using .(): and are expanded until no more callees can be reached.

Since this is a tree reduction of the call graph each concrete method is expanded exactly once. The tree representation inherently omits calls to methods that have already been explored in a different branch or previously on the same branch. This restriction implicitly fixes the recursion problem. To convey the information that is lost through tree reduction each concrete method is given a unique id. Thus when a method is reached for the first time it declares an identifier as id= . Subsequent discoveries of the same method use an identifier reference to point to the previously expansion location: id-ref= . Each id= and id-ref= are followed by a blank space to make it easy to search.

Each invoke is tagged with the invocation bci: @bci= . For invokes of inline methods the is a list of bci values, separated with -> , enumerating the inline locations, backwards to the original invocation location.

Image object tree

The image object tree is an exhaustive expansion of the objects included in the native image heap. The tree is obtained by a depth first walk of the native image heap object graph. It is enabled using the -H:+PrintImageObjectTree option. The roots are either static fields or method graphs that contain embedded constants. The printed values are concrete constant objects added to the native image heap. Produces a file with the structure:

Heap roots ├── root value: │ └── toString= fields: │ ├── value=null │ ├── toString= (expansion suppressed) │ ├── value: │ │ └── toString= fields: │ │ └── │ ├── value: │ │ └── toString= elements (excluding null): │ │ ├── [] toString= fields: │ │ │ └── │ │ └── [] toString= elements (excluding null): │ │ └── │ ├── value: │ │ └── id-ref= toString= │ ├── value: │ │ └── toString= (no fields) │ └── value: │ └── toString= (no elements) ├── root id-ref= toString= ├── root value: │ └── └── . 

The tags between < and >are expanded with concrete values, the rest is printed as presented. The root fields are formatted using .: . The non-root fields are formatted using : . The value types are formatted using . The root methods are formatted using .(): No-array objects are expanded for all fields (including null). No-array objects with no fields are tagged with (no fields) . Array objects are expanded for all non-null indexes: [] Empty array objects or with all null elements are tagged with (no elements) .

Each constant value is expanded exactly once to compress the format. When a value is reached from multiple branches it is expanded only the first time and given an identifier: id= . Subsequent discoveries of the same value use an identifier reference to point to the previously expansion location: id-ref= .

Suppressing expansion of values

Some values, such as String , BigInteger and primitive arrays, are not expanded by default and marked with (expansion suppressed) . All the other types are expanded by default. To force the suppression of types expanded by default you can use -H:ImageObjectTreeSuppressTypes= . To force the expansion of types suppressed by default or through the option you can use -H:ImageObjectTreeExpandTypes= . When both -H:ImageObjectTreeSuppressTypes and -H:ImageObjectTreeExpandTypes are specified -H:ImageObjectTreeExpandTypes has precedence.

Similarly, some roots, such as java.lang.Character$UnicodeBlock.map» that prints a lot of strings, are not expanded at all and marked with (expansion suppressed) as well. All the other roots are expanded by default. To force the suppression of roots expanded by default you can use -H:ImageObjectTreeSuppressRoots= . To force the expansion of roots suppressed by default or through the option you can use -H:ImageObjectTreeExpandRoots= . When both -H:ImageObjectTreeSuppressRoots and -H:ImageObjectTreeExpandRoots are specified -H:ImageObjectTreeExpandRoots has precedence.

All the suppression/expansion options above accept a comma-separated list of patterns. For types the pattern is based on the fully qualified name of the type and refers to the concrete type of the constants. (For array types it is enough to specify the elemental type; it will match all the arrays of that type, of all dimensions.) For roots the pattern is based on the string format of the root as described above. The pattern accepts the * modifier:

• ends-with: * — the pattern exactly matches all entries that end with
• starts-with: * — the pattern exactly matches all entries that start with
• contains: ** — the pattern exactly matches all entries that contain
• equals: — the pattern exactly matches all entries that are equal to
• all: * — the pattern matches all entries

Examples

• -H:ImageObjectTreeSuppressTypes=java.io.BufferedWriter — suppress the expansion of java.io.BufferedWriter objects
• -H:ImageObjectTreeSuppressTypes=java.io.BufferedWriter,java.io.BufferedOutputStream — suppress the expansion of java.io.BufferedWriter and java.io.BufferedOutputStream objects
• -H:ImageObjectTreeSuppressTypes=java.io.* — suppress the expansion of all java.io.* objects
• -H:ImageObjectTreeExpandTypes=java.lang.String — force the expansion of java.lang.String objects
• -H:ImageObjectTreeExpandTypes=java.lang.String,java.math.BigInteger — force the expansion of java.lang.String and java.math.BigInteger objects
• -H:ImageObjectTreeExpandTypes=java.lang.* — force the expansion of all java.lang.* objects
• -H:ImageObjectTreeSuppressTypes=java.io.* -H:ImageObjectTreeExpandTypes=java.io.PrintStream — suppress the expansion of all java.io.* but not java.io.PrintStream objects
• -H:ImageObjectTreeExpandTypes=* — force the expansion of objects of all types, including those suppressed by default

• -H:ImageObjectTreeSuppressRoots=»java.nio.charset.Charset.lookup(String)» — suppress the expansion of all constants embedded in the graph of com.oracle.svm.core.amd64.FrameAccess.wordSize()
• -H:ImageObjectTreeSuppressRoots=java.util.* — suppress the expansion of all roots that start with java.util.
• -H:ImageObjectTreeExpandRoots=java.lang.Character$UnicodeBlock.map — force the expansion of java.lang.Character$UnicodeBlock.map static field root
• -H:ImageObjectTreeSuppressRoots=java.util.* -H:ImageObjectTreeExpandRoots=java.util.Locale — suppress the expansion of all roots that start with java.util. but not java.util.Locale
• -H:ImageObjectTreeExpandRoots=* — force the expansion of all roots, including those suppressed by default

Report files

The reports are generated in the reports subdirectory, relative to the image building directory. When executing the native-image executable the image build directory defaults to the working directory and can be modified using the -H:Path= option.

The call tree report name has the structure call_tree__.txt . The object tree report name has the structure: object_tree__.txt . The image name is the name of the generated image, which can be set with the -H:Name= option. The is in the yyyyMMdd_HHmmss format.

Источник