Writing an Analysis

Writing an Analysis

Chord provides several analysis templates: classes containing boilerplate code that can be extended by users to rapidly prototype different kinds of analyses. These classes are organized in the following hierarchy in package chord.project.analyses:

JavaAnalysis
    |
    |--- ProgramDom
    |
    |--- ProgramRel
    |
    |--- DlogAnalysis
    |
    |--- RHSAnalysis
    |        |
    |        |--- ForwardRHSAnalysis
    |        |
    |        |--- BackwardRHSAnalysis
    |
    |--- BasicDynamicAnalysis
             |
             |--- DynamicAnalysis

The following sections describe each of these analysis templates in more detail.

JavaAnalysis

Class chord.project.analyses.JavaAnalysis is the most general template for writing an analysis. An analysis can be created using this template by extending this class as follows:

import chord.project.Chord;
import chord.project.ClassicProject;
import chord.project.analyses.JavaAnalysis;
import chord.program.Program;

@Chord(
    name = "<ANALYSIS_NAME>",
    consumes = { "C1", ..., "Cn" },
    produces = { "P1", ..., "Pm" },
    namesOfTypes = { "C1", ..., "Cn", "P1", ..., "Pm" },
    types = { A1.class, ..., An.class, B1.class, ..., Bm.class }
)
public class ExampleAnalysis extends JavaAnalysis {
    @Override public void run() {
        Program program = Program.g();
        ClassicProject project = ClassicProject.g();
        A1 c1 = (A1) project.getTrgt("C1");
        ...
        An cn = (An) project.getTrgt("Cn");
        B1 p1 = (B1) project.getTrgt("P1");
        ...
        Bm pm = (Bm) project.getTrgt("Pm");
        // compute produced targets p1, ..., pm from program and
        // consumed targets c1, ..., cn
        ...
    }
}

To run the analysis, class ExampleAnalysis must be compiled to a .class file that occurs in some element (directory or jar/zip file) of the path specified by property chord.java.analysis.path. This causes the analysis to be included in a Chord project as a task that is represented as a separate object of class ExampleAnalysis.

The @Chord annotation, defined in class chord.project.Chord, specifies via fields the following aspects of the analysis:

• Field name specifies the name of the analysis (<ANALYSIS_NAME>).
• Field consumes specifies the names of targets that are consumed by the analysis (C1, ..., Cn).
• Field produces specifies the names of targets that are produced by the analysis (P1, ..., Pm).
• Fields namesOfTypes and types specify the types of targets. There is a 1-to-1 correspondence between the arrays denoted by these two fields, e.g., the type of the target named C1 is class A1, and so on. In principle, the type of any target in the project can be specified here. In practice, however, the types of only the targets declared as consumed/produced by this analysis are specified. Moreover, although the type of each target that is consumed/produced by the above analysis is specified in the above annotation, in practice the types of hardly any targets need to be explicitly specified, because they can be automatically inferred by Chord from analyses created using more specialized templates discussed below that also consume/produce those targets.

The code of the analysis must be supplied in the run() method. This method typically does the following in order: (1) retrieves the program being analyzed and the representation of each consumed/produced target from the project; (2) performs some computation that uses the program and the consumed targets as inputs; and (3) writes the outputs of the computation to the produced targets.

The analysis templates presented in the following sections are more specialized forms of the JavaAnalysis template: they constrain the number and kinds of consumed/produced targets and/or the analysis code in the run() method.

ProgramDom

Class chord.project.analyses.ProgramDom is a template for writing a program domain analysis. A program domain represents an indexed set of values of a fixed kind, typically from the program being analyzed, such as the set of all methods in the program, the set of all fields in the program, etc. Indices are assigned starting from 0 and in the order in which values are added to the set. A program domain primarily serves as an input to Datalog analyses (see Section *). Thus, it is a kind of target (i.e., analysis result) in a Chord project. A common way to define a program domain is to create a program domain analysis by extending class ProgramDom as follows:

import chord.project.Chord;
import chord.project.ClassicProject;
import chord.project.analyses.ProgramDom;
import chord.program.Program;

@Chord(
    name = "<DOM_NAME>",
    consumes = { "C1", ..., "Cn" }
)
public class ExampleDom extends ProgramDom<DOM_TYPE> {
    @Override public void fill() {
        Program p = Program.g();
        ClassicProject project = ClassicProject.g();
        A1 c1 = (A1) project.getTrgt("C1");
        ...
        An cn = (An) project.getTrgt("Cn");
        // populate domain using program and consumed targets c1, ..., cn
        for (...) {
            DOM_TYPE e = ...;
            add(e); 
        }
    }
}

To run the analysis, class ExampleDom must be compiled to a .class file that occurs in some element (directory or jar/zip file) of the path specified by property chord.java.analysis.path. This causes the analysis to be included in a Chord project as a task that is represented as a separate object of class ExampleDom. Moreover, that object also denotes a target in the Chord project. Both the task and target have the same name <DOM_NAME>.

