Java 类soot.jimple.DefinitionStmt 实例源码

@Override
protected void internalTransform(Body body, String phaseName, Map<String, String> options) {
    // Do not instrument methods in framework classes
    if (!canInstrumentMethod(body.getMethod()))
        return;

    instrumentInfoAboutNonAPICall(body);

    //important to use snapshotIterator here
    Iterator<Unit> iterator = body.getUnits().snapshotIterator();
    while(iterator.hasNext()){
        Unit unit = iterator.next();
        if(unit instanceof ReturnStmt || unit instanceof ReturnVoidStmt)
            instrumentInfoAboutReturnStmt(body, unit);
        else if(unit instanceof DefinitionStmt || unit instanceof InvokeStmt)
            instrumentInfoAboutNonApiCaller(body, unit);
        else if(unit instanceof IfStmt)
            instrumentEachBranchAccess(body, (IfStmt)unit);
    }               
}

public static void removeUnit(Body b, Unit u) {
    LocalGenerator lg = new LocalGenerator(b);
    if (u instanceof DefinitionStmt) {
        DefinitionStmt def = (DefinitionStmt) u;
        Type t = def.getRightOp().getType();
        if (!(t instanceof PrimType)) {
            Local l_obj = lg.generateLocal(RefType.v("java.lang.Object"));
            Local l_type = lg.generateLocal(t);
            Unit u1 = Jimple.v().newAssignStmt(l_obj,
                    Jimple.v().newNewExpr(RefType.v("java.lang.Object")));
            Unit u2 = Jimple.v().newAssignStmt(l_type, Jimple.v().newCastExpr(l_obj, t));
            def.getRightOpBox().setValue(l_type);
            b.getUnits().insertBefore(u1, u);
            b.getUnits().insertBefore(u2, u);
            return;
        }
    }
    b.getUnits().remove(u);
}

void handleAssign(DefinitionStmt stmt) {
    Value lval = stmt.getLeftOp();
    Value rval = stmt.getRightOp();
    Variable rvar;
    if (lval instanceof Local) {
        rvar = getLocalVariable((Local)lval);
    } else {
        rvar = jt.makeVariable(rval);
    }
    et.translateExpr(rvar, stmt.getRightOpBox());
    if (lval instanceof ArrayRef) {
        notSupported("We do not support arrays");
    } else if (lval instanceof FieldRef) {
        notSupported("We do not support field references");
    }
}

private void handleRefTypeAssignment(DefinitionStmt assignStmt,
        AnalysisInfo rhsInfo, AnalysisInfo out) {
    Value left = assignStmt.getLeftOp();
    Value right = assignStmt.getRightOp();

    //unbox casted value
    if(right instanceof JCastExpr) {
        JCastExpr castExpr = (JCastExpr) right;
        right = castExpr.getOp();
    }

    // An assignment invalidates any assumptions of null/non-null for lhs
    // We COULD be more accurate by assigning those assumptions to the rhs prior to this statement
    rhsInfo.put(right,BOTTOM);

    //assign from rhs to lhs
    out.put(left,rhsInfo.get(right));
}

protected void flowThrough(HashMap<Local,Set<NewExpr>> in, Unit unit,
        HashMap<Local,Set<NewExpr>> out)
{
    Stmt    s   = (Stmt)    unit;

    out.clear();
    out.putAll(in);

    if (s instanceof DefinitionStmt) {
        DefinitionStmt ds = (DefinitionStmt) s;
        Value lhs = ds.getLeftOp();
        Value rhs = ds.getRightOp();
        if (lhs instanceof Local) {
            HashSet<NewExpr> lv = new HashSet<NewExpr>();
            out.put((Local) lhs, lv);
            if (rhs instanceof NewExpr) {
                lv.add((NewExpr) rhs);
            } else if (rhs instanceof Local) {
                lv.addAll(in.get(rhs));
            } else lv.add(UNKNOWN);
        }
    }
}

public void inASTMethodNode(ASTMethodNode node){
    Stmt s = ofInterest.get_Stmt();
    //check this is a definition
    if(! (s instanceof DefinitionStmt )){
        possible=false;
        return;
    }

    Value defined = ((DefinitionStmt)s).getLeftOp();
    if(!(defined instanceof Local)){
        possible=false;
        return;
    }

    //check that this is a local defined in this method
    //its a sanity check
    List declaredLocals = node.getDeclaredLocals();
    if(!declaredLocals.contains(defined)){
        possible=false;
        return;
    }
    definedLocal = (Local)defined;
}

