Patent Description:
Uses of Artificial Intelligence (AI), and particularly Machine Learning (ML), have been rising. AI and ML have found places in almost in every area of life. One promising application area for AI/ML, is intelligent software analysis with various objectives such as vulnerability prediction, source code review and completion, synthesis, repairs and more.

ML models are trained and developed over only numerical data in the form of an array(s). For example, consider the task of image classification by ML. Images are made up of pixels, the smallest part of an image, where each pixel has its own color that is represented with a number between <NUM> and <NUM> in a grey color system. Thus, an image is in fact regarded as a matrix, from the perspective of a ML model, comprising numerical values.

On the other hand, source code is mostly written in high-level programming languages (such as Java, Python, etc.) including text-based keywords, words and phrases from English (or other) natural languages. Therefore, a piece of source code written in a high-level language may be difficult to process directly using ML models.

<NPL>, relates to a report on experience of deploying a deep learning tree-based defect prediction model in practice (Abstract).

<CIT> relates to automated generation. or completion. or checking of source code whereby a probabilistic model having been trained using a corpus of natural source code examples is used.

The invention is as defined in and by the appended claims. A method providing evaluation of source code of a programming language includes the following operations. The source code of the programming language is provided, wherein the source code includes a plurality of source code elements. A source code element is selected from the plurality of source code elements of the source code. A plurality of tokens are generated based on the source code element, wherein each token of the plurality of tokens comprises a sequence of text characters. A binary Abstract Syntax Tree (AST) representation of the source code element is generated based on the plurality of tokens of the source code element, wherein the binary AST representation comprises a plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes is based on a respective one of the plurality of tokens of the source code element. Each of the binary AST token nodes and binary AST null nodes is encoded into a respective numeric value. A numeric array representation of the source code element is generated based on the binary AST representation, wherein the numeric values for the respective binary AST token nodes and binary AST null nodes are mapped to locations in the numeric array representation based on respective locations of the binary AST token nodes and binary AST null nodes in the binary AST representation.

There is also provided a source code evaluation node that is adapted to perform the following operations. The source code of the programming language is provided, wherein the source code includes a plurality of source code elements. A source code element is selected from the plurality of source code elements of the source code. A plurality of tokens are generated based on the source code element, wherein each token of the plurality of tokens comprises a sequence of text characters. A binary Abstract Syntax Tree (AST) representation of the source code element is generated based on the plurality of tokens of the source code element, wherein the binary AST representation comprises a plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes is based on a respective one of the plurality of tokens of the source code element. Each of the binary AST token nodes and binary AST null nodes is encoded into a respective numeric value. A numeric array representation of the source code element is generated based on the binary AST representation, wherein the numeric values for the respective binary AST token nodes and binary AST null nodes are mapped to locations in the numeric array representation based on respective locations of the binary AST token nodes and binary AST null nodes in the binary AST representation.

There is also provided a source code evaluation node that includes processing circuitry and memory coupled with the processing circuitry. The memory includes instructions that when executed by the processing circuitry causes the source code evaluation node to perform the following operations. The source code of the programming language is provided, wherein the source code includes a plurality of source code elements. A source code element is selected from the plurality of source code elements of the source code. A plurality of tokens are generated based on the source code element, wherein each token of the plurality of tokens comprises a sequence of text characters. A binary Abstract Syntax Tree (AST) representation of the source code element is generated based on the plurality of tokens of the source code element, wherein the binary AST representation comprises a plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes is based on a respective one of the plurality of tokens of the source code element. Each of the binary AST token nodes and binary AST null nodes is encoded into a respective numeric value. A numeric array representation of the source code element is generated based on the binary AST representation, wherein the numeric values for the respective binary AST token nodes and binary AST null nodes are mapped to locations in the numeric array representation based on respective locations of the binary AST token nodes and binary AST null nodes in the binary AST representation.

There is also provided a computer program that includes program code to be executed by processing circuitry of a source code evaluation node, whereby execution of the program code causes the source code evaluation node to perform the following operations. The source code of the programming language is provided, wherein the source code includes a plurality of source code elements. A source code element is selected from the plurality of source code elements of the source code. A plurality of tokens are generated based on the source code element, wherein each token of the plurality of tokens comprises a sequence of text characters. A binary Abstract Syntax Tree (AST) representation of the source code element is generated based on the plurality of tokens of the source code element, wherein the binary AST representation comprises a plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes is based on a respective one of the plurality of tokens of the source code element. Each of the binary AST token nodes and binary AST null nodes is encoded into a respective numeric value. A numeric array representation of the source code element is generated based on the binary AST representation, wherein the numeric values for the respective binary AST token nodes and binary AST null nodes are mapped to locations in the numeric array representation based on respective locations of the binary AST token nodes and binary AST null nodes in the binary AST representation.

