WasmWalker: Path-based Code Representations for Improved WebAssembly Program Analysis

WebAssembly (Wasm) is a cross-platform low-level binary format that enables browsers to execute code with near-native performance. Wasm is an open standard, currently maintained by the World Wide Web Consortium (W3C). The technology was created as a collaboration between W3C, Mozilla, Google, Microsoft, and Apple [17]. The development of Wasm began in 2015, and version 1.0 was officially released in 2017. Wasm seeks to go beyond the limitations of JavaScript, providing a secure platform for executing programs in web browsers. Some of JavaScript’s problems include: 1) its dynamic nature requires heroic efforts to execute efficiently; 2) as a client-side language, JavaScript has limited access to memory and the file system; and 3) JavaScript’s multiprocessing capabilities are restricted. Wasm was developed with the aim of filling these gaps. In terms of facilitating the deployment of platform-independent code and providing a security model that ensures that the system functions in a secure and reliable manner, the role of Wasm on the client is comparable to the role that Java performed in the early 2000s on the server with the Java Virtual Machine.

Wasm is becoming more and more popular: Wasm’s adoption has created new opportunities for web development, enabling programmers to consider using Wasm in performance-critical applications, such as cloud computing, video conferencing, and gaming. Some well-known programming languages, including C, C++, and Rust, now have Wasm compilers available. Wasm’s popularity serves as an invitation for more tools and techniques to be created to support this newly-emerged technology.

This context motivated us to develop new tools and techniques for static analysis of Wasm. We focus particularly on techniques that can help with deep learning: the application of deep learning in static analysis has brought about significant advancements in the field. Deep learning models are able to analyze large datasets quickly and can predict properties of unseen data with high accuracy and consistency. This has made deep learning one of the most popular tools for static analysis, and its popularity is growing as the learning methods are constantly evolving. Deep learning can be used for many interesting properties that we target in static analysis. For instance, researchers have developed deep learning tools to detect security vulnerabilities in high level programming languages [29, 44, 7], and also native binaries [4]. Other applications include defect prediction [31, 34] and clone detection [28, 42].

The input provided to deep learning models greatly impacts their performance and accuracy. If the input contains the right information and is structured correctly, models can make highly-accurate predictions. However, if the input data contains redundant information or is poorly structured, this can slow down the training process and reduce the accuracy of the models. Our primary goal is to devise a useful structure for providing information about code as input to models.

Model inputs can be fixed-sized or variable-sized. Fixed-sized inputs work when the data’s number of features is known: datapoints are vectors of numbers. Vector dimensions are associated with defined features. In static analysis, inputs are usually programs or parts of programs. Yet, computer programs are inherently variable-sized information. Thus, to use them as inputs to, for example, feedforward neural networks, we must embed them into fixed-sized vectors—a process known as code embedding [11]. Researchers have proposed many approaches for embedding high-level code [2, 14, 10, 3] and native binaries [8, 45, 36, 43].

Unlike fixed-sized inputs, variable-sized inputs do not have an a priori known number of features. Variable-sized inputs are typically used when features are more complex and cannot be easily transformed into numerical values. In the case of static analysis, the input can directly be the sequence of program statements. More complex (and hence more expensive) deep learning models, including RNNs, LSTMs [20], Transformer Networks [41], and GPT-3 [9], process variable-sized inputs.

In this project, we aim to make information extracted from Wasm ASTs available as input to deep learning models. Towards this goal, we introduce WasmWalker, a pipeline for extracting AST information from Wasm binaries and representing that information as both fixed-sized and variable-sized model inputs. Using WasmWalker, we conducted an empirical study to find the most frequent paths that emerge in the abstract syntax tree of WebAssembly Text (WAT) format of Wasm binaries across a large dataset. We used, as a primary dataset, the same one used in SnowWhite [27], a study that offers a framework for recovering precise C/C++ high level types from low-level limited Wasm type system. The dataset includes 6.3 million type-labeled Wasm samples, extracted from 300,905 object files, which were compiled from 4,081 C and C++ Ubuntu packages. We also augmented the C/C++ dataset with a secondary set of 10 mid-to-large Rust projects to cross-check the generalizability of our paths set. We emphasize, however, that the representations that we present in this work are novel; while SnowWhite uses only a naive representation that consists of taking the last 20 instructions of a method, we propose and evaluate easy-to-compute representations that work better than SnowWhite’s naive representation. We emphasize that our novel code representations can be used in models that use either fixed-size or variable-sized inputs, versus SnowWhite, which can only be used in models which accept variable-sized inputs.

