CAREER: Adaptive Large-Scale Program Analysis

在过去三十年中开发的自动化程序分析已经证明了证明现实世界程序的非平凡属性的能力。这种能力反过来又应用于安全、软件定义网络、网络物理系统等新兴软件挑战。这类应用程序的多样性要求在可伸缩性、适用性和准确性方面调整底层程序分析以满足客户需求。然而，今天的程序分析并没有提供有用的调优旋钮。本研究的目标是一种通用的计算机辅助方法，以有效地适应不同客户的程序分析。一方面，它弥合了几十年的程序分析研究和建立在它们之上的各种工件之间的差距，以解决另一方面出现的软件挑战。在这样做的过程中，它扩大并增强了程序分析对其用户的好处，以及对那些质量受到程序分析影响的软件用户的好处。这项研究有三个关键因素。首先，它提出了优化问题，暴露了大量的选择，以适应程序分析的各个方面，例如成本、结果的准确性以及对缺失信息的假设。其次，它通过新的搜索算法解决了这些优化问题，这些算法可以有效地导航大型搜索空间，在存在噪声的情况下进行推理，与用户交互，并跨程序学习。第三，构建程序分析平台，方便用户指定和编写分析，使搜索算法能够对分析进行推理，并允许使用大规模计算资源并行化分析。该方法在分析移动应用程序（在智能手机和平板电脑等先进移动设备上运行的程序）的背景下得到了证明。移动应用程序代表了越来越多的非专业程序员的使用，它们可能被广泛的用户在异构和苛刻的条件下使用，这些用户可以从程序分析提供的假设分析中受益。

Automated program analyses developed over the last three decades have demonstrated the ability to prove non-trivial properties of real-world programs. This ability, in turn, has applications to emerging software challenges in security, software-defined networking, cyber-physical systems, and beyond. The diversity of such applications necessitates adapting the underlying program analyses to client needs, in aspects of scalability, applicability, and accuracy. Today's program analyses, however, do not provide useful tuning knobs. The goal of this research is a general computer-assisted approach to effectively adapt program analyses to diverse clients. It bridges the gap between decades of program analysis research on one hand and diverse artifacts built atop them to address emerging software challenges on the other. In doing so, it broadens and enhances the benefits of program analysis to its users, as well as users of software whose quality is impacted by program analysis.The research has three key ingredients. First, it poses optimization problems that expose a large set of choices to adapt various aspects of a program analysis, such as its cost, the accuracy of its result, and the assumptions it makes about missing information. Second, it solves those optimization problems by new search algorithms that efficiently navigate large search spaces, reason in the presence of noise, interact with users, and learn across programs. Third, it builds a program analysis platform that facilitates users to specify and compose analyses, enables search algorithms to reason about analyses, and allows using large-scale computing resources to parallelize analyses. The approach is demonstrated in the context of analyzing mobile apps -- programs that run on advanced mobile devices such as smartphones and tablets. Mobile apps represent an increasing use of non-expert programmers and they are likely to be used across a wide range of users in heterogeneous and demanding conditions that can benefit from what-if analyses that program analysis can offer.