Static Analysis of Lua

Cours Static Analysis of Lua, tutoriel & guide de travaux pratiques en pdf.

Static Analysis of Lua

We can think of scripts as having many run-time states reachable via possibly many execution paths. Running every program path is infeasible, but abstracting from specific execution states enables us to reason about software properties and to compute them timely. Static analysis refers to the extraction of information about states and behavior from a software application without executing it.
Table 2 enumerates static analysis features applicable to Lua and compares existing analysis tools. Features include distinguishing between global and local variables (1) and relating declarations to uses (4), possibly using syntax high-lighting. Many of these features (1-6) can be approximated by data flow analysis techniques [9] such as reaching definitions, which computes for each program point which assignments can reach it. Others features require no flow analysis (7, 8) or require more advanced inference techniques (9-13). Figure 1 illustrates features described in Table 2 using comments and references (fn), where (a) illustrates features 1, 2, 4, 7, 8 and 9 and (b) shows features 1-3.
Koneki Lua Development Tools (LDT)4 is an Eclipse plug-in that provides remote debugging and rudimentary static analysis for highlighting and refactor-ing. Lua Inspect5 is an experimental static analysis tool that infers values, but incorrectly for conditional assignments. Lua Checker6 is a basic command-line tool that checks local variable declarations against their uses. Lua for IDEA7 enriches call sites with API structure (e.g. for World of Warcraft). LDT and Lua Inspect are based on Metalua [10], a Lua extension for static meta-programming.

Lua AiR Framework

This section explains the approach of the Lua AiR framework. IC3D Media has developed two languages for interoperability between Lua and their Logos3D game engine called Interface Definition Language (IDL) and Interface Generator Language (IGL). IDL defines function signatures and data types. IGL defines the generator format of the mapping between engine functionality defined in IDL models and Lua. Unlike other approaches shown in Table 2, we utilize information from the embedded context in our analysis. Functions and data structures exposed to Lua, and managed by the Logos3D engine, are statically defined and strongly typed. Sharing function signatures and data types modeled in IDL between the embedded environment and Lua enables checking function call site arguments against formal parameter types. Furthermore, it reduces the need for type inference and saves computation time in inter-procedural analysis. Additionally, code documentation can be shared between script proxies and the embedded context.
Lua AiR is a Rascal meta-program that implements the analysis as a pipeline, as illustrated by Figure 2. Rascal generates a specialized Eclipse IDE for Lua editing, highlighting, and static analysis. The analysis consists of the following model transformations. 1) The Lua script under analysis is fed into the parser generated by Rascal from our Lua Grammar (130 LOC). This produces a parse tree (a), depicted as a triangle. 2) The implode function matches the nodes of this tree to an Algebraic Data Type (ADT) that represents our Abstract Syntax Tree (AST) (b). This model transformation relies on compatible names and types between the Lua grammar and the ADT. 3) Reduce and Expand rewrite the AST to simplify the analysis (c). 4) The Checker provides static type checking and annotates the AST with scope information (d). 5) Given this AST, the Control Flow (CF) Analyzer generates a Control Flow Graph (CFG). 6) The Reaching Definitions (RD) Analyzer uses the CFG and performs fixed-point computation over generate and kill sets to generate the reaching definitions. Finally, the tool displays a log and the view in the IDE is updated by annotating the parse tree with results. The meta-program currently comprises approximately 3 KLOC.