Honors Theses

Date of Award

2021

Document Type

Undergraduate Thesis

Degree Name

BS

Department

Computer Science

Faculty Mentor

J. Todd McDonald

Abstract

Securing applications on untrusted platforms can involve protection against legitimate endusers who act in the role of malicious reverse engineers and hackers. Such adversaries have access to the full execution environment of programs, whether the program comes in the form of software or hardware. In this thesis, we consider the nature of obfuscating algorithms that perform iterative, stepwise transformation of programs into more complex forms that are intended to increase the complexity (time, resources) for malicious reverse engineers.

We consider simple Boolean logic programs as the domain of interest and examine a specific transformation technique known as Iterative Selection and Replacement (ISR), which represents a practical, syntactic approach for obfuscation. Specifically, we focus on improving the security of ISR by maximizing the flexibility and potential security of the replacement step of the algorithm which can be formulated in the following question: Given a selection of Boolean logic gates (i.e., a subcircuit), how can we produce a semantically equivalent (polymorphic) version of the subcircuit such that the distribution of potential replacements represents a random, uniform distribution from the set of all possible replacements?

This practical question is related to the theoretic study of indistinguishability obfuscation, where a transformer for a class of circuits guarantees that given any two semantically equivalent circuits from the class, the distribution of variants from their obfuscation are computationally indistinguishable. Ideally, polymorphic circuits that follow a random, uniform distribution provide stronger protection against malicious analyzers that target identification of distinct patterns as a basis for deobfuscation and simplification.

We introduce a novel approach for polymorphic circuit replacement called Random Boolean Logic Expansion (RBLE), which applies Boolean logic laws (of reduction) in reverse. We compare this approach against another proposed method of polymorphic replacement that relies on static circuit libraries. As a contribution, we show the strengths and weaknesses of each approach, examine initial results from empirical studies to estimate the uniformity of polymorphic distributions, and provide the argument for how such algorithms can be readily applied in software contexts. RBLE provides a unique method to generate polymorphic variants of arbitrary input, output, and gate size. We report initial findings for studying variants produced by this method and, from empirical evaluation, show that RBLE has promise for generating distributions of unique, uniform circuits when size is unconstrained, but for targeted size distributions, the approach requires adjustment for reaching potential circuit variant.

Download

Share

COinS