Initially, WasmWalker gathered over 800,000 root-to-leaf paths. We refined these paths to obtain a more compact and abstract representation that respects the nested structure of ASTs and the order of non-terminals within root-to-leaf paths. Our refined paths include 3,352 paths encoding conditional and loop nested structures. Building on the refined paths, we developed a fixed-sized feature vector for each Wasm function—the path vector. Each dimension of our path vectors corresponds to one of the 3,352 paths we identified, and the numerical value for that dimension represents the number of times that path occurred in the Wasm function’s AST. This construction of our path vectors yields some interpretability—there is a reason that each value in a path vector has a particular value.

Using our path vectors, we developed two different code representations for Wasm functions: (1) a (variable-sized) path sequence, that indicates the appearance of each path along with a numerical value that corresponds to the number of times that path appeares in the Wasm function, and (2) a (fixed-size) code embedding, similar to code2vec [3], that reduces the dimensionality of our path vectors from 3,352 to 50.

Although our path-based approach, which can produce code embeddings, is more broadly applicable than that of SnowWhite [27], we also carried out a head-to-head test showing improvements over that previous work. Thus, we evaluated the prediction accuracy of our code representations using the dataset provided in SnowWhite. We conducted two experiments. First, we attempted to predict actual method names based on Wasm binaries. Second, similar to SnowWhite, we aimed to recover high-level C/C++ return types from Wasm primitive types. Our findings indicate that a hybrid approach, where a selection of instructions is concatenated to our path sequence, resulted in the best models. Specifically, our new representation led to a 5.36% (11.31%) improvement in Top-1 (Top-5) accuracy in method name prediction and a 8.02% (7.92%) improvement in recovering precise return types. Also, we demonstrate the effectiveness of our embeddings in clustering method names that contain semantically similar method bodies close together.

Contributions This paper makes the following contributions:

• •

  We conduct the first empirical study of the most frequent paths in the ASTs of Wasm binaries over a large-scale dataset.

• •

  We propose two novel and easy-to-compute representations of Wasm functions: (1) a path sequence containing AST path information, and (2) a code embedding that leverages the information we gathered about paths. These representations enable the use of Wasm functions as input to deep learning techniques—even those techniques that require code embeddings as inputs. Previous approaches could only feed into variable-size inputs, whereas our representation works for both variable-size and fixed-size inputs.

• •

  We compare our approach to previous work on two deep learning use cases: method name prediction and recovering precise return types. Our path sequence in combination with Wasm instructions improves accuracy over the previous state-of-the-art.

We show that incorporating AST knowledge into the input for models analyzing Wasm binaries enhances their effectiveness. We believe our novel code representations help uncover new properties from Wasm binaries, expanding our understanding of their potential.

Data Availability Statement Our software pipeline, as well as the datasets generated and analyzed in this work, are available at the anonymyzed https://zenodo.org/records/10983638.

In this section, we demonstrate, by example, how the WasmWalker pipeline works. We start with Wasm binaries, generated from C/C++ source code using emscripten. Next, we tranform Wasm binaries to WAT files and extract AST paths from them. Finally, we show how WasmWalker computes two different code representations using the AST paths.

