International maritime traffic is controlled by collision-avoidance regulations (COLREGs) with 41 standardized rules describing how a vessel should navigate in the proximity of other vessels. Since some rules can be overridden by human judgement when resolving critical encounters of vessels, justifying COLREGs compliance has become a significant challenge in the increasing presence of autonomous surface vehicles (ASVs) operated without (or with only remote) human control. This paper provides a high-level framework and long-term research agenda towards the automated synthesis of test scenarios to assure COLREGs compliance for ASVs by exploiting various model-driven engineering techniques. By adapting ideas from testing self-driving cars, we envisage a multi-layered test scenario generation approach involving functional, logical and concrete scenarios. In the current paper, we demonstrate how functional scenarios of COLREGs situations between given vessels can be precisely formalized by using metamodels, domain-specific graph models and first-order logic graph constraints. By using automated model generation techniques, we derive a complete set of functional-level test scenarios, which includes all possible COLREGs situations that may arise between given vessels. As initial result, we provide several dangerous situations involving only three vessels where a potential collision may occur even when all vessels follow the COLREGs, which showcases that some COLREGs rules need further clarification for the safe regulation of ASVs.

Obfuscation is frequently used by both benign and malicious Android apps. Since static analysis of obfuscated apps often produces incomplete or misleading results, the problems of identifying and quantifying the use of specific obfuscation techniques in apps has received significant attention. Even though several existing works have addressed these problems, most studies focus on data obfuscation methods such as identifier renaming and string obfuscation, while more advanced code obfuscation methods, such as reflection and control-flow obfuscation, have received less attention. Moreover, existing approaches to detecting Android code obfuscation have significant limitations, as shown by a detailed survey that we present as part of this paper. This is in part due to a fundamental “bootstrapping” problem: since, on one hand, the landscape of Android code obfuscation is poorly known, researchers have very little guidance when designing new detection methods. On the other hand, the lack of detection methods mean that the obfuscation landscape is bound to remain largely unexplored.

Abstract Decompilers are indispensable tools in Android malware analysis and app security auditing. Numerous academic works also employ an Android decompiler as the first step in a program analysis pipeline. In such settings, decompilation is frequently regarded as a “solved” problem, in that it is simply expected that source code can be accurately recovered from an app. On the other hand, it is known that, e.g, obfuscation can negatively impact a decompiler’s effectiveness. Therefore, in order to better understand potential failure modes of, e.g., automated analysis pipelines involving decompilation, it is important to characterize the performance of decompilers on both benign and malicious apps. To this end, we have performed what is, to the best of our knowledge, the first large-scale study of Android decompilation failure rates, using three sets of apps; namely, 3,018 open-source apps, 13,601 apps crawled from Google Play, and an existing collection of 24,553 malware samples. In addition to the state-of-the-art Dalvik bytecode decompiler Jadx, we also studied the performance of three popular Java decompilers. Furthermore, this paper also presents the findings from a follow-up study on 54,945 malware apps, where we additionally performed an analysis of the reasons for decompilation failures. Our study revealed that decompilers generally have very low failure rates, and that few failures on benign apps appear to be related to obfuscation. On malware, however, obfuscation appears to be a more prominent cause of failures, although the vast majority of malicious apps could still be fully decompiled by an ensemble of decompilers.

Code obfuscation is an important topic, both in terms of defense, when trying to prevent intellectual property theft, and from the offensive point of view, when trying to break obfuscation used in malware. Several recent works have discussed techniques for preventing or delaying reverse engineering of binaries. While most works focus on methods that obscure program logic, the complimentary approach of disassembly desynchronization has received relatively little attention, despite being often used by, for example, malware authors. The technique puts another hurdle in the way of attackers by targeting the most fundamental step of the reverse-engineering process: recovering assembly code from a program binary. In the interest of furthering research into this kind of obfuscation, we present desync-cc, a tool for automatic application of disassembly desynchronization. To facilitate maximal ease-of-use, the tool is designed as a drop-in replacement for gcc, and works by intercepting and modifying intermediate assembly-code during compilation.

The emerging field of edge computing is suffering from a lack of representative data to evaluate rapidly introduced new algorithms or techniques. That is a critical issue as this complex paradigm has numerous different use cases which translate into a highly diverse set of workload types.In this work, within the context of the edge computing activity of SPEC RG Cloud, we continue working towards an edge benchmark by defining high-level workload classes as well as collecting and analyzing traces for three real-world edge applications, which, according to the existing literature, are the representatives of those classes. Moreover, we propose a practical and generic methodology for workload definition and gathering. The traces and gathering tool are provided open-source.In the analysis of the collected workloads, we detect discrepancies between the literature and the traces obtained, thus highlighting the need for a continuing effort into gathering and providing data from real applications, which can be done using the proposed trace gathering methodology. Additionally, we discuss various insights and future directions that rise to the surface through our analysis.

