Next-generation Constraint Solvers for Software Engineering and Security

约束求解器是一种自动求解数学约束的程序，在工程和科学中有大量的应用。解算器可以比作瑞士军刀，用于规划机器人的运动、配置汽车或自动查找软件中的漏洞。工程师使用数学约束对他们的问题进行建模，然后使用求解器自动求解。就在十年前，对文字处理器和操作系统等商业软件进行可扩展的自动漏洞查找实际上还被认为是不可行的。由于解算器性能的显著提高(由于包括我在内的许多研究人员)，自动错误查找不仅成为可能，而且在像微软这样的公司中是强制性的。尽管迄今为止的成果很重要，但随着工程师处理更困难的应用，如软件合成，对功能更强大、表达能力更强的求解器的需求仍在继续增长。因此，我提出了一个长期的研究计划，以开发新的求解器技术，这些技术比今天的更快、更有表现力，目的是为了软件可靠性和安全性的软件工程工具。 更准确地说，我的研究计划有以下三个方面：i)我将探索基于机器学习的新技术。ML的理论和技术已经发生了名副其实的革命。我们可以使用ML和随机推理技术来学习大型约束中的微妙元级别模式，从而实现更快的求解(类似于人类从数据中识别深层概念的方式)，ii)利用无处不在的廉价多核处理器来构建可扩展的并行解算器的技术，以及iii)利用特定于领域的知识作为关键来解锁约束的解决方案的解算器技术。拟议中的研究将产生深远的基础性科学、技术和商业影响。这些基础性结果将通过参数复杂性和ML的思想为求解器启发式算法提供理论支持。技术和商业影响将是一套新的可伸缩和可扩展的解算器，它们有可能改变软件的可靠性和安全性。

Constraint solvers, programs that automatically solve mathematical constraints, are used in myriad applications in engineering and science. Solvers can be likened to swiss-army knives, used in applications such as planning a robot's movement, configuring a car or automatically finding bugs in software. Engineers model their problem using mathematical constraints, and then use solvers to automatically solve them. As little as a decade ago, scalable automatic bug-finding of commercial software like word processors and operating systems was considered practically infeasible. Thanks to impressive gains in solver performance (due to many researchers including myself), not only has automatic bug-finding become feasible but is mandatory in companies like Microsoft. While the gains to-date are important, the demand for ever-more powerful and expressive solvers continues to grow unabated as engineers tackle even harder applications such as software synthesis. Hence, I propose a long-term research program to develop new solver techniques that are orders of magnitude faster and more expressive than today's, aimed at software engineering tools for software reliability and security. More precisely, my research program has the following three thrusts: i) I will explore new techniques based on machine learning (ML). There has been a veritable revolution in ML theory and techniques. We can use ML and stochastic inference techniques to learn subtle meta-level patterns in large constraints that enable faster solving (similar to how humans identify deep concepts from data), ii) techniques that leverage ubiquitous and cheap multi-core processors to build scalable parallel solvers, and iii) solver techniques that leverage domain-specific knowledge as keys to unlock solutions to constraints. The proposed research will have deep fundamental scientific, technical, and commercial impact. The foundational results will provide theoretical underpinning for solver heuristics through ideas from parametric complexity and ML. The technical and commercial impact will be a set of new scalable and extensible solvers which have the potential to transform software reliability and security.