Search

Ethereum is the most widely used open-source public chain project, with smart contracts serving as the pattern for developing decentralized applications. The prevalence of attacks against smart contracts has increased in recent years due to the attached amounts of high-value cryptocurrency. Various attacks against smart contracts have caused significant financial losses, amounting to hundreds of millions of dollars. As manual auditing of smart contracts is time-consuming and costly, automatic detection of vulnerabilities is crucial. Existing work does not dig deeper into contextual information contained in the program, which suffers from the difficulty of covering paths with more complex conditions. In this paper, we propose Ethchecker, a smart contract vulnerability detection tool which combines fuzzing and symbolic execution techniques together. Particularly, we propose an analysis module to extract static information from smart contracts. Besides, the tool introduces a genetic algorithm to enlarge code coverage, while considering the contextual information of the code. The results of the experiment show that in terms of F1-score for vulnerability detection, Ethchecker outperforms sFuzz by an average of 21.89% and outperforms Mythril by an average of 12.5%. Furthermore, in the comparison experiments on a dataset consisting of 1000 long smart contract codes (comprising over 3000 instructions), the proposed algorithm can improve the code coverage by 18.56% compared to the random fuzzing algorithm. In addition, we also used Ethchecker to test against 8922 randomly crawled real-world smart contracts. The result demonstrates the stability of this tool. [ABSTRACT FROM AUTHOR]

This article introduces novel tools to automatically generate pertinent Ada values in order to produce higher quality tests for Ada subprograms. A first tool will generate valid Ada values based on a structural analysis of the types of the parameters of the subprogram under test following various customizable strategies. Those values will then be filtered in order to satisfy the specifications of the subprogram, and new coverage criteria for executable specifications will be used to assess the relevance of the generated testsuite. This first set of values will then be used as seeds both for a fuzzing process, and a symbolic execution campaign, from which values of interest will be then extracted. This integrated process will enable users to generate a high value starting test corpus, which can then be expanded upon by domain-specific tests. [ABSTRACT FROM AUTHOR]

We propose Abstract Execution, a static verification framework based on symbolic execution and dynamic frames for proving properties of schematic programs. Since a schematic program may potentially represent infinitely many concrete programs, Abstract Execution can analyze infinitely many programs at once. Trading off expressiveness and automation, the framework allows proving many interesting (universal, behavioral) properties fully automatically. Its main application are correctness proofs of program transformations represented as pairs of schematic programs. We implemented Abstract Execution in a deductive verification framework and designed a graphical workbench supporting the modeling process. Abstract Execution has been applied to correct code refactoring, analysis of the cost impact of transformation rules, and parallelization of sequential code. Using our framework, we found and reported several bugs in the refactoring engines of the Java IDEs IntelliJ IDEA and Eclipse, which were acknowledged and fixed. [ABSTRACT FROM AUTHOR]

Automated test generation tools enable test automation and further alleviate the low efficiency caused by writing hand-crafted test cases. However, existing automated tools are not mature enough to be widely used by software testing groups. This paper conducts an empirical study on the state-of-the-art automated tools for Java, i.e., EvoSuite, Randoop, JDoop, JTeXpert, T3, and Tardis. We design a test workflow to facilitate the process, which can automatically run tools for test generation, collect data, and evaluate various metrics. Furthermore, we conduct empirical analysis on these six tools and their related techniques from different aspects, i.e., code coverage, mutation score, test suite size, readability, and real fault detection ability. We discuss about the benefits and drawbacks of hybrid techniques based on experimental results. Besides, we introduce our experience in setting up and executing these tools, and summarize their usability and user-friendliness. Finally, we give some insights into automated tools in terms of test suite readability improvement, meaningful assertion generation, test suite reduction for random testing tools, and symbolic execution integration. [ABSTRACT FROM AUTHOR]

Summary: Constraint solving is the enabling technique for symbolic execution. The advancement of constraint solving boosts the development and application of symbolic execution. Modern Satisfiability Modulo Theories (SMT) solvers provide the mechanism of solving strategy, allowing users to control the solving procedure. This mechanism significantly improves the solver's generalization ability. We observe that the symbolic executions of different programs are different constraint solving problems. Therefore, we propose synthesizing solving strategies for a program to fit the program's symbolic execution best. To achieve this, we propose an adaptive framework for synthesizing solving strategies, in which the constraints are classified into different categories, and the solving strategies are synthesized for different categories on demand. We propose novel synthesis algorithms that combine the offline trained deep learning models and online tuning to synthesize the solving strategy. The algorithms balance the synthesis overhead and the improvement achieved by the synthesized solving strategy. We have implemented our method on the state‐of‐the‐art symbolic execution engine KLEE for C programs and Symbolic Pathfinder (SPF) for Java programs. The results of the extensive experiments indicate that our method effectively improves the efficiency of symbolic execution. For the Coreutils benchmark, our method, on average, increases the numbers of paths and queries by 74.37% and 73.94% under Breadth First Search (BFS), respectively. Besides, we applied our method to a different benchmark of C programs and a benchmark of Java programs to validate the generalization ability. The results demonstrate that for the C benchmark, our method increases the numbers of paths and queries by 71.09% and 70.60% under BFS, respectively; For the Java benchmark, our method increases the numbers of paths and queries by 50.31% and 49.93% under BFS, respectively. These results show that our method has a good generalization ability. [ABSTRACT FROM AUTHOR]

