Differential cost analysis with simultaneous potentials and anti-potentials

Dorde Zikelic, Bor-Yuh Evan Chang, Pauline Bolignano, Franco Raimondi

Abstract

Differential cost analysis is essential for identifying performance regressions and side-channel vulnerabilities during software evolution. Traditional relational methods often rely on structural alignment between program versions, which fails when significant refactoring occurs. This paper introduces a novel, alignment-free approach that simultaneously computes upper bounds (potentials) for a new program version and lower bounds (anti-potentials) for the original version. By leveraging Handelman’s theorem and linear programming, the method derives tight thresholds for resource usage differences. Experimental results on 19 benchmarks demonstrate that the approach effectively handles non-aligned code, achieving tight bounds in 74% of cases.

1. Introduction

In software engineering, ensuring that code updates do not introduce performance regressions is a critical challenge. Differential cost analysis seeks to establish a threshold $t$ such that the difference in resource consumption (e.g., time, memory) between a new version ($P'$) and an old version ($P$) is bounded: $Cost(P') - Cost(P) \le t$.

Historically, this has been approached through relational analysis, which attempts to align the execution steps of two programs. However, structural changes—such as loop interchanges or significant refactoring—break these alignments. When alignment fails, tools often revert to unary reasoning, which analyzes each version in isolation. This typically results in loose, pessimistic bounds that are of limited use to developers. This paper proposes a method to sidestep the alignment problem entirely by comparing cost-bound summaries.

2. Methodology: Simultaneous Potentials and Anti-potentials

The primary contribution of this work is an automated, alignment-free method for differential cost analysis. The core innovation lies in the introduction of anti-potential functions.

2.1 Potentials and Anti-potentials

  • Potential Functions (PFs): These are standard tools in amortized analysis used to derive an upper bound on the cost of a program.
  • Anti-potential Functions (anti-PFs): This paper introduces anti-PFs as the dual to potentials, specifically designed to derive a formal lower bound on program costs.

2.2 Simultaneous Optimization

Instead of calculating bounds independently, the proposed algorithm computes the PF for the new version and the anti-PF for the old version simultaneously. This joint optimization allows the solver to find a threshold $t$ that is significantly tighter than the result of simply subtracting an independently calculated lower bound from an independent upper bound. By treating lower bounds as first-class citizens, the analysis captures the nuances of resource consumption changes more accurately.

3. The Analysis Pipeline

The method follows a four-step automated workflow to derive the threshold:

  1. Template Generation: The system generates symbolic polynomial templates representing the potential of the new program and the anti-potential of the old program.
  2. Constraint Collection: The algorithm extracts constraints from the programs' transitions to ensure the PF remains a valid upper bound and the anti-PF remains a valid lower bound across all possible executions.
  3. Algebraic Transformation: To handle complex polynomial inequalities, the authors employ Handelman’s Theorem. This theorem allows the transformation of polynomial constraints into a system of linear constraints.
  4. Linear Programming (LP) Solving: The resulting linear system is processed by an LP solver (such as Gurobi). By setting the objective function to minimize $t$, the solver automatically identifies the tightest possible threshold for the cost difference.

4. Experimental Evaluation

The implementation was evaluated using a suite of 19 program pairs sourced from existing cost analysis and semantic differencing literature. The benchmarks included complex structures such as nested loops, conditional branching, and non-deterministic behavior.

A key focus of the evaluation was "loop interchange" examples. In these cases, the two program versions are semantically similar but syntactically distinct, making them impossible to analyze using traditional alignment-based relational tools.

4.1 Key Findings

  • Precision: The method successfully computed tight thresholds for 14 out of 19 benchmarks (74%).
  • Efficiency: The entire process—from invariant generation to LP solving—is highly efficient, typically completing within a few seconds.
  • Self-Diagnosis: An interesting side effect of this method is its application to single programs. The gap between a program's PF and anti-PF serves as a formal guarantee of the analysis's precision.

5. Discussion and Limitations

While the simultaneous potential/anti-potential approach represents a significant advancement, several areas for improvement remain:

  • Piecewise Costs: The current reliance on polynomial templates makes it difficult to model costs involving max(x, y) or complex if-else logic. This limitation accounted for the five benchmarks where the tool failed to find tight bounds.
  • Program Assumptions: The analysis currently assumes program termination. Future work may extend the theory to handle non-terminating or probabilistic systems.
  • Scalability: The current prototype performs global analysis. For industrial-scale applications, the authors suggest moving toward a modular approach using method summaries.
  • Language Support: The current front-end (using C2fsm) lacks support for pointers and boolean data types, though the underlying theory is designed to accommodate them.

6. Conclusion

By optimizing upper and lower bounds simultaneously, this research provides a robust framework for differential cost analysis that is resilient to code refactoring. The ability to reason about cost differences without requiring code alignment offers a practical path forward for catching performance regressions in evolving software systems.

Summary updated

BibTeX
@inproceedings{zikelic2022differential,
  author = {Dorde Zikelic and Bor-Yuh Evan Chang and Pauline Bolignano and Franco Raimondi},
  title = {{Differential cost analysis with simultaneous potentials and anti-potentials}},
  booktitle = {PLDI},
  year = {2022},
  doi = {10.1145/3519939.3523435},
}
Figure