[Soot-list] FlowDroid produces unreasonable false positive

[flanker017]

Hi, I found FlowDroid produces unreasonable false positive on fields.

if f.a is tainted, FlowDroid will mark f as tainted, thus introducing huge amount of false positives.

Detail can be found at https://github.com/secure-software-engineering/soot-infoflow-android/issues/38.

FlowDroid will deduce that there is a flow from intent.getStringExtra('r') to this.getString(2131230774) for the following source, which is no doubt a false positive.

package com.example.testwebview;

import android.app.Activity;
import android.content.Intent;
import android.os.Bundle;
import android.widget.Button;

public class MainActivity extends Activity {
    protected String n;
    protected Button T;

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);

        Intent intent = this.getIntent();
        this.n = intent.getStringExtra("r");
        this.T = new Button(this);
        this.T.setText(this.getString(2131230774));

    }
}

Produced flow:

[main] INFO soot.jimple.infoflow.data.pathBuilders.ContextInsensitivePathBuilder - Obtainted 1 connections between sources and sinks
[main] INFO soot.jimple.infoflow.data.pathBuilders.ContextInsensitivePathBuilder - Building path 1
[main] INFO soot.jimple.infoflow.data.pathBuilders.ContextInsensitivePathBuilder - Path processing took 0.002538356 seconds in total for 3 edges
[main] INFO soot.jimple.infoflow.Infoflow - The sink $r3 = virtualinvoke $r0.<com.example.testwebview.MainActivity: java.lang.String getString(int)>(2131230774) in method <com.example.testwebview.MainActivity: void onCreate(android.os.Bundle)> was called with values from the following sources:
[main] INFO soot.jimple.infoflow.Infoflow - - $r3 = virtualinvoke $r2.<android.content.Intent: java.lang.String getStringExtra(java.lang.String)>("r") in method <com.example.testwebview.MainActivity: void onCreate(android.os.Bundle)>
[main] INFO soot.jimple.infoflow.Infoflow -     on Path: 
[main] INFO soot.jimple.infoflow.Infoflow -      -> <com.example.testwebview.MainActivity: void onCreate(android.os.Bundle)>
[main] INFO soot.jimple.infoflow.Infoflow -          -> $r3 = virtualinvoke $r2.<android.content.Intent: java.lang.String getStringExtra(java.lang.String)>("r")
[main] INFO soot.jimple.infoflow.Infoflow -      -> <com.example.testwebview.MainActivity: void onCreate(android.os.Bundle)>
[main] INFO soot.jimple.infoflow.Infoflow -          -> $r0.<com.example.testwebview.MainActivity: java.lang.String n> = $r3
[main] INFO soot.jimple.infoflow.Infoflow -      -> <com.example.testwebview.MainActivity: void onCreate(android.os.Bundle)>
[main] INFO soot.jimple.infoflow.Infoflow -          -> $r3 = virtualinvoke $r0.<com.example.testwebview.MainActivity: java.lang.String getString(int)>(2131230774)

Running arguments: app-debug.apk /home/xxx/adt-bundle/sdk/platforms/ --aplength 1 --nocallbacks --layoutmode none --pathalgo CONTEXTINSENSITIVE

Test apk:

https://www.dropbox.com/s/wnirus0as7p0p2n/sample.apk?dl=0

I trace down the source code, and think the issue maybe at 

public FlowFunction<Abstraction> getCallToReturnFlowFunction, 

In field references, newSource.getAccessPath.getPlainValue() is "field base value", not actually tainted value. That is , if f.a is tainted, this method will return f, not f.a, which is not reasonable.

