Date of Award

3-2008

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Department of Electrical and Computer Engineering

First Advisor

J. Todd McDonald, PhD

Abstract

Software protection remains an active research area with the goal of preventing adversarial software exploitation such as reverse engineering, tampering, and piracy. Heuristic obfuscation techniques lack strong theoretical underpinnings while current theoretical research highlights the impossibility of creating general, efficient, and information theoretically secure obfuscators. In this research, we consider a bridge between these two worlds by examining obfuscators based on the Random Program Model (RPM). Such a model envisions the use of program encryption techniques which change the black-box (semantic) and white-box (structural) representations of underlying programs. In this thesis we explore the possibilities for white-box transformation. Under an RPM formulation, if an adversary cannot distinguish an original program from either its obfuscated version (whose black-box behavior has been strategically altered) or a randomly generated program of comparable size, then the white-box intent of the original program has been sufficiently protected. One proposed method of creating such random indistinguishability is by choosing (at random) a program from a size-bounded set of all semantically equivalent possibilities. Since full enumeration of reasonably sized programs is not possible, in this work we focus on obfuscators which introduce random white-box structural variation based on iterative selection and replacement. We design and develop an obfuscation framework for programmatic logic expressed as combinatorial Boolean circuits and compare six unique approaches for sub-circuit selection. We analyze the relative behavior of random and guided-random sub-circuit selection algorithms while showing their utility in producing random white-box structural variation.

AFIT Designator

AFIT-GCS-ENG-08-17

DTIC Accession Number

ADA486799

Download

Share

COinS