String Constraint Solving with Real-World Regular Expressions

使用真实世界的正则表达式解决字符串约束

• 批准号: EP/T00021X/1
• 负责人: Matthew Hague
• 金额: $ 50.15万
• 依托单位: Royal Holloway University of London
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FT00021X%2F1
• 关键词: String; Constraint; Solving; Real; World

Strings in programming languages are sequences of characters that represent any kind of text. They are a fundamental aspect of information representation: user names, passwords, or indeed any kind of text are handled as strings.The manipulation of strings, however, can also lead to subtle programming errors, that can have consequences for program correctness as well as information security. For example, a malicious user may enter computer code as their username. If the system is not sufficiently secure, this code can allow the user to hack the system. The Open Web Application Security Project lists this kind of attack among the top 10 application security risks.Despite this kind of attack being well-known, it has proved surprisingly difficult to avoid due to the complex nature of computer programs. Ideally, programming mistakes will be caught during testing. However, manual testing is a tedious and time-consuming process which requires the developer to imagine every possible user input. Automatic test-case generation can take this burden away from the developer and allow more complete testing to be done more efficiently. However, this relies on the tools used for test-case generation to be able to accurately reason about how software will run.This project will focus on how software deals with strings. Typically "regular expressions" are used for this purpose. However, current research takes an idealised view of regular expressions that omits many important features of the regular expressions provided by modern programming languages. We will address this shortcoming both in the theory of computer science and in practice. In particular, we will create a test-case generation tool-chain that will provide better test-case generation for software dealing with strings. These tools will be tested on real-world industrial code provided by Prodo.ai.

编程语言中的字符串是表示任何类型文本的字符序列。它们是信息表示的一个基本方面：用户名、密码或实际上任何类型的文本都作为字符串处理。然而，对字符串的操作也可能导致微妙的编程错误，从而对程序正确性和信息安全产生影响。例如，恶意用户可能输入计算机代码作为他们的用户名。如果系统不够安全，此代码可能允许用户破解系统。开放 Web 应用程序安全项目将此类攻击列为十大应用程序安全风险之一。尽管此类攻击众所周知，但由于计算机程序的复杂性，事实证明它难以避免。理想情况下，编程错误将在测试期间被发现。然而，手动测试是一个繁琐且耗时的过程，需要开发人员想象每一个可能的用户输入。自动测试用例生成可以减轻开发人员的负担，并允许更有效地完成更完整的测试。然而，这依赖于用于测试用例生成的工具能够准确地推断软件将如何运行。该项目将重点关注软件如何处理字符串。通常，“正则表达式”用于此目的。然而，当前的研究对正则表达式采取了理想化的观点，忽略了现代编程语言提供的正则表达式的许多重要特征。我们将在计算机科学理论和实践中解决这个缺陷。特别是，我们将创建一个测试用例生成工具链，为处理字符串的软件提供更好的测试用例生成。这些工具将在 Prodo.ai 提供的真实工业代码上进行测试。

项目成果

Solving string constraints with Regex-dependent functions through transducers with priorities and variables

• DOI: 10.1145/3498707
• 发表时间: 2021-11
• 期刊: Proceedings of the ACM on Programming Languages
• 作者: Taolue Chen;Alejandro Flores-Lamas;M. Hague;Zhilei Han;Denghang Hu;Shuanglong Kan;A. Lin;Philipp Rümmer;Zhilin Wu