[Soot-list] Callgraph generation with Paddle

[François GOICHON]

Hello,

After getting a bit deeper into Paddle, I am still encountering some 
problems. Raising the maximum heap memory to 2gigs solved partially the 
problems I had as I am now able to compute a 1-object-sensitive callgraph.
Even then, running a points-to analysis (with on-the-fly callgraph 
generation or independently) with whatever propagator segfaults. It is 
the same for 2-object-sensitive callgraph generation or 
1-object-sensitive callgraph generation with heap variables abstraction. 
When I try Paddle without BDDs with object-sensitivity enabled I get a 
Not Yet Implemented runtime error.

However, I am not quite sure whether this really indicates an 
out-of-memory error. For example, when trying to perform a 
1-object-sensitive points-to analysis after callgraph generation, the 
problematic frame is bdd_makenode+0x75 inside libjeddbuddy and the CR2 
register is at 0x28442810, which is between two allocated heap segments:

2317b000-27dc7000 rwxp 00000000 00:00 0
28b00000-28c00000 rwxp 00000000 00:00 0


While generating a 2-object-sensitive callgraph, the bug happens at 
bdd_makenode+0x58 and CR2 is at 0xd73ff030, which is within kernel 
memory and is unlikely to be a normal value from userland...

I am really unfamiliar with Jedd and BuDDy implementations, but couldn't 
these be some simple memory handling bugs ?

As using older JDKs is not really an option for me (I don't control the 
end-user's execution environment), do you think I am getting short of 
possibilities there ?

I am also having a hard time understanding contexts representation 
within Paddle. For example, while iterating over the object-sensitive 
callgraph, I obtain such edges:

[*] Edge from <AnyObject: void method(AnyObject,int)>
        In Context: GlobalAllocNode 17 Any_subtype_of_AnyObject in null
    To node: <AnyObject: AnotherObject getObj()>
        In Context: GlobalAllocNode 17 Any_subtype_of_AnyObject in null


[*] Edge from <AnyObject: void method(AnyObject,int)
        In Context: GlobalAllocNode 17 Any_subtype_of_AnyObject in null
    To node: <AnyObject: AnotherObject getObj()>
        In Context: GlobalAllocNode 17 Any_subtype_of_AnyObject in null


Which correspond to the following code:

class AnyObject {
    private AnotherObject att = new AnotherObject();

    public AnotherObject getObj() {
        return this.att;
    }

    void method(AnyObject Untrusted, int i) {
        AnotherObject localUntrusted = untrusted.getObj();
        AnotherObject localTrusted = this.getObj();
       [...]
    }
}

As I understand it, for an object-sensitive analysis, the context 
attached to these methods should be the allocation site of the receiver 
objects, which are not allocated at the same line, so why are these 
contexts similar ?

Thank you very much and sorry for all these questions..

François


François GOICHON wrote:
> Hello,
>
> Thank you very much for these two rapid answers. I will try this out 
> and add more memory.
> I'll let you know if I encounter more problems.
> Thanks again,
>
> François
>
> Patrick Lam wrote:
>> On 22/04/10 10:14 AM, François GOICHON wrote:
>>  
>>> Because of the apparent simplicity of this application, I am astonished
>>> that there are roughly 2150 classes loaded in the Soot Scene, 
>>> doesn't it
>>> seem a lot ? Anyway, I start the analysis, which takes some minutes and
>>> terminates with a segfault inside libjeddbuddy (during pt.solve()),
>>> because I am running out of memory I suppose. I provided -Xmx512m
>>> -Xss256m as vm arguments.
>>> So my questions are:
>>>   - is it possible not to load all this classes, most of them being
>>> certainly loaded from unrealizable paths for my application (I actually
>>> tried not to use the full resolver option but then I add to add 
>>> hundreds
>>> of addBasicClass(..., SIGNATURE|BODIES) and it was giving the same
>>> result anyway) ? Or to let Paddle dynamically load the needed classes
>>> when it encounters them ?
>>> - do I really need more memory for such a small program ??
>>>   - is there an easier way to build a context-sensitive callgraph with
>>> paddle (I am actually not sure what is going on within
>>> PaddleScene.solve()) ?
>>> I tried some different solutions from different existing applications
>>> using paddle without success.. I am quite lost and any hint or remark
>>> would be of great help for me.
>>>     
>>
>> As Eric said, it's better to use a SceneTransformer. But you'll still 
>> have many, many classes due to the Java library; using older JDKs 
>> will make your life better. And you'll probably need to provide more 
>> than 512 megs.
>>
>> Ondrej may have more comments here.
>>
>> pat
>>   
>
>