A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> We apply data mining to version histories in order to guide programmers along related changes: "Programmers who changed these functions also changed. . . ". Given a set of existing changes, such rules (a) suggest and predict likely further changes, (b) show up item coupling that is indetectable by program analysis, and (c) prevent errors due to incomplete changes. After an initial change, our ROSE prototype can correctly predict 26% of further files to be changed - and 15% of the precise functions or variables. The topmost three suggestions contain a correct location with a likelihood of 64%. <s> BIB001 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> We describe a method to use the source code change history of a software project to drive and help to refine the search for bugs. Based on the data retrieved from the source code repository, we implement a static source code checker that searches for a commonly fixed bug and uses information automatically mined from the source code repository to refine its results. By applying our tool, we have identified a total of 178 warnings that are likely bugs in the Apache Web server source code and a total of 546 warnings that are likely bugs in Wine, an open-source implementation of the Windows API. We show that our technique is more effective than the same static analysis that does not use historical data from the source code repository. <s> BIB002 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> We present a statistical debugging algorithm that isolates bugs in programs containing multiple undiagnosed bugs. Earlier statistical algorithms that focus solely on identifying predictors that correlate with program failure perform poorly when there are multiple bugs. Our new technique separates the effects of different bugs and identifies predictors that are associated with individual bugs. These predictors reveal both the circumstances under which bugs occur as well as the frequencies of failure modes, making it easier to prioritize debugging efforts. Our algorithm is validated using several case studies, including examples in which the algorithm identified previously unknown, significant crashing bugs in widely used systems. <s> BIB003 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> A software system interacts with third-party libraries through various APIs. Using these library APIs often needs tofollow certain usage patterns. Furthermore, ordering rules (specifications) exist between APIs, and these rules govern the secure and robust operation of the system using these APIs. But these patterns and rules may not be well documented by the API developers. Previous approaches mine frequent association rules, itemsets, or subsequences that capture API call patterns shared by API client code. However, these frequent API patterns cannot completely capture some useful orderings shared by APIs, especially when multiple APIs are involved across different procedures. In this paper, we present a framework to automatically extract usage scenarios among user-specified APIs as partial orders, directly from the source code (API client code). We adapt a model checker to generate interprocedural control-flow-sensitive static traces related to the APIs of interest. Different API usage scenarios are extracted from the static traces by our scenario extraction algorithm and fed to a miner. The miner summarizes different usage scenarios as compact partial orders. Specifications are extracted from the frequent partial orders using our specification extraction algorithm. Our experience of applying the framework on 72 X11 clients with 200K LOC in total has shown that theextracted API partial orders are useful in assisting effective API reuse and checking. <s> BIB004 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> Program specifications are important for many tasks during software design, development, and maintenance. Among these, temporal specifications are particularly useful. They express formal correctness requirements of an application's ordering of specific actions and events during execution, such as the strict alternation of acquisition and release of locks. Despite their importance, temporal specifications are often missing, incomplete, or described only informally. Many techniques have been proposed that mine such specifications from execution traces or program source code. However, existing techniques mine only simple patterns, or they mine a single complex pattern that is restricted to a particular set of manually selected events. There is no practical, automatic technique that can mine general temporal properties from execution traces. In this paper, we present Javert, the first general specification mining framework that can learn, fully automatically, complex temporal properties from execution traces. The key insight behind Javert is that real, complex specifications can be formed by composing instances of small generic patterns, such as the alternating pattern ((ab)) and the resource usage pattern ((ab c)). In particular, Javert learns simple generic patterns and composes them using sound rules to construct large, complex specifications. We have implemented the algorithm in a practical tool and conducted an extensive empirical evaluation on several open source software projects. Our results are promising; they show that Javert is scalable, general, and precise. It discovered many interesting, nontrivial specifications in real-world code that are beyond the reach of existing automatic techniques. <s> BIB005 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> Malicious applications pose a threat to the security of the Android platform. The growing amount and diversity of these applications render conventional defenses largely ineffective and thus Android smartphones often remain unprotected from novel malware. In this paper, we propose DREBIN, a lightweight method for detection of Android malware that enables identifying malicious applications directly on the smartphone. As the limited resources impede monitoring applications at run-time, DREBIN performs a broad static analysis, gathering as many features of an application as possible. These features are embedded in a joint vector space, such that typical patterns indicative for malware can be automatically identified and used for explaining the decisions of our method. In an evaluation with 123,453 applications and 5,560 malware samples DREBIN outperforms several related approaches and detects 94% of the malware with few false alarms, where the explanations provided for each detection reveal relevant properties of the detected malware. On five popular smartphones, the method requires 10 seconds for an analysis on average, rendering it suitable for checking downloaded applications directly on the device. <s> BIB006 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> Probabilistic programs are usual functional or imperative programs with two added constructs: (1) the ability to draw values at random from distributions, and (2) the ability to condition values of variables in a program via observations. Models from diverse application areas such as computer vision, coding theory, cryptographic protocols, biology and reliability analysis can be written as probabilistic programs. Probabilistic inference is the problem of computing an explicit representation of the probability distribution implicitly specified by a probabilistic program. Depending on the application, the desired output from inference may vary---we may want to estimate the expected value of some function f with respect to the distribution, or the mode of the distribution, or simply a set of samples drawn from the distribution. In this paper, we describe connections this research area called ``Probabilistic Programming" has with programming languages and software engineering, and this includes language design, and the static and dynamic analysis of programs. We survey current state of the art and speculate on promising directions for future research. <s> BIB007 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> Mobile devices are an important part of our everyday lives, and the Android platform has become a market leader. In recent years a number of approaches for Android malware detection have been proposed, using permissions, source code analysis, or dynamic analysis. In this paper, we propose to use a probabilistic discriminative model based on regularized logistic regression for Android malware detection. Through extensive experimental evaluation, we demonstrate that it can generate probabilistic outputs with highly accurate classification results. In particular, we propose to use Android API calls as features extracted from decompiled source code, and analyze and explore issues in feature granularity, feature representation, feature selection, and regularization. We show that the probabilistic discriminative model also works well with permissions, and substantially outperforms the state-of-the-art methods for Android malware detection with application permissions. Furthermore, the discriminative learning model achieves the best detection results by combining both decompiled source code and application permissions. To the best of our knowledge, this is the first research that proposes probabilistic discriminative model for Android malware detection with a thorough study of desired representation of decompiled source code and is the first research work for Android malware detection task that combines both analysis of decompiled source code and application permissions. <s> BIB008 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> We propose the neural programmer-interpreter (NPI): a recurrent and compositional neural network that learns to represent and execute programs. NPI has three learnable components: a task-agnostic recurrent core, a persistent key-value program memory, and domain-specific encoders that enable a single NPI to operate in multiple perceptually diverse environments with distinct affordances. By learning to compose lower-level programs to express higher-level programs, NPI reduces sample complexity and increases generalization ability compared to sequence-to-sequence LSTMs. The program memory allows efficient learning of additional tasks by building on existing programs. NPI can also harness the environment (e.g. a scratch pad with read-write pointers) to cache intermediate results of computation, lessening the long-term memory burden on recurrent hidden units. In this work we train the NPI with fully-supervised execution traces; each program has example sequences of calls to the immediate subprograms conditioned on the input. Rather than training on a huge number of relatively weak labels, NPI learns from a small number of rich examples. We demonstrate the capability of our model to learn several types of compositional programs: addition, sorting, and canonicalizing 3D models. Furthermore, a single NPI learns to execute these programs and all 21 associated subprograms. <s> BIB009 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> There are families of neural networks that can learn to compute any function, provided sufficient training data. However, given that in practice training data is scarce for all but a small set of problems, a core question is how to incorporate prior knowledge into a model. Here we consider the case of prior procedural knowledge such as knowing the overall recursive structure of a sequence transduction program or the fact that a program will likely use arithmetic operations on real numbers to solve a task. To this end we present a differentiable interpreter for the programming language Forth. Through a neural implementation of the dual stack machine that underlies Forth, programmers can write program sketches with slots that can be filled with learnable behaviour. As the program interpreter is end-to-end differentiable, we can optimize this behaviour directly through gradient descent techniques on user specified objectives, and also integrate the program into any larger neural computation graph. We show empirically that our interpreter is able to effectively leverage different levels of prior program structure and learn complex transduction tasks such as sequence sorting or addition with substantially less data and better generalisation over problem sizes. In addition, we introduce neural program optimisations based on symbolic computation and parallel branching that lead to significant speed improvements. <s> BIB010 </s> A Survey of Machine Learning for Big Code and Naturalness <s> RELATED RESEARCH AREAS <s> Learning tasks on source code (i.e., formal languages) have been considered recently, but most work has tried to transfer natural language methods and does not capitalize on the unique opportunities offered by code's known syntax. For example, long-range dependencies induced by using the same variable or function in distant locations are often not considered. We propose to use graphs to represent both the syntactic and semantic structure of code and use graph-based deep learning methods to learn to reason over program structures. ::: In this work, we present how to construct graphs from source code and how to scale Gated Graph Neural Networks training to such large graphs. We evaluate our method on two tasks: VarNaming, in which a network attempts to predict the name of a variable given its usage, and VarMisuse, in which the network learns to reason about selecting the correct variable that should be used at a given program location. Our comparison to methods that use less structured program representations shows the advantages of modeling known structure, and suggests that our models learn to infer meaningful names and to solve the VarMisuse task in many cases. Additionally, our testing showed that VarMisuse identifies a number of bugs in mature open-source projects. <s> BIB011
A variety of related research areas within software engineering and programming languages overlap with the area of statistical modeling of code. One of the most closely related research areas is mining software repositories (MSR) and big code. MSR is a well-established, vibrant, and active field; the idea is to mine the large amounts of source code data and metadata available in open source (and commercial) repositories to gain valuable information and use this information to enhance both tools and processes. The eponymous flagship conference is now in its 15th iteration. "Big Code" is a synonymous neologism, created by DARPA's MUSE program BIB011 to borrow some branding shine from the well-marketed term "Big Data." The MSR field's early successes date back to work by Zimmermann et al. BIB001 , Williams and Hollingsworth BIB002 , Gabel and Su BIB005 , and Acharya et al. BIB004 on mining API protocols from source code bases. These approaches used pragmatic counting techniques, such as frequent item-set mining. Mining software repositories is in one sense a broader field than statistical models of code, as rather than focusing on code alone, MSR considers the full spectrum of software engineering data that can be derived from the software engineering process, such as process measures, requirement traceability, and commit logs. Additionally, research in malware detection is related to probabilistic models of code BIB006 BIB008 . Another active area at the intersection machine-learning and programming language research is probabilistic programming BIB007 . This might appear to be related to statistical models of code, but in fact there is a fundamental difference; essentially, probabilistic programming works in the reverse direction. Probabilistic programming seeks to deploy programming language concepts to make it easier for developers to write new machine-learning algorithms. Statistical code models seek to apply machine-learning concepts to make it easier for developers to write new programs. In some sense, the two areas are dual to each other. That being said, one can certainly imagine completing the cycle and attempting to develop statistical code models for probabilistic programming languages. This could be a fascinating endeavor as probabilistic programming grows in popularity to the extent that large corpora of probabilistic programs become available. In software engineering, the term modeling often refers to formal specifications of program behavior, which are clearly a very different kinds of models than those described here. Combining formal models of semantics with statistical models of source code described in this review would be an interesting area for future research. There is also some work on probabilistic models of code that do not have a learning component, such as Liblit et al. BIB003 . Within machine learning, there has been an interesting recent line of work on neural abstract machines [75, BIB009 BIB010 , which extend deterministic automata from computer science, such as pushdown automata and Turing machines, to represent differentiable functions, so that the functions can be estimated by techniques from machine learning. To the best of our knowledge, this intriguing line of work does not yet consider source code, unlike the work described in this review. Finally, semantic parsing is a vibrant research area of NLP that is closely related to the idea of program synthesis from natural language; see Section 5.5 for more discussion.