Dynaplex: analyzing program complexity using dynamically inferred recurrence relations

Abstract

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 bounds of recursive programs. From program execution traces, we learn recurrence relations and solve them using pattern matching to obtain closed-form solutions representing the complexity bounds of the program. This approach allows us to efficiently infer simple recurrence relations that represent nontrivial, potentially nonlinear polynomial and non-polynomial, complexity bounds.

Document Details

Document Type
Pub Defense Publication
Publication Date
Oct 15, 2021
Source ID
10.1145/3485515

Entities

People

  • Didier Ishimwe
  • KimHao Nguyen
  • ThanhVu Nguyen

Organizations

  • Army Research Office
  • George Mason University
  • National Science Foundation
  • University of Nebraska–Lincoln

Tags

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Calculus or Mathematical Analysis
  • Parallel and Distributed Computing.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms