Tai-e Reference Documentation

Download IntelliJ IDEA from JetBrains. and install it. We recommend installing a recent version (2021.3 or newer) of IntelliJ IDEA for better support of Java 17.

Start to open a project

Select root directory of Tai-e and click "Open".

IntelliJ IDEA may pop up a dialog asking if you trust the Gradle project. Just click "Trust Project" (Don’t worry. Tai-e is benign 😃).

You may wait a moment for importing Tai-e.

Go to File > Project Structure…, click "Project SDK", select JDK 17. Next, expand "Language level", select "SDK default" (if the default is just 17) or "17 - Sealed types, always-strict floating-point semantics":

As Tai-e is a Gradle project, IntelliJ IDEA always build and run it with Gradle by default, which makes it a bit slower and always output some annoying Gradle-related messages:

To get rid of these problems, you could use IntelliJ IDEA instead of Gradle to build and run Tai-e. Just go to File > Settings, and change the build and run tool from Gradle to IntelliJ IDEA:

To run Tai-e in IntelliJ IDEA, first choose main class of Tai-e and open "Run Configuration":

then configure program arguments as follows:

That’s it! If you could finish above steps without any problems, then you have successfully setup Tai-e in IntelliJ IDEA. ヽ(｡◕‿◕｡)ﾉﾟ

Before running Tai-e, please finish following steps:

The main class (entry) of Tai-e is pascal.taie.Main, and we classified its options into three categories:

Below we introduce these options.

These options specify the Java program (say P) and library to be analyzed.

These options decide the analyses to be executed and their behaviors. We divided these options into two groups: general analysis options which affect multiple analyses, and specific analysis options which are relevant to individual analysis.

We give an example of how to analyze a program by Tai-e. Suppose we want to analyze a program P as described below:

Then the options would be:

In Tai-e, taint analysis is designed and implemented as a plugin of pointer analysis framework. To enable taint analysis, simply start pointer analysis with option taint-config, for example:

then Tai-e will run taint analysis (together with pointer analysis) using a configuration file specified by <path/to/config> (if you need to specify multiple configuration files, please refer to Multiple Configuration Files). In the upcoming section, we will provide a comprehensive guide on crafting a configuration file.

In this section, we present instructions on configuring sources, sinks, taint transfers, and sanitizers for the taint analysis using a YAML configuration file. To get a broad understanding, you can start by examining the taint-config.yml file from our test cases as an illustrative example.

Currently, the output of the taint analysis consists of two parts: console output and taint flow graph.

At first, you need to implement your analysis class, which should extend either MethodAnalysis, ClassAnalysis or ProgramAnalysis (all in package pascal.taie.analysis) depending on whether the analysis runs on method-, class- or program-level. When writing the analysis class, you need to:

Note that above *Analysis classes are generic and the type parameter is identical to the type of analysis result, which is the return type of the corresponding analyze method, i.e., Tai-e assumes that return value of analyze is the analysis result (and manages results based on such assumption). Below we give some tips that may be useful for developing new analysis.

To make an analysis available in Tai-e, you need to register it by adding its information (such as analysis id, analysis class, etc.) to the configuration file src/main/resources/tai-e-analyses.yml ("config file" for short), which contains the information of all available analyses. Please refer to Analysis Management for details about analysis registration.

After adding analysis information to config file, your analysis is now available in Tai-e.

We give a simple example to illustrate how to add a new analysis to Tai-e.

Suppose that we are going to implement an intra-procedural dead code detection, which requires CFG and the analysis results of live variable analysis and constant propagation. We choose to extend MethodAnalysis, and complete the required tasks as explained in Step 1 (we omit concrete analysis logic for simplicity):

Then we register the analysis by adding its information to src/main/resources/tai-e-analyses.yml (The analysis does not have options, thus we can ignore item options):

That’s it! Now you can run the dead code detection via option -a my-deadcode.

Tai-e IR is typed, 3-address, statement and expression based representation of Java method body.

You could dump IR for the classes of input program to .tir files via option -a ir-dumper. By default, Tai-e dumps IR to its default output directory output/. If you want to dump IR to a specific directory, just use option -a ir-dumper=dump-dir:path/to/dir. ir-dumper is implemented as a class analysis, thus the scope of the classes it dumps are affected by option -scope.

The IR classes reside in package pascal.taie.ir and its sub-packages.