The ProgramDom template can be viewed as providing the following specialized form of the general JavaAnalysis template:

• It consumes any number and kinds of targets explicitly declared in the @Chord annotation (C1, ..., Cn).
• It produces a single target, namely, the defined program domain itself (named <DOM_NAME> and of type ExampleDom). It is a runtime error to explicitly declare any produced targets in the @Chord annotation (see below).
• Its run() method adds values to the defined program domain. Typically, it suffices to override the fill() method (which is called by the run() method) and call from it the add(e) method for each value e to be added to the domain in order.

It is a runtime error to explicitly specify any produced targets in the @Chord annotation of a class extending ProgramDom. If you wish to define an analysis that produces additional targets besides a program domain, then you can still define the program domain in a class such as ExampleDom that extends ProgramDom, but you must not annotate it with the @Chord annotation (since this annotation causes the class to be egarded as defining an analysis). Instead, define the analysis in a separate class that extends JavaAnalysis, as follows:

import chord.project.Chord;
import chord.project.ClassicProject;
import chord.project.analyses.JavaAnalysis;

@Chord(
    name = "<ANALYSIS_NAME>",
    consumes = { "C1", ..., "Cn" },
    produces = { "<DOM_NAME>", ... }
)
public class ExampleAnalysis extends JavaAnalysis {
    @Override public void run() {
        ExampleDom d = (ExampleDom) ClassicProject.g().getTrgt("<DOM_NAME>");
        d.run();  // produce domain named <DOM_NAME>
        ...
    }
}

Note that targets C1, ..., Cn that were declared as consumed in the @Chord annotation of class ExampleDom (and any other fields such as namesOfTypes and types) must now be provided in the @Chord annotation of class ExampleAnalysis.

ProgramRel

Class chord.project.analyses.ProgramRel is a template for writing a program relation analysis. A program relation represents a set of tuples over one or more fixed program domains. A program relation primarily serves as an input or output of Datalog analyses (see Section *). Thus, it is a kind of target (i.e., analysis result) in a Chord project. A common way to define a program relation is to create a program domain analysis by extending class ProgramRel as follows:

import chord.project.Chord;
import chord.project.ClassicProject;
import chord.project.analyses.ProgramDom;
import chord.project.analyses.ProgramRel;
import chord.program.Program;

@Chord(
    name = "<REL_NAME>",
    consumes = { "C1", ..., "Cn" },
    sign = "<DOM_NAMES>:<DOM_ORDER>"
)
public class ExampleRel extends ProgramRel {
    @Override public void fill() {
        Program p = Program.g();
        ProgramDom<T1> d1 = doms[0];
        ...
        ProgramDom<Tm> dm = doms[m-1];
        ClassicProject project = ClassicProject.g();
        A1 c1 = (A1) project.getTrgt("C1");
        ...
        An cn = (An) project.getTrgt("Cn");
        // populate relation using program, its domains d1, ..., dm, and
        // consumed targets c1, ..., cn
        for (...) {
            T1 o1 = ...;
            Tm om = ...;
            add(o1, ..., om); 
        }
    }
}

To run the analysis, class ExampleRel must be compiled to a .class file that occurs in some element (directory or jar/zip file) of the path specified by property chord.java.analysis.path. This causes the analysis to be included in a Chord project as a task that is represented as a separate object of class ExampleRel. Moreover, that object also denotes a target in the Chord project. Both the task and target have the same name <REL_NAME>.

The ProgramRel template can be viewed as providing the following specialized form of the general JavaAnalysis template:

• It consumes any number and kinds of targets explicitly declared in the @Chord annotation (C1, ..., Cn) as well as implicit targets corresponding to the program domains in the schema of the defined program relation (named D1, ..., Dm and having type ProgramDom).
• It produces a single target, namely, the defined program relation itself (named <REL_NAME> and of type ExampleRel). It is a runtime error to explicitly declare any produced targets in the @Chord annotation (see below).
• Its run() method adds tuples to the defined program relation. Typically, it suffices to override the fill() method (which is called by the run() method) and call from it the add(o1, ..., om) method for each tuple (o1, ..., om) to be added to the relation.

Unlike for program domains, the order in which tuples are added to a program relation is irrelevant. But the relative ordering of the program domains over which the program relation is declared matters heavily for performance. This is because each program relation in Chord is represented symbolically (as oppoosed to explicitly) using a data structure called a Binary Decision Diagram (BDD for short). This in turn is because in pratice, a program relation (e.g., one representing context-sensitive points-to information) can contain millions or billions of tuples even for a moderately-sized input Java program; representing such a large number of tuples explicitly is prohibitively and needlessly expensive. The size of a BDD, on the other hand, does not depend at all upon the number of tuples in the program relation that the BDD represents. Instead, it depends heavily upon the relative ordering of the program domains over which the program relation is declared. Hence, the @Chord annotation on a class such as ExampleRel that extends ProgramRel is required to have a sign field whose value is the sign of the program relation. A sign is a string of the form <DOM_NAMES>:<DOM_ORDER> where:

