Polymorphic Circuit Generation Using Random Boolean Logic Expansion
Polymorphic Circuit Generation Using Random Boolean Logic Expansion
复制标题
使用随机布尔逻辑扩展生成多态电路
DOI：
10.1145/3341105.3374031
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
and Andel, T.
中科院分区：
文献类型：
--
作者：
McDonald, J.;Stroud, T.;and Andel, T.
在不受信任的平台上保护应用程序可能涉及保护合法的最终用户免受恶意逆向工程师和黑客的攻击。这样的对手可以访问程序的完整执行环境，无论程序是以软件还是硬件的形式出现。在本文中，我们认为混淆算法的性质，执行迭代，逐步变换的程序到更复杂的形式，旨在增加恶意逆向工程的复杂性（时间，资源）。我们认为简单的布尔逻辑程序作为感兴趣的领域，并检查一个特定的转换技术称为迭代子电路选择和替换（ISR），这是一个实用的，语法的混淆方法。具体来说，我们专注于通过最大化算法的替换步骤的灵活性和潜在安全性来提高ISR的安全性，该算法可以用以下问题来表述：给定布尔逻辑门的选择（即，子电路），我们如何能够产生子电路的语义上等效（多态）的版本，使得潜在替换的分布表示来自所有可能替换的集合的随机、均匀分布。这个实际问题涉及到不可混淆性混淆的理论研究，其中一类电路的Transformer保证给定来自该类的任何两个语义等效电路，来自其混淆的变体的分布在计算上是不可区分的。理想情况下，多态电路，遵循一个随机的，均匀的分布提供了更强的保护，以防止恶意的分析，目标识别不同的模式作为基础的去混淆和simplification.In本文中，我们介绍了一种新的方法，多态电路替换称为随机布尔逻辑扩展（RBLE），它适用于布尔逻辑法律（减少）在反向。我们将这种方法与另一种依赖于静态电路库的多态替换方法进行比较。作为一个贡献，我们展示了每种方法的优点和缺点，从实证研究的初步结果来估计多态分布的均匀性，并提供了这样的算法可以很容易地应用于软件环境中的参数。RBLE提供了一种独特的方法来生成任意输入、输出和门大小的多态变体。我们报告的初步研究结果，研究这种方法产生的变体，从实证评估，表明RBLE有希望产生分布的独特的，均匀的电路时，大小是不受约束的，但有针对性的大小分布，该方法需要一些调整，以达到潜在的电路变体。
Securing 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.