if (isSink) {

// If we are inside a conditional branch, we consider every sink call a leak

boolean conditionalCall = enableImplicitFlows 

&& !interproceduralCFG().getMethodOf(call).isStatic()

&& aliasing.mayAlias(interproceduralCFG().getMethodOf(call).getActiveBody().getThisLocal(),

newSource.getAccessPath().getPlainValue())

&& newSource.getAccessPath().getFirstField() == null;

boolean taintedParam = (conditionalCall

|| newSource.getTopPostdominator() != null

|| newSource.getAccessPath().isEmpty())

&& newSource.isAbstractionActive();

// If the base object is tainted, we also consider the "code" associated

// with the object's class as tainted.

if (!taintedParam) {

for (int i = 0; i < callArgs.length; i++) {

if (aliasing.mayAlias(callArgs[i], newSource.getAccessPath().getPlainValue())) {

taintedParam = true;

break;

}

}

}

if (taintedParam && newSource.isAbstractionActive())

addResult(new AbstractionAtSink(newSource, invExpr, iStmt));

// if the base object which executes the method is tainted the sink is reached, too.

if (invExpr instanceof InstanceInvokeExpr) {

InstanceInvokeExpr vie = (InstanceInvokeExpr) iStmt.getInvokeExpr();

if (newSource.isAbstractionActive()

&& aliasing.mayAlias(vie.getBase(), newSource.getAccessPath().getPlainValue()))

{

addResult(new AbstractionAtSink(newSource, invExpr, iStmt));

}

}

}

Will someone kindly look into this issue? Thanks. 

[Steven Arzt]

Hi,

 

You found the correct piece of code. There is even a comment that documents precisely the behavior you describe:

 

// if the base object which executes the method is tainted the sink is reached, too.

 

The reasoning behind this rule is as follows: If I write a tainted value into an object and a method on the class of that object is defined as a sink, it could theoretically read out the tainted value and leak it. Take the following example:

 

                Container c = new Container();

                c.data = source();

                c.leakMyData();

 

Since the classes containing sinks are assumed to be library classes, you cannot look into them in the usual case. You thus cannot know whether “leakMyData()” actually leaks the contents of field “data” or not. We thus conservatively assume it does.

 

The only way around this problem would be to extend the SourceSinkManager to have distinct notations for sinks which only leak data if one of their parameters is  tainted and ones which read out fields. More precisely, a sink description would need to speak about concrete fields and concrete parameters instead of just saying “if anything that flows into this method is tainted, consider it as a leak”. While this would be helpful in some cases, it also requires some implementation effort. If you volunteer to extend FlowDroid in that direction, I would be happy to merge the results back into the open-source project and also provide some assistance.

 

Best regards,

  Steven

 

 

M.Sc. M.Sc. Steven Arzt

Secure Software Engineering Group (SSE)

European Center for Security and Privacy by Design (EC SPRIDE)

Mornewegstraße 32

D-64293 Darmstadt

Phone: +49 61 51 16-75426

Fax: +49 61 51 16-72118

eMail: steve...@ec-spride.de

Web: http://sse.ec-spride.de

[flanker017]

Thanks Steven for your reply, I understand this tradeoff although in many cases it will lead to taint explosion and the results are misleading. I'm trying to work on a better approach, especially for instance fields.

--
Sincerely,

Flanker He (a.k.a. Qidan He)

Website: http://flanker017.me

[Steven Arzt]

Hi,

 

I am wondering, why getString() is a source in your context. Just by looking at your code snippet, I would have thought it were a source.

 

In practice, we have not experienced many issues with the current solution. Still, I agree that it is not optimal and can be improved. If I have spare resources (e.g., students) at some point, I can extend the FlowDroid part, but it is more complicated than visible at first sight. We do not write our lists of sources and sinks by hand, but by using an automated approach that analyzes the Android framework and applies machine learning to deduce whether a certain method is a source, a sink, or neither. If we have a more precise source/sink definition in FlowDroid, we would also have to re-visit the question of how to obtain the source and sink lists.

 

By the way, “especially instance fields” is misleading, because the imprecision only arises in the very case I explained. There should not be anything else, but instance fields in this very precise scenario.

 

Best regards,

  Steven

[flanker017]

Sorry for not adding the mail list.

