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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Program-Structure Order Watermarking: A Semantics-Constrained Framework for Provenance Encoding and Refactoring-Aware Verification in AI-Generated Code

Jincheng Zhang
2 links
Zenodo (CERN European Organization for Nuclear Research)
Software Engineering Research
preprint

Program-Structure Order Watermarking: A Semantics-Constrained Framework for Provenance Encoding and Refactoring-Aware Verification in AI-Generated Code

Jincheng Zhang
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Software Engineering Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon