您的位置：首页 > 党团工作党团工作
毕业论文-基于程序切片安卓软件安全分析
2025-08-31人已围观
毕业论文-基于程序切片安卓软件安全分析
南京邮电大学 毕 业 设 计（论 文）
题
目 基于程序切片的安卓软件安全分析 专
业 软件工程 学生姓名
班级学号
指导教师
指导单位 计算机学院、软件学院
日期：
2014 年 3 月 10 日
至
2014 年 6 月 13 日
毕业设计（论文）原创性声明
本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。
论文作者签名：
日期：
年
月
日
摘
要
Android 系统是现在市场上占有率最大的手机系统，其开源的性质，让系统更加脆弱，所以更多的恶意软件针对 Android 系统，使得检测 Android 软件的安全性成为了十分重要的问题。在智能手机成为生活中的重要一部分的同时，每个人的隐私在手机上有着十分重要的地位。
JAVA 切片作为一个成熟的分析安全算法，对安卓程序有十分大的借鉴意义，因此本文提供的安卓安全分析算法研究具有相当的理论价值。
本文的目的在于研究基于程序切片的安卓软件安全分析，在成熟程序切片算法的基础上得到对安卓软件的安全性检查的算法和解决方案。
本文首先对基于 WALA 平台的切片算法进行研究，熟悉 JAVA 切片的算法,并基于 JAVA SWT 展示 WALA 平台的切片算法。之后对安卓软件的结构进行分析，了解安卓软件的安全漏洞，并分析这些漏洞。最终对基于 WALA 的安全分析软件SCanDroid 软件进行研究，得到安卓安全分析的算法和方法，使用数据可视化软件，对测试结果进行分析和统计，以直观的图形呈现，为成熟的 Android 软件检测方法提供了解决方案。
关键词：Android；安全分析；切片；WALA；数据可视化；
ABSTRACT Android system is now on the market share of the largest mobile phone system , its open source nature , make the system more fragile, so more malware for the Android system , which makes safety testing Android software has become a very important issue. The purpose of this paper is to study the safety analysis based on Android software program slice. Android software algorithms can be security checks and solutions based on a mature program slicing algorithm . Firstly, the slicing algorithm based research platform WALA familiar with JAVA slice algorithm and demonstrate slicing algorithm WALA platform based JAVA SWT. After the software to analyze the structure of Andrews , Andrews understand software security vulnerabilities , analysis of these vulnerabilities. WALA final safety analysis based software SCanDroid software research, algorithms and methods to get Android security analysis , and the results were analyzed using data visualization software to analyze the test results and statistics , finishing as intuitive graphic for reference, provides solutions for sophisticated Android software detection methods. In smart phones become an important part of life at the same time , everyone"s privacy on the phone has a very important position , as Android phones on the market share of the largest mobile phone systems, software security is very important , JAVA slice as a mature the analysis of security algorithm, the program has a very large Andrews reference , so Andrews security analysis algorithm provided herein have considerable theoretical value .
Keywords
：Android; Safety Analysis ; Slicer ; WALA; Data Visualization
目
录
第一章
绪论 .............................................. 1
1.1 课题背景和研究意义 ....................................................................................... 1
1.2 研究现状 ........................................................................................................... 2
1.3 本文工作 ........................................................................................................... 2
1.4 结构安排 ........................................................................................................... 3
第二章 程序切片的原理和算法 ............................... 4
2.1
程序切片简介 ................................................................................................. 4
2.1.1
程序切片准则 ...................................................................................... 4
2.1.2
程序切片分类 ...................................................................................... 5
2.2 程序切片的算法 ............................................................................................... 7
2.2.1 基于数据流方程的算法 ........................................................................ 8
2.2.2 基于依赖图(DG)的图形可达性算法 .................................................... 9
2.3 安卓系统简介 ................................................................................................. 10
2.4 本章小结 ......................................................................................................... 13
第三章 WALA 框架分析与测试 ................................ 14
3.1 WALA 平台简介 .............................................................................................. 14
3.2 WALA 框架的分析 .......................................................................................... 14
3.2.1 WALA 平台的下载及编译 ................................................................... 14
3.2.2 WALA 框架的表示分析 ....................................................................... 15
3.2.2 WALA 切片的功能分析 ....................................................................... 16
3.2.3 WALA 切片测试用例 ........................................................................... 18
3.3 WALA 测试用例结果分析 .............................................................................. 23
3.3.1 分析工具 .............................................................................................. 23
3.3.2 结果分析 .............................................................................................. 25
3.4 本章小结 ......................................................................................................... 30
第四章 安卓应用安全分析 .................................. 31
4.1 安卓系统安全机制解析 ................................................................................. 31
4.2 安卓恶意软件方式分析 ................................................................................. 32
4.3 SCanDroid 程序分析 ....................................................................................... 33
4.3.1 SCanDroid 程序原理 ............................................................................ 33
4.3.2 SCanDroid 程序测试 ............................................................................ 34
4.3.3 SCanDroid 结果分析 ............................................................................ 34
4.4 本章小结 ......................................................................................................... 36
结束语 ................................................... 37
致
谢 ................................................... 38
参考文献 ................................................. 39
南京邮电大学 2014 届本科生毕业设计（论文）
1
第一章
绪论 1.1 课题背景和研究意义 如今社会手机已经成为了人们生活中必不可少的一部分，显然智能手机占据了手机市场的绝大部分。据统计，2013 年全球手机市场销量增速持续放缓，但智能手机销量依旧一路狂奔，保持快速增长的势头。全球市场研究公司 Gartner 数据显示，如下图 1.1，2013 年第二季度全球智能手机销量首次超越了功能手机。同时Gartner 预测，2013 年全球智能手机销量将接近 10 亿部，占整个手机市场销量的比例将超过 50%。
图 1.1
手机销量走势
2013 Q2 促使全球智能手机销量首次超越功能手机的最大功臣非谷歌 Android系统莫属。Gartner 数据显示，2013 年 Q2Android 系统全球市场占有率为 79%，总销量为1.77亿部，2012年同期则仅为8000万部，市场份额不足60%。2013Q1Android系统市场份额为 74.4%，Q3 则达到了 81.9%，超过八成。
综上所述，我们可以看出，Android 系统现在已经日益影响大部分人的生活。在这个信息化时代，关注安卓软件安全问题刻不容缓。
根据芬兰计算机及网络安全提供商 F-Secure 提供的 2013 年手机平台恶意软件检测报告，2013 年 Android 平台滋生的恶意软件占所有手机恶意软件的 97％，而2012 年这一比例为 79％。虽然 Android 官方市场 Google Play 能够及时清除恶意应用程序，成为安全威胁比例最低的应用商店，其安全威胁比例仅为 0.1％。但是，
南京邮电大学 2014 届本科生毕业设计（论文）
2
由于 Android 系统的开放性，不少用户不会使用官方市场，这就给恶意软件有了可乘之机。
图 1.2
恶意软件占有率
目前现有的安卓安全管理软件，如国内的金山、QQ 手机管家、360 手机管家等等，都只能起到表面的监测作用，不能对源代码结构进行分析。所以，本课题致力于从程序切片方面着手，从 Android 软件的源代码入手，了解恶意软件的具体危害，将软件在安装前检测出问题。
1.2 研究 现状
目前的切片方法主要针对 Java 或者 C 语言的代码分析，用于安全检测，软件测试等方面，这些都有比较成熟的算法和理论，而在安卓系统上，只能在软件运行时检测出软件的危险性，并没有在在软件源代码上得到过切片的成熟理论和算法。
1.3 本文 工作 本文按照既定的计划进行研究和实践。首先了解了切片的概念和安卓软件恶意检测的常用手段，对常用的切片方式进行了分析，找到适合安卓分析的切片方法。之后对 JAVA 切片的算法进行了分析和了解，尝试常用的切片程序，然后对WALA 框架分析，了解了 WALA 框架在切片上实现的方式，使用 WALA 框架为基础将它的切片过程以客户端的形式表现出来。最终在以 WALA 框架为基础的SCanDroid 程序上实现对安卓软件的安全监测功能，并对程序进行性质判定。
南京邮电大学 2014 届本科生毕业设计（论文）
3
本文的创新之处在于：
1) 研究了针对安卓安全的切片程序实现方法，将传统的 JAVA 切片迁移到安卓程序切片，扩展了切片的使用范围。
2) 利用了开源的 WALA 框架并在其基础上进行了改进，对开源代码做出了贡献。
3) 将 SCanDroid 这一基于 WALA 框架的程序应用到实践中去，对该程序能够广泛使用提供了帮助。
1.4 结构 安排 本文对首先对当前的程序切片进行了研究，继而对 WALA 框架进行了切片研究，之后针对 SCanDroid 程序进行了安卓切片的研究，并对程序进行了测试，最后得出安卓切片的方向和解决方案。
南京邮电大学 2014 届本科生毕业设计（论文）
4
第二章 程序 切片 的原理和算法 程序切片是本课题的核心。在本章中，首先介绍程序切片的原理和分类，之后给出程序切片的算法节以及对其性能和可用性的测试。
2.1
程序 切片简介 程序切片是一种分析和理解程序的技术，通过分析程序语句之间的依赖性关系，自动分解源程序，程序切片技术在程序调试、回归测试、程序分析和理解、软件维护以及反向工程等领域都有广泛的应用。
程序切片首先是由 Weiser 在他的博士论文中提出来的，后来他又在 1981 年国际软件工程大会(ICSE"81)以及 1984 年 IEEE Transactions 上相继发表文章进一步阐述了程序切片的思想和实现算法。Weiser 描述的程序切片定义如下：：
定义 2.1：非形式化地，满足以下两个条件的程序称为切片：
(1) 一个切片对应一个特定的切片准则<V, i>，其中 v 表示变量的集合，i 指程序中的某个点(一般指某条语句)； (2) 程序 P 对应切片准则<V, i>的切片 S 可通过从 P 中删除一条或者多条和切片准则不相关的语句得到，并且要保证程序 P 和切片 S 关于切片准则(V, i)的行为相同。
随着切片技术的发展，S.Horwitz 等人给出了一个更精确的程序切片定义。
定义 2.2：一个程序切片是由程序中的一些语句和判定表达式组成的集合。这些语句和表达式可能会影响在程序中的某个位置(常用行号标识)P 上所定义的或所使用的变量 v 的值。<P, v>称为切片准则。
2.1.1
程序 切片 准则 计算程序切片必须考虑切片准则。对同样的程序计算切片时，如果切片准则发生变化，则计算得到的程序切片也会不同。因而程序切片准则是程序切片技术的重要环节。目前存在主要切片准则有：
静态后向切片准则：构造一个程序 P 的静态后向切片时，考虑的切片准则是一个二元组(V,p)，其中 V 是一组变量，p 是程序中的一个兴趣点，程序 p 的一个切片时任何一个在 V 中 p 点对变量具有与 P 相同影响的程序。
动态后向切片准则：构造一个程序 P 的动态后向切片构造时，考虑的切片准则是一个三元组(V,p,x)，其中 V 是变量的集合，p 是程序 P 中的一个兴趣点，x 是一个输入序列。当用 x 输入时，一个动态切片保留 P 的与 p 点的变量集合 V 有关的投影含义。
传统的前向切片准则：构造一个程序 P 的传统的前向切片时，考虑的切片准则是(V,p)，这里 V 是变量的集合，p 是程序 P 中一个兴趣点。程序切片是一个语句和谓词组成的集合，这些语句和谓词受到 P 中 V 的变量在 p 的值对它的影响。
南京邮电大学 2014 届本科生毕业设计（论文）
5
分解切片准则：程序 P 的关于一个变量 V 的分解切片的构造，是关于切片准则 ({v},end) 静 态 后 向 切 片 和 {({v},n1), … … ， ({v},nm)} 的 并 组 成 ， 其 中{n1,n2,……,nm}是行的集合(v 在 P 中是输出，end 是程序的结尾语句)。
多点切片准则：构造程序 P 的多点切片需要考虑二元组(V,N)，其中 N 是程序P 中点的集合，V 是变量的集合。当在 N 中任何一点执行一条语句时，对 V 中所有变量，切片和程序 P 具有同样的效果。
广义切片准则：广义切片是传统切片的扩展，其中变量被随机的有名程序实体代替，语句被随机的程序构造代替。
迭代切片准则：构造一个程序 P 的迭代切片时，考虑的切片准则是(V,p,n)，这里 V 是变量的集合，p 是程序 P 中一个兴趣点，n 是自然数。程序 P 的第 n 次（静态）迭代切片 S 是由第 n 次执行到达 p 时那些保持程序 P 的投影含义不变的语句组成。当 n 换成 N（自然数集）时就编程广义迭代切片准则。
条件切片准则：构造一个程序 P 的条件切片时，考虑的切片准则是一个四元组(l,p,π,V),这里 l 是变量名的集合，这些变量的值是从输入序列中获得的，p 是程序 P 中一个兴趣点，π 是一个谓词，它的自由变量是 l 的一个子集，V 是一个变量名的集合。构造一个程序 P 的条件切片 S，当在一个满足 π 的初始状态执行时，条件切片 S 必须保持程序 P（与 V 有关）的投影含义。
2.1.2
程序 切片 分类 程序切片主要分为以下几类：
1. 后向切片和前向切片 后向切片指包含影响变量的所有语句和断言；前向切片指包含受该变量影响的所有语句和断言。如图 2.1 所示。
图 2.1
语句 y：=x+4 的后向和前向切片计算结果
2. 静态切片和动态切片 MODULE BackwardSlicing VAR
x,y,z：INTEGER BEGIN
x：=3；
y：=x+4；
z：=y+3； END BackwardSlicing MODULE ForwardSlicing VAR
x,y,z：INTEGER BEGIN
x：=3；
y：=x+4；
z：=y+3； END ForwardSlicing
南京邮电大学 2014 届本科生毕业设计（论文）
6
静态切片：利用静态分析产生切片，也就是分析程序的源代码，计算所有可能输入值情况下的切片。动态切片：是在某个特定输入下的程序切片，它把在特定输入时实际影响某个程序点变量值的所有语句包含到切片中。如图 2.2 所示。
图 2.2（a）
图 2.2（b）
图 2.2 在最后一个语句计算的静态切片（a），当输入 op=“sin”时计算的动态切片（b ）
3. 过程内切片和过程间切片 过程内切片：主要在一个过程之内计算切片；过程间切片：如果一个程序由多个过程组成，则需要利用过程间切片来计算程序切片。过程间切片引起一个新的问题：当一个过程在不同的地方被调用时，必须考虑调用的上下文，以便在编译时能够正确模型化运行时执行情况。过程间数据流分析有一个类似的目标就是只考虑对应于合法 call/return 序列的路径。如图 2.3. MODULE DynamicSlicing IMPORT Math,In,Out VAR x,y：Real； op：
APPLY 10 OF CHAR； BEGIN In.Open； In.String(op)；In.Real(x)； IF op=sin THEN
y：=Math.Sin(x) ELSE ：
。MODULE StaticSlicing IMPORT Math,In,Out VAR x,y：Real； op：
APPLY 10 OF CHAR； BEGIN In.Open； In.String(op)；In。Real(x)； IF op=sin THEN
y：=Math。Sin(x) ELSE
y：=Math.Cos(x)
南京邮电大学 2014 届本科生毕业设计（论文）
7
图 2.3
考虑调用的上下文时过程 Increment 的输出参数 z 的切片
2.2 程序切片 的算法 程序切片的算法主要有 Weiser 的基于数据流方程的算法、无定型切片算法、Bergeretti 的基于信息流关系的算法、K.J. Ottenstein 和 L.M. Ottenstein 以及 Horwitz的基于程序依赖图的图形可达性算法、杨洪的基于波动图的算法。另外，还有参数化程序切片算法、并行切片算法以及面向对象的分层切片算法等。这里重点介绍基于数据流方程的算法和基于依赖图的算法。
MODULE CallingContext
PROCEDURE Add(VAR a ：INTEGER；b INTEGER)； BEGIN a：=a+b END Add；
PROCEDURE Increment(VAR z：INTEGER)； BEGIN Add(z,1) END Increment；
PROCEDURE A(VAR x,y：INTEGER) BEGIN
Add(x,y)；
Increment(y) END A；
PROCEDURE Main；
VAR sum,i：INTEGER； BEGIN
sum：=0； i：=1；
WHERE i<：100
A(sum,i) END END Main； END CallingContex
南京邮电大学 2014 届本科生毕业设计（论文）
8
2.2.1 基于数据流方程的 算法 Weiser 是根据数据流方程的迭代解最早定义程序切片的。他定义的程序切片是通过对初始程序删除零条或多条语句而获得的一个可执行的程序。切片准则由一个二元组（n，V）构成，其中 n 是程序的 CFG 中一个结点，V 是程序中变量的一个子集。关于切片准则（n，V）的程序切片是程序 P 的语句的一个子集 S，它必须满足下列特性：
① S 必须是一个有效程序；
② 对一个给定的输入，P 发生中断时，S 也会发生中断。无论何时与结点 n相关的语句被执行时，计算 V 中所有变量的值（对 P 和 V 来说）分别是相同的。
公理 1：
对应任何一个切片准则，至少存在一个切片，即程序本身。
如果对同一个切片准则来说，没有其他的切片比某个切片 Sminimal 包含更少的语句，则称 Sminimal 为最少语句的切片。Weiser 认为最少语句切片不一定是唯一的，且如何确定最少语句切片问题是不可判定的。
Weiser 描述了一个用来计算最少语句切片近似值的迭代算法。这种算法使用两种不同的迭代层次，即: ① 跟踪可传递的数据依赖层。这要求迭代过程是在循环存在情况下发生的；
②跟踪控制依赖层。该层把跟踪到的新的控制谓词控制的语句包含到某个控制谓词的切片中。对每个这样的谓词，到把它依赖的所有语句包含进来为止。这类算法确定相关变量的连贯集合，由此可得到相关语句的集合。
Weiser 迭代算法的第 1 层要确定直接相关变量：这是上面论述的迭代过程步骤 1 的一个实例。CFG 中结点 i 的直接相关变量的集合记为 R0C(i)。迭代开始于初始值 R0C(n)=V，且对任何结点 m≠n，满足 R0C(m=。图 1 中定义的一组方程可确定在 CFG 的边 i→CFG j 的终点 j 的相关变量的集合是如何影响在开始点 i 的相关变量的集合。这个过程的最小不动点就是在结点 i 的直接相关变量的集合。从R0C 可得到直接相关语句集合 S0C。图 1 表示了 S0C 是如何被定义为所有结点 i的集合，i 定义了变量 v，该变量在 i 的一个 CFG 后继是相关的。
Weiser 迭代算法的第 2 层要考虑控制依赖。如果在一个 if 或 while 语句控制谓词的控制体中至少有一条语句是相关的，则变量引用是间接相关的。为了实现这个目标，一条分支语句 b 的影响范围 Infl(b)定义为由所有控制依赖 b 的语句组成的集合。图 2 表示分支语句的一个定义 BkC。由于它们对 SkC 中结点 i 的影响，因而是间接相关的。间接相关变量的 Rk+1C(i)得到确定。除 RkC(i)中的变量之外，Rk+1C(i)包含的变量是相关的，因为它们对 BkC 中的语句存在可传递的数据依赖。这通过再一次执行第 1 层迭代来确定（也就是跟踪可传递的数据流），同时考虑的一组准则是（b，Ref(b)），这里 b 是 BkC 中的一条分支语句。图 2 还定义了在 k+1次迭代过程中间接相关语句（indirectly relevant statements）的集合 Sk+1C。这个集
南京邮电大学 2014 届本科生毕业设计（论文）
9
合由 BkC 中的结点 i 一起构成，结点 i 定义了一个变量，该变量对 CFG 的后继 j来说是 Rk+1C 相关的。由此可得下面的定义。
定义 2.3：程序切片是由程序中某个兴趣点的相关语句集合的不动点构成的集合。计算程序切片就是计算相关语句集合的不动点。
集合 Rk+1C 和 Sk+1C 分别是程序的变量和语句的非递减子集；计算得到的集合 Sk+1C 的不动点就构成期望的程序切片。
Lyle 虽然提供了 Weiser 切片算法一种修改版，但除了在术语方面的细小改变外，与 Weiser 算法本质上没有什么两样。
Hausler 用函数的风格重述了 Weiser 的算法。对每种类型的语句（空语句、赋值语句、语句组合、if 和 while），他定义了两个函数 δ 和 α。粗略地说，这些函数分别表示一条语句是如何转换相关变量的集合 RiC，以及相关语句的集合 SiC。函数 δ 和 α 是以一种组合的方式定义的。对空语句和赋值语句，δ 和 α 可以按语法制导的方式从语句中产生出来。语句序列和 if 语句的 δ 和 α 函数可以分别从它们构件的 δ 和 α 函数推导出来。通过把它有效地转换成一个 if 语句的无穷序列来获得while 语句的函数。
2.2.2 基于依赖图(DG) 的图形可达性算法 Ottenstein等在1984年提出了切片准则由一个程序点p和一个在p定义的或使用的变量 v 构成，且在一个程序依赖图(PDG)上使用图形可达性算法来计算切片。根据他们对切片含义的理解，切片是由程序中所有可能影响 v 在 p 点值的语句和谓词构成。1990 年，Horwitz 等使用依赖图来计算切片，他们开发了一种过程间的程序表示——系统依赖图(SDG)，并实现了一个基于系统依赖图的两阶段图形可达性切片算法。由于使用调用位置的可传递的依赖流信息中包含被调用过程的上下文环境，所以该算法的计算精度比以前的算法更高。后来，为了切片面向对象的程序又出现了多种依赖图，具有代表性的有：Zhao 提出的一种动态面向对象的依赖图(DODG)和系统依赖图网（SDN），分别用于解决面向对象程序的动态切片问题和并发面向对象的程序切片问题；Krishnaswamy 提出一种面向对象的程序依赖图(OPDG)，并在 OPDG 上实现了计算语句切片的算法。OPDG 是通过对传统的程序依赖图进行面向对象的扩充获得的，但 OPDG 不能表示虚继承、动态对象等问题，因而 OPDG 是不完全的面向对象程序表示。下面简单分析一下各种依赖图在切片算法中应用及其特点。
1) 程序依赖图(PDG)
PDG 是程序的一种图形表示，它把控制依赖和数据依赖包含在单个的结构中。如果给定程序中的语句 X 和 Y，则 X 和 Y 可以通过控制流或者数据流来彼此关联。如果从 Y 至少可以引出两条路径，其中一条总会导致 X 的执行，而另一条可能导致 X 不执行，则称语句 X 控制依赖于语句 Y；如果有一条从 Y 到 X 的路径，且存
南京邮电大学 2014 届本科生毕业设计（论文）
10
在一个在 Y 点定义在 X 点使用的变量，且该变量在沿从 Y 到 X 的路径上其它任何地方没有被重新定义，则称语句 X 数据依赖于语句 Y。PDG 的形式定义是由一个控制依赖子图(CDG)，一个控制流图(CFG)和一个数据依赖子图(DDG)组成。其中CDG 包含了程序中的控制依赖； CFG 描述了一个程序中的控制流，它类似于正常情况下的流图；DDG 是一个程序中语句之间所有数据依赖的集合。CDG 包含语句结点、域结点和谓词结点等类型的结点。语句结点表示程序中的语句；域结点概括了域中语句间的控制依赖；谓词结点（由此可以引出两条边）表示程序中的策略或分支条件。CDG 中的域结点可利用相同的控制依赖来集合语句。DDG 包含语句间的数据依赖，可通过在 CDG 的结点之间插入数据依赖边来构造 DDG。PDG不允许过程间分析，它也没有能力表示继承、多态性和动态定连等重要的面向对象的特性。
2) 系统依赖图（SDG）
SDG 是程序的一种语法分析树表示。结点表示程序构造，输入输出参数和调用位置等，边表示与之相连的结点之间的各种依赖(例如数据依赖、控制依赖和声明等)。程序依赖图通常是为单个的过程间程序来定义的。由于现实世界的程序一般是由多个过程组成的，所以必须考虑使用一种与现实世界程序匹配的表示方法，于是 Horwitz 等人提出了系统依赖图。SDG 是一棵经过装饰的表示程序的语法分析树。形式地说，SDG 是由一个程序依赖图和一组过程依赖图（PrDG）构成的有向、带标记的多重图。PDG 模型化软件系统中的主程序，PrDG 模型化软件系统中的多个过程体。SDG 可以用来处理过程间的数据流和控制流，并能表示参数传递。SDG 允许过程间分析，但面向对象程序远不是一些过程或方法的简单组合，所以SDG 提供的机制还不足以描述这些面向对象的概念。
2.3 安卓 系统简介 Android 是一种基于 Linux 的自由及开放源代码的操作系统，主要使用于移动设备，如智能手机和平板电脑，由 Google 公司和开放手机联盟领导及开发。尚未有统一中文名称，中国大陆地区较多人使用“安卓”或“安致”。Android 操作系统最初由 Andy Rubin 开发，主要支持手机。2005 年 8 月由 Google 收购注资。2007 年11 月，Google 与 84 家硬件制造商、软件开发商及电信营运商组建开放手机联盟共同研发改良 Android 系统。随后 Google 以 Apache 开源许可证的授权方式，发布了Android 的源代码。第一部 Android 智能手机发布于 2008 年 10 月。
Android 分为四个层，从高层到低层分别是应用程序层、应用程序框架层、系统运行库层和 Linux 内核层。
操作系统：
Android 使用 Linux2。6 作为操作系统，Linux2。6 是一种标准的技术，Linux 也是一个开放的操作系统。Android 对操作系统的使用包括核心和驱动程序两部
南京邮电大学 2014 届本科生毕业设计（论文）
11
分，Android 的 Linux 核心为标准的 Linux2。6 内核，Android 更多的是需要一些与移动设备相关的驱动程序。
显示驱动（Display Driver）：常用基于 Linux 的帧缓冲（Frame Buffer）驱动,Flash 内存驱动（Flash Memory Driver）,照相机驱动（Camera Driver）：常用基于 Linux 的 v4l（Video for ）驱动。音频驱动（Audio Driver）：常用基于 ALSA（Advanced Linux Sound Architecture，高级 Linux 声音体系）驱动，WiFi 驱动（Camera Driver）：基于 IEEE 802.11 标准的驱动程序，键盘驱动（KeyBoard Driver），蓝牙驱动（Bluetooth Driver）,Binder IPC 驱动：Android 一个特殊的驱动程序，具有单独的设备节点，提供进程间通讯的功能,Power Management（能源管理）。
应用程序框架：
Android 的应用程序框架为应用程序层的开发者提供 APIs，它实际上是一个应用程序的框架。由于上层的应用程序是以 JAVA 构建的，因此本层次提供的首先包含了 UI 程序中所需要的各种控件：
例如：
Views ( 视图组件 ) 包括 lists( 列表 ), grids( 栅格 ), text boxes( 文本框 ), buttons( 按钮 ) 等，甚至一个嵌入式的 Web 浏览器。一个 Android 的应用程序可以利用应用程序框架中的以下几个部分：
Activity （活动）、Broadcast Intent Receiver （广播意图接收者）、Service （服务）、Content Provider （内容提供者）。
应用程序：
Android 的应用程序主要是用户界面（User Interface），通常以 JAVA 程序编写，其中还可以包含各种资源文件（放置在 res 目录中）。JAVA 程序及相关资源经过编译后，将生成一个 APK 包。Android 本身提供了主屏幕（Home），联系人（Contact），电话（Phone），浏览器（Browsers）等众多的核心应用。同时应用程序的开发者还可以使用应用程序框架层的 API 实现自己的程序。
南京邮电大学 2014 届本科生毕业设计（论文）
12
图 2.4
Android 的层次分析
系统运行库：
Android 包含一些 C/C++库，这些库能被 Android 系统中不同的组件使用。它们通过 Android 应用程序框架为开发者提供服务。以下是一些核心库：
* 系统 C 库 - 一个从 BSD 继承来的标准 C 系统函数库 Libc )， 它是专门为基于 Embedded Linux 的设备定制的。
* 媒体库 - 基于 PacketVideo OpenCORE；该库支持多种常用的音频、视频格式回放和录制，同时支持静态图像文件。编码格式包括 MPEG4, H。264, MP3, AAC, AMR, JPG, PNG 。
* Surface Manager - 对显示子系统的管理，并且为多个应用程序提 供了 2D和 3D 图层的无缝融合。
* LibWebCore - 一个最新的 web 浏览器引擎用，支持 Android 浏览器和一个可嵌入的 web 视图。
Android 中，Activity 是所有程序的根本，所有程序的流程都运行在 Activity 之中，Activity 可以算是开发者遇到的最频繁，也是 Android 当中最基本的模块之一。Service 是 Android 系统中的一种组件，它跟 Activity 的级别差不多，但是他不能自己运行，只能后台运行，并且可以和其他组件进行交互。Service 是没有界面的长生命周期的代码。Service 是一种程序，它可以运行很长时间，但是它却没有用户界面。在 Android 中，Broadcast 是一种广泛运用的在应用程序之间传输信息的机制。而 BroadcastReceiver 是对发送出来的 Broadcast 进行过滤接受并响应的一类组件。可以使用 BroadcastReceiver 来让应用对一个外部的事件做出响应。Content Provider 是 Android 提供的第三方应用数据的访问方案。
Android 通常与一系列核心应用程序包一起发布，该应用程序包包括客户端、SMS 短消息程序、日历、地图、浏览器、联系人管理程序等。所有的应用程序都是使用 JAVA 语言编写的。
开发人员也可以完全访问核心应用程序所使用的 API 框架。该应用程序的架构设计简化了组件的重用；任何一个应用程序都可以发布它的功能块并且任何其它的应用程序都可以使用其所发布的功能块（不过得遵循框架的安全性）。同样，该应用程序重用机制也使用户可以方便的替换程序组件。隐藏在每个应用后面的是一系列的服务和系统, 其中包括；丰富而又可扩展的视图（Views)，可以用来构建应用程序， 它包括列表（Lists)，网格（Grids)，文本框（Text boxes)，按钮（Buttons)， 甚至可嵌入的 Web 浏览器。内容提供器（Content Providers)使得应用程序可以访问另一个应用程序的数据（如联系人数据库)，或者共享它们自己的数据资源管理器（Resource Manager)提供非代码资源的访问，如本地字符串、图形和布局文件。通知管理器 （Notification Manager) 使得应用程序可以在状态栏中显示自定义的示
南京邮电大学 2014 届本科生毕业设计（论文）
13
信息。活动管理器（ Activity Manager) 用来管理应用程序生命周期并提供常用的导航回退功能。
从以上 Android 的机制的中可以发现，Android 应用虽然使用 JAVA 语言编写，但是需要在 Android 虚拟机中运行，这就增加了对 Android 程序切片的难度。
2.4 本章小结 本课题针对基于 WALA 的 CallGraph 和 Slicer 进行研究，研究前向切片和基本的切片方法，从中得到上下文相关的依赖关系图，可以得到本课题对安全机制的研究方向，以及从切片算法的结果中进行可视化分析。继而对安卓系统进行初步的了解，以及对安卓切片的进行初步的设想和假设遇到的问题。
南京邮电大学 2014 届本科生毕业设计（论文）
14
第三章 WALA 框架 分析 与测试 本章提供了有关如何获取、安装和使用 WALA 框架的信息。目前为止，关于WALA 的文档只存在于 wiki 中。因此，本文对 WALA 框架的安装过程进行了详细的讲解。
3.1 WALA 平台简介 WALA 框架提供了为 JAVA 字节码和 JavaScript 语言的静态分析功能，最初WALA 项目是由 IBM 的 T.J. Watson 研发中心负责研发，在 2006 将 WALA 项目捐给了开源组织发布。
WALA 框架有以下特性：：
1) JAVA 类型系统和类层次的结构分析； 2) 支持 JAVA 和 JAVASCRIPT 语言的分析； 3) 交互过程的数据流分析； 4) 基于上下文交互的切片处理； 5) 指针分析和调用图结构； 6) 基于 SSA 的 IR 数据中间结构； 7) 迭代数据流的总体框架； 8) 一般分析实用程序和数据结构； 9) 字节码标准库和 JAVA 的动态链接库。
这些特性使得 WALA 具有强大的功能来分析源代码的特征和功能。
3.2 WALA 框架 的 分析 3.2.1 WALA 平台的下载及编译 WALA 源代码放在 github 上，作为公共代码，任何人可以进行修改上传。开发者可以通过 github 打包为压缩包下载下来。查看源代码需要开发工具 Eclipse，软件项目管理工具 Maven，项目管理工具 svn，Java JDK。对于 WALA 结果的分析，需要绘图软件 Graphviz/Gephi 等。最终我们通过生成的图像进行解析，寻找源代码间的关系，以此来分析源代码的安全性。
WALA 代码的编译需要在软件项目管理工具 Maven 下进行。Maven 是一个基于项目对象模型(POM)，可以通过一小段描述信息来管理项目的构建。WALA 项目是一个 Maven 项目，WALA 项目需要许多依赖包，需要在编译时下载到本地，所以，编译源代码是十分有必要的。将编译完成 WALA 源代码导入到 Eclipse，并进行配置。因为本文只对 Java 做切片研究，所以工程中有 JavaScript 工程错误，不影响笔者的研究。
需要配置一下几项来支持研究,笔者对其进行详细解释：
南京邮电大学 2014 届本科生毕业设计（论文）
15
? wala.properties 中的 java_runtime_dir 值,及 output_dir 值，java_runtime_dir 制定安装的 jre 中 lib 路径，例如笔者的是 C：/Program Files/Java/jre7/lib,注意的是，笔者曾经犯过错误，将 lib 制定到 jdk 中位置，导致出错。Output_dir 的指定生成的数据所放置的位置，例如 pdf 图，dt 数据等。
? wala.examples.properties 中的 pdfview_exe 和 dot_exe 的值，pdfview 值指定了读取 pdf 图软件的位置，如 adobe reader 的位置。dot_exe 指定了 Graphviz 软件的位置，Graphviz 是一个由 AT&T 实验室启动的开源工具包，用于绘制 DOT 语言脚本描述的图形。WALA 会在将分析的结果存储在文本文件 temp.dt，实际上该文件是 dot 文件的形式，可以由 Graphviz 进行绘图，笔者在实验中发现，Graphviz 在绘制大量点时，对电脑性能要求很高。
3.2.2 WALA 框架 的 表示 分析 JAVA 运行时以字节码的形式在虚拟机中运行，比如，有一个类 A 继承于类 B继承于标准库 java.lang.Object，类 A 和类 B 都重写了 lang.Object.toString()，于是在字节码中以如下形式存在：
< Application, A, toString() > < Application, B, toString() > < Application, Ljava/lang/Object, toString() > < Primordial, Ljava/lang/Object, toString() > 但是在运行时，会被转换为就一条语句：
< Primordial, Ljava/lang/Object, toString() >。
在 WALA 运行时，需要确定分析范围，分析范围的文件用以下形式表示：
Classloader,Language,Type,Location 例如：Primordial,Java,stdlib,none。
在确定分析范围时，WALA 需要确定所有的类的类型，WALA 确定类的层次通过以下两种方式：：
Application：加载应用程序的类加载器。
Primordial：加载 J2SE 标准库的类加载器。
WALA 框架了还提供了多种自定义指针分析上下文相关的分析方式。
指针上下文分析有两种方式：
Heap Model：指向虚指针和堆的位置 ContextSelector：调用上下文的调用图构建。
在 WALA 中，WALA 使用 IR 数据结构来表示方法的结构，IR 表示一种接近于 JVM 字节码的中间结构，IR 是作为基本块的控制流图的说明。
IR 不支持数据转换，用于生成分析信息，从而获得数据流的结构和地图。为后续的 CallGraph 和 Slicer 提供基础。
南京邮电大学 2014 届本科生毕业设计（论文）
16
3.2.2 WALA 切片 的功能分析 切片功能的实现首先需要实现对源代码的调用图 CallGraph 的生成。
Callgraph 分析：
Callgraph 表示上下文相关调用图，每个调用关系调用图的节点表示一个方法。
Callgraph 的代码表示：
buildCG(String jarFile) {
// 确定分析范围
AnalyisScope scope=AnalysisScopeReader。makeJavaBinaryAnalysisScope(jarFile, null)； (1)
// 类层次的分析 IClassHierarchy cha=ClassHierarchy。make(scope)； (2)
// 找到主函数入口 Iterable<Entrypoint> e=(3)
Util。makeMainEntrypoints(scope, cha)；
//设置分析的配置
AnalysisOptions o=new AnalysisOptions(scope, e)； (4)
// 生成 CallGraph 调用图
CallGraphBuilder builder=(5)
Util。makeZeroCFABuilder(o, new AnalysisCache(),
cha, scope)；
CallGraph cg=builder。makeCallGraph(o, null)； (6)
} 上面的代码能够清晰的表面 CallGraph 生成的过程。
接下来笔者分析下 CallGraphBuilder：
南京邮电大学 2014 届本科生毕业设计（论文）
17
图 3.1 h CallGraph 生成过程
从图中可以看出，CallGraphBuilder 由 AnalysisOptions，HeapModel 和 ContextSelector 三部分得到。
Slicer 分析：
WALA 中包含了基于上下文相关的系统调用图。它的基本框架图如下：
图 3.2 r Slicer 生成过程
从图中可以看出 Slicer 功能提供了前向和后向切片功能。Slicer 需要提供以下参数：
南京邮电大学 2014 届本科生毕业设计（论文）
18
? CallGraph参数，即前面分析的CallGraphbuilder生成的CallGraph对象。
? ControlDependenceOptions ? PointerAnalysis ? DataDenpendenceOptions Slicer 的 的 语法分析：
? Normal 语句 从 SSA IR 的结构中提取出的普通语法。
? PAPAM_CALLER 和 PAPAM_CALLEE 语句，函数的呼叫者和应答者。
? RETURN_CALLER 和 RETURN_CALLEE 语句，返回值的流回应。
? HEAP_*语句，代表着对方法的调用和返回语句。
ControlDependenceOptions 设置：
? FULL 和 NONE，分析所有的控制依赖和忽略所有的控制依赖。
? NO_EXCEPTIONAL_EDGES,忽略异常的控制依赖。
DataDenpendenceOptions 设置：
? FULL 和 NONE，所有的数据依赖和忽略所有的数据依赖。
? NO_BASE_PTRS，忽略依赖的基本指针。
? NO_HEAP,忽略堆中的来往依赖。
? NO_EXCEPTIONS，忽略异常抛出的错误。
? 组合，比如：NO_BASE,NO_HEAP。
3.2.3 WALA 切片 测试 用例 笔者通过 WALA 提供的接口实现了一个能够实现 CallGraph 和 Slicer 功能的JAVA 程序。
南京邮电大学 2014 届本科生毕业设计（论文）
19
图 3.3
软件界面
该软件界面基于 Java SWT 组件进行开发。主要功能如下 生成 CallGraph dot 文件和 Slicer dot 文件，生成 CallGraph 图和 Slicer 图。
使用方法如下：
1. 提交 jar 包，该包是将工程打包后生成的 jar 包，在实验中笔者发现，最好使用 eclipse 工具导出 jar 包，用 cmd 命令导出的包可能会有问题。
2. 提交 jar 包后会在 jar 路径的文本框中显示该 jar 包位置，以便 CallGraph和 Slicer 功能调用。点击 CallGraph 按钮，等待分析，时间会依据每个包的大小不同而不同。
3. 生成 CallGraph 图后，得到了该 jar 包的所有类和方法，接下来就可以选择进行切片。
4. 切片功能选择较多，参数一共有 7 个：
? appJar jar 包的路径，即提交的 jar 路径 ? mainClass 选择需要切片的类，软件会提供下拉框的形式供使用者选择 ? srcCaller 选择需要切片的类中的一个函数作为切片入口。在切片语法中，作为一个呼叫者 ? srcCallee 选择切片入口中的切片函数 ? forward/backward 选择前向或者是后向切片 ? dd 即 data dependence ，选择数据依赖参数 ? cd 即 control dependence，选择控制依赖参数 切片功能也会生成一个.dot 文件，生成 pdf 图。
接下来笔者使用一个测试用例来展示该软件的功能。
该软件测试 4 个类之间的互相调用关系。
图 3.4
测试用例代码结构
南京邮电大学 2014 届本科生毕业设计（论文）
20
笔者选择 HelloWorld 作为主类入口，main 函数的代码如下：
图 3.5
测试用例主函数代码
笔者将该工程导出，命名为 testcode.jar，接下来将 testcode.jar 导入
图 3.6
导入 jar 包界面
进行生成 CallGraph 操作
南京邮电大学 2014 届本科生毕业设计（论文）
21
图 3.7
CallGraph 操作
由 Graphviz 生成的 pdf 图：
图 3.8
生成的 CallGraph 图
从该 pdf 图中我们可以看到类和方法的调用关系图，十分清晰。如入口函数main 等。
接下来笔者选择一个函数进行切片功能进行演示：
南京邮电大学 2014 届本科生毕业设计（论文）
22
图 3.9
Slicer 功能演示
笔者选择 HelloWorld 类中 main 函数下的 aaa 函数进行分析，选择前向切片，数据依赖选择 no_base_ptrs，控制依赖选择 full。依据是官方建议这样选择切片参数可以得到最简洁的切片，便于分析。
切片功能会生成新的 temp.dt 图和 pdf 图：
图 3.10
切片生成的新 temp.dt 显示在框中
南京邮电大学 2014 届本科生毕业设计（论文）
23
图 3.11
切片生成的 aaa 函数对上下文的影响图
3.3 WALA 测试用例 结果分析 3.3.1 分析 工具 1)DOT 语言 DOT 语言是一种文本图形描述语言。它提供了一种简单的描述图形的方法，并且可以为人类和计算机程序所理解。DOT 语言文件通常...
相关热词搜索：
切片
毕业论文
程序
南京邮电大学 毕 业 设 计（论 文）
题
目 基于程序切片的安卓软件安全分析 专
业 软件工程 学生姓名
班级学号
指导教师
指导单位 计算机学院、软件学院
日期：
2014 年 3 月 10 日
至
2014 年 6 月 13 日
毕业设计（论文）原创性声明
本人郑重声明：所提交的毕业设计（论文），是本人在导师指导下，独立进行研究工作所取得的成果。除文中已注明引用的内容外，本毕业设计（论文）不包含任何其他个人或集体已经发表或撰写过的作品成果。对本研究做出过重要贡献的个人和集体，均已在文中以明确方式标明并表示了谢意。
论文作者签名：
日期：
年
月
日
摘
要
Android 系统是现在市场上占有率最大的手机系统，其开源的性质，让系统更加脆弱，所以更多的恶意软件针对 Android 系统，使得检测 Android 软件的安全性成为了十分重要的问题。在智能手机成为生活中的重要一部分的同时，每个人的隐私在手机上有着十分重要的地位。
JAVA 切片作为一个成熟的分析安全算法，对安卓程序有十分大的借鉴意义，因此本文提供的安卓安全分析算法研究具有相当的理论价值。
本文的目的在于研究基于程序切片的安卓软件安全分析，在成熟程序切片算法的基础上得到对安卓软件的安全性检查的算法和解决方案。
本文首先对基于 WALA 平台的切片算法进行研究，熟悉 JAVA 切片的算法,并基于 JAVA SWT 展示 WALA 平台的切片算法。之后对安卓软件的结构进行分析，了解安卓软件的安全漏洞，并分析这些漏洞。最终对基于 WALA 的安全分析软件SCanDroid 软件进行研究，得到安卓安全分析的算法和方法，使用数据可视化软件，对测试结果进行分析和统计，以直观的图形呈现，为成熟的 Android 软件检测方法提供了解决方案。
关键词：Android；安全分析；切片；WALA；数据可视化；
ABSTRACT Android system is now on the market share of the largest mobile phone system , its open source nature , make the system more fragile, so more malware for the Android system , which makes safety testing Android software has become a very important issue. The purpose of this paper is to study the safety analysis based on Android software program slice. Android software algorithms can be security checks and solutions based on a mature program slicing algorithm . Firstly, the slicing algorithm based research platform WALA familiar with JAVA slice algorithm and demonstrate slicing algorithm WALA platform based JAVA SWT. After the software to analyze the structure of Andrews , Andrews understand software security vulnerabilities , analysis of these vulnerabilities. WALA final safety analysis based software SCanDroid software research, algorithms and methods to get Android security analysis , and the results were analyzed using data visualization software to analyze the test results and statistics , finishing as intuitive graphic for reference, provides solutions for sophisticated Android software detection methods. In smart phones become an important part of life at the same time , everyone"s privacy on the phone has a very important position , as Android phones on the market share of the largest mobile phone systems, software security is very important , JAVA slice as a mature the analysis of security algorithm, the program has a very large Andrews reference , so Andrews security analysis algorithm provided herein have considerable theoretical value .
Keywords
：Android; Safety Analysis ; Slicer ; WALA; Data Visualization
目
录
第一章
绪论 .............................................. 1
1.1 课题背景和研究意义 ....................................................................................... 1
1.2 研究现状 ........................................................................................................... 2
1.3 本文工作 ........................................................................................................... 2
1.4 结构安排 ........................................................................................................... 3
第二章 程序切片的原理和算法 ............................... 4
2.1
程序切片简介 ................................................................................................. 4
2.1.1
程序切片准则 ...................................................................................... 4
2.1.2
程序切片分类 ...................................................................................... 5
2.2 程序切片的算法 ............................................................................................... 7
2.2.1 基于数据流方程的算法 ........................................................................ 8
2.2.2 基于依赖图(DG)的图形可达性算法 .................................................... 9
2.3 安卓系统简介 ................................................................................................. 10
2.4 本章小结 ......................................................................................................... 13
第三章 WALA 框架分析与测试 ................................ 14
3.1 WALA 平台简介 .............................................................................................. 14
3.2 WALA 框架的分析 .......................................................................................... 14
3.2.1 WALA 平台的下载及编译 ................................................................... 14
3.2.2 WALA 框架的表示分析 ....................................................................... 15
3.2.2 WALA 切片的功能分析 ....................................................................... 16
3.2.3 WALA 切片测试用例 ........................................................................... 18
3.3 WALA 测试用例结果分析 .............................................................................. 23
3.3.1 分析工具 .............................................................................................. 23
3.3.2 结果分析 .............................................................................................. 25
3.4 本章小结 ......................................................................................................... 30
第四章 安卓应用安全分析 .................................. 31
4.1 安卓系统安全机制解析 ................................................................................. 31
4.2 安卓恶意软件方式分析 ................................................................................. 32
4.3 SCanDroid 程序分析 ....................................................................................... 33
4.3.1 SCanDroid 程序原理 ............................................................................ 33
4.3.2 SCanDroid 程序测试 ............................................................................ 34
4.3.3 SCanDroid 结果分析 ............................................................................ 34
4.4 本章小结 ......................................................................................................... 36
结束语 ................................................... 37
致
谢 ................................................... 38
参考文献 ................................................. 39
南京邮电大学 2014 届本科生毕业设计（论文）
1
第一章
绪论 1.1 课题背景和研究意义 如今社会手机已经成为了人们生活中必不可少的一部分，显然智能手机占据了手机市场的绝大部分。据统计，2013 年全球手机市场销量增速持续放缓，但智能手机销量依旧一路狂奔，保持快速增长的势头。全球市场研究公司 Gartner 数据显示，如下图 1.1，2013 年第二季度全球智能手机销量首次超越了功能手机。同时Gartner 预测，2013 年全球智能手机销量将接近 10 亿部，占整个手机市场销量的比例将超过 50%。
图 1.1
手机销量走势
2013 Q2 促使全球智能手机销量首次超越功能手机的最大功臣非谷歌 Android系统莫属。Gartner 数据显示，2013 年 Q2Android 系统全球市场占有率为 79%，总销量为1.77亿部，2012年同期则仅为8000万部，市场份额不足60%。2013Q1Android系统市场份额为 74.4%，Q3 则达到了 81.9%，超过八成。
综上所述，我们可以看出，Android 系统现在已经日益影响大部分人的生活。在这个信息化时代，关注安卓软件安全问题刻不容缓。
根据芬兰计算机及网络安全提供商 F-Secure 提供的 2013 年手机平台恶意软件检测报告，2013 年 Android 平台滋生的恶意软件占所有手机恶意软件的 97％，而2012 年这一比例为 79％。虽然 Android 官方市场 Google Play 能够及时清除恶意应用程序，成为安全威胁比例最低的应用商店，其安全威胁比例仅为 0.1％。但是，
南京邮电大学 2014 届本科生毕业设计（论文）
2
由于 Android 系统的开放性，不少用户不会使用官方市场，这就给恶意软件有了可乘之机。
图 1.2
恶意软件占有率
目前现有的安卓安全管理软件，如国内的金山、QQ 手机管家、360 手机管家等等，都只能起到表面的监测作用，不能对源代码结构进行分析。所以，本课题致力于从程序切片方面着手，从 Android 软件的源代码入手，了解恶意软件的具体危害，将软件在安装前检测出问题。
1.2 研究 现状
目前的切片方法主要针对 Java 或者 C 语言的代码分析，用于安全检测，软件测试等方面，这些都有比较成熟的算法和理论，而在安卓系统上，只能在软件运行时检测出软件的危险性，并没有在在软件源代码上得到过切片的成熟理论和算法。
1.3 本文 工作 本文按照既定的计划进行研究和实践。首先了解了切片的概念和安卓软件恶意检测的常用手段，对常用的切片方式进行了分析，找到适合安卓分析的切片方法。之后对 JAVA 切片的算法进行了分析和了解，尝试常用的切片程序，然后对WALA 框架分析，了解了 WALA 框架在切片上实现的方式，使用 WALA 框架为基础将它的切片过程以客户端的形式表现出来。最终在以 WALA 框架为基础的SCanDroid 程序上实现对安卓软件的安全监测功能，并对程序进行性质判定。
南京邮电大学 2014 届本科生毕业设计（论文）
3
本文的创新之处在于：
1) 研究了针对安卓安全的切片程序实现方法，将传统的 JAVA 切片迁移到安卓程序切片，扩展了切片的使用范围。
2) 利用了开源的 WALA 框架并在其基础上进行了改进，对开源代码做出了贡献。
3) 将 SCanDroid 这一基于 WALA 框架的程序应用到实践中去，对该程序能够广泛使用提供了帮助。
1.4 结构 安排 本文对首先对当前的程序切片进行了研究，继而对 WALA 框架进行了切片研究，之后针对 SCanDroid 程序进行了安卓切片的研究，并对程序进行了测试，最后得出安卓切片的方向和解决方案。
南京邮电大学 2014 届本科生毕业设计（论文）
4
第二章 程序 切片 的原理和算法 程序切片是本课题的核心。在本章中，首先介绍程序切片的原理和分类，之后给出程序切片的算法节以及对其性能和可用性的测试。
2.1
程序 切片简介 程序切片是一种分析和理解程序的技术，通过分析程序语句之间的依赖性关系，自动分解源程序，程序切片技术在程序调试、回归测试、程序分析和理解、软件维护以及反向工程等领域都有广泛的应用。
程序切片首先是由 Weiser 在他的博士论文中提出来的，后来他又在 1981 年国际软件工程大会(ICSE"81)以及 1984 年 IEEE Transactions 上相继发表文章进一步阐述了程序切片的思想和实现算法。Weiser 描述的程序切片定义如下：：
定义 2.1：非形式化地，满足以下两个条件的程序称为切片：
(1) 一个切片对应一个特定的切片准则<V, i>，其中 v 表示变量的集合，i 指程序中的某个点(一般指某条语句)； (2) 程序 P 对应切片准则<V, i>的切片 S 可通过从 P 中删除一条或者多条和切片准则不相关的语句得到，并且要保证程序 P 和切片 S 关于切片准则(V, i)的行为相同。
随着切片技术的发展，S.Horwitz 等人给出了一个更精确的程序切片定义。
定义 2.2：一个程序切片是由程序中的一些语句和判定表达式组成的集合。这些语句和表达式可能会影响在程序中的某个位置(常用行号标识)P 上所定义的或所使用的变量 v 的值。<P, v>称为切片准则。
2.1.1
程序 切片 准则 计算程序切片必须考虑切片准则。对同样的程序计算切片时，如果切片准则发生变化，则计算得到的程序切片也会不同。因而程序切片准则是程序切片技术的重要环节。目前存在主要切片准则有：
静态后向切片准则：构造一个程序 P 的静态后向切片时，考虑的切片准则是一个二元组(V,p)，其中 V 是一组变量，p 是程序中的一个兴趣点，程序 p 的一个切片时任何一个在 V 中 p 点对变量具有与 P 相同影响的程序。
动态后向切片准则：构造一个程序 P 的动态后向切片构造时，考虑的切片准则是一个三元组(V,p,x)，其中 V 是变量的集合，p 是程序 P 中的一个兴趣点，x 是一个输入序列。当用 x 输入时，一个动态切片保留 P 的与 p 点的变量集合 V 有关的投影含义。
传统的前向切片准则：构造一个程序 P 的传统的前向切片时，考虑的切片准则是(V,p)，这里 V 是变量的集合，p 是程序 P 中一个兴趣点。程序切片是一个语句和谓词组成的集合，这些语句和谓词受到 P 中 V 的变量在 p 的值对它的影响。
南京邮电大学 2014 届本科生毕业设计（论文）
5
分解切片准则：程序 P 的关于一个变量 V 的分解切片的构造，是关于切片准则 ({v},end) 静 态 后 向 切 片 和 {({v},n1), … … ， ({v},nm)} 的 并 组 成 ， 其 中{n1,n2,……,nm}是行的集合(v 在 P 中是输出，end 是程序的结尾语句)。
多点切片准则：构造程序 P 的多点切片需要考虑二元组(V,N)，其中 N 是程序P 中点的集合，V 是变量的集合。当在 N 中任何一点执行一条语句时，对 V 中所有变量，切片和程序 P 具有同样的效果。
广义切片准则：广义切片是传统切片的扩展，其中变量被随机的有名程序实体代替，语句被随机的程序构造代替。
迭代切片准则：构造一个程序 P 的迭代切片时，考虑的切片准则是(V,p,n)，这里 V 是变量的集合，p 是程序 P 中一个兴趣点，n 是自然数。程序 P 的第 n 次（静态）迭代切片 S 是由第 n 次执行到达 p 时那些保持程序 P 的投影含义不变的语句组成。当 n 换成 N（自然数集）时就编程广义迭代切片准则。
条件切片准则：构造一个程序 P 的条件切片时，考虑的切片准则是一个四元组(l,p,π,V),这里 l 是变量名的集合，这些变量的值是从输入序列中获得的，p 是程序 P 中一个兴趣点，π 是一个谓词，它的自由变量是 l 的一个子集，V 是一个变量名的集合。构造一个程序 P 的条件切片 S，当在一个满足 π 的初始状态执行时，条件切片 S 必须保持程序 P（与 V 有关）的投影含义。
2.1.2
程序 切片 分类 程序切片主要分为以下几类：
1. 后向切片和前向切片 后向切片指包含影响变量的所有语句和断言；前向切片指包含受该变量影响的所有语句和断言。如图 2.1 所示。
图 2.1
语句 y：=x+4 的后向和前向切片计算结果
2. 静态切片和动态切片 MODULE BackwardSlicing VAR
x,y,z：INTEGER BEGIN
x：=3；
y：=x+4；
z：=y+3； END BackwardSlicing MODULE ForwardSlicing VAR
x,y,z：INTEGER BEGIN
x：=3；
y：=x+4；
z：=y+3； END ForwardSlicing
南京邮电大学 2014 届本科生毕业设计（论文）
6
静态切片：利用静态分析产生切片，也就是分析程序的源代码，计算所有可能输入值情况下的切片。动态切片：是在某个特定输入下的程序切片，它把在特定输入时实际影响某个程序点变量值的所有语句包含到切片中。如图 2.2 所示。
图 2.2（a）
图 2.2（b）
图 2.2 在最后一个语句计算的静态切片（a），当输入 op=“sin”时计算的动态切片（b ）
3. 过程内切片和过程间切片 过程内切片：主要在一个过程之内计算切片；过程间切片：如果一个程序由多个过程组成，则需要利用过程间切片来计算程序切片。过程间切片引起一个新的问题：当一个过程在不同的地方被调用时，必须考虑调用的上下文，以便在编译时能够正确模型化运行时执行情况。过程间数据流分析有一个类似的目标就是只考虑对应于合法 call/return 序列的路径。如图 2.3. MODULE DynamicSlicing IMPORT Math,In,Out VAR x,y：Real； op：
APPLY 10 OF CHAR； BEGIN In.Open； In.String(op)；In.Real(x)； IF op=sin THEN
y：=Math.Sin(x) ELSE ：
。MODULE StaticSlicing IMPORT Math,In,Out VAR x,y：Real； op：
APPLY 10 OF CHAR； BEGIN In.Open； In.String(op)；In。Real(x)； IF op=sin THEN
y：=Math。Sin(x) ELSE
y：=Math.Cos(x)
南京邮电大学 2014 届本科生毕业设计（论文）
7
图 2.3
考虑调用的上下文时过程 Increment 的输出参数 z 的切片
2.2 程序切片 的算法 程序切片的算法主要有 Weiser 的基于数据流方程的算法、无定型切片算法、Bergeretti 的基于信息流关系的算法、K.J. Ottenstein 和 L.M. Ottenstein 以及 Horwitz的基于程序依赖图的图形可达性算法、杨洪的基于波动图的算法。另外，还有参数化程序切片算法、并行切片算法以及面向对象的分层切片算法等。这里重点介绍基于数据流方程的算法和基于依赖图的算法。
MODULE CallingContext
PROCEDURE Add(VAR a ：INTEGER；b INTEGER)； BEGIN a：=a+b END Add；
PROCEDURE Increment(VAR z：INTEGER)； BEGIN Add(z,1) END Increment；
PROCEDURE A(VAR x,y：INTEGER) BEGIN
Add(x,y)；
Increment(y) END A；
PROCEDURE Main；
VAR sum,i：INTEGER； BEGIN
sum：=0； i：=1；
WHERE i<：100
A(sum,i) END END Main； END CallingContex
南京邮电大学 2014 届本科生毕业设计（论文）
8
2.2.1 基于数据流方程的 算法 Weiser 是根据数据流方程的迭代解最早定义程序切片的。他定义的程序切片是通过对初始程序删除零条或多条语句而获得的一个可执行的程序。切片准则由一个二元组（n，V）构成，其中 n 是程序的 CFG 中一个结点，V 是程序中变量的一个子集。关于切片准则（n，V）的程序切片是程序 P 的语句的一个子集 S，它必须满足下列特性：
① S 必须是一个有效程序；
② 对一个给定的输入，P 发生中断时，S 也会发生中断。无论何时与结点 n相关的语句被执行时，计算 V 中所有变量的值（对 P 和 V 来说）分别是相同的。
公理 1：
对应任何一个切片准则，至少存在一个切片，即程序本身。
如果对同一个切片准则来说，没有其他的切片比某个切片 Sminimal 包含更少的语句，则称 Sminimal 为最少语句的切片。Weiser 认为最少语句切片不一定是唯一的，且如何确定最少语句切片问题是不可判定的。
Weiser 描述了一个用来计算最少语句切片近似值的迭代算法。这种算法使用两种不同的迭代层次，即: ① 跟踪可传递的数据依赖层。这要求迭代过程是在循环存在情况下发生的；
②跟踪控制依赖层。该层把跟踪到的新的控制谓词控制的语句包含到某个控制谓词的切片中。对每个这样的谓词，到把它依赖的所有语句包含进来为止。这类算法确定相关变量的连贯集合，由此可得到相关语句的集合。
Weiser 迭代算法的第 1 层要确定直接相关变量：这是上面论述的迭代过程步骤 1 的一个实例。CFG 中结点 i 的直接相关变量的集合记为 R0C(i)。迭代开始于初始值 R0C(n)=V，且对任何结点 m≠n，满足 R0C(m=。图 1 中定义的一组方程可确定在 CFG 的边 i→CFG j 的终点 j 的相关变量的集合是如何影响在开始点 i 的相关变量的集合。这个过程的最小不动点就是在结点 i 的直接相关变量的集合。从R0C 可得到直接相关语句集合 S0C。图 1 表示了 S0C 是如何被定义为所有结点 i的集合，i 定义了变量 v，该变量在 i 的一个 CFG 后继是相关的。
Weiser 迭代算法的第 2 层要考虑控制依赖。如果在一个 if 或 while 语句控制谓词的控制体中至少有一条语句是相关的，则变量引用是间接相关的。为了实现这个目标，一条分支语句 b 的影响范围 Infl(b)定义为由所有控制依赖 b 的语句组成的集合。图 2 表示分支语句的一个定义 BkC。由于它们对 SkC 中结点 i 的影响，因而是间接相关的。间接相关变量的 Rk+1C(i)得到确定。除 RkC(i)中的变量之外，Rk+1C(i)包含的变量是相关的，因为它们对 BkC 中的语句存在可传递的数据依赖。这通过再一次执行第 1 层迭代来确定（也就是跟踪可传递的数据流），同时考虑的一组准则是（b，Ref(b)），这里 b 是 BkC 中的一条分支语句。图 2 还定义了在 k+1次迭代过程中间接相关语句（indirectly relevant statements）的集合 Sk+1C。这个集
南京邮电大学 2014 届本科生毕业设计（论文）
9
合由 BkC 中的结点 i 一起构成，结点 i 定义了一个变量，该变量对 CFG 的后继 j来说是 Rk+1C 相关的。由此可得下面的定义。
定义 2.3：程序切片是由程序中某个兴趣点的相关语句集合的不动点构成的集合。计算程序切片就是计算相关语句集合的不动点。
集合 Rk+1C 和 Sk+1C 分别是程序的变量和语句的非递减子集；计算得到的集合 Sk+1C 的不动点就构成期望的程序切片。
Lyle 虽然提供了 Weiser 切片算法一种修改版，但除了在术语方面的细小改变外，与 Weiser 算法本质上没有什么两样。
Hausler 用函数的风格重述了 Weiser 的算法。对每种类型的语句（空语句、赋值语句、语句组合、if 和 while），他定义了两个函数 δ 和 α。粗略地说，这些函数分别表示一条语句是如何转换相关变量的集合 RiC，以及相关语句的集合 SiC。函数 δ 和 α 是以一种组合的方式定义的。对空语句和赋值语句，δ 和 α 可以按语法制导的方式从语句中产生出来。语句序列和 if 语句的 δ 和 α 函数可以分别从它们构件的 δ 和 α 函数推导出来。通过把它有效地转换成一个 if 语句的无穷序列来获得while 语句的函数。
2.2.2 基于依赖图(DG) 的图形可达性算法 Ottenstein等在1984年提出了切片准则由一个程序点p和一个在p定义的或使用的变量 v 构成，且在一个程序依赖图(PDG)上使用图形可达性算法来计算切片。根据他们对切片含义的理解，切片是由程序中所有可能影响 v 在 p 点值的语句和谓词构成。1990 年，Horwitz 等使用依赖图来计算切片，他们开发了一种过程间的程序表示——系统依赖图(SDG)，并实现了一个基于系统依赖图的两阶段图形可达性切片算法。由于使用调用位置的可传递的依赖流信息中包含被调用过程的上下文环境，所以该算法的计算精度比以前的算法更高。后来，为了切片面向对象的程序又出现了多种依赖图，具有代表性的有：Zhao 提出的一种动态面向对象的依赖图(DODG)和系统依赖图网（SDN），分别用于解决面向对象程序的动态切片问题和并发面向对象的程序切片问题；Krishnaswamy 提出一种面向对象的程序依赖图(OPDG)，并在 OPDG 上实现了计算语句切片的算法。OPDG 是通过对传统的程序依赖图进行面向对象的扩充获得的，但 OPDG 不能表示虚继承、动态对象等问题，因而 OPDG 是不完全的面向对象程序表示。下面简单分析一下各种依赖图在切片算法中应用及其特点。
1) 程序依赖图(PDG)
PDG 是程序的一种图形表示，它把控制依赖和数据依赖包含在单个的结构中。如果给定程序中的语句 X 和 Y，则 X 和 Y 可以通过控制流或者数据流来彼此关联。如果从 Y 至少可以引出两条路径，其中一条总会导致 X 的执行，而另一条可能导致 X 不执行，则称语句 X 控制依赖于语句 Y；如果有一条从 Y 到 X 的路径，且存
南京邮电大学 2014 届本科生毕业设计（论文）
10
在一个在 Y 点定义在 X 点使用的变量，且该变量在沿从 Y 到 X 的路径上其它任何地方没有被重新定义，则称语句 X 数据依赖于语句 Y。PDG 的形式定义是由一个控制依赖子图(CDG)，一个控制流图(CFG)和一个数据依赖子图(DDG)组成。其中CDG 包含了程序中的控制依赖； CFG 描述了一个程序中的控制流，它类似于正常情况下的流图；DDG 是一个程序中语句之间所有数据依赖的集合。CDG 包含语句结点、域结点和谓词结点等类型的结点。语句结点表示程序中的语句；域结点概括了域中语句间的控制依赖；谓词结点（由此可以引出两条边）表示程序中的策略或分支条件。CDG 中的域结点可利用相同的控制依赖来集合语句。DDG 包含语句间的数据依赖，可通过在 CDG 的结点之间插入数据依赖边来构造 DDG。PDG不允许过程间分析，它也没有能力表示继承、多态性和动态定连等重要的面向对象的特性。
2) 系统依赖图（SDG）
SDG 是程序的一种语法分析树表示。结点表示程序构造，输入输出参数和调用位置等，边表示与之相连的结点之间的各种依赖(例如数据依赖、控制依赖和声明等)。程序依赖图通常是为单个的过程间程序来定义的。由于现实世界的程序一般是由多个过程组成的，所以必须考虑使用一种与现实世界程序匹配的表示方法，于是 Horwitz 等人提出了系统依赖图。SDG 是一棵经过装饰的表示程序的语法分析树。形式地说，SDG 是由一个程序依赖图和一组过程依赖图（PrDG）构成的有向、带标记的多重图。PDG 模型化软件系统中的主程序，PrDG 模型化软件系统中的多个过程体。SDG 可以用来处理过程间的数据流和控制流，并能表示参数传递。SDG 允许过程间分析，但面向对象程序远不是一些过程或方法的简单组合，所以SDG 提供的机制还不足以描述这些面向对象的概念。
2.3 安卓 系统简介 Android 是一种基于 Linux 的自由及开放源代码的操作系统，主要使用于移动设备，如智能手机和平板电脑，由 Google 公司和开放手机联盟领导及开发。尚未有统一中文名称，中国大陆地区较多人使用“安卓”或“安致”。Android 操作系统最初由 Andy Rubin 开发，主要支持手机。2005 年 8 月由 Google 收购注资。2007 年11 月，Google 与 84 家硬件制造商、软件开发商及电信营运商组建开放手机联盟共同研发改良 Android 系统。随后 Google 以 Apache 开源许可证的授权方式，发布了Android 的源代码。第一部 Android 智能手机发布于 2008 年 10 月。
Android 分为四个层，从高层到低层分别是应用程序层、应用程序框架层、系统运行库层和 Linux 内核层。
操作系统：
Android 使用 Linux2。6 作为操作系统，Linux2。6 是一种标准的技术，Linux 也是一个开放的操作系统。Android 对操作系统的使用包括核心和驱动程序两部
南京邮电大学 2014 届本科生毕业设计（论文）
11
分，Android 的 Linux 核心为标准的 Linux2。6 内核，Android 更多的是需要一些与移动设备相关的驱动程序。
显示驱动（Display Driver）：常用基于 Linux 的帧缓冲（Frame Buffer）驱动,Flash 内存驱动（Flash Memory Driver）,照相机驱动（Camera Driver）：常用基于 Linux 的 v4l（Video for ）驱动。音频驱动（Audio Driver）：常用基于 ALSA（Advanced Linux Sound Architecture，高级 Linux 声音体系）驱动，WiFi 驱动（Camera Driver）：基于 IEEE 802.11 标准的驱动程序，键盘驱动（KeyBoard Driver），蓝牙驱动（Bluetooth Driver）,Binder IPC 驱动：Android 一个特殊的驱动程序，具有单独的设备节点，提供进程间通讯的功能,Power Management（能源管理）。
应用程序框架：
Android 的应用程序框架为应用程序层的开发者提供 APIs，它实际上是一个应用程序的框架。由于上层的应用程序是以 JAVA 构建的，因此本层次提供的首先包含了 UI 程序中所需要的各种控件：
例如：
Views ( 视图组件 ) 包括 lists( 列表 ), grids( 栅格 ), text boxes( 文本框 ), buttons( 按钮 ) 等，甚至一个嵌入式的 Web 浏览器。一个 Android 的应用程序可以利用应用程序框架中的以下几个部分：
Activity （活动）、Broadcast Intent Receiver （广播意图接收者）、Service （服务）、Content Provider （内容提供者）。
应用程序：
Android 的应用程序主要是用户界面（User Interface），通常以 JAVA 程序编写，其中还可以包含各种资源文件（放置在 res 目录中）。JAVA 程序及相关资源经过编译后，将生成一个 APK 包。Android 本身提供了主屏幕（Home），联系人（Contact），电话（Phone），浏览器（Browsers）等众多的核心应用。同时应用程序的开发者还可以使用应用程序框架层的 API 实现自己的程序。
南京邮电大学 2014 届本科生毕业设计（论文）
12
图 2.4
Android 的层次分析
系统运行库：
Android 包含一些 C/C++库，这些库能被 Android 系统中不同的组件使用。它们通过 Android 应用程序框架为开发者提供服务。以下是一些核心库：
* 系统 C 库 - 一个从 BSD 继承来的标准 C 系统函数库 Libc )， 它是专门为基于 Embedded Linux 的设备定制的。
* 媒体库 - 基于 PacketVideo OpenCORE；该库支持多种常用的音频、视频格式回放和录制，同时支持静态图像文件。编码格式包括 MPEG4, H。264, MP3, AAC, AMR, JPG, PNG 。
* Surface Manager - 对显示子系统的管理，并且为多个应用程序提 供了 2D和 3D 图层的无缝融合。
* LibWebCore - 一个最新的 web 浏览器引擎用，支持 Android 浏览器和一个可嵌入的 web 视图。
Android 中，Activity 是所有程序的根本，所有程序的流程都运行在 Activity 之中，Activity 可以算是开发者遇到的最频繁，也是 Android 当中最基本的模块之一。Service 是 Android 系统中的一种组件，它跟 Activity 的级别差不多，但是他不能自己运行，只能后台运行，并且可以和其他组件进行交互。Service 是没有界面的长生命周期的代码。Service 是一种程序，它可以运行很长时间，但是它却没有用户界面。在 Android 中，Broadcast 是一种广泛运用的在应用程序之间传输信息的机制。而 BroadcastReceiver 是对发送出来的 Broadcast 进行过滤接受并响应的一类组件。可以使用 BroadcastReceiver 来让应用对一个外部的事件做出响应。Content Provider 是 Android 提供的第三方应用数据的访问方案。
Android 通常与一系列核心应用程序包一起发布，该应用程序包包括客户端、SMS 短消息程序、日历、地图、浏览器、联系人管理程序等。所有的应用程序都是使用 JAVA 语言编写的。
开发人员也可以完全访问核心应用程序所使用的 API 框架。该应用程序的架构设计简化了组件的重用；任何一个应用程序都可以发布它的功能块并且任何其它的应用程序都可以使用其所发布的功能块（不过得遵循框架的安全性）。同样，该应用程序重用机制也使用户可以方便的替换程序组件。隐藏在每个应用后面的是一系列的服务和系统, 其中包括；丰富而又可扩展的视图（Views)，可以用来构建应用程序， 它包括列表（Lists)，网格（Grids)，文本框（Text boxes)，按钮（Buttons)， 甚至可嵌入的 Web 浏览器。内容提供器（Content Providers)使得应用程序可以访问另一个应用程序的数据（如联系人数据库)，或者共享它们自己的数据资源管理器（Resource Manager)提供非代码资源的访问，如本地字符串、图形和布局文件。通知管理器 （Notification Manager) 使得应用程序可以在状态栏中显示自定义的示
南京邮电大学 2014 届本科生毕业设计（论文）
13
信息。活动管理器（ Activity Manager) 用来管理应用程序生命周期并提供常用的导航回退功能。
从以上 Android 的机制的中可以发现，Android 应用虽然使用 JAVA 语言编写，但是需要在 Android 虚拟机中运行，这就增加了对 Android 程序切片的难度。
2.4 本章小结 本课题针对基于 WALA 的 CallGraph 和 Slicer 进行研究，研究前向切片和基本的切片方法，从中得到上下文相关的依赖关系图，可以得到本课题对安全机制的研究方向，以及从切片算法的结果中进行可视化分析。继而对安卓系统进行初步的了解，以及对安卓切片的进行初步的设想和假设遇到的问题。
南京邮电大学 2014 届本科生毕业设计（论文）
14
第三章 WALA 框架 分析 与测试 本章提供了有关如何获取、安装和使用 WALA 框架的信息。目前为止，关于WALA 的文档只存在于 wiki 中。因此，本文对 WALA 框架的安装过程进行了详细的讲解。
3.1 WALA 平台简介 WALA 框架提供了为 JAVA 字节码和 JavaScript 语言的静态分析功能，最初WALA 项目是由 IBM 的 T.J. Watson 研发中心负责研发，在 2006 将 WALA 项目捐给了开源组织发布。
WALA 框架有以下特性：：
1) JAVA 类型系统和类层次的结构分析； 2) 支持 JAVA 和 JAVASCRIPT 语言的分析； 3) 交互过程的数据流分析； 4) 基于上下文交互的切片处理； 5) 指针分析和调用图结构； 6) 基于 SSA 的 IR 数据中间结构； 7) 迭代数据流的总体框架； 8) 一般分析实用程序和数据结构； 9) 字节码标准库和 JAVA 的动态链接库。
这些特性使得 WALA 具有强大的功能来分析源代码的特征和功能。
3.2 WALA 框架 的 分析 3.2.1 WALA 平台的下载及编译 WALA 源代码放在 github 上，作为公共代码，任何人可以进行修改上传。开发者可以通过 github 打包为压缩包下载下来。查看源代码需要开发工具 Eclipse，软件项目管理工具 Maven，项目管理工具 svn，Java JDK。对于 WALA 结果的分析，需要绘图软件 Graphviz/Gephi 等。最终我们通过生成的图像进行解析，寻找源代码间的关系，以此来分析源代码的安全性。
WALA 代码的编译需要在软件项目管理工具 Maven 下进行。Maven 是一个基于项目对象模型(POM)，可以通过一小段描述信息来管理项目的构建。WALA 项目是一个 Maven 项目，WALA 项目需要许多依赖包，需要在编译时下载到本地，所以，编译源代码是十分有必要的。将编译完成 WALA 源代码导入到 Eclipse，并进行配置。因为本文只对 Java 做切片研究，所以工程中有 JavaScript 工程错误，不影响笔者的研究。
需要配置一下几项来支持研究,笔者对其进行详细解释：
南京邮电大学 2014 届本科生毕业设计（论文）
15
? wala.properties 中的 java_runtime_dir 值,及 output_dir 值，java_runtime_dir 制定安装的 jre 中 lib 路径，例如笔者的是 C：/Program Files/Java/jre7/lib,注意的是，笔者曾经犯过错误，将 lib 制定到 jdk 中位置，导致出错。Output_dir 的指定生成的数据所放置的位置，例如 pdf 图，dt 数据等。
? wala.examples.properties 中的 pdfview_exe 和 dot_exe 的值，pdfview 值指定了读取 pdf 图软件的位置，如 adobe reader 的位置。dot_exe 指定了 Graphviz 软件的位置，Graphviz 是一个由 AT&T 实验室启动的开源工具包，用于绘制 DOT 语言脚本描述的图形。WALA 会在将分析的结果存储在文本文件 temp.dt，实际上该文件是 dot 文件的形式，可以由 Graphviz 进行绘图，笔者在实验中发现，Graphviz 在绘制大量点时，对电脑性能要求很高。
3.2.2 WALA 框架 的 表示 分析 JAVA 运行时以字节码的形式在虚拟机中运行，比如，有一个类 A 继承于类 B继承于标准库 java.lang.Object，类 A 和类 B 都重写了 lang.Object.toString()，于是在字节码中以如下形式存在：
< Application, A, toString() > < Application, B, toString() > < Application, Ljava/lang/Object, toString() > < Primordial, Ljava/lang/Object, toString() > 但是在运行时，会被转换为就一条语句：
< Primordial, Ljava/lang/Object, toString() >。
在 WALA 运行时，需要确定分析范围，分析范围的文件用以下形式表示：
Classloader,Language,Type,Location 例如：Primordial,Java,stdlib,none。
在确定分析范围时，WALA 需要确定所有的类的类型，WALA 确定类的层次通过以下两种方式：：
Application：加载应用程序的类加载器。
Primordial：加载 J2SE 标准库的类加载器。
WALA 框架了还提供了多种自定义指针分析上下文相关的分析方式。
指针上下文分析有两种方式：
Heap Model：指向虚指针和堆的位置 ContextSelector：调用上下文的调用图构建。
在 WALA 中，WALA 使用 IR 数据结构来表示方法的结构，IR 表示一种接近于 JVM 字节码的中间结构，IR 是作为基本块的控制流图的说明。
IR 不支持数据转换，用于生成分析信息，从而获得数据流的结构和地图。为后续的 CallGraph 和 Slicer 提供基础。
南京邮电大学 2014 届本科生毕业设计（论文）
16
3.2.2 WALA 切片 的功能分析 切片功能的实现首先需要实现对源代码的调用图 CallGraph 的生成。
Callgraph 分析：
Callgraph 表示上下文相关调用图，每个调用关系调用图的节点表示一个方法。
Callgraph 的代码表示：
buildCG(String jarFile) {
// 确定分析范围
AnalyisScope scope=AnalysisScopeReader。makeJavaBinaryAnalysisScope(jarFile, null)； (1)
// 类层次的分析 IClassHierarchy cha=ClassHierarchy。make(scope)； (2)
// 找到主函数入口 Iterable<Entrypoint> e=(3)
Util。makeMainEntrypoints(scope, cha)；
//设置分析的配置
AnalysisOptions o=new AnalysisOptions(scope, e)； (4)
// 生成 CallGraph 调用图
CallGraphBuilder builder=(5)
Util。makeZeroCFABuilder(o, new AnalysisCache(),
cha, scope)；
CallGraph cg=builder。makeCallGraph(o, null)； (6)
} 上面的代码能够清晰的表面 CallGraph 生成的过程。
接下来笔者分析下 CallGraphBuilder：
南京邮电大学 2014 届本科生毕业设计（论文）
17
图 3.1 h CallGraph 生成过程
从图中可以看出，CallGraphBuilder 由 AnalysisOptions，HeapModel 和 ContextSelector 三部分得到。
Slicer 分析：
WALA 中包含了基于上下文相关的系统调用图。它的基本框架图如下：
图 3.2 r Slicer 生成过程
从图中可以看出 Slicer 功能提供了前向和后向切片功能。Slicer 需要提供以下参数：
南京邮电大学 2014 届本科生毕业设计（论文）
18
? CallGraph参数，即前面分析的CallGraphbuilder生成的CallGraph对象。
? ControlDependenceOptions ? PointerAnalysis ? DataDenpendenceOptions Slicer 的 的 语法分析：
? Normal 语句 从 SSA IR 的结构中提取出的普通语法。
? PAPAM_CALLER 和 PAPAM_CALLEE 语句，函数的呼叫者和应答者。
? RETURN_CALLER 和 RETURN_CALLEE 语句，返回值的流回应。
? HEAP_*语句，代表着对方法的调用和返回语句。
ControlDependenceOptions 设置：
? FULL 和 NONE，分析所有的控制依赖和忽略所有的控制依赖。
? NO_EXCEPTIONAL_EDGES,忽略异常的控制依赖。
DataDenpendenceOptions 设置：
? FULL 和 NONE，所有的数据依赖和忽略所有的数据依赖。
? NO_BASE_PTRS，忽略依赖的基本指针。
? NO_HEAP,忽略堆中的来往依赖。
? NO_EXCEPTIONS，忽略异常抛出的错误。
? 组合，比如：NO_BASE,NO_HEAP。
3.2.3 WALA 切片 测试 用例 笔者通过 WALA 提供的接口实现了一个能够实现 CallGraph 和 Slicer 功能的JAVA 程序。
南京邮电大学 2014 届本科生毕业设计（论文）
19
图 3.3
软件界面
该软件界面基于 Java SWT 组件进行开发。主要功能如下 生成 CallGraph dot 文件和 Slicer dot 文件，生成 CallGraph 图和 Slicer 图。
使用方法如下：
1. 提交 jar 包，该包是将工程打包后生成的 jar 包，在实验中笔者发现，最好使用 eclipse 工具导出 jar 包，用 cmd 命令导出的包可能会有问题。
2. 提交 jar 包后会在 jar 路径的文本框中显示该 jar 包位置，以便 CallGraph和 Slicer 功能调用。点击 CallGraph 按钮，等待分析，时间会依据每个包的大小不同而不同。
3. 生成 CallGraph 图后，得到了该 jar 包的所有类和方法，接下来就可以选择进行切片。
4. 切片功能选择较多，参数一共有 7 个：
? appJar jar 包的路径，即提交的 jar 路径 ? mainClass 选择需要切片的类，软件会提供下拉框的形式供使用者选择 ? srcCaller 选择需要切片的类中的一个函数作为切片入口。在切片语法中，作为一个呼叫者 ? srcCallee 选择切片入口中的切片函数 ? forward/backward 选择前向或者是后向切片 ? dd 即 data dependence ，选择数据依赖参数 ? cd 即 control dependence，选择控制依赖参数 切片功能也会生成一个.dot 文件，生成 pdf 图。
接下来笔者使用一个测试用例来展示该软件的功能。
该软件测试 4 个类之间的互相调用关系。
图 3.4
测试用例代码结构
南京邮电大学 2014 届本科生毕业设计（论文）
20
笔者选择 HelloWorld 作为主类入口，main 函数的代码如下：
图 3.5
测试用例主函数代码
笔者将该工程导出，命名为 testcode.jar，接下来将 testcode.jar 导入
图 3.6
导入 jar 包界面
进行生成 CallGraph 操作
南京邮电大学 2014 届本科生毕业设计（论文）
21
图 3.7
CallGraph 操作
由 Graphviz 生成的 pdf 图：
图 3.8
生成的 CallGraph 图
从该 pdf 图中我们可以看到类和方法的调用关系图，十分清晰。如入口函数main 等。
接下来笔者选择一个函数进行切片功能进行演示：
南京邮电大学 2014 届本科生毕业设计（论文）
22
图 3.9
Slicer 功能演示
笔者选择 HelloWorld 类中 main 函数下的 aaa 函数进行分析，选择前向切片，数据依赖选择 no_base_ptrs，控制依赖选择 full。依据是官方建议这样选择切片参数可以得到最简洁的切片，便于分析。
切片功能会生成新的 temp.dt 图和 pdf 图：
图 3.10
切片生成的新 temp.dt 显示在框中
南京邮电大学 2014 届本科生毕业设计（论文）
23
图 3.11
切片生成的 aaa 函数对上下文的影响图
3.3 WALA 测试用例 结果分析 3.3.1 分析 工具 1)DOT 语言 DOT 语言是一种文本图形描述语言。它提供了一种简单的描述图形的方法，并且可以为人类和计算机程序所理解。DOT 语言文件通常...
相关热词搜索：
切片
毕业论文
程序
上一篇：毕业致辞,(合集)
下一篇：毕业论文感谢致辞(集锦9篇)