There is also provided a computer program product that includes a non-transitory storage medium including program code to be executed by processing circuitry of a source code evaluation node, whereby execution of the program code causes the source code evaluation node to perform the following operations. The source code of the programming language is provided, wherein the source code includes a plurality of source code elements. A source code element is selected from the plurality of source code elements of the source code. A plurality of tokens are generated based on the source code element, wherein each token of the plurality of tokens comprises a sequence of text characters. A binary Abstract Syntax Tree (AST) representation of the source code element is generated based on the plurality of tokens of the source code element, wherein the binary AST representation comprises a plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes is based on a respective one of the plurality of tokens of the source code element. Each of the binary AST token nodes and binary AST null nodes is encoded into a respective numeric value. A numeric array representation of the source code element is generated based on the binary AST representation, wherein the numeric values for the respective binary AST token nodes and binary AST null nodes are mapped to locations in the numeric array representation based on respective locations of the binary AST token nodes and binary AST null nodes in the binary AST representation.

According to techniques provided herein, more efficient evaluation of source code may be facilitated by generating a binary Abstract Syntax Tree representation for a source code element, and using the binary AST representation to generate a numeric array representation of the source code element. Such operations may facilitate evaluation of the source code element, for example, using Machine Learning (ML) to provide one or more of vulnerability prediction, code review, code completion, synthesis, repairs, etc..

<FIG> is a block diagram illustrating elements of a source code evaluation node configured to provide source code evaluation according to some embodiments of inventive concepts. As shown, the source code evaluation node may include network interface circuitry <NUM> (also referred to as a network interface) configured to provide communications with other nodes. The source code evaluation node may also include a processing circuitry <NUM> (also referred to as a processor) coupled to the network interface circuitry, and memory circuitry <NUM> (also referred to as memory) coupled to the processing circuitry. The memory circuitry <NUM> may include computer readable program code that when executed by the processing circuitry <NUM> causes the processing circuitry to perform operations according to embodiments disclosed herein. According to other embodiments, processing circuitry <NUM> may be defined to include memory so that a separate memory circuitry is not required.

As discussed herein, operations of the source code evaluation node may be performed by processing circuitry <NUM> and/or network interface circuitry <NUM>. For example, processing circuitry <NUM> may control network interface circuitry <NUM> to communicate with one or more other nodes. Moreover, modules may be stored in memory <NUM>, and these modules may provide instructions so that when instructions of a module are executed by processing circuitry <NUM>, processing circuitry <NUM> performs respective operations (e.g., operations discussed below with respect to <FIG>).

Source code cannot be directly executed by processors in a computer architecture. There are compilers or interpreters, which are kinds of computer programs, that process source code and translate the source code into low-level programming languages (e.g., assembly language, object code, or machine code) that are more appropriate to be executed by instructions in a computer architecture. In this process of compiling source code, there are several intermediate steps where source code elements are exposed to different procedures, such as lexical analysis, parsing, abstract syntax tree (AST) representation, etc..

In lexical analysis, a source code element is transformed into a series of tokens, by discarding any whitespace or comments in the source code. For example, in C language, the source code element (also referred to as a line of source code) given below,
int a = <NUM>; // This is a comment!
produces the following sequence of tokens,
int (keyword), a (identifier), = (operator), <NUM> (constant), ; (symbol).

In a parsing process, the tokens generated in lexical analysis are converted into a data structure (mostly a kind of rooted parse tree or other hierarchical structure) giving a structural representation of the input while checking for correct syntax based on the rules of a context-free grammar (CFG). This step can yield a non-binary Abstract Syntax Tree (AST) representation of the given source code element, which is a type of data structure in a rooted tree form based on the tokens extracted in lexical analysis. For example, a non-binary AST of the source code element given above may be provided as shown in <FIG> which illustrates a non-binary AST of the source code element: "int a = <NUM>; // This is a comment!".

A non-binary AST may be a useful representation of a source code element because it includes both syntax and semantic information related to the source code element.

Source code elements may be examined for several reasons, some of which include vulnerability detection or prediction, source code review and completion, converting to another language, synthesis, repairs, and more. In terms of vulnerability detection, there have been two main approaches to perform some analyses on source code elements against potential vulnerabilities (also referred to as bugs). These include (i) Static Code Analyses and (ii) Dynamic Code Analyses. In static code analyses, source code elements are directly analyzed without executing them, whereas in dynamic analysis, source code elements are executed with a specific set of inputs and their behaviors are observed for the intended objective. There are open source and commercial tools for both methods of analysis.

On the other hand, with the advent of Artificial Intelligence (AI) and Machine Learning (ML) techniques, there are now growing trends and research activities on how to leverage advanced capabilities of AI/ML to provide intelligent software analysis. More particularly, there is interest in automatic prediction of potential software vulnerabilities prior to their release by employing AI/ML.

