PCP-Mark: Software Watermarking with an Undecidable Problem
Schwarzbeck D, Heineken T, Philippsen M (2026)
Publication Language: English
Publication Type: Conference contribution, Original article
Publication year: 2026
Pages Range: 1-12
Event location: Porto
Abstract
Software watermarking embeds a message into programs to assert ownership. Existing techniques are prone to subtractive attacks that aim to remove the watermark. PCP-Mark achieves computability-theoretic full subtractive resilience. It embeds the watermark into the control flow of the program as instances of the Post Correspondence Problem (PCP). An attacker cannot remove a PCP-Mark without risking corruption of the program, even with full knowledge of the watermark location and method. (Only brute force attacks may succeed). Although a PCP-Mark is a dynamic watermark that unfolds in running loops, it resides in the static data of the program so that its presence can be proven without running the watermarked program. Heuristics keep the average runtime overhead of a PCP-Mark in benchmark programs below 4% despite of its theoretical complexity. PCP-Mark is available as an LLVM-pass that automatically adds the watermark to arbitrary programs.
Authors with CRIS profile
David Schwarzbeck
Lehrstuhl für Informatik 2 (Programmiersysteme)
Tobias Heineken
Lehrstuhl für Informatik 2 (Programmiersysteme)
Michael Philippsen
Lehrstuhl für Informatik 2 (Programmiersysteme)
Related research project(s)
How to cite
APA:
Schwarzbeck, D., Heineken, T., & Philippsen, M. (2026). PCP-Mark: Software Watermarking with an Undecidable Problem. In Proceedings of the Proceedings of the 23rd International Conference on Security and Cryptography (SECRYPT 2026) (pp. 1-12). Porto, PT.
MLA:
Schwarzbeck, David, Tobias Heineken, and Michael Philippsen. "PCP-Mark: Software Watermarking with an Undecidable Problem." Proceedings of the Proceedings of the 23rd International Conference on Security and Cryptography (SECRYPT 2026), Porto 2026. 1-12.
BibTeX: Download