A wrong call graph but pointsTo analysis result is correct

[RichardHoOoOo]

Hi @StevenArzt , I found FlowDroid manifest a weird bug on this specific app (apk). It turns out the pointsTo analysis is correct but the call graph is not correct.

I simplify the inheritance hierarchy that is related to the bug as follows. CycleStreets extends MainNavDrawerActivity, whose method onNewVersion is then overridden by CycleStreets.

class CycleStreets extends MainNavDrawerActivity {
     protected void onCreate() {
         super.onCreate();
     }

     protected void onNewVersion() {...}
}

abstract class MainNavDrawerActivity {
     protected void onCreate() {
         onNewVersion();
     }

     protected void onNewVersion() {...}
}

Then I print the call graph, the expected result should be

MainNavDrawerActivity: onCreate() ==> CycleStreets: onNewVersion()

However, the actual output is

MainNavDrawerActivity: onCreate() ==> MainNavDrawerActivity: onNewVersion()

I also locate the callsite of onNewVersion() and see the pointTo results of the base local (i.e., r0 at virtualinvoke r0.<net.cyclestreets.MainNavDrawerActivity: void onNewVersion()>()). I found the only possible types of r0 is CycleStreets, which means the pointsTo result is correct. In this case, why the call graph is not correct?

BTW, I also make my own app to simulate this inheritance structure and it looks the call graph is correct. So the bug can only be reproduced on that specific app. Could you take a look at this issue? Thanks in advance!

[RichardHoOoOo]

Hi @StevenArzt , it looks I can reproduce this issue on other apps. Is it because when the pointsTo result on the base of an instance invocation is pretty much similar (or exactly the same) to a CHA result, soot will drop all edges at this call site? Such a design does have benefits (e.g., reduce FPs) but this is just my guess.

[StevenArzt]

We don't have an explicit optimiaztion to drop edges. FlowDroid, in its default configuration, completely relies on SPARK for application code. The taint wrapper uses the declared callee to find the appropriate summary, but that's not relevant for app code, as there is no summary definition for app code.

I'm not sure why the callgraph is wrong. SPARK builds the CG on top of the propagated points-to information, i.e., the output of SPARK is a combination of points-to and CG. I'd suggest to look at points-to and CG after each round of callgraph construction, since we run the callback analysis (and thus CG/points-to analysis) iteratively. If it's broken right from the start, that might be a bug in SPARK. If it gets broken later one, it might be a weird issue with how we run the iterative CG/points-to combination based on SPARK.

I'm afraid I don't have the time at the moment to debug into this on my own.

[RichardHoOoOo]

Hi @StevenArzt , thanks for your reply. I follow your advice and it seems the bug might be in SPARK. I print the pointsTo result and the call graph in each round. It turns out the pointsTo result is Any_subtype_of_... in the 1st round but it becomes the correct result in all subsequent rounds. However, the call graph keeps missing the edge in all rounds.

[StevenArzt]

This raises two questions. Firstly, why do we get Any_subtype_of_... in the first round?

Secondly, why is the callgraph not updated? That is strange as well. The CG after the first round should point to both methods given that pointsTo is any-subtype. With this debugging result, I would rather expect an FP than a FN.

Even if we don't get any edge in the first round (for whatever reason), the second round should fix it. We get a new points-to set, hence the CG should be called again (recall that SPARK calls back and forth between points-to analysis and CG until a fixpoint is reached) and the edge to CycleStreets should be added.

[RichardHoOoOo]

Hi @StevenArzt , I found the root cause. The bug is caused by modifiers.

It turns out if I change protected to public on the onNewVersion declared in the parent class, the call graph will be correct.

class CycleStreets extends MainNavDrawerActivity {
     protected void onCreate() {
         super.onCreate();
     }

     protected void onNewVersion() {...}.  <======= Change protected to public
}

abstract class MainNavDrawerActivity {
     protected void onCreate() {
         onNewVersion();
     }

     protected void onNewVersion() {...}
}

I guess it is because CycleStreets.onCreate() is invoked by the dummy main, which is not under the same package of CycleStreets

Maybe we can put the dummy main of a component into the same package of that component, rather than just put all dummy mains in dummyMainClass? What do you think?

[StevenArzt]

I'm slightly confused. The dummy main method should only call onCreate, which in turn calls onNewVersion. Therefore, access rules shouldn't even be checked between the dummy main method and onNewVersion. So I don't really understand how your proposed fix solves the problem. It shouldn't matter in which package the dummy main method is, because it doesn't call onNewVersion.

If the call from MainNavDrawerActivity.onCreate to CycleStreets.onNewVersion is resolved incorrectly because of access flags, that would be a more generic problem with the access rule checking in Soot. I wonder why this doesn't affect many more cases in which protected methods of abstract parent classes are overridden in child classes. It would definitely be worthwhile to debug into Soot's access rule checker here.

[RichardHoOoOo]

Hi @StevenArzt , I have narrowed down the issue. It seems the problem lies in resolveConcreteDispatch()

When I set onNewVersion to be public and then call Scene.v().getOrMakeFastHierarchy().resolveConcreteDispatch(Scene.v().getSootClass("...CycleStreets"), Scene.v().getMethod("<...MainNavDrawerActivity: ... onNewVersion()>")), the output is the onNewVersion in CycleStreets.

If I set onNewVersion to be protected, the output is the onNewVersion in MainNavDrawerActivity.

[RichardHoOoOo]

Hi @StevenArzt , it turns out this may be a stupid bug...

It is caused at two call cites on isVisible in FastHierarchy

Line 865: if (isVisible(declaringClass, concreteType, candidate.getModifiers())) {
Line 900: if (method != null && isVisible(declaringClass, iFace, method.getModifiers())) {

The declaration of isVisible is

private boolean isVisible(SootClass from, SootClass declaringClass, int modifier) {

Obviously, the 1st parameter should be the class to check and the 2nd parameter should be the class declaring the method got from an invoke expression. But when isVisible is invoked, arguments are passed in at wrong places. For example, declaringClass should be passed to the 2nd parameter, but it is actually passed to the 1st parameter.

So after switching 1st and 2nd arguments like this

Line 865: if (isVisible(concreteType, declaringClass, candidate.getModifiers())) {
Line 900: if (method != null && isVisible(iFace, declaringClass, method.getModifiers())) {

The result call graph is correct.

Could you check if my investigation is correct? One thing I don't understand is why this commit introduce this "bug"?

[StevenArzt]

That commit was apparently part of the effort to add support for default methods in interfaces. We should check that the fix doesn't introduce problems with default methods. I'd rather assume oversight than an intended change, though.

[RichardHoOoOo]

Hold on @StevenArzt , it looks the fix proposed by me introduces other issues.

For example

public class ActivityA extends ActivityB {
       ...  // no onCreate() in ActivityA
}

public abstract class ActivityB extends Activity {
      protected void onCreate() {...}
}

Although I can see virtualinvoke $r0.<ActivityB: void onCreate(android.os.Bundle)>(null); ($r0's type is ActivityA) generated in the dummy main of ActivityA, I cannot found dummyMainMethod_ActivityA(android.content.Intent) ==> <ActivityB: void onCreate(android.os.Bundle)> in the call graph.

The call graph is correct if I do not apply the fix.

I am confused about this because when I call Scene.v().getOrMakeFastHierarchy().resolveConcreteDispatch(Scene.v().getSootClass("ActivityA"), Scene.v().getMethod("<ActivityB: void onCreate(android.os.Bundle)>")) independently after applying the fix, the return is correct.

[RichardHoOoOo]

Close as fixed in Soot