Machine Learning algorithms may only accept numerical inputs for the purpose of training and developing a model. Validation and test data should also be numerical. However, source code elements are mostly written in high-level programming languages, comprising elements that are not in appropriate form to be directly processed by ML algorithms and models. As a result, source code may need to be pre-processed according to some embodiments of inventive concepts before feeding into ML models.

Most prior studies in the literature borrow some methods from Natural Language Processing (NLP) techniques to process source code elements for ML applications as discussed, for example, by <NPL>" (cited below as Reference [<NUM>]). One of the well-known methods in this category is Bag-of-Words (BoW), where each word is tagged with a numeric value, and then the number of occurrences is calculated for each word and phrase to perform some further analyses. However, in this approach, semantic information in the source code element may be lost, and therefore, these methods may not be able to characterize the source code element well enough.

Another approach for source code processing is to use a non-binary AST representation of a source code element, which is a tree-based data structure of the source code element after being tokenized in a compiler or lexer/parser. A non-binary AST includes rich information about the original source code element both in terms of semantic and syntax information. Therefore, a non-binary AST representation may be useful for ML applications. A non-binary AST by itself, however, may not be appropriate to feed ML algorithms directly, because it is based on tokens of the source code element.

One promising use case of leveraging ML techniques for software analysis is vulnerability prediction. Predicting potential vulnerabilities in source code elements may be useful, and its potential advantages are discussed in greater detail below. Traditional methods such as Static Code Analysis and Dynamic Code Analysis have their pros and cons. In static code analysis tools, targeted vulnerabilities are formalized, and rules are defined to detect them, which may require hand-engineering. However, there may be too many false positives and a majority of critical vulnerabilities may not be detected by most of the static analysis tools. On the other hand, dynamic analysis may require running source code elements and observing behavior to detect some vulnerabilities, which may be time consuming and/or likely to fail since it may be difficult to try and test all possible sets of inputs.

There are efforts and trends investigating how to leverage AI/ML techniques to predict potential vulnerabilities in source code elements before their release. This may be important because certain vulnerabilities may cause devastating losses in business. In this area, a problem, which is not completely solved yet, is how to represent source code elements appropriately to feed ML algorithms. This may be useful/required because ML algorithms may accept only numerical data to perform training and test tasks. However, source code elements are just strings including letters, characters, numbers, operators, etc. Therefore, it may not be possible to directly input source codes to ML algorithms.

According to some embodiments of inventive concepts, methods are provided to translate source code elements into a numeric array representation that enables leveraging Machine Learning techniques to perform intelligent analysis on the source code. In such methods, an non-binary Abstract Syntax Tree (AST) representation (which is a tree-type data structure based on the tokens extracted) of a given source code element is first obtained via a parser. Then, the obtained non-binary AST is converted to complete binary AST in which every node other than the leaves has two children. Later, the nodes in this complete binary abstract syntax tree structure are encoded into predefined numeric values (also referred to as numeric keys) along with auxiliary data associated with each node. Finally, the resulting numerically tagged binary AST is converted to an array by mapping nodes into immutable consistent locations (indexes) in the array depending on the location of each node in the binary AST.

In addition, proposed methods have been implemented, and experiments have been performed to predict vulnerabilities in source code elements using ML. Initial experimental results appear to be promising and indicate that the presented source code element representation method may be capable of characterizing some/all vulnerabilities considered in the experiments.

According to some embodiments of inventive concepts, data driven techniques (e.g., AI/ML) are leveraged to perform intelligent analysis directly on source code elements, including but not limited to vulnerability prediction, code review, code completion, synthesis, repairs, and more. A use case for vulnerability prediction is given in the present disclosure with experimental results. With regard to other use cases, it may be determined whether there are any missing parts in the tree by checking an AST of a source code element. If there is, models disclosed herein may offer what child nodes could be inserted in the missing parts. This example can be applied also for a use case 'code repair'.

According to some embodiments of inventive concepts, a language independent method is provided and is applied for any high-level programming language.

According to some embodiments of inventive concepts, a need for domain expert and/or hand-engineering to perform specific analysis is reduced/eliminated by paving the way for data driven techniques (e.g., AI/ML). For example, it is experimentally shown that it is possible to perform vulnerability prediction even without knowing details of the targeted vulnerabilities.

According to some embodiments of inventive concepts, the development of ML-based models and/or tools may be improved/optimized according to an intended objective(s).

According to some embodiments of inventive concepts, ways to perform predictive analysis are provided.

According to some embodiments of inventive concepts, a numerical vectoral representation of a given source code element may be provided while preserving semantic information.

