Understanding Program Semantics

Thus far, we have established the need to represent code as vectors before feeding it into a machine learning classifier that will help us sort through a messy project. We have also discussed at length why neural network based encoders are probably the best for this task. However, a new problem arises from this. In the case of natural language, the features and labels were clear: we try to predict neighboring words from a central word, as is done in code2vec. But with code we have more freedom, in a way: code has several special properties and structure. So we need to decide how to represent pieces of code before even feeding them to the network that will give us the vector representations, if you recall, as a by-product in the middle layers.

One of these possible representations, is to represent snippets of code as bags of words (tokens), i.e., a simple assignment of words to numbers and then making up a vector around that saying which tokens occur in a snippet. And, by the way, we skip the neural network encoder. This is what we did initially, but it is clear even from the foundations that this leaves room for improvement.

Another possibility is to use the snippet’s Abstract Syntax Tree (AST), which, incidentally, is what they use in tools such as code2vec and code2seq. However an issue that we could claim to be present here is that code is not just about syntax, but it also has rich semantics which could be exploited by us to obtain more useful vector representations and thus, hopefully, better results at the classifier level. Remember: garbage in, garbage out. The better the input to the classifier, the better the triaging overall.

One interesting approach I found which does take into account the semantics of the code to be represented works by using intraprocedural symbolic execution. Let’s see if this improves accuracy and actually adds value to our toolchain.

As a refresher, recall that symbolic execution. traverse all the paths a program could take with all possible inputs, never defining them (unlike fuzzing), but rather treating them symbolically like algebraic indeterminates.

In the work we are reviewing, these paths are known as traces which are left during the symbolic execution and are further abstracted or, if you will, simplified, so that a simple snippet like the following becomes two abstracted traces like this:

Incidentally, these Call, Error, AccessPath, etc type of abstractions subtly hint at an idea we’ve been considering, namely, using an intermediate representation of code before performing the actual encoding. This could be one such candidate, but pseudocode, assembly or even some other ad hoc kind of intermediate representation would solve or improve on two issues at hand:

Back to abstracted symbolic traces, they then proceed to encode these as words in order to use GloVe, a sort of big brother to Word2Vec. (I warned you, most code encoders either work with or are heavily inspired by W2V). GloVe exploits the intuition that when words appear together frequently, they have some relation, which seems reasonable in the regular usage of language. It remains to be seen how well such an idea translates to code, though.

That describes the entire architecture of this system of embedding code into vectors. They ran comprehensive experiments to determine the added value vs the overhead of running symbolic execution regarding the quality of the learned embeddings. One is the production of code analogies: much like "king - man + woman = queen" for natural language, similar relations arise here, such as “receive` is to download as send is to `upload”, where each of those are tokens naturally occurring in snippets of code. Of course, this is not yet standardized, so the is no benchmark; the authors had to make their own benchmark and corresponding dataset, a task we will certainly be confronted with soon.

Almost 300% better. This makes intuitive sense, since considering more information, and especially the information which gives code its meaning, should give better results. However only the experiment proves it. And quite resoundingly at that. In the image above, OOV means out-of-vocabulary tests, i.e., the ones that can’t be tested. Even leaving these out, the semantic results are twice as good as the syntax-based ones. This means, on the one hand, that is is certainly worthwile to include semantic information in the code representation for input to embedders, despite the overhead. On the other, to be fair, the syntax-only approach they use might not be as sophisticated as, say, code2vec. It could be that we are comparing the weakest machine gun to the weakest pistol, instead of to the strongest, which might win (sorry, I’m short on metaphors today, but you get the idea).