Dramatically Reducing Software Vulnerabilities: Report to the White House Office of Science and Technology Policy
Representation Early static checkers usually had to include their own parsers for building an AST to analyze. However, compiler writers realized the importance of developing common intermediate representations (IRs) that are well documented and easily accessible. For instance, in version 4.0, the development team of the GNU compiler, gcc, [GCC16] introduced the intermediate language GENERIC, which is a language independent format for representing source programs in any of several languages. As another example, the Clang compiler [Clang] provides a well documented AST that may be either directly accessed by third party plugins or saved in a common format, such as JSON, to be processed by third party analysis tools. Other compilers that provide well documented interchange formats include Frama C [FramaC] and the ROSE compiler infrastructure [Rose16] Intermediate Representation Tools may perform in depth analyses on intermediate representations (IRs) that are closer to the final executable code generated by compilers. For instance, the GNU compiler defines the GIMPLE format in which the original source program is broken down into a simple three address language. Similarly, the Clang compiler provides the LLVM bitcode representation, a kind of typed assembly language format that is not tied to a specific processor. Others are Common Intermediate Language (CIL) [ECMA12] and the Java Virtual Machine Instruction Set or bytecode [Lindholm15] The Vine Intermediate Language is a platform independent machine language [Song08] Semantic Representations Tools that check functional correctness properties typically need a representation that is more suited to expressing logical program properties than the representations discussed above. While such representations are not as mature as ASTs and compiler IRs, a few have gained popularity in recent years. For instance, the intermediate NISTIR 8151 DRAMATICALLY REDUCING SOFTWARE VULNERABILITIES: REPORT TO OSTP 18 This puication is avilable ree of carge rom https:/rg/10.6028/N IS .IR .151 verification language Boogie [Barnett05] which provides features such as parametric polymorphism, universal and existential quantification, nondeterministic choice and partial orderings, has become a popular backend for sophisticated checkers of both low level languages, such as C and C+ and higher level object oriented languages, such as Eiffel and C# Boogie programs can be translated into the SMT LIB format [SMTLIB15] which allows them to be checked with any theorem prover that accepts the SMT LIB format. Another example of a common language for semantic representations is Datalog [Whaley05] which has been used to build a variety of tools for checking array bound overflows, finding race conditions in multithreaded programs and checking web application security. 2.3.2 Tool Development Framework or Architecture To foster new tool development, additive software analysis requires initial building blocks. The key initial building block is a framework that can tie the capabilities of tools or techniques together. Just as Eclipse greatly facilitates the improvement of IDE technology for developing code, a framework for additive software analysis will aim to enable synergistic development of software assurance and testing tools. This "framework" may be a separate tool, or it may be a plugin or update to an existing IDE. Broadly speaking, there are two common methods for frameworks to transmit information between program analysis tools. The first method integrates a checker as a plugin into an existing compiler toolchain. Modern compiler frameworks, e.g. gcc, Clang and Frama C, make it easy to write new plugins. Furthermore, plugins are often allowed to update an AST or intermediate form, thus allowing plugins to make the results of their analysis available for use by other plugins. For instance, the Frama C compiler framework provides a library of plugins that includes use def and pointer alias analyses that are often necessary for writing semantic analyzers. The second method relies on a common format that is written to disk or sent via network to pass information. An example of this is the Evidential Tool Bus [Rushby05] that allows multiple analysis engines produced by different vendors to exchange logical conclusions in order to perform sophisticated program analyses. Information could be attached to the code to become "assurance carrying code" [Woody16] An additive framework would support both information transmission approaches in order to reuse existing efforts as much as possible. The framework capabilities referred to in this section focus on information exchange among tools, rather than development capabilities of frameworks discussed in Sect. 2.4. 2.3.3 Strategy to Combine Analysis Results With standards in place and a framework, we can get increased benefit by adding together or combining different software analyses. There are three general ways that results of software analysis can be added together. The first case is simply more information. Suppose the programmer already has a tool to check for injection bugs (INJ class) [Bojanova16] Adding a tool to check for deadlocks could give the programmer more information. NISTIR 8151 DRAMATICALLY REDUCING SOFTWARE VULNERABILITIES: REPORT TO OSTP 19 This puication is avilable ree of carge rom https:/rg/10.6028/N IS .IR .151 The second case is confirmatory or contradictory. The programmer may have two different heuristics to find faulty operation (FOP class) bugs [Bojanova16] that have independent chances of reporting true FOP bugs and false positives. The framework could be used to correlate the outputs of the two heuristics to produce a single result with fewer false positives. In contrast, one tool may say that a statement is reachable, while another tool says that it is not. This contradiction may indicate differences in assumptions or an error in a tool. A set of deduction rules used in one tool may be consistent in isolation, but inconsistent with rules from another tool. The third case of additive software analysis is synergy. A research group with expertise in formal reasoning about memory use and data structures could build upon a component developed by a group that specializes in "parsing" binary code, thus creating a tool that reasons about the memory use of binaries. Developers can experiment with hybrid and concolic assurance tools more quickly. For instance, a tool may use a static analyzer to get the code locations that may have problems then, using constraint satisfiers and symbolic execution, create inputs that trigger a failure at each location. 2.3.4 Technology to Combine Analysis Results Once trained, such neural networks might serve as vulnerability detection engines in their own right. Incorrect conclusions from manual analysis is both timeand resource intensive. To be effective, the above strategies to combine results must be instantiated in tools with appropriate technology. For instance, Code Dx [CodeDx15] is a tool that matches, consolidates and presents the output of analysis tools. Even more powerful would be applying machine learning techniques, such as those in Microsoft's Cognitive Services and Computational Network Toolkit and Google's TensorFlow. The underlying hardware required to perform both the training and inference stages of deep learning and neural networks has dramatically dropped in price. Cloud services now provide high end graphics processor unit (GPU) instances on demand. This computing capability dramatically increases the speed of machine learning algorithms, allowing for training with much larger datasets and significantly faster training and feedback loops. Organizations that have amassed large corpora of vulnerability, exploit, malware, rootkit and backdoor information can mine this information with well known data science techniques to derive new insights and value. Once trained, such neural networks might serve as vulnerability detection engines in their own right. Incorrect conclusions from human practitioners can be fed back into the training phase to automatically strengthen the discrimination of the algorithms or networks and incrementally improve them. These techniques have the potential to detect vulnerabilities across a broad set of languages, including newly launched languages without well established analysis tools, and even detect new classes of vulnerabilities. NISTIR 8151 DRAMATICALLY REDUCING SOFTWARE VULNERABILITIES: REPORT TO OSTP 20 This puication is avilable ree of carge rom https:/rg/10.6028/N IS .IR .151 This detection capability could augment existing tool chains. More importantly, results from other analysis tools could be an additional source of information for training and analysis of these powerful techniques. These same networks, given enough resources, can also analyze vast swaths of source code with the same goal of identifying and prioritizing risky components. 2.3.5 Maturity Level Many commonly used compilers, such as gcc, Clang and Frama C, provide built in support for adding plugins that process and update AST and IR representations. Additionally, large communities have developed extensive libraries of plugins and created wiki sites with tutorials and reference manuals that lower the bar for new users to become involved. In the case of semantic representations, the communities are smaller and the bar to entry is higher, although languages like Boogie have been successfully used as the engine by several research groups for building checkers for diverse languages, such as C [VCC13] and Eiffel [Tschannen11] and even an operating system [Yang10] There are many current software information exchange systems, such as LLVM, ROSE, gcc's GENERIC or GIMPLE and the Knowledge Discovery Metamodel (KDM) Formats to consolidate the output of tools, such as Tool Output Integration Framework (TOIF) and Software Assurance Findings Expression Schema (SAFES) [Barnu