Abstract
The immaturity of current intrusion detection techniques limits the traditional security systems in surviving malicious attacks. Intrusion tolerance approaches have emerged to overcome these vulnerabilities. Before intrusion tolerance is accepted as an approach to security, there must be quantitative techniques to measure its survivability. However, there are very few attempts to do quantitative, model-based evaluation of the survivability of intrusion tolerant systems, especially in database field. In this thesis, I focus on modeling the survivability of an intrusion tolerant database system in the presence of attacks.
Before studying the survivability of intrusion tolerant systems, we need to have a better understanding of the attack behavior and its degree of spreading. Based on the classical epidemic model, a stochastic database damage propagation model is proposed. This model leads to a better understanding and prediction of the scale and speed of database damage propagation.
To study the survivability, the intrusion tolerant database system is modeled as a series of state transition models. Based on the Continuous Time Markov Chain (CTMC) and semi-Markov models, quantitative measures are proposed to characterize the capability of a resilient database system surviving intrusions. These facilitate a systematic evaluation to capture the survivability of intrusion tolerant database systems and the impact of system deficiencies on it. An Intrusion Tolerant DataBase system (ITDB) is studied as an example.
CHAPTER 1 INTRODUCTION
1.1 RESEARCH PROBLEM
Database security concerns the confidentiality, integrity, and availability of information stored in a database. A broad span of research [4, 5, 6] addresses primarily how to protect thesecrecy of a database, namely its confidentiality. However, very limited research has been done on how to survive successful database attacks, which can seriously impair the integrity and availability of a database. Experience with data-intensive applications such as credit card billing, banking, and online stock trading, have shown that a variety of attacks do succeed to fool traditional database protection mechanisms. These attacks include but are not limited to malicious transactions through insider attacks, identity theft attacks, SQL injection attacks, and cross site scripting flaws [7] . In fact, we must recognize that not all attacks, even obvious ones, can be averted at their outset. Attacks that succeed, to some degree at least, are unavoidable. To remedy the limitations of database protection mechanisms, survivable database systems that can tolerate malicious attacks are getting increasingly important to data-intensive applications. Some intrusion tolerant database systems [8, 9] have been proposed recently, where in-depth defenses have been added to detect and respond to database intrusions.
However, despite that intrusion tolerance techniques, which gain impressive attention recently, are claimed to be able to enhance the system survivability, evaluation models are largely overlooked in the previous research. Quantifying survivability metrics of database systems are needed and important to meet the user requirements and compare different intrusion tolerant architectures. Efforts aimed at survivability evaluation have been based on classic reliability or availability models.
The present work is motivated by the limitations of existing criteria for reliability and availability to evaluate survivability. The evaluation criteria for system reliability and availability have a fairly matured literature as summarized in [10, 11] . As defined in [12] ,reliability is the probability that a system can perform a specified service throughout a specified interval of time. Availability is a quantification of the alternation between proper and improper service, and is often expressed as the fraction of time that a system can be used for its intended purpose during a specified interval of time or in steady state. Survivability refers to the capability of a system to complete its mission in a timely manner, even if significant portions are compromised by attacks or accidents [13] . However, the reliability and availability models cannot be used to quantify survivability of a security system. Aside from the differences between security and fault tolerance, a fundamental reason for this is the fact that the classic the availability model assumes “fail-stop” semantics, whereas “attack-stop” semantics probably can never be assumed in trustworthy data processing systems, not only because of the substantial detection latency, but also because of the need for degraded services.
The goal of this work is to take the first step toward development of a survivability evaluation model that can systematically address the inherent limitations of classic reliability and availability evaluation models in measuring survivability. The approach I proposed utilizes a state transition graph to model an intrusion tolerant database system.
I attempt to model the system in a modular way, so that it can be easily adapted to a wide variety of intrusion tolerant database systems. Quantitative measures are proposed to characterize the capability of a security database system surviving intrusions. Furthermore, I am interested in understanding the impact of existing system deficiencies, such as false positive, and attack behaviors on the survivability. In this thesis, I take the first steps toward performing a detailed, quantitative evaluation of the survivability of intrusion tolerant database system and assessing the impact of system deficiencies and attack behaviors on it.
1.2 CONTRIBUTION OF THIS STUDY
In particular, the main goals of this thesis are five-fold:
- Based the traditional epidemic model, a stochastic (Markovian) damage propagation model in continuous time is proposed. This model leads to a better understanding and prediction of the scale and speed of damage propagation in database system.
- Extending the classic availability model to a new survivability model. Comprehensive state-space approaches are applied to study the complex relationships and their transition structure encoding sequencing response of intrusion tolerant database systems facing attacks.
- Novel quantitative survivability evaluation metrics are proposed. Mean Time to Attack (MTTA), Mean Time to Detection (MTTD), Mean Time to Marking (MTTM), and Mean Time to Repair (MTTR) are proposed as basic measures
of survivability. I found that there is a natural mapping between the MTTAMTTD-MTTM-MTTR model and the steady state probabilities of the system in state transition modeling. This mapping not only provides valuable insights into why the MTTA-MTTD-MTTM-MTTR model can measure survivability, but also provides a convenient way to use mathematical analysis to quantify survivability. Based on the MTTA-MTTD-MTTM-MTTR model, this survivability measuring methodology is no longer ad hoc.
- In some real cases the attack and repair time are not exponentially distributed. Semi-Markov process has the advantage of allowing nonexponential distributions for transitions between states and to generalize several kinds of stochastic processes. I extended the CTMC models to semi-Markov process which can fit the real world
better.
- To validate the survivability model I proposed, a representative intrusion tolerant database system, ITDB [8] , is studied as an empirical example. A real testbed is established to conduct comprehensive validation experiments running TPC-C benchmark transactions. Experiment results show the validity of the survivability model.
- To further validate the security of ITDB, I have done an empirical survivability evaluation, where maximum-likelihood methods are applied to estimate the values of the parameters used in my state transition models. The impacts of existing system deficiencies and attack behaviors on the survivability are studied using quantitative measures I defined.
1.3 OUTLINE
The rest of the thesis is organized as follows. In Chapter 2, I overview related work. It discusses the existing intrusion tolerance systems, the security criteria, and evaluation techniques.
In Chapter 3, I give an overview of the ITDB framework. Four important components of ITDB, namely transaction proxy, attack recovery, damage quarantine, and intrusion detection subsystems, are introduced.
In Chapter 4, damage spreading phenomena in database is discussed. Based on the classical epidemic SIS model, a stochastic (Markovian) damage propagation model in continuous time is proposed.
In Chapter 5, a series of state transition models are proposed. The basic state transition model focuses on a general intrusion tolerant database system. In the intrusion detection system model, a comprehensive model of intrusion detection subsystem is integrated into the whole system. A comprehensive state transition model of ITDB is proposed in the end of this chapter.
In Chapter 6, quantitative measures are proposed to facilitate evaluating the survivability of intrusion tolerant database systems from several aspects. Mean Time to Attack (MTTA), Mean Time to Detection (MTTD), Mean Time to Marking (MTTM), and Mean Time to Repair (MTTR) are proposed as basic measures of survivability.
Instead of using some traditional metrics, two novel evaluation metrics, Integrity and Rewarding Availability, are proposed to quantify survivability. I also analyze the state models proposed in this chapter.
In Chapter 7, I extend the CTMC models to semi-Markov processes. Semi-Markov processes are able to allow nonexponential distributions for transitions between states and to generalize several kinds of stochastic processes. It is important to model the most real cases which do not follow exponential distribution.
In Chapter 8, a real testing environment is built to validate the proposed state transition models. TPC-c benchmark is chose as background transaction. A representative intrusion tolerant database system, ITDB, is implemented as an empirical example. Chapter 9 discusses the experiments conducted to validate the established models. I compare the steady state probabilities of my models with a set of measured ITDB
behaviors facing attacks.
Survivability and performance evaluation results are reported in Chapter 10. Instead of evaluating the performance of a specified system, I focus on the impact of different system deficiencies on the survivability in the face of attacks. Different detection deficiencies, such as false alarm rate, detection latency, and different workloads, such as attack rate are studied in this part.
I conclude my thesis in Chapter 11 where future work is also discussed.
MODELING AND EVALUATING THE SURVIVABILITY OF AN INTRUSION TOLERANT DATABASE SYSTEM