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

协作研究：SaTC：核心：小型：通过正确和安全的正则表达式改进清理并避免拒绝服务

• 批准号: 2135156
• 负责人: James Davis
• 金额: $ 27.4万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-06-15 至 2025-05-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2135156&HistoricalAwards=false
• 关键词: Collaborative; Research; SaTC; CORE; Small

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.

该项目将提高软件的安全性。该项目将重点介绍正则表达式中的网络安全问题。正则表达式是计算机程序员用来操纵数据的重要工具。正式表达式以多种方式应用，包括验证网络形式中的输入并检查互联网流量是否有恶意活动。不幸的是，计算机程序员通常会错误地使用正则表达式，从而导致程序行为不安全。这些行为导致错误的网络安全后果，包括允许恶意演员窃取个人信息，抓住计算机控制或导致许多网站崩溃。该项目将通过改善正则表达工程实践，并使正则表达式所依赖的基础架构更具值得信赖的基础架构来解决这些限制。该团队将纳入本科研究人员，开发教育材料，并与K-12学生互动。该项目的成功完成将是消除与正则表达式有关的网络安全事件的重要一步。该项目将设计，开发和评估（第1部分）新技术，以使程序员更容易重新使用高质量的正则表达式; （第2部分）可免受正则表达拒绝服务（重做）的新型正则发动机。在第一部分中，团队提出了过程和工具，以帮助工程师开发正确的回音。该方法基于重复使用范式，帮助工程师从他人的专业知识中学习。但是，为了启用重复使用，必须在Regex索引，查询，匹配，排名和比较中解决开放问题。该团队将在853,818个正则拨号的数据集建立基础上，将开发正则群集技术，并将新颖的工具开发与用户研究集成在一起，以了解查询，排名和比较的方式和指标。将应用这些技术，机器学习和新算法的综合，以实现基于重复使用的组合，合成和修复安全敏感的回音。项目发现将体现在新型的公开访问的正则搜索引擎和随附的工具中。在第二部分中，团队将通过消除有问题的最坏情况特征来提高正则发动机的可信度。该团队已开始探索算法进步，以解决其最糟糕的超级线性行为。该团队将设计一种重做安全的算法，可证明具有恒定的空间绑定，并为扩展功能（例如Backeference）开发新颖的最坏情况分析。就实用性而言，团队的正则发动机更换必须是透明的。但是，向后兼容性检查Regex引擎是一个空旷的问题。该团队将根据变质和差分测试开发第一个正则发动机语义测试技术；并通过第一个系统的正则绩效基准启用Regex引擎性能回归测试。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响评估标准通过评估来支持的。