%AMcDonald, J.%AStroud, T.%Aand Andel, T.%D2020%I
%K
%MOSTI ID: 10173571
%PMedium: X
%TPolymorphic Circuit Generation Using Random Boolean Logic Expansion
%XSecuring applications on untrusted platforms can involve protection
against legitimate end-users 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 paper, we consider
the nature of obfuscating algorithms that perform iterative,
step-wise 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 sub-circuit 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
sub-circuit), how can we produce a semantically equivalent (polymorphic)
version of the sub-circuit 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.
In this paper, 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 some adjustment
in order to reach potential circuit variants.
Country unknown/Code not availablehttps://doi.org/10.1145/3341105.3374031OSTI-MSA