The results of running FlowDroid multiple times are inconsistent.

[litter47]

Dear Dr. Arzt,

I have observed a phenomenon but am unsure of the exact cause.I used the core analysis engine of FlowDroid to run a Java program and found that the results were inconsistent across multiple runs.After an Abstraction reaches the sink point and begins the process of tracing back the call chain, it produces different results, even though the Abstraction that reaches the sink point is the same.

The structure of the Abstraction that reaches the sink is:
Current Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Predecessor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
Current Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Predecessor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
Current Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: r1(javax.servlet.ServletRequest) * <+length> | >>
-> Predecessor Abstraction: $r2(javax.servlet.ServletRequest) * <+length> | >>
Current Abstraction: $r2(javax.servlet.ServletRequest) * <+length> | >>
-> Neighbor Abstraction: $r2(javax.servlet.ServletRequest) * <+length> | >>
-> Predecessor Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
Current Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
-> Neighbor Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
-> Neighbor Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
-> Neighbor Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
-> Neighbor Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
-> Predecessor Abstraction: $r3(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
Current Abstraction: $r3(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
-> Predecessor Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
Current Abstraction: r0(org.apache.catalina.core.ApplicationFilterChain$1) <org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> * <+length> | >>
-> Predecessor Abstraction: r2(org.apache.catalina.connector.RequestFacade) * <+length> | >>
Current Abstraction: r2(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Predecessor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
Current Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Neighbor Abstraction: r1(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Predecessor Abstraction: servletrequest(org.apache.catalina.connector.RequestFacade) * <+length> | >>
Current Abstraction: servletrequest(org.apache.catalina.connector.RequestFacade) * <+length> | >>
-> Predecessor Abstraction: request(org.apache.catalina.connector.RequestFacade) * <+length> | >>
Current Abstraction: request(org.apache.catalina.connector.RequestFacade) * <+length> | >>
No more predecessors.

The execution results are as follows:
1：
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - on Path:
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <dummyMainClass: void dummyMainMethod(java.lang.String[])>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> request = virtualinvoke $r7.<org.apache.catalina.connector.Request: javax.servlet.http.HttpServletRequest getRequest()>()
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <dummyMainClass: void dummyMainMethod(java.lang.String[])>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> servletrequest = (javax.servlet.ServletRequest) request
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <dummyMainClass: void dummyMainMethod(java.lang.String[])>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> virtualinvoke $r2.<org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(servletrequest, servletresponse)
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> specialinvoke $r3.<org.apache.catalina.core.ApplicationFilterChain$1: void (org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r0, r1, r2)
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain$1: void (org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> r0.<org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req> = r2
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain$1: void (org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> return
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> staticinvoke <java.security.AccessController: java.lang.Object doPrivileged(java.security.PrivilegedExceptionAction)>($r3)
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain$1: java.lang.Void run()>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> $r2 = r0.<org.apache.catalina.core.ApplicationFilterChain$1: javax.servlet.ServletRequest val$req>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain$1: java.lang.Void run()>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> staticinvoke <org.apache.catalina.core.ApplicationFilterChain: void access$000(org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>($r3, $r2, $r1)
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void access$000(org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> specialinvoke r0.<org.apache.catalina.core.ApplicationFilterChain: void internalDoFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r1, r2)
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void internalDoFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - -> interfaceinvoke $r38.<javax.servlet.Servlet: void service(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r1, r2)
09:36:24.639 [main] INFO auth.jarInflow.JarAuthInfoflow - Data flow solver took 4 seconds. Maximum memory consumption: 1444 MB
09:36:24.640 [main] INFO SetupApplication - Found 1 leaks from 29 sources

2:
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - on Path:
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <dummyMainClass: void dummyMainMethod(java.lang.String[])>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> request = virtualinvoke $r7.<org.apache.catalina.connector.Request: javax.servlet.http.HttpServletRequest getRequest()>()
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <dummyMainClass: void dummyMainMethod(java.lang.String[])>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> servletrequest = (javax.servlet.ServletRequest) request
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <dummyMainClass: void dummyMainMethod(java.lang.String[])>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> virtualinvoke $r2.<org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(servletrequest, servletresponse)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> specialinvoke $r3.<org.apache.catalina.core.ApplicationFilterChain$1: void (org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r0, r1, r2)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain$1: void (org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> return
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> specialinvoke r0.<org.apache.catalina.core.ApplicationFilterChain: void internalDoFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r1, r2)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void internalDoFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> interfaceinvoke r35.<javax.servlet.Filter: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse,javax.servlet.FilterChain)>(r1, r2, r0)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <BOOT-INF.classes.com.jsh.erp.filter.LogCostFilter: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse,javax.servlet.FilterChain)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> interfaceinvoke r13.<javax.servlet.FilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r0, r2)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> specialinvoke $r3.<org.apache.catalina.core.ApplicationFilterChain$1: void (org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r0, r1, r2)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain$1: void (org.apache.catalina.core.ApplicationFilterChain,javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> return
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void doFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> specialinvoke r0.<org.apache.catalina.core.ApplicationFilterChain: void internalDoFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r1, r2)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> <org.apache.catalina.core.ApplicationFilterChain: void internalDoFilter(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - -> interfaceinvoke $r38.<javax.servlet.Servlet: void service(javax.servlet.ServletRequest,javax.servlet.ServletResponse)>(r1, r2)
09:40:12.596 [main] INFO auth.jarInflow.JarAuthInfoflow - Data flow solver took 5 seconds. Maximum memory consumption: 1233 MB
09:40:12.597 [main] INFO SetupApplication - Found 1 leaks from 9 sources

[t1mlange]

The IFDS-native result representation is a taint graph with predecessors and neighbors (incoming abstraction that is already in the graph, e.g., after if else). Because the IFDS solver is highly parallelized, the order in which edges are discovered is non-deterministic. So in one execution, the graph might contain the abstraction from the condition=true path and the neighbor from the condition=false path, and in another vice versa.

Afterwards, this graph is traversed to build a concrete path through the program (see IAbstractionPathBuilder). The path builder builds a single witness, i.e., outputs a single path for each sink-source connection. The first path is stored and outputted. The path building is also parallelized, so the order of discovery doesn't necessarily determine the order in which paths are discovered. However, you might be able to add some logic to InfoflowResults to deterministically store the path (e.g. shortest and then lexically sorted or so).

Furthermore, there seems to be another problem in your case. It seems that the number of sources differs between different runs (from 9 sources vs from 29 sources). The obvious cause could be that the callgraph building reaches a timeout and therefore, the callgraph is incomplete and different. FlowDroid supports to serialize and deserialize the callgraph, which we always use when comparing different runs on the same application.

[litter47]

Thank you for your answer.

[StevenArzt]

To give you some more background on why we report a single witness and not all paths, take the following code example:

a = source();
if (...)
  b = a;
else
  b = "Hello";
if (...)
  c = "Hello";
else
  c = a;
sink(b+c);

In this example, there are 3 leaking paths:

• source + source
• "Hello" + source
• source + "Hello"

In the general case, if you have N conditionals, there might be 2^n paths. This can lead to a path explosion quickly and the analysis would no longer terminate in any realistic timeframe.

[litter47]

Thank you for your detailed explanations, which have given me a deeper understanding of FlowDroid. However, I still have a small question. Every time I run the analysis, the final result, Found 1 leaks from 149 sources, varies, with the “from xxx sources” part being different each time. In my analysis, there is only one source point and one sink point. As mentioned earlier, this variation might be caused by differences in the CallGraph. However, I have found that the CallGraph remains consistent in every run(The final generated Set<AbstractionAtSink> res is the same.). I can understand that the difference in the final result numbers is due to the fact that, as you mentioned, it generates not the full set of paths, but a subset of the full paths, so the number of paths differs each time.

[t1mlange]

Are the numbers also different in the source lookup log?

[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - Source lookup done, found X sources and Y sinks.

The easiest would be if you could provide the options and sources/sinks you used and the jar under analysis.

[litter47]

I'm sorry if my explanation was a bit unclear.

I modified a part of FlowDroid and used it to analyze a Java Web application. My entry point for the analysis is a self-constructed virtual main method. In the program, I only defined one source and one sink, and during the process of finding the source and sink, it only identified one of each:
16:40:12.825 [main] INFO auth.jarInflow.JarAuthInfoflow - Source lookup done, found 1 sources and 1 sinks.

Later, when tracking back from the abstraction that reaches the sink to find the propagation path to the source, the paths found are different each time the program is executed. The log looks as follows:
16:45:42.177 [main] INFO SetupApplication - Found 1 leaks from 5 sources.

My understanding is that these two logs have the following meanings:

The first log indicates how many sources and sinks were identified in the program (as mentioned above).
The second log indicates how many propagation paths exist from the defined source(s) to the defined sink(s).

Is my understanding correct?

[t1mlange]

Is my understanding correct?

Yep.

The final generated Set res is the same

This is not sufficient to tell whether the callgraph is the same. But if the callgraph had a bug, both lines would be unstable as FlowDroid only searches for sources and sinks in the reachable methods. That's why I've asked.

Another log line that might help you is

[main] INFO soot.jimple.infoflow.android.SetupApplication$InPlaceInfoflow - IFDS problem with F forward and B backward edges solved in S seconds, processing R results...

If F or B is different between runs, your main method changes or you found a non-determinism inside the data-flow analysis. If R changes between runs, you might have a problem with a buggy equals() that leads to loss of information in the hashmap or some other data race.

[litter47]

I run the same explame three times,and following are the key logs from each run.

18:19:21.449 [main] INFO auth.jarInflow.JarAuthInfoflow - IFDS problem with 91284 forward and 50792 backward edges solved in 1 seconds, processing 1 results...
18:19:22.727 [main] INFO SetupApplication - Found 1 leaks from 25 sources


18:20:52.068 [main] INFO auth.jarInflow.JarAuthInfoflow - Source lookup done, found 1 sources and 1 sinks.
18:20:53.878 [main] INFO auth.jarInflow.JarAuthInfoflow - IFDS problem with 91289 forward and 50792 backward edges solved in 2 seconds, processing 1 results...
18:20:55.081 [main] INFO SetupApplication - Found 1 leaks from 41 sources


18:22:20.684 [main] INFO auth.jarInflow.JarAuthInfoflow - Source lookup done, found 1 sources and 1 sinks.
18:22:22.612 [main] INFO auth.jarInflow.JarAuthInfoflow - IFDS problem with 91289 forward and 50792 backward edges solved in 2 seconds, processing 1 results...
18:22:23.881 [main] INFO SetupApplication - Found 1 leaks from 94 sources

Based on your guidance, I suspect that the reason for the differences in the results of the last line lies in the process of finding the paths.

[StevenArzt]

The concept is as follows. FlowDroid first identifies all source statements and injects taint abstractions there. These taints are then propagated through the interprocedural control flow graph using IFDS. During propagation, each new taint has a reference to its predecessor. That means, while every taint knows its predecessor, it does not know the source from which it came.

Once the IFDS phase has completed, we have a set of taints that have arrived at sink statements. The path reconstructor now traverses the taint graph backwards via the predecessor links to reconstruct a path that ends at a source. Starting at one sink, there may be many paths to many different sources. If the path reconstructor hits a timeout, it will stop.

If you don't need the paths and you're only interested in which source is connected to which sink, you can use the ContextInsensitiveSourceFinder as path reconstruction algorithm. It is much simpler (the code is only a handful of lines) and much more efficient - at the cost of not having paths along the way and not checking contexts in the taint graph.

Keep in mind that the IFDS phase is always context-sensitive. Ignoring contexts during path reconstruction only leads to a false positive if multiple flows overlap with different contexts in the same method. There are examples, but it doesn't mean that you have an overall context-insensitive analysis. It's still pretty good for many cases.