From c75aa3a57ead9a9ec83d0146eabf9ca3b2204107 Mon Sep 17 00:00:00 2001 From: jjenista Date: Sat, 26 Jun 2010 21:36:37 +0000 Subject: [PATCH] Do effects as a global space, don't even need to consider call site transform, taints propagate interprocedurally and pick everything up, whoo hoo --- .../Analysis/Disjoint/DisjointAnalysis.java | 51 +--- Robust/src/Analysis/Disjoint/EffectSet.java | 37 --- .../Analysis/Disjoint/EffectsAnalysis.java | 263 +++++------------- Robust/src/Analysis/Disjoint/ReachGraph.java | 18 +- Robust/src/Tests/disjoint/taintTest1/makefile | 4 +- 5 files changed, 79 insertions(+), 294 deletions(-) delete mode 100644 Robust/src/Analysis/Disjoint/EffectSet.java diff --git a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java index 21c80a58..5f02861f 100644 --- a/Robust/src/Analysis/Disjoint/DisjointAnalysis.java +++ b/Robust/src/Analysis/Disjoint/DisjointAnalysis.java @@ -674,7 +674,7 @@ public class DisjointAnalysis { } if( doEffectsAnalysis ) { - effectsAnalysis.writeEffectsPerMethodAndRBlock( "effects.txt" ); + effectsAnalysis.writeEffects( "effects.txt" ); } } @@ -1087,12 +1087,7 @@ public class DisjointAnalysis { rg.assignTempXEqualToTempYFieldF( lhs, rhs, fld ); if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - FlatSESEEnterNode seseContaining = - rblockRel.getRBlockStacks( fmContaining, fn ).peek(); - - effectsAnalysis.analyzeFlatFieldNode( fmContaining, - seseContaining, - rg, rhs, fld ); + effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fld ); } } break; @@ -1107,12 +1102,7 @@ public class DisjointAnalysis { boolean strongUpdate = rg.assignTempXFieldFEqualToTempY( lhs, fld, rhs ); if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - FlatSESEEnterNode seseContaining = - rblockRel.getRBlockStacks( fmContaining, fn ).peek(); - - effectsAnalysis.analyzeFlatSetFieldNode( fmContaining, - seseContaining, - rg, lhs, fld, strongUpdate ); + effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fld, strongUpdate ); } } break; @@ -1132,12 +1122,7 @@ public class DisjointAnalysis { rg.assignTempXEqualToTempYFieldF( lhs, rhs, fdElement ); if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - FlatSESEEnterNode seseContaining = - rblockRel.getRBlockStacks( fmContaining, fn ).peek(); - - effectsAnalysis.analyzeFlatFieldNode( fmContaining, - seseContaining, - rg, rhs, fdElement ); + effectsAnalysis.analyzeFlatFieldNode( rg, rhs, fdElement ); } } break; @@ -1163,12 +1148,7 @@ public class DisjointAnalysis { rg.assignTempXFieldFEqualToTempY( lhs, fdElement, rhs ); if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - FlatSESEEnterNode seseContaining = - rblockRel.getRBlockStacks( fmContaining, fn ).peek(); - - effectsAnalysis.analyzeFlatSetFieldNode( fmContaining, - seseContaining, - rg, lhs, fdElement, + effectsAnalysis.analyzeFlatSetFieldNode( rg, lhs, fdElement, false ); } } @@ -1339,32 +1319,13 @@ public class DisjointAnalysis { } else { - // calculate the method call transform - - Hashtable tCallee2tsCaller = null; - - if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - tCallee2tsCaller = new Hashtable(); - } - + // calculate the method call transform rgCopy.resolveMethodCall( fc, fmPossible, rgEffect, callerNodeIDsCopiedToCallee, - tCallee2tsCaller, writeDebugDOTs ); - - if( doEffectsAnalysis && fmContaining != fmAnalysisEntry ) { - - FlatSESEEnterNode seseContaining = - rblockRel.getRBlockStacks( fmContaining, fn ).peek(); - - effectsAnalysis.analyzeFlatCall( fmContaining, - seseContaining, - fmPossible, - tCallee2tsCaller ); - } } rgMergeOfEffects.merge( rgCopy ); diff --git a/Robust/src/Analysis/Disjoint/EffectSet.java b/Robust/src/Analysis/Disjoint/EffectSet.java deleted file mode 100644 index 12d12089..00000000 --- a/Robust/src/Analysis/Disjoint/EffectSet.java +++ /dev/null @@ -1,37 +0,0 @@ -package Analysis.Disjoint; - -import java.util.HashSet; -import java.util.Hashtable; -import java.util.Set; -import java.util.Iterator; -import IR.Flat.TempDescriptor; - -public class EffectSet { - - private Hashtable> taint2effects; - - public EffectSet() { - taint2effects = new Hashtable>(); - } - - public void addEffect(Taint t, Effect e) { - HashSet effectSet = taint2effects.get(t); - if (effectSet == null) { - effectSet = new HashSet(); - } - effectSet.add(e); - taint2effects.put(t, effectSet); - } - - public Set getEffects(Taint t) { - return taint2effects.get(t); - } - - public Iterator getAllEffectPairs() { - return taint2effects.entrySet().iterator(); - } - - public String toString() { - return taint2effects.toString(); - } -} diff --git a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java index cf9eaf38..9603b22e 100644 --- a/Robust/src/Analysis/Disjoint/EffectsAnalysis.java +++ b/Robust/src/Analysis/Disjoint/EffectsAnalysis.java @@ -27,164 +27,117 @@ import IR.Flat.FlatSESEEnterNode; public class EffectsAnalysis { - private Hashtable fm2effectSet; - private Hashtable sese2effectSet; + // the effects analysis should combine taints + // that match except for predicates--preds just + // support interprocedural analysis + private Hashtable> taint2effects; public EffectsAnalysis() { - fm2effectSet = new Hashtable(); - sese2effectSet = new Hashtable(); + taint2effects = new Hashtable>(); } - public void analyzeFlatFieldNode(FlatMethod fmContaining, - FlatSESEEnterNode seseContaining, - ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld) { - VariableNode vn = rg.td2vn.get(rhs); - if( vn == null ) { + public Set getEffects(Taint t) { + Taint tNoPreds = Canonical.changePredsTo( t, + ReachGraph.predsEmpty + ); + return taint2effects.get(tNoPreds); + } + + public Iterator iteratorTaintEffectPairs() { + return taint2effects.entrySet().iterator(); + } + + + protected void add(Taint t, Effect e) { + if( t.getSESE().getIsCallerSESEplaceholder() ) { return; } - for (Iterator iterator = vn.iteratorToReferencees(); iterator.hasNext();) { - RefEdge edge = iterator.next(); - TaintSet taintSet = edge.getTaints(); - AllocSite affectedAlloc = edge.getDst().getAllocSite(); - for (Iterator taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) { - Taint taint = taintSetIter.next(); - - EffectSet effectSet = fm2effectSet.get(fmContaining); - if (effectSet == null) { - effectSet = new EffectSet(); - } - - Effect effect = new Effect(affectedAlloc, Effect.read, fld); + Taint tNoPreds = Canonical.changePredsTo( t, + ReachGraph.predsEmpty + ); - add( fmContaining, taint, effect ); - add( seseContaining, taint, effect ); - } + Set effectSet = taint2effects.get(tNoPreds); + if (effectSet == null) { + effectSet = new HashSet(); } + effectSet.add(e); + taint2effects.put(tNoPreds, effectSet); } - public void analyzeFlatSetFieldNode(FlatMethod fmContaining, - FlatSESEEnterNode seseContaining, - ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, boolean strongUpdate) { - VariableNode vn = rg.td2vn.get(lhs); + public void analyzeFlatFieldNode(ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld) { + + VariableNode vn = rg.td2vn.get(rhs); if( vn == null ) { return; } for (Iterator iterator = vn.iteratorToReferencees(); iterator.hasNext();) { - RefEdge edge = iterator.next(); - TaintSet taintSet = edge.getTaints(); + RefEdge edge = iterator.next(); + TaintSet taintSet = edge.getTaints(); AllocSite affectedAlloc = edge.getDst().getAllocSite(); + Effect effect = new Effect(affectedAlloc, Effect.read, fld); + for (Iterator taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) { - Taint taint = taintSetIter.next(); - - Effect effect = new Effect(affectedAlloc, Effect.write, fld); - add( fmContaining, taint, effect ); - add( seseContaining, taint, effect ); - - if (strongUpdate) { - Effect effectSU = new Effect(affectedAlloc, Effect.strongupdate, fld); - add( fmContaining, taint, effect ); - add( seseContaining, taint, effect ); - } + Taint taint = taintSetIter.next(); + add(taint, effect); } } } - public void analyzeFlatCall(FlatMethod fmContaining, FlatSESEEnterNode seseContaining, - FlatMethod fmCallee, Hashtable tCallee2tsCaller) { - - EffectSet esCallee = getEffectSet(fmCallee); - if( esCallee == null ) { - esCallee = new EffectSet(); - } + public void analyzeFlatSetFieldNode(ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, boolean strongUpdate) { - Iterator meItr = esCallee.getAllEffectPairs(); - while( meItr.hasNext() ) { - Map.Entry me = (Map.Entry) meItr.next(); - Taint tCallee = (Taint) me.getKey(); - HashSet effects = (HashSet) me.getValue(); + VariableNode vn = rg.td2vn.get(lhs); + if( vn == null ) { + return; + } - if( tCallee2tsCaller.containsKey( tCallee ) ) { + for (Iterator iterator = vn.iteratorToReferencees(); iterator.hasNext();) { + RefEdge edge = iterator.next(); + TaintSet taintSet = edge.getTaints(); + AllocSite affectedAlloc = edge.getDst().getAllocSite(); + Effect effect = new Effect(affectedAlloc, Effect.write, fld); + Effect effectSU = null; - Iterator tItr = tCallee2tsCaller.get( tCallee ).iterator(); - while( tItr.hasNext() ) { - Taint tCaller = tItr.next(); - - EffectSet esCaller = new EffectSet(); + if (strongUpdate) { + effectSU = new Effect(affectedAlloc, Effect.strongupdate, fld); + } - Iterator eItr = effects.iterator(); - while( eItr.hasNext() ) { - Effect e = eItr.next(); - - esCaller.addEffect( tCaller, e ); - } + for (Iterator taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) { + Taint taint = taintSetIter.next(); + add( taint, effect ); - add( fmContaining, tCaller, esCaller ); - add( seseContaining, tCaller, esCaller ); + if (strongUpdate) { + add( taint, effectSU ); } } } } - public EffectSet getEffectSet(FlatMethod fm) { - return fm2effectSet.get(fm); + + public String toString() { + return taint2effects.toString(); } - public void writeEffectsPerMethodAndRBlock( String outfile ) { + public void writeEffects( String outfile ) { try { BufferedWriter bw = new BufferedWriter(new FileWriter(outfile)); - bw.write( "Effects Per Method\n\n" ); - - Iterator meItr1 = fm2effectSet.entrySet().iterator(); - while( meItr1.hasNext() ) { - Map.Entry me1 = (Map.Entry) meItr1.next(); - FlatMethod fm = (FlatMethod) me1.getKey(); - EffectSet es = (EffectSet) me1.getValue(); - - bw.write( "\n"+fm+"\n--------------\n" ); - - Iterator meItr2 = es.getAllEffectPairs(); - while( meItr2.hasNext() ) { - Map.Entry me2 = (Map.Entry) meItr2.next(); - Taint taint = (Taint) me2.getKey(); - HashSet effects = (HashSet) me2.getValue(); - - Iterator eItr = effects.iterator(); - while( eItr.hasNext() ) { - Effect e = eItr.next(); - - bw.write( " "+taint+"-->"+e+"\n" ); - } - } - } - - - bw.write( "\n\nEffects Per RBlock\n\n" ); + bw.write( "Effects\n---------------\n\n" ); - meItr1 = sese2effectSet.entrySet().iterator(); - while( meItr1.hasNext() ) { - Map.Entry me1 = (Map.Entry) meItr1.next(); - FlatSESEEnterNode sese = (FlatSESEEnterNode) me1.getKey(); - EffectSet es = (EffectSet) me1.getValue(); + Iterator meItr = taint2effects.entrySet().iterator(); + while( meItr.hasNext() ) { + Map.Entry me = (Map.Entry) meItr.next(); + Taint taint = (Taint) me.getKey(); + Set effects = (Set) me.getValue(); - bw.write( "\n"+sese.toPrettyString()+"\n--------------\n" ); - - Iterator meItr2 = es.getAllEffectPairs(); - while( meItr2.hasNext() ) { - Map.Entry me2 = (Map.Entry) meItr2.next(); - Taint taint = (Taint) me2.getKey(); - HashSet effects = (HashSet) me2.getValue(); - - Iterator eItr = effects.iterator(); - while( eItr.hasNext() ) { - Effect e = eItr.next(); + Iterator eItr = effects.iterator(); + while( eItr.hasNext() ) { + Effect e = eItr.next(); - bw.write( " "+taint+"-->"+e+"\n" ); - } + bw.write( taint+"-->"+e+"\n" ); } } @@ -192,84 +145,6 @@ public class EffectsAnalysis { } catch( IOException e ) {} } - protected void add( FlatMethod fm, Taint t, Effect e ) { - EffectSet es = fm2effectSet.get( fm ); - if( es == null ) { - es = new EffectSet(); - } - es.addEffect( t, e ); - - fm2effectSet.put( fm, es ); - } - - protected void add( FlatSESEEnterNode sese, Taint t, Effect e ) { - - if( sese.getIsCallerSESEplaceholder() ) { - return; - } - - EffectSet es = sese2effectSet.get( sese ); - if( es == null ) { - es = new EffectSet(); - } - es.addEffect( t, e ); - - sese2effectSet.put( sese, es ); - } - - protected void add( FlatMethod fm, Taint t, EffectSet es ) { - EffectSet esExisting = fm2effectSet.get( fm ); - if( esExisting == null ) { - esExisting = new EffectSet(); - } - - Iterator meItr = es.getAllEffectPairs(); - while( meItr.hasNext() ) { - Map.Entry me = (Map.Entry) meItr.next(); - Taint taint = (Taint) me.getKey(); - HashSet effects = (HashSet) me.getValue(); - - Iterator eItr = effects.iterator(); - while( eItr.hasNext() ) { - Effect e = eItr.next(); - - esExisting.addEffect( taint, e ); - } - } - - fm2effectSet.put( fm, esExisting ); - } - - protected void add( FlatSESEEnterNode sese, Taint t, EffectSet es ) { - - if( sese.getIsCallerSESEplaceholder() ) { - return; - } - - EffectSet esExisting = sese2effectSet.get( sese ); - - if( esExisting == null ) { - esExisting = new EffectSet(); - } - - Iterator meItr = es.getAllEffectPairs(); - while( meItr.hasNext() ) { - Map.Entry me = (Map.Entry) meItr.next(); - Taint taint = (Taint) me.getKey(); - HashSet effects = (HashSet) me.getValue(); - - Iterator eItr = effects.iterator(); - while( eItr.hasNext() ) { - Effect e = eItr.next(); - - esExisting.addEffect( taint, e ); - } - } - - sese2effectSet.put( sese, esExisting ); - } - - /* * public MethodEffects getMethodEffectsByMethodContext(MethodContext mc){ * return mapMethodContextToMethodEffects.get(mc); } diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 10be7c50..71a6f983 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -1670,8 +1670,7 @@ public class ReachGraph { // equivalent, just eliminate Taints with bad preds protected TaintSet toCallerContext( TaintSet ts, - Hashtable calleeTaintsSatisfied, - Hashtable tCallee2tsCaller + Hashtable calleeTaintsSatisfied ) { TaintSet out = TaintSet.factory(); @@ -1699,17 +1698,6 @@ public class ReachGraph { out = Canonical.add( out, tCaller ); - - // this mapping aids the effects analysis-- - // ONLY DO IF MASTER MAP IS NOT NULL - if( tCallee2tsCaller != null ) { - TaintSet tsCaller = tCallee2tsCaller.get( tCallee ); - if( tsCaller == null ) { - tsCaller = TaintSet.factory(); - } - tsCaller = Canonical.add( tsCaller, tCaller ); - tCallee2tsCaller.put( tCallee, tsCaller ); - } } } @@ -2218,7 +2206,6 @@ public class ReachGraph { FlatMethod fmCallee, ReachGraph rgCallee, Set callerNodeIDsCopiedToCallee, - Hashtable tCallee2tsCaller, boolean writeDebugDOTs ) { @@ -2756,8 +2743,7 @@ public class ReachGraph { calleeEdge2calleeStatesSatisfied.get( reCallee ) ), preds, toCallerContext( reCallee.getTaints(), - calleeEdge2calleeTaintsSatisfied.get( reCallee ), - tCallee2tsCaller ) + calleeEdge2calleeTaintsSatisfied.get( reCallee ) ) ); ChangeSet cs = ChangeSet.factory(); diff --git a/Robust/src/Tests/disjoint/taintTest1/makefile b/Robust/src/Tests/disjoint/taintTest1/makefile index 75ab66b0..ec24f5e6 100644 --- a/Robust/src/Tests/disjoint/taintTest1/makefile +++ b/Robust/src/Tests/disjoint/taintTest1/makefile @@ -5,7 +5,7 @@ SOURCE_FILES=$(PROGRAM).java BUILDSCRIPT=~/research/Robust/src/buildscript BSFLAGS= -mainclass Test -justanalyze -ooojava -disjoint -disjoint-k 1 -enable-assertions -DEBUGFLAGS= -disjoint-write-dots final -disjoint-write-initial-contexts -disjoint-write-ihms -disjoint-debug-snap-method main 0 10 true +DEBUGFLAGS= #-disjoint-write-dots final -disjoint-write-initial-contexts -disjoint-write-ihms -disjoint-debug-snap-method main 0 10 true all: $(PROGRAM).bin @@ -27,4 +27,4 @@ clean: rm -f *.dot rm -f *.png rm -f aliases.txt - rm -f effects-per-method.txt + rm -f effects.txt -- 2.34.1