summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/uestcthesis/doc/chapters/implementation.tex
blob: 9636d04113f41f2e1395d9c4b351450015093974 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
% !Mode:: "TeX:UTF-8"

\chapter{示例:实现方案}
本章首先介绍了本系统实现的设计原则与目标,然后描述了系统的整体架构与总体设计方案,接着阐述了系统的各个模块实现时的解决方案,最后给出了系统在~Android~具体实现时的实现方法和使用说明。
\section{设计目标与原则}
	\subsection{设计目标}
	本系统能够检测已知恶意软件及其变种,并能通过模糊检测发现具有相似恶意行为的未知恶意软件,为~Android~平台这样的开放式移动平台提供安全保障,可广泛用于各种型号的~Android~设备。系统具体设计目标如下:
	\begin{enumerate}
	\item 适用于目前主流的~Android~平板及手机,至少可运行于3.0版本系统。
	\item 能够检测用户指定的程序是否为恶意程序。
	\item 能够自动检测设备上的所有程序,并可定时检测。
	\item 能够监控设备的程序安装行为,自动检测安装的程序是否为恶意程序。
	\item 能够保证本程序自身的特征库不被破坏,并能及时修复和更新特征库。
	\item 能够保证用户使用方便。
	\end{enumerate}
	
	\subsection{设计原则}
	 从安全产品的特点出发,本系统设计与实现将遵循下列一些设计原则:
	\begin{enumerate}
	\item 高效性
	
	 系统运行效率高,可快速实现对目标程序的特征提取与检测,并将结果用最清晰简洁的方式告知用户。
	\item 灵活性
	
	 为用户提供的各种功能具有可选性,用户可根据自己的需要选择其中的功能,而且用户可自行决定如何处理检测结果为恶意的程序。
	
	\item 实用性
	
	本系统应按照实用性原则进行设计,在保证对程序检测的同时,力求用户界面简洁友好。
	
	\item 可扩展性
	
	 目前本系统只检测程序的~Java~实现部分,但是还有极少数程序代码是用~C~语言编写的,在后续的开发过程中,可以在不改变程序结构的前提下,实现这一部分的检测功能。
	
	\item 健壮性 \par
	 系统应具有应对非法操作的能力,并且当针对于本系统的恶意攻击到来时,可以及时防御,防止自身特征库遭到损坏。
	\end{enumerate}
	
\section{系统方案}
	 本系统由两部分构成,第一部分是产品部分,即~Android~应用程序,采用~Java~作为编程语言。第二部分是检测算法模型构建部分,采用~Matlab~实现,其输出的模型数据供产品部分作为特征库使用。故本系统的特征库构建于~PC~端,而对目标程序的检测运行于~Android~端。从而将构建过程中包含的巨大计算量留在~PC~端。其具体结构如图~\ref{system}~所示。
\pic[htbp]{系统结构}{height=5.86cm}{system}

	 其中程序信息抽取模块是本系统检测恶意软件的基础,特征检测模块是系统的核心与实现难点。特征检测模块中又分为变种检测模块和模糊检测模块,变种检测模块检测待检软件是否是已知恶意软件的变种,而模糊检测模块实现的是本系统从人脸匹配中引入的新型检测手段,可对特征库中不存在的未知恶意软件进行检测。
	