• <DOM_NAMES> is mandatory and specifies the relation's schema: a comma-separated list of names of the domains over which the relation is defined, with each domain name suffixed with a non-negative integer that is typically 0 and must be unique across multiple occurrences of the same domain name. The order of domain names in the schema is irrelevant: users must pick this order purely based on what order they find most convenient to remember.

  For example, suppose the program relation represents the result of Class Hierarchy Analysis (CHA), i.e., it contains each tuple of the form (m₁,t,m₂) such that method m₂ is the resolved method of an invokevirtual or invokeinterface call with resolved method m₁ on an object of class t. Let M and T denote the names of the program domains representing the set of all methods and the set of all classes, respectively, in the Java program being analyzed. Then, <DOM_NAMES> for this program relation could be any of "M0,T0,M1", "M1,T0,M0", "M0,T1,M1", and so on.

• <DOM_ORDER> is optional and determines the relation's representation as a BDD. It is a permutation of the names in DOM_NAMES> with a separator `_' or `x' between consecutive names. The order of names in this list, and the kind of separators used between them, are what determines both the size of the BDD and the performance of operations on it (such as join, selection, projection, etc.).

  An example value of <DOM_ORDER> for the CHA program relation above with <DOM_LIST> as "M0,T0,M1" is "M0xM1_T0"; another example value is "M1_T0_M0".

Chapter * describes how BDDs are represented (Section *) and how you can tune their size and the performance of operations on them (Section *).

It is a runtime error to explicitly specify any produced targets in the @Chord annotation of a class extending ProgramRel. If you wish to define an analysis that produces additional targets besides a program relation, then you can still define the program relation in a class such as ExampleRel that extends ProgramRel, but you must not annotate it with the @Chord annotation (since this annotation causes the class to be egarded as defining an analysis). Instead, define the analysis in a separate class that extends JavaAnalysis, as follows:

import chord.project.Chord;
import chord.project.ClassicProject;
import chord.project.analyses.JavaAnalysis;

@Chord(
    name = "<ANALYSIS_NAME>",
    consumes = { "C1", ..., "Cn" },
    produces = { "<REL_NAME>", ... },
    namesOfSigns = { "<REL_NAME>", ... },
    signs = { "<DOM_ORDER>:<DOM_NAME>", ... }
)
public class ExampleAnalysis extends JavaAnalysis {
    @Override public void run() {
        ExampleRel r = (ExampleRel) ClassicProject.g().getTrgt("<REL_NAME>");
        r.run();  // produce program relation named <REL_NAME>
    }
}

Note that targets C1, ..., Cn that were declared as consumed in the @Chord annotation of class ExampleRel (and any other fields such as namesOfTypes and types) must now be provided in the @Chord annotation of class ExampleAnalysis. Just like the 1-to-1 correspondence between the values of fields namesOfTypes and types, there is a 1-to-1 correspondence between the values of fields namesOfSigns and signs, which allow relating the name of any program relation in the project with its sign.

DlogAnalysis

A common way to rapidly prototype analyses in Chord is using a declarative logic-programming language called Datalog. A Datalog analysis is defined in a .dlog file that primarily specifies the following:

• A set of program domains D1, ..., Dk. A program domain is a set of values of a fixed kind. Each program domain in a Chord project is a target that is represented as a separate object of class ProgramDom (see Section *).
• A set of program relations, including input relations I1, ..., In and output relations O1, ..., Om. A program relation is a set of tuples over one or more fixed program domains D1, ..., Dk. Each program relation in a Chord project is a target that is represented as a separate object of class ProgramRel (see Section *).
• A set of rules (constraints) R specifying how to compute the output relations from the input relations.

To run the analysis, the .dlog file must occur in some element (directory or jar/zip file) of the path specified by property chord.dlog.analysis.path. This causes the analysis to be included in a Chord project as a task that is represented as a separate object of class chord.project.analyses.DlogAnalysis. Note that, unlike class JavaAnalysis, users must not extend class DlogAnalysis but must instead define the analysis in a .dlog file.

The DlogAnalysis template can be viewed as providing the following specialized form of the general JavaAnalysis template:

• It consumes targets D1, ..., Dk of type ProgramDom and I1, ..., In of type ProgramRel.
• It produces targets O1, ..., Om of type ProgramRel.
• Its run() method executes Datalog solver bddbddb to compute output relations O1, ..., Om from input relations I1, ..., In by solving constraints R.

DynamicAnalysis

Under construction

RHSAnalysis

Under construction

Writing an Analysis