The primary dataset that we used in this work contains Wasm binaries that are created by compiling C/C++ code using the Emscripten toolchain, although Section 3.2 describes our evaluation of binaries generated from Rust. Emscripten [1] is an open source compiler toolchain that compiles C/C++ programs, or any other languages that use LLVM as a part of their compilation process, into WebAssembly. LLVM [21] is a compiler infrastructure that offers a set of modular and reusable compiler technologies. The LLVM Intermediate Representation (LLVM IR) is an assembly-like language that acts as a middle ground between (programmer-written) high-level code and (executable) native code. An intermediate representation makes it possible for compiler developers to only focus on writing the frontend part of the compiler and to delegate the responsibility for dealing with the target architecture to the back-end part of the compilation toolchain. Emscripten’s primary work is performed by a series of Wasm-specific optimization passes. To produce LLVM IR code, Emscripten uses Clang, which is a part of the LLVM compiler infrastructure. As a backend, i.e. to transform LLVM IR to Wasm binaries, after using LLVM’s optimizer tools to improve performance and efficiency, Emscripten uses the Binaryen tool [33] to produce Wasm binaries.

Our objective is to analyze the Wasm binary files that we obtain. However, these binary files contain a stream of binary values that make it challenging to perform structural analysis. To overcome this, we use the WebAssembly Text (WAT) format, which is a human-readable representation of Wasm code. We convert a Wasm binary to its respective WAT file using the wasm2wat module of WABT [40], a binary toolkit for Wasm. While there are some similarities between LLVM code and WAT code, they serve different purposes. LLVM files are an intermediate representation used during compilation, optimization, and code generation and are not intended for human consumption. In contrast, WAT files are commonly used for debugging and inspecting Wasm code, and they offer a tree-like structure of Wasm binaries that can be parsed into an AST for structural analysis, which is crucial for our analysis objectives.

Analogues to our WAT-based approach for other languages should be relatively straightforward to implement. Our technique leverages the fact that a structured AST is available for WAT; such an AST is generally available when compiling from source. Applying our technique to flat IRs or binaries would require first applying decompilation techniques [13, 6] to obtain a structured AST.

Figure 1 illustrates different code files that we create until we extract the necessary AST information for further analysis. Subfigure 1(a) shows the C source code for a simple sign() function that outputs the sign of its integer input. There are three possible outputs: 0 if the input is 0; and 1 or -1 if the input is a positive or negative integer, respectively. Using Emscripten, we then compile the C function to a LLVM IR function, shown in subfigure 1(b). We can select different optimization levels to create LLVM code—the code shown in the subfigure is generated using the -O3 option. At the last stage of compilation, Emscripten generates Wasm binaries, shown in subfigure 1(c). As discussed earlier, a Wasm binary is a stream of binary values. To ease analysis, we convert it to WAT format. As illustrated in subfigure 1(d), the WAT files yield a tree-like intermediate representation of Wasm binaries. We can extract all paths within this tree using a Depth-First Search (subfigure 1(e)). Note that the shown extracted paths are raw paths. We carry out a refinement process to reduce the number of paths, and only keep paths that are more semantically valuable. Section 3 discusses the refinement process in greater depth.

We extract the AST paths from all the Wasm binaries within our dataset. The total number of all the paths after refinement is 3,352. We represent each Wasm function using a feature vector, which we call the path vector. This vector has 3,352 dimensions. The $i^{\text{th}}$ element of the vector corresponds to the number of times path $i$ occurs in the AST of that function. We build two code representations using our path vectors: (1) a path sequence that is a sequential representation of the path vector, but with normalized occurrence values, and (2) a code embedding similar to that of code2vec [3], which is a distributional representation of Wasm code using fewer dimensions (namely, 50). Subfigure 1(f) shows the structure of our path vector, path sequence, and code embedding. In this subfigure, path_vector has value 2 at index 2. This means that the third path (path vector indices are zero-based) in our paths set appeared twice in our AST. path_sequence yields a sequence representation of path_vector, after removing zero-valued paths and normalizing the values. code_embedding embeds path_vector into a 50-dimensional vector using a feedforward-neural network. Like code2vec [3], creating embeddings requires a target property; in this work, we use method names as the target property, but the process works equally well with other target properties.

