编程语言测试综述

文章目录

• 0 引言
• 1 编程语言基础设施概述
• 2 编程语言测试的难点
• 3 编程语言测试的技术
• • 3.1 编译器测试技术
  • • 3.1.1 学术界对编译器的测试
    • 3.1.2 工业界对编译器的测试
  • 3.2 标准库测试技术
  • 3.3 其他部分的测试
• 4 编程语言测试的挑战
• 5 总结
• 参考文献

0 引言

编程语言作为构建一切软件的基础，被誉为系统软件“皇冠上的明珠”，而作为保障编程语言基础设施质量的测试技术则是让这颗明珠持续闪亮的“聚光灯”。随着现代编程语言的兴起，编程语言基础设施测试涵盖的组件也越来越多，不仅包含传统的编译器测试，同时还包含语言标准库、运行时、调试器、程序分析工具、构建工具、部署工具、IDE 等一系列语言组件的测试，如何保证质量，甚至是 10 倍质量，成为构建一套语言基础设施的难点，更成为一款商用编程语言的核心竞争力。

如果您想要了解更多编程语言相关的测试技术，请记得持续关注我们哟！也非常欢迎您加入我们的编程语言技术 区SIG-编程语言测试小组，和我们一起深入探索编程语言测试技术。
加入方式：文末有小助手微信，添加并备注加入SIG-编程语言测试。

1 编程语言基础设施概述

如果说语言是人类进行沟通和交流的表达方式，凝聚了人类文明的千年历史。那么编程语言作为人机对话所必须的具有共同处理规则的沟通指令，则代表了一代又一代计算机科学家智慧的结晶。1946 年 2 月 14 日，世界上第一台通用计算机“ENIAC”在美国宾夕法尼亚大学诞生。迄今在通用计算机上，至少诞生了超过上千种的编程语言。这些编程语言因其设计的初衷和需要解决的问题不同，而具备了不同的语言特性及编程方式 [1]。

在旧约故事里，上帝将巴别塔建造者们的语言打乱，让他们再也不能明白对方的意思，并把他们分散到了世界各地。同物种间的跨语言沟通尚且需要翻译，更何况是跨物种的人机交互。

学术界发表了比较多编译器测试的论文，根据陈俊洁 [9] 团队的研究 [10]，编译器测试的研究可以分为如下图展示的几个方面。

每一个由 Csmith 生成的程序都可以被分割为三个部分：

• 包含对全局变量的 CRC 校验及首函数调用的 main 函数
• 内容随机的首函数
• 内容随机的被首函数调用的函数

这种以函数为粒度的程序块在生成时其实是作为 “BLOCK” 来划分的。而每一个函数的 “BLOCK” 中包含了若干条 Statement，即语句。Statement 的分解如下图所示：

• C-specific peephole passes
  • –x^=y -> x=y
  • -while(…) -> if (…)
  • –x y : z -> y
  • …
• Remove chunks of text,like Delta
• Some non-local transformations
• C/C++ -specific plugins including
  • Inline a function call
  • Un-nest nested function calls
  • Make function return void
  • Reduce array dimension or pointer level
  • …

下图是 C-Reduce 用例裁剪的一个基本过程，持续应用 plugin 规则，就可能达到一个比较小规模的测试用例。经过裁剪后的代码明显代码行数变少而且变得简单。

学术界的很多工具和方法因其有效性，而被工业界认可，进而被购买和收购。典型案例：GraphicsFuzz [23] 工具是由英国帝国理工的 ALASTAIR F. DONALDSON 教授 [24] 的团队开发，用于 GPU 编译器测试的用例生成工具.由于发现 bug 的效果非常好，后来被 Google GPU 编译器团队收购。

工业界与学术界在编译器测试领域也展开广泛的合作。例如 Intel 公司与 Utah 大学开展合作开发了 YARPGen 工具 [12]，这个工具在 GCC、LLVM 和 Intel C++ Compiler 测试中发现超过 220 个 bug，也取得了很好的效果。

学术界的技术成果在工业界得到了广泛的应用，但事实上工业界关注的重点与学术界也略有不同。

3.1.2 工业界对编译器的测试

商业公司一般都会编译器进行标准测试，例如某个 C 语言编译器是否满足 C99 标准。也会有相应的公司提供相应的测试用例，例如针对是否满足 C89/C99 标准， ACE 公司有 SuperTest 测试套 [25]，PlumHall 公司有 C & C++ Validation Test Suites 测试套 [26]。针对是否满足 Java 语言规范和 Java 虚拟机规范，Oracle 公司有 JCK（Java Compatibility Kit）测试套 [27]。