---------- Forwarded message ----------
From: flanker017 <flanke...@gmail.com>
Date: 2014-10-31 13:14 GMT+08:00
Subject: Re: [Soot-list] FlowDroid produces unreasonable false positive
To: Steven Arzt <Steve...@cased.de>

Hi Steven:

I'm just setting getString(int) as a sink for debugging purpose. getString(int) shouldn't have any data flowing in it since the param of it is constant value, and the function itself doesn't depend on user input. For example, for the source I listed above, 

 @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(

savedInstanceState);

        Intent intent = this.getIntent();
        this.n = intent.getStringExtra("r"); //source
        this.T = new Button(this);
        this.T.setText(this.getString(2131230774)); //setText is sink but won't be reached from source

    }

SOURCE: getStringExtra(String)

SINK: setText(String)

I'm originally setting getStringExtra(String) as a source and setText as a sink. There should not exist a flow from source to sink, as the sink's parameter is return value of getString(int), an API funciton call to extract string from constant layout, which has clearly no relationship with getStringExtra. 

However, as I pasted above, I surprisingly found FlowDroid generate two flow traces, one from getStringExtra() ->this.n=<tainted>-> this.getString(int) -> this.T.setText (value tainted), one from getStringExtra->this.n=<tainted>->this.T=newButton(this)->this.T.setText (base tainted). Since I found getString(int) appears on taint path, I tried to set it as sink for debug purpose, and found FlowDroid still found flow into it, which as I stated above, definitely unreasonable.

I trace down the result through debugging, and I found that this.T=<tainted> will generate AccessPath <$r0 this.T> , with base value $r0, a.k.a "this".  As data flowing, InfoflowProblem's implementation will taint this.getString(int) when the base value appears in AccessPath as "this($r0)", because many statements in InfoFlowProblem generate and transfer taints based on comparing the base value of AccessPath only. And it will also taint this.T = new Button(this), because param of <init>, which is $r0, appears in AccesPath. These two together generates false positives that this.T is tainted, this.getString(int)'s return value tainted, causing multiple flows to the final sink statements, which are both incorrect.

So as you have replied, this may be a design decision, that " if a field of base class is tainted, then all function calls invoking this instance and using this instance as param should be tainted." I did find this logic in multiple code lines in FlowDroid, as  InfoFlowProblem generate and transfer taints based on comparing the base value of AccessPath only, not taking fields into consideration . However, as the example code snippet states, this will cause may false positives, as developers tend to store values in Activity fields, as what I've shown in the "MyActivity" example. For the current implementation, this will cause the Activity instance as tainted, making all function calls using Activity instance as base or param tainted, and all sub-class of this Activity tainted.

[Steven Arzt]

Hi,

 

It seems that there has been a fair amount of misunderstanding about the precise effect of what we were discussing. FlowDroid is a field- and object-sensitive data flow tracker, so it does take fields into account and handles them precisely. Precise object and field handling is the very point of using access paths. If the access path “a.b” is tainted, this does not mean that “a.c” is tainted, nor that “a.*” is tainted, but only refers to the very entity “a.b”.

 

Therefore, your interpretation of how FlowDroid works is wrong in several places:

 

Ø  “because many statements in InfoFlowProblem generate and transfer taints based on comparing the base value of AccessPath only”

 

Nope. The taints are always transferred using the full access path. If I have the statement “a = b” and “b.x” is tainted, this is used to generate the additional taint “a.x”. In this case, the base local gets substituted, but that does not mean that the rest of the access path is lost.

 

Ø  “InfoFlowProblem generate and transfer taints based on comparing the base value of AccessPath only, not taking fields into consideration “

 

Wrong. Taints are always propagated using access paths, see above.

 

Once again: The imprecision we discussed only refers to cases in which a tainted access path arrives at a method call into a sink method that is part of a library:

 

                a.sink();

 

In this case – and only in this case – we don’t regard the fields. There is no other way as long as we don’t have any more precise information about the behavior of the sink method. Since it’s a library method (otherwise we would have the code and could go deeper), we need external information to do anything better.

 

Best regards,

  Steven