PaperlayerView exact revision on arXiv

Source-linked AI summary

SLEUTH: Real-time Attack Scenario Reconstruction from COTS Audit Data

Md Nahid Hossain, Sadegh M Milajerdi, Junao Wang, Birhanu Eshete, Rigel Gjomemo, R Sekar, Scott Stoller, VN Venkatakrishnan

arXiv:1801.02062v1cs.CR

TL;DR

SLEUTH tackles the problem of reconstructing enterprise attack scenarios from noisy COTS audit logs in real time. It uses a platform-neutral main-memory dependency graph, tag-based detection and reconstruction, and compact visual attack graphs. In a DARPA red-team evaluation across Windows, FreeBSD, and Linux, it successfully reconstructed attacks, while its evaluation scope excluded demonstrating detection of the most sophisticated adversary and its detection methods avoid detailed application-specific knowledge.

  • Problem

    Analysts need compact causal summaries to detect significant intrusions, identify breach points, and determine attack impact amid large, fragmented audit data.

  • Method

    SLEUTH represents multi-OS audit data as a platform-neutral main-memory dependency graph and applies tag-based detection, source identification, impact analysis, graph simplification, and customizable policies.

  • Results

    SLEUTH successfully detected and reconstructed red-team attacks on Windows, FreeBSD, and Linux, including their entry points, system activities, and exfiltration points.

  • Takeaways & Limitations

    SLEUTH provides real-time attack prioritization and compact scenario reconstruction from COTS audit logs without requiring detailed application-specific knowledge.

  • Takeaways & Limitations

    The evaluation was not intended to demonstrate detection of the most sophisticated adversary, and SLEUTH constrains detection methods to avoid detailed application-specific knowledge.

Abstract

from arXiv · show

We present an approach and system for real-time reconstruction of attack scenarios on an enterprise host. To meet the scalability and real-time needs of the problem, we develop a platform-neutral, main-memory based, dependency graph abstraction of audit-log data. We then present efficient, tag-based techniques for attack detection and reconstruction, including source identification and impact analysis. We also develop methods to reveal the big picture of attacks by construction of compact, visual graphs of attack steps. Our system participated in a red team evaluation organized by DARPA and was able to successfully detect and reconstruct the details of the red team's attacks on hosts running Windows, FreeBSD and Linux.

1 Introduction

SLEUTH addresses the difficulty of detecting and reconstructing long, multi-stage attacks from noisy audit data in real time. It combines a platform-neutral main-memory dependency graph, tag-based analysis, customizable policies, and compact visual summaries, and was evaluated across three operating systems.

  • 1 Introduction: Enterprise defenders face overwhelming security data and fragmented attack evidence, making significant campaigns difficult to distinguish and connect across applications or hosts.Analysts may need substantial manual effort and expertise, and some campaigns can remain undetected for weeks or months.
  • 1 Introduction: SLEUTH targets real-time event storage, entity prioritization, scenario reconstruction, benign-activity handling, and interactive reasoning about alternate attack hypotheses.These challenges include processing millions of records quickly, identifying likely attack entities, tracing entry points and impact, and distinguishing benign activities from attacks.
  • 1.1 Approach Overview and Contributions: SLEUTH converts Windows, Linux, and FreeBSD audit data into a platform-neutral graph whose vertices are subjects and objects and whose edges represent audit events.The graph supports attack detection, causality analysis, and scenario reconstruction.
  • 1.1 Approach Overview and Contributions: The system uses a compact main-memory dependence graph and tag-based algorithms for prioritization, source identification, impact analysis, and compact attack-graph construction.Backward dependency searches identify attack sources, while forward searches analyze adversary impact and pruning and transformation produce succinct visual graphs.
  • 1.1 Approach Overview and Contributions: Customizable policies initialize and propagate tags, tune detection for operating-system or application-specific benign behavior, and support alternate-hypothesis analysis.Policies can reclassify trustworthy or sensitive entities and rerun analysis to investigate suspected behavior, enabled by high processing speed.
  • 1.1 Approach Overview and Contributions: SLEUTH processed audit logs from DARPA red-team attacks on Windows, FreeBSD, and Linux, detecting and reconstructing attack details while filtering noise and maintaining low error rates.Reported outcomes include entry-point, system-activity, and exfiltration-point reconstruction, reductions of up to 100K times, and processing tens of millions of events in seconds.
  • 1.1 Approach Overview and Contributions: The evaluation was not intended to demonstrate detection of the most sophisticated adversary; it focused on prioritizing correct results in real time without human assistance.This scope contrasts with forensic analysis that is primarily initiated manually.

