Discriminating traces with time

DOI10.1007/978-3-662-54580-5_2MaRDI QIDQ3303919zbMATH OpenOpenAlexFDO

Authors Saeid Tizpaz-Niari, Pavol Černý, Bor-Yuh Evan Chang, Sriram Sankaranarayanan, Ashutosh Trivedi

Publication date 5 August 2020

Published in Tools and Algorithms for the Construction and Analysis of Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.07103

zbMATH Keywords

decision treedecision tree learningexecution timeexecution traceinteger linear programming

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Abstract: 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.

Recommendations

• Formal methods and automated tool for timing-channel identification in TCB source code
• Tempus fugit: How to plug it
• scientific article; zbMATH DE number 2090700
• Transforming out timing leaks
• Robust profiling for DPA-style attacks

Cites work

• Constructing optimal binary decision trees is NP-complete
• Foundations of machine learning
• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• Mining specifications
• Tools and Algorithms for the Construction and Analysis of Systems

Describes a project that uses

Uses Software

• rapidminer
• DroidMat

This page was built for publication: Discriminating traces with time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3303919)