Attention:The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, August 13 until 12:00 AM ET on Friday, August 14 due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


This content will become publicly available on May 18, 2027

Title: Coral: Fast Succinct Non-Interactive Zero-Knowledge CFG Proofs
We introduce Coral, a system for proving in zeroknowledge that a committed byte stream corresponds to a structured object in accordance to a Context Free Grammar. Once a prover establishes the validity of the parsed object with Coral, they can selectively prove facts about the object—such as fields in Web API responses or in JSON Web Tokens—–to third parties or blockchains. Coral reduces the problem of correct parsing to a few simple checks over a left-child right-sibling tree and introduces a novel segmented memory abstraction that unifies and extends prior constructions for RAM in zkSNARKs. Our implementation of Coral runs on a standard laptop, and non-interactively proves the parsing of real Web responses (JSON) and files (TOML and C) in seconds. The resulting proofs are small and cheap to verify  more » « less
Award ID(s):
2045861
PAR ID:
10664738
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
IEEE Symposium on Security and Privacy (S&P)
Date Published:
Subject(s) / Keyword(s):
Zero-knowledge proofs SNARKs, context-free grammars, parsing
Format(s):
Medium: X
Location:
San Franciso, CA
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Proceedings of the VLDB Endowment)
    null (Ed.)
    JavaScript Object Notation (JSON) and its variants have gained great popularity in recent years. Unfortunately, the performance of their analytics is often dragged down by the expensive JSON parsing. To address this, recent work has shown that building bitwise indices on JSON data, called structural indices , can greatly accelerate querying. Despite its promise, the existing structural index construction does not scale well as records become larger and more complex, due to its (inherently) sequential construction process and the involvement of costly memory copies that grow as the nesting level increases. To address the above issues, this work introduces Pison - a more memory-efficient structural index constructor with supports of intra-record parallelism. First, Pison features a redesign of the bottleneck step in the existing solution. The new design is not only simpler but more memory-efficient. More importantly, Pison is able to build structural indices for a single bulky record in parallel, enabled by a group of customized parallelization techniques. Finally, Pison is also optimized for better data locality, which is especially critical in the scenario of bulky record processing. Our evaluation using real-world JSON datasets shows that Pison achieves 9.8X speedup (on average) over the existing structural index construction solution for bulky records and 4.6X speedup (on average) of end-to-end performance (indexing plus querying) over a state-of-the-art SIMD-based JSON parser on a 16-core machine. 
    more » « less
  2. ; ; ; ; ; (, Proceedings of the Annual Computer Security Applications Conference (ACSAC), 2025)
    Web Application Firewalls (WAFs) have been in- troduced as essential and popular security gates that inspect incoming HTTP traffic to filter out malicious requests and provide defenses against a diverse array of web-based threats. Evading WAFs can compromise these defenses, potentially harming Internet users. In recent years, parsing discrepan- cies have plagued many entities in the communication path; however, their potential impact on WAF evasion and re- quest smuggling remains largely unexplored. In this work, we present an innovative approach to bypassing WAFs by uncovering and exploiting parsing discrepancies through ad- vanced fuzzing techniques. By targeting non-malicious com- ponents such as headers and segments of the body and us- ing widely used content-types such as application/json, multipart/form-data, and application/xml, we iden- tified and confirmed 1207 bypasses across 5 well-known WAFs, AWS, Azure, Cloud Armor, Cloudflare, and Mod- Security. To validate our findings, we conducted a study in the wild, revealing that more than 90% of websites ac- cepted both application/x-www-form-urlencoded and multipart/form-data interchangeably, highlighting a sig- nificant vulnerability and the broad applicability of our bypass techniques. We have reported these vulnerabilities to the af- fected parties and received acknowledgments from all, as well as bug bounty rewards from some vendors. Further, to mitigate these vulnerabilities, we introduce HTTP-Normalizer, a ro- bust proxy tool designed to rigorously validate HTTP requests against current RFC standards. Our results demonstrate its effectiveness in normalizing or blocking all bypass attempts presented in this work. 
    more » « less
  3. ; ; (, Proceedings of the ACM on Management of Data)
    The popularity of JSON as a data interchange format resulted in big amounts of datasets available for processing. Users would like to analyze this data using SQL queries but existing distributed systems limit their users to only two specific formats, JSONLine and GeoJSON. The complexity of JSON schema makes it challenging to parse arbitrary files in a modern distributed system while producing records with unified schema that can be processed with SQL. To address these challenges, this paper introduces dsJSON, a state-of-the-art distributed JSON processor that overcomes limitations in existing systems and scales to big and complex data. dsJSON introduces the projection tree, a novel data structure that applies selective parsing of nested attributes to produce records that are ready for SQL processors. The key objective of the projection tree is to parse a big JSON file in parallel to produce records with a unified schema that can be processed with SQL. dsJSON is integrated into SparkSQL which enables users to run arbitrary SQL queries on complex JSON files. It also pushes projection and filter down into the parser for full integration between the parser and the processor. Experiments on up-to two terabytes of real data show that dsJSON performs several times faster than existing systems. It can also efficiently parse extremely large files not supported by existing distributed parsers 
    more » « less
  4. ; (, Glycobiology)
    Abstract Standalone AlphaFold 3 (AF3) models proteins, post-translational modifications, and ligands (including glycans) from a single JSON input file. Plausible glycan stereochemistry is more consistently achieved when monosaccharides are specified as Chemical Component Dictionary (CCD) entries and connected using bondedAtomPairs (BAP) syntax. Although this approach preserves glycan stereochemistry, assembling JSON input files manually is challenging due to the diversity of monosaccharides, linkages, branching, and structural complexity. To simplify this process, we developed JAAG (JSON input file Assembler for AlphaFold 3 with Glycan integration (https://biofgreat.org/JAAG and https://github.com/chinchc/JAAG), a web-based graphical interface that streamlines AF3 JSON file creation, reduces errors, and facilitates modeling of glycans and glycan-macromolecule interactions. 
    more » « less
  5. ; ; ; ; ; ; ; (, 2024 IEEE 40th International Conference on Data Engineering (ICDE))
    SQL is five decades old and has outlasted many programming and query languages that have come and gone during its lifetime. It was born shortly after the introduction of the relational model, and was designed for querying a flat and typed tabular world. Support for modern, flexible data in the SQL standard and in relational database systems has largely been approached via the addition of new column types (e.g. XML or JSON) together with functions to operate on them. It is time for a cleaner solution that retains the benefits that have allowed SQL to be so successful for so long. We describe SQL++, a SQL extension that relaxes SQL's strictness in terms of both object structure (flat → nested) and schema (mandatory → optional), along with a multi-party effort to agree on a core definition and syntax supportable by multiple vendors. SQL++ sees relational data as a subset of a more flexible object model and it sees collections of document data (e.g., JSON) as a natural and supportable relaxation as opposed to a “bolt on” addition via a SQL column type. We describe the core features of SQL++ and explain how its definition can accommodate flexible data, while staying true to SQL in situations where the target data is tabular and strongly typed. Index Terms-semistructured data, query, JSON, SQL, NoSQL 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Text Encoded Conversion
  • XML
  • Save / Share this Record
  • Send to Email