{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:41Z","timestamp":1750308581922,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000005","name":"Department of Defense","doi-asserted-by":"crossref","award":["FA8702-15-D-0002"],"award-info":[{"award-number":["FA8702-15-D-0002"]}],"id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","award":["DM17-0093"],"award-info":[{"award-number":["DM17-0093"]}],"id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>\n            A timing enforcer is a scheduler that not only allocates CPU cycles to threads, but also uses timers to enforce time budgets. An approach for verifying safety properties of timing enforcers at the source code level is presented. We assume that the enforcer is implemented as a set of \u201cenforcer\u201d functions that are executed atomically on critical system-level events, such as the arrival and departure of jobs, and triggering of timers. The key idea is to express the safety property as an invariant, and prove that it is inductive across all the enforcer functions. A formal semantics of timing enforcers is presented, including the semantics of functions used to read the system clock and set timers. Using this semantics, the verification approach is presented, and its soundness proved. Further, the approach also takes into consideration the periodicity of tasks. It is validated by proving the correctness of the enforcement of CPU cycle budgets for tasks by the Zero-Slack Rate Monotonic (\n            <jats:sc>zsrm<\/jats:sc>\n            ) scheduler, which is implemented in C as a Linux kernel module. The inductiveness of the necessary\n            <jats:sc>zsrm<\/jats:sc>\n            invariants is proved by expressing them as function contracts using the\n            <jats:sc>acsl<\/jats:sc>\n            specification language, and verifying the contracts using the\n            <jats:sc>frama-c<\/jats:sc>\n            tool.\n          <\/jats:p>","DOI":"10.1145\/3126517","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T12:33:53Z","timestamp":1506515633000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Formal Verification of a Timing Enforcer Implementation"],"prefix":"10.1145","volume":"16","author":[{"given":"Sagar","family":"Chaki","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, SEI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dionisio De","family":"Niz","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, SEI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/186025.186058"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.018"},{"key":"e_1_2_1_3_1","unstructured":"ACSL website. {n.d.}. ({n.d.}). http:\/\/frama-c.com\/acsl.html.  ACSL website. {n.d.}. ({n.d.}). http:\/\/frama-c.com\/acsl.html."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2011.38"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2016.18"},{"volume-title":"Davis","year":"2015","author":"Burns Alan","key":"e_1_2_1_6_1"},{"volume-title":"Proc. of HILT.","year":"2016","author":"Chaki Sagar","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03359-9_2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1792734.1792766"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.46"},{"volume-title":"Proceedings of the 20th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS\u201914)","author":"de Niz Dionisio","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","unstructured":"Frama-C website. {n.d.}. ({n.d.}). http:\/\/frama-c.com.  Frama-C website. {n.d.}. ({n.d.}). http:\/\/frama-c.com."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2012.24"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592434.1592438"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629596"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.14"},{"volume-title":"Proceedings of the 8th Real-Time Systems Symposium (RTSS\u201987)","author":"Lehoczky John P.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/MMCS.1994.292439"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/520050.828443"},{"volume-title":"Time and Petri Nets","author":"Popova-Zeugmann Louchka","key":"e_1_2_1_20_1"},{"volume-title":"ARINC specification 653 based real-time software engineering. e-Informatica 5, 1","year":"2011","author":"Samolej Slawomir","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2016.7461326"},{"volume-title":"Proceedings of the 7th Real-Time Systems Symposium (RTSS\u201986)","year":"1986","author":"Sha Lui","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02341920"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.368008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46681-0_53"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.35"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126517","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126517","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126517","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:01Z","timestamp":1750273501000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126517"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":27,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3126517"],"URL":"https:\/\/doi.org\/10.1145\/3126517","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2017,9,27]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}