private void convertVarStoreInsn(VarInsnNode insn) {
    int op = insn.getOpcode();
    boolean dword = op == LSTORE || op == DSTORE;
    StackFrame frame = getFrame(insn);
    Operand opr = dword ? popDual() : pop();
    Local local = getLocal(insn.var);
    if (!units.containsKey(insn)) {
        DefinitionStmt as = Jimple.v().newAssignStmt(local, opr.stackOrValue());
        opr.addBox(as.getRightOpBox());
        frame.boxes(as.getRightOpBox());
        frame.in(opr);
        setUnit(insn, as);
    } else {
        frame.mergeIn(opr);
    }
    assignReadOps(local);
}

private void convertLabel(LabelNode ln) {
    if (!trapHandlers.containsKey(ln))
        return;
    StackFrame frame = getFrame(ln);
    Operand[] out = frame.out();
    Operand opr;
    if (out == null) {
        CaughtExceptionRef ref = Jimple.v().newCaughtExceptionRef();
        Local stack = newStackLocal();
        DefinitionStmt as = Jimple.v().newIdentityStmt(stack, ref);
        opr = new Operand(ln, ref);
        opr.stack = stack;
        frame.out(opr);
        setUnit(ln, as);
    } else {
        opr = out[0];
    }
    push(opr);
}

private void checkAccessStmt(Stmt sootStmt, SootMethod currentMethod)
{
    if(sootStmt.containsFieldRef())
    {
        SootField accessField = sootStmt.getFieldRef().getField();
        boolean isWrite = (((DefinitionStmt)sootStmt).getLeftOp() instanceof FieldRef);
        boolean isStatic = (sootStmt.getFieldRef() instanceof StaticFieldRef);
        Value object = isStatic ? NullConstant.v() : ((InstanceFieldRef)sootStmt.getFieldRef()).getBase();

        String methodSig = currentMethod.getSignature();

        List<Value> currentLocks = new ArrayList<Value>(lockStack);

        System.out.println(isWrite+" access on "+isStatic+" field "+accessField+" of "+object+" in "+methodSig+" with "+currentLocks.size()+" locks");

        if(!variableAccesses.containsKey(methodSig))
        {
            variableAccesses.put(methodSig, new HashSet<VariableAccess>());
        }
        variableAccesses.get(currentMethod.getSignature()).add(
                new VariableAccess(accessField, sootStmt, currentMethod, isWrite, isStatic, currentLocks));
    }
}

void getIntConstantsFromLocal(SimpleLocalDefs sld, Local l, Unit u, List<String> whats) throws IOException {
    Iterator<Unit> iter = sld.getDefsOfAt(l, u).iterator();
    while (iter.hasNext()) {
        Unit def = iter.next();
        if (! (def instanceof DefinitionStmt)) continue;
        DefinitionStmt assign = (DefinitionStmt) def;
        Value rightOp = assign.getRightOp();
        if (rightOp instanceof IntConstant) {
            whats.add(rightOp.toString());
        } else if (rightOp instanceof ParameterRef){
            whats.add(rightOp.toString());
        } else if (rightOp instanceof Local) {
            getIntConstantsFromLocal(sld, (Local)rightOp, def, whats);
            print("getIntConstantsFromLocal -> local");
        } else {
            print("???"+def.toString());
        }
    }
}

@Override
public KillGenInfo propagateCallToReturnFlow(Trackable trackable, Stmt callSite) {
    if (!(callSite instanceof DefinitionStmt))
        return identity();

    Taint taint = (Taint) trackable;
    DefinitionStmt defStmt = (DefinitionStmt) callSite;
    if (!defStmt.getLeftOp().equals(taint.value))
        return identity();

    if (defStmt.getLeftOp() instanceof Local) {
        return kill();
    } else {
        // if the stmt defines a local then we know that this value we
        // definitely overwritten;
        // if it does not define a local (but, say, a FieldRef) then the
        // value *may* have been
        // overwritten; hence we need to track the source, too
        return identity();
    }
}

