Page 313 - 《软件学报》2024年第6期

徐建 等: LibPass: 基于包结构和签名的第三方库检测方法 2889

j ⩽ n} , 其中 s ij 表示包 p i 与 p j 之间的依赖强度.
∑ n ∑ m
定义 3. 依赖强度. 任意两个包 p i 与 p j 之间的依赖强度 s ij , s ij = w t(e x ,e y ) e x ∈ p i ,e y ∈ p j , 其中 t(e x ,e y )
|
x=1 y=1
获取 e x 和 e y 之间的关系类型, 值为 1 到 5.
定义 4. 应用程序根包 ARP. 应用程序根包是由 m 个具有最长共同路径, 且有强依赖关系的子包构成的,
arp = {asp ,...,asp ,...,asp } , 满足两个约束条件: 1) path(asp )∩...∩ path(asp )∩...∩ path(asp ) , ∅ ; 2) 对于任
m
1
1
m
i
i
意的子包 asp , 至少存在一个子包 asp , j , i , 使得 asp 与 asp 的依赖强度 s ji 大于依赖强度阈值 δ d .
i
j
j
i
第 1 个约束条件表明同一个根包中的所有子包应该具有相同的命名空间, 这符合 Java 语言中包命名机制. 但
是仅依赖于相同的路径前缀来判别两个或多个子包是否属于同一个根包是不充分的. 以两个较为广泛使用的第三
方库 com.google.common 和 com.google.zxing 为例, 它们具有相同的路径前缀 com.google, 但是不存在依赖关系.
因此, 第 2 个约束条件用于增加同一个根包中子包间存在依赖关系的判定, 仅查找一个子包与该根包中至少一个
子包有依赖关系.
一旦判定 APK 没有混淆, 算法第 4 行直接通过解析其 AndroidManifest.xml 文件中包含的关于“package”的元
信息获取主模块的名称, 否则算法第 6 行为混淆 APK 构建根包级别的包依赖关系图. 值得注意的是, 这里仍然沿
图
用定义 2 和 3 来构造包依赖关系图, 只不过需要将节点表示的 ASP, 替换为 ARP. 算法第 7 行负责在 PDG 上度量
每个节点的依赖强度, 并且根据依赖强度对模块进行降序排列; 算法第 8 行将所有的模块按照依赖强度大小逆序
排列, 依赖强度最大的模块作为主模块.
2.2 基于包结构树的候选 TPL 识别方法
应用主模块识别方法排除 APK 中的主模块后剩余部分以根包的形式组织, 每个 ARP 都可能源自于特定的
TPL. 为了提升混淆情形下的检测精度, 提高检测效率, 提出了一种基于包结构树的候选 TPL 方法, 该方法利用包
结构特征的稳定性来应对混淆, 并借助于包结构签名完成快速比对识别候选 TPL. 该方法由包结构树生成、包结
构树签名和基于签名的候选筛选等过程构成.
首先, 构造包结构树. 无论是 ARP, 还是 LRP, 都是由若干个具有层次关系的子包构成, 因此根据包层次关系
以点分隔法可以为一个 ARP 或 LRP 构造为一棵缺省的包结构树, 同一层上隶属于相同父节点的子包以字典序排
序. 以第三方库“glide-3.8.0”的根包“com.bumptech.glide”为例, 生成的缺省包结构树如图 3(a) 所示. 集成到应用程
序中的 TPL 在应用正式发布前会进行混淆, 可能删除部分库中未被使用的子包, 还可能混淆包名, 这些混淆操作
会导致包结构树显著地不同于所引入 LRP 的缺省包结构树, 从而使得通过比较包结构树的方式识别 TPL 的方法
准确性低. 为了对抗混淆, 提升检测准确率, 引入了包结构树整形概念, 涉及两个操作, 一是改变子包排序方式, 二
是对包名进行重命名. 具体地, 考虑以子包重要性排序替换缺省包结构树中同一层上隶属于相同父节点的子包以
字典序排序的方式, 同时对所有包名进行重命名. 子包重要性取决于在包结构树中每个子包拥有的孩子节点个数,
即在包结构树中拥有更多孩子节点的子包承载更多功能, 其重要性更高, 在混淆阶段被移除的可能性更小, 因此将
其放置在同一层上的更左侧位置. 按照自顶向下方式对包结构树进行整形, 先计算同一层上的节点作为根节点, 子
树拥有的节点数, 并按照从左到右降序排列, 即拥有孩子节点数多的节点放置在树的左侧; 然后, 将同一层上有相
同的孩子节点数的节点按照节点名字母顺序降序排列; 最后, 对整形后的包结构树上的节点进行重命名, 即将每层
隶属于同一个父节点的节点从左到右用大写字母升序进行替换. 图 3(a) 中的包结构树经过整形后得到了如
3(b) 所示的结果, 其中括号中字符串表示整形操作中重命名后结果, 从图中可以看出第 2 层上节点 load 包含的
子包数目最多, 是构成第三方库的重要组成部分, 在混淆阶段被移除的可能性小.
在为待比较的 ARP 和 LRP 构造包结构树后, 直接比较它们对应的包结构树仍然需要较大的计算代价, 为此
引入包结构树签名, 如定义 5 所示, 通过深度优先方式遍历包结构树生成包结构树签名.
定义 5. 包结构树签名 (package structure tree signature, PSTS). 一个根包的包结构树签名是一个哈希值,
(∑ n )
Sig (p) = hash strcat(name(p i ),‘,’) , name(p i ) 表示子包 p i 的名称, strcat(·,·) 表示字符串连接操作, hash(·) 表
pst
i
示通过哈希算法计算字符串的的哈希值, 这里采用 16 位的 MD5 算法计算哈希值.