[Soot-list] Missing call graph edges
Peter Kim
chpkim at gmail.com
Mon Feb 9 16:38:01 EST 2015
Hi Sam,
Yes, I changed the code, re-ran Soot, and Soot still doesn't report the
edges.
Hi Steve,
Note that when I change "free()" to a static method, the edge is reported,
but when it is an instance method, it is not reported. In light of the
discussion with Sam, I want to make it absolutely clear that the code runs
fine even when it is an instance method, so in my view, it seems to be a
bug or perhaps Infoflow is constructing a call graph that is different from
the traditional call graph, but since you told me that you changed it back
to return a traditional call graph, I think it deserves an investigation.
Thanks.
On Mon, Feb 9, 2015 at 9:31 PM, Sam Blackshear <
samuel.blackshear at colorado.edu> wrote:
> Call graph construction is typically flow-insensitive, so it is not
> precise enough to do the kind of reasoning you are doing in your head (i.e.
> For "objects.remove()" to be included in the call graph, "obj" cannot be
> null). If you are not familiar with the flow-insensitive call graph
> construction algorithms used by tools like Soot, this
> <http://manu.sridharan.net/files/aliasAnalysisChapter.pdf> is a good
> place to start.
>
> Now, if you changed the code in that way that you described (adding one or
> more objects to the objects list), re-ran Soot, and Soot still does not
> report the edges, that is a problem for Soot (and thus goes beyond my
> expertise :)). But for the example program you posted, Soot's result is as
> expected for a flow-insensitive call graph construction algorithm.
>
> - Sam
>
> On Mon, Feb 9, 2015 at 2:22 PM, Peter Kim <chpkim at gmail.com> wrote:
>
>> Hi Sam,
>>
>> The code snippet is the following:
>>
>> BaseTweet<?> obj = objects.get(i);
>> if (obj.isFinished() && obj.isAutoRemoveEnabled) {
>> objects.remove(i);
>> obj.free();
>> }
>>
>> For "objects.remove()" to be included in the call graph, "obj" cannot be
>> null. So even without any object in the list, if "objects.remove()" is
>> included, then "obj.free()" should be included as well.
>>
>> Just to be absolutely sure though, I just ran the app with one object in
>> the list and made sure that the true branch is executed. Soot still returns
>> only "remove()" in the call graph. I also made sure that "free()" prints
>> output (meaning it shouldn't be excluded from the call graph).
>>
>>
>> On Mon, Feb 9, 2015 at 9:08 PM, Sam Blackshear <
>> samuel.blackshear at colorado.edu> wrote:
>>
>>> Peter,
>>> What you observe is consistent with what I explained. The
>>> objects.remove() method is included because objects is initialized to a
>>> non-null ArrayList. However, obj.free() is not included because the
>>> analysis is smart enough to determine that there is no possible concrete
>>> execution in which the method obj.free() will be called (the statement
>>> obj.free() will throw an exception *if* it ever executes, because obj will
>>> always be null).
>>>
>>> - Sam
>>>
>>> On Mon, Feb 9, 2015 at 1:54 PM, Peter Kim <chpkim at gmail.com> wrote:
>>>
>>>> Hi Sam,
>>>>
>>>> The loop iteration is executed only if there is an item in the list, so
>>>> it shouldn't matter if no object has been added to the list. The code runs
>>>> without exception. The problem is that of two call graph edges that are
>>>> part of the same basic block (remove() and free()), only one call graph
>>>> edge (remove()) is being returned, which is strange.
>>>>
>>>> On Mon, Feb 9, 2015 at 8:19 PM, Sam Blackshear <
>>>> samuel.blackshear at colorado.edu> wrote:
>>>>
>>>>> Hi Peter,
>>>>> My suspicion is that the callgraph is correct here. You never add
>>>>> anything the the objects ArrayList, so whenever you try to read a BaseTweet
>>>>> object out of the list, the analysis (correctly) concludes that only null
>>>>> could be returned. If you call a method on null (like isFinished), the call
>>>>> graph (correctly) concludes that this would result in an NPE and thus does
>>>>> not add the edge. If you want to see these edges in the callgraph, extend
>>>>> your code to add something to the objects ArrayList:
>>>>>
>>>>> objects.add(new BaseTweet())
>>>>>
>>>>> When debugging your static analysis results, it's often helpful to
>>>>> concretely execute your target program and be sure that it behaves as you
>>>>> expect!
>>>>>
>>>>> - Sam
>>>>>
>>>>>
>>>>> On Mon, Feb 9, 2015 at 12:40 PM, Peter Kim <chpkim at gmail.com> wrote:
>>>>>
>>>>>> Hi Steven,
>>>>>>
>>>>>> Here is a complete minimal example as an Eclipse project (just import
>>>>>> into your workspace):
>>>>>> https://drive.google.com/file/d/0B9KLXcAovVUHa0FuN3gzRGJETmc/view
>>>>>>
>>>>>> I retrieve the CFG of this app at Infoflow.runAnalysis(final
>>>>>> ISourceSinkManager sourcesSinks, final Set<String> additionalSeeds),
>>>>>> calling "CallGraph cg = Scene.v().getCallGraph();" right before "iCfg =
>>>>>> icfgFactory.buildBiDirICFG(callgraphAlgorithm);". I use cg, not iCfg.
>>>>>>
>>>>>> The edges out of
>>>>>> com.example.toyandroid.ChpkimMainActivity.chpkimUpdate() I get are:
>>>>>>
>>>>>> <java.util.ArrayList: int size()>
>>>>>> <java.util.ArrayList: java.lang.Object get(int)>
>>>>>> <java.util.ArrayList: java.lang.Object remove(int)>
>>>>>>
>>>>>> But they should be:
>>>>>>
>>>>>> <java.util.ArrayList: int size()>
>>>>>> <java.util.ArrayList: java.lang.Object get(int)>
>>>>>> <java.util.ArrayList: java.lang.Object remove(int)>
>>>>>> <com.example.toyandroid.BaseTweet: boolean isFinished()>
>>>>>> <com.example.toyandroid.BaseTweet: void free()>
>>>>>> <com.example.toyandroid.BaseTweet: void update(float)>
>>>>>>
>>>>>> Thanks for your help.
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Mon, Feb 9, 2015 at 8:40 AM, Steven Arzt <Steven.Arzt at cased.de>
>>>>>> wrote:
>>>>>>
>>>>>>> Hi Peter,
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Can you please send me a more complete minimal example with which I
>>>>>>> can reproduce the issue?
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Best regards,
>>>>>>>
>>>>>>> Steven
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> *Von:* soot-list-bounces at CS.McGill.CA [mailto:
>>>>>>> soot-list-bounces at CS.McGill.CA] *Im Auftrag von *Peter Kim
>>>>>>> *Gesendet:* Sonntag, 8. Februar 2015 19:05
>>>>>>> *An:* Steven Arzt
>>>>>>> *Cc:* soot-list at cs.mcgill.ca
>>>>>>> *Betreff:* Re: [Soot-list] Missing call graph edges
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> eliminateDeadCode() is *not* being called and I'm still running into
>>>>>>> the problem. Thanks in advance for your help.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Sun, Feb 8, 2015 at 5:37 PM, Peter Kim <chpkim at gmail.com> wrote:
>>>>>>>
>>>>>>> Hi Steven,
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> I'm still running into the same problem after pulling from Github.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Fri, Feb 6, 2015 at 9:24 AM, Steven Arzt <Steven.Arzt at cased.de>
>>>>>>> wrote:
>>>>>>>
>>>>>>> Hi Peter,
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> that might have to do with an optimization I added recently. In
>>>>>>> short, FlowDroid removes these callgraph edges for which it can easily
>>>>>>> decide that having them does not influence the outcome of the taint
>>>>>>> analysis. I can however fully understand that this might lead to surprising
>>>>>>> results if you are using the FlowDroid components for other analyses, so I
>>>>>>> decided to make this optimization optional and turn it off by default.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> The new code is on Github and a new nightly build will be available
>>>>>>> tomorrow.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Best regards,
>>>>>>>
>>>>>>> Steven
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> M.Sc. M.Sc. Steven Arzt
>>>>>>>
>>>>>>> Secure Software Engineering Group (SSE)
>>>>>>>
>>>>>>> European Center for Security and Privacy by Design (EC SPRIDE)
>>>>>>>
>>>>>>> Rheinstraße 75
>>>>>>>
>>>>>>> D-64293 Darmstadt
>>>>>>>
>>>>>>> Phone: +49 61 51 869-336
>>>>>>>
>>>>>>> Fax: +49 61 51 16-72118
>>>>>>>
>>>>>>> eMail: steven.arzt at ec-spride.de
>>>>>>>
>>>>>>> Web: http://sse.ec-spride.de
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> *Von:* soot-list-bounces at CS.McGill.CA [mailto:
>>>>>>> soot-list-bounces at CS.McGill.CA] *Im Auftrag von *Peter Kim
>>>>>>> *Gesendet:* Freitag, 6. Februar 2015 00:05
>>>>>>> *An:* soot-list at cs.mcgill.ca
>>>>>>> *Betreff:* [Soot-list] Missing call graph edges
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> I'm extending FlowDroid to construct an Android app's call graph.
>>>>>>> More specifically, I get the call graph by modifying
>>>>>>> Infoflow.runAnalysis(final ISourceSinkManager sourcesSinks, final
>>>>>>> Set<String> additionalSeeds) to call Scene.v().getCallGraph(). The call
>>>>>>> graph is missing edges in an odd way - for a function, the graph has some
>>>>>>> outgoing edges but is missing ones that should be there. Namely, given the
>>>>>>> following function (shown in Java rather than jimple for readability), the
>>>>>>> called methods should be "get()", "isFinished()", "remove()", "free()",
>>>>>>> "size()", "update()", but I'm only getting "get()", "size()", and
>>>>>>> "remove()". I don't understand why "remove()" is included but "free()" is
>>>>>>> not since they are in the same basic block. I'm
>>>>>>> using soot.jimple.toolkits.callgraph.TransitiveTargets to analyze the call
>>>>>>> graph.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> public void update(float x) {
>>>>>>>
>>>>>>> for (...size()..) {
>>>>>>>
>>>>>>> get();
>>>>>>>
>>>>>>> if (isFinished()) {
>>>>>>>
>>>>>>> remove();
>>>>>>>
>>>>>>> free();
>>>>>>>
>>>>>>> }
>>>>>>>
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> if (y) {
>>>>>>>
>>>>>>> if (x) {
>>>>>>>
>>>>>>> for (... size()...) get().update(x);
>>>>>>>
>>>>>>> } else {
>>>>>>>
>>>>>>> for (...size()...) get().update(x);
>>>>>>>
>>>>>>> }
>>>>>>>
>>>>>>> }
>>>>>>>
>>>>>>> }
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Thank you for your help.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> Soot-list mailing list
>>>>>> Soot-list at CS.McGill.CA
>>>>>> https://mailman.CS.McGill.CA/mailman/listinfo/soot-list
>>>>>>
>>>>>>
>>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://mailman.CS.McGill.CA/pipermail/soot-list/attachments/20150209/667dc3fa/attachment-0001.html
More information about the Soot-list
mailing list