/***** API calls *****/

    // Sanitizer for user study. Kill the parameter and its aliases
    private boolean applySanitizer(Unit call, FlowAbstraction source) {

        // Call itself
        Stmt stmt = (Stmt) call;
        final String target = stmt.getInvokeExpr().getMethod().getSignature();
        final List<Value> args = stmt.getInvokeExpr().getArgs();

        if (!target.equals("<sanitizers.Sanitizer: void sanitize(java.lang.Object)>"))
            return false;

        if (killforSanit(call, args.get(0), source))
            return true;

        // Case of valueOf for primitive types
        // a = Integer.valueOf(b); and sanit(a) -> must also treat aliases of b
        List<Unit> predecessors = icfg.getPredsOf(call);
        for (Unit predecessor : predecessors) {
            if (predecessor instanceof DefinitionStmt) {
                DefinitionStmt def = (DefinitionStmt) predecessor;
                if (def.getLeftOp().equals(args.get(0)) && def.getRightOp() instanceof StaticInvokeExpr) {
                    InvokeExpr expr = (StaticInvokeExpr) def.getRightOp();
                    final SootMethod method = expr.getMethod();
                    if (method.getName().equals("valueOf") && expr.getArgCount() == 1
                            && method.getDeclaringClass().getType().equals(method.getReturnType())
                            && isPrimitiveType(method.getReturnType())) {
                        if (killforSanit(predecessor, expr.getArg(0), source))
                            return true;
                    }
                }
            }
        }
        return false;
    }

/**
 * Checks whether the given method is a library stub method
 * @param method The method to check
 * @return True if the given method is an Android library stub, false
 * otherwise
 */
private boolean methodIsAndroidStub(SootMethod method) {        
    if (!(Options.v().src_prec() == Options.src_prec_apk
            && method.getDeclaringClass().isLibraryClass()
            && SystemClassHandler.isClassInSystemPackage(
                    method.getDeclaringClass().getName())))
        return false;

    // Check whether there is only a single throw statement
    for (Unit u : method.getActiveBody().getUnits()) {
        if (u instanceof DefinitionStmt) {
            DefinitionStmt defStmt = (DefinitionStmt) u;
            if (!(defStmt.getRightOp() instanceof ThisRef)
                    && !(defStmt.getRightOp() instanceof ParameterRef)
                    && !(defStmt.getRightOp() instanceof NewExpr))
                return false;
        }
        else if (u instanceof InvokeStmt) {
            InvokeStmt stmt = (InvokeStmt) u;

            // Check for exception constructor invocations
            SootMethod callee = stmt.getInvokeExpr().getMethod();
            if (!callee.getSubSignature().equals("void <init>(java.lang.String)"))
                // Check for super class constructor invocation
                if (!(method.getDeclaringClass().hasSuperclass()
                        && callee.getDeclaringClass() == method.getDeclaringClass().getSuperclass()
                        && callee.getName().equals("<init>")))
                    return false;
        }
        else if (!(u instanceof ThrowStmt))
            return false;
    }
    return true;
}

@Override
public SourceInfo getSourceInfo(Stmt sCallSite, InterproceduralCFG<Unit, SootMethod> cfg) {
    if (sCallSite.containsInvokeExpr()
            && sCallSite instanceof DefinitionStmt
            && sCallSite.getInvokeExpr().getMethod().getName().equals("getSecret")) {
        AccessPath ap = new AccessPath(((DefinitionStmt) sCallSite).getLeftOp(), true);
        return new SourceInfo(ap);
    }
    return null;
}

@Override
public SourceInfo getSourceInfo(Stmt sCallSite, InterproceduralCFG<Unit, SootMethod> cfg) {
    if (sCallSite.containsInvokeExpr()
            && sCallSite instanceof DefinitionStmt
            && (sCallSite.getInvokeExpr().getMethod().getName().equals("getSecret")
                    || (sCallSite.getInvokeExpr().getMethod().getName().equals("getSecret2")))) {
        AccessPath ap = new AccessPath(((DefinitionStmt) sCallSite).getLeftOp(), true);
        return new SourceInfo(ap);
    }
    return null;
}

@Override
public SourceInfo getSourceInfo(Stmt sCallSite, InterproceduralCFG<Unit, SootMethod> cfg) {
    if (sCallSite.containsInvokeExpr()
            && sCallSite instanceof DefinitionStmt
            && sCallSite.getInvokeExpr().getMethod().getName().equals("getSecret")) {
        AccessPath ap = new AccessPath(((DefinitionStmt) sCallSite).getLeftOp(), false);
        return new SourceInfo(ap);
    }
    return null;
}

private void handleRefTypeAssignment(DefinitionStmt assignStmt, AnalysisInfo out) {
    Value left = assignStmt.getLeftOp();
    Value right = assignStmt.getRightOp();

    //unbox casted value
    if(right instanceof JCastExpr) {
        JCastExpr castExpr = (JCastExpr) right;
        right = castExpr.getOp();
    }

    //if we have a definition (assignment) statement to a ref-like type, handle it,
    if ( isAlwaysNonNull(right)
    || right instanceof NewExpr || right instanceof NewArrayExpr
    || right instanceof NewMultiArrayExpr || right instanceof ThisRef
    || right instanceof StringConstant || right instanceof ClassConstant
    || right instanceof CaughtExceptionRef) {
        //if we assign new... or @this, the result is non-null
        out.put(left,NON_NULL);
    } else if(right==NullConstant.v()) {
        //if we assign null, well, it's null
        out.put(left, NULL);
    } else if(left instanceof Local && right instanceof Local) {
        out.put(left, out.get(right));
    } else {
        out.put(left, TOP);
    }
}

