Using Dynamically Inferred Invariants to Analyze Program Runtime Complexity
Published in International Workshop on Software Security from Design to Deployment, 2020
Recommended citation: ThanhVu Nguyen, Didier Ishimwe, Alexey Malyshev, Timos Antonopoulos, and Quoc-Sang Phan. 2020. Using dynamically inferred invariants to analyze program runtime complexity. Proceedings of the 3rd ACM SIGSOFT International Workshop on Software Security from Design to Deployment. Association for Computing Machinery, New York, NY, USA, 11–14.
In this work, we propose a new dynamic analysis approach for learning recurrence relations to capture complexity bounds for recursive programs. This approach allows us to efficiently infer simple linear recurrence relations that represent nontrivial, potentially nonlinear, complexity bounds. Preliminary results on several popular recursive programs show that we can learn precise recurrence relations capturing worst-case complexity bounds such as O(n log n) and O(cn)