Certification through auditing allows to ensure that critical embedded systems are secure. This entails reviewing their critical components and checking for dangerous execution paths. This latter task requires the use of specialized tools which allow to explore and replay executions but are also difficult to use effectively within the context of the audit, where time and knowledge of the code are limited. Fault analysis is especially tricky as the attacker may actively influence execution, rendering some common methods unusable and increasing the number of possible execution paths exponentially. In this work, we present a new method which mitigates these issues by reducing the number of fault injection points considered to only the most relevant ones relatively to some security properties. We use fast and robust static analysis to detect injection points and assert their impactfulness. A more precise dynamic/symbolic method is then employed to validate attack paths. This way the insight required to find attacks is reduced and dynamic methods can better scale to realistically sized programs. Our method is implemented into a toolchain based on Frama-C and KLEE and validated on WooKey, a case study proposed by the National Cybersecurity Agency of France. [ABSTRACT FROM AUTHOR]

Fuzzers have proven to be a vital tool in identifying vulnerabilities. As an area of active research, there is a constant drive to improve fuzzers, and it is equally important to improve benchmarks used to evaluate their performance alongside evolving heuristics. Current research has primarily focused on using CVE bugs as benchmarks, with synthetic benchmarks receiving less attention due to concerns about overfitting specific fuzzing heuristics. In this paper, we introduce ShadowBug, a new methodology that generates enhanced synthetic bugs. In contrast to existing synthetic benchmarks, our approach involves well-arranged bugs that fit specific distributions by quantifying the constraint-solving difficulty of each block. We also uncover implicit constraints of real-world bugs that prior research has overlooked and develop an integer-overflow-based transformation from normal constraints to their implicit forms. We construct a synthetic benchmark and evaluate it against five prominent fuzzers. The experiments reveal that 391 out of 466 bugs were detected, which confirms the practicality and effectiveness of our methodology. Additionally, we introduce a finer-grained evaluation metric called “bug difficulty,” which sheds more light on their heuristic strengths with regard to constraint-solving and bug exploitation. The results of our study have practical implications for future fuzzer evaluation methods.

Directed greybox fuzzing can mainly be used for vulnerability mining and vulnerability replication. However, there are still some issues with existing directional fuzzing tools. One is that after providing problematic changes or patches, it is not possible to quickly target and discover the problem. Secondly, it is difficult to break through the magic byte path, making it difficult to mine deep vulnerabilities. This article proposes a new vulnerability mining and repair framework: American Fuzz Lop Plus (AFL++). Firstly, we utilize alias analysis to enhance inter-procedural control flow graphs and redefine the distance calculation formula to obtain more accurate distances. Secondly, the Newton interpolation method is used for the energy initialization of each seed to prevent test cases from being filtered out due to low energy. A heuristic energy scheduling algorithm is proposed to judiciously schedule the energy of seeds. During the path exploration phase, by adjusting the seed energy, shorter-distance seeds quickly reach the target; with increasing time, seeds tend to explore deeper paths. We then represent the symbolic distance by the number of instructions passed to reach the target and investigate the shortest path search strategy to achieve path pruning, alleviating the problem of path explosion. Finally, based on the above methods, we implement the AFL++ prototype system, integrating directed greybox fuzzing with symbolic execution technology for vulnerability discovery. By interleaving directed symbolic execution and directed greybox fuzzing, the efficiency of vulnerability discovery and reproduction is effectively enhanced. [ABSTRACT FROM AUTHOR]

Software security analysts typically only have access to the executable program and cannot directly access the source code of the program. This poses significant challenges to security analysis. While it is crucial to identify vulnerabilities in such non-source code programs, there exists a limited set of generalized tools due to the low versatility of current vulnerability mining methods. However, these tools suffer from some shortcomings. In terms of targeted fuzzing, the path searching for target points is not streamlined enough, and the completely random testing leads to an excessively large search space. Additionally, when it comes to code similarity analysis, there are issues with incomplete code feature extraction, which may result in information loss. In this paper, we propose a cross-platform and cross-architecture approach to exploit vulnerabilities using neural network obfuscation techniques. By leveraging the Angr framework, a deobfuscation technique is introduced, along with the adoption of a VEX-IR-based intermediate language conversionmethod. This combination allows for the unified handling of binary programs across various architectures, compilers, and compilation options. Subsequently, binary programs are processed to extract multi-level spatial features using a combination of a skip-gram model with self-attention mechanismand a bidirectional Long Short-TermMemory (LSTM) network. Finally, the graph embedding network is utilized to evaluate the similarity of program functionalities. Based on these similarity scores, a target function is determined, and symbolic execution is applied to solve the target function. The solved content serves as the initial seed for targeted fuzzing. The binary program is processed by using the de-obfuscation technique and intermediate language transformation method, and then the similarity of program functions is evaluated by using a graph embedding network, and symbolic execution is performed based on these similarity scores. This approach facilitates cross-architecture analysis of executable programs without their source codes and concurrently reduces the risk of symbolic execution path explosion. [ABSTRACT FROM AUTHOR]