商业公司更注重工程实践，一般都会建立自己的 CodeDB（Code Database），针对特定客户，会建立符合用户特征的代码库。在得到用户同意的情况下，也可以直接使用用户的代码，同时也会将大量的开源代码引入到 CodeDB，用以保证编译器的质量。商业公司也会引入大量的通用 benchmark 用于编译器的性能测试，例如 SPEC-Int [28]、EEMBC [29] 等，针对特定用户建立定制的 benchmark，进行性能测试。

商业公司通过一系列的标准测试、性能测试、兼容性测试等一系列的测试才能构建起完整的测试体系，使最终发布的产品质量可控。因此工业界的测试更加关注测试体系的完整性。

虽然近十年来，学术界和工业界都对编译器测试贡献了许多的工具和方法，使相关测试技术有了长足的进步。但编译器测试仍然存在着巨大的挑战。

3.2 标准库测试技术

关于库的测试，学术界主要的关注点是安全问题、系统漏洞以及覆盖率的提高，常见的测试有符 执行、模糊测试技术。

符 执行与模糊测试在业界已经广泛应用，这两种技术都具有一定的优缺点 [30]：

符 执行可以生成复杂条件分支的测试用例，但在符 化执行过程中往往会出现路径爆炸问题；

模糊测试随机变异生成测试用例，可以覆盖到较深的分支，但很难通过变异的方法生成复杂条件分支的测试用例。

符 执行 [31] 通过符 化执行程序来收集约束条件, 并借助约束求解器为每条路径生成测试用例，大致原理如下图所示。

3.3 其他部分的测试

除了前面的内容，一般还会调试器的测试。对于发布的用户指南等文档需要进行资料测试，针对 IDE 进行用户体验测试。对于多个操作系统的版本进行兼容性测试和安装测试，以及前后版本的兼容性测试。

总之对于编程语言的测试是一个复杂系统的测试，虽然学术界，工业界虽然都做出了很多努力，但仍然充满很多的挑战。

4 编程语言测试的挑战

如何综合评价编程语言/strong>
当前针对编程语言的综合评估比较少。当前的工具更多的是针对编译器，尤其是优化测试的比较多，而针对编程语言综合评估其实比较少。例如从性能、可读性、代码的书写效率、安全性以及商业因素等等多个方面去评估编程语言。导致一个编程语言能够被广泛使用的因素有哪些，各个因素起了什么作用。

库函数的功能测试/strong>
库函数涉及的内容非常广泛，而当前常用的工具和方法更多的是针对安全测试和漏洞挖掘。因此功能测试更多的是通过人工写用例的方式完成。而人工写用例的方式需要耗费大量的人力。

如何 “更方便” 地生成 “更好” 的测试用例/strong>
针对测试用例的生成，具体的挑战表现为如下 3 个问题。

针对不同的语言，如何快速开发一个用例生成工具/strong>
由于 Csmith 发现的 bug 的效率很高，因此其他的编程语言也希望开发类似的工具，但开发这样的工具是也需要一定的工作量，Csmith 有 30K 的代码量。当前除了类似 Csmith 直接在代码中描述语法语义外，还有一些其他的用例生成技术。DeepFuzz 基于神经 络生成测试用例，但这需要有训练的过程。Xsmith [37] 是一个能够支撑多个编程语言开发用例生成工具的框架。但 Xsmith 是基于 Racket 语言开发的，学习 Racket 语言又引入了一定的学习成本。因此如何能够快速开发一个高质量的用例生成工具对于企业来说还是很重要的。

如何生成指定优化或者满足用户代码特征的用例/strong>
当前的用例生成工具，更多的是一个 Fuzz 工具，往往没有什么具体的指向性。但实际的测试人员往往都是针对某一个具体的优化进行测试，导致在实际的工作中，迭代内的测试并不能直接使用用例生成工具。

如何从大量失败用例中，快速地对 bug 进行定位和分类/strong>
Bug 的快速定位，具体的挑战是 Fail 用例的去重与优先级排序。由于 Csmith 类似的工具是随机生成的测试用例，一旦 bug 很多时，可能会有一部分用例是重复的，多人分析用例的时候往往会重复，造成人力的浪费。在修复 bug 的时候，有些 bug 对用户可能影响大，有些影响小，希望能够对 Fail 的用例进行排序，优先解决影响大的 Fail 用例。

5 总结

