Intro Flashcards
Dynamic analysis
Dynamic analysis is the class of run-time analyses. These analyses discover
information by running the program and observing its behavior.
Static analysis
Static analysis is the class of compile-time analyses. These analyses discover
information by inspecting the source code or binary code of the program.
Hybrid analysis
Hybrid analyses combine aspects of both dynamic and static analyses, by combining
runtime and compile-time information in interesting ways
iterative approximation.
A common static analysis method. The term iterative approximation implies that in general, the analysis might need to
visit the same program point multiple times. This is because of the presence of loops,
which can require the analysis to update facts that were previously inferred by the
analysis at the same program point. We will emphasize this aspect in the following
example.
Parts of static analysis
Program representation. In order to analyze a program, we
must be able to represent it precisely. Choices in program representation range
broadly with different levels of abstraction. Common representation choices include
control-flow graphs, Abstract Syntax Trees (ASTs), and bytecode
Abstract domain. Static analysis does not operate on actual
program values, so we must represent concrete states with an approximate, abstract
domain. In our example, we chose single constant values, in combination with ‘top’
and ‘bottom’ to comprise our abstract domain.
A transfer function specifies how to calculate the abstract state given a program
statement. For example, in our iterative analysis, given the statement “x=1”, the
transfer function would set x to 1 in our abstract state. The transfer functions also
specify how to combine information at control-flow merge points.
Fixed-point computation algorithm. Invokes
the transfer functions of individual program statements to analyze the program. The
algorithm computes a “fixed-point” meaning that it terminates when the abstract states
are no longer changing.
At each step, the analysis designer has many choices.
Sound analysis
Never accepts bad programs
Complete analysis
Never rejects good programs
Trivial analysis
rejects every program
False positive
a good program that rejected by an analysis
Precision and recall
are standard ways to measure accuracy of the systems that output binary (yes/no) classifications. Analysis either accepts or rejects a given program
Precision
measures the number of bad programs among all programs that analysis rejected. It measures the false positive rate of the analysis.
precision = # true positives/ # rejected
Recall
measures the number of bad programs that the analysis rejected among among all bad programs. It measures false negative rate of the analysis.
recall = # true positives/#bad
F-Measure or FI score
a standard measure of
accuracy that combines both precision and recall. It is computed by taking the
harmonic mean of precision and recall.
F-measure = 2/((1/precision) + (1/recall))
Who needs program analysis
Compilers
Software quality tools
IDEs(Integrated Development Environments)