The lack of sound, concise and comprehensive error reports emitted by a static analysis tool can cause increased fixing cost, bottleneck at the availability of experts and even may undermine the trust in static analysis as a method. This paper presents novel techniques to improve the quality of bug reports for static analysis tools that employ symbolic execution. With the combination of data and control dependency analysis, we can identify the relevance of particular code snippets that were previously missing from the report. We demonstrated the benefits of our approach by implementing an improved bug report generator algorithm for the Clang Static Analyzer. After being tested by the open source community our solution became enabled by default in the tool. [ABSTRACT FROM AUTHOR]

Automatic Exploit Generation (AEG) involves automatically discovering paths in a program that trigger vulnerabilities, thereby generating exploits. While there is considerable research on heap-related vulnerability detection, such as detecting Heap Overflow and Use After Free (UAF) vulnerabilities, among contemporary heap-automated exploit techniques, only certain automated exploit techniques can hijack program control flow to the shellcode. An important limitation of this approach is that it cannot effectively bypass Linux's protection mechanisms. To solve this problem, we introduced Automatic Advanced Heap Exploit Generation (AAHEG). It first applies symbolic execution to analyze heap-related primitives in files and then detects potential heap-related vulnerabilities without a source code. After identifying these vulnerabilities, AAHEG builds an exploit abstract syntax tree (AST) to identify one or more successful exploit strategies, such as fast bin attack and Safe-unlink. AAHEG then selects exploitable methods via an abstract syntax tree (AST) and performs final testing to produce the final exploit. AAHEG chose to generate advanced heap-related exploits because the exploits can bypass Linux protections. Basically, AAHEG can automatically detect heap-related vulnerabilities in binaries without source code, build an exploit AST, choose from a variety of advanced heap exploit methods, bypass all Linux protection mechanisms, and generate final file-form exploit based on pwntools which can pass local and remote testing. Experimental results show that AAHEG successfully completed vulnerability detection and exploit generation for 20 Capture The Flag (CTF) binary files, 11 of which have all protection mechanisms enabled. [ABSTRACT FROM AUTHOR]

Memory corruption is a serious class of software vulnerabilities, which requires careful attention to be detected and removed from applications before getting exploited and harming the system users. Symbolic execution is a well-known method for analyzing programs and detecting various vulnerabilities, e.g., memory corruption. Although this method is sound and complete in theory, it faces some challenges, such as path explosion, when applied to real-world complex programs. In this paper, we present a method for improving the efficiency of symbolic execution and detecting four classes of memory corruption vulnerabilities in executable codes, i.e., heap-based buffer overflow, stack-based buffer overflow, use-after-free, and double-free. We perform symbolic execution only on test units rather than the whole program to lower the chance of path explosion. In our method, test units are considered parts of the program's code, which might contain vulnerable statements and are statically identified based on the specifications of memory corruption vulnerabilities. Then, each test unit is symbolically executed to calculate path and vulnerability constraints for each statement of the unit, which determine the conditions on unit input data for executing that statement or activating vulnerabilities in it, respectively. Solving these constraints gives us input values for the test unit, which execute the desired statements and reveal vulnerabilities in them. Finally, we use machine learning to approximate the correlation between system and unit input data. Thereby, we generate system inputs that enter the program, reach vulnerable instructions in the desired test unit, and reveal vulnerabilities in them. This method is implemented as a plug-in for angr framework and evaluated using a group of benchmark programs. The experiments show its superiority over similar tools in accuracy and performance. [ABSTRACT FROM AUTHOR]

Security attacks abuse software vulnerabilities of IoT devices; hence, detecting and eliminating these vulnerabilities immediately are crucial. Fuzzing is an efficient method to identify vulnerabilities automatically, and many publications have been released to date. However, fuzzing for embedded systems has not been studied extensively owing to various obstacles, such as multi-architecture support, crash detection difficulties, and limited resources. Thus, the article introduces fuzzing techniques for embedded systems and the fuzzing differences for desktop and embedded systems. Further, we collect state-of-the-art technologies, discuss their advantages and disadvantages, and classify embedded system fuzzing tools. Finally, future directions for fuzzing research of embedded systems are predicted and discussed. [ABSTRACT FROM AUTHOR]