According to some embodiments of inventive concepts, performance of automated code analyses with various objectives (e.g., vulnerability detection) may be enabled. With the rise of Artificial Intelligence (AI), there is a trend to leverage Machine Learning (ML) and Data Mining techniques to perform some intelligent analysis on source code elements. For example, predicting potential software vulnerabilities beforehand in source code elements by using ML algorithms is a significant research area. However, how to do this is yet unclear, and a state-of-the-art approach for this purpose is not currently available. The difficulty may arise from a few factors, such as (i) a lack of useful and large enough datasets that are accurately labelled with identified vulnerabilities and (ii) a lack of effective methods to translate source code elements into a useful data format that can be directly used to train ML models. In fact, source code elements, which are inherently composed of words and phrases in their natural form, may not be appropriate to directly feed ML models because ML algorithms may be trained and developed only over numerical data in vectoral or matrix structure. In the present disclosure, methods are provided to translate source code elements into a useful vectoral structure including numerical values (e.g., including only numerical values), which may be appropriate to directly feed ML algorithms, while keeping semantic and syntactic information about the original source code element as much as possible. Moreover, proposed methods may be implemented and some experiments may be performed with the objective of vulnerability prediction over a large public dataset containing function-level source code elements labelled with known/certain vulnerability types. Thus, experimental results are presented that show feasibility of presented methods.

<FIG> illustrates operations of methods according to some embodiments of inventive concepts, and these operations are also illustrated in flow chart of <FIG>.

Operation <NUM> (Source Code): In operation <NUM>, the source code to be processed is taken as input. The source code may be written in any high-level programming language. As an example, <FIG> illustrates a sample/piece of source code written in C language including two source code elements.

Operation <NUM> (Function-level partition): In operation <NUM>, the source code of a program or application can be arbitrarily long in terms of the number of source code elements (also referred to as source code lines and/or source code functions defined). Therefore, a good practice may be to break the source code into function-level source code elements in order to increase granularity in processing as well as reduce/limit its size to some extent. This can be done manually or automatically by using parsers. Then, each source code element is processed separately in the following operations. After operation <NUM>, the term "source code element" is used in the sense of a function-level source code element. <FIG> illustrate the extraction of two source code elements (function-level source code elements) from the original source code of <FIG>.

Operation <NUM> (Tokenization): In operation <NUM>, the source code element (e.g., the main function of <FIG>) may be first cleaned by removing its unimportant portions of source code element such as comments, whitespaces, tabs, new lines, etc. Then, the remaining portion of the source code element is converted into a series of tokens, where a token is a sequence of text characters that can be treated as a unit in the grammar of the programming language. This can be achieved by using a lexer specifically developed for the language of the source code. By way of example, tokens of the main function of <FIG> may be given as follows: int (keyword), main (identifier), LPAREN (delimiter), RPAREN (delimiter), = (operator), <NUM> (constant), ; (symbol).

Operation <NUM> (non-binary AST Generation): In Operation <NUM>, a non-binary AST of the source code element is generated, which can be achieved using a parser developed specifically for the language of the source code. A non-binary AST contains rich information about the source code element, including syntax and semantic information to some extent. Note that the nodes in a non-binary AST can have an arbitrary number of child nodes, which may make it difficult/impossible to estimate in advance the number of nodes that exist at a certain depth of the non-binary AST. This may be an issue while trying to map nodes of a non-binary AST into a fixed length array. An approach to address this issue is discussed below with respect to Operation <NUM>. <FIG> illustrates a non-binary AST of the main function source code element of <FIG>. In the non-binary AST, each node is a token node corresponding to one of the tokens of the source code element, and each of the tokens of the source code element may be represented in a respective one of the nodes of the non-binary AST.

Operation <NUM> (Conversion to Complete Binary AST): Operation <NUM> may be important to enable assignment of elements (nodes) of a non-binary AST into a fixed length array consistently as described in the following operations. In a regular non-binary AST, the nodes can have an arbitrary number of child nodes, whereas the nodes in a binary AST can have at most two children, which are generally named as left-child and right-child. In operation <NUM>, the regular non-binary AST is converted to complete binary AST, where all leaves (also referred to as terminal nodes) have the same depth and all internal nodes (also referred to as non-terminal nodes) have degree <NUM> (meaning that an internal node has two child nodes). There may be many alternative approaches to convert an m-ary non-binary abstract syntax tree to a binary abstract syntax tree, and any one of these approaches may be used in this operation. As an example, an approach based on the following two rules may be used to convert an m-ary non-binary abstract syntax tree to a corresponding complete binary abstract syntax tree:.

