1

Closed

Infinite Loops and Out of Memory Exceptions

description

Hello,

I'm having problems running SEAL on quite a few different programs. In particular, I'm having two main problems.

First is an infinite loop that seems to be occurring in quite a few DLLs. The loop is happening in HigherOrderHeapGraphBuilder.ComposeResolvableSkippedCalls inside the do/while. The output indicates this loop is never making progress, as it continues to print the same iteration number, vertex count, and edge count.

Second is an out of memory exception that happens quite frequently. It usually occurs in the constructor of HeapGraph.

Can I fix these issues? Are there any configuration values I need to change? I'm fine with an incomplete analysis, as long as it is conservative (never labels a non-pure method pure) and it terminates.

I can provide more details as needed, including the DLLs I'm using if required.

Any help is appreciated,

thanks!

file attachments

Closed Feb 11, 2014 at 2:21 PM by Ravi87

comments

kapilv wrote Jan 13, 2014 at 8:40 PM

Can we request you to send the DLLs that are causing problems?

ThanksKapil

fmc3 wrote Jan 14, 2014 at 3:40 AM

Thanks for the quick reply.

So it seems like the problems I'm running into are related to a change I made in SEAL in order to create a conservative analysis (I posted about this in the discussion section). The only functional change I've made is to SummaryTemplates.GetUnanalyzableCallSummary, which I changed to this:

public static PurityAnalysisData GetUnanalyzableCallSummary(string methodname, string containingType){ var data = SummaryTemplates.CreatePureData(); var field = NamedField.New(Guid.NewGuid().ToString(), Guid.NewGuid().ToString()); SummaryTemplates.WriteGlobalObject(data,field); return data;}

Which was basically the recommendation made by Ravi in the discussion thread. My understanding of what this does is it marks all unanalyzable calls impure by indicating they write to some global static field. However, this change is causing the problems I described above, because when I'm running the problematic DLL's on a clean copy of SEAL, I'm not having the problems.

To recep: I want unanalyzable calls to be considered impure. The change I made to SummaryTemplates.GetUnanalyzableCallSummary is wrong and is causing non-termination.

How can I fix this?

I've attached a dll I'm having issues with.

Ravi87 wrote Jan 15, 2014 at 2:42 PM

As you may be aware, Seal performs an iterative fix-point analysis to compute side-effects. In each iteration on encountering a method call seal looks up its summary and uses it to compute the abstract state after the call. It is important that the summary of a call remains exactly the same (even syntactically) across the iterations of the fix-point analysis for seal to terminate. The above code that you have been using for unanalyzable calls creates a distinct summary in each iteration for the same call statement because of the use of Guids. It is always safes to depend only on the method and typename to create a summary for a method. For instance, the following code can used to accomplish your task.

var data = SummaryTemplates.CreatePureData(); var field = NamedField.New(containingType+"::"+methodname, String.Empty); SummaryTemplates.WriteGlobalObject(data, field); return data;

With the above code, every call to a method say "System::BinarySearch" in a procedure A for which there exists no summary will result in an effect "System::BinarySearch" in the summary of A. With this modification Seal terminates on core.dll in 11 min (with default config.) on my system.

I did notice that some of the unanalyzable calls in your application (core.dll) belonged to the core C# libraries (mscorlib, system, system.core). These weren't analyzable by the tool because we haven't written any stubs for them. If you require more precise results then you could try writing stubs manually for these unanalyzable methods. The easiest way to do that is to hard code the summaries like done in the above code. For more details look at the "SyntheticMethodStub" class.

Thanks,Ravi

Ravi87 wrote Jan 18, 2014 at 10:43 AM

I would like to add one more point regarding you comment: "The loop is happening in HigherOrderHeapGraphBuilder.ComposeResolvableSkippedCalls inside the do/while. The output indicates this loop is never making progress, as it continues to print the same iteration number, vertex count, and edge count."

The vertices/edges in the heap graph are only a part of the abstract state. The abstract state (defined in PurityAnalysisData) has other components such as read sets, write sets etc. In your case, the edges and vertices stabilised after some iterations but the "write set" did not because you were creating new writes to new fields (using Guids) in each itreation. Since, the write sets were not printed it might have seemed as if the loop is stuck.

I would like to close this issue if you do not have any follow up questions ?

Ravi

fmc3 wrote Jan 18, 2014 at 10:24 PM

Thank you for the detailed response - I appreciate it. The code you provided does indeed fix the halting issue.

I do have a follow up question though - I'm still getting out of memory exceptions on a few DLLs without any functional changes to SEAL. I've attached a DLL I'm having issues with. There are other DLLs where I'm also hitting an out of memory exception. I'll attach them in another comment because this only allows me to add 1 file.

fmc3 wrote Jan 18, 2014 at 10:25 PM

Another DLL causing out of memory exception.

Ravi87 wrote Jan 19, 2014 at 8:49 AM

Amazon web services DLL (AWSSDK.dll) is a massive application. Seal shows that it has nearly 40K methods and I would suspect that it has close to a million lines of code. Lucene is also huge (about 8k methods) but seems manageable by Seal. I have listed below a few strategies for making Seal scale to these applications. But unfortunately, there is no guarantee that seal may succeed. If you manage to get Seal working on these please do let us know, that would be a great result.

Some hacks for making Seal (in its present form) scale to large applications:

a) Patch "checker.exe" to use 4G of virtual memory:

Unfortunately, Seal is a 32bit application as it depends on Phoenix which is 32bit. So by default it can use only 2GB of memory. However, you can make it use 4GB by using this patch: http://www.ntcore.com/4gb_patch.php. Apply this patch on the "checker.exe" executable before running the tool. But this is the limit and cannot be pushed any further. We will consider porting seal to a better front end in the future.

b) Try splitting the application in to multiple DLLs if possible:

At present, Seal stores the data (such as method summaries, type informations etc.) of the DLL being analysed completely in memory. However, the information about previously analysed DLLs are serialised to the disk. So Seal has a good chance of scaling better on a bunch of DLLs of the same size compared to a single monolithic DLL. See https://seal.codeplex.com/wikipage?title=Inputs%20to%20Seal for information on analysing multiple DLLs together.

c) Set context-bound to 0 and flow-sensitivity to false in the config file:This will make seal imprecise but is the last resort.

While all of these can address the memory issue, there is also the time factor. If seal takes too long then there is very little we can do about it, at present. However, there is feature called "analysable-list" which is a hack to make seal analyse only some portion of a DLL, we use this to skips many parts of mscorlib. I will give you more information on how to use this if the above strategies fail.

fmc3 wrote Jan 19, 2014 at 7:43 PM

Thanks again for the thorough response. I may try the 4gb patch but will just skip running those libraries if it still fails (hopefully lucene will work).

You should consider posting this information on the documentation tab - I'm sure it could be useful to others who may also run into this issue.

I think that is it for this issue. Feel free to close it!

Thanks for you time.