From d29538b94d066c7f4f9cfb5beb6b208871bcc741 Mon Sep 17 00:00:00 2001 From: jjenista Date: Mon, 21 Jun 2010 21:32:26 +0000 Subject: [PATCH] capturing partially implemented taints before altering implementation --- Robust/src/Analysis/Disjoint/Canonical.java | 35 +++++++- Robust/src/Analysis/Disjoint/ExistPred.java | 26 +++--- Robust/src/Analysis/Disjoint/ReachGraph.java | 10 ++- Robust/src/Analysis/Disjoint/Taint.java | 79 ++++++++++++++++--- Robust/src/Analysis/Disjoint/TaintSet.java | 13 ++- .../src/Tests/disjoint/taintTest1/test.java | 9 ++- 6 files changed, 136 insertions(+), 36 deletions(-) diff --git a/Robust/src/Analysis/Disjoint/Canonical.java b/Robust/src/Analysis/Disjoint/Canonical.java index 12f1ea88..372ff3b1 100644 --- a/Robust/src/Analysis/Disjoint/Canonical.java +++ b/Robust/src/Analysis/Disjoint/Canonical.java @@ -1418,8 +1418,39 @@ abstract public class Canonical { // otherwise, no cached result... TaintSet out = new TaintSet(); - out.taints.addAll( ts1.taints ); - out.taints.addAll( ts2.taints ); + + // first add everything from 1, and if it was also in 2 + // take the OR of the predicates + Iterator tItr = ts1.iterator(); + while( tItr.hasNext() ) { + Taint t1 = tItr.next(); + Taint t2 = ts2.containsIgnorePreds( t1 ); + + if( t2 != null ) { + out.taints.add( Taint.factory( t1.callSite, + t1.paramIndex, + t1.sese, + t1.insetVar, + t1.allocSite, + Canonical.join( t1.preds, + t2.preds + ) + ) ); + } else { + out.taints.add( t1 ); + } + } + + // then add everything in 2 that wasn't in 1 + tItr = ts2.iterator(); + while( tItr.hasNext() ) { + Taint t2 = tItr.next(); + Taint t1 = ts1.containsIgnorePreds( t2 ); + + if( t1 == null ) { + out.taints.add( t2 ); + } + } out = (TaintSet) makeCanonical( out ); op2result.put( op, out ); diff --git a/Robust/src/Analysis/Disjoint/ExistPred.java b/Robust/src/Analysis/Disjoint/ExistPred.java index 33b5ada0..8db8adfc 100644 --- a/Robust/src/Analysis/Disjoint/ExistPred.java +++ b/Robust/src/Analysis/Disjoint/ExistPred.java @@ -76,6 +76,7 @@ public class ExistPred extends Canonical { // edge uses same ReachState ne_state as node type above + // a static debug flag for higher abstraction code // to enable debug info at this level public static boolean debug = false; @@ -294,20 +295,17 @@ public class ExistPred extends Canonical { return null; } - // when state is null it is not part of the predicate - // so we've satisfied the edge existence - if( ne_state == null ) { - return edge.getPreds(); + // only check state as part of the predicate if it + // is non-null + if( ne_state != null && + // TODO: contains OR containsSuperSet OR containsWithZeroes?? + hrnDst.getAlpha().containsIgnorePreds( ne_state ) != null + ) { + return null; } - - // otherwise look for state too - // TODO: contains OR containsSuperSet OR containsWithZeroes?? - if( hrnDst.getAlpha().containsIgnorePreds( ne_state ) - == null ) { - return edge.getPreds(); - } - - return null; + + // predicate satisfied + return edge.getPreds(); } throw new Error( "Unknown predicate type" ); @@ -439,7 +437,7 @@ public class ExistPred extends Canonical { if( ne_state != null ) { hash ^= ne_state.hashCode(); } - + return hash; } diff --git a/Robust/src/Analysis/Disjoint/ReachGraph.java b/Robust/src/Analysis/Disjoint/ReachGraph.java index 62923825..7c13cd45 100644 --- a/Robust/src/Analysis/Disjoint/ReachGraph.java +++ b/Robust/src/Analysis/Disjoint/ReachGraph.java @@ -1701,10 +1701,12 @@ public class ReachGraph { ExistPredSet.factory( pred ); Taint paramTaint = - Taint.factory( index, + Taint.factory( fc, + index, null, null, - hrnDstCallee.getAllocSite() + hrnDstCallee.getAllocSite(), + preds ); TaintSet taints = @@ -2057,6 +2059,10 @@ public class ReachGraph { Hashtable< RefEdge, Set > calleeEdges2oocCallerSrcMatches = new Hashtable< RefEdge, Set >(); + //Hashtable taintsSatisfied = + // new Hashtable(); + + Iterator meItr = rgCallee.id2hrn.entrySet().iterator(); while( meItr.hasNext() ) { Map.Entry me = (Map.Entry) meItr.next(); diff --git a/Robust/src/Analysis/Disjoint/Taint.java b/Robust/src/Analysis/Disjoint/Taint.java index 3c58ae9f..1f9f1ead 100644 --- a/Robust/src/Analysis/Disjoint/Taint.java +++ b/Robust/src/Analysis/Disjoint/Taint.java @@ -24,17 +24,20 @@ import java.io.*; /////////////////////////////////////////// // a taint is applied to a reference edge, and -// is used to associate an effect with a heap root +// is used to associate an effect with an +// sese (rblock) and in- public class Taint extends Canonical { // taints can either be associated with - // parameters or seses (rblocks), + // a callsite and parameter index or + // an sese (rblock) and an in-set var // only one set of identifying objects // will be non-null // identify a parameter index - protected Integer paramIndex; + protected FlatCall callSite; + protected Integer paramIndex; // identify an sese (rblock) + inset var protected FlatSESEEnterNode sese; @@ -44,26 +47,49 @@ public class Taint extends Canonical { // an allocation site protected AllocSite allocSite; + // existance predicates must be true in a caller + // context for this taint's effects to transfer from this + // callee to that context + protected ExistPredSet preds; - public static Taint factory( Integer pi, + + public static Taint factory( FlatCall fc, + Integer pi, FlatSESEEnterNode s, TempDescriptor iv, AllocSite as ) { - Taint out = new Taint( pi, s, iv, as ); + Taint out = new Taint( fc, pi, s, iv, as ); + out.preds = ExistPredSet.factory(); + out = (Taint) Canonical.makeCanonical( out ); + return out; + } + + public static Taint factory( FlatCall fc, + Integer pi, + FlatSESEEnterNode s, + TempDescriptor iv, + AllocSite as, + ExistPredSet eps ) { + Taint out = new Taint( fc, pi, s, iv, as ); + out.preds = eps; out = (Taint) Canonical.makeCanonical( out ); return out; } - protected Taint( Integer pi, + protected Taint( FlatCall fc, + Integer pi, FlatSESEEnterNode s, TempDescriptor iv, AllocSite as ) { + + // either fc and pi are non-null, OR s and iv are non-null assert - (pi != null && s == null && iv == null) || - (pi == null && s != null && iv != null); + (fc != null && pi != null && s == null && iv == null) || + (fc == null && pi == null && s != null && iv != null); assert as != null; - + + callSite = fc; paramIndex = pi; sese = s; insetVar = iv; @@ -71,13 +97,17 @@ public class Taint extends Canonical { } public boolean isParamTaint() { - return paramIndex != null; + return callSite != null; } public boolean isSESETaint() { return sese != null; } + public FlatCall getCallSite() { + return callSite; + } + public Integer getParamIndex() { return paramIndex; } @@ -94,8 +124,20 @@ public class Taint extends Canonical { return allocSite; } + public ExistPredSet getPreds() { + return preds; + } public boolean equalsSpecific( Object o ) { + if( !equalsIgnorePreds( o ) ) { + return false; + } + + Taint t = (Taint) o; + return preds.equals( t.preds ); + } + + public boolean equalsIgnorePreds( Object o ) { if( o == null ) { return false; } @@ -106,6 +148,13 @@ public class Taint extends Canonical { Taint t = (Taint) o; + boolean fcMatches = true; + if( callSite == null ) { + fcMatches = t.callSite == null; + } else { + fcMatches = callSite.equals( t.callSite ); + } + boolean piMatches = true; if( paramIndex == null ) { piMatches = t.paramIndex == null; @@ -134,6 +183,10 @@ public class Taint extends Canonical { public int hashCodeSpecific() { int hash = allocSite.hashCode(); + if( callSite != null ) { + hash = hash ^ callSite.hashCode(); + } + if( paramIndex != null ) { hash = hash ^ paramIndex.hashCode(); } @@ -152,12 +205,12 @@ public class Taint extends Canonical { public String toString() { String s = "("; - if( paramIndex != null ) { - s += "param"+paramIndex; + if( isParamTaint() ) { + s += "cs"+callSite.nodeid+"-"+paramIndex; } else { s += sese.toPrettyString()+"-"+insetVar; } - return s+", "+allocSite.toStringBrief()+")"; + return s+", "+allocSite.toStringBrief()+"):"+preds; } } diff --git a/Robust/src/Analysis/Disjoint/TaintSet.java b/Robust/src/Analysis/Disjoint/TaintSet.java index 1b7b4be2..6631de37 100644 --- a/Robust/src/Analysis/Disjoint/TaintSet.java +++ b/Robust/src/Analysis/Disjoint/TaintSet.java @@ -59,9 +59,18 @@ public class TaintSet extends Canonical { return taints.isEmpty(); } - public boolean containsTaint( Taint t ) { + public Taint containsIgnorePreds( Taint t ) { assert t != null; - return taints.contains( t ); + + Iterator tItr = taints.iterator(); + while( tItr.hasNext() ) { + Taint tThis = tItr.next(); + if( tThis.equalsIgnorePreds( t ) ) { + return tThis; + } + } + + return null; } public boolean equalsSpecific( Object o ) { diff --git a/Robust/src/Tests/disjoint/taintTest1/test.java b/Robust/src/Tests/disjoint/taintTest1/test.java index 04ed03b8..bae5a1a5 100644 --- a/Robust/src/Tests/disjoint/taintTest1/test.java +++ b/Robust/src/Tests/disjoint/taintTest1/test.java @@ -10,11 +10,14 @@ public class Test { Foo a = new Foo(); Foo b = new Foo(); - giveParamNames( a, b ); + Foo c = new Foo(); + Foo d = new Foo(); + giveParamNames( a, b, c ); } - static void giveParamNames( Foo a, Foo b ) { - Foo c = doStuff( a, b ); + static void giveParamNames( Foo a, Foo b, Foo c ) { + Foo e = doStuff( a, b ); + Foo f = doStuff( a, c ); } static Foo doStuff( Foo m, Foo n ) { -- 2.34.1