End-to-End Prediction of Buffer Overruns from Raw Source Code via Neural Memory Networks

1 Introduction

Detecting potential bugs in software programs has long been a challenge ever since computers were first introduced. To tackle this problem, researchers in the domain of programming languages developed various techniques called static analysis, which tries to find potential bugs in source codes without having to execute them based on a solid mathematical framework [Cousot and Cousot, 1977]. However, designing a static analyzer is tightly coupled with a particular programming language, and it is mainly based on a rigid set of rules designed by a few experts, considering numerous types of possible program states and bug cases. Thus, even with its slight syntax changes frequently found in real-world settings, e.g., several variants of ANSI C languages, a significant amount of engineering effort is required to make a previously designed analyzer applicable to the other similar languages.

To overcome these limitations, one can suggest datadriven, machine learning-based approaches as the rapid growth of deep neural networks in natural language processing has proved its effectiveness in solving similar problems such as defect predictions. Studies show that deep convolutional neural networks (CNNs) and recurrent neural networks (RNNs) are capable of learning patterns or structures within text corpora such as source codes, so they can be applied to programming language tasks such as bug localization [Lam et al., 2015], syntax error correction [Bhatia and Singh, 2016; Pu et al., 2016], and code suggestion [White et al., 2015].

Despite their impressive performances at detecting syntaxlevel bugs and code patterns, deep neural networks have shown less success at understanding how data values are transferred and used within source codes. This semantic level of understanding requires not only knowledge on the overall structure but also the capability to track the data values stored in different variables and methods. Although the aforementioned deep learning models may learn patterns and structures, they cannot keep track of how values are changed. This restriction greatly limits their usefulness in program analysis since run-time bugs and errors are usually much more difficult to detect and thus are often treated with greater importance.

In response, we introduce a new deep learning model with the potential of overcoming such difficulties: memory networks [Weston et al., 2015b; Sukhbaatar et al., 2015]. Memory networks are best described as neural networks with external memory 'slots' to store previously introduced information for future uses. Given a question, it accesses relevant memory slots via an attention mechanism and combines the values of the accessed slots to reach an answer. While long short-term memories (LSTMs) and earlier models also have external memories, theirs tend to evolve as longer sequences of information are fed in to the network, thus failing to fully preserve and represent information introduced at earlier stages. Memory networks on the other hand can preserve the given information even during long sequences.

This unique aspect of memory networks makes it and its variant models [Kumar et al., 2016; Henaff et al., 2016] perform exceptionally well at question answering tasks, e.g., the Facebook bAbI task [Weston et al., 2015a], a widely-used QA benchmark set. The structure of these tasks comprises a story, a query, and an answer, from which a model has to predict the correct answer to the task mentioned in the query by accessing relevant parts of the given story. These tasks are logical questions such as locating an object, counting numbers, or basic induction/deduction. All questions can be correctly answered by referring to appropriate lines of the given story.

We point out that this task setting is in fact similar to that of a buffer overrun analysis that requires the understanding of previous lines in a source code to evaluate whether a buffer access is valid. Both tasks require knowledge not only on how each line works but also on how to select the best relevant information from previous lines. It is this very situation at which our work sets a starting point.

In this study we set the objective as demonstrating a datadriven model free of hand-crafted features and rules, and yet capable of solving tasks with the complexity of buffer overrun analyses. We present how memory networks can be effectively applied to tasks that require the understanding of not only syntactic aspects of a source code but also more complex tasks such as how values are transferred along code lines. We present how our models can learn the concept of numbers and numerical comparison simply by training on such buffer overrun tasks without any additional information. We also introduce a generated source code dataset that was used to compensate for difficulties we faced in our data-driven approach. As far as our knowledge goes, our proposed approach is the first to use deep learning to directly tackle a run-time error prediction task such as buffer overruns.

In Section 2, we cover previous work related to our task. In Section 3, we redefine our tasks, introduce our generated dataset and its purposes, and propose characteristics of the memory network model and how it is applied to this domain. In Section 4, we report experimental results and further discuss the performance of memory networks and notable characteristics it learned during the process. In Section 5 we conclude our work and discuss future work as well as the potential of memory networks for future tasks.

