Program-Structure Order Watermarking: A Semantics-Constrained Framework for Provenance Encoding and Refactoring-Aware Verification in AI-Generated Code
The increasing use of generative artificial intelligence in software development has created an urgent need for reliable mechanisms to identify the provenance of generated source code. Unlike natural-language content, program code is governed by strict syntactic, semantic, and execution constraints. Even small structural modifications may alter program behavior, invalidate dependencies, or introduce errors. Existing software watermarking research has explored code reordering, function relocation, control-flow transformations, and abstract syntax tree (AST)-based transformations. However, a fundamental challenge remains: how can an intentional, verifiable watermark encoded through program-structure ordering be distinguished from ordinary software refactoring, compiler optimization, and naturally occurring structural variation? This paper introduces Program-Structure Order Watermarking (PSOW), a theoretical framework that treats admissible ordering relationships among program components as potential carriers of provenance information. The framework considers multiple structural levels, including functions, statements, modules, declarations, basic blocks, control-flow structures, and AST nodes. Its central contribution is a provenance-directed encoding and verification model that distinguishes intentional watermark-bearing order configurations from incidental ordering changes through secret-key conditioning, payload-dependent encoding, dependency-constrained transformations, and refactoring-aware statistical verification. Unlike a system that merely observes structural differences, PSOW requires a reproducible relationship between an authorized watermark payload and a detectable program-structure configuration. It introduces a program dependency model, an admissible ordering space, a keyed structural encoder, a watermark-specific verification procedure, and a differential evaluation protocol against ordinary refactoring transformations. The framework also distinguishes source-level order, AST-level order, intermediate-representation order, and execution-level behavior, recognizing that a transformation valid at one representation may not remain meaningful at another. To the best of our knowledge, this paper presents the first dedicated theoretical formulation that places the distinction between provenance-directed program-structure order encoding and ordinary semantics-preserving refactoring at the center of a unified framework for AI-generated code watermarking. This narrowly scoped priority claim does not imply that code-reordering watermarking, function relocation, or AST-based code watermarking are new. The paper establishes theoretical definitions, research hypotheses, and an experimental methodology without claiming unperformed experiments or empirically established performance.
Authors
- Jincheng Zhang (ORCID: https://orcid.org/0009-0005-1860-0009)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24392259
- Primary Topic
- Software Engineering Research
- Type
- preprint