{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:25:31Z","timestamp":1767860731822,"version":"3.49.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T00:00:00Z","timestamp":1686009600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"name":"DARPA","award":["HR0011-19-C-0073"],"award-info":[{"award-number":["HR0011-19-C-0073"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["FMiTF-1918396"],"award-info":[{"award-number":["FMiTF-1918396"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,6,6]]},"abstract":"<jats:p>File formats specify how data is encoded for persistent storage. They cannot be formalized as context-free grammars since their specifications include context-sensitive patterns such as the random access pattern and the type-length-value pattern. We propose a new grammar mechanism called Interval Parsing Grammars IPGs) for file format specifications. An IPG attaches to every nonterminal\/terminal an interval, which specifies the range of input the nonterminal\/terminal consumes. By connecting intervals and attributes, the context-sensitive patterns in file formats can be well handled. In this paper, we formalize IPGs' syntax as well as its semantics, and its semantics naturally leads to a parser generator that generates a recursive-descent parser from an IPG. In general, IPGs are declarative, modular, and enable termination checking. We have used IPGs to specify a number of file formats including ZIP, ELF, GIF, PE, and part of PDF; we have also evaluated the performance of the generated parsers.<\/jats:p>","DOI":"10.1145\/3591264","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T20:06:24Z","timestamp":1686081984000},"page":"1073-1095","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Interval Parsing Grammars for File Format Parsing"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-8254-5077","authenticated-orcid":false,"given":"Jialun","family":"Zhang","sequence":"first","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-5614","authenticated-orcid":false,"given":"Greg","family":"Morrisett","sequence":"additional","affiliation":[{"name":"Cornell University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6109-6091","authenticated-orcid":false,"given":"Gang","family":"Tan","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,6]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2008. Document managementPortable Document 493 FormatPart 1: PDF 1.7. 2008. Document managementPortable Document 493 FormatPart 1: PDF 1.7."},{"key":"e_1_2_2_2_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1986","unstructured":"Alfred V. Aho , Ravi Sethi , and Jeffrey D . Ullman . 1986 . Compilers : Principles, Techniques, and Tools. Addison-Wesley , Reading, MA. Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45821-2_4"},{"key":"e_1_2_2_4_1","volume-title":"USENIX Symposium on Operating Systems Design and Implementation (OSDI). 615\u2013628","author":"Bangert Julian","year":"2014","unstructured":"Julian Bangert and Nickolai Zeldovich . 2014 . Nail: A practical tool for parsing and generating data formats . In USENIX Symposium on Operating Systems Design and Implementation (OSDI). 615\u2013628 . Julian Bangert and Nickolai Zeldovich. 2014. Nail: A practical tool for parsing and generating data formats. In USENIX Symposium on Operating Systems Design and Implementation (OSDI). 615\u2013628."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_2_6_1","unstructured":"1995. Executable and Linking Format (ELF) Specification. Version 1.2. 1995. Executable and Linking Format (ELF) Specification. Version 1.2."},{"key":"e_1_2_2_7_1","volume-title":"ACM Conference on Programming Language Design and Implementation (PLDI). ACM Press","author":"Fisher Kathleen","year":"2005","unstructured":"Kathleen Fisher and Robert Gruber . 2005 . PADS: a domain-specific language for processing ad hoc data . In ACM Conference on Programming Language Design and Implementation (PLDI). ACM Press , New York, NY, USA. 295\u2013304. Kathleen Fisher and Robert Gruber. 2005. PADS: a domain-specific language for processing ad hoc data. In ACM Conference on Programming Language Design and Implementation (PLDI). ACM Press, New York, NY, USA. 295\u2013304."},{"key":"e_1_2_2_8_1","volume-title":"ACM Symposium on Principles of Programming Languages (POPL). ACM Press","author":"Fisher Kathleen","year":"2006","unstructured":"Kathleen Fisher , Yitzhak Mandelbaum , and David Walker . 2006 . The next 700 data description languages . In ACM Symposium on Principles of Programming Languages (POPL). ACM Press , New York, NY, USA. 2\u201315. Kathleen Fisher, Yitzhak Mandelbaum, and David Walker. 2006. The next 700 data description languages. In ACM Symposium on Principles of Programming Languages (POPL). ACM Press, New York, NY, USA. 2\u201315."},{"key":"e_1_2_2_9_1","first-page":"31","volume-title":"Conference Record of the Annual ACM Symposium on Principles of Programming Languages","author":"Ford Bryan","year":"2004","unstructured":"Bryan Ford . 2004 . Parsing expression grammars: A recognition-based syntactic foundation . Conference Record of the Annual ACM Symposium on Principles of Programming Languages , 31 (2004), 111\u2013122. isbn:158113729X issn:07308566 Bryan Ford. 2004. Parsing expression grammars: A recognition-based syntactic foundation. Conference Record of the Annual ACM Symposium on Principles of Programming Languages, 31 (2004), 111\u2013122. isbn:158113729X issn:07308566"},{"key":"e_1_2_2_10_1","volume-title":"Parsing Expression Grammars: A Recognition-based Syntactic Foundation. In ACM Symposium on Principles of Programming Languages (POPL). 111\u2013122","author":"Ford Bryan","year":"2004","unstructured":"Bryan Ford . 2004 . Parsing Expression Grammars: A Recognition-based Syntactic Foundation. In ACM Symposium on Principles of Programming Languages (POPL). 111\u2013122 . Bryan Ford. 2004. Parsing Expression Grammars: A Recognition-based Syntactic Foundation. In ACM Symposium on Principles of Programming Languages (POPL). 111\u2013122."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPRAS.2018.00011"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2012.15"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Trevor Jim Yitzhak Mandelbaum and David Walker. 2010. Semantics and Algorithms for Data-dependent Grammars. 417\u2013430. Trevor Jim Yitzhak Mandelbaum and David Walker. 2010. Semantics and Algorithms for Data-dependent Grammars. 417\u2013430.","DOI":"10.1145\/1707801.1706347"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0204007"},{"key":"e_1_2_2_15_1","unstructured":"2015. Kaitai Struct User Guide. https:\/\/doc.kaitai.io\/user_guide.html 2015. Kaitai Struct User Guide. https:\/\/doc.kaitai.io\/user_guide.html"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01692511"},{"key":"e_1_2_2_17_1","volume-title":"DISV: Domain Independent Semantic Validation of Data Files. In 9th Workshop on Language-Theoretic Security (LangSec).","author":"Kumar Ashish","year":"2023","unstructured":"Ashish Kumar , Bill Harris , and Gang Tan . 2023 . DISV: Domain Independent Semantic Validation of Data Files. In 9th Workshop on Language-Theoretic Security (LangSec). Ashish Kumar, Bill Harris, and Gang Tan. 2023. DISV: Domain Independent Semantic Validation of Data Files. In 9th Workshop on Language-Theoretic Security (LangSec)."},{"key":"e_1_2_2_18_1","volume-title":"Parsing PEGs with Length Fields in Software and Hardware. In 2021 IEEE Security and Privacy Workshops (SPW). 128\u2013133","author":"Lucas Zephyr S","year":"2021","unstructured":"Zephyr S Lucas , Joanna Y Liu , Prashant Anantharaman , and Sean W Smith . 2021 . Parsing PEGs with Length Fields in Software and Hardware. In 2021 IEEE Security and Privacy Workshops (SPW). 128\u2013133 . Zephyr S Lucas, Joanna Y Liu, Prashant Anantharaman, and Sean W Smith. 2021. Parsing PEGs with Length Fields in Software and Hardware. In 2021 IEEE Security and Privacy Workshops (SPW). 128\u2013133."},{"key":"e_1_2_2_19_1","volume-title":"Research Report: The Parsley Data Format Definition Language. In 6th Workshop on Language-Theoretic Security (LangSec). 300\u2013307","author":"Mundkur Prashanth","unstructured":"Prashanth Mundkur , Linda Briesemeister , Natarajan Shankar , Prashant Anantharaman , Sameed Ali , Zephyr Lucas , and Sean W. Smith . 2020 . Research Report: The Parsley Data Format Definition Language. In 6th Workshop on Language-Theoretic Security (LangSec). 300\u2013307 . Prashanth Mundkur, Linda Briesemeister, Natarajan Shankar, Prashant Anantharaman, Sameed Ali, Zephyr Lucas, and Sean W. Smith. 2020. Research Report: The Parsley Data Format Definition Language. In 6th Workshop on Language-Theoretic Security (LangSec). 300\u2013307."},{"key":"e_1_2_2_20_1","volume-title":"ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 579\u2013598","author":"Parr Terence","year":"2014","unstructured":"Terence Parr , Sam Harwell , and Kathleen Fisher . 2014 . Adaptive LL(*) parsing: the power of dynamic analysis . In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 579\u2013598 . Terence Parr, Sam Harwell, and Kathleen Fisher. 2014. Adaptive LL(*) parsing: the power of dynamic analysis. In ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). 579\u2013598."},{"key":"e_1_2_2_21_1","volume-title":"EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats. In Usenix Security Symposium. 1465\u20131482","author":"Ramananandro Tahina","year":"2019","unstructured":"Tahina Ramananandro , Antoine Delignat-Lavaud , C\u00e9dric Fournet , Nikhil Swamy , Tej Chajed , Nadim Kobeissi , and Jonathan Protzenko . 2019 . EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats. In Usenix Security Symposium. 1465\u20131482 . Tahina Ramananandro, Antoine Delignat-Lavaud, C\u00e9dric Fournet, Nikhil Swamy, Tej Chajed, Nadim Kobeissi, and Jonathan Protzenko. 2019. EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats. In Usenix Security Symposium. 1465\u20131482."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.2218\/ijdc.v7i1.217"},{"key":"e_1_2_2_23_1","unstructured":"W3C. 2018. Scalable Vector Graphics (SVG) 2. https:\/\/www.w3.org\/TR\/SVG2\/ W3C. 2018. Scalable Vector Graphics (SVG) 2. https:\/\/www.w3.org\/TR\/SVG2\/"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Jialun Zhang Greg Morrisett and Gang Tan. 2023. Interval Parsing Grammars for File Format Parsing. arxiv:2304.04859. Jialun Zhang Greg Morrisett and Gang Tan. 2023. Interval Parsing Grammars for File Format Parsing. arxiv:2304.04859.","DOI":"10.1145\/3591264"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7811236"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591264","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:20Z","timestamp":1750178840000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591264"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,6]]},"references-count":25,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2023,6,6]]}},"alternative-id":["10.1145\/3591264"],"URL":"https:\/\/doi.org\/10.1145\/3591264","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,6]]},"assertion":[{"value":"2023-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}