这是一个艰难的决定：研究 WebAssembly 调用图构建的挑战

本仓库包含论文 "That’s a Tough Call: On Static Call Graph Construction for WebAssembly Binaries"（ISSTA'23）的补充材料。

通过 Docker 运行

构建镜像

要构建该工件，只需运行：

git clone <this repo>
cd wasm-call-graphs
chmod +x setup.sh && ./setup.sh
docker build -t toughcall .

该镜像本身在磁盘上约为 6 GB，构建时间介于 15 到 30 分钟之间，具体取决于硬件和网络连接。

运行镜像

以下命令将以守护模式启动 toughcall Docker 容器，这意味着 docker 容器在后台运行，并且可以连接。

docker run -d -t -i -p 3000:3000 -p 5000:5000 toughcall
# The container ID will be written to the console.

连接容器时需要容器 ID。你可以通过运行 docker ps 并记录名为 toughcall 的容器的 ID 来恢复容器 ID。你可以使用 docker stop <container-id> 停止容器。如果收到端口被占用的错误，你可以选择在不同的端口上运行，或者停止当前正在运行的容器，然后在同一端口上重新运行 run 命令。

要连接到容器，请运行：

docker exec -it <container-id> bash

容器结构

容器的组织方式如下。

/home/toughcall/
- challenges-prevalence/: 用于研究调用图挑战普遍性的评估脚本（第 3 节）。
  - figures/: 论文中出现的图表。
  - wasm/: Rust WebAssembly 解析器和分析库的源代码。
  - scripts/: 用于分析 WasmBench 的脚本以及提取的数据。
- data/: 微基准测试和真实世界程序的原始数据。
  - microbenchmarks-raw-data/
  - real-world-programs-raw-data/
  - tables/: 论文中表格的 .tex 文件。
  - microbenchmarks-processed-data.json/: 来自微基准测试的处理后数据。
  - real-world-processed-data.json/: 来自真实世界程序的处理后数据。
- evaluation/: 用于研究各种静态分析的正确性（以及微基准测试的精确性）的评估脚本。
  - instrumented-real-world-programs/: 已使用 Wasabi 进行插桩的真实世界程序。
  - metadce-inputs/: MetaDCE 工具的输入。
  - scripts/:
    - analysis.py/: 对真实世界程序和微基准测试运行分析。
    - get-dyn-data.py/: 读取 Wasabi 输出文件并将数据保存到 JSON 文件中。
    - get-static-data.py/: 获取给定 WebAssembly 二进制的静态数据。
    - get-tools-data.py/: 在传入的 Wasm 文件上运行所有正在评估的工具。
    - instrument-test.sh/: 用于插桩 npm 应用程序以使用 Wasabi 收集数据的 Bash 脚本。
    - latexify.py/: 从处理后数据生成 ASCII 和 LaTeX 表格。
    - run-eval.py/: 对真实世界程序和微基准测试运行评估。
- microbenchmarks/: 包含其构建和运行脚本的微基准测试集合。
- real-world-programs/: 从 NPM 和 GitHub 收集的代码。

Sanity Check

本节展示了该工件的一般工作流程。假设您位于 Docker 容器中。运行完本节内容后，应能确认该工件可正常运行。

这是什么工件？

该工件是一个自包含的环境，用于复现 ISSTA'23 论文 "That’s a Tough Call: Studying the Challenges of Call Graph Construction for WebAssembly" 的评估。该工件包含 25 个微基准测试和 10 个真实世界的 npm 应用程序，用于评估各种 WebAssembly 静态分析工具和框架。该工件会自动构建这些工具，从每个被评估的微基准测试和应用程序中的 WebAssembly 二进制文件中提取静态和动态信息，并在它们上运行每个工具。所有中间数据都已存储在每次评估运行中，并且可以进行检查。

运行以下命令以运行整个评估：

cd /home/toughcall/evaluation/scripts
python3 run-eval.py --all-fresh

您应该看到论文中 LaTeX 表格的 ASCII 表格。例如：

