Boomerang crashes when summaries are enabled

[dseekatz]

Hi,

I am using Boomerang 3.0.10 and trying to run the provided examples, but with call summaries enabled. The only change I have made to the examples is that I have replaced

          // 1. Create a Boomerang solver.
          Boomerang solver =
              new Boomerang(
                  sootCallGraph, SootDataFlowScope.make(Scene.v()), new DefaultBoomerangOptions());

with the following code:

        // 1. Create a Boomerang solver.
        Boomerang solver =
            new Boomerang(
                sootCallGraph,
                SootDataFlowScope.make(Scene.v()),
                new DefaultBoomerangOptions() {
                  @Override
                  public boolean callSummaries() {
                    return true;
                  }
                });

Running ExampleMain1 produces the following output:

<boomerang.example.BoomerangExampleTarget1: void <init>()>
<boomerang.example.BoomerangExampleTarget1: void main(java.lang.String[])>
<boomerang.example.BoomerangExampleTarget1: void staticCallOnFile(boomerang.example.BoomerangExampleTarget1$ClassWithField,boomerang.example.BoomerangExampleTarget1$NestedClassWithField)>
<boomerang.example.BoomerangExampleTarget1: void queryFor(boomerang.example.BoomerangExampleTarget1$ObjectOfInterest)>
Solving query: BackwardQuery: (queryVariable (boomerang.example.BoomerangExampleTarget1.<boomerang.example.BoomerangExampleTarget1: void staticCallOnFile(boomerang.example.BoomerangExampleTarget1$ClassWithField,boomerang.example.BoomerangExampleTarget1$NestedClassWithField)>),RS: queryFor(queryVariable))
Boomerang CRASHEDjava.lang.NullPointerException
All allocation sites of the query variable are:
{}
All aliasing access path of the query variable are:
[]

The null pointer exception occurs when Boomerang tries to retrieve a summary automaton during post*, but no summaries have been created yet at this point. I can also provide the whole stack trace if it helps, but it is quite long.

Is there some additional way that I need to configure Boomerang before I can use summaries?

Thanks,
David

[copumpkin]

Just FYI, it looks like this repository has zero watchers, which I think means that nobody will be notified of tickets in here, and it didn't have an issue tracker until a few days ago. @johspaeth in case you missed this

[johspaeth]

Thanks. @copumpkin I indeed did not receive notification so far. I am watching this repository now.

In short:

Unfortunately, sharing summaries between different queries is not supported yet. At this stage, you cannot use summaries.
Note: Weighted Pushdown Systems, as IFDS, internally still do compute summaries, but sharing them between different queries is not possible as of aliasing, which would lead to indeterministic results.

Long explanation & example:

Let's take the following code, in which you find a sensitive data-flow from //source2 to //sink2, but not from //source1 to //sink1.

public static void main(...){
    A a = new A();
    A b = new A();
    String taint = source(); //source1
    foo(a, b, taint); //context1
    sink(b.mayBeTaintedField); //sink1

    A c = new A();
    A d = c;
    String taint = source(); //source2
    foo(c, d, taint); //context2
    sink(d.mayBeTaintedField); //sink2
}

foo(A x, B y, String taintedValue){
    x.mayBeTaintedField = taintedValue
}

Let's look at the computation of the summaries.

The summary for foo(...) under //context1 (before the mapping of the arguments at the call sites) has to like

s1: taintedValue flows to {x.mayBeTaintedField}

whereas the summary for foo(...) under //context2 (before the mapping of the arguments at the call sites) has to look like

s2: taintedValue flows to {x.mayBeTaintedField, y.mayBeTaintedField}

because x and y, respectively c and d are aliased under //context2.

Now, depending on whether s1 or s2 are computed first, the data-flow results differ.

If s1 were to be computed first, the analysis misses the taint flow from //source2 to //sink2 because the summary misses the aliasing of d = c within the calling context.

If s2 were to be computed first, the analysis imprecisely reports a taint flow form //source1 to //sink1.

Conceptually, one needs to take aliasing into account at the time the summaries are applied. This is something that Boomerang does not yet support. Hence, one needs to instantiate one solver per query.

[dseekatz]

Thanks @copumpkin for pinging @johspaeth, and thanks @johspaeth for the excellent detailed explanation.

Conceptually, one needs to take aliasing into account at the time the summaries are applied. This is something that Boomerang does not yet support.

I assume it would be very tricky to implement this efficiently for a demand-driven analysis framework like Boomerang?

[johspaeth]

I assume it would be very tricky to implement this efficiently for a demand-driven analysis framework like Boomerang?

I have some concepts and ideas for summarization that need to be implemented. But certainly not an easy task.