Flowdroid Report Different Set of Flows On Same Analysis

[ClaudioRizzo]

Hi, it seems like Flowdroid is not deterministic. Running the same analysis (for the same APK) reports a different set of sources and sinks. For example, I am running Flowdroid with its "pro-performace" configuration (using EasyTaintWrapper)
java -jar Flowdroid.jar -apk /path/to/apk.apk -p ~/Android/Sdk/platforms/ -tw easy -t tmp/flowdroid-workspace/EasyTaintWrapperSource.txt -s /home/clod/tmp/flowdroid-workspace/general_source_sinks.txt -ne -af -al 3 -ca FAST -nc -ns -o out.xml
and I get the following two runs:

[main] INFO soot.jimple.infoflow.memory.MemoryWarningSystem - Shutting down the memory warning system...
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Memory consumption after path building: 164 MB
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Path reconstruction took 1 seconds
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink staticinvoke <android.util.Log: int e(java.lang.String,java.lang.String,java.lang.Throwable)>($r0, $r1, $r2) in method <com.startapp.android.publish.h.l: void b(java.lang.String,int,java.lang.String,java.lang.Throwable)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getCid()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r6 = virtualinvoke $r2.<android.location.LocationManager: android.location.Location getLastKnownLocation(java.lang.String)>($r5) in method <com.startapp.android.publish.h.k: android.location.Location a(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLatitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getLac()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r7 = virtualinvoke $r6.<android.net.wifi.WifiInfo: java.lang.String getSSID()>() in method <com.startapp.android.publish.model.BaseRequest: void fillWifiDetails(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLongitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink staticinvoke <android.util.Log: int v(java.lang.String,java.lang.String,java.lang.Throwable)>($r0, $r1, $r2) in method <com.startapp.android.publish.h.l: void b(java.lang.String,int,java.lang.String,java.lang.Throwable)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getCid()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r6 = virtualinvoke $r2.<android.location.LocationManager: android.location.Location getLastKnownLocation(java.lang.String)>($r5) in method <com.startapp.android.publish.h.k: android.location.Location a(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLatitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getLac()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r7 = virtualinvoke $r6.<android.net.wifi.WifiInfo: java.lang.String getSSID()>() in method <com.startapp.android.publish.model.BaseRequest: void fillWifiDetails(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLongitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r9.<java.io.Writer: void write(char[],int,int)>($r10, 0, $i0) in method <com.startapp.android.publish.h.n: boolean a(android.content.Context,java.lang.String,java.util.Map,java.lang.StringBuilder)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r8 = virtualinvoke $r5.<java.net.HttpURLConnection: java.io.InputStream getInputStream()>() in method <com.startapp.android.publish.h.n: boolean a(android.content.Context,java.lang.String,java.util.Map,java.lang.StringBuilder)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r7.<java.io.ByteArrayOutputStream: void write(byte[])>($r5) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.io.InputStream,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink staticinvoke <android.util.Log: int d(java.lang.String,java.lang.String)>($r1, $r0) in method <com.heyzap.internal.Logger: void debug(java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r0.<com.heyzap.house.abstr.AbstractActivity: android.content.Intent getIntent()>() in method <com.heyzap.house.abstr.AbstractActivity: void onCreate(android.os.Bundle)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Data flow solver took 5 seconds. Maximum memory consumption: 143 MB
[main] INFO soot.jimple.infoflow.android.SetupApplication - Found 9 leaks

and, for instance:

[main] INFO soot.jimple.infoflow.memory.MemoryWarningSystem - Shutting down the memory warning system...
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Memory consumption after path building: 165 MB
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Path reconstruction took 2 seconds
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r9.<java.io.Writer: void write(char[],int,int)>($r10, 0, $i0) in method <com.startapp.android.publish.h.n: boolean a(android.content.Context,java.lang.String,java.util.Map,java.lang.StringBuilder)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r8 = virtualinvoke $r5.<java.net.HttpURLConnection: java.io.InputStream getInputStream()>() in method <com.startapp.android.publish.h.n: boolean a(android.content.Context,java.lang.String,java.util.Map,java.lang.StringBuilder)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink staticinvoke <android.util.Log: int e(java.lang.String,java.lang.String,java.lang.Throwable)>($r0, $r1, $r2) in method <com.startapp.android.publish.h.l: void b(java.lang.String,int,java.lang.String,java.lang.Throwable)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getCid()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r6 = virtualinvoke $r2.<android.location.LocationManager: android.location.Location getLastKnownLocation(java.lang.String)>($r5) in method <com.startapp.android.publish.h.k: android.location.Location a(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLatitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getLac()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r7 = virtualinvoke $r6.<android.net.wifi.WifiInfo: java.lang.String getSSID()>() in method <com.startapp.android.publish.model.BaseRequest: void fillWifiDetails(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLongitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink staticinvoke <android.util.Log: int v(java.lang.String,java.lang.String,java.lang.Throwable)>($r0, $r1, $r2) in method <com.startapp.android.publish.h.l: void b(java.lang.String,int,java.lang.String,java.lang.Throwable)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getCid()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r6 = virtualinvoke $r2.<android.location.LocationManager: android.location.Location getLastKnownLocation(java.lang.String)>($r5) in method <com.startapp.android.publish.h.k: android.location.Location a(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLatitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $i0 = virtualinvoke $r5.<android.telephony.gsm.GsmCellLocation: int getLac()>() in method <com.startapp.android.publish.model.BaseRequest: void fillNetworkOperatorDetails(android.content.Context,android.telephony.TelephonyManager)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r7 = virtualinvoke $r6.<android.net.wifi.WifiInfo: java.lang.String getSSID()>() in method <com.startapp.android.publish.model.BaseRequest: void fillWifiDetails(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $d0 = virtualinvoke $r5.<android.location.Location: double getLongitude()>() in method <com.startapp.android.publish.model.GetAdRequest: void fillLocationDetails(com.startapp.android.publish.model.AdPreferences,android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink virtualinvoke $r5.<java.io.ByteArrayOutputStream: void write(byte[])>($r6) in method <com.heyzap.http.SimpleMultipartEntity: void addPart(java.lang.String,java.lang.String,java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - The sink staticinvoke <android.util.Log: int d(java.lang.String,java.lang.String)>($r1, $r0) in method <com.heyzap.internal.Logger: void debug(java.lang.String)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r0.<com.heyzap.house.abstr.AbstractActivity: android.content.Intent getIntent()>() in method <com.heyzap.house.abstr.AbstractActivity: void onCreate(android.os.Bundle)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - - $r5 = virtualinvoke $r3.<java.util.Locale: java.lang.String getCountry()>() in method <com.heyzap.internal.Utils: java.util.HashMap extraParams(android.content.Context)>
[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Data flow solver took 5 seconds. Maximum memory consumption: 144 MB
[main] INFO soot.jimple.infoflow.android.SetupApplication - Found 8 leaks

It varies with multiple runs. I have tried different configurations and all of them at some point present the same issue (the more precise, the rarer it is). Is non-determinism to be expected? I know there was an issue similar to this at some point in the past (https://github.com/secure-software-engineering/soot-infoflow-android/issues/31). It is somehow related?

The following is the SHA256 of the apk I am analysing: 9E4E75F510F76C4E4376A9AD6FD01843EA3F0F53CB9B3AEBDD3EBC6DC0A72C1D

[StevenArzt]

Do you also have a different number of results being reported before path reconstruction starts? There is a line in the log before the portion you have posted that tells you about the number of leaks detected during the taint propagation phase, right before path reconstruction starts.

Generally, path reconstruction is a best-effort approach. The result of the taint propagation phase is a taint graph that connects sources to sinks via data flow edges. FlowDroid then starts at the sinks and traverses the graph backwards to generate paths between sources and sinks. Unfortunately, taint graphs can contain cycles (loops, recursions). Therefore, the number of paths between a given source and a given sink is unbounded in the general case. FlowDroid solves this issue by returning a "witness", i.e., one path among all that are possible for a given pair of source and sink. This process is relatively complex, so I suspect some paths get dropped here.

[ClaudioRizzo]

First, thank you for your prompt reply.

So far no, before the path reconstruction the result is always the same in the few runs I have tried.

I tried a new fresh clone of Flowdroid this morning and run everything with the default SourceAndSinks definition shipped with it. I attached the 2 run.
It seems like that the solution to the IFDS reports the same number of results in both cases. However, I am not sure how to map this result to the one flowdroid reports. Sources and Sinks couple are not always the same. For instance, you won't find the sink with signature
<android.util.Log: int d(java.lang.String,java.lang.String,java.lang.Throwable)> in log11, but you will in log14.

Even more odd, I can find the couple (source, sink) (<android.location.LocationManager: android.location.Location getLastKnownLocation(java.lang.String)>, <android.util.Log: int v(java.lang.String,java.lang.String,java.lang.Throwable)>) in out11 but not out14. On the other hand, in out14 there is a similar couple, which is the same apart from the fact that the sink is the version without java.lang.Throwable.

Also, I found that the total of unique source and sinks for out14 sums up to 23, which is the number of result reported before the path reconstruction happens.

For my analysis, I need to run two analysis with different taint wrappers and report the differences in flows I find. However, due to this problem I cannot be sure whether these differences are due to the TaintWrapper or not. Do you have any workaround/advice on this?

log11.txt
log14.txt

[negara]

So does Flowdroid report deterministic leak results?