+--------------------------------------------------------------------+
|        Evaluation of each tool against the microbenchmarks         |
+---------------------------+---------+-----------+---------+--------+
|            Name           | Wassail | WAVM+LLVM | MetaDCE | Twiggy |
+---------------------------+---------+-----------+---------+--------+
|                           |  S   P  |   S   P   |  S   P  | S   P  |
|     direct-call-simple    |  ✓   ✓  |   ✓   ✓   |  ✓   ✓  | ✓   ✓  |
|   direct-call-transitive  |  ✓   ✓  |   ✓   ✓   |  ✓   ✓  | ✓   ✓  |
| direct-call-imported-func |  ✓   ✓  |   ✓   ✓   |  ✓   ✓  | ✓   ✓  |
|     entry-point-start     |  ✓   ✓  |   ✓   ✓   |  ✓   ✓  |   -    |
|                                 ...                                |
+--------------------------------------------------------------------+

注意：如果您收到来自 npm 的错误，提示您安装更新版本的 npm，只需重新运行该脚本即可。该错误不应再次出现。

工件详细描述

我们现在将描述工件中使用的各种脚本及其输出。

`get-static-data.py`

此脚本分析给定的 WebAssembly 二进制文件，并报告关于该二进制文件的静态信息。具体而言，它报告以下信息：

类型段中的类型数量。
二进制文件中的函数数量。
关于二进制文件中表的详细信息，包括其大小、类型、元素段如何初始化以及所有条目。
关于导入和导出段的详细信息，包括导入/导出的总数、导入/导出的函数以及是否导入了/导出了表或内存段。
关于导入的详细信息，包括导入类型、模块名称、导出名称和内部 ID。
关于导出的详细信息，包括导出类型、名称和内部 ID。
将内部函数 ID 映射到调试名称的调试名称。
关于二进制文件中调用的详细信息，包括每个调用、调用总数和唯一调用数。
关于二进制文件中间接调用的详细信息，包括间接调用总数和间接调用的函数类型。

`instrument-test.sh` 和 `get-dyn-data.py`

instrument-test.sh 使用动态分析框架 Wasabi 对你的 npm 应用程序进行插桩。它通过为所有调用、函数开头和存储指令生成钩子，使用 Wasabi 对给定的 WebAssembly 文件进行插桩。

get-dyn-data.py 随后运行插桩后的 npm 应用程序，并报告在该次应用程序运行中可达的导出函数和内部函数。这在后续评估中用于确定调用图分析工具是否健全且精确。以下是该脚本在库 shiki 的测试上运行时的示例输出。

Running tests for shiki...

shiki/example-cpp
7 exported functions are reachable.
518 callsites have been analyzed.
103 functions are the lower bound for the analysis.

shiki/example-js
7 exported functions are reachable.
437 callsites have been analyzed.
85 functions are the lower bound for the analysis.

shiki/example-bash
7 exported functions are reachable.
414 callsites have been analyzed.
91 functions are the lower bound for the analysis.

`get-tools-data.py`

此脚本在传入的 WebAssembly 文件上运行所有正在评估的工具。首先，提取每个工具生成的调用图。记录执行时间。随后，将调用图规范化为标准表示形式。如果工具执行了死代码消除，则同样记录并标准化其结果。每个工具的调用图以及 stdout 和 stderr 均位于 data/<real/micro>/lib/tool-evaluation-data/<tool>/。该脚本在 stdout 上报告工具是否成功运行于 WebAssembly 二进制文件、执行耗时，或者在失败的情况下，错误记录的位置，以及工具确定有多少个函数是可到达的。在 fonteditor-core/woff2.wasm 上运行的脚本输出如下所示：

Computing set of reachable functions for each tool being evaluated...
Executing wassail        ...SUCCESS. 1.05ms
Executing wasm-metadce   .....ERROR. Error recorded in fonteditor-core/tool-evaluation-data/metadce/output.txt.
Executing twiggy IR      ...SUCCESS. 0.86ms
Executing twiggy garbage ...SUCCESS. 1.31ms
Executing wavm           ...SUCCESS. 1.13ms
Executing llvm-as        ...SUCCESS. 1.19ms
Executing opt            ...SUCCESS. 1.15ms
1118 reachable functions computed for wassail.
 345 reachable functions computed for wavm.
 345 reachable functions computed for twiggy.