public TypeResolver(JimpleBody jb)
{
    this.jb = jb;

    this.assignments = new ArrayList<DefinitionStmt>();
    this.depends = new HashMap<Local, BitSet>();
    for ( Local v : this.jb.getLocals() )
        this.addLocal(v);
    this.initAssignments();
}

/**
 * Checks whether the given local is guaranteed to be always null at the
 * given statement
 * @param s The statement at which to check the local
 * @param base The local to check
 * @param defs The definition analysis object to use for the check
 * @return True if the given local is guaranteed to always be null at the
 * given statement, otherwise false
 */
private boolean isAlwaysNullBefore(Stmt s, Local base, LocalDefs defs) {
    List<Unit> baseDefs = defs.getDefsOfAt(base, s);
    if (baseDefs.isEmpty())
        return true;

    for (Unit u : baseDefs) {
        if (!(u instanceof DefinitionStmt))
            return false;
        DefinitionStmt defStmt = (DefinitionStmt) u;
        if (defStmt.getRightOp() != NullConstant.v())
            return false;
    }
    return true;
}

/**
 * Checks whether the given local has been redefined between the original
 * definition unitDef and the use unitUse.
 * @param l The local for which to check for redefinitions
 * @param unitUse The unit that uses the local
 * @param unitDef The unit that defines the local
 * @param graph The unit graph to use for the check
 * @return True if there is at least one path between unitDef and unitUse on
 * which local l gets redefined, otherwise false 
 */
   private boolean isRedefined(Local l, Unit unitUse, AssignStmt unitDef,
        UnitGraph graph) {
    List<Unit> workList = new ArrayList<Unit>();
    workList.add(unitUse);

    Set<Unit> doneSet = new HashSet<Unit>();

    // Check for redefinitions of the local between definition and use
    while (!workList.isEmpty()) {
        Unit curStmt = workList.remove(0);
        if (!doneSet.add(curStmt))
            continue;

        for (Unit u : graph.getPredsOf(curStmt)) {
            if (u != unitDef) {
                if (u instanceof DefinitionStmt) {
                    DefinitionStmt defStmt = (DefinitionStmt) u;
                    if (defStmt.getLeftOp() == l)
                        return true;
                }
                workList.add(u);
            }
        }
    }
    return false;
}

public void inDefinitionStmt(DefinitionStmt s){
Value leftOp = s.getLeftOp();
if(leftOp instanceof FieldRef){
    //System.out.println("leftOp is a fieldRef:"+s);
    SootField field = ((FieldRef)leftOp).getField();
    //check if this is a final field
    if(field.isFinal()){
    //System.out.println("the field is a final variable");
    finalFieldDefined=true;
    }
}

   }

public void inDefinitionStmt(DefinitionStmt s){
    if(definedLocal==null)
        return;

    Value defined = (s).getLeftOp();
    if(!(defined instanceof Local)){
        return;
    }

    if(defined.equals(definedLocal)){
        //the local of interest is being defined

        //if this is the augmentedStmt of interest set possible to true if not already seen
        if(s.equals(ofInterest.get_Stmt())){
            //it is the stmt of interest
            if(seenBefore==0)
                possible=true;
            else
                possible=false;
        }
        else{
            //its a definition of the local of interest but not by the stmt of interest
            seenBefore++;
        }

    }   
}

public boolean isInSequenceAssignment(Stmt s, Value leftOp, int index){
    //DEBUG=false;
    if(!(s instanceof DefinitionStmt))
        return false;

    DefinitionStmt ds = (DefinitionStmt)s;
    Value leftValue = ds.getLeftOp();
    if(! (leftValue instanceof ArrayRef))
        return false;

    if(DEBUG){
        System.out.println("Stmt number "+index + " is an array ref assignment"+leftValue);
        System.out.println("Array is"+leftOp);
    }

    ArrayRef leftRef = (ArrayRef)leftValue;
    if(! (leftOp.equals(leftRef.getBase()))){
        if(DEBUG)
            System.out.println("Not assigning to same array");
        return false;
    }

    if( ! (leftRef.getIndex() instanceof IntConstant)){
        if(DEBUG)
            System.out.println("Cant determine index of assignment");
        return false;
    }

    IntConstant leftIndex = (IntConstant)leftRef.getIndex();
    if(leftIndex.value != index){
        if(DEBUG)
            System.out.println("Out of order assignment");
        return false;
    }

    return true;
}

