In recent years, mobile apps have become the infrastructure of many popular Internet services. It is now fairly common that a mobile app serves a large number of users across the globe. Different from web- based services whose important program logic is mostly placed on remote servers, many mobile apps require complicated client-side code to perform tasks that are critical to the businesses. The code of mobile apps can be easily accessed by any party after the software is installed on a rooted or jailbroken device. By examining the code, skilled reverse engineers can learn various knowledge about the design and implementation of an app. Real-world cases have shown that the disclosed critical information allows malicious parties to abuse or exploit the app-provided services for unrightful profits, leading to significant financial losses for app vendors.
One of the most viable mitigations against malicious reverse engineering is to obfuscate the software before release. Despite that security by obscurity is typically considered to be an unsound protection methodology, software obfuscation can indeed increase the cost of reverse engineering, thus delivering practical merits for protecting mobile apps.
In this paper, we share our experience of applying obfuscation to multiple commercial iOS apps, each of which has millions of users. We discuss the necessity of adopting obfuscation for protecting modern mobile business, the challenges of software obfuscation on the iOS platform, and our efforts in overcoming these obstacles. Our report can benefit many stakeholders in the iOS ecosystem, including developers, security service providers, and Apple as the administrator of the ecosystem.
more »
« less
Polymorphic Circuit Generation Using Random Boolean Logic Expansion
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.
more »
« less
- Award ID(s):
- 1811578
- NSF-PAR ID:
- 10173571
- Date Published:
- Journal Name:
- 35th ACM/SIGAPP Symposium On Applied Computing
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
As the underground market of malware flourishes, there is an exponential increase in the number and diversity of malware. A crucial question in malware analysis research is how to define malware specifications or signatures that faithfully describe similar malicious intent and also clearly stand out from other programs. Although the traditional malware specifications based on syntactic signatures are efficient, they can be easily defeated by various obfuscation techniques. Since the malicious behavior is often stable across similar malware instances, behavior-based specifications which capture real malicious characteristics during run time, have become more prevalent in anti-malware tasks, such as malware detection and malware clustering. This kind of specification is typically extracted from the system call dependence graph that a malware sample invokes. In this paper, we present replacement attacks to cam- ouflage similar behaviors by poisoning behavior-based specifications. The key method of our attacks is to replace a system call dependence graph to its semantically equivalent variants so that the similar malware samples within one family turn out to be different. As a result, malware analysts have to put more efforts into reexamining the similar samples which may have been investigated before. We distil general attacking strategies by mining more than 5, 200 malware samples’ behavior specifications and implement a compiler-level prototype to automate replacement attacks. Experiments on 960 real malware samples demonstrate the effectiveness of our approach to impede various behavior-based mal- ware analysis tasks, such as similarity comparison and malware clustering. In the end, we also discuss possible countermeasures in order to strengthen existing mal- ware defense.more » « less
-
more » « less
Summary In recent years, mobile apps have become the infrastructure of many popular Internet services. It is now common that a mobile app serves millions of users across the globe. By examining the code of these apps, reverse engineers can learn various knowledge about the design and implementation of the apps. Real‐world cases have shown that the disclosed critical information allows malicious parties to abuse or exploit the app‐provided services for unrightful profits, leading to significant financial losses. One of the most viable mitigations against malicious reverse engineering is to obfuscate the apps. Despite that security by obscurity is typically considered to be an unsound protection methodology, software obfuscation can indeed increase the cost of reverse engineering, thus delivering practical merits for protecting mobile apps. In this paper, we share our experience of applying obfuscation to multiple commercial iOS apps, each of which has millions of users. We discuss the necessity of adopting obfuscation for protecting modern mobile business, the challenges of software obfuscation on the iOS platform, and our efforts in overcoming these obstacles. We especially focus on factors that are unique to mobile software development that may affect the design and deployment of obfuscation techniques. We report the outcome of our obfuscation with empirical experiments. We additionally elaborate on the follow‐up case studies about how our obfuscation affected the app publication process and how we responded to the negative impacts. This experience report can benefit mobile developers, security service providers, and Apple as the administrator of the iOS ecosystem.
-
Raz, Ran (Ed.)We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem.more » « less
-
null (Ed.)With many fabless companies outsourcing integrated circuit (IC) fabrication, the extent of design information recoverable by any third-party foundry remains clouded. While traditional reverse engineering schemes from the layout employ expensive high-resolution imaging techniques to recover design information, the extent of design information that can be recovered by the foundry remains ambiguous. To address this ambiguity, we propose ReGDS, a layout reverse engineering (RE) framework, posing as an inside-foundry attack to acquire original design intent. Our framework uses the layout, in GDSII format, and the technology library to extract the transistor-level connectivity information, and exploits unique relationship-based matching to identify logic gates and thereby, recover the original gate-level netlist. Employing circuits ranging from few hundreds to millions of transistors, we validate the scalability of our framework and demonstrate 100% recovery of the original design from the layout. To further validate the effectiveness of the framework in the presence of obfuscation schemes, we apply ReGDS to layouts of conventional XOR/MUX locked circuits and successfully recover the obfuscated netlist. By applying the Boolean SATisfiability (SAT) attack on the recovered obfuscated netlist, one can recover the entire key and, thereby, retrieve the original design intent. Thus ReGDS results in accelerated acquisition of the gate-level netlist by the attacker, in comparison to imaging-based RE schemes. Our experiments unearth the potential threat of possible intellectual property (IP) piracy at any third-party foundry.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3341105.3374031