In the next section we describe WasmWalker, the pipeline we developed for extracting paths from WAT files. Then we discuss empirical results about extracted paths, the decisions behind our path refinement process, and more details about our code representations.

Our objective is to encode information about a complete Wasm function to an interpretable vector. Similar to Feng et al. [15], a naive approach could be to build a feature vector for a function, where the features are general metadata about the function (e.g. number of variables). The problem with that approach is that it does not contain any information about code structure. We take a different approach: we exploit information encoded in the AST structure of Wasm programs, and hence what the program does, to form feature vectors.

Wasm binaries are generally being produced by tools that leverage LLVM compiler infrastructure: in addition to supporting WebAssembly, LLVM provides a high-performance and well-documented toolchain for producing WebAssembly binaries.

However, to study the AST form of the Wasm binaries, we need to convert the binaries to WebAssembly Text (WAT) format, which provides a more structured representation of Wasm binaries. We use wasm2wat [40] for that purpose. The output of wasm2wat is a textual representation of the WebAssembly module that closely mirrors the binary format, but with additional annotations and tree-like formatting to make the module structure more clear.

To process the nested structure of WAT files, we need to linearize the paths so that we can study their content. code2vec [3] extracts all leaf-to-leaf paths in the AST. That yields a $\Theta(n^{2})$ space explosion given $n$ terminals; for further discussion, see Section 6. Unlike code2vec, we instead record all root-to-leaf paths for two primary reasons: (1) to avoid the quadratic explosion, and (2) it is not clear that terminals in WAT ASTs contain useful information. The terminals are memory offset values and can easily change with slight modifications to the original program, even when the semantics stay the same. For instance, if in an alternative implementation of a subroutine, we use an extra variable, the memory locations of other variables may shift to make room for the new variable: the compiler allocates memory for variables based on their type and size. This phenomenon is due to working at a lower (IR) level than the source AST, where the terminals are usually variable names.

Figure 2 shows an overview of how we collect the common paths, store them in our paths set, and leverage them to generate path vectors. This figure illustrates the use of emscripten and wasm2wat for transforming C/C++ code to WAT files. Then, we parse the WAT files and extract the raw paths. The raw paths are then refined (we present the refinement process in Section 3.1.1 and 3.1.2) and stored in an ordered paths set with unique numbers associated with each path.

Our pipeline, WasmWalker, traverses a WAT file’s AST using Depth-First Search and extracts paths inside the subtree of a target function, as the WAT file can contain multiple functions. We refer to internal nodes in our AST as nonterminals and the leaves as terminals. The paths start with the nonterminal “func” and end with a terminal (see subfigure 1(e)). We drop the keyword “func”, since it is the same for all paths, and also the terminal at the end. The resulting path is a sequence of nonterminals. Note that our use of “terminal” and “nonterminal” does not match their use in parsing.

WasmWalker is first applied to the training data to populate the paths set. The pipeline is then used again to generate path vectors, which contain the frequency of each path at its corresponding location in the set. The paths set is queried to obtain the index associated with a path. Each path vector also includes metadata, such as the function’s name and high-level return type, collected from DWARF debugging information.

While our primary objectives in this work are to contribute the notion of path-based representations for Wasm and that of extracting both fixed-sized and variable-sized representations from Wasm code, we do provide an comparative evaluation of our approach in cases where it can compare directly to previous work. We thus evaluate our approach on two tasks: (1) prediction of method names and (2) recovery of precise return types, using the same dataset for both evaluations. First, we provide an overview of the general characteristics of the dataset. Then we introduce the models that we created and used for evaluation. Finally, we present our results for method name prediction in Section 4.1 and for precise return type recovery in Section 4.2.

