Exploring Multiple Execution Paths for Malware Analysis
(S&P’07)
Abstract
恶意代码（或恶意软件）被定义为满足攻击者故意有害意图的软件。恶意软件分析是确定给定恶意软件样本（例如病毒，蠕虫或特洛伊木马）的行为和目的的过程。该过程是开发有效检测技术和消除工具的必要步骤。目前，恶意软件分析主要是一个繁琐且耗时的手动过程。为了缓解这个问题，已经提出了许多分析工具，它们通过在受限环境中执行并记录被调用的操作系统调用来自动提取未知程序的行为。
动态分析工具的问题是只能观察到单个程序的执行。然而，遗憾的是，某些恶意行为可能仅在特定情况下触发（例如，在某一特定日期，某个文件存在时或收到某个命令时）。在本文中，我们提出了一个系统，它允许我们探索多个执行路径，并识别仅在满足某些条件时执行的恶意操作。这使我们能够自动提取正在分析的程序的更完整视图，并确定在何种情况下执行可疑行动。我们的实验结果表明，许多恶意软件样本根据从环境读取的输入显示不同的行为。因此，通过探索多个执行路径，我们可以获得更完整的行动图。
1 INTRODUCTION
恶意软件是用于描述各种恶意软件（例如，病毒，蠕虫或特洛伊木马）的通用术语。恶意软件不仅对计算机用户及其数据的安全性和隐私构成严重威胁，而且还造成大量财务损失。不幸的是，恶意代码的问题可能在未来继续增长，因为恶意软件编写很快就会变成一个有利可图的业务[26]。恶意软件的作者将他们的创作卖给了歹徒，然后他们使用恶意代码来破坏大量在所谓的僵尸网络中链接在一起的机器。然后，这些僵尸网络被滥用作为发起拒绝服务攻击或垃圾邮件中继的平台。问题重要的一个重要标志是，即使对计算机没有任何特殊兴趣的人也会发现CodeRed或Sasser等蠕虫。这是因为安全事件影响了数百万用户，并且经常成为主流新闻来源的头条新闻。
防范恶意代码的最重要防线是病毒扫描程序。这些扫描程序通常依赖于表征已知恶意软件实例的签名数据库。每当在野外发现未知的恶意软件样本时，通常需要相应地更新签名数据库，以便扫描引擎可以检测到这种新颖的恶意软件。为此，能够快速分析未知恶意软件样本并了解其在系统中的行为和影响非常重要。此外，有关恶意软件功能的知识对于删除它很重要。也就是说，为了能够有效地从受感染的机器中删除一块恶意软件，通常不足以删除二进制文件本身。通常，还必须删除恶意代码留下的残留物（例如不受欢迎的注册表项，服务或进程）并撤消对合法文件所做的更改。所有这些操作都需要详细了解恶意代码及其行为。 分析未知程序行为的传统方法是在受限环境中执行二进制文件并观察其操作。受限制的环境通常是一个调试器，人类分析师使用它来手动逐步执行代码以了解其功能。不幸的是，反病毒公司每天都会收到多达数百个新的恶意软件样本。显然，无法完全手动执行这些恶意软件样本的分析。
在迈向自动化解决方案的第一步中，提出了许多动态恶意软件测试系统。这些系统，如CWSandbox [29]，Norman Sand-Box [25]，TTAnalyze [2]或Cobra [28]自动将待分析的样本加载到虚拟机环境中并执行它。程序运行时，会记录与操作系统的交互。通常，这涉及记录调用哪些系统调用及其参数。自动分析的结果是一个报告，显示程序创建或访问的操作系统资源（例如，文件或Windows注册表项）。有些工具还允许系统连接到本地网络（甚至是Internet）并监控网络流量。通常，生成的报告为人类分析人员提供样本行为的概述，并允许他们快速决定是否需要更接近的手动分析。因此，这些自动化系统使分析师无需浪费时间在已知的恶意软件上。此外，一些工具已经部署在Internet上，并作为蜜罐安装（如Nepenthes [1]）的实时分析后端。不幸的是，当前的分析系统也存在一个明显的缺点：它们的分析仅基于单个执行跟踪。也就是说，它们的报告仅包含在某个特定测试环境中某个时间点运行样本时观察到的相互作用。不幸的是，这种方法有可能错过程序在不同情况下可能表现出来的很大一部分行为。
恶意软件程序经常包含检查，用于确定计算机上是否存在某些文件或目录，并且只在它们执行时运行部分代码。其他人则要求建立与Internet的连接或者不存在特定的互斥对象。如果不满足这些条件，恶意软件可能会立即终止。这类似于检查虚拟机环境的指示的恶意代码，如果存在这样的指示则修改其行为以便使其在虚拟环境中的分析更加困难。每次运行时未调用的其他功能是恶意软件例程，这些例程仅在特定日期或某个时间执行。例如，Bagle蠕虫的一些变体包括一个检查，它会在某个日期之后完全停用蠕虫。另一个例子是米开朗基罗病毒，它大部分时间都处于休眠状态，只在3月6日（这是米开朗基罗的生日）提供其负担。当然，功能也可以由其他条件触发，例如用户名或本地网络接口的IP地址。最后，某些恶意软件会侦听某些必须在启动活动之前通过控制通道发送的命令。例如，自动登录到IRC服务器的机器人通常会监视通道以获取触发某些有效负载例程的关键字列表。
当从一次运行确定程序的行为时，可能无法观察到许多先前提到的动作。这可能导致人类分析师对某些样本的风险得出错误的结论。更糟糕的是，当代码在早期检查时失败并立即退出时，生成的报告可能根本不会显示任何恶意活动。解决此问题的一种可能性是尝试增加测试覆盖率。这可以通过在不同环境中运行可执行文件来完成，可能使用各种操作系统版本，已安装的应用程序和数据/时间设置。不幸的是，即使在虚拟机的帮助下，创建和维护这样的测试系统也可能成本很高。此外，对每个样本执行数百次测试效率不高，尤其是因为许多环境变化对程序执行没有影响。此外，在恶意代码期望某些命令作为输入或检查非标准文件的存在（例如，先前利用可能已经创建的文件）的情况下，实际上不可能触发某些动作。
在本文中，我们提出了一个解决测试覆盖问题的解决方案，它允许自动化恶意分析系统生成更全面的报告。基本思想是我们探索被测程序的多个执行路径，但是通过监视代码如何使用某些输入来驱动对不同路径的探索。更确切地说，我们动态跟踪程序读取的某些输入值（例如来自操作系统的当前时间，文件内容或检查Internet连接的结果）并识别执行中输入的点用于制定控制流量决策。确定此类决策点后，我们首先创建程序执行当前状态的快照。然后，允许程序沿着一个执行分支继续，具体取决于实际输入值。稍后，我们返回快照并重写输入值，以便获取另一个分支。这允许我们探索两个程序分支。此外，我们可以确定执行某些代码路径的条件。
举一个简单的例子，考虑一个检查文件是否存在的程序。在执行期间，我们跟踪检查该文件是否存在的操作系统调用的结果。当该结果稍后由程序在条件分支中使用时，我们存储当前执行状态的快照。例如，假设文件不存在，程序快速退出。此时，我们将进程回退到先前存储的状态并重写结果，以便报告文件的存在。然后，我们可以探索程序在文件存在的情况下执行的操作。
我们为Microsoft Windows开发了一个系统，允许我们动态执行程序并跟踪它们读取的输入。 此外，我们已经实现了一种机制来捕获执行进程的快照，然后恢复到以前存储的状态。 这为我们提供了探索恶意软件程序执行空间和观察传统恶意软件分析环境无法看到的行为的方法。 为了证明我们的方法的可行性，我们分析了大量真实的恶意软件样本。 在我们的实验中，我们能够根据某些文件的存在来识别保护损坏程序和不同行为的时间检查。 此外，我们能够自动为机器人提取许多命令字符串及其相应的操作。
总之，本文的贡献如下：
- 我们提出了一种动态分析技术，使我们能够创建有关恶意代码行为的综合报告。为此，我们的系统探索了多个程序路径，这些路径由程序处理的输入驱动。此外，我们的系统会报告触发特定操作的输入条件集。
- 我们开发了一种工具，通过在基于虚拟机的环境中执行它们来分析Microsoft Windows程序。我们的系统跟踪用户输入，并可在控制流决策点创建当前流程的快照。此外，我们可以将运行进程重新设置为先前存储的状态，并不断修改其内存，以便探索替代执行路径。
- 我们在大量现实恶意软件样本上评估了我们的系统，并证明我们能够识别在单个执行跟踪中无法观察到的行为。
2 System Overview
本文中描述的技术是对现有自动恶意软件分析系统的扩展[2]。该工具基于Qemu [3]，一种快速虚拟机仿真器。使用Qemu仿真Intel x86主机系统，安装了Windows 2000客户机操作系统。 Windows和英特尔x86架构的选择受到以下事实的推动：恶意软件的主要部分是为此平台开发的。分析的工作原理是将（恶意软件）程序加载到模拟的Windows环境中，开始执行，然后监视其活动。为此，分析工具分析由二进制文件调用的所有操作系统调用。对于每个系统调用，分析工具记录所请求的服务类型和相应的参数。根据执行期间观察到的系统调用，生成一个报告，总结安全相关的操作。这些操作目前包括创建和修改文件、Windows注册表项，进程间通信和基本网络交互。
现有的分析工具实现了一些虚拟机器内省功能;特别地，它能够将由仿真处理器执行的每个指令归因于客户系统的操作系统进程（或内核）。这允许我们仅跟踪由分析中的代码调用的那些系统调用。此外，系统提供了一种机制来复制复杂数据结构的内容，这些内容可以包含指向进程虚拟地址空间中其他对象的指针，从Windows客户系统到主机系统。这很方便，以便能够将系统调用参数从仿真系统复制到分析环境中。不幸的是，现有系统只收集了一条执行跟踪。
Multiple Execution Paths:为了解决单个执行跟踪通常只产生完整程序行为的一部分的问题，我们扩展了分析工具，以便探索多个执行路径。目标是获得许多不同的执行路径，并且每个路径可能揭示一些在其他跟踪中无法观察到的特定行为。分支点的选择 - 即程序执行中的两个备选延续是感兴趣的点 - 基于程序处理输入数据的方式。更确切地说，当控制流决策基于先前通过系统调用读取的某个输入值时，程序采用一个分支（这取决于具体检查的结果）。在这一点上，我们问自己以下问题：如果输入是另一个分支，可以观察到哪种行为？
为了回答这个问题，我们标记了程序感兴趣的某些输入，并在执行期间动态跟踪它们的传播。类似于其他作者在以前的工作[12,23]中使用的污点信息的传播，我们的系统监视这些输入值被过程移动和操纵的方式。每当我们基于标记值检测到控制流决策时，就存储过程地址空间的当前内容。然后，执行继续正常进行。当该过程稍后希望终止时，它会自动重置为先前存储的快照。这是通过用先前存储的值替换进程地址空间的当前内容来完成的。此外，我们重写控制流决策中使用的输入值，以便反转该决策的结果。然后，该过程继续沿着另一个分支执行。当然，有可能遇到连续的多个分支。在这种情况下，通过以深度优先顺序选择连续点来探索执行空间。
有关如何探索程序的多个执行路径的示例，请考虑图1.请注意，尽管此示例在C代码中显示（为了使其更容易遵循），但我们的系统直接在x86二进制文件上工作。执行程序时，它首先接收一些输入并将其存储到变量x（第1行）。请注意，因为x被认为是有趣的，所以它被标记。假设在这个具体的运行中，存储到x中的值是2.在第2行，它被比较为0.此时，我们的系统检测到涉及标记数据的比较操作。因此，创建了当前进程的快照。然后，允许该过程继续。因为满足条件，所以采用if-branch并记录x必须大于0的事实。在第3行，下一次检查失败。但是，由于比较再次涉及标记数据，因此会创建另一个快照。这一次，进程在else-branch上继续，并且即将调用exit。因为仍有未探索的路径（即，存在两个尚未访问的状态），所以该过程恢复到先前的（第二个）状态。我们的系统检查第3行的比较并尝试重写x以使检查成功。为此，必须遵守附加约束x> 0。这会产生x等于1的解.x的值更新为1并重新启动进程。这次，调用第4行的print语句。当进程即将在第5行退出时，它将重置为第一个快照。这次，系统搜索未通过第2行检查的x的值。因为没有x的附加约束，所以选择了一个任意的非正整数，并且该过程沿着else-branch继续。这次，允许退出调用，并且分析过程终止于报告，该报告指示在输入x为1（但不是0或2）的条件下发出了对打印的调用。
Consistent memory updates.不幸的是，当重写某个输入值以探索替代执行路径时，通常不足以改变控制流决策所使用的单个存储器位置。相反，有必要一致地更新（或重写）进程地址空间中与输入相关的所有值。原因是原始输入值可能已被复制到其他存储器位置，甚至被程序用作以前计算的一部分。仅修改输入的单个实例时，原始值的副本可能保留在程序的数据部分中。这可能导致执行无效操作或探索不可能的路径。因此，每当重写输入值时，必须保持程序状态一致并适当地更新输入的所有副本，以及涉及该值的先前操作的结果。此外，在为特定输入选择替代值时，我们可能没有完全的自由度。例如，在先前的比较操作中可能已经使用了输入，并且在选择可以在分支点处恢复控制流决策的值时需要观察所得到的约束。甚至可能没有有效的替代值可以导致探索替代路径。因此，为了能够一致地更新和输入及其相关值，有必要跟踪哪些存储器位置取决于某个输入以及它们如何依赖于该值。
3 Path Exploration
为了能够探索多个程序路径，需要两个主要组件。 首先，我们需要一种机制来确定我们的系统应该何时分析两个程序路径。 为此，我们跟踪程序如何使用来自某些输入源的数据。 其次，当找到一个有趣的分支点时，我们需要一种机制来保存当前的程序状态，并在以后重新加载它以探索替代路径。 以下两个小节将更详细地讨论这两个组件。
3.1 Tracking Input
在传统的基于污点的系统中，知道某个存储位置取决于一个或多个输入值就足够了。为了获得这些信息，这类系统通常依赖于三个组件：一组污点源，一个影子存储器，以及传播污点信息的机器指令的扩展。
污点源用于最初将标签分配给感兴趣的某些存储器位置。例如，Vigilante [11]是一个基于污点的系统，可以检测通过网络传播的计算机蠕虫。在该系统中，网络被认为是污点源。结果，操作系统从网卡读取的每个新输入字节都接收新标签。需要影子存储器来跟踪在某个时间点将哪些标签分配给哪些存储器位置。通常，阴影字节用于物理机器内存的每个字节。此影子字节存储当前附加到物理内存位置的标签。最后，当操作操作或移动标记数据时，需要对机器指令进行扩展以传播污点信息。最常见的传播策略可确保操作的结果接收操作参数的标签的并集。例如，考虑添加机器指令，将常数值10添加到存储位置M1并将结果存储在位置M2。在这种情况下，系统将使用影子存储器查找附加到M1的标签并将该标签附加到M2。因此，在操作之后，位置M1和M2共享相同的标签（尽管它们的内容不同）。
原则上，我们依赖于之前描述的基于污点的系统来跟踪分析中的程序如何处理输入值。也就是说，我们有许多污点源，它们为程序读取的输入分配标签，我们使用影子存储器来跟踪分配给每个存储器位置的当前标签（包括处理器寄存器）。我们系统中的污点源主要是系统调用，它返回我们认为与恶意代码行为相关的信息。这包括访问文件系统的系统调用（例如，检查文件是否存在，读取文件内容），Windows注册表和网络。此外，返回当前时间或网络连接状态的系统调用很有趣。每当我们的程序调用相关函数（或系统调用）时，我们的系统会自动为接收此函数结果的每个内存位置分配一个新标签。有时，这意味着标记了一个整数。在其他情况下，例如，当程序从文件或网络读取时，标记完整的返回缓冲区，每个字节使用一个唯一标签。
Inverse Mapping. 除了将内存位置映射到标签的影子内存之外，我们还需要逆映射。逆映射为每个标签存储当前保存该标签的所有存储器位置的地址。当进程重置为先前存储的状态并且必须重写某个输入变量时，需要此信息。原因是当修改具有特定标签的存储器位置时，必须同时更改具有相同标签的所有其他位置。否则，过程的状态变得不稳定。例如，考虑在标记输入x的值最终存储在存储器位置y之前多次复制的情况。此外，假设y被条件分支用作参数。要探索备用执行分支，y的内容必须改变了。但是，通过一系列中间位置，该值最终取决于x。因此，需要适当地修改所有中间位置。为此，需要一个映射来帮助我们快速识别当前共享相同标签的所有位置。
为了强调一致的内存更新的重要性，请考虑图2中的示例。假设第1行上的函数读取输入是污点源。因此，当程序执行该函数时，变量x被标记。在我们的示例中，程序最初读取值0.当调用检查例程时，变量x的值被复制到参数魔术中。作为此分配的一部分，变量magic接收x的标签。当稍后在第7行的检查中使用魔法时，将获取当前状态的快照（因为条件分支的结果取决于标记值）。执行继续但在第8行快速终止。此时，该过程将恢复为先前存储的快照，并且我们的系统确定必须将magic的值重写为0x1508才能获取if分支。此时，新值必须传播到共享相同标签的所有其他位置（在我们的示例中，变量x）。否则，程序将错误地在第3行上打印0而不是0x1508。
Linear dependencies. 在前面的讨论中，初始输入值在被用作控制流决策中的参数之前被复制到新的存储器位置。在这种情况下，重写此参数意味着必须使用相同的值更新共享相同标签的所有位置。但是，到目前为止，我们还没有考虑过初始输入不是简单复制，而是在计算中用作操作数的情况。使用上面简述的直接污点传播机制，带有标记参数的操作的结果接收该参数的标签。当操作的结果具有与参数不同的值时，也会发生这种情况。不幸的是，这会在快照点重写变量时导致问题。特别是，当不同的内存位置共享相同的标签但保持不同的值时，不能简单地用一个新的值覆盖这些内存位置。
我们通过为涉及标记参数的任何操作（不同于复制）的结果分配新标签来解决此问题。此外，我们必须记录新标签的值如何取决于旧标签的值。这是通过创建一个新约束来实现的，该约束捕获旧标签和新标签之间的关系，具体取决于操作的语义。然后将约束添加到约束系统中，该约束系统作为进程执行状态的一部分保留。考虑一个简单的例子，其中带有标签l0的值被add操作使用，该操作通过常量10增加该值。在这种情况下，操作的结果接收新标签l1。另外，我们记录了使用l1的操作结果等于由l0加10标记的值的事实。即，约束l1 = l0 + 10被插入到约束系统中。当两个标记的输入（一个标签为l 0，另一个标签为l1）相加时，该方法的工作方式类似。在这种情况下，结果接收新标签l2并且l2 = l0 + l1。
在我们当前的系统中，我们只能模拟输入变量之间的线性关系。也就是说，我们的约束系统是一个线性约束系统，它可以在{cn * ln + cn-1 * ln-1 + … + c1 * l1 + c0}的形式中存储项，其中ci是常数。这些术语可以通过相等或不等式运算符连接。为了跟踪标签之间的线性相关性，必须扩展负责加法，减法和乘法的机器指令的污点传播机制。
使用线性约束系统提供的信息，可以通过线性关系正确更新依赖于输入值x的所有存储器位置。考虑条件控制流决策使用带有标签ln的值的情况。为了探索这个决定的替代分支，我们必须重写标记值，以便恢复条件的结果。为了始终如一地这样做，我们首先使用线性约束系统来识别与ln相关的所有标签。这为我们提供了内存位置与ln有某种联系的信息，因此也必须更新。在第二步中，线性约束求解器用于确定这些存储器位置的具体值。
两个标签ls和lt与（a）当它们在同一约束中一起出现时或（b）当存在标签{li0，…，lin}序列时相关，使得ls = li0，lt = lin，和li，li +1∀n-1出现在同一约束中。 i = 0更正式地说，相关的二元关系是二元关系的传递闭包出现在同一约束中。因此，当标签ln的值应该重写时，我们首先确定与约束系统中的ln相关的所有标签。然后，我们提取包含至少一个与ln相关的标签的约束。然后使用线性约束求解器（我们使用Parma多面体库）来解决这组约束。
当约束系统没有解决方案时，不能更改标记值，以便恢复条件的结果。在这种情况下，我们的系统无法探索备用路径，并继续存储下一个快照。另一方面，当找到解决方案时，可以直接使用此解决方案来持续更新过程状态。为此，我们可以为每个标签直接使用求解程序确定更新相应内存位置的值。这是有效的，因为值之间的所有（线性）依赖关系都由约束系统中的相应约束编码。也就是说，约束系统的解决方案尊重必须在存储器位置之间保持的关系。共享同一标签的所有内存位置都会收到相同的值。但是，正如预期的那样，当内存位置具有不同的标签时，它们也可以接收不同的值。这些值遵循先前由过程执行的操作引入的关系，并由约束系统中的相应约束捕获。
为了说明值之间的线性依赖关系的概念并显示约束系统如何捕获它们的依赖关系，请考虑图3.该示例显示了执行简单atoi函数时引入的标签和约束。此函数的目标是将字符串转换为此字符串表示的整数值。对于此示例，我们假设函数在具有三个字符的字符串str上执行;前两个是等于数字0的ASCII字符（即30）。第三个值为0并终止字符串。我们假设有趣的输入被读入字符串;结果，第一个字符str [0]具有标签l0，str [1]具有标签l1。
该图显示了程序变量和标签之间的初始映射。对于这个初始状态，尚未确定任何约束。在第一次循环迭代之后，可以看出变量c和sum也被标记。这是由第7行和第8行的操作产生的。变量之间的关系由两个约束捕获。因为在此循环迭代之前sum为0，所以变量sum和c保持相同的值。这由约束l 3 = l2表示。请注意，此示例略有简化。原因是由第5行的while语句执行的检查导致创建额外的约束，以确保str [0]和str [1]的值在30（ASCII值为’0’）之间和39（字符’9’的ASCII值）。此外，由于检查对标记数据进行操作，因此系统会为每个检查创建快照，并尝试稍后探索其他路径。对于这些备用路径，字符串元素被重写为不表示数字的字符。在这些情况下，while循环将立即终止。
在该示例中，程序在第二次循环迭代之后到达第11行的检查。给定str的原始输入，此时sum为0，并采用else-branch。但是，因为此条件分支涉及标记为l6的值sum，所以会创建当前程序状态的快照。稍后恢复此快照时，我们的系统需要使用值82来重写sum，以便能够采用if-branch。为了确定如何一致地更新程序状态，约束系统解决了l 6 = 82.可以找到该系统的解决方案（l0 = 38，l1 = 32，l2 = l3 = 8，l4 = 80，和l5 = 2）。使用映射，此解决方案确定如何一致地修改相关的内存位置。正如所料，str [0]和str [1]分别设置为字符’8’和’2’。变量c也设置为2。
No-linear dependencies. 先前讨论的atoi函数表示可以用线性关系捕获的更复杂的示例。但是，程序也可能执行不能表示为线性约束的操作。这些操作涉及例如按位运算符，例如和，或者或者将输入值用作表的索引的查找。在非线性关系的情况下，我们当前的系统不能推断为标签分配适当的值，以便可以根据需要重写某个存储位置。因此，只要操作在标签l i和lj之间创建非线性依赖关系，当任何与li或lj相关的标签应该被重写时，我们就不能再一致地更新状态。为了解决这个问题，我们维护一个N集，它跟踪所有属于非线性依赖关系的标签。无论何时应重写标签，都要确定所有相关标签。如果这些标签中的任何一个在N中，则不能一致地改变状态并且不能探索替代路径。
3.2 Saving and Restoring Program State
上一节解释了我们在程序执行期间跟踪输入值传播的技术。依赖于某些有趣输入的每个内存位置都有一个附加标签，约束系统决定了不同标签的值如何相互关联。基于此信息，可以探索执行空间中的多个路径。为此，我们的系统监视使用一个（或两个）标记参数的条件操作的程序执行。当识别出这样的分支指令时，创建当前过程状态的快照。
当前执行状态的快照包含正在使用的完整虚拟地址空间的内容。另外，我们必须存储当前映射和约束系统。但在允许该过程继续之前，还需要一个额外的步骤。在此步骤中，我们必须确保考虑条件操作本身。原因是无论实际采用哪个分支，此条件操作都会对标记参数的可能值范围强制实施约束。我们将此约束称为路径约束。必须记住路径约束，并在稍后重写标记值（进一步沿执行路径）的情况下将其考虑在内。否则，我们可能会创建不一致的状态或达到不可能的路径。当采用条件的if分支时（即，对于当前标记值，它的计算结果为true），条件直接用作路径约束。否则，当遵循else分支时，必须在将条件添加到约束系统之前反转条件。为此，我们只是采取条件的否定。
例如，回想一下我们在图1中显示的第一个程序。该程序使用两个检查来确保在调用print函数之前x> 0且x <2。当在第2行到达第一个if语句时，将创建状态的快照。因为x的初始值为2，所以该过程沿if分支继续。但是，我们必须记录if-branch只能在标记值大于0时才采用的事实。假设x的标签是l0。因此，适当的路径约束l0> 0被添加到约束系统。在第3行的下一次检查中，将创建另一个快照。这次，采用了else分支，并且我们将路径约束l0> = 2添加到约束系统（由于else分支，它是条件检查x <2的否定）。当进程即将在第5行终止时，它将重置为先前存储的状态。这次，必须采用第3行的if-branch。为此，我们将路径约束l 0 <2添加到约束系统。此时，约束系统包含两个条目。一个是刚添加的约束（即，l 0 <2）。另一个源于第一次检查并且要求l0> 0.当分析这些约束时，我们的求解器确定l0 = 1.结果，x被重写为1并且程序继续调用打印。
当程序状态恢复时，我们系统的第一项任务是加载以前保存的程序地址空间内容，并用存储的内容覆盖当前值。然后，加载保存的约束系统。与采用第一个分支的情况类似，在跟随备用分支时也需要添加适当的路径约束。为此，最初使用的路径约束是相反的（也就是说，我们将其否定）。此新路径约束将添加到约束系统，并启动约束求解器。找到解决方案后，我们使用所有相关标签的新值以一致的方式重写相应的内存位置。如前所述，当没有找到解决方案时，无法探索替代分支。
请注意，在程序执行期间的任何时刻，约束系统的解空间都会指定标记输入可能具有的所有可能值，以便在程序执行中达到此点。该信息对于确定表现出某些行为的条件非常重要。例如，考虑我们的分析观察应该包含在可疑行为报告中的操作系统调用。在这种情况下，我们可以使用约束系统的解决方案来确定标记输入可以用于达到此调用的所有值。这有助于了解触发某些恶意行为的条件。例如，考虑一个在某个日期之后停用自身的蠕虫。通过我们的分析，我们可以找到表现出恶意行为的程序路径。然后我们可以检查约束系统以确定在何种情况下采用该路径。这会产生当前时间必须在某个日期之前的信息。
4 System Implementation
我们实现了上一节中介绍的概念，以探索Windows二进制文件的执行空间。 更确切地说，我们扩展了之前的恶意软件分析工具[2]，能够自动标记感兴趣的输入源并使用标准污点分析跟踪它们的传播（例如，在[12,23]中实现）。 此外，我们实施了持续保存和恢复程序状态的机制。 这使我们能够自动生成比原始工具更完整的恶意行为报告。 报告还包含在何种情况下观察到特定行为的信息。 在本节中，我们将描述和分享我们认为对读者感兴趣的实施细节。
4.1 Creating and Restoring Program Snapshots
我们的系统（和原始分析工具）建立在系统仿真器Qemu [3]之上。因此，保存程序执行状态的最简单方法是保存完整虚拟机的状态（Qemu已经支持此功能）。不幸的是，在分析样本时，必须创建许多快照。保存完整虚拟机的映像会花费太多时间和资源。因此，我们需要一种机制来仅拍摄过程图像的快照。为此，我们开发了一个Qemu组件，可以识别在客户操作系统（在我们的例子中是Microsoft Windows）中执行的进程的活动内存页面。这是通过分析属于Windows进程的页表目录来完成的。由于Qemu是PC模拟器，因此我们可以完全访问模拟机器的物理内存。因此，我们可以访问Windows内核数据结构并执行与Windows内存管理代码相同的计算，以确定属于正在分析的进程的某个虚拟地址的物理页面。一旦我们确定了为我们的流程进行内存映射的所有页面，我们只需复制那些被标记为有效的内容。此外，在创建流程快照时，我们必须复制虚拟CPU寄存器，影子存储器和约束系统。
上述方法具有一个限制。我们不能存储（或重置）在磁盘上分页的内存。这种限制源于这样一个事实：尽管我们可以从外部访问完整的主内存，但我们无法读取虚拟硬盘上的内容（不了解如何实现Windows文件系统和交换）。因此，我们必须禁用交换并阻止客户操作系统将内存页面移动到无法再访问它们的磁盘。在我们的实验中，我们发现这种限制不是问题，因为我们的恶意软件样本具有非常适度的内存需求，并且从未超过客户操作系统的256 MB主内存。
要重置进程以使其从先前保存的快照继续，我们使用类似于存储执行状态的过程。首先，我们确定属于我们感兴趣的过程的所有映射页面。然后，对于之前保存的每个页面，我们使用存储的内容覆盖当前内容。页面恢复后，我们还将虚拟CPU重置为其保存状态。请注意，进程可能分配的页数多于拍摄快照时的页数。当程序从操作系统请求额外内存时就是这种情况。当然，这些新页面无法恢复。幸运的是，这没有问题，也没有改变过程的行为。原因是现在指向新内存区域的原始页面中的所有引用都将恢复为它们在快照时（当新页面尚不存在时）所具有的值。唯一的问题是新分配的页面在进程中丢失，但仍被操作系统使用。例如，当探索不同的执行路径时，各种时间执行存储器分配例程时，这种“存储器泄漏”可能成为问题。虽然我们从未在实验中遇到过问题，但一种可能的解决方案是将代码注入释放内存的客户操作系统。
一个重要的观察是，只有在用户模式下执行时，才能将进程重置为先前存储的状态。当进程正在执行内核代码时，将其还原回用户模式状态会使Windows内核使用的数据结构处于不一致状态。当操作系统执行中断处理例程时也是如此。通常，在不处于用户模式时重置进程会导致崩溃或冻结系统。
我们当前的实现允许我们可靠地将进程重置为先前的执行状态。 但是，在拍摄或重新存储快照时，必须考虑内核状态。 特别是，我们必须解决在拍摄快照后资源可能返回到操作系统的问题。 当我们稍后恢复到之前存储的快照时，资源已经消失，并且它的任何句柄都是陈旧的。 例如，在创建快照后关闭文件时可能会发生这种情况。 为解决此问题，我们从不允许进程关闭或释放从操作系统获取的任何资源。 为此，每当应用程序调用NtClose函数或尝试将已分配的内存返回给OS时，我们都会拦截该函数并立即返回到用户程序。 从操作系统的角度来看，没有句柄被关闭。 因此，当进程重置为旧状态时，旧句柄仍然有效。
4.2 Identification of Program Termination
我们的方法的目标是在尽可能多的不同执行路径上获得程序活动的综合日志。因此，在恢复到先前存储的状态之前，通常允许该过程一直运行直到它正常退出或崩溃。当然，我们的系统不允许进程实际终止。否则，客户操作系统从其内部数据结构（例如，调度程序队列）中移除与进程相关的条目并释放其内存。在这种情况下，我们将失去将图像恢复为我们之前拍摄的快照的可能性。
为了防止程序正常退出，我们忽略了对NtTerminateProcess系统服务函数的所有调用（由ntdll.dll库提供）。这是通过检查模拟CPU的程序计数器是否等于NtTerminateProcess函数的起始地址来完成的。只要被调用的进程调用此函数，我们就会假设它希望终止。在这种情况下，我们可以将程序恢复为以前的快照（如果还剩下未探索的路径）。
分段错误（即非法存储器访问）是我们拦截的程序终止的另一个场所。为此，我们挂钩页面错误处理程序，并在发生页面错误时检查模拟CPU的状态。如果检测到无效的内存访问，则该过程将还原为存储的快照。有趣的是，无效的内存访问相对频繁地发生。原因是在路径探索期间，我们经常遇到确保指针不为空的检查。为了探索替代路径，指针被设置为任意非空值。稍后取消引用此值时，很可能会引用未映射的内存区域，从而导致非法访问。
通常，我们会遇到恶意代码根本不会终止的情况。 例如，传播例程通常实现为无限循环，不会停止扫描易受攻击的目标。 在这种情况下，我们不能简单地结束分析，因为我们将无法分析其他可能有趣的路径。 为了克服这个问题，我们为系统探索的每条路径设置了一个超时（目前为20秒）。 每当超时到期时仍然执行路径，我们的系统将等待，直到过程处于安全状态，然后将其恢复为之前的快照（直到没有剩余未探索的路径）。 因此，攻击者也不可能通过在无限循环中以未使用的执行路径插入代码来阻止我们的分析。
4.3 Optimization
程序中经常出现的一种结构是字符串比较。通常，通过在两个字符串中的相应字符之间执行成对相等性检查的序列来比较两个字符串。当其中一个字符串（或两者）被标记时，这可能会导致问题。请注意，每个字符比较都在标记的参数上运行，因此是一个分支点。因此，当将带有n个字符的标记字符串与另一个字符串进行比较时，我们会创建n个状态。状态si：0≤i≤n中的每一个表示两个字符串的前i个字符匹配的情况，而具有偏移i + 1的两个字符不同。出于实际目的，我们通常不需要这种详细的分辨率来进行字符串比较。原因在于，大多数情况下，程序仅区分两个字符串相等或不相等的两种情况。为了解决这个问题，我们实施了一种试图识别字符串比较的启发式算法。这是通过检查重复执行相同比较指令的情况来实现的，并且此比较的参数具有在每次迭代时增加1的地址。当这样的字符串比较被反对时，我们不会在每次检查时进行分支。相反，我们探索一个路径，其中第一个字符立即不同，第二个路径与两个字符串匹配。这种优化避免了必须以其他方式处理的总体状态数量的显着增加（通常不会产生任何附加信息）。
4.4 Limitations
在4.1节中，我们讨论了永远不会将任何已分配资源重新转换为操作系统的方法。目标是避免在进程首次关闭句柄时导致的无效句柄，然后将其重置为先前的快照（此句柄仍然有效）。在大多数情况下，我们的方法很有效然而，必须考虑过程创建外部效应的情况，例如，当写入文件或通过网络发送数据时。
程序写入文件时几乎没有问题。原因是文件指针存储在用户存储器中，因此，当进程恢复时，它会自动重置为先前的值。此外，如前所述，文件永远不会关闭。不幸的是，情况并不那么容易在处理网络流量时。考虑一个应用程序，它打开与远程服务器的连接，然后交换一些数据（例如，连接到IRC服务器的机器人）。恢复到先前状态时，应用程序和服务器之间的同步将丢失。特别是，当程序首先发出一些数据，稍后重置，然后再次发出这些数据时，远程服务器接收数据两次。通常，这会破坏协议逻辑并导致连接终止。在我们的当前实现中，我们按如下方式解决了这个问题：程序尝试建立连接或发送数据的所有网络系统调用都被截获，并且不会中继到操作系统。也就是说，对于这些调用，我们的系统只返回成功代码而不实际打开连接或发送数据包。每当程序尝试从网络读取时，我们只需返回一串所请求的最大长度的随机字符。这个想法是因为网络读取的结果被标记，我们的多路径探索技术稍后将确定触发某些动作的那些串（例如，发送到机器人的命令串）。
另一个限制是缺乏对信号和多线程应用程序的支持。目前，我们不会记录传递给流程的信号。因此，当发出信号时，这只发生一次。当该过程稍后恢复到先前状态时，不重新发送该信号。缺乏对多线程应用程序的支持本身并不是问题。为整个过程创建快照的工作与线程数无关。但是，为了确保确定性行为，我们的系统必须确保线程被确定性地调度。
特制恶意软件程序也可能通过阻止我们的系统探索某条路径来隐藏某些恶意行为。为此，程序必须确保分支操作依赖于通过非线性依赖性与其他值相关的值。例如，恶意代码可能故意将非线性操作（如xor）应用于某个值。当稍后在条件操作中使用该值时，我们的系统将确定它不能被重写，因为相关的存储器位置不能一致地更新。因此，不会探索替代分支。有两种方法可以解决这种威胁。首先，我们可以用一个可以处理更复杂关系的系统来替换线性约束求解器。例如，通过使用SAT求解器，我们还可以跟踪涉及按位运算的依赖关系。不幸的是，在分析专门设计用于经受我们分析的二进制文件时，我们的原型将永远无法正确反转所有相应的操作。一个例子是单向散列函数，我们的系统不能仅从散列值推断出原始数据。因此，第二种方法可以放宽一致的更新要求。也就是说，我们允许我们的系统通过重写内存位置来探索路径，而无法正确修改所有相关的输入值。这种方法可以提高分析代码的覆盖率，但是我们失去了在某条路径上驱动执行所需的输入知识。此外，由于状态不一致，程序可能执行不可能的操作（或简单地崩溃）。但是，我们系统无法解决的频繁出现的条件跳转可能会被解释为恶意攻击。在这种情况下，我们可以提出适当的警告并让人类分析师进行更深入的调查。
5 Evaluation
在本节中，我们将讨论通过在一组308个真实恶意代码示例上运行我们的恶意软件分析工具获得的结果。这些样本是由一家反病毒公司在野外收集的，涵盖了各种恶意代码类，如病毒，蠕虫，特洛伊木马和机器人。请注意，我们对收到的所有样本进行了实验，没有任何预选。
我们的测试集中的308个样本属于92个不同的恶意软件家族（在某些情况下，样本集中包括单个家族的几个不同版本）。我们使用viruslist.com上提供的免费病毒百科全书对这些恶意软件系列进行了分类。分析结果，我们发现42个恶意软件系列属于基于电子邮件的蠕虫类（例如，Netsky，Blaster）。 30个家庭被归类为基于漏洞的蠕虫（例如，Blaster，Sasser）。 10个恶意软件系列属于经典类型的文件传感器病毒（例如，Elkern，Kriz）。其余10个家族被归类为特洛伊木马和后门，通常与机器人功能相结合（例如，AceBot，AgoBot或rBot）。为了解我们的恶意软件实体有多广泛，我们检查了卡巴斯基2006年7月的前20个病毒列表，即我们收到测试数据的月份。我们发现我们的样本涵盖了此列表中的18个条目。因此，我们认为我们已经汇集了一套全面的恶意代码示例，涵盖了野外出现的各种恶意软件类。
在第一步中，我们的目标是了解哪些恶意软件使用有趣的输入来执行控制流决策。为此，我们必须定义适当的输入源。在我们当前的原型实现中，我们考虑表1中列出的函数来提供有趣的输入。这些功能的选择主要基于我们之前的恶意软件分析经验（以及与在反病毒公司工作的经验丰富的恶意软件分析师的讨论）。在过去，我们已经看到了使用其中一个函数提供的输出来触发操作的恶意代码。另外，请注意，如果需要，添加额外的输入源是微不足道的，并不是我们方法的限制。在分析期间，我们标记检查操作系统资源是否存在的函数的返回值。对于从资源（即文件，网络或计时器）读取的函数，我们标记返回的完整缓冲区（通过为每个字节使用一个标签）。
在对完整的308个真实恶意软件样本进行分析后，我们观察到这些样本中有229个使用了至少一个我们定义的受污染输入源。表1中显示了基于输入的使用情况细分。当然，从受污染源读取并不会自动暗示我们可以探索其他执行路径。例如，许多样本将他们自己的可执行文件复制到特定目录（例如，Windows系统文件夹）中。在这种情况下，我们的分析观察到文件被读取，并适当地污染输入。但是，受污染的字节只是写入另一个文件，但不用于任何条件控制流决策。因此，没有其他可供探索的计划途径。
在访问受污染源的229个样本中，172个使用一些受污染的字节来控制流量决策。在这种情况下，我们的分析能够探索其他路径并提取仅基于单个执行跟踪的动态分析未检测到的行为。通常，探索多个路径可以更全面地了解该代码的行为。然而，期望我们的分析能够总是提取有关计划行为的重要额外知识是不合理的。例如，多个恶意软件实例实现了一个使用互斥对象的检查，以确保只有一个程序实例同时运行。也就是说，当在第一执行路径上未找到互斥锁时，恶意软件执行其正常的恶意操作。当我们的系统分析替代路径时（即，我们假装互斥锁存在），程序立即退出。在这种情况下，我们只能通过特定互斥体的存在导致立即终止这一事实来增加我们的知识。当然，还有许多其他情况，其中附加行为很重要，并揭示了单个跟踪中不存在的隐藏功能。
表2显示了我们探索替代分支时恶意代码覆盖率的增加。更准确地说，该表显示了在考虑替代路径时我们的系统分析的基本块数量的相对增加。每个样本的基线是在我们的分析环境中简单运行样本时所涵盖的基本块的数量。对于少量样本（172个中的21个），新检测到的代码区域小于基线的10％。虽然这些10％可能包含与分析者相关的信息，但它们主要是由于探索错误路径而导致程序终止。对于剩余的样本（172个中的151个），代码覆盖率的增加超过10％，并且通常显着更大。例如，在分析Win32.Plexus.B蠕虫时，我们观察到的代码覆盖率增幅最大，为3413.58％。这是因为此示例仅在其文件名包含字符串upu.exe时才执行其有效内容。由于上传到我们的分析系统的样本不是这种情况，因此恶意软件有效负载仅在备用路径中运行。我们系统的有用性的轶事证据在下面的段落中提供，其中我们描述了替代路径揭示的有趣行为。然而，单独检查定量结果，很明显，野外几乎一半的恶意软件样本包含重要的隐藏功能，这些功能可通过简单的分析而遗漏。
行为分析结果。我们系统可以有效检测到的一类有趣的行为是仅在特定日期（或时间间隔）执行的代码。作为此类的示例，请考虑图4左侧显示的Blaster代码。此代码启动拒绝服务攻击，但仅在8月15日之后。假设Blaster在1月1日执行。在这种情况下，单个执行跟踪不会产生攻击的迹象。但是，使用我们的系统，会创建第一次检查if条件的快照。重置过程后，日期被重写为大于15.之后，系统还会通过月份检查，将月份变量更新为8或更大的值。因此，多个执行路径探索允许我们识别Blaster发起拒绝服务攻击的事实，以及它启动的日期。
我们的分析可以提供更完整的行为图像的另一个有趣的案例是恶意软件检查文件是否存在以确定它是否已经安装。例如，Kriz病毒首先检查系统文件夹中是否存在文件KRIZED.TT6。当此文件不存在时，病毒只会将自身复制到系统文件夹中并终止。仅当文件已存在时，才能观察到恶意行为。在这种情况下，执行单次执行运行的分析系统只能监视安装。
最后，我们的系统非常适合识别由网络接收或从文件读取的命令触发的操作。可以通过远程命令控制的一类重要的恶意软件是IRC（互联网中继聊天）机器人。启动时，这些程序通常连接到IRC服务器，加入频道，并监听聊天流量，以获取触发某些操作的关键字。现代IRC机器人通常可以理解超过100个命令，使得手动分析变得缓慢而乏味。使用我们的系统，我们可以自动化流程，并为每个命令确定触发的行为。相比之下，当在现有分析工具中运行机器人时，可能不会看到任何恶意操作，仅仅因为机器人从未接收任何命令。图4右侧的代码显示了bot rxBot命令循环的一个片段。此代码实现了一系列if语句，用于检查从IRC服务器接收的行是否存在某些关键字。分析此代码时，将标记从网络读取的结果（即数组a的内容）。因此，对strcmp函数的所有调用都被视为分支点，我们可以在每个不同的路径上提取一个命令的操作。
性能。我们系统的目标是为恶意分析师提供有关未知样本行为的详细报告。因此，性能不是主要要求。然而，对于某些程序，需要探索大量的路径。因此，不能完全忽略保存和恢复状态的时间和空间要求。
每当我们的系统创建快照时，它都会保存进程的完整活动内存内容。此外，状态包含来自影子记忆和约束系统的信息。在我们的实验中，我们确定状态的大小等于进程分配的内存量的大约三倍。平均而言，一个州的大小约为3.5 MB，并且从未超过10 MB。创建或重新存储快照所需的时间平均为4毫秒，差异很小（在具有3.4 GHz和2 GB RAM的Intel Pentium IV上）。如4.2节所述，为每个单独的程序路径的探索设置了20秒的超时。此外，我们为每个样品的完整分析运行设置了100秒的超时。引入了这个严格的额外时间限制，以便能够处理大量样本，以防某些恶意软件实例产生许多路径。在我们的实验中，我们观察到58％的恶意软件程序在超时发布之前完成。当分析过程终止时，剩余的42％的样品具有未开发的路径。因此，通过增加总超时，我们可以期望代码覆盖率比前面段落中报告的更大。权衡是需要更长的时间才能获得结果。
如果我们利用了影子内存中的大多数内存位置和条目为0的事实，那么状态的大小可以大大减少。此外，我们可以尝试创建仅存储当前状态和先前状态之间差异的增量快照。在理论上，并发活动状态的数量可以与遇到的分支点数一样高。然而，我们观察到通常不是这种情况，并且实验期间同时活动状态的数量较低。更确切地说，我们的系统平均使用31个并发状态（最大值为469）。请注意，这些数字也代表我们观察到的搜索树的平均深度和最大深度，因为我们使用深度优先搜索策略。州总数平均为32个，最多为1,210个。鉴于同时处于活动状态的数量，我们认为没有必要开发更复杂的算法来创建程序快照。此外，在综合基准测试中，我们验证了我们的系统可以处理超过一千个活动状态。
7 Conclusions
在本文中，我们提出了一个系统来探索Windows可执行文件的多个执行路径。目标是获得未知样本可以执行的操作的更全面的概述。此外，该工具可以自动提供触发恶意操作的环境信息。
我们的系统通过跟踪程序如何处理有趣的输入（例如，本地时间，文件检查，从网络读取）来工作。特别是，我们动态检查条件分支指令，其结果取决于某些输入值。当遇到这样的指令时，创建当前执行状态的快照。当程序稍后沿第一个分支完成时，我们将其重置为先前保存的状态并修改条件的参数，以便获取另一个分支。执行此重写操作时，一致地更新与参数值相关的所有内存位置非常重要。这是防止程序执行无效或不可能路径所必需的。
我们的实验表明，对于我们评估集中的恶意软件样本的重要部分，系统确实在探索多条路径。在这些情况下，与观察单次运行的系统相比，我们对程序行为的了解得到了扩展。我们还针对一些现实世界的恶意软件样本展示了我们的技术发现的操作揭示了有关恶意代码行为的重要且相关的信息。