FANS阅读笔记

论文FANS: Fuzzing Android Native System Services via Automated Interface Analysis阅读笔记和代码阅读笔记

FANS: Fuzzing Android Native System Services via Automated Interface Analysis [29th USENIX]

文章提出了一个全自动化fuzz安卓原生系统服务的工具。
依照AOSP编译流程，扫描涉及interface的相关代码源文件，得到所有interface基本信息
通过对interface model的理解，生成合法的输入进行测试。
测试框架采用CS架构，建立在多台测试真机和服务器之上，发现了若干漏洞和exception。

Knownledge

Android native system service

binder & RPC

challenges

1. Android原生系统服务通过基于Binder的特定接口唤醒，所以需要自动识别并生成针对性的测试用例。
2. 有效的测试用例需要满足对应的接口模型。
3. 有效的测试用例还得满足语义要求，包括变量依赖和接口依赖

routine

1. 首先收集目标服务中所有的interface和nest-interface。
2. 然后提取interface model以及interface AST，包括transaction code, variable name, variable type in transaction data。
3. 基于variable name&type推断variable dependency，基于生成和使用关系推断interface dependency。
4. 基于以上的interface model和dependency知识，生成语义语法合规的sequence of transactions。
5. 实验在6台Android9机器上进行，从数千个crash中发现了20个vulnerabilities,20个已经被Google确认。以及138个Java exceptions。

1 Introduction

1.1 Related Work

BinderCracker

通过记录调用来获取target service model。

不能获取准确的输入语义知识（变量名和变量类型），也不能获取rare interface和nested interface。

Chizpufle

改进BinderCracker: 使用反射技术获取目标interface的参数知识，用于fuzz厂商预置的Java服务。
但是不能测试Android原生系统服务。

1.2 Challenges&Approaches

1. interface识别：top-level&multi-level【Location】
   【现状】
   top-level会在ServiceManager中完成注册，multi-level interface通过top-level interface被获取。
   多数interface通过AIDL定义，C++定义或者动态生成的interface是少数（之前的研究没有找到统一规律）。
   【解决】
   扫描Service注册操作，得到所有的top-level interface
   扫描writeStrongBinder方法得到所有的multi-level interface。(deep interface通过调用该方法动态生成)

2. interface model extraction【Grammar】
   【现状】
   对于每个interface，需要找到支持的transactions列表。
   需要确定interface输入数据的格式，且每个transaction有自己的输入数据格式，需要完全的自动化。
   【解决】

   考虑到Android总是使用一系列特定的方法来实现序列化和反序列化（readInt32, writeInt32），所以可以通过识别这些方法的调用序列，推断出interface的输入语法。
   为了维护变量的名字和类型，这里建立了发序列化操作的AST。

3. 语义合法的输入生成【Semantic】
   【现状】
   Android会有安全检查（Sanity Check），因此输入的data需要语义合法。
   语义要求包括变量名、变量类型、变量依赖、interface依赖以及变量和interface之间的依赖，比较难提取。
   【解决】
   通过2中获取的变量名和类型的知识，识别transaction内的变量依赖。
   依赖transaction会反序列化被依赖transaction序列化的data，由此可以建立transaction之间的依赖关系。
   通过生成&使用关系推断interface之间的依赖关系。

2 Background

2.1 Android System Service

category

Java System Service[Java: Activity Manager]
Native System Service[C++: Camera Service]

Services in normal domain, vendor domain, hardware domain。

Application-Service Communication Model

service向service manager注册自己；
service监听并响应application的调用，返回调用结果；

application向service manager请求目标service的interface(top-level interface)；
application向top-level interface请求multi-level interface；
application调用目标interface的transaction完成动作；

2.2 Research Scope

Android native system service
相关经验可以推广到其他类别的service

3 Design

3.1 Design Choices

RPC-centric testing

测试系统服务，可以直接向系统注入服务可响应的事件，直接绕过RPC。
但是这种做法会因为生成了大量异常事件带来极高的误报率。

因为在实际中，攻击者与service的交互会经过IPC机制。
而IPC Binder会对数据进行安全检查，序列化操作也会受到系统状态的影响。
实现难度较大
所以，需要通过将生成数据注入IPC Binder机制，使得达到service的数据满足一定的语法语义特征，从而降低误报率。

