Correlation Tracking for Points-To Analysis of JavaScript

JavaScript poses significant challenges for points-to analysis, particularly due to its flexible object model in which object properties can be created and deleted at run-time and accessed via first-class names. These features cause an increase in the worst-case running time of field-sensitive Andersen-style analysis, which becomes O(N4), where N is the program size, in contrast to the O(N3) bound for languages like Java. In practice, we found that a standard implementation of the analysis was unable to analyze popular JavaScript frameworks. We identify correlated dynamic property accesses as a common code pattern that is analyzed very imprecisely by the standard analysis, and show how a novel correlation tracking technique enables us to handle this pattern more precisely, thereby making the analysis more scalable. In an experimental evaluation, we found that correlation tracking often dramatically improved analysis scalability and precision on popular JavaScript frameworks, though in some cases scalability challenges remain.

JavaScript对指向分析提出了重大挑战，特别是由于其灵活的对象模型，在该模型中，对象属性可以在运行时创建和删除，并通过一等公民名称进行访问。这些特性导致字段敏感的Andersen式分析在最坏情况下的运行时间增加，变为O(N⁴)，其中N是程序大小，而对于像Java这样的语言，其复杂度界限为O(N³)。在实践中，我们发现该分析的标准实现无法分析流行的JavaScript框架。 我们将相关动态属性访问确定为一种常见的代码模式，标准分析对其分析得非常不精确，并展示了一种新颖的相关性跟踪技术如何使我们能够更精确地处理这种模式，从而使分析更具可扩展性。在一项实验评估中，我们发现相关性跟踪通常极大地提高了对流行JavaScript框架分析的可扩展性和精度，尽管在某些情况下可扩展性挑战仍然存在。