2 Main Memory Dependency Graph

SLEUTH uses a compact, platform-neutral dependency graph in main memory to support fast, bidirectional audit-data analysis at enterprise scale.

  • Main-memory graph storage addresses the performance and memory limits of general graph databases for real-time audit analysis.The paper contrasts roughly 10 bytes per edge with 250 bytes to 3KB for other graph systems.
  • The per-host graph represents processes as subjects, files, pipes, sockets, and connections as objects, with labeled audit events forming edges.Edges capture operations including read, connect, and execve, and the graph is optimized for intra-host references.
  • Events are compressed using variable-length encodings, compact identifiers, relative timestamps, and abbreviated object and event references.Typical subject-event records use 4 bytes, while frequent event names use 3 bits or less and object references use 8 bits or less.
  • The representation supports navigation from subjects to objects and from objects back to subjects by retaining selected dataflow events in both directions.Object-event records are maintained for events such as reads and writes, while non-dataflow events such as opens are omitted from objects.
  • Bidirectional timestamped edges require as little as 6 bytes, with average system memory use within 10 bytes per event.The design preserves full information for important rare events, while typical access times remain below 100ns.

3 Tags and Attack Detection

SLEUTH uses provenance-derived tags to prioritize attack-relevant entities and detect behavior involving suspicious data, code, and modifications.

  • Tags summarize trustworthiness and sensitivity using provenance, prior system knowledge, and observed subject behavior.
  • A conservative default policy propagates the lowest input trustworthiness and highest input confidentiality to outputs, favoring over-tainting over missed dependencies.
  • Tags accelerate detection, forward and backward analysis, and scenario reconstruction by eliminating technically dependent but uninformative audit data.
  • SLEUTH separates process code and data trustworthiness tags, which the paper reports improves detection and reduces reconstructed forensic scenarios.
  • SLEUTH focuses on attacker objectives and means, using unknown provenance tags to represent influence from untrusted sources.
  • Detection policies target untrusted code execution and lower-trust subjects modifying higher-trust objects.
  • The untrusted-code policy remains effective across intermediary downloads, extraction, compression, compilation, and later execution.
  • The untrusted-code execution policy does not detect the first step of typical vulnerability exploits, although later execution or permission changes can trigger detection.

4 Policy Framework

SLEUTH expresses tag initialization, propagation, and detection behavior through rule-based policies evaluated at event-specific trigger points.

  • Policies use event-associated conditions on names, tags, ownership, permissions, and subject or object attributes to produce alerts or modify tags.
  • Trigger points control policy ordering and allow policies to be shared across distinct events with similar purposes.
  • The framework uses a define pseudoevent when an object is first encountered, including new connections, preexisting files, and newly created files.
  • Detection policies run at alarm triggers, while tag-setting policies are tried in trigger order and stop after the first matching rule.
  • Initialization policies assign tags to new or first-mentioned objects, overriding default inheritance when specified.
  • Policies can override default propagation to prevent over-tainting, accommodate operating-system or application behavior, and test alternate attack hypotheses.
  • Trusted servers, installers, and verified software updaters are treated as cases where interactions with untrusted sites need not downgrade trustworthiness.

5 Tag-Based Bi-Directional Analysis

