Static Analysis

Static Analysis
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Some Common Terms

These Terms as they Apply to Programs

Static Analysis of a Program

Defined:
- The automated review of a program (or a part of a program) "before" it is executed
Possible Inputs:
- Source code
- Compiled/partially-compiled code

Kinds of Static Analysis

Style Checking:
- Syntactically correct but stylistically inappropriate
- Nerd Humor:
  
  (Courtesy of xkcd)
Construct Checking:
- "Suspicious" constructs (e.g., variables used but not initialized, division, unused variables, constant logical expressions, etc...)
- Non-portable constructs (e.g., potential range problems)
- Memory allocation inconsistencies
Software Metrics:
- Thousand Lines of Code (KLOC)
- Cyclomatic Complexity (calculated from the nodes and edges in the control flow graph)
- Halstead Complexity (calculated from the number of operators and operands)
Formal Methods:
- Model Checking (determine if the program satisfies all requirements)
- Data Flow Analysis (calculate the possible set of values using the control flow graph)

Some History

FORTRAN:
- As early as 1954 FORTRAN compilers included static analysis tools for optimization
lint:
- Developed at Bell Labs in the mid 1970s to find the "undesirable fiber and fluff" in C programs
Software Assurance Marketplace (SWAMP):
- Trying to become a free central repository for a wide variety of tools (funded by the Department of Homeland Security)

Something to Think About

Suppose:
- An adversary/attacker gets access to your source code
An Unfortunate Use of Static Analysis Tools:
- She/he can use static analysis tools to find vulnerabilities (e.g., a buffer overrun)
An Important Implication:
- Developers should use static analysis to eliminate these vulnerabilities (and the resulting attacks)

Some Empirical Results (Nagappan and Call, 2005)

Static analysis can be used to predict pre-release defect density
Static analysis can be used to discriminate between components of high and low quality

Strengths and Weaknesses of Existing Tools

Strengths:
- Can check a large code base
- Are very fast
Weaknesses:
- Only work for certain types of faults/defects
- Often generate false positives