connglli / elegant Goto Github PK

周报

2017.08.23 ~ 2017.08.29

工作概述

同上周计划所述，本周开始了开发工作，首先明确定位和开发安排：

• 定位：fic-finder 初步欲实现为一个 CLI 工具，后期将迭代为一个 web 工具。
• 开发安排：
  1. 框架的搭建
  2. 配置文件的约定与读写
  3. 实现核心算法
  4. 进行测试并改进
  5. 搭建网站，实现 web 端上传，处理后返回 web 端，做成可用的配套工具，同时提供更丰富的 web 端配置。

框架的搭建

fic-finder 初步欲实现为一个 CLI 工具，按照如下的方式运行：

java -cp ficfinder.jar --models=models.json --apk=xxx.apk 

目前初步打算先实现两个配置项：

--models 使用到的 acpairs 配置文件
--apk    欲分析的 apk 文件位置

其中，配置文件声明方式待会会有详述。

fic-finder 的初步架构如下图所示：

         input
           |
           v
+----------------------+
|        Configs       |     issue handles
+----------------------+     -------------
           | set               |   |   |
           v                   v   v   v
+----------------------+   +---------------+
|    Env: acpairs..    |   | Issue Tracker |
+----------------------+   +---------------+
           | provide               ^
           v                       |
+----------------------+    emit   |
|         Core         | ----------+
+----------------------+
 

首先进行 配置Configs 的读取并进行 全局Env 的设定，然后开始运行 核心算法Core，运行过程中，Core 从 Env 获取所需的数据，当发现问题时会 emit 到 Issue Tracker 利用挂载在其上的 Issue Handles 作统一的处理，欲实现 Layer、Filter、Pub/Sub 的模式。但目前功能尚少，可能还不是很清晰。(这样的实现还可以添加 Hooks 来形成框架 framework，而不仅仅是一个库 library)。

配置文件的读写

同最早的考虑对应，我们利用 json 这种简便易读开销小的格式来对 ApiContext Model 进行配置，使用 json 考虑到如下几个方面：

1. 基于开闭原则
2. 利用配置文件容易实现多应用交互（爬虫爬文档我觉得还是必要的，因此需要一个使两者进行交互而又不耦合的工具，小东西用不到消息队列，就用配置文件）
3. 考虑到后期要进行 web 端，json 小巧开销小。

配置文件格式形如下：

[
  {
    "api": {
      "@type": "method",
      "pkg": "android.media",
      "iface": "AudioMedia",
      "method": "setRouting",
      "ret": {
        "pkg": "",
        "iface": "void"
      },
      "paramList": [
        {
          "pkg": "",
          "iface": "int"
        },
        {
          "pkg": "",
          "iface": "int"
        },
        {
          "pkg": "",
          "iface": "int"
        }
      ]
    },
    "context": {
      "min_api_level": 1,
      "max_api_level": 3
    }
  },
  {
    "api": {
      "@type": "field",
      "pkg": "android.content",
      "iface": "Intent",
      "type": {
        "pkg": "java.lang",
        "iface": "String"
      },
      "field": "EXTRA_REMOTE_INTENT_TOKEN"
    },
    "context": {
      "min_api_level": 5
    }
  },
  {
    "api": {
      "@type": "iface",
      "pkg": "android.provider.SyncStateContract",
      "iface": "Constants"
    },
    "context": {
      "min_api_level": 5
    }
  }
]

正如上述所示，配置文件由一个 数组 构成，数组内对每一个 Model 都进行了语义化的描述，每个 Model 由两部分即 api 和 context 组成。

api

对于任意一个 api，都必须含有 @type 和 pkg 字段，其中 @type描述了该 api 的类型，pkg描述了该 api 所处的包。

目前根据 @type 主要有 3 种不同的 api ：

• @type = iface，这种类型的 api 针对接口与类，必须含有iface字段，它表示类名，如Constants；如果是B是A的内部类，请用A$B；对于泛型类，请使用类型擦除把泛型去掉，如 Set<T> 将擦除为 Set。
• @type = method，这种类型的 api 针对方法，必须含有method 、ret和paramList字段。其中，method表示该方法的方法名，ret表示返回值类型，paramList表示该方法的参数类型，他们同pkg一起构成了函数的签名；对于泛型参数/泛型返回值，请擦除掉，如 T 将擦除为 java.lang.Object，Set<String> 将擦除为 Set；对于不定参数，请使用数组表示，如 int... 将表示为 int[]。
• @type = field，这种类型的 api 针对属性，必须含有field和type字段。其中，field表示该属性的名称，type表示该属性的类型，他们同pkg一起构成了属性的签名。

context

目前 context 主要有以下几个字段组成，任何一个都是可选的：