2 RelatedWork

To improve traditional static analysis techniques in the programming language domain, data-driven approaches based on machine learning have been recently studied. Obtaining general properties of a target program, namely, invariants, is one of the prime examples. When concrete data of target programs such as test cases or logs are available, data-driven approaches can be used to identify general properties [Sharma et al., 2012; 2013b; 2013a; Sankaranarayanan et al., 2008b; 2008a; Nori and Sharma, 2013], similar to static analysis techniques. This use case is particularly useful when a target program has inherent complexity that makes contemporary static analyzers to compromise either of precision and cost, but is bundled with test cases that can cover most of cases.

Meanwhile, following the upsurge in the developing field of neural computing and deep learning, many models have been applied to natural language texts, especially in identifying language structure and patterns. Socher et al. [Socher et al., 2013] introduced recursive neural networks which parse a sentence into subsections. [Sutskever et al., 2014] proposed RNNs that learn structures of long text sequences. Source codes of a program can also be seen as a text corpus with its own grammar structure, thus being applicable for such neural network models. [Karpathy et al., 2015] showed that a character-level LSTM trained with Linux kernel codes is capable of detecting features such as brackets or sentence length as well as generating simulated codes that greatly resemble actual ones in syntactic structure. Motivated by such results in the pattern discovery of source codes, several approaches have been taken to solve practical issues in source code analysis. [Gupta et al., 2016], [Pu et al., 2016] and [Bhatia and Singh, 2016] gathered data from programming assignments submitted for a MOOC class to train a correction model which corrects syntax errors in assignments. [Huo et al., 2016] and [Lam et al., 2015] applied attention-based CNNmodels to detect buggy source codes. [Allamanis et al., 2014] learned coding styles by searching for patterns with neural networks. While these approaches proved that neural networks are capable of detecting patterns within codes, they are limited to detecting only syntax errors or bugs and not the transition of values stored inside variables or functions of a source code program.

Neural networks with external memories have shown better performances in inference or logical tasks compared to contemporary models. Following the introduction of neural Turing machines [Graves et al., 2014] and memory networks [Weston et al., 2015b; Sukhbaatar et al., 2015], many variants of these models were applied to various tasks other than QA tasks such as sentiment analysis, part-of-speech tagging [Kumar et al., 2016], and information extraction from documents [Miller et al., 2016]. Yet, so far there has been no work that applies a memory network-based model to tasks with the complexity of semantic analysis in source codes.

3 Model Description

In this section, we first provide the rationale for solving buffer overruns as a QA task. We also introduce a source codebased training dataset that we designed. Lastly, we describe the structure of our model which is based on the memory network [Sukhbaatar et al., 2015] and how it predicts buffer overruns from a source code.

3.1 Benchmark Source Code Generation

Comparison of bAbI tasks and buffer overruns. We return to our statement that analyzing buffer overruns is similar to solving bAbI tasks. Consider Fig. 1. The bAbI task shown in Fig. 1(a) is given a story (lines 1-7) and a query (line 8). A solver model understands this task by looking at 'John' and

'where' from the query and then attends the story to find lines related to 'John.' Lines 3 and 5 are chosen as candidates. The model understands from the sequential structure that line 5 contains more recent, thus relevant information. Line 5 also contains information about 'garden', which is the location of John. Thus, the output vector created by looking at line 5 contains information 'garden', which is used for comparison with the query. In the end, the model returns the answer 'yes' as the term 'garden' is encoded in both the query and the output.

Meanwhile, the task of Fig. 1(b) is to discriminate whether the buffer access made at line 6 is valid. A buffer overrun analyzer first understands that its objective is to compare the size of the character array entity_2 and the integer variable entity_1. These information are stored in the output, which is used to formulate a new query. Using the next query, it searches for the length of entity_2 at line 3, where the value 53 is allocated. This information is added to the next query which is used to gain knowledge from line 2 that entity_1 is equivalent to 70. The remaining task is to compare the integer variables 53 and 70 and return an alarm (unsafe) if the index exceeds the length of the character array. One can think of lines 1-5 as a story and line 6 as a query, perfectly transforming this problem into a bAbI task.

