DESIGN, IMPLEMENTATION AND EVALUATION OF A SYMBOLIC N-VARIANT SIMULATOR

Abstract

Artificial diversity is an approach aims to increase the cost for attackers to compromise software systems by randomizing implementation properties of software. However, its protection depends heavily on maintaining secrecy. N-variant system addresses this problem by executing a set of diversified software variants on the same input, and monitors their behaviors to detect divergence. It exhibits appealing security properties of high assurance detection for certain class of attacks without relying on secrets. However, requiring large amount of extra computing resources and extra time hampers its practicality in real world scenarios.

In this thesis^[1] , we focus on reducing the cost for deploying N-variant system, yet still maintaining its security advantages. As a popular program analysis and testing technique, symbolic execution characterizes program input and the part of program which the input causes to execute. We observe that such characterization can be used to simulate actual program execution efficiently. Based on this observation, we propose a symbolic N-variant system framework as a new approach to build N-variant system. After introducing artificial divergences to software, we symbolic execute each application variants to generate program summaries. During runtime, instead of executing input in the real program, we simulate the execution in a symbolic N-variant simulator, and detect behavior divergences.

We build a prototype based on the proposed system framework. This thesis emphasizes on the design, implementation and evaluation of the symbolic N-variant simulator, as part of the whole system. We also evaluate the prototype in terms of run-time performance and resource consumption, and the effectiveness of detecting attacks of certain class.

[1] The thesis project is collaborated with Jun Xu (jxx13@psu.edu). Jun Xu is mainly responsible for the design and implementation of SAV Generator (Section 3.2.2) and security effectiveness evaluation (Section 6.2).

 

Chapter 1

Introduction

The commoditization of commercial computer systems brought homogeneity with respect to computer software, which simplifies the logistics of software distribution and maintenance, and provides software users with consistent behaviors [1] . However, the homogeneity provides convenience for adversaries around cyberspace as well. Using an identical exploit, an attacker can probe a vulnerability in one software copy, and target on millions of computers that run the same distribution. For instance, recently disclosed Heartbleed vulnerability in 2014 affects around 17% of SSL web servers which use OpenSSL cryptography library [2] , including major websites such as Amazon, Github, etc.

The risks of monoculture have been widely recognized in secure computing community [3] . The resilience nature provided by software diversity is gaining more attention in security research community. Recent research studied a set of promising strategies by introducingartificial diversity to software. Artificial diversity increases the difficulty and cost for attackers by introducing uncertainty into aspects of software implementation. Without the knowledge of specific implementation, time and energy required for attackers to breach the software increase significantly. Moreover, attackers are forced to target on specific software distribution individually, and thus, raise the bar for mass scale exploitation [1] .

In the past decade, several techniques for intentionally introducing software diversity have been developed, including address space layout randomization (ASLR)

Figure 1.1. Cox et al. N-Variant System Framework

[4, 5] , instruction set randomization [6, 7] , data structure layout randomization (DSLR) [8] , data randomization [9] , etc.

However, the effectiveness of artificial diversity relies heavily on keeping diversity method (how the diversity of the running execution of the particular software is generated) as secret to attackers. Otherwise, attackers can craft customized malicious input for the software variant. Recent discovered location inference side channels [10, 11] show that the secret can be compromised by ROP attacks.

To mitigate this problem, Cox et al. [12] propose an N-variant system framework as shown in Figure 1.1. In the N-variant system, a polygrapher replicates external program input into different artificially diversified application variants. A monitor collects behaviors from each variant and detects divergences which reveal attacks. The assumption behind this framework is that: there must exist an execution pathway in one variant that exploits a vulnerability without producing anomalous behaviors in other variants. That is, as long as no single malicious input can simultaneously compromise all the variants, attacks could be detected, although every variant might be vulnerable. This framework shows appealing security advantages:

• The framework requires no secret keeping. Even if an attacker has complete knowledge on the diversity key used in each software variant, attacks could be detected as long as no pathway as described above exists.
• By using some diversification techniques, the framework provides deterministic detection of attacks of certain class.

However, despite the security merits it offers, a dominant barrier for wide deployment of N-Variant systems is its inherent costly nature:

• The extra computing resources required for N-Variant system is N times greater than the original software system to be protected.
• The performance for malicious input detection must be slower than an execution in the original software system, since it requires a synchronization and synopsis phase to detect divergences.

In this thesis, we focus on addressing the cost problem for N-Variant system using symbolic execution. As a program analysis and testing technique, symbolic execution can be used to characterize program input and the part of program which the input causes to execute. We make an observation that such characterization can serve as a program summary and be used to simulate actual program execution efficiently. Based on this observation, we propose a symbolic N-variant system, as a new approach to build N-variant system.

Instead of executing actual software variants with input, we execute the execution in symbolic variants. After introducing artificial divergences to software variants, we symbolic execute each program variants. The symbolic execution generates program summaries which consist of constraint predicates on input, and program behaviors along corresponding program part. With the program summaries of a variant, we build an innovative symbolic path search tree for this variant. During run-time, inputs are duplicated into different symbolic variants for simulation.

Monitor collects behavior from each variant and detect divergences.

Our key contributions are described as follows.

• We develop a novel symbolic execution based approach to build N-variant systems. To the best of the our knowledge, this work is the firstly designed applicable N-variant system.
• We implement a symbolic N-variant system prototype which consists of three parts: a server system, a symbolic application variants generator, and a symbolic N-variant simulator. The prototype is based on a commercial web server lighttpd and we target on a real vulnerability inside the program.
• We evaluate the prototype in terms of its efficiency and security effectiveness. The experiment results show that the average performance of our system is still much faster than the real server when 10 symbolic variants are concurrently working under saturated workload. Also, our prototype can detect attacks of certain class without raising false positive or negative.

This thesis is inspired by a collaborative research project. We mainly focus on describe the author’s contribution on the design, implementation and evaluation of a symbolic N-variant simulator. The rest of the thesis is organized as follows. In Chapter 2, we provide a more detailed description of N-variant system, formalize the problem definition, and describe the threat model used in this thesis. In Chapter 3, we present an overview for the system model and architecture of our symbolic N-variant system framework. In Chapter 4 , we present the design and implementation of a prototype symbolic N-variant simulator based on a popular application. We discuss some heuristics deployed in our design to speed up the simulation performance in Chapter 5. In Chapter 6, we evaluate the efficiency and security effectiveness of our prototype. We discuss some limitations and future work in Chapter 7, and offer some related work in Chapter 8. Chapter 9 concludes.

DESIGN, IMPLEMENTATION AND EVALUATION OF A SYMBOLIC N-VARIANT SIMULATOR

Sharing is caring!