Explaining Bug Provenance with Trace Witnesses
summary
Proposes a decidable analysis that maps programs into a simplified machine called the constant copy machine and constructs tree witness traces that explain how a reported assertion is reachable. Implements a gadget (backed by the Doop front end) and a witness generator using all-pairs shortest paths (Floyd–Warshall) so generation runs in polynomial time. Evaluated on Java NPEs reported by Thicket and finds about 80% of reports lack a witness, indicating many likely false positives or unreachable paths.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:03Finding Tools
- 1:37Motivation Example
- 2:30Back Finding
- 4:02Motivation
- 4:37Deep Thinking
- 5:48Our Work
- 7:12CCM Model
- 9:02Semantics
- 10:29Development
- 12:57Tree Witness Generators
- 14:46Case Study
- 15:15Results
- 16:25Conclusion
- 17:32Questions
related talks
48mDPTrace: Dual Purpose Trace for Exploitability Analysis of Program Crashes
27mVerifiable eBPF Traces for Supply Chain Artifacts with Witness and Tetragon
28mDetecting Borrow and Provenance Bugs Across Unsafe Rust [...]
40mCatching More Bugs with Fewer False Alarms
34mTracing: The Bane of You Security Folks
28mSee It to Believe It: Bringing Observability to Otherwise ...
20mBillion Dollar Bugs
22mExploring Answer Set Programming for Provenance Graph-Based Cyber Threat Detection: A(…)