Code obfuscation is an important topic, both in terms of defense, when trying to prevent intellectual property theft, and from the offensive point of view, when trying to break obfuscation used by malware authors to hide their malicious intents. Consequently, several works in recent years have discussed techniques that aim to prevent or delay reverse-engineering of binaries. While most works focus on methods that obscure the program logic from potential attackers, the complimentary approach of disassembly desynchronization has received relatively little attention. This technique puts another hurdle in the way of attackers by targeting the most fundamental step of the reverse-engineering process: recovering assembly code from a program binary. The technique works by tricking a disassembler into decoding the instruction stream at an invalid offset. On CPU architectures with variable-length instructions, this often yields valid albeit meaningless assembly code, while hiding a part of the original code. In the interest of furthering research into disassembly desynchronization, both from a defensive and offensive point of view, we have created desync-cc, a tool for automatic application of disassembly-desynchronization obfuscation. The tool is designed as a drop-in replacement for gcc, and works by intercepting and modifying intermediate assembly code during compilation. By applying obfuscation after the code generation phase, our tool allows a much more granular control over where obfuscation is applied, compared to a source-code level obfuscator. In this paper, we describe the design and implementation of desync-cc, and present a preliminary evaluation of its effectiveness and efficiency on a number of real-world Linux programs.

Decompilers are indispensable tools in Android malware analysis and app security auditing. Numerous academic works also employ an Android decompiler as the first step in a program analysis pipeline. In such settings, decompilation is frequently regarded as a "solved" problem, in that it is simply expected that source code can be accurately recovered from an app. While a large proportion of methods in an app can typically be decompiled successfully, it is common that at least some methods fail to decompile. In order to better understand the practical applicability of techniques in which decompilation is used as part of an automated analysis, it is important to know the actual expected failure rate of Android decompilation. To this end, we have performed what is, to the best of our knowledge, the first large-scale study of Android decompilation failure rates. We have used three sets of apps, consisting of, respectively, 3,018 open-source apps, 13,601 apps from a recent crawl of Google Play, and a collection of 24,553 malware samples. In addition to the state-of-the-art Dalvik bytecode decompiler jadx, we used three popular Java decompilers. While jadx achieves an impressively low failure rate of only 0.02% failed methods per app on average, we found that it manages to recover source code for all methods in only 21% of the Google Play apps.We have also sought to better understand the degree to which in-the-wild obfuscation techniques can prevent decompilation. Our empirical evaluation, complemented with an indepth manual analysis of a number of apps, indicate that code obfuscation is quite rarely encountered, even in malicious apps. Moreover, decompilation failures mostly appear to be caused by technical limitations in decompilers, rather than by deliberate attempts to thwart source-code recovery by obfuscation. This is an encouraging finding, as it indicates that near-perfect Android decompilation is, at least in theory, achievable, with implementation-level improvements to decompilation tools.

Greybox fuzzing has recently emerged as a scalable and practical approach to finding security bugs in software. For example, AFL ---the current state-of-the-art greybox fuzzer --- has found hundreds of vulnerabilities in popular software since its release in 2013. The combination of lightweight coverage instrumentation and a simple evolutionary algorithm allows AFL to quickly generate inputs that exercise new code. AFL also obviates the need to manually set adhoc fuzzing ratios, which has been a major limitation of classical black-box fuzzers. Instead, AFL's first fuzzing pass exhaustively applies a set of mutations to every byte of a program input. While this approach allows for more thorough exploration of the input space, and therefore improves the chances of finding complex bugs, it also drastically slows down the fuzzing progress for "heavyweight" programs, or programs that take large inputs. This makes AFL less suitable for fuzzing input formats with large size overhead, such as various document formats. In this paper, we propose focused fuzzing as a practical trade-off between thoroughness and speed, for fuzzers that employ input mutation. We extend the notion of code coverage to individual bytes of input, and show how forward dynamic slicing can be used to efficiently determine the set of program instructions that are affected by a particular input byte. This information can then be used to restrict expensive mutations to a small subset of input bytes. We implement focused fuzzing on top of AFL, and evaluate it on four "real-life" Linux programs. Our evaluation shows that focused fuzzing noticeably improves bug discovery, compared to vanilla AFL.