SLEUTH uses tag-guided bidirectional graph analysis to identify attack entry points and assess campaign impact without exhaustive traversal. It converts reconstruction into cost-sensitive shortest-path search and prunes the resulting impact graph for compactness.

  • Backward analysis: Backward analysis starts from alarm-linked suspect nodes and searches backward through dependencies to identify untrusted entry points.Entry points have graph in-degree zero and may include network connections or files introduced through USB devices.
  • Backward analysis: Large graphs and numerous reachable paths make naive backward searches expensive and prone to false positives.The dependence graph can contain hundreds of millions of edges, while alarms may number in the thousands.
  • Backward analysis: Tag values guide backward search by defining edge costs that favor paths through unknown entities and discourage benign information flows.The formulation addresses both scalability and multiple-path ambiguity by preferring relevant, lower-cost paths.
  • Backward analysis: Dijkstra’s algorithm grows a shortest-path tree in increasing cost order and can stop when an entry-point node is reached.This avoids traversing the entire graph when a suitable entry point is found.
  • Forward analysis: Forward analysis starts at identified entry points to find campaign effects, then reduces oversized impact graphs using distance-based costs and simplification rules.In experiments, the refined algorithm reduced naive impact graphs containing millions of edges by 100x to 500x.
  • Forward analysis: The output is compacted by pruning irrelevant dependencies, merging same-named entities, and collapsing repeated events while retaining first and last occurrences when interleaving exists.These transformations target dependencies that do not contribute to suspect-node analysis and repetitive event sequences.

6 Experimental Evaluation

The evaluation uses multi-OS red-team and benign audit data to test SLEUTH’s reconstruction under realistic background activity. The datasets include heterogeneous audit semantics and substantial event volume.

  • Evaluation setup: SLEUTH’s implementation combines approximately 9.5KLoC of C++ with 1.6KLoC of Python for graph processing, detection, reconstruction, and presentation.C++ implements most core components, while Python handles reconstruction and presentation.
  • Evaluation setup: The red-team evaluation spans Windows, Linux, and FreeBSD campaigns, while benign data comes from four Linux servers over 3 to 5 days.The attack datasets include campaigns W-1/W-2, L-1 through L-3, and F-1 through F-3.
  • Evaluation setup: The attack corpus covers 358 hours and about 73 million events, with the first eight dataset rows corresponding to DARPA Transparent Computing campaigns.The final dataset row represents benign laboratory activity.
  • Evaluation setup: Audit-event distributions differ across operating systems because reported operations include different file, network, library-loading, and memory-mapping semantics.For example, Windows omits file open and close operations, while Linux read/write counts include network activity.
  • Evaluation setup: Red-team campaigns ran for two or four days and pursued objectives including executable delivery and execution, host intelligence gathering, and backdoor injection.Benign browsing, downloads, email, and document processing occurred concurrently during the engagements.
  • Evaluation setup: The reported findings were compared with ground truth released by the red team after SLEUTH’s report was submitted.The paper presents selected reconstructed scenarios before summarizing aggregate results.

6.4 Selected Reconstruction Results

SLEUTH automatically reconstructs compact attack graphs from noisy Windows and FreeBSD audit data, preserving the sequence from initial compromise through execution, collection, and exfiltration.

  • Selected scenarios: The selected scenarios are W-2 on Windows and F-3 on FreeBSD, with graph generation automated but narrative interpretation performed manually.Graph edges include event names and global sequence numbers; shapes distinguish processes, sockets, and files.
  • Campaign W-2: In W-2, Firefox is compromised through a web server, after which dropper provides a remote shell, gathers host information, exfiltrates it, and performs cleanup.The reconstructed chain includes cmd.exe, whoami, hostname, netstat, git-based exfiltration, and burnout.bat.
  • Campaign F-3: In F-3, an sshd-created bash process launches scp and shell activity that installs Dropbear keys, gathers host data, and exfiltrates it.The reconstruction infers stolen SSH credentials from subsequent scp activity rather than direct audit evidence.
  • Summary: The two graphs were constructed automatically and remained compact despite hours of audit data dominated by benign activity.For W-2, benign activity accounted for more than 99.8% of audit events, while SLEUTH still isolated the attack sequence.

