大土豆安全笔记 | 利用记忆化搜索解决漏洞路径重复搜索

今天这篇文章希望能够跟在做基于控制流图的漏洞扫描器的同学们有更进一步的交流

简单描述下问题场景：我们在常规开发中，因为种种目的，会实现一个BaseActivity之类的组件作为基本Activity，Service，BroadcastReceiver同理，此处仅以Activity举例

假设有五个Activity继承BaseActivity，BaseActivity未在AndroidManifest注册，五个子类都在AndroidManifest注册且导出，按照漏洞攻击面扫描的思路，我们会对导出的组件进行分析，所以此时五个子类加入扫描队列

组件Activity有很多的Override方法，但一般我们可以不需要全部进行搜索，挑选一些比较常见的即可，但有时候也会出现奇奇怪怪的入口，比如按返回键会触发的onBackPressed()，之前TikTok就是在onBackPressed()里存在私有组件越权调用，结合FileProvider获取私有目录动态库的读写权限，导致了本地代码执行

overrideFunctions := []string{
    "->onCreate(Landroid/os/Bundle;)V",
	"->onActivityResult(IILandroid/content/Intent;)V",
	"->onNewIntent(Landroid/content/Intent;)V", 
	"->onBackPressed()V", 
	"->onResume()V"}

以Override方法onCreate()为例

当我们搜索A.onCreate()的时候，因为存在super.onCreate()调用，所以会回到BaseActivity.onCreate()，此时BaseActivity.onCreate()被搜索一次

当我们搜索B.onCreate()的时候，也会因为super.onCreate()的调用，回到BaseActivity.onCreate()进行搜索，此时BaseActivity.onCreate()被搜索两次

所以在这个例子中，光onCreate()方法就会搜索五次BaseActivity.onCreate()，这相当浪费时间

补充一下，当子类没有实现onCreate()的时候，动态运行时也是会有一个从子类onCreate()到父类onCreate()的调用，如果是这种情况我们需要手动进行这条边的补全

今天我们不聊边的补全，主要是来解决路径重复搜索的问题

上一篇文章我简单提过一种思路，就是在搜索的时候，记录下当前节点是否被搜索过，如果搜索过，直接获取搜索的结果，这个方法其实是有名字的，叫作记忆化搜索

我当时脑子一抽就想出了这个方法，但是记忆化搜索这几个字给忘了，潜意识里就觉得该这样搞，可能是搞ACM的后遗症

记忆化搜索的核心是记录当前节点的搜索结果，常见会把记忆化搜索跟动态规划结合在一起，如果仔细一想的话，其实也是符合状态转移方程来处理的

今天我对上一篇文章中提出的思路进行了修改，更加合理，更容易实现

全局定义一个用于记忆化搜索的字典globalDPMap，然后为方法结构体添加一个布尔类型的字段isStartActivitySearched，这里只是为了测试关键节点startActivity()，后续工作要补全剩余所有需要搜索的关键节点

以上图为例，我们先搜索入口A.onCreate()，因为此时是第一次搜索，所以globalDPMap为空，无法进行判断，这个字典在此处也就没有作用，因为super.onCreate()的存在，此时会调用BaseActivity.onCreate()，BaseActivity.onCreate()里会调用方法startActivity()，那么一条攻击路径就出来了

A.onCreate() -> BaseActivity.onCreate() -> startActivity()

到此搜索导出组件A的Override方法onCreate()就完成了，同理还有上面提过的好几个其它方法也会进行搜索

当导出组件A的所有Override方法都完成对关键节点startActivity()的搜索，我们开始处理返回结果，依次遍历所有的攻击路径，将攻击路径存储到路径关联到的节点

依旧是这条攻击路径

A.onCreate() -> BaseActivity.onCreate() -> startActivity()

