[Soot-list] ForwardBranchedFlowAnalysis gets stuck in endless loop

[Daniel Popescu]

Thanks Eric!

The flow analysis framework works correctly.

My analysis was incorrectly implementing the copy method. My copy
method was not creating a 1:1 copy of the source set. Instead, it was
merging all source elements into the destination set.

Daniel

On Sun, Aug 28, 2011 at 4:05 AM, Eric Bodden
<bodden at st.informatik.tu-darmstadt.de> wrote:
> Thanks for the detailed description, Daniel.
>
> Do you have a little test case that exposes the problem? That would
> help us checking if a possible patch really works.
>
> Also, I would like to make sure this is really a problem of the flow
> analysis framework and not a problem of some implementation of some
> concrete analysis abstraction.
>
> Best wishes,
> Eric
>
> On 28 August 2011 05:34, Daniel Popescu <dpopescu at usc.edu> wrote:
>> ForwardBranchedFlowAnalysis can get stuck in an endless loop because
>> ForwardBranchedFlowAnalysis does not correctly update the working list
>> changedUnits.
>>
>> The endless loop happens whenever ForwardBranchedFlowAnalysis analyzes
>> a method that contains a loop. Every time ForwardBranchedFlowAnalysis
>> has finished analyzing a unit, it compares the two sets afterFlow and
>> previousAfterFlow. The set afterFlow will contain the data values from
>> all previously analyzed units. However, the set previousAfterFlow will
>> only contain the data values from units that
>> ForwardBranchedFlowAnalysis analyzed more than once.
>>
>> The endless loop happens because ForwardBranchedFlowAnalysis only adds
>> the successors of a changed unit to the working list. Units that are
>> outside of the loop are not analyzed more than once.
>>
>> If we would also add the changed unit itself to the working list, the
>> analysis would not get stuck.
>>
>> Daniel
>> _______________________________________________
>> Soot-list mailing list
>> Soot-list at sable.mcgill.ca
>> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>>
>
>
>
> --
> Dr. Eric Bodden, http://bodden.de/
> Principal Investigator in Secure Services at CASED
> Coordinator of the CASED Advisory Board of Study Affairs
> PostDoc at Software Technology Group, Technische Universität Darmstadt
> Tel: +49 6151 16-5478    Fax: +49 6151 16-5410
> Mailing Address: S2|02 A209, Hochschulstraße 10, 64289 Darmstadt
>