802 results on '"symbolic execution"'
Search Results
2. Automatic Detection, Validation, and Repair of Race Conditions in Interrupt-Driven Embedded Software
- Author
-
Yu Wang, Tingting Yu, Xuandong Li, Linzhang Wang, Fengjuan Gao, and Jianhua Zhao
- Subjects
Embedded software ,Program analysis ,Resource (project management) ,Computer science ,business.industry ,Embedded system ,Concurrent computing ,Static analysis ,Interrupt ,Symbolic execution ,business ,Software ,Race condition - Abstract
Interrupt-driven programs are widely deployed in safety-critical embedded systems to perform hardware and resource dependent data operation tasks. The frequent use of interrupts in these systems can cause race conditions to occur due to interactions between application tasks and interrupt handlers (or two interrupt handlers). Numerous program analysis and testing techniques have been proposed to detect races in multithreaded programs. Little work, however, has addressed race condition problems related to hardware interrupts. In this paper, we present SDRacer, an automated framework that can detect, validate and repair race conditions in interrupt-driven embedded software. It uses a combination of static analysis and symbolic execution to generate input data for exercising the potential races. It then employs virtual platforms to dynamically validate these races by forcing the interrupts to occur at the potential racing points. Finally, it provides repair candidates to eliminate the detected races. We evaluate SDRacer on nine real-world embedded programs written in C language. The results show that SDRacer can precisely detect and successfully fix race conditions.
- Published
- 2022
3. SpecSafe: detecting cache side channels in a speculative world
- Author
-
Mahmut Kandemir, Danfeng Zhang, Robert Brotzman, and Gang Tan
- Subjects
Computer science ,business.industry ,Speculative execution ,Program transformation ,Cryptography ,Static analysis ,Symbolic execution ,Computer security ,computer.software_genre ,Scalability ,Side channel attack ,Cache ,Safety, Risk, Reliability and Quality ,business ,computer ,Software - Abstract
The high-profile Spectre attack and its variants have revealed that speculative execution may leave secret-dependent footprints in the cache, allowing an attacker to learn confidential data. However, existing static side-channel detectors either ignore speculative execution, leading to false negatives, or lack a precise cache model, leading to false positives. In this paper, somewhat surprisingly, we show that it is challenging to develop a speculation-aware static analysis with precise cache models: a combination of existing works does not necessarily catch all cache side channels. Motivated by this observation, we present a new semantic definition of security against cache-based side-channel attacks, called Speculative-Aware noninterference (SANI), which is applicable to a variety of attacks and cache models. We also develop SpecSafe to detect the violations of SANI. Unlike other speculation-aware symbolic executors, SpecSafe employs a novel program transformation so that SANI can be soundly checked by speculation-unaware side-channel detectors. SpecSafe is shown to be both scalable and accurate on a set of moderately sized benchmarks, including commonly used cryptography libraries.
- Published
- 2021
4. Dynamic Property Enforcement in Programmable Data Planes
- Author
-
Miguel Neves, Bradley Huffaker, Marinho P. Barcellos, and Kirill Levchenko
- Subjects
Correctness ,business.industry ,Computer Networks and Communications ,Computer science ,Distributed computing ,Throughput ,Symbolic execution ,Networking hardware ,Computer Science Applications ,Pipeline transport ,Software ,Software bug ,Scalability ,Forwarding plane ,Overhead (computing) ,Latency (engineering) ,Electrical and Electronic Engineering ,business ,Enforcement - Abstract
Network programmers can currently deploy an arbitrary set of protocols in forwarding devices through data plane programming languages such as P4. However, as any other type of software, P4 programs are subject to bugs and misconfigurations. Network verification tools have been proposed as a means of ensuring that the network behaves as expected, but these tools frequently face severe scalability issues. In this paper, we argue for a novel approach to this problem. Rather than statically inspecting a network configuration looking for bugs, we propose to enforce networking properties at runtime. To this end, we developed P4box , a system for deploying runtime monitors in programmable data planes. P4box allows programmers to easily express a broad range of properties (both program-specific and network-wide). Moreover, we provide an automated framework based on assertions and symbolic execution for ensuring monitor correctness. Our experiments on a SmartNIC show that P4box monitors represent a small overhead to network devices in terms of latency, throughput and power consumption.
- Published
- 2021
5. Information-flow control on ARM and POWER multicore processors
- Author
-
Graeme Smith, Nicholas Coughlin, and Toby Murray
- Subjects
Multi-core processor ,Correctness ,Computer science ,business.industry ,HOL ,020207 software engineering ,02 engineering and technology ,Thread (computing) ,Symbolic execution ,Operational semantics ,Theoretical Computer Science ,Hardware and Architecture ,020204 information systems ,Embedded system ,0202 electrical engineering, electronic engineering, information engineering ,Code (cryptography) ,Information flow (information theory) ,business ,Software - Abstract
Weak memory models implemented on modern multicore processors are known to affect the correctness of concurrent code. They can also affect whether or not the concurrent code is secure. This is particularly the case in programs where the security levels of variables are value-dependent, i.e., depend on the values of other variables. In this paper, we illustrate how instruction reordering allowed by ARM and POWER multicore processors leads to vulnerabilities in such programs, and present a compositional, flow-sensitive information-flow logic which can be used to detect such vulnerabilities. The logic allows step-local reasoning (one instruction at a time) about a thread’s security by tracking information about dependencies between instructions which guarantee their order of occurrence. Program security can then be established from individual thread security using rely/guarantee reasoning. The logic has been proved sound with respect to existing operational semantics using Isabelle/HOL, and implemented in an automatic symbolic execution tool.
- Published
- 2021
6. Diversifying Focused Testing for Unit Testing
- Author
-
Paolo Tonella, Federica Sarro, Héctor D. Menéndez, David H. Clark, and Gunel Jahangirova
- Subjects
Unit testing ,business.industry ,Computer science ,Random testing ,020207 software engineering ,02 engineering and technology ,Symbolic execution ,Fault detection and isolation ,Software ,Computer engineering ,Search algorithm ,Test set ,0202 electrical engineering, electronic engineering, information engineering ,Test suite ,020201 artificial intelligence & image processing ,business - Abstract
Software changes constantly, because developers add new features or modifications. This directly affects the effectiveness of the test suite associated with that software, especially when these new modifications are in a specific area that no test case covers. This article tackles the problem of generating a high-quality test suite to cover repeatedly a given point in a program, with the ultimate goal of exposing faults possibly affecting the given program point. Both search-based software testing and constraint solving offer ready, but low-quality, solutions to this: Ideally, a maximally diverse covering test set is required, whereas search and constraint solving tend to generate test sets with biased distributions. Our approach, Diversified Focused Testing (DFT), uses a search strategy inspired by GödelTest. We artificially inject parameters into the code branching conditions and use a bi-objective search algorithm to find diverse inputs by perturbing the injected parameters, while keeping the path conditions still satisfiable. Our results demonstrate that our technique, DFT, is able to cover a desired point in the code at least 90% of the time. Moreover, adding diversity improves the bug detection and the mutation killing abilities of the test suites. We show that DFT achieves better results than focused testing, symbolic execution, and random testing by achieving from 3% to 70% improvement in mutation score and up to 100% improvement in fault detection across 105 software subjects.
- Published
- 2021
7. Software Testing or The Bugs’ Nightmare
- Author
-
Héctor D. Menéndez
- Subjects
Computer science ,business.industry ,Software development ,020207 software engineering ,02 engineering and technology ,Fuzz testing ,Symbolic execution ,Search based testing ,Nightmare ,Software testing ,0202 electrical engineering, electronic engineering, information engineering ,medicine ,Automatic test generation ,020201 artificial intelligence & image processing ,medicine.symptom ,Software engineering ,business - Abstract
Software development is not error-free. For decades, bugs –including physical ones– have become a significant development problem requiring major maintenance efforts. Even in some cases, solving bugs led to increment them. One of the main reasons for bug’s prominence is their ability to hide. Finding them is difficult and costly in terms of time and resources. However, software testing made significant progress identifying them by using different strategies that combine knowledge from every single part of the program. This paper humbly reviews some different approaches from software testing that discover bugs automatically and presents some different state-of-the-art methods and tools currently used in this area. It covers three testing strategies: search-based methods, symbolic execution, and fuzzers. It also provides some income about the application of diversity in these areas, and common and future challenges on automatic test generation that still need to be addressed.
- Published
- 2021
8. Automatic Vulnerability Detection in Embedded Devices and Firmware
- Author
-
Abdullah Qasem, Paria Shirani, Lingyu Wang, Mourad Debbabi, Basile L. Agba, and Bernard Lebel
- Subjects
General Computer Science ,Computer science ,business.industry ,Firmware ,020207 software engineering ,Vulnerability detection ,02 engineering and technology ,Reuse ,Static analysis ,Symbolic execution ,computer.software_genre ,Field (computer science) ,Theoretical Computer Science ,Software ,020204 information systems ,Embedded system ,0202 electrical engineering, electronic engineering, information engineering ,business ,Internet of Things ,computer - Abstract
In the era of the internet of things (IoT), software-enabled inter-connected devices are of paramount importance. The embedded systems are very frequently used in both security and privacy-sensitive applications. However, the underlying software (a.k.a. firmware) very often suffers from a wide range of security vulnerabilities, mainly due to their outdated systems or reusing existing vulnerable libraries; which is evident by the surprising rise in the number of attacks against embedded systems. Therefore, to protect those embedded systems, detecting the presence of vulnerabilities in the large pool of embedded devices and their firmware plays a vital role. To this end, there exist several approaches to identify and trigger potential vulnerabilities within deployed embedded systems firmware. In this survey, we provide a comprehensive review of the state-of-the-art proposals, which detect vulnerabilities in embedded systems and firmware images by employing various analysis techniques, including static analysis, dynamic analysis, symbolic execution, and hybrid approaches. Furthermore, we perform both quantitative and qualitative comparisons among the surveyed approaches. Moreover, we devise taxonomies based on the applications of those approaches, the features used in the literature, and the type of the analysis. Finally, we identify the unresolved challenges and discuss possible future directions in this field of research.
- Published
- 2021
9. Specification-Driven Conformance Checking for Virtual/Silicon Devices Using Mutation Testing
- Author
-
Li Lei, Mingsong Chen, Haifeng Gu, Tongquan Wei, Zhang Jianning, and Fei Xie
- Subjects
business.industry ,Computer science ,02 engineering and technology ,Application software ,computer.software_genre ,Symbolic execution ,Conformance checking ,020202 computer hardware & architecture ,Theoretical Computer Science ,Software ,Computational Theory and Mathematics ,Hardware and Architecture ,Virtual machine ,Formal specification ,Embedded system ,0202 electrical engineering, electronic engineering, information engineering ,Mutation testing ,Software system ,business ,Conformance testing ,computer ,Implementation - Abstract
Modern software systems, either system or application software, are increasingly being developed on top of virtualized software platforms. They may simply intend to execute on virtual machines or they may be expected to port to physical machines eventually. In either case, the devices, virtual or silicon, in the target virtual or physical machines are expected to conform to the specifications based on which the software systems have been developed. Non-conformance of these devices to the specifications can cause catastrophic failures of the software systems. In this article, we propose a mutation-based framework for effective and efficient conformance checking between virtual/silicon device implementations and their specifications. Based on our defined mutation operators, device specifications can be automatically instrumented with weak mutant-killing constraints to model potential erroneous device behaviors. To kill all feasible mutants, our approach adopts a cooperative symbolic execution mechanism that can efficiently automate the test case generation and conformance checking for virtual/silicon devices. By symbolically executing the instrumented specifications with virtual/silicon device traces obtained from the cooperative execution, our method can accurately measure whether the designs have been sufficiently validated and report the inconsistencies between device specifications and implementations. Comprehensive experiments on two industrial network adapters and their virtual devices demonstrate the effectiveness of our proposed approach in conformance checking for both virtual and silicon devices.
- Published
- 2021
10. Beyond Tests
- Author
-
Gregory J. Duck, Bo Wang, Abhik Roychoudhury, Yingfei Xiong, Ruyi Ji, and Xiang Gao
- Subjects
Correctness ,Exploit ,Computer science ,business.industry ,020207 software engineering ,Crash ,02 engineering and technology ,Overfitting ,Machine learning ,computer.software_genre ,Symbolic execution ,Constraint (information theory) ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Test suite ,Benchmark (computing) ,Artificial intelligence ,business ,computer ,Software - Abstract
Automated program repair is an emerging technology that seeks to automatically rectify program errors and vulnerabilities. Repair techniques are driven by a correctness criterion that is often in the form of a test suite. Such test-based repair may produce overfitting patches, where the patches produced fail on tests outside the test suite driving the repair. In this work, we present a repair method that fixes program vulnerabilities without the need for a voluminous test suite. Given a vulnerability as evidenced by an exploit, the technique extracts a constraint representing the vulnerability with the help of sanitizers. The extracted constraint serves as a proof obligation that our synthesized patch should satisfy. The proof obligation is met by propagating the extracted constraint to locations that are deemed to be “suitable” fix locations. An implementation of our approach (E xtract F ix ) on top of the KLEE symbolic execution engine shows its efficacy in fixing a wide range of vulnerabilities taken from the ManyBugs benchmark, real-world CVEs and Google’s OSS-Fuzz framework. We believe that our work presents a way forward for the overfitting problem in program repair by generalizing observable hazards/vulnerabilities (as constraint) from a single failing test or exploit.
- Published
- 2021
11. Directed Test Generation for Activation of Security Assertions in RTL Models
- Author
-
Hasini Witharana, Prabhat Mishra, and Yangdi Lyu
- Subjects
Model checking ,business.industry ,Computer science ,Assertion ,020206 networking & telecommunications ,02 engineering and technology ,Symbolic execution ,Computer Graphics and Computer-Aided Design ,020202 computer hardware & architecture ,Computer Science Applications ,Test (assessment) ,Software ,Runtime error detection ,Scalability ,0202 electrical engineering, electronic engineering, information engineering ,State space ,Electrical and Electronic Engineering ,Software engineering ,business - Abstract
Assertions are widely used for functional validation as well as coverage analysis for both software and hardware designs. Assertions enable runtime error detection as well as faster localization of errors. While there is a vast literature on both software and hardware assertions for monitoring functional scenarios, there is limited effort in utilizing assertions to monitor System-on-Chip (SoC) security vulnerabilities. We have identified common SoC security vulnerabilities and defined several classes of assertions to enable runtime checking of security vulnerabilities. A major challenge in assertion-based validation is how to activate the security assertions to ensure that they are valid. While existing test generation using model checking is promising, it cannot generate directed tests for large designs due to state space explosion. We propose an automated and scalable mechanism to generate directed tests using a combination of symbolic execution and concrete simulation of RTL models. Experimental results on diverse benchmarks demonstrate that the directed tests are able to activate security assertions non-vacuously.
- Published
- 2021
12. Deep Learning-Based Hybrid Fuzz Testing
- Author
-
Yu Wang, Lingyun Situ, Linzhang Wang, and Fengjuan Gao
- Subjects
Computer science ,business.industry ,Software testing ,Deep learning ,Hybrid testing ,Artificial intelligence ,Fuzz testing ,Symbolic execution ,business ,Software engineering - Published
- 2021
13. Exploratory Review of Hybrid Fuzzing for Automated Vulnerability Detection
- Author
-
Fayozbek Rustamov, Juhwan Kim, Jihyeon Yu, and Joobeom Yun
- Subjects
concolic execution ,General Computer Science ,business.industry ,Computer science ,vulnerability ,General Engineering ,software testing ,Fuzz testing ,Information security ,Symbolic execution ,TK1-9971 ,Software ,Hybrid fuzzing ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Component (UML) ,Key (cryptography) ,survey ,General Materials Science ,The Internet ,Electrical engineering. Electronics. Nuclear engineering ,Heuristics ,Software engineering ,business ,symbolic execution - Abstract
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.
- Published
- 2021
14. Gaining trust by tracing security protocols
- Author
-
Hans Svensson, Lars-Åke Fredlund, Clara Benac Earle, and Thomas Arts
- Subjects
Handshake ,business.industry ,Programming language ,Computer science ,Logic ,Interoperability ,020207 software engineering ,Erlang (programming language) ,Cryptography ,02 engineering and technology ,Tracing ,Cryptographic protocol ,Symbolic execution ,computer.software_genre ,Theoretical Computer Science ,Computational Theory and Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Rewriting ,business ,computer ,Software ,computer.programming_language - Abstract
In this article we test an Erlang implementation of the Noise Protocol Framework, using a novel form of white-box testing. We extend interoperability testing of an Erlang enoise implementation against an implementation of Noise in C. Testing typically performs a noise protocol handshake between the two implementations. If successful, then both implementations are somehow compatible. But this does, for example, not detect whether we reuse keys that have to be newly generated. Therefore we extend such operability testing: During the handshake the Erlang noise implementation is traced. The resulting protocol trace is refactored, obtaining as the end result a symbolic description (a functional term) of how key protocol values are constructed using cryptographic operations and keys. Therafter, this symbolic term is compared, using term rewriting, with a symbolic term representing the ideal symbolic execution of the tested noise protocol handshake (i.e., the "semantics" of the handshake). The semantic symbolic term is obtained by executing a symbolic implementation of the noise protocol that we have developed.
- Published
- 2023
15. Automated Patch Transplantation
- Author
-
Shin Hwei Tan, Abhik Roychoudhury, Mingyuan Gao, and Ridwan Shariffdeen
- Subjects
Computer science ,business.industry ,Vulnerability ,020207 software engineering ,02 engineering and technology ,Symbolic execution ,Transplantation ,Workflow ,Software ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Dynamic program analysis ,Differential testing ,Software engineering ,business ,Implementation - Abstract
Automated program repair is an emerging area that attempts to patch software errors and vulnerabilities. In this article, we formulate and study a problem related to automated repair, namely automated patch transplantation. A patch for an error in a donor program is automatically adapted and inserted into a “similar” target program. We observe that despite standard procedures for vulnerability disclosures and publishing of patches, many un-patched occurrences remain in the wild. One of the main reasons is the fact that various implementations of the same functionality may exist and, hence, published patches need to be modified and adapted. In this article, we therefore propose and implement a workflow for transplanting patches. Our approach centers on identifying patch insertion points, as well as namespaces translation across programs via symbolic execution. Experimental results to eliminate five classes of errors highlight our ability to fix recurring vulnerabilities across various programs through transplantation. We report that in 20 of 24 fixing tasks involving eight application subjects mostly involving file processing programs, we successfully transplanted the patch and validated the transplantation through differential testing. Since the publication of patches make an un-patched implementation more vulnerable, our proposed techniques should serve a long-standing need in practice.
- Published
- 2020
16. Tainting-Assisted and Context-Migrated Symbolic Execution of Android Framework for Vulnerability Discovery and Exploit Generation
- Author
-
Qiang Zeng, Min Yang, Limin Liu, Lannan Luo, Jian Liu, Peng Liu, Neng Gao, Kai Chen, Xinyu Xing, and Chen Cao
- Subjects
Exploit ,Computer Networks and Communications ,Computer science ,business.industry ,Mobile computing ,Vulnerability ,020206 networking & telecommunications ,02 engineering and technology ,Symbolic execution ,Computer security ,computer.software_genre ,0202 electrical engineering, electronic engineering, information engineering ,Global Positioning System ,Electrical and Electronic Engineering ,Android (operating system) ,business ,computer ,Software ,Vulnerability discovery - Abstract
Android Application Framework is an integral and foundational part of the Android system. Each of the two billion (as of 2017) Android devices relies on the system services of Android Framework to manage applications and system resources. Given its critical role, a vulnerability in the framework can be exploited to launch large-scale cyber attacks and cause severe harms to user security and privacy. Recently, many vulnerabilities in Android Framework were exposed, showing that it is indeed vulnerable and exploitable. While there is a large body of studies on Android application analysis, research on Android Framework analysis is very limited. In particular, to our knowledge, there is no prior work that investigates how to enable symbolic execution of the framework, an approach that has proven to be very powerful for vulnerability discovery and exploit generation. We design and build the first system, Centaur , that enables symbolic execution of Android Framework. Due to the middleware nature and technical peculiarities of the framework that impinge on the analysis, many unique challenges arise and are addressed in Centaur . The system has been applied to discovering new vulnerability instances, which can be exploited by recently uncovered attacks against the framework, and to generating PoC exploits.
- Published
- 2020
17. Benchmarking the Capability of Symbolic Execution Tools with Logic Bombs
- Author
-
Hui Xu, Yangfan Zhou, Zirui Zhao, and Michael R. Lyu
- Subjects
021110 strategic, defence & security studies ,Computer science ,Process (engineering) ,Logic bomb ,Semantics (computer science) ,business.industry ,0211 other engineering and technologies ,02 engineering and technology ,Benchmarking ,Symbolic execution ,Program analysis ,Benchmark (computing) ,The Symbolic ,Electrical and Electronic Engineering ,Software engineering ,business - Abstract
Symbolic execution has become an indispensable technique for software testing and program analysis. However, since several symbolic execution tools are presently available off-the-shelf, there is a need for a practical benchmarking approach. This paper introduces a fresh approach that can help benchmark symbolic execution tools in a fine-grained and efficient manner. The approach evaluates the performance of such tools against known challenges faced by general symbolic execution techniques, e.g., floating-point numbers and symbolic memories. We first survey related papers and systematize the challenges of symbolic execution. We extract 12 distinct challenges from the literature and categorize them into two categories: symbolic-reasoning challenges and path-explosion challenges . Next, we develop a dataset of logic bombs and a framework for benchmarking symbolic execution tools automatically. For each challenge, our dataset contains several logic bombs, each addressing a specific challenging problem. Triggering one or more logic bombs confirms that the symbolic execution tool in question is able to handle the corresponding problem. Real-world experiments with three popular symbolic execution tools, namely, KLEE, angr, and Triton have shown that our approach can reveal the capabilities and limitations of the tools in handling specific issues accurately and efficiently. The benchmarking process generally takes only a few dozens of minutes to evaluate a tool. We have released our dataset on GitHub as open source, with an aim to better facilitate the community to conduct future work on benchmarking symbolic execution tools.
- Published
- 2020
18. Report on the Differential Testing of Static Analyzers
- Author
-
Gábor Horváth, Reka Nikolett Kovacs, and Peter Szecsi
- Subjects
Information Systems and Management ,Source code ,Computer science ,business.industry ,Heuristic ,media_common.quotation_subject ,020207 software engineering ,02 engineering and technology ,Fuzz testing ,Management Science and Operations Research ,Static analysis ,Symbolic execution ,Theoretical Computer Science ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science (miscellaneous) ,Test suite ,Computer Vision and Pattern Recognition ,Software system ,Electrical and Electronic Engineering ,Software engineering ,business ,Software ,Language construct ,media_common - Abstract
Program faults, best known as bugs, are practically unavoidable in today's ever growing software systems. One increasingly popular way of eliminating them, besides tests, dynamic analysis, and fuzzing, is using static analysis based bug-finding tools. Such tools are capable of finding surprisingly sophisticated bugs automatically by inspecting the source code. Their analysis is usually both unsound and incomplete, but still very useful in practice, as they can find non-trivial problems in a reasonable time (e.g. within hours, for an industrial project) without human intervention. Because the problems that static analyzers try to solve are hard, usually intractable, they use various approximations that need to be fine-tuned in order to grant a good user experience (i.e. as many interesting bugs with as few distracting false alarms as possible). For each newly introduced heuristic, this normally happens by performing differential testing of the analyzer on a lot of widely used open source software projects that are known to use related language constructs extensively. In practice, this process is ad hoc, error-prone, poorly reproducible and its results are hard to share. We present a set of tools that aim to support the work of static analyzer developers by making differential testing easier. Our framework includes tools for automatic test suite selection, automated differential experiments, coverage information of increased granularity, statistics collection, metric calculations, and visualizations, all resulting in a convenient, shareable HTML report.
- Published
- 2020
19. Evaluating Synthetic Bugs
- Author
-
Tim Leek, Brendan Dolan-Gavitt, Joshua Bundt, Andrew Fasano, and William Robertson
- Subjects
FOS: Computer and information sciences ,Root (linguistics) ,Computer Science - Cryptography and Security ,business.industry ,Computer science ,CPU time ,020207 software engineering ,02 engineering and technology ,Fuzz testing ,Symbolic execution ,Machine learning ,computer.software_genre ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Artificial intelligence ,business ,computer ,Cryptography and Security (cs.CR) - Abstract
Fuzz testing has been used to find bugs in programs since the 1990s, but despite decades of dedicated research, there is still no consensus on which fuzzing techniques work best. One reason for this is the paucity of ground truth: bugs in real programs with known root causes and triggering inputs are difficult to collect at a meaningful scale. Bug injection technologies that add synthetic bugs into real programs seem to offer a solution, but the differences in finding these synthetic bugs versus organic bugs have not previously been explored at a large scale. Using over 80 years of CPU time, we ran eight fuzzers across 20 targets from the Rode0day bug-finding competition and the LAVA-M corpus. Experiments were standardized with respect to compute resources and metrics gathered. These experiments show differences in fuzzer performance as well as the impact of various configuration options. For instance, it is clear that integrating symbolic execution with mutational fuzzing is very effective and that using dictionaries improves performance. Other conclusions are less clear-cut; for example, no one fuzzer beat all others on all tests. It is noteworthy that no fuzzer found any organic bugs (i.e., one reported in a CVE), despite 50 such bugs being available for discovery in the fuzzing corpus. A close analysis of results revealed a possible explanation: a dramatic difference between where synthetic and organic bugs live with respect to the ''main path'' discovered by fuzzers. We find that recent updates to bug injection systems have made synthetic bugs more difficult to discover, but they are still significantly easier to find than organic bugs in our target programs. Finally, this study identifies flaws in bug injection techniques and suggests a number of axes along which synthetic bugs should be improved., Comment: 15 pages
- Published
- 2022
- Full Text
- View/download PDF
20. Analyzing system software components using API model guided symbolic execution
- Author
-
Ken Yihang Bai and Tuba Yavuz
- Subjects
Programming language ,business.industry ,Computer science ,020207 software engineering ,Linux kernel ,02 engineering and technology ,Symbolic execution ,computer.software_genre ,Software framework ,Protocol stack ,Software ,Component (UML) ,Component-based software engineering ,0202 electrical engineering, electronic engineering, information engineering ,business ,computer ,System software - Abstract
Analyzing real-world software is challenging due to complexity of the software frameworks or APIs they depend on. In this paper, we present a tool, PROMPT, that facilitates the analysis of software components using API model guided symbolic execution. PROMPT has a specification component, PROSE, that lets users define an API model, which consists of a set of data constraints and life-cycle rules that define control-flow constraints among sequentially composed API functions. Given a PROSE model and a software component, PROMPT symbolically executes the component while enforcing the specified API model. PROMPT has been implemented on top of the KLEE symbolic execution engine and has been applied to Linux device drivers from the video, sound, and network subsystems and to some vulnerable components of BlueZ, the implementation of the Bluetooth protocol stack for the Linux kernel. PROMPT detected two new and four known memory vulnerabilities in some of the analyzed system software components.
- Published
- 2020
21. Modified condition/decision coverage (MC/DC) oriented compiler optimization for symbolic execution
- Author
-
Ji Wang, Weijiang Hong, Zhenbang Chen, Yi-jun Liu, and Wei Dong
- Subjects
Computer Networks and Communications ,Computer science ,business.industry ,Programming language ,Existential quantification ,Process (computing) ,Optimizing compiler ,Binary number ,020207 software engineering ,02 engineering and technology ,Symbolic execution ,computer.software_genre ,Support vector machine ,Modified condition/decision coverage ,Software ,Hardware and Architecture ,020204 information systems ,Signal Processing ,0202 electrical engineering, electronic engineering, information engineering ,Electrical and Electronic Engineering ,business ,computer - Abstract
Symbolic execution is an effective way of systematically exploring the search space of a program, and is often used for automatic software testing and bug finding. The program to be analyzed is usually compiled into a binary or an intermediate representation, on which symbolic execution is carried out. During this process, compiler optimizations influence the effectiveness and efficiency of symbolic execution. However, to the best of our knowledge, there exists no work on compiler optimization recommendation for symbolic execution with respect to (w.r.t.) modified condition/decision coverage (MC/DC), which is an important testing coverage criterion widely used for mission-critical software. This study describes our use of a state-of-the-art symbolic execution tool to carry out extensive experiments to study the impact of compiler optimizations on symbolic execution w.r.t. MC/DC. The results indicate that instruction combining (IC) optimization is the important and dominant optimization for symbolic execution w.r.t. MC/DC. We designed and implemented a support vector machine based optimization recommendation method w.r.t. IC (denoted as auto). The experiments on two standard benchmarks (Coreutils and NECLA) showed that auto achieves the best MC/DC on 67.47% of Coreutils programs and 78.26% of NECLA programs.
- Published
- 2020
22. On the Detection of Exploitation of Vulnerabilities Leading to the Execution of a Malicious Code
- Author
-
Yury V. Kosolapov
- Subjects
Economics and Econometrics ,Exploit ,Computer science ,Shell (computing) ,0211 other engineering and technologies ,Information technology ,02 engineering and technology ,Symbolic execution ,Set (abstract data type) ,Software ,0202 electrical engineering, electronic engineering, information engineering ,Materials Chemistry ,Media Technology ,Code (cryptography) ,021110 strategic, defence & security studies ,software vulnerability ,library calls ,business.industry ,Forestry ,Function (mathematics) ,T58.5-58.64 ,Task (computing) ,020201 artificial intelligence & image processing ,business ,Algorithm ,system calls - Abstract
Software protection from exploitation of possible unknown vulnerabilities can be performed both by searching (for example, using symbolic execution) and subsequent elimination of the vulnerabilities and by using detection and / or intrusion prevention systems. In the latter case, this problem is usually solved by forming a profile of a normal behavior and deviation from normal behavior over a predetermined threshold is regarded as an anomaly or an attack. In this paper, the task is to protect a given software P from exploiting unknown vulnerabilities. For this aim a method is proposed for constructing a profile of the normal execution of the program P, in which, in addition to a set of legal chains of system and library functions, it is proposed to take into account the distances between adjacent function calls. At the same time, a profile is formed for each program. It is assumed that taking into account the distances between function calls will reveal shell code execution using system and / or library function calls. An algorithm and a system for detecting abnormal code execution are proposed. The work carried out experiments in the case when P is the FireFox browser. During the experiments the possibility of applying the developed algorithm to identify abnormal behavior when launching publicly available exploits was investigated.
- Published
- 2020
23. ConTesa: Directed Test Suite Augmentation for Concurrent Software
- Author
-
Zunchen Huang, Tingting Yu, and Chao Wang
- Subjects
Computer science ,business.industry ,020207 software engineering ,02 engineering and technology ,Thread (computing) ,Symbolic execution ,Software ,Test case ,Embedded system ,Regression testing ,0202 electrical engineering, electronic engineering, information engineering ,Test suite ,Concurrent computing ,business - Abstract
As software evolves, test suite augmentation techniques may be used to identify which part of the program needs to be tested due to code changes and how to generate these new test cases for regression testing. However, existing techniques focus exclusively on sequential software, without considering concurrent software in which multiple threads may interleave with each other during the execution and thus lead to a combinatorial explosion. To fill the gap, we propose ConTesa , the first test suite augmentation tool for concurrent software. The goal is to generate new test cases capable of exercising both code changes and the thread interleavings affected by these code changes. At the center of ConTesa is a two-pronged approach. First, it judiciously reuses the current test inputs while amplifying their interleaving coverage using random thread schedules. Then, it leverages an incremental symbolic execution technique to generate more test inputs and interleavings, to cover the new concurrency-related program behaviors. We have implemented ConTesa and evaluated it on a set of real-world multithreaded Linux applications. Our results show that it can achieve a significantly high interleaving coverage and reveal more bugs than state-of-the-art testing techniques.
- Published
- 2020
24. CSEFuzz: Fuzz Testing Based on Symbolic Execution
- Author
-
Xie Zhangwei, Jiaming Zhang, Xiulei Liu, Zhanqi Cui, and Liwei Zheng
- Subjects
Parsing ,General Computer Science ,business.industry ,Computer science ,General Engineering ,020207 software engineering ,02 engineering and technology ,Fuzz testing ,computer.software_genre ,Symbolic execution ,Set (abstract data type) ,Test case ,Software ,initial seeds ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,General Materials Science ,Data mining ,lcsh:Electrical engineering. Electronics. Nuclear engineering ,business ,computer ,lcsh:TK1-9971 ,symbolic execution ,test coverage criteria - Abstract
Fuzz testing has been successful in finding defects of various software packages. These defects include file parsing, image processing, Internet browsers, and network protocols. However, the quality of the initial seed test cases greatly influences the coverage and defect detection capability of fuzz testing. To address this issue, we propose CSEFuzz, a fuzz testing approach based on symbolic execution for defect detection. First, CSEFuzz generates candidate test cases by symbolic execution and collects coverage information of the test cases. Then, CSEFuzz extracts the test-case templates of the test cases and selects a set of test-case templates according to specific coverage criteria. Finally, CSEFuzz selects test cases according to the selected test-case templates, and the selected test cases are used as initial seed test cases for fuzz testing. Experiments are conducted on 11 open-source programs. The results show that in comparison with afl-cmin, which is the test-case selection command of Kelinci, CSEFuzz with a path coverage criterion reduces the time costs of the initial seed test selection and verification by 94.26%. In addition, compared with afl-cmin, 32 more paths are covered and 16 more defects are detected by CSEFuzz.
- Published
- 2020
25. Automated Data-Processing Function Identification Using Deep Neural Network
- Author
-
Hongyu Kuang, Chao Feng, Jian Wang, Xing Zhang, and Ruilin Li
- Subjects
Source code ,source code ,General Computer Science ,Data-processing ,Computer science ,media_common.quotation_subject ,Automated data processing ,vulnerability ,Code coverage ,Symbolic execution ,Machine learning ,computer.software_genre ,Taint checking ,Software ,function identification ,General Materials Science ,media_common ,Vulnerability (computing) ,business.industry ,General Engineering ,deep neural network ,Fuzz testing ,Identification (information) ,Artificial intelligence ,lcsh:Electrical engineering. Electronics. Nuclear engineering ,business ,computer ,lcsh:TK1-9971 - Abstract
The number of software vulnerabilities is increasing year by year. In the era of big data, data-processing software with many users is more concerned by hackers. It is essential to improve the efficiency of discovering vulnerabilities in data-processing software. We noticed that in the process of discovering vulnerabilities, some problems of existing technology such as fuzzing, symbolic execution, and taint analysis have more or fewer relationships with data-processing functions. In fuzzing, there are two types of sanity checks toward the target program: NCC (Non-critical check) and CC (critical check). It is usually challenging to bypass such a sanity check, which leads to low code coverage during fuzzing. In symbolic execution, the constraint solver still has the problem of trying to deal with the constraints of complex algorithms. In taint analysis, the problem of over-taint and under-taint is always the key to affect the accuracy of the results. Therefore, to solve the above problems, it is necessary to identify the data-processing function. Based on identifying data-processing functions, we could identify those sanity checks, ease the solution of complex constraints, and understand the way of taints propagation to assist in software vulnerability discovery and analysis. This paper proposed a method called DPFI(data-processing function identification) for identifying data-processing functions with deep neural networks. We collected 37000 functions from GitHub and implemented the method on the data set with several neural networks, among which the performance of CNN achieved best and $F_{1}$ -score was 0.90. We then applied the trained model on CGC(cyber grand challenge) data and real softwares for testing. For CGC, we got 448 functions in 20 programs, in which 35 were identified as data-processing functions. For real softwares, such as FFmpeg, 7zip, jpeg, the precision rate all reached 0.90 and $F_{1}$ -score was above 0.87.
- Published
- 2020
26. Differential Testing of Certificate Validation in SSL/TLS Implementations
- Author
-
Zhenhua Duan, Chu Chen, Liang Zhao, and Cong Tian
- Subjects
Protocol (science) ,Transport Layer Security ,business.industry ,Computer science ,020207 software engineering ,02 engineering and technology ,Request for Comments ,Certificate ,Internet security ,Symbolic execution ,computer.software_genre ,Test case ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Operating system ,business ,Implementation ,computer ,Software - Abstract
Certificate validation in Secure Sockets Layer or Transport Layer Security protocol (SSL/TLS) is critical to Internet security. Thus, it is significant to check whether certificate validation in SSL/TLS implementations is correctly implemented. With this motivation, we propose a novel differential testing approach that is based on the standard Request for Comments (RFC). First, rules of certificates are extracted automatically from RFCs. Second, low-level test cases are generated through dynamic symbolic execution. Third, high-level test cases, i.e., certificates, are assembled automatically. Finally, with the assembled certificates being test cases, certificate validations in SSL/TLS implementations are tested to reveal latent vulnerabilities or bugs. Our approach named RFCcert has the following advantages: (1) certificates of RFCcert are discrepancy-targeted, since they are assembled according to standards instead of genetics; (2) with the obtained certificates, RFCcert not only reveals the invalidity of traditional differential testing but also is able to conduct testing that traditional differential testing cannot do; and (3) the supporting tool of RFCcert has been implemented and extensive experiments show that the approach is effective in finding bugs of SSL/TLS implementations. In addition, by providing seed certificates for mutation approaches with RFCcert, the ability of mutation approaches in finding distinct discrepancies is significantly enhanced.
- Published
- 2019
27. Are we done yet? Our Journey to Fight against Memory-safety Bugs
- Author
-
Taesoo Kim
- Subjects
Thread (network protocol) ,Computer science ,business.industry ,Legacy system ,Fuzz testing ,Computer security ,computer.software_genre ,Symbolic execution ,Software ,business ,computer ,Memory safety ,Hacker ,Rust (programming language) ,computer.programming_language - Abstract
Memory-safety issues have been a long-standing concern of the security practitioners. According to Microsoft and Google, memory-safety bugs still represent 70% of the exploited vulnerabilities in complex, real-world programs like OSes and Web browsers. However, it doesn't mean that academics and practitioners haven't tried hard to alleviate the problem. Advances in automatic techniques like fuzzing and sanitizers revolutionize the way we tame the memory safety bugs, but the increasing volume of new software simply outpaces the adoption rate of these promising new techniques, setting the legacy programs aside. In this talk, I'd like to share "our" own journey to fight against memory-safety bugs - "our" is important as all research is conducted together with the brightest hackers in SSLab at Georgia Tech. First, I'd like to talk about our group's research agenda in the memory-safety world ranging from binary exploitation, programming analysis, fuzzing, symbolic execution and security education. Second, I will share our group's journey to participate in the DARPA CGC, DEFCON CTF and pwn2own competitions. Third, I will also present where our group is heading to: a promising new memory/thread-safe language, called Rust. Lastly, I will conclude the talk with an important projection by using our recent work on finding bugs in the Rust packages: like COVID-19, the memory-safety bugs likely stay with us for the next decade, if not more.
- Published
- 2021
28. Delta-based verification of software product families
- Author
-
Dominic Steinhöfel, Marco Scaletta, Reiner Hähnle, and Richard Bubel
- Subjects
Correctness ,Generalization ,Computer science ,Programming language ,business.industry ,Program transformation ,computer.software_genre ,Liskov substitution principle ,Symbolic execution ,Set (abstract data type) ,Software ,Code (cryptography) ,business ,computer - Abstract
The quest for feature- and family-oriented deductive verification of software product lines resulted in several proposals. In this paper we look at delta-oriented modeling of product lines and combine two new ideas: first, we extend Hahnle & Schaefer’s delta-oriented version of Liskov’s substitution principle for behavioral subtyping to work also for overridden behavior in benign cases. For this to succeed, programs need to be in a certain normal form. The required normal form turns out to be achievable in many cases by a set of program transformations, whose correctness is ensured by the recent technique of abstract execution. This is a generalization of symbolic execution that permits reasoning about abstract code elements. It is needed, because code deltas contain partially unknown code contexts in terms of “original” calls. Second, we devise a modular verification procedure for deltas based on abstract execution, representing deltas as abstract programs calling into unknown contexts. The result is a “delta-based” verification approach, where each modification of a method in a code delta is verified in isolation, but which overcomes the strict limitations of behavioral subtyping and works for many practical programs. The latter claim is substantiated with case studies and benchmarks.
- Published
- 2021
29. AttkFinder: Discovering Attack Vectors in PLC Programs using Information Flow Analysis
- Author
-
Martín Ochoa, Owen Arden, Jianying Zhou, Alvaro A. Cardenas, and John Henry Castellanos
- Subjects
Software ,Network packet ,business.industry ,Computer science ,Testbed ,Programmable logic controller ,Process (computing) ,Information flow (information theory) ,Industrial control system ,business ,Symbolic execution ,Computer network - Abstract
To protect an Industrial Control System (ICS), defenders need to identify potential attacks on the system and then design mechanisms to prevent them. Unfortunately, identifying potential attack conditions is a time-consuming and error-prone process. In this work, we propose and evaluate a set of tools to symbolically analyse the software of Programmable Logic Controllers (PLCs) guided by an information flow analysis that takes into account PLC network communication (compositions). Our tools systematically analyse malicious network packets that may force the PLC to send specific control commands to actuators. We evaluate our approach in a real-world system controlling the dosing of chemicals for water treatment. Our tools are able to find 75 attack tactics (56 were novel attacks), and we confirm that 96% of these tactics cause the intended effect in our testbed.
- Published
- 2021
30. SyML: Guiding Symbolic Execution Toward Vulnerable States Through Pattern Learning
- Author
-
Giovanni Vigna, Lukas Dresel, Kyle Zeng, Tiffany Bao, Stefano Zanero, Mario Polino, Nicola Ruaro, Christopher Kruegel, Andrea Continella, Services, Cybersecurity & Safety, and Digital Society Institute
- Subjects
Symbolic execution ,Cybersecurity ,Computer science ,business.industry ,media_common.quotation_subject ,Vulnerability ,Crash ,Replicate ,Machine learning ,computer.software_genre ,Path (graph theory) ,Vulnerability discovery ,Leverage (statistics) ,The Symbolic ,Artificial intelligence ,business ,Function (engineering) ,computer ,media_common - Abstract
Exploring many execution paths in a binary program is essential to discover new vulnerabilities. Dynamic Symbolic Execution (DSE) is useful to trigger complex input conditions and enables an accurate exploration of a program while providing extensive crash replayability and semantic insights. However, scaling this type of analysis to complex binaries is difficult. Current methods suffer from the path explosion problem, despite many attempts to mitigate this challenge (e.g., by merging paths when appropriate). Still, in general, this challenge is not yet surmounted, and most bugs discovered through such techniques are shallow. We propose a novel approach to address the path explosion problem: A smart triaging system that leverages supervised machine learning techniques to replicate human expertise, leading to vulnerable path discovery. Our approach monitors the execution traces in vulnerable programs and extracts relevant features - register and memory accesses, function complexity, system calls - to guide the symbolic exploration. We train models to learn the patterns of vulnerable paths from the extracted features, and we leverage their predictions to discover interesting execution paths in new programs. We implement our approach in a tool called SyML, and we evaluate it on the Cyber Grand Challenge (CGC) dataset - a well-known dataset of vulnerable programs - and on 3 real-world Linux binaries. We show that the knowledge collected from the analysis of vulnerable paths, without any explicit prior knowledge about vulnerability patterns, is transferrable to unseen binaries, and leads to outperforming prior work in path prioritization by triggering more, and different, unique vulnerabilities.
- Published
- 2021
31. SymbA: Symbolic Execution at C-level for Hardware Trojan Activation
- Author
-
Arash Vafaei, Farimah Farahmandi, Nick Hooten, and Mark Tehranipoor
- Subjects
Hardware Trojan ,Computer science ,business.industry ,Embedded system ,Symbolic execution ,business - Published
- 2021
32. Risks of Concurrent Execution in E-Commerce Processes
- Author
-
Ivo Oditis, Zane Bicevska, Janis Bicevskis, Anastasija Nikiforova, and Girts Karnitis
- Subjects
Service (systems architecture) ,Exact model ,Risk analysis (engineering) ,Process (engineering) ,Computer science ,business.industry ,Information and Communications Technology ,ComputingMilieux_COMPUTERSANDSOCIETY ,E-commerce ,Symbolic execution ,business - Abstract
The development of ICT facilitates replacing the traditional buying and selling processes with e-commerce solutions. If several customers are served concurrently, e.g. at the same time, the processes can interference each other causing risks for both the buyer and the seller. The paper offers a method to identify purchase/sale risks in simultaneous multi-customer service processes. First, an exact model of buying-selling processes is created and the conditions for the correct process execution are formulated. Then an analysis of all the possible scenarios, including the concurrently executed buying-selling scenarios, is performed using a symbolic execution of process descriptions. The obtained result allows both the buyer and the seller to identify the risks of an e-commerce solution.
- Published
- 2021
33. The Impact of Compiler Optimizations on Symbolic Execution
- Author
-
Jiaorui Shen
- Subjects
Software ,Computer science ,business.industry ,Path (graph theory) ,Optimizing compiler ,Compiler ,Parallel computing ,Symbolic execution ,computer.software_genre ,business ,computer - Abstract
Software test plays an important role in software engineering, and dynamic symbolic execution (DSE) has become a popular technique in white-box testing. However, the efficiency of DSE is a big challenge of this technique. Compiler optimizations may have a big impact on DSE in some cases. In this paper, we introduce two small examples to visually show the impact of compiler optimizations on constraints solving and path exploration of DSE. After that, we propose a series of experiments using KLEE and LL VM compiler as a case to test real C programs in Coreutils-8.32. We use a simple model to assess the impact of different compiler optimizations and we also study on the combinations of compiler optimizations. The results show compiler optimizations can have both positive and negative effects, and some optimizations like FI may have greater influences than others. Moreover, some combinations of compiler optimizations can better improve the efficiency of DSE than single compiler optimization, which can be further studied.
- Published
- 2021
34. Inferring Relations Among Test Programs in Microservices Applications
- Author
-
Guglielmo De Angelis, Alessandro Pellegrini, Emanuele De Angelis, and Maurizio Proietti
- Subjects
Focus (computing) ,Settore ING-INF/05 ,Computer science ,business.industry ,software testing ,Context (language use) ,Microservices ,Symbolic execution ,Automation ,Test (assessment) ,microservices architecture ,test program similarity ,symbolic execution ,automated reasoning ,Automated reasoning ,Software engineering ,business ,Architectural style - Abstract
The emergence of the microservices-oriented architectural style calls for novel methodologies and technological frameworks that support the design, development, and main-tainance of applications structured according to this new style. In this paper, we consider the issue of designing suitable strategies for the governance and the automation of testing activities within the microservices paradigm. We focus on the problem of discovering relations between test programs that help avoiding to re-run all the available test suites each time one of its constituents evolves. We propose an analysis technique, based on symbolic execution of test programs, which is able to collect information about the invocations of local and remote APIs performed when running such programs. Symbolic execution enables the analysis of sets of executions corresponding to different input data, and hence it is also suitable for parametric test programs. The information extracted by symbolic execution is processed by a rule-based automated reasoning engine, which infers dependencies and similarities among test programs. In particular, test programs are considered similar if they involve the same microservice instance, or they connect to the same remote API, or they locally activate overlapping APIs, or they raise similar kinds of errors. We show the viability of our approach by presenting a case study within the context of a real-world microservice application that implements an open-source educational platform.
- Published
- 2021
35. Symbolic Model-based Design and Generation of Logical Scenarios for Autonomous Vehicles Validation
- Author
-
Julien Niol, Boutheina Bannour, Paolo Crisafulli, CEA- Saclay (CEA), Commissariat à l'énergie atomique et aux énergies alternatives (CEA), APSYS [Elancourt], APSYS, and IRT SystemX
- Subjects
Black box (phreaking) ,[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC] ,Theoretical computer science ,Computer science ,business.industry ,Time series analysis ,Modular design ,Symbolic execution ,Formal methods ,[INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation ,Identification (information) ,[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] ,Redundancy ,Self-Driving Vehicles ,[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] ,Model-based design ,Redundancy (engineering) ,Analytical models ,Representation (mathematics) ,business ,Advanced Driver Assistance Systems ,[PHYS.PHYS.PHYS-DATA-AN]Physics [physics]/Physics [physics]/Data Analysis, Statistics and Probability [physics.data-an] - Abstract
International audience; Finding comprehensive and relevant scenarios is a major challenge for autonomous vehicles validation and SOTIF. A functional scenario, e.g. a cut-in, encloses many concrete variations. Formal methods help covering an intermediate level of scenario families, called logical, and capitalizing them in a scenario database. Families are generated from discrete and modular symbolic models through a new subsumption criterion which allows the identification of scenario suffixes which are redundant and eliminate them during the generation. The generation, including the implementation of the subsumption criterion, benefits from: i) the compact representation of models thanks to discretization and symbolic arithmetic, ii) dedicated symbolic execution techniques. Analysis is performed to verify how the generated scenarios cover real situations by confronting them to time series from the modeled system and identify potential gaps in the model. We formally define our approach, implement it in the symbolic execution tool DIVERSITY. Assessment is carried out on a real autopilot black box module from the project 3SA.
- Published
- 2021
36. Synthesize solving strategy for symbolic execution
- Author
-
Ziqi Shuai, Zehua Chen, Ji Wang, Guofeng Zhang, Weiyu Pan, Zhenbang Chen, and Yufeng Zhang
- Subjects
Theoretical computer science ,Java ,business.industry ,Computer science ,Generalization ,Deep learning ,Solver ,Symbolic execution ,Constraint (information theory) ,Benchmark (computing) ,Overhead (computing) ,Artificial intelligence ,business ,computer ,computer.programming_language - Abstract
Symbolic execution is powered by constraint solving. The advancement of constraint solving boosts the development and the applications of symbolic execution. Modern SMT solvers provide the mechanism of solving strategy that allows the users to control the solving procedure, which significantly improves the solver's generalization ability. We observe that the symbolic executions of different programs are actually different constraint solving problems. Therefore, we propose synthesizing a solving strategy for a program to fit the program's symbolic execution best. To achieve this, we divide symbolic execution into two stages. The SMT formulas solved in the first stage are used to online synthesize a solving strategy, which is then employed during the constraint solving in the second stage. We propose novel synthesis algorithms that combine 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. The results of the extensive experiments indicate that our method effectively improves the efficiency of symbolic execution. On average, our method increases the numbers of queries and paths by 58.76% and 66.11%, respectively. Besides, we applied our method to a Java Pathfinder-based concolic execution engine to validate the generalization ability. The results indicate that our method has a good generalization ability and increases the numbers of queries and paths by 100.24% and 102.6% for the benchmark Java programs, respectively.
- Published
- 2021
37. AngErza: Automated Exploit Generation
- Author
-
T K Geethna, Shruti Dixit, Vipin Pavithran, and Swaminathan Jayaraman
- Subjects
Identification (information) ,Software ,Exploit ,Software bug ,Computer science ,business.industry ,Payload ,Code (cryptography) ,Software engineering ,business ,Symbolic execution ,Buffer overflow - Abstract
Vulnerability detection and exploitation serves as a milestone for secure development and identifying major threats in software applications. Automated exploit generation helps in easier identification of bugs, the attack vectors and the various possibilities of generation of the exploit payload. Thus, we introduce AngErza which uses dynamic and symbolic execution to identify hot-spots in the code, formulate constraints and generate a payload based on those constraints. Our tool is entirely based on angr which is an open-sourced offensive binary analysis framework. The work around AngErza focuses on exploit and vulnerability detection in CTF-style C binaries compiled on 64-bit Intel architecture for the early-phase of this project.
- Published
- 2021
38. A Framework for the Composition of IoT and CPS Capabilities
- Author
-
Edward Griffor, A.T. Dahbura, Khalid Halba, and Ahmed Lbath
- Subjects
business.industry ,Computer science ,Semantics (computer science) ,Formal specification ,The Internet ,Symbolic execution ,business ,Software engineering ,Temporal logic of actions ,Formal verification ,Protocol (object-oriented programming) ,Building automation - Abstract
By 2030, over a half trillion devices will be connected to the internet. With so many devices providing a wide range of features, there is a need for a framework for innovation and reuse of Internet of Things (IoT) and Cyber-Physical Systems (CPS) capabilities. Such framework should facilitate the composition of capabilities and provide stakeholders means to reliably model and verify compositions. An IoT and CPS Composition Framework (ICCF) is proposed to achieve this goal. ICCF is based on the NIST CPS framework composition guidelines, intuitive composition semantics inspired from the mPlane protocol, and strong formal verification capabilities of the Temporal Logic of Actions (TLA) formal descriptors and tools. This paper demonstrates why such framework, semantics, and formal specification and verification components form a powerful and intuitive composition framework that satisfies different stakeholders concerns. To achieve this purpose, semantics and formal specification of the composition algebra were provided, a well-being composite capability within a smart building was specified, its prototype model in a formal verification tool was run, an analysis of the results of symbolic execution quantitatively and qualitatively was performed, and assessment of the trustworthiness of the composition was done. Lastly, implementation details were provided and proposed extensions to other domains such as smart transportation and smart health were discussed.
- Published
- 2021
39. QFuzz: Quantitative Fuzzing for Side Channels
- Author
-
Saeid Tizpaz-Niari and Yannic Noller
- Subjects
FOS: Computer and information sciences ,Computer Science - Cryptography and Security ,Java ,Computer science ,business.industry ,Distributed computing ,Min entropy ,Fuzz testing ,Static analysis ,Symbolic execution ,Software Engineering (cs.SE) ,Computer Science - Software Engineering ,Software ,Scalability ,Software system ,business ,Cryptography and Security (cs.CR) ,computer ,computer.programming_language - Abstract
Side channels pose a significant threat to the confidentiality of software systems. Such vulnerabilities are challenging to detect and evaluate because they arise from non-functional properties of software such as execution times and require reasoning on multiple execution traces. Recently, noninterference notions have been adapted in static analysis, symbolic execution, and greybox fuzzing techniques. However, noninterference is a strict notion and may reject security even if the strength of information leaks are weak. A quantitative notion of security allows for the relaxation of noninterference and tolerates small (unavoidable) leaks. Despite progress in recent years, the existing quantitative approaches have scalability limitations in practice. In this work, we present QFuzz, a greybox fuzzing technique to quantitatively evaluate the strength of side channels with a focus on min entropy. Min entropy is a measure based on the number of distinguishable observations (partitions) to assess the resulting threat from an attacker who tries to compromise secrets in one try. We develop a novel greybox fuzzing equipped with two partitioning algorithms that try to maximize the number of distinguishable observations and the cost differences between them. We evaluate QFuzz on a large set of benchmarks from existing work and real-world libraries (with a total of 70 subjects). QFuzz compares favorably to three state-of-the-art detection techniques. QFuzz provides quantitative information about leaks beyond the capabilities of all three techniques. Crucially, we compare QFuzz to a state-of-the-art quantification tool and find that QFuzz significantly outperforms the tool in scalability while maintaining similar precision. Overall, we find that our approach scales well for real-world applications and provides useful information to evaluate resulting threats. Additionally, QFuzz identifies a zero-day side-channel vulnerability in a security critical Java library that has since been confirmed and fixed by the developers.
- Published
- 2021
40. Towards a Hybrid Approach to Protect Against Memory Safety Vulnerabilities
- Author
-
Fedor Shmarov, Kaled Alshamrany, Konstantin Korovin, Mustafa A. Mustafa, Pierre Olivier, Lucas C. Cordeiro, Giles Reger, Tom Melham, and Ahmed Bhayat
- Subjects
Model checking ,Computer science ,business.industry ,Runtime verification ,Memory corruption ,Static analysis ,computer.software_genre ,Symbolic execution ,Embedded system ,Instrumentation (computer programming) ,Compiler ,business ,Memory safety ,computer - Abstract
Memory corruption bugs continue to plague low-level systems software generally written in unsafe programming languages. In order to detect and protect against such exploits, many pre- and post-deployment techniques exist. In this position paper, we propose and motivate the need for a hybrid approach for the protection against memory safety vulnerabilities, combining techniques that can identify the presence (and absence) of vulnerabilities pre-deployment with those that can detect and mitigate such vulnerabilities post-deployment. Our hybrid approach involves three layers: hardware runtime protection provided by capability hardware, software runtime protection provided by compiler instrumentation, and static analysis provided by bounded model checking and symbolic execution. The key aspect of the proposed hybrid approach is that the protection offered is greater than the sum of its parts -- the expense of post-deployment runtime checks is reduced via information obtained during pre-deployment analysis. During pre-deployment analysis, static checking can be guided by runtime information.
- Published
- 2021
41. Vulnerability Detection Algorithm of Lightweight Linux Internet of Things Application with Symbolic Execution Method
- Author
-
Lili Zhou, Hafsah Taha, Mingming Xing, and Li Hongrui
- Subjects
Computer science ,business.industry ,media_common.quotation_subject ,computer.file_format ,Symbolic execution ,Encryption ,Debugging ,Robustness (computer science) ,Vulnerability assessment ,Executable ,business ,Algorithm ,computer ,Vulnerability (computing) ,media_common ,Buffer overflow - Abstract
The security of Internet of Things (IoT) devices has become a matter of great concern in recent years. The existence of security holes in the executable programs in the IoT devices has resulted in difficult to estimate security risks. For a long time, vulnerability detection is mainly completed by manual debugging and analysis, and the detection efficiency is low and the accuracy is difficult to guarantee. In this paper, the mainstream automated vulnerability analysis methods in recent years are studied, and a vulnerability detection algorithm based on symbol execution is presented. The detection algorithm is suitable for lightweight applications in small and medium-sized IoT devices. It realizes three functions: buffer overflow vulnerability detection, encryption reliability detection and protection state detection. The robustness of the detection algorithm was tested in the experiment, and the detection of overflow vulnerability program was completed within 2.75 seconds, and the detection of encryption reliability was completed within 1.79 seconds. Repeating the test with multiple sets of data showed a small difference of less than 6.4 milliseconds. The results show that the symbol execution detection algorithm presented in this paper has high detection efficiency and more robust accuracy and robustness.
- Published
- 2021
42. OCTOPOCS: Automatic Verification of Propagated Vulnerable Code Using Reformed Proofs of Concept
- Author
-
Seongkyeong Kwon, Seunghoon Woo, Gangmo Seong, and Heejo Lee
- Subjects
business.industry ,Computer science ,Vulnerability ,Crash ,Entry point ,Symbolic execution ,Mathematical proof ,Computer security ,computer.software_genre ,Taint checking ,Software ,Code (cryptography) ,business ,computer - Abstract
Addressing vulnerability propagation has become a major issue in software ecosystems. Existing approaches hold the promise of detecting widespread vulnerabilities but cannot be applied to verify effectively whether propagated vulnerable code still poses threats. We present OCTOPOCS, which uses a reformed Proof-of-Concept (PoC), to verify whether a vulnerability is propagated. Using context-aware taint analysis, OCTOPOCS extracts crash primitives (the parts used in the shared code area between the original vulnerable software and propagated software) from the original PoC. OCTOPOCS then utilizes directed symbolic execution to generate guiding inputs that direct the execution of the propagated software from the entry point to the shared code area. Thereafter, OCTOPOCS creates a new PoC by combining crash primitives and guiding inputs. It finally verifies the propagated vulnerability using the created PoC. We evaluated OCTOPOCS with 15 real-world C and C++ vulnerable software pairs, with results showing that OCTOPOCS successfully verified 14 propagated vulnerabilities.
- Published
- 2021
43. NFReducer: Redundant Logic Elimination for Network Functions with Runtime Configurations
- Author
-
Bangwen Deng and Wenfei Wu
- Subjects
Program analysis ,Noise measurement ,Semantics (computer science) ,Computer science ,business.industry ,Embedded system ,Packet processing ,Redundancy (engineering) ,Overhead (computing) ,business ,Symbolic execution ,Dead code elimination - Abstract
Network functions (NFs) are critical components in the network data plane. Their efficiency is important to the whole network's end-to-end performance. We identify three types of runtime redundant logic in individual NF and NF chains when they are deployed with concrete configured rules. We use program analysis techniques to optimize away the redundancy where we also overcome the NF specific challenges — we combine symbolic execution and dead code elimination to eliminate unused logic, we customize the common sub-expression elimination to eliminate duplicated logic, and we add network semantics to the dead code elimination to eliminate overwritten logic. We implement a prototype named NFReducer using LLVM. Our evaluation on both legacy and platform NFs shows that after eliminating the redundant logic, the packet processing rate of the NFs can be significantly improved and the operational overhead is small.
- Published
- 2021
44. On the Feasibility of Automated Built-in Function Modeling for PHP Symbolic Execution
- Author
-
Kangjie Lu, Changhua Luo, Wei Meng, and Penghui Li
- Subjects
Correctness ,Exploit ,business.industry ,Computer science ,Programming language ,media_common.quotation_subject ,Process (computing) ,020207 software engineering ,02 engineering and technology ,Symbolic execution ,computer.software_genre ,Task (computing) ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Web application ,business ,Function (engineering) ,Implementation ,computer ,media_common - Abstract
Symbolic execution has been widely applied in detecting vulnerabilities in web applications. Modeling language-specific built-in functions is essential for symbolic execution. Since built-in functions tend to be complicated and are typically implemented in low-level languages, a common strategy is to manually translate them into the SMT-LIB language for constraint solving. Such translation requires an excessive amount of human effort and deep understandings of the function behaviors. Incorrect translation can invalidate the final results. This problem aggravates in PHP applications because of their cross-language nature, i.e., , the built-in functions are written in C, but the rest code is in PHP. In this paper, we explore the feasibility of automating the process of modeling PHP built-in functions for symbolic execution. We synthesize C programs by transforming the constraint solving task in PHP symbolic execution into a C-compliant format and integrating them with C implementations of the built-in functions. We apply symbolic execution on the synthesized C program to find a feasible path, which gives a solution that can be applied to the original PHP constraints. In this way, we automate the modeling of built-in functions in PHP applications. We thoroughly compare our automated method with the state-of-the-art manual modeling tool. The evaluation results demonstrate that our automated method is more accurate with a higher function coverage, and can exploit a similar number of vulnerabilities. Our empirical analysis also shows that the manual and automated methods have different strengths, which complement each other in certain scenarios. Therefore, the best practice is to combine both of them to optimize the accuracy, correctness, and coverage of symbolic execution.
- Published
- 2021
45. Vulnerabilities Detection via Static Taint Analysis
- Author
-
Nikita Vladimirovitch Chimtchik and Valery Nikolaevitch Ignatiev
- Subjects
business.industry ,Computer science ,Static program analysis ,уязвимости ,Symbolic execution ,computer.software_genre ,анализ помеченных данных ,lcsh:QA75.5-76.95 ,Variety (cybernetics) ,Taint checking ,Software ,Distributive property ,Test suite ,Code (cryptography) ,General Earth and Planetary Sciences ,Data mining ,lcsh:Electronic computers. Computer science ,business ,статический анализ кода ,computer ,General Environmental Science - Abstract
Due to huge amounts of code in modern software products, there is always a variety of subtle errors or flaws in programs, which are hard to discover during everyday use or through conventional testing. A lot of such errors could be used as a potential attack vector if they could be exploited by a remote user via manipulation of program input. This paper presents the approach for automatic detection of security vulnerabilities using interprocedural static taint analysis. The goal of this study is to develop the infrastructure for taint analysis applicable for detection of vulnerabilities in C and C++ programs and extensible with separate detectors. This tool is based on the Interprocedural Finite Distributive Subset (IFDS) algorithm and is able to perform interprocedural, context-sensitive, path-insensitive analysis of programs represented in LLVM form. According to our research it is not possible to achieve good results using pure taint analysis, so together with several enhancements of existing techniques we propose to supplement it with additional static symbolic execution based analysis stage, which has path-sensitivity and considers memory region sizes for filtering results found by the first stage. The evaluation of results was made on Juliet Test Suite and open-source projects with publicly known vulnerabilities from CVE database.
- Published
- 2019
46. Implementation of an effective dynamic concolic execution framework for analyzing binary programs
- Author
-
Peng Wen, Erzhou Zhu, Ruhui Ma, and Kanqi Ni
- Subjects
Source code ,General Computer Science ,business.industry ,Computer science ,media_common.quotation_subject ,020206 networking & telecommunications ,02 engineering and technology ,computer.file_format ,Symbolic execution ,Software ,Computer engineering ,0202 electrical engineering, electronic engineering, information engineering ,Program slicing ,x86 ,020201 artificial intelligence & image processing ,State (computer science) ,Executable ,business ,Law ,computer ,Buffer overflow ,Vulnerability (computing) ,media_common - Abstract
With the increasing availability of the computational power and constraint solving technology, the symbolic execution technology has regained interest in recent years. However, it still suffers from state explosion and low efficiency issues due to the large number of paths that need to be analyzed and the complexity of the constraints generated. Meanwhile, most of the present symbolic execution techniques are working on the source code, but the source code of most software is hard to acquire in practice. In order to cope with these issues, this paper presents BinSE, a lightweight dynamic symbolic execution framework for analyzing x86 binary programs. The framework adapts the dynamic analysis model, which combines symbolic execution with concrete execution to simplify the complexity of the path conditions. Furthermore, the hierarchical backward program slicing and the revised irrelevant API filtration mechanisms are introduced to optimize the performance of the framework. According to the experimental results, the proposed framework is efficient and can cover almost all the effective paths of the target program. Meanwhile, it also holds a promise to provide novel solutions to a broad spectrum of security problems. To demonstrate our technique, we apply the framework to detect buffer overflow vulnerability from binary executables.
- Published
- 2019
47. Unit Test Data Generation for C Using Rule-Directed Symbolic Execution
- Author
-
Ming-Zhe Zhang, Yawen Wang, Dahai Jin, and Yunzhan Gong
- Subjects
Unit testing ,Theoretical computer science ,Computer science ,business.industry ,Test data generation ,media_common.quotation_subject ,Software development ,020207 software engineering ,02 engineering and technology ,Symbolic execution ,Computer Science Applications ,Theoretical Computer Science ,Computational Theory and Mathematics ,Hardware and Architecture ,Theory of computation ,0202 electrical engineering, electronic engineering, information engineering ,Unreachable code ,Function (engineering) ,business ,Software ,media_common ,Test data - Abstract
Unit testing is widely used in software development. One important activity in unit testing is automatic test data generation. Constraint-based test data generation is a technique for automatic generation of test data, which uses symbolic execution to generate constraints. Unit testing only tests functions instead of the whole program, where individual functions typically have preconditions imposed on their inputs. Conventional symbolic execution cannot detect these preconditions, let alone converting these preconditions into constraints. To overcome these limitations, we propose a novel unit test data generation approach using rule-directed symbolic execution for dealing with functions with missing input preconditions. Rule-directed symbolic execution uses predefined rules to detect preconditions in the individual function, and generates constraints for inputs based on preconditions. We introduce implicit constraints to represent preconditions, and unify implicit constraints and program constraints into integrated constraints. Test data generated based on integrated constraints can explore previously unreachable code and help developers find more functional faults and logical faults. We have implemented our approach in a tool called CTS-IC, and applied it to real-world projects. The experimental results show that rule-directed symbolic execution can find preconditions (implicit constraints) automatically from an individual function. Moreover, the unit test data generated by our approach achieves higher coverage than similar tools and efficiently mitigates missing input preconditions problems in unit testing for individual functions.
- Published
- 2019
48. A synergistic approach to improving symbolic execution using test ranges
- Author
-
Guowei Yang, Corina S. Păsăreanu, Rui Qiu, Junye Wen, and Sarfraz Khurshid
- Subjects
Computer Applications ,Computer science ,business.industry ,Suite ,020207 software engineering ,02 engineering and technology ,Reuse ,Symbolic execution ,Bottleneck ,Constraint (information theory) ,020204 information systems ,Encoding (memory) ,0202 electrical engineering, electronic engineering, information engineering ,Key (cryptography) ,Software engineering ,business ,Software - Abstract
Symbolic execution is a systematic technique for checking programs, which has received a lot of research attention during the last decade. In principle, symbolic execution provides a powerful analysis for bug finding. In practice however, the technique remains computationally expensive and hard to scale. This paper introduces SynergiSE, a novel synergistic approach to improving symbolic execution by tackling a key bottleneck to its wider adoption: costly and incomplete constraint solving. To mitigate the cost, SynergiSE introduces a succinct encoding of constraint solving results, thereby enabling symbolic execution to be distributed among different workers while sharing and reusing constraint solving results among them without having to communicate databases of constraint solving results. To mitigate the incompleteness, SynergiSE introduces an integration of complementary approaches for testing, e.g., search-based test generation, with symbolic execution, thereby enabling symbolic execution and other techniques to apply in tandem, say to create higher-quality tests. Experimental results using a suite of Java programs show that SynergiSE presents a promising approach for improving symbolic execution.
- Published
- 2019
49. A dynamic approach to detecting, eliminating and fixing memory leaks
- Author
-
Bin Yu, Cong Tian, Nan Zhang, Hongwei Du, and Zhenhua Duan
- Subjects
Leak ,021103 operations research ,Control and Optimization ,Computer science ,business.industry ,Applied Mathematics ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,Symbolic execution ,01 natural sciences ,Computer Science Applications ,Memory leak ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Virtual machine ,Embedded system ,Theory of computation ,Discrete Mathematics and Combinatorics ,Compiler ,business ,computer - Abstract
This paper presents a dynamic approach to detecting, eliminating and fixing memory leaks. With our approach, a program to be analyzed is instrumented before its execution. Dynamic symbolic execution is employed so as to expose memory leaks occurring in all execution paths. During the program execution, information about each allocated memory area is updated when corresponding statements are executed. Based on this information, a back-end leak checker records the changes of variables pointing to each memory area, detects memory leaks and deallocates leaked memory areas. After the program execution, a fixed program containing deallocation statements is generated. We have implemented our approach in a tool called DEF_LEAK based on Low Level Virtual Machine compiler infrastructure. Experiments show that DEF_LEAK can detect more leaks than the existing dynamic detection tools for programs with user inputs. Moreover, DEF_LEAK is more effective for helping programmers understand and fix memory leaks than other detection tools.
- Published
- 2019
50. Quantifying the Information Leakage in Cache Attacks via Symbolic Execution
- Author
-
Moritz Beck, Andreas Zeller, Sudipta Chattopadhyay, and Ahmed Rezine
- Subjects
Hardware_MEMORYSTRUCTURES ,Computer science ,business.industry ,Cache attack ,020207 software engineering ,02 engineering and technology ,Symbolic execution ,020202 computer hardware & architecture ,Hardware and Architecture ,Information leakage ,0202 electrical engineering, electronic engineering, information engineering ,Binary code ,Cache ,Side channel attack ,business ,Software ,Computer network - Abstract
Cache attacks allow attackers to infer the properties of a secret execution by observing cache hits and misses. But how much information can actually leak through such attacks? For a given program, a cache model, and an input, our CHALICE framework leverages symbolic execution to compute the amount of information that can possibly leak through cache attacks. At the core of CHALICE is a novel approach to quantify information leakage that can highlight critical cache side-channel leakage on arbitrary binary code. In our evaluation on real-world programs from OpenSSL and Linux GDK libraries, CHALICE effectively quantifies information leakage: For an AES-128 implementation on Linux, for instance, CHALICE finds that a cache attack can leak as much as 127 out of 128 bits of the encryption key.
- Published
- 2019
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.