软件学报

作者：郑黎晓，余李林，陈海明，陈祖希，骆翔宇，汪小勇

单位：郑黎晓，华侨大学 计算机科学与技术学院, 福建 厦门 36102111,余李林，华侨大学 计算机科学与技术学院, 福建 厦门 36102102,陈海明，计算机科学国家重点实验室 (中国科学院 软件研究所 ), 北京 10019003,陈祖希，华侨大学 计算机科学与技术学院, 福建 厦门 36102104,骆翔宇，华侨大学 计算机科学与技术学院, 福建 厦门 36102105,汪小勇，卡斯柯信号有限公司, 上海 20007006

关键词：正则表达式;正则语言;字符串生成;变异测试;变异体约简

基金：国家自然科学基金(61872339); 福建省自然科学基金(2021J01316, 2021J01320); 中央高校基本科研业务费专项资金(ZQN-1010); 厦门市自然科学基金(3502Z20227191); 上海市自然科学基金(22ZR1422200)

正则表达式在计算机科学的许多领域具有广泛应用. 然而, 由于正则表达式语法比较复杂, 并且允许使用大量元字符, 导致开发人员在定义和使用时容易出错. 测试是保证正则表达式语义正确性的实用和有效手段, 常用的方法是根据被测表达式生成一些字符串, 并检查它们是否符合预期. 现有的测试数据生成大多只关注正例串, 而研究表明, 实际开发中存在的错误大部分在于定义的语言比预期语言小, 这类错误只能通过反例串才能发现. 研究基于变异的正则表达式反例测试串生成. 首先通过变异向被测表达式中注入缺陷得到一组变异体, 然后在被测表达式所定义语言的补集中选取反例字符串揭示相应变异体所模拟的错误. 为了能够模拟复杂缺陷类型, 以及避免出现变异体特化而无法获得反例串的问题, 引入二阶变异机制. 同时采取冗余变异体消除、变异算子选择等优化技术对变异体进行约简, 从而控制最终生成的测试集规模. 实验结果表明, 与已有工具相比, 所提算法生成的反例测试串规模适中, 并且具有较强的揭示错误能力.

来源：2024年第7期

《软件学报》期刊编辑部

查看软件学报杂志2024年第7期