search

soot-oss / soot

Soot - A Java optimization framework
GNU Lesser General Public License v2.1
2.86k stars 705 forks source link

Data Races in Scene.getSootClassUnsafe() #1373

Open ingo-budde opened 4 years ago

ingo-budde commented 4 years ago

We identified three bugs that are probably caused by data races in the implementation of Scene.getSootClassUnsafe(). We are already experimenting with a potential solution and we will provide a merge request for that soon. Thanks to Marcus Hüwe (@marcus-h) for the problem analysis and detailed explanations below.

The method Scene.getSootClassUnsafe() already makes use of the synchronized keyword to guard against race conditions and also provides special logic for the dummy class SootClass.INVOKEDYNAMIC_DUMMY_CLASS_NAME, but the current implementation cannot completely prevent the three following edge cases:

Issue 1: For a given className, several SootClass instances are created

For this, assume two threads are calling Scene.getSootClassUnsafe(SootClass.INVOKEDYNAMIC_DUMMY_CLASS_NAME, true) and there exists no RefType named SootClass.INVOKEDYNAMIC_DUMMY_CLASS_NAME. In this case, it is possible that both threads end up executing the following code:

type = getOrAddRefType(className);
synchronized (type) {
  SootClass c = new SootClass(className);
  c.isPhantom = true;
  addClassSilent(c);
  c.setPhantomClass();
  return c;
}

Consequently, two SootClass instances are created where only one of them will be associated with RefType type afterwards. This could lead to potential issues. Note that the second addClassSilent() call does not result in a "duplicate class" RuntimeException because the SootClass(...) constructor (indirectly) calls RefType.setSootClass(this), which causes Scene.containsClass() to return false when called in Scene.addClassSilent().

Issue 2: "duplicate class: soot.dummy.InvokeDynamic" RuntimeException

For this, first create "several" class files that contain invokedynamic instructions.

marcus@linux:~/repro> cat gen_classes.sh 
#!/bin/bash
for i in $(seq 30); do
    cat > "Test$i.java" <<EOF
public class Test$i {
    public String run$i() {
        String x = "foo";
        String y = x + "Test$i";
        System.out.println(y);
        return y;
    }

    public static void main(String[] args) {
        new Test$i().run$i();
    }
}
EOF
    javac11 -d out "Test$i.java"
    rm "Test$i.java"
done
marcus@linux:~/repro> bash gen_classes.sh 
marcus@linux:~/repro>

Next, execute soot (and keep fingers crossed to see some "bad" interleaving;) )

marcus@linux:~/repro> java11 -cp /path/to/sootclasses-trunk-jar-with-dependencies.jar soot.Main -f J --process-dir out
Soot started on Tue Jun 23 10:53:59 CEST 2020
[Thread-7] ERROR heros.solver.CountingThreadPoolExecutor - Worker thread execution failed: Failed to convert <Test4: java.lang.String run4()>
java.lang.RuntimeException: Failed to convert <Test4: java.lang.String run4()>
    at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2163)
    at soot.SootMethod.retrieveActiveBody(SootMethod.java:402)
    at soot.PackManager$1.run(PackManager.java:1279)
    at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
    at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
    at java.base/java.lang.Thread.run(Thread.java:834)
Caused by: java.lang.RuntimeException: duplicate class: soot.dummy.InvokeDynamic
    at soot.Scene.addClassSilent(Scene.java:894)
    at soot.Scene.getSootClassUnsafe(Scene.java:1232)
    at soot.Scene.getSootClassUnsafe(Scene.java:1204)
    at soot.Scene.getSootClass(Scene.java:1243)
    at soot.asm.AsmMethodSource.convertInvokeDynamicInsn(AsmMethodSource.java:1466)
    at soot.asm.AsmMethodSource.convert(AsmMethodSource.java:1909)
    at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2161)
    ... 5 more
java.lang.RuntimeException: Failed to convert <Test4: java.lang.String run4()>
    at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2163)
    at soot.SootMethod.retrieveActiveBody(SootMethod.java:402)
    at soot.PackManager$1.run(PackManager.java:1279)
    at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
    at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
    at java.base/java.lang.Thread.run(Thread.java:834)