6.5 Overall Effectiveness

Across the evaluation, SLEUTH recovered major APT stages and key attack entities while producing no alerts during the benign software-update study. The results also expose missed entities, omitted datasets, and a false-positive case tied to auditing outside the engagement.

  • APT-stage coverage: SLEUTH captured concrete data exfiltration evidence in all 8 reconstructed scenarios, drop-and-load activity in 7, and attacker information-gathering commands in 7.These counts were correlated with stages documented in postmortem reports of notable APT campaigns.
  • APT-stage coverage: Backdoor injection appeared in 6 of 8 scenarios, while cleanup activities appeared in 5 of 8.Cleanup included removing dropped executables and data files created during attacks.
  • Entity reconstruction: Table 7 summarizes reconstructed entry entities, program executions, key files, and exfiltration exit points against red-team ground truth.The comparison counts attack-related entities across several categories rather than reporting only a single aggregate measure.
  • Entity reconstruction: Two entities were initially missed because sensitive data files and device files had not been cataloged, but marking them correctly enabled identification of all key entities.The missed entities were filtered during forward analysis and simplification.
  • Evaluation boundaries: The evaluation omits or restricts some attack evidence because W-3 was not recorded, L-3 activities were incomplete, and only one W-2 instance was examined.Table 7 therefore counts only the available subset of L-3 key entities.
  • Benign environment: No alerts were triggered during benign software upgrades and updates collected from four Ubuntu Linux servers.The benign study specifically tested activities that download code and could otherwise resemble untrusted execution.
  • Evaluation boundaries: SLEUTH incorrectly identified 21 F-1 entities because auditing continued after the engagement during testing and administration steps.The false positives corresponded to activity that should have occurred after the auditing system was shut down.

6.6 False Alarms in a Benign Environment

SLEUTH was evaluated on benign Ubuntu servers and combined compact memory use with rapid analysis of multi-day audit datasets. The section reports that its overall processing supports real-time consumption and analysis with a small memory footprint.

  • Benign environment: SLEUTH analyzed benign audit data collected from four Ubuntu Linux servers over 3 to 5 days, focusing on software updates and upgrades.The evaluation included a mail server, web server, and NFS/SSH/SVN server; updates could otherwise trigger untrusted-code execution alarms.
  • Memory use: 329MB stored 38.5M events spanning about 3.5 days for the densest campaign, while larger datasets required about 8 bytes per event.The compact main-memory representation was designed to retain data spanning long periods.
  • Runtime: Analysis of datasets covering several hours to a few days took seconds to a couple of minutes, including graph construction, detection, and reconstruction.The reported runtime was measured after the engagement, although data were consumed as they were produced during it.
  • Throughput: SLEUTH’s speed-up can be interpreted as the number of simultaneous data streams it could handle when CPU use was the only constraint.This interpretation accompanies the runtime measurements in Table 9.
  • Conclusion: SLEUTH consumed and analyzed COTS audit data from several operating systems in real time while maintaining a small memory footprint.This is the section’s stated summary conclusion.

6.8 Benefit of split tags for code and data

Separating code and data trustworthiness tags sharply improves SLEUTH’s selectivity, reducing alarms and forward-analysis graphs before final simplification. The combined pipeline can compress tens of millions of edges into graphs of roughly a hundred edges.

  • Mechanism: Prioritizing detection and forward analysis on code trustworthiness cuts down alarms and decreases forward-analysis output size.The split-tag design distinguishes each subject’s code trustworthiness from its data trustworthiness.
  • Alarm reduction: Separate code and data trustworthiness tags reduce alarms by factors of 100 to over 1000 in some cases.Table 10 compares alarm counts under a single trustworthiness tag with split trustworthiness tags.
  • Forward analysis: 100x to 1000x reductions in forward-analysis graph size often result from splitting the trustworthiness tag.The increased selectivity is attributed to the split tag in Table 11.
  • Data reduction: Two to three orders of magnitude of data reduction are achieved relative to single t-tag analysis.The reduction is reported across the analyzed campaigns before the full simplification effect is described.
  • Simplification: The pipeline applies split tags and simplification to reduce tens of millions of edges to graphs with perhaps a hundred edges.The overall reduction reaches five orders of magnitude for L-2 and L-3 and four orders for other data.

