From 381c28daaa5eed14e4796f61c37f86d5b91eb454 Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 28 Sep 2009 20:58:28 +0000 Subject: [PATCH] initial commit for maintaining reference edges with taint information. --- .../OwnershipAnalysis/EffectsKey.java | 17 ++++- .../OwnershipAnalysis/MethodEffects.java | 8 +-- .../OwnershipAnalysis/OwnershipAnalysis.java | 4 +- .../OwnershipAnalysis/OwnershipGraph.java | 64 ++++++++++++++++++- .../OwnershipAnalysis/ReferenceEdge.java | 26 +++++++- 5 files changed, 107 insertions(+), 12 deletions(-) diff --git a/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java b/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java index ae09f844..39d9c6c1 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java +++ b/Robust/src/Analysis/OwnershipAnalysis/EffectsKey.java @@ -6,10 +6,12 @@ public class EffectsKey { private String fd; private TypeDescriptor td; + private Integer hrnId; - public EffectsKey(String fd, TypeDescriptor td) { + public EffectsKey(String fd, TypeDescriptor td, Integer hrnId) { this.fd = fd; this.td = td; + this.hrnId = hrnId; } public String getFieldDescriptor() { @@ -20,8 +22,12 @@ public class EffectsKey { return td; } + public Integer getHRNId() { + return hrnId; + } + public String toString() { - return "(" + td + ")" + fd; + return "(" + td + ")" + fd + "#" + hrnId; } public int hashCode() { @@ -36,6 +42,10 @@ public class EffectsKey { hash += td.getSymbol().hashCode(); } + if (hrnId != null) { + hash += hrnId.hashCode(); + } + return hash; } @@ -53,7 +63,8 @@ public class EffectsKey { EffectsKey in = (EffectsKey) o; if (fd.equals(in.getFieldDescriptor()) - && td.getSymbol().equals(in.getTypeDescriptor().getSymbol())) { + && td.getSymbol().equals(in.getTypeDescriptor().getSymbol()) + && hrnId.equals(in.getHRNId())) { return true; } else { return false; diff --git a/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java b/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java index 85b79cd2..624443a4 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java +++ b/Robust/src/Analysis/OwnershipAnalysis/MethodEffects.java @@ -40,7 +40,7 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addReadingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), srcDesc.getType())); + fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID())); } } @@ -55,7 +55,7 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addReadingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), srcDesc.getType())); + fieldDesc.getSymbol(), srcDesc.getType(),hrn.getID())); } } @@ -87,7 +87,7 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addWritingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), dstDesc.getType())); + fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); } } @@ -102,7 +102,7 @@ public class MethodEffects { while (paramIter.hasNext()) { Integer paramID = paramIter.next(); effectsSet.addWritingVar(paramID, new EffectsKey( - fieldDesc.getSymbol(), dstDesc.getType())); + fieldDesc.getSymbol(), dstDesc.getType(),hrn.getID())); } } diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java index 75e3125b..70488f02 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipAnalysis.java @@ -1084,7 +1084,7 @@ public class OwnershipAnalysis { keyStr += " " + key; } } - keyStr += "}"; + keyStr += " }"; bw.write(" Paramter " + paramName + " ReadingSet=" + keyStr + "\n"); @@ -1098,7 +1098,7 @@ public class OwnershipAnalysis { } } - keyStr += "}"; + keyStr += " }"; bw.write(" Paramter " + paramName + " WritingngSet=" + keyStr + "\n"); diff --git a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java index 448b3308..6a703241 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java +++ b/Robust/src/Analysis/OwnershipAnalysis/OwnershipGraph.java @@ -484,10 +484,15 @@ public class OwnershipGraph { edgeExisting.setBeta( edgeExisting.getBeta().union( edgeNew.getBeta() ) ); + int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY); + edgeExisting.tainedBy(newTaintIdentifier); // a new edge here cannot be reflexive, so existing will // always be also not reflexive anymore edgeExisting.setIsInitialParam( false ); } else { + int newTaintIdentifier=getTaintIdentifierFromHRN(hrnY); + edgeNew.setTaintIdentifier(newTaintIdentifier); + propagateTaintIdentifier(hrnX,newTaintIdentifier,new HashSet()); addReferenceEdge( hrnX, hrnY, edgeNew ); } } @@ -661,6 +666,7 @@ public class OwnershipGraph { null, // field false, // special param initial (not needed on label->node) betaSoup ); // reachability + edgeFromLabel.tainedBy(paramIndex); addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel ); ReferenceEdge edgeFromLabelQ = @@ -670,6 +676,7 @@ public class OwnershipGraph { null, // field false, // special param initial (not needed on label->node) betaSoup ); // reachability + edgeFromLabelQ.tainedBy(paramIndex); addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ ); ReferenceEdge edgeSecondaryReflexive; @@ -681,6 +688,7 @@ public class OwnershipGraph { null, // match all fields true, // special param initial betaSoup ); // reachability + edgeSecondaryReflexive.tainedBy(paramIndex); addReferenceEdge( hrnSecondary, hrnSecondary, edgeSecondaryReflexive ); ReferenceEdge edgeSecondary2Primary = @@ -690,6 +698,7 @@ public class OwnershipGraph { null, // match all fields true, // special param initial betaSoup ); // reachability + edgeSecondary2Primary.tainedBy(paramIndex); addReferenceEdge( hrnSecondary, hrnPrimary, edgeSecondary2Primary ); ReferenceEdge edgeFromLabelR = @@ -699,6 +708,7 @@ public class OwnershipGraph { null, // field false, // special param initial (not needed on label->node) betaSoup ); // reachability + edgeFromLabelR.tainedBy(paramIndex); addReferenceEdge( lnParamR, hrnSecondary, edgeFromLabelR ); } @@ -712,7 +722,8 @@ public class OwnershipGraph { fd.getType(), // type fd.getSymbol(), // field true, // special param initial - betaSoup ); // reachability + betaSoup ); // reachability + edgePrimaryReflexive.tainedBy(paramIndex); addReferenceEdge( hrnPrimary, hrnPrimary, edgePrimaryReflexive ); } @@ -727,6 +738,7 @@ public class OwnershipGraph { fd.getSymbol(), // field true, // special param initial betaSoup ); // reachability + edgePrimary2Secondary.tainedBy(paramIndex); addReferenceEdge( hrnPrimary, hrnSecondary, edgePrimary2Secondary ); } } @@ -756,7 +768,7 @@ public class OwnershipGraph { ReferenceEdge edgeReflexive = new ReferenceEdge( hrn, hrn, null, null, true, beta ); - + addReferenceEdge( lnBlob, hrn, edgeFromLabel ); addReferenceEdge( hrn, hrn, edgeReflexive ); } @@ -840,6 +852,7 @@ public class OwnershipGraph { null, // field false, // special param initial (not needed on label->node) betaSoup ); // reachability + edgeFromLabel.tainedBy(paramIndex); addReferenceEdge( lnParam, hrnPrimary, edgeFromLabel ); ReferenceEdge edgeFromLabelQ = @@ -849,6 +862,7 @@ public class OwnershipGraph { null, // field false, // special param initial (not needed on label->node) betaSoup ); // reachability + edgeFromLabelQ.tainedBy(paramIndex); addReferenceEdge( lnParamQ, hrnPrimary, edgeFromLabelQ ); ReferenceEdge edgeAliased2Primary = @@ -858,6 +872,7 @@ public class OwnershipGraph { null, // match all fields true, // special param initial betaSoup ); // reachability + edgeAliased2Primary.tainedBy(paramIndex); addReferenceEdge( hrnAliasBlob, hrnPrimary, edgeAliased2Primary ); ReferenceEdge edgeFromLabelR = @@ -867,6 +882,7 @@ public class OwnershipGraph { null, // field false, // special param initial (not needed on label->node) betaSoup ); // reachability + edgeFromLabelR.tainedBy(paramIndex); addReferenceEdge( lnParamR, hrnAliasBlob, edgeFromLabelR ); } @@ -975,6 +991,7 @@ public class OwnershipGraph { fd.getSymbol(), // field true, // special param initial betaSoup ); // reachability + edgePrimaryReflexive.tainedBy(new Integer(i)); addReferenceEdge( primaryI, primaryI, edgePrimaryReflexive ); } @@ -991,6 +1008,7 @@ public class OwnershipGraph { fd.getSymbol(), // field true, // special param initial betaSoup ); // reachability + edgePrimary2Secondary.tainedBy(new Integer(i)); addReferenceEdge( primaryI, hrnAliasBlob, edgePrimary2Secondary ); // ask whether these fields might match any of the other aliased @@ -1025,6 +1043,7 @@ public class OwnershipGraph { fd.getSymbol(), // field true, // special param initial betaSoupWJ ); // reachability + edgePrimaryI2PrimaryJ.tainedBy(new Integer(i)); addReferenceEdge( primaryI, primaryJ, edgePrimaryI2PrimaryJ ); } } @@ -1055,6 +1074,7 @@ public class OwnershipGraph { ReferenceEdge lnI2PrimaryJ = lnJ2PrimaryJ.copy(); lnI2PrimaryJ.setSrc( lnParamI ); lnI2PrimaryJ.setType( tdParamI.getType() ); + lnI2PrimaryJ.tainedBy(new Integer(j)); addReferenceEdge( lnParamI, primaryJ, lnI2PrimaryJ ); } } @@ -3711,6 +3731,8 @@ public class OwnershipGraph { edgeToMerge.setBeta( edgeToMerge.getBeta().union(edgeA.getBeta() ) ); + //TODO eom + edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier()); if( !edgeA.isInitialParam() ) { edgeToMerge.setIsInitialParam(false); } @@ -3772,6 +3794,8 @@ public class OwnershipGraph { edgeToMerge.setBeta( edgeToMerge.getBeta().union(edgeA.getBeta() ) ); + //TODO eom + edgeToMerge.unionTaintIdentifier(edgeA.getTaintIdentifier()); if( !edgeA.isInitialParam() ) { edgeToMerge.setIsInitialParam(false); } @@ -4656,4 +4680,40 @@ public class OwnershipGraph { writeReferencers); } } + + public int getTaintIdentifierFromHRN(HeapRegionNode hrn){ + HashSet referenceEdges=hrn.referencers; + Iterator iter=referenceEdges.iterator(); + + int taintIdentifier=0; + while(iter.hasNext()){ + ReferenceEdge edge=iter.next(); + taintIdentifier=taintIdentifier | edge.getTaintIdentifier(); + } + + return taintIdentifier; + + } + + public void propagateTaintIdentifier(HeapRegionNode hrn, int newTaintIdentifier, HashSet visitedSet){ + + HashSet setEdge=hrn.referencers; + Iterator iter=setEdge.iterator(); + while(iter.hasNext()){ + ReferenceEdge edge= iter.next(); + edge.unionTaintIdentifier(newTaintIdentifier); + if(edge.getSrc() instanceof HeapRegionNode){ + + HeapRegionNode refHRN=(HeapRegionNode)edge.getSrc(); + //check whether it is reflexive edge + if(!refHRN.equals(hrn) && !visitedSet.contains(refHRN)){ + visitedSet.add(refHRN); + propagateTaintIdentifier((HeapRegionNode)edge.getSrc(),newTaintIdentifier,visitedSet); + } + + } + } + + } + } diff --git a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java index 51389d48..669da7bd 100644 --- a/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java +++ b/Robust/src/Analysis/OwnershipAnalysis/ReferenceEdge.java @@ -17,6 +17,7 @@ public class ReferenceEdge { protected OwnershipNode src; protected HeapRegionNode dst; + private int taintIdentifier; public ReferenceEdge(OwnershipNode src, @@ -31,6 +32,7 @@ public class ReferenceEdge { this.type = type; this.field = field; this.isInitialParam = isInitialParam; + this.taintIdentifier = 0; if( beta != null ) { this.beta = beta; @@ -45,12 +47,14 @@ public class ReferenceEdge { public ReferenceEdge copy() { - return new ReferenceEdge(src, + ReferenceEdge copy= new ReferenceEdge(src, dst, type, field, isInitialParam, beta); + copy.setTaintIdentifier(this.taintIdentifier); + return copy; } @@ -218,6 +222,8 @@ public class ReferenceEdge { if( isInitialParam ) { edgeLabel += "*init*\\n"; } + + edgeLabel+="*taint*="+taintIdentifier+"\\n"; edgeLabel += beta.toStringEscapeNewline(); @@ -231,4 +237,22 @@ public class ReferenceEdge { return new String("("+src+"->"+type+" "+field+"->"+dst+")"); } + + public void tainedBy(Integer paramIdx){ + int newTaint=(int) Math.pow(2, paramIdx.intValue()); + taintIdentifier=taintIdentifier | newTaint; + } + + public void setTaintIdentifier(int newTaint){ + taintIdentifier=newTaint; + } + + public void unionTaintIdentifier(int newTaint){ + taintIdentifier=taintIdentifier | newTaint; + } + + public int getTaintIdentifier(){ + return taintIdentifier; + } + } -- 2.34.1