Caused by: java.lang.RuntimeException: duplicate class: soot.dummy.InvokeDynamic
    at soot.Scene.addClassSilent(Scene.java:894)
    at soot.Scene.getSootClassUnsafe(Scene.java:1232)
    at soot.Scene.getSootClassUnsafe(Scene.java:1204)
    at soot.Scene.getSootClass(Scene.java:1243)
    at soot.asm.AsmMethodSource.convertInvokeDynamicInsn(AsmMethodSource.java:1466)
    at soot.asm.AsmMethodSource.convert(AsmMethodSource.java:1909)
    at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2161)
    ... 5 more
Exception in thread "Thread-7" java.lang.RuntimeException: Failed to convert <Test4: java.lang.String run4()>
    at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2163)
    at soot.SootMethod.retrieveActiveBody(SootMethod.java:402)
    at soot.PackManager$1.run(PackManager.java:1279)
    at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
    at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
    at java.base/java.lang.Thread.run(Thread.java:834)
Caused by: java.lang.RuntimeException: duplicate class: soot.dummy.InvokeDynamic
    at soot.Scene.addClassSilent(Scene.java:894)
    at soot.Scene.getSootClassUnsafe(Scene.java:1232)
    at soot.Scene.getSootClassUnsafe(Scene.java:1204)
    at soot.Scene.getSootClass(Scene.java:1243)
    at soot.asm.AsmMethodSource.convertInvokeDynamicInsn(AsmMethodSource.java:1466)
    at soot.asm.AsmMethodSource.convert(AsmMethodSource.java:1909)
    at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2161)
    ... 5 more

For instance, this can occur if two threads (Thread-7 and Thread-1) call Scene.getSootClassUnsafe(SootClass.INVOKEDYNAMIC_DUMMY_CLASS_NAME, true) and interleave as follows:

Thread-7                                            Thread-1