• min_api_level：该 api 支持的最小 API level（并非严格是 android doc 里指示的 added in API level xxx），默认为 1
• max_api_level：该 api 支持的最大 API level（并非严格是 android doc 里指示的 deprecated at API level xxx），默认为 27
• min_system_level：该 api 支持的最小系统版本号，默认为 1
• max_system_level：该 api 支持的最大系统版本号，默认为 `27
• bad_devices：该 api 可能会出现问题的设备标识，默认为 []
• important: 指示比较重要的指标，当该指标被检测到后将跳过剪枝阶段，直接进行 issue 报告。值为 min_api_level/max_api_level/min_system_level/max_system_level/bad_devices 中的一个。
• message: 想要在技术报告中提示开发者的消息。

系统运行概述

目前的工作进行到 开发安排 的第二个阶段结束，系统可以正确读取配置文件并对全局进行设置，同时获取 CallGraph。系统运行流程如下：

系统的入口位于 Application，进入系统，首先由Configs（单例）进行配置选项的分析与全局环境的设置和初始化，目前包括：

1. 对 models 选项对应的 json 文件进行读取并进行 Env 的设置，详情于 Configs.parseModels。
2. 对 apk 选项对应的 apk 文件进行假读取和 App 的创建与设置，详情于 Configs.parseApk。

配置分析结束后，将进入Core，Core的运行预计将有 3 各阶段（也可能为了可扩展性和可框架而进行更多阶段的设置从而能够提供更多的 Hooks ）：

1. setUp：对 apk 文件进行真正的读取，并获取 CallGraph。
2. core：执行核心算法，在执行过程中将与 Env 和 Issue Tracker 进行交互（后者目前还未实现，将实现成 Pub/Sub 模式，从而方便对 Issue 进行监听并实现插件式分析）。
3. tearDown：结束后的收尾工作。

项目地址：fic-finder

暂放于 Github，牵扯到 core 实现时将进行搬迁。由于涉及 android 的库，比较大，所以没上传与 android 相关的库，可能直接 clone 下来没法跑，如果要跑的话，在这里或者这里多下载几个（最好全下，android-16 对于目前来说是必须的）放到 assets/android-platforms 下。

周报

2017.11.08 ~ 2017.11.14

已经一个月不做汇报，因此这周的汇报先对上次汇报的内容做一个回顾和总结，然后给出这周的工作做一个整理 : )。

回顾和总结

上次汇报已经提到，之前的代码已经完成了整个项目的搭建和基本功能代码的编写，但有几个问题仍需解决：

1. SDG

我们只在代码中对每个方法进行了 PDG 的构建，但 SDG 并未进行。

2. unitIteratorOfPDGNode

Set<Unit> runBackwardSlicingFor(Callsite callsite) 依赖于方法 Iterator<Unit> unitIteratorOfPDGNode(PDGNode n)，该方法做了如下假设：

假设 PDGNode 的类型仅有 CFGNODE 和 REGION 两种，因为 Soot 的 javaDOC 中有这么几句：

In essence, the PDG nodes represent (within them) either CFG nodes or Region nodes.

3. canHandleIssue

boolean canHandleIssue(ApiContext model, Unit unit) 目前实现过于简单，上面也提到过，是个难点。

本周工作整理

根据上周的进展和问题，本周做了如下工作：

1. 对上次完成的代码进行初步测试，并在测试过程中基本确定了上面提到的 unitIteratorOfPDGNode 问题

上次的工作已经在 github 仓库的 master 分支 下，直接利用 CSipSimple 对这份简单实现版本的 FicFinder 进行第一次测试，测试结果很显然。没有报告任何 Issue，对于程序崩溃和乱报错误来说，这还算一个可以接受的结果。但显然，结果是错误的(CSipSimple 里有显而易见的 FIC 问题)，因此对代码打 log 进行了追踪。

在代码追踪的过程中，发现每次 unitIteratorOfPDGNode 都能返回预期的结果，说明上面的假设是成立的。

2. 对测试结果的分析

代码的追踪发现了以下几个问题：

1. callsite 寻找不充分。追踪发现，在寻找 callsite 时几乎所有 model 都没有任何 callsite 找到，主要问题出在 callgraph.edgesInto 这个方法上，由于 Call Graph 强依赖于程序入口，因此可能是 flowdroid 生成的 dummyMain 有问题，但得出这个结论的前提是其他代码没有问题。
2. slicing 生成不充分。目前 slicing 的生成仅仅依赖 PDG，使用的核心方法是 PDGNode.getBackDependets。因为目前还未涉及到 SDG，所以导致这个问题的原因主要是：a. 对核心方法的使用不当以及核心方法返回的不充分性。 b. SDG 尚未构建，导致 slicing 偏小。

3. 根据测试进行的改进

发现上述问题后，咨询了下 Lili，帮了大忙。对上述问题目前有了以下的讨论和解决：

首先对问题进行化简，先不讨论安卓应用，仅讨论一份简单的 java 代码，因此在上述仓库下创建了 java 分支 ，先来保证 FicFinder 可以对普通的 java 进行类似的分析。这次测试的代码使用了项目 test 目录下的 DozeChecker.java，我们在里面利用类 os 及其内部类 Build 模拟了一个 FIC 问题。

a. callsite 寻找不充分

咨询 Lili 后了解到，Lili 寻找对方法 M 的 callsite 的方法是通过遍历所有的语句来寻找，并未使用 callsite.edgeInto 这个方法。因此这个问题的原因究竟是不是 dummyMain 的问题现在还不能确定，但由于这次我们先讨论一份简单的 java 代码，不存在 dummyMain 的问题，因此我们暂时先使用 callsite.edgesInto，如果最终结果符合预期，我们便可以断定 dummyMain 有问题，否则将不是 dummyMain 的问题。

b. slicing 生成不充分

上面提到，这个问题的出现有两个原因。

首先针对第一个原因，利用 DozeChecker 对 FicFinder 进行追踪发现几乎每个 PDGNode 的 getBackDependets 大小都是 0，而 pdg.getDependents 却不是，因为暂时还并未查到 Soot 中所指的 backDependents 和 dependents 的区别，因此本着扩大 slicing 的想法暂时使用了后者。

然后针对第二个问题，我们说之所以需要 SDG 的部分信息是因为大多数开发者会通过 DozeChecker 中使用的方式（即提取一个公共方法出来，而并不是在每个需要监测的地方都重写判断逻辑）来进行兼容性解决，因此 PDG 或者说 intra-procedure analysis 并不能解决这种问题。目前的解决方案是，寻找 callsite 前面距离 callsite 最近(之后或许应该改成 k 邻近)的 IfStmt，对该 IfStmt 中使用到的变量(use value)进行反向追踪，寻找其定义(define value)的 AssignStmt 语句，并将其加入 slicing 中，如果这条 AssignStmt 进行了方法调用，则该方法的所有(之后应该进行更精确的寻找)语句都加入 slicing 中。

通过上述分析，目前修改 runBackwardSlicingFor 如下：

/**
 * Backward slicing algorithm.
 *
 * we find the backward slicing of a unit by:
 *  1. get the corresponding pdg, which describes the unit's method
 *  2. find the dependents of callerUnit
 *  3. find the nearest IfStmt of the caller unit
 *  4. find the dependents of ifUnit(which defines the variable used in ifUnit)
 *
 */
private Set<Unit> runBackwardSlicingFor(Callsite callsite) {
  Set<Unit> slice = new HashSet<>(128);
  Map<String, ProgramDependenceGraph> pdgMapping = Env.v().getPdgMapping();

  // 1. get the corresponding pdg, which describes the unit's method
  SootMethod caller = callsite.getMethod();
  ProgramDependenceGraph pdg = pdgMapping.get(caller.getSignature());
  Unit callerUnit = callsite.getUnit();

  // 2. find the dependents of callerUnit
  slice.addAll(findDependentOf(pdg, callerUnit));

  // 3. find the nearest IfStmt of the caller unit
  Unit ifUnit = null; int ifIdx = -1;
  List<Unit> unitsOfCaller = new ArrayList<>(caller.getActiveBody().getUnits());

  for (int i = 0; i < unitsOfCaller.size(); i ++) {
    Unit u = unitsOfCaller.get(i);
    if (!u.equals(callerUnit)) { if (u instanceof IfStmt) { ifUnit = u; ifIdx = i; } }
    else { break; }
  }

  // 4.  find the dependents of ifUnit(which defines the variable used in ifUnit)
  if (ifUnit != null) {
    IfStmt ifStmt = (IfStmt) ifUnit;
    // get use boxed, e.g. [$v1, $v2] of `if $v1 > $v2 goto label 0`
    Set<Value> useValuesOfIfUnit = new HashSet<>(2);
    for (ValueBox vb : ifStmt.getCondition().getUseBoxes()) {
      Value v = vb.getValue();
      // we only save Locals
      if (v instanceof Local) {
        useValuesOfIfUnit.add(vb.getValue());
      }
    }
    for (int i = ifIdx - 1; i >= 0; i --) {
      Unit u = unitsOfCaller.get(i);
      // $vx = ...
      if (u instanceof AssignStmt) {
        AssignStmt assignStmt = (AssignStmt) u;
        List<ValueBox> defBoxesOfAssignUnit = assignStmt.getDefBoxes();
        // check whether $vx in useBoxesOfIfUnit, if yes, then add it to slice
        for (ValueBox vb : defBoxesOfAssignUnit) {
          if (useValuesOfIfUnit.contains(vb.getValue())) {
            slice.add(assignStmt);
            // $vx = virtualinvoke method, then we need to add all stmt in method
            if (assignStmt.containsInvokeExpr()) {
              SootMethod method = assignStmt.getInvokeExpr().getMethod();
              slice.addAll(assignStmt.getInvokeExpr().getMethod().getActiveBody().getUnits());
            }
          }
        }
      }
    }
  }

  return slice;
}

4. 新的测试结果

因为目前我们简化了问题，目前的版本对 DozeChecker 的测试已经能够成功报告我们模拟的问题，但有一处误报，误报的原因会在下面提到：

API <com.example.DozeChecker: void go()> should be used within the context: 
	 android API level: [5, 26]
	 android system version: [1.7976931348623157E308, ~]
	 

API <com.example.DozeChecker: void go()> should be used within the context: 
	 android API level: [5, 26]
	 android system version: [1.7976931348623157E308, ~]

4. 发现的新问题

1. Soot 的同步问题：Call Graph 的构建是并行的，追踪时有几次中间运行结果不一致。解决方案，放到回调里。
2. Soot 在将 java 代码转换成 Jimple 的时候可能会做优化，在 DozeChecker 的检测里，对方法 isCompatible 转换后的 Jimple 代码如下所示：（可以看到并没有对 os.Build 的引用，这也就是上面提到的会误报的原因）

// java source code
public boolean isCompatible() {
  return os.Bulid.SDK_VERSION > 26;
}

// converted jimple target code
public boolean isCompatible() {
  com.example.DozeChecker this;
  this := @this: com.example.DozeChecker;
  goto label1;
label1:
  goto label2;
label2:
  return 0;
}

5. 接下来的任务

1. 解决上面提到的两个问题，尤其需要考虑第二个问题的解决方案。
2. 对 slicing 过程进行进一步调优，如上面提到的 k 邻近，以及更精确到查找。
3. 对 canHandleIssue 进行更精确到判断，需要涉及对判断语义的理解，从而降低误报率。
4. 上面三个问题解决后转到安卓。
5. 按以前计划进行下一步。

心声

• 相比前几周仅仅是写代码，这周看到的结果令人欣慰，虽然目前的结果精确性不高，误报率很大，但至少已经有了一个好的开头，接下来的调试和优化将是一个令人兴奋的过程。

周报

2017.12.06 ~ 2017.12.12

上周的时候提了两个问题，并给出了(暂定的)解决方案，这周对其进行了实现。这里将对这两个问题给出更详细的步骤，并对代码进行部分解释。

computeCallsite 寻找不充分导致误报率提高

上周简单提到，对这个问题的解决欲采用 indirect-caller 的方式进行解决。采用这种方式，我们容易想到，对于某个 api A，它将有 n0 个 0-indirect-caller，而在每个 0-indirect-caller 内部，将有 n0i 个真正的 callsite（即真正的调用点），并且对于每个 0-indirect-caller，将有 n1i 个 1-indirect-caller... 如此所有 call sites 将形成一棵调用树。如图所示：

有了上面的 call sites tree 后，我们寻找可能存在的 FIC issues 过程就变成了下面的 3 步：

1. 生成。即由 call graph 生成上面的图示。算法描述中将找到所有的 indirect-caller，但实际实现中考虑到现实以及性能我们使用 K-indirect-caller。
2. 剪枝。很容易想到，在开发者未做任何 FIC issues 的 fix 情况下，上面所有由叶子节点到根节点的调用链都是一条会产生 FIC issue 的调用。因此我们需要将上面的树进行剪枝，删掉其中开发者已经解决掉的节点：对于所有的 call site 进行遍历，删除所有已经删除的 call sites，如果某个节点内部的 call sites 全部被 fix，那么直接删除该结点(及其子节点)。
3. 路径生成。即 issue 触发。

重新描述一下算法过程：

algorighm do
  foreach api-context model ac in api-context model list do
    if (model does not satisfy FIC conditions)
      continue
    fi
	  
    callSitesTree = create_Tree(callgraph, model.api) # creation
    callSitesTree = prune_Tree(callSitesTree, model)  # pruning
    issues = genPathes_Tree(callSitesTree, model)     # generating
	  
    emit all issues
  done
done


function create_Tree(callgraph, api) do
  root = new Root({ caller: api })
  
  clarify all callsites of api by every callsite's method
  add all methods to root as root.method
  
  foreach method m in root.methods do
    childnode = create_Tree(callgraph, m)
    append childnode to root as a child node
  done
done


function prune_Tree(t) do
  queue = Queue(t.root)

  # we use BFS to traverse the tree
  while queue is not empty do
    node = queue.deque()
    foreach child node c in node.getChildren() do
      queue.enque(c)
    done
    
    foreach call site cs in node.getCallSites() do
      slicing = runBackgroundSlicing(cs)
      foreach slice s in slicing do
        if (s can fix issue) then
          delete cs in node
          break
        fi
      done
    done
    
    if node.getCallSites() == empty then
      while node.getParent() != t.root do
        node = node.getParent()
      done
      delete node in t
    fi
  done
done


function genPathes_Tree(t) do
	pathes = []

	foreach child node n in t.getChlidren do
	  genPathes_Tree(n)
	    .map(p, pathes.add(p.clone().append(t.caller)))
	done
	
	return pathes
done

代码实现位于 core，computeCallSitesTree 和 pruneCallSitesTree。

修改 canHandleIssue 以提高精确度

上周已经详细说明了提高精确度的方式，这里不再赘述。这部分关于 Callsite 和 IfStmt 的实现已经基本完成，并且能对我们上次提到的情况进行分析并正确输出（下面的输出中 PATH of method calling 是会引起 FIC issue 的一条调用链，以这样的方式呈现，应该能给开发者更多的信息）：

INVALID use of API: <android.app.Activity: android.app.ActionBar getActionBar()>
  PATH of method calling: [
    <com.example.fictest.MainActivity: void virtualCheck()>(~:58) ->
    <com.example.fictest.MainActivity: void _acpair_check_getActionBar()>(~:62) ->
    <android.app.Activity: android.app.ActionBar getActionBar()>
  ]
  SHOULD be used within the context:
     android API level:  [ 11, ~ ]
     android OS version: [ 1.0, ~ ]
     except:             [  ]
  Please check your api version or devices

INVALID use of API: <android.app.Activity: android.app.ActionBar getActionBar()>
  PATH of method calling: [
    <com.example.fictest.MainActivity: void virtualCheck()>(~:58) ->
    <com.example.fictest.MainActivity: void _acpair_check_getActionBar()>(~:65) ->
    <android.app.Activity: android.app.ActionBar getActionBar()>
  ]
  SHOULD be used within the context:
     android API level:  [ 11, ~ ]
     android OS version: [ 1.0, ~ ]
     except:             [  ]
  Please check your api version or devices

INVALID use of API: <android.app.Activity: android.app.ActionBar getActionBar()>
  PATH of method calling: [
    <com.example.fictest.MainActivity: void dontCheck()>(~:31) ->
    <com.example.fictest.MainActivity: void _acpair_check_getActionBar()>(~:62) ->
    <android.app.Activity: android.app.ActionBar getActionBar()>
  ]
  SHOULD be used within the context:
     android API level:  [ 11, ~ ]
     android OS version: [ 1.0, ~ ]
     except:             [  ]
  Please check your api version or devices

INVALID use of API: <android.app.Activity: android.app.ActionBar getActionBar()>
  PATH of method calling: [
    <com.example.fictest.MainActivity: void dontCheck()>(~:31) ->
    <com.example.fictest.MainActivity: void _acpair_check_getActionBar()>(~:65) ->
    <android.app.Activity: android.app.ActionBar getActionBar()>
  ]
  SHOULD be used within the context:
     android API level:  [ 11, ~ ]
     android OS version: [ 1.0, ~ ]
     except:             [  ]
  Please check your api version or devices

测试代码是：

public class MainActivity extends BaseActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);

        dontCheck();
        directCheck();
        functionalCheck();
        interfCheck();
    }

    @Override
    public void onBackPressed() {
        super.onBackPressed();
    }

    private void dontCheck() {
        _acpair_check_getActionBar();
    }

    private void directCheck() {
        if (Build.VERSION.SDK_INT > 11) {
            _acpair_check_getActionBar();
        }
    }

    private boolean isCompatible(int v) {
        return Build.VERSION.SDK_INT > v;
    }

    private void functionalCheck() {
        if (isCompatible((11))) {
            _acpair_check_getActionBar();
        }
    }

    private void interfCheck() {
        if (Compatiblity.isCompatible(11)) {
            _acpair_check_getActionBar();
        }
    }

    @Override
    protected void virtualCheck() {
        _acpair_check_getActionBar();
    }

    private void _acpair_check_getActionBar() {
        ActionBar actionBar = getActionBar();
        actionBar.setTitle("123");

        ActionBar secondActionBar = getActionBar();
        secondActionBar.setTitle("123");
    }

}

代码在 call-site-tree 分支。

关于 Value，发现了几点问题，现在还在考虑解决中。

2017.12.20 ~ 2017.12.26

从这周开始，任务主要是开始寻找更多的测试用例，针对之前 Lili 他们在实验中找到的问题进行分析，从而不断完善目前的版本。这周使用测试用例是 AnkiDroid。

编译

首先是对 AnkiDroid 几个有问题（buggy）以及问题被解决后（fixed）提交版本对进行了编译，其中（本周已经做的）主要包括以下 buggy-fixed 对：

很幸运的是，只是上述几个简单的 api 就已经覆盖了好几种不同的问题解决方式（bug fixing manner），同时暴露了当前版本仍然存在的问题。现在我们对目前收集到的、开发者可能使用的解决方式进行总结，并对目前存在的问题进行阐述。

问题解决方式

为方便描述，我们为每种解决方式都起一个名字，并给出一些简单的代码来描述。

1. direct-checking

这是我们最早想到的一种最简单的解决方式，也就是直接（direct）在 api 调用之前对版本等信息进行检查：

if (android.os.Build.VERSION.SDK_INT > 11) {
  invokeSomeFICApi();
}

2. method-checking

这一种也是我们很容易会想到的，既然每次都是用 1 中提到的最简单的方式，为简化代码，提取为一个公共的方法（method）是一种不错的选择：

if (isCompatible(11)) {
  invokeSomeFICApi();
}

3. static-checking

当跨类的时候，2 中提到的方式也会造成代码冗余，因此，提取代码到一个公共的兼容性检测类中以静态（static）方法的形式提供出来是个容易想到的方式：

if (Compact.isCompatible(11)) {
  invokeSomeFICApi();
}

4. reflection-fixing

直接对版本进行检查（checking）从而得知某些 api 可能在当前版本不合适需要开发者对方法和版本的映射关系有清楚地了解，然而当方法一多，或者开发者不太喜欢去记住哪些方法在哪些版本才出现这一映射关系，直接使用反射（reflection）的方式对开发者认为的可能会出现问题的方法进行检测，是一种简化记忆（但略微牺牲性能）的方式。描述起来可能不是很容易理解，代码更清晰：

// 开发者知道 getActionBar 可能会出现问题，但不知道是哪个版本会出现问题，直接利用运行时环境信息查看是否可用是一种简便（但略微牺牲性能）的方式。
Method getActionBar = Activity.class.getMethod("getActionBar");
if (null != getActionBar) { // 可用！
  ActionBar actionBar = (ActionBar) getActionBar.invoke(this);
  actionBar.setTitle("This is title");
}

5. polymorphism-fixing

某些 API 可能在不同的版本上变现不一致，或者在某个低版本引入但却在某个高版本删掉了，为简化逻辑，利用多态（polymorphism）并假设他们一直是存在的是一种更清晰有效的方式：

// 多态引入
public interface Compact {
    public void invalidateOptionsMenu(Activity activity);
}

public class CompactV3 implements Compact {
    @Override
  public void invalidateOptionsMenu(Activity activity) {
    // 构造一个空方法
  }
}

public class CompactV11 implements Compact {
    @Override
    public void invalidateOptionsMenu(Activity activity) {
        activity.invalidateOptionsMenu();
    }
}

// 使用的时候假设其一直存在
Compact compact;

if (getApiLevel() > 11) {
  compact = new CompactV11();
} else {
  compact = new CompactV3();
}

compact.invalidateOptionsMenu(this);

6. workaround-fixing

最后一种就是某些开发者根据 app 的特定情况使用的 workaround。针对这种，由于其与 app 特定场景以及使用情况有关，我们无法检测更无法预测，因此不作处理，这也是误报存在的地方。

当前版本问题阐述

目前为止，我们对这些解决方案总结成了上述 6 种方式，而从我们目前的工作来看，前 3 种以 checking 结尾（考虑到作者的思路就是对版本进行检测，因此以 checking 结尾，而后三种作者的思路聚焦于解决，因此以 fixing 结尾）的方式我们已经考虑到并暂时解决（从我们之前的测试来看，当然仍然需要更多的测试来巩固这一结论）了，而后三种还未解决，其主要原因在于：

1. 无法定位：对于 reflection-fixing，直接利用 call graph 我们无法定位某个 api 的调用。要想检测到，需要在 call graph 中对 Class.getMethod 这一方法进行查找，并根据具体的方法进行定位。
2. 无法判断：对于 polymorphism-fixing，这种其实我们已经定位到了（为证实这一点，在代码中引入了一个 call graph 可视化的工具，可以看到 flowdroid 生成 call graph 是可以捕捉到这一点的），因此使我们对其是否已经解决的判断不准确造成的，对这一点，还需要进一步修改。

提前祝许老师和 Lili 新年快乐！🎉🎉🎉

The line:
iterator = ((IRegion) n.getNode()).getUnitGraph().iterator()
in unitIteratorOfPDGNode(PDGNode n)

I think it would return the iterator of the unit graph instead of the Region.

What you are looking for might be iterator = ((IRegion) n.getNode()).getUnits().iterator()?

It would not affect your analysis as the PDG-based backslicing would always give you an empty set, since getBackDependet of the PDG might have an issue and always return 0.

周报

2017.11.15 ~ 2017.11.21

相比上周，本周的任务相对比较轻。首先我们回顾一下上周提到的接下来的任务：

5. 接下来的任务

1. 解决上面提到的两个问题，尤其需要考虑第二个问题的解决方案。
2. 对 slicing 过程进行进一步调优，如上面提到的 k 邻近，以及更精确到查找。
3. 对 canHandleIssue 进行更精确到判断，需要涉及对判断语义的理解，从而降低误报率。
4. 上面三个问题解决后转到安卓。
5. 按以前计划进行下一步。

根据上面提到的问题，本周首先针对 1 和 2 进行了解决。

问题 1.1 - Soot 的同步问题

上周提到，在进行代码追踪的时候发现代码执行中存在有几次中间运行结果不一致的现象，本考虑到将核心代码放到回调中执行，但查看 email-list 后发现官方给出的 flow-droid 的代码就是同步的代码，而非异步代码，因此这个问题暂留，随代码更新继续查看。

问题 1.2 - Soot 的优化问题

针对这种编译优化问题，如果我们把问题报出来，由于这个问题已经被开发者解决而我们却报告，将会导致误报率提高；如果我们不报，准确率将提高。因此本着**“降低误报率、提高准确性”**的原则，我们在这种问题上做一点 trick，考虑到大多数开发者对兼容性问题的解决一般都会以 *compatible* 命名，因此我们将检测方法名，如果方法名中存在 compatible 字段，我们认为问题已经解决。

问题 2 - k 邻近优化

我们知道，开发者对兼容性问题的解决方式多种多样，常见的解决方式在上次汇报中已经提到，然而，即便是这种常见的情况，仅仅使用最近的 IfStmt 来进行检测得到的结果仍然是宽泛的，考虑下面的情况：

public void someMethod() {
  ...
  if (isCompatible()) {
    for (int i = 0; i < 100; i ++) {
       if (i % 7) {
         someApi();
       }
    }
  }
  ...
}

可以看到，在上面对 someApi 的兼容性解决中，在检测到兼容性后中间还涉及了更多的代码，其中不乏 if/for 等流程控制语句，从而在代码中引入了更多的 IfStmt，而最近的 IfStmt 便不是针对兼容性问题的检测，因此我们引入常量 ENV_K_NEIGHBORS 来对 API 临近的 ENV_K_NEIGHBORS 个 IfStmt 进行检测，从而使得上述问题得到解决，最终得到的结果显然取决于 ENV_K_NEIGHBORS 的值。

修改代码如下：

/**
* Find K IfStmt neighbors
*
*/
private List<Map.Entry<Integer, Unit>> findKNeighbors(List<Unit> unitsOfCaller,
                                                      Unit callerUnit) {
  LinkedList<Map.Entry<Integer, Unit>> queue = new LinkedList<>();
	
  for (int i = 0; i < unitsOfCaller.size(); i ++) {
    Unit u = unitsOfCaller.get(i);
	
    // stop here
    if (u.equals(callerUnit)) { break; }
	
    // add to queue
    if (u instanceof IfStmt) {
      if (queue.size() == Env.ENV_K_NEIGHBORS) {
        queue.poll();
      }
      queue.offer(new HashMap.SimpleEntry<>(i, u));
    }
  }
	
  return queue;
}

剩余的问题

1. Soot 同步问题（随着代码继续更新再次查看是否还有类似问题）
2. 对 canHandleIssue 进行更精确到判断，需要涉及对判断语义的理解，从而降低误报率。
3. 上面三个问题解决后转到安卓。
4. 按以前计划进行下一步。

周报

2017.08.05 ~ 2017.08.09

论文

距离上次许老师给我论文到现在大概过去了一个月，上次迷迷糊糊读的文章到现在也是忘得差不多了，因此这周的首要任务便是对 Lili 学姐的论文进行了再读，并进行了一些记录从而对接下来的研究和开发工作做好铺垫和准备。下面是论文阅读过程中的一些记录，如有不正确还希望许老师和学姐学长指正！

Android 系统兼容性问题概述

我们知道，Android 自诞生到现在，已经拥有了丰富的生态(无线端、智能家居甚至嵌入式等)，而且版本迭代非常迅速，同时，基于 Android 原生的第三方 OS 也层出不穷，包括但不限于三星、LG、索尼、HTC、华为、中兴、小米等，也正是如此，才使得 App 在这不同的系统以及版本之间出现了各种兼容性问题，如正常运行在系统 A 上的 App 到了系统 B 可能就会白屏、崩溃等。

待解决的三个问题：

1. RQ1 - FIC 在 Android Apps 中有哪些类型？引起他们的根源是什么？
2. RQ2 - FIC 的普遍“症状”有哪些？
3. RQ3 - Android 开发者在开发中是如何解决这类问题的？其中有没有共性？

RQ1 - FIC issues 分类

2 大类，5 小类。

1. Device-Specific - 59%
   1. *Problematic drive implementation
   2. OS customization
      1. Functionality modifying
      2. Functionality arguments
      3. Functionality removal
2. Paculiar hardware composition
3. Non-Device-Specific - 41%
   1. *Android platform API evolution
   2. Original Android system bugs

RQ2 - “症状”

会导致出现应用崩溃、不正常工作、性能下降、用户体验下降等功能性和非功能性问题。

这些症状可能是应用特有的，对于此类很难做测试预言。

RQ3 - 解决方案和共性

通常问题的定位是非常具有挑战性的一项任务，以致于有些问题难于解决，但问题的解决却通常简单（如加一个判断、try-catch 语句块等）。

共性：查看设备信息、查看设备资源的可用性等。

FicFinder

兼容性测试：维度/搜索空间（版本迭代多、设备多样性、App 组件多）大

API-Context Pair Model

一个 API (i.e. issue-inducing api) 和 Context (i.e. issue-triggering context) 构成的元组。(i.e. acpair := (api, context))

• API follows its standard

• Context follows the following CFG

Context -> Context | Context^Condition
Condition -> Software_env | Hardware_env | API usage

因此，根据上述模型，调用某个 API 会造成兼容性问题，当调用这个 API 的上下文满足对应的 Context 的时候。

兼容性检测

提取 API-Context Pair 模型（25 out of 191）

Model 需满足条件：

1. 可以静态地进行检测（上下文不是仅当运行时才可以获取）
2. 它们会影响 App 在常见设备上的运行

FicFinder 算法

## ALGORITHM
# @params apk     预分析的 apk 文件
# @params acPairs 所用到的 API-Context 模型
# @return         分析到的 FIC issues
function analyseFICIssues(apk, acPairs) {
  for acPair in acPairs do
    # 获取所有调用
    callsites := GetCallSites(acPair.API)
    for callsite in callsites do
      # 检测是否符合 API 用法以及软件配置
      if MatchAPIUsage(callsite, acPair.CTX) and MatchSWConfig(callsite, acPair.CTX) then
        # 调用 Soot，根据程序依赖图和调用图确定  callsite 的所有依赖
        slice := BackwardSlicing(callsite)
        issueHanddled := false
        for stmt in slice do
          if stmt checks acPair.CTX then
            issueHanddled := true
          fi
        done
        if  issueHanddled == false then
          emit(a warning and debugging info)
        fi
      fi
    done
  done
}

备注：上述算法 BackwardSlicing 对Soot API的调用涉及到“程序依赖图”（program dependence graph）和“调用图”（call graph），且根据文中意思，这两种图的构建限于 Java 本身语言的机制（反射机制可以动态的添加方法等）而无法得到完全准确的解，因此 FicFinder 可能会误报。

Soot

限于某些原因（下面 心声 部分会提到），本周对 Soot 工具仅仅看了下文档介绍，还未做其他深入了解。

下周计划

1. 安装并配置 Soot，跑几个 Demo，并对程序依赖图和调用图做了解
2. 考虑 API-Context Model 的实现，主要考虑这么几个部分：
   1. 在没有 Lili 学姐的帮助下，能否根据论文中提到的5个项目中自己进行 Issue 的提取
   2. 在没有 Lili 学姐的帮助下，能否根据论文中提到的5个项目中自己进行 Model 的提取（尤其是配置项的选择）
   3. 如果上述两个工作可以完成，考虑配置文件的书写规则（json？xml？或者 spring 格式），这需要根据 java 来进行适配，当然直接读文件也是可取的，但并不友好。

心声

因为现在正在阿里做 Summer Intern，而且跟着一个比较急着上线的项目，而且本周周一到周三集团又对实习生进行了为期三天的百技培训，所以这周没能拿出比较多的时间看这个东西。下周开始还是应该好好安排实习和研究的时间，争取都能做到自己满意的结果。

P.S.
以前没写过周报，这周报的格式是阿里内部周报大家常用的格式（项目、技术、心声等等模块），不知道合不合要求...

周报

2017.09.20 ~ 2017.09.26

这周的工作相比前几周有了些进展，但问题还未完全解决。这次的周报还是主要汇报这周的工作进展，同时理一下目前仍然存在需要讨论的问题。

问题解决

首先说上周提到的三个问题：

1. 如何对 field 和 iface 进行定位
2. PDG 目前已经可以构建，并且可以成功得到针对某个 callsite 的依赖节点，但却无法明确地获得其对应的 Unit
3. 如何添加一个 intra-procedural 的 data-flow analysis 来对 DDG 进行捕获

上周提出这三个问题后 Lili 很快给出了解答，非常感谢！针对 Lili 的回答我也对代码进行了修改：

针对第一个问题，Lili 也提到很难对这种 API 进行定位，尤其是一些编译优化的存在使得底层代码变动的更大，比如直接使用常量折叠与常量计算把一些高级 API 里才会用到的常量直接利用字面量替换了进去。这种很难进行捕捉。因此这两种暂时进行了 @warning 提示。

代码中暂时以 TODO 的形式留下了：

case ApiField.TAG: {
    // TODO I have no idea how to get the callsite of a specific field

    System.out.println("@WARNING: Model of @field is not supported by now");

    // ApiField apiField = (ApiField) model.getApi();
    // SootField sootField = scene.getField(apiField.getSiganiture());

    break;
}

针对第二个问题，也是困扰了我一段时间的问题，Lili 的实现中直接使用了 Block 对应的 Units，而并未定位到具体的 Unit，这在分析的准确性上也不会影响，接受 Lili 的建议，这里我也直接这样做了。这部分代码的相关逻辑主要是这样（注释部分）：

/**
 * Backward slicing algorithm.
 *
 * we find the backward slicing of a unit by:
 *  1. get the corresponding pdg, which describes the unit's method
 *  2. find the corresponding PDGNode srcNode, which contains the unit
 *  3. find all the dependent PDGNodes of srcNode
 *  4. get all the units of each dependent PDGNode
 *
 */
private Set<Unit> runBackwardSlicingFor(Callsite callsite);

针对第三个问题，由于目前对 SDG 的了解不是很多，因此暂时还未实现。

进展

进展一

这周在稍微有点头绪后，先把整个代码需要运行起来的其他部分完成了，也就是 PubSub 模式的 Tracker/Issue。代码集中在 tracker 包下。

进展二

对检测 Issue 是否会得到解决做了初步判断，主要是根据 Context 给出的条件对 Jimple Stmt 进行判断，判断其是否会进行相关的环境判断(如 api level，devices)等，但现在的判断非常不精确，仅仅会检查其是否会对 os.Build 进行调用，具体的值判断还需要对 Stmt 进行分析，个人觉得这也是一个难点。由于针对不同的 API 会有不同的检测方式，甚至对同一种 API 也会有多种检测方式和实现方式，即使利用 slicing 恐怕也难以进行。还需进一步思考。目前这部分判断在：

/**
 * Check whether the stmt can handle the specific issue
 *
 */
public boolean canHandleIssue(ApiContext model, Unit unit) {
    // we only parse Jimple
    if (!(unit instanceof Stmt) || !((Stmt) unit).containsFieldRef()) {
        return false;
    }

    //
    // TODO CHECK
    //  I don;t know exactly what FieldRef of a Stmt is!!!
    //  what if a Stmt contains more than one SootField?
    //
    Stmt stmt = (Stmt) unit;
    SootField field = stmt.getFieldRef().getField();
    String siganiture = field.getSignature();

    if (model.needCheckApiLevel() || model.needCheckSystemVersion()) {
        return Strings.contains(siganiture,
                "android.os.Build.VERSION_CODES",
                "android.os.Build.VERSION.SDK_INT",
                "android.os.Build.VERSION.SDK");
    }

    if (model.hasBadDevices()) {
        return Strings.contains(siganiture,
                "android.os.Build.BOARD",
                "android.os.Build.BRAND",
                "android.os.Build.DEVICE",
                "android.os.Build.PRODUCT");
    }


    return false;
}

进展三

各部分到目前为止已经搭建好了，而且每部分也都有了基础的实现代码，接下来就到遗留问题了！

遗留问题

照常，对问题进行解释与说明：

SDG

SDG 构建还未进行，上面提到了。

unitIteratorOfPDGNode

Set<Unit> runBackwardSlicingFor(Callsite callsite) 依赖于方法 Iterator<Unit> unitIteratorOfPDGNode(PDGNode n)，该方法做了如下假设：

假设 PDGNode 的类型仅有 CFGNODE 和 REGION 两种，因为 Soot 的 javaDOC 中有这么几句：

In essence, the PDG nodes represent (within them) either CFG nodes or Region nodes.

直接认为该 DOC 是正确的(DOC 太乱，都不敢相信其正确性)，因此做了如下实现：

/**
 * In javaDoc of Soot, the following information are mentioned:
 *
 *   This class(PDGNode) defines a Node in the Program Dependence
 *   Graph. There might be a need to store additional information
 *   in the PDG nodes. In essence, the PDG nodes represent (within
 *   them) either CFG nodes or Region nodes.
 *
 * So we simply considered that as only CFGNODE and REGION are allowed
 */
private Iterator<Unit> unitIteratorOfPDGNode(PDGNode n) {
    Iterator<Unit> iterator = null;
    PDGNode.Type type = n.getType();

    // get iterator
    if (type.equals(PDGNode.Type.CFGNODE)) {
        iterator = ((Block) n.getNode()).iterator();
    } else if (type.equals(PDGNode.Type.REGION)) {
        iterator = ((Region) n.getNode()).getUnitGraph().iterator();
    } else {
        System.out.println("Only REGION and CFGNODE are allowed");
    }

    return iterator;
}

canHandleIssue

boolean canHandleIssue(ApiContext model, Unit unit) 目前实现过于简单，上面也提到过，是个难点。

心声

• :( 本来以为代码写起来会很简单，没想到会有这么多需要了解的知识点和( Soot 给挖的)坑。
• :) 还是需要继续学习。希望推荐代码静态分析相关的课程(慕课，Stanford，Coursera)！感觉网上的资料并不多，有些论文也确实难懂。
• :) 在使用 Soot 的过程中，看了下 WALA，是 IBM 出的，应该是一个 IBM 的大工程项目，对 SDG、Slicer 的支持也比较好。由于是 IBM 的软件工程项目，所以代码质量和文档质量还是信得过的，而且还有对 Javascript 进行静态分析的支持，在 Javascript 大行其道的今天，感觉以后使用 WALA 也会成为必选。现在开发中客户端( Android/iOS )项目转无线端( H5/Javascript )的非常多，感觉这也是一个研究点，对 Javascript 的分析与编译(Babel 和 Webpack 做的非常好)也应该是一个重点。

周报

2017.08.16 ~ 2017.08.22

工作概述

同上周计划所述，本周的主要工作集中于 Model 的粗提取和第一步精提取，以下是 Model 提取的信息。

Model的提取 - 1.1.2

Model Api-Context 表格

以下表格列出了我对大部分 Issue 的分析，其中并没有包含太多 OS 和 Driver 相关的 Issue，因为这些偏底层，有些代码一时半会也不太好理解。

备注

1. #9 不应该作为 API ，而应该作为 System 特性之类的，因为这不是 API 引起的，而是从 API level 11 引入的可选中特性。
2. #30 相关链接可以在这里找到。
3. #51 给出的 issues 链接可能有误，应该是这个。
4. #52 根据commit描述，不应该归为 FIC issue。描述中说的是 KitKat 及以上版本默认的手势系统对于 AnySoftKeyboard 这个 App 来说不是很合适，但这应该不能归结为一个 FIC issue。
5. #140 之所以位于 jdk 中的 Arrays 也会作为 Android FIC issues 出现，是因为：Android 为了提升性能，在内核中重新实现了 JVM 和 JDK，也正式因为这样，Oracle 才告 Google 侵权（知识产权，Oracle 认为 API 也是知识产权的一部分，Google 没有经过 Oracle 的同意就使用了 JDK 的 API ），也就造成了今天 Kotlin 成为了 Android 唯一的官方语言。
6. #146 应该归结为 system bug (同#147)，这不是因为 API 更迭引起的，而是系统实现，所以作者的解决方案也是根据 系统版本 （而非 API）来进行数字的隐藏。
7. #148 个人理解这是一种需求/功能的实现方式，虽然其中确有与版本相关的内容(有一个工厂方法来根据版本确定 TitleBarWebView 的类型)，但这不应该算作 API 更迭引起的 FIC issue。
8. #172/#177 给出的 commit hash 好像有问题...没搜到，其实 VLC 给出的链接好像都不怎么好用

Model 的提取 - 1.2

对上述提到的整个表格进行抽取后得到如下精简的表格

1. [S]：suggested，建议
2. [U]：unsuggested，不建议

小结

上表的分析同 Lily 学姐论文所述（数据也是从论文中取得的），FIC issues 中 Non-Device-Specific 的因素所占的比例更高，且在其中，API 更迭占的比重更高，但上表仍有以下几点不足值得继续修改：

1. 对于原数据中的 Device-Specific 部分，有些代码难于理解，只能根据 BUILD.MODEL 或者 BUILD.DEVICE 来进行粗略判断，准确性有待提高，同时上表对于这种情况也亟待补充。
2. 表格中所涉及 API 较多，大多 API 的使用均在官方文档有明确说明，所以不禁有这样的思考：既然引起 FIC issue 的问题占比最大的就是 API 更迭，那为何不对官方文档进行爬取，从而利用爬取到的 API 建立和废弃的信息进行 acpair 的建立？获取准确性将更高。

Weekly report - QUESTIONS SUMMARY

2017.08.23 ~ 2017.08.29

Complexity

I had thought to implement the core algorithms of fic-finder in one week, but it seems that it is quite a challenge for me, because of my little knowledge on PDG i.e. program dependence graph.

As we know, core of the algorithm of fic-finder is an operation/technique called “Program Slicing”, it is highly dependent on PDG, going backward down which, we can easily find all dependencies aka slicing of a specific method/field.

List<Node> runBackwardSlicingFor(Node target) {
  List<Node> slicing = new ArrayList<Node>();
  int ptr = -1;

  slicing.add(pdg.getNode(target));
  ptr += 1;

  do {
    Node n = slicing.get(ptr);
    Iterator<Node> iterator = n.getPrevious().iterator();

    while(iterator.hasNext()) {
      Node n = iterator.next();
      if (slicing.indexOf(n) == -1) {
        slicing.add(iterator.next());
      }
      ptr += 1; 
    }
  } while(ptr != slicing.size());
  
  return slicing;
}

As shown above, Program Slicing is quite easy when you get the PDG. However, the complex thing is the PDG itself.

This week, after I had knowledge of Program Slicing, I stepped to find the algorithm of PDG, and implement it by myself. But fine, it scared me. The paper stating its principle PAPER-The.Program.Dependence.Graph.And.Its.Use.In.Optimization is long and not easy to understand. By reading it and its slides as well as some other files(I attached it in this email), I figured out what is PDG and how to manually draw an easy PDG.

I marked word easy, because when it involves function invoking, things of PDG get quite complex. And I have not clearly understand how it runs. So it will continue taking a somewhat long time for me to figure it out clearly.

"But whatever, implementation sometime is less relavant to the principle. There must be many libraries already implementing PDG and we can just use it by now." I thought. Yes, soot implements a PDG, but as the maintainer said: "It lacks the implementation of DDG and I seldom use it."(Sorry that I cannot find url of this sentence). And when I used it, the program just complained "java.lang.RuntimeException: PDG construction: A and B are not supposed to be the same node!", I searched and no solutions found.

Then I turned to Github, tried to find some libraries, but to be honest, I couldnot find some suitable libraries that we could easily and directly use. The following libraries implenents PDG as part of it:

• wala: a large program analysis lib, just like soot, but not compatible
• indus: another program analysis lib, Jimple based, compatible with soot
• Slithice: a slicer. No docs offered, not easy to use, soot based
• jpdg: A personal project, soot based

As you can see above, the last three libs/projs are soot based, but they directly use soot to analyse general jars not android apks, and they all use a separate soot as their engine, that is to say, if we directly include them, we will have 2 soot instance, and the performance will be quite bad.

By now, I have added some files of jpdg to fic-finder, and I am reading the source codes of jpdg now. jpdg is the least large one of these three, but question is it doesn't provide any interface to access the inner data structure of it's node and node relationships. So I intend to rewrite jpdg so that we can use one soot instance and I will have more knowledge on PDG(It may take a long time).

Structure and new Ideas

I add some new todo features to fic-finder:

• Make every apk containable, that is to say, every apk runs separately, and fic-finder will have the ability to handle multiple apks
• A official website that can, receive apk and models rules, and return issues
• The website can hold the following functions:
  • separately run a FIC checking using the predefined rules
  • separately run a FIC checking using self-defined i.e. customized rules
  • separately run a FIC checking using the mixed rules i.e. predefined and customized
  • request a list of api-models, well defined rules i.e. quite useful rules will be added to predefined rules
  • a graph showing the issue distributions on api-context models

The structure will be:

            apks                                      +-------------+
             |         +--------------------------+-> | Container 2 |
             v         |                          |   +-------------+
  +----------------------+  +-------------------+ |   +-------------+
  |        Configs       |  |   issue handles   | +-> | Container 3 |
  +----------------------+  |   -------------   | |   +-------------+
             | set          |     |   |   |     | +->      ...
             v              |     v   v   v     | |   +-------------+
+---------------------------+                   | +-> | Container N |
| +----------------------+   +---------------+  |     +-------------+
| |    Env: acpairs..    |   | Issue Tracker |  |
| +----------------------+   +---------------+  |
|            | provide               ^          |
|            v                       |          |
| +----------------------+    emit   |          |
| |         Core         | ----------+          |
| +----------------------+                      |
|                                   Container 1 |
+-----------------------------------------------+

Backup

Could Lili provide some tutorials/libs on soot as well as PDG that I can directly ref? Thanks :-)

周报

前段时间到上周对 Lili 实验使用的 App 进行了部分构建，虽然还没有完全构建完，但大概 2/3 已经处于可用状态。按上周说的，这周就利用截止目前实现的版本对这几个 App 进行了测试，但测试结果确实不太理想，这里对发现的问题以及部分修正做一下陈述。

✅ out of memory heap

问题陈述

当 apk 相对较大方法相对较多时，目前的 fic-finder 经常爆堆（开 2G 都不够用），弹 OutOfMemory 异常。

检查后发现，是最初学习使用 soot 内置的 ProgramDependenceGraph 的时候因为不熟悉理解不深导致写的代码有点问题，当时按照一位博主的博客在 "jtp" 阶段把所有的 PDG 都进行了存储，每个 PDG 体积都不小，而 PDG （目前）仅在做 backward program slicing 的时候会发挥作用，而且也只有这里面的很少一部分才会用到，从而造成了不必要的堆开销。

解决方案

放弃对 PDG 的预先处理，采用懒处理的方式，即用即生成 PDG。

❗️ call graph incompleteness

问题陈述

之前 Lili 也说，soot 生成的 call graph 是不完整的，实验发现也确实是这样（但这也是情有可原，任何静态分析都不可能达到 100% 的准确性），这就导致针对某一条 api 找到的 call site 不足，从而漏报。

解决方案

重写 computeCallSites 的第 251 行，在获取 call site 的时候：

1. 使用内建 call graph 的 edgesInto() 得到一部分 call site
2. 遍历 App 所有的类的所有方法，对每条语句都进行查询

这里说明一下为什么仍然不能舍弃使用内建的 call graph 进行 call site 的查找：2 中的方法仅仅能对 明显 是一个调用点的语句进行获取，而无法识别多态等复杂运算，而 call graph 在构建的过程中会使用 CHA/RTA/VTA/… (目前了解也比较少，之后会看相关论文补一下对 OOP 做静态分析的知识) 等方法对类间关系进行捕获、会做 PointsTo 分析对指针（引用）进行捕获，从而尽可能多地识别多态等 比较隐含 的调用点。

这里重写的方法 findCallSites位于 utils/Soots.java，这个类里写了一些无状态的纯净方法来方便地利用 soot，比如：

• findInternalForwardSlicing 可以获取 intra-procedural 的 static forward program slicing。
• findDominators 可以获取 inter-CFG 中某条语句的 dominators，与之相对应的还有 findImmediateDominator/findPostDominators/findImmediatePostDominator 等。

以下是针对 findCallSites 的实现：

// doFindCallSites finds the relatively complete set of call sites of a callee, by:
// 1. the built-in call graph
// 2. the classes cached in invokingStmtsCache
private static Map<SootMethod, CallSites> doFindCallSites(SootMethod callee, CallGraph cg) {
    Map<SootMethod, CallSites> callers = new HashMap<>(1);

    // firstly we get all callers from the incomplete call graph built in soot
    Iterator<Edge> edgeIterator = cg.edgesInto(callee);
    while (edgeIterator.hasNext()) {
        Edge       edge     = edgeIterator.next();
        SootMethod caller   = edge.src();
        Unit       callSite = edge.srcUnit();

        if (callers.containsKey(caller)) {
            callers.get(caller).addCallSite(callSite);
        } else {
            callers.put(caller, new CallSites(callee, caller, callSite));
        }
    }

    // then we traverse all invoking statements, and check
    for (Map.Entry<SootMethod, Set<Unit>> entry : invokingStmtsCache.entrySet()) {
        for (Unit u : entry.getValue()) {
            InvokeExpr invokeExpr = ((Stmt) u).getInvokeExpr();
            if (callee.equals(invokeExpr.getMethod())) {
                if (callers.containsKey(u)) {
                    callers.get(entry.getKey()).addCallSite(u);
                } else {
                    callers.put(entry.getKey(), new CallSites(callee, entry.getKey(), u));
                }
            }
        }
    }

    return callers;
}

❗️ backward program slicing incompleteness

问题陈述

之前提到，call graph 的不完整性同样导致了 inter-CFG 的不完整性，进而导致了 backward program slicing 的不完整性。

解决方案

之前打算使用 AEM 来解决这个问题，但工程量偏大，而且这周翻了翻 soot-infoflow 的 javadoc 发现了一个 IInfoflowCFG 的类，它继承自 IntraproceduralCFG，快速地翻了翻 FlowDroid 的论文也发现，FlowDroid 本身已经对 android 进行了建模，因此想着暂时先放一放 AEM ，用这个 IInfoflowCFG 对 runBackwardSlicing 进行了一下重新实现，因为 slicing 主要包括 data-flow dependent slicing 和 control-flow dependent slicing 两部分，因此就对这两部分单独进行了实现：

• 数据流依赖暂定算法：对一条特定语句中的 use 变量集合递归的进行 backward program slicing，对于涉及函数参数的变量，利用 call site 递归地向其方法中进行查找。

# statement: the statement that needs doing program slicing
# indices:   the indices of arguments that needs tracking (some
#            arguments of a method may not need tracking)
function program_data_dependencies_slicing_except(statement, ex_values) do
  ret_statements = { statement }
  for v in statement.used_values do
    if (v in ex_values) do continue; done # ignore that does not needs tracking ones
    redefined_statements = get_redefined_statements(v)
    for s in redefined_statements do
      if (v is redefined by this method arguments) then
        arg_idx = index of this index
        callsites = get_call_sites(statement.method)
        for callsite in callsites do
          tracked_arg = callsite.invoked_method.arguments.get(arg_idx)
          ret_statements.union(
            program_data_dependencies_slicing_except(callsite, callsites.used_values.exclude(tracked_arg)))
        done
      else
        ret_statements.union(program_data_dependent_slicing_except(s, a empty set))
      fi
    done
  done
  return ret_statements
done

function program_data_dependencies_slicing(statement) do
  program_data_dependencies_slicing_except(statement, a empty set)
done

• 控制流依赖暂定：使用内建的 inter-CFG 来获取针对某条语句的所有 dominators 并加入到 slicing 中。

function program_control_dependencies_slicing(statement) do
  ret_statements = findDominators(u);
  return ret_statements;
done

其他

上述第三个问题利用截至目前的解决方案再去跑测试，发现效果还是不好，而且上周提到的问题 (与 compact 类和生命周期相关的) 仍然没能解决， 测试 IrssiNotifier/PactrackDroid/transdroid/AntennaPod/Kore/k-9/android-backdroid/AnySoftKeyboard/QKSMS/PocketHub 后，仅有 PactrackDroid 和 IrssiNotifier 发现并报告了几个错误，但报告的错误都是 TP。

问题可能是 IInfoflowCFG 仍然有点问题，但也可能是其他代码甚至是 api context pairs 最初构建的问题，针对此，接下来的任务其实是聚焦在：

1. 看一下最开始的 weekly report，把最初搜罗下来的 api-context pairs 再次进行核对，修改并完善一下（记得当初是对 device specific 相关的 issue 都没有很仔细地进行记录）。
2. 针对每个 app 和 Lili 实验中发现的 issue 一个个进行核对，看看漏算了哪些，算法哪里不足，代码在哪里出了问题。
3. 稍微深入地了解下 FlowDroid 对 android 建模的方法（这周快速浏览了一下，没怎么弄懂），搞清楚一下 IInfoflowCFG 的构建。

I read the weekly reports in this project and want to use the function of program slicing in Android application.Could you tell me how to get this function?Is there API that I can use to directly get the program slicing of Android application?Thanks a lot!

周报

这周的工作就按照上周所说的：

1. 根据之前的 weekly report (第 4 份) 重新对比了从 empirical study 中获取到的 api context pair，并做了重新整理（目前只是重新修改和整理了之前已经发现的，对之前没能发现的这周也暂时没有分析，这是后续的工作）。
2. 对目前已经构建好的所有 app，关掉 validate 阶段（每个都是 detect/validate/generate 三个阶段，分别做 call site tree 生成、剪枝和生成 issue 的工作），一个个地查看能否发现论文和 github issues 中提到的问题。

因为这周的工作比较零碎，所以以单条列在下面，其中 ✅ 表示发现并已经完成的部分，❗ 根据优先级（越多表示优先级越高）表示发现并且正在进行/还未进行的工作。

1. ✅ 需要在 ApiContext 的 context 里加入新的标记

   • message:string 用于打印一些针对该 acpair 想要输出的信息。
   • important:string 当非空时，表示通知 ficfinder，当 important 对应的 context 的条件检测到时，不需要进行 validate，如果 detect 到，直接报告。

   如：

   {
       "api": {
           "@type": "method",
           "pkg": "android.view",
           "iface": "View",
           "method": "setFocusableInTouchMode",
           "ret": {
               "pkg": "",
               "iface": "void"
           },
           "paramList": [
               {
                   "pkg": "",
                   "iface": "boolean"
               }
           ]
       },
       "context": {
           "min_api_level": 8,
           "important": "min_api_level",
           "message": "this api is recommended to be used together with `void setFocusable(boolean)` when your app is running on Froyo(2.2) or lower. Check https://issuetracker.google.com/issues/36908479 for more help"
       }
   },
   {
       "api": {
           "@type": "method",
           "pkg": "android.widget",
           "iface": "RemoteViews",
           "method": "setViewVisibility",
           "ret": {
               "pkg": "",
               "iface": "void"
           },
           "paramList": [
               {
                   "pkg": "",
                   "iface": "int"
               },
               {
                   "pkg": "",
                   "iface": "int"
               }
           ]
       },
       "context": {
           "min_api_level": 8,
           "important": "min_api_level",
           "message": "this api is not recommended to be used together with progress bar when your app is running on Froyo(2.2) or lower. If you have to use it on Froyo(2.2) or lower, try to wrap the progress bar in a LinearLayout or FrameLayout and use setViewVisibility() to make the Layout INVISIBLE/GONE instead of the progress bar. Check https://issuetracker.google.com/issues/36921090 for more help"
       }
   },
   {
       "api": {
           "@type": "method",
           "pkg": "android.content",
           "iface": "ContentProvider",
           "method": "query",
           "ret": {
               "pkg": "android.database",
               "iface": "Cursor"
           },
           "paramList": [
               {
                   "pkg": "android.net",
                   "iface": "Uri"
               },
               {
                   "pkg": "java.lang",
                   "iface": "String[]"
               },
               {
                   "pkg": "android.os",
                   "iface": "Bundle"
               },
               {
                   "pkg": "android.os",
                   "iface": "CancellationSignal"
               }
           ]
       },
       "context": {
           "max_api_level": 23,
           "important": "max_api_level",
           "message": "this api is recommended to be used together with the permission controll when your app is running on android 23 or higher. Check https://github.com/ankidroid/Anki-Android/commit/f5fab36ce309ce2d1e327cfc3fb59db85c609f96 for more help"
       }
   },
   {
       "api": {
           "@type": "method",
           "pkg": "android.content",
           "iface": "ContentProvider",
           "method": "update",
           "ret": {
               "pkg": "",
               "iface": "int"
           },
           "paramList": [
               {
                   "pkg": "android.net",
                   "iface": "Uri"
               },
               {
                   "pkg": "android.content",
                   "iface": "ContentValues"
               },
               {
                   "pkg": "java.lang",
                   "iface": "String"
               },
               {
                   "pkg": "java.lang",
                   "iface": "String[]"
               }
           ]
       },
       "context": {
           "max_api_level": 23,
           "important": "max_api_level",
           "message": "this api is recommended to be used together with the permission controll when your app is running on android 23 or higher. Check https://github.com/ankidroid/Anki-Android/commit/f5fab36ce309ce2d1e327cfc3fb59db85c609f96 for more help"
       }
   },
   {
       "api": {
           "@type": "method",
           "pkg": "android.content",
           "iface": "ContentProvider",
           "method": "insert",
           "ret": {
               "pkg": "android.net",
               "iface": "Uri"
           },
           "paramList": [
               {
                   "pkg": "android.net",
                   "iface": "Uri"
               },
               {
                   "pkg": "java.lang",
                   "iface": "String"
               },
               {
                   "pkg": "java.lang",
                   "iface": "String[]"
               }
           ]
       },
       "context": {
           "max_api_level": 23,
           "important": "max_api_level",
           "message": "this api is recommended to be used together with the permission controll when your app is running on android 23 or higher. Check https://github.com/ankidroid/Anki-Android/commit/f5fab36ce309ce2d1e327cfc3fb59db85c609f96 for more help"
       }
   },
   {
       "api": {
           "@type": "method",
           "pkg": "android.content",
           "iface": "ContentProvider",
           "method": "delete",
           "ret": {
               "pkg": "",
               "iface": "int"
           },
           "paramList": [
               {
                   "pkg": "android.net",
                   "iface": "Uri"
               },
               {
                   "pkg": "android.content",
                   "iface": "ContentValues"
               },
           ]
       },
       "context": {
           "max_api_level": 23,
           "important": "max_api_level",
           "message": "this api is recommended to be used together with the permission controll when your app is running on android 23 or higher. Check https://github.com/ankidroid/Anki-Android/commit/f5fab36ce309ce2d1e327cfc3fb59db85c609f96 for more help"
       }
   },
   {
       "api": {
           "@type": "method",
           "pkg": "android.content",
           "iface": "ContentProvider",
           "method": "bulkInsert",
           "ret": {
               "pkg": "",
               "iface": "int"
           },
           "paramList": [
               {
                   "pkg": "android.net",
                   "iface": "Uri"
               },
               {
                   "pkg": "android.content",
                   "iface": "ContentValues[]"
               },
           ]
       },
       "context": {
           "max_api_level": 23,
           "important": "max_api_level",
           "message": "this api is recommended to be used together with the permission controll when your app is running on android 23 or higher. Check https://github.com/ankidroid/Anki-Android/commit/f5fab36ce309ce2d1e327cfc3fb59db85c609f96 for more help"
       }
   },
   {
       "api": {
           "@type": "method",
           "pkg": "android.content",
           "iface": "ContentValues",
           "method": "put",
           "ret": {
               "pkg": "",
               "iface": "void"
           },
           "paramList": [
               {
                   "pkg": "java.lang",
                   "iface": "String"
               },
               {
                   "pkg": "java.lang",
                   "iface": "Short"
               }
           ]
       },
       "context": {
           "bad_devices": [
               "saga"
           ],
           "important": "bad_devices",
           "message": "this api is recommended to be used together with cv.put(Data.RAW_CONTACT_ID, someId) when your app is running one HTC desire S series. Check https://github.com/r3gis3r/CSipSimple/blob/340eea18b5143d1ff0c33c5fab4b5be272689203/src/com/csipsimple/utils/CallLogHelper.java for more help"
       }
   },

   其他的还有 setFocusable/setFocusableInTouchMode。

2. ✅ 所有的 IssueHandle 改一下，统一放到一块儿，ApiContext 加一个 report(Out) 方法，用于对 ApiContext 进行报告，IssueHandle 仅仅报告 Issue 相关的，而不报告 ApiContext 相关的。改成类似于：

   model.report(out);
   out.out(...);
   
   // 加一句
   out.out("Ignore it if it does not happen in your project.");

3. ✅ 与 2 相关，需要加一个配置选项—out 用于对 technique report 进行重定向输出。

   • stdout: System.out
   • stderr: System.err
   • file: new PrintStream("file")

4. ✅ 与 2 相关，PubSub 加入默认实现，即 Tracker 的实现，放到 utils 下，同时修改 Tracker 仅继承自 PubSub 而已，放到 core.finder 下。

5. ✅ 与 2 相关，加入一个默认的 Handle 类，在 core.tracker 的 tracker 中其中包含域 PrintStream out 用于输出，把所有的 IssueHandle 继承自它。

6. ✅ 结构：

   core +- finder - pfinder, rfinder, ...
        +- tracker - Tracker, Issue, Handle
        +- env - Env
        `- config - ConfigParser(=> Parser)
   

