Parallel IFDS solver (maxThreadNum=-1) intermittently misses a flow that maxThreadNum=1 always finds

[yuan2li]

Describe the bug
InfoflowConfiguration.maxThreadNum defaults to -1, i.e., one IFDS solver worker per available processor. On the attached input, that default misses a real data flow in most runs but not all, while setMaxThreadNum(1) finds it in every run. The program is straight-line and single-threaded, so this is not about analysing concurrency; only the solver's own parallelism varies.

Executing the program confirms the tainted value does reach the sink, so the parallel result is a false negative rather than a difference of opinion.

No third-party libraries or tools are involved. The analysis is plain-Java mode via Infoflow.computeInfoflow, with no taint wrapper, no access-path settings, and no code-elimination override — everything except maxThreadNum is FlowDroid's stock configuration. The input depends on nothing but the JDK.

Input file
Attached: flowdroid-maxthreadnum-repro.zip — classes/ (the compiled input, JDK 8 bytecode) plus Repro.java and Drv.java for reference.

Repro.java, the whole input:

public class Repro {

    static final class Cell { volatile String v; }

    /** source */
    static String source() {
        // An explicit allocation rather than a literal: SPARK does not model
        // string constants as allocation sites, which would leave the value
        // with an empty points-to set for reasons unrelated to this report.
        return new String(new char[]{'s', 'e', 'e', 'd'});
    }

    public void handle() throws java.io.IOException {
        String data = source();
        final Cell c1 = new Cell();
        final String in1 = data;
        Runnable r1 = new Runnable() { public void run() { c1.v = in1; } };
        try { r1.run(); } catch (Exception e) { throw new IllegalStateException(e); }
        String s1 = c1.v;
        final Cell c2 = new Cell();
        final String in2 = s1;
        Runnable r2 = new Runnable() { public void run() { c2.v = in2; } };
        try { r2.run(); } catch (Exception e) { throw new IllegalStateException(e); }
        String s2 = c2.v;
        final Cell c3 = new Cell();
        final String in3 = s2;
        Runnable r3 = new Runnable() { public void run() { c3.v = in3; } };
        try { r3.run(); } catch (Exception e) { throw new IllegalStateException(e); }
        String s3 = c3.v;
        final Cell c4 = new Cell();
        final String in4 = s3;
        Runnable r4 = new Runnable() { public void run() { c4.v = in4; } };
        try { r4.run(); } catch (Exception e) { throw new IllegalStateException(e); }
        String s4 = c4.v;
        final Cell c5 = new Cell();
        final String in5 = s4;
        Runnable r5 = new Runnable() { public void run() { c5.v = in5; } };
        try { r5.run(); } catch (Exception e) { throw new IllegalStateException(e); }
        String s5 = c5.v;
        Runtime.getRuntime().exec(s5); // sink
    }

    public static void main(String[] a) throws Exception {
        new Repro().handle();
    }
}

Five sequential hops, each storing into a fresh holder object through an anonymous Runnable that is invoked directly. No threads are created. Shorter versions of the same shape (one to four hops) are found under every setting; only the five-hop version separates them.

To reproduce
FlowDroid ships no plain-Java CLI, so the runner is the second attached file. It sets maxThreadNum and nothing else:

import java.util.Collections;
import soot.jimple.infoflow.Infoflow;
import soot.jimple.infoflow.InfoflowConfiguration;
import soot.jimple.infoflow.results.InfoflowResults;

public class Drv {
    public static void main(String[] args) throws Exception {
        String appPath = args[0], libPath = args[1];
        int threads = Integer.parseInt(args[2]);

        Infoflow flow = new Infoflow();
        InfoflowConfiguration cfg = flow.getConfig();
        if (threads > 0) cfg.setMaxThreadNum(threads);   // the only setting

        flow.computeInfoflow(appPath, libPath,
            "<Repro: void main(java.lang.String[])>",
            Collections.singletonList("<Repro: java.lang.String source()>"),
            Collections.singletonList(
                "<java.lang.Runtime: java.lang.Process exec(java.lang.String)>"));

        InfoflowResults r = flow.getResults();
        System.out.println("RESULT "
                + (r != null && !r.isEmpty() ? "FOUND" : "MISS"));
    }
}

unzip flowdroid-maxthreadnum-repro.zip          # gives classes/, Repro.java, Drv.java
javac -cp "$FLOWDROID_CP" -d drv Drv.java       # JDK 11+

LIB="$JDK8_HOME/jre/lib/rt.jar:$JDK8_HOME/jre/lib/jce.jar"

# pinned to one worker -- prints FOUND every time
java -cp "drv:$FLOWDROID_CP" Drv ./classes "$LIB" 1

# shipped default (-1) -- prints MISS most of the time; repeat it
java -cp "drv:$FLOWDROID_CP" Drv ./classes "$LIB" 0

The last argument is maxThreadNum; 0 means "leave the default". Because the effect is intermittent, please run the second command several times — a single run can land on either answer.

Expected behavior
The flow exists and is confirmed by executing the program, so we expect RESULT FOUND. Two weaker expectations are also violated:

1. the same version, on the same input, in the same configuration, should give the same answer across runs; and
2. the shipped default should not be less complete than a pinned single thread.

Stacktrace
None — nothing throws, and the analysis terminates normally. InfoflowResults.getTerminationState() reports no aborts on any run, whether
the flow was found or not, so this is not a swallowed timeout or OOM.

Version information

• FlowDroid soot-infoflow 2.15.1 (Maven Central), plain-Java mode
• Analysis runs on JDK 21; the input is JDK 8 bytecode, with a JDK 8 rt.jar/jce.jar as the library path
• Reproduced on macOS/arm64 (8 cores) and Linux/x86-64

Additional context
Setting maxThreadNum explicitly, 10 runs per setting, on macOS/arm64 with 8 cores, stock configuration otherwise:

maxThreadNum	flow found
1	10/10
2	4/10
3	2/10
4	1/10
8	4/10
default (-1)	0/10

Two things stand out. One worker is the only setting that answers consistently. And two workers are already enough to lose the flow — the effect does not need many cores, and the miss rate does not fall off smoothly as workers are added, which is what one would expect if the outcome depends on worklist interleaving rather than on the amount of parallelism.

The generated program this file was reduced from behaves the same way. It was also checked on Linux/x86-64 in containers limited to 8 and 64 effective CPUs (the JVM reported the intended Effective CPU Count): three runs each, six in total, all missing this flow while the pinned single-thread run found it. Those six agreed with each other across a larger generated corpus, but at a miss rate this high, six agreeing runs are not by themselves evidence of determinism — the intermittency above is the sharper observation. Over that corpus, the parallel and single-threaded configurations differ on exactly one program: this one.
What we were able to rule out:

• Not a timeout or OOM — see Stacktrace above; the analysis takes about three seconds against a default budget.
• Not machine load — twelve runs on an idle machine and twelve with all cores saturated gave statistically indistinguishable flip rates.
• Not the host OS or instruction set — macOS/arm64 and Linux/x86-64 both show it.
• Not the analysed program — it creates no threads and has no concurrency of its own.
• Not the configuration — the runner above touches one setting.

This may also be the root cause of #164, which reports inconsistent results across runs without identifying a mechanism. Workaround for anyone hitting that issue: config.setMaxThreadNum(1).