Hiding Information in Completeness Holes

New perspectives in code obfuscation and watermarking

Key note lecture (Slides)

Roberto Giacobazzi
Dip. di Informatica
Univsit\agrave di Verona
Strada Le Grazie a Ca' Vignal 2, 37134 Verona (Italy)


In this paper we show how abstract interpretation, and more specifically completeness, provides an adequate model for reasoning about code obfuscation and watermarking. The idea is that making a program obscure, or equivalently hiding information in it, corresponds to force an interpreter (the attacker) to become incomplete in its attempts to extract information about the program. Here abstract interpretation provides the model of the attacker (malicious host) and abstract interpretation transformers provide driving methods for understanding and designing new obfuscation and watermarking strategies: Obfuscation corresponds to make the malicious host incomplete and watermarking corresponds to hide secrets where incomplete attackers cannot extract them unless some secret key is given.

Available soon in PDF, BibTeX Entry.

Related papers:
  • A Unifying View on Abstract Domain Design (ACM Comp. Surveys 28(2), 1996)
  • Refining and compressing abstract domains (ICALP'97, LNCS 1256: 771-781, 1997)
  • Making abstract interpretations complete (ACM JACM 47(2):361-416, 2000)
  • Domain Compression for Complete Abstractions (VMCAI'03, LNCS 2575, 2003)
  • Abstract Non-Interference (ACM POPL'04, 2004)
  • Making abstract domains condensing (ACM Transactions on Computational Logic (TOCL). 6(1):33--60, 2005)
  • Semantics-based Code Obfuscation by Abstract Interpretation (ICALP05, LNCS 3580 2005)
  • Control Code Obfuscation by Abstract Interpretation (SEFM05, IEEE 2005)
  • Transforming Semantics by Abstract Interpretation (Theoretical Computer Science. 337(1-3):1-50, 2005)
  • Adjoining Declassification and Attack Models by Abstract Interpretation (ESOP05, LNCS 3444 2006)
  • Opaque Predicate Detection by Abstract Interpretation (AMAST06, LNCS 4019, 2006)
  • What you lose is what you leak: Information leakage in Declassification Policies (MFPS'07, ENCS 2007)
  • Hiding software watermarks in loop structures (SAS08, LNCS 5079 2008)
  • Transforming abstract interpretations by abstract interpretation (SAS08, LNCS 5079 2008)
  • roberto.giacobazzi@univr.it