https://dl.acm.org/doi/10.1145/3591264 skip to main content * ACM Digital Library home * ACM Association for Computing Machinery corporate logo * Advanced Search * Browse * About * + Sign in + Register * * Advanced Search * Journals * Magazines * Proceedings * Books * SIGs * Conferences * People * * More * Search ACM Digital Library[ ] SearchSearch Advanced Search Proceedings of the ACM on Programming Languages * Journal Home * Just Accepted * Latest Issue * * Archive * Authors + Author Guidelines + Calls for Papers + PACMPL Policies + ACM Author Policies + Author List * Editors + Editorial Board + Associate Editors Welcome Video * Reviewers * Open Access + PACMPL Open Access + ACM Open Access * Award Winners * About + About PACMPL + Announcements + Abstracting/Indexing + PACMPL Affiliations * Contact Us * More * Home * ACM Journals * Proceedings of the ACM on Programming Languages * Vol. 7, No. PLDI * Interval Parsing Grammars for File Format Parsing research-article Open access [icon-small][icon-small] Share on * * * * * * Interval Parsing Grammars for File Format Parsing Authors: [default-pr]Jialun Zhang, [contrib-81]Greg Morrisett, [default-pr]Gang TanAuthors Info & Claims Proceedings of the ACM on Programming Languages, Volume 7, Issue PLDI Article No.: 150, Pages 1073 - 1095 https://doi.org/10.1145/3591264 Published: 06 June 2023 Publication History Related Artifact: Reproduction Package for Article "Interval Parsing Grammars for File Format Parsing" June 2023 software https://doi.org/ 10.5281/zenodo.7811236 1citation11,482Downloads Metrics Total Citations1 Total Downloads11,482 Last 12 Months11,405 Last 6 weeks573 Get Citation Alerts New Citation Alert added! This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited. To manage your alert preferences, click on the button below. Manage my Alerts New Citation Alert! Please log in to your account PDFeReader * Contents Proceedings of the ACM on Programming Languages Volume 7, Issue PLDI PREVIOUS ARTICLE Automated Expected Value Analysis of Recursive Programs Previous NEXT ARTICLE Iris-Wasm: Robust and Modular Verification of WebAssembly Programs Next + Abstract + Supplementary Material + References ACM Digital Library * + Information & Contributors + Bibliometrics & Citations + View Options + References + Media + Tables + Share Abstract 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. Supplementary Material Auxiliary Archive (pldi23main-p263-p-archive.zip) The appendix. * Download * 829.13 KB References [1] 2008. Document managementPortable Document 493 FormatPart 1: PDF 1.7. Google Scholar [2] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA. Digital Library Google Scholar [3] Godmar Back. 2002. Datascript - A specification and scripting language for binary data. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2487, Springer Verlag, 66-77. isbn:3540442847 issn:16113349 https://doi.org/10.1007/3-540-45821-2_4 Crossref Google Scholar [4] 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-628. Google Scholar [5] Leonardo De Moura and Nikolaj Bjorner. 2008. Z3: An efficient SMT solver. In International conference on Tools and Algorithms for the Construction and Analysis of Systems. 337-340. Crossref Google Scholar [6] 1995. Executable and Linking Format (ELF) Specification. Version 1.2. Google Scholar [7] 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-304. Digital Library Google Scholar [8] 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-15. Digital Library Google Scholar [9] 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-122. isbn:158113729X issn:07308566 Digital Library Google Scholar [10] Bryan Ford. 2004. Parsing Expression Grammars: A Recognition-based Syntactic Foundation. In ACM Symposium on Principles of Programming Languages (POPL). 111-122. Digital Library Google Scholar [11] Alexei Hmelnov Hmelnov and Andrei Mikhailov. 2019. Generation of Code for Reading Data from the Declarative File Format Specifications Written in Language FlexT. Proceedings - 2018 Ivannikov Isp Ras Open Conference, ISPRAS 2018, 23-30. isbn:9781728112756 https://doi.org/ 10.1109/ISPRAS.2018.00011 Crossref Google Scholar [12] Suman Jana and Vitaly Shmatikov. 2012. Abusing file processing in malware detectors for fun and profit. In 2012 IEEE Symposium on Security and Privacy. 80-94. Digital Library Google Scholar [13] Trevor Jim, Yitzhak Mandelbaum, and David Walker. 2010. Semantics and Algorithms for Data-dependent Grammars. 417-430. Google Scholar [14] Donald B. Johnson. 1975. Finding All the Elementary Circuits of a Directed Graph. SIAM J. Comput., 4, 1 (1975), 77-84. Digital Library Google Scholar [15] 2015. Kaitai Struct User Guide. https://doc.kaitai.io/user_guide.html Google Scholar [16] Donald E. Knuth. 1968. Semantics of context-free languages. Mathematical Systems Theory, 2, 2 (1968), 127-145. Crossref Google Scholar [17] Ashish Kumar, Bill Harris, and Gang Tan. 2023. DISV: Domain Independent Semantic Validation of Data Files. In 9th Workshop on Language-Theoretic Security (LangSec). Google Scholar [18] 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-133. Google Scholar [19] 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-307. Google Scholar [20] 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-598. Digital Library Google Scholar [21] Tahina Ramananandro, Antoine Delignat-Lavaud, Cedric 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-1482. Google Scholar [22] William Underwood. 2012. Grammar-Based Specification and Parsing of Binary File Formats. International Journal of Digital Curation, 7, 1 (2012), 95-106. issn:1746-8256 https://doi.org/10.2218/ijdc.v7i1.217 Crossref Google Scholar [23] W3C. 2018. Scalable Vector Graphics (SVG) 2. https://www.w3.org/TR/ SVG2/ Google Scholar [24] Jialun Zhang, Greg Morrisett, and Gang Tan. 2023. Interval Parsing Grammars for File Format Parsing. arxiv:2304.04859. Google Scholar [25] Jialun Zhang, Greg Morrisett, and Gang Tan. 2023. Reproduction Package for article "Interval Parsing Grammars for File Format Parsing". https://doi.org/10.5281/zenodo.7811236 Digital Library Google Scholar Cited By View all * Tullsen MCowger SDodds MWyatta P(2024)Research Report: An Optim (l) Approach to Parsing Random-Access Formats2024 IEEE Security and Privacy Workshops (SPW)10.1109/SPW63631.2024.00023(192-199) Online publication date: 23-May-2024 https://doi.org/10.1109/SPW63631.2024.00023 Index Terms 1. Interval Parsing Grammars for File Format Parsing 1. Software and its engineering 1. Software notations and tools 1. Compilers 1. Parsers 2. Context specific languages Recommendations * Parsing expression grammars: a recognition-based syntactic foundation POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ... Read More * Parsing expression grammars: a recognition-based syntactic foundation POPL '04 For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ... Read More * Left recursion in Parsing Expression Grammars Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG ... Read More Comments Please enable JavaScript to view thecomments powered by Disqus. Information & Contributors Information Published In cover image Proceedings of the ACM on Programming Languages Proceedings of the ACM on Programming Languages Volume 7, Issue PLDI June 2023 2020 pages EISSN:2475-1421 DOI:10.1145/3554310 * Editor: * Author PictureMichael Hicks Amazon, USA Issue's Table of Contents Copyright (c) 2023 Owner/Author. This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Publisher Association for Computing Machinery New York, NY, United States Publication History Published: 06 June 2023 Published in PACMPL Volume 7, Issue PLDI Permissions Request permissions for this article. Request Permissions Check for updates Badges * [icon-large]Artifacts Available / v1.1 * [icon-large]Artifacts Evaluated & Reusable / v1.1 Author Tags 1. Context-sensitive Grammars 2. File Formats Qualifiers * Research-article Funding Sources * DARPA * NSF (National Science Foundation) Contributors [loader-7e6] Other Metrics View Article Metrics Bibliometrics & Citations Bibliometrics Article Metrics * 1 Total Citations View Citations * 11,482 Total Downloads * Downloads (Last 12 months)11,405 * Downloads (Last 6 weeks)573 Reflects downloads up to 05 Aug 2024 Other Metrics View Author Metrics Citations Cited By View all * Tullsen MCowger SDodds MWyatta P(2024)Research Report: An Optim (l) Approach to Parsing Random-Access Formats2024 IEEE Security and Privacy Workshops (SPW)10.1109/SPW63631.2024.00023(192-199) Online publication date: 23-May-2024 https://doi.org/10.1109/SPW63631.2024.00023 View Options View options PDF View or Download as a PDF file. PDF eReader View online with eReader. eReader Get Access Login options Check if you have access through your login credentials or your institution to get full access on this article. Sign in Full Access Get this Article Media Figures Other Tables Share Share Share this Publication link Copy Link Copied! Copying failed. Share on social media XLinkedInRedditFacebookemail Affiliations [default-pr] Jialun Zhang Pennsylvania State University, USA https://orcid.org/0009-0008-8254-5077 View Profile [contrib-81] Greg Morrisett Cornell University, USA https://orcid.org/0000-0002-2619-5614 View Profile [default-pr] Gang Tan Pennsylvania State University, USA https://orcid.org/0000-0001-6109-6091 View Profile Download PDF Go to Go to Show all references Request permissionsExpand All Collapse Expand Table Authors Info & Affiliations View Issue's Table of Contents Export Citations Select Citation format[BibTeX ] * Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download,a status dialog will open to start the export process. The process may takea few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download + Download citation + Copy citation Footer Categories * Journals * Magazines * Books * Proceedings * SIGs * Conferences * Collections * People About * About ACM Digital Library * ACM Digital Library Board * Subscription Information * Author Guidelines * Using ACM Digital Library * All Holdings within the ACM Digital Library * ACM Computing Classification System * Accessibility Statement Join * Join ACM * Join SIGs * Subscribe to Publications * Institutions and Libraries Connect * Contact us via email * ACM on Facebook * ACM DL on X * ACM on Linkedin * Send Feedback * Submit a Bug Report The ACM Digital Library is published by the Association for Computing Machinery. Copyright (c) 2024 ACM, Inc. * Terms of Usage * Privacy Policy * Code of Ethics ACM Digital Library home ACM Association for Computing Machinery corporate logo Your Search Results Download Request We are preparing your search results for download ... We will inform you here when the file is ready. Download now! Your Search Results Download Request Your file of search results citations is now ready. Download now! Your Search Results Download Request Your search export query has expired. Please try again.