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

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

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.