大土豆安全笔记

这篇文章会涉及一些基础的图论名词，但都简单易懂，且只聊思路，并不涉及太多的代码，请放心阅读

周末做了两件事

优化了Neo4j的搜索逻辑
在李神探的指导下，很快跑通了FlowDroid

先讲讲Neo4j的搜索，用AndroGuard生成函数调用图，这个图是以node和edge的形式存储在GML文件里，表示形式如下

node [
    id 143
    label "Lcom/wnagzihxa1n/myapplication/MainActivity;->onCreate(Landroid/os/Bundle;)V [access_flags=protected] @ 0x10a98"
    external False
    entrypoint True
]

node [
    id 144
    label "Lcom/wnagzihxa1n/myapplication/MainActivity;->startActivity(Landroid/content/Intent;)V"
    external True
    entrypoint True
]

edge [
    source 143
    target 144
]

这就表示了从节点143到节点144有一条边，这些节点和边的定义构成了一个有向图

我们只需要解析GML文件，将节点和边导入Neo4j数据库，再进行路径搜索即可

效果还是很好的

为什么我一开始说的是优化搜索逻辑呢？

因为这些工作其实早就做完了，并不是周末做的，上面的搜索相当耗时，单位都是小时来计算，我看看弄一台服务器来跑

在图够准确的情况下，我将两个小时的搜索压缩到了一分钟以内

优化一

首先我们将GML重写，将所有节点解析成一行，然后申请内存，此处用C语言写，将数据存储在内存里，用结构体存储节点，并且我们只需要id和label两个结构体成员

node [ id 0 label "Landroidx/activity/R$attr;-><init>()V [access_flags=private constructor] @ 0xe4e4" ]
node [ id 1 label "Ljava/lang/Object;-><init>()V" ]
node [ id 2 label "Landroidx/activity/R$color;-><init>()V [access_flags=private constructor] @ 0xe4fc" ]
node [ id 3 label "Landroidx/activity/R$dimen;-><init>()V [access_flags=private constructor] @ 0xe514" ]

将所有节点写入内存，这里小几十万个节点写入堆完全没问题的

但是这里的写，并不是随便申请堆空间吭哧吭哧就往里面写，而是利用偏移存储

我们在进行GML重写的时候大概计算一下所有label字段拼接的长度，有了这一长度数据，我们就可以在堆空间申请的时候有一个大概的参考

申请label堆空间之后，我们申请所有Node结构体的堆空间，都申请好之后，开始写入数据

这里我们将结构体的概念去除，完全靠偏移，从Node结构体的堆首地址开始往下写，使用一个额外的读指针指向label堆空间

第一个Node：写入第一个节点的id，第二个字段是label堆空间的首地址，写完label堆空间将指针挪动，并且记录堆地址起点

第二个Node：写入第二个节点的id，第二个字段直接赋值为上面记录的新堆地址起点，重复上面的挪动过程

后面的节点按照上面的操作记录即可

此时我们分割Node结构体的堆空间，长度按照大家的运行平台计算，但是每个结构体所占用的长度肯定是固定的

比如我这里需要获取id为1000的结构体，那么从Node结构体堆空间起始地址开始，算上一千个结构体长度，就是我们需要的节点，对其进行取值即可，这是我用来存储的方式

优化二

实践过的同学都会发现一个问题，就是冗余的节点和边实在是太多了，又用不到，徒增性能开销

node [ id 0 label "Landroidx/activity/R$attr;-><init>()V [access_flags=private constructor] @ 0xe4e4" ]
node [ id 1 label "Ljava/lang/Object;-><init>()V" ]
node [ id 2 label "Landroidx/activity/R$color;-><init>()V [access_flags=private constructor] @ 0xe4fc" ]
node [ id 3 label "Landroidx/activity/R$dimen;-><init>()V [access_flags=private constructor] @ 0xe514" ]
node [ id 4 label "Landroidx/activity/R$drawable;-><init>()V [access_flags=private constructor] @ 0xe52c" ]
node [ id 5 label "Landroidx/activity/R$id;-><init>()V [access_flags=private constructor] @ 0xe544" ]
node [ id 6 label "Landroidx/activity/R$integer;-><init>()V [access_flags=private constructor] @ 0xe55c" ]
node [ id 7 label "Landroidx/activity/R$layout;-><init>()V [access_flags=private constructor] @ 0xe574" ]
node [ id 8 label "Landroidx/activity/R$string;-><init>()V [access_flags=private constructor] @ 0xe58c" ]
node [ id 9 label "Landroidx/activity/R$style;-><init>()V [access_flags=private constructor] @ 0xe6d0" ]
node [ id 10 label "Landroidx/activity/R$styleable;-><init>()V [access_flags=private constructor] @ 0xe6b8" ]
node [ id 11 label "Landroidx/activity/R;-><init>()V [access_flags=private constructor] @ 0xe6e8" ]

