{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T11:03:45Z","timestamp":1777806225875,"version":"3.51.4"},"reference-count":26,"publisher":"SAGE Publications","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JCS"],"published-print":{"date-parts":[[2023,10,13]]},"abstract":"<jats:p>We present a formal model of Checked C, a dialect of C that aims to enforce spatial memory safety. Our model pays particular attention to the semantics of dynamically sized, potentially null-terminated arrays. We formalize this model in Coq, and prove that any spatial memory safety errors can be blamed on portions of the program labeled unchecked; this is a Checked C feature that supports incremental porting and backward compatibility. While our model\u2019s operational semantics uses annotated (\u201cfat\u201d) pointers to enforce spatial safety, we show that such annotations can be safely erased. Using PLT Redex we formalize an executable version of our model and a compilation procedure to an untyped C-like language, as well as use randomized testing to validate that generated code faithfully simulates the original. Finally, we develop a custom random generator for well-typed and almost-well-typed terms in our Redex model, and use it to search for inconsistencies between our model and the Clang Checked C implementation. We find these steps to be a useful way to co-develop a language (Checked C is still in development) and a core model of it.<\/jats:p>","DOI":"10.3233\/jcs-230040","type":"journal-article","created":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T11:35:08Z","timestamp":1693308908000},"page":"581-614","source":"Crossref","is-referenced-by-count":0,"title":["A formal model of Checked C1"],"prefix":"10.1177","volume":"31","author":[{"given":"Liyi","family":"Li","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiyun","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, University of Pennsylvania, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deena","family":"Postol","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas","family":"Lampropoulos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Van Horn","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Hicks","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, MD, USA"},{"name":"Amazon, VA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"issue":"3","key":"10.3233\/JCS-230040_ref1","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s10817-009-9148-3","article-title":"Mechanized semantics for the Clight subset of the C language","volume":"43","author":"Blazy","year":"2009","journal-title":"Journal of Automated Reasoning"},{"key":"10.3233\/JCS-230040_ref2","doi-asserted-by":"crossref","unstructured":"J.\u00a0Condit, M.\u00a0Harren, Z.\u00a0Anderson, D.\u00a0Gay and G.C.\u00a0Necula, Dependent types for low-level programming, in: Proceedings of European Symposium on Programming (ESOP\u201907), 2007.","DOI":"10.1007\/978-3-540-71316-6_35"},{"key":"10.3233\/JCS-230040_ref3","doi-asserted-by":"crossref","unstructured":"J.\u00a0Duan, Y.\u00a0Yang, J.\u00a0Zhou and J.\u00a0Criswell, Refactoring the FreeBSD kernel with Checked C, in: IEEE Cybersecurity Development Conference (SecDev), 2020.","DOI":"10.1109\/SecDev45635.2020.00018"},{"key":"10.3233\/JCS-230040_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/SecDev.2018.00015"},{"key":"10.3233\/JCS-230040_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103719"},{"key":"10.3233\/JCS-230040_ref6","unstructured":"M.\u00a0Felleisen, R.B.\u00a0Findler and M.\u00a0Flatt, Semantics Engineering with PLT Redex, 1st edn, The MIT Press, 2009. ISBN 0262062755."},{"key":"10.3233\/JCS-230040_ref7","doi-asserted-by":"crossref","unstructured":"D.\u00a0Grossman, G.\u00a0Morrisett, T.\u00a0Jim, M.\u00a0Hicks, Y.\u00a0Wang and J.\u00a0Cheney, Region-based memory management in cyclone, in: PLDI, 2002.","DOI":"10.1145\/512529.512563"},{"key":"10.3233\/JCS-230040_ref8","doi-asserted-by":"crossref","unstructured":"A.\u00a0Guha, C.\u00a0Saftoiu and S.\u00a0Krishnamurthi, The essence of Javascript, in: Proceedings of the 24th European Conference on Object-Oriented Programming, ECOOP\u201910, Springer-Verlag, Berlin, Heidelberg, 2010, pp.\u00a0126\u2013150. ISBN 3642141064.","DOI":"10.1007\/978-3-642-14107-2_7"},{"issue":"6","key":"10.3233\/JCS-230040_ref9","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1145\/2813885.2737979","article-title":"Defining the undefinedness of C","volume":"50","author":"Hathhorn","year":"2015","journal-title":"SIGPLAN Not."},{"key":"10.3233\/JCS-230040_ref10","unstructured":"T.\u00a0Jim, G.\u00a0Morrisett, D.\u00a0Grossman, M.\u00a0Hicks, J.\u00a0Cheney and Y.\u00a0Wang, Cyclone: A safe dialect of C, in: USENIX Annual Technical Conference, USENIX, Monterey, CA, 2002, pp.\u00a0275\u2013288."},{"issue":"6","key":"10.3233\/JCS-230040_ref11","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/2813885.2738005","article-title":"A formal C memory model supporting integer-pointer casts","volume":"50","author":"Kang","year":"2015","journal-title":"SIGPLAN Not."},{"key":"10.3233\/JCS-230040_ref12","unstructured":"L.\u00a0Lampropoulos and B.C.\u00a0Pierce, QuickChick: Property-Based Testing in Coq, Software Foundations Series, Vol.\u00a04, Electronic textbook, 2018, Version 1.0, http:\/\/www.cis.upenn.edu\/~bcpierce\/sf."},{"issue":"7","key":"10.3233\/JCS-230040_ref13","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1538788.1538814","article-title":"Formal verification of a realistic compiler","volume":"52","author":"Leroy","year":"2009","journal-title":"Communications of the ACM"},{"issue":"POPL","key":"10.3233\/JCS-230040_ref15","doi-asserted-by":"publisher","first-page":"67:1","DOI":"10.1145\/3290380","article-title":"Exploring C semantics and pointer provenance","volume":"3","author":"Memarian","year":"2019","journal-title":"Proc. ACM Program. Lang."},{"issue":"6","key":"10.3233\/JCS-230040_ref16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2980983.2908081","article-title":"Into the depths of C: Elaborating the de facto standards","volume":"51","author":"Memarian","year":"2016","journal-title":"SIGPLAN Not."},{"key":"10.3233\/JCS-230040_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542504"},{"key":"10.3233\/JCS-230040_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/1065887.1065892"},{"key":"10.3233\/JCS-230040_ref20","doi-asserted-by":"publisher","DOI":"10.1145\/1982595.1982615"},{"key":"10.3233\/JCS-230040_ref21","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.237.5"},{"key":"10.3233\/JCS-230040_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17138-4_4"},{"key":"10.3233\/JCS-230040_ref23","unstructured":"K.\u00a0Serebryany, D.\u00a0Bruening, A.\u00a0Potapenko and D.\u00a0Vyukov, AddressSanitizer: A fast address sanity checker, in: Proceedings of the 2012 USENIX Conference on Annual Technical Conference, 2012."},{"key":"10.3233\/JCS-230040_ref24","unstructured":"D.\u00a0Tarditi, Extending C with Bounds Safety and Improved Type Safety, 2021, https:\/\/github.com\/secure-sw-dev\/checkedc\/."},{"issue":"9","key":"10.3233\/JCS-230040_ref25","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/2692915.2628161","article-title":"Refinement types for Haskell","volume":"49","author":"Vazou","year":"2014","journal-title":"SIGPLAN Not."},{"key":"10.3233\/JCS-230040_ref26","unstructured":"B.\u00a0Zeng, G.\u00a0Tan and U.\u00a0Erlingsson, Strato: A retargetable framework for low-level inlined-reference monitors, in: Proceedings of the 22Nd USENIX Conference on Security, 2013."},{"issue":"1","key":"10.3233\/JCS-230040_ref27","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1145\/2103621.2103709","article-title":"Formalizing the LLVM intermediate representation for verified program transformations","volume":"47","author":"Zhao","year":"2012","journal-title":"SIGPLAN Not."},{"key":"10.3233\/JCS-230040_ref28","unstructured":"F.\u00a0Zhou, J.\u00a0Condit, Z.\u00a0Anderson, I.\u00a0Bagrak, R.\u00a0Ennals, M.\u00a0Harren, G.\u00a0Necula and E.\u00a0Brewer, SafeDrive: Safe and recoverable extensions using language-based techniques, in: 7th Symposium on Operating System Design and Implementation (OSDI\u201906), USENIX Association, Seattle, Washington, 2006."}],"container-title":["Journal of Computer Security"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JCS-230040","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:44Z","timestamp":1777495544000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/JCS-230040"}},"subtitle":[],"editor":[{"given":"Stefano","family":"Calzavara","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"David","family":"Naumann","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2023,10,13]]},"references-count":26,"journal-issue":{"issue":"5"},"URL":"https:\/\/doi.org\/10.3233\/jcs-230040","relation":{},"ISSN":["1875-8924","0926-227X"],"issn-type":[{"value":"1875-8924","type":"electronic"},{"value":"0926-227X","type":"print"}],"subject":[],"published":{"date-parts":[[2023,10,13]]}}}