/**
 * Return all possible values for an integer local variable.
 * 
 * @param start The statement where the analysis should start.
 * @param local The local variable whose values we are looking for.
 * @param visitedStmts The set of visited statement.
 * @return The set of possible values for the local variable.
 */
private Set<Object> findIntAssignmentsForLocal(Stmt start, Local local, Set<Stmt> visitedStmts) {
  List<DefinitionStmt> assignStmts =
      findAssignmentsForLocal(start, local, true, new HashSet<Pair<Unit, Local>>());
  Set<Object> result = new HashSet<>(assignStmts.size());

  for (DefinitionStmt assignStmt : assignStmts) {
    Value rhsValue = assignStmt.getRightOp();
    if (rhsValue instanceof IntConstant) {
      result.add(((IntConstant) rhsValue).value);
    } else if (rhsValue instanceof LongConstant) {
      result.add(((LongConstant) rhsValue).value);
    } else if (rhsValue instanceof ParameterRef) {
      ParameterRef parameterRef = (ParameterRef) rhsValue;
      Iterator<Edge> edges =
          Scene.v().getCallGraph()
              .edgesInto(AnalysisParameters.v().getIcfg().getMethodOf(assignStmt));
      while (edges.hasNext()) {
        Edge edge = edges.next();
        InvokeExpr invokeExpr = edge.srcStmt().getInvokeExpr();
        Value argValue = invokeExpr.getArg(parameterRef.getIndex());
        if (argValue instanceof IntConstant) {
          result.add(((IntConstant) argValue).value);
        } else if (argValue instanceof LongConstant) {
          result.add(((LongConstant) argValue).value);
        } else if (argValue instanceof Local) {
          Set<Object> newResults =
              findIntAssignmentsForLocal(edge.srcStmt(), (Local) argValue, visitedStmts);
          result.addAll(newResults);
        } else {
          result.add(TOP_VALUE);
        }
      }
    } else {
      return Collections.singleton((Object) TOP_VALUE);
    }
  }

  return result;
}

/**
 * Return all possible values for an integer local variable.
 * 
 * @param start The statement where the analysis should start.
 * @param local The local variable whose values we are looking for.
 * @param visitedStmts The set of visited statement.
 * @return The set of possible values for the local variable.
 */
private Set<Object> findIntAssignmentsForLocal(Stmt start, Local local, Set<Stmt> visitedStmts) {
  List<DefinitionStmt> assignStmts =
      findAssignmentsForLocal(start, local, true, new HashSet<Pair<Unit, Local>>());
  Set<Object> result = new HashSet<>(assignStmts.size());

  for (DefinitionStmt assignStmt : assignStmts) {
    Value rhsValue = assignStmt.getRightOp();
    if (rhsValue instanceof IntConstant) {
      result.add(((IntConstant) rhsValue).value);
    } else if (rhsValue instanceof LongConstant) {
      result.add(((LongConstant) rhsValue).value);
    } else if (rhsValue instanceof ParameterRef) {
      ParameterRef parameterRef = (ParameterRef) rhsValue;
      Iterator<Edge> edges =
          Scene.v().getCallGraph()
              .edgesInto(AnalysisParameters.v().getIcfg().getMethodOf(assignStmt));
      while (edges.hasNext()) {
        Edge edge = edges.next();
        InvokeExpr invokeExpr = edge.srcStmt().getInvokeExpr();
        Value argValue = invokeExpr.getArg(parameterRef.getIndex());
        if (argValue instanceof IntConstant) {
          result.add(((IntConstant) argValue).value);
        } else if (argValue instanceof LongConstant) {
          result.add(((LongConstant) argValue).value);
        } else if (argValue instanceof Local) {
          Set<Object> newResults =
              findIntAssignmentsForLocal(edge.srcStmt(), (Local) argValue, visitedStmts);
          result.addAll(newResults);
        } else {
          result.add(TOP_VALUE);
        }
      }
    } else {
      return Collections.singleton((Object) TOP_VALUE);
    }
  }

  return result;
}

