From a2ab4426be3b40aea29384f6b6a562f2048ff004 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Thu, 17 Mar 2011 00:26:38 +0000 Subject: [PATCH] changes towards taints --- Robust/src/Analysis/Disjoint/Canonical.java | 27 +++++ Robust/src/Analysis/Disjoint/TaintSet.java | 4 + Robust/src/Analysis/Pointer/Edge.java | 10 ++ Robust/src/Analysis/Pointer/Pointer.java | 117 ++++++++++++++++++-- 4 files changed, 150 insertions(+), 8 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/Canonical.java b/Robust/src/Analysis/Disjoint/Canonical.java index 633b96e3..44377080 100644 --- a/Robust/src/Analysis/Disjoint/Canonical.java +++ b/Robust/src/Analysis/Disjoint/Canonical.java @@ -1480,6 +1480,33 @@ abstract public class Canonical { return out; } + public static TaintSet removeInContextTaintsNP( TaintSet ts, + FlatSESEEnterNode sese ) { + assert ts != null; + assert ts.isCanonical(); + assert sese != null; + + // NEVER a cached result... (cry) + TaintSet out = new TaintSet(); + + Iterator tItr = ts.iterator(); + while( tItr.hasNext() ) { + Taint t = tItr.next(); + + // what is allowed through? stall site taints always + // go through, anything where rblock doesn't match is + // unaffected, and if the taint has a non-empty predicate + // it is out of context so it should go through, too + if( t.getSESE() == null || + t.getSESE()!=sese) { + out.taints.add( t ); + } + } + + out = (TaintSet) makeCanonical( out ); + return out; + } + public static TaintSet removeStallSiteTaints( TaintSet ts ) { assert ts != null; assert ts.isCanonical(); diff --git a/Robust/src/Analysis/Disjoint/TaintSet.java b/Robust/src/Analysis/Disjoint/TaintSet.java index 7e632b18..697ae815 100644 --- a/Robust/src/Analysis/Disjoint/TaintSet.java +++ b/Robust/src/Analysis/Disjoint/TaintSet.java @@ -88,6 +88,10 @@ public class TaintSet extends Canonical { taints = new HashSet(); } + public Set getTaints() { + return taints; + } + public Iterator iterator() { return taints.iterator(); } diff --git a/Robust/src/Analysis/Pointer/Edge.java b/Robust/src/Analysis/Pointer/Edge.java index 94d50884..c13a7d5d 100644 --- a/Robust/src/Analysis/Pointer/Edge.java +++ b/Robust/src/Analysis/Pointer/Edge.java @@ -80,6 +80,16 @@ public class Edge { return newe; } + public TaintSet getTaints() { + return taints; + } + + public Edge changeTaintSet(TaintSet ts) { + Edge newe=copy(); + newe.taints=ts; + return newe; + } + public boolean equals(Object o) { if (o instanceof Edge) { Edge e=(Edge) o; diff --git a/Robust/src/Analysis/Pointer/Pointer.java b/Robust/src/Analysis/Pointer/Pointer.java index e704b51f..50b4974c 100644 --- a/Robust/src/Analysis/Pointer/Pointer.java +++ b/Robust/src/Analysis/Pointer/Pointer.java @@ -6,6 +6,8 @@ import Analysis.Liveness; import Analysis.Pointer.BasicBlock.BBlock; import Analysis.Pointer.AllocFactory.AllocNode; import Analysis.Disjoint.Taint; +import Analysis.Disjoint.TaintSet; +import Analysis.Disjoint.Canonical; import Analysis.CallGraph.CallGraph; import java.io.*; @@ -17,6 +19,7 @@ public class Pointer { HashMap> returnMap; HashMap> bblivetemps; + boolean OoOJava=false; CallGraph callGraph; State state; TypeUtil typeUtil; @@ -381,12 +384,14 @@ public class Pointer { case FKind.FlatSetFieldNode: case FKind.FlatSetElementNode: return processSetFieldElementNode(node, delta, newgraph); + case FKind.FlatSESEEnterNode: + return processSESEEnterNode((FlatSESEEnterNode) node, delta, newgraph); + case FKind.FlatSESEExitNode: + return processSESEExitNode((FlatSESEExitNode) node, delta, newgraph); case FKind.FlatMethod: case FKind.FlatExit: case FKind.FlatBackEdge: case FKind.FlatGenReachNode: - case FKind.FlatSESEEnterNode: - case FKind.FlatSESEExitNode: return processFlatNop(node, delta, newgraph); case FKind.FlatCall: return processFlatCall(bblock, index, (FlatCall) node, delta, newgraph); @@ -395,7 +400,9 @@ public class Pointer { } } - Delta processSESEEnter(FlatSESEEnterNode sese, Delta delta, Graph graph) { + Delta processSESEEnterNode(FlatSESEEnterNode sese, Delta delta, Graph graph) { + if (!OoOJava) + return processFlatNop(sese, delta, graph); if (delta.getInit()) { removeInitTaints(null, delta, graph); for (TempDescriptor tmp:sese.getInVarSet()) { @@ -428,24 +435,118 @@ public class Pointer { return callGraph.getCalleeSet(md).contains(md); } - - Delta processSESEExit(FlatSESEExitNode seseexit, Delta delta, Graph graph) { + Delta processSESEExitNode(FlatSESEExitNode seseexit, Delta delta, Graph graph) { + if (!OoOJava) + return processFlatNop(seseexit, delta, graph); FlatSESEEnterNode sese=seseexit.getFlatEnter(); //Strip Taints from this SESE if (delta.getInit()) { removeInitTaints(isRecursive(sese)?sese:null, delta, graph); } else { - removeDiffTaints(isRecursive(sese)?sese:null, delta, graph); + removeDiffTaints(isRecursive(sese)?sese:null, delta); } applyDiffs(graph, delta); return delta; } + + void removeDiffTaints(FlatSESEEnterNode sese, Delta delta) { + //Start with variable edges + { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + + //Process base diff edges + processEdgeMap(sese, delta.basevaredge, null, delta.varedgeremove, edgestoremove, edgestoadd); + //Process delta edges + processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e:edgestoremove) { + delta.removeVarEdge(e); + } + for(Edge e:edgestoadd) { + delta.addVarEdge(e); + } + } + + //Now do heap edges + { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + + //Process base diff edges + processEdgeMap(sese, delta.baseheapedge, null, delta.heapedgeremove, edgestoremove, edgestoadd); + //Process delta edges + processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e:edgestoremove) { + delta.removeHeapEdge(e); + } + for(Edge e:edgestoadd) { + delta.addHeapEdge(e); + } + } + } void removeInitTaints(FlatSESEEnterNode sese, Delta delta, Graph graph) { - + //Start with variable edges + { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + + //Process parent edges + processEdgeMap(sese, graph.parent.varMap, graph.varMap, delta.varedgeremove, edgestoremove, edgestoadd); + //Process graph edges + processEdgeMap(sese, graph.varMap, null, delta.varedgeremove, edgestoremove, edgestoadd); + //Process delta edges + processEdgeMap(sese, delta.varedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e:edgestoremove) { + delta.removeVarEdge(e); + } + for(Edge e:edgestoadd) { + delta.addVarEdge(e); + } + } + + //Now do heap edges + { + MySet edgestoadd=new MySet(); + MySet edgestoremove=new MySet(); + + //Process parent edges + processEdgeMap(sese, graph.parent.nodeMap, graph.nodeMap, delta.heapedgeremove, edgestoremove, edgestoadd); + //Process graph edges + processEdgeMap(sese, graph.nodeMap, null, delta.heapedgeremove, edgestoremove, edgestoadd); + //Process delta edges + processEdgeMap(sese, delta.heapedgeadd, null, null, edgestoremove, edgestoadd); + for(Edge e:edgestoremove) { + delta.removeHeapEdge(e); + } + for(Edge e:edgestoadd) { + delta.addHeapEdge(e); + } + } } - void processEdgeMap(FlatSESEEnterNode sese, Delta delta, Graph graph, HashMap> edgemap) { + void processEdgeMap(FlatSESEEnterNode sese, HashMap> edgemap, HashMap> childmap, HashMap> removemap, MySet edgestoremove, MySet edgestoadd) { + for(Map.Entry> entry:edgemap.entrySet()) { + //If the parent map exists and overrides this entry, skip it + if (childmap!=null&&childmap.containsKey(entry.getKey())) + continue; + for(Edge e:entry.getValue()) { + //check whether this edge has been removed + if (removemap==null&&removemap.containsKey(entry.getKey())&& + removemap.get(entry.getKey()).contains(e)) + continue; + //have real edge + TaintSet ts=e.getTaints(); + TaintSet newts=null; + //update non-null taint set + if (ts!=null) + newts=Canonical.removeInContextTaintsNP(ts, sese); + if (newts!=null) { + edgestoremove.add(e); + edgestoadd.add(e.changeTaintSet(newts)); + } + } + } } void removeDiffTaints(FlatSESEEnterNode sese, Delta delta, Graph graph) { -- 2.34.1