“Synthesizing input grammars”: a replication study
“Synthesizing input grammars”: a replication study
复制标题
“合成输入语法”：一项复制研究
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
A. Zeller
中科院分区：
文献类型：
--
作者：
Bachir Bendrissou;Rahul Gopinath;A. Zeller
当为程序产生测试输入时，测试生成器（“模糊器”）可以从形式化描述预期输入的语言的语法中大大受益。近年来，研究人员研究了从程序及其执行中恢复输入语法的方法。Bastani等人的GLADE算法，在PLDI 2017上发表的，是第一个黑盒方法，用于声明非平凡语言（如XML，Lisp，URL等）的输入规范的上下文无关近似。最近的观察表明，GLADE算法可能会显示出较低的性能比在原来的论文中报告，我们从头开始重新实现GLADE算法。我们的评估证实，GLADE论文中报告的有效性评分（F1）过于乐观，在某些情况下，基于错误的语言。此外，GLADE在评估的几种真实语言中表现不佳，产生的语法需要花费兆字节来枚举输入。
When producing test inputs for a program, test generators ("fuzzers") can greatly profit from grammars that formally describe the language of expected inputs. In recent years, researchers thus have studied means to recover input grammars from programs and their executions. The GLADE algorithm by Bastani et al., published at PLDI 2017, was the first black-box approach to claim context-free approximation of input specification for non-trivial languages such as XML, Lisp, URLs, and more. Prompted by recent observations that the GLADE algorithm may show lower performance than reported in the original paper, we have reimplemented the GLADE algorithm from scratch. Our evaluation confirms that the effectiveness score (F1) reported in the GLADE paper is overly optimistic, and in some cases, based on the wrong language. Furthermore, GLADE fares poorly in several real-world languages evaluated, producing grammars that spend megabytes to enumerate inputs.