Generation-based fuzzing

mutation-based fuzzing生成的测试数据容易出现语法错误或者语义错误，所以选择Generation-based fuzzing。

Learn input model from code

如何指导测试用例的生成？
grammar knowledge obtained manully: 大量人工参与，不能自动化
learn from transactions recorded：受数据集影响较大，有什么数据学到什么知识；容易忽略不常见的transaction

从源代码中挖掘输入模型的知识，input model knowledge is buried in the source code

3.2 Overview

3.3 Interface Collector

每一个interface都会使用onTransact()方法来响应调用操作，可以根据这个知识来识别出所有的interface。
具体来说，FANS并不是直接扫描AOSP的所有C/C++源代码，而是扫描出现在编译命令中的所有C/C++源代码，这样子可以识别出通过AIDL动态生成的interface。

（存疑）
目前看来是把AOSP代码编译一遍，然后记录所有的编译命令，搜索编译命令中涉及到的文件，对去检查这些文件是否包含关于接口的代码。
这样子就可以检查到编译过程中通过AIDL动态生成的interface。

3.4 Interface Model Extractor

对interface建模

3 Principles

Complete-完备：所有的interface，所有的transaction
Precise-准确：要生成合法的输入通过IPC Binder的安全检查。（从变量模式、变量名和变量类型入手，也就是语法与语义都要合法）
Convenient-便捷：建模方法要简单。

Choices

选择深入分析server端的代码，以期达到更为准确全面的提取效果。
先使用工具将AIDL接口代码转化为C/C++代码，保留信息的准确性。
再建立AST提取onTransact()方法的信息。

Transaction Code Identification

Service->Interface->Transaction

一个Service可能有多个Interface，在一个Interface中，根据收到的code的不同，会进入不同的处理逻辑，称transaction。

具体到onTransact()方法中，interface会根据code将控制流分配到不同的transaction逻辑中。
一般会通过switch语句实现，case就是code值了。
所以建立了onTransact()的AST模型之后，不同的transaction就会形成不同的子树，由此识别出不同的transaction。

Variable Extraction

通过建立AST，获取interface-transaction输入输出的语法语义知识。 Gammar&Semantic

当完成了transaction代码的识别之后，需要进一步地识别出transaction从data中反序列化得到的所有输入变量。
因为要尝试推断inter-transaction依赖，所以还要识别向replay中序列化注入了哪些输出变量。

flag不需要fuzz，后文用于标记synchronized call和asynchronized call。

变量通过代码语句生效，从编码的角度而言，有顺序语句、条件语句和循环语句，这里再特别分类出返回语句，那么变量也有相应的4类。

Sequential Variable:

checkInterface(): 检查client端提供的token是否合法
readXXX(): readInt32, readString16
read(a, sizeof(a)*num): 读入一个原生数据结构
read(a): 读入一个可子序列化的对象 Flattenable&Light-Flattenable
readFromParcel(&data): 基于自己实现的反序列化方法获取对象
callLocal():
Misc: 调用其他函数处理，递归式识别

Conditional Variable

if&switch语句，将相关的变量(fd)作为conditional input

Loop Variable

识别出循环语句内部的变量，记为loop variable

Return Variable

如果一条执行路径返回了ERROR_CODE，那么这条路径出现漏洞的概率更低。
虽然在fuzz的过程中，总是希望输入使得目标程序出现ERROR，但是这里的ERROR是程序本身识别抛出的，说明存在一定的安全检查逻辑。
所以会把这条执行路径降权，生成较少的测试用例来测试这条路径。

同时，会帮助建立准确的transaction间依赖关系。（存疑）

Besides, it will also help us generate explicit inter-transaction dependency, as inputs that do not satisfy the dependency usually fall back to error handling paths.

Type Definition Extraction

都可以通过AST完成

在基本类型之外，需要重点分析以下三类

structure-like: 联合体和结构体
Enumeration: 枚举类
Alias: typedef别名，注意命名空间namespace，避免冲突；可能会递归头文件

3.5 Dependency Inferer

interface dependency: how an interface is used by other interface
variable dependency in transaction

Interface Dependency

onTransact() write/readStrongBinder() 在interface extrector和interface dependency inferer中的作用不是非常明确。

