[论文翻译]Why Software Hangs and What Can Be Done With It.docx

Why Software Hangs and What Can Be Done With ItXiang Song,Haibo Chen and Binyu ZangParallel Processing Institute,Fudan Universityxiangsong,hbchen,2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN)软件为什么会挂起及如何处理它摘要软件挂起是一种烦人的行为，它对很多软件系统的可靠性构成了主要威胁。为了在设计阶段避免软件挂起或在运行阶段修复它，我们需要了解它的特性。可惜，对于为何软件会挂起以及如何来处理软件挂起这些方面的问题，当前还没有进行过综合的研究。为了进一步认识软件挂起的特性，为了在第一阶段修复它或在产品运行时纠正它提供一些指导，在这篇文章中，我们研究了四款典型开源应用程序已报告的挂起相关的错误。1 前言软件可靠性对于服务器和用户应用程序至关重要，尤其是一些任务要求比较高的应用。可是，软件挂起这种无应答现象，仍然对软件可靠性构成主要威胁。这种错误存在于很多商业软件系统，比如web浏览器、数据库服务器和办公软件。大多数挂起相关的错误在正常运行时并没有明显的影响。然而，当他们出现时，用户将无法在期望时间内得到响应。更糟糕的是，一个严重的挂起错误可能会冻结整个系统，并导致重启。大部分以前的软件错误研究集中在特殊的系统，比如操作系统错误1和网络服务错误9。但他们都没有集中在软件挂起错误。虽然有几项研究涉及可能导致挂起的特殊原因，比如死锁错误3,4，无限循环，I/O阻塞错误13,10和并发性错误5，但还不清楚它们是否是主要的原因以及它们如何引起软件挂起的。在本文中，我们首次全面研究现实世界中的软件挂起错误。我们研究了四款流行的开源应用程序的挂起相关错误报告：MySQL，PostGre，Apache-httpd服务器和Firefox，它们都广泛使用于三层的浏览器-服务器架构中。我们总共收集307个已证实的挂起错误，分析了已知根源的233个错误（称为：确定根源错误）的特性。我们还检查了其余74个错误（称为：不确定根源错误），以便研究修复这些错误的障碍。我们的研究得到了以下的观察结果：l 应用程序不仅受已知挂起因素的影响，比如死锁、数据竞争、无限循，还受其他因素的影响，比如设计错误和执行环境。l 挂起错误根源的不确定性是修复错误的主要障碍，而可使错误重现的简洁的测试用例可以明显加快错误修正的进度。l 修复时间跨度研究表明，环境相关错误、无限循环错误和并发错误，与其他类型的错误相比，会持续更长时间。l 为了减轻挂起相关的错误，操作者应该在进行软件更新前检查协议的一致性，在运行应用程序前检查运行时的资源使用状况，在部署应用前仿真模拟运行环境。本文剩下的部分组织如下，第2部分主要讲了我们进行研究时所使用的错误调查方法。第3部分主要对软件挂起错误中的确定根源错误进行了全面分析。第4部分主要讲了如何修复错误。第5部分主要讨论了我们的观察结果，提出了一些避免软件挂起错误的建议。在第6部分，我们调查了相关的工作，并在第7部分总结了我们所做的工作。2 错误调查方法2.1 挂起错误的来源我们的研究选择了3个服务器端应用程序和1个客户端应用程序：MySQL、PostGre、Apache HTTPD server 和 Firefox。这些程序广泛应用于三层客服架构中，并且有着维护良好的错误数据库。在这些应用程序中，为处理多个请求，并行处理被广泛使用。我们相信这些应用程序中挂起错误的特性可以作为很多其他应用程序的代表。2.2 调查方法我们从这4个应用程序的错误数据库中搜集一些挂起错误。为了搜集到挂起相关的错误，我们使用了一些关键字比如挂起、无应答、冻结来进行搜索。在搜集到错误报告之后，我们亲自分析每一个错误报告的评论、测试用例、补丁和源代码，以确定它是否是一个挂起错误，并找出每个挂起错误的根源。我们也设法重现其中的几种错误，以便分析它们的特性。最后，我们总共研究了307个已证实的挂起错误。通常，我们把这些收集来的挂起错误分为两类：确定根源错误和不确定根源错误，二者的主要区别于能否找到错误根源。通过分类，我们得到了233个确定根源错误和74个不确定根源错误。详细的分类信息参见表格1。对于不确定根源的挂起错误，我们通过寻找用户和维护人员的证明或者手动实验使错误重现来证实它们是真正的挂起错误。应用程序描述确定根源错误不确定根源错误MySQL数据库9739PostGre数据库6115ApacheWeb服务器358FirefoxWeb浏览器4012总计23374表格 1：确定根源错误和不确定根源错误的分布3 错误分析对于确定根源的挂起错误，我们根据它们产生根源的不同，将它们再分成9个子类别。从表格2，我们可以看到确定根源错误的基本分类。在这部分，我们主要描述了每个子类别，并讨论了几个代表性的挂起错误。原因错误数量所占百分比配置135.58%设计3715.88%环境3916.74%无限循环3213.7%低效算法146.01%并行5423.2%用户操作错误208.58%内置插件125.15%其它125.15%总计233100%表格 2：9个子类别的错误分类3.1 错误分类配置 一个应用程序可以以不同的配置运行于各种各样的平台之上。粗心配置的软件可能会遇到严重的挂起错误，比如，一个配置错误的端口号会导致连接失败，使正在运行的MySQL集群被挂起。设计很大一部分挂起错误（15.88%）和设计问题相关。这些挂起错误是由应用程序设计错误、维护时的失误以及非预期的工作环境引起的。我们将在3.2.1节进行更详细的讨论。环境还有一些挂起错误是由应用程序运行所依赖的非预期环境引起的，这部分错误在确定根源错误中所占的比例超过了16%。我们将在3.2.2节进行详细讨论。无限循环 在这个类别中，主要是循环终止条件未能满足，导致CPU资源被消耗殆尽。这类错误在确定根源错误中占了13.7%。所以这也很重要的一个分类，我们将在3.2.3节进行详细讨论。低效算法这种问题和正确性问题无关，但是不管怎么样，一个有问题的算法的执行效率要比一个设计良好的算法的效率低上一个指数级。当一个有问题的算法在运行时，相关的操作会在一个较长时间内消耗大量的CPU和内存资源，就好象程序运行于一个无限循环中。并行为了充分开发现在多核架构的资源，现在的应用程序大部分都是多线程的。并行相关的错误多是由同步错误引起的，比如数据竞争、死锁，这部分在确定根源错误中占了23.3%，我们将在3.2.4节进行详细的讨论。用户操作错误这种类别的挂起错误是由用户操作失误引起的。对操作的错误理解以及操作的错误使用是引起这类问题的主要原因。例如，忘记确认执行中的事务会导致相关的事务被挂起。内置插件所有导致挂起错误的的内置插件和扩展都是通过Firefox的软件缺陷追踪工具发现的。有很多种不同的插件和扩展，比如Flash、Adblock、Adobe Acrobat Reader。调试这类错误需要用户、应用程序维护人员和插件及扩展开发人员的合作。这就增加了修复错误的复杂性。其它还有大概5%的其它4个类别的软件挂起错误：资源枯竭、资源泄漏、编程错误和内部结构崩溃。3.2 关键挂起错误分析大概70%的确定根源错误都属于设计、环境、无限循环和并行相关的错误。在这部分，我们会研究每个类别的主要特性，并提供几组研究示例。3.2.1 设计设计引起的挂起错误占总数的15.88%，我们会进一步将它们分为两个子类：设计和协议、异常输入。设计和协议在程序设计和维护过程中，有些程序片断将被添加、修改或删除，以修正错误、增加新的功能或提高性能。这时内部协议可能会改变，甚至被破坏，这将造成严重的挂起错误。更糟的是，这些副作用通常是很难发现和纠正的。最常见的情况是，一个组件出现故障，无法将所需的消息发送到另一个组件，使等待者挂起。图1展现了和协议破坏相关的错误示例。在MySQL中，所有在内部函数NAME_CONST中的参数都应该是常量表达式。但是当软件演化时，就会打破这种不变，导致客户端被挂起来，等待来自服务器的响应。应用程序：MySQL 5.0.40平台：FreeBSD描述：MySQL的内部函数NAME_CONST要求它所有的参数都是常量表达式，并将会在方法Item_name_const:fix-fields中进行检查。然而如果该函数的参数不是一个常数表达式，没有错误信息会报告给客户端。结果导致客户端一直挂起，等待来自服务器端的响应。图1：典型协议设计导致的挂起错误异常输入虽然许多软件系统通常用很多测试用例来验证期望输入，但是还会存在用例的覆盖范围问题，比如在一些不正常的情况下，一些合法但未经检验的输入，可能会导致程序进入一种未定义的状态，比如软件挂起。这种错误是难以察觉的，而当确定是输入错误时，就相对容易解决了。3.2.2 环境环境导致的挂起错误占了16.74%，我们根据它们所依赖的组件，将这些错误中的一些分为更细的子类别。表格3列出了这些类别和它们的分布。类型错误数所占百分比I/O连接断开512.82%模块依赖37.69%多线程支持37.69%资源不可用717.95%其它2153.85%总计39100%表格 3：环境相关挂起错误分布I/O连接断开手动拔出网络电缆、网络服务的关闭、集线器的处理错误以及其它意外事件都会引起这种错误。模块依赖模块是为软件的主要功能提供便捷扩展的一种典型方式。然而，如果模块和主要软件之间的交互设计的不好或模块有错误，这也会增加软件挂起的可能性。多线程支持这类问题主要在于对底层环境的多线程支持。一个著名的例子是thread_rwlock_unlock在glibc中的汇编代码错误。我们在MySQL的挂起错误报告中发现了它，同时在其他的软件如Redhat，Ubuntu等中也发现了类似的错误报告。资源不可用资源不可用是引起环境相关挂起错误的另一个重要来源。有两个例子是，由于缺少守护进程导致整个Apache httpd服务器挂起，一些丢失的文件导致PostGre初始化进程的挂起。不管怎么样，还有剩下53.85%的错误不能归于上面的分类，它们大部分和下面列出的整个执行环境相关。l 操作系统。l 仿真环境，比如PostGre中的Cygwin。l 后台运行的僵尸应用程序。l 网络环境，尤其是多级的http服务器。l 防火墙。3.2.3 无限循环无限循环引起的挂起错误占了13.7%，我们可以把它们分成以下三个子类别。不满足循环条件就像名字所说的那样，这类循环主要是由类似“while(true)”的无限循环引起。问题在于，循环终止条件不满足，导致不停的消耗CPU资源。环状链表对链表处理不慎很容易导致无限循环。当链表中的一部分为一个环，并且目标节点位于环外，若通过遍历环中节点来找到目标节点将导致程序无限循环。典型示例如图2。应用程序： MySQL 5.0平台：所有描述：在连接算法的视图函数mysql_make_view中，视图的子队列被插入select_lexslave(-next)*链中。如果连接有几个视图，多次增加同样的子队列，会在上面的链中形成一个循环，导致数据的多个部分被破坏。图2：环状链表引起挂起错误示例其它其它种类的无限循环挂起错误和上面的两种类型很相似，总会形成一个环，其中的一个例子是，在Firefox软件缺陷追踪工具中报告的自引用导致的挂起错误。3.2.4 并行这类错误占到了挂起错误的23.2%，现在的应用程序一般都是多线程的，这样可以更有效地利用现在的多核架构。由于使用更多的CPU核心，由并行导致的挂起错误也越来越严重，表格4总结了几个子类别的错误。类型死锁活锁竞争总计错误数32131358所占百分比59.26%24.07%16.67%100%表格 4：并行引起的挂起错误分布死锁有很多由死锁引起的挂起的例子，尤其是在数据库应用程序（MySQL和PostGre）修改表或连接数据库的过程中。尽管在过去的几年中出现了一些死锁检测机制，它仍然在挂起错误中占了明显的比重。活锁活锁一般不是由类似死锁的锁定情况引起的，有些甚至不需要一个单锁就可以产生，产生活锁有各种各样的原因：l 应用程序等待不存在的线程或者对象，而它们根本没有被创建或者已经被清除。l 应用程序等待某一消息，而该消息因为另一边的错误状态早已被发送过了。l 日志文件已满导致日志操作的阻塞。l 因权限不足导致的信号通知错误。竞争当使用多线程或多进程编程模型时，不同线程或进程之间的竞争很普遍。竞争相关的挂起错误通常由错误的的状态转移序列引起，比如事件传递序列错误和状态变化序列错误。重新执行是处理竞争问题的一个很好的方法。但是，与死锁不同，竞争挂起错误更复杂，原因如下：l 状态变量不如死锁明显。l 状态组合比锁更复杂。l 一种状态有多种表现形式。4 错误修复研究在这一部分，首先，我们会说明错误修复研究的策略；然后，我们会检验不确定根源错误，以说明错误根源的不确定性是修复错误的主要障碍；最后，我们会提出错误修复时间跨度的研究。4.1 修复策略在我们的研究中有几种不同的处理挂起错误的修复策略。l 补丁修复加入一个经过仔细测试的补丁。l 绕开错误代码移除错误代码或过滤错误条件。不过，这可能会牺牲应用程序的可扩展性和功能。l 不修复某些错误由于太复杂或功能太重要，不可被修复或绕过。唯一可做的事情是，通知用户特定错误的存在。l 更新最后的策略是用新的设计和实现来更新应用程序。通常不能发现错误根源时，尝试新的版本并期望错误被修复是唯一的选择。4.2 修复错误的障碍修复挂起错误的一个主要障碍在于错误如何发生、错误发生于哪里以及什么原因导致了错误的这些问题的不确定性。正如表格5所示，将近一半的错误没有被修复，这一点从错误报告中可以得出，而且只有约13.5%的错误可以通过补丁修复。补丁修复和快速修复是指错误可以通过补丁进行修复或者很快将在下一个版本中修复。虽然我们没有找到错误的原因，软件维护人员可能已经发现了引起错误的根源，在24个错误报告中有21个，我们已经找到重现错误的测试用例。版本修复的意思是挂起错误可以通过版本升级来修复，在有重现描述的11个错误报告中有8个，维护人员已经做出了反应，要么已经在版本中修复，要么即将修复。在剩余的6个错误中，有5个已经可以通过尝试新版本修复。不修复是指没有在错误报告中发现挂起原因，没有发现修复报告。它们只包含了挂起的确认消息和场景描述，只有12个错误报告提供了重现错误的步骤，而大部分是没用的。类别错误数可重现数所占百分比不确定 不修复331236.4%不确定 快速修复141285.7%不确定 补丁修复10990%不确定 版本修复17847.1%总计744155.4%表格 5：不确定根源类别分布既然不确定性是修复挂起错误的重要障碍，使错误重现的简洁的测试用例就成了加速错误修复过程的关键。4.3 修复时间跨度我们检查了160个确定根源挂起错误的修复时间跨度，而没有分析PostGre的错误的修复时间跨度，因为它的错误报告时间记录的不够好；我们也没有检查插件和扩展错误的修复时间跨度，因为它们通常不是由应用程序开发人员维护的。表格6列出了确定根源挂起错误8个子类别的平均修复时间跨度。原因天数配置74.10设计74.32环境147.46无限循环140.23低效算法96.50并行137.47用户操作错误85.64其它62.78表格 6：8个挂起错误子类别的平均修复时间跨度（我们忽略了两个大概需要2000天来修复的错误）有三个类别的挂起错误需要超过平均100天来进行修复，环境、无限循环和并行。尤其是竞争和管道（活锁的一部分）相关的挂起错误，它们都属于并行这个大类，占用更长的时间来进行修复（分别是213天和444天）。在竞争这一类8个错误中有3个甚至需要1.5年来修复，因为它们非常复杂，很难找到根源。5 从研究中吸取的经验在这一部分，我们提出了如何提高挂起错误修复进度的观察结果和建议。5.1 应用程序内部错误分布不同的应用程序通常有不同的用途、设计和实现策略。为了获得每个应用软件的挂起信息，我们在表格7中做了一般的总结。从表中，我们观察到了有4个主要的挂起错误贡献者，它们严重影响了4个应用程序的运行。不过应用程序也明显受到其它特定挂起错误的影响：l 数据库应用程序受到并行错误的影响，这类错误大概占了25%。l 在Apache HTTPD服务器中，环境相关的错误占了将近1/3。l Web浏览器Firefox，主要受低效算法的影响。原因MySQLPostGreHTTPDFirefox配置3.09%4.92%11.43%10.71%设计21.65%14.75%11.43%10.71%环境13.40%18.03%34.29%10.71%无限循环12.37%14.75%14.29%21.43%低效算法6.01%1.64%0%21.43%并行23.2%26.23%14.29%17.86%用户操作错误7.22%16.39%8.57%0%其它6.19%3.28%5.71%7.14%总计100%100%100%100%表格 7：挂起错误分布5.2 观察结果我们在研究过程中得到了一些有趣的关于软件挂起错误成因的观察结果。1. 很多挂起错误，尤其是无限循环、设计和竞争相关的错误，实际上和状态不连续相关。对程序员来说，如何在正确的时间保持正确的状态是一个关键问题。这也对研究人员开发实用的工具提出了挑战。2. TCP协议栈的改变和程序的升级所引起的不兼容可能会引起挂起错误和其它错误。一些被当作设计错误的挂起错误实际上是由不同组件的内部兼容性引起的，比如，请求处理不兼容。当现在的软件越来越复杂，并大量依赖于组件之间的合作，兼容性问题也越来越严重。3. 正如3.2.2和3.2.4节中所讨论的，资源不可用是挂起错误的一个主要原因，而不管不可用的原因是什么。在软件开发过程中，在运行之前检查运行时资源的可用性应该成为一个普遍的编程规则。4. 配置问题可能会引起软件挂起，这就需要程序员写出更好的自配置代码来根据运行环境调整软件的配置。5. 具有不同知识的用户可能对软件如何工作有不同的理解。重要的是要调整软件，并告诉用户如何正确使用软件。文档中应该有更多的关于软件关键部分的细节和要点。6. 正如3.2.3节提到的，链表容易引起挂起，而它又广泛应用于现在的软件，所以我们需要使用封装良好的接口来操作链表，以避免软件挂起。5.3 改进错误修复的方法以下是在我们研究的基础上提出的检测软件挂起和改进挂起错误修复的建议：1. 软件升级可能会带来不同组件之间通信协议的不兼容性，因此，在软件升级时需要加入通信协议一致性检查。2. 对于开发人员来说，提供足够多的不同执行环境下的测试用例是很重要的，这样可以减轻非预期环境引起的挂起错误。3. 运行时检查或者资源保障机制可以帮助避免资源相关的错误，比如检查底层的TCP栈来避免防火墙触发的堆栈不一致的问题。4. 设计配置脚本来满足尽可能多的软硬件组合，并且设计自配置工具来根据运行时环境作出调整。在各种各样软硬件平台上的仿真可以帮助在应用程序部署前提前检测到脚本错误。6 相关工作错误特性研究：目前在商业软件中已经有很多对其他类型错误的研究工作了，包括操作系统错误1、系统实用工具6、网络应用程序9和并行错误5。与这些研究相比，我们的研究是独一无二的，我们对软件挂起错误的特性做了综合的研究。错误分析和调试工具：关于分析和调试错误，已经有了很多的研究。在过去的10年中重现技术7,11已经被广泛的讨论。远程日志技术12也已应用于分布式系统和网络的错误分析。最近的工作也提出了软件的静态语义2一致性检查。这些技术都可以应用于调试一些软件挂起错误，比如并行、无限循环和设计相关的错误。挂起检测工具：在硬件和内核模块的帮助下，已经有了几个技术可以用于软件挂起8检测。大部分这样的方法是用探针检测技术，就像一个watchdog帮助检测系统的挂起。可是，在实践中很难确定10合适的延时。7 总结软件挂起是软件可靠性的一个严重威胁，在这篇文章中，我们从4款流行的开源应用程序入手，对它们的挂起相关的软件错误的特性进行了综合的研究。我们在研究中对错误类型进行了分类，提出了9类错误，它们是导致软件挂起的主要成因，其中设计、环境、无限循环和并行相关的错误是最主要的软件挂起贡献者。我们对错误修复的研究表明，一份良好的软件错误报告是加速挂起错误修复进度的关键。同时，在如何改善软件挂起故障修复过程方面，我们提供了一些观察结果，提出了一些建议。参考文献1 A. Chou, J. Yang, B. Chelf, S. Hallem, and D. Engler. An empirical study of operating systems errors. In Proc. SOSP, pages 73-88, 2001. 2 I. Dillig, T. Dillig, and A. Aiken. Static error detection using semantic inconsistency inference. In Proc. PLDI, pages 435-445,2007. 3 D. Engler and K. Ashcraft. RacerX: effective, static detection of race conditions and deadlocks. ACM SIGOPS Operating Systems Review, 37(5):237-252, 2003. 4 T. Li, C. Ellis, A. Lebeck, and D. Sorin. Pulse: a dynamic deadlock detection mechanism using speculative execution. In Proc. USENIX ATC, pages 3-3, 2005. 5 S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from mistakes:a comprehensive study on real world concurrency bug characteristics. ASPLOS, 2008. 6 B. Miller, L. Fredriksen, and B. So. An empirical study of the reliability of UNIX utilities. Communications of the ACM, 33(12):32-44, 1990. 7 P. Montesinos, L. Ceze, and J. Torrellas. DeLorean: Recording and Deterministically Replaying Shared-Memor