\section{系统模块的实现}
	\subsection{程序分解模块}
		
		 Android~的程序文件为~APK~格式,APK~文件是~Android~最终的运行程序,是~Android~Package~的全称。类似于~Symbian~ 操作系统中~sis~文件,APK~文件其实是~Zip~文件格式,但后缀名被修改为~APK。通过解压,可以看到~Dex~ 文件。Dex~是~Dalvik~VM~executes~的全称,即~Dalvik~虚拟机可执行文件,并非~Java~ME~的字节码而是~Dalvik~字节码。\\
		一个APK文件结构为:
		\begin{enumerate}
		\item META-INF$\backslash$————签名信息,用来保证~apk~包的完整性和系统的安全,jar~文件经常可以看到;
		\item res$\backslash$————资源文件夹,包括程序中使用的图片,布局文件等;
		\item AndroidManifest.xml$\backslash$————项目配置清单,但不是明文的XML格式,无法直接打开阅读;
		\item classes.dex$\backslash$————Dalvik~可执行二进制文件,在运行时被动态优化为dey文件并由Dalvik虚拟机解释执行	 ;
		\item resources.arsc$\backslash$————编译后的二进制资源文件,资源文件打包而成,字符串值(源码中的/value/Strings.xml)就在其中;
		\item lib$\backslash$————动态链接库文件;
		\item assets$\backslash$————原始文件文件夹,其中的文件不会被压缩,也不能像~res~目录下的资源文件一样通过资源类引用。
		\end{enumerate}\par
		 图~\ref{apk}~是我们解压缩helloworld.apk文件后看到的内容,可以看到其结构跟工程结构有些类似。
		
\pic[htbp]{helloworld.apk的结构}{width=0.5\textwidth}{apk}

		
		 classes.dex~文件是~Java~源码编译后生成的~Java~字节码文件。但由于~Android~使用的~Dalvik~虚拟机与标准的~Java~虚拟机是不兼容的,Dex~文件与~Class~文件相比,不论是文件结构还是~opcode~都不一样。目前常见的~Java~ 反编译工具都不能处理~Dex~文件。Android~SDK~中提供了一个~Dex~文件的反编译工具~dexdump。用法为,dexdump -d -f -h  xxx.dex。
		\\
		指令参数解释:\\
		-d : 反编译程序段\\
		-f : 从文件头显示摘要信息\\
		-h : 显示文件头详情\\
		-C : 反编译低级符号名\\
		-S : 只计算大小 \par
		 在知道了程序安装包是~Zip~编码之后,我们就可以通过遍历~Zip~包中包含的项目名,找到程序的二进制文件,即~Dex~文件。并在内存中建立一段缓冲区,可将~Dex~文件读入内存,再写到指定的临时文件中。分解流程如图~\ref{flow1}~所示。
	
\pic[htbp]{程序分解流程}{height = 5.76cm}{flow1}	
		
	\subsection{构建特征向量模块}
		 特征向量是数据挖掘中的一个概念,一个数据集中的每个数据实例都可以用一组属性值来描述,每一个数据实例都具有一个特殊的目标属性,称为类属性,它表征每个数据实例归属的类。这一组属性值即是代表这个数据实例的特征向量。在我们的检测问题中,Android~系统~API~和~Java~标准函数就是我们定义的属性,而恶意和非恶意就是类属性。这一过程如图~\ref{flow3}~所示。
		
\pic[htbp]{构建特征向量流程}{height = 0.5\textwidth}{flow3}	
		
		 我们将特征向量空间($\Omega$)存储在数据库中,数据表的定义见表~\ref{omegatable}~所示。

\threelinetable[htbp]{omegatable}{0.8\textwidth}{llllX}{$\Omega$~数据表定义}
{字段&主键&类型&是否为空&备注\\
}{
ID&是&Int&NOT NULL&特征向量维度序号\\
MethodName&否&Text&NOT NULL&函数名\\
}{\item
}

		 构造特征向量时,先初始化一个全为0的特征向量,然后利用SQL查询语句确定代表某一函数名的维度序号:\\
		select ID from Omega where MethodName = “待查函数名”;\\
		 并将特征向量($\omega$)的第~ID~位设置为1。见式(\ref{omegai})。
		\begin{equation}\label{omegai}
		\omega_i =
		\begin{cases}
		1 & i = ID \\
		0 & else
		\end{cases}
		\end{equation}
	\subsection{特征库构建模块}
		 特征库构建模块实现于~PC~端,恶意样本来自各大权威机构公布的数据,详见第\pageref{omegai}页\ref{omegai}小节,其流程如图~\ref{flow5}~所示,特征库数据模型构建方法如下:
		
\begin{pics}[htbp]{特征库构建流程}{flow5}
  \addsubpic{KNN特征库构建流程}{width=0.3\textwidth}{flow5-1}
  \addsubpic{K-L~变换矩阵构建流程}{width=0.3\textwidth}{flow5-2}
  \addsubpic{LDA~投影矩阵构建流程}{width=0.3\textwidth}{flow5-3}
