Preemptive Intrusion DetectionPhuong Cao, Key-whan Chung,Zbigniew Kalbarczyk, Ravishankar IyerCoordinated Science LaboratoryUniversity of Illinois at Urbana Champaign{pcao3,kchung10,kalbarcz,iyer}@illinois.eduAdam J. SlagellNational Center for Supercomputing ApplicationsUniversity of Illinois at Urbana Champaignslagell@illinois.eduABSTRACTThis paper presents a system named SPOT to achieve highaccuracy and preemptive detection of attacks. We use se-curity logs of real-incidents that occurred over a six-yearperiod at National Center for Supercomputing Applications(NCSA) to evaluate SPOT. Our data consists of attacksthat led directly to the target system being compromised,i.e., not detected in advance, either by the security analystsor by intrusion detection systems. Our approach can detect75 percent of attacks as early as minutes to tens of hoursbefore attack payloads are executed.Categories and Subject DescriptorsC.2.0 [Computer-Communication Networks]: Securityand protectionGeneral Termscyber-system, security incident, graphical modelKeywordscredential stealing attack, factor graph, tagging, timeliness1. INTRODUCTIONCyber-systems, such as super-computers or data centers,host mission-critical services and valuable data, making theman enchanting target of attacks. Credentials to those sys-tems may be tied to previously leaked credentials: millionsof them can be bought from black-markets for a low cost [1].However, attacks targeting these systems are often discov-ered when they are in the f i nal stage, resulting in suspensionof critical system services or conf i dential data leak [4].We focus on detection of attacks that take advantage ofstolen credentials ahead of time, i.e., before the system ismisused, while minimizing the false positives is a dif f i cultproblem. Major challenges are: (i) an early detection meansonly a partial knowledge of the attack (e.g., system-levelPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for prof i t or commercial advantage and that copiesbear this notice and the full citation on the f i rst page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specif i cpermission and/or a fee.HotSoS ’14 Raleigh, NC USACopyright 2014 ACM 978-1-4503-2907-1/14/04http://dx.doi.org/10.1145/2600176.2600197.events such as logging in from a remote host) is available, (ii)the attackers enter the target system as legitimate users withknown credentials – not leaving many traces, (iii) semanticsof event logs may be dif f i cult to correlate with the attacker’sactions. Examining an event in isolation is not suf f i cientto detect such attacks. An event represents a fact, but itssemantics can be interpreted dif f erently depending on thecontext. For example, remote login may indicate that theuser is traveling or the user account is being compromised.Restarting the SSH daemon could indicate a maintenanceactivity or an integrity violation of the daemon [4].This paper presents SPOT – an approach to identify at-tacks before attack payloads are executed. Events leadingto attacks are associated with user states and attack statesto understand user intentions and attack semantics. Weassume the events are not contaminated. Theory of factorgraph (FG) is used to develop a probabilistic model thatcaptures transitions and relations between the events andthe states. In a FG, a variable node can be an event (e.g., asecurity alert) or a state (e.g., the user state is suspicious).The variable nodes are connected by factor functions de-scribing relationships between the nodes. Using the def i nedfactor graph, SPOT tags, i.e., determines, the most prob-able state of the user (e.g., a user is compromised) basedon the events observed in real-time. It results in identifyingattackers early, i.e., before the system is misused.2. APPROACHSystem model. Consider a target system of functionalobjects (components) and monitors (deployed to probe ob-jects). A user u interacts with objects in the system. Mon-itors probe the interactions and emit an event sequence E.An event e is a tuple of the user u, the object o, and theevent e which belong to a f i nite set of events E. An alert is acritical event that may violates security property of the tar-get system. Additional evidence regarding the user behaviorand system performance can be obtained from the user pro-f i le u and measurement metrics M = {m i }. For example, ametric can be the number of login attempts.Problem def i nition. Given observed evidence X = {event sequence E, user prof i le u, metrics M}, SPOT in-fers security state Y = {S} of the target system. Eachevent e is tagged with state variables: user state s u and at-tack state s a . A user can be in one of the three states:s u ∈ {benign,suspicious,malicious}. At f i rst, when noevent is observed, a user is benign. Its state changes accord-ing to observed events. When the user transitions from thebenign to the suspicious state (i.e., the user performs some
