Facebook对崩溃软件错误的进化搜索

2018-06-17 15

Facebook网站及其应用程序每天拥有13亿用户,是世界上使用最多的软件。只有少数软件公司,包括微软、Google和苹果,进入了类似的无处不在的梯队。无论好坏,这就是我们现在生活的世界,我们很大一部分醒来的时间都花在与软件交互上——而Facebook则领先,平均每天50分钟的用户主要是看视频和喜欢婴儿照片。电视是世界上唯一比Facebook更受关注的休闲活动。别忘了Facebook现在也拥有Instagram和WhatsApp。

那么,Facebook非常关心软件的质量是可以理解的。如果Facebook推出带有崩溃错误的Android应用程序新版本,数百万用户可能会受到影响。这些用户可能倾向于切换到另一个社交网络,甚至更糟:放下电话,与现实世界互动。无论是哪种方式,净效果都是一样的: Facebook在你的注意力中所占的份额,以及潜在的收入,都会减少。这就是为什么Facebook有一些先进的错误发现工具——包括一个非常聪明的动态分析工具,最初由伦敦大学学院的学生设计,然后由Facebook伦敦办事处获得并进一步开发。这是他们第一次向媒体展示这种被称为Sapienz的新工具的内部工作原理。

静态与动态分析进一步了解安全漏洞的工作原理:缓冲区溢出这是自动分析软件的两种方法,用于查找错误、安全漏洞和其他潜在问题。顾名思义,静态分析只对程序的源代码感兴趣。动态分析正好相反:你运行程序,给它提供一堆输入,并记录它的行为。

每种技术都有不同的用途,大型软件公司通常会同时使用这两种技术。静态分析非常适合于正式验证算法是否按预期工作,或者突出显示可能导致缓冲区溢出或其他安全漏洞的错误代码。动态分析更有利于发现导致碰撞的粗糙边缘情况。当然,人类可以手动执行这两种分析,但在测试数百万可能的输入时,计算机显然要快得多。

Facebook的静态分析器称为推断。该公司在2013年开放了该工具,许多大公司(优步、Spotify、Mozilla )都在使用它。除了看起来很受欢迎和有效之外,没有什么可说的了;立即下载!

根据Facebook,Sapienz进一步阅读Microsoft推出的“fuzzing - as - service”,以帮助开发人员发现安全漏洞。有很多动态分析器,但没有一个像Sapienz一样。动态测试的最大问题是找到导致应用崩溃的正确输入。Facebook表示,一些动态分析器只是在应用程序中随机输入序列,在崩溃之间有多达1.5万个输入事件。另一方面,sapienz只需要大约100 - 150个事件就能找到崩溃的错误。实际上,这意味着Facebook在更短的时间内发现了更多的崩溃错误。

Sapienz有三个主要的诀窍。首先,它使用基于搜索的进化算法,而不是随机或基于模型的方法。其次,指导算法如何进化的适应度函数非常复杂:有多个目标,被帕累托最优结合在一起,每一次进化变化都必须满足这些目标才能获得成功。第三,Facebook可以在一个世界测试平台上运行Sapienz,让工程师可以同时在数百个不同的Android设备上发现崩溃的错误。( Sapienz目前只支持Android应用程序,但计划扩展到其他平台和应用程序类型。)

让我们把这些点按顺序拆开,因为它们都在Sapienz的功效中起着重要作用。大多数现有的动态分析器要么向应用程序抛出随机输入,要么使用某种模型:一组由外部知识通知的测试用例,如应用程序的头文件或配置文件。sapienz使用一种进化算法,呃,根据应用程序对早期输入的实际响应来进化测试输入,希望能更有效地发现崩溃案例。

进化算法成功的关键在于它的适应度函数。我不是你的大学计算机科学讲师,所以我不会讲太多细节,但是健身功能本质上是查看测试用例的结果,并决定该结果与期望的结果/目标有多接近。不具备健身功能的结果被绑在麻袋里扔到河里;好的一起培育,形成下一次rou的基础第二次测试。根据Facebook工程师的说法,他们的秘密酱料大部分都在Sapienz的健身功能中,它有三个目的:尽可能多地测试应用程序的方法和语句,尽可能多地发现崩溃,并最小化导致崩溃所需的测试序列长度。前两个都是关于生产更好的、没有崩溃的软件;三是提高系统效率,在合理的时间内找到大量的死机。

这三个目标由帕累托效率的适应度函数评估。也就是说,一个目标并不比其他目标更重要:如果进化算法只产生长的测试序列,但是它们提供了良好的覆盖,并且发现了大量崩溃,那么这些长的测试将保持有效。随着时间的推移,系统试图达到帕累托最优:在这种情况下,不可能在不负面影响另一个目标的情况下改进一个目标。因此,在这种情况下,该算法将尝试减少测试序列长度,而不减少覆盖或故障揭示。

Sapienz还做了一些其他聪明的事情,比其他分析者更能找出更多的崩溃。许多自动分析器使用原子事件——也就是说,仅仅是上下文无关的输入流。不过,应用程序要比这复杂得多:你做一件事(尝试上传一个图像),然后在同一上下文中做另一件事(选择一个图像)。为了测试更复杂的交互,Sapienz使用基序模式(低级原子事件的分组),这些基序模式源自应用程序使用的各种UI元素。

Sapienz还略微跨越边界进入静态分析:它试图对应用程序(本例中为Android APK )进行逆向工程,以提取一些字符串,然后在测试开始时将其用作自然语言输入。研究人员说:「我们发现这种种子在测试需要大量使用者产生内容的应用程式时特别有用,例如Facebook,因为它让Sapienz能够以明显更具人情味的方式张贴和评论。」

按Adobe Stock

列出图像页面:下一步12→)