{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:17:05Z","timestamp":1750220225459,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,12,9]],"date-time":"2021-12-09T00:00:00Z","timestamp":1639008000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["Sn11-12\/3"],"award-info":[{"award-number":["Sn11-12\/3"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"BMBF","award":["01BY1172"],"award-info":[{"award-number":["01BY1172"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2022,3,31]]},"abstract":"<jats:p>\n            We present efficient algorithms for\n            <jats:italic>time-sensitive<\/jats:italic>\n            control dependencies (CDs). If statement\n            <jats:italic>y<\/jats:italic>\n            is time-sensitively control dependent on statement\n            <jats:italic>x<\/jats:italic>\n            , then\n            <jats:italic>x<\/jats:italic>\n            decides not only whether\n            <jats:italic>y<\/jats:italic>\n            is executed but also how many timesteps after\n            <jats:italic>x<\/jats:italic>\n            . If\n            <jats:italic>y<\/jats:italic>\n            is not standard control dependent on\n            <jats:italic>x<\/jats:italic>\n            , but time-sensitively control dependent, then\n            <jats:italic>y<\/jats:italic>\n            will always be executed after\n            <jats:italic>x<\/jats:italic>\n            , but the execution time between\n            <jats:italic>x<\/jats:italic>\n            and\n            <jats:italic>y<\/jats:italic>\n            varies. This allows us to discover, e.g., timing leaks in security-critical software.\n          <\/jats:p>\n          <jats:p>\n            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\u2019s efficient algorithm for dominance frontiers [\n            <jats:xref ref-type=\"bibr\">10<\/jats:xref>\n            ] 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.\n          <\/jats:p>","DOI":"10.1145\/3486003","type":"journal-article","created":{"date-parts":[[2021,12,9]],"date-time":"2021-12-09T16:36:47Z","timestamp":1639067807000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On Time-sensitive Control Dependencies"],"prefix":"10.1145","volume":"44","author":[{"given":"Martin","family":"Hecker","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon","family":"Bischof","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregor","family":"Snelting","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,12,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/325694.325702"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201008"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.10.002"},{"key":"e_1_3_2_5_2","volume-title":"Cache-Timing Attacks on AES","author":"Bernstein Daniel J.","year":"2005","unstructured":"Daniel J. Bernstein. 2005. Cache-Timing Attacks on AES. Technical Report."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2006.95"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.3233\/JCS-17984"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49635-0_4"},{"key":"e_1_3_2_9_2","unstructured":"Keith D. Cooper Timothy J. Harvey and Ken Kennedy. 2001. A Simple Fast Dominance Algorithm . Technical Report. Rice University."},{"key":"e_1_3_2_10_2","volume-title":"Code Tools: jmh","author":"Corporation Oracle","year":"2020","unstructured":"Oracle Corporation. 2020. Code Tools: jmh. Retrieved from https:\/\/github.com\/AlDanial\/cloc."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/24039.24041"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-014-0257-6"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49635-0_5"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-009-0086-1"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512946"},{"key":"e_1_3_2_17_2","volume-title":"Timing Sensitive Dependency Analysis and its Application to Software Security","author":"Hecker Martin","year":"2020","unstructured":"Martin Hecker. 2020. Timing Sensitive Dependency Analysis and its Application to Software Security. Ph.D. Dissertation. Karlsruher Institut f\u00fcr Technologie, Fakult\u00e4t f\u00fcr Informatik."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.02.031"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/73560.73573"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/77606.77608"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.5555\/153676"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2011.19"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","unstructured":"Paul Kocher Daniel Genkin Daniel Gruss Werner Haas Mike Hamburg Moritz Lipp Stefan Mangard Thomas Prescher Michael Schwarz and Yuval Yarom. 2018. Spectre attacks: Exploiting speculative execution. arxiv:1801.01203. Retrieved from http:\/\/arxiv.org\/abs\/1801.01203.","DOI":"10.1109\/SP.2019.00002"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/940071.940096"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/357062.357071"},{"key":"e_1_3_2_26_2","volume-title":"Advanced Compiler Design and Implementation","author":"Muchnik Steven","year":"1997","unstructured":"Steven Muchnik. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann."},{"key":"e_1_3_2_27_2","article-title":"JGraphT: A Java Library of Graph Theory Data Structures and Algorithms","author":"Naveh Barak","unstructured":"Barak Naveh and Stephane Popinet. 2003\u20132019. JGraphT: A Java Library of Graph Theory Data Structures and Algorithms. Retrieved from https:\/\/jgrapht.org\/.","journal-title":"https:\/\/jgrapht.org\/"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.58784"},{"key":"e_1_3_2_29_2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-662-54455-6_1","volume-title":"Principles of Security and Trust,","author":"Rafnsson Willard","year":"2017","unstructured":"Willard Rafnsson, Limin Jia, and Lujo Bauer. 2017. Timing-sensitive noninterference through composition. In Principles of Security and Trust,Lecture Notes in Computer Science, Matteo Maffei and Mark Ryan (Eds.), Vol. 10204. Springer, 3\u201325."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1275497.1275502"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/193173.195287"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/794200.795151"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/572937"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486003","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3486003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:08Z","timestamp":1750188608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,9]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,3,31]]}},"alternative-id":["10.1145\/3486003"],"URL":"https:\/\/doi.org\/10.1145\/3486003","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2021,12,9]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}