大土豆安全笔记
这篇文章会涉及一些基础的图论名词，但都简单易懂，且只聊思路，并不涉及太多的代码，请放心阅读
周末做了两件事
- 优化了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运行效率作斗争的工作中