Tai-e seems unable to handle the taint-flow through the collection-class correctly.

[Spr1n9T1me]

📝 Overall Description

Description

I tried to test the taint-analysis Module of Tai-e with one example below:

package collection;

import util.SourceSinks;
import java.util.ArrayList;

public class CollectionExample {
    public static void main(String[] args) throws Exception{
        ArrayList<String> list = new ArrayList<>();
        list.add(SourceSinks.getTaintedInput()); // source point
        list.add(SourceSinks.getSafeInput());
        String element = list.get(0);
        Runtime.getRuntime().exec(element); // sink point
    }
}

which converts to tir format is:

public class collection.CollectionExample extends java.lang.Object {

   public void <init>() {
       [0@L8] invokespecial %this.<java.lang.Object: void <init>()>();
       [1@L8] return;
   }

   public static void main(java.lang.String[] r6) {
       java.util.ArrayList $r0;
       java.lang.String $r1, $r2, r4;
       java.lang.Object $r3;
       int %intconst0;
       java.lang.Runtime $r5;
       [0@L11] $r0 = new java.util.ArrayList;
       [1@L11] invokespecial $r0.<java.util.ArrayList: void <init>()>();
       [2@L12] $r1 = invokestatic <util.SourceSinks: java.lang.String getTaintedInput()>();
       [3@L12] invokevirtual $r0.<java.util.ArrayList: boolean add(java.lang.Object)>($r1);
       [4@L13] $r2 = invokestatic <util.SourceSinks: java.lang.String getSafeInput()>();
       [5@L13] invokevirtual $r0.<java.util.ArrayList: boolean add(java.lang.Object)>($r2);
       [6@L14] %intconst0 = 0;
       [7@L14] $r3 = invokevirtual $r0.<java.util.ArrayList: java.lang.Object get(int)>(%intconst0);
       [8@L14] r4 = (java.lang.String) $r3;
       [9@L15] $r5 = invokestatic <java.lang.Runtime: java.lang.Runtime getRuntime()>();
       [10@L15] invokevirtual $r5.<java.lang.Runtime: java.lang.Process exec(java.lang.String)>(r4);
       [11@L26] return;
   }

}

When pointer analysis is executed to [7@L14] $r3 = invokevirtual $r0.<java.util.ArrayList: java.lang.Object get(int)>(%intconst0); , the system will try to get pts(%intconst0), but during initialization, %intconst0 = 0; is not considered a statement that creates ConstantObj. The reason is that DefaultSolver can only create ConstantObj for statements whose Rvalue is ReferenceLiteral(refer to link ).NumberLiteral is not a sub-type of ReferenceLiteral. As a result, the passed parameter pointer set of list.get(0) is null, and pointer analysis is interrupted here. Ultimately, the taint-flow cannot be detected.
So my question is, how to detect the taint-flow In this case.

taint-flow-graph output

I have dumped the outputed taint-flow-graph.dot，content below:

digraph G {
  node [];
  edge [];
  "VarNode{<collection.CollectionExample: void main(java.lang.String[])>/$r1}" [fillcolor=floralwhite,shape=box,style=filled];
  "VarNode{<java.util.ArrayList: boolean add(java.lang.Object)>/r2}" [fillcolor=floralwhite,shape=box,style=filled];
  "ArrayIndexNode{NewObj{<java.util.ArrayList: void <init>(int)>[3@L153] newarray java.lang.Object[i0]}}" [fillcolor=khaki1,style=filled];
  "VarNode{<collection.CollectionExample: void main(java.lang.String[])>/$r1}" -> "VarNode{<java.util.ArrayList: boolean add(java.lang.Object)>/r2}" [color=blue];
  "VarNode{<java.util.ArrayList: boolean add(java.lang.Object)>/r2}" -> "ArrayIndexNode{NewObj{<java.util.ArrayList: void <init>(int)>[3@L153] newarray java.lang.Object[i0]}}" [color=red];
  "{ kind: \"call\", method: \"<util.SourceSinks: java.lang.String getTaintedInput()>\", index: \"result\", type: \"java.lang.String\" }\n<collection.CollectionExample: void main(java.lang.String[])>[2@L12] $r1 = invokestatic util.SourceSinks.getTaintedInput()/result" [fillcolor=gold,shape=doubleoctagon,style=filled];
  "{ kind: \"call\", method: \"<util.SourceSinks: java.lang.String getTaintedInput()>\", index: \"result\", type: \"java.lang.String\" }\n<collection.CollectionExample: void main(java.lang.String[])>[2@L12] $r1 = invokestatic util.SourceSinks.getTaintedInput()/result" -> "VarNode{<collection.CollectionExample: void main(java.lang.String[])>/$r1}";
}

🎯 Expected Behavior

Detect the taint-flow correctly through collection-class.

🐛 Current Behavior

Pointer analysis interrupted encountering collection-class.

🔄 Reproducible Example

given above.

⚙️ Tai-e Arguments

🔍 Click here to see Tai-e Options

optionsFile: null
printHelp: false
classPath: []
appClassPath:
- tai-e-tir-test/target/classes
mainClass: collection.CollectionExample
inputClasses: []
javaVersion: 8
prependJVM: false
allowPhantom: true
worldBuilderClass: pascal.taie.frontend.soot.SootWorldBuilder
outputDir: output
preBuildIR: false
worldCacheMode: false
scope: REACHABLE
nativeModel: true
planFile: null
analyses:
ir-dumper: ""
pta: cs:ci;distinguish-string-constants:app;taint-config:src\main\resources\taint-config.yml;only-app:false;dump-ci:true
onlyGenPlan: false
keepResult:
- $KEEP-ALL

📜 Tai-e Log

🔍 Click here to see Tai-e Log

{{The content of 'output/tai-e.log' file}}

ℹ️ Additional Information

none

[jjppp]

Hi, could you share your TaintAnalysis configuration file taint-config.yml?

[Spr1n9T1me]

Hi, could you share your TaintAnalysis configuration file taint-config.yml?

sure, here is the taint-config.yml:

sources:
  - { kind: "call", method: "<util.SourceSinks: java.lang.String getTaintedInput()>",index: "result",type: "java.lang.String" }

sinks:
  - { method: "<java.lang.Runtime: java.lang.Process exec(java.lang.String)>", index: "0" }

addtionally, the SourceSinks class:

package util;

public class SourceSinks {
    public static String getTaintedInput() { return "tainted"; }
    public static String getSafeInput() { return "safe"; }
}

[jjppp]

Hi @Spr1n9T1me! Sorry for the delayed response.
I don't think NumberLiteral is causing the problem, since ArrayLists are backed by arrays, and Tai-e handles arrays in a conservative way that does not require precise information about array indices.

89a4ea0 introduces a fix to handle arrays more soundly to capture taint flows that are previously missed due to an aggressive optimization, and can successfully detect the taint flow in your example after some testing. I would strongly recommend you try out our latest commit😊

[Spr1n9T1me]

Solved, thanks for your help!