From 9dfdca00acf795117136425841493a1b0f036f10 Mon Sep 17 00:00:00 2001 From: yeom Date: Sun, 21 Oct 2012 02:10:14 +0000 Subject: [PATCH] changes on the composite location generation (but still it doesn't work) & found bugs in the type checker + fixed annotations --- Robust/src/Analysis/SSJava/FlowDownCheck.java | 58 ++- Robust/src/Analysis/SSJava/FlowGraph.java | 6 +- .../src/Analysis/SSJava/GlobalFlowGraph.java | 5 + .../src/Analysis/SSJava/HierarchyGraph.java | 3 + .../Analysis/SSJava/LocationInference.java | 419 +++++++----------- Robust/src/Analysis/SSJava/NodeTupleSet.java | 40 +- .../SSJava/MP3Decoder/Equalizer.java | 4 +- .../SSJava/MP3Decoder/huffcodetab.java | 3 +- 8 files changed, 252 insertions(+), 286 deletions(-) diff --git a/Robust/src/Analysis/SSJava/FlowDownCheck.java b/Robust/src/Analysis/SSJava/FlowDownCheck.java index 8f5ae45e..f3d34a55 100644 --- a/Robust/src/Analysis/SSJava/FlowDownCheck.java +++ b/Robust/src/Analysis/SSJava/FlowDownCheck.java @@ -363,10 +363,12 @@ public class FlowDownCheck { CompositeLocation thisLoc = new CompositeLocation(new Location(md, thisLocId)); paramList.add(0, thisLoc); - md2ReturnLocGen.put(md, new ReturnLocGenerator(md2ReturnLoc.get(md), md, paramList, md - + " of " + cd.getSourceFileName())); + } + md2ReturnLocGen.put(md, new ReturnLocGenerator(md2ReturnLoc.get(md), md, paramList, md + + " of " + cd.getSourceFileName())); + } // fourth, check declarations inside of method @@ -550,6 +552,10 @@ public class FlowDownCheck { private CompositeLocation checkLocationFromReturnNode(MethodDescriptor md, SymbolTable nametable, ReturnNode rn, CompositeLocation constraint) { + if (ssjava.getMethodContainingSSJavaLoop().equals(md)) { + return new CompositeLocation(); + } + ExpressionNode returnExp = rn.getReturnExpression(); CompositeLocation declaredReturnLoc = md2ReturnLoc.get(md); @@ -701,14 +707,14 @@ public class FlowDownCheck { private CompositeLocation checkLocationFromIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn, CompositeLocation constraint) { - System.out.println("checkLocationFromIfStatementNode="+isn); + System.out.println("checkLocationFromIfStatementNode=" + isn); CompositeLocation condLoc = checkLocationFromExpressionNode(md, nametable, isn.getCondition(), new CompositeLocation(), constraint, false); - System.out.println("-######old constraint="+constraint); + System.out.println("-######old constraint=" + constraint); constraint = generateNewConstraint(constraint, condLoc); - System.out.println("-######new constraint="+constraint); + System.out.println("-######new constraint=" + constraint); checkLocationFromBlockNode(md, nametable, isn.getTrueBlock(), constraint); if (isn.getFalseBlock() != null) { @@ -1026,7 +1032,7 @@ public class FlowDownCheck { if (!argLocation.get(0).isTop() && CompositeLattice.compare(argLocation, constraint, true, - generateErrorMessage(cd, min)) == ComparisonResult.GREATER) { + generateErrorMessage(cd, min)) == ComparisonResult.LESS) { CompositeLocation paramLocation = calleeParamList.get(idx); @@ -1047,7 +1053,8 @@ public class FlowDownCheck { System.out.println("---PARAM LOC=" + paramLocation + " calleePCLOC=" + calleePCLOC + " paramCompareResult=" + paramCompareResult); - if (paramCompareResult != ComparisonResult.GREATER) { + if (!(paramLocation.get(0).equals(calleePCLOC.get(0)) && calleePCLOC.getSize() > 1) + && paramCompareResult != ComparisonResult.LESS) { throw new Error( "The program counter location " + constraint @@ -1068,8 +1075,7 @@ public class FlowDownCheck { checkCalleeConstraints(md, nametable, min, baseLocation, constraint); - // checkCallerArgumentLocationConstraints(md, nametable, min, - // baseLocation, constraint); + checkCallerArgumentLocationConstraints(md, nametable, min, baseLocation, constraint); if (!min.getMethod().getReturnType().isVoid()) { // If method has a return value, compute the highest possible return @@ -1163,7 +1169,16 @@ public class FlowDownCheck { generateErrorMessage(md.getClassDesc(), min)); } - if (!CompositeLattice.isGreaterThan(callerArgLoc, paramLocation, errorMsg)) { + Location argLastLoc = callerArgLoc.get(callerArgLoc.getSize() - 1); + Location paramLastLoc = paramLocation.get(paramLocation.getSize() - 1); + + if (argLastLoc.equals(paramLastLoc) && ssjava.isSharedLocation(argLastLoc) + && ssjava.isSharedLocation(paramLastLoc)) { + continue; + } + + // if (!CompositeLattice.isGreaterThan(callerArgLoc, paramLocation, errorMsg)) { + if (CompositeLattice.compare(callerArgLoc, paramLocation, true, errorMsg) == ComparisonResult.LESS) { throw new Error("Caller argument '" + min.getArg(i).printNode(0) + " : " + callerArgLoc + "' should be higher than corresponding callee's parameter : " + paramLocation + " at " + errorMsg); @@ -1310,16 +1325,24 @@ public class FlowDownCheck { String paramName1, paramName2; - if (i == 0) { - paramName1 = "'THIS'"; + if (!calleemd.isStatic()) { + if (i == 0) { + paramName1 = "'THIS'"; + } else { + paramName1 = "'parameter " + calleemd.getParamName(i - 1) + "'"; + } } else { - paramName1 = "'parameter " + calleemd.getParamName(i - 1) + "'"; + paramName1 = "'parameter " + calleemd.getParamName(i) + "'"; } - if (j == 0) { - paramName2 = "'THIS'"; + if (!calleemd.isStatic()) { + if (j == 0 && !calleemd.isStatic()) { + paramName2 = "'THIS'"; + } else { + paramName2 = "'parameter " + calleemd.getParamName(j - 1) + "'"; + } } else { - paramName2 = "'parameter " + calleemd.getParamName(j - 1) + "'"; + paramName2 = "'parameter " + calleemd.getParamName(j) + "'"; } throw new Error( @@ -1545,7 +1568,6 @@ public class FlowDownCheck { SymbolTable nametable, FieldAccessNode fan, CompositeLocation loc, CompositeLocation constraint) { - ExpressionNode left = fan.getExpression(); TypeDescriptor ltd = left.getType(); @@ -1632,7 +1654,6 @@ public class FlowDownCheck { private CompositeLocation checkLocationFromAssignmentNode(MethodDescriptor md, SymbolTable nametable, AssignmentNode an, CompositeLocation loc, CompositeLocation constraint) { - ClassDescriptor cd = md.getClassDesc(); Set inputGLBSet = new HashSet(); @@ -1660,7 +1681,6 @@ public class FlowDownCheck { checkLocationFromExpressionNode(md, nametable, an.getSrc(), new CompositeLocation(), constraint, false); - if (an.getOperation().getOp() >= 2 && an.getOperation().getOp() <= 12) { // if assignment contains OP+EQ operator, need to merge location types // of LHS & RHS into the RHS diff --git a/Robust/src/Analysis/SSJava/FlowGraph.java b/Robust/src/Analysis/SSJava/FlowGraph.java index 77ec3d14..2ab6dad9 100644 --- a/Robust/src/Analysis/SSJava/FlowGraph.java +++ b/Robust/src/Analysis/SSJava/FlowGraph.java @@ -109,7 +109,7 @@ public class FlowGraph { mapDescTupleToInferNode.put(tuple, newNode); // nodeSet.add(newNode); - System.out.println("create new intermediate node= " + newNode); + System.out.println("create new intermediate node= " + newNode); return newNode; } @@ -235,7 +235,7 @@ public class FlowGraph { return; } - // System.out.println("create an edge from " + fromNode + " to " + toNode); + System.out.println("create an edge from " + fromNode + " to " + toNode); int fromTupleSize = fromDescTuple.size(); NTuple curFromTuple = new NTuple(); @@ -467,8 +467,6 @@ public class FlowGraph { Descriptor localDesc = fn.getDescTuple().get(0); - System.out.println("descTuple=" + descTuple); - if (fn.isIntermediate()) { Location interLoc = new Location(md, localDesc.getSymbol()); interLoc.setLocDescriptor(localDesc); diff --git a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java index 1cf59b77..a9ef90af 100644 --- a/Robust/src/Analysis/SSJava/GlobalFlowGraph.java +++ b/Robust/src/Analysis/SSJava/GlobalFlowGraph.java @@ -91,6 +91,11 @@ public class GlobalFlowGraph { public void addValueFlowEdge(NTuple fromLocTuple, NTuple toLocTuple) { + Location lastElementfromLocTuple = fromLocTuple.get(fromLocTuple.size() - 1); + if (lastElementfromLocTuple.getLocDescriptor().equals(LocationInference.LITERALDESC)) { + return; + } + GlobalFlowNode fromNode = getFlowNode(fromLocTuple); GlobalFlowNode toNode = getFlowNode(toLocTuple); diff --git a/Robust/src/Analysis/SSJava/HierarchyGraph.java b/Robust/src/Analysis/SSJava/HierarchyGraph.java index 720be2dc..49b8984f 100644 --- a/Robust/src/Analysis/SSJava/HierarchyGraph.java +++ b/Robust/src/Analysis/SSJava/HierarchyGraph.java @@ -141,10 +141,13 @@ public class HierarchyGraph { if (possibleCycleSet.size() > 0) { if (possibleCycleSet.size() == 1) { + System.out.println("possibleCycleSet=" + possibleCycleSet + " from src=" + srcHNode + + " dstHNode=" + dstHNode); if (dstHNode.isSharedNode()) { // it has already been assigned shared node. } else { dstHNode.setSharedNode(true); + System.out.println("$$$setShared=" + dstHNode); } return; } diff --git a/Robust/src/Analysis/SSJava/LocationInference.java b/Robust/src/Analysis/SSJava/LocationInference.java index f09b930d..b17ea3c7 100644 --- a/Robust/src/Analysis/SSJava/LocationInference.java +++ b/Robust/src/Analysis/SSJava/LocationInference.java @@ -98,6 +98,8 @@ public class LocationInference { private Map> mapMethodInvokeNodeToBaseTuple; + private Map>> mapMethodInvokeNodeToPCLocTupleSet; + private Map mapMethodDescToMethodLocationInfo; private Map mapClassToLocationInfo; @@ -186,6 +188,9 @@ public class LocationInference { this.mapMethodInvokeNodeToMapCallerArgToCalleeArg = new HashMap, NTuple>>(); + this.mapMethodInvokeNodeToPCLocTupleSet = + new HashMap>>(); + } public void setupToAnalyze() { @@ -235,7 +240,9 @@ public class LocationInference { constructFlowGraph(); assignCompositeLocation(); + updateFlowGraph(); + assignCompositeLocation(); updateFlowGraph(); // calculate RETURNLOC,PCLOC @@ -421,6 +428,7 @@ public class LocationInference { // tuple of 'min'. translateMapLocationToInferCompositeLocationToCalleeGraph(callerGlobalFlowGraph, min); calleeSet.add(min.getMethod()); + } for (Iterator iterator = calleeSet.iterator(); iterator.hasNext();) { @@ -428,6 +436,51 @@ public class LocationInference { translateCompositeLocationAssignmentToFlowGraph(callee); } + for (Iterator iterator = minSet.iterator(); iterator.hasNext();) { + MethodInvokeNode min = (MethodInvokeNode) iterator.next(); + // add an additional ordering constraint + // if the first element of a parameter composite location matches 'this' reference, + // the corresponding argument in the caller is required to be higher than the translated + // parameter location in the caller lattice + // TODO + addOrderingConstraintFromCompLocParamToArg(mdCaller, min); + } + + } + + private void addOrderingConstraintFromCompLocParamToArg(MethodDescriptor mdCaller, + MethodInvokeNode min) { + System.out.println("-addOrderingConstraintFromCompLocParamToArg=" + min.printNode(0)); + + GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(ssjava.getMethodContainingSSJavaLoop()); + + Set> pcLocTupleSet = getPCLocTupleSet(min); + + MethodDescriptor mdCallee = min.getMethod(); + + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); + for (int idx = 0; idx < calleeFlowGraph.getNumParameters(); idx++) { + FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); + NTuple globalParamLocTuple = + translateToLocTuple(mdCallee, paramNode.getDescTuple()); + translateToLocTuple(mdCallee, paramNode.getDescTuple()); + CompositeLocation compLoc = paramNode.getCompositeLocation(); + System.out.println("---paramNode=" + paramNode + " compLoc=" + compLoc); + if (compLoc != null) { + NTuple argTuple = getNodeTupleByArgIdx(min, idx); + NTuple globalArgLocTuple = translateToLocTuple(mdCaller, argTuple); + System.out.println("----- add global flow globalArgLocTuple=" + globalArgLocTuple + + "-> globalParamLocTuple=" + globalParamLocTuple); + globalGraph.addValueFlowEdge(globalArgLocTuple, globalParamLocTuple); + + for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator.next(); + System.out.println("----- add global flow PCLOC=" + pcLocTuple + + "-> globalParamLocTuple=" + globalParamLocTuple); + globalGraph.addValueFlowEdge(pcLocTuple, globalParamLocTuple); + } + } + } } public void assignCompositeLocationToFlowGraph(FlowGraph flowGraph, Location loc, @@ -710,6 +763,7 @@ public class LocationInference { globalFlowGraph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); // Set reachNodeSet = globalFlowGraph.getReachableNodeSetFrom(node); + System.out.println("node=" + node + " prefixList=" + prefixList); // System.out.println("node=" + node + " prefixList=" + prefixList + " reachableNodeSet=" // + reachableNodeSet); @@ -717,12 +771,15 @@ public class LocationInference { NTuple curPrefix = prefixList.get(i); Set> reachableCommonPrefixSet = new HashSet>(); + System.out.println("curPrefix=" + curPrefix); for (Iterator iterator2 = reachableNodeSet.iterator(); iterator2.hasNext();) { GlobalFlowNode reachNode = (GlobalFlowNode) iterator2.next(); + System.out.println("reachNode=" + reachNode); if (reachNode.getLocTuple().startsWith(curPrefix)) { reachableCommonPrefixSet.add(reachNode.getLocTuple()); } } + System.out.println("reachableCommonPrefixSet=" + reachableCommonPrefixSet); if (!reachableCommonPrefixSet.isEmpty()) { @@ -732,6 +789,10 @@ public class LocationInference { MethodDescriptor nodePrefixLocFirstElementMethodDesc = (MethodDescriptor) prefixLoc.getDescriptor(); + System.out.println("curPrefixFirstElementMethodDesc=" + curPrefixFirstElementMethodDesc); + System.out.println("nodePrefixLocFirstElementMethodDesc=" + + nodePrefixLocFirstElementMethodDesc); + if (curPrefixFirstElementMethodDesc.equals(nodePrefixLocFirstElementMethodDesc) || isTransitivelyCalledFrom(nodePrefixLocFirstElementMethodDesc, curPrefixFirstElementMethodDesc)) { @@ -791,24 +852,31 @@ public class LocationInference { Set incomingNodeSetPrefix = graph.getIncomingNodeSetByPrefix(node.getLocTuple().get(0)); - // System.out.println("incomingNodeSetPrefix=" + incomingNodeSetPrefix); + System.out.println("incomingNodeSetPrefix=" + incomingNodeSetPrefix); // - // Set reachableNodeSetPrefix = - // graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); - // System.out.println("reachableNodeSetPrefix=" + reachableNodeSetPrefix); + Set reachableNodeSetPrefix = + graph.getReachableNodeSetByPrefix(node.getLocTuple().get(0)); + System.out.println("reachableNodeSetPrefix=" + reachableNodeSetPrefix); List> prefixList = new ArrayList>(); for (Iterator iterator = incomingNodeSetPrefix.iterator(); iterator.hasNext();) { GlobalFlowNode inNode = (GlobalFlowNode) iterator.next(); NTuple inNodeTuple = inNode.getLocTuple(); - + System.out.println("inNodetuple=" + inNodeTuple); + // if (inNodeTuple.size() == 1) { + // if (!prefixList.contains(inNodeTuple)) { + // prefixList.add(inNodeTuple); + // } + // } else { for (int i = 1; i < inNodeTuple.size(); i++) { NTuple prefix = inNodeTuple.subList(0, i); + System.out.println("-p=" + prefix); if (!prefixList.contains(prefix)) { prefixList.add(prefix); } } + // } } Collections.sort(prefixList, new Comparator>() { @@ -831,14 +899,16 @@ public class LocationInference { ClassDescriptor cd = md.getClassDesc(); int idx = 0; - + System.out.println("$$$$$$$$$$$prefixList=" + prefixList); Set> toberemoved = new HashSet>(); - for (int i = 0; i < prefixList.size(); i++) { - NTuple prefixLocTuple = prefixList.get(i); - if (!containsClassDesc(cd, prefixLocTuple)) { - toberemoved.add(prefixLocTuple); - } - } + // for (int i = 0; i < prefixList.size(); i++) { + // NTuple prefixLocTuple = prefixList.get(i); + // if (!containsClassDesc(cd, prefixLocTuple)) { + // toberemoved.add(prefixLocTuple); + // } + // } + + System.out.println("method class=" + cd + " toberemoved=" + toberemoved); prefixList.removeAll(toberemoved); @@ -892,7 +962,7 @@ public class LocationInference { MethodDescriptor md = flowGraph.getMethodDescriptor(); - GlobalFlowGraph globalGraph = new GlobalFlowGraph(md); + GlobalFlowGraph globalGraph = getSubGlobalFlowGraph(md); // Set nodeSet = flowGraph.getNodeSet(); Set edgeSet = flowGraph.getEdgeSet(); @@ -1836,6 +1906,8 @@ public class LocationInference { NTuple srcCurTuple = srcNode.getCurrentDescTuple(); NTuple dstCurTuple = dstNode.getCurrentDescTuple(); + // System.out.println("-srcCurTuple=" + srcCurTuple + " dstCurTuple=" + dstCurTuple); + if ((srcCurTuple.size() > 1 && dstCurTuple.size() > 1) && srcCurTuple.get(0).equals(dstCurTuple.get(0))) { @@ -1851,7 +1923,7 @@ public class LocationInference { } extractFlowsBetweenFields(classDesc, srcNode, dstNode, 1); - } else { + } else if (!srcCurTuple.get(0).equals(dstCurTuple.get(0))) { // value flow between local var - local var or local var - field Descriptor srcDesc = srcCurTuple.get(0); @@ -2603,7 +2675,7 @@ public class LocationInference { NTuple returnLocTuple = generateLocTupleRelativeTo(md, tupleToBeHigherThanReturnLocSet, RLOC); - System.out.println("returnLocTuple=" + returnLocTuple); + // System.out.println("returnLocTuple=" + returnLocTuple); NTuple returnDescTuple = translateToDescTuple(returnLocTuple); for (Iterator iterator = tupleToBeHigherThanReturnLocSet.iterator(); iterator.hasNext();) { @@ -2612,7 +2684,7 @@ public class LocationInference { } fg.getFlowNode(returnDescTuple).setSkeleton(true); - System.out.println("fg node set=" + fg.getNodeSet()); + // System.out.println("fg node set=" + fg.getNodeSet()); methodSummary.setRETURNLoc(new CompositeLocation(returnLocTuple)); @@ -3094,6 +3166,10 @@ public class LocationInference { } private GlobalFlowGraph getSubGlobalFlowGraph(MethodDescriptor md) { + + if (!mapMethodDescriptorToSubGlobalFlowGraph.containsKey(md)) { + mapMethodDescriptorToSubGlobalFlowGraph.put(md, new GlobalFlowGraph(md)); + } return mapMethodDescriptorToSubGlobalFlowGraph.get(md); } @@ -3165,208 +3241,31 @@ public class LocationInference { for (int idx = 0; idx < numParam; idx++) { FlowNode paramNode = calleeFlowGraph.getParamFlowNode(idx); CompositeLocation compLoc = paramNode.getCompositeLocation(); - if (compLoc != null) { + if (compLoc != null && compLoc.get(0).getLocDescriptor().equals(min.getMethod().getThis())) { System.out.println("$$$COMPLOC CASE=" + compLoc); NTuple argTuple = getNodeTupleByArgIdx(min, idx); - NTuple translatedParamTuple = translateCompositeLocationToCaller(min, compLoc); + NTuple translatedParamTuple = + translateCompositeLocationToCaller(idx, min, compLoc); System.out.println("add a flow edge= " + argTuple + "->" + translatedParamTuple); callerFlowGraph.addValueFlowEdge(argTuple, translatedParamTuple); - } - } - - } - - private void propagateFlowsToCaller(MethodInvokeNode min, MethodDescriptor mdCaller, - MethodDescriptor mdCallee) { - - System.out.println("\n##PROPAGATE callee=" + mdCallee + "TO caller=" + mdCaller); - - // if the parameter A reaches to the parameter B - // then, add an edge the argument A -> the argument B to the caller's flow - // graph - - // TODO - // also if a parameter is a composite location and is started with "this" - // reference, - // need to make sure that the corresponding argument is higher than the - // translated location of - // the parameter. - - FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); - FlowGraph callerFlowGraph = getFlowGraph(mdCaller); - int numParam = calleeFlowGraph.getNumParameters(); - - for (int i = 0; i < numParam; i++) { - for (int k = 0; k < numParam; k++) { - - if (i != k) { - - FlowNode paramNode1 = calleeFlowGraph.getParamFlowNode(i); - FlowNode paramNode2 = calleeFlowGraph.getParamFlowNode(k); - - System.out.println("param1=" + paramNode1 + " curDescTuple=" - + paramNode1.getCurrentDescTuple()); - System.out.println("param2=" + paramNode2 + " curDescTuple=" - + paramNode2.getCurrentDescTuple()); - - // TODO: deprecated method - // NodeTupleSet tupleSetArg1 = getNodeTupleSetByArgIdx(min, i); - // NodeTupleSet tupleSetArg2 = getNodeTupleSetByArgIdx(min, k); - NodeTupleSet tupleSetArg1 = null; - NodeTupleSet tupleSetArg2 = null; - - for (Iterator> iter1 = tupleSetArg1.iterator(); iter1.hasNext();) { - NTuple arg1Tuple = iter1.next(); - - for (Iterator> iter2 = tupleSetArg2.iterator(); iter2.hasNext();) { - NTuple arg2Tuple = iter2.next(); - - // check if the callee propagates an ordering constraints through - // parameters - - Set localReachSet = - calleeFlowGraph.getLocalReachFlowNodeSetFrom(paramNode1); - - if (localReachSet.contains(paramNode2)) { - // need to propagate an ordering relation s.t. arg1 is higher - // than arg2 - - System.out - .println("-param1=" + paramNode1 + " is higher than param2=" + paramNode2); - System.out.println("-arg1Tuple=" + arg1Tuple + " is higher than arg2Tuple=" - + arg2Tuple); - - if (!min.getMethod().isStatic()) { - // check if this is the case that values flow to/from the - // current object reference 'this' - - NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); - Descriptor baseRef = baseTuple.get(baseTuple.size() - 1); - - System.out.println("paramNode1.getCurrentDescTuple()=" - + paramNode1.getCurrentDescTuple()); - // calculate the prefix of the argument - - if (arg2Tuple.size() == 1 && arg2Tuple.get(0).equals(baseRef)) { - // in this case, the callee flow causes a caller flow to the - // object whose method - // is invoked. - - if (!paramNode1.getCurrentDescTuple().startsWith(mdCallee.getThis())) { - // check whether ??? - - NTuple param1Prefix = - calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg1Tuple, - paramNode1); - - if (param1Prefix != null && param1Prefix.startsWith(mdCallee.getThis())) { - // in this case, we need to create a new edge - // 'this.FIELD'->'this' - // but we couldn't... instead we assign a new composite - // location started - // with 'this' reference to the corresponding parameter - - CompositeLocation compLocForParam1 = - generateCompositeLocation(mdCallee, param1Prefix); - - System.out - .println("set comp loc=" + compLocForParam1 + " to " + paramNode1); - paramNode1.setCompositeLocation(compLocForParam1); - // then, we need to make sure that the corresponding - // argument in the caller - // is required to be higher than or equal to the - // translated parameter - // location - - NTuple translatedParamTuple = - translateCompositeLocationToCaller(min, compLocForParam1); - - // TODO : check if the arg >= the tranlated parameter - - System.out.println("add a flow edge= " + arg1Tuple + "->" - + translatedParamTuple); - callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); - - continue; - - } - - } else { - // param1 has already been assigned a composite location - - System.out.println("--param1 has already been assigned a composite location"); - CompositeLocation compLocForParam1 = paramNode1.getCompositeLocation(); - NTuple translatedParamTuple = - translateCompositeLocationToCaller(min, compLocForParam1); - - // TODO : check if the arg >= the tranlated parameter - - System.out.println("add a flow edge= " + arg1Tuple + "->" - + translatedParamTuple); - callerFlowGraph.addValueFlowEdge(arg1Tuple, translatedParamTuple); - - continue; - - } - - } else if (arg1Tuple.size() == 1 && arg1Tuple.get(0).equals(baseRef)) { - // in this case, the callee flow causes a caller flow - // originated from the object - // whose - // method is invoked. - - System.out.println("###FROM CASE"); - - if (!paramNode2.getCurrentDescTuple().startsWith(mdCallee.getThis())) { - - NTuple param2Prefix = - calculatePrefixForParam(callerFlowGraph, calleeFlowGraph, min, arg2Tuple, - paramNode2); - - if (param2Prefix != null && param2Prefix.startsWith(mdCallee.getThis())) { - // in this case, we need to create a new edge 'this' -> - // 'this.FIELD' but we couldn't... instead we assign the - // corresponding - // parameter a new composite location started with - // 'this' reference - - CompositeLocation compLocForParam2 = - generateCompositeLocation(mdCallee, param2Prefix); - - // System.out.println("set comp loc=" + compLocForParam2 - // + - // " to " + paramNode2); - paramNode1.setCompositeLocation(compLocForParam2); - continue; - } - } - - } - } - - // otherwise, flows between method/field locations... - callerFlowGraph.addValueFlowEdge(arg1Tuple, arg2Tuple); - System.out.println("arg1=" + arg1Tuple + " arg2=" + arg2Tuple); - - } - - } - - } - System.out.println(); + Set> pcLocTupleSet = getPCLocTupleSet(min); + for (Iterator iterator = pcLocTupleSet.iterator(); iterator.hasNext();) { + NTuple pcLocTuple = (NTuple) iterator.next(); + callerFlowGraph.addValueFlowEdge(translateToDescTuple(pcLocTuple), translatedParamTuple); } + } } - System.out.println("##\n"); + } - private NTuple translateCompositeLocationToCaller(MethodInvokeNode min, + private NTuple translateCompositeLocationToCaller(int idx, MethodInvokeNode min, CompositeLocation compLocForParam1) { + NTuple baseTuple = mapMethodInvokeNodeToBaseTuple.get(min); NTuple tuple = new NTuple(); - for (int i = 0; i < baseTuple.size(); i++) { tuple.add(baseTuple.get(i)); } @@ -3904,12 +3803,11 @@ public class LocationInference { System.out.println("SSJAVA: Constructing a sub global flow graph: " + md); GlobalFlowGraph subGlobalFlowGraph = constructSubGlobalFlowGraph(getFlowGraph(md)); - mapMethodDescriptorToSubGlobalFlowGraph.put(md, subGlobalFlowGraph); // TODO System.out.println("-add Value Flows From CalleeSubGlobalFlowGraph"); addValueFlowsFromCalleeSubGlobalFlowGraph(md, subGlobalFlowGraph); - subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); + // subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); // System.out.println("-propagate Flows From Callees With No CompositeLocation"); // propagateFlowsFromCalleesWithNoCompositeLocation(md); @@ -4037,40 +3935,6 @@ public class LocationInference { } - private void propagateFlowsFromCallees(MethodDescriptor mdCaller) { - - // the transformation for a call site propagates flows through parameters - // if the method is virtual, it also grab all relations from any possible - // callees - - Set setMethodInvokeNode = - mapMethodDescriptorToMethodInvokeNodeSet.get(mdCaller); - - if (setMethodInvokeNode != null) { - - for (Iterator iterator = setMethodInvokeNode.iterator(); iterator.hasNext();) { - MethodInvokeNode min = (MethodInvokeNode) iterator.next(); - MethodDescriptor mdCallee = min.getMethod(); - Set setPossibleCallees = new HashSet(); - if (mdCallee.isStatic()) { - setPossibleCallees.add(mdCallee); - } else { - Set calleeSet = ssjava.getCallGraph().getMethods(mdCallee); - // removes method descriptors that are not invoked by the caller - calleeSet.retainAll(mapMethodToCalleeSet.get(mdCaller)); - setPossibleCallees.addAll(calleeSet); - } - - for (Iterator iterator2 = setPossibleCallees.iterator(); iterator2.hasNext();) { - MethodDescriptor possibleMdCallee = (MethodDescriptor) iterator2.next(); - propagateFlowsToCaller(min, mdCaller, possibleMdCallee); - } - - } - } - - } - private void analyzeMethodBody(ClassDescriptor cd, MethodDescriptor md) { BlockNode bn = state.getMethodBody(md); NodeTupleSet implicitFlowTupleSet = new NodeTupleSet(); @@ -4383,7 +4247,7 @@ public class LocationInference { private void analyzeFlowIfStatementNode(MethodDescriptor md, SymbolTable nametable, IfStatementNode isn, NodeTupleSet implicitFlowTupleSet) { - System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); + // System.out.println("analyzeFlowIfStatementNode=" + isn.printNode(0)); NodeTupleSet condTupleNode = new NodeTupleSet(); analyzeFlowExpressionNode(md, nametable, isn.getCondition(), condTupleNode, null, @@ -4399,7 +4263,7 @@ public class LocationInference { // System.out.println("-newImplicitTupleSet=" + newImplicitTupleSet); if (needToGenerateInterLoc(newImplicitTupleSet)) { - + System.out.println("2"); // need to create an intermediate node for the GLB of conditional locations & implicit flows NTuple interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = newImplicitTupleSet.iterator(); idxIter.hasNext();) { @@ -4606,16 +4470,31 @@ public class LocationInference { return mapMethodDescToParamNodeFlowsToReturnValue.get(md); } - private void analyzeFlowMethodInvokeNode(MethodDescriptor md, SymbolTable nametable, + private Set> getPCLocTupleSet(MethodInvokeNode min) { + if (!mapMethodInvokeNodeToPCLocTupleSet.containsKey(min)) { + mapMethodInvokeNodeToPCLocTupleSet.put(min, new HashSet>()); + } + return mapMethodInvokeNodeToPCLocTupleSet.get(min); + } + + private void analyzeFlowMethodInvokeNode(MethodDescriptor mdCaller, SymbolTable nametable, MethodInvokeNode min, NodeTupleSet nodeSet, NodeTupleSet implicitFlowTupleSet) { + System.out.println("analyzeFlowMethodInvokeNode=" + min.printNode(0)); + + Set> pcLocTupleSet = getPCLocTupleSet(min); + for (Iterator iterator = implicitFlowTupleSet.iterator(); iterator.hasNext();) { + NTuple pcDescTuple = (NTuple) iterator.next(); + pcLocTupleSet.add(translateToLocTuple(mdCaller, pcDescTuple)); + } + mapMethodInvokeNodeToArgIdxMap.put(min, new HashMap>()); if (nodeSet == null) { nodeSet = new NodeTupleSet(); } - MethodDescriptor calleeMethodDesc = min.getMethod(); + MethodDescriptor mdCallee = min.getMethod(); NameDescriptor baseName = min.getBaseName(); boolean isSystemout = false; @@ -4623,20 +4502,27 @@ public class LocationInference { isSystemout = baseName.getSymbol().equals("System.out"); } - if (!ssjava.isSSJavaUtil(calleeMethodDesc.getClassDesc()) - && !ssjava.isTrustMethod(calleeMethodDesc) && !isSystemout) { + if (!ssjava.isSSJavaUtil(mdCallee.getClassDesc()) && !ssjava.isTrustMethod(mdCallee) + && !isSystemout) { - addMapCallerMethodDescToMethodInvokeNodeSet(md, min); + addMapCallerMethodDescToMethodInvokeNodeSet(mdCaller, min); - FlowGraph calleeFlowGraph = getFlowGraph(calleeMethodDesc); + FlowGraph calleeFlowGraph = getFlowGraph(mdCallee); Set calleeReturnSet = calleeFlowGraph.getReturnNodeSet(); - // System.out.println("-calleeReturnSet=" + calleeReturnSet); + System.out.println("---calleeReturnSet=" + calleeReturnSet); + + for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { + FlowNode calleeReturnNode = (FlowNode) iterator.next(); + NTuple calleeReturnLocTuple = + translateToLocTuple(mdCallee, calleeReturnNode.getDescTuple()); + nodeSet.addGlobalFlowTuple(calleeReturnLocTuple); + } if (min.getExpression() != null) { NodeTupleSet baseNodeSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, min.getExpression(), baseNodeSet, null, + analyzeFlowExpressionNode(mdCaller, nametable, min.getExpression(), baseNodeSet, null, implicitFlowTupleSet, false); assert (baseNodeSet.size() == 1); @@ -4649,7 +4535,7 @@ public class LocationInference { for (Iterator iterator = calleeReturnSet.iterator(); iterator.hasNext();) { FlowNode returnNode = (FlowNode) iterator.next(); NTuple returnDescTuple = returnNode.getDescTuple(); - if (returnDescTuple.startsWith(calleeMethodDesc.getThis())) { + if (returnDescTuple.startsWith(mdCallee.getThis())) { // the location type of the return value is started with 'this' // reference NTuple inFlowTuple = new NTuple(baseTuple.getList()); @@ -4661,7 +4547,7 @@ public class LocationInference { // System.out.println("inFlowSet=" + inFlowSet + " from retrunNode=" + returnNode); for (Iterator iterator2 = inFlowSet.iterator(); iterator2.hasNext();) { FlowNode inFlowNode = (FlowNode) iterator2.next(); - if (inFlowNode.getDescTuple().startsWith(calleeMethodDesc.getThis())) { + if (inFlowNode.getDescTuple().startsWith(mdCallee.getThis())) { nodeSet.addTupleSet(baseNodeSet); } } @@ -4685,16 +4571,17 @@ public class LocationInference { ExpressionNode en = min.getArg(i); int idx = i + offset; NodeTupleSet argTupleSet = new NodeTupleSet(); - analyzeFlowExpressionNode(md, nametable, en, argTupleSet, false); + analyzeFlowExpressionNode(mdCaller, nametable, en, argTupleSet, false); // if argument is liternal node, argTuple is set to NULL NTuple argTuple = new NTuple(); if (needToGenerateInterLoc(argTupleSet)) { + System.out.println("3"); NTuple interTuple = - getFlowGraph(md).createIntermediateNode().getDescTuple(); + getFlowGraph(mdCaller).createIntermediateNode().getDescTuple(); for (Iterator> idxIter = argTupleSet.iterator(); idxIter.hasNext();) { NTuple tuple = idxIter.next(); - addFlowGraphEdge(md, tuple, interTuple); + addFlowGraphEdge(mdCaller, tuple, interTuple); } argTuple = interTuple; } else if (argTupleSet.size() == 1) { @@ -4720,8 +4607,8 @@ public class LocationInference { // } if (hasInFlowTo(calleeFlowGraph, paramNode, calleeReturnSet) - || calleeMethodDesc.getModifiers().isNative()) { - addParamNodeFlowingToReturnValue(calleeMethodDesc, paramNode); + || mdCallee.getModifiers().isNative()) { + addParamNodeFlowingToReturnValue(mdCallee, paramNode); nodeSet.addTupleSet(argTupleSet); } } @@ -5079,6 +4966,7 @@ public class LocationInference { // creates edges from RHS to LHS NTuple interTuple = null; if (needToGenerateInterLoc(nodeSetRHS)) { + System.out.println("1"); interTuple = getFlowGraph(md).createIntermediateNode().getDescTuple(); } @@ -5099,6 +4987,21 @@ public class LocationInference { } } + // create global flow edges if the callee gives return value flows to the caller + if (nodeSetRHS.globalLocTupleSize() > 0) { + GlobalFlowGraph globalFlowGraph = getSubGlobalFlowGraph(md); + for (Iterator> iterator = nodeSetRHS.globalIterator(); iterator.hasNext();) { + NTuple calleeReturnLocTuple = iterator.next(); + for (Iterator> iter2 = nodeSetLHS.iterator(); iter2.hasNext();) { + NTuple callerLHSTuple = iter2.next(); + globalFlowGraph.addValueFlowEdge(calleeReturnLocTuple, + translateToLocTuple(md, callerLHSTuple)); + System.out.println("$$$ GLOBAL FLOW ADD=" + calleeReturnLocTuple + " -> " + + translateToLocTuple(md, callerLHSTuple)); + } + } + } + } else { // postinc case @@ -5248,8 +5151,10 @@ public class LocationInference { for (Iterator iterator = keySet.iterator(); iterator.hasNext();) { MethodDescriptor md = (MethodDescriptor) iterator.next(); FlowGraph fg = mapMethodDescriptorToFlowGraph.get(md); + GlobalFlowGraph subGlobalFlowGraph = getSubGlobalFlowGraph(md); try { fg.writeGraph(); + subGlobalFlowGraph.writeGraph("_SUBGLOBAL"); } catch (IOException e) { e.printStackTrace(); } diff --git a/Robust/src/Analysis/SSJava/NodeTupleSet.java b/Robust/src/Analysis/SSJava/NodeTupleSet.java index 62c313b7..c8e80cb7 100644 --- a/Robust/src/Analysis/SSJava/NodeTupleSet.java +++ b/Robust/src/Analysis/SSJava/NodeTupleSet.java @@ -10,10 +10,13 @@ import IR.Descriptor; public class NodeTupleSet { - private List> list; + private ArrayList> list; + + private ArrayList> globalLocTupleList; public NodeTupleSet() { list = new ArrayList>(); + globalLocTupleList = new ArrayList>(); } public void addTuple(NTuple tuple) { @@ -28,6 +31,14 @@ public class NodeTupleSet { list.add(tuple); } + public void addGlobalFlowTuple(NTuple tuple) { + globalLocTupleList.add(tuple); + } + + public Iterator> globalIterator() { + return globalLocTupleList.iterator(); + } + public void removeTuple(NTuple tuple) { list.remove(tuple); } @@ -37,7 +48,13 @@ public class NodeTupleSet { } public String toString() { - return list.toString(); + String str = list.toString(); + + if (globalLocTupleList.size() > 0) { + str += " GlobalFlow=" + globalLocTupleList.toString(); + } + + return str; } public Set> getSet() { @@ -62,4 +79,23 @@ public class NodeTupleSet { public void clear() { list.clear(); } + + public int globalLocTupleSize() { + return globalLocTupleList.size(); + } + + private void setGlobalLocTupleList(ArrayList> in) { + globalLocTupleList = in; + } + + private void setDescTupleList(ArrayList> in) { + list = in; + } + + public NodeTupleSet clone() { + NodeTupleSet set = new NodeTupleSet(); + set.setDescTupleList((ArrayList>) list.clone()); + set.setGlobalLocTupleList((ArrayList>) globalLocTupleList.clone()); + return set; + } } diff --git a/Robust/src/Benchmarks/SSJava/MP3Decoder/Equalizer.java b/Robust/src/Benchmarks/SSJava/MP3Decoder/Equalizer.java index f5aea8a6..8ba6180d 100644 --- a/Robust/src/Benchmarks/SSJava/MP3Decoder/Equalizer.java +++ b/Robust/src/Benchmarks/SSJava/MP3Decoder/Equalizer.java @@ -31,7 +31,7 @@ * @author MDM */ @LATTICE("B