void getStringConstantsFromLocal(SimpleLocalDefs sld, Local l, Unit u, HashMap<String,String> perms) throws IOException {
    Iterator<Unit> iter = sld.getDefsOfAt(l, u).iterator();
    while (iter.hasNext()) {
        Unit def = iter.next();
        if (! (def instanceof DefinitionStmt)) continue;
        DefinitionStmt assign = (DefinitionStmt) def;
        Value rightOp = assign.getRightOp();
        if (rightOp instanceof StringConstant) {
            int i=0;
            boolean found = false;
            while(i<numPerm && !found) {
                if (rightOp.toString().equals("\""+permissions[i]+"\"")) {
                    found = true;
                    if (u instanceof DefinitionStmt && !isKnownCheck(u.toString())) {
                        perms.put(permissions[i], "NOTDIRECTUSE");
                    } else {
                        perms.put(permissions[i], "");
                    }
                }
                i++;
            }
        } else if (rightOp instanceof Local) {
            getStringConstantsFromLocal(sld, (Local)rightOp, def, perms);
        } else {
            //irrelevant types
        }
    }
}

/**
 * Analyze a statement and computes an abstract value representing what it produces. (Value
 * assigned for an assign) and call approximation for an invoke.
 * @param u
 * @param seen
 * @return
 */
public AbsValue analyze_single (Unit u, Set<Unit> seen) {
    if (u instanceof InvokeStmt) {
        ProgramSpy.debug("************ INVOKE ********");
        InvokeExpr e = ((InvokeStmt) u).getInvokeExpr();
        return analyzeInvoke(e,u,seen);
    } else if (u instanceof DefinitionStmt) {
        ProgramSpy.debug("************ DEFINITION "+ u + " ********");
        Value r = ((DefinitionStmt)u).getRightOp ();
        return analyze_expr(r,  u, seen);
    } else {
        ProgramSpy.debug("************ OTHER STMT ********");
        return new UnknownValue (u.toString());
    }
}

@Override
public KillGenInfo propagateNormalFlow(Trackable trackable, Unit curr, Unit succ) {
    if (!(curr instanceof DefinitionStmt))
        return identity();

    Taint taint = (Taint) trackable;
    DefinitionStmt defStmt = (DefinitionStmt) curr;
    // extract "base" locals of array refs
    Value leftBase = AnalysisUtil.getBackwardsBase(defStmt.getLeftOp());
    Value rightBase = AnalysisUtil.getBackwardsBase(defStmt.getRightOp());

    if (!AnalysisUtil.maybeSameLocation(taint.value, leftBase))
        return identity();
    if (leftBase.equals(rightBase)) // x = x; or x[i] = x[j]; -> do nothing
        return identity();

    if (defStmt.getLeftOp() instanceof Local) { // Local
        if (defStmt.getRightOp() instanceof Constant || !AnalysisUtil.isAssignable(taint.type, rightBase.getType()))
            return kill();

        return propagate(taint.createAlias(rightBase, curr));
    } else { // Field
        if (defStmt.getRightOp() instanceof Constant || !AnalysisUtil.isAssignable(taint.type, rightBase.getType()))
            return identity();

        // if the stmt defines a local then we know that this value we
        // definitely overwritten;
        // if it does not define a local (but, say, a FieldRef) then the
        // value *may* have been
        // overwritten; hence we need to track the source, too
        return gen(taint.createAlias(rightBase, curr));
    }
}

@Override
public KillGenInfo propagateNormalFlow(Trackable trackable, Unit curr, Unit succ) {
    Taint taint = (Taint) trackable;
    if (curr instanceof DefinitionStmt) {
        DefinitionStmt defStmt = (DefinitionStmt) curr;

        Value rightBase = AnalysisUtil.getForwardsBase(defStmt.getRightOp());
        Value leftBase = AnalysisUtil.getForwardsBase(defStmt.getLeftOp());

        if (leftBase.equals(rightBase)) // x = x; or x[i] = x[j]; -> do
                                        // nothing
            return identity();

        // kill the LHS if it is assigned another value
        Value left = defStmt.getLeftOp();
        if (left instanceof Local && taint.value.equals(left)) {
            return kill();
        }

        if (rightBase instanceof CastExpr) {
            CastExpr castExpr = (CastExpr) rightBase;
            if (AnalysisUtil.maybeSameLocation(taint.value, castExpr.getOp())) {
                if (AnalysisUtil.isAssignable(taint.type, leftBase.getType())) {
                    return gen(taint.createAlias(leftBase, curr));
                } else {
                    return identity();
                }
            }
        }

        // at assignments, propagate taint from right to left
        if (taint.value.equivTo(rightBase) || AnalysisUtil.maybeSameLocation(taint.value, rightBase)) {
            return gen(taint.createAlias(leftBase, curr));
        }
    }
    return identity();
}

