abstract-trace-summarizer

Abstract Trace Summarizer

Overview

This skill performs abstract interpretation to analyze program behavior and produce summarized execution traces. It computes over-approximations of possible runtime states, tracks control flow paths, infers variable relationships, and generates high-level behavioral summaries without requiring concrete program execution.

Core Workflow

1. Program Analysis Setup

Initial Assessment:

• Identify programming language and paradigm
• Determine analysis scope (function, module, program)
• Select appropriate abstract domains
• Identify analysis goals (safety, correctness, optimization)

Abstract Domain Selection:

Choose domains based on analysis needs:

Numerical domains:

• Intervals: Track value ranges [min, max]
• Signs: Track {negative, zero, positive, unknown}
• Octagons: Linear constraints ±x ±y ≤ c
• Polyhedra: General linear constraints

Non-numerical domains:

• Nullness: Track {null, non-null, unknown} for pointers
• Constant propagation: Track known constant values
• Type domains: Track possible types
• Parity: Track {even, odd, unknown}

Relational vs non-relational:

• Non-relational: Track variables independently (faster, less precise)
• Relational: Track relationships between variables (slower, more precise)

2. Control Flow Analysis

Build Control Flow Graph (CFG):

Represent program structure:

Entry → Statement₁ → Statement₂ → ... → Exit
         ↓ (branch)
       Statement₃ → ...

Identify key structures:

• Sequential: Straight-line code
• Conditional: if-then-else branches
• Loops: while, for, do-while
• Function calls: Call/return edges
• Exception handling: try-catch-finally

Path analysis:

• Path-sensitive: Track separate states per path (more precise)
• Path-insensitive: Merge states at join points (more efficient)
• Trace partitioning: Hybrid approach based on key predicates

3. Abstract State Computation