Xmark: Dynamic Software Watermarking Using Collatz Conjecture

Haoyu Ma, Chunfu Jia, Shijia Li, Wantong Zheng, Dinghao Wu

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


Dynamic software watermarking is one of the major countermeasures against software licensing violations. However, conventional dynamic watermarking approaches have exhibited a number of weaknesses including exploitable payload semantics, exploitable embedding/recognition procedures, and weak correlation between payload and subject software. This paper presents a novel dynamic watermarking method, Xmark, which leverages a well-known unsolved mathematical problem referred to as the Collatz conjecture. Our method works by transforming selected conditional constructs (which originally belonged to the software to be watermarked) with a control flow obfuscation technique based on Collatz conjecture. These obfuscation routines are built in a particular way such that they are able to express a watermark in the form of iteratively executed branching activities occurred during computing the aforementioned conjecture. Exploiting the one-to-one correspondence between natural numbers and their orbits computed by the conjecture (also known as the 'Hailstone sequences'), Xmark's watermark-related activities are designed to be insignificant without the pre-defined secret input. Meanwhile, being integrated with obfuscation techniques, our method is able to resist attacks based on various reverse engineering techniques on both syntax and semantic levels. Analyses and simulations indicated that Xmark could evade detections via pattern matching and model checking, and meanwhile effectively prohibit dynamic symbolic execution. We have also shown that our method could remain robust even if a watermarked software is compromised via re-obfuscation using approaches like control flow flattening.

Original languageEnglish (US)
Article number8676372
Pages (from-to)2859-2874
Number of pages16
JournalIEEE Transactions on Information Forensics and Security
Issue number11
StatePublished - Nov 2019

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Computer Networks and Communications


Dive into the research topics of 'Xmark: Dynamic Software Watermarking Using Collatz Conjecture'. Together they form a unique fingerprint.

Cite this