<commit_before>/*******************************************************************************
 * Copyright (c) 2012 Secure Software Engineering Group at EC SPRIDE.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the GNU Lesser Public License v2.1
 * which accompanies this distribution, and is available at
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * 
 * Contributors: <NAME>, <NAME>, <NAME>, <NAME>, and others.
 ******************************************************************************/
package soot.jimple.infoflow.problems;

import heros.FlowFunction;
import heros.FlowFunctions;
import heros.flowfunc.Identity;
import heros.flowfunc.KillAll;
import heros.solver.PathEdge;

import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

import soot.ArrayType;
import soot.Local;
import soot.PrimType;
import soot.RefType;
import soot.Scene;
import soot.SootMethod;
import soot.Type;
import soot.Unit;
import soot.Value;
import soot.jimple.ArrayRef;
import soot.jimple.AssignStmt;
import soot.jimple.BinopExpr;
import soot.jimple.CastExpr;
import soot.jimple.Constant;
import soot.jimple.DefinitionStmt;
import soot.jimple.FieldRef;
import soot.jimple.IdentityStmt;
import soot.jimple.InstanceFieldRef;
import soot.jimple.InstanceInvokeExpr;
import soot.jimple.InstanceOfExpr;
import soot.jimple.InvokeExpr;
import soot.jimple.LengthExpr;
import soot.jimple.NewArrayExpr;
import soot.jimple.ReturnStmt;
import soot.jimple.StaticFieldRef;
import soot.jimple.Stmt;
import soot.jimple.UnopExpr;
import soot.jimple.infoflow.InfoflowManager;
import soot.jimple.infoflow.aliasing.Aliasing;
import soot.jimple.infoflow.collect.MutableTwoElementSet;
import soot.jimple.infoflow.data.Abstraction;
import soot.jimple.infoflow.data.AccessPath;
import soot.jimple.infoflow.solver.IInfoflowSolver;
import soot.jimple.infoflow.solver.functions.SolverCallFlowFunction;
import soot.jimple.infoflow.solver.functions.SolverCallToReturnFlowFunction;
import soot.jimple.infoflow.solver.functions.SolverNormalFlowFunction;
import soot.jimple.infoflow.solver.functions.SolverReturnFlowFunction;
import soot.jimple.infoflow.taintWrappers.ITaintPropagationWrapper;
import soot.jimple.infoflow.util.BaseSelector;
import soot.jimple.infoflow.util.TypeUtils;

/**
 * class which contains the flow functions for the backwards solver. This is
 * required for on-demand alias analysis.
 */
public class BackwardsInfoflowProblem extends AbstractInfoflowProblem {
	private IInfoflowSolver fSolver;
	
	public void setTaintWrapper(ITaintPropagationWrapper wrapper) {
		taintWrapper = wrapper;
	}
	
	public BackwardsInfoflowProblem(InfoflowManager manager) {
		super(manager);
	}

	public void setForwardSolver(IInfoflowSolver forwardSolver) {
		fSolver = forwardSolver;
	}
	