If Node-x (e.g., a binary AST token node corresponding to a node of the non-binary AST and to a token of the source code element) has no children, then its right -child becomes NULL (referred to as a binary AST null node), and if Node-x is the rightmost child of its parent, then its left-child becomes NULL (referred to as a binary AST null node). The examples of <FIG> illustrate conversion of a regular m-ary non-binary abstract syntax tree to a complete binary abstract syntax tree according to some embodiments. Dashed NULL nodes (also referred to as a binary AST null node) are added to provide a complete binary abstract syntax tree. In such a complete binary AST, each level i includes <NUM>' nodes, so that each level is "complete.

By way of example, the regular m-ary non-binary abstract syntax tree illustrated in <FIG> may be provided at operation <NUM>.

A corresponding complete binary abstract syntax tree may be provided at operation <NUM> as shown in <FIG> based on the given m-ary non-binary abstract syntax tree of <FIG>.

<FIG> thus illustrates a complete binary abstract syntax tree corresponding to the sample regular non-binary abstract syntax tree of <FIG>.

As discussed above, a complete binary abstract syntax tree may grow exponentially until all leaves becomes NULL. However, this may lead to a huge number of child nodes when the depth of the binary abstract syntax tree increases. Therefore, in some embodiments, it may be enough to consider the binary abstract syntax tree of a depth up to a threshold, which can be determined based on performance requirements. In empirical studies, a partial binary abstract syntax tree up to depth-<NUM> may represent a whole binary abstract syntax tree to a sufficient extent. By setting a limit on a depth of the complete binary AST of Operation <NUM>, a size of the complete binary AST (including a total number of nodes and levels) may be fixed regardless of a size of the corresponding non-binary AST, so that one or more tokens of the source code element may be omitted from the complete binary AST, and/or so that a number of non-binary token nodes of the non-binary AST exceeds a number of binary AST token nodes of the complete binary AST.

By way of example, <FIG> is a binary AST of the function 'main' given in <FIG>, <FIG>.

<FIG> thus illustrates a complete binary AST of the regular non-binary AST illustrated in <FIG>.

In a binary AST, token nodes (shown as ovals in <FIG>, also referred to as binary AST token nodes) correspond to the token nodes of the non-binary AST (also referred to as non-binary AST token nodes) and to the tokens of the source code element, and null nodes (shown as squares in <FIG>, also referred to as binary AST null nodes) are used to provide that each level i includes <NUM>' nodes and that each node in a level that is not the last level (level n) has two child nodes. In a complete binary AST that has a depth of n, the binary AST has levels i = <NUM>, <NUM>, <NUM>,. n (corresponding to depths <NUM>, <NUM>, <NUM>,. n), each level i of the binary AST includes <NUM>' nodes, each node of levels i = <NUM>, <NUM>, <NUM>,. n - <NUM> has <NUM> child nodes in a next level, the binary AST includes <MAT> nodes, and the numeric array representation (of Operation <NUM>) includes <MAT> numeric values respectively corresponding to the <MAT> nodes of the binary AST.

Operation <NUM> (Encoding to Numeric Values): In the obtained complete binary AST, nodes are named with words or text strings such as "FuncDef", "Decl", "TypeDecl", "Constant", "ID", and so on (corresponding to tokens of the source code element discussed above). These names are encoded into numeric values to allow them to be processed by ML algorithms. Therefore, these node names may be mapped into predetermined numerical values, where each numeric value for a node name may be provided as a numeric tuple. Examples of encodings from token names to numeric tuples are illustrated in the table of <FIG> by way of example.

In this encoding, a first number in the encoded numeric tuple represents the type of token, while second and third numbers in the numeric tuple can be used to provide auxiliary information that may exist at nodes. This encoding is just an example based on one embodiment. Notice that tokens as well as encoded numeric values may vary from one programming language to another language.

Operation <NUM> (Numeric Array Representation): Operation <NUM> may be the last operation. Notice that in a complete binary abstract syntax tree, the number of nodes that can exist at each depth (level) may be certain. For example, there can be at most <NUM> nodes at level-<NUM>, <NUM> nodes at level-<NUM>, <NUM> nodes at level-<NUM>, <NUM> nodes at level-<NUM>, and so on. The number of nodes that can exist at each level increases with the power of <NUM>. Thus, at depth-k, there can be at most <NUM>k nodes. This determinism allows creation of a fixed length numeric array representation in which an index of elements can be assigned consistently to the nodes in binary AST, as illustrated in <FIG>, where <FIG> illustrates Converting a binary abstract syntax tree data structure to a numeric array representation.

The main function given in <FIG> (reproduced as <FIG>) is converted to the numeric array representation of <FIG>.

<FIG> illustrates the numeric array representation of the source code element of the given function, up to Depth-<NUM>. By selecting a depth of <NUM> (i.e., n = <NUM>) for the binary AST, the binary AST will have <NUM> nodes calculated as <MAT>. More generally, the number of nodes N can be calculated as: <MAT> where: N is the number of nodes of the binary AST, n is the depth of the binary AST, and i represents each level from <NUM> to n.

