wnagzihxa1n

wnagzihxa1n

iOS/Android Security

© 2021

大土豆安全笔记 2020.04.20

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

周末做了两件事

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

先讲讲Neo4j的搜索,用AndroGuard生成函数调用图,这个图是以nodeedge的形式存储在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数据库,再进行路径搜索即可

效果还是很好的

IMAGE

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

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

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

优化一

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

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" ]

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

我这里的缩点有两步

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

第一个缩点很好理解,有向图的节点入度和出度都为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的结果略有出入,但不影响分析,可以看到调用关系还是很清晰的

IMAGE

我们最后处理的时候以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运行效率作斗争的工作中

就如同李神探所说,如果能够在已有FlowDroid框架上进行优化到一分钟,都可以发Paper了

所以说当别人提出一些想法的时候,不要着急否定,你怎么知道我一口吃不成个大胖子呢?

有时候不多认识些优秀的同龄人,都不知道自己原来这么弱