High-Performance Generation of Constrained Inputs
Addison Crump, Alexi Turcotte, José Antonio Zamudio Amaya, Andreas Zeller
基于语言的测试将无上下文语法定义与语法元素的语义约束相结合,以生成测试输入。 通过将无上下文语法与约束配对,用户可以在保留简单结构的同时,具有不受限制语法的表现力。 然而,在存在这种限制的情况下提供投入可能具有挑战性。 在过去的方法中,SMT求解器在找到字符串解决方案方面非常缓慢;进化算法更快,更普遍,但目前的实现仍然难以应对编译器测试等域所需的复杂约束。 在本文中,我们提出了一种基于进化语言的测试的新方法,该方法在当前最先进的条件下将性能提高了3-4个数量级,将生成时间并减少了时间,并将解决时间限制到几秒钟。 我们通过(1)仔细将语法定义转换为 Rust 类型和 trait 实现来实现这一点,确保编译器可以近乎最大化地优化任意语法上的任意操作;(2)使用更好的进化算法,提高基于语言的测试解决复杂约束系统的能力。 这些性能和算法改进允许我们的原型FANDANGO-RS解决以前策略根本无法处理的限制。 我们通过C子集的案例研究证明了这一点,其中FANDANGO-RS每分钟能够为C编译器生成401个多样化,复杂和有效的测试输入。
Language-based testing combines context-free grammar definitions with semantic constraints over grammar elements to generate test inputs. By pairing context-free grammars with constraints, users have the expressiveness of unrestricted grammars while retaining simple structure. However, producing inputs in the presence of such constraints can be challenging. In past approaches, SMT solvers have been found to be very slow at finding string solutions; evolutionary algorithms are faster and more gen...