Predictive Monitoring against Pattern Regular Languages
summary
Shows a conditional hardness result: predictive monitoring against regular languages requires at least O(n^α) lower bound time under fine-grained assumptions (α relates to thread count), so generic predictive checking is infeasible for large executions. Defines pattern languages (depth D≈3–5) that capture common concurrency bugs, gives a PatternTrack constant-space streaming algorithm (vector-clock implementation, space O(#threads), or D!·|Σ| for the NFA approach), and evaluates it on Java benchmarks showing scalability and practical bug detection.
AI-written summary · about
chapters (10)
- 0:00Predictive monitoring intro
- 1:10Dynamic analysis limits
- 3:02Predictive monitoring problem
- 4:07M-traces and independence
- 5:53Regular language challenges
- 7:41Pattern languages for monitoring
- 9:10Streaming algorithm
- 11:36Evaluation and scalability
- 12:41Summary and future work
- 13:25Q&A
related talks
15mSound Dynamic Deadlock Prediction in Linear Time
55mJava PathFinder: going to Mars without bugs and deadlocks
24mTLA+: Your Secret Weapon Against Concurrency Hell
59mUnder-approximation for Scalable Bug Detection
15mPAFL: Enhancing Fault Localizers by Leveraging Project-Specific Fault Patterns
20mAutomatic Repair of Regular Expressions
15mGrammar-Based Testing for Little Languages: An Experience Report with Student Compilers
38mFixing your performance and concurrency bugs