\end{pics}

		\begin{enumerate}
		\item 最近邻居(KNN)算法\par
		 KNN~算法的特征库就是恶意程序样本的特征向量集合,我们将这些特征向量存储到数据库中。
		
		\item 主成分分析(PCA)算法\par
		 考虑到文献\citeup{wangang1912}\citeup{zhaokaihua1995}中的适用条件,由于我们的特征向量维度远大于样本数量,所以需要去掉冗余数据,使训练数据矩阵为可逆矩阵才能使用线性判别分析(LDA)算法。

		 PCA~方法主要是通过对协方差矩阵进行本征分解,以得出数据的主成分(即本征矢量)与它们的权值(即本征值)。PCA~ 提供了一种降低数据维度的有效办法;如果分析者在原数据中除掉最小的本征值所对应的成分,那么所得的低维度数据必定是最优化的(也即这样降低维度必定是失去信息最少的方法)。

		 我们的目标是把高维的数据集~$\Omega_B$~和~$\Omega_M$~变换成具有较小维度的数据集~$Y_B$~和~$Y_M$。$Y_B$~和~$Y_M$~是矩阵~$\Omega_B$~和~$\Omega_M$~的~Karhunen–Loève~变换(K-L~变换)。即~$\mathbf{Y}=\mathbb{KLT}\{\mathbf{X}\}$。\\
		计算特征向量平均值见式(\ref{mean})。
		\begin{equation}\label{mean}
		u=\dfrac{1}{N} \sum_{\omega \in \Omega_B \cup \Omega_M} \omega
		\end{equation}
		 从~$\Omega_B$~和~$\Omega_M$~中减去平均值~$u$~见式(\ref{Omega_u})。
		\begin{equation}\label{Omega_u}
		\begin{split}
		B & =\begin{vmatrix}\Omega_B \\ \Omega_M \end{vmatrix}-hu\\
		  & \text{其中h是全为1的列向量。}
		\end{split}
		\end{equation}
		求协方差矩阵~C~见式(\ref{getC})。
		\begin{equation}\label{getC}
		C=B \cdot B^T
		\end{equation}
		 计算~C~的特征值和特征向量,提取不为0的特征值所对应的特征向量,构成~K-L~变换矩阵~W。\\
		 所以,$Y_B$~和~$Y_M$~可由式(\ref{ybym})计算。
		\begin{equation}\label{ybym}
		\begin{split}
		Y_B &= \Omega_B \cdot W \\
		Y_M &= \Omega_M \cdot W
		\end{split}
		\end{equation}
		
		最后我们将~K-L~变换矩阵~W~存储在数据库中。
				
		\item Fisher~线性判别分析(LDA)\par
\threelinetable[htbp]{ldaparameterdeftable}{\textwidth}{lXlX}{LDA算法变量定义}
{变量&定义&变量&定义\\
}{
        $S_b$ 	& 样本类间离散度矩阵 & $x$		& 一个程序\\
		$S_i$ 	& 样本类内离散度矩阵&$X_M$	& 恶意程序集合\\
		$S_w$ 	& 总类内离散度矩阵&$X_B$	& 非恶意程序集合\\
		$W$   	& 投影方向向量&$y_M$ 	& 恶意样本的投影值 \\
		$J_F(W)$& Fisher~准则函数&$y_B$ 	& 非恶意样本的投影值\\
		$M$		& 恶意(Malice)的缩写&$y_0$ 	& 识别阈值点\\
		$B$		& 非恶意(Benign)的缩写&&\\
}{
\item
}

