Collaborative Research: SaTC: CORE: Small: Improving Sanitization and Avoiding Denial of Service Through Correct and Safe Regexes

该项目将提高软件的安全性。该项目将重点关注正则表达式中的网络安全问题。正则表达式是计算机程序员用来操作数据的重要工具。正则表达式应用于许多方面，包括验证Web表单中的输入以及检查恶意活动的Internet流量。不幸的是，计算机程序员经常错误地使用正则表达式，导致不安全的程序行为。这些行为会导致严重的网络安全后果，包括允许恶意行为者窃取个人信息，控制计算机或导致许多网站崩溃。这个项目将通过改进正则表达式工程实践来解决这些限制，并使正则表达式所依赖的基础设施更加值得信赖。该团队将包括本科研究人员，开发教育材料，并与K-12学生接触。该项目的成功完成将是消除与正则表达式相关的网络安全事件的重要一步。该项目将设计、开发和评估（第1部分）使程序员更容易重用高质量正则表达式的新技术;以及（第2部分）防止正则表达式拒绝服务（ReDoS）的新型正则表达式引擎。在第一部分中，团队提出了帮助工程师开发正确的正则表达式的过程和工具。该方法基于重用范式，帮助工程师学习他人的专业知识。然而，为了实现重用，必须解决正则表达式索引、查询、匹配、排名和比较中的开放问题。基于853，818个正则表达式的数据集，该团队将开发正则表达式聚类技术，并将新工具开发与用户研究相结合，以了解查询，排名和比较的模式和指标。综合这些技术，机器学习和新的算法，使基于重用的组合，合成和修复安全敏感的正则表达式将被应用。项目结果将体现在一个新的公开访问的正则表达式搜索引擎和配套工具。在第二部分中，团队将通过消除有问题的最坏情况特征来提高正则表达式引擎的可信度。该团队已经开始探索算法的进步，以解决其最坏情况下的超线性行为。该团队将设计一个具有可证明的恒定空间边界的ReDoS安全算法，并为扩展功能（例如，反向引用）。为了实用，团队的正则表达式引擎更改必须是透明的。然而，正则表达式引擎的向后兼容性检查是一个开放的问题。该团队将开发第一个基于变形和差分测试的正则表达式引擎语义测试技术;并通过第一个系统化的正则表达式性能基准来实现正则表达式引擎性能回归测试。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估而被认为值得支持。

This project will improve the security of software. The project will focus on cybersecurity issues in regular expressions. Regular expressions are an important tool used by computer programmers to manipulate data. Regular expressions are applied in many ways, including to validate input in a web form and to check internet traffic for malicious activity. Unfortunately, computer programmers often use regular expressions incorrectly, leading to insecure program behavior. These behaviors result in errors with serious cybersecurity consequences, including allowing malicious actors to steal personal information, seize control of a computer, or cause many websites to crash. This project will address these limitations by improving regular expression engineering practices, and by and making more trustworthy the infrastructure on which regular expressions rely. The team will incorporate undergraduate researchers, develop educational material, and engage with K-12 students. The successful completion of the project will be a significant step towards eliminating cybersecurity incidents related to regular expressions.This project will design, develop, and evaluate (Part 1) New techniques to make it easier for programmers to re-use high-quality regular expressions; and (Part 2) Novel regex engines that are safe from regular expression denial of service (ReDoS). In Part One, the team proposes processes and tools to help engineers develop correct regexes. The approach is grounded in the re-use paradigm, helping engineers learn from others' expertise. However, to enable re-use, open problems must be addressed in regex indexing, querying, matching, ranking, and comparison. Building on a dataset of 853,818 regexes, the team will develop regex clustering techniques, and integrate novel tool development with user studies to understand modalities and metrics for querying, ranking, and comparison. Synthesizing these techniques, machine learning and new algorithms to enable the reuse-based composition, synthesis, and repair of security sensitive regexes will be applied. Project findings will be embodied in a novel publicly-accessible regex search engine and accompanying tools. In Part Two, the team will improve the trustworthiness of regex engines by eliminating the problematic worst-case characteristics. The team has begun exploring algorithmic advances that address its worst-case super-linear behavior. The team will design a ReDoS-safe algorithm with a provably constant space bound and develop novel worst-case analyses for extended features (e.g., backreferences). For practicality, the team's regex engine changes must be transparent. However, backwards compatibility checking for regex engines is an open problem. The team will develop the first regex engine semantic testing techniques, based on metamorphic and differential testing; and enable regex engine performance regression testing through the first systematic regex performance benchmark.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.