According to some embodiments, of inventive concepts, one advantage of such a numeric array representation is that each particular index (location) of the numeric array representation represents/holds a feature (corresponding to a node of the corresponding binary AST), and these indexes are consistently associated with the same node in a binary AST. This may allow transfer of semantic information in the binary AST to the numeric array representation, which may be a useful property to make comparisons between binary ASTs of different source code elements and to extract patterns and hidden relations between nodes.

According to some embodiments, a use case may provide vulnerability Prediction for Source Code.

To show that proposed methods are feasible and useful to perform intelligent analysis on source code elements using ML techniques, the presented method was implemented and experiments were performed with the objective of predicting certain vulnerabilities in given source code elements. To do this, a public dataset (given in Reference [<NUM>] as Draper VDISC Dataset) was used that contains a relatively large number of function-level source code elements labelled with <NUM> different categories of vulnerabilities. The source code elements in this dataset were extracted from a Debian Linux distribution, Git repositories on GitHub and SATE IV Juilet Test Suite of NIST's Samate project, and then were exposed to static tool analysis and investigated by security experts to label them if they included pre-defined certain vulnerabilities or not. The investigated vulnerabilities are described below with respect to <FIG>.

<FIG> illustrates the types of vulnerabilities (each referred to as a Common Weakness Enumeration or CWE) investigated in the experimental work with the number of samples in each class.

Methods according to some embodiments were implemented using a neural network model. Then, two different performance evaluation tests were performed on both (i) a balanced dataset (i.e. containing an identical number of positive and negative samples in training and test sets) and (ii) an imbalanced dataset (i.e. the number of positive samples is much higher than the number of negative samples, or vice versa, in the dataset). Experimental results are presented in the disclosure below.

Performance Evaluation on the Balanced Dataset is discussed below with respect to <FIG> and <FIG>.

In this part, a balanced subset was extracted from the original dataset referenced above, and its details are given in <FIG> provides numbers of positive and negative samples in the balanced dataset that is obtained by under-sampling the original dataset. <FIG> provides the True Positive Rate and the False Positive Rate of the ML (neural network) implementation tested on Balanced Dataset according to some embodiments of inventive concepts.

As shown in <FIG>, the trained model performs well compared to No skill (random decision) for all classes, even though these are initial results without tuning hyperparameters to improve/optimize the model. These results show that the proposed source code representation method may be highly useful in the use case of vulnerability prediction from source code.

Performance Evaluation on Imbalanced Dataset is discussed with respect to <FIG> and <FIG>.

In this part, a subset of the original dataset is used with the details given in <FIG> provides the numbers of positive and negative samples in the imbalanced dataset. <FIG> provides Precision-Recall curves for different classes tested on the Imbalanced Dataset.

<FIG> shows individual Precision-Recall PR curves for different classes. There are also underlying f1 score curves. While interpreting this figure, the ratio of positive and negative samples should be taken into consideration because it determines baseline.

According to some embodiments of inventive concepts, methods of source code representation for Machine Learning applications are provided.

According to some embodiments of inventive concepts, methods of translating a source code element into a numeric array representation are provided.

According to some embodiments of inventive concepts, methods of preprocessing a source code element before feeding into ML implementations are provided.

According to some embodiments of inventive concepts, methods of performing intelligent analysis directly on source code elements are provided.

According to some embodiments of inventive concepts, methods providing vulnerability prediction directly from source code elements are provided.

According to some embodiments of inventive concepts, methods of providing automated source code analysis without requiring any domain expert or hand-engineering are provided.

According to some embodiments of inventive concepts, methods of encoding tokens identified in lexical analyses of source code elements into numerical values are provided.

According to some embodiments of inventive concepts, methods of encoding a binary AST representation of a source code element into a numeric array representation are provided.

Operations of a source code evaluation node <NUM> (implemented using the structure of <FIG>) will now be discussed with reference to the flow chart of <FIG> according to some embodiments of inventive concepts. For example, modules may be stored in memory <NUM> of <FIG>, and these modules may provide instructions so that when the instructions of a module are executed by processing circuitry <NUM>, processing circuitry <NUM> performs respective operations of the flow chart.

At block <NUM>, processing circuitry <NUM> provides the source code of the programming language (e.g., a high-level programming language), wherein the source code includes a plurality of source code elements. Operations of block <NUM>, for example, may be performed as discussed above with respect to operation <NUM> of <FIG>.

At block <NUM>, processing circuitry <NUM> selects a first source code element (e.g., a function-level source code element) from the plurality of source code elements of the source code. According to some embodiments, the first source code element may include letters, characters, numbers, and operators. Operations of block <NUM>, for example, may be performed as discussed above with respect to operation <NUM> of <FIG>.