There are three core classes in Tai-e IR:

We believe that the API of IR is self-documenting and easy to use. To make IR more intelligible, we present a formal definition (i.e., context-free grammar) below that illustrates all kinds of expressions and statements in the IR, and how Stmt are formed by Exp. Most non-terminals in the grammar corresponds to classes in pascal.taie.ir.

As mentioned in Develop A New Analysis, to add a new analysis to Tai-e, one needs to register its information in analysis configuration file src/main/resources/tai-e-analyses.yml. Each analysis entry consists of five (or less) attributes:

This attribute allowing to specify default values for all options of the analysis. These values can be overwritten by runtime-specified option values. You don’t need to write this attribute if your analysis has no options.

You can see examples about analysis registration in Section 5.1 of our technical report and tai-e-analyses.yml.

At runtime, Tai-e first generates an analysis plan (essentially a list of analyses to be executed) based on tai-e-analyses.yml and runtime-provided option values, and then runs analyses in order according to the plan.

As described in Command-Line Options, there are two approaches to specify the analyses to execute. Next, we will explain how they affect the generated analysis plan.

Result management is important for the cases that an analysis requires the results of other analyses, which happen frequently. Depending on the type of analysis, Tai-e automatically stores the results in various locations:

Benefiting from the result management, the developers only need to remember one API, getResult(id) (id is identifier of the analysis), to obtain results of any types of analyses, e.g., ir.getResult(id) for method-level analysis, jclass.getResult(id) for class-level analysis, and world.getResult(id) for program-level analysis.

With aforementioned mechanisms, it is fairly simple to coordinate multiple analyses in Tai-e.

The analysis id of pointer analysis is pta, and here we list its key options:

We explain how this analysis plugin system works.As shown in figure below:

The analysis plugin system includes a pointer analysis solver (pascal.taie.analysis.pta.core.solver.Solver) and a number of analyses that communicate with it.Each of these analyses is referred to as an analysis plugin that needs to implement interface pascal.taie.analysis.pta.plugin.Plugin.The interactions between pointer analysis solver and analysis plugin are carried out by calling each other’s APIs of Solver and Plugin, which are highlighted in blue and red, respectively.The Solver APIs have been implemented in the framework, and developers only need to implement the related APIs of Plugin, which are invoked by Solver at different stages (e.g., initialization and finishing) or on different events (e.g., discovery of new points-to relations and call edges).The additional auxiliary APIs, e.g., Solver.addStmts() and Plugin.onNewMethod(), are optional and designed to make it easier to implement specific analysis logics.

Let us briefly illustrate the basic working mechanism that drives those core APIs. Assuming you are implementing the onNewPointsToSet() method of an analysis Plugin, this means whenever an interested variable’s (parameter CSVar) points-to set (parameter PointsToSet) is changed (i.e., it points to more objects), you need to encode your logic to reflect the side effect made by this change; the final consequence of such an effect, from the perspective of pointer analysis, is to modify the points-to set of any related pointers or to add call graph edges at pertinent call sites. Accordingly, you should call Solver.addPointsTo() or Solver.addCallEdge() to alert the solver of these modifications. Conversely, during each analysis iteration, the solver calls Plugin.onNewPointsToSet() and Plugin.onNewCallEdge() of every plugin to notify them of any changes to the variables' points-to sets or call graph edges, respectively. As a result, to add a new analysis that interacts with pointer analysis, developers just need to implement a few methods of Plugin in accordance with the requirement, as previously described.

This analysis plugin system is currently being used by a number of ongoing internal projects implemented by different developers (these projects will be released when finished), and the feedback from developers is very promising: everyone agrees that it can fulfill their practical needs and is simple to understand and apply. For more details of the analysis plugin system, please see Section 4.1 of Tai-e’s paper and the source code (specifically, the interfaces Plugin and Solver, which are self-documenting).

We use an example to illustrate how to develop a new analysis plugin and add it to the pointer analysis framework.For simplicity, we omit the concrete analysis logics in the example.

Suppose we are implementing a taint analysis that interacts with pointer analysis.It requires following steps.

Analysis plugins are loaded via reflection, so that you do not need to modify existing code to integrate the plugin. Simply add the plugin class name to the plugins option of pointer analysis to turn it on:

That’s it! Your taint analysis will run together with the pointer analysis.