When a computer system is hacked, analyzing the root-cause (for example entry-point of penetration) is a diagnostic process. An audit trail, as defined in the National Information Assurance Glossary, is a securityrelevant chronological (set of) record(s), and/or destination and source of records that provide evidence of the sequence of activities that have affected, at any time, a specific operation, procedure, or event. After detecting an intrusion, system administrators manually analyze audit trails to both isolate the root-cause and perform damage impact assessment of the attack. Due to the sheer volume of information and low-level activities in the audit trails, this task is rather cumbersome and time intensive. In this position paper, we discuss our ideas to automate the analysis of audit trails using machine learning and model-based reasoning techniques. Our approach classifies audit trails into the high-level activities they represent, and then reasons about those activities and their threat potential in real-time and forensically. We argue that, by using the outcome of this reasoning to explain complex evidence of malicious behavior, we are equipping system administrators with the proper tools to promptly react to, stop, and mitigate attacks. Today, enterprise system and network behaviors are typically “opaque”: stakeholders lack the ability to assert causal linkages in running code, except in very simple cases. At best, event logs and audit trails can offer some partial information on temporally and spatially localized events as seen from the viewpoint of individual applications. Thus current techniques give operators little system-wide situational awareness, nor any viewpoint informed by a long-term perspective. Adversaries have taken advantage of this opacity by adopting a strategy of persistent, low-observability operation from inside the system, hiding effectively through the use of long causal chains of system and application code. We call such adversaries advanced persistent threats, or APTs.
To address current limitations, this position paper discusses a technique that aims to track causality across the enterprise and over extended periods of time, identify subtle causal chains that represent malicious behavior, localize the code at the roots of such behavior, trace the effects of other malicious actions descended from those roots, and make recommendations on how to mitigate those effects. By doing so, the proposed approach aims to enable stakeholders to understand and manage the activities going on in their networks. The technique exploits both current and novel forms of local causality to construct higher-level observations, long-term causality in system information flow. We propose to use a machine learning approach to classify segments of low-level events by the activities they represent, and reasons over these activities, prioritizing candidate activities for investigation. The diagnostic engine investigates these candidates looking for patterns that may represent the presence of APTs. Using pre-defined security policies and related mitigations, the approach explains discovered APTs and recommends appropriate mitigations to operators. We plan to leverage models of APT and normal business logic behavior to diagnose such threats. Note that the technique is not constrained by availability of human analysts, but can benefit by human-onthe-loop assistance.
The approach discussed in the paper will offer unprecedented capability for observation of long-term, subtle system-wide activity by automatically constructing such global, long-term causality observations. The ability to automatically classify causal chains of events in terms of abstractions such as activities, will provide operators with a unique capability to orient to long-term, system-wide evidence of possible threats. The diagnostic engine will provide a unique capability to identify whether groups of such activities likely represent active threats, making it easier for operators to decide whether long-term threats are active, and where they originate, even before those threats are identified by other means. Thus, the approach will pave the way for the first automated, longhorizon, continuously operating system-wide support for an effective defender Observe, Orient, Decide, and Act (OODA) loop. 2
The methods proposed in this article are illustrated on a realistic running example. The attackers in this example use sophisticated and recently discovered exploits to gain access to the victim’s resources. The attack is remote and does not require social engineering or opening a malicious email attachment. The methods that we propose, however, are not limited to this class of attacks. router hacker
Internet victim’s local network web server front-end data storage back end
system administrator
The network topology used for our running example is shown in figure 1. The attack is executed over several days. It starts by (1) compromising the web server front-end, followed by (2) a reconnaissance phase and (3) compromising the data storage back end and ultimately extracting and modifying sensitive information belonging to the victim.
Both the front-end and the back end in this example run unpatched UBUNTU 13.1 LINUX OS on an INTEL R SANDY BRIDGETM architecture.
What follows is a detailed chronology of the events: 1. The attacker uses the APACHE httpd server, a cgi-bin script, and the SHELLSHOCK vulnerability (GNU bash exploit registered in the Common Vulnerabilities and Exposures database as CVE 2014-6271 (see https://nvd.nist. gov/) to gain remote shell access to the victim’s front-end. It is now possible for the attacker to execute processes on the front-end as the nonprivileged user www-data. 2. The attacker notices that the front-end is running an unpatched UBUNTU LINUX OS version 13.1. The attacker uses the nc Linux utility to copy an exploit for obtaining root privileges. The particular exploit that the attacker uses utilizes the x32 recvmmsg() kernel vulnerability registered in the Common Vulnerabilities and Exposures (CVE) database as CVE 2014-0038. After running the copied binary for a few minutes the attacker gains root access to the front-end host. 3. The attacker installs a root-kit utility that intercepts all input to ssh; 4. A system administrator uses the compromised ssh to connect to the back-end revealing his backend password to the attacker; 5. The attacker uses the compromised front-end to bypass firewalls and uses the newly acquired back-end administrator’s password to access the back-end; 6. The attacker uses a file-tree traversing utility on the back-end that collects sensitive data and consolidates it in an archive file; 7. The attacker sends the archive file to a third-party hijacked computer for analysis. 3
Almost all computing systems of sufficiently highlevel (with the exception of some embedded systems) leave detailed logs of all system and application activities. Many UNIX variants such as LINUX log via the syslog daemon, while WINDOWSTM uses the event log service. In addition to the usual logging mechanisms, there is a multitude of projects related to secure and detailed auditing. An audit log is more detailed trail of any security or computation-related activity such as file or RAM access, system calls, etc.
Depending on the level of security we would like to provide, there are several methods for collecting input security-related information. On one extreme, it is possible to use the existing log files. On the other extreme there are applications for collecting detailed information about the application execution. One such approach [1] runs the processes of interest through a debugger and logs every memory read and write access.
It is also possible to automatically inject logging calls in the source files before compiling them, allowing us to have static or dynamic logging or a combination of the two. Log and audit information can be signed, encrypted and sent in real-time to a remote server to make system tampering and activity-hiding more difficult. All these configuration decisions impose different trade-offs in security versus computational and RAM load [2] and depend on the organizational context. front_end.secure_access_log:11.239.64.213 - [22/Apr/2014 06:30:24 +0200] "GET /cgi-bin/test.cgi HTTP/1.1" 401 381 front_end.rsyslogd.log:recvmsg(3, msg_name(0) = NULL, msg_iov(1) = ["29/Apr/2014 22:15:49 ...", 8096], msg_controllen = 0, msg_flags = MSG_CTRUNC, MSG_DONTWAIT) = 29 back_end:auditctl:type = SYSCALL msg = audit(1310392408.506:36): arch = c000003e syscall = 2 success = yes exit = 3 a0 = 7fff2ce9471d a1 = 0 a2 = 61f768 a3 = 7fff2ce92a20 items = 1 ppid = 20478 pid = 21013 auid = 1000 uid = 0 gid = 0 euid = 0 suid = 0 fsuid = 0 egid = 0 sgid = 0 fsgid = 0 ses = 1 comm = "grep" exe = "/bin/grep" . . . abstractions may be composed of lower-order abstractions that are in turn abstractions of low-level events. For example, a sequential set of logged events such as ‘browser forking bash’, ‘bash initiating Netcat’, and ‘Netcat listening to new port’, might be abstracted as the activity ‘remote shell access’. The set of activities, ‘remote shell access’, and ‘escalation of privilege’ can be abstracted as the activity ‘remote root shell access’.
We approach activity annotation as a supervised learning problem that uses classification techniques to generate activity tags for audit trails. Table 1 shows multiple levels of activity classifications for the above APT example.
To obtain several layers of abstraction for reasoning over, and thus reduce overall error in classification, we use a multi-level learning strategy that models information at multiple levels of semantic abstraction using multiple classifiers. Each classifier solves the problem at one abstraction level, by mapping from a lower-level (fine) feature space to the next higher-level conceptual (coarse) feature space.
The activity classifier rely on both a vocabulary of activities and a library of patterns describing these activities that will be initially defined manually. This vocabulary and pattern set reside in a Knowledge Base.
In our training approach, results from training lower level classifiers are used as training data for higher level classifiers. In this way, we coherently train all classifiers by preventing higher-level classifiers from being trained with patterns that will never be generated by their lower-level precursors. We use an ensemble learning approach to achieve accurate classification. This involves stacking together both bagged and boosted models to reduce both variance and bias error components [3]. The classification algorithm will be trained using an online-learning technique and integrated within an Active Learning Framework to improve classification of atypical behaviors.
Generating Training Data for Classification To build the initial classifier, training data is generated using two methods. First, an actual deployed system is used to collect normal behavior data, and a Subject Matter Expert manually labels it. Second, a testing platform is used to generate data in a controlled environment, particularly platform dependent vulnerability-related behavior. In addition, to generate new training data of previously unknown behavior, we use an Active Learning framework as described in Section 5. As the Activity Classifier annotates audit trails with activity descriptors, the two (parallel) next steps in our workflow are to 1) prioritize potential threats to be referred to the Diagnostic Engine (see Section 6) for investigation, and 2) prioritize emergent activities that (after suitable review and labeling) are added to the activity classifier training data. This module prioritizes activities by threat severity and confidence level . This prioritization process presents three key challenges. One challenge in ranking activities according to their threat potential is the complex (and dynamic) notion of what constitutes a threat. Rankings based on matching to known prior threats is necessary, but not sufficient. An ideal ranking approach should take known threats into account, while also proactively considering the unknown threat potential of new kinds of activities. Another such challenge is that risk may be assessed at various levels of activity abstraction, requiring that overall ranking must be computed by aggregating risk assessments at multiple abstraction levels.
We implement two ranking approaches: a supervised ranker based on previously known threats and an unsupervised ranker that considers unknown potential threats.
Supervised ranking using APT classification to catch known threats. The goal of APT classification is to provide the diagnostic engine with critical APT related information such as APT Phase, severity of attack, and confidence level associated with APT tagging for threat prioritization. Since the audit trails are annotated hierarchically into different granularity of actions, multiple classifiers will be built to consider each hierarchical level separately. APT classifiers are used to identify entities that are likely to be instances of known threats or phases of an APT attack. Two types of classifiers are used. The first classifier is hand-coded and the second classifier is learned from training data.
The hand-coded classifier is designed to have high precision, using hand-coded rules, mirroring SIEM and IDS systems. Entities tagged by this classifier are given the highest priority for investigation. The second classifier, which is learned from training data, will provide higher recall at the cost of precision. Activities are ranked according to their threat level by aggregating a severity measure (determined by classified threat type) and a confidence measure. We complement the initial set of training data to calibrate our classifiers by using an Active Learning Framework, which focuses on improving the classification algorithm through occasional manual labeling of the most critical activities in the audit trails.
Unsupervised ranking using normalcy characterization to catch unknown threats. The second component of the prioritizer is a set of unsupervised normalcy rankers, which rank entities based on their statistical “normalcy". Activities identified as unusual will be fed to the Active Learning framework to check if any of them are “unknown” APT activities. This provides a mechanism for detecting “unknown” threats while also providing feedback to improve the APT classifier. 5.2
One of the key issues with combining the outputs of
multiple risk ranking is dealing with two-dimensional
risk (severity, confidence) scores that may be on very
different scales. A diverse set of score normalization
techniques have been proposed [4; 5; 6] to deal with
this issue, but no single technique has been found to
be superior over all the others. An alternative to
combining scores is to combine rankings [
We will develop combination techniques for
weighted risk rankings based on probabilistic rank
aggregation methods. This approach builds on our own
work [
Traditionally, the goal of rank aggregation [9; 10] is to combine a set of rankings of the same candidates into a single consensus ranking that is “better” than the individual rankings. We extend the traditional approach to accommodate the specific context of weighted risk ranking. First, unreliable rankers will be identified and either ignored or down-weighted, lest their rankings decrease the quality of the overall consensus [7; 10]. Second, we will discount excessive correlation among rankers, so that a set of 4 highly redundant rankers do not completely outweigh the contribution of other alternative rankings. To address these two issues, we will associate a probabilistic latent variable Zi with the i’th entity of interest, which indicates whether the entity is anomalous or normal. Then, we will build a probabilistic model that allows us to infer the posterior distribution over the Zi based on the observed rankings produced by each of the input weighted risk rankings. This posterior probability of Zi being normal will then be used as the weighted risk rank. Our model will make the following assumptions to account for both unreliable and correlated rankers: 1) Anomalies are ranked lower than all normal instances and these ranks tend to be concentrated near the lower rankings of the provided weighted risk rankings, and 2) Normal data instances tend to be uniformly distributed near the higher rankings of the weighted risk rankings.
There are various ways to build a probabilistic
model that reflects the above assumptions and
allows for the inference of the Zi variables through
Expectation-Maximization [
We view the problem of detecting, isolating, and
explaining complex APT campaigns behavior from rich
activity data is a diagnostic problem. We will use
an AI-based diagnostic reasoning to guide the global
search for possible vulnerabilities that enabled the
breach. Model-based diagnosis (MBD) [
Attack detection and isolation are two distinct
challenges. Often diagnostic approaches use separate
models for detection and isolation [
The diagnostic approach takes into consideration
the bootstrapping of an APT which we consider the
root-cause of the attack. What enables a successful
APT is either a combination of software component
5
vulnerabilities or the combined use of social
engineering and insufficiency of the organizational security
policies. We use MBD for computing the set of
simultaneously exploited vulnerabilities that allowed the
deployment of the APT. Computing such explanations
is possible because MBD reasons in terms of
multiplefaults [
The abstract security model is used to gather
information about types of attacks the system is vulnerable
to, and to aid deciding the set of actions required to
stop an APT campaign (policy enforcement). Various
heuristics exist to find the set of meaningful diagnosis
candidates. As an example, one might be interested
in the minimal set of actions to stop the attack [15;
16] or select those candidates that capture significant
probability mass [
Data The abstract security model provides an abstraction mechanism that is originally missing in the audit trails. More precisely what is not in the audit trails and what is in the security model is how to connect (possibly disconnected) activities for the purpose of global reasoning. The abstract security model and the sensor data collected from the audit trails are provided as inputs to an MBD algorithms that performs the highlevel reasoning about possible vulnerabilities and attacks similar to what a human security officer would do.
The information in the “raw” audit trails is of too high fidelity [2] and low abstraction to be used by a “crude” security model. That is the reason the diagnostic engine needs the machine learning module to temporally and spatially group nodes in the audit trails and to provide semantically rich variable/value sensor data about actions, suitable for MBD. Notice that in this process, the audit trail structure is translated to semantic categories, i.e., the diagnostic engine receives as observations time-series of sensed actions.
The listing that follows next shows an abstract
security model for the running example in the LYDIA
language [
!leak_passwd; // passwords don’t leak if (! escalation_vuln ) { // if healthy
! root_shell ; // no root shell is possible bool access_passwd; attribute observable (access_passwd) = true ; bool httpd_shell_vuln ; // vulnerability bool buffer_overflow_vuln ; // vulnerability bool escalation_vuln ; // vulnerability // weak−fault models if (! httpd_shell_vuln ) { // if healthy
! httpd_shell ; // forbid shells via httpd /∗∗ ∗ Normal users can only communicate with a ∗ list of permitted hosts . ∗/ if (! know_root_password) {
comm == true; /∗∗ ∗ Knowing the root password can be explained ∗ by a root shell ( for example there is a ∗ password sniffer ). ∗/ know_root_password => (( httpd_shell || leak_passwd) && root_shell ); system front_end fe (know_root_password); system back_end be(know_root_password);
LYDIA translates the model to an internal
propositional logic formula. Part of this internal
representation is shown in figure 3, which uses the standard VLSI
[
httpd shell leak pw1 buffer overflow vuln1 know root password root shell 2p 2q 2r
>
Legend:
1assumable variable
2internal variable
rity constraints in it is notoriously difficult, hence we
plan to create or use specialized modal logic similar to
the one proposed in [
Notice that the format of the Boolean circuit shown
in figure 3 is very close to the one used in Truth
Maintenance System (TMS) [
We next show how a reasoning engine can discover a conflict through forward and backward propagation. Looking at figure 3, it is clear that r must be true because it is an input to an AND-gate whose output is set to true. Therefore either p or q (or both) must be true. This means that either buffer_overflow_vuln or leak_pw must be false. If we say that leak_pw is assumed to be true (measured or otherwise inferred), then leak_pw and buffer_overflow_vuln are together part of a conflict. It means that the reasoning engine has to change one of them to resolve the contradiction.
Based on the observation from our running example and a TMS constructed from the security model shown in figure 3, the hitting set algorithm computes two possible diagnostic hypotheses: (1) the attacker gained a shell access through a web-server vulnerability and the attacker performed privilege escalation or (2) the attacker injected binary code through a buffer overflow and the attacker performed privilege escalation.
If we use LYDIA to compute the set of diagnoses for the running example, we get the following two (ambiguous) diagnoses for the root-cause of the penetration: $ lydia example.lm example.obs d1 = { fe.escalation_vuln,
fe.httpd_shell_vuln } d2 = { fe.buffer_overflow_vuln, fe.escalation_vuln }
MBD uses probabilities to computes a sequence of possible diagnoses ordered by likelihood. This probability can be used for many purposes: decide which diagnosis is more likely to be the true fault explanation, whether there is the need for consider further evidence from the logs or limit the number of diagnoses that need to be identified. Many policies exist to compute these probabilities [27; 28].
For illustration purposes we consider that the diagnoses for the running example are ambiguous. Before we discuss methods for dealing with this ambiguity, we address the major research challenge of model generation. 6.3
The abstract vulnerability model can either be constructed manually or semi-automatically. The challenge with modeling is that an APT campaign generally exploits unknown vulnerabilities. Therefore, our approach to address this issue is to construct the model which captures expected behavior (known goods) of the system. Starting from generic parameterized vulnerability models and security objectives, the abstract vulnerability model can be extended with information related to known vulnerabilities (known bads).
Generating the model can be done either manually or semi-automatically. We will explore venues to generate this model manually, which requires significant knowledge about potential security vulnerabilities, while being error prone and not detailed enough. Amongst company specific requirements, we envisage the abstract vulnerability model to capture the most common attacks that target software systems, as described in the Common Attack Pattern Enumeration and Classification (CAPEC1). The comprehensive list of known attacks has been designed to better understand the perspective of an attacker exploiting the vulnerabilities and, from this knowledge, devise appropriate defenses.
As modeling is challenging, we propose to explore semi-automatic approaches to construct models. The semi-automatic method is suitable to addressing the modeling because in security, similarly to diagnosis, there is (1) component models and (2) structure. While it is difficult to automate the building of component models (this may even require natural language parsing of databases such as CAPEC), it is feasible to capture diagnosis-oriented information from structure (physical networking or network communication).
Yet another approach to semi-automatically
generate the model is to learn it from executions of the
system (e.g., during regression testing, just before
deployment). This approach to system modeling is
inspired by the work in automatic software
debugging work [
The outlined approaches to construct the abstract vulnerability model entail different costs and diagnostic accuracies. As expected, manually building the model is the most expensive one. Note that building the model is a time-consuming and error-prone task. The two semi-automatic ways also entail different costs: one exploits the available, static information and the other requires the system to be executed to compute a meaningful set of executions. We will investigate the trade-offs between modeling approaches and their diagnostic accuracy in the context of transparent computing. 7
Identifying the root-cause and perform damage impact assessment of advanced persistent threats can be framed as a diagnostic problem. In this paper, we discuss an approach that leverages machine learning and model-based diagnosis techniques to reason about potential attacks.
Our approach classifies audit trails into high-level activities, and then reasons about those activities and their threat potential in real-time and forensically. By using the outcome of this reasoning to explain complex evi- dence of malicious behavior, the system administrators is provided with the proper tools to promptly react to, stop, and mitigate attacks.