7. ✅ 根据 valgrind 的输出格式重新整理输出格式，方便开发者查阅，主要是进行 api 合并。

8. ❗ 加一个 max_version 选项，用于配置当前最大 android 版本环境。

9. ❗❗ program slicing 的时候还需要加入 <clinit> （类的 static 代码块） 的代码，有些开发者会利用这个特性检查是否可用。

10. ❗❗ 主要的问题：1. acpair 分析的还是少，不够。 2. program slicing 还是有问题。

11. ❗❗❗ ==任务== 注释掉 validate() 只用 detect 和 generate 先查看能报出多少 ，解决后再考虑 validate 的问题。

12. ❗ PrintStream.close() 别忘了。

13. ❗ 把测试代码放到 fic-finder/test 下，不要太分散。

14. ❗ 加一个verbose 选项，用于输出所有的调用链信息，如果没有 verbose 仅输出最近一次的调用（即调用点，从而简化输出）。

15. ❗❗ 优化：Issue里存的调用链不要用链表了，用树表示，既方便 13，又省内存。

16. ❗ 升级 Soot 到 3.0.0，FlowDroid 到 develop 版本，使用最新的日志系统，把 Soot 和 FlowDroid 输出的所有 debug 的东西都给关了。

17. ❗ 找一个可以移除第三方库代码的 jar 工具，用到 Soots.findCallSites 里。

