关键词:
软件测试
基于模型测试
文件系统
多线程程序
摘要:
软件是当今信息时代必不可少的基础设施。但软件缺陷引起的事故也频频发生,轻则影响用户体验,重则带来巨大的经济损失甚至危及人身安全。因此,保障软件质量至关重要。软件测试是目前最有效的软件质量保障手段之一,因其易部署、代价低的优点而成为工业实践中最被广泛采纳的技术。自动化地为软件生成测试输入是软件工程领域最重要的研究问题之一。尽管已有诸多技术被相继提出并使用,但目前许多复杂的基础软件系统(如操作系统内核、并发服务器系统等)即便经过了广泛的自动化测试,依然存有大量缺陷被用户触发并上报。如何更好地为此类复杂软件系统生成测试输入来尽可能多地检测出缺陷仍有待解决。本文观察到已有自动化测试技术在为复杂软件系统生成输入这一问题上的局限性。虽然目前黑盒测试和模糊测试技术因自动化程度高,而成了测试复杂软件系统的首选技术,但他们将实现逻辑、执行等各方面都极其复杂的软件系统几乎视作黑盒,仅采用粗粒度信息(如“输入-输出”关系或是“输入-代码覆盖”关系等)来启发式地指导生成输入。由于粗粒度信息无法反映输入在软件系统上的具体执行,所以指导生成的输入很难驱动软件系统执行到深层次的状态并暴露出缺陷。另一方面,基于模型测试技术尽管在理论上能够借助模型生成具有针对性的测试输入并早已被提出,但在复杂软件系统上一直由于建模难度巨大而未被广泛使用。针对上述不足,本文提出了一种基于“缺陷可解释性”的测试输入自动生成框架,该框架立足于“大部分复杂软件系统的缺陷都有一个程序员能理解的解释”这一核心观察,完成了对复杂软件系统输入与缺陷解释之间的建模并实现了“输入-缺陷解释”的自动转换,从而所生成的输入能够有效地促使复杂软件系统执行到潜在触发缺陷的状态,并更快、更多地暴露缺陷。我们的框架弥补了基于模型测试工作一直以来在复杂软件系统上切实运用的短板。具体而言,框架包含如下三个方面。1.我们基于观察并结合已有工作提出了“缺陷可解释性”假设作为建模方法的理论基础。由于大部分复杂软件系统的缺陷都能被理解,即缺陷只涉及部分且能够被建模的系统行为,所以我们能够建模出(暴露缺陷的)输入和缺陷解释(所涉及的软件行为)之间的关系。基于此,我们提出了针对复杂软件系统输入的建模方法,该方法的核心在于以输入为建模对象、以缺陷的解释为导向,将输入建模到缺陷解释,即抽象该输入在软件系统上执行时潜在的缺陷触发条件。由于我们直接刻画了复杂软件系统缺陷触发的诱因,所以相比于已有工作(黑盒测试和模糊测试技术),利用我们的模型生成测试输入更具有效性。2.我们找到了模型形态(输入解释)的统一表示形态并设计了建模语言,其能够帮助我们在不同复杂软件系统上轻易地完成建模过程并大大降低建模工作量。首先,我们发现图结构是一种简单但通用的表示形式,它能够跨不同领域的复杂软件系统表示出各类系统的缺陷解释。其次,我们观测到复杂软件系统的输入往往具有“单调性”。基于此,我们设计了元-元级建模语言,该语言能够被用于撰写带标注的上下文无关文法,该文法描述了软件系统输入的语法和建模规则。利用这一建模语言,我们能够简单地将软件系统的输入建模到缺陷解释。3.我们提出了自动化生成测试输入算法,其能够到达“枚举输入解释,生成测试输入”的测试效果。我们将输入解释量化到了数值空间,并提出了系统化的采样算法能够自动采样不同的输入解释。同时,我们提出了自动化测试输入生成算法。任意给定一个输入解释作为测试目标,我们通过该算法能够得到一个测试输入。算法的核心在于将输入生成问题转化到了传统的代码合成问题,并通过搜索策略得以解决。我们将上述框架实例化到了不同的实际复杂软件系统上,给出了完整的建模,以及在不同领域内对模型可进行更有效的定制化。实验结果表明了我们方法的有效性,在短时间的测试下,我们的工具分别能够在操作系统内核的复杂文件系统及复杂的并发服务器中找到多个隐藏已久的未知缺陷。