package Analysis.Disjoint;
-import java.util.Hashtable;
-import java.util.Iterator;
+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.*;
+import IR.Flat.*;
/////////////////////////////////////////////
//
public class EffectsAnalysis {
- private Hashtable<FlatMethod, EffectSet> mapFlatmethodToEffectset;
+ // the effects analysis should combine taints
+ // that match except for predicates--preds just
+ // support interprocedural analysis
+ private Hashtable<Taint, Set<Effect>> taint2effects;
- // private Hashtable<MethodContext, MethodEffects>
- // mapMethodContextToMethodEffects;
- // boolean methodeffects = false;
+ // 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 EffectsAnalysis(boolean methodeffects) {
- mapFlatmethodToEffectset = new Hashtable<FlatMethod, EffectSet>();
+ public static State state;
+ public static BuildStateMachines buildStateMachines;
+
+
+ public EffectsAnalysis() {
+ taint2effects = new Hashtable<Taint, Set<Effect>>();
+
+ sese2te = new Hashtable<FlatSESEEnterNode, Hashtable<Taint, Set<Effect>> >();
+ stallSite2te = new Hashtable<FlatNode, Hashtable<Taint, Set<Effect>> >();
}
- public void analyzeFlatFieldNode(FlatMethod fmContaining, ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld) {
- VariableNode vn = rg.td2vn.get(rhs);
+ public Set<Effect> getEffects(Taint t) {
+ Taint tNoPreds = Canonical.changePredsTo( t,
+ ReachGraph.predsEmpty
+ );
+ return taint2effects.get(tNoPreds);
+ }
+
+ public Iterator iteratorTaintEffectPairs() {
+ return taint2effects.entrySet().iterator();
+ }
- EffectSet effectSet = mapFlatmethodToEffectset.get(fmContaining);
+ protected void add(Taint t, Effect e, FlatNode currentProgramPoint) {
+
+ Taint tNoPreds = Canonical.changePredsTo( t,
+ ReachGraph.predsEmpty
+ );
+
+ if( state.RCR ) {
+ buildStateMachines.addToStateMachine( t, e, currentProgramPoint );
+ }
+
+ // add to the global bag
+ Set<Effect> effectSet = taint2effects.get(tNoPreds);
if (effectSet == null) {
- effectSet = new EffectSet();
+ effectSet = new HashSet<Effect>();
}
+ effectSet.add(e);
+ taint2effects.put(tNoPreds, effectSet);
- 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();
+ // add to the alternate retrieval bags
+ if( t.getSESE() != null ) {
+ FlatSESEEnterNode sese = t.getSESE();
+
+ Hashtable<Taint, Set<Effect>> te = sese2te.get( sese );
+ if( te == null ) {
+ te = new Hashtable<Taint, Set<Effect>>();
+ }
+
+ Set<Effect> effects = te.get(tNoPreds);
+ if (effects == null) {
+ effects = new HashSet<Effect>();
+ }
+ effects.add(e);
+ te.put(tNoPreds, effects);
+
+ sese2te.put(sese, te);
-// Effect effect = new Effect(taint.getParamIndex(), taint.getAllocSite(), affectedAlloc, Effect.read, fld);
-// effectSet.addMethodEffect(taint.getParamIndex(), effect);
+ } 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>>();
}
+
+ Set<Effect> effects = te.get(tNoPreds);
+ if (effects == null) {
+ effects = new HashSet<Effect>();
+ }
+ effects.add(e);
+ te.put(tNoPreds, effects);
+ stallSite2te.put(stallSite, te);
+ }
+ }
+
+
+ public Hashtable<Taint, Set<Effect>> get( FlatSESEEnterNode sese ) {
+ return sese2te.get(sese);
+ }
+
+ public Hashtable<Taint, Set<Effect>> get( FlatNode stallSite ) {
+ return stallSite2te.get(stallSite);
+ }
+
+
+
+ public void analyzeFlatFieldNode(ReachGraph rg, TempDescriptor rhs, FieldDescriptor fld, FlatNode currentProgramPoint) {
+
+ VariableNode vn = rg.td2vn.get(rhs);
+ if( vn == null ) {
+ return;
}
- mapFlatmethodToEffectset.put(fmContaining, 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);
+ for (Iterator<Taint> taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) {
+ Taint taint = taintSetIter.next();
+ add(taint, effect, currentProgramPoint);
+ }
+ }
}
- public void analyzeFlatSetFieldNode(FlatMethod fmContaining, ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld) {
+ public void analyzeFlatSetFieldNode(ReachGraph rg, TempDescriptor lhs, FieldDescriptor fld, FlatNode currentProgramPoint, boolean strongUpdate) {
VariableNode vn = rg.td2vn.get(lhs);
-
- EffectSet effectSet = mapFlatmethodToEffectset.get(fmContaining);
- if (effectSet == null) {
- effectSet = new EffectSet();
+ if( vn == null ) {
+ return;
}
for (Iterator<RefEdge> 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.write, fld);
+ Effect effectSU = null;
+
+ if (strongUpdate) {
+ effectSU = new Effect(affectedAlloc, Effect.strongupdate, fld);
+ }
+
for (Iterator<Taint> taintSetIter = taintSet.iterator(); taintSetIter.hasNext();) {
Taint taint = taintSetIter.next();
+ add( taint, effect, currentProgramPoint );
-// Effect effect = new Effect(taint.getParamIndex(), taint.getAllocSite(), affectedAlloc, Effect.write, fld);
-// effectSet.addMethodEffect(taint.getParamIndex(), effect);
-
+ if (strongUpdate) {
+ add( taint, effectSU, currentProgramPoint );
+ }
}
}
+ }
- mapFlatmethodToEffectset.put(fmContaining, effectSet);
-
+
+ public String toString() {
+ return taint2effects.toString();
}
- public EffectSet getEffectSet(FlatMethod fm) {
- return mapFlatmethodToEffectset.get(fm);
+ 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 Hashtable<Taint, Set<Effect>> getAllEffects() {
+ return taint2effects;
+ }
}