Dataset We used the same dataset introduced in SnowWhite [27] for three main reasons: (1) the dataset has been filtered and each data point is linked to a sequence of instructions, which are refined for more accurate type recovery. This provides us with a good opportunity to examine whether our insights regarding common AST paths and our path sequence can enhance accuracy results where both our approach and SnowWhite apply. (2) The dataset contains ground-truth DWARF debugging information, including function names and precise types, properties that our experiments are designed to predict. (3) To the best of our knowledge, this is the largest dataset for WebAssembly and is significantly larger than the datasets used in previous works [17, 19, 26, 22].

The dataset used in this study contains 6.3 million samples of WebAssembly code and type information obtained from 300,905 object files that were compiled from 4,081 C and C++ packages for the Ubuntu operating system. To prevent artificial inflation of results, the SnowWhite dataset curators applied some pre-processing steps, such as deduplication and discarding data points where the number of return types in WebAssembly does not match the number in C/C++ code. In addition to that, to use the wasm2wat module as part of deriving ASTs, we also discarded datapoints that take more than 30 seconds to translate to WAT files. The dataset has already been divided, based on the number of packages, into three portions, with 96% for training, 2% for early stopping and evaluating hyperparameters, and 2% reserved for a held-out test set.

Models We trained five different models to assess whether AST paths enable us to create better models for predicting properties of Wasm programs. To carry out a more accurate comparison with SnowWhite, we use the same sequence-to-sequence model as SnowWhite for predicting the types of function parameters and return values in code. The only difference between our approach and SnowWhite is that we did not use subword tokenization because it had zero impact on our model’s performance. SnowWhite uses a bidirectional LSTM model [37] with global attention [5] and dropout [39] for regularization. The model is optimized with backpropagation-through-time gradient descent using the Adam optimizer [23]. The SnowWhite authors chose hyperparameters including hidden vector dimension, number of layers, learning rate, dropout rate, and embedding dimension through experimentation. To conduct an accurate comparison, we use the same hyperparameters. The model has a total of 5.5 million learnable parameters. Both we and the SnowWhite authors also experimented with the Transformer architecture but found that the LSTM model was more effective. There are more computationally expensive LLM architectures, such as CodeBERT [16], that we could experiment with. However, this work focuses on the advantages of integrating path-awareness to Wasm code representations, and improving results in more resource-constrained environments.

We use the same sequence-to-sequence architecture for our five models, with each model receiving a different input. The first model (seq2seq-INP) receives a concatenation of the last 20 Instructions and Nested Path sequences. (Capitalized letters indicate the abbreviation mapping, e.g. INP stands for Instructions and Nested Paths.) Remember that we are concatenating two strings of different types: the sequence of the last 20 instructions (in textual, i.e. WAT, format), and a sequence of tuples representing the frequency of each nested path in our program’s AST (similar to path_sequence shown in  1(f)). We will justify our choice of the last 20 instructions in Section 5. The second model (seq2seq-ISP) is similar to the first model, except the path sequence does not reflect the 3,352 nested paths but 185 Simpler Paths after dropping if and loop subtrees, as discussed in Section 3. The third model (seq2seq-I) only receives the last 20 Instructions sequences, which is the model used in SnowWhite. The fourth model (seq2seq-NP) only receives the path sequence, reflecting the 3,352 Nested Paths. The fifth model (seq2seq-SP) is similar to the fourth model, but it uses the 185 Simpler Paths instead of the nested ones.

We chose these five models to control the type and amount of information being input to our models and to enable accurate comparisons between them. The seq2seq-INP model receives the most information, as it takes in both the instruction and path sequences, with the path sequence being nested rather than simple.

Like SnowWhite, we used OpenNMT [24] to train our models. We trained our models using Google Colaboratory Pro+. Our training setup was an Intel(R) Xeon(R) CPU with 3.7GHz clock speed and 16 cores, 85GB of RAM, and an NVIDIA P100 GPU with dedicated memory. Training of each model, including the SnowWhite-like model, took about the same amount of time, which was less than 10 minutes.

