近年来,随着移动设备的不断普及,移动应用的数量也呈现爆炸式的增长。安卓(Android)系统是其中使用量最多的移动操作系统,给人们带来了生活方式的改变。但是由于安卓系统本身的开源性和安卓应用的普遍性,不法分子将安卓应用作为目标,采取一系列手段来获取违法利益。在这些手段中,安卓应用重打包(Repackaging)已经成为最主要的方式之一。安卓重打包指的是解压安卓应用程序包并在可能的修改后重新打包并且发布到应用市场的过程。在重打包期间,可以对目标应用程序的反编译代码和/或其他资源文件进行各种修改,攻击者往往是出于非法目的进行这些修改。重打包可能会侵害用户和开发者的利益,乃至危害整个安卓市场和生态环境。因此,在应用市场上对重打包进行检测有着十分重要的意义。为了对重打包的应用进行检测,研究者提出了许多的方法。软件胎记(Software Birthmark)[1]技术是其中一种重要的技术。软件胎记技术通过静态或动态手段抽取软件所特有的、稳定的、具有标识作用的结构或行为特征,作为标识该软件的胎记,通过比较不同软件的胎记,可以检测软件克隆、盗版等现象。然而很多软件胎记容易受到应用混淆和加密的影响,导致抽取的软件胎记信息并不可靠。同时,移动应用结构混合化使得提取稳定统一的信息更为困难,进一步加大了重打包检测的困难。另外,诸多工作对重打包应用的识别计算效率不够高,不能很好地应用到实际应用市场中。考虑到重打包的应用为了利用原应用的流行性,通常会保持和原应用相似的观感,使得在应用界面布局、交互方式上,重打包应用和原应用有着较高的相似性。因此,本文认为从动态界面信息中提取软件胎记是一个可行的技术方案。本文提出了一个新的软件胎记模型——网格向量组图(GVGG),并以此建立重打包应用的检测框架,大大加速了软件胎记之间的相似度计算速度,实现了一个基于GVGG的重打包检测系统原型。总结而言,本文主要贡献如下:1.基于现有的抽象软件胎记模型,提出一个更准确高效的软件胎记模型。该模型优化了现有的软件胎记中的界面数据处理方法,提出了一种更高效的界面特征编码方式——网格向量编码,并以此建立软件胎记模型——网格向量组图。该网格向量编码可以处理目前大部分的应用混淆和加密的干扰,同时能够应对现有的异构应用的影响,有效处理原生的安卓应用以及大部分混合应用的界面。2.现有的软件胎记模型大多基于计算两个应用的软件胎记相似度的方法来检测是否为重打包应用。本文提出的基于网格向量组图的重打包检测框架,改进了JGrapht[2]的最大权二分图匹配算法,在保证准确度的情况下,极大地提高了相似度计算的速度。每一对应用相似度计算平均时间为59微秒,计算速度相比Rep Droid[3]和Region Droid[4]提高了100倍以上,更能满足现有大规模市场检测的效率,具有大规模市场运用的前景。3.基于本文提出的软件胎记模型,我们实现了原型工具系统,该系统集成了数据获取模块、数据存储模块、胎记图生成模块、胎记图比较模块、检测结果可视化模块,为应用市场管理人员提供了对应用的监督、管理功能。