用这两种方法标定interface？
还是说先用onTransact()标定top-level interface，然后用write/readStrongBinder确定依赖关系，同时标定multi-level interface？

我认为是后者，因为在interface-colletor.py中还是单纯依赖onTransact()函数名判断是否为interface related file

【原文】Interface Acquisition： As for top-level interfaces, we can get them through the service manager. Multi-level interfaces can then be recursively obtained via the recognized interface dependency

Generation Dependency

如前所述，top-level interface会直接向servicemanager注册自己，直接被获取。
multi-level interface通过top/upper-level interface的返回来获取。

向A接口请求B接口，则A接口会调用**writeStringBinder()**方法向reply写入一个序列化的B接口，然后返回给调用者。

Use Dependency

如果B接口使用了A接口，那么B接口会调用readStrongBinder()方法从data中反序列化一个A接口出来用。

区别

A接口生成B接口，写入reply中给调用者使用。
B接口从接收的data中反序列化出来一个A接口使用。

Variable Dependency

intra-transaction

条件语句->条件依赖
循环语句->循环依赖
array类数据->array依赖，通常会有一个变量来声明array的长度，类似循环依赖

inter-transaction

一个transaction的input可能是另外一transaction的output。（两个transaction同属一个interface）

这里采取的是一些模糊的规则来建立跨transaction的两个变量之间的依赖（依据存疑）

1. 一个变量是输入，一个变量是输出
2. 处于不同的transaction
3. 变量的类型相同 (primitive type)
4. 要么输入变量的type不是基本类型，要么两者的变量名相似

3.6 Fuzzer Engine

Fuzz工作在设备上进行
Manager将fuzzer和语料传递到设备上
fuzzer将日志数据传回用于分析

Principles of Transaction Generator

在生成transaction数据时，依次满足以下三个principle

1. 约束：A变量是否存在取决于B变量，则在生成transaction时，先检查B变量

2. 依赖：如果A变量可以通过一个transaction生成，则以较高的概率通过这个transaction生成一个A变量，以较低的概率不通过transaction生成

3. 类型与名称：直接根据变量的类型和名称生成具体的值，例如根据opPackageName生成一个String16，根据pid生成一个int。

   依赖原则是调用其他transaction生成数据，类型与名称原则是直接生成，相互矛盾。
   如果有个变量A既可以通过transaction生成，也有type和name，如何处理？
   依照原则的优先级，应该以较高概率使用依赖原则调用其他transaction生成数据，以较低概率直接直接生成。

4 Implementation

从零开始的FANS，而不是AFL-based。

搜索接口 Interface Collector

因为有的interface是通过AIDL动态生成的，所以这里是在编译AOSP源码的过程中记录编译命令，获取到interface和variable。
具体的原理尚不清楚，但是根据前文“并不是扫描整个AOSP源码”描述，猜测可能是通过编译命令涉及到的文件缩小搜索范围，根据onTransaction获取interface相关代码文件，然后提取interface model。

提取接口 Interface Model Extractor

使用Clang生成AST文件，只保留AST中与输入输出变量相关的节点，接着进行后续处理使其可以被fuzzer使用。(JSON格式)

依赖推断 Dependency Inferer

遍历AST，推断出interface的generation dependency和use dependency，
以及variable的inter-transaction dependency。

Fuzzer Engine

在host上的Fuzzer Manager会在多台设备上运行fuzzer、同步数据。

使用ASan检查内存错误

fuzzer以root权限运行

配置flag，表示是否需要接收reply，指定transaction是synchronous还是asynchronous

logcat+tombstones记录crash

5 Evaluation

Interface

Interface Collection

编译1小时，搜索几秒钟，共计68个interface。

Interface Dependency

依赖关系图大致是有向无环图。
一个interface可以通过多个上级interface得到，于是从多条依赖路径来测试目标interface。

Interface Model 1375

811个interface transactions，1375条transaction path，说明许多transaction有多条执行路径、多个返回可能。

statistices

多数变量是conditional variable

所有的别名操作（typedef）都是对三种基本变量的重组，内涵更多的语义信息。

Primitive、String之间的依赖较多

建模方法的准确性

因为没有可以对比的数据和研究，所以这里是随机选择了10个interface手动建模对比的。

not entirely precise but good enough

