[Soot-list] patch to make HashMutablePDG not loop forever for figure 5 from cytron's SSA construction paper.
Eric Bodden
eric.bodden at ec-spride.de
Thu Apr 5 15:34:26 EDT 2012
Thanks Phil.
Could you please re-send the patch as an attachments and preferably as
a "unified diff"? I am getting problems with applying the patch due to
line breaks in the email...
Eric
On 4 April 2012 22:45, Phil Pratt-Szeliga <pcpratts at syr.edu> wrote:
> Hello,
>
> Here is a patch to make HashMutablePDG not loop forever for figure 5
> from cytron's SSA construction paper. I also made a public getter for
> m_blockCFG because I need that.
>
> My test case that caused the bug behavior is:
>
> //////////////////////////////////////////////////////////////////////
> // CytronFigure5.java
> //////////////////////////////////////////////////////////////////////
>
> package edu.syr.pcpratts.symarray.test;
>
> public class CytronFigure5 {
>
> public void figure5(boolean p, boolean q, boolean r, boolean s, boolean t){
> int i = 1;
> int j = 1;
> int k = 1;
> int l = 1;
> do {
> if(p){
> j = i;
> if(q){
> l = 2;
> } else {
> l = 3;
> }
> ++k;
> } else {
> k += 2;
> }
> System.out.println("i: "+i+" j: "+j+" k: "+k+" l: "+l);
> do {
> if(r){
> l += 4;
> }
> } while(s == false);
> i += 6;
> } while(t == false);
> }
> }
>
> ////////////////////////////////////////////////////////////
> // The patch
> ////////////////////////////////////////////////////////////
>
> diff --git a/src/soot/toolkits/graph/pdg/HashMutablePDG.java
> b/src/soot/toolkits/graph/pdg/HashMutablePDG.java
> --- a/src/soot/toolkits/graph/pdg/HashMutablePDG.java
> +++ b/src/soot/toolkits/graph/pdg/HashMutablePDG.java
> @@ -26,6 +26,8 @@
> import java.util.LinkedList;
> import java.util.List;
> import java.util.Queue;
> +import java.util.Set;
> +import java.util.HashSet;
>
> import soot.Body;
> import soot.SootClass;
> @@ -36,6 +38,7 @@
> import soot.toolkits.graph.HashMutableEdgeLabelledDirectedGraph;
> import soot.toolkits.graph.UnitGraph;
> import soot.toolkits.graph.pdg.IRegion;
> +import soot.toolkits.graph.DirectedGraph;
>
>
> /**
> @@ -91,7 +94,6 @@
> protected List<PDGRegion> m_pdgRegions = null;
> private RegionAnalysis m_regionAnalysis = null;
> private int m_strongRegionStartID;
> -
>
> public HashMutablePDG(UnitGraph cfg)
> {
> @@ -126,6 +128,10 @@
> this.m_startNode.setNode(r);
>
> }
> +
> + public BlockGraph getBlockGraph(){
> + return m_blockCFG;
> + }
>
> /**
> * This is the heart of the PDG contruction. It is huge and definitely needs
> @@ -153,12 +159,14 @@
> this.m_startNode = pdgnode;
> topLevelRegion.setParent(null);
>
> + Set<Region> processedRegions = new HashSet<Region>();
> regions2process.add(topLevelRegion);
>
> //while there's a (weak) region to process
> while(!regions2process.isEmpty())
> {
> Region r = regions2process.remove(0);
> + processedRegions.add(r);
>
> //get the corresponding pdgnode
> pdgnode = this.m_obj2pdgNode.get(r);
> @@ -276,7 +284,9 @@
> //add the dependency edges
> this.addEdge(pdgNodeOfA, pdgnodeOfBRegion, "dependency");
> pdgNodeOfA.addDependent(pdgnodeOfBRegion);
> - regions2process.add(regionOfB);
> + if(!processedRegions.contains(regionOfB)){
> + regions2process.add(regionOfB);
> + }
> //now remove b and all the nodes in the same weak region from
> the list of dependents
> copyOfDependents.remove(b);
> copyOfDependents.removeAll(regionOfB.getBlocks());
> @@ -326,7 +336,9 @@
> //add the dependency edges
> this.addEdge(pdgnodeOfBRegion, pdgnodeOfdepBRegion, "dependency");
> pdgnodeOfBRegion.addDependent(pdgnodeOfdepBRegion);
> - regions2process.add(rdepB);
> + if(!processedRegions.contains(rdepB)){
> + regions2process.add(rdepB);
> + }
>
> //now remove all the nodes in the same weak region from the
> list of dependents
>
> @@ -371,7 +383,9 @@
>
> this.addEdge(pdgnodeOfBRegion, pdgnodeOfdepBRegion, "dependency");
> pdgnodeOfBRegion.addDependent(pdgnodeOfdepBRegion);
> - regions2process.add(rdepB);
> + if(!processedRegions.contains(rdepB)){
> + regions2process.add(rdepB);
> + }
>
> //now remove all the nodes in the same weak region from the
> list of dependents
>
> @@ -686,8 +700,11 @@
>
> private static PDGRegion pdgpostorder(PDGNode node, List<PDGRegion> list)
> {
> + if(node.getVisited()){
> + return null;
> + }
> node.setVisited(true);
> -
> +
> PDGRegion region = null;
> if(!node2Region.containsKey(node))
> {
> @@ -696,8 +713,7 @@
> }
> else
> region = node2Region.get(node);
> -
> -
> +
> //If there are children, push the children to the stack
> List<PDGNode> dependents = node.getDependets();
> if(!dependents.isEmpty())
> @@ -713,12 +729,13 @@
> {
> PDGNode body = ((LoopedPDGNode)curNode).getBody();
> PDGRegion kid = pdgpostorder(body, list);
> - kid.setParent(region);
> - region.addChildRegion(kid);
> + if(kid != null){
> + kid.setParent(region);
> + region.addChildRegion(kid);
>
> - //This sets the node from the old Region into a PDGRegion
> - body.setNode(kid);
> -
> + //This sets the node from the old Region into a PDGRegion
> + body.setNode(kid);
> + }
> }
> else if(curNode instanceof ConditionalPDGNode)
> {
> @@ -728,12 +745,13 @@
> {
> PDGNode child = (PDGNode)condItr.next();
> PDGRegion kid = pdgpostorder(child, list);
> - kid.setParent(region);
> - region.addChildRegion(kid);
> - //This sets the node from the old Region into a PDGRegion
> + if(kid != null){
> + kid.setParent(region);
> + region.addChildRegion(kid);
> + //This sets the node from the old Region into a PDGRegion
>
> - child.setNode(kid);
> -
> + child.setNode(kid);
> + }
> }
>
> }
>
> diff --git a/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
> b/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
> --- a/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
> +++ b/src/soot/toolkits/graph/pdg/ProgramDependenceGraph.java
> @@ -22,6 +22,7 @@
> import java.util.List;
>
> import soot.toolkits.graph.MutableEdgeLabelledDirectedGraph;
> +import soot.toolkits.graph.BlockGraph;
>
>
> /**
> @@ -60,6 +61,8 @@
> * @return The root region of the PDG.
> */
> public IRegion GetStartRegion();
> +
> + public BlockGraph getBlockGraph();
>
> /**
> * @return The root node of the PDG, which is essentially the same
> as the start region
>
>
>
> Phil Pratt-Szeliga
> Syracuse University
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
--
Eric Bodden, Ph.D., http://bodden.de/
Head of Secure Software Engineering Group at EC SPRIDE
Principal Investigator in Secure Services at CASED
Tel: +49 6151 16-75422 Fax: +49 6151 16-72051
Room 3.2.14, Mornewegstr. 30, 64293 Darmstadt
More information about the Soot-list
mailing list