Data Flow Analysis

This section covers data flow analysis engines and tools.

• Algebraic Program Analysis (APA)
  • Overview
  • Main components
  • Interprocedural Forward Summary Solver
  • Typical use cases
  • See also
• Control Flow Support
  • Overview
  • Main components
  • Why it exists
  • See also
• Monotone Dataflow Engine
• Overview
• Core Idea
• Example Analyses
  • Live Variables (SSA)
  • Reachable Instructions
• IFDS / IDE Engine
• Overview
• IFDS: Set-Valued Problems
  • Example — Taint Analysis
• IDE: Value-Enriched Problems
  • Example — Linear Constant Propagation
  • Example — Typestate Analysis
• Usage
• Command-Line Tool: lotus-taint
  • Key Options
  • Examples
• VASCO Value-Context Framework
• Overview
• Why VASCO
• Value Contexts
• Algorithm Sketch
• Core API
  • Generic Interfaces
  • Directional Solvers
• Results
  • Context-sensitive results
  • Merged meet-over-valid-paths results
• LLVM Instantiation in Lotus
• Parallel Context Scheduling
  • Core Idea
  • Versioned Summary Replay
  • Public API
  • Configuration
  • Usage Example
  • Correctness Invariants
  • Design Document
• Current Scope and Caveats
• Relationship to Other Lotus Engines
• WPDS Dataflow Engine
• Overview
• Core Idea
• Example Analyses
  • Constant Propagation
  • Liveness
  • Taint Analysis
  • Uninitialized Variables
• Newtonian Program Analysis (NPA)
• Overview
• Conceptual Background
  • Key Insight: Algebraic Generalization
• Mathematical Foundation
  • ω-Continuous Semirings
  • Comparison with Kleene’s Method
• Examples and Applications
  • May-Alias Analysis
  • Average Runtime Analysis
  • LCFL Sub-Problems and Tensor-Product Regularization
  • Other Applications
• Distributive vs. Non-Distributive Analyses
• Core Implementation (include/Dataflow/NPA/Core)
• Usage Notes
• Practical notes for numeric domains
• References