对编程语言的测试会用到很多的测试用例生成技术，还涉及符 执行技术、Fuzz 测试技术以及人工智能技术（应用 LSTM 神经 络生成测试用例，即 Test By AI；也有针对 Transformer-XL 模型的测试，即 Test for AI）、同时也会涉及到用例裁剪等编译器技术、IDE 的用户体验测试等。因此编程语言测试是一个综合的、系统的测试技术，需要学术界和工业界共同努力，才能保证编程语言的质量。

参考文献

1. Programming language – Wikipedia: https://en.wikipedia.org/wiki/Programming_language

2. Backus–Naur form – Wikipedia: https://en.wikipedia.org/wiki/Backus–Naur_form

3. GNU Compiler Collection – Wikipedia: https://en.wikipedia.org/wiki/GNU_Compiler_Collection

4. Status of Supported Architectures from Maintainers’ Point of View – GNU Project – Free Software Foundation (FSF): https://gcc.gnu.org/backends.html

5. 江贺: http://oscar-lab.org/people/~hjiang/index_chn.htm

6. Compiler testing: a systematic literature analysis. Y Tang, Z Ren, W Kong, H Jiang, 2019

7. LLVM 3.9 Release: https://lists.llvm.org/pipermail/llvm-announce/2016-September/000070.html

8. Professor Zhendong Su’s Homepage: https://people.inf.ethz.ch/suz/

9. JunjieChen: https://sites.google.com/site/junjiechen08/

10. A Survey of Compiler Testing. J Chen, J Patra, M Pradel, Y Xiong, H Zhang, D Hao, L Zhang, 2020

11. Finding and understanding bugs in C compilers. X Yang, Y Chen, E Eide, J Regehr, 2012. In Proceedings of the 2011 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2011.

12. Random testing for C and C++ compilers with YARPGen. V Livinskii, D Babokin, J Regehr, 2020

13. SRCIROR: A Toolset for Mutation Testing of C Source Code and LLVM Intermediate Representation. Farah Hariri, August Shi, 2018

14. DeepFuzz: Automatic Generation of Syntax Valid C Programs for Fuzz Testing. Xiao Liu, Xiaoting Li, Rupesh Prajapati, Dinghao Wu

15. Test oracle – Wikipedia: https://en.wikipedia.org/wiki/Test_oracle

16. Compiler validation via equivalence modulo inputs. V. Le, M. Afshari, and Z. Su. In Proceedings of the 2014 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2014

17. Gcov Intro (Using the GNU Compiler Collection (GCC))
    https://gcc.gnu.org/onlinedocs/gcc/Gcov-Intro.html#Gcov-Intro

18. Test-Case Reduction for C Compiler Bugs. John Regehr, Yang Chen, Pascal Cuoq,Eric Eide, Chucky Ellison, Xuejun Yang.

19. Perses：Syntax-Guided Program Reduction. Chengnian Sun, Yuanbo Li, Qirun Zhang, Tianxiao Gu, Zhendong Su.

20. Formal verification – Wikipedia: https://en.wikipedia.org/wiki/Formal_verification

21. 形式化程序验证和可信软件. 冯新宇

22. Provably Correct Peephole Optimizations with Alive. Nuno P. Lopes, David Menendez, Santosh Nagarakatte, John Regehr

23. Automated Testing of Graphics Shader Compilers. ALASTAIR F. DONALDSON,HUGUES EVRARD, ANDREI LASCU, PAUL THOMSON.

24. Professor Alastair Donaldson: https://www.imperial.ac.uk/people/alastair.donaldson

25. SuperTest http://www.ace.nl/compiler/supertest-compiler-test-and-validation-suite

26. Plum Hall, Inc. – C and C++ Validation Test Suites
    http://www.plumhall.com/suites.html

27. Gaining Access to the JCK https://openjdk.java.net/groups/conformance/JckAccess/

28. SPEC Benchmarks https://www.spec.org/benchmarks.html

29. EMBC https://www.eembc.org/

30. 基于符 执行与模糊测试的混合测试方法. 谢肖飞, 李晓红.

31. 符 执行测试自动生成技术原理及应用. 丁国富.

32. Symbolic Execution for Software Testing: Three Decades Later. Cristian Cadar, Koushik Sen

33. KLEE https://klee.github.io/

34. S2E http://s2e.systems/docs/#

35. APL https://github.com/google/AFL

36. Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context. Zihang Dai, Zhilin Yang, Yiming Yang, Jaime Carbonell, Quoc V. Le, Ruslan Salakhutdinov

37. Xsmith https://www.flux.utah.edu/project/xsmith