Missed sink when using --pathreconstructionmode PRECISE

[draftyfrog]

Please consider the following code:

public void onCreate(Bundle savedInstanceState){
    super.onCreate(savedInstanceState);
    setContentView(R.layout.activity_main);

    String taint_1 = function1(source());
    String taint_2 = function1(taint_1);
    sink(taint_2);
}
public String source(){ // Defined as source 
    return "Secret";
}

public void sink(String param){ // Defined as sink
}

public String function1(String arg1){
    arg1 = function2(arg1);
    return arg1;
}
public String function2(String arg1){
    return arg1;
}

There is a taint path from the source()-call in onCreate to the sink, traversing function1 and function2 two times. If I run FlowDroid with the following command

java -jar ./soot-infoflow-cmd-2.13.0-jar-with-dependencies.jar \
 -a {path-to-apk} \
 -s ./SourcesAndSinks.xml \
 -o ./out.xml \
 -p {path-to-android-platforms-folder} \
 --mergedexfiles \
 --pathreconstructionmode PRECISE

it won't report this leak. If I change the --pathreconstructionmode from PRECISE to FAST or NONE (or just remove the whole argument), FlowDroid reports this leak.

If relevant, my SourcesAndSinks.xml looks like this

<sinkSources>
    <category id="NO_CATEGORY">
        <method signature="{package-name}.MainActivity: java.lang.String source()&gt;">
            <return type="java.lang.String">
                <accessPath isSource="true" isSink="false">
                </accessPath>
            </return>
        </method>
        <method signature="{package-name}.MainActivity: void sink(java.lang.String)&gt;">
            <param index="0" type="java.lang.String">
                <accessPath isSource="false" isSink="true"/>
            </param>
        </method>
    </category>
</sinkSources>

[t1mlange]

That's sort of a known limitation.

The result of the IFDS-based analysis is a taint graph where the nodes are the domain elements. Transforming this graph into a path through the program is basically equal to unrolling the DFS path. Because taint graphs can be cyclic (recursion) and we need to ensure termination, there is the arbitrarily-chosen limit of unrolling each taint at most once.

However, a limit of one also prevents building the path through repeatedly called functions.

FlowDroid/soot-infoflow/src/soot/jimple/infoflow/data/SourceContextAndPath.java

Lines 187 to 195 in 3a45a5d

	// Do not add the very same abstraction over and over again.
	if (this.path != null) {
	Iterator<Abstraction> it = path.reverseIterator();
	while (it.hasNext()) {
	Abstraction a = it.next();
	if (a == abs)
	return null;
	}
	}

Further, setting the path mode also affects an optimization in the IFDS solver itself.

• If the user does not want any paths, there's no need to keep the taint graph of callees at all. So in your example, at the end, we just have a graph source() -> taint_1 -> taint_2.
• If the user just cares about things that contribute to the taint propagation, we can cut out all callees that returned the calling context. Basically, this removes the arg -> param -> arg edges out of the taint graph.
• PRECISE equals to just print every statement associated with a taint in the graph, so there is no cutting at return sites at all.
  Therefore, the cutting might remove the cycle before the graph is being passed into the path builder.

FlowDroid/soot-infoflow/src/soot/jimple/infoflow/solver/AbstractIFDSSolver.java

Lines 26 to 54 in 3a45a5d

	/**
	* Shortens the predecessors of the first argument if configured.
	*
	* @param returnD data flow fact leaving the method, which predecessor chain should be shortened
	* @param incomingD incoming data flow fact at the call site
	* @param calleeD first data flow fact in the callee, i.e. with current statement == call site
	* @return data flow fact with a shortened predecessor chain
	*/
	protected D shortenPredecessors(D returnD, D incomingD, D calleeD, N currentUnit, N callSite) {
	switch (shorteningMode) {
	case AlwaysShorten:
	// If we don't build a path later, we do not have to keep flows through callees.
	// But we have to keep the call site so that we do not lose any neighbors, but
	// skip any abstractions inside the callee. This sets the predecessor of the
	// returned abstraction to the first abstraction in the callee.
	if (returnD != calleeD) {
	D res = returnD.clone(currentUnit, callSite);
	res.setPredecessor(calleeD);
	return res;
	}
	break;
	case ShortenIfEqual:
	if (returnD.equals(incomingD))
	return incomingD;
	break;
	}
	return returnD;
	}

If I change the --pathreconstructionmode from PRECISE to FAST or NONE (or just remove the whole argument), FlowDroid reports this leak.

If I run your example, only NONE will report the leak, as expected by the explanation above.