北航马帅团队 | 综述: 正则表达式正确性保证

论文题名：Ensuring the Correctness of Regular Expressions: A Review

论文作者：Li-Xiao Zheng, Shuai Ma, Zu-Xi Chen, Xiang-Yu Luo

全文链接：https://link.springer.com/article/10.1007/s11633-021-1301-4

参考链接：https://mp.weixin.qq.com/s/Q-PUU3ASufWEtA0_tvFiVA

正则表达式是对字符串操作的一种逻辑公式，许多程序设计语言都支持利用正则表达式进行字符串操作。在最近的六十年中，正则表达式逐渐从模糊而深奥的数学概念，发展成为在计算机各类工具和软件包应用中的主要功能。若正则表达式的定义出现错误，则可能导致使用它们的应用程序失败。因此，保证正则表达式的正确性是其实际应用的重要前提。北京航空航天大学马帅教授团队系统综述了正则表达式正确性保证的相关研究。相关成果已发表于IJAC，全文免费下载！

图片来自Springer

正则表达式(Regular expressions)具有较强的表达能力和灵活的定义方式，在计算机科学的许多领域具有广泛应用。其最早用于构造编译器的词法分析程序，近年来应用范围扩大至网络协议分析(network protocol analysis)、MySQL注入防御(MySQL injection prevention)、网络入侵检测(network intrusion detection)、XML数据模式描述(XML data specification)以及数据库查询(database querying)等，甚至在计算机领域以外也有正则表达式的应用，如在生物信息学领域使用正则表达式进行DNA序列比对。

正则表达式常用于计算机程序中的模式搜索(pattern searching)和字符串匹配(string matching)，是几乎所有现代编程语言的核心组件，经常出现在软件源代码中。研究表明，超过三分之一的JavaScript和Python项目至少包含一个正则表达式。

然而，最近的研究发现正则表达式很难理解、编写，并且容易出错。确实如此，由于正则表达式语法比较紧凑，并且使用大量元字符，导致开发人员在定义和使用时容易出错。即使是对于非常短的正则表达式，也很难读懂和理解其语义，对于可能包含100个字符或超过10个嵌套级别的复杂正则表达式来说，难度会更大。这都是软件开发人员面临的真实情况。例如，在一个备受开发者们欢迎的编程知识分享和学习网站上(stackoverflow.com)，超过20万个问题被标记为"regex"(正则表达式)。

若正则表达式的定义出现错误，则可能导致使用它们的应用程序出现缺陷。因此，保证正则表达式的正确性是其应用于实际的重要前提。事实上，一些研究者们也已经认识到该问题的重要性。然而，一项实证研究表明，在实际项目开发中使用的正则表达式有约80%未经测试，而在经过测试的正则表达式中，约有一半仅仅只使用了一个测试字符串。因此，亟需系统有效的方法和技术来确保正则表达式的正确性，以提高相应软件系统的质量。

本文综述了正则表达式正确性保证的相关研究，将现有工作分为不同类别，包括实证研究、测试串生成、自动合成与学习、静态检查与验证、可视化表示与解释及修复。针对每一类别，分别综述了主要的研究成果，比较了不同的方法，并且讨论了各自的优缺点。

本文其余部分组织如下：第2节介绍了正则表达式相关的基本知识，包括其不同方言、正确性含义和有限自动机。第3-8节基于不同的分类，分别对正则表达式正确性保证的相关工作进行了回顾。第9节总结并讨论了未来的研究方向。

来源：《International Journal of Automation and Computing》编辑部