private void instrumentInfoAboutNonApiCaller(Body body, Unit unit)
{   
    //our instrumented code
    if(unit.hasTag(InstrumentedCodeTag.name))
        return;

    InvokeExpr invokeExpr = null;
    if(unit instanceof DefinitionStmt)
    {
        DefinitionStmt defStmt = (DefinitionStmt)unit;
        if(defStmt.containsInvokeExpr())
        {
            invokeExpr = defStmt.getInvokeExpr();
        }
    }                   
    else if(unit instanceof InvokeStmt)
    {
        InvokeStmt invokeStmt = (InvokeStmt)unit;
        invokeExpr = invokeStmt.getInvokeExpr();
    }               

    if(invokeExpr != null)
    {           
        if(!UtilInstrumenter.isApiCall(invokeExpr))
        {
            String invokeExprMethodSignature = invokeExpr.getMethod().getSignature();

            List<Value> parameter = invokeExpr.getArgs();
            List<Unit> generated = new ArrayList<Unit>();
            Pair<Value, List<Unit>> arrayRefAndInstrumentation = UtilInstrumenter.generateParameterArray(parameter, body);

            List<Unit> generatedArrayInstrumentation = arrayRefAndInstrumentation.getSecond();
            Value arrayRef = arrayRefAndInstrumentation.getFirst();

            Unit generatedInvokeStmt = UtilInstrumenter.makeJimpleStaticCallForPathExecution("logInfoAboutNonApiMethodCaller",  
                    RefType.v("java.lang.String"), StringConstant.v(body.getMethod().getSignature()),
                    RefType.v("java.lang.String"), StringConstant.v(invokeExprMethodSignature),
                    UtilInstrumenter.getParameterArrayType(), (parameter.isEmpty())? NullConstant.v() : arrayRef);
            generatedInvokeStmt.addTag(new InstrumentedCodeTag());
            generated.addAll(generatedArrayInstrumentation);
            generated.add(generatedInvokeStmt);

            body.getUnits().insertBefore(generated, unit);
        }
    }       
}

public Map<Unit, Set<Pair<Value, Set<DefinitionStmt>>>> initialSeeds() {
    return DefaultSeeds.make(
            Collections.singleton(Scene.v().getEntryPoints().get(0).getActiveBody()
                    .getUnits().getFirst()), zeroValue());
}

public Pair<Value, Set<DefinitionStmt>> createZeroValue() {
    System.err.println("calling createZeroValue");
    return new Pair<Value, Set<DefinitionStmt>>(new JimpleLocal("<<zero>>",
            NullType.v()), Collections.<DefinitionStmt> emptySet());
}

public Map<Unit, Set<Pair<Value, Set<DefinitionStmt>>>> initialSeeds() {
    return DefaultSeeds.make(Collections.singleton(Scene.v().getEntryPoints().get(0).getActiveBody().getUnits().getFirst()), zeroValue());
}

public Pair<Value, Set<DefinitionStmt>> createZeroValue() {
    return new Pair<Value, Set<DefinitionStmt>>(new JimpleLocal("<<zero>>", NullType.v()), Collections.<DefinitionStmt> emptySet());
}

public ArrayIndexLivenessAnalysis(DirectedGraph dg, 
                                  boolean takeFieldRef, 
                                  boolean takeArrayRef,
                                  boolean takeCSE,
                                  boolean takeRectArray)
{
    super(dg);

    fieldin = takeFieldRef;
    arrayin = takeArrayRef;
    csin = takeCSE;
    rectarray = takeRectArray;

    if (Options.v().debug()) 
        G.v().out.println("Enter ArrayIndexLivenessAnalysis");

    eug = (ExceptionalUnitGraph)dg;
    retrieveAllArrayLocals(eug.getBody(), fullSet);

    /* compute gen set, kill set, and condition set */
    genOfUnit = new HashMap<Stmt, HashSet<Object>>(eug.size()*2+1);
    absGenOfUnit = new HashMap<Stmt, HashSet<Value>>(eug.size()*2+1);
    killOfUnit = new HashMap<Stmt, HashSet<Value>>(eug.size()*2+1);
    conditionOfGen = new HashMap<Stmt, HashSet<Value>>(eug.size()*2+1);

    if (fieldin)
    {
        localToFieldRef = new HashMap<Object, HashSet<Value>>();
        fieldToFieldRef = new HashMap<Object, HashSet<Value>>();
        allFieldRefs = new HashSet<Value>();
    }

    if (arrayin)
    {
        localToArrayRef = new HashMap();
        allArrayRefs = new HashSet();

        killArrayRelated = new HashMap<DefinitionStmt, Value>();
        killAllArrayRef = new HashMap<DefinitionStmt, Boolean>();

        if (rectarray)
        {
            multiarraylocals = new HashSet<Local>();
            retrieveMultiArrayLocals(eug.getBody(), multiarraylocals);
        }
    }

    if (csin)
    {
        localToExpr = new HashMap<Value, HashSet<Value>>();
    }

    getAllRelatedMaps(eug.getBody());

    getGenAndKillSet(eug.getBody(), absGenOfUnit, genOfUnit, killOfUnit, conditionOfGen);

    doAnalysis();

    if (Options.v().debug()) 
        G.v().out.println("Leave ArrayIndexLivenessAnalysis");
}

