论文部分内容阅读
【摘要】 由于Android平台的开放性和普及性，其上的应用开发日益增多。但由于有Android系统及开发工具是开源的，所有有些个人和企业利用反向工程工具对他人开发的应用进行破解修改，作为自己的产品进行发布销售。这种行为严重侵害了原作者的利益。应用商城的运营者为了保证自己运营的产品是正版产品，必须花费大量人力进行测试比对。而本文提出了通过提取Android程序包中函数调用关键字，并使用文本余弦相似度算法进行盗版应用自动检测的方法。并基于此方法对Android反盗版系统的基础构架进行了设计。
【关键词】 余弦相似度 Android应用 版权保护 反向工程
一、引言
Android操作系统是由谷歌公司推出的基于Linux开源的嵌入式操作系统，当前它主要运用于手机等移动设备上。从2008年推出第一款基于Android的手机以来，在短短的5年里，它已超过了原有的塞班系统占领了手机市场份额第一的位置。截止2013年9月全世界采用这款系统的设备数量已经达到10亿台[1]。
Android系统之所以能这样受到广大用户和开发者的青睐，主要原因在于其开放的系统和易于上手的应用开发平台，大大降低了第三方厂商进入Android应用开发的门槛。正是由于Android平台和应用开发技术相对透明，有些公司和个人为了其自身利益，剽窃他人应用，进行反向工程，替换小部分代码、图片文字，改头换面作为自己的产品推向市场。这种行为严重扰乱了Android应用市场，从长远来说将影响整个产业链的健康发展。尤其对于“手机应用商店”的运营方，应该担负起平台推广和销售的应用产品监督和管控的职能，避免侵权的应用在平台运营。当前，“手机应用商店”的运营方多是以书面版权文档审核，人工评测的方式进行版权及内容审查。这种方式费时费力，而且存在人员主观因素。因此，需要一种由计算机辅助的应用程序包自动版权检测工具。
二、Android應用盗版手段分析
要反Android应用盗版侵权，就要了解常用的应用盗版手段。作为Android应用盗版者最容易获得的是已编译好可执行的Android应用程序包。这个包里包括了已编译的执行代码、本地库文件、图片和字符串资源、相关应用的配置文件等。应用盗版者通过使用反向工程工具把APK包解开，转化为可直接编辑修改的资源文件、配置文件、smali代码和动态链接库文件[2]。最容易的应用盗版方法，就是直接修改图片和字符串资源，这样可以快速地完成对外观的修改，使其从用户界面上完全不同于原应用。还有一些技术较高的修改者会对配置文件和smali代码进行修改，改变应用执行的顺序，跳过一些公司信息、版本信息、联网激活等代码，并植入一些自己的代码，使得应用运行时的行为与原应用有较大差异。但不论何种手段，是对于一个应用盗版者，没有源代码，从成本考虑一般不能对程序运行逻辑进行大的调整，函数调用关系基本保持与原应用一致。如果对应用程序的片段引用，而程序的主体框架结构都是自创，则不应该归类为抄袭和盗版的一类。
通过对盗版者的修改行为分析，被盗版的Android 应用和新应用虽然在界面，图片，文字，甚至用户体验流程上可能有很大差异，但是盗版者从节约成本的经济利益角度考虑，不会对晦涩难懂的字节码程序作大的修改。这就为进行自动代码分析，提取代码特征进行比对，最终为确定Android应用相似度奠定了基础。
三、文本余弦相似度概念和运用
文本余弦相似度，是基于一段文字中各关键字的词频乘以它的权重而组成的向量来表示一个文本的特征，而每个文本都可以通过统计获取到它的特征向量，而两文本的相似度就是由它们特征向量在空间中的夹角余弦值来表示的。文本的余弦相似度在0到1间变化。如果0代表两特征向量成直角正交，两篇文本中没有任何相同的关键词，可以认为两篇文本没有抄袭的嫌疑。如果1代表特征向量重合，两篇文本具有完全相同的关键词，而且出现的频率完全相同，可以认为两篇文本有高度抄袭的嫌疑[3]。
要完整理解文本余弦相似度算法，必须先了解词频和逆向文件频率TF-IDF的概念。TF-IDF是一种用于资讯检索与文本挖掘的常用加权技术。词频TF表示词条t在文档d中出现的频率。逆向文件频率IDF表示词条t在文档库中的稀有程度[4]。IDF越大，则说明词条t具有很好的类别区分能力。
四、Android应用相似度比较算法设计
正如前文分析的，作为Android应用最难以修改的部分是程序逻辑。如何从程序包中提取出程序逻辑呢？一个常用的Android程序包反向工程工具Apktool是最好的选择。在运行带反编译参数的Apktool命令行后，会生成Davlik虚拟机语言（Android的Java虚拟机）表述的程序文件（smali目录）。它是类似于汇编语言的低级语言，只要做简单的汇编就能转化为虚拟机可执行字节码[5]。正是由于此种特性，也就决定了其语法和格式的严谨性，语义上无二义性，可以作为比较Android应用相似性的基础文本。
首先，提取出反编译后代码中所有函数调用行，并通过空格把语句分成独立的词。可以分解为操作符、参数、被调用的函数。而其中操作符和参数都是频繁出现在每个应用中，不能表示特定应用的特征，应该把其归入到终止统计的词中，避免干扰特征向量的有用关键词信息。这样就只有被调用的函数被纳入关键词TD-IDF向量，这个关键词包括函数的类名、函数名、参数类型列表、返回值类型，是函数的最基本特征，是最不容易被篡改的内容。这样就可以对于在一个应用中出现的所有被调用函数关键词进行词频统计。
得到词频TF后，还有一个关键参数IDF（逆向文件频率）。这需要对所有可以收集到的应用程序建立应用反编译库（必须要有足够数量，这对于专门进行应用商城运营的机构是相对容易的），提取出每个应用中被调用的函数。并以函数为查询索引，统计包含这个函数调用的应用个数。知道了应用反编译库的总应用个数和包含这个函数调用的应用个数，就能根据IDF公式计算出某个函数调用的IDF值。如果这个函数调用出现的应用越少，这个函数调就越能表现出当前应用与其他应用的区别，IDF值就越大，此函数调用在该应用中的特征向量的权重就越大。
有了一个应用中每个函数调用的TF和IDF，就能得到这个应用程序特征向量。每个应用都有这样一个特征向量，这样就可以把需要检测的应用的特征向量和应用库中的每个应用的特征向量进行组合计算余弦相似度。在得到相似度的值后，可以和设定相似度阀值比对，比如超过95%的就设为高度可疑。这样原本无方向大范围的人工比对过程，改进为人工对高度可疑的盗版应用的比对，提高了处理效率。对于每个被确定为正版应用的Android包，最后被添加到大的应用库中，为未来其他应用分析提供更精确地IDF和更丰富的特征向量。
五、Android应用反盗版系统设计
Android应用相似度比较的算法只是反盗版系统设计的核心，在系统实现时必须考虑到在成本和效率。因为为应用的数量是十分庞大的，而且每个应用中的函数少则数百，多则数千。在系统设计是要考虑如何低成本的存储这些数据非结构化的离散数据。显然关系型数据库对于这类数据存储是低效和高成本的。可以考虑针对大数据和文本处理设计的Nosql数据库，比如开源的HBASE，可以有效降低成本，平滑扩展。在运算能力上，由于应用库中每个应用都要和被检测应用进行相似度比较，而且运算涉及向量运算，运算量较大。考虑到缩短处理时间和提升用户感知，可以使用多服务器并行算法，例如Map-reduce算法，把计算任务平摊到多台廉价服务器上，避免采购高价的高性能、多CPU的小型机[6]。最终的相似度计算结果可以保存到关系数据库中，用户可以通过多种索引便捷查询，或以图形化报表展示。
六、结语
关于如何打击Android应用盗版是维护产业健康发展的关键问题。这个问题需要从法律、管理和技术多个层面共同解决。而作为应用商店运营者是有义务对其推广的应用进行必要的过滤和审核，避免盗版应用上线销售。在本文中使用了文本余弦相似度算法，通过对应用中的函数调用特征进行比较，发现高度相似的应用，为后续人工比对提供了方向和指导。这种方法简单易用，实现成本不高，能起到辅助判断作用。当然对于盗版者而言可能会有针对此方法故意加入一些无用的代码段，干扰计算结果。因此，此方法还可以进行改进，比如过滤掉不被调用的函数和代码段，再进行分析。总而言之，盗版和反盗版总是不断魔高一尺，道高一丈的过程。反盗版的方法需要针对盗版方式的变化不断提升演进。
【关键词】 余弦相似度 Android应用 版权保护 反向工程
一、引言
Android操作系统是由谷歌公司推出的基于Linux开源的嵌入式操作系统，当前它主要运用于手机等移动设备上。从2008年推出第一款基于Android的手机以来，在短短的5年里，它已超过了原有的塞班系统占领了手机市场份额第一的位置。截止2013年9月全世界采用这款系统的设备数量已经达到10亿台[1]。
Android系统之所以能这样受到广大用户和开发者的青睐，主要原因在于其开放的系统和易于上手的应用开发平台，大大降低了第三方厂商进入Android应用开发的门槛。正是由于Android平台和应用开发技术相对透明，有些公司和个人为了其自身利益，剽窃他人应用，进行反向工程，替换小部分代码、图片文字，改头换面作为自己的产品推向市场。这种行为严重扰乱了Android应用市场，从长远来说将影响整个产业链的健康发展。尤其对于“手机应用商店”的运营方，应该担负起平台推广和销售的应用产品监督和管控的职能，避免侵权的应用在平台运营。当前，“手机应用商店”的运营方多是以书面版权文档审核，人工评测的方式进行版权及内容审查。这种方式费时费力，而且存在人员主观因素。因此，需要一种由计算机辅助的应用程序包自动版权检测工具。
二、Android應用盗版手段分析
要反Android应用盗版侵权，就要了解常用的应用盗版手段。作为Android应用盗版者最容易获得的是已编译好可执行的Android应用程序包。这个包里包括了已编译的执行代码、本地库文件、图片和字符串资源、相关应用的配置文件等。应用盗版者通过使用反向工程工具把APK包解开，转化为可直接编辑修改的资源文件、配置文件、smali代码和动态链接库文件[2]。最容易的应用盗版方法，就是直接修改图片和字符串资源，这样可以快速地完成对外观的修改，使其从用户界面上完全不同于原应用。还有一些技术较高的修改者会对配置文件和smali代码进行修改，改变应用执行的顺序，跳过一些公司信息、版本信息、联网激活等代码，并植入一些自己的代码，使得应用运行时的行为与原应用有较大差异。但不论何种手段，是对于一个应用盗版者，没有源代码，从成本考虑一般不能对程序运行逻辑进行大的调整，函数调用关系基本保持与原应用一致。如果对应用程序的片段引用，而程序的主体框架结构都是自创，则不应该归类为抄袭和盗版的一类。
通过对盗版者的修改行为分析，被盗版的Android 应用和新应用虽然在界面，图片，文字，甚至用户体验流程上可能有很大差异，但是盗版者从节约成本的经济利益角度考虑，不会对晦涩难懂的字节码程序作大的修改。这就为进行自动代码分析，提取代码特征进行比对，最终为确定Android应用相似度奠定了基础。
三、文本余弦相似度概念和运用
文本余弦相似度，是基于一段文字中各关键字的词频乘以它的权重而组成的向量来表示一个文本的特征，而每个文本都可以通过统计获取到它的特征向量，而两文本的相似度就是由它们特征向量在空间中的夹角余弦值来表示的。文本的余弦相似度在0到1间变化。如果0代表两特征向量成直角正交，两篇文本中没有任何相同的关键词，可以认为两篇文本没有抄袭的嫌疑。如果1代表特征向量重合，两篇文本具有完全相同的关键词，而且出现的频率完全相同，可以认为两篇文本有高度抄袭的嫌疑[3]。
要完整理解文本余弦相似度算法，必须先了解词频和逆向文件频率TF-IDF的概念。TF-IDF是一种用于资讯检索与文本挖掘的常用加权技术。词频TF表示词条t在文档d中出现的频率。逆向文件频率IDF表示词条t在文档库中的稀有程度[4]。IDF越大，则说明词条t具有很好的类别区分能力。
四、Android应用相似度比较算法设计
正如前文分析的，作为Android应用最难以修改的部分是程序逻辑。如何从程序包中提取出程序逻辑呢？一个常用的Android程序包反向工程工具Apktool是最好的选择。在运行带反编译参数的Apktool命令行后，会生成Davlik虚拟机语言（Android的Java虚拟机）表述的程序文件（smali目录）。它是类似于汇编语言的低级语言，只要做简单的汇编就能转化为虚拟机可执行字节码[5]。正是由于此种特性，也就决定了其语法和格式的严谨性，语义上无二义性，可以作为比较Android应用相似性的基础文本。
首先，提取出反编译后代码中所有函数调用行，并通过空格把语句分成独立的词。可以分解为操作符、参数、被调用的函数。而其中操作符和参数都是频繁出现在每个应用中，不能表示特定应用的特征，应该把其归入到终止统计的词中，避免干扰特征向量的有用关键词信息。这样就只有被调用的函数被纳入关键词TD-IDF向量，这个关键词包括函数的类名、函数名、参数类型列表、返回值类型，是函数的最基本特征，是最不容易被篡改的内容。这样就可以对于在一个应用中出现的所有被调用函数关键词进行词频统计。
得到词频TF后，还有一个关键参数IDF（逆向文件频率）。这需要对所有可以收集到的应用程序建立应用反编译库（必须要有足够数量，这对于专门进行应用商城运营的机构是相对容易的），提取出每个应用中被调用的函数。并以函数为查询索引，统计包含这个函数调用的应用个数。知道了应用反编译库的总应用个数和包含这个函数调用的应用个数，就能根据IDF公式计算出某个函数调用的IDF值。如果这个函数调用出现的应用越少，这个函数调就越能表现出当前应用与其他应用的区别，IDF值就越大，此函数调用在该应用中的特征向量的权重就越大。
有了一个应用中每个函数调用的TF和IDF，就能得到这个应用程序特征向量。每个应用都有这样一个特征向量，这样就可以把需要检测的应用的特征向量和应用库中的每个应用的特征向量进行组合计算余弦相似度。在得到相似度的值后，可以和设定相似度阀值比对，比如超过95%的就设为高度可疑。这样原本无方向大范围的人工比对过程，改进为人工对高度可疑的盗版应用的比对，提高了处理效率。对于每个被确定为正版应用的Android包，最后被添加到大的应用库中，为未来其他应用分析提供更精确地IDF和更丰富的特征向量。
五、Android应用反盗版系统设计
Android应用相似度比较的算法只是反盗版系统设计的核心，在系统实现时必须考虑到在成本和效率。因为为应用的数量是十分庞大的，而且每个应用中的函数少则数百，多则数千。在系统设计是要考虑如何低成本的存储这些数据非结构化的离散数据。显然关系型数据库对于这类数据存储是低效和高成本的。可以考虑针对大数据和文本处理设计的Nosql数据库，比如开源的HBASE，可以有效降低成本，平滑扩展。在运算能力上，由于应用库中每个应用都要和被检测应用进行相似度比较，而且运算涉及向量运算，运算量较大。考虑到缩短处理时间和提升用户感知，可以使用多服务器并行算法，例如Map-reduce算法，把计算任务平摊到多台廉价服务器上，避免采购高价的高性能、多CPU的小型机[6]。最终的相似度计算结果可以保存到关系数据库中，用户可以通过多种索引便捷查询，或以图形化报表展示。
六、结语
关于如何打击Android应用盗版是维护产业健康发展的关键问题。这个问题需要从法律、管理和技术多个层面共同解决。而作为应用商店运营者是有义务对其推广的应用进行必要的过滤和审核，避免盗版应用上线销售。在本文中使用了文本余弦相似度算法，通过对应用中的函数调用特征进行比较，发现高度相似的应用，为后续人工比对提供了方向和指导。这种方法简单易用，实现成本不高，能起到辅助判断作用。当然对于盗版者而言可能会有针对此方法故意加入一些无用的代码段，干扰计算结果。因此，此方法还可以进行改进，比如过滤掉不被调用的函数和代码段，再进行分析。总而言之，盗版和反盗版总是不断魔高一尺，道高一丈的过程。反盗版的方法需要针对盗版方式的变化不断提升演进。