6.10 Discussion of Additional Attacks

SLEUTH reconstructed additional campaigns across Linux, FreeBSD, and Windows by representing attack steps as scenario graphs. The cases include exploitation, payload execution, data gathering, key creation, and exfiltration.

  • Attack L-1: In L-1, an exploited Firefox drops mozillanightly, which downloads and executes mozillaautoup before gathering and exfiltrating information.The reconstructed chain also includes shells and spawned processes.
  • Attack F-1: In F-1, an exploited nginx server executes dropper, which spawns processes, accesses sensitive files, and communicates with the attacker’s IP.The figure also includes restoration and administration after the engagement.
  • Attack F-2: In F-2, dropper downloads recon, sysman, and mailman, which are later executed and used to exfiltrate gathered system data.The attack begins similarly to F-1.
  • Attack W-1: In W-1, Firefox is exploited twice: one payload captures and exfiltrates a screenshot, while another gathers system data and exfiltrates it.The first payload uses photosnap.exe; the second uses burnout.bat, cmd.exe, and mnsend.exe.
  • Attack L-3: In L-3, dropbearLINUX.tar is downloaded and extracted, dropbearkey creates three keys, and dropbear reads them before exfiltration.The scenario graph captures this sequence of downloaded archive, key generation, key use, and exfiltration.

7 Related Work

SLEUTH builds on intrusion detection, alert correlation, and provenance-based forensics while targeting real-time analysis. Its distinguishing focus is application-independent, tag-informed reconstruction from audit data rather than enforcement or offline-only investigation.

  • Provenance and forensics: Unlike forensic systems such as Backtracker, SLEUTH designs its data representation and analysis for real-time detection and reconstruction.The paper reports Backtracker taking 3 hours for 24 hours of audit data, while SLEUTH processed 358 hours in a little less than 3 minutes.
  • Provenance and forensics: SLEUTH uses tag-based detection results to guide forensic search and pruning, making its analysis inherently more precise than searches driven by external alarms.The comparison specifically contrasts principled tag-based detection with Backtracker’s externally generated alarms.
  • Provenance and forensics: BEEP and ProTracer construct dependence graphs for forensic analysis, whereas SLEUTH builds dependence graphs for real-time detection and extracts scenario subgraphs during forensic analysis.The cited comparison also notes instrumentation and scalability challenges for the execution-unit approach.
  • Information flow: Information-flow systems can provide finer-grained provenance at higher overhead, and SLEUTH can use such provenance when available to improve accuracy.Most other systems discussed operate at the system-call level.
  • Attack detection: SLEUTH differs from misuse, anomaly, and specification-based detection by using application-independent policies derived from provenance information in audit data.Specification and policy approaches otherwise require application-specific policies or expert knowledge.
  • Information flow: IFC systems focus on enforcement and prevention, while SLEUTH must distinguish attacks from normal activity and separate attack actions within audit data.The paper identifies policy-violation analysis and audit-data disambiguation as central challenges for SLEUTH’s setting.
  • Alert correlation: Alert-correlation systems cluster, prioritize, and causally relate alerts, but depend on manually supplied expert knowledge about dependencies between alert types.SLEUTH instead derives relevant context from audited system activity and tags.

8 Conclusion

SLEUTH provides real-time attack detection and reconstruction from COTS audit logs using an efficient, precise analysis framework. Evaluation across three major operating systems reconstructed all attacks with very few errors.

  • SLEUTH detects attacks and reconstructs attack scenarios from COTS audit logs in real time.
  • Its main-memory graph model and rich tag-based policy framework support efficient and precise analysis.
  • Evaluation on large datasets from 3 major operating systems reconstructed all red-team attacks with very few errors.
Loading 1801.02062v1…