PDF在源头消除软件缺陷
SETH HALLEM、DAVID PARK、DAWSON ENGLER，COVERITY
源代码分析是软件行业中一项新兴技术，它允许在程序运行之前检测到关键的源代码缺陷。尽管在编译时检测编程错误的概念并不新鲜，但构建有效工具的技术长期以来一直未能进入市场，这些工具能够处理数百万行代码，并报告实质性缺陷，且仅有少量噪声。与此同时，为了应对软件行业当前的趋势，即传统软件测试和质量保证的有效性正在稳步下降，需要一种不同的解决方案。这些趋势包括：
- CPU性能的提高和内存成本的降低，这使得开发更大、更复杂的软件成为可能。
- 互联网的兴起，为大多数软件创造了一个不可预测的执行环境，并将安全风险附加到每个软件缺陷上。
- 嵌入式系统和软件服务的增长推动了对软件质量的更高要求。
源代码分析通过有效地搜索所有可执行路径上的编程规则违规行为来应对这些趋势。适用于自动化分析的规则类型涵盖了程序员长期以来已知且长期以来在没有任何开发工具帮助的情况下努力遵守的各种属性。
软件质量危机
美国国家标准与技术研究院（NIST）于2002年5月发布的一份报告1估计，美国软件缺陷造成的年度成本为595亿美元。每个在产品发布后才被检测到的缺陷，软件生产商可能需要花费数万美元来解决和修补。该产品的用户所遭受的损失通常要高出几个数量级。
这些天文数字成本的根本原因是当今软件日益增长的复杂性。在计算机发展的早期，存在严格的内存限制，通过限制代码大小来内在地控制复杂性。随着这些内存要求的消失和处理器性能的提高，对软件的要求也发生了根本性的变化。现代服务器端应用程序，如操作系统、应用服务器和数据库，通常包含数十万行，甚至数百万行的源代码。
当今网络计算世界的一个不幸的后果是，它为软件质量的经济影响贡献了第二个因素。一旦软件在网络环境中运行，实际上该软件中的每个错误都可能成为安全漏洞。如果外部人员有任何方法触发到该错误的特定代码路径，那么该错误至少是一个等待被发现的DoS（拒绝服务）攻击，甚至更糟。此类安全攻击的发生率在过去几年中呈指数级增长，美国超过十分之八的企业在过去一年中成为安全漏洞的受害者2。
虽然转向安全语言（例如，Java、.Net）缓解了构建安全软件的一些挑战，但这些环境仍然容易受到另一种阴险类型的安全漏洞的影响：不正确的外部人员验证，这允许未经授权访问私人信息。这个问题通常可以追溯到源代码中的错误，而分析工具可以检测到这些错误。随着Java系统部署在银行、保险公司和政府机构，不当信息访问的影响可能会变得非常昂贵。
第三个从根本上增加了软件质量经济影响的趋势是嵌入式设备的激增。在设备内部运行的软件通常带有持续正常运行时间的期望。由于这些期望，嵌入式设备的软件补丁成本非常高昂。除了嵌入式设备之外，通过互联网和企业内联网的连接普及已将这些高昂的补丁成本扩展到每个文件服务器、软件路由器、服务提供商以及更多期望在网络上持续运行的设备。一台大型计算机不再是唯一代价高昂的故障点。
软件行业正在通过将可靠性提升到前台来应对这些趋势。首先，冗余已经成为维护可靠性的直接但昂贵的权宜之计。许多流行的网站都由数百或数千台可互换的机器提供支持，这些机器可以重新启动，而不会显着影响整体流量模式。在某些情况下，机器会在短时间后有意重新启动，以避免软件中内存泄漏导致的病态性能问题（即，抖动）。
其次，可靠性保证正在成为竞争差异化的关键指标。包括Sun、惠普和IBM在内的供应商正在为其基础设施产品承诺高可用性，而Oracle则交付了“坚不可摧”的承诺3。这些给这些供应商带来了巨大的压力，要求他们交付更高质量的软件，并且在发生软件故障时，在短时间内开发有效的解决方法。
对自动化源代码分析的需求
2002年NIST的报告4估计，“可行的”测试基础设施改进可以将美国软件缺陷的年度成本降低222亿美元。可行改进与总成本595亿美元之间的差距反映了一个众所周知的事实，即没有任何解决方案可以找到任何大型软件项目中的所有错误。222亿美元的减少是基于软件质量行业当前研发趋势的经济可行性估计。
NIST报告中引用的具体改进分为两类：（1）在软件开发周期的早期，更接近错误引入点的位置检测错误，以及（2）通过更快、更精确地定位错误根本原因来降低修复缺陷的成本5。鉴于这种成本结构，不难看出自动化源代码分析的价值。源代码分析可以在代码编写完成后的编译时立即识别缺陷。此外，由于检测到的缺陷来源于代码本身，因此源代码分析器可以精确定位每个错误的位置和根本原因。
相比之下，将更多资源投入到传统测试中将导致收益递减，并且最终将无法跟上软件日益增长的规模和复杂性。软件测试的最佳实践采用工具集来管理和监控旨在在真实世界情况下执行软件的大型测试套件。管理工具包括测试生成器（主要用于Web应用程序）和测试用例管理工具。监控解决方案包括代码覆盖率工具，用于确定测试套件执行了多少百分比的代码，以及动态分析工具，用于检测代码以精确定位测试失败的原因（例如，Purify、Insure++、BoundsChecker）。虽然这些工具提高了软件测试的效率，但它们并没有解决由路径爆炸属性引起的基本挑战。
路径爆炸属性指出，通过程序的执行路径数量随代码行数呈指数级增长。即使在测试期间实现了100%的代码覆盖率，它仍然可能只占代码执行路径的一小部分。对于大多数大型商业软件，考虑软件将运行的所有场景是不可行的。实际上，即使所有测试场景都以某种方式神奇地枚举出来，手动执行和测试复杂程序中的每个可行路径通常也需要宇宙的寿命。
重要的是要注意，永远不会有一种技术可以完全取代传统测试。完全自动化诸如用户交互和业务逻辑等软件功能的测试是不可能的。但是，有大量关键缺陷可以在编译时自动检测到，并且超越了传统编译器捕获的语法错误。
此外，当一个属性适合源代码分析时，分析几乎总是比人工代码审查更有效地检查该属性是否未被违反。由于分析是在编译时而不是运行时完成的，因此它可以搜索代码中所有路径上的缺陷。许多这些路径既难以通过传统的运行时测试来执行，也难以让人在代码审查期间跟踪。将源代码分析添加到开发过程可以大大减少一类代价高昂的错误，这些错误以前是在集成测试期间或在现场检测到的。通过在开发人员的桌面上消除这些错误，测试组织可以完全专注于那些超出自动化工具范围的属性。
分析源代码
源代码分析的基本思想是在执行环境的显着简化模型中模拟代码的执行。就本次讨论而言，状态是一组反映正在运行的程序当前状态的值。状态包括内存中所有可访问的值、硬盘上所有相关的文件以及指令队列中的下一条指令。状态空间定义为所有可能状态的集合。显然，枚举硬盘、内存和指令队列中可能存在的所有可能值的集合将产生一个实际上无限的列表。这个观察结果是路径爆炸属性的一个可能的理由。
然而，源代码分析的关键见解是，对于任何特定的程序属性，并非构成状态的所有数据都是相关的。考虑图1中用C编程语言编写的示例函数。虽然我们的示例函数可以接受任意整数，但值为1表示指针p设置为地址0，而任何其他值表示相同的指针初始化为堆上可访问的内存块（假设对malloc的调用永远不会失败）。通常，尝试访问包含值0作为地址的指针将导致操作系统终止程序。
图1
说明指针的0地址属性的玩具代码示例
int test(int x) { int *pointer; if (x == 1) { pointer = 0; /* A */ } else { pointer = (int*) malloc(sizeof *pointer); /* B */ } if (!pointer) { printf(“Bad pointer. Should exit!”); /* C */ } else { *pointer = 10; } return *pointer; /* D */ }
如果我们正在分析源代码以检测此类非法访问，我们只关心程序中每个指针的两种可能状态：指针为0（空状态），指针不为0（非空状态）。将状态空间减少到这些可能性有效地将我们状态空间中的可能值从数十亿个值（32位）减少到两个值（1位）。与其通过对内存、硬盘等进行适当修改来评估程序中的每个语句，我们不如只关注每个可执行代码路径上的指针值。在图1中，有两条可执行路径，一条执行语句A、C和D，另一条执行语句B和D。语句A向我们的分析表明，“指针”随后在当前代码路径上为0。在语句D处，分析识别出对值为0的指针的非法解引用，并报告错误。在另一条路径上，语句B将一个有效的、可解引用的值分配给“指针”，我们在此函数中不报告错误。
虽然上面的示例可能看起来太简单，不可能存在于生产代码中，但图2中的示例直接取自Linux内核，说明即使是这些简单的缺陷类别在广泛部署的代码库中也很普遍（见图2）。虽然这种类型的错误通常在集成测试期间检测到，但源代码分析工具本可以在错误代码引入代码库之前检测到该错误。
图2
Linux 2.5.54开发内核中文件“drivers/net/pppoe.c”的代码片段
. . . if (!po) { int hash = hash_item(po->pppoe_pa.sid, po->pppoe_pa.remote); . . . } . . .
此代码片段显示了即使是最简单的NULL指针错误在经验丰富的程序员中也很常见。如果变量po为0，则表达式po->pppoe_pa.sid和po->pppoe_pa.remote在执行时都会使内核崩溃。如果发布，此错误将影响所有通过使用PPPOE的消费者DSL线路进行通信的Linux计算机。此错误已在Linux内核的最新发布快照中修复。
即使在这个简化的状态空间中，在所有情况下准确确定指针是否可以保存0值也是不可行的。在编译时彻底推断复杂的算术运算或非平凡的数据结构在理论上是不可判定的。因此，任何源代码分析工具都必须进行近似。
学术研究传统上侧重于完全验证。在这种情况下，验证器会做出这样的假设：每当不清楚指针是否具有值0时，最安全的做法是假设它确实具有值0并相应地报告错误。做出这种假设的分析通常会产生高达100甚至1,000个误报/真实错误报告的误报率。另一种假设是，每当分析无法确定指针是否为0时，最好假设指针不为0。这种假设可能会使分析遗漏某些类别的缺陷，但它会产生一个实用性更高的工具。根据我们的经验，具有良好启发式方法的工具仍然可以检测到很高比例的错误。
定义空间
通常，几乎任何可以用源代码术语表达的属性都可以转换为搜索违反该属性的分析。原型示例包括：
内存泄漏：每个指针都有一个关联的状态：已分配，表示指针引用必须返回给系统的已分配内存块；或未分配，表示指针不指向已分配的内存块。
文件句柄泄漏：每个文件句柄都有一个附加状态：已打开，表示句柄引用一个已打开的文件；或未打开，表示句柄不指向已打开的文件。
权限检查：某些操作必须受到所有可执行路径上的权限检查的保护，否则程序容易受到未经授权的访问。源代码分析可以检查调用进程的权限是否在执行受保护的操作之前得到正确验证。系统的状态是一个全局值，指示当前代码路径上的权限级别。状态空间只是所有可能的权限级别的列表。
缓冲区溢出：每个缓冲区都有一个附加状态，即该缓冲区的分配大小。每个索引变量都有一个附加状态，即该索引变量的值。
一旦状态空间被简化，软件错误就可以简化为以抽象空间指定的属性违规。例如，当局部定义的指针在某些代码路径上进入已分配状态，并且在封闭例程退出之前未能恢复到未分配状态时，就会发生内存泄漏违规。
通常，确定属性是否适合源代码分析的最简单方法是从识别违反该属性的代码片段开始。在现有产品中诊断出的错误或玩具示例就足够了。如果可以完成此步骤，通常会存在某种类型的分析可以自动检测已识别形式的违规行为。
下一步是确定分析需要有多智能才能产生良好的结果。通常，分析必须具有的关于代码中的数据结构或程序的输入值的知识越多，精确跟踪属性就越困难。在这种情况下，通常存在一种有效的启发式方法，可以应用于识别特定子集的错误。使用多种启发式分析通常比单个精确分析产生更好的结果。
例如，要确定属性3的违规行为是否适合源代码分析，我们可以从已知的安全漏洞开始。安全漏洞可能是通过调用操作系统（OS）函数来识别的，而没有验证执行程序权限的周围条件。在这一点上，我们可以构建一个简单的分析，查找对所讨论的OS函数的调用，而没有任何封闭的条件检查。可以通过枚举正确的权限检查的源代码编写方式来进一步改进该分析，然后增强分析以在存在封闭条件检查但该检查不正确时报告错误。作为进一步的改进，如果存在多个只能由特权用户执行的OS函数，我们可以枚举从检查到函数的映射，并将该映射直接编码到我们的分析中。
上述属性表明源代码分析的价值适用于所有编程语言。虽然某些特定问题（例如，内存泄漏）不适用于安全语言，但所有程序都与资源交互，并且必须遵守编码规则的编程接口，这些规则可以通过源代码分析工具进行检查。因此，这些工具的价值不仅限于任何特定的编程语言，甚至不限于特定的编程范例。
探索空间
一旦定义了状态空间，下一个任务是搜索程序状态空间以查找每个属性的违规行为。搜索状态空间的基本技术源自称为数据流分析的研究体系。
数据流分析的基本思想是搜索整个程序的状态空间，直到无法导出新信息（不动点）。程序首先表示为图，其中每个节点是源代码中的可执行语句，图中的边表示程序中的控制流。违规行为（如内存泄漏）可以描述为关联的状态机（见图3），它跟踪程序图中每条路径上每个指针的状态。在程序图的每个节点中，指针可以处于已分配或未分配状态。当程序图中的节点（或语句）包含与正在检查的属性相关的程序构造时，它们可能会触发此状态机中的转换。例如，调用malloc（标准C库中的内存分配函数）可以触发从未分配到已分配的状态机转换，而返回语句或任何其他退出作用域的语句都可以触发从已分配到错误的转换。
因此，程序图以深度优先的方式搜索，监控状态机的变化。一个关键的见解是，如果我们跟踪在每个程序图节点看到的的状态机状态，则可以显着优化搜索。即使通常有多条路径到达特定节点，我们也不必重新访问我们以前见过的节点，只要跟踪状态机在先前访问期间也在这些节点处于相同的状态。重新访问此类节点是不必要的，因为两次访问之间运行程序的状态的所有可能差异与正在检查的属性无关。
通过使用这种优化，分析能够避免路径爆炸问题，因为算法的性能现在与程序的大小呈线性关系，而不是指数关系。这种类型的数据流分析在实践中效果良好，在Linux和OpenBSD操作系统中发现了数千个关键错误和可利用的安全漏洞6。
刚刚描述的方法的一个缺点是，它需要手动指定分析检查的每个程序属性。一种解决方案是将源代码分析算法与数据挖掘算法相结合，该算法尝试直接从源代码中推断出正确的行为，以减轻一些规范负担。尽管这些自动化推断技术是使源代码分析作为产品有效的关键特征，但对这些技术的完整解释超出了本次讨论的范围。
可用工具
源代码分析的思想以工具形式存在多年，通过一系列源自Lint的工具7。虽然Lint在学术界和工业界都衍生出了变体，但Lint的最初重点是通过本质上对所有程序员施加C风格指南来为C源代码提供额外的严谨性。创建具有更广泛错误检查功能的类似Lint的工具的尝试通常都失败了。这些Lint变体的根本缺陷一直是报告的错误与检测到的实际缺陷的比率。这些工具通常会报告数十甚至数百条消息，这些消息可能反映了不良的编程风格，但没有反映分析软件中的真正缺陷。报告的错误也可能仅仅反映了工具的功能不足。此外，工具的有效性与向实际源代码添加规范密切相关，从而要求组织内的开发人员有纪律地使用Lint注释。
下一代源代码分析工具将所有必需的规范都放在工具内部，允许该工具处理数百万行源代码，而无需对代码进行任何修改。此外，这些工具还包括一个更复杂的程序状态模型，使其能够发现更复杂类别的软件缺陷，并将误报率降低到最坏情况下接近20%。随着这些工具集成到商业开发流程中，这些比率将进一步下降，因为程序员将认识到适合工具分析的编码风格和习惯用法，并自然而然地倾向于它们。
目标是使源代码分析成为行业最佳实践，就像自动化测试套件在过去十年中所做的那样。曾经有一段时间，少量的手写测试通常足以验证程序是否按预期工作。也曾有一段时间，研究人员认为有可能证明程序正在正确运行。虽然这些方法不再可行，但提供一种充当程序员错误绝缘层的工具可以使公司防止数百甚至数千个关键软件缺陷到达生产环境。问
参考文献
1. Tassey, G. 软件测试基础设施不足的经济影响。规划报告 02-3。RTI为美国国家标准与技术研究院（NIST）编写，2002年5月：参见http://www.nist.gov/director/prog-ofc/report02-3.pdf（需要会员资格）。
2. Cisco Systems. 网络安全威胁的经济影响。思科白皮书。2002年12月：参见http://www.cisco.com/warp/public/cc/so/neso/sqso/roi1_wp.pdf。
3. Oracle：参见http://www.oracle.com/oramag/oracle/02-mar/index.html?o22break.html。
4. Tassey, G. 软件测试基础设施不足的经济影响。规划报告 02-3。RTI为美国国家标准与技术研究院（NIST）编写，2002年5月：参见http://www.nist.gov/director/prog-ofc/report02-3.pdf（需要会员资格）。
5. Tassey, G. 软件测试基础设施不足的经济影响。规划报告 02-3。RTI为美国国家标准与技术研究院（NIST）编写，2002年5月：参见http://www.nist.gov/director/prog-ofc/report02-3.pdf（需要会员资格）。
6. Engler, D., Chelf, B., Chou, A., and Hallem, S. 使用特定于系统的程序员编写的编译器扩展检查系统规则，操作系统设计与实现会议论文集（2002年9月）：另请参见http://metacomp.stanford.edu/osdi2000/paper.html。
7. Johnson, S. C. Lint，C程序检查器。《Unix程序员手册》，1978年：参见http://plan9.bell-labs.com/7thEdMan/vol2/lint。
SETH HALLEM 是Coverity的联合创始人兼高级架构师，Coverity是一家位于加利福尼亚州门洛帕克的初创公司，专门从事源代码分析工具。在不到一年的时间里，Coverity已从斯坦福实验室的一个想法发展成为一家客户范围从初创公司到财富100强的公司。在加入Coverity之前，Hallem是斯坦福大学的博士候选人，与Dawson Engler一起从事元编译项目。在此期间，他与人合著了多篇学术出版物，发表在操作系统和编程语言领域的著名会议上。Hallem目前的工作重点是为Java编程语言设计和开发源代码分析工具。
DAVID PARK 是Coverity的联合创始人，并在这家快速发展的初创公司管理业务发展和销售工作。作为多家风险投资初创公司（涉及电子商务、电信和网络）的早期贡献者，Park在过去几年中帮助将成功的想法推向市场。在此之前，他是斯坦福大学计算机科学专业的博士候选人，在那里他从事建模检查网络协议和并发Java程序的工具。他是软件规范和验证领域多篇出版物的合著者，并且是国家科学基金会奖学金和斯坦福特曼工程奖的获得者。
DAWSON ENGLER 是斯坦福大学的助理教授，也是Coverity的联合创始人。他的研究兴趣是操作系统和编译器。他在斯坦福大学的工作重点是静态分析和模型检查领域的软件检查。Engler的元编译项目已在著名的学术期刊上发表了十多篇出版物，并创立了一家快速发展的初创公司（Coverity）。在加入斯坦福大学学院之前，Engler从麻省理工学院获得了博士学位，在那里他与人共同创立了exokernel操作系统项目。
最初发表于Queue第1卷，第8期—
在数字图书馆中评论本文
更多相关文章
Sanjay Sha - 企业应用程序的可靠性
企业可靠性是一门学科，它确保应用程序以一致、可预测和经济高效的方式交付所需的业务功能，而不会损害可用性、性能和可维护性等核心方面。本文描述了一组企业可以应用的核心原则和工程方法，以帮助他们驾驭复杂的企业可靠性环境，并交付高度可靠且经济高效的应用程序。
Robert Guo - MongoDB的JavaScript Fuzzer
随着MongoDB随着时间的推移变得更加功能丰富和复杂，开发更复杂的方法来查找错误的需求也在增长。三年前，MongDB在其工具包中添加了一个自制的JavaScript fuzzer，它现在是我们最多产的错误查找工具，在两个发布周期中负责检测到近200个错误。这些错误跨越了从分片到存储引擎的各种MongoDB组件，症状从死锁到数据不一致不等。fuzzer作为CI（持续集成）系统的一部分运行，它经常捕获新提交代码中的错误。
Robert V. Binder, Bruno Legeard, Anne Kramer - 基于模型的测试：它的现状如何？
您可能听说过MBT（基于模型的测试），但像许多未使用MBT的软件工程专业人士一样，您可能对其他人使用这种测试设计方法的经验感到好奇。从2014年6月中旬到2014年8月初，我们进行了一项调查，以了解MBT用户如何看待其效率和有效性。2014年MBT用户调查是2012年类似调查的后续调查，向所有评估或使用过任何MBT方法的人开放。它的32个问题包括在2013年高级自动化测试用户会议上分发的一项调查中的一些问题。一些问题侧重于MBT的效率和有效性，提供了管理者最感兴趣的数据。
Terry Coatta, Michael Donat, Jafar Husain - EA的自动化QA测试：事件驱动
对于数百万游戏发烧友来说，在Electronic Arts担任QA（质量保证）测试员的职位似乎是一份梦想的工作。但从公司的角度来看，与QA相关的开销可能看起来非常可怕，尤其是在大型多人游戏时代。
© 保留所有权利。