From 381c28daaa5eed14e4796f61c37f86d5b91eb454 Mon Sep 17 00:00:00 2001
From: yeom <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<HeapRegionNode>());
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<ReferenceEdge> referenceEdges=hrn.referencers;
+ Iterator<ReferenceEdge> 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<HeapRegionNode> visitedSet){
+
+ HashSet<ReferenceEdge> setEdge=hrn.referencers;
+ Iterator<ReferenceEdge> 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