private void getGenAndKillSet(Body body, HashMap<Stmt, HashSet<Value>> absgen, HashMap<Stmt, HashSet<Object>> gen, HashMap<Stmt, HashSet<Value>> kill, HashMap<Stmt, HashSet<Value>> condition)
{
    for (Unit u : body.getUnits())
    {
        Stmt stmt = (Stmt)u;

        HashSet<Object> genset = new HashSet<Object>();
        HashSet<Value> absgenset = new HashSet<Value>();
        HashSet<Value> killset = new HashSet<Value>();
        HashSet<Value> condset = new HashSet<Value>();

        if (stmt instanceof DefinitionStmt)
        {
            getGenAndKillSetForDefnStmt((DefinitionStmt)stmt, absgen,
                                        genset, absgenset, 
                                        killset, condset);

        }
        else if (stmt instanceof IfStmt)
        {
            /* if one of condition is living, than other one is live. */
            Value cmpcond = ((IfStmt)stmt).getCondition();

            if (cmpcond instanceof ConditionExpr)
            {
                Value op1 = ((ConditionExpr)cmpcond).getOp1();
                Value op2 = ((ConditionExpr)cmpcond).getOp2();

                if (fullSet.contains(op1) && fullSet.contains(op2))
                {
                    condset.add(op1);
                    condset.add(op2);

                    genset.add(op1);
                    genset.add(op2);
                }
            }
        }

        if (genset.size() != 0)
            gen.put(stmt, genset);
        if (absgenset.size() != 0)
            absgen.put(stmt, absgenset);
        if (killset.size() != 0)
            kill.put(stmt, killset);
        if (condset.size() != 0)
            condition.put(stmt, condset);
    }
}

private void initAssignments()
{
    for ( Unit stmt : this.jb.getUnits() )
        if ( stmt instanceof DefinitionStmt )
            this.initAssignment((DefinitionStmt)stmt);
}

private void split_new()
{       
    LocalDefs defs = LocalDefs.Factory.newLocalDefs(jb);
    PatchingChain<Unit> units = this.jb.getUnits();
    Stmt[] stmts = new Stmt[units.size()];

    units.toArray(stmts);

    for ( Stmt stmt : stmts )
    {
        if ( stmt instanceof InvokeStmt )
        {
            InvokeStmt invoke = (InvokeStmt)stmt;

            if ( invoke.getInvokeExpr() instanceof SpecialInvokeExpr )
            {
                SpecialInvokeExpr special
                    = (SpecialInvokeExpr)invoke.getInvokeExpr();

                if ( special.getMethodRef().name().equals("<init>") )
                {
                    List<Unit> deflist = defs.getDefsOfAt(
                        (Local)special.getBase(), invoke);

                    while ( deflist.size() == 1 )
                    {
                        Stmt stmt2 = (Stmt)deflist.get(0);

                        if ( stmt2 instanceof AssignStmt )
                        {
                            AssignStmt assign = (AssignStmt)stmt2;

                            if ( assign.getRightOp() instanceof Local )
                            {
                                deflist = defs.getDefsOfAt(
                                    (Local)assign.getRightOp(), assign);
                                continue;
                            }
                            else if ( assign.getRightOp()
                                instanceof NewExpr )
                            {
                                Local newlocal = Jimple.v().newLocal(
                                    "tmp", null);
                                newlocal.setName("tmp$" + System.identityHashCode(newlocal));
                                this.jb.getLocals().add(newlocal);

                                special.setBase(newlocal);

                                DefinitionStmt assignStmt
                                    = Jimple.v().newAssignStmt(
                                    assign.getLeftOp(), newlocal);
                                Unit u = Util.findLastIdentityUnit(jb, assign);
                                units.insertAfter(assignStmt, u);
                                assign.setLeftOp(newlocal);

                                this.addLocal(newlocal);
                                this.initAssignment(assignStmt);
                            }
                        }
                        break;
                    }
                }
            }
        }
    }
}

public Map<Unit, Set<Pair<Value, Set<DefinitionStmt>>>> initialSeeds() {
    return DefaultSeeds.make(Collections.singleton(Scene.v().getMainMethod().getActiveBody().getUnits().getFirst()), zeroValue());
}