应用统计方法解决模式识别问题时,一再碰到的问题之一是维数问题。在低维空间里解析上或计算上行得通的方法,在高维空间里往往行不通。因此,降低维数有时就成为处理实际问题的关键。在数学上总是可以把高维空间样本投影到一条直线上,形成一维空间,即把维数压缩到一维。但是投影方向有无数种,若把样本投影到一条任意的直线上,可能使几类样本混在一起无法区分,如图~\ref{fisher1}~所示。。但在一般情况下,总可以找到某个方向,使在这个方向的直线上,样本的投影能分开得最好,如图~\ref{fisher2}~所示。。 问题是如何根据实际情况找到这条最好的、最易于区分的投影线。这就是~Fisher~法所要解决的基本问题。\par

\begin{pics}[htbp]{Fisher~线性判别基本原理}{fisher}
  \addsubpic{最优方向投影}{width=0.4\textwidth}{fisher1}
  \addsubpic{K-L~任意方向投影}{width=0.4\textwidth}{fisher2}
\end{pics}

		 描述~LDA~算法前,首先定义几个基本变量,变量定义见表~\ref{ldaparameterdeftable}。LDA~算法步骤如下:

		\begin{enumerate}
		\item 计算样本均值向量~$m_i$:
		\begin{equation*}
		m_i=\dfrac{1}{N_i}\sum_{y \in Y_i}y ~~~~,i=B,M
		\end{equation*}
		\item 计算样本类内离散度矩阵~$S_i$~和总类内离散度矩阵~$S_w$:
		\begin{align}
		S_i & = \sum_{y \in Y_i}(y-m_i)(x-m_i)^T ~~~~,i=B,M\\
		S_w & = P(x|x \in X_B)S_B + P(x|x\in X_M)S_M
		\end{align}
		\item 计算样本类间离散度矩阵~$S_b$:
		\begin{equation*}
		S_b=P(x|x \in X_B)P(x|x\in X_M)(m_B-m_M)(m_B-m_M)^T
		\end{equation*}
		$P(x|x \in X_B)$~和~$P(x|x\in X_M)$~是恶意程序和非恶意程序的先验概率,根据目前~Android~市场的情况,我们取~$P(x|x\in X_M)=0.001$。
		\item Fisher准则函数为:
		\begin{equation}
		J_F(W) = \dfrac{W^T S_b W}{W^T S_w W}
		\end{equation}
		 为求函数取极大值时的~$W^*$。可用拉格朗日乘数法,定义拉格朗日函数为:
		\begin{equation*}
		\dfrac{L(W,\lambda)}{W} = S_bW-\lambda S_w W
		\end{equation*}
		另偏导数为零,得
		\begin{equation*}
		S_b W^* = \lambda S_w W^*
		\end{equation*}
		 其中~$W^*$~就是~$J_F(W)$~的极值解。因为~$S_w$~可逆,等式两边左乘~$S_w^{-1}$,可得
		\begin{equation*}
		S_w^{-1} S_b W^* = \lambda W^*
		\end{equation*}
		所以求~$W^*$~即求矩阵~$S_w^{-1} S_b$~的特征值问题。在我们这个特殊情况下,只有两种类别,故
		\begin{equation*}
		S_b W^* = (m_B-m_M)(m_B-m_M)^T W^*
		\end{equation*}
		 其值为一标量,所以对~$W$~投影方向无影响。忽略这个标量的比例因子可得,
		\begin{equation*}
		W^* = S_w^{-1} (m_B-m_M)
		\end{equation*}
		\item 求出~$W^*$~后即可计算:
		\begin{align}
		y_M & = mean(W^*T \cdot Y_M) \\
		y_B & = mean(W^*T \cdot Y_B) \\
		y_0 & = \dfrac{m_B+m_M}{2}  +  \dfrac{\ln (P(x|x\in X_B)/P(x|x\in X_M))}{N_B+N_M-2}
		\end{align}
		 最后将LDA变换矩阵~$W$、$y_M$、$y_B$、$y_0$保存在数据库中。
		\end{enumerate}	
		\end{enumerate}
\section{本章小结}
本章介绍了~AFace~系统的实现细节,它是一个由~Android~端和~PC~端两部分组成的系统。我们首先介绍了系统的设计原则。然后介绍了我们在此原则下设计的检测流程及其背后的检测原理。最后,作为一款完整的产品,还介绍了系统的产品软件架构以及产品的界面设计。