We began by extracting empirical insights from the nested structures of WAT files. These findings not only served as the foundation and main motivation for WasmWalker’s development, but also provide valuable insights in their own right. For instance, the list of least common Wasm instructions within compiled Ubuntu packages can directly assist Wasm runtime developers in assessing the compatibility of their runtimes with real-world binaries. WasmWalker is built upon empirical data comprising all AST paths found in the largest available Wasm corpus. This collected set of AST paths also serves as valuable empirical data, shedding light on the structure of WAT files. However, our goal was not merely to collect empirical data. Instead, we aimed to leverage this empirical information to create useful tools that contribute to the analysis of Wasm binaries.

Our hypothesis was that information about AST paths in Wasm can improve the effectiveness of our models. We tested this hypothesis by applying our models to two different tasks: (1) method name prediction, and (2) recovering precise return types. Our results demonstrate the adaptability and versatility of our AST-aware approach—there are fundamental differences in tool requirements for these two tasks—and also show its effectiveness. Additionally, we showed our technique’s effectiveness on a third task: the AST paths enable effective code embedding, which is challenging for non-path-aware approaches like SnowWhite.

Method name prediction and return type recovery benefit from different types of information about the program under analysis. Method name prediction usually requires analysis of the program’s control flow, while data flow analysis ought to be more helpful for recovering precise high-level types. All three tasks can be helpful for reverse engineering, detecting security vulnerabilities, and understanding the internal structures used inside the program.

Another key difference between tasks is that method name prediction and code embedding conceptually should require all of the (binary) code of the target function, i.e. a method name is associated with the whole method body. On the other hand, recovering precise return types can definitely be done with a selected portion of the binary code of the target function. In practice, recall that we found that method name prediction works to some extent with the last 20 instructions, but adding the paths (INP vs I) works 11.31% better (top-5) on our dataset for method name prediction.

Despite the differences between the tasks of method name prediction and recovering precise high-level types, we showed that both tasks benefit from knowledge of the AST. More specifically, we observed that using the seq2seq-INP model, which includes nested AST paths information in the code representation, we achieve a higher accuracy compared to the SnowWhite-like seq2seq-I model, which does not. This improvement in accuracy was observed across a diverse set of programs in our dataset, containing Ubuntu packages with a wide range of software, including networking programs and high-performance security and cryptographic packages. Therefore, incorporating AST paths information can be beneficial for both method name prediction and recovering precise high-level types, and this holds true for a wide variety of programs; AST paths also enable further applications like code embedding.

Providing more instructions could also be a way to embed more knowledge about the program in our inputs. However, this would not be practical, given that even a basic Wasm program has thousands of instructions. Our novelty lies in our ability to store the AST information using a concise path sequence.

WasmWalker provides ways to construct both fixed-sized and variable-sized inputs for a multitude of predictive models. On the fixed-sized side, unlike SnowWhite, our pipeline can produce code embeddings that can be used in traditional machine learning models like ANNs; and, the plot in Figure 4 illustrates the effectiveness of our embeddings in grouping similar programs together. SnowWhite is simply not usable for applications that require code embeddings. Regarding variable-sized inputs, our results offer compelling evidence that augmenting the sequence of instructions with our novel path sequence, which summarizes the structure of the AST in a compact form, leads to measurable improvements.

A reader may wonder about the performance of the seq2seq-NP model without the I. Indeed, that model alone performs worse than seq2seq-I. We are proposing the joint use of the Instructions and the Nested Paths for variable-sized inputs; there is no good reason to use the Nested Paths alone for this type of input, and using both does better than just the Instructions. We reiterate that seq2seq-I, which is our replication of SnowWhite, is not path-aware and cannot be used in applications that work with code embeddings.