...
type = getOrAddRefType(className);
synchronized (type) {
                                                    RefType type = nameToClass.get(className);
                                                    SootClass tsc = type.getSootClass();
                                                    -- SootResolver.v().makeClassRef(...)
  SootClass c = new SootClass(className);
  c.isPhantom = true;
                                                    ---- newClass = new SootClass(className);
                                                    ---- newClass.setResolvingLevel(SootClass.DANGLING);
                                                    ---- Scene.v().addClass(newClass);
                                                    ...
                                                    return tsc;
  addClassSilent(c);

When Thread-7 calls addClassSilent(c), the SootClass instance that was created by Thread-1 is associated with the RefType type and also part of the Scene (that is, Scene.containsClass() returns true). Hence, the "duplicate class: soot.dummy.InvokeDynamic" RuntimeException is thrown.

Issue 3: DANGLING resolving level during method resolution

For this, reuse the class files from Issue 2 and execute soot (again, keep fingers crossed to see a "bad" interleaving).

marcus@linux:~/repro> java11 -cp /path/to/sootclasses-trunk-jar-with-dependencies.jar soot.Main --validate -f J --process-dir out
Soot started on Tue Jun 23 13:35:04 CEST 2020
[Thread-10] ERROR heros.solver.CountingThreadPoolExecutor - Worker thread execution failed: This operation requires resolving level SIGNATURES but soot.dummy.InvokeDynamic is at resolving level DANGLING
If you are extending Soot, try to add the following call before calling soot.Main.main(..):
Scene.v().addBasicClass(soot.dummy.InvokeDynamic,SIGNATURES);
Otherwise, try whole-program mode (-w).
java.lang.RuntimeException: This operation requires resolving level SIGNATURES but soot.dummy.InvokeDynamic is at resolving level DANGLING
If you are extending Soot, try to add the following call before calling soot.Main.main(..):
Scene.v().addBasicClass(soot.dummy.InvokeDynamic,SIGNATURES);
Otherwise, try whole-program mode (-w).
    at soot.SootClass.checkLevelIgnoreResolving(SootClass.java:198)
    at soot.SootClass.checkLevel(SootClass.java:180)
    at soot.SootClass.getMethodUnsafe(SootClass.java:561)
    at soot.SootMethodRefImpl.tryResolve(SootMethodRefImpl.java:210)
    at soot.SootMethodRefImpl.resolve(SootMethodRefImpl.java:263)
    at soot.SootMethodRefImpl.resolve(SootMethodRefImpl.java:183)
    at soot.jimple.internal.AbstractInvokeExpr.getMethod(AbstractInvokeExpr.java:56)
    at soot.jimple.validation.InvokeArgumentValidator.validate(InvokeArgumentValidator.java:54)
    at soot.jimple.JimpleBody.validate(JimpleBody.java:118)
    at soot.jimple.JimpleBody.validate(JimpleBody.java:98)
    at soot.PackManager.runBodyPacks(PackManager.java:1007)
    at soot.PackManager.lambda$runBodyPacks$0(PackManager.java:660)
    at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
    at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
    at java.base/java.lang.Thread.run(Thread.java:834)
java.lang.RuntimeException: This operation requires resolving level SIGNATURES but soot.dummy.InvokeDynamic is at resolving level DANGLING
If you are extending Soot, try to add the following call before calling soot.Main.main(..):
Scene.v().addBasicClass(soot.dummy.InvokeDynamic,SIGNATURES);
Otherwise, try whole-program mode (-w).
    at soot.SootClass.checkLevelIgnoreResolving(SootClass.java:198)
    at soot.SootClass.checkLevel(SootClass.java:180)
    at soot.SootClass.getMethodUnsafe(SootClass.java:561)
    at soot.SootMethodRefImpl.tryResolve(SootMethodRefImpl.java:210)
    at soot.SootMethodRefImpl.resolve(SootMethodRefImpl.java:263)
    at soot.SootMethodRefImpl.resolve(SootMethodRefImpl.java:183)
    at soot.jimple.internal.AbstractInvokeExpr.getMethod(AbstractInvokeExpr.java:56)
    at soot.jimple.validation.InvokeArgumentValidator.validate(InvokeArgumentValidator.java:54)
    at soot.jimple.JimpleBody.validate(JimpleBody.java:118)
    at soot.jimple.JimpleBody.validate(JimpleBody.java:98)
    at soot.PackManager.runBodyPacks(PackManager.java:1007)
    at soot.PackManager.lambda$runBodyPacks$0(PackManager.java:660)
    at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
    at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
    at java.base/java.lang.Thread.run(Thread.java:834)
Exception in thread "Thread-10" java.lang.RuntimeException: This operation requires resolving level SIGNATURES but soot.dummy.InvokeDynamic is at resolving level DANGLING
If you are extending Soot, try to add the following call before calling soot.Main.main(..):
Scene.v().addBasicClass(soot.dummy.InvokeDynamic,SIGNATURES);
Otherwise, try whole-program mode (-w).
    at soot.SootClass.checkLevelIgnoreResolving(SootClass.java:198)
    at soot.SootClass.checkLevel(SootClass.java:180)
    at soot.SootClass.getMethodUnsafe(SootClass.java:561)
    at soot.SootMethodRefImpl.tryResolve(SootMethodRefImpl.java:210)
    at soot.SootMethodRefImpl.resolve(SootMethodRefImpl.java:263)
    at soot.SootMethodRefImpl.resolve(SootMethodRefImpl.java:183)
    at soot.jimple.internal.AbstractInvokeExpr.getMethod(AbstractInvokeExpr.java:56)
    at soot.jimple.validation.InvokeArgumentValidator.validate(InvokeArgumentValidator.java:54)
    at soot.jimple.JimpleBody.validate(JimpleBody.java:118)
    at soot.jimple.JimpleBody.validate(JimpleBody.java:98)
    at soot.PackManager.runBodyPacks(PackManager.java:1007)
    at soot.PackManager.lambda$runBodyPacks$0(PackManager.java:660)
    at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
    at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
    at java.base/java.lang.Thread.run(Thread.java:834)

Note: the --validate option is needed in order to trigger the method resolution.

As in Issue 2, this is, again, due to some bad interleaving of (at least) two threads that call Scene.getSootClassUnsafe(SootClass.INVOKEDYNAMIC_DUMMY_CLASS_NAME, true), which is indirectly called from soot.asm.AsmMethodSource.convertInvokeDynamicInsn(), which is indirectly called from PackManager.retrieveAllBodies.

Thread-7                                            Thread-1

...
type = getOrAddRefType(className);
synchronized (type) {
                                                    RefType type = nameToClass.get(className);
                                                    SootClass tsc = type.getSootClass();
                                                    -- SootResolver.v().makeClassRef(...)
  SootClass c = new SootClass(className);
  c.isPhantom = true;
  addClassSilent(c);
  c.setPhantomClass();
  return c;
}
                                                    ---- newClass = new SootClass(className);
                                                    ---- newClass.setResolvingLevel(SootClass.DANGLING);
                                                    ---- Scene.v().addClass(newClass);
                                                    ...
                                                    return tsc;

That is, in soot.asm.AsmMethodSource.convertInvokeDynamicInsn() a new SootMethodRef(Impl) is constructed where the declaring class has a DANGLING resolving level. Hence, the RuntimeException is thrown when resolving this SootMethodRefImpl instance (in Thread-10).

marcus-h commented 4 years ago

On 2020-06-24 05:57:06 -0700, Ingo Budde wrote:

The method Scene.getSootClassUnsafe() already makes use of the synchronized keyword to guard against race conditions and also provides special logic for the dummy class SootClass.INVOKEDYNAMIC_DUMMY_CLASS_NAME, but the current implementation cannot completely prevent the three following edge cases:

Just for the record: we also have a potential fix [1] [2], which we are currently testing/evaluating:)