`analysis.py` 和 `latexify.py`

analysis.py 概述了为每个微基准测试和真实世界程序计算并存储的原始数据。对于真实世界程序，它将计算出的调用图与使用 Wasabi 提取的动态可达性信息进行比较，并确定是否存在缺失的函数（这是不健全性的指示）或正确移除的函数（这是调用图精确度的指示）。它为每一项计算绝对值和百分比。对于微基准测试，它将每个工具生成的调用图与手写的精确调用图进行比较，并确定健全性和精确度。所有分析数据，以及每个程序的静态、动态和特定于工具的数据，都存储在 data/microbenchmarks-processed-data.json 或 data/real-world-processed-data.json 中。

这些 JSON 文件由 latexify.py 读取，以创建在运行评估结束时看到的三个 ASCII 表格（以及 LaTeX 表格）。具体而言，

标题为 Evaluation of each tool against the microbenchmarks 的表格对应于论文中的表 1。
标题为 Coverage of each test case for its library 的表格对应于论文中的表 2。
标题为 Evaluation of the soundness of existing call graph analyses on real-world programs 的表格对应于论文中的表 3。

`run-eval.py`

评估可以通过 run-eval.py 脚本轻松重新运行。该脚本根据传入的不同选项，交错运行上述各个脚本。在全新评估（--all-fresh）中，它为每个 WebAssembly 文件提取静态信息，使用 Wasabi 为每个应用程序计算（动态提取的）可达函数集合，并为每个被评估的工具计算可达函数集合。然后，它对所有提取的数据进行分析，将相关数据转换为 LaTeX 格式，同时在标准输出上报告结果。该脚本还具有选项，仅重新运行评估的特定部分，例如选项 --real --eval-tools，它会在所有真实世界程序上重新运行工具。可以使用 --help 探索这些选项。

扩展工件

任何希望针对 WebAssembly 进行静态分析原型设计的研究人员或开发人员都可能从该工件中受益。我们关于在后端使用 WebAssembly 的 JS 应用程序的数据集是首创的（大多数论文使用编译为 WebAssembly 的 PolyBench），并且如论文中所述，对于评估新的静态分析至关重要。此外，get-tools-data.py 可以轻松扩展，以针对微基准测试中的不同挑战以及当前最先进水平评估新的调用图分析。具体而言，扩展脚本以支持新工具需要进行以下添加：

添加一个新函数 run_tool，用于在指定的 WebAssembly 二进制文件上运行该工具。
添加一个新函数 process_tool，用于处理由前一个函数提取的数据。根据输出格式，此函数可以利用对函数 replace_graph_nodes_with_id 或 replace_names_with_internal_ids 的调用，将可达性图规范化为标准表示。然后可以调用函数 get_reachable_funcs_and_edges 或 get_reachable_funcs_from_dot 从一组初始可达函数中提取可达函数。

本地运行

如果您想自行运行我们的分析和评估，以下是所需软件和输入数据的大致列表：

OS: Ubuntu 20.04 LTS
Wasmtime 作为符合 WASI 标准的 WebAssembly VM，参见 https://github.com/bytecodealliance/wasmtime
WABT 用于各种 WebAssembly 二进制检查工具，参见 https://github.com/WebAssembly/wabt
Rust 发行版 > 版本 1.60（rustc、cargo 等），参见 https://rustup.rs/
Python >3.9
WasmBench 作为流行性研究的数据集，参见 https://github.com/sola-st/WasmBench/
现有的静态分析工具：
- Wassail: https://github.com/acieroid/wassail
- Binaryen (metadce): https://github.com/WebAssembly/binaryen
- Twiggy: https://github.com/rustwasm/twiggy
- WAVM: https://github.com/WAVM/WAVM
- LLVM-opt，版本 12（用于获取 WAVM LLVM 输出的调用图）：https://llvm.org/

许可证

我们所有的分析程序均采用 Apache 2 许可证，参见 LICENSE。我们不对我们评估和在此重新分发的任何 WebAssembly 程序主张所有权或版权，仅出于研究目的重新分发。所有程序均来自公开来源。