漏洞列表

共计30个漏洞，22个在Android native system service中， 5个在lib中，3个属于Linux的漏洞。

还触发了138个Java Exception

6 Discussion

对比评价

BinderCracker

开源 vs 闭源

基于input model vs 基于traffic学习

30+138 on 9.0 vs 89 on 5.1

automated vs manully [gong(first)]

native and promote vs vendor [Chizpurfle]

自我评价

Interface Model Accuracy

good enough but not entirely precise

loop次数的判定：如果不能准确确定，就使用loop的前一个变量。
用alias标识变量类型，但是使用时又用primitive type。
transaction dependency: 可能存在特定的调用顺序，服务可以被视作状态机 （？state-sensitive）

Coverage Guided Fuzzing

没有使用覆盖率知识
state-sensitive: 当前程序的coverage也还受到之前输入的影响。（Fork()）

Fuzzing Efficiency

fuzzer以root权限运行，导致系统经常进入recovery模式。
然后就得手动重新刷机，影响实验效率。

Interface-based Fuzzing in Android

提出可以把本文的理论推广到vendor service和hardware service。

7 My View

测试部署架构，不够稳定，性能不够 -> 模拟器

FANS Code Review

android.googlesource.com访问有问题，使用aosp.tuna.tshinghua.edu.cn替换来git clone

python2，安装python2或者退出anaconda的base环境

# 可能需要安装以下库文件
sudo apt-get install libx11-dev:i386 libreadline6-dev:i386 libgl1-mesa-dev g++-multilib
sudo apt-get install -y git flex bison gperf build-essential libncurses5-dev:i386
sudo apt-get install tofrodos python-markdown libxml2-utils xsltproc zlib1g-dev:i386
sudo apt-get install dpkg-dev libsdl1.2-dev libesd0-dev
sudo apt-get install git-core gnupg flex bison gperf build-essential
sudo apt-get install zip curl zlib1g-dev gcc-multilib g++-multilib
sudo apt-get install libc6-dev-i386
sudo apt-get install lib32ncurses5-dev x11proto-core-dev libx11-dev
sudo apt-get install libgl1-mesa-dev libxml2-utils xsltproc unzip m4
sudo apt-get install lib32z-dev ccache
sudo apt-get install libssl-dev
sudo apt-get install libxml2-dev libxml2-doc

# 我觉得日志最后输出这些就算编译好了
[100% 73879/73879] /bin/bash -c "(export SGDISK=out/host/linux-x86/bin/sgdisk; device/generic/goldfish/tools/mk_qemu_image.sh out/target/product/generic/system.img)"
1+0 records in
2048+0 records out
1048576 bytes (1.0 MB, 1.0 MiB) copied, 0.00850228 s, 123 MB/s
1536+0 records in
1536+0 records out
1610612736 bytes (1.6 GB, 1.5 GiB) copied, 1.41226 s, 1.1 GB/s
1048576+0 records in
1048576+0 records out
1048576 bytes (1.0 MB, 1.0 MiB) copied, 0.977471 s, 1.1 MB/s
Creating new GPT entries.
Warning: The kernel is still using the old partition table.
The new table will be used at the next reboot.
The operation has completed successfully.
Setting name!
partNum is 0
REALLY setting name!
Warning: The kernel is still using the old partition table.
The new table will be used at the next reboot.
The operation has completed successfully.

