weekly report: 2018.03.14-2018.03.20

周报

前段时间到上周对 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 的时候：

使用内建 call graph 的 edgesInto() 得到一部分 call site
遍历 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 最初构建的问题，针对此，接下来的任务其实是聚焦在：

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

connglli / ELEGANT