Dynamic Slicing of WebAssembly Binaries

This is the replication package that accompanies the paper titled: "Dynamic Slicing of WebAssembly Binaries". # Slices dataset ## Generating the dataset The dynamic slices have been generated with [P-ORBS](https://syed-islam.github.io/research/program-analysis/#observation-based-program-slicing-orbs). The steps and scripts to generate the dynamic slices are included in the `slicing-steps/` directory. These steps also describe how to generate the `stats.csv` file that is included in this dataset. The static slices have been generated with [wassail](https://github.com/acieroid/wassail). The scripts to generate the static slices are included in the current directory (`generate-static-slices.sh` which relies on `run_wassail.sh`). These steps generate the file `static-stats.csv` that is included in this dataset. The `original-size.csv` file, included in this dataset, can be generated as follows: ```sh find subjects-wasm-extract-slice -name \*.c.wat -exec c_count {} \; | grep subjects > counts.txt echo 'slice,original fn slice' > evaluation/original-sizes.csv sed -E 's|^(.*) subjects-wasm-extract-slice/[^/]*/([^/]*)/.*$|\2,\1|' counts.txt >> evaluation/original-sizes.csv ``` The numbers in Table 1 of the paper (the list of programs in the dataset along with their sizes) can be generated as follows. For the WebAssembly files, we can count the function size: ``` find subjects-wasm-extract-slice -name \*.c.wat -exec c_count {} \; | grep subjects > counts.txt sed -E 's|^(.*) subjects-wasm-extract-slice/([^/]*)/.*$|\1 \2|' counts.txt | python evaluation/table1-wasm-mean.py ``` or the full program size: ``` find subjects-wasm-extract-slice -name t.wat -exec c_count {} \; | grep subjects > counts.txt sed -E 's|^(.*) subjects-wasm-extract-slice/([^/]*)/.*$|\1 \2|' counts.txt | python evaluation/table1-wasm-mean.py ``` ## Structure of the dataset The dataset is structured as follows: - `subjects/` contains the instrumented `.c` source code, along with scripts to generate the dynamic slices. The original source code can be obtained by removing the line `printf("\nORBS:%x\n....`. - `subjects-wasm-extract-slice/` contains the original WebAssembly programs to slice. Each program has two files: `t.wat` is the full binary file, and `name.c.wat` is the binary code of the function containing the slicing criterion. - `all_slices/` contains the slices. For example, program `adpcm_ah1_254_expr` has the following files - `adpcm/adpcm_ah1_254_expr/EWS_adpcm.wat`: the EWS slice - `adpcm/adpcm_ah1_254_expr/SEW_adpcm.wat`: the SEW slice - `adpcm/adpcm_ah1_254_expr/ESW_adpcm.wat`: the ESW slice - `adpcm/adpcm_ah1_254_expr/static_adpcm.wat.slice`: the SWS slice The other files are produced by intermediary steps and can be ignored. They are: - `adpcm/adpcm_ah1_254_expr/ESW_adpcm.wat.orig`: original (unsliced) binary *file* from which SW and ESW slices are computed - `adpcm/adpcm_ah1_254_expr/SEW_adpcm.wat.orig`: original (unsliced) binary *function* from which SEW slice is computed - `adpcm/adpcm_ah1_254_expr/SW_adpcm.wat`: slice of entire binary file from which ESW slice is extracted - `adpcm/adpcm_ah1_254_expr/WS_adpcm.wat`: compiled (binary) version of dynamic C slice from which EWS slice is extracted # Research questions ## RQ1 The script `./RQ1.py` found in the `evaluation/` directory generates: - Figure 3 (time.pdf) - The mean, min, max, and stddev of the times - How many slices are computed below 10, 100, 1000, and 10000 seconds ## RQ2 The script `./RQ2.py` found in the `evaluation/` directory generates: - Figure 4 (loc.pdf) - The mean, median, min, max, and stddev of the sizes - The largest differences between the approaches - The number of slices larger than the original program ## RQ3 and RQ4 The process for these research questions is manual and requires comparing slices. It cannot be automated. We did make heavy use of `diff --side-by-side` in this analysis.本复现包配套于题为《WebAssembly二进制程序动态切片》的论文。 # 切片数据集 ## 数据集生成 动态切片已通过[P-ORBS](https://syed-islam.github.io/research/program-analysis/#observation-based-program-slicing-orbs)生成。生成动态切片的步骤与脚本收录于`slicing-steps/`目录中，该目录同时说明了如何生成本数据集包含的`stats.csv`文件。 静态切片已通过[wassail](https://github.com/acieroid/wassail)生成。生成静态切片的脚本收录于当前目录（`generate-static-slices.sh`，其依赖`run_wassail.sh`），该流程将生成本数据集包含的`static-stats.csv`文件。 本数据集包含的`original-size.csv`文件可通过如下命令生成： sh find subjects-wasm-extract-slice -name *.c.wat -exec c_count {} ; | grep subjects > counts.txt echo 'slice,original fn slice' > evaluation/original-sizes.csv sed -E 's|^(.*) subjects-wasm-extract-slice/[^/]*/([^/]*)/.*$|2,1|' counts.txt >> evaluation/original-sizes.csv 论文中表1所列内容（数据集内程序列表及其规模）可通过如下方式生成。针对WebAssembly文件，可通过以下方式统计函数规模： find subjects-wasm-extract-slice -name *.c.wat -exec c_count {} ; | grep subjects > counts.txt sed -E 's|^(.*) subjects-wasm-extract-slice/([^/]*)/.*$|1 2|' counts.txt | python evaluation/table1-wasm-mean.py 或统计完整程序规模： find subjects-wasm-extract-slice -name t.wat -exec c_count {} ; | grep subjects > counts.txt sed -E 's|^(.*) subjects-wasm-extract-slice/([^/]*)/.*$|1 2|' counts.txt | python evaluation/table1-wasm-mean.py ## 数据集结构 本数据集结构如下： - `subjects/` 目录包含插桩后的`.c`源代码，以及用于生成动态切片的脚本。原始源代码可通过移除`printf(" ORBS:%x ....`这一行得到。 - `subjects-wasm-extract-slice/` 目录包含待切片的原始WebAssembly程序。每个程序包含两个文件：`t.wat`为完整二进制文件，`name.c.wat`为包含切片准则的函数对应的二进制代码。 - `all_slices/` 目录包含所有切片。以程序`adpcm_ah1_254_expr`为例，其包含如下文件： - `adpcm/adpcm_ah1_254_expr/EWS_adpcm.wat`：EWS切片 - `adpcm/adpcm_ah1_254_expr/SEW_adpcm.wat`：SEW切片 - `adpcm/adpcm_ah1_254_expr/ESW_adpcm.wat`：ESW切片 - `adpcm/adpcm_ah1_254_expr/static_adpcm.wat.slice`：SWS切片 其余文件为中间步骤产物，可忽略，具体包括： - `adpcm/adpcm_ah1_254_expr/ESW_adpcm.wat.orig`：用于生成SW与ESW切片的原始（未切片）二进制文件 - `adpcm/adpcm_ah1_254_expr/SEW_adpcm.wat.orig`：用于生成SEW切片的原始（未切片）二进制函数 - `adpcm/adpcm_ah1_254_expr/SW_adpcm.wat`：用于提取ESW切片的完整二进制文件切片 - `adpcm/adpcm_ah1_254_expr/WS_adpcm.wat`：用于提取EWS切片的动态C切片编译后的二进制版本 # 研究问题 ## 研究问题1 位于`evaluation/`目录下的脚本`./RQ1.py`可生成： - 图3（time.pdf） - 耗时的均值、最小值、最大值与标准差 - 耗时低于10秒、100秒、1000秒与10000秒的切片数量 ## 研究问题2 位于`evaluation/`目录下的脚本`./RQ2.py`可生成： - 图4（loc.pdf） - 规模的均值、中位数、最小值、最大值与标准差 - 各切片方法间的最大规模差异 - 规模大于原始程序的切片数量 ## 研究问题3与研究问题4 这两个研究问题需手动完成切片对比，无法自动化实现。本分析过程大量使用了`diff --side-by-side`命令。