[1] https://github.com/fraunhofer-iem/soot-umbrella/commit/a0552d59e05438b30ccc73b3f33822edd7f23eb2 [2] https://github.com/fraunhofer-iem/soot-umbrella/tree/bugfix/fix_data_race_in_getSootClassUnsafe

mbenz89 commented 4 years ago

Thanks for the in-depth report. Any updates on this issue?

marcus-h commented 4 years ago

On 2020-07-15 02:31:35 -0700, Manuel Benz wrote:

Thanks for the in-depth report. Any updates on this issue?

Unfortunately, our "internal" testing got delayed a bit... (in fact, it just started a few hours ago:/ )

Are you "blocked" on this issue? (If so, you can give the referenced patch (see my previous reply) a try.)

I'll try to push this a bit so that we can file a PR ASAP. Sorry for the delay...

yijunwu commented 4 years ago

I also encountered the same problem. With the same application code, most of the time soot succeeds, but sometimes it throws "duplicate class: soot.dummy.InvokeDynamic" error, so it does look like a race condition error. Error msg as blow. Looking forward to the fix. 

java.lang.RuntimeException: Failed to convert <com.alibaba.intl.nyse.gateway.driver.pp.rule.refund.AbstractRefundRequestRule: void lambda$buildRefundRequest$3(java.util.Map,com.alibaba.intl.nyse.gateway.driver.pp.rule.refund.InstrumentRefundBuildRequest,com.taobao.payment.facade.req.v2.RefundRequest,java.util.concurrent.atomic.AtomicReference,com.alibaba.intl.nyse.ability.refund.model.extra.FullRefundInstrument)>
at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2062)
at soot.SootMethod.retrieveActiveBody(SootMethod.java:402)
at soot.PackManager$1.run(PackManager.java:1279)
at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
at java.lang.Thread.run(Thread.java:745)
Caused by: java.lang.RuntimeException: duplicate class: soot.dummy.InvokeDynamic
at soot.Scene.addClassSilent(Scene.java:822)
at soot.Scene.addClass(Scene.java:803)
at soot.SootResolver.makeClassRef(SootResolver.java:128)
at soot.RefType.getSootClass(RefType.java:118)
at soot.Scene.getSootClassUnsafe(Scene.java:1153)
at soot.Scene.getSootClassUnsafe(Scene.java:1136)
at soot.Scene.getSootClass(Scene.java:1177)
at soot.asm.AsmMethodSource.convertInvokeDynamicInsn(AsmMethodSource.java:1406)
at soot.asm.AsmMethodSource.convert(AsmMethodSource.java:1813)
at soot.asm.AsmMethodSource.getBody(AsmMethodSource.java:2060)
... 5 more
mbenz89 commented 4 years ago

Are you "blocked" on this issue? (If so, you can give the referenced patch (see my previous reply) a try.)

We are also victim to this bug. I'm not blocked by it, however. I just wanted to check-in if you are making progress with a fix.

I'll try to push this a bit so that we can file a PR ASAP. Sorry for the delay...

It's not an issue, thanks for investigating the problem!

marcus-h commented 4 years ago

On 2020-07-17 02:40:39 -0700, Manuel Benz wrote:

I'll try to push this a bit so that we can file a PR ASAP. Sorry for the delay...

It's not an issue, thanks for investigating the problem!

I just created PR#1390.