CS6340 Exam Notes - Software Analysis and Testing

Flashcards on Software Analysis and Testing

Program Analysis

A body of techniques and tools that automatically discover useful properties or facts about computer programs.

Dynamic Program Analysis

Analyzing a program during its execution.

Purify

Detects memory access errors like array bounds violations during dynamic analysis.

Eraser

Identifies data races in multithreaded programs during dynamic analysis.

Valgrind

Detects memory leaks, use-after-free bugs, etc. during dynamic analysis.

Daikon

Dynamically infers program invariants during dynamic analysis.

Static Program Analysis

Examines source code or intermediate representations without executing the program.

Lint, FindBugs, Coverity

Detect suspicious code patterns and possible bugs during static analysis.

Infer (by Facebook)

Identifies memory leaks and null pointer issues in Android and iOS apps during static analysis.

SLAM (Microsoft Research)

Verifies that Windows device drivers correctly use the Windows kernel API during static analysis.

ESC/Java

Checks correctness properties (invariants) of Java programs during static analysis.

Hybrid Program Analysis

Combines both static and dynamic analysis.

Program Invariant

A property or fact that holds true at a particular program point during all possible executions.

Control Flow Graph (CFG)

A representation of all paths that might be traversed through a program during its execution.

Concrete State

Exact variable values at runtime (available in dynamic analysis).

Abstract State

Approximate or symbolic representations of values (used in static analysis).

Termination

The analysis process should eventually halt.

Completeness

An analysis is complete if it finds all possible issues, but static analysis is rarely complete because it relies on approximation.

Soundness

An analysis is sound if all the reported facts are guaranteed to be true across all program executions.

False Positive

Analysis wrongly flags correct code as buggy.

False Negative

Analysis misses an actual issue in the code.

Testing

Checks whether the actual behavior matches the intended behavior.

Consistency Checking (in Testing)

Verify consistency between implementation and specification.

Black-Box Testing

Tests the external behavior of the software; does not require code access or knowledge of internal structure.

White-Box Testing

Leverages knowledge of internal code structure to design tests; helps with path coverage, checking all branches, loops, conditions, etc.

Pre-Condition

What must be true before a function executes.

Post-Condition

What must be true after the function executes, if the pre-condition held.

Frame Conditions

Assumptions about unchanged parts of the program.

Code Coverage Metrics

Measures how much of the code has been exercised.

Function Coverage

Which functions were executed?

Statement Coverage

Which lines were run?

Branch Coverage

Were all decision branches taken?

Basic Block Coverage

Execution of straight-line code sequences.

Competent Programmer Hypothesis

Real programs are close to correct, so small changes (mutants) are meaningful tests.

Mutation Testing

Introduce small changes (mutants) to code (e.g., change x > 0 to x < 0).

Equivalent Mutants

A mutant behaves identically to the original for all inputs.

Korat

Automatically generate small, valid, and diverse test inputs satisfying pre-conditions.

Randoop

Automatically generate valid method call sequences that explore new object states and violate contracts if bugs exist; uses execution feedback to guide generation of new test sequences.

Pointer Aliasing

Occurs when the same memory address is referred to through different variables.

May-Alias Analysis (Pointer Analysis)

Assumes that two variables may point to the same object; initially, all pairs are assumed to alias, and analysis removes false pairs as it gathers more information.

Must-Alias Analysis

Assumes two variables must point to the same object and builds constraints based on this.

Heap Abstraction

How to model dynamically allocated memory (heap).

Allocation-Site Based Heap Abstraction

One abstract object per allocation site (new, malloc).

Type-Based Heap Abstraction

One abstract object per type.

Heap-Insensitive Heap Abstraction

One abstract object for entire heap.

Flow-Insensitive

Ignores the order of statements; performs weak updates (accumulates new facts without removing old ones).

Flow-Sensitive

Considers the exact flow of control; performs strong updates (can remove old facts).

Context-Insensitive

Analyzes each procedure once.

Context-Sensitive

Analyzes each procedure per abstract calling context.

Arrays (in Pointer Analysis)

Use a single field [ * ] to represent all elements; loses ability to distinguish between elements.

Field-Insensitive

All fields of a record merged.

Field-Based

Same-named fields across records are merged.

Field-Sensitive

Most precise — each field of each object is separate.