Binary code similarity is the foundation of many security and software engineering applications. Recent works leverage deep neural networks (DNN) to learn a numeric vector representation (namely, embeddings) of assembly functions, enabling similarity analysis in the numeric space. However, existing DNN-based techniques capture syntactic-, control flow-, or data flow-level information of assembly code, which is too coarsegrained to represent program functionality. These methods can suffer from low robustness to challenging settings such as compiler optimizations and obfuscations. We present sem2vec, a binary code embedding framework that learns from semantics. Given the controlflow graph (CFG) of an assembly function, we divide it into tracelets, denoting continuous and short execution traces that are reachable from the function entry point. We use symbolic execution to extract symbolic constraints and other auxiliary information on each tracelet. We then train masked language models to compute embeddings of symbolic execution outputs. Last, we use graph neural networks, to aggregate tracelet embeddings into the CFG-level embedding for a function. Our evaluation shows that sem2vec extracts highquality embedding and is robust against different compilers, optimizations, architectures, and popular obfuscation methods including virtualization obfuscation. We further augment a vulnerability search application with embeddings computed by sem2vec and demonstrate a significant improvement in vulnerability search accuracy. [ABSTRACT FROM AUTHOR]

In this paper, we present an algebraic approach to the precise and global verification and explanation of Rectifier Neural Networks, a subclass of Piece-wise Linear Neural Networks (PLNNs), i.e., networks that semantically represent piece-wise affine functions. Key to our approach is the symbolic execution of these networks that allows the construction of semantically equivalent Typed Affine Decision Structures (TADS). Due to their deterministic and sequential nature, TADS can, similarly to decision trees, be considered as white-box models and therefore as precise solutions to the model and outcome explanation problem. TADS are linear algebras, which allows one to elegantly compare Rectifier Networks for equivalence or similarity, both with precise diagnostic information in case of failure, and to characterize their classification potential by precisely characterizing the set of inputs that are specifically classified, or the set of inputs where two network-based classifiers differ. All phenomena are illustrated along a detailed discussion of a minimal, illustrative example: the continuous XOR function. [ABSTRACT FROM AUTHOR]

This article tackles the problem of designing efficient binary-level verification for a subset of information flow properties encompassing constant-time and secret-erasure. These properties are crucial for cryptographic implementations but are generally not preserved by compilers. Our proposal builds on relational symbolic execution enhanced with new optimizations dedicated to information flow and binary-level analysis, yielding a dramatic improvement over prior work based on symbolic execution. We implement a prototype, Binsec/Rel, for bug-finding and bounded-verification of constant-time and secret-erasure and perform extensive experiments on a set of 338 cryptographic implementations, demonstrating the benefits of our approach. Using Binsec/Rel, we also automate two prior manual studies on preservation of constant-time and secret-erasure by compilers for a total of 4,148 and 1,156 binaries, respectively. Interestingly, our analysis highlights incorrect usages of volatile data pointer for secret-erasure and shows that scrubbing mechanisms based on volatile function pointers can introduce additional register spilling that might break secret-erasure. We also discovered that gcc -O0 and backend passes of clang introduce violations of constant-time in implementations that were previously deemed secure by a state-of-the-art constant-time verification tool operating at LLVM level, showing the importance of reasoning at binary level. [ABSTRACT FROM AUTHOR]

Code obfuscation has been well developed as mitigated endogenous security technology, to effectively resist MATE attacks (e.g.reverse engineering).And it also has important value for the reasonable metrics of code obfuscation effect.Since symbolic execution is widely used in anti-obfuscation attacks, metrics for code obfuscation resilience can refer to the efforts of generating input test set for executing all program paths.However, some adversarial techniques could reduce the symbol execution efficiency significantly based on the nested structure of the program and increase the error of the resilience reference.To solve the above problems, a metrics for code obfuscation was proposed based on symbolic execution and N-scope complexity.The obfuscation resilience was defined with symbolic execution time and obfuscation potency was defined based on the proposed N-scope complexity for better robustness in measuring the resilience of multi-nested structure programs.Furthermore, the correlation analysis of obfuscation effect was proposed and the effect was quantified by symbolic execution and control flow diagram extraction of programs.Over 4000 obfuscated programs from 3 open-sourced assemblies were evaluated with proposed metrics in the experiment, which indicated the generalization performance and practicality of the metrics.And an example of this metrics application was presented in a simulated obfuscation scenario which provided references of obfuscation technology metrics and obfuscation configuration for obfuscation users.

Symbolic execution is a widely used method for the systematic study of program execution paths; it allows solving a number of important problems related to verification of correctness: searching for errors and vulnerabilities, automatic test generation, etc. The main idea of symbolic execution is generation and use of symbolic expressions in the program analysis in direct order, i.e., from the entry point to the points of interest. At the same time, since the time of E.W. Dijkstra, the method of backward symbolic execution has been popular when the conditions for hitting the point of interest are extended to the entry point of the program due to the iterative calculation of the weakest preconditions. This method is usually much more difficult to implement than direct symbolic execution, so even the artifacts of the latter cannot be used in the implementation. In this paper, the relationship between direct and backward symbolic execution based on the calculation of the weakest preconditions is investigated. In particular, it is shown that the latter can be implemented using the former. A formal presentation of symbolic execution with lazy initialization for programs with dynamic memory is given. An algorithm for calculating the weakest preconditions for arbitrary symbolic executed program branches is proposed. The lazy initialization mechanism and the algorithm for calculating the weakest preconditions are implemented in KLEE, a symbolic virtual machine for the well-known LLVM platform. The proposed method allows performing backward symbolic analysis using direct symbolic execution. This is important for the implementation of bidirectional program execution which can be used both for program verification and for automatic test generation.