	@Override
	public FlowFunctions<Unit, Abstraction, SootMethod> createFlowFunctionsFactory() {
		return new FlowFunctions<Unit, Abstraction, SootMethod>() {
			
			private Abstraction checkAbstraction(Abstraction abs) {
				// Primitive types and strings cannot have aliases and thus
				// never need to be propagated back
				if (!abs.getAccessPath().isStaticFieldRef()) {
					if (abs.getAccessPath().getBaseType() instanceof PrimType)
						return null;
					if (TypeUtils.isStringType(abs.getAccessPath().getBaseType()))
						return null;
				}
				else {
					if (abs.getAccessPath().getFirstFieldType() instanceof PrimType)
						return null;
					if (TypeUtils.isStringType(abs.getAccessPath().getFirstFieldType()))
						return null;
				}
				return abs;
			}

			/**
			 * Computes the aliases for the given statement
			 * @param def The definition statement from which to extract
			 * the alias information
			 * @param leftValue The left side of def. Passed in to allow for
			 * caching, no need to recompute this for every abstraction being
			 * processed.
			 * @param d1 The abstraction at the method's start node
			 * @param source The source abstraction of the alias search
			 * from before the current statement
			 * @return The set of abstractions after the current statement
			 */
			private Set<Abstraction> computeAliases
					(final DefinitionStmt defStmt,
					Value leftValue,
					Abstraction d1,
					Abstraction source) {
				assert !source.getAccessPath().isEmpty();
				
				// A backward analysis looks for aliases of existing taints and thus
				// cannot create new taints out of thin air
				if (source == getZeroValue())
					return Collections.emptySet();
				
				final Set<Abstraction> res = new MutableTwoElementSet<Abstraction>();
				
				// Check whether the left side of the assignment matches our
				// current taint abstraction
				final boolean leftSideMatches = Aliasing.baseMatches(leftValue, source);
				if (!leftSideMatches)
					res.add(source);
				else {
					// The left side is overwritten completely
					
					// If we have an assignment to the base local of the current taint,
					// all taint propagations must be below that point, so this is the
					// right point to turn around.
					for (Unit u : interproceduralCFG().getPredsOf(defStmt))
						fSolver.processEdge(new PathEdge<Unit, Abstraction>(d1, u, source));
				}
				
				// We only handle assignments and identity statements
				if (defStmt instanceof IdentityStmt) {
					res.add(source);
					return res;
				}
				if (!(defStmt instanceof AssignStmt))
					return res;
				
				// Get the right side of the assignment
				final Value rightValue = BaseSelector.selectBase(defStmt.getRightOp(), false);
				
				// Is the left side overwritten completely?
				if (leftSideMatches) {
					// Termination shortcut: If the right side is a value we do not track,
					// we can stop here.
					if (!(rightValue instanceof Local || rightValue instanceof FieldRef))
						return Collections.emptySet();
				}
				
				// If we assign a constant, there is no need to track the right side
				// any further or do any forward propagation since constants cannot
				// carry taint.
				if (rightValue instanceof Constant)
					return res;
				
				// If this statement creates a new array, we cannot track upwards the size
				if (defStmt.getRightOp() instanceof NewArrayExpr)
					return res;
				
				// We only process heap objects. Binary operations can only
				// be performed on primitive objects.
				if (defStmt.getRightOp() instanceof BinopExpr)
					return res;
				if (defStmt.getRightOp() instanceof UnopExpr)
					return res;
				
				// If we have a = x with the taint "x" being inactive,
				// we must not taint the left side. We can only taint
				// the left side if the tainted value is some "x.y".
				boolean aliasOverwritten = Aliasing.baseMatchesStrict(rightValue, source)
						&& rightValue.getType() instanceof RefType
						&& !source.dependsOnCutAP();
				
				if (!aliasOverwritten && !(rightValue.getType() instanceof PrimType)) {
					// If the tainted value 'b' is assigned to variable 'a' and 'b'
					// is a heap object, we must also look for aliases of 'a' upwards
					// from the current statement.
					Abstraction newLeftAbs = null;
					if (rightValue instanceof InstanceFieldRef) {
						InstanceFieldRef ref = (InstanceFieldRef) rightValue;
						if (source.getAccessPath().isInstanceFieldRef()
								&& ref.getBase() == source.getAccessPath().getPlainValue()
								&& source.getAccessPath().firstFieldMatches(ref.getField())) {
							newLeftAbs = checkAbstraction(source.deriveNewAbstraction(leftValue, true,
									defStmt, source.getAccessPath().getFirstFieldType()));
						}
					}
					else if (manager.getConfig().getEnableStaticFieldTracking()
							&& rightValue instanceof StaticFieldRef) {
						StaticFieldRef ref = (StaticFieldRef) rightValue;
						if (source.getAccessPath().isStaticFieldRef()
								&& source.getAccessPath().firstFieldMatches(ref.getField())) {
							newLeftAbs = checkAbstraction(source.deriveNewAbstraction(leftValue, true,
									defStmt, source.getAccessPath().getBaseType()));
						}
					}
					else if (rightValue == source.getAccessPath().getPlainValue()) {
						Type newType = source.getAccessPath().getBaseType();
						if (leftValue instanceof ArrayRef)
							newType = buildArrayOrAddDimension(newType);
						else if (defStmt.getRightOp() instanceof ArrayRef)
							newType = ((ArrayType) newType).getElementType();
						
						// Type check
						if (!manager.getTypeUtils().checkCast(source.getAccessPath(),
								defStmt.getRightOp().getType()))
							return Collections.emptySet();
						
						// If the cast was realizable, we can assume that we had the
						// type to which we cast. Do not loosen types, though.
						if (defStmt.getRightOp() instanceof CastExpr) {
							CastExpr ce = (CastExpr) defStmt.getRightOp();								
							if (!Scene.v().getFastHierarchy().canStoreType(newType, ce.getCastType()))
								newType = ce.getCastType();
						}
						// Special type handling for certain operations
						else if (defStmt.getRightOp() instanceof LengthExpr) {
							// ignore. The length of an array is a primitive and thus
							// cannot have aliases
							return res;
						}
						else if (defStmt.getRightOp() instanceof InstanceOfExpr) {
							// ignore. The type check of an array returns a
							// boolean which is a primitive and thus cannot
							// have aliases
							return res;
						}
						
						if (newLeftAbs == null)
							newLeftAbs = checkAbstraction(source.deriveNewAbstraction(
									source.getAccessPath().copyWithNewValue(leftValue, newType, false), defStmt));
					}
					
					if (newLeftAbs != null) {
						// If we ran into a new abstraction that points to a
						// primitive value, we can remove it
						if (newLeftAbs.getAccessPath().getLastFieldType() instanceof PrimType)
							return res;
						
						if (!newLeftAbs.getAccessPath().equals(source.getAccessPath())) {
							// Propagate the new alias upwards
							res.add(newLeftAbs);
							
							// Inject the new alias into the forward solver
							for (Unit u : interproceduralCFG().getPredsOf(defStmt))
								fSolver.processEdge(new PathEdge<Unit, Abstraction>(d1, u, newLeftAbs));
						}
					}
				}
				
				// If we have the tainted value on the left side of the assignment,
				// we also have to look or aliases of the value on the right side of
				// the assignment.
				if ((rightValue instanceof Local || rightValue instanceof FieldRef)
						&& !(leftValue.getType() instanceof PrimType)) {
					boolean addRightValue = false;
					boolean cutFirstField = false;
					Type targetType = null;
					
					// if both are fields, we have to compare their fieldName via equals and their bases via PTS
					if (leftValue instanceof InstanceFieldRef) {
						if (source.getAccessPath().isInstanceFieldRef()) {
							InstanceFieldRef leftRef = (InstanceFieldRef) leftValue;
							if (leftRef.getBase() == source.getAccessPath().getPlainValue()) {
								if (source.getAccessPath().firstFieldMatches(leftRef.getField())) {
									targetType = source.getAccessPath().getFirstFieldType();
									addRightValue = true;
									cutFirstField = true;
								}
							}
						}
						// indirect taint propagation:
						// if leftValue is local and source is instancefield of this local:
					} else if (leftValue instanceof Local && source.getAccessPath().isInstanceFieldRef()) {
						Local base = source.getAccessPath().getPlainValue();
						if (leftValue == base) {
							targetType = source.getAccessPath().getBaseType();
							addRightValue = true;
						}
					} else if (leftValue instanceof ArrayRef) {
						ArrayRef ar = (ArrayRef) leftValue;
						Local leftBase = (Local) ar.getBase();
						if (leftBase == source.getAccessPath().getPlainValue()) {
							addRightValue = true;
							targetType = source.getAccessPath().getBaseType();
						}
						// generic case, is true for Locals, ArrayRefs that are equal etc..
					} else if (leftValue == source.getAccessPath().getPlainValue()) {
						// If this is an unrealizable cast, we can stop propagating
						if (!manager.getTypeUtils().checkCast(source.getAccessPath(), leftValue.getType()))
							return Collections.emptySet();
						
						addRightValue = true;
						targetType = source.getAccessPath().getBaseType();
					}
					
					// if one of them is true -> add rightValue
					if (addRightValue) {
						if (targetType != null) {
							// Special handling for some operations
							if (defStmt.getRightOp() instanceof ArrayRef)
								targetType = buildArrayOrAddDimension(targetType);
							else if (leftValue instanceof ArrayRef) {
								assert source.getAccessPath().getBaseType() instanceof ArrayType;
								targetType = ((ArrayType) targetType).getElementType();
								
								// If we have a type of java.lang.Object, we try to tighten it
								if (TypeUtils.isObjectLikeType(targetType))
									targetType = rightValue.getType();
								
								// If the types do not match, the right side cannot be an alias
								if (!manager.getTypeUtils().checkCast(rightValue.getType(), targetType))
									addRightValue = false;
							}
						}
						
						// Special type handling for certain operations
						if (defStmt.getRightOp() instanceof LengthExpr)
							targetType = null;
						
						// We do not need to handle casts. Casts only make
						// types more imprecise when going backwards.

						// If the source has fields, we may not have a primitive type
						if (targetType instanceof PrimType || (targetType instanceof ArrayType
								&& ((ArrayType) targetType).getElementType() instanceof PrimType))
							if (!source.getAccessPath().isStaticFieldRef() && !source.getAccessPath().isLocal())
								return Collections.emptySet();
						if (rightValue.getType() instanceof PrimType || (rightValue.getType() instanceof ArrayType
								&& ((ArrayType) rightValue.getType()).getElementType() instanceof PrimType))
							if (!source.getAccessPath().isStaticFieldRef() && !source.getAccessPath().isLocal())
								return Collections.emptySet();
						
						// If the right side's type is not compatible with our current type,
						// this cannot be an alias
						if (addRightValue) {
							if (!manager.getTypeUtils().checkCast(rightValue.getType(), targetType))
								addRightValue = false;
						}
						
						// Make sure to only track static fields if it has been enabled
						if (addRightValue)
							if (!manager.getConfig().getEnableStaticFieldTracking()
									&& rightValue instanceof StaticFieldRef)
								addRightValue = false;

						if (addRightValue) {
							Abstraction newAbs = checkAbstraction(source.deriveNewAbstraction(
									rightValue, cutFirstField, defStmt, targetType));
							if (newAbs != null && !newAbs.getAccessPath().equals(source.getAccessPath())) {
								res.add(newAbs);
								
								// Inject the new alias into the forward solver
								for (Unit u : interproceduralCFG().getPredsOf(defStmt))
									fSolver.processEdge(new PathEdge<Unit, Abstraction>(d1, u, newAbs));
							}
						}
					}
				}
				
				return res;
			}
			
			@Override
			public FlowFunction<Abstraction> getNormalFlowFunction(final Unit src, final Unit dest) {
				

				if (src instanceof DefinitionStmt) {
					final DefinitionStmt defStmt = (DefinitionStmt) src;
					final Value leftValue = BaseSelector.selectBase(defStmt.getLeftOp(), true);
					
					final DefinitionStmt destDefStmt = dest instanceof DefinitionStmt
							? (DefinitionStmt) dest : null;
					final Value destLeftValue = destDefStmt == null ? null : BaseSelector.selectBase
							(destDefStmt.getLeftOp(), true);

					return new SolverNormalFlowFunction() {

						@Override
						public Set<Abstraction> computeTargets(Abstraction d1, Abstraction source) {
							if (source == getZeroValue())
								return Collections.emptySet();
							assert source.isAbstractionActive() || manager.getConfig().getFlowSensitiveAliasing();
							
							Set<Abstraction> res = computeAliases(defStmt, leftValue, d1, source);
							
							if (destDefStmt != null && interproceduralCFG().isExitStmt(destDefStmt))
								for (Abstraction abs : res)
									computeAliases(destDefStmt, destLeftValue, d1, abs);
							
							return res;
						}

					};
				}
				return Identity.v();
			}

			@Override
			public FlowFunction<Abstraction> getCallFlowFunction(final Unit src, final SootMethod dest) {
				if (!dest.isConcrete())
					return KillAll.v();
								
				final Stmt stmt = (Stmt) src;
				final InvokeExpr ie = (stmt != null && stmt.containsInvokeExpr())
						? stmt.getInvokeExpr() : null;

				final Value[] paramLocals = new Value[dest.getParameterCount()]; 
				for (int i = 0; i < dest.getParameterCount(); i++)
					paramLocals[i] = dest.getActiveBody().getParameterLocal(i);
				
				final boolean isSource = manager.getSourceSinkManager() != null
						? manager.getSourceSinkManager().getSourceInfo((Stmt) src, interproceduralCFG()) != null : false;
				final boolean isSink = manager.getSourceSinkManager() != null
						? manager.getSourceSinkManager().isSink(stmt, interproceduralCFG(), null) : false;
				
				// This is not cached by Soot, so accesses are more expensive
				// than one might think
				final Local thisLocal = dest.isStatic() ? null : dest.getActiveBody().getThisLocal();	
				
				// Android executor methods are handled specially. getSubSignature()
				// is slow, so we try to avoid it whenever we can
				final boolean isExecutorExecute = isExecutorExecute(ie, dest);
				
				return new SolverCallFlowFunction() {

					@Override
					public Set<Abstraction> computeTargets(Abstraction d1, Abstraction source) {
						if (source == getZeroValue())
							return Collections.emptySet();
						assert source.isAbstractionActive() || manager.getConfig().getFlowSensitiveAliasing();
						
						//if we do not have to look into sources or sinks:
						if (!manager.getConfig().getInspectSources() && isSource)
							return Collections.emptySet();
						if (!manager.getConfig().getInspectSinks() && isSink)
							return Collections.emptySet();
						
						// Do not propagate in inactive taints that will be
						// activated there since they already came out of the
						// callee
						if (isCallSiteActivatingTaint(stmt, source.getActivationUnit()))
							return Collections.emptySet();
						
						// taint is propagated in CallToReturnFunction, so we do not
						// need any taint here if the taint wrapper is exclusive:
						if(taintWrapper != null && taintWrapper.isExclusive(stmt, source))
							return Collections.emptySet();
						
						// Only propagate the taint if the target field is actually read
						if (manager.getConfig().getEnableStaticFieldTracking()
								&& source.getAccessPath().isStaticFieldRef())
							if (!interproceduralCFG().isStaticFieldRead(dest,<commit_msg>also check for static initialiazers in the backwards problem<commit_after>/*******************************************************************************
 * Copyright (c) 2012 Secure Software Engineering Group at EC SPRIDE.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the GNU Lesser Public License v2.1
 * which accompanies this distribution, and is available at
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * 
 * Contributors: <NAME>, <NAME>, <NAME>, Eric
 * Bodden, and others.
 ******************************************************************************/
package soot.jimple.infoflow.problems;

import heros.FlowFunction;
import heros.FlowFunctions;
import heros.flowfunc.Identity;
import heros.flowfunc.KillAll;
import heros.solver.PathEdge;

import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;

import soot.ArrayType;
import soot.Local;
import soot.PrimType;
import soot.RefType;
import soot.Scene;
import soot.SootMethod;
import soot.Type;
import soot.Unit;
import soot.Value;
import soot.jimple.ArrayRef;
import soot.jimple.AssignStmt;
import soot.jimple.BinopExpr;
import soot.jimple.CastExpr;
import soot.jimple.Constant;
import soot.jimple.DefinitionStmt;
import soot.jimple.FieldRef;
import soot.jimple.IdentityStmt;
import soot.jimple.InstanceFieldRef;
import soot.jimple.InstanceInvokeExpr;
import soot.jimple.InstanceOfExpr;
import soot.jimple.InvokeExpr;
import soot.jimple.LengthExpr;
import soot.jimple.NewArrayExpr;
import soot.jimple.ReturnStmt;
import soot.jimple.StaticFieldRef;
import soot.jimple.Stmt;
import soot.jimple.UnopExpr;
import soot.jimple.infoflow.InfoflowManager;
import soot.jimple.infoflow.aliasing.Aliasing;
import soot.jimple.infoflow.collect.MutableTwoElementSet;
import soot.jimple.infoflow.data.Abstraction;
import soot.jimple.infoflow.data.AccessPath;
import soot.jimple.infoflow.solver.IInfoflowSolver;
import soot.jimple.infoflow.solver.functions.SolverCallFlowFunction;
import soot.jimple.infoflow.solver.functions.SolverCallToReturnFlowFunction;
import soot.jimple.infoflow.solver.functions.SolverNormalFlowFunction;
import soot.jimple.infoflow.solver.functions.SolverReturnFlowFunction;
import soot.jimple.infoflow.taintWrappers.ITaintPropagationWrapper;
import soot.jimple.infoflow.util.BaseSelector;
import soot.jimple.infoflow.util.TypeUtils;

/**
 * class which contains the flow functions for the backwards solver. This is
 * required for on-demand alias analysis.
 */
public class BackwardsInfoflowProblem extends AbstractInfoflowProblem {
	private IInfoflowSolver fSolver;
	
	public void setTaintWrapper(ITaintPropagationWrapper wrapper) {
		taintWrapper = wrapper;
	}
	
	public BackwardsInfoflowProblem(InfoflowManager manager) {
		super(manager);
	}

	public void setForwardSolver(IInfoflowSolver forwardSolver) {
		fSolver = forwardSolver;
	}
	
	@Override
	public FlowFunctions<Unit, Abstraction, SootMethod> createFlowFunctionsFactory() {
		return new FlowFunctions<Unit, Abstraction, SootMethod>() {
			
			private Abstraction checkAbstraction(Abstraction abs) {
				// Primitive types and strings cannot have aliases and thus
				// never need to be propagated back
				if (!abs.getAccessPath().isStaticFieldRef()) {
					if (abs.getAccessPath().getBaseType() instanceof PrimType)
						return null;
					if (TypeUtils.isStringType(abs.getAccessPath().getBaseType()))
						return null;
				}
				else {
					if (abs.getAccessPath().getFirstFieldType() instanceof PrimType)
						return null;
					if (TypeUtils.isStringType(abs.getAccessPath().getFirstFieldType()))
						return null;
				}
				return abs;
			}

			/**
			 * Computes the aliases for the given statement
			 * @param def The definition statement from which to extract
			 * the alias information
			 * @param leftValue The left side of def. Passed in to allow for
			 * caching, no need to recompute this for every abstraction being
			 * processed.
			 * @param d1 The abstraction at the method's start node
			 * @param source The source abstraction of the alias search
			 * from before the current statement
			 * @return The set of abstractions after the current statement
			 */
			private Set<Abstraction> computeAliases
					(final DefinitionStmt defStmt,
					Value leftValue,
					Abstraction d1,
					Abstraction source) {
				assert !source.getAccessPath().isEmpty();
				
				// A backward analysis looks for aliases of existing taints and thus
				// cannot create new taints out of thin air
				if (source == getZeroValue())
					return Collections.emptySet();
				
				final Set<Abstraction> res = new MutableTwoElementSet<Abstraction>();
				
				// Check whether the left side of the assignment matches our
				// current taint abstraction
				final boolean leftSideMatches = Aliasing.baseMatches(leftValue, source);
				if (!leftSideMatches)
					res.add(source);
				else {
					// The left side is overwritten completely
					
					// If we have an assignment to the base local of the current taint,
					// all taint propagations must be below that point, so this is the
					// right point to turn around.
					for (Unit u : interproceduralCFG().getPredsOf(defStmt))
						fSolver.processEdge(new PathEdge<Unit, Abstraction>(d1, u, source));
				}
				
				// We only handle assignments and identity statements
				if (defStmt instanceof IdentityStmt) {
					res.add(source);
					return res;
				}
				if (!(defStmt instanceof AssignStmt))
					return res;
				
				// Get the right side of the assignment
				final Value rightValue = BaseSelector.selectBase(defStmt.getRightOp(), false);
				
				// Is the left side overwritten completely?
				if (leftSideMatches) {
					// Termination shortcut: If the right side is a value we do not track,
					// we can stop here.
					if (!(rightValue instanceof Local || rightValue instanceof FieldRef))
						return Collections.emptySet();
				}
				
				// If we assign a constant, there is no need to track the right side
				// any further or do any forward propagation since constants cannot
				// carry taint.
				if (rightValue instanceof Constant)
					return res;
				
				// If this statement creates a new array, we cannot track upwards the size
				if (defStmt.getRightOp() instanceof NewArrayExpr)
					return res;
				
				// We only process heap objects. Binary operations can only
				// be performed on primitive objects.
				if (defStmt.getRightOp() instanceof BinopExpr)
					return res;
				if (defStmt.getRightOp() instanceof UnopExpr)
					return res;
				
				// If we have a = x with the taint "x" being inactive,
				// we must not taint the left side. We can only taint
				// the left side if the tainted value is some "x.y".
				boolean aliasOverwritten = Aliasing.baseMatchesStrict(rightValue, source)
						&& rightValue.getType() instanceof RefType
						&& !source.dependsOnCutAP();
				
				if (!aliasOverwritten && !(rightValue.getType() instanceof PrimType)) {
					// If the tainted value 'b' is assigned to variable 'a' and 'b'
					// is a heap object, we must also look for aliases of 'a' upwards
					// from the current statement.
					Abstraction newLeftAbs = null;
					if (rightValue instanceof InstanceFieldRef) {
						InstanceFieldRef ref = (InstanceFieldRef) rightValue;
						if (source.getAccessPath().isInstanceFieldRef()
								&& ref.getBase() == source.getAccessPath().getPlainValue()
								&& source.getAccessPath().firstFieldMatches(ref.getField())) {
							newLeftAbs = checkAbstraction(source.deriveNewAbstraction(leftValue, true,
									defStmt, source.getAccessPath().getFirstFieldType()));
						}
					}
					else if (manager.getConfig().getEnableStaticFieldTracking()
							&& rightValue instanceof StaticFieldRef) {
						StaticFieldRef ref = (StaticFieldRef) rightValue;
						if (source.getAccessPath().isStaticFieldRef()
								&& source.getAccessPath().firstFieldMatches(ref.getField())) {
							newLeftAbs = checkAbstraction(source.deriveNewAbstraction(leftValue, true,
									defStmt, source.getAccessPath().getBaseType()));
						}
					}
					else if (rightValue == source.getAccessPath().getPlainValue()) {
						Type newType = source.getAccessPath().getBaseType();
						if (leftValue instanceof ArrayRef)
							newType = buildArrayOrAddDimension(newType);
						else if (defStmt.getRightOp() instanceof ArrayRef)
							newType = ((ArrayType) newType).getElementType();
						
						// Type check
						if (!manager.getTypeUtils().checkCast(source.getAccessPath(),
								defStmt.getRightOp().getType()))
							return Collections.emptySet();
						
						// If the cast was realizable, we can assume that we had the
						// type to which we cast. Do not loosen types, though.
						if (defStmt.getRightOp() instanceof CastExpr) {
							CastExpr ce = (CastExpr) defStmt.getRightOp();								
							if (!Scene.v().getFastHierarchy().canStoreType(newType, ce.getCastType()))
								newType = ce.getCastType();
						}
						// Special type handling for certain operations
						else if (defStmt.getRightOp() instanceof LengthExpr) {
							// ignore. The length of an array is a primitive and thus
							// cannot have aliases
							return res;
						}
						else if (defStmt.getRightOp() instanceof InstanceOfExpr) {
							// ignore. The type check of an array returns a
							// boolean which is a primitive and thus cannot
							// have aliases
							return res;
						}
						
						if (newLeftAbs == null)
							newLeftAbs = checkAbstraction(source.deriveNewAbstraction(
									source.getAccessPath().copyWithNewValue(leftValue, newType, false), defStmt));
					}
					
					if (newLeftAbs != null) {
						// If we ran into a new abstraction that points to a
						// primitive value, we can remove it
						if (newLeftAbs.getAccessPath().getLastFieldType() instanceof PrimType)
							return res;
						
						if (!newLeftAbs.getAccessPath().equals(source.getAccessPath())) {
							// Propagate the new alias upwards
							res.add(newLeftAbs);
							
							// Inject the new alias into the forward solver
							for (Unit u : interproceduralCFG().getPredsOf(defStmt))
								fSolver.processEdge(new PathEdge<Unit, Abstraction>(d1, u, newLeftAbs));
						}
					}
				}
				
				// If we have the tainted value on the left side of the assignment,
				// we also have to look or aliases of the value on the right side of
				// the assignment.
				if ((rightValue instanceof Local || rightValue instanceof FieldRef)
						&& !(leftValue.getType() instanceof PrimType)) {
					boolean addRightValue = false;
					boolean cutFirstField = false;
					Type targetType = null;
					
					// if both are fields, we have to compare their fieldName via equals and their bases via PTS
					if (leftValue instanceof InstanceFieldRef) {
						if (source.getAccessPath().isInstanceFieldRef()) {
							InstanceFieldRef leftRef = (InstanceFieldRef) leftValue;
							if (leftRef.getBase() == source.getAccessPath().getPlainValue()) {
								if (source.getAccessPath().firstFieldMatches(leftRef.getField())) {
									targetType = source.getAccessPath().getFirstFieldType();
									addRightValue = true;
									cutFirstField = true;
								}
							}
						}
						// indirect taint propagation:
						// if leftValue is local and source is instancefield of this local:
					} else if (leftValue instanceof Local && source.getAccessPath().isInstanceFieldRef()) {
						Local base = source.getAccessPath().getPlainValue();
						if (leftValue == base) {
							targetType = source.getAccessPath().getBaseType();
							addRightValue = true;
						}
					} else if (leftValue instanceof ArrayRef) {
						ArrayRef ar = (ArrayRef) leftValue;
						Local leftBase = (Local) ar.getBase();
						if (leftBase == source.getAccessPath().getPlainValue()) {
							addRightValue = true;
							targetType = source.getAccessPath().getBaseType();
						}
						// generic case, is true for Locals, ArrayRefs that are equal etc..
					} else if (leftValue == source.getAccessPath().getPlainValue()) {
						// If this is an unrealizable cast, we can stop propagating
						if (!manager.getTypeUtils().checkCast(source.getAccessPath(), leftValue.getType()))
							return Collections.emptySet();
						
						addRightValue = true;
						targetType = source.getAccessPath().getBaseType();
					}
					
					// if one of them is true -> add rightValue
					if (addRightValue) {
						if (targetType != null) {
							// Special handling for some operations
							if (defStmt.getRightOp() instanceof ArrayRef)
								targetType = buildArrayOrAddDimension(targetType);
							else if (leftValue instanceof ArrayRef) {
								assert source.getAccessPath().getBaseType() instanceof ArrayType;
								targetType = ((ArrayType) targetType).getElementType();
								
								// If we have a type of java.lang.Object, we try to tighten it
								if (TypeUtils.isObjectLikeType(targetType))
									targetType = rightValue.getType();
								
								// If the types do not match, the right side cannot be an alias
								if (!manager.getTypeUtils().checkCast(rightValue.getType(), targetType))
									addRightValue = false;
							}
						}
						
						// Special type handling for certain operations
						if (defStmt.getRightOp() instanceof LengthExpr)
							targetType = null;
						
						// We do not need to handle casts. Casts only make
						// types more imprecise when going backwards.

						// If the source has fields, we may not have a primitive type
						if (targetType instanceof PrimType || (targetType instanceof ArrayType
								&& ((ArrayType) targetType).getElementType() instanceof PrimType))
							if (!source.getAccessPath().isStaticFieldRef() && !source.getAccessPath().isLocal())
								return Collections.emptySet();
						if (rightValue.getType() instanceof PrimType || (rightValue.getType() instanceof ArrayType
								&& ((ArrayType) rightValue.getType()).getElementType() instanceof PrimType))
							if (!source.getAccessPath().isStaticFieldRef() && !source.getAccessPath().isLocal())
								return Collections.emptySet();
						
						// If the right side's type is not compatible with our current type,
						// this cannot be an alias
						if (addRightValue) {
							if (!manager.getTypeUtils().checkCast(rightValue.getType(), targetType))
								addRightValue = false;
						}
						
						// Make sure to only track static fields if it has been enabled
						if (addRightValue)
							if (!manager.getConfig().getEnableStaticFieldTracking()
									&& rightValue instanceof StaticFieldRef)
								addRightValue = false;

						if (addRightValue) {
							Abstraction newAbs = checkAbstraction(source.deriveNewAbstraction(
									rightValue, cutFirstField, defStmt, targetType));
							if (newAbs != null && !newAbs.getAccessPath().equals(source.getAccessPath())) {
								res.add(newAbs);
								
								// Inject the new alias into the forward solver
								for (Unit u : interproceduralCFG().getPredsOf(defStmt))
									fSolver.processEdge(new PathEdge<Unit, Abstraction>(d1, u, newAbs));
							}
						}
					}
				}
				
				return res;
			}
			
			@Override
			public FlowFunction<Abstraction> getNormalFlowFunction(final Unit src, final Unit dest) {
				

				if (src instanceof DefinitionStmt) {
					final DefinitionStmt defStmt = (DefinitionStmt) src;
					final Value leftValue = BaseSelector.selectBase(defStmt.getLeftOp(), true);
					
					final DefinitionStmt destDefStmt = dest instanceof DefinitionStmt
							? (DefinitionStmt) dest : null;
					final Value destLeftValue = destDefStmt == null ? null : BaseSelector.selectBase
							(destDefStmt.getLeftOp(), true);

					return new SolverNormalFlowFunction() {

						@Override
						public Set<Abstraction> computeTargets(Abstraction d1, Abstraction source) {
							if (source == getZeroValue())
								return Collections.emptySet();
							assert source.isAbstractionActive() || manager.getConfig().getFlowSensitiveAliasing();
							
							Set<Abstraction> res = computeAliases(defStmt, leftValue, d1, source);
							
							if (destDefStmt != null && interproceduralCFG().isExitStmt(destDefStmt))
								for (Abstraction abs : res)
									computeAliases(destDefStmt, destLeftValue, d1, abs);
							
							return res;
						}

					};
				}
				return Identity.v();
			}

			@Override
			public FlowFunction<Abstraction> getCallFlowFunction(final Unit src, final SootMethod dest) {
				if (!dest.isConcrete())
					return KillAll.v();
								
				final Stmt stmt = (Stmt) src;
				final InvokeExpr ie = (stmt != null && stmt.containsInvokeExpr())
						? stmt.getInvokeExpr() : null;

				final Value[] paramLocals = new Value[dest.getParameterCount()]; 
				for (int i = 0; i < dest.getParameterCount(); i++)
					paramLocals[i] = dest.getActiveBody().getParameterLocal(i);
				
				final boolean isSource = manager.getSourceSinkManager() != null
						? manager.getSourceSinkManager().getSourceInfo((Stmt) src, interproceduralCFG()) != null : false;
				final boolean isSink = manager.getSourceSinkManager() != null
						? manager.getSourceSinkManager().isSink(stmt, interproceduralCFG(), null) : false;
				
				// This is not cached by Soot, so accesses are more expensive
				// than one might think
				final Local thisLocal = dest.isStatic() ? null : dest.getActiveBody().getThisLocal();	
				
				// Android executor methods are handled specially. getSubSignature()
				// is slow, so we try to avoid it whenever we can
				final boolean isExecutorExecute = isExecutorExecute(ie, dest);
				
				return new SolverCallFlowFunction() {

					@Override
					public Set<Abstraction> computeTargets(Abstraction d1, Abstraction source) {
						if (source == getZeroValue())
							return Collections.emptySet();
						assert source.isAbstractionActive() || manager.getConfig().getFlowSensitiveAliasing();
						
						//if we do not have to look into sources or sinks:
						if (!manager.getConfig().getInspectSources() && isSource)
							return Collections.emptySet();
						if (!manager.getConfig().getInspectSinks() && isSink)
							return Collections.emptySet();
						
						// Do not propagate in inactive taints that will be
						// activated there since they already came out of the
						// callee
						if (isCallSiteActivatingTaint(stmt, source.getActivationUnit()))
							return Collections.emptySet();
						
						// Do not analyze static initializers if static field
						// tracking is disabled
						if (!manager.getConfig().getEnableStaticFieldTracking() && dest.isStaticInitializer())
							return Collections.emptySet();
						
						// taint is propagated in CallToReturnFunction, so we do not
						// need any taint here if the taint wrapper is exclusive:
						if(taintWrapper != null && taintWrapper.isExclusive(stmt, source))
							return Collections.emptySet();
						
						// Only propagate the taint if the target field is actually read
						if (manager.getConfig().getEnableStaticFieldTracking()
								&& source.getAccessPath().isStaticFieldRef())
							if (!interproceduralCFG().isStaticFieldRead(dest,
{'fraction_non_alphanumeric': 0.10312278769763235, 'fraction_numerical': 0.0009439156768662, 'mean_word_length': 3.1515184499836724, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3108568', 'n_tokens_mistral': 14114, 'n_tokens_neox': 10432, 'n_words': 3120}