We incorporated concrete knowledge of Wasm binaries into the seq2seq-INP, -ISP and -I models by using the last 20 instructions sequence; we now discuss our two main reasons for choosing the specific number 20. Firstly, this was the approach used in previous work (SnowWhite) for recovering precise return types: the assumption was that the last 20 instructions are most closely related to the return type. Secondly, we needed to limit the number of instructions used in our models: using all instructions can result in overfitting and long training times. Giving more instructions to seq2seq models would lead to a linear increase in the additional space ($\Theta(n)$) proportional to the number of instructions $n$. On the other hand, the benefits of adding path sequences are independent of the selected number of instructions: our path sequence imposes a constant additional space complexity ($\Theta(1)$). That is also the reason why there is no noticeable difference in training time and model sizes compared to SnowWhite. We point out that the average number of unique paths in a path sequence is 21.5, and that the path sequence represents an entire function, not just the last 20 instructions.

We thus argue that incorporating structured AST knowledge is an economical and efficient method of enhancing our analysis models with more valuable information versus other linear approaches. While we designed WasmWalker for WebAssembly, the fundamental methodology is flexible and would apply to related technologies (like LLVM IR, or Java bytecode).

It is worth noting that our path extraction method did not include concrete terminals, as we aimed to reduce the number of paths and keep them simple. Additionally, the use of terminals can vary significantly for semantically similar programs. However, further investigation of how the terminals, mainly memory locations, change in Wasm binaries with slight variations in the high-level source code could improve our method. Such a study would provide more insight into how our model can leverage terminal information in its path extraction process.

The analysis of binary code is a widely used method for studying closed-source programs. This approach has a wide range of applications, including identifying plagiarism, predicting performance, detecting malware, and discovering vulnerabilities. Researchers have developed many techniques for analyzing binary code.

Lehmann et al. [27] proposed SnowWhite, a neural approach for recovering precise high-level parameter and return types of WebAssembly functions. To represent high-level types, SnowWhite uses an expressive type language that describes a large number of complex types, and builds on the success of neural sequence-to-sequence models for sequence prediction. SnowWhite is the first work that evaluates its performance on a large-scale dataset of 6.3 million type samples extracted from 300,905 WebAssembly object files. The results highlight that SnowWhite’s type language is expressive and accurately matches a significant portion of parameter and return types with the top-1 and top-5 predictions. Our work uses the dataset from SnowWhite. We also take advantage of the instruction sequences that our work provides to create a more effective code representation for WebAssembly functions which includes both the last 20 instructions as well as nested paths. A key difference between our approach and SnowWhite’s is that our representation is path-aware.

Feng et al. [15] proposed Genius, a graph embedding pipeline. Genius splits native code into a collection of basic blocks and creates an attributed control flow graph (ACFG); ACFG nodes are basic blocks. These nodes contain two types of attributes: block-level attributes (e.g. the number of instructions) and inter-block attributes (e.g. the number of offspring). To transform an ACFG to an embedding, Genius trains a codebook using a clustering algorithm. Then it leverages a bipartite graph matching algorithm to measure the similarity between an ACFG and the representative of a cluster. These similarity measures then map to fixed-sized feature vectors.

The main drawback of the Genius work is that generating the codebook is costly, and the quality of the codebook is limited by the size of the training dataset. Xu et. al [43] improved on Genius with neural network-based embedding generation instead of bipartite graph matching. They tested their method on three different datasets, including the one from Genius, and achieved better accuracy and training time. Our work is similar to these two studies: we also transform block-level information into fixed-sized vectors. Like Xu et. al, we use a neural approach that yields a reduced training time compared to traditional methods like Genius codebooks. However, there are key differences. First, their ACFG graph traversal algorithm for generating embeddings does not involve path extraction, whereas our method is based on gathering paths from ASTs. Second, their dataset did not include Wasm binaries.

To capture code semantics, Ben-Nun et al. [8] follow a hypothesis for computer programs akin to the linguistic Distributional Hypothesis [35]. This hypothesis states that statements used in the same context often have similar semantics. They thus devise a representation for LLVM IR statements called conteXtual Flow Graphs (XFG) that incorporates the relative data- and control-flow of a statement. To build a XFG, they use LLVM IR statements in Static Single Assignment format. After preprocessing, they used the skip-gram model [32] to derive embeddings. The authors evaluated the derived XFG embeddings in three high-level classification and prediction tasks and found that they outperformed all manually extracted features. The results were comparable to or better than results from two inherently different specialized DNN solutions.

