Unsoundness in InterproceduralConstantValuePropagator

[amordahl]

Hi,

When running FlowDroid under a configuration that sets codeelimination to REMOVECODE, the tool misses flows because the implementation of the InterproceduralConstantValuePropagator is unsound.

Test Case

ActivityLifecycle1.apk in DroidBench 3.0.

Expected Output

[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke r4.<java.net.HttpURLConnection: void connect()>() in method <de.ecspride.ActivityLifecycle1: void connect()> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r4 = virtualinvoke r3.<android.telephony.TelephonyManager: java.lang.String getDeviceId()>() in method <de.ecspride.ActivityLifecycle1: void onCreate(android.os.Bundle)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Data flow solver took 0 seconds. Maximum memory consumption: 56 MB
[main] INFO soot.jimple.infoflow.android.SetupApplication - Found 1 leaks

This is output by the default configuration.

Actual Output

[main] WARN soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - No results found.
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Data flow solver took 0 seconds. Maximum memory consumption: 58 MB
[main] INFO soot.jimple.infoflow.android.SetupApplication - Found 0 leaks

Observations

FlowDroid unsoundly removes the method connect() in the APK:

private void connect() throws IOException{
    	URL url = new URL(URL);
    	HttpURLConnection conn = (HttpURLConnection) url.openConnection(); //sink, leak
        conn.setRequestMethod("GET");
        conn.setDoInput(true);
        // Starts the query
        conn.connect();
    }

By using breakpoints, I was able to identify the problem as being in InterproceduralConstantValuePropagator, specifically in the hasSideEffectsOrCallsSink method. There are two issues I've identified here:

1. Unsound short circuiting.

The following happens in both hasSideEffectsOrCallsSink and hasSideEffectsOrReadsThis:

Boolean hasSideEffects = methodSideEffects.get(method);
if (hasSideEffects != null)
	return hasSideEffects;

The logic to determine whether a method can be removed is

// If this method returns nothing, is side-effect free and does not call a sink,
// we can remove it altogether. No data can ever flow out of it.
boolean remove = callee.getReturnType() == VoidType.v() && !hasSideEffectsOrReadsThis(callee);
remove |= !hasSideEffectsOrCallsSink(callee);

This is unsound; we can only terminate early if hasSideEffects is TRUE (i.e., we know we cannot remove the method). If it's FALSE, we need to continue analyzing the method in hasSideEffectsOrCallsSink.

2. Uninitialized methodSinks list.

When connect() is checked in hasSideEffectsOrCallsSink, the methodSinks structure is empty:

Boolean hasSink = methodSinks.get(method);
if (hasSink != null)
	return hasSink;

Obviously, this should find that connect() calls the sink conn.connect().

[StevenArzt]

Thanks for the thorough analysis of the issue. Can you open a merge request with a fix?

[amordahl]

Hi Steven,

While I would be happy to fix the first issue (i.e., unsound short circuiting), I am unaware of where or how methodSinks is intended to be initialized so I don't yet have a fix. I can continue looking but do you have any insight as to what the intended logic is?

[StevenArzt]

I committed some changes. That might not be the most elegant solution, but it should resolve the immediate problem with methodSinks.