Static program analysis

Static program analysis is the practice of reasoning about the behavior of computer programs without actually running them. It can be useful for development of more efficient compilers, as well as for automated error detection, which can improve the reliability and security of code.

Static program analysis is a practice and set of technologies which are designed to analyze application source code, byte code, and binaries for features and behaviors without actually needing to run the code. Static program analysis has been used since the 1960s to optimize compilers, but has been applied more recently to the problems of finding software bugs, verifying and validating code, and in integrated development environments (IDEs) to support program development.

In the context of application security, wherein static program analysis techniques are used to detect security vulnerabilities, the practice is often referred to as static application security testing (SAST).

Applications of static program analysis

Static program analysis can be applied across several different domains of software development practice. The ability to predict program behavior can aid in program optimization, security audits, automatic parallelization, and correctness verification.

Advantages and disadvantages

Software testing typically occurs in one of two basic ways: static analysis and dynamic analysis. Static analysis evaluates the correctness and soundness of code without needing to actually run the code. Dynamic analysis, however, evaluates software based on its runtime and outputs, requiring the tester to run the program, sometimes in a virtual environment. Each has its advantages and disadvantages.

Engineering workflow

  • Static analysis can scale well across a large software development organization. Automated static analysis can be run repeatedly, such as when shipping nightly builds or as part of a continuous integration workflow.
  • Dynamic analysis checks that a software project achieves its specified functionality.
  • Static analysis can decrease the amount of testing and debugging required to consider a piece of software ready to ship.To pass most static analysis tests, code must be written in a way that is reliable, readable, and less prone to errors on future tests.

Soundness and completeness

  • The results of dynamic analysis are not generalized for future executions. There is no certainty that the set of inputs over which the program was run is characteristic of all possible program executions.
  • Static analysis can be sound because it evaluates the logic and structure of code. A sound static analysis tool will occasionally produce false positives, suggesting that a piece of code may be buggy or when it is just fine.

Selection criteria

  • Support for the programming language or framework(s) which needs to be analyzed.
  • Types of errors and vulnerabilities the static analysis testing tool can detect.
  • The accuracy of the tool, including its rate of false positives.
  • Ease of use and integration into existing development tools and deployment workflows.
  • In the case of commercial solutions, cost and licensing presents its own set of decisions and trade-offs

Evolution of static analysis tools

Static analysis is frequently used in evaluating code validity and code security. Static analysis tools, including those designed for security testing, have evolved over time.

First generation of tools

The first generation of static analysis software tools emerged in the 1970s.

In the context of security, these early tools primarily consisted of homegrown scripts which would apply 'grep'-like functions to source code to determine whether the code employed unsafe functions which could expose vulnerable information or crash the program.

These first generation tools would create many false positives which would require manual review by the programmer or security analyst.

Second generation

Second generation tools took advantage of increased processing power and system memory to perform more complex forms of analysis of code. These tools emerged in the 1990s and early 2000s. Moving beyond spot checks and what was essentially simple keyword search within source code, second generation tools implemented more complex methods like path analysis to evaluate the deeper reasoning of a program's behavior at runtime.

Open source security testing tools like RATS from Secure Software, David Wheeler's Flawfinder, and ITS4 from Cigital are part of this second generation.

Third generation

The third generation of static analysis tools emerged in the 2000s and facilitated deeper code evaluation and analysis, as well as testing for more languages and frameworks.

Abstract syntax tree modeling helped give many of these tools a leg up in terms of accuracy and completeness. Using an abstract structure to represent the logic of a program captures the essence of a codebase's logic. This results in a more efficient way to predict the codebase's behavior.

In the 2010's and later, viewing code as data became more of a norm.

Companies

Static analysis software companies

Timeline

1978

Computer scientist Stephen C. Johnson, then working at Bell Labs, releases 'lint'

Lint was developed by computer scientist Stephen C. Johnson, then working at Bell Labs. Johnson explains that he developed lint to help with debugging the YACC grammar he was writing for the C programming language.

In an interview with red-gate.com, Johnson recalls, "I had the grammar written, but no way to test it! I could run it on the body of C code that existed, but I had no way of telling whether I had correctly 'understood' the programs. So I hit on the idea of checking the consistency between function calls and definitions (this was before C had function prototypes, so mismatches were a common source of errors). When we ported Unix to a 32-bit machine, all of a sudden portability become very important, and we found ourselves looking for things that might cause portability problems."

Lint is derived from the Portable C Compiler, which Johnson also developed at Bell Labs. Richard Morris, who interviewed Johnson for red-gate.com, explains that "Lint was a preprocessor written to indicate problem areas in code such as variables being used before being set, conditions that are constant, and calculations whose result was likely to be outside the range of values that could be represented in the type used. Versions of Lint were eventually developed for many C and C++ compilers. This function is nowadays usually included within the compiler itself but Lint-like applications are also used to indicate ‘code-smells’."

Lint and following lint-like applications (often called "linters") are among the earliest examples of static code analysis tools used in development environments.

People

Name
Role
LinkedIn

Further reading

Title
Author
Link
Type
Date

jacob-l/awesome-static-analysis

Web

Static and dynamic analysis: synergy and duality

Michael D. Ernst

PDF

2003

Static Program Analysis

Anders Møller and Michael I. Schwartzbach

PDF

December 16, 2009

What's the Difference Between Sound and Unsound Static Analysis?

Claire Dross and Boris Yakobowski

Web

Documentaries, videos and podcasts

Title
Date
Link

Static Analysis: Introduction part 2 - PROGRAM ANALYSIS | Coursera

Theories, Solvers and Static Analysis by Abstract Interpretation

August 16, 2016

What Are Static Analysis Tools?

What is Static Analysis? by Matt Might

August 1, 2004

Companies

Company
CEO
Location
Products/Services

References

Golden logo
Text is available under the Creative Commons Attribution-ShareAlike 4.0; additional terms apply. By using this site, you agree to our Terms & Conditions.