Similarly, Redmond et al. [36] introduced an instruction embedding model. They created a joint model combining the context information found in instruction sequences within the same architecture and the semantic similarities found in instruction sequence pairs from different architectures. They used word2vec’s CBOW algorithm and evaluated the model on three tasks: (1) determining instruction similarity within the same architecture, (2) determining instruction similarity across different architectures, and (3) comparing basic block similarity across different architectures.

Our embeddings, unlike prior work, maps functions to vectors, rather than instructions to vectors. Furthermore, our results on Wasm ASTs provide not just an embedding, but also an interpretable sequence representation of a Wasm function, which is not offered by the prior studies. Our path sequence is interpretable as we draw each path from an indexed paths set (shown in Figure 2).

Alon et al. [3] proposed code2vec as a method to embed code in high-level programming languages into fixed-sized vectors. Their approach involved extracting paths from the AST, focusing specifically on leaf-to-leaf paths. They asserted that these paths contain more semantic information, as they include all the information between two terminals such as variable names in the AST. As discussed in Section 3, we believe that leaf-to-leaf paths do not contain additional useful semantic information in our context. They assigned fixed-sized vectors to paths and program tokens, which were then fed into a neural network to learn how to combine the vectors into a single embedding. The authors trained the network with an attention mechanism for predicting method names in Java programs and achieved promising results. However, code2vec faces challenges in creating input for the network. code2vec cannot handle the variable number of paths in a program, and additionally will always consider a quadratic number of leaf-to-leaf paths (which is why we were unable to directly compare our method with code2vec). These challenges can be addressed by adding padding or using RNNs to obtain a compressed representation of paths. In contrast, our method avoids these challenges, as it is based on the limited number of refined paths in WAT ASTs and the fact that we use root-to-leaf paths to avoid the quadratic explosion.

Like us, the ASTMiner [25] and PSIMiner [38] projects also provide tools that extract representations from code for use in machine learning models. One of our primary contributions is the path-based refinements described in Section 3.1. While PSIMiner’s tree transformation framework appears to be able to support such refinements, they demonstrate simpler refinements like hiding literals and removing comments. Furthermore, both ASTMiner and PSIMiner work at AST level rather than at IR level as we do. Supporting WAT in these tools and evaluating our refinements in their context seems to require significant implementation effort. The benefits of integrating our tool with theirs also appear to be limited: like ASTMiner and PSIMiner, WasmWalker already generates output that is easily usable by the Python tools usually used as the next stage of machine learning pipelines.

In this study, using our pipeline, WasmWalker, we conducted the first empirical investigation of the common paths within the AST of Wasm programs over a large dataset of Ubuntu 18.04 packages. After preprocessing the collected paths, our analysis revealed that there are only 3,352 root-to-leaf paths within the ASTs of Wasm programs. Our main contribution lies in the development of two code representations based on our empirical findings about these 3,352 root-to-leaf paths that facilitate program analysis over WebAssembly binaries, providing researchers with a valuable tool for this purpose. The two code representations we propose are: (1) a path sequence that shows the paths inside a Wasm function and the number of times they occurred in the AST, and (2) a code embedding that encapsulates all the information within a Wasm function into a compact vector. To demonstrate the utility of our proposed code representations for WebAssembly program analysis, we evaluated them using five sequence-to-sequence models across two tasks: (1) method name prediction and (2) recovering precise return types. When concatenated with a portion of actual instructions, our path sequence representation led to improved prediction accuracy in both of these tasks. Specifically, it resulted in up to 5.36% (11.31%) improvement in Top-1 (Top-5) accuracy in method name prediction and 8.02% (7.92%) improvement in recovering precise return types, compared to the state-of-the-art. As a third task, our code embedding approach successfully provides similar embeddings for method names that have semantically similar method bodies. Although we tailored WasmWalker specifically for WebAssembly, the underlying approach can be readily adapted to other technologies.