KIT | KIT-Bibliothek | Impressum | Datenschutz

On Time-sensitive Control Dependencies

Hecker, Martin; Bischof, Simon; Snelting, Gregor

Abstract:

We present efficient algorithms for time-sensitive control dependencies (CDs). If statement y is time-sensitively control dependent on statement x, then x decides not only whether y is executed but also how many timesteps after x. If y is not standard control dependent on x, but time-sensitively control dependent, then y will always be executed after x, but the execution time between x and y varies. This allows us to discover, e.g., timing leaks in security-critical software.

We systematically develop properties and algorithms for time-sensitive CDs, as well as for nontermination-sensitive CDs. These work not only for standard control flow graphs (CFGs) but also for CFGs lacking a unique exit node (e.g., reactive systems). We show that Cytron’s efficient algorithm for dominance frontiers [10] can be generalized to allow efficient computation not just of classical CDs but also of time-sensitive and nontermination-sensitive CDs. We then use time-sensitive CDs and time-sensitive slicing to discover cache timing leaks in an AES implementation. Performance measurements demonstrate scalability of the approach.


Verlagsausgabe §
DOI: 10.5445/IR/1000142656
Veröffentlicht am 24.02.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2022
Sprache Englisch
Identifikator ISSN: 0164-0925, 1558-4593
KITopen-ID: 1000142656
Erschienen in ACM Transactions on Programming Languages and Systems
Verlag Association for Computing Machinery (ACM)
Band 44
Heft 1
Seiten Art.-Nr.: 2
Schlagwörter Control dependency, program slicing, timing dependency, timing leak
Nachgewiesen in Web of Science
Dimensions
Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page