Browse Prior Art Database

System, Method and Apparatus for Effective Hybrid Construction of JavaScript Call Graphs

IP.com Disclosure Number: IPCOM000239750D
Publication Date: 2014-Dec-01
Document File: 3 page(s) / 74K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a hybrid method for JavaScript call-graph construction that combines (i) a relatively precise static construction algorithm and (ii) a dynamic oracle, which is preferably based on a large set of execution traces. The key idea is to combine the two such that precision and/or scalability bottlenecks are identified and addressed in a comparative way, and the corresponding resolution is achieved via the dynamic oracle.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 45% of the total text.

Page 01 of 3

System, ,

Method and Apparatus for Effective Hybrid Construction of JavaScript Call

      Method and Apparatus for Effective Hybrid Construction of JavaScript Call Graphs

JavaScript has several attractive features, including rich and flexible syntactic constructs as well as extensive library support (i.e. jQuery). JavaScript motivates specialized forms of tooling and analysis (e.g., security analysis, auto completion, type inference, etc.) These analyses and others rely on a basic representation of the JavaScript program as a call graph, which models the call structure between JavaScript functions. While in general, call$graph construction is an undecidable problem, and thus only approximate solutions are possible, algorithms designed for Java, .NET and other statically typed languages often work well in practice.

With JavaScript, however, the situation is different. The rich runtime behavior of JavaScript code, including built$in reflective constructs such as property traversal and dynamic constructs such as introducing new functions and properties into the prototype of a given type, lead to highly conservative call graph approximations in practice.

The consequence is twofold. First, the resulting call graph is often so imprecise that it is of virtually no practical utility. Second, the cost of accounting for challenging language features is often so expensive that the analysis exhausts memory or times out. As an example, the analysis may reach into large amounts of dead code when modeling use of libraries like jQuery by the client JavaScript program.

Current solutions to improve the precision of JavaScript call graph construction include correlation analysis [1], field$based analysis [2], and blended analysis [3]. None of these provides a complete solution.

The novel contribution is a hybrid method for JavaScript call $graph construction. This approach brings together (i) a relatively precise static construction algorithm and (ii) a dynamic oracle, which is preferably based on a large set of execution traces . The key idea is to combine the two such that precision and /or scalability bottlenecks are identified and addressed in a comparative way, and the corresponding resolution is achieved via the dynamic oracle.

This approach is backed by practical experience that indicates that often JavaScript programs (and especially frameworks and libraries) are equipped with an extensive set of unit, integration, and regression tests. This is precisely because of the dynamic, and thus challenging, nature of JavaScript code.

Driven by this observation, the preferred embodiment of the method is for the dynamic oracle to be based on the entire set of tests accompanying the subject application . Building such an oracle amounts to recording dynamic call$site resolutions, in which the call site is identified via a static label. The dynamic oracle may additionally factor in other context information per the context$sensitivity policy of the correspond...