Energy harvesting battery-free embedded devices rely only on ambient energy harvesting that enables standalone and sustainable IoT applications. These devices execute programs when the harvested ambient energy in their energy reservoir is sufficient to operate and stop execution abruptly (and start charging) otherwise. These intermittent programs have varying timing behavior under different energy conditions, hardware configurations, and program structures. This article presents Energy-aware Timing Analysis of intermittent Programs (ETAP), a probabilistic symbolic execution approach that analyzes the timing and energy behavior of intermittent programs at compile time. ETAP symbolically executes the given program while taking time and energy cost models for ambient energy and dynamic energy consumption into account. We evaluate ETAP by comparing the compile-time analysis results of our benchmark codes and real-world application with the results of their executions on real hardware. Our evaluation shows that ETAP's prediction error rate is between 0.0076% and 10.8%, and it speeds up the timing analysis by at least two orders of magnitude compared to manual testing. [ABSTRACT FROM AUTHOR]

Homomorphic Encryption (HE) allows computing operations on encrypted data, and it is a potential solution to enable Deep Learning (DL) in privacy-enforcing scenarios (e.g., sending private data to cloud services). However, HE remains a complex technology with multiple challenges that prevent successful application by non-experts. In this work, we present HEFactory, a program compiler that effectively assists in building HE applications in Python for both general-purpose and Deep Learning applications, focusing on non-expert data scientists. HEFactory relies on a layered architecture that deals with challenges such as automatic parameter selection and specific data representation of HE applications. Our benchmarks show that HEFactory substantially lowers the programming complexity (i.e., a reduction of 80% in the number of lines of code) with negligible performance overhead over programs written by experts using native HE frameworks.

Automatic Exploit Generation (AEG) involves automatically discovering paths in a program that trigger vulnerabilities, thereby generating exploits. While there is considerable research on heap-related vulnerability detection, such as detecting Heap Overflow and Use After Free (UAF) vulnerabilities, among contemporary heap-automated exploit techniques, only certain automated exploit techniques can hijack program control flow to the shellcode. An important limitation of this approach is that it cannot effectively bypass Linux’s protection mechanisms. To solve this problem, we introduced Automatic Advanced Heap Exploit Generation (AAHEG). It first applies symbolic execution to analyze heap-related primitives in files and then detects potential heap-related vulnerabilities without a source code. After identifying these vulnerabilities, AAHEG builds an exploit abstract syntax tree (AST) to identify one or more successful exploit strategies, such as fast bin attack and Safe-unlink. AAHEG then selects exploitable methods via an abstract syntax tree (AST) and performs final testing to produce the final exploit. AAHEG chose to generate advanced heap-related exploits because the exploits can bypass Linux protections. Basically, AAHEG can automatically detect heap-related vulnerabilities in binaries without source code, build an exploit AST, choose from a variety of advanced heap exploit methods, bypass all Linux protection mechanisms, and generate final file-form exploit based on pwntools which can pass local and remote testing. Experimental results show that AAHEG successfully completed vulnerability detection and exploit generation for 20 Capture The Flag (CTF) binary files, 11 of which have all protection mechanisms enabled.

Obfuscation is used to protect programs from analysis and reverse engineering. There are theoretically effective and resistant obfuscation methods, however, most of them are not implemented in practice yet. The main issues are the large overhead for the execution of obfuscated code and the limitation of application only to a specific class of programs. On the other hand, a large number of obfuscation methods have been developed that are applied in practice. The existing approaches to the assessment of such obfuscation methods are based mainly on the static characteristics of programs. Therefore, the comprehensive (taking into account the dynamic characteristics of programs) justification of their effectiveness and resistance is a relevant task. It seems that such a justification can be made using machine learning methods based on feature vectors that describe both static and dynamic characteristics of programs. In this paper, it is proposed to build such a vector on the basis of characteristics of two compared programs: the original and obfuscated, original and deobfuscated, obfuscated and deobfuscated. In order to obtain the dynamic characteristics of the program, a scheme based on a symbolic execution is constructed and presented in this paper. The choice of the symbolic execution is justified by the fact that such characteristics can describe the difficulty of comprehension of the program in dynamic analysis. This paper proposes two implementations of the scheme: extended and simplified. The extended scheme is closer to the process of analyzing a program by an analyst, since it includes the steps of disassembly and translation into intermediate code, while in the simplified scheme these steps are excluded. In order to identify the characteristics of symbolic execution that are suitable for assessing the effectiveness and resistance of obfuscation based on machine learning methods, experiments with the developed schemes were carried out. Based on the obtained results, a set of suitable characteristics is determined. [ABSTRACT FROM AUTHOR]