针对现在构建成功的 App，检测以及未检测到的 API 及其原因记录（按 11 所述，仅仅使用 detect 阶段，屏蔽 validate 阶段）：

1. IrssiNotifier/AnkiDroid/Kore/BankDroid 论文中没有发现问题，暂没测试。
2. AnternaPod
   1. ✅ AsyncTask.execute 对 empirical 分析不准确，以及对 android api doc 阅读不仔细，导致之前的 model.json 里没加入。android api doc 里显示这个 API 在 API level 1 就加入了，但同时也显示，从 API level 11 开始，这个 API 不提供真正的并行能力。
   2. ✅ AlarmManager.set 对 empirical 分析不准确，以及对 android api doc 阅读不仔细，导致之前的 model.json 里没加入；findCallSites 方法错误地把其所在的类当成第三方库过滤掉了。android api doc 里显示这个 API 在 API level 19 后无法保证设置时间的准确性，在对时间准确性要求极高的 app 中不应该使用这个 API，应该考虑使用 setExact/setWindow。
   3. ❗ support.v7.setSupportActionBar 对 empirical 分析不准确，这是一个 device specific 的 API，导致之前的 model.json 里没加入。这个 API 会使得部分三星手机挂掉。
3. AnySoftKeyboard
   1. ✅ AsyncTask.execute 同 AnternaPod.1。