At block <NUM>, processing circuitry <NUM> generates a first plurality of tokens based on the first source code element, wherein each token of the first plurality of tokens comprises a sequence of text characters. According to some embodiments, the first plurality of tokens may be generated based on lexical analysis of the first source code element. Operations of block <NUM>, for example, may be performed as discussed above with respect to operation <NUM> of <FIG>.

At block <NUM>, processing circuitry <NUM> generates a non-binary Abstract Syntax Tree (AST) representation of the first source code element based on the first plurality of tokens of the first source code element. The non-binary AST representation includes non-binary AST token nodes, and each of the non-binary AST token nodes is based on a respective one of the first plurality of tokens of the first source code element. According to such embodiments, the binary AST representation of block <NUM> may be generated based on the non-binary AST representation of block <NUM>, and each of the binary AST token nodes may correspond to a respective one of the non-binary AST token nodes. In such embodiments, a number of the non-binary AST token nodes may exceed a number of the binary AST token nodes. Operations of block <NUM>, for example, may be performed as discussed above with respect to operation <NUM> of <FIG>.

At block <NUM>, processing circuitry <NUM> generates a first binary Abstract Syntax Tree (AST) representation of the first source code element based on the first plurality of tokens of the first source code element, wherein the first binary AST representation comprises a first plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes of the first binary AST representation is based on a respective one of the first plurality of tokens of the first source code element. Operations of block <NUM>, for example, may be performed as discussed above with respect to operation <NUM> of <FIG>.

According to some embodiments, a number of the first plurality of tokens based on the source code may exceed a number of the binary AST token nodes of the first binary AST representation. For example, the binary AST representation may have a depth of n, the binary AST representation may have levels i = <NUM>, <NUM>, <NUM>,. n, each level i of the binary AST representation may include <NUM>' nodes, each node of levels i = <NUM>, <NUM>, <NUM>,. n-<NUM> may have <NUM> child nodes in a next level, the binary AST representation may include <MAT> nodes, and the numeric array representation may include <MAT> numeric values respectively corresponding to the <MAT> nodes of the binary AST representation. Accordingly, at least one of the first plurality of tokens generated based on the first source code element may be omitted from the binary AST representation.

At block <NUM>, processing circuitry <NUM> encodes each of the binary AST token nodes and binary AST null nodes into a respective numeric value (e.g., a numeric tuple). Operations of block <NUM>, for example, may be performed as discussed above with respect to operation <NUM> of <FIG>.

At block <NUM>, processing circuitry <NUM> generates a first numeric array representation of the first source code element based on the first binary AST representation, wherein the first numeric values for the respective binary AST token nodes and binary AST null nodes are mapped to locations in the first numeric array representation based on respective locations of the binary AST token nodes and binary AST null nodes in the first binary AST representation. Operations of block <NUM>, for example, may be performed as discussed above with respect to operation <NUM> of <FIG>.

Operations of blocks <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM> may be repeated at block <NUM> for each source code element of the source code. At block <NUM>, processing circuitry <NUM> may determine if numeric array representations have been generated for all source code elements of the source code, and if not operations of blocks <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM> may be repeated for a next source code element of the source code as discussed below.

According to some embodiments, at block <NUM>, processing circuitry <NUM> may select a second source code element from the plurality of source code elements of the source code.

According to some embodiments, at block <NUM>, processing circuitry <NUM> may generate a second plurality of tokens based on the second source code element, wherein each token of the second plurality of tokens comprises a sequence of text characters.

According to some embodiments, at block <NUM>, processing circuitry <NUM> may generate a second non-binary Abstract Syntax Tree (AST) representation of the second source code element based on the second plurality of tokens of the second source code element. The second non-binary AST representation may include non-binary AST token nodes, and each of the non-binary AST token nodes of the second non-binary AST representation may be based on a respective one of the second plurality of tokens of the second source code element.

According to some embodiments, at block <NUM>, processing circuitry <NUM> may generate a second binary Abstract Syntax Tree (AST) representation of the second source code element based on the second plurality of tokens of the second source code element, wherein the second binary AST comprises a second plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes of the second binary AST is based on a respective one of the second plurality of tokens of the second source code element. According to such embodiments, the second binary AST representation of block <NUM> may be generated based on the second non-binary AST representation of block <NUM>, and each of the binary AST token nodes of the second binary AST representation may correspond to a respective one of the non-binary AST token nodes. In such embodiments, a number of the non-binary AST token nodes of the second non-binary AST representation may exceed a number of the binary AST token nodes of the second binary AST representation.

According to some embodiments, at block <NUM>, processing circuitry <NUM> may encode each of the token nodes and null nodes of the second plurality of binary AST nodes into a respective numeric value.

