文法件自适应随机测试研究
发布时间：2018-12-27 09:22
【摘要】：文法件是一类用文法描述和解答问题的系统,其测试工作不同于其他程序:文法件的测试用例是符合文法规则的句子,获取途径主要是各种句子生成算法;文法件的测试代价通常较高,实践中要求使用少量高质量的测试用例发现尽可能多的错误。因此,生成具有较高检错效率的句子成为了文法件测试的重要课题。现有句子生成算法中,基于规则覆盖方式生成的句子集合在实际测试中因句子不足导致检错能力低下,需使用随机生成方式进行补充。随机生成方式虽然可以弥补规则覆盖方式的不足,但生成的句子可能存在相似甚至相同的情况,导致测试效率降低。本文通过引入自适应随机测试方法,使随机生成的句子均匀分布,从而提高句子质量与测试效率。本文通过实验验证了句子随机生成方式对规则覆盖方式的补充作用;针对随机生成方式在实践中存在的循环问题,提出设置最大推导次数加以解决。给出了句子自适应随机生成算法框架,对关键的距离定义问题进行深入探讨。根据文法件输入域特征,从字符串、产生式状态、树结构三个角度为句子距离提出了若干假设,并通过理论分析、直觉判断、实验验证对每种距离进行了一一研究。此外,本文还阐述了句子枚举与自适应随机测试的结合应用。实验表明,以产生式树编辑距离作为句子距离定义有理论上的依据,符合直觉上的判断,在各实验中表现良好,在计算效率上处于优势,是句子距离的合理定义。句子自适应随机生成方法在以产生式树编辑距离为距离定义时,生成的句子普遍具有较高的测试质量,可有效提高文法件的测试效率。
[Abstract]:Grammars are a class of systems which describe and solve problems by grammar. Their test work is different from other programs. The test cases of grammar parts are sentences that conform to the rules of grammar. The cost of testing grammars is usually high. In practice, a small number of high-quality test cases are required to detect as many errors as possible. Therefore, the generation of sentences with high error detection efficiency has become an important task in grammar testing. In the existing sentence generation algorithms, the sentence set generated by the rule coverage method has low error detection ability due to the lack of sentence in the actual test, so it needs to be supplemented by random generation method. Although random generation can make up for the lack of rule coverage, the generated sentences may have similar or even the same situation, resulting in lower test efficiency. In this paper, the adaptive random test method is introduced to make the randomly generated sentences distribute uniformly, thus improving the sentence quality and testing efficiency. This paper verifies the supplementary function of the random generation of sentences to the rule coverage through experiments, and puts forward setting the maximum derivation times to solve the cycle problem of random generation in practice. A framework of adaptive random sentence generation algorithm is presented, and the key problem of distance definition is discussed in detail. According to the input field features of grammar pieces, some assumptions about sentence distance are put forward from three angles: string, production state and tree structure. Through theoretical analysis, intuitive judgment, and experimental verification, each distance is studied one by one. In addition, this paper also describes the combination of sentence enumeration and adaptive random test. The experimental results show that the definition of sentence distance based on production tree editing distance has theoretical basis and is in accordance with intuitive judgment. It is a reasonable definition of sentence distance because of its good performance in each experiment and its advantage in computing efficiency. When the distance is defined by the distance of production tree, the generated sentences generally have high test quality and can effectively improve the test efficiency of grammar parts.
【学位授予单位】：华侨大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.53
本文编号：2392849
[Abstract]:Grammars are a class of systems which describe and solve problems by grammar. Their test work is different from other programs. The test cases of grammar parts are sentences that conform to the rules of grammar. The cost of testing grammars is usually high. In practice, a small number of high-quality test cases are required to detect as many errors as possible. Therefore, the generation of sentences with high error detection efficiency has become an important task in grammar testing. In the existing sentence generation algorithms, the sentence set generated by the rule coverage method has low error detection ability due to the lack of sentence in the actual test, so it needs to be supplemented by random generation method. Although random generation can make up for the lack of rule coverage, the generated sentences may have similar or even the same situation, resulting in lower test efficiency. In this paper, the adaptive random test method is introduced to make the randomly generated sentences distribute uniformly, thus improving the sentence quality and testing efficiency. This paper verifies the supplementary function of the random generation of sentences to the rule coverage through experiments, and puts forward setting the maximum derivation times to solve the cycle problem of random generation in practice. A framework of adaptive random sentence generation algorithm is presented, and the key problem of distance definition is discussed in detail. According to the input field features of grammar pieces, some assumptions about sentence distance are put forward from three angles: string, production state and tree structure. Through theoretical analysis, intuitive judgment, and experimental verification, each distance is studied one by one. In addition, this paper also describes the combination of sentence enumeration and adaptive random test. The experimental results show that the definition of sentence distance based on production tree editing distance has theoretical basis and is in accordance with intuitive judgment. It is a reasonable definition of sentence distance because of its good performance in each experiment and its advantage in computing efficiency. When the distance is defined by the distance of production tree, the generated sentences generally have high test quality and can effectively improve the test efficiency of grammar parts.
【学位授予单位】：华侨大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.53
【参考文献】
相关期刊论文 前1条
1 ;Linear algorithm for lexicographic enumeration of CFG parse trees[J];Science in China(Series F:Information Sciences);2009年07期
，本文编号：2392849
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/2392849.html
