StaticCodeAnalysisWithMachineLearning.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Generic stuff\n",
    "from IPython.display import IFrame"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machine learning for vulnerabilities prediction in static code analysis\n",
    "\n",
    "## Introduction\n",
    "\n",
    "This notebook is merely a quick peek at how one can leverage machine learning in the field of static code analysis, more specifically in the field of vulnerabilities detection. In practice, we are going to take a look a how the problem can be framed, what are the most reknown datasets in this field, and actual application/outcomes\n",
    "\n",
    "## References\n",
    "\n",
    "This notebook as been inspired by the following articles:\n",
    "* [Vulnerability Prediction From Source Code Using Machine Learning](https://ieeexplore.ieee.org/iel7/6287639/8948470/09167194.pdf) from 2020 [1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IFrame(\"doc/StaticCodeAnalysis/Vulnerability_Prediction_From_Source_Code_Using_Machine_Learning.pdf\", width=1200, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* [Automated software vulnerability detection with machine learning](https://arxiv.org/abs/1803.04497) from 2018 [2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IFrame(\"doc/StaticCodeAnalysis/1803.04497.pdf\", width=1200, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* [Discovering software vulnerabilities using data-flow analysis and machine learning](https://dl.acm.org/doi/abs/10.1145/3230833.3230856) from 2018 [3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IFrame(\"doc/StaticCodeAnalysis/1803.04497.pdf\", width=1200, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* [Software Vulnerability Detection via Deep Learning over Disaggregated Code Graph Representation\n",
    "](https://arxiv.org/abs/2109.05740)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IFrame(\"doc/StaticCodeAnalysis/2109.05740.pdf\", width=1200, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* [Data Preparation for Software Vulnerability Prediction: A Systematic Literature Review](https://arxiv.org/abs/2109.03341)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IFrame(\"doc/StaticCodeAnalysis/2109.03341.pdf\", width=1200, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[A Novel Neural Source Code Representation Based on Abstract Syntax Tree](http://hongyujohn.github.io/ASTNN.pdf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IFrame(\"doc/StaticCodeAnalysis/ASTNN.pdf\", width=1200, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Code Completion by Modeling Flattened Abstract Syntax Trees as Graphs](https://lihui.info/doc/AAAI21.pdf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#IFrame(\"doc/StaticCodeAnalysis/AAAI21.pdf\", width=1200, height=800)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Main classes of vulerabilities\n",
    "\n",
    "### ML in static code analysis\n",
    "From [1]: A promising application area for AI/ML is automated and intelligent intelligent software analysis with various objectives such as vulnerability prediction [6], code summarization [12], [13], code classification and clone detection [14].\n",
    "Employing ML for software security analysis not only reduces the dependence on domain experts for the hand-crafted pattern or feature extraction [15], but also helps to simplify and automate processes that are required for the\n",
    "current security analysis techniques [7]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Best know datasets\n",
    "* [List of source code analysis tools from National Institute of Standards and Technology (NIST)](https://samate.nist.gov/index.php/Source_Code_Security_Analyzers.html)\n",
    "\n",
    "* [Software Assurance Metrics And Tool Evaluation (SAMATE) project](https://samate.nist.gov/Main_Page.html). The SAMATE project provides very useful overview, evaluations and test results about effectiveness of several static code analysis tools based on a public dataset that includes real and synthetic test cases with a set of known security flaws\n",
    "\n",
    "* [https://osf.io/d45bw](Draper VDISC Dataset) that contains a large amount of labeled real source code components mined from several open-source projects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is an Abstract Syntax Tree (AST)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Useful representation for ML in static analysis framework\n",
    "\n",
    "### Introduction\n",
    "From [1], ideally, one would start a ML pipeline with a method for vectorial representation of source code\n",
    "while preserving syntactic and semantic relations contained in the source code fragments.\n",
    "\n",
    "### Software metrics\n",
    "* From [1]: In **Y. Shin, A. Meneely, L. Williams, and J. A. Osborne, ‘‘Evaluating complexity, code churn, and developer activity metrics as indicators of software vulnerabilities,’’ IEEE Trans. Softw. Eng., vol. 37, no. 6, pp. 772-787, Nov. 2011.** The authors examined the applicability of three types of software metrics (complexity, code churn,and developer activity) to build vulnerability prediction models. They found that 24 of the 28 metrics collected are discriminative of vulnerabilities for both projects.\n",
    "* Another work **B. Chernis and R. Verma, ‘‘Machine learning methods for software vulnerability detection,’’ in Proc. 4th ACM Int. Workshop Secur. Privacy Analytics IWSPA, 2018, pp. 31–39.** demonstrated that some trivial software metrics such as character diversity, string entropy, function length and nesting depth could be useful indicators for vulnerability detection.\n",
    "\n",
    "### Text mining\n",
    "From [1]:\n",
    "In **J. Walden, J. Stuckman, and R. Scandariato, ‘‘Predicting vulnerable components: Software metrics vs text mining,’’ in Proc. IEEE 25th Int. Symp. Softw. Rel. Eng., Nov. 2014, pp. 23–33** the author claims that the prediction techniques, in intelligent software analysis, based on text mining perform better than the prediction techniques based on software metrics. The former approach treats the source code as regular text in general and leverages the natural language processing (NLP) techniques for code representation and feature extraction. The\n",
    "naturalness hypothesis of software approaches the subject in a similar way and asserts that although programming\n",
    "languages, in theory, are complex, flexible and powerful, the code fragments that real people actually write are mostly simple and rather repetitive, and thus they have usefully predictable statistical properties that can be captured in statistical language models.\n",
    "IE for instance with pretrained embeddings used for transfer learning, training model very similar to sentiment analysis...."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Static code analysis based on Abstract Syntax tree\n",
    "Treating the source code as natural language has some limitations in capturing comprehensive program semantics to\n",
    "characterize vulnerabilities of high diversity and complexity in real source code, because source code is actually more structural and logical than natural languages and has various aspects of representation such as AST, data flow and control flow.\n",
    "\n",
    "In [1] the authors propose the following process:\n",
    "1. **Step-1 (Source Code)**. Any high level source code such C/C++ java or python can be used\n",
    "2. **Step-2 (Function-level partition)**: Instead of dealing with the source code as a whole, it is a good practice to split it into sub-parts and handle each sub-part separately. For this purpose, we prefer to use function-level source code because it is the lowest level of granularity, capturing the overall flow of a sub-routine.\n",
    "3. **Step-3 (Tokenization)**: In this step, firstly, the source code is cleaned by removing its unnecessary elements such as comments, whitespaces, tabs, newlines, etc. Then, the remaining part is converted into a series of tokens, where a token is a sequence of characters that can be treated as a unit in the grammar of the corresponding programming language. This can be achieved by using a lexer. IE:\n",
    "\n",
    "| C code | Tokenization from lexer |\n",
    "| :--- | :--- |\n",
    "| int main(){ int a = 5, b = 2; printf(a+b); } | int (keyword), main (identifier), LPAREN (delimiter), RPAREN (delimiter), = (operator), 5 (constant),; (symbol)|\n",
    "\n",
    "4. **Step-4 (AST Generation)**: In this step, AST of the source code is generated, which can be achieved by using a parser developed specifically for the language of the code. AST contains syntax and semantic information\n",
    "about the source code, and therefore it is highly useful for further analysis. Figure 3 shows AST of the main function given in Step 2. The structural relations (e.g., parent-child) are important in the AST and could be useful for vulnerability identification. Therefore, these relational pieces of information should not be lost during the transformations in source code representation stages. This is a bit challenging given that a regular AST is a kind of m-ary tree where there is no restriction on the values that m can take, which means each node may have an arbitrary number of child nodes that makes the structural shape of the AST unpredictable. To overcome this issue, we apply the next step to the AST.\n",
    "![title](doc/StaticCodeAnalysis/AST_sample.png)\n",
    "\n",
    "5. **Step-5 (Conversion to Complete Binary AST)**: AST is a tree type data structure and we need to convert it into an array format to feed an ML algorithm. Suppose for a moment that we convert an AST into an array by placing nodes side by side starting from root level to deeper levels. Structural relations among AST nodes such as parent-child relations would be lost in the resulting array because a parent node may have arbitrary number of children. Second, the resulting arrays would be in different lengths. However, it is highly important to preserve structural relations among AST nodes while mapping them into a one-dimensional arrayin this step, we convert a regular AST to the corresponding complete binary AST, where all leaves have the same depth, and all internal nodes have exactly two children. Here is how:\n",
    "* The leftmost child of node-x in the m-ary tree is assigned as the right-child of node-x in the corresponding complete binary tree (single child is treated as the left-most child here),\n",
    "* The right sibling of node-x in the m-ary tree is assigned as left-child of node-x in the corresponding complete binary tree, and\n",
    "* If node-x has no children, then its right-child becomes NULL, and if node-x is the rightmost child of its parent, then its left-child becomes NULL."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}