4. Transdroid
   1. ❗ support.v7.setSupportActionBar 同 AnternaPad.1
5. k-9
   1. ✅ AlarmManager.set 同 AnternaPad.2
6. PactrackDroid
   1. ✅ ConnectivityManager.getBackgroundDataSetting 这一条之前的版本可以发现。
7. QKSMS
   1. ✅ Resources.getDrawable 对 empirical 分析不准确，导致之前的 model.json 里没加入。这个 API 在 API level 22 被废弃。
   2. ❗ android.text.format.Time 是一个 iface，暂时还没考虑。
   3. ❗ support.v7.setSupportActionBar 同 AnternaPad.1
8. PocketHub
   1. ❗ support.v7.setSupportActionBar 同 AnternaPad.1
9. 1Sheeld
   1. ✅ AlarmManager.set 同 AnternaPad.2
10. ConnectBot
    1. ✅ MenuItem.setShowAsAction 这一条之前的版本可以发现
11. Conversations
    1. ✅ AlarmManager.set 同 AnternaPad.2
    2. ✅ KeyChain.getPrivateKey 对 empirical 分析不准确，导致之前的 model.json 里没加入。这是一个 android system bug，在 android < 4.2 的机器上，使用这个 API，只要不维持一个对其返回值的引用，而是仅仅获取（调用）一下的话，一旦后续有 GC 操作，将引起 app 的 crash。
12. WordPress
    1. ✅ AsyncTask.execute 同 AnternaPad.1

一些根据以前的 weekly report 又重新整理但还未能成功加入 models 的 api（这些 api 后续仍然需要继续分析整理，根据现在的测试结果，有一大部分未能发现的问题都是因为 api context 库不足引起的。）：

1. #14 RadioButton 的 setText 在 <= 16 时不能对齐
2. #61 ContentResolver 的 insert 方法需要加一个 IllegalArgumentException 捕获
3. #146 Notification 的 number 在 android >= 11 时不显示，应该使用 Builder.setNumber() 让它显示
4. #62 ContentValues.put 在 HTC Desire S 上需要 personId

周报

2017.11.29 ~ 2017.12.05

回想上周，我们本周的关注点只有一个：如何提高 canHandleIssue 的精确性，并进一步降低误报率。

提高精确性

上周我们提到，要提高精确性可能要涉及到对判断语义的理解。目前打算的实现方式是这样的：

首先对现在的 slicing 进行改写，目前的 slicing 是 Unit 的集合，现在打算将 slicing 改为 从 Object 到 Set<Unit> 的映射，即 map<Object, Set<Unit>>。

根据我们寻找 slicing 的算法，我们知道：

slice = "dependents of a Callsite" + 
        "dependents of some IfStmts"

Callsite 的依赖通常是一系列 Unit。而 IfStmt 的依赖则是它所使用的两个变量的依赖语句。对于 IfStmt，若其中一个变量是某个方法的返回值，那么我们将对该方法的所有语句进行遍历，对其中使用“特殊字串”（如 android.os.Build$VERSION: int SDK_INT 等）定义的变量及使用过它的 IfStmt 语句（及其依赖）进行递归查找，并以 Value -> Set<Unit> 的映射存储。即，我们构造的 slicing 将是如下的形式：

slicing = {
  Callsite: dependent Units of Callsite,
  IfStmt1: 2 definition Units of 2 variables used by IfStmt1,
  Value1:  Units which defines or uses Value1, and Value1 is a value used by some IfStmt,
  ...
}

这样，在 canHandleIssue 的时候，我们采用以下启发式方式来检测是否能够被处理：

• Callsite

使用现在的方式，即检测其 slicing 中是否包含相应的字符串。

• IfStmt

将对语义进行解析：上面提到，IfStmt 的依赖一般是 IfStmt 使用的变量的定义语句，因此，我们将：

假设该 IfStmt 使用的两个 expr 为 e1 和 e2：
  1. 若 ei（i = 1，2） 为常量，且为 0 或者 1，且 ej（j != i，j = 1，2）
     为变量，令 ej 的定义语句为 dj：
    1.1. 若 dj 包含方法调用语句，且该调用语句的参数部分（一般是个数字）满足我们的
      acpair（在最大最小值之间），我们认为该处被 fix。
  2. 若 ei（i = 1，2） 为常量，且不为 0 也不为 1，且 ej（j != i，j = 1，2）
    为变量，令 ej 的定义语句为 dj：
    2.1. 若 dj 包含相应的字符串，且 ei 对应的常量满足我们的 acpair，我们认为该处
      被 fix。
  3. 对其他任何情况，我们都认为该 IfStmt 不能 fix 此处。

上述提到的两种 fix 方式一般对应于以下两种 fix 方式：

1.1 if (Xxx.isCompatible(11)) { ... }

2.1 if (os.Build.VERSION.SDK_INT > 11) { ... }

我们将随着测试用例的增加进一步扩展对 IfStmt 的检测

• Value

我们将按照上述提到的 IfStmt 的检测方式对每条使用该 Value 的 IfStmt 进行检测。

降低误报率

关于误报率，这几天在测试的时候发现，（我）目前的实现还是有提高误报率的操作，是在 computeCallsite 的时候：

我们知道，callgraph 是程序的静态表示，其中并不包含控制流信息，因此利用我们寻找到的仅仅针对某个 acpair.api 的 callsites 并不能精确地告诉我们该 acpair 在某个 callsite 处是否被 fix。说起来可能很费力，举个例子：

private void _acpair_check_getActionBar() {
  ActionBar actionBar = getActionBar();
  actionBar.setTitle("123");
}

private void directCheck() {
  if (Build.VERSION.SDK_INT > 11) {
    _acpair_check_getActionBar();
  }
}

上面的代码中，getActionBar 在 api < 11 的时候是个 FIC issue，无论是利用 callgraph 还是像 Lili 一样一条一条语句地进行检测，我们最终找到的 callsite 都是第 2 行，即 _acpair_check_getActionBar 会调用 getActionBar，而对第 2 行的代码利用我们目前的方式进行 slicing 的时候实际上并不能追溯到 directCheck 方法（或许真正的 SDG 可以追溯到，因为 SDG 里面包含了控制流和数据流信息），所以利用 fic-finder 在进行检测的时候会报告第 2 行有个 FIC issue 没有被 fix，但显然这是一个 FP（因为第 7 行已经 fix 掉了）。

不知道 Lili 的实现里有没有可能这种会误报的情况。目前我考虑的针对这种问题的解法也跟之前提到的 IfStmt 寻找类似，即寻找 K 层调用，不光寻找某个 acpair.api 的 caller（我们暂称为 acpair.api 的 direct caller ），还要寻找 acpair.api.direct_caller 的 caller（我们暂称为 acpair.api 的 1-indirect-caller），一直找到 acpair.api 的 K-indirect-caller。

总结

1. 上面的所有思考是这周在一遍进行测试的时候一边想到的，现在还没有转换为代码，其中应该也有一些问题，Lili 和 许老师 先看下，讨论一下其中可能存在的问题并进行修正后再转换为代码。
2. 我已经提前把代码转换到了安卓，因为在做纯 java 的时候对一些 fix 方式还是不是很好模拟。代码在 j2a 分支

周报

2017.09.14 ~ 2017.09.19

这周的工作相比前几周进展也不是很大，主要问题还是集中于 slicing 的实现上。由于进展不大，因此这次的周报主要记录一下这周内所做过和尝试过的事情。

jpdg

就像上周说的，打算利用 jpdg 提供的源码自行实现 PDG/SDG 和 slice，因此这周花了一些时间在 jpdg 的源码上，但由于没有找到非常明确的 PDG/SDG 的实现算法，因此看的过程还是比较艰苦。目前还打算继续看下去，感觉对理解 PDG/SDG 应该帮助很大。

