public static TrackableSelector taint(final String name) {
	return new TrackableSelector() {
	
		@Override
		public boolean matches(Trackable trackable) {
			if (trackable instanceof Taint) {
				String taintString = ((Taint) trackable).value.toString();
				if (taintString.equals(name)) {
					return true;
				}
			}
			return false;
		}
	
		@Override
		public String toString() {
			return name;
		}
	};
} public static TrackableSelector taintContains(final String name) {
	return new TrackableSelector() {
	
		@Override
		public boolean matches(Trackable trackable) {
			if (trackable instanceof Taint) {
				String taintString = ((Taint) trackable).value.toString();
				if (taintString.contains(name)) {
					return true;
				}
	
			}
			return false;
		}
	
		@Override
		public String toString() {
			return ".*" + name + ".*";
		}
	};
} public static UnitSelector anyUnit() {
	return new UnitSelector() {

		@Override
		public boolean matches(SootMethod method, Unit unit) {
			return true;
		}

		@Override
		public String toString() {
			return "any unit";
		}
	};
} public static UnitSelector unitByLabel(final String label) {
	return new UnitSelector() {
		@Override
		public boolean matches(SootMethod method, Unit unit) {
			return unit.toString().contains(label);
		}

		@Override
		public String toString() {
			return label;
		}
	};
} public static UnitSelector unitInMethod(final String methodString, final UnitSelector selector) {
	return new UnitSelector() {
		@Override
		public boolean matches(SootMethod method, Unit unit) {
			return method.toString().contains(methodString) && selector.matches(method, unit);
		}

		@Override
		public String toString() {
			return "'" + selector.toString() + "' in '" + methodString + "'";
		}
	};
} public static UnitSelector unitWithoutLabel(final String label, final UnitSelector selector) {
	return new UnitSelector() {
		@Override
		public boolean matches(SootMethod method, Unit unit) {
			return !unit.toString().contains(label) && selector.matches(method, unit);
		}

		@Override
		public String toString() {
			return "'" + selector.toString() + "' without '" + label + "'";
		}
	};
} public class SolverFactory {

	public static void runOneDirectionSolver(AnalysisConfigurationBuilder configBuilder) {

		Pair<IfdsReporter, AnalysisConfigurationBuilder> pair = configBuilder.decorateReporter(new PropagationReporterDecorator() {
			@Override
			public IfdsReporter decorate(IfdsReporter reporter) {
				return new DelayingReporter(reporter);
			}
		});
		
		TabulationProblem problem = createTabulationProblem(pair.second);
		IFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>> solver = createSolver(problem);

		AnalysisReporting.analysisStarted();
		
		_runOneDirectionSolver(problem, solver);
		pair.first.analysisFinished();
		AnalysisReporting.analysisFinished();
	}

	public static void runInnerToOuterSolver(AnalysisConfigurationBuilder configBuilder) {

		Pair<IfdsReporter, AnalysisConfigurationBuilder> pair = configBuilder.decorateReporter(new PropagationReporterDecorator() {
			@Override
			public IfdsReporter decorate(IfdsReporter reporter) {
				return new DelayingReporter(reporter);
			}
		});
		configBuilder = pair.second;
		
		TabulationProblem forwardTabulationProblem = createTabulationProblem(configBuilder.direction(FORWARDS));
		IFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>> forwardSolver = createSolver(forwardTabulationProblem);
		TabulationProblem backwardTabulationProblem = createTabulationProblem(configBuilder.direction(BACKWARDS));
		IFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>> backwardSolver = createSolver(backwardTabulationProblem);

		AnalysisReporting.analysisStarted();
		
		_runOneDirectionSolver(forwardTabulationProblem, forwardSolver);
		_runOneDirectionSolver(backwardTabulationProblem, backwardSolver);
		pair.first.analysisFinished();
		AnalysisReporting.analysisFinished();
	}

	protected static void _runOneDirectionSolver(final TabulationProblem tabulationProblem, IFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>> solver) {
		AnalysisReporting.ifdsStarting(tabulationProblem.getContext(), solver);
		solver.solve();
		AnalysisReporting.ifdsFinished(tabulationProblem.getContext(), solver, FlowFunctionFactory.propCounter.get());
		FlowFunctionFactory.propCounter.set(0);
	}

	private static IFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>> createSolver(
			final TabulationProblem tabulationProblem) {
		IFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>> solver = new PathTrackingIFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>>(
				tabulationProblem) {
			@Override
			protected String getDebugName() {
				if (tabulationProblem.getContext().direction == FORWARDS)
					return "FW";
				else
					return "BW";
			}
		};
		return solver;
	}

	private static TabulationProblem createTabulationProblem(
			AnalysisConfigurationBuilder configBuilder) {
		final TabulationProblem tabulationProblem = new TabulationProblem(configBuilder.build());
		return tabulationProblem;
	}

	public static void runBiDirectionSolver(AnalysisConfigurationBuilder configBuilder) {
		Pair<IfdsReporter, AnalysisConfigurationBuilder> pair = configBuilder.decorateReporter(new PropagationReporterDecorator() {
			@Override
			public IfdsReporter decorate(IfdsReporter reporter) {
				return new DelayingReporter(reporter);
			}
		});
		configBuilder = pair.second;

		TabulationProblem backwardsTabulationProblem = new TabulationProblem(configBuilder.direction(BACKWARDS).build());
		TabulationProblem forwardsTabulationProblem = new TabulationProblem(configBuilder.direction(FORWARDS).build());

		BiDiIFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>> biDiIFDSSolver = new BiDiIFDSSolver<Unit, Trackable, SootMethod, BiDiInterproceduralCFG<Unit, SootMethod>>(
				forwardsTabulationProblem, backwardsTabulationProblem);

		AnalysisReporting.analysisStarted();
		
		AnalysisReporting.ifdsStarting(backwardsTabulationProblem.getContext(), biDiIFDSSolver);
		AnalysisReporting.ifdsStarting(forwardsTabulationProblem.getContext(), biDiIFDSSolver);
		biDiIFDSSolver.solve();
		AnalysisReporting.ifdsFinished(backwardsTabulationProblem.getContext(), biDiIFDSSolver, FlowFunctionFactory.propCounter.get());
		AnalysisReporting.ifdsFinished(forwardsTabulationProblem.getContext(), biDiIFDSSolver, FlowFunctionFactory.propCounter.get());
		pair.first.analysisFinished();
		AnalysisReporting.analysisFinished();
	}
} public abstract class AbstractTaintAnalysisTest extends AbstractAnalysisTest {

	@Rule
	public TestWatcher name = new TestWatcher() {
		@Override
		public void failed(Throwable e, Description description) {
			StringBuilder builder = new StringBuilder();
			builder.append("tmp/");
			builder.append(AbstractTaintAnalysisTest.this.getClass().getSimpleName());
			builder.append("_");
			builder.append(description.getMethodName());
			verifier.writeDebugFile(builder.toString());
		}
	};
	private AnalysisGraphVerifier verifier;

	protected AnalysisGraphVerifier runTest(final String... classNames) {
		runAnalysis(new TestAnalysis(classNames) {
			@Override
			protected void executeAnalysis() {
				verifier = executeTaintAnalysis(classNames);
			}
		});
		return verifier;
	}

	protected abstract AnalysisGraphVerifier executeTaintAnalysis(String[] classNames);

} public class AnalysisGraphVerifier implements IfdsReporter {

	private TrackableGraphPlotter debugPlotter;
	private Map<Unit, SootMethod> unit2Method = Maps.newHashMap();
	private Multimap<Unit, Pair<Unit, Trackable>> successors = HashMultimap.create();
	private Multimap<Unit, Trackable> trackablesAtUnit = Multimaps.newSetMultimap(new HashMap<Unit, Collection<Trackable>>(),
			new Supplier<Set<Trackable>>() {
				@Override
				public Set<Trackable> get() {
					return new IdentityHashSet<>();
				}
			});

	public AnalysisGraphVerifier() {
		// debugPlotter = new DebugPlotter();
		debugPlotter = new TrackableGraphPlotter();
	}

	@Override
	public void reportTrackable(Report report) {
		debugPlotter.reportTrackable(report);
		createEdges(report.context, report.trackable, report.targetUnit);
	}

	private void createEdges(AnalysisContext context, Trackable trackable, Unit unit) {
		unit2Method.put(unit, context.icfg.getMethodOf(unit));

		for (Trackable neighbor : trackable.getSelfAndNeighbors()) {
			trackablesAtUnit.put(unit, neighbor);
			if (neighbor.sourceUnit == null)
				continue;

			if (successors.put(neighbor.sourceUnit, new Pair<Unit, Trackable>(unit, neighbor)))
				createEdges(context, neighbor.predecessor, neighbor.sourceUnit);
		}
	}

	@Override
	public void analysisFinished() {
	}

	public void writeDebugFile(String fileName) {
		System.out.println("Writing debug graph file for failed test: " + fileName);
		debugPlotter.writeFile(fileName);
	}

	public UnitNode find(UnitSelector selector) {
		for (Unit unit : unit2Method.keySet()) {
			if (selector.matches(unit2Method.get(unit), unit)) {
				return new UnitNode(unit);
			}
		}
		throw new AssertionFailedError(format("Unit not found: %s", selector));
	}

	public void cannotFind(UnitSelector selector) {
		for (Unit unit : unit2Method.keySet()) {
			if (selector.matches(unit2Method.get(unit), unit)) {
				throw new AssertionFailedError(format("Unit found: %s", selector));
			}
		}
	}

	public class UnitNode {

		private final Unit unit;

		public UnitNode(Unit unit) {
			this.unit = unit;
		}

		public UnitNode edge(TrackableSelector trackableSelector, UnitSelector unitSelector) {
			for (Pair<Unit, Trackable> successor : successors.get(unit)) {
				if (unitSelector.matches(unit2Method.get(successor.getO1()), successor.getO1()) && trackableSelector.matches(successor.getO2())) {
					return new UnitNode(successor.getO1());
				}
			}

			throw new AssertionFailedError(format("No edge found from '%s' to '%s' with trackable matching '%s'", unit.toString(), unitSelector,
					trackableSelector.toString()));
		}

		public UnitNode pathTo(TrackableSelector trackableSelector, UnitSelector selector) {
			Set<Unit> visited = Sets.newHashSet();
			List<Unit> worklist = Lists.newLinkedList();
			worklist.add(unit);
			while (!worklist.isEmpty()) {
				Unit current = worklist.remove(0);
				if (visited.add(current)) {
					for (Pair<Unit, Trackable> successor : successors.get(current)) {
						if (selector.matches(unit2Method.get(successor.getO1()), successor.getO1()) && trackableSelector.matches(successor.getO2())) {
							return new UnitNode(successor.getO1());
						}
						worklist.add(successor.getO1());
					}
				}
			}
			throw new AssertionFailedError(format("There is no connection from '%s' to '%s' with the taint '%s' at the destination.",
					unit.toString(), selector, trackableSelector.toString()));
		}

		public void assertHasNot(TrackableSelector trackableSelector) {
			for (Pair<Unit, Trackable> successor : successors.get(unit)) {
				if (trackableSelector.matches(successor.getO2())) {
					throw new AssertionFailedError(format("There is a taint matching '%s' into unit '%s' that should not be there!",
							trackableSelector, unit));
				}
			}
		}

		public void assertNoOutgoingEdges() {
			Assert.assertEquals(format("Unit '%s' has outgoing edges, but should have none.", unit), 0, successors.get(unit).size());
		}

		public void assertIncomingEdges(int expected) {
			int actual = 0;
			for (Trackable t : trackablesAtUnit.get(unit)) {
				if (t.predecessor != null)
					actual++;
			}
			Assert.assertEquals(expected, actual);
		}

	}

} public class UnitNode {

	private final Unit unit;

	public UnitNode(Unit unit) {
		this.unit = unit;
	}

	public UnitNode edge(TrackableSelector trackableSelector, UnitSelector unitSelector) {
		for (Pair<Unit, Trackable> successor : successors.get(unit)) {
			if (unitSelector.matches(unit2Method.get(successor.getO1()), successor.getO1()) && trackableSelector.matches(successor.getO2())) {
				return new UnitNode(successor.getO1());
			}
		}

		throw new AssertionFailedError(format("No edge found from '%s' to '%s' with trackable matching '%s'", unit.toString(), unitSelector,
				trackableSelector.toString()));
	}

	public UnitNode pathTo(TrackableSelector trackableSelector, UnitSelector selector) {
		Set<Unit> visited = Sets.newHashSet();
		List<Unit> worklist = Lists.newLinkedList();
		worklist.add(unit);
		while (!worklist.isEmpty()) {
			Unit current = worklist.remove(0);
			if (visited.add(current)) {
				for (Pair<Unit, Trackable> successor : successors.get(current)) {
					if (selector.matches(unit2Method.get(successor.getO1()), successor.getO1()) && trackableSelector.matches(successor.getO2())) {
						return new UnitNode(successor.getO1());
					}
					worklist.add(successor.getO1());
				}
			}
		}
		throw new AssertionFailedError(format("There is no connection from '%s' to '%s' with the taint '%s' at the destination.",
				unit.toString(), selector, trackableSelector.toString()));
	}

	public void assertHasNot(TrackableSelector trackableSelector) {
		for (Pair<Unit, Trackable> successor : successors.get(unit)) {
			if (trackableSelector.matches(successor.getO2())) {
				throw new AssertionFailedError(format("There is a taint matching '%s' into unit '%s' that should not be there!",
						trackableSelector, unit));
			}
		}
	}

	public void assertNoOutgoingEdges() {
		Assert.assertEquals(format("Unit '%s' has outgoing edges, but should have none.", unit), 0, successors.get(unit).size());
	}

	public void assertIncomingEdges(int expected) {
		int actual = 0;
		for (Trackable t : trackablesAtUnit.get(unit)) {
			if (t.predecessor != null)
				actual++;
		}
		Assert.assertEquals(expected, actual);
	}

} public interface TrackableSelector {
	boolean matches(Trackable trackable);
} public interface UnitSelector {
	boolean matches(SootMethod method, Unit unit);
}
import static flow.twist.config.AnalysisConfigurationBuilder.i2oSimpleClassForNameDefaults;
import static flow.twist.config.AnalysisDirection.FORWARDS;
import static flow.twist.test.util.selectors.TrackableSelectorFactory.taint;
import static flow.twist.test.util.selectors.TrackableSelectorFactory.taintContains;
import static flow.twist.test.util.selectors.UnitSelectorFactory.anyUnit;
import static flow.twist.test.util.selectors.UnitSelectorFactory.unitByLabel;
import static flow.twist.test.util.selectors.UnitSelectorFactory.unitInMethod;
import static flow.twist.test.util.selectors.UnitSelectorFactory.unitWithoutLabel;
import org.junit.Ignore;
import org.junit.Test;
import flow.twist.SolverFactory;
import flow.twist.test.util.AbstractTaintAnalysisTest;
import flow.twist.test.util.AnalysisGraphVerifier;
import flow.twist.test.util.AnalysisGraphVerifier.UnitNode;
import flow.twist.test.util.selectors.TrackableSelector;
import flow.twist.test.util.selectors.UnitSelector;
package flow.twist.test.unit;




public class ForwardsGraphTests extends AbstractTaintAnalysisTest {

	private UnitSelector forNameSelector = unitByLabel("forName");

	@Override
	protected AnalysisGraphVerifier executeTaintAnalysis(String[] classNames) {
		AnalysisGraphVerifier verifier = new AnalysisGraphVerifier();
		SolverFactory.runOneDirectionSolver(i2oSimpleClassForNameDefaults().direction(FORWARDS).reporter(verifier));