Program Analysis
{ Mario Barrenechea
[Link]@[Link]
What’s the Point of Analyzing Programs?
Benefits: Program correctness, optimization, verification, performance, profiling,
…
Costs: Development time or testing time, depending on when analysis is
done.
Some analyzers are very expensive (GrammaTech [1] has a static analyzer for
C/C++ that costs almost $6000 for a single license).
Alternatives: Brute force testing, testing, testing.
But you never really know when you’re done…
Consequences (for not doing it): Sometimes inexplicable and critical
failures that lead to software crises [WP].
NASA Mariner 1
Mars Polar Lander
F22 Raptor
Radiation Therapy machine from the 1980’s.
Patriot Missile System.
Software bugs costs the U.S $59.5 billion annually, according to a 2002 NIST report
[WP].
Testing vs. Program Analysis
These forms of software verification are hard to pull apart. Testing can be thought of as
a program analysis technique (verification, validation), yet program analysis also has
applications for performance, profiling, and even more formal methods for verifying
program correctness (instead of robustness or fault-tolerance, for example).
Testing: Focused on the verification and validation of software programs, often by
utilizing executable, non-formal methods such as:
Black, gray, and white box testing
Unit/integration/subsystem/regression/acceptance testing
Mutation testing
Other methods.
Testing is the de facto standard for performing quality assurance for a software project.
Program Analysis: Focused on utilizing tools and techniques (not so much
methodology) on the rigorous and sometimes formal examination of program source
code:
Data flow analysis
Dependency Analysis
Symbolic Execution
Can you pull them apart in a different way?
Definitely. Testing is considered a form of dynamic verification, while program analysis
is more often a form of static verification. Think about what it means to perform static
examinations of a program.
Three Kinds of Analyses
Generally speaking, there are three ways in which program analysis can
be performed to analyze program source code:
Static: Set of techniques to analyze source code without actually
executing the program:
Data-flow Analysis (DFA)
Symbolic Execution
Dependence Analysis
Dynamic: Set of techniques to rigorously examine a program based on
some criteria during run-time:
Code Coverage Analysis
Error-seeding and mutation testing, regression testing, other testing
Program slicing
Assertions
Human: Often goes without saying, but human analyses include:
Program comprehension
Code reviews and walkthroughs
Code inspections
A brisk walk through these analyses
We will visit some static, dynamic, and human analysis
techniques.
But it won’t get too complicated; the idea is only to get an idea of
how these analysis techniques can help aid the developer in
producing quality software.
And there will be pointers to some tools out there that exemplify
how these techniques can be useful!
Static Analysis
Static analysis is a rigorous examination of program source code during
compile-time (before run-time). The programmer must specify from the
array of static analysis tools to fulfill the job of helping to satisfy some
criteria, or the set of concerns shared by the programmer:
Memory leaks
Dangling pointers
Uninitialized variables
Buffer overflow
Concurrency Issues {deadlock, race conditions}
Performance bottlenecks
You can think of a set of criterion (or criteria) [3] as some predicate
𝐶 𝑇, 𝑆 , where 𝑇 is the set of test inputs on an executable component 𝑆,
for which 𝑇 satisfies some selection criterion over executing 𝑆. The
expression 𝑆(𝑇) shows the results of executing 𝑆 on 𝑇.
An example of a criteria is something like, for these inputs (𝑇) and this
system (𝑆), 𝐶 (𝑇, 𝑆) = “Does this input instance create a memory leak?”
More on Static Analysis
We also need a way to compare compile-time criteria:
Not all criteria can be satisfied with a single static technique.
Ideally, we would like 𝐶 (𝑇, 𝑆) such that for any 𝑆 and every 𝑇 ⊆ 𝐷(𝑆),
where 𝐷 is the domain of execution of 𝑆:
if 𝑆(𝑇) is correct, then 𝑆 is correct.
Again, ideal, not realistic.
But we can use subsumption to analyze and evaluate these criteria w.r.t the
techniques used:
Ex: Branch Coverage (S,T) => Statement Coverage (S,T)
That is to say, branch coverage “subsumes” statement coverage; every program
S run successfully on branch coverage will also run successfully on statement
coverage.
Note that static analysis can not possibly examine everything.
Since the analyzer is not given the program executable, it cannot infer any
optimizations that the compiler will make on the program.
The implication of this is that a static analyzer can trace through lines of
code and make evaluations based on the logic represented by those
statements. However, it cannot make evaluations based on the execution
of those statements.
The best thing to do? Do both static and dynamic analyses on your
program.
Static Analysis: Data-flow Analysis (DFA)
Data flow analysis is a technique to monitor how variables and
their values change through the program flow. This is awfully
generic, so there are sub-techniques that belong within the DFA
framework that specialize in this form of analysis.
DFA can be broken down into two approaches: forward analysis
and backward analysis. Essentially, to compute several
properties of program statements, some sub-techniques require a
backward approach to DFA while others require a forward one.
Reaching Definitions: Given a variable x and its assignment, where does
it “reach” to without intervening assignments? At what point is the
current value of x irrelevant?
Live Variable Analysis: Given a variable x and its assignment, how long
does it retain a specific value before being re-assigned?
Available Expressions: Given an expression (x+y), where can the
program re-use this expression such that it doesn’t have to be re-computed?
DFA: CFGs!
Before diving in to these sub-techniques, we need a way in which we can
model the program flow. Robert Floyd devised a flowchart language [4]
that allows for propositional interpretation of programs. Today, we call
his construct a flowchart, or more formally, a control-flow-graph (CFG).
A CFG is a graph 𝐺 (𝑉, 𝐸, 𝑆, 𝑇) with 𝑉 vertices, 𝐸 edges, where 𝑢, 𝑣 ∈
𝑉 and an edge connecting 𝑢 and 𝑣 is represented as (𝑢, 𝑣) ∈ 𝐸, 𝑆 as the
starting vertex, and 𝑇 as the terminating (exit) vertex. Since programs
naturally have looping structures, we consider CFGs as directed, cyclic
graphs.
Note that there is more to the eye than just graphically representing a
program using vertices and edges. Floyd was arguing about a novel
construct that could help reason about program correctness using
propositions that are generated after each vertex.
So if a particular program statement assigned the value 5 to a variable x,
then the proposition, “x = 5” is generated in conjunction with all other
propositions that came before that statement. We don’t worry about this
so-called, “propositional propagation” here.
An example of a CFG
START
Does this code terminate?
x := 5
y := x + 50
F
while (x < y) EXIT
x := x + 1
y := y - 1
DFA: Available Expressions
The sub-technique called available expressions allocates re-usable
expressions that recur within the code and propagates them
throughout the program.
Consider the following code:
The value for x wouldn’t be saved, since it’s a simple primitive
value. However, the expression for y = x + 50 and z = x + y + 5.0
would be saved and kept as available expressions.
However, the trick here is that when y or z are changed later in
the program, its assigned expression cannot be re-used again
since the values for those variables have changed.
{ (y = x + 50), (z = x + y + 5.0)} are allocated by the analyzer, but once it
evaluates y = (int) z/y; , we cannot rely on the expression (z = x + y +
5.0) as an available expression, since the value for y has changed.
DFA: Available Expressions
START
x := 5
At a particular vertex i in
the CFG for this program,
two sets called GEN(i) y := x + 50
and KILL(i) are created,
which represent the
available expressions Before each vertex is
allocated within the z := x + y + 5.0
evaluated, the analyzer takes
vertex 𝑖 and those being the set intersection of the GEN
removed, respectively. sets coming into the vertex
and propagates that through,
y := z/y inserting new expressions into
the GEN set and removing
others from the KILL set. The
result of this sub-technique is
Print y several available expressions
that can be saved and used
throughout the program.
EXIT
DFA: Reaching Definitions
Recall: Given an assignment x, where does x “reach out” to? The
sub-technique Reaching Definitions is yet another forward
analysis.
We need to define 𝑑𝑒𝑓 (𝑥) and 𝑢𝑠𝑒 𝑥 pairs for a particular
variable x.
𝑑𝑒𝑓 𝑥 = The point in the program where x is defined or re-defined.
𝑢𝑠𝑒 𝑥 = The point in the program where x is being used or referred.
We call this linkage a def-use chain or pair.
Why do we care about this?
Reaching Definitions can help us spot “dead code”, or code that
contains a def or ref of some variable x that will not be used in the
program.
Ex: Where is the dead code here?
DFA: Reaching Definitions
START
x := 100
x := 60
print x EXIT
We perform the same forward propagation here: At the vertex where 𝑥 ≔ 100 ,
we add that assignment to the GEN set for this vertex. Then, for the next vertex
at [𝑥 ≔ 60], we make the set assignment:
𝑮𝑬𝑵 𝒙≔𝟔𝟎 = 𝑮𝑬𝑵 𝒙≔𝟏𝟎𝟎 − 𝑲𝑰𝑳𝑳 𝒙≔𝟏𝟎𝟎
When we find that the current assignment overlaps with an assignment in the
GEN set, we add that GEN set member to the KILL set so that we get rid of it –
dead code.
DFA: Live Variable Analysis (LVA)
LVA: “What variables might get used later?”
This time, we’ll use a backward analysis sub-technique known as
LVA.
LVA allows us to compute the GEN and KILL sets of variables
from the bottom going up. For each vertex in the CFG, the
analyzer keeps track of used variables and eliminate those that
have been defined. This backward propagation allows us to keep
track of variables that are “live” at various points in the program.
With this code split into two blocks
(separated by line break), the GEN set
for the first vertex going up is {z} and
KILL is {y} since it is being assigned.
Consequently, the GEN set for the
second code block must be {} since it is
at the top of the program, and all of
the variables have been shown to be
defined at some point.
EXIT
DFA: LVA
The last code block performs x := 0
a set union from the GEN set y := 1
from the first and the second z := x + y
vertices to represent true and if (z < 10) {
false branches from the
conditional. Finally, we see y := 10
that all of the variables have z := x + y
been defined here, as our }
GEN set after the vertex has
been evaluated is {}. The
KILL set, on the other hand, print x,y,z
is {x,y,z}. w := x + y + z START
z = z + w
The next block is the body of We start down here, remember? The
the if conditional. The GEN GEN set for this vertex after it has been
set for this vertex after it has evaluated contains {x,y,z}. The KILL set
been evaluated contains {x}. was {z, w} because both were defined
The KILL set contains {z,y}. here.
Dynamic Analysis
While static analysis is done to make rigorous evaluations of the
program source code for optimization, correctness, or
performance purposes, dynamic analysis is well suited for making
evaluations based on program runtime, or execution.
Typically, a dynamic analyzer needs an output specification to
compare the actual output to. Generally speaking, an oracle is the
specification against which actual outputs compare their results.
Can be another system, model, person, customer, etc.
In the case of black box testing, the output specification is the oracle.
Here, we see criteria play a role in which some techniques (or
even sub-techniques) are better than others.
Coverage analysis is a great example of this: The most costly (and yet
most powerful) form of code coverage is all-paths, where
𝐴𝑙𝑙 𝑃𝑎𝑡ℎ𝑠 𝑇, 𝑆 => 𝐵𝑟𝑎𝑛𝑐ℎ 𝑇, 𝑆 => 𝑆𝑡𝑎𝑡𝑒𝑚𝑒𝑛𝑡(𝑇, 𝑆)
Dynamic Analysis: Assertions
Assertions are fantastic ways to perform dynamic analysis in a program.
It’s easy, almost all languages have assertions built into them, and they
help prevent dubious or malicious inputs from creating unintended
behavior.
Assertions are simple checks to make as actual program statements
within the program source code. When the program is run, all assertions
must be checked and satisfied before program execution can proceed. If
at a point in the program the assertion is not satisfied, the program halts,
and an error message is produced.
Ex:
Dynamic Analysis: Coverage Analysis
As learned in class, code coverage, or coverage analysis, is a way to
dynamically evaluate the pathways through program execution
for given inputs. The idea here is that programmer strives for
100% coverage, through true/false branches of while/for/if/case
structures, as well as all program statements.
3
EXIT
START T
F
2 4
Dynamic Analysis: Testing
Don’t forget: Testing is yet another form of dynamic analysis! Testing is a
method of quality assurance that allows developers to estimate with a
certain percentage of confidence that the program will produce correct
output:
Black/Gray/White box testing: Testing with certain transparency of the
system, which directs how we test the system itself.
Unit testing: Testing several methods, functions, classes
Integration Testing: Testing the connection between modules and their
intra-functionality.
Subsystem Testing: Testing subsystems of modules together with their
intended functionality.
Acceptance Testing: Testing to see if the program meets the requirements
of the customer. Here, the oracle is the customer him/herself!
Human Analysis
Self-explanatory, but it’s the most natural (and presumably most
labor-intensive) way of verifying that the code produces correct
results. In human analysis, programmers, designers, managers,
and testers perform qualitatively and quantitatively controlled
review processes to examine code without use of a computer.
Code reviews, inspections, and human-factors methodologies (ex.
SCRUM) focus in on how to designate teams for improved
developer productivity, communication, and feedback.
Defect Detection methods, developer group
size, and single-interval vs. multiple-interval
sessions are factors discussed in [6] that show
significant tradeoffs made when humans seek
to inspect code bugs without aid of systematic
methods.
Human Analysis: Inspections
In human analysis, the inspection allows a team of program role
members (programmers, testers, managers) to find errors in the
program code in a formal, efficient, and economical fashion [10].
Usually in teams of 4-5, so there is no strict number.
The inspection team for a particular module comprises the tester,
designer, developer, and the moderator:
Moderator: The key to any successful inspection, the moderator uses
his/her leadership to conduct meetings, delegate tasks, and follow-
up on rework.
After the individual preparation of the module being inspected,
the inspection team gathers and enumerates through the logic of
the module.
The designer first explains the design, and with the general
understanding of that design, the team members walk carefully
through the module line by line (and branch) in order to find errors.
Human Analysis: Inspections
An example [10] of a code inspection report that the inspection
team uses to monitor error-tracking:
Note that this is how bug-tracking was done in 1976!
Program Analysis Tools?
I’m quite bitter about them.
There are two worlds out there:
One world with program analysis tools that come integrated into
development environments that enable the developer to make more
rigorous examinations of her code.
The other world chalk full of exciting and (mostly) free program
analysis tools that are exceedingly difficult to configure or install
properly, comprehend, and use within your development
environment.
I’m a fan of the first world and not the second.
Case Study: Eclipse
The Eclipse Integrated Development Environment (IDE) [9] is an
excellent way to take advantage of a plethora of static analysis
techniques at your fingertips.
When you create a new Java project and start writing code, you
will notice red and yellow squiggly lines underneath some of
your code.
The yellow squiggly line indicates a future compiler warning; that is,
the eclipse environment has evaluated your code and foretold you
that some program statement is causing an irregular behavior,
perhaps an unused variable, un-genericized type, or some other
reason.
The red squiggly line, on the other hand, indicates a future compiler
error that will cause unpredictable behavior if the program is run.
This is most typically due to syntax errors, but it can also be because
of referring to a type not recognized, a variable not defined yet, etc.
What kinds of static analyses can detect these problems?
Case Study: Eclipse
Example of a future
compiler warning:
Example of a future
compiler error:
Conclusions
Program Analysis is a deep sub-field straddled between software
engineering and programming language research with lots of
open problems.
To determine if a program will halt (or not) is undecidable. How
does this affect our analysis?
Static, dynamic, and human analyses help us be more informed of
our program behavior and how we can improve it.
As newer technologies (cloud computing for example), we must find
ways of breaking down their complexity to address security,
performance, and other thematic concerns. Program analysis
provides a means of breaking down (analyzing) that complexity.
Visit the Tools page (next slide) to learn more about the tools
referenced throughout this presentation.
List of Tools
List of tools:
Coverity [2] : [Link]
C/C++ static analyzer for commercial use
Grammatech Codesurfer/Codesonar [1]: [Link]
C/C++ static analyzer for commercial use
Eclipse development environment [9]: [Link]
Open source programming environment for a host of supported
languages and technologies. Very popular and comes with integrated
static analyzer for select languages.
Soot [5]: [Link]
Java Optimization framework (static analysis), although not
straightforward to set up.
Xcode [7]: [Link]
Apple’s very own integrated development environment that comes with
a built-in static analyzer and performance monitoring tools.
Avalanche [8]: [Link]
An open-source dynamic analyzer. Again, very hard to configure and
use.
References
[1]: Static Analysis for C and C++ | GrammaTech. (n.d.). Retrieved March 21, 2012,
from [Link]
[2]: Coverity Static Analysis Tools for C/C++, C#, and Java | Coverity. (n.d.). Retrieved
March 21, 2012, from [Link]
[3]: Clarke, L. A. (2010). Introduction to Dynamic Analysis. Presentation.
[4]: Floyd, R. (1967). Assigning meanings to programs. Mathematical aspects of computer
science. Retrieved from
[Link]
s=i1HMoZeLAd&sig=9mSUp4i49ntWJW1G7rjm8KFBQh8
[5]: Soot: a Java Optimization Framework. (n.d.). Retrieved March 22, 2012, from
[Link]
[6]: Porter, A., Siy, H., & Toman, C. A. (1995). An Experiment to Assess the Cost-
Benefits of Code Inspections in Large Scale Software Development, 92-103.
[7]: Apple Xcode Tools. [Link]
[8]: Avalanche Dynamic Analysis. [Link]
[9]: The Eclipse Foundation. [Link]
[10]: Fagan, M. (1976). Design and code inspections to reduce errors in program
development. IBM Systems Journal, 15(3), 258-287. Retrieved from
[Link]
And [WP]: Wikipedia for general acquaintance with the body of knowledge.
Program Analysis
Mario Barrenechea
Software and its complexity has increasingly convinced
researchers and engineers to utilize program analysis as a form of
verification, both through formal and practical methods.
This presentation will walk through three types of analyses
{static, dynamic, human} in order to give a well-rounded glimpse
of how program analysis can help you in future development!
Static techniques: Dynamic techniques: Human techniques:
Data-flow analysis Testing Code Inspection
Symbolic Execution Assertions Program Comprehension
Dependence Analysis Coverage Analysis Code Reviews