The software packages of the Debian distribution include more than twenty-seven thousand maintainer scripts in total, almost all of them being written in the Posix shell language. These scripts are executed with root privileges at installation, update, and removal of a package, which makes them critical for system maintenance. While the Debian policy provides guidance for package maintainers producing the scripts, only few tools exist to check the compliance of a script to that policy. We present CoLiS, a software platform for discovering violations of non-trivial properties required by the Debian policy in maintainer scripts. We describe our methodology which is based on symbolic execution and feature tree constraints, and we give an overview of the toolchain. We obtain promising results: our toolchain is effective in analysing a large set of Debian maintainer scripts, and it has already detected over 150 policy violations that have led to bug reports, more than two-third of them now being fixed. [ABSTRACT FROM AUTHOR]

Featured Application: A multi-priority scheduling path exploration technology based on abstract syntax tree analysis. Symbolic execution is well known as a dynamic vulnerability discovery technique. Its greatest advantage is the capability to analyze the execution information of the program and to explore the path in the program deterministically. This is a more accurate way to determine if there are vulnerabilities in a program than randomized testing by fuzzing. In addition, symbolic execution does not suffer from the problem of decreasing the capability to discover new paths as more paths are discovered, similar to that caused by random-based fuzzing. However, the reason why symbolic execution is not widely used in vulnerability discovery is mainly due to the state space explosion in the program. The state space explosion severely affects the applicability of symbolic execution. To further improve the applicability of symbolic execution, this paper proposes a path exploration technology based on abstract syntax tree analysis. With the distance between the expression generated by the symbolic execution of the repeat location and the "unsatisfiable" condition of the "unsat" state, we can perform multi-priority scheduling for the repeat location state, thus mitigating the impact of the state space explosion on path exploration. We proposed and implemented EtWExplorer, a multi-priority scheduling technique based on abstract syntax tree analysis. With this technique, we can significantly improve the capability of symbolic execution to discover unknown paths even in state space exploration. Experiments show that EtWExplorer introduces a performance overhead of 72% in the worst case and can improve performance by 294% in the best case. EtWExplorer has a 95% improvement in state space explosion mitigation capability and a 199% to 983% improvement in the path exploration capability of block coverage and a 181% to 1047% improvement in the path exploration capability of edge coverage when facing programs that cause a state space explosion. [ABSTRACT FROM AUTHOR]

In recent years, coverage-guided technology has become the mainstream method of fuzzing. A coverage-guided fuzzer can guide a program to a new path (edge) so that previously untested code can be tested. As coverage-guided fuzzers have become more popular, the difficulty of discovering vulnerabilities has increased significantly. This paper proposes ObFuzzer, an object-oriented binary hybrid fuzzer based on a new assumption. Namely, the object which has been operated more times and operated in more positions is more likely to have defects. Our ObFuzzer consists of the following steps. First, ObFuzzer obtains the inner relations of object operations in the target program through static analysis and analyzes the riskiness of the basic blocks containing such operations. Then, ObFuzzer generates test cases that can guide the program to the basic blocks that this paper considers to be the most dangerous by symbolic execution. Finally, fuzzing is performed using the riskiness of the object operations rather than code coverage. To demonstrate the effectiveness of ObFuzzer over a traditional coverage-guided fuzzer, this paper evaluates its performance in a real program. When facing object-oriented programs, ObFuzzer has a 29% to 40% increase in object operation complexity during execution. These more complex object operations can enhance the ability to discover vulnerabilities related to object operations. Eventually, ObFuzzer found five unique vulnerabilities and one logic error without a crash in "xpdf". [ABSTRACT FROM AUTHOR]

Symbolic execution can comprehensively analyze program execution space in theory, but it is not feasible in practice for large programs like security protocols, due to the explosion of path space and the limitation of difficulty in solving path constraints. According to the characteristics of security protocol program, a method to guide the symbolic execution of security protocol code by using protocol state machine information obtained from model learning was proposed. At the same time, by separating cryptographic logic from protocol interaction logic, the problem that path constraints cannot be solved caused by the complexity of cryptographic logic is avoided. The feasibility of the method is demonstrated by the practice on the SSH open source project Dropbear. Compared with Dropbear's test suite, the proposed method has advantages in code coverage and error point discovery.

Symbolic execution is a program analysis technique that aims to automatically identify interesting inputs for an application, using them to generate program executions covering different parts of the code. It is widely used in the context of vulnerability discovery and reverse engineering. In this paper we present SENinja, a symbolic execution plugin for the BinaryNinja disassembler. The tool allows the user to perform symbolic execution analyses directly within the user interface of the disassembler, and can be used to support a variety of reverse engineering tasks.

A recent case study from AWS by Chong et al. proposes an effective methodology for Bounded Model Checking in industry. In this paper, we report on a follow-up case study that explores the methodology from the perspective of three research questions: (a) can proof artefacts be used across verification tools; (b) are there bugs in verified code; and (c) can specifications be improved. To study these questions, we port the verification tasks for aws-c-common library to SeaHorn, SMACK and KLEE. We show the benefits of using compiler semantics and cross-checking specifications with different verification techniques, and call for standardizing proof library extensions to increase specification reuse. The verification tasks discussed are publicly available online. [ABSTRACT FROM AUTHOR]