我们先取路径第一个节点A.onCreate()，任意一个节点在此时出现都说明它已经被搜索过某个关键节点，比如这里就是startActivity()，我们先将节点A.onCreate()对应方法结构体里的字段isStartActivitySearched赋值为true，把这个节点名作为键，存储到globalDPMap，它的键值也是一个字典，它的键是关键节点的漏洞标识，比如当前搜索的是startActivity()，那就存储为startActivity()，比如ZipFile解压缩路径穿越，就写ZipEntryGetName()，自己能识别出来就好，它的键值用字符串数组数组来存储，这里没写错，是字符串数组数组，因为路径绝不会只有一条，它一般都会有很多条，第一个路径节点处理完的结果如下

{
    "A.onCreate()": 
    {
        "startActivity()": [["BaseActivity.onCreate()", "startActivity()"]],
        "ZipEntryGetName()": [],
        ...
    }
}

取路径第二个节点BaseActivity.onCreate()，把这个节点名作为键写入，同时往字典里对应的位置写入路径，同时标记BaseActivity.onCreate()对应方法结构体的字段isStartActivitySearched为true

{
    "A.onCreate()": 
    {
        "startActivity()": [["BaseActivity.onCreate()", "startActivity()"]],
        "ZipEntryGetName()": [],
        ...
    },
    "BaseActivity.onCreate()":
    {
        "startActivity()": [["startActivity()"]],
        "ZipEntryGetName()": [],
        ...
    }
}

最后一个节点就是关键节点，不进行搜索

搜索入口来到导出组件B的系列Override方法，当搜索到B.onCreate，因为super.onCreate()会去调用BaseActivity.onCreate()，我们拿要搜索的节点到globalDPMap查询是否存在扫描结果，发现BaseActivity.onCreate()对应方法结构体的字段isStartActivitySearched为true，说明这个节点扫描过这个关键节点，globalDPMap存在对startActivity()的扫描结果，那么直接获取路径数组即可，就不再需要重新扫描一次

接下来开始实现环节，入口限制为导出Activity的Override方法onCreate()，且只搜索关键节点startActivity()

在未进行记忆化搜索的时候，日志如下，可以看到类Settings$CreateShortcutActivity和Settings$NetworkDashboardActivity都未实现Override方法onCreate()，且都找到了父类SettingsActivity的Override方法onCreate()进行搜索

[*] [Go Scanner] Start Searching Context.startActivity() -> 
[!] Find Activity ==> Lcom/android/settings/homepage/SettingsHomepageActivity;->onCreate(Landroid/os/Bundle;)V
    [!] 进入搜索 Lcom/android/settings/homepage/SettingsHomepageActivity;->onCreate(Landroid/os/Bundle;)V
[!] Find Activity ==> Lcom/android/settings/network/telephony/MobileNetworkActivity;->onCreate(Landroid/os/Bundle;)V
    [!] 进入搜索 Lcom/android/settings/network/telephony/MobileNetworkActivity;->onCreate(Landroid/os/Bundle;)V
[!] Not Find Activity Override Function ==> Lcom/android/settings/Settings$CreateShortcutActivity;->onCreate(Landroid/os/Bundle;)V
    [!] Attempt to Find SuperClass ==> Lcom/android/settings/SettingsActivity;
[!] Find Activity ==> Lcom/android/settings/SettingsActivity;->onCreate(Landroid/os/Bundle;)V
    [!] 进入搜索 Lcom/android/settings/SettingsActivity;->onCreate(Landroid/os/Bundle;)V
[!] Not Find Activity Override Function ==> Lcom/android/settings/Settings$NetworkDashboardActivity;->onCreate(Landroid/os/Bundle;)V
    [!] Attempt to Find SuperClass ==> Lcom/android/settings/SettingsActivity;
[!] Find Activity ==> Lcom/android/settings/SettingsActivity;->onCreate(Landroid/os/Bundle;)V
    [!] 进入搜索 Lcom/android/settings/SettingsActivity;->onCreate(Landroid/os/Bundle;)V
...

全局定义一个记忆化搜索字典

// 定义
var globalDPMap map[string]map[string][][]string
// 创建字典
globalDPMap = make(map[string]map[string][][]string)

添加一个布尔字段isStartActivitySearched用于标记该方法节点是否搜索过关键节点startActivity()

type DexMethod struct {
	...
	isStartActivitySearched bool
}