Soot built-in PDG

因为看 jpdg 的过程还是挺累的，因此除此之外还在想着到底能不能利用 soot 内置的 ProgramDependenceGraph 来实现 slice。

首先说一下上次提到的异常："java.lang.RuntimeException: PDG construction: A and B are not supposed to be the same node!"。

这周 check 了好多遍代码都没有发现问题，把代码打平(抽离所有不必要的成分，如 Config 等，只保留与 soot 相关的部分)后再次运行也是会产生同样的问题，所以这周就咨询了两位学长和 Lili：两位学长都说没有碰到过类似的异常并且说只简单地用过；Lili 说使用了内置的 PDG 但没有出现类似问题，有时间也会帮我排查一下(非常感谢 Lili)。鉴于此，再次感觉是我代码的问题，于是再次进行了代码打平，却依然有错误，因此，我把焦点放在了这几行代码上，因为正是这几行代码的加入使得整个程序崩溃：

// add a transform to generate PDG
packManager.getPack("jtp").add(new Transform("jtp.pdg_transform", new BodyTransformer() {
    @Override
    protected void internalTransform(Body body, String s, Map<String, String> map) {
        Env.v().setPdg(new HashMutablePDG(new BriefUnitGraph(body)));
    }
}));

仔细观察后(因为 soot 的文档里根本没提到 PDG，这几行代码是从一篇博客中看到的)发现，这个 transform 会聚焦在 Body 上，而我们知道，Body 是 Method 所具有的东西，换言之，这个方法会在类的每个 method 上都会被调用，因此可以知道，soot 内置的 PDG 是狭义的 PDG（仅对某个方法或者基本块进行 PDG 的构建，PDG 中不涉及方法调用），而非 SDG，因此我尝试了下面的方式来检测是否有成功的方法：

// add a transform to generate PDG
packManager.getPack("jtp").add(new Transform("jtp.pdg_transform", new BodyTransformer() {
    @Override
    protected void internalTransform(Body body, String s, Map<String, String> map) {
        String methodSignature = body.getMethod().getSignature();
        try {
            Env.v().getPdgMapping().put(
                    methodSignature,
                    new HashMutablePDG(new BriefUnitGraph(body)));
        } catch (Exception e) {
            System.out.println("Error in generating PDG for " + methodSignature);
        }
    }
}));

结果成功了，这样就知道，上述 transform 会在某些方法上产生异常，大多数方法还是可行的，到 soot 的 issues 下查类似的问题(之前查的一直是"java.lang.RuntimeException: PDG construction: A and B are not supposed to be the same node!"，而不是"Work thread failed, null ponter..."，所以才没有任何收获)才发现确实有这个 bug。因此利用上述的代码就成功的对大部分的方法进行了 PDG 的构建。

接下来说一下有了上述 PDG 进行 slice 还需要的一些条件。

就像上次提到的，soot 内置的 PDG 有一个很大的缺陷，它提供的 PDG 是 CDG only 的，里面并没有与 DDG 相关的任何信息，因此如果使用上述方式对每个方法都进行 PDG 的构建，接下来我们还需要：

1. 加入一个 intra-procedural 的 analysis 来对 DDG 进行捕获
2. 利用 CallGraph 来生成一些与 SDG 相关的信息

与 Lili 聊过，她也是这样来实现的，Lili 还提到，只需少量与 SDG 相关的信息便可以有比较好的结果。

利用 Soot built-in PDG 实现

有了上述的思路，我使用了如下的实现，但目前还是存在问题，先说下代码，再说问题。

首先是 callsite 的定位，对于 callsite 我们利用 method + unit 来定位其发生的位置：

public class Callsite {

    private SootMethod method;

    private Unit unit;

    public Callsite(SootMethod m, Unit u) {
        this.method = m;
        this.unit = u;
    }

	...
}

之前提到过，对于 model，有 method，field 和 iface 这么几种：

• 对于 method，利用 callgraph 的 edgesInto 来定位对某个方法的调用。
• 对于 field 和 iface，还没有找到合适的 API 来定位。

代码里利用 List<Callsite> computeCallsites(ApiContext model) 这个方法来对上述的 model 进行定位。

private List<Callsite> computeCallsites(ApiContext model) {
    CallGraph callGraph = Scene.v().getCallGraph();
    Scene scene = Scene.v();

    String type = model.getApi().getClass().toString().split(" ")[1];
    List<Callsite> callsites = new ArrayList<>(128);

    // get callsites of the specific api
    switch (type) {
        case ApiField.TAG: {
            ApiField apiField = (ApiField) model.getApi();
            SootField sootField = scene.getField(apiField.getSiganiture());

            // TODO I have no idea how to get the callsite of a specific field

            break;
        }

        case ApiMethod.TAG: {
            ApiMethod apiMethod = (ApiMethod) model.getApi();
            SootMethod sootMethod = scene.getMethod(apiMethod.getSiganiture());

            Iterator<Edge> edges = callGraph.edgesInto(sootMethod);

            while (edges.hasNext()) {
                Edge edge = edges.next();
                callsites.add(new Callsite(edge.src(), edge.srcUnit()));
            }

            break;
        }

        case ApiIface.TAG: {
            ApiIface apiIface = (ApiIface) model.getApi();
            SootClass sootIface = scene.getSootClass(apiIface.getSiganiture());

            // TODO I have no idea how to get the callsite of a specific interface

            break;
        }

        default: throw new RuntimeException("Invalid api type: " + type);
    }

    return callsites;
}

假设我们已经找到了定位，接下来是进行 slice 工作，代码中利用 List<Unit> runBackwardSlicingFor(Callsite callsite) 这个方法来进行：

private List<Unit> runBackwardSlicingFor(Callsite callsite) {

    // TODO run backward slicing here

    List<Unit> slice = new ArrayList<>(128);
    Map<String, ProgramDependenceGraph> pdgMapping = Env.v().getPdgMapping();
    ProgramDependenceGraph pdg = pdgMapping.get(callsite.getMethod().getSignature());

    // callsite unit
    Unit callsiteUnit = callsite.getUnit();
    PDGNode srcNode = null;

    // find the corresponding PDGNode
    for (PDGNode n : pdg) {
        PDGNode.Type type = n.getType();
        Iterator<Unit> iterator = null;

        // get iterator
        if (type.equals(PDGNode.Type.CFGNODE)) {
            iterator = ((Block) n.getNode()).iterator();
        } else if (type.equals(PDGNode.Type.REGION)) {
            iterator = ((Region) n.getNode()).getUnitGraph().iterator();
        }

        // get srcNode
        if (iterator != null) {
            while (iterator.hasNext()) {
                if (iterator.next().equals(callsiteUnit)) {
                    srcNode = n;
                    break;
                }
            }
        }

        if (iterator != null && srcNode != null) {
            break;
        }
    }

    // find the slice in pdg
    List<PDGNode> dependents = srcNode.getBackDependets();

    // TODO find suitable api to get the slice in Unit

    return slice;
}

问题

可以看到，上述代码中有几处 TODO，正是目前需要解决的几个问题，这里提一下：

1. 如何对 field 和 iface 进行定位
2. PDG 目前已经可以构建，并且可以成功得到针对某个 callsite 的依赖节点，但却无法明确地获得其对应的 Unit
3. 如何添加一个 intra-procedural 的 data-flow analysis 来对 DDG 进行捕获

思考

可以说，上面三个问题中，阻碍开发进行的正是第二个问题，这也是亟需 Lili 帮助的一个问题。不过总结一下也容易看出来，这些问题归到底是对 soot 的不熟练造成的(感觉文档确实写的不是很清楚，使得上手非常困难)。

另外，还发现了几篇关于 slice 的文章，这里推荐一下。

1. 这是一个 slice 工具的论文，稍微详细一点地解释了 PDG/SDG 等的构建，但偏长也不易读，目前正在看，但没有发现工具的代码
2. 这也是一个 slice 工具，是篇中文论文，代码也在 Github 上，名字就叫 Slithice
3. 这一篇讲了一下 DDG 在 Soot 构建的方式，目前读了一下摘要，还没继续读

周报

测试结果

这周除了邮件中列出的几点工作外，还对现在的版本（branch: counterpart, revision: 3045bdb）进行了测试，测试主要从几个方面下手：

1. detection 阶段后每个 App 可以检测到的 FIC Issues 数目（以 api/call-sites/call-chains 个数表示，每条 api 会有多个 call sites 对他进行调用，而每处 call site 又会形成更多的 call chain，因此 api < call-sites < call-chains）
2. validation 阶段后每个 App 可以检测到的 FIC Issues 数目。
3. 每个 App 报出的 FIC Issues 有多少 TP，多少 FP。
4. 对目前构建成功的 15 (实际计算中只有 14 个，其中一个 PocketHub 有问题，没列入计算) 个 App，validation 阶段有多高的剪枝率。
5. 对目前构建成功的 15 个 App，总共检测到的 FIC Issues 数目是多少，误报率多高。

下表为针对上述指标所列的表：

测试结果解读

从上表可以看出，对这 15 个 App（实际只有 14 个参与计算，PocketHub 没参与）

1. detection 阶段共报出 46/202/1202 个 FIC Issues，经过 validation 阶段后，剩下 39/165/532 个，剪枝率为 0.152/0.183/0.557。
2. 对最后（validation 阶段后）报出的 39/165/532 个 FIC Issues，其中 TP 有 27/119/423 个，FP 有 12/46/109 个，误报率为 0.307/0.279/0.205。

测试结果分析

回看 Lili 论文中所做的实验，针对上述 14 个 App，Lili 共发现了 21 个 FIC Issues（这里我假设为 api 数量），其中有 3 个 FP，误报率 0.143。可见，当前版本（branch: counterpart, revision: 3045bdb）能够发现更多的 Issues，但误报率也更高。下面总结了一些好与不好的原因：

1. 能够报出更多的 Issues
   1. 两个实验使用的 acpairs 数目和种类不同，这可能是其中的原因之一。
   2. 在搜索 call-site 的过程中，不仅使用了所有的 class，也使用了内置的 call graph，内置的 call graph 在构造的时候做了 OOP 的 CHA，所以可以发现更多的问题。
   3. 利用到了 call-chain，call-chain 所带来的好处就是：(1) 如果开发者意识到了某个 API 的问题，但却仅仅在某些地方进行了 fix，Lili 的方法就无法进行检测（Lili 的方法会认为被 fix 掉了，而实际上还有其他的 call-chain 没被 fix）。
2. 误报率更高
   1. 其中有些显而易见的问题，因为 slicing 不足而没有发现。如利用 if-else 而 fix 掉的 issue（这里说明一点，因为现在的版本使用了内置的 icfg，所以摒弃了之前周报中提到的专门针对 if-else 的比较 “狭隘” 的分析，相关的分析在 master 分支中仍然存在，但是现在我觉得这种分析继续下去会没完没了，后续是否再次加入还待考虑）
   2. 报告出了一些第三方库代码所引起的 Issues，因为所有的代码（无论是库代码还是 App 代码）都会被集成到 apk 中，所以第三方库中的代码也会被 Soot 分析。而目前的版本针对第三方库的代码用到的方式仅仅是黑名单，而黑名单里只能加入一些常用的第三方库。这种方式的问题就在于，(1) 每发现一个三方库，就得加入进去，麻烦；(2) 对于一些第三方库的组织所做的 App，它们（这些 App）与第三方库共享包名前缀，从而导致这些 App 无法被分析（这也是 PocketHub 无法被正确分析的原因，因为他用了 com.github）这个包前缀，这个前缀也正是很多很多 github 官方常用三方库的包前缀。
   3. 我在 ApiContext Model 中引入了 “important” 机制（这在上次的周报中已经提到了），使用了 “important” 的 acpair，只要 detect 到，直接报出，而不会经过 validate 阶段。引入这种机制考虑到的是，有些 acpair 是语义相关，这种 acpair 无法通过对代码的检测（validation 阶段）而得到任何有用的信息，而 validation 阶段又是费时的，所以直接报出来提醒开发者注意这样的问题才是更好的选择。与之相关的有 (1) AlarmManager.set 这个 API，根据官方文档，无法设置精确的时间，但使用这个 API 的开发者到底是真的需要精确的时间还是仅仅需要一个 App 特定的推动时间我们不可知，代码不可知，因此需要 "important"；(2) AsynTask.execute 这个 API，根据官方文档，无法真正的实现并行化，而是一个串行化的操作，同 (1) 一样，开发者是否真的需要并行也是代码不可知的，因此需要 "important"；(3) …
   4. 有些 API 真的一定 会在某些设备上引发问题，但却是代码不可知的（这种与 (3) 的区别在于，(3) 中所提到的 API 不一定 会引发问题），如 AppCompatActivity.setSupportActionBar，这个 API 会在三星 Galaxy 上引发问题，但解决方式是利用 proguard 配置文件，而不是代码。

其实误报率里的水分（有偏高的水分也有偏低的水分）很大一部分原因就是上述提到的 2/3/4，ELEGANT 把他们直接报告了出来，而实际上并不一定是开发者实际的（语义）需求。下面我也把这 15 个 App 所报出的 FIC Issues 的 API 进行了 TP 和 FP 的汇总，并列出了报告为 FP 的原因。其中 ✅ 表示 TP，❗ 表示 FP，❓ 表示 TP 和 FP 都有（针对这种，我把它列为了 TP），同时列出了新发现（和目前版本已经有的）的一些第三方包。（我在考虑能不能找到一些 3rd party libs elimination 的工具进行集成）

If, in some api, some call sites of it are fixed while others are not, we classify it into TP.

1. 1Sheeld
   • ❗❗ TextToSpeech.setOnUtteranceProgressListener => fixed using if (Build.VERSION.SDK_INT >= 15)
   • ✅ AsyncTask.execute
   • ✅ AlarmManager.set
   • ❓ Resources.getDrawable => 3rd-party libs: 2 (com.facebook, com.handmark)
2. BankDroid
   • ✅ Activity.onKeyDown
   • ❗ AppCompatActivity.setSupportActionBar => fixed in proguard-rules.pro
   • ✅ AsyncTask.execute
3. AnkiDroid
   • ✅ Activity.onKeyDown
   • ❗❗ TextToSpeech.setOnUtteranceProgressListener => fixed using class hierarchy
   • ❗ AppCompatActivity.setSupportActionBar => fixed in proguard-rules.pro
   • ✅ AsyncTask.execute
4. AntennaPod
   • ❗ AppCompatActivity.setSupportActionBar => fixed in proguard-rules.pro
   • ❗❗ AsyncTask.executeOnExecutor => fixed using if (Build.VERSION.SDK_INT >= 15)
   • ✅ AsyncTask.execute
   • ✅ AlarmManager.set
   • ❗ Resources.getDrawable => 3rd-party libs: 1 (com.viewpagerindicator)
5. AnySoftKeyboard
   • ✅ AsyncTask.execute
   • ✅ Resources.getDrawable
6. ConnectBot
   • ✅ MenuItem.setShowAsAction
   • ✅ AsyncTask.execute
7. Conversations
   • ✅ KeyChain.getPrivateKey
   • ✅ AlarmManager.set
8. IrssiNotifier
   • ✅ AsyncTask.execute
   • ❗ Activity.getActionBar => 3rd-party libs: 1 (com.actionbarsherlock)