Fuzzing is an effective approach to discover bugs in programs, especially memory corruption bugs, using randomly generated test cases. However, without prior knowledge of the target program, the fuzzer can generate only a limited number of test cases because of sanity checks. To solve this problem, recent studies have proposed hybrid fuzzers that observe the context of a target program using symbolic execution; these fuzzers generate test cases to bypass the sanity check. While hybrid fuzzers explore "deep" bugs in the target program, they generate many ineffective test cases. In this paper, we propose a concolic execution algorithm that combines deep reinforcement learning with a hybrid fuzzing solution, Dr.PathFinder. When the reinforcement learning agent encounters a branch during concolic execution, it evaluates the state and determines the search path. In this process,"shallow" paths are pruned, and "deep" paths are searched first. This reduces unnecessary exploration, allowing the efficient memory usage and alleviating the state explosion problem. In experiments with the CB-multios dataset for deep bug cases, Dr.PathFinder discovered approximately five times more bugs than AFL and two times more than Driller-AFL. In addition to finding more bugs, Dr.PathFinder generated 19 times fewer test cases and used at least 2 % less memory than Driller-AFL. While it performed well in finding bugs located in deep paths, Dr.PathFinder had limitation to find bugs located at shallow paths, which we discussed. [ABSTRACT FROM AUTHOR]

The LLVM Clang Static Analyzer is a source code analysis tool which aims to find bugs in C, C++, and Objective-C programs using symbolic execution, i.e. it simulates the possible execution paths of the code. Currently the simulation of the loops is somewhat naive (but efficient), unrolling the loops a predefined constant number of times. However, this approach can result in a loss of coverage in various cases. This study aims to introduce two alternative approaches which can extend the current method and can be applied simultaneously: (1) determining loops worth to fully unroll with applied heuristics, and (2) using a widening mechanism to simulate an arbitrary number of iteration steps. These methods were evaluated on numerous open source projects, and proved to increase coverage in most of the cases. This work also laid the infrastructure for future loop modeling improvements. [ABSTRACT FROM AUTHOR]

In this paper, we introduce an interactive simulator for programs in the form of LLVM bitcode. The main features of the simulator include precise control over thread scheduling, automatic checkpoints and reverse stepping, support for source-level information about functions and variables in C and C++ programs and structured heap visualisation. Additionally, DivSIM is compatible with DiVM (DIVINE VM) hypercalls, which makes it possible to load, simulate and analyse counterexamples from an existing model checker, and with abstract bitcode generated by LART (LLVM Abstraction and Refinement Tool), making it suitable for direct analysis of abstract and/or symbolic programs and counterexamples. [ABSTRACT FROM AUTHOR]

Testing network protocol implementations is difficult mainly because of the temporal uncertain nature of network events. To evaluate the worst-case performance or detect the bugs of a network protocol implementation using network simulators, we need to systematically simulate the behavior of the network protocol under all possible cases of the temporal uncertain events, which is time consuming. The recently proposed Symbolic Execution based Interval Branching (SEIB) simulates a group of uncertain cases together in a single simulation branch and thus is more efficient than brute force testing. In this article, we argue that the efficiency of SEIB could be further significantly improved by eliminating unnecessary comparisons of the event timestamps. Specifically, we summarize and present three general types of unnecessary comparisons when SEIB is applied to a general network simulator, and then correspondingly propose three novel techniques to eliminate them. Our extensive simulations show that our techniques can improve the efficiency of SEIB by several orders of magnitude, such as from days to minutes. [ABSTRACT FROM AUTHOR]

Verification of programs using floating-point arithmetic is challenging on several accounts. One of the difficulties of reasoning about such programs is due to the peculiarities of floating-point arithmetic: rounding errors, infinities, non-numeric objects (NaNs), signed zeroes, denormal numbers, different rounding modes, etc. One possibility to reason about floating-point arithmetic is to model a program computation path by means of a set of ternary constraints of the form and use constraint propagation techniques to infer new information on the variables' possible values. In this setting, we define and prove the correctness of algorithms to precisely bound the value of one of the variables x, y or z, starting from the bounds known for the other two. We do this for each of the operations and for each rounding mode defined by the IEEE 754 binary floating-point standard, even in the case the rounding mode in effect is only partially known. This is the first time that such so-called filtering algorithms are defined and their correctness is formally proved. This is an important slab for paving the way to formal verification of programs that use floating-point arithmetics. [ABSTRACT FROM AUTHOR]

Static deadlock analyses might be able to verify the absence of deadlock. However, they are usually not able to detect its presence. Moreover, when a potential deadlock is detected, they provide little (and often no) information that can help the user in finding the source of the anomalous behaviour. This paper proposes a testing methodology that combines static analysis and symbolic execution for effective deadlock detection in asynchronous programs. When the program features a deadlock, our testing methodology provides an effective technique to catch deadlock traces. While if the program does not have deadlock, but the static deadlock analysis inaccurately spotted it, our approach is able to prove deadlock freedom (up to the limit of the performed symbolic exploration).