According to some embodiments at block <NUM>, processing circuitry <NUM> may generate a second numeric array representation of the second source code element based on the second binary AST representation, wherein the numeric values for the respective token nodes and null nodes of the second plurality of binary AST nodes are mapped to locations in the second numeric array representation based on respective locations of the token nodes and null nodes in the second binary AST representation.

According to some embodiments at block <NUM>, processing circuitry <NUM> may determine if numeric array representations have been generated for all source code elements of the source code. If not, operations of blocks <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM> may be repeated at block <NUM> for a next source code element of the source code. Otherwise, at block <NUM>, processing circuitry <NUM> may evaluate the source code based on one or more of the numeric array representations of the respective source code elements using a machine learning (ML) model, wherein the ML model is based on a dataset of source code elements.

Block <NUM> includes one or more of predicting a software vulnerability for the source code, detecting a vulnerability for the source code, identifying an error in the source code, and/or correcting an error in the source code using the ML model, wherein the ML model is based on the dataset of source code elements and at least one of corresponding respective vulnerabilities corresponding to the source code elements of the dataset and/or respective errors corresponding to the source code elements of the data set.

According to some embodiments, processing circuitry may evaluate each numerical array representation for each source code element using the ML model. For example, processing circuitry <NUM> may evaluate the first source code element using the first numeric array representation and the ML model to predict a software vulnerability for the first source code element, detect a vulnerability for the first source code element, identify an error in the first source code element, and/or correct an error in the first source code element, and processing circuitry <NUM> may evaluate the second source code element using the second numeric array representation and the ML model to predict a software vulnerability for the second source code element, detect a vulnerability for the second source code element, identify an error in the second source code element, and/or correct an error in the second source code element.

As shown in <FIG>, numeric array representations may be generated for all source code elements of the source code before using the numeric array representations to evaluate the source code at block <NUM>. According to some other embodiments, each source code element may be evaluated using the respective numeric array representation before generating a next numeric array representation for a next source code element (e.g., moving block <NUM> between blocks <NUM> and <NUM>).

According to some embodiments, processing circuitry <NUM> may generate an output (e.g., an output to be rendered on a video display) indicating at least one of a predicted software vulnerability for the first source code element, a detected vulnerability for the first source code element, an error in the first source code element, and/or a correction for the first source code element. According to some embodiments, processing circuitry <NUM> may automatically generate (without user intervention) a corrected version of the first source code element responsive to evaluating the first source code element at block <NUM>, and processing circuitry <NUM> may save the corrected version of the first source code element in memory <NUM>. According to some embodiments, processing circuitry <NUM> may automatically generate (without user intervention) a corrected version of the first source code element responsive to evaluating the first source code element at block <NUM>, and processing circuitry <NUM> may save a revised version of the source code including the corrected version of the first source code element in memory <NUM>.

Additional explanation is provided below.

Some of the embodiments contemplated herein have been described with reference to the accompanying drawings.

The term "and/or" (abbreviated "/") includes any and all combinations of one or more of the associated listed items.

Many variations and modifications can be made to the embodiments without substantially departing from the principles of the present inventive concepts.

Explanations are provided below for various abbreviations/acronyms used in the present disclosure.

Claim 1:
A method providing evaluation of source code, the source code being written in a programming language, the method comprising:
providing (<NUM>) the source code, wherein the source code includes a plurality of source code elements;
selecting (<NUM>) a source code element from the plurality of source code elements;
generating (<NUM>) a plurality of tokens based on the source code element, wherein each token of the plurality of tokens comprises a sequence of text characters;
generating (<NUM>) a non-binary Abstract Syntax Tree, AST, representation of the source code element based on the plurality of tokens of the source code element, wherein the non-binary AST representation comprises non-binary AST token nodes, where each of the non-binary AST token nodes is based on a respective one of the plurality of tokens of the source code element;
generating (<NUM>) a binary AST representation of the source code element based on the plurality of tokens of the source code element and the non-binary AST representation, wherein the binary AST representation comprises a plurality of binary AST nodes including binary AST token nodes and binary AST null nodes, wherein each of the binary AST token nodes is based on a respective one of the plurality of tokens of the source code element, and wherein each of the binary AST token nodes corresponds to a respective one of the non-binary AST token nodes;
encoding (<NUM>) each of the binary AST token nodes and binary AST null nodes into a respective numeric value;
generating (<NUM>) a numeric array representation of the source code element based on the binary AST representation, wherein the numeric values for the respective binary AST token nodes and binary AST null nodes are mapped to locations in the numeric array representation based on respective locations of the binary AST token nodes and binary AST null nodes in the binary AST representation; and
evaluating (<NUM>) the source code based on the numeric array representation of the source code element using a machine learning, ML, model.