[0;32m#### build completed successfully (28:52 (mm:ss)) ####[00m

搜索相关教程，把Android Pie的编译流程走一遍。由命令make -j [N_PROCS] showcommands 2>&1 >cmd.txt，得到cmd.txt保存编译命令。

# 一行编译命令如下
[ 89% 65753/73879] /bin/bash -c "(rm -f out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.dynsyms out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.funcsyms out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.keep_symbols out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.debug out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.mini_debuginfo.xz ) && (if prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-strip --strip-all -R .comment out/target/product/generic/symbols/system/lib/vndk-28/libstagefright_omx.so -o out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so; then prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-objcopy --only-keep-debug out/target/product/generic/symbols/system/lib/vndk-28/libstagefright_omx.so out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.debug && prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-nm -D out/target/product/generic/symbols/system/lib/vndk-28/libstagefright_omx.so --format=posix --defined-only | awk '{ print \$1 }' | sort >out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.dynsyms && prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-nm out/target/product/generic/symbols/system/lib/vndk-28/libstagefright_omx.so --format=posix --defined-only | awk '{ if (\$2 == \"T\" || \$2 == \"t\" || \$2 == \"D\") print \$1 }' | sort >out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.funcsyms && comm -13 out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.dynsyms out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.funcsyms >out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.keep_symbols && echo >>out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.keep_symbols && prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-objcopy --rename-section .debug_frame=saved_debug_frame out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.debug out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.mini_debuginfo && prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-objcopy -S --remove-section .gdb_index --remove-section .comment --keep-symbols=out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.keep_symbols out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.mini_debuginfo && prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-objcopy --rename-section saved_debug_frame=.debug_frame out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.mini_debuginfo && rm -f out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.mini_debuginfo.xz && xz out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.mini_debuginfo && prebuilts/gcc/linux-x86/arm/arm-linux-androideabi-4.9/bin/arm-linux-androideabi-objcopy --add-section .gnu_debugdata=out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so.mini_debuginfo.xz out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so; else cp -f out/target/product/generic/symbols/system/lib/vndk-28/libstagefright_omx.so out/target/product/generic/obj/SHARED_LIBRARIES/libstagefright_omx.vendor_intermediates/libstagefright_omx.vendor.so; fi )"

1 Service Related File Collector

旨在收集与Android native system service相关的文件，具体来说，与以下主体相关：

1. top-level & multi-level interface
2. 标准的parcel、flattenable、lightFlattenable结构体
3. 接收parcel类参数的函数
4. 不使用readFromParcel&writeToParcel的特殊parcel结构体

大致流程如下：

1. FANS分析cmd.txt文件，提取AOSP编译过程中涉及到的cpp/cc文件，缩小搜索范围，同时排除特定目录下的文件和hardware相关的代码文件
2. 枚举文件每一行代码，根据status_t xxxxx::onTransact(的模式确定包含的interface，将interface和当前文件file关联
3. 如果代码包含interface，那显然是interface-related
4. 如果代码中有readFromParcel、writeToParcel、flatten、unflatten关键字，说明可能与interface交互，也是interface-related的
5. 如果代码中有包含misc_parcel_related_function或者special_parcelable_function，也视作是interface_related的
6. 最后输出两个文件，记录interface与所在文件路径的json格式文件[interface2file.json]，记录所有interface-related file的文件[service_related_file.txt]。

2 Interface Model Extractor

2.1 Pre-Procees

根据readme.md，似乎得先把llvm以及clang-6.0配置好再运行gen_all_related_cc1_cmd.py。

gen_all_related_cc1_cmd.py又把cmd.txt拿出来分析，把AOSP编译过程中涉及到clang编译的命令记录筛选出来。（”-v 2>&1”，把错误输出也定向到标准输出），然后把结果保存为json，键值关系是<filepath,cmd_result>。

extract_from_ast.py把前一步得到的cmd_result拿出来，把aosp_clang_location替换为manually_build_clang_location，同时修改了一些其他的编译配置，然后去执行编译一遍。最后检查命令行的输出结果，确保编译顺利完成。

考虑到在上述两者之间，我们还手动编译了BinderIface，需要搞懂它的作用。这里面涉及到了一些AST的东西。
同时需要注意的是，整个pre-process的工作都还是只提取interface/service related information，真正的处理还是得看post-process。

BinderIface

VisitTypedefDecl()： 似乎是记录编译目标cpp/cc时，涉及到的变量类型的alias和type，将其保存在typemap<underlyingType, qualifiedName>中。
暂时姑且认为BinderIface已经完成了对interface的AST操作。

Corner Case
在部分代码中，switch case语句并没有按照一定格式优雅地编写，需要手动调整这一小部分代码，便于后续处理。具体的细节在pre-process/misc.md中。

2.2 post-process

init.sh

重置一些目录和文件，然后调用init.py。处理一下pre-process中收集到的underlyingType与qualifiedName。
简单来说就是借用并查集操作，把各级别名与对应的基本类型直接关联起来。
从文件操作上来看，读入rough_interface_related_data_dir/typemap.txt，输出interface_model_extractor_dir/simplified_typemap_file.txt。