Limitations of test suites. Although test suites such as Juliet Test Suite for C programming language [Boland and Black, 2012] are designed for benchmarking buffer overrun and other program analysis tasks, there are some obstacles to applying them for our approach. First, the data is not diverse enough. Code samples differ by only a small fraction such as a different variable nested in a conditional statement or loop, while a large portion of code appears repeatedly over several samples. A data-driven model will inevitably learn from only the small variations (e.g. different values stored in a particular variable) and ignore a large portion of the code where much of the valuable information is stored (e.g. overall code structure for understanding how to track buffer values). Second, actual program codes are heavily intertwined with internal and external functions and libraries. The executability of a code in a program is often dependent on functions which appear in different files. Such conditions are difficult to consider when only looking at raw source codes as text.

Program structure. We tackle this problem of data inadequacy by generating our own training source code dataset. 1 Our dataset adopts buffer access functions and initialization methods from Juliet to maintain at least an equal level of task complexity, while also preserving an underlying structure that makes it applicable for deep learning approaches. Each sample is a void function of 10 to 30 lines of C code and consists of three stages: initialization, allocation, and query. During the initialization stage, variables are initialized as either characters, character arrays, or integers. At the allocation stage, these variables are assigned values using randomly generated integers between 1 to 100. Buffer sizes are allocated to character arrays with malloc and memset functions. At the query stage, a buffer access is attempted on one of the allocated character arrays via a direct access on an array index (Fig. 2(a)). We formulate this task into a binary classification problem where an 'unsafe' sign is returned if a character array is accessed with a string or index that exceeds its size.

Naming conventions. In deep learning models, words or characters are usually processed into vectors of a fixed length with an external lookup dictionary. Since there is an unlimited number of possible identifier names that programmers can think of, it is both impossible and impractical to create a dictionary of possible identifier names without some kind of restriction. Therefore we set a rule to ensure that only a limited number of individual variables appear in each program sample. Each variable is given the name entity_n where n ∈ {i|0 ≦ i ≦ Nupper, i ∈ Z} and Nupper is an integer set by default to 10. Each n is assigned randomly to variables and invariant of their introduced order or data type. One can imagine a situation where an agent (variable) is given a fake ID (entity name) for a particular task (sample). The agent learns to complete the task with that fake ID, then discards it upon task completion, and selects a new one for the subsequent task. In this manner, we can prevent entities from learning task-specific knowledge and instead train them as representations of universal variables which can replace any kind of variable that appears in a program. We can easily apply our model to real-life source codes using this naming convention by simply changing the names of newly introduced variables and methods to different entities.

1 The generated dataset and generator codes are available at https://github.com/mjc92/buffer_overrun_ memory_networks

Adding complexity. Our model has to adapt to more realistic source codes with complex structures. Possible settings that complicate our task include

• selecting only the appropriate variables out of several dummy variables,
• introducing different buffer access methods requiring the comparison of two character arrays such as strcpy or memcpy functions,
• allocating the sizes of character arrays not with integers but indirectly with previously assigned integer variables,
• reallocating integer variables prior to or after their use in allocating a character array.

We first assign a number of dummy variables to each sample program. Each dummy variable is initialized and allocated in the same manner as the ones actually used in the buffer access. We include the use of strcpy (Fig. 2(b)) / memcpy (Fig. 2(d)) functions for buffer accesses. We also add cases where character arrays are allocated not directly by integers, but indirectly with additionally introduced integer variables (Fig. 2(c)). Given this setting, the model has to learn to store the integer value allocated to the integer variable first, then use that value to obtain the length of the character array. Finally, we add further cases where the additional integer variable itself is reallocated (Fig. 2(d)), either before or after it is used to define the character array length. Now the model has to learn to choose whether the previously assigned or reallocated value was used for allocating a character array.

