False negative when handling field abstraction in backward alias analysis

[flankerhqd]

Hi:

There's a false negative when handling field abstraction in backward alias analysis, lead to missing of taints which was seen in quite a few real world code snippets. Consider the following example, which is provided as in #415 as a failed test case aliasWithOverwriteTest1:

	class D {
		E e;

		public void read() {
			e = new E();
			e.read();
		}
	}

	class E {
		String str;
		public void read() {
			str = ""; //comment out this line passes the test
			str = str + TelephonyManager.getDeviceId(); // or simply `str = TelephonyManager.getDeviceId();`
		}
	}
	public void aliasWithOverwriteTest1() {
		D d = new D();
		d.read();
		ConnectionManager cm = new ConnectionManager();
		cm.publish(d.e.str);
	}

In the read function of class E, when the field str is tainted, a backward alias analysis is triggered as a taint with abstraction statement and pops upwards. Normally, this backward taint should reach out of the original method and walks all the way up and then reverse again to forward solver and finally taints this.d.e.str.

However, since there is an overwrite statement 'str = ""' above, the current BackwardsInfoFlowProblem.computeAliases logic will consider the left side overwritten completely, and refuses to pass the taint upwards.

				// 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))
						manager.getForwardSolver().processEdge(new PathEdge<Unit, Abstraction>(d1, u, source));
				}

And the InfoFlowProblem forward solver does not trigger alias analysis when the function returns. This taint thus disappears from this.d.e, and then missing fro the final sink cm.publish(d.e.str);, which is of course incorrect.

It can be tackled by forcing forward solver to trigger alias analysis when return, i.e. forcing true in aliasing.getAliasingStrategy().requiresAnalysisOnReturn

							if ((abs.isImplicit() && !callerD1sConditional)
									|| aliasing.getAliasingStrategy().requiresAnalysisOnReturn()) {
								for (Abstraction d1 : callerD1s) {
									aliasing.computeAliases(d1, iCallStmt, null, res,
											interproceduralCFG().getMethodOf(callSite), abs);
								}
							}

but I suspect this will introduce huge performance impact and may lead to other false positives.

I'm wondering what's the better solutions for this situation?

Thanks!

[flankerhqd]

Changes requiresAnalysisOnReturn fails HeapTests.negativeMultiLevelTest2

[StevenArzt]

I can confirm that this is a false negative. Strangely enough, the flow isn't even found when I comment out the line str = ""; I have to look into why this happens.

[flankerhqd]

I can confirm that this is a false negative. Strangely enough, the flow isn't even found when I comment out the line str = ""; I have to look into why this happens.

Oh sorry for the typo, I believe the additional strange one you mentioned is a different wrapper issue, because StringBuilder is implicitly used for string concatenation. This is found if we use initInfoflow(true);, but not when we comment out that line. But this does not affect the original problem.

With wrapper used:
Found for

			str = str + TelephonyManager.getDeviceId();

And

			str = TelephonyManager.getDeviceId();

Not found for

                        str = "";
			str = str + TelephonyManager.getDeviceId();

And

                        str = "";
			str = TelephonyManager.getDeviceId();

To simplify the problem, with wrapper not used, please try this more minimized testcase (flow not found):

                        str = "";
			str = TelephonyManager.getDeviceId();

(Flow found)

                        
			str = TelephonyManager.getDeviceId();

[flankerhqd]

Changes requiresAnalysisOnReturn fails HeapTests.negativeMultiLevelTest2

I did a bit digging and found, changing requiresAnalysisOnReturn introduces false positive and fails HeapTests.negativeMultiLevelTest2 because, if this is turned on and alias analysis is triggered on method return, the activation statement for the newly generated inactive taint is set to the iCallStmt.

So when the inactive taint is passed backwards, it will encounter an assign statement, and reverses its direction to go downwards. However, since the taint's activation statement is set to the call statement but not the actual statement in the method body which the original taint was generated, in CallFlowFunction when the solver processes the very function call which it was generated, it will activate this taint. Thus, the taint is mistakenly treated alive the very moment it enters the function, rather than the statement in which it is actually generated.

[StevenArzt]

Should be fixed.