既然重写，那就重写的更彻底一些，我决定缩点，这里的缩点并非图论里的缩点，但是思想类似

我这里的缩点有两步

将入度和出度都为0的节点优化掉
将系统库内调用的节点优化掉

第一个缩点很好理解，有向图的节点入度和出度都为0表示没有边，没有边的节点表示没有调用，直接删除

第二个缩点我们以代码来看，节点7093指向了节点7010，系统库内的调用对我们来说是没有意义的，所以我们可以进行动态标记，先将所有的边遍历一遍，把系统库内函数为source的边，全部删除

node [
    id 7093
    label "Landroid/support/v4/provider/TreeDocumentFile;->createDirectory(Ljava/lang/String;)Landroid/support/v4/provider/DocumentFile; [access_flags=public] @ 0x1ca25c"
    external False
    entrypoint False
]
  
node [
    id 7010
    label "Landroid/support/v4/provider/TreeDocumentFile;-><init>(Landroid/support/v4/provider/DocumentFile; Landroid/content/Context; Landroid/net/Uri;)V [access_flags=constructor] @ 0x1ca1f4"
    external False
    entrypoint False
]
  
edge [
    source 7093
    target 7010
]

这里是否有例外呢？我还不能肯定，还请师傅们指点

补充有向图的三个概念

强连通：有向图G存在节点A和节点B，节点A有一条路径可以到达节点B，节点B有一条路径可以到达节点A，就叫作两个节点强连通

强连通图：有向图G中任意两个节点都强连通，就叫作强连通图

强连通分量：有向图G中有一个子图，这个子图满足任意两个节点强连通，就叫作强连通分量

有向图的缩点是指求出有向图G所有强连通分量之后，将每一个强连通分量以一个节点的形式来表示，重构有向图G的过程

思路我已经抛出来了，大家可以思考下是否能通过图论里的缩点思想，来实现路径搜索优化呢？

优化三

此时我们就可以开始构建图了，这个优化我先不说，而我用了什么方法，我相信聪明的读者看到我上面的存储方式，就已经猜到了:)

上面为什么我说”图够准确”呢？

因为安卓平台的应用存在大量的回调操作，比如控件Button的点击事件，而AndroGuard默认并未生成绑定监听相关的edge，这就造成了可能的误报和漏报

来看一个通过按钮点击跳转Activity的例子

protected void onCreate(Bundle bundle) {
    super.onCreate(bundle);
    
    ...
    
    v0_3.setOnClickListener(new bc(this));  // 此处绑定点击事件回调
    
    ...
}

final class bc implements View$OnClickListener {
    bc(SelectVideoActivity argActivity) {
        this.activity = argActivity;
        super();
    }

    public final void onClick(View view) {
        Intent intent = new Intent();
        intent.setClass(this.activity, SearchPagerActivity.class);
        this.activity.startActivity(intent);
        MTAReport.reportUserEvent("video_jce_circle_search_btn", new String[0]);
    }
}

对应的GML文件相关数据如下，可以看到有onClick()指向startActivity()的边，但是却没有指向回调函数的边

node [
    id 107682
    label "Lcom/tencent/qqlive/ona/circle/activity/SelectVideoActivity;->onCreate(Landroid/os/Bundle;)V [access_flags=protected] @ 0x6047ac"
    external False
    entrypoint True
]

node [
    id 107914
    label "Lcom/tencent/qqlive/ona/circle/activity/bc;->onClick(Landroid/view/View;)V [access_flags=public final] @ 0x607c5c"
    external False
    entrypoint False
]

node [
    id 107697
    label "Lcom/tencent/qqlive/ona/circle/activity/SelectVideoActivity;->startActivity(Landroid/content/Intent;)V"
    external True
    entrypoint True
]

edge [
    source 107914
    target 107697
]

对于这种问题，我决定自己优化AndroGuard的生成结果

上面这个例子对应的Smali代码如下，JEB和APKTool的结果略有出入，但不影响分析，可以看到调用关系还是很清晰的

我们最后处理的时候以APKTool反编译的Smali代码为准，我们不用关心这个点击事件回调绑定的哪个控件，只要存在，就把这条边记录下来

.line 1167
new-instance v1, Lcom/tencent/qqlive/ona/circle/activity/bc;

invoke-direct {v1, p0}, Lcom/tencent/qqlive/ona/circle/activity/bc;-><init>(Lcom/tencent/qqlive/ona/circle/activity/SelectVideoActivity;)V

invoke-virtual {v0, v1}, Landroid/view/View;->setOnClickListener(Landroid/view/View$OnClickListener;)V

路漫漫其修远兮，这是一项体力活

FlowDroid的工作说起来可就优雅多了

从官方的仓库获取代码，配置两个环境变量，然后mvn install就行了，虽然会有若干错误，还是比较容易解决的

中间最关键的一步就是切换到master分支，要解决的错误少多了

接下来我就投入精力到与FlowDroid运行效率作斗争的工作中

Share this article: