Introduction

之前的一些 JS 的 callgraph 相關的工作忽略了動態(tài)屬性訪問（比如 Field-based Analysis）。最近的 ECOOP'22 的工作顯示動態(tài)屬性訪問是最主要的 unsoundness 的來源。這篇文章主要關注動態(tài)屬性訪問，使用 dynamic pre-analysis 的信息減少 unsoundness。

這個技術的靈感來源于之前 OOPSLA'14 的工作：當使用動態(tài)對象操作來初始化庫 API 時，這些操作往往發(fā)生在與程序輸入無關的執(zhí)行上下文中。確定性 determinacy 指在某個程序位置 \(l\) 和上下文 \(c\) 中，變量 \(x\) 的值始終相同。以往的確定性技術還沒有在大規(guī)模的程序上做驗證。這里的 approximate interpretation 技術是一種輕量化的動態(tài)確定性技術，還會收集到之前的方法收集不到的關系型信息 relational information。

簡單來說，approximate interpretation 會通過強制運行代碼來收集一系列提示 hints 給主要的靜態(tài)分析過程使用。強制執(zhí)行可能到達一些在實際情況下不能達到的程序狀態(tài)，但是這種不精確是可以接受的。

Motivating Example

在這個例子中，調用關系包括：

• express() 調用 createApplication()

• createApplication() 調用 mixin() 兩次，把 EventEmitter.prototype 和 proto 的 descriptor 復制到 app 上

• (a) 中的 app.get 實際上可以看作 app["get"]，這個函數在 (d) 中初始化的時候通過 app[method] = ... 進行賦值，最終返回的對象為 proto，(b) 中調用mixin 方法再把 proto 上對應地屬性函數復制到 (a) 中的 app 上，實際上的調用關系非常復雜

• app.listen 同樣是在初始化的時候被動態(tài)加入到對象屬性當中的

在這種復雜的例子下，如果做 over-approximate，精度就會特別差；如果忽略動態(tài)屬性訪問（比如 Field-based 的 WALA），那么就會丟失掉這些調用邊

Express 的 application 對象在每次調用 createApplication 時都以相同方式初始化，那么只需要一次運行，就能得到確定性的信息，補齊靜態(tài)分析丟失的信息：

隨意運行任意的函數并不容易，采用一種稱為近似解釋 approximate interpretation 的強制執(zhí)行策略避免構造能夠覆蓋所有相關函數的輸入。

Approximate Interpretation

有幾點特殊的語言性質需要注意：

• 作為模塊的源代碼可以通過函數 require 動態(tài)的引入

• 使用 function value 來指代作為運行時值存在的函數，因為函數可能包含那些不在自身定義域里面定義的變量（閉包），模塊函數例外

Approximate interpretation 使用 worklist 算法：

• \(Worklist\) 維護一個待處理的模塊和 function values 的列表

• \(Visited\) 是已處理過的模塊和 function definitions 的集合

• \(H_R : Loc \rightarrow P(Loc)\) 是從某個代碼位置到一組代碼位置的映射，\(l' \in H(l)\) 意味著在位置 \(l'\) 創(chuàng)建的對象在 \(l\) 被動態(tài)屬性讀取了

• \(H_W : \{ Loc \times String \times Loc \}\) 是三元組 \((l, p, l')\) 的集合，意味著位置 \(l'\) 創(chuàng)建的對象通過動態(tài)屬性訪問被寫入了位置 \(l\) 創(chuàng)建的對象的屬性 \(p\) 上

• \(loc : Object \rightarrow Loc\)；\(this : Object \rightarrow Object\)

運行一個函數 \(f\) 會有些麻煩：\(f\) 需要參數，也可能訪問 arguments 和 this。使用 JS 的 proxy object：創(chuàng)建一個全局對象 \(p \star\)，通過 f.apply(w, p★) 來運行，若 this(f) 已定義，則 w = this(f)，否則 w = p★。然后根據 JS 代碼選擇不同的操作：

• 創(chuàng)建對象：把對象 \(v\) 和位置 \(l\) 加入到 \(loc\) 映射中

• 函數定義：把 function value \(v\) 和位置 \(l\) 加入到 \(loc\) 映射中，如果 \(loc(v) \notin Visited\) 那么就加入到 \(Worklist\) 中去

• 函數調用：1. 如果 v = p★ 那么直接返回 p★；2. 如果函數是一個 Node.js 標準庫函數，那么使用 mock 替換可能與外部環(huán)境交互的函數，模擬函數會立即調用所有作為參數傳入的回調，并以 p★ 作為返回值；3. 如果是 JS 標準庫函數，對于某些構造 object 等特殊的函數需要特殊處理（Object.create 被看作創(chuàng)建對象，Object.defineProperty 被看作動態(tài)寫屬性）；4. 普通函數調用，function value 被移進 \(Visited\)，從 \(Worklist\) 里面移出。

• 靜態(tài)屬性讀：若 v = p★，則通過代理機制將 p★ 作為結果值

• 靜態(tài)屬性寫：若 v = p★，則本次寫入被忽略

• 動態(tài)屬性讀：通過將 \(loc(v)\) 加入 \(H_R(l)\) 收集一次讀提示，然后按常規(guī)方式完成讀取

• 動態(tài)屬性寫：將三元組 \((loc(v), p, loc(v′′))\) 加入 \(H_W\) 收集一次寫提示

Reducing unsoundness of static call graph and points-to analysis

靜態(tài)分析是一個傳統(tǒng)的，基于子集規(guī)則的，流不敏感和上下文不敏感的方法。

前面幾個規(guī)則比較簡單，我們更關注最后兩條使用動態(tài)分析信息輔助的靜態(tài)分析規(guī)則?；仡檮討B(tài)分析過程，若在位置 \(l\) 的動態(tài)屬性讀取操作 \(E[E']\) 的近似執(zhí)行過程中，觀察到一個源自位置 \(l'\) 的對象作為結果值，則會生成讀提示 \(l' \in H_R(l)\)。對于每一個這樣的提示，我們將對應的抽象值 \(t_{l'}\) 加入該表達式的抽象結果中，即 \(t_{l'} \in \llbracket E[E'] \rrbracket\)。

寫提示 \(H_W\) 的處理方式類似。若在動態(tài)屬性寫入操作 \(E[E'] = E''\) 的近似執(zhí)行過程中，一個源自 \(l''\) 的對象被寫入到源自 \(l\) 的對象的屬性 \(p\) 上，則會生成寫提示 \((l, p, l'') \in H_W\)。因此，我們只需將建模自 \(l''\) 的抽象值 \(t_{l''}\) 加入建模自 \(l\) 的抽象值 \(t_l\) 的屬性 (p) 中，即 \(t_{l''} \in \llbracket t_l.p \rrbracket\)。一個重要特性是：它們能夠更精確地捕獲“被寫入的抽象對象—屬性名—被寫入的抽象值”三者之間的關聯(lián)信息。