在进行一个节点搜索之前先判断这个节点对应isStartActivitySearched是否为true，如果为true直接从globalDPMap中获取结果，无论是否有数据都获取，因为不是所有节点都能搜索到能到达关键节点的路径，如果为false，那就说明没有搜索过

在搜索完之后，遍历得到的路径，把每个路径都节点加入到globalDPMap里，并且把节点对应的isStartActivitySearched赋值为true

接下来我画个图来理解一下上面的文字描述

FirstActivity继承父类BaseActivity，从节点a开始，有非常多的关联节点

其中能到达关键节点startActivity()的有两条路径

FirstActivity.onCreate() -> BaseActivity.onCreate() -> a() -> b() -> d() -> h() -> startActivity()
FirstActivity.onCreate() -> BaseActivity.onCreate() -> a() -> b() -> d() -> i() -> startActivity()

按照上述记忆化搜索，我们会对这两条路径关联到的所有节点做标记，用绿色高亮出所有被标记的节点，关键节点不做标记

在完成第一条路径搜索之后，用于记忆化搜索的globalDPMap的数据如下图所示，这里有个细节处理是当前节点是否要加入路径，我选择不加入，在后续搜索的时候再把当前节点加到路径里

第二条路径也搜索完之后，我们着重看新增的部分是否正确，我用红框圈出来了

大家来思考一下，还有没有地方可以优化

我们这里只处理了那些能够到达关键节点的节点，另外那些不能到达关键节点的节点呢？

比如节点c，它其实已经被搜索过，只是没有可达路径，如果此时有一个SecondActivity.onCreate()调用了节点c，是不是得重新搜索一遍节点c？

所以新的优化方式来了

在搜索到达叶子节点的时候，对当前路径上所有节点进行标记，但是要进行条件判断，比如节点a往节点b走就存在路径，往节点c走就不存在路径，所以当我们遇到的节点为空节点，就可以标记为空路径，如果有值，就跳过不处理

在上篇文章里，我提到谷歌的应用Setting会反复的搜索类Lcom/android/settings/SettingsActivity;里的Override方法，因为它有很多子类，所以扫描的非常慢

这一次使用记忆化搜索之后，时间花费为69.451584ms，重复搜索父类的问题顺利解决

后来我测了今日头条和所有应用都克我的美团系APP，对于搜索同一个关键节点startActivity()，今日头条耗时586.960151ms，美团外卖则花了6.60880796s，效果喜人

前几天有个机会跟科恩的一位大佬聊了一个小时，收获颇多，大佬推荐我挖一挖Google Play的漏洞奖励计划，加油干！

• https://www.google.com/about/appsecurity/play-rewards/

华为最近也在推一个应用商店的活动，不过这个偏向隐私相关，严重这一栏里的第二个样例是”利用漏洞直接获取客户端最高权限”，这里的描述并不是很清楚，是说这个应用存在漏洞，可以被拿到最高权限，还是这个应用是恶意应用，利用其它应用的漏洞去获取其它应用的最高权限？

推荐一本书《最强iOS和macOS安全宝典》，搞iOS和macOS的同学都知道这本书有多难买，这半年有好几位好心的朋友自费从海外买了书然后邮寄回国内，前后花了好几千，还把扫描完的版本发我，这种方式得到书的小王学习的格外认真，小王算了一下，喊上各位老师一次性团购四本可以获得最优惠的单价，一本只需要五十三块，如果单本购买需要一百零一块，已安排

突然就想起我读大学的时候学习《0DAY2》，因为当时已经绝版，我是自己用A4纸打印了一本学习，由于我拿到的PDF版本是黑白的，所以很多OD调试时的截图里的内存数据根本看不清，只能先自己跟着调试，然后看着自己调试出来的数据进行猜测，虽然费了点劲，但是最后弹出计算器的界面是很让人激动的

后来这本书又重新组织印刷，我第一时间也买了一本，虽然已经用不上，但它永远是我安全路上最重要的一本书之一

最近的事情都在朝着自己所希望的方向发展，只要心怀热爱，永远都是当打之年！