9. K-9 Mail
   • ✅ Activity.onKeyDown
   • ✅ KeyChain.getPrivateKey
   • ✅ AlarmManager.set
   • ❓ Resources.getDrawable => 3rd-party libs: 6 (com.handmark, com.bumptech, org.openintents)
10. Kore
    • ✅ AppCompatActivity.setSupportActionBar
    • ❗ Resources.getDrawable => 3rd-party libs: 1 (com.melnykov)
11. PacktrackDroid
    • ✅ ConnectivityManager.getBackgroundDataSetting
12. PocketHub
    • ==com.github was regarded as a 3rd party, so data here is not reliable==
13. QKSMS
    • ✅ AppCompatActivity.setSupportActionBar
    • ✅ AlarmManager.set
    • ❗ Resources.getDrawable => 3rd-party libs: 1 (com.melnykov)
14. Transdroid
    • ✅ AppCompatActivity.setSupportActionBar
    • ❗ Resources.getDrawable => 3rd-party libs: 2 (com.getbase)
15. WordPress
    • ❗ AppCompatActivity.setSupportActionBar => fixed in proguard.cfg
    • ✅ ContentValues.put
    • ❓ Resources.getDrawable => 3rd-party libs: 2 (com.helpshift)

newly found 3rd party libs list

"com.handmark",           // Android Pull-to-Refresh
"com.facebook",           // facebook related sdk
"com.bumptech",           // glide
"com.viewpagerindicator", // ViewPager related
"com.actionbarsherlock",  // ActionBar related
"org.openintents",        // Intent related
"com.melnykov",           // FloatingActionButton related
"com.helpshift"           // help shift android sdk

embedded 3rd party libs list

"android",          // android official
"java",             // java official
"com.jakewharton",  // butterknife
"com.github",       // github related, glide, etc.
"com.squareup",     // okhttp, retrofit, etc.
"com.google",       // google related, gson, guava, etc.
"com.crashlytcics", // firebase
"org.omg",          // extends to java
"org.w3c",          // extends to java
"org.xml",          // extends to java
"org.apache",       // apache organization
"com.sun",          // sun
"org.eclipse",      // eclipse
"rx"                // reactivex java

周报

2017.08.10 ~ 2017.08.15

Soot

安装和配置

本周的第一个任务就是对 Soot 进行了快速的了解和学习。虽然只是下一个 jar 包而已，但其间也是遇到了一个小坑，这里记录一下。

根据官方Wiki的讲解，由于 Soot 有自己的 classpath ，因此我们在使用命令行工具的时候需要手动添加 $CLASSPATH 或 $JAVA_HOME 来解决类似 java.lang.Object 无法加载的问题:

# 或者
java -cp soot-x.y.z.jar soot.Main -cp .:${JAVA_HOME}/jre/lib/rt.jar A
# 或者
java -cp soot-2.5.0.jar soot.Main -cp . -pp A

然而，即使这样也可能会遇到:

Exception in thread main java.lang.RuntimeException: Could not load classfile: java.lang.CharSequence

查询后发现是 java 版本的问题，在 java 8 下会报这样的错误，解决方案：

• 降版本到 java 7（T_T 绝对很坑，java 8 的闭包[虽然是个语法糖]不知道好用到哪里去了）
• 使用 Soot 的 nightly build 版本（链接）

虽然是个小小的 jar 包，但也是历经一番辛苦才搞好。

调研与使用

看了文档后，了解到 Soot 是一个经常用来分析和优化 java/android 应用的工具，提供了诸如

• 调用图(call graph)构建
• 指针(points-to)分析
• 数据流分析(def/use等)
• ...

等能力，同时提供了四种主要的中间代码表示形式：

1. Jimple
2. Shimple
3. Baf
4. Dava

详细的使用将在开发阶段进行，这不作为本周的重点。

Issues 的提取

按照上周计划，本打算根据 Lili 学姐论文中提到的数据收集和分析的方法自己进行 issue 的提取，但当打开 CSipSimple 项目对第一个关键词 device 进行搜索并欲进行整理和分析的时候，发现搜到的结果竟有 43 次 Commit 和 8 个 issue，考虑到还有14个关键词和4个项目，数量有点大而且不易仔细分析，于是便暂时先放弃了自己进行搜索和分析的想法，暂时先使用学姐给出的 191 个 issue 来优先进行 Model 的提取。可等开发完成后再回头考虑如何能好又快的进行 Issue 的提取。这里暂时先给自己留个坑出来以后填。

Model 的提取 - 1.1.1

根据学姐项目主页的数据表，对其中每一个 Issue 都进行了查找和分析，并**初步（仅对原因进行了分析，还未进行进一步抽象与提取）**得到了以下的 Model（限于时间，目前仅对 CSipSimple 进行了小部分分析，下周会继续）：

备注：平台版本、级别、VERSION_CODE 对应关系见这里

疑问！！！

为什么 #61 是 Device-Specific 的？其代码修改如下（代码中未体现设备相关性）：

@@ -26,7 +26,9 @@
  import android.content.Context;
  import android.content.Intent;
  import android.net.Uri;
 +import android.os.Build;
  import android.provider.CallLog;
 +import android.provider.ContactsContract.Data;
  
  import com.csipsimple.api.SipCallSession;
  import com.csipsimple.api.SipManager;
 @@ -95,6 +97,12 @@ public static ContentValues logValuesForCall(Context context, SipCallSession cal
  			cv.put(CallLog.Calls.CACHED_NAME, callerInfo.name);
  			cv.put(CallLog.Calls.CACHED_NUMBER_LABEL, callerInfo.numberLabel);
  			cv.put(CallLog.Calls.CACHED_NUMBER_TYPE, callerInfo.numberType);
 +			
 +			if(Build.DEVICE.equalsIgnoreCase("saga")) {
 +			    // For HTC desire S they need for some reason the personId
 +			    // Thx Maximus for the tip
 +			    cv.put(Data.RAW_CONTACT_ID, callerInfo.personId);
 +			}
  		}
  		
  		return cv;

#128 代码为什么使用 0x00040000 而非 ApplicationInfo.FLAG_EXTERNAL_STORAGE 既然兼容 API level 8

public static boolean isInstalledOnSdCard(Context context) {
  // check for API level 8 and higher
  if (Compatibility.isCompatible(8)) {
    PackageManager pm = context.getPackageManager();
    try {
      PackageInfo pi = pm.getPackageInfo(context.getPackageName(), 0);
      ApplicationInfo ai = pi.applicationInfo;
      return (ai.flags & 0x00040000 /*ApplicationInfo.FLAG_EXTERNAL_STORAGE*/) == 0x00040000 /*ApplicationInfo.FLAG_EXTERNAL_STORAGE*/;
    } catch (NameNotFoundException e) {
      // ignore
    }
  }
 
  // check for API level 7 - check files dir
  try {
    String filesDir = context.getFilesDir().getAbsolutePath();
    if (filesDir.startsWith("/data/")) {
      return false;
    } else if (filesDir.contains(Environment.getExternalStorageDirectory().getPath())) {
      return true;
    }
  } catch (Throwable e) {
    // ignore
  }

  return false;
}

下周计划

1. 完成剩余 Model 的分析与提取 (Model 的提取 1.1.2 ~ Model 的提取 1.1.x)
2. 对提取到的 Model 进行下一步的分析，抽取共性并舍弃一些相互调用相关性比较强的特例（如保存Log需要多步并且只有HTC desire S系列才会出问题的例子）。(Model 的提取 1.2)
3. 若上述两步骤完成，进入开发阶段，进行项目创建和框架搭建。

心声

1. 本来时间规划并不是一件难事，但它难就难在阿里给了一个 一周开发+前后端联调+提测+20号上线 的项目，不过实习确实学到了挺多东西，也真正了解到了软件工程的整个开发阶段、中后台项目的前端解决方案以及一个日 PV 高达 2kw 的项目的前后端解决方案。
2. FicFinder的实现也会继续合理安排时间进行，目前进度偏慢，希望后续能有时间和能力加速。

周报

这次的周报总结一下这段（挺长）时间做的事情，好久没写了，这次也写的稍微多了一点。

回顾

首先还是说一下上一次周报提到的问题，上次周报提到了这么几个问题：

1. 对于 reflection-fixing，除了之前提到的利用 if (null == someMethodHandle) 检查的解决方案，还能预想到一种类似的解决方案，利用 try-catch 来空指针等的捕获异常。
2. 对于 reflection-fixing，之前提交的代码中已经有了对空指针检查的部分，但检查相对较弱，代码中所做的检查仅仅是对每次 someMethodHandle 调用前的是否有空指针检测进行检测，而没有考虑控制流和数据流的问题。正确的处理方式应该是对 someMethodHandle 所在的方法进行 nullness analysis，从而保证在 someMethodHandle 的每次调用前都能够保证 someMethodHandle 的非空性。
3. 剪枝阶段对调用链的检测没有考虑到安卓生命周期的问题，猜想造成这种问题的原因其实是 event-driven 的方式造成了 CFG 的不完整性，从而使得我们无法获取到正确的 slicing。

解决方案

1. 上述 1/2 问题可以合并解决，首先对 someMethodHandle 所在的方法添加一个 NullnessAnalysis，如果每次对 someMethodHandle 的调用都能保证其非空性，我们认为开发者已经将这个 issue 进行了 fix；否则，我们将 (1) 检查此处调用是否在一个 try 语句块中，并 (2) 检查该语句块是否是用来捕获 NullPointerException/NoSuchMethodException 的语句块，如果 (1) (2) 同时满足我们同样认为开发者已经对这个 issue 进行了 fix。否则，我们认为开发者未能预见这种情况，我们将汇报该条 issue。下面的代码展示了主逻辑部分（代码一直在我本地，昨天刚刚提交到 github 上，代码主要位于 RFinder.java 里）：

   // non-nullness can be ensured by: 1. if-else checking 2. try-catch block
   Body body = caller.getActiveBody();
   
   // here we will run a nullness analysis, to guarantee that the r9 is checked non-nullness via if-else
   NullnessAnalysis nullnessAnalysis = new NullnessAnalysis(new BriefUnitGraph(body));
   
   // we must guarantee that the handler got by reflection is not null
   boolean    fixed = true;
   List<Unit> units = new ArrayList<>(body.getUnits());
   int        index = units.indexOf(callSiteUnit);
   
   // get all try-catch blocks to get ready for try-catch checking
   List<Trap> traps = new ArrayList<>(body.getTraps());
   
   // traverse units after call site, guarantee that invoking of r9 is checked non-nullness
   for (int i = index + 1; i < units.size(); i++) {
       Unit u = units.get(i);
   
       // u does not invoke r9, skip it
       if (!Strings.contains(u.toString(), definedVar.toString() + ".")) { continue; }
   
       // ensure that r9 is non-null via if-else
       if (!nullnessAnalysis.isAlwaysNonNullBefore(u, (Immediate) definedVar)) {
           // non-nullness can not be guaranteed by if-else,
           // then, we must do a try-catch checking
           boolean caught = false;
           for (Trap trap : traps) {
               SootClass exceptionClass = trap.getException();
               String exceptionJavaStyleName = exceptionClass.getJavaStyleName();
               int bidx = units.indexOf(trap.getBeginUnit());
               int eidx = units.indexOf(trap.getEndUnit());
   
               // this trap can catch u, and the exception to be caught
               // is a NullPointerException or a NoSuchMethodException
               // or a its super classes' instance
               if (bidx <= i && i <= eidx &&
                       ("NullPointerException".equals(exceptionJavaStyleName) ||
                        "NoSuchMethodException".equals(exceptionJavaStyleName) ||
                        "ReflectiveOperationException".equals(exceptionJavaStyleName) ||
                        "Exception".equals(exceptionJavaStyleName))
                       ) {
                   caught = true;
                   break;
               }
           }
   
           if (!caught) {
               fixed = false;
               break;
           }
       }
   }
   
   if (!fixed) {
       validatedEdges.add(edge);
   }

2. 虽然 soot/flowdroid 对安卓有了一个假入口函数 FakeMainEntry 的实现，并使我们能够获取到整个的 CFG，但从我们并不能获得正确的 slicing 这点来看，我们猜想这个 CFG 是不完整的，但这一点目前并没有获得证实（我向 soot-email-list 发了两封邮件询问几个有关 soot 的问题，一封是年前发的，一封是前几天发的，但都没有得到回应，真惨，明明我经常收到作者对其他人询问问题的回复），因此这个问题到现在仍然悬而未决，我现有的想法，或者是请教一下刘烨庞师兄像 GreenDroid (Y. Liu, etc) 一样去对 Android 进行一点建模，或者是像 EnergyPatch (A. Banerjee, etc) 一样利用 Dynodroid 获取 EFG，从而获取 CFG，然后抛弃 soot 获取 slicing 的方法，重新写一个 program slicing 的算法（我目前手边和网上也都没有找到一份完整的算法，我目前看到的 program slicing 的说法都很模糊，没看到十分精确、完整的定义），但这样都会极大地（真的是不止一点点地）增大工作量。==不知道 Lili 对这点有没有什么想法？:confused:==

其他工作

除了对上述提到的问题进行思考和部分着手解决，这段时间还在写脚本整理最后 Lili 进行实验的 27 个 App，打算利用现在的版本跑个测试试试，主要是：

1. 从 github 上爬。国内 git clone 是真的慢，这 27 个项目单单下载就花接近了 2 天的时间，大项目 git 在下载过程中经常因为网络问题挂，开了 ss 也不稳定，所以脚本里会有 if [-d xxx] 这样检查项目的代码存在，因为这脚本跑了不知道几遍。:cry:
2. 建分支（Lili 的实验都是基于某个分支的代码，应该是做实验时比较稳定的版本），为方便，这里我统一叫它们 fic-finder-test-version 分支，过程中发现，有两个项目的两个分支不存在（==不知道是不是 Lili 论文里标错了 commit 号==），分别是 "openvpn/9278fa4" 和 "owncloud/cfd3b94"
3. 进行 apk 的构建，这工作量相对来说还可以，这也真是一项挑战，不用 docker 做项目开发的开发者们不知道在配环境上费了多大功夫，期间遇到了不少麻烦，虽然有解决的，但不知道这种粗略的解决会对工程造成多大的影响。

下面先罗列下脚本（不打算上传，所以在这里写一下），然后记录一下期间的问题和解决方案（如果以后真的有问题也方便查看）。

下载 - download.sh

#! /bin/bash

TEST_PROJECTS_REPO_URL=(
  "https://github.com/Integreight/1Sheeld-Android-App.git"
  "https://github.com/connectbot/connectbot.git"
  "https://github.com/ankidroid/Anki-Android.git"
  "https://github.com/AntennaPod/AntennaPod.git"
  "https://github.com/siacs/Conversations.git"
  "https://github.com/cgeo/cgeo.git"
  "https://github.com/xbmc/Kore.git"
  "https://github.com/AnySoftKeyboard/AnySoftKeyboard.git"
  "https://github.com/erickok/transdroid.git"
  "https://github.com/k9mail/k-9.git"
  "https://github.com/r3gis3r/CSipSimple.git"
  "https://github.com/DrKLO/Telegram.git"
  "https://github.com/wordpress-mobile/WordPress-Android.git"
  "https://github.com/OpenVPN/openvpn.git"
  "https://github.com/brave/link-bubble.git"
  "https://github.com/firetech/PactrackDroid.git"
  "https://github.com/moezbhatti/qksms.git"
  "https://github.com/rcgroot/open-gpstracker.git"
  "https://github.com/liato/android-bankdroid.git"
  "https://github.com/evercam/evercam-android.git"
  "https://github.com/bitcoin-wallet/bitcoin-wallet.git"
  "https://github.com/guardianproject/ChatSecureAndroid.git"
  "https://github.com/inaturalist/iNaturalistAndroid.git"
  "https://github.com/hypery2k/owncloud.git"
  "https://github.com/pockethub/PocketHub.git"
  "https://code.videolan.org/videolan/vlc-android.git"
)
readonly TEST_PROJECTS_REPO_URL

