# Discriminating Traces with Time

arXiv: https://arxiv.org/abs/1702.07103 · HTML: https://mlsanity.com/paper/1702.07103/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2017.

## Built on by (most cited first, 1 of 1)

- [Worst-Case Convergence Time of ML Algorithms via Extreme Value Theory](https://mlsanity.com/paper/2404.07170/) (2024)

## Abstract (arXiv)

What properties about the internals of a program explain the possible differences in its overall running time for different inputs? In this paper, we propose a formal framework for considering this question we dub trace-set discrimination. We show that even though the algorithmic problem of computing maximum likelihood discriminants is NP-hard, approaches based on integer linear programming (ILP) and decision tree learning can be useful in zeroing-in on the program internals. On a set of Java benchmarks, we find that compactly-represented decision trees scalably discriminate with high accuracy---more scalably than maximum likelihood discriminants and with comparable accuracy. We demonstrate on three larger case studies how decision-tree discriminants produced by our tool are useful for debugging timing side-channel vulnerabilities (i.e., where a malicious observer infers secrets simply from passively watching execution times) and availability vulnerabilities.