关于模糊哈希（Fuzzy Hashing）算法，目前网上有几篇中文资料介绍，但均不准确。写这篇文章以纠正，并对其原理和应用作详细的介绍。

一、概述

模糊哈希算法又叫基于内容分割的分片分片哈希算法（context triggered piecewise hashing, CTPH），主要用于文件的相似性比较。

2006年，Jesse Kornblum [1] 提出CTPH，并给出一个名为spamsum的算法实例。随后，Jason Sherman开发了ssdeep [2] 工具以实现这一算法。该算法最初用于取证，后来被用于恶意代码检测，最近又有用于开源软件漏洞挖掘等。

模糊哈希的主要原理是，使用一个弱哈希计算文件局部内容，在特定条件下对文件进行分片，然后使用一个强哈希对文件每片计算哈希值，取这些值的一部分并连接起来，与分片条件一起构成一个模糊哈希结果。使用一个字符串相似性对比算法判断两个模糊哈希值的相似度有多少，从而判断两个文件的相似程度。

对文件的部分变化（包括在多处修改、增加、删除部分内容），使用模糊哈希均能发现与源文件的相似关系，是目前判断相似性较好的一种方法。

Continue reading →

Android工程副总裁Hiroshi Lockheimer在Google移动官方博客发文称已经为官方市场的应用软件引入了恶意代码检测机制，地址是：

http://googlemobile.blogspot.com/2012/02/android-and-security.html

下面是对其中一段关键内容的翻译：

今天我们公开一个我们开发的服务，名为Bouncer。它提供了对Android市场上潜在恶意软件的自动化扫描服务，并且不影响Android市场的用户体验，也不需要开发者走应用软件批准流程。

该服务对Android市场的新增应用软件、已有应用软件、开发者帐号进行一些分析。它是这样工作的：当一个应用软件被上传后，该服务立即开始分析，判断其是否已知恶意代码、间谍件或木马；它还查找其中是否存在不当行为，并将其与之前分析过的软件进行比较以检测可疑点。事实上，我们将每个软件在Google的云设施上运行，模拟它们在Android设备上运行的情况，并观察是否有隐藏或恶意的行为。此外，我们还分析新增的开发者帐号以防止恶意代码出现、防止反复违规的开发者卷土重来。

文章称该服务已经在官方市场运行一段时间（可能是去年下半年开始的），并取得了较为显著的效果。

NCSU的蒋旭宪教授团队去年在Android恶意代码发现上做出了有目共睹的成绩。昨天看到论文“Hey, You, Get off of My Market: Detecting Malicious Apps in Official and Alternative Android Markets”已经在其首页上公开，仔细阅读了一遍。做笔记如下。

文章主要介绍了名为DroidRanger的系统，用于从官方市场、第三方市场抓取和发现Android中已知家族和未知家族。

已知家族的策略是：

1. 基于已知家族所需必要权限，对所有灰名单样本过滤。例如，bgserv需要internet和收发短信权限，这样能过滤掉98.42%的灰名单样本。但也有例外，比如ddlight的过滤效果不好，则加上一个特定intent的receiver的规则来过滤；basebridge没有特殊权限，则用native代码来过滤。这样，每个家族的规则都能将灰名单样本过滤到5%以下。

2. 基于行为的特征匹配。包括三个方面的行为特征：manifest里注册的组件及其intent；特定组件（例如接收短信的receciver）的代码解析，提取API调用序列（例如invoke了abortBroadcast）；代码结构布局（即Java的树形结构源文件，但没想明白在这里怎么提取特征）。

在已知方面，他们基于10个已知家族（每个家族2个样本）提取了权限过滤规则和行为检测规则，在官方市场和第三方市场的20万个灰名单样本中发现这10个家族共119个新样本。

在未知家族检测上，策略是：

1. 基于启发式特征的过滤。这里的启发式特征并不是统一的单点特征集，而是真正体现样本潜在行为的复杂特征。例如，样本使用DexClassLoader加载从远程下载的jar或dex代码（但大部分是第三方广告，用白名单过滤掉）；样本在非默认路径lib/armeabi加载执行本地native code（常用于执行提权代码）。在这种启发式特征过滤下，把灰名单样本数量过滤到了1%以下。

2. 基于动态运行的行为监控。主要在两个层面做，对动态加载的jar和dex，记录其API调用及参数，例如sendTextMessage及其参数；对动态加载的native code，记录其发生的敏感系统调用，例如sys_mount（用于remount文件系统，常用于提权后写入系统分区的自我保护）。最后人工对这些日志进行分析。

在未知上，该团队由此发现Plankton（第一个DexClassLoader的恶意代码，官方市场，远控）和DroidKungfu（使用大量本地提权工具）。

从后续情况看，AnserverB应该也是被这种启发式规则触发而发现的。

论文提到还可以有其它启发式的特征，例如向高额扣费号码发送短信；将短信内容当成控制指令等。去年下半年该团队发现的很多新家族均有短信扣费和拦截的特点，猜测确实使用了这些特征。

关于已知检测的漏报问题，论文用contagio的公开样本进行了测试，称无漏报。

文中还提供了其他数据，例如对20万个样本的处理速度等。

总的来看，论文对细节公开的非常充分，取得的效果也很明显，值得我们学习。

NSA在1月16日发布了基于SELinux的SEAndroid。项目主页是：

http://selinuxproject.org/page/SEAndroid

粗读了一下他们的幻灯片，主要意思如下：

1、要把SELinux系统及其设计思想移植到Android有不少困难，比如非标准Linux机制（Ashmem、Binder等模块）、Android框架层的策略、现有DAC权限控制模型、文件系统不支持安全标签等等，但SEAndroid项目最后解决了这些问题

2、对目前Android系统上发现的几乎所有提权漏洞、Android应用上发现的大量信息泄露漏洞，SEAndroid都能补上，主要是漏洞利用程序的利用步骤会被SEAndroid的安全策略所阻止，也就是无法顺利利用漏洞。

3、作者认为对Android，MAC模型是有意义的，并且可以和现有安全体系并存。

从RageAgainstTheCage、zergRush（幻灯片中称之为GingerBreak）这两个漏洞利用的阻止细节上，我觉得SEAndroid的安全做得比较理想，对权限的管理已经到了及其严格的地步，利用代码几乎寸步难行。

而这个项目目前存在什么问题，幻灯片中只字不提。我觉得，对性能的损耗可能是第一位的。

在去年看到的一篇论文中，有提到，即便是在Android所有敏感API的入口处基于源码做hook，记录API触发行为和参数，编译得到的系统的性能都有显著的降低，而这个降低的性能在真实机器上可能引发连锁效应，导致整个系统无法启动。

而SEAndroid从文件系统开始广泛使用标签，对每个需要管理的对象使用标签来实施安全策略，这里还包括对每个敏感行为的审计。我倾向于认为这样的改动也会遇到同样的问题。至于NSA有没有解决，是如何解决的，还需要进一步看细节。我会在年后使用他们提供的源码编译出一份可用的系统，在Nexus S上进行测试。

无论如何，这个项目值得我们进一步学习。