DOI: 10.5281/zenodo.5821007
title: Static Stack-Preserving Intra-Procedural Slicing of WebAssembly Binaries

description: # About this artifact<br> This artifact contains the implementation and the results of the evaluation of a<br> static slicer for WebAssembly described in the ICSE 2022 paper titled "Static<br> Stack-Preserving Intra-Procedural Slicing of WebAssembly Binaries". The artifact contains a docker image (`wassail-eval.tar.xz`) that contains<br> everything necessary to reproduce our evaluation, and the actual data resulting<br> from our evaluation:<br> 1. The implementation of our slicer (presented in Section 4.1) is included in<br> the docker machine, and is available publicly here:<br> https://github.com/acieroid/wassail/tree/icse2022<br> 2. Test cases used for our evaluation of RQ1 are included in the docker machine<br> and in the `rq1.tar.xz` archive.<br> 3. The dataset used in RQ2, RQ3, and RQ4 is included in the docker machine.<br> 4. The code needed to run our evaluation of RQ2, RQ3, and RQ4 is included in the<br> docker machine.<br> 5. The scripts used to generate the statistics and graphs that are included in<br> the paper for RQ2, RQ3, and RQ4 are included in the docker machine and as the<br> `*.py` files in this artifact.<br> 6. The data of RQ5 that has been used in our manual investigation is included in<br> the docker machine and in the `rq5.tar.xz` archive, along with<br> `rq5-manual.txt` detailing our manual analysis findings. # How to obtain it<br> Our artifact is available on Zenodo at the following URL: https://zenodo.org/record/5821007 # Setting up the Docker image<br> ## Downloading The Artifact<br> The artifact is available at the following URL: https://zenodo.org/record/5821007 ## Loading The Docker Image<br> Once the artifact is downloaded in the file `icse2022slicing.tar.xz`, it can be extracted and loaded into Docker as follows (this takes a few minutes):<br> ```<br> docker import icse2022slicing.tar.xz<br> ```<br> To simplify further commands, you can tag the image using the printed sha256 hash of the image: if the `docker import` command resulted in the hash `54aa9416a379a6c71b1c325985add8bf931752d754c8fb17872c05f4e4b52ea2`, you can run:<br> ```<br> docker tag 54aa9416a379a6c71b1c325985add8bf931752d754c8fb17872c05f4e4b52ea2 wassail-eval<br> ``` Once the Docker image has been loaded, you can run the following commands to<br> obtain a shell in the appropriate environment:<br> ```<br> docker volume create result<br> docker run -it -v result:/tmp/out/ wassail-eval bash<br> su - opam<br> ``` # Reproducing results of RQ1<br> Our manual translations of the "classical" examples are included in the `rq1/`<br> directory (available in the docker image and in `rq1.tar.xz`). We<br> include the slices computed by our implementation in the `rq1/out/` directory. A slice can be produced for each example in the docker image as follows, where<br> the first argument is the name of the program being sliced, the second the<br> function index being sliced, the third the slicing criterion (indicated as the<br> instruction index, where instructions start at 1), and the last argument is the<br> output file for the slice: ```<br> cd rq1/<br> wassail slice scam-mug.wat 5 8 scam-mug-slice.wat<br> wassail slice montreal-boat.wat 5 19 montreal-boat-slice.wat<br> wassail slice word-count.wat 1 41 word-count-slice1.wat<br> wassail slice word-count.wat 1 43 word-count-slice2.wat<br> wassail slice word-count.wat 1 39 word-count-slice3.wat<br> wassail slice word-count.wat 1 45 word-count-slice4.wat<br> wassail slice word-count.wat 1 37 word-count-slice5.wat<br> wassail slice agrawal-fig-3.wat 3 38 agrawal-fig-3-slice.wat<br> wassail slice agrawal-fig-5.wat 3 37 agrawal-fig-5-slice.wat<br> ``` The slice results can then be inspected manually, and compared with the original<br> version of the .wat program to see which instructions have been removed, or with<br> the expected solutions in the `out/` directory, e.g. by running:<br> ```<br> diff word-count-slice1.wat out/word-count-slice1.wat<br> ```<br> (No output is expected if the slice is correct) # Reproducing results of RQ2, RQ3, and RQ4<br> For these RQ, we include the data resulting from our evaluation, but we also<br> allow reviewers to rerun the full evaluation if needed. However, such an<br> evaluation requires a heavy machine and takes quite some time (4-5 days to run<br> to completion with a 4 hours timeout). In our case, we used a machine with 256<br> GB of RAM and a 64-core processor with HyperThreading enabled, allowing us to<br> run 128 slicing jobs in parallel. ## Runnig the Evaluation<br> We explain how to run the full evaluation, or only a partial evaluation below.<br> One can directly skip to the next section and reuse our raw evaluation results,<br> provided alongside this artifact. ### Running the Full Evaluation<br> In order to reproduce our evaluation, you can run the following commands in the<br> docker image. It is recommended to run them in a tmux session if one wants to<br> inspect other elements in parallel (tmux is installed in the docker image). The<br> timeout (set to 4 hours per binary, like in the paper) can be decreased by<br> editing the `evaluate.sh` script (vim is installed in the docker image). This is expected to take 2-3 days of time, on a machine with 128 cores.<br> In order to produce only partial results, see the next section. ```<br> cd filtered<br> cat ../supported.txt | parallel --bar -j 128 sh ../evaluate.sh {}<br> ``` The results are outputted in the `/tmp/out/` directory. ### Running a Partial Evaluation<br> If one does not have access to a high-end machine with 128 cores nor the time to<br> run the full evaluation, it is possible to produce partial results. To do so,<br> the following commands can be run. This will run the evaluation on the full<br> dataset in a random order, which can be stopped early to represent a partial<br> view of our evaluation, on a random subset of the data. In order to gather more<br> datapoints, it is also advised to decrease the timeout in the `evaluate.sh`<br> file, for example to 20 minutes by setting `TIMEOUT=20m` with `nano<br> evaluate.sh`. The number of slicing jobs running in parallel can also be<br> decreased to match the number of processors on the machine running the<br> experiments (the `-j 128` argument in the following command runs 128 parallel<br> jobs) ```<br> sudo chown opam:opam /tmp/out/<br> cd filtered<br> shuf ../supported.txt | parallel --bar -j 128 sh ../evaluate.sh {}<br> ``` The evaluation results will be stored in the `/tmp/out/` directory. ### Skipping the Evaluation Run<br> Instead of rerunning the evaluation, one can rely on our full results included<br> in the `data.txt.xz` and `error.txt.xz` archives. These can simply be downloaded<br> from within the Docker machine and extracted in `/tmp/out/`: ```<br> cd /tmp/out/<br> wget https://zenodo.org/record/5821007/files/data.txt.xz<br> wget https://zenodo.org/record/5821007/files/error.txt.xz<br> unxz data.txt.7z<br> unxz error.txt.7z<br> ``` ## Processing the data In order to process this data, we included multiple python script.<br> These require around 100GB of RAM to load the full dataset in memory.<br> The scripts should be run with Python 3.<br> When running this in the docker image, first run `cd /tmp/out/ && cp /home/opam/*.py ./`<br> - To count the number of functions sliced, run `cut -d, -f 1,2 data.txt | sort<br> -u | wc -l`. This takes around 6 minutes to run on the full dataset.<br> - To count the total number of slices encountered, run `wc -l data.txt<br> error.txt`. This takes around 15 seconds to run.<br> - To count the number of errors encountered, run `wc -l error.txt`. This takes<br> around 1 second to run.<br> - To produce data and graphs regarding the sizes and timing, run `python3<br> statistics-and-plots.py`. This will output the statistics presented in the<br> paper, along with Figure 2 (rq2-sizes.pdf) and Figure 3 (rq2-times.pdf). This<br> script takes around 35 minutes to run.<br> - To find the executable slices that are larger than the original programs, run<br> `python3 larger-slices.py &gt; larger.txt`. This script takes around 2h30 to<br> run. It will list the slice using the notation `filename function-sliced<br> slicing-criterion` in the larger.txt file, from which the slice can be<br> recomputed by running `wassail slice function-sliced slicing-criterion<br> output.wat` in the docker image. It will also output statistics regarding<br> these slices, which you can easily inspect by running `tail larger.txt`.<br> - To investigate slices that could not be computed, run:<br> ```<br> sed -i error.txt -e 's/annotation,/annotation./'<br> python3 errors.py<br> ```<br> This will take a few seconds to run and will print a summary of the errors<br> encountered during the slicing process, and requires some manual sorting to map<br> to the categories we discuss in the paper. Here is a summary of the errors<br> encountered and their root cause: ### Root Cause: Unsupported Usage of br_table<br> Error: (Failure"Invalid vstack when popping 2 values")<br> Error: (Failure"Spec_inference.drop: not enough elements in stack")<br> Error: (Failure"Spec_inference.take: not enough element in var list")<br> Error: (Failure"unsupported in spec_inference: incompatible stack lengths (probably due to mismatches in br_table branches)")<br> ### Root Cause: Unreachable Code<br> Error: (Failure"Unsupported in slicing: cannot find an instruction. It probably is part of unreachable code.")<br> Error: (Failure"bottom annotation")<br> Error: (Failure"bottom annotation. this an unreachable instruction") # RQ5: Comparison to Slicing C Programs<br> For this RQ, we include the following data in the `rq5.7z` archive, and in the `rq5/` directory in the docker image:<br> - The slicing subjects in their C and textual wasm form in `rq5/subjects/`<br> - The CodeSurfer slices in their C and textual wasm form in `rq5/codesurfer/`<br> - Our slices in their wasm form in `rq5/wasm-slices/` As this RQ requires heavy manual comparison, we do not expect the reviewers to<br> reproduce all of our results. We include a summary of our manual investigation<br> in `rq5-manual.txt`. In order to validate these manual findings, one can for<br> example inspect a specific slice. For example, the following line in<br> `rq5-manual.txt`: ```<br> adpcm_apl1_565_expr.c.wat INTERPROCEDURAL<br> ``` can be validated as follows:<br> ```<br> cd ~/<br> # This generates a trimmed down version of the CodeSurfer slice, only containing the function of interest<br> wassail count-in-slice rq5/codesurfer/adpcm_slices/adpcm_apl1_565_expr.c.wat slice.wat<br> # This compares the CodeSurfer slice with our slice<br> diff --side-by-side slice.wat rq5/adpcm_apl1_565_expr.c.wat<br> ``` In this case, most extraneous instructions are present in the CodeSurfer slices,<br> at the end of the function. This indicates that these are present in order to<br> preserve interprocedural behavior, which corresponds to the `INTERPROCEDURAL`<br> tag in the `rq5-manual.txt`