package Analysis.Disjoint;
import java.util.*;
+import java.util.Map.Entry;
import java.io.*;
-import IR.FieldDescriptor;
-import IR.Flat.FlatCall;
-import IR.Flat.FlatMethod;
-import IR.Flat.TempDescriptor;
-import IR.Flat.FlatSESEEnterNode;
+import IR.*;
+import IR.Flat.*;
+import Analysis.Pointer.Edge;
+import Analysis.Pointer.AllocFactory.AllocNode;
/////////////////////////////////////////////
-//
+//
// Effects analysis computes read/write/strong
// update and other sorts of effects for the
// scope of a method or rblock. The effects
public class EffectsAnalysis {
- private Hashtable<FlatMethod, EffectSet> fm2effectSet;
- private Hashtable<FlatSESEEnterNode, EffectSet> sese2effectSet;
+ // the effects analysis should combine taints
+ // that match except for predicates--preds just
+ // support interprocedural analysis
+ private Hashtable<Taint, Set<Effect>> taint2effects;
- public EffectsAnalysis() {
- fm2effectSet = new Hashtable<FlatMethod, EffectSet>();
- sese2effectSet = new Hashtable<FlatSESEEnterNode, EffectSet>();
- }
+ // redundant views of the effect set for
+ // efficient retrieval
+ private Hashtable<FlatSESEEnterNode, Hashtable<Taint, Set<Effect>> > sese2te;
+ private Hashtable<FlatNode, Hashtable<Taint, Set<Effect>> > stallSite2te;
- public void analyzeFlatFieldNode(FlatMethod fmContaining,
- FlatSESEEnterNode seseContaining,
- ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld) {
+ public static State state;
+ public static BuildStateMachines buildStateMachines;
- VariableNode vn = rg.td2vn.get(rhs);
-
- for (Iterator<RefEdge> iterator = vn.iteratorToReferencees(); iterator.hasNext();) {
- RefEdge edge = iterator.next();
- TaintSet taintSet = edge.getTaints();
- AllocSite affectedAlloc = edge.getDst().getAllocSite();
- for (Iterator<Taint> 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);
+ public EffectsAnalysis() {
+ taint2effects = new Hashtable<Taint, Set<Effect>>();
- add( fmContaining, taint, effect );
- add( seseContaining, taint, effect );
- }
- }
+ sese2te = new Hashtable<FlatSESEEnterNode, Hashtable<Taint, Set<Effect>> >();
+ stallSite2te = new Hashtable<FlatNode, Hashtable<Taint, Set<Effect>> >();
}
- public void analyzeFlatSetFieldNode(FlatMethod fmContaining,
- FlatSESEEnterNode seseContaining,
- ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, boolean strongUpdate) {
- VariableNode vn = rg.td2vn.get(lhs);
+ public Set<Effect> getEffects(Taint t) {
+ Taint tNoPreds = Canonical.changePredsTo(t,
+ ReachGraph.predsEmpty
+ );
+ return taint2effects.get(tNoPreds);
+ }
- for (Iterator<RefEdge> iterator = vn.iteratorToReferencees(); iterator.hasNext();) {
- RefEdge edge = iterator.next();
- TaintSet taintSet = edge.getTaints();
- AllocSite affectedAlloc = edge.getDst().getAllocSite();
- for (Iterator<Taint> 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 );
- }
- }
- }
+ public Iterator iteratorTaintEffectPairs() {
+ return taint2effects.entrySet().iterator();
}
- public void analyzeFlatCall(FlatMethod fmContaining, FlatSESEEnterNode seseContaining,
- FlatMethod fmCallee, Hashtable<Taint, TaintSet> tCallee2tsCaller) {
-
- EffectSet esCaller = getEffectSet(fmContaining);
- if( esCaller == null ) {
- esCaller = new EffectSet();
- }
-
- EffectSet esCallee = getEffectSet(fmCallee);
- if( esCallee == null ) {
- esCallee = new EffectSet();
- }
+ protected void add(Taint t, Effect e, FlatNode currentProgramPoint) {
+ Taint tNoPreds = Canonical.changePredsTo(t,
+ ReachGraph.predsEmpty
+ );
- Iterator meItr = esCallee.getAllEffectPairs();
- while( meItr.hasNext() ) {
- Map.Entry me = (Map.Entry) meItr.next();
- Taint tCallee = (Taint) me.getKey();
- HashSet<Effect> effects = (HashSet<Effect>) me.getValue();
+ if( state.RCR ) {
+ buildStateMachines.addToStateMachine(t, e, currentProgramPoint);
+ }
- if( tCallee2tsCaller.containsKey( tCallee ) ) {
+ // add to the global bag
+ Set<Effect> effectSet = taint2effects.get(tNoPreds);
+ if (effectSet == null) {
+ effectSet = new HashSet<Effect>();
+ }
+ effectSet.add(e);
+ taint2effects.put(tNoPreds, effectSet);
- Iterator<Taint> tItr = tCallee2tsCaller.get( tCallee ).iterator();
- while( tItr.hasNext() ) {
- Taint tCaller = tItr.next();
+ // add to the alternate retrieval bags
+ if( t.getSESE() != null ) {
+ FlatSESEEnterNode sese = t.getSESE();
- Iterator<Effect> eItr = effects.iterator();
- while( eItr.hasNext() ) {
- Effect e = eItr.next();
-
- esCaller.addEffect( tCaller, e );
- }
+ Hashtable<Taint, Set<Effect>> te = sese2te.get(sese);
+ if( te == null ) {
+ te = new Hashtable<Taint, Set<Effect>>();
+ }
- add( fmContaining, tCaller, esCaller );
- add( seseContaining, tCaller, esCaller );
- }
+ Set<Effect> effects = te.get(tNoPreds);
+ if (effects == null) {
+ effects = new HashSet<Effect>();
}
- }
- }
+ effects.add(e);
+ te.put(tNoPreds, effects);
- public EffectSet getEffectSet(FlatMethod fm) {
- return fm2effectSet.get(fm);
- }
+ sese2te.put(sese, te);
- public void writeEffectsPerMethodAndRBlock( 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<Effect> effects = (HashSet<Effect>) me2.getValue();
-
- Iterator<Effect> eItr = effects.iterator();
- while( eItr.hasNext() ) {
- Effect e = eItr.next();
-
- bw.write( " "+taint+"-->"+e+"\n" );
- }
- }
+ } else {
+ assert t.getStallSite() != null;
+ FlatNode stallSite = t.getStallSite();
+
+ Hashtable<Taint, Set<Effect>> te = stallSite2te.get(stallSite);
+ if( te == null ) {
+ te = new Hashtable<Taint, Set<Effect>>();
}
-
- bw.write( "\n\nEffects Per RBlock\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();
-
- 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<Effect> effects = (HashSet<Effect>) me2.getValue();
-
- Iterator<Effect> eItr = effects.iterator();
- while( eItr.hasNext() ) {
- Effect e = eItr.next();
-
- bw.write( " "+taint+"-->"+e+"\n" );
- }
- }
+ Set<Effect> effects = te.get(tNoPreds);
+ if (effects == null) {
+ effects = new HashSet<Effect>();
}
+ effects.add(e);
+ te.put(tNoPreds, effects);
+ stallSite2te.put(stallSite, te);
+ }
+ }
- bw.close();
- } catch( IOException e ) {}
+
+ public Hashtable<Taint, Set<Effect>> get(FlatSESEEnterNode sese) {
+ return sese2te.get(sese);
}
- 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 );
+ public Hashtable<Taint, Set<Effect>> get(FlatNode stallSite) {
+ return stallSite2te.get(stallSite);
}
- protected void add( FlatSESEEnterNode sese, Taint t, Effect e ) {
- if( sese.getIsCallerSESEplaceholder() ) {
+
+ public void analyzeFlatFieldNode(ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld, FlatNode currentProgramPoint) {
+
+ VariableNode vn = rg.td2vn.get(rhs);
+ if( vn == null ) {
return;
}
- EffectSet es = sese2effectSet.get( sese );
- if( es == null ) {
- es = new EffectSet();
+ for (Iterator<RefEdge> iterator = vn.iteratorToReferencees(); iterator.hasNext(); ) {
+ RefEdge edge = iterator.next();
+ TaintSet taintSet = edge.getTaints();
+ AllocSite affectedAlloc = edge.getDst().getAllocSite();
+ Effect effect = new Effect(affectedAlloc, Effect.read, fld, currentProgramPoint);
+
+ for (Iterator<Taint> taintSetIter = taintSet.iterator(); taintSetIter.hasNext(); ) {
+ Taint taint = taintSetIter.next();
+ add(taint, effect, currentProgramPoint);
+ }
}
- 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();
- }
+ public void analyzeFlatFieldNode(Set<Edge> sources, FieldDescriptor fld, FlatNode currentProgramPoint) {
+ for (Edge edge:sources) {
+ TaintSet taintSet = edge.getTaints();
+ Alloc affectedAlloc = edge.getDst().getAllocSite();
+ Effect effect = new Effect(affectedAlloc, Effect.read, fld, currentProgramPoint);
- Iterator meItr = es.getAllEffectPairs();
- while( meItr.hasNext() ) {
- Map.Entry me = (Map.Entry) meItr.next();
- Taint taint = (Taint) me.getKey();
- HashSet<Effect> effects = (HashSet<Effect>) me.getValue();
-
- Iterator<Effect> eItr = effects.iterator();
- while( eItr.hasNext() ) {
- Effect e = eItr.next();
-
- esExisting.addEffect( taint, e );
- }
+ if (taintSet!=null)
+ for (Taint taint : taintSet.getTaints()) {
+ add(taint, effect, currentProgramPoint);
+ }
}
-
- fm2effectSet.put( fm, esExisting );
}
- protected void add( FlatSESEEnterNode sese, Taint t, EffectSet es ) {
+ public void analyzeFlatSetFieldNode(ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, FlatNode currentProgramPoint, boolean strongUpdate) {
- if( sese.getIsCallerSESEplaceholder() ) {
+ VariableNode vn = rg.td2vn.get(lhs);
+ if( vn == null ) {
return;
}
- EffectSet esExisting = sese2effectSet.get( sese );
+ for (Iterator<RefEdge> 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, currentProgramPoint);
+ Effect effectSU = null;
+
+ if (strongUpdate) {
+ effectSU = new Effect(affectedAlloc, Effect.strongupdate, fld, currentProgramPoint);
+ }
+
+ for (Iterator<Taint> taintSetIter = taintSet.iterator(); taintSetIter.hasNext(); ) {
+ Taint taint = taintSetIter.next();
+ add(taint, effect, currentProgramPoint);
- if( esExisting == null ) {
- esExisting = new EffectSet();
+ if (strongUpdate) {
+ add(taint, effectSU, currentProgramPoint);
+ }
+ }
}
+ }
- Iterator meItr = es.getAllEffectPairs();
- while( meItr.hasNext() ) {
- Map.Entry me = (Map.Entry) meItr.next();
- Taint taint = (Taint) me.getKey();
- HashSet<Effect> effects = (HashSet<Effect>) me.getValue();
-
- Iterator<Effect> eItr = effects.iterator();
- while( eItr.hasNext() ) {
- Effect e = eItr.next();
-
- esExisting.addEffect( taint, e );
- }
+
+ public void analyzeFlatSetFieldNode(Set<Edge> dstedges, FieldDescriptor fld, FlatNode currentProgramPoint) {
+ for (Edge edge : dstedges) {
+ TaintSet taintSet = edge.getTaints();
+ Alloc affectedAlloc = edge.getDst().getAllocSite();
+ Effect effect = new Effect(affectedAlloc, Effect.write, fld, currentProgramPoint);
+ if (taintSet!=null)
+ for (Taint taint : taintSet.getTaints()) {
+ add(taint, effect, currentProgramPoint);
+ }
}
+ }
+
- sese2effectSet.put( sese, esExisting );
+ public String toString() {
+ return taint2effects.toString();
}
+ public void writeEffects(String outfile) {
+ try {
+ BufferedWriter bw = new BufferedWriter(new FileWriter(outfile));
+
+ bw.write("Effects\n---------------\n\n");
+
+ Iterator meItr = taint2effects.entrySet().iterator();
+ while( meItr.hasNext() ) {
+ Map.Entry me = (Map.Entry)meItr.next();
+ Taint taint = (Taint) me.getKey();
+ Set<Effect> effects = (Set<Effect>)me.getValue();
+
+ Iterator<Effect> eItr = effects.iterator();
+ while( eItr.hasNext() ) {
+ Effect e = eItr.next();
+
+ bw.write(taint+"-->"+e+"\n");
+ }
+ }
+
+ bw.close();
+ } catch( IOException e ) {
+ }
+ }
/*
* public MethodEffects getMethodEffectsByMethodContext(MethodContext mc){
* return mapMethodContextToMethodEffects.get(mc); }
- *
+ *
* public void createNewMapping(MethodContext mcNew) { if(!methodeffects)
* return; if (!mapMethodContextToMethodEffects.containsKey(mcNew)) {
* MethodEffects meNew = new MethodEffects();
* return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
* me.analyzeFlatFieldNode(og, srcDesc, fieldDesc);
* mapMethodContextToMethodEffects.put(mc, me); }
- *
+ *
* public void analyzeFlatSetFieldNode(MethodContext mc, OwnershipGraph og,
* TempDescriptor dstDesc, FieldDescriptor fieldDesc) { if(!methodeffects)
* return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
* me.analyzeFlatSetFieldNode(og, dstDesc, fieldDesc);
* mapMethodContextToMethodEffects.put(mc, me); }
- *
+ *
* public void analyzeFlatSetElementNode(MethodContext mc, OwnershipGraph og,
* TempDescriptor dstDesc, FieldDescriptor fieldDesc) { if(!methodeffects)
* return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
* me.analyzeFlatSetElementNode(og, dstDesc, fieldDesc);
* mapMethodContextToMethodEffects.put(mc, me); }
- *
+ *
* public void analyzeFlatElementNode(MethodContext mc, OwnershipGraph og,
* TempDescriptor dstDesc, FieldDescriptor fieldDesc) { if(!methodeffects)
* return; MethodEffects me = mapMethodContextToMethodEffects.get(mc);
* me.analyzeFlatElementNode(og, dstDesc, fieldDesc);
* mapMethodContextToMethodEffects.put(mc, me); }
- *
- *
+ *
+ *
* public void writeMethodEffectsResult() throws IOException {
- *
+ *
* try { BufferedWriter bw = new BufferedWriter(new FileWriter(
* "MethodEffects_report.txt"));
- *
+ *
* Set<MethodContext> mcSet = mapMethodContextToMethodEffects.keySet();
* Iterator<MethodContext> mcIter = mcSet.iterator(); while (mcIter.hasNext())
* { MethodContext mc = mcIter.next(); MethodDescriptor md =
* (MethodDescriptor) mc.getDescriptor();
- *
+ *
* int startIdx = 0; if (!md.isStatic()) { startIdx = 1; }
- *
+ *
* MethodEffects me = mapMethodContextToMethodEffects.get(mc); EffectsSet
* effectsSet = me.getEffects();
- *
+ *
* bw.write("Method " + mc + " :\n"); for (int i = startIdx; i <
* md.numParameters() + startIdx; i++) {
- *
+ *
* String paramName = md.getParamName(i - startIdx);
- *
+ *
* Set<EffectsKey> effectSet = effectsSet.getReadingSet(i); String keyStr =
* "{"; if (effectSet != null) { Iterator<EffectsKey> effectIter =
* effectSet.iterator(); while (effectIter.hasNext()) { EffectsKey key =
* effectIter.next(); keyStr += " " + key; } } keyStr += " }";
* bw.write(" Paramter " + paramName + " ReadingSet=" + keyStr + "\n");
- *
+ *
* effectSet = effectsSet.getWritingSet(new Integer(i)); keyStr = "{"; if
* (effectSet != null) { Iterator<EffectsKey> effectIter =
* effectSet.iterator(); while (effectIter.hasNext()) { EffectsKey key =
* effectIter.next(); keyStr += " " + key; } }
- *
+ *
* keyStr += " }"; bw.write(" Paramter " + paramName + " WritingngSet=" +
* keyStr + "\n");
- *
+ *
* } bw.write("\n");
- *
+ *
* }
- *
+ *
* bw.close(); } catch (IOException e) { System.err.println(e); }
- *
+ *
* }
*/
+
+ public Hashtable<Taint, Set<Effect>> getAllEffects() {
+ return taint2effects;
+ }
}
projects / IRC.git / blobdiff