Program trace alignment is the process of establishing a correspondence between dynamic instruction instances in executions of two semantically similar but syntactically different programs. In this paper we present what is, to the best of our knowledge, the first method capable of aligning realistically long execution traces of real programs. To maximize generality, our method works entirely on the machine code level, i.e. it does not require access to source code. Moreover, the method is based entirely on dynamic analysis, which avoids the many challenges associated with static analysis of binary code, and which additionally makes our approach inherently resilient to e.g. static code obfuscation. Therefore, we believe that our trace alignment method could prove to be a useful aid in many program analysis tasks, such as debugging, reverse-engineering, investigating plagiarism, and malware analysis. We empirically evaluate our method on 11 popular Linux programs, and show that it is capable of producing meaningful alignments in the presence of various code transformations such as optimization or obfuscation, and that it easily scales to traces with tens of millions of instructions.

Establishing binary correspondence is the process of finding corresponding pairs of program elements, e.g., functions or individual instructions, between two semantically equivalent (or nearly-equivalent) but syntactically different program binaries. The binary-correspondence problem has applications in many fields, e.g., plagiarism and clone detection, reverse engineering, and security, and has therefore received significant attention both in industry and academia. Most binary-correspondence methods used in practice today are based on static analysis of the control structure in binaries. Unfortunately, such methods are often highly sensitive to syntactic differences between binaries, and discrepancies in the control structure due to, for example, using different compilers or optimization levels often severely reduce their accuracy. Several recent works have therefore proposed using dynamic analysis and comparing runtime-observed results of computations to establish binary correspondence. In this paper, we study the discriminative power of runtime-values for matching instructions in binaries, and propose several ways to increase the accuracy of value-based analyses. By utilizing techniques from the field of information retrieval combined with dynamic data-flow analysis, we improve matching accuracy by up to 55% in our experiments.

Mutation-based fuzzing is a popular and widely employed black-box testing technique for finding security and robustness bugs in software. It owes much of its success to its simplicity; a well-formed seed input is mutated, e.g. through random bit-flipping, to produce test inputs. While reducing the need for human effort, and enabling security testing even of closed-source programs with undocumented input formats, the simplicity of mutation-based fuzzing comes at the cost of poor code coverage. Often millions of iterations are needed, and the results are highly dependent on configuration parameters and the choice of seed inputs. In this paper we propose a novel method for automated generation of high-coverage test cases for robustness testing. Our method is based on the observation that, even for closed-source programs with proprietary input formats, an implementation that can generate well-formed inputs to the program is typically available. By systematically mutating the program code of such generating programs, we leverage information about the input format encoded in the generating program to produce high-coverage test inputs, capable of reaching deep states in the program under test. Our method works entirely at the machine-code level, enabling use-cases similar to traditional black-box fuzzing. We have implemented the method in our tool MutaGen, and evaluated it on 7 popular Linux programs. We found that, for most programs, our method improves code coverage by one order of magnitude or more, compared to two well-known mutation-based fuzzers. We also found a total of 8 unique bugs.

Dynamic program slicing is widely recognized as a powerful aid for e.g. Program comprehension during debugging. However, its widespread use has been impeded in part by scalability issues that occur when constructing the dynamic dependence graph necessary to compute dynamic slices. A few seconds of execution time on a modern CPU can easily yield dynamic dependence graphs on the order of tens of gigabytes in size. Existing methods either produce imprecise slices, incur large time overheads during slice computation, or run out of memory for long program executions. By carefully designing our method to take advantage of locality, we are able to efficiently use secondary storage for dynamic dependence graphs, thus allowing our method to scale to long program executions. Our prototype implementation runs directly on x86 executables, eliminating problems with e.g. Binary-only libraries. We show in our experiments that graphs can be constructed for program runs with billions of executed instructions, at slowdowns ranging from 62x to 173x. Our optimized format also allows graphs to be traversed at speeds of several million dependence edges per second.

Third-party security analysis of closed-source programs has become an important part of a defense-in-depth approach to software security for many companies. In the absence of efficient tools, the analysis has generally been performed through manual reverse engineering of the machine code. As reverse engineering is an extremely time-consuming and costly task, much research has been performed to develop more powerful methods for analysis of program binaries. One such popular method is dynamic taint analysis (DTA), which is a type of runtime data-flow analysis, where certain input data is marked as tainted. By tracking the flow of tainted data, DTA can, for instance, be used to determine which computations in a program are affected by a certain part of the input. In this paper we present Input Tracer, a tool that utilizes DTA for aiding in manual program comprehension and analysis of unmodified x86 executables running in Linux. A brief overview of dynamic taint analysis is given, followed by a description of the tool and its implementation. We also demonstrate the tool's ability to provide exact information on the origin of tainted data through a detailed use case, where the tool is used to find the root cause of a memory corruption bug.