Inferring Complexity Bounds from Recurrence Relations
Pages 2198 - 2200
Abstract
Determining program complexity bounds is a fundamental problem with a variety of applications in software development. In this paper we present a novel approach for computing the asymptotic complexity bounds of non-deterministic recursive programs by solving dynamically inferred recurrence relations. Recurrences are inferred from program execution traces and solved using the annihilator method and Master Theorem to obtain closed-form solutions representing the complexity bounds.
Our preliminary evaluation shows that this approach can learn correct bounds for popular classical recursive programs (e.g. O(n2) for quicksort), achieving more precise bounds for exponential programs than previously reported (e.g. O((1+√5/2)n) for fibonacci), and capturing a wide range of bounds including non-linear polynomial and non-polynomial, logarithmic, and exponential relations.
References
[1]
Jason Breck, John Cyphert, Zachary Kincaid, and Thomas Reps. 2020. Templates and Recurrences: Better Together. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020). Association for Computing Machinery, New York, NY, USA. 688–702. isbn:9781450376136
[2]
Krishnendu Chatterjee, Hongfei Fu, and Amir Kafshdar Goharshady. 2019. Non-polynomial worst-case analysis of recursive programs. ACM Transactions on Programming Languages and Systems, 41, 4 (2019), 1–52.
[3]
Michael A Colón, Sriram Sankaranarayanan, and Henny B Sipma. 2003. Linear invariant generation using non-linear constraint solving. In Computer Aided Verification: 15th International Conference, CAV 2003, Boulder, CO, USA, July 8-12, 2003. Proceedings 15. 420–432.
[4]
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MIT press.
[5]
Scott A Crosby and Dan S Wallach. 2003. Denial of Service via Algorithmic Complexity Attacks. In USENIX Security Symposium. 29–44.
[6]
Simon F Goldsmith, Alex S Aiken, and Daniel S Wilkerson. 2007. Measuring empirical computational complexity. In Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering. 395–404.
[7]
Jan Hoffmann, Ankush Das, and Shu-Chun Weng. 2017. Towards automatic resource bound analysis for OCaml. In Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages. 359–373.
[8]
Didier Ishimwe, KimHao Nguyen, and ThanhVu Nguyen. 2021. Dynaplex: analyzing program complexity using dynamically inferred recurrence relations. Proc. ACM Program. Lang., 5, OOPSLA (2021), 1–23.
[9]
Didier Ishimwe, ThanhVu Nguyen, and KimHao Nguyen. 2022. Dynaplex: inferring asymptotic runtime complexity of recursive programs. In Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings. 61–64.
[10]
George S Lueker. 1980. Some techniques for solving recurrences. ACM Computing Surveys (CSUR), 12, 4 (1980), 419–436.
[11]
ThanhVu Nguyen, Matthew Dwyer, and William Visser. 2017. SymInfer: Inferring Program Invariants using Symbolic States. In Automated Software Engineering. IEEE, 804–814.
[12]
ThanhVu Nguyen, Didier Ishimwe, Alexey Malyshev, Timos Antonopoulos, and Quoc-Sang Phan. 2020. Using dynamically inferred invariants to analyze program runtime complexity. In Proceedings of the 3rd ACM SIGSOFT International Workshop on Software Security from Design to Deployment. 11–14.
[13]
Sriram Sankaranarayanan, Henny B Sipma, and Zohar Manna. 2004. Constraint-based linear-relations analysis. In Static Analysis: 11th International Symposium, SAS 2004, Verona, Italy, August 26-28, 2004. Proceedings 11. 53–68.
[14]
Peng Wang, Di Wang, and Adam Chlipala. 2017. TiML: a functional language for practical complexity analysis with invariants. Proceedings of the ACM on Programming Languages, 1, OOPSLA (2017), 79.
[15]
Jiayi Wei, Jia Chen, Yu Feng, Kostas Ferles, and Isil Dillig. 2018. Singularity: Pattern fuzzing for worst case complexity. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 213–223.
Index Terms
- Inferring Complexity Bounds from Recurrence Relations
Recommendations
Dynaplex: inferring asymptotic runtime complexity of recursive programs
ICSE '22: Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion ProceedingsAutomated runtime complexity analysis can help developers detect egregious performance issues. Existing runtime complexity analysis are often done for imperative programs using static analyses. In this demo paper, we demonstrate the implementation and ...
Dynaplex: analyzing program complexity using dynamically inferred recurrence relations
Being able to detect program runtime complexity is useful in many tasks (e.g., checking expected performance and identifying potential security vulnerabilities). In this work, we introduce a new dynamic approach for inferring the asymptotic complexity ...
Using dynamically inferred invariants to analyze program runtime complexity
SEAD 2020: Proceedings of the 3rd ACM SIGSOFT International Workshop on Software Security from Design to DeploymentBeing able to detect program runtime complexity can help identify security vulnerabilities such as DoS attacks and side-channel information leakage. In prior work, we use dynamic invariant generation to infer nonlinear numerical relations to represent ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
2215 pages
ISBN:9798400703270
DOI:10.1145/3611643
- General Chair:
- Satish Chandra,
- Program Chairs:
- Kelly Blincoe,
- Paolo Tonella
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 November 2023
Check for updates
Author Tags
Qualifiers
- Short-paper
Conference
ESEC/FSE '23
Sponsor:
ESEC/FSE '23: 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering
December 3 - 9, 2023
CA, San Francisco, USA
Acceptance Rates
Overall Acceptance Rate 112 of 543 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 132Total Downloads
- Downloads (Last 12 months)132
- Downloads (Last 6 weeks)19
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in