# $1: project name to be downloaded
# $2: project repo_url
function download() {
  # some projects have been already downloaded, we ignore them
  if [[ ! -d ${1} ]]; then
    echo -e "\033[1;32mdownload ${1} from ${2}\033[0m"
    # downloads from repo of $2
    git clone ${2}
  fi
}

for repo_url in ${TEST_PROJECTS_REPO_URL[@]}; do
  project_name=$(echo ${repo_url} | cut -d '/' -f 5 | cut -d '.' -f 1)
  download ${project_name} ${repo_url}
done

建立分支 - checkout.sh

#! /bin/bash

FIC_FINDER_TEST_BRANCH_NAME="fic-finder-test-version"

TEST_PROJECTS_COMMIT=(
  "IrssiNotifier/ad68bc3"
  "1Sheeld-Android-App/b49c98a"
  "connectbot/49712a1"
  "Anki-Android/dd654b6"
  "AntennaPod/6f15660"
  "Conversations/1a073ca"
  "vlc-android/4588812"
  "cgeo/5f58482"
  "Kore/0b73228"
  "AnySoftKeyboard/d0be248"
  "transdroid/28786b0"
  "k-9/74c6e76"
  "CSipSimple/fd1e332"
  "Telegram/a7513b3"
  "WordPress-Android/efda4c9"
  # "openvpn/9278fa4"
  "link-bubble/65cd91d"
  "PactrackDroid/1090758"
  "qksms/73b3ec4"
  "open-gpstracker/763d1e2"
  "android-bankdroid/f491574"
  "evercam-android/c4476de"
  "bitcoin-wallet/3235281"
  "ChatSecureAndroid/30f54a4"
  "iNaturalistAndroid/1e837ca"
  # "owncloud/cfd3b94"
  "PocketHub/a6e9583"
)
readonly TEST_PROJECTS_COMMIT

# $1: the directory
# $2: the commit that will be checkouted
function makeBranchOnCommit() {
  # enter the directory
  # make a new branch named "fic-finder-test-version" based on the corresponding commit
  # exit this directory
  echo -e "entering \033[1;32m${1}\033[0m"
  cd ${1}

  git checkout -b ${FIC_FINDER_TEST_BRANCH_NAME} ${2} &&
    echo -e "\033[1;32mmaking branch ${FIC_FINDER_TEST_BRANCH_NAME} based on commit ${2}\033[0m"

  echo -e "exiting \033[1;32m${1}\033[0m"
  cd ..
}

for ele in ${TEST_PROJECTS_COMMIT[@]}; do
  project_name=$(echo ${ele} | cut -d '/' -f 1)
  commit=$(echo ${ele} | cut -d '/' -f 2)
  makeBranchOnCommit ${project_name} ${commit}
done

构建 apk

#! /bin/bash

TESTS_HOME=`pwd`
readonly TESTS_HOME

TEST_PROJECTS_LIST=(
  "IrssiNotifier/Android"
  "1Sheeld-Android-App"
  "connectbot"
  "Anki-Android"
  "AntennaPod"
  "Conversations"
  "vlc-android"
  "cgeo"
  "Kore"
  "AnySoftKeyboard"
  "transdroid"
  "k-9"
  "CSipSimple"
  "Telegram"
  "WordPress-Android"
  # "openvpn"
  "link-bubble/Application"
  "PactrackDroid"
  "qksms"
  "open-gpstracker/studio"
  "android-bankdroid"
  "evercam-android"
  "bitcoin-wallet/wallet"
  "ChatSecureAndroid"
  "iNaturalistAndroid"
  # "owncloud"
  "PocketHub"
)
readonly TEST_PROJECTS_LIST

for project_path in ${TEST_PROJECTS_LIST[@]}; do
  project_name=$(echo ${project_path} | cut -d '/' -f 1)

  echo -e "\033[1;32m========> ${project_name}\033[0m"

  echo "  1. entering"
  cd ${project_path}

  if [[ ! -f "gradlew" ]]; then
    echo "${project_name}" >> "${TESTS_HOME}/not.studio.log"
    echo "  2. exiting"
    cd ${TESTS_HOME}
  else
    # here we use assembleDebug to build a debug version
    chmod +x gradlew &&
      echo "  2. cleaning up" &&
      ./gradlew clean > /dev/null 2> "${TESTS_HOME}/${project_name}.clean.fail.log" &&
      echo "  3. building" &&
      ./gradlew assembleDebug > /dev/null 2>> "${TESTS_HOME}/${project_name}.build.fail.log" &&
      echo -e "  \033[1;32msucceeded\033[0m in building" &&
      echo "${project_name}" >> ${TESTS_HOME}/succ.log

    echo "  5. exiting"
    cd ${TESTS_HOME}
  fi
done

构建过程中遇到的问题

• NDK

  1. 下载 NDK 并进行环境配置（嗯，官网是下不了的，dl.google 抽风不知道抽了多长时间了，NDK 在东软的镜像上有）
  2. 下载后解压到与 SDK 相同的目录下，其名 ndk，并将其加入环境变量 $PATH。
  3. 在需要的项目目录下使用命令 echo "ndk.dir=${ANDROID_HOME}/../ndk"

• 警告与错误

  因为我们需要测的都是这些项目过去的 commit，其中有一些 api 已经是 deprecated 状态，因此为了不让这些 deprecated api 阻碍我们构建，需要在所有项目的顶层 build.gradle 里加入：

  allprojects {
      gradle.projectsEvaluated {
          tasks.withType(JavaCompile) {
              options.compilerArgs << "-Xlint:unchecked" << "-Xlint:deprecation"
          }
      }
  }

• strerror，memmove

  有个项目使用了 strerror/memmove 等函数，却没包含头文件，这在某些编译器下是会自动添加到，但在某些编译器（如 clang）下它就挂，它位于头文件 string.h。

• R.string.xxxx 不存在

  有几个项目报这个错误，暂时性地在其 res/values/strings.xml 下为所有 i18n 的情况下都加入一条 <string name="xxx">whatever</string> 来跳过这个错误，这不会对我们的分析有任何影响，但对 App 有什么影响就未可知了。:slightly_smiling_face:

• failed to find target with hash string 'Google Inc.:Goole APIs:21'

  有几个项目写依赖时采用了这种方式（猜测这应该是一种老式写法），现在不可用了，直接将它们改成 21 （即，只需要写出版本就行）

• template

  有几个项目需要开发者使用自己在某些站点的用户名和用户密码或者 key 来进行填充，项目开发人员为使用这个项目的开发者提供了一些模板（template）文件，对于这种情况暂时直接使用 template（这也不会对我们的分析有任何影响，但对 App 有什么影响也未可知🙂）

• Build Tools Version

  有个项目使用了 23.0.0 版本的 build tools，但 sdk manager 里最低版本都是 23.0.1，找不到 23.0.0 的，因此直接把 23.0.0 改成了 23.0.1（这可能会对我们的分析有些许影响，因为我们的分析里需要使用到版本信息，但之所以说些许，是基于假设 “API 的迭代一般不会在小版本里，都是跨版本的”，这个假设的可靠性是基于开发经验和 API 设计角度的，待进一步确认）。

• failed to apply plugin [id 'com.android.application']

  同样是因为 commit 有点老的问题，对于这种情况，对于 Android Studio 3.0，需要在 build.gradle 里添加（或修改）：

  buildscript {
      repositories {
          jcenter() 
      }
      dependencies {
          // for Android Studio 3.0
          classpath 'com.android.tools.build:gradle:3.0.1'
      }
  }

  对于 Android Studio 2.3，需要改成 classpath 'com.android.tools.build:gradle:2.3.3'。

  对于某些需要 23 版本的项目，需要改成 classpath 'com.android.tools.build:gradle:2.2.3'

到目前还未能编译成功的问题

• 非 gradle/Android Studio 项目
  1. vlc-android
  2. CSipSimple
  3. bitcoin-wallet
  4. ChatSecureAndroid
• build tools (sdk-build 或者 ndk-build) 构建失败
  1. cgeo
  2. link-bubble
  3. iNaturalistAndroid
• keystore 签名问题
  1. Telegram
• 代码问题
  1. open-gpstracker
  2. evercam-android
• commit 不存在
  1. openvpn
  2. owncloud

周报

2018.01.17 ~ 2018.01.23

停了近一个月的 FicFinder，这周又开始工作了！先回顾一下上次 FicFinder 周报的内容：

回顾

上次对 AnkiDroid 几个有问题（buggy）以及问题被解决后（fixed）提交版本对进行了编译，并根据编译和目前 FicFinder 的测试结果给出了几种问题解决方式（bug fixing manner）：

1. direct-checking
2. method-checking
3. static-checking
4. reflection-fixing
5. polymorphism-fixing
6. workaround-fixing

上次提到，针对以上 1-4 目前的 FicFinder 已经可以解决（针对目前的测试，还需要更多的测试来巩固和加强），但针对 4、5 仍无法完成，并且给出了针对 4、5 的简单的解决方案描述，本周针对上次的描述进行了实现，同时对遇到的新问题进行阐述。

relfection-fixing

上周提到，针对这种形式的解决开发者（可能会以如下的方式解决）：

// 开发者知道 getActionBar 可能会出现问题，但不知道是哪个版本会出现问题，直接利用运行时环境信息查看是否可用是一种简便（但略微牺牲性能）的方式。
Method getActionBar = Activity.class.getMethod("getActionBar");
if (null != getActionBar) { // 可用！
  ActionBar actionBar = (ActionBar) getActionBar.invoke(this);
  actionBar.setTitle("This is title");
}

因此针对这种形式我们的解决方案如下：

function ReflectionFixing(acpair) do
  collect all call sites of "<java.lang.Class: java.lang.reflect.Method getMethod(java.lang.String,java.lang.Class[])>" save them to S
  for each call site s in S do
    if (s gets the handler of acpair.api) {
      r = s.return value
      for each invoking point p on r do
        if (does not check non-nullness of r before p) then
          report p
        fi
      done
    }
  done
done

解释一下：

对代码中所有对 <java.lang.Class: java.lang.reflect.Method getMethod(java.lang.String,java.lang.Class[])> 的 call site 进行查找，并存在集合 S 中（第 2 行）。对于 S 中的每一处调用 s （第 3 行），如果 s 是对 acpair.api 的调用（第 4 行），对 s 的返回值 r 进行保存，并检测对 r 之后的所有调用点 p（第 6 行），如果 p 之前没有对 r 非空的判断（第 7 行），认为 s 没解决掉这个 FIC bug，并对这处进行报告。否则，继续进行遍历 S。

针对这部分的代码位于 src/com/example/ficfinder/reflectionfinder/RFinder.java 中。

polymorphis-fixing

上周提到，针对这种形式的解决开发者（可能会以如下的方式解决）：

// 多态引入
public interface Compact {
    public void invalidateOptionsMenu(Activity activity);
}

public class CompactV3 implements Compact {
    @Override
  public void invalidateOptionsMenu(Activity activity) {
    // 构造一个空方法
  }
}

public class CompactV11 implements Compact {
    @Override
    public void invalidateOptionsMenu(Activity activity) {
        activity.invalidateOptionsMenu();
    }
}

// 使用的时候假设其一直存在
Compact compact;

if (getApiLevel() > 11) {
  compact = new CompactV11();
} else {
  compact = new CompactV3();
}

compact.invalidateOptionsMenu(this);

针对这样的解决，我们仍然沿用以前的方式，并对以前的代码进行了部分修正，从而完成这部分的检测。

问题

利用目前的 FicFinder 来对上周提到的编译版本进行测试，除了 invalidateOptionsMenu 这个例子外其他都三个都已通过（buggy 版本能够检测到，fixed 版本检测不到），现在来阐述下一些目前能想到的但仍待解决的问题：

• 对于 reflection-fixing，除了上述的解决方案，还能预想到一种类似的解决方案：

  // 开发者知道 getActionBar 可能会出现问题，但不知道是哪个版本会出现问题，直接利用运行时环境信息查看是否可用是一种简便（但略微牺牲性能）的方式。
  try {
    Method getActionBar = Activity.class.getMethod("getActionBar");
    ActionBar actionBar = (ActionBar) getActionBar.invoke(this);
    actionBar.setTitle("This is title");
  } catch (NullPointerException e) {
    // do nothing here
  }

  即开发者会利用异常处理来进行处理，对这种情况，我们目前还未覆盖。

• 对于 reflection-fixing，仔细考虑会发现，我们的实现存在以下的问题：

  上面关于 ReflectionFixing 的伪代码第 7 行，我们很含糊的表述了 “如果每处 r 的调用 p 前都有 non-nullness 的检测”，但我们目前的实现却仅仅是对没处调用前面的部分进行 if 语句的判断，这显然是 unsound 的。正确的方式应该是对该处调用 p 所在的方法进行一个空指针分析，从而保证 p 前（CFG前）一定有/可能没有 non-nullness 的检测。因此下周的第一个任务就是利用 Soot 实现一个 intra-procedural 的空指针分析。

• 对于任何形式的解决方案，我们提到，我们在剪枝阶段是检测调用链上每个调用点附近是否有对该 FIC issue 的解决，但这样形成的调用链没有考虑安卓生命周期的问题，考虑下面的情况：

  public MyActivity extends AppCompactActivity {
  
    private Compact compact;
    
    void onCreate() {
      if (getApiLevel() > 11) {
        compact = new CompactV11();
      } else {
        compact = new CompactV3();
      }
    }
  
    void onPause() {
  	compact.invalidateOptionsMenu(this);
    }
  }

  可以看到，我们上面的代码实际上对 invalidateOptionsMenu 这个 FIC bug 进行了修正，但从调用链上却显示不出来：

  onPause -> compact.invalidateOptionsMenu -> activity.invalidateOptionsMenu
  

  因此剪枝无法对这样的情况进行处理，考虑造成这种情况的根本原因，其实是安卓生命周期（或者说是 event driven 的方式）造成了 inter-producedural 的 CFG 不完整，导致我们无法获取到正确的 slicing 造成的。对这种问题如何解决，目前还在考虑（这也是 invalidateOptionsMenu 这个测试不通过的原因）。

其他

另外，本周还对代码进行了部分重构，现在结构如下：

1. com.example.ficfinder.finder.reflectionfinder 中的 RFinder 主要完成对 reflection-fixing 的工作，plainfinder 中的 PFinder 完成其他工作

2. RFinder 和 PFinder 都是 AbstractFinder 的实现。一个 AbstractFinder 包括：

   detection/validation/generation 三个部分，（顾名思义，）分别完成对一个 api-context pair 的检测与构建、剪枝、生成 issue 三方面的工作。

代码仍然在 call-site-tree 分支。