Recently, software testing has become a significant component of information security. The most reliable technique for automated software testing is a fuzzing tool that feeds programs with random test-input and detects software vulnerabilities that are critical to security. Similarly, symbolic execution has gained the most attention as an efficient testing tool for producing smart test-inputs and discovering hard-to-reach bugs using search-based heuristics and compositional approaches. The combination of fuzzing and symbolic execution makes software testing more efficient by mitigating the limitations in each other. Although several studies have been conducted on hybrid fuzzing in recent years, a comprehensive and consistent review of hybrid fuzzing techniques has not been explored. To add coherence to the extensive literature on hybrid fuzzing and to make it reach a large audience, this study provides an overview of key concepts along with the taxonomy of existing hybrid fuzzing tools, problems, and solutions that have been developed in this sphere. It also includes evaluations of the proposed approaches and a number of suggestions for the development of hybrid fuzzing in the future.

Mutation testing is basically a fault-based software testing technique, which has been proposed to measure the fault detection effectiveness of a test suite using programs with simulated faults (namely mutants). However, mutation testing is time consuming and computationally expensive because of the normal use of a large amount of mutants. Thus, reducing the mutants is of great significance. To address this problem, various mutant reduction techniques have been proposed. Among them, the identification of redundant mutants aims at removing mutants whose test results can be inferred by other mutants. This article proposes a redundant mutant identification technique based on selective symbolic execution called ReMuSSE for weak mutation testing. Redundant mutants could be revealed by identifying those with similar program execution state changes within a program block involving mutated statements. An empirical study was conducted using 13 C programs from different application domains with varying sizes. The empirical results showed that ReMuSSE could identify up to 31.4% redundant mutants and consequentially save up to 35.2% time cost of weak mutation testing. The results demonstrated that ReMuSSE could effectively identify redundant mutants and thus could significantly improve the efficiency of weak mutation testing. [ABSTRACT FROM AUTHOR]

Using conditional exception code construction and exception handler to replace conditional jump code, the branch obfuscation get the right branch selection, but the address of branch point was concealed, so this obfuscation method can defeat symbolic execution by impeding the constraint condition collecting. The normal method of conditional exception code construction has a fault that the key data in conditional exception code has two-value problem, this fault make down the ability of branch obfuscation in impeding symbolic execution. Based on this shortcoming, a novel method which can make the key data in conditional exception code diversity was proposed. This method can improve the difficulty of constraint condition fetching, so the ability to defeat symbolic execution of branch obfuscation was enhanced. At last, a prototype obfuscation system based on structural exception handler was implemented to test the new method of conditional exception code construction.

This special issue of Software Tools for Technology Transfer comprises extended versions of selected papers from the 26th edition of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2020). The focus of this conference series is tools and algorithms for the rigorous analysis of software and hardware systems, and the papers in this special cover the spectrum of current work in this field. [ABSTRACT FROM AUTHOR]

Automated search for vulnerabilities in ARM IoT devices is considered. The problems of using symbolic execution for vulnerability detection are investigated. A dynamic symbolic execution approach with taint analysis is proposed to improve the efficiency of vulnerability detection, which eliminates the problems that arise when using classical symbolic execution. [ABSTRACT FROM AUTHOR]

Modern operating systems set exploit mitigations to thwart the exploit, which has also become a barrier to automated exploit generation (AEG). Many current AEG solutions do not fully account for exploit mitigations, and as a result, they are unable to accurately assess the exploitability of vulnerabilities in such settings.This paper proposes AEMB, an automated solution for bypassing exploit mitigations and generating useable exploits (EXPs). Initially, AEMB identifies exploit mitigations in the system based on characteristics of the program execution environment. Then, AEMB implements exploit mitigations bypassing the payload generation by modeling expert experience and constructs the corresponding constraints. Next, during the program's execution, AEMB uses symbol execution to collect symbol information and create exploit constraints. Finally, AEMB utilizes a solver to solve the constraints, including payload constraints and exploit constraints, to generate the EXP. In this paper, we evaluated a prototype of AEMB on six test programs and seven real-world applications. Furthermore, we conducted 54 sets of experiments on six different combinations of exploit mitigations. Experiment results indicate that AEMB can automatically overcome exploit mitigations and produce successful exploits for 11 out of 13 applications. [ABSTRACT FROM AUTHOR]

The authors offer a method for detecting potentially incorrect execution of concurrent business processes. It is achieved by using symbolic execution of business process descriptions. The proposed method provides six steps: create a detailed business process description, define transactions, define the incorrect business process execution, create a tree of executable scenarios, calculate the results of the concurrent execution and identify scenarios leading to incorrect results. The proposed algorithm applies to both formally and informally described processes. The method was applied to analysis of different concurrent processes in e-commerce solutions, ticket distribution systems and hotel bookings. [ABSTRACT FROM AUTHOR]