[Soot-list] Missing call graph edges
Peter Kim
chpkim at gmail.com
Mon Feb 9 16:22:18 EST 2015
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/65be02fd/attachment-0001.html
More information about the Soot-list
mailing list