Our generated source codes are equivalent to an expanded version of Juliet test suite in terms of data flow, that is, the flow of data values defined and used within a source code. Compared to codes in Juliet which only define the source and destination variables that will be used for buffer access, ours include dummy variables which are defined and used similarly. Now our model has to avoid selecting lines which include the dataflow of unrelated variables. Various settings such as memory allocation using assigned integer variables instead of raw integers and reassignment of variables also increase the number of possible situations and increase task difficulty. Overall, our source codes provide a tougher environment for models to solve buffer overrun tasks than the existing Juliet dataset as there are more variations to consider.

3.2 Model Structure

Our memory network-based model encodes lines of source code into vector embeddings, stores information of each line into external memory blocks, and uses a given query line to search parts of the memory that are related to solving the buffer overrun task. The output vector produced by this process contains information of whether the given query is true or false.

The overall structure of our model is displayed in Fig. 3. Input encoding (Fig. 3(a)). The memory network takes in as input a program code X consisting of n search lines X1,X2, · · · ,Xn and a single buffer access line or query Xq. A single program line Xm is a list of words w1m,w2m, · · · ,wlm. With V as the vocabulary size or the total number of unique tokens that appear in all programs, we define xlm as the V -dimensional one-hot vector representation of a word wlm. We set an upper limit N for the max number of lines a memory can store, and we pad zeros for the remaining lines if a program is shorter than N lines.

Note that every word in the source code is treated as a word token. This includes not only variable names (entity), type definitions (int) and special characters, ('[', '*'), but also integers as well. This setting matches our concept of an endto-end model that does not require explicit parsing. While it is possible to apply parsers to extract numbers and represent them differently from other word tokens, this would contradict our goal of applying a purely data-driven approach. Treating integers as individual word tokens means that our model will not be given any prior information regarding the size differences between numbers, and thus has to learn such numerical concepts by itself. We further the effects of this setting in Section 4. Next, we compute vector representations for each sentence using its words. Each word is represented in a d-dimensional vector using an embedding matrix Eval ∈ Rd×V . We also multiply a column vector lj to the j-th word vector for each word to allocate different weights according to word positions. This concept known as position encoding [Sukhbaatar et al., 2015] enables our model to discriminate the different roles of variables when two or more identical words appear in a single sentence. Without such settings, our model may fail to discriminate between source and destination variables such as in a strcpy function. The memory representation mi of line i consisting of J words and the k-th element lk j of the position encoding vector lj ∈ Rd for word j in the line i are obtained as

where '·' is element-wise multiplication.

Memory storage (Fig. 3(b)). Next, we allocate our encoded sentences mi into matrices called memory blocks. Fig. 3(b) shows two memory blocks, the memory value block (Mval ∈ RN×d ) and the memory address block (Maddr ∈ RN×d ). Each sentence is allocated into one row of memory block, namely a memory slot. Mval stores semantical information about the contents of a code line while Maddr stores information for locating how much to address each line. For this reason, sentences are encoded using two different word embedding matrices, Eval and Eaddr for Mval andMaddr, respectively.

Memory search (Fig. 3(c)). The query is encoded into a representation using Eaddr. We denote the initial query embedding as u0 . By computing the inner products between the query embedding and each slot of the memory address block, then applying a softmax function to the resulting vector, we obtain the attention vector p which indicates how related each line is to the query. The i-th element of p is obtained as

with the softmax function as

The response vector o is computed as in

This vector contains information collected over all lines of the memory value block according to their attention weights obtained from the memory address block. Each line of the memory value block contributes differently to constructing the response vector. Recall that the query contains names of variables whose values have to be found throughout the given source code. Lines that contain relevant information such as variable names used in the query will have higher attention values, and will have a greater contribution towards the resulting response vector. This is equivalent to searching the memory for different parts of information with respect to a given query.

Multiple hops and output (Fig. 3(d)). The response vector o can be either directly applied to a weight matrix W to produce an output, or added to strengthen the query u. In the latter case, the query is updated as in Eq. (6) by simply adding the response vector to the previous query embedding.

We repeat from Eq. (3) to obtain a new response vector. Our model iterates through multiple hops where at each hop the desired information to be obtained from the memory slightly changes. This accounts for situations where a model has to first look for lines where an array is allocated, and then gather information from lines stating the size of the variables used for allocating the array size. The final output is a floating value ranging from 0 (unsafe) to 1 (safe), which we round to the nearest integer to obtain a binary prediction result.

4 Experiments

In this section, we present both quantitative and qualitative results of our experiments on model performance and learned characteristics.

4.1 Quantitative Evaluation

Experiment settings. Our main dataset consists of C-style source codes discussed in Section 3.2. We used a single training set consisting of 10,000 sample programs. We generated four test sets with 1,000 samples each and assigned them levels one to four, with a higher level indicating a more complex condition (see Table 2). Samples ranged from 8 to 33 lines of code, with an average of 16.01. A total of 196 unique words appeared in the training set. A maximum of four dummy variables were added to each sample. We used random integers between 0 and 100 for buffer allocation and access. We conducted every experiment on a Intel (R) Xeon (R) CPU E52687W v3 @ 3.10GHz machine equipped with two GeForce GTX TITAN X GPUs. All models were implemented with Tensorflow 0.12.1 using Python 2.7.1 on an Ubuntu 14.04 environment. Model Comparison. We set our memory network to three hops with a memory of 30 lines and the embedding size of d = 32. As there has been no previous work on using deep learning models for such tasks, we used existing deep learning models often used for text classification tasks as baselines. That is, we included a CNN for text classification [Kim, 2014] and a two-layer LSTM binary classifier. All models were trained with Adam [Kingma and Ba, 2014] at a learning rate selected by grid search from ranges between 0.0001 to 0.1. We used the classification accuracy, F1 score, and the area under the ROC curve (AUC) as performance metrics. We averaged the scores of the ten best cases with the smallest training error.

Performance results shown in Table 1 demonstrate that all models decrease in performance as task levels increase, due to our level assignment. Of the deep learning models, only memory networks performed consistently at a high level on all four level settings with accuracy rates higher than 80%. This is expected since their hops allow them to solve even complex situations such as variable reallocation and different buffer access types. Meanwhile, CNNs failed to complete even the simplest tasks since they cannot capture the sequential information in input sentences and instead apply convolutional filters to words of all regions on an equal basis. Any positional information is discarded.

Interestingly, LSTM models also performed well when set to easier tasks. Results show that LSTMs performed comparably to memory networks, even equaling them on Level 1 tasks. However, its performance sharply dropped when used on higher level tasks. This partial success of LSTMs relates to the simple structure of Level 1 tasks. The size of the character array always appears before the index to access, so the model can cheat by comparing the only two numbers that appear within the entire code. This cheating becomes obsolete as higher-level tasks require knowledge only obtainable by attending previous lines in a stepwise manner.

4.2 Qualitative Analysis

We further examine the performance of our memory network model and the steps it takes to obtain a correct answer. We also present visualization results on how our model learns the concepts of numbers and numerical comparison without being explicitly supervised about such tasks.

Tracking hop-wise results. In order to prove that our model solves the tasks in our desired manner, that is, by attending and collecting relevant information from different parts of the memory at different hops, we analyze individual prediction cases by inspecting which parts of information our model has obtained from taking each hop.

Fig. 5 displays an example of buffer overrun analysis using our model. We can observe that when given a strcpy buffer access as a query, the model's initial attention shifts to the sentence where the destination buffer (entity_3) is allocated. The model decides here to next look for entity_9, which contains the size used for allocating to entity_3. During the next hop it attends the line where the source buffer (entity_2) is allocated and obtains data of 99, the size of entity_2. At the last hop the memory network visits entity_9 and obtains 69. After the three hops, the destination size 69 is compared with source size 99, and being a smaller number, returns 'unsafe' as a result. As the result value is a continuous value between 0 and 1, we can use this value to measure prediction confidence as in Fig. 5 to indicate how close the predicted value is to the ground answer.

Numerical concepts automatically learned. Recall from Section 3 that our model was not given any prior information regarding the notion of quantitative values. Interestingly, our model learned to compare between different numbers. Fig. 4 displays visualization results using only the word embedding vectors corresponding to the 100 numbers. In all subfigures (a)-(c) higher numerical values are represented in red and lower values in blue.

Figs. 4(a) and (b) display the cosine similarities and the L2norm distances of all numbers from 1 to 100, starting with 1 at the topmost left-hand side. The colors observed at the first and third quadrants from both figures show that numbers with large differences are trained to minimize cosine similarities while maximizing L2-norm distances, thus spacing themselves apart. In contrast, similar numbers in the second and fourth quadrants have opposite characteristics, meaning they are similarly placed.

The word embedding vectors of numbers across all d dimensions as seen in Fig. 4(c) further demonstrate a clear sequential order between numbers. The highlighted column forms a strong color spectrum starting from a low value which gradually increases as the corresponding number increases from 1 to 100. As all word embeddings were initialized with random values at the beginning, this spectrum indicates that our model learns by itself to assign such values for comparison purposes.

Last of all, Fig. 4(d) is a t-SNE representation of all word embedding vectors. The black gradation indicates the word embeddings of numbers, with denser colors indicating larger numbers. We notice that they are embedded in a consistent direction in an increasing order. While this again shows how our model learns numerical characteristics, we also discover that dots in red, which correspond to entities from Section 3, stand out from other word embeddings. As mentioned earlier, entities correspond to the identifiers that appear in source codes as integer variables or character buffers. This implies that our model learns to train word embeddings differently according to their purposes within a code.

5 Limitations

Given our extreme end-to-end settings, our model inevitably suffers from a number of limitations. First, our model assumes that each and every line contains data assignment of some sort, and calculates attention to find the most relevant code line. This is difficult to apply to source codes that include conditional statements such as if- and for- statements, as the attention cannot consider such conditions. Also, it cannot cover cases where a buffer overrun is dependent on external functions or programs which may be defined in another file and thus not taken into input data. Although end-to-end settings are convenient and straightforward, this alone cannot consider the numerous conditions and syntax rules which form compilable source codes.

Current research on code generation and other program analysis methods using deep learning methods mostly incorporate syntax knowledge to the applied models. Source codes can be reconfigured as abstract syntax trees (AST) which contain structural and syntax information of the specific programming language. Applying such information to neural network models has proven to be effective in solving program-related tasks such as semantic parsing [Dong and Lapata, 2016], API sequence generation [Gu et al., 2016], and code summarization [Allamanis et al., 2016]. While adding such syntax information to our solver model may lead to solving more complex conditions, this restricts the data to source codes that can be successfully parsed with a specific parser, and also opposes to the end-to-end settings proposed in our work.

6 Conclusions and FutureWork

In this work, we proposed a memory network-based model for predicting buffer overruns in programming language analysis. Our work is the first to apply a deep learning-based approach to a problem in the field of program analysis that requires both syntactic and semantic knowledge. Performance results show that memory networks are superior to other models in solving buffer overrun tasks across all difficulty levels. We also presented that our model successfully learns the notion of numbers and their quantitative comparisons from merely textual data in an end-to-end setting.

Our work has room to improve in many interesting aspects from a software engineering perspective. As mentioned earlier, source codes preserve much syntactic information which can be processed to better understand the structure of programs. The use of sophisticated models that take in additional syntactic information can lead to better performances. Meanwhile, we can expand our model to cover different program analysis tasks such as pointer analysis, interval analysis, and flow-sensitivity analysis, which share similar semantic natures. Applying more sophisticate memory network models that preserve state changes can provide solutions to such problems. Our knowledge of models learning numerical representations can further aid deep learning models compatible with arithmetic and logical reasoning. All of these combined, our work marks a stepping stone to a fully data-driven program analyzer.

Acknowledgements

This work was supported in part by Basic Science Research Program through the National Research Foundation of Korea (NRF) grants funded by the Korea government (MSIP) (No. NRF-2016M3C1B6950000, NRF2016R1C1B2014062). Any opinions, findings, and conclusions or recommendations expressed here are those of the authors and do not necessarily reflect the views of funding agencies.