Home

discovery.csc.ncsu.edu - Repository

1. Appendix A Knowledge Base Used In The Experiment lt Arg id 2 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name ExistFTPService gt lt Arg id 3 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name GainAccess gt lt Arg id 4 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name GainAdmindInfo gt lt Arg id 5 Pos 1 Attr varchar 15 gt lt Arg gt lt Arg id 6 Pos 2 Attr int gt lt Arg gt lt Predicate gt lt Predicate Name GainInformation gt lt Arg id 7 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name Gain0SInfo gt lt Arg id 8 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name GainServiceInfo gt lt Arg id 9 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt lt Predicate Name GainSMTPInfo gt lt Arg id 10 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name GainTerminalType gt lt Arg id 11 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name JavaEnabledBrowser gt lt Arg id 12 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name MailLeakage gt lt Arg id 13 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt 69 Appendix A Knowledge Base Used In The Experiment lt Predicate Name
2. Email_Ehlo gt MTPSupportEhlo DestIP ND ExistService DestIP DestPort GainSMTPInfo DestIP Email_Helo_Overflow lt gt ulnerableMailServer DestIP ND ExistService DestIP DestPort GainAccess DestIP Email_Qmail_Length lt gt ulnerableMailServer DestIP ND ExistService DestIP DestPort gt SystemAttacked DestIP Email_QuickStore VulnerableWebStore DestIP GainRootAccess DestIP Email_Turn SMTPSupportTurn DestIP MailLeakage DestIP Finger_Bomb ExistFingerService DestIP SystemAttacked DestIP Finger Perl AND ExistService DestIP DestPort ExistPerlFingerd DestIP ND VulnerableFingerService DestIP SystemCompromised DestIP Finger RTM A AND ExistService DestIP DestPort VulnerableFingerService DestIP ND GainOSInfo DestIP ND ExistService DestIP DestPort A A GainRootAccess DestIP Appendix A Knowledge Base Used In The Experiment 90 Hyper alert Type Prerequisite Consequence FSP_Detected ExistFSPService DestIP SystemCompromised DestIP AND GainOSInfo DestIP AND ExistService DestIP DestPort FTP_Args VulnerableFTPService DestIP GainRootAccess DestIP AND ExistService DestIP DestPort FTP_Bounce ExistService DestIP DestPort BypassFirewall SpoofedAddress FTP_Format_String VulnerableF TPService DestIP AND ExistService DestIP Dest Po
3. lt ArgMap gt lt ImplyingArg id 2 gt lt ImplyingArg gt lt ImpliedArg id 1 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implication Phantom Yes gt lt ImplyingName gt Gain0SInfo lt ImplyingName gt lt ImpliedName gt 0SUnix lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 4 gt lt ImplyingArg gt lt ImpliedArg id 5 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implications gt Figure 4 4 A sample Implications section in a knowledge base XML file 4 3 The second and the third tuple in figure 4 2 a represent another predicate ExistService which is also defined in figure 4 3 Implications The Implications section contains a set of Implications Implication is used to represent the rela tionship between predicates This part is saved in the Implication table in the database To simplify the implementation we assume that for all implication of the form VI 73 Un Y1 Y2 Ym P1 L1 12 Un PalY1 Y2 Ym Y1 Y2 Ym E 1 22 En As a result in order to keep the implication from p to p2 we only need to record what arguments of p are mapped to the arguments of pa For example EristService IP port ExistHost IP can be represented as the first tuple in figure 4 2 b which states that the first argument of ExistHost is the first argument of ExistService Figure 4 4 shows a sample Implications section in a knowledge base XML file
4. lt Fact FactName DestPort FactType int gt lt Fact gt lt Consequence gt Se lt Predicate Name GainServiceInfo gt lt Arg id 9 ArgName DestIPAddress gt lt Arg gt lt Predicate gt gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt Appendix A Knowledge Base Used In The Experiment 83 lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name RIPAdd gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt HyperAlertType gt lt HyperAlertType Name RIPExpire gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt HyperAlertType gt lt HyperAlertType Name Rsh gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequ
5. In the Implications section there are two kinds of implications normal and phantom Normal implications are the implications can be derived by us the correlators directly For example Erist Service IP port ExistHost IP is a normal implication because we are sure if EristService IP port is true EristHost IP must be true This relationship can be derived by us the correlators directly While the phantom implications mean that the implied predicate is unclear to us but Chapter 4 Implementation 24 it is clear to the attacker For example the consequence of FTP_Syst is GainOSInfo Through FTP Syst the attacker may get knowledge about what operating system is in the target machine either OSUniz or OS Windows etc But we the correlators cannot get this detailed information So we call this kind of implication GainOSInfo IP OSUnix IP phantom implication Impli cation relationships are not complete without the phantom implications because we should stand on attackers position and see what information they can get In the knowledge base XML file we use an attribute Phantom to indicate whether this implication is a phantom implication or not The default value is false We regard an implication as a normal im plication if the Phantom attribute is not specified In the correlation process both phantom implica tions and normal implications have the same effect and this information isn t stored in the database We mar
6. inputGraphID AND PreparingHyperAlertID IN SELECT HyperAlertID FROM HyperAlertFact WHERE inputFocusingConstraint AND PreparedHyperAlertID IN SELECT HyperAlertID FROM HyperAlertFact WHERE inputFocusingConstraint 4 8 Graph Decomposition As explained in the previous chapter graph decomposition is to decompose a graph according to the common features shared by hyper alerts That is we will cluster the alerts into clusters based on the clustering constraint The constraint could be the same destination IP address same source IP address etc If any two alerts match the constraint they fall into the same cluster Each cluster could be viewed as a sub graph of the original graph Since we will plug in the clustering constraint into an SQL statement the user is requested to provide it in an SQL valid presentation Not only it must be SQL valid it must also be a relationship between hi and h2 because we use h1 and h2 as two alerts in the query For example if user wants to decompose a graph based on alerts source IP addresses then h1 SrcIPAddress h2 SrcIPAddress would be the clustering constraint If user wants to decompose a graph based on both source IP ad dresses and destination IP addresses then h1 SrcIPAddrss h2 SrcIPAddress and h1 DestIPAddress h2 DestIPAddress is the clustering constraint Also these features Sre PAddress DestIPAddress must be the valid attributes in the knowledge base We use a linked list to keep al
7. lt Predicate Name VulnerableCGIBin gt lt Arg id 19 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Predicate Name 0SUNIX gt lt Arg id 26 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt Appendix A Knowledge Base Used In The Experiment 82 lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Mstream_Zombie gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name SystemCompromised gt lt Arg id 18 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Predicate Name SystemCompromised gt lt Arg id 18 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name ReadyToLaunchDDOSAttack gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Port_Scan gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt
8. Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name SystemCompromised gt lt Arg id 18 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt Appendix A Knowledge Base Used In The Experiment 79 lt HyperAlertType Name FTP_Syst gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt l lt Predicate Name ExistFTPService gt lt Arg id 3 ArgName DestIPAddress gt lt Arg gt lt Predicate gt gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name Gain0SInfo gt lt Arg id 8 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name FTP_User gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact F
9. ID NCSU targetNamespace ID NCSU elementFormDefault qualified gt lt Big Picture of KnowledgeBase gt lt xsd element name KnowledgeBase gt lt xsd complexType gt lt xsd sequence gt lt xsd element ref Predicates gt lt xsd element ref Implications gt lt xsd element ref HyperAlertTypes gt lt xsd sequence gt lt xsd complexType gt lt xsd unigue name uniquel gt lt xsd selector xpath HyperAlertTypes HyperAlertType gt lt xsd field xpath Name gt lt xsd unigue gt 61 Appendix A Knowledge Base Used In The Experiment 62 lt set the name of the predicate as the key gt lt xsd key name PredicateNameKey gt lt xsd selector xpath Predicates Predicate gt lt xsd field xpath Name gt lt xsd key gt lt xsd keyref name keyref1 refer PredicateNameKey gt lt xsd selector xpath Implications Implication Implying gt lt xsd field xpath ImplyingName gt lt xsd keyref gt lt xsd keyref name keyref2 refer PredicateNameKey gt lt xsd selector xpath Implications Implication Implied gt lt xsd field xpath ImpliedName gt lt xsd keyref gt lt xsd keyref name keyref3 refer PredicateNameKey gt lt xsd selector xpath HyperAlertTypes HyperAlertType Prerequisite Predicate gt lt xsd field xpath Name gt lt xsd keyref gt lt xsd keyref name keyref4 refer PredicateNameKey gt lt xsd selector xpath HyperAlertTyp
10. amp Operation Manual C 1 Introduction This tool takes the alerts generated by Intrusion Detection System IDS as input and applies our correlation techniques upon them The false alerts will be filtered out by the tool and a set of correlation graphs will be generated to show the attack scenarios hiding behind the alerts In a word this tool aims to assist human user in analyzing the potentially large amount of intrusion alerts and uncovering the high level attack strategies This tool is written using Java with JDBC to access the database The GraphViz package 1 is adopted to visualize the results The techniques that this tool was based on can be found in 4 and 5 C 2 Installation C 2 1 System Environment This tool is developed with Java 2 A relational database is a must to use this tool In order to support knowledge base generation Xerces Java Parser is also needed We use Java 2 SDK Standard Edition v1 3 1_04 and Xerces Java Parser v1 4 4 3 Our tests were conducted on Windows 2000 with Microsoft SQL Server 2000 The original alerts were generated by RealSecure Network Sensor 6 0 2 C 2 2 Checklist Here is the list you need to run this tool e Java 98 Appendix C User Installation amp Operation Manual 99 e Database e JDBC Driver e Raw alerts generated by IDS which are stored in database e Knowledge Base e Xerces Java Parser v1 4 4 If you haven t a knowledge base ready and you want to generate it
11. ha and h Note that C h1 h2 implies that h and ha are in the same cluster but h and ha in the same cluster do not always imply C h1 h2 True or C h2 h1 True This is because C h1 h2 A Ce ha h3 does not imply C h1 h3 nor Celha h Chapter 4 Implementation In this chapter we give an overview of the implementation of an off line intrusion alerts correlator based on the frame work discussed before Figure 4 1 shows the architecture of this tool It consists of a knowledge base an alert preprocessor a correlation engine utility processors a graph generator and a visualization component We adopt the GraphViz package 1 as the visualization component We assume that all the alerts generated by IDSs are stored in a relational database so is the knowledge base All these components except for the visualization component interact with a rela tional database management system RDBMS which provides persistent storage for the interme diate data as well as the correlated alerts In other words this tool interacts with the RDBMS to access the alerts generated by IDSs and store the results back into the database Such a method not only takes advantage of the RDBMS s functionalities but also allows easy integration with other RDBMS based intrusion analysis tools Java is used to implement this tool and JDBC is used to communicate with the database 4 1 Knowledge Base The knowledge base contains the necessary informa
12. lt ImplyingArg gt lt ImpliedArg id 25 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implication Phantom Yes gt lt ImplyingName gt Gain0SInfo lt ImplyingName gt lt ImpliedName gt OSUNIX lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 8 gt lt ImplyingArg gt lt ImpliedArg id 26 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implication Phantom Yes gt lt ImplyingName gt GainSMTPInfo lt ImplyingName gt lt ImpliedName gt SMTPSupportTurn lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 28 gt lt ImplyingArg gt lt ImpliedArg id 30 gt lt ImpliedArg gt lt ArgMap gt lt ArgMap gt lt ImplyingArg id 29 gt lt ImplyingArg gt lt ImpliedArg id 31 gt lt ImpliedArg gt lt ArgMap gt 73 Appendix A Knowledge Base Used In The Experiment 74 lt Implication gt lt Implications gt lt HyperAlertTypes gt lt HyperAlertType Name Admind gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt lt Prereguisite gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Predicate Name 0SSolaris gt lt Arg id 25 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Predicate Name VulnerableSadmind gt lt Arg id 21 ArgName DestI
13. varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name 0SUNIX gt lt Arg id 26 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name DDOSAgainst gt lt Arg id 27 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name GainSMTPInfo gt lt Arg id 28 Pos 1 Attr varchar 15 gt lt Arg gt lt Arg id 29 Pos 2 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name SMTPSupportTurn gt lt Arg id 30 Pos 1 Attr varchar 15 gt lt Arg gt lt Arg id 31 Pos 2 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicates gt lt Implications gt lt l lt Implication gt lt ImplyingName gt GainAdmindInfo lt ImplyingName gt lt ImpliedName gt GainInformation lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 5 gt lt ImplyingArg gt lt ImpliedArg id 7 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implication gt lt ImplyingName gt Gain0SInfo lt ImplyingName gt lt ImpliedName gt GainInformation lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 8 gt lt ImplyingArg gt lt ImpliedArg id 7 gt lt ImpliedArg gt 71 Appendix A Knowledge Base Used In The Experiment lt ArgMap gt lt Implication gt lt Implication gt lt ImplyingName gt GainServiceInfo lt ImplyingName gt lt ImpliedName gt GainInformation lt ImpliedName gt lt ArgMap gt lt ImplyingArg id
14. 2 0 2 misses the IPSweep so do us RealSecure generates several duplicated Rsh alerts so do us But we can eliminate this duplication In this experiment we haven t used the time constraint we just simply map one alert to one hyper alert If we use the time constraint for example we set the time interval constraint t 0 we can map the alerts with same timestamps to one hyper alert and remove the duplicated alerts In this way we can decrease the false alarm rate more Finally not all of the Mstream_Zombie alerts prepare for the Stream_DoS alert Only two of them with alert ID 67776 and 67777 prepare for Stream_DoS directly What the other four Mstream_Zombie alerts do is to let the handler record them in the known agents list They are part of the attack but they don t lead to Stream_DoS alert directly The command sent from handler to agent has the default destination port number 7983 while the command from agent to handler uses 9325 as its default destination port number If we consider this factor in our experiment we can distinguish these two kinds of Mstream_Zombie alerts To better understand the effectiveness of our method we examine the completeness and the soundness of alert correlation The completeness of alert correlation assesses how well we can corre late related alerts together while the soundness evaluates how correctly the alerts are correlated We introduce two simple measures Re and Rs to quantitatively evaluate c
15. Because this tool is implemented with Java JDBC is used as the bridge to communicate with database User can change the JDBC driver and database URL based on the environment Section 2 contains the knowledge base related parameters User can specify the path of the knowledge base XML file in this section so that the tool will parse this XML file and save the content as the knowledge base Section 3 contains the parameters for the correlation engine User needs to tell the tool where the original alerts are what is the table name of the alerts generated by IDS the column names the tool cares about and so on Section 4 5 and 6 contain the parameters for the three utilities adjustable graph reduction focused analysis and graph decomposition respectively User can specify which graph needs to be analyzed what constraint will be used and so on Section 7 is an optional one We assume that the hyper alerts have the same name with the original alerts if not specified But we also provide this section as an alternative way to accommodate different names between hyper alerts and original alerts Detailed information about the property file can be found in the appendix Chapter 5 Experimental Results To evaluate the effectiveness of our method in constructing attack scenarios and its ability to differ entiate true and false alerts some experiments on different datasets are performed The results are very good One dataset is DARPA evaluation datas
16. DestIP ND ExistService DestIP Dest Port GainAccess DestIP HTTP_WebSite_Sample lt gt gt lnerableWebServer DestIP ND ExistService DestIP DestPort GainAccess DestIP HTTP_WebSite_Uploader lt gt c lnerableWebServer DestIP ND ExistService DestIP DestPort GainAccess DestIP HTTP_WebStore lt gt ulnerableWebStore DestIP ND ExistService DestIP DestPort gt GainOrderLogFile DestIP Ident Error OSUNIX DestIP GainInformation DestIP Ident_Linux_DoS Vulnerableldent DestIP SystemAttacked DestIP AND OSLinux DestIP IPDuplicate IPFrag SystemAttacked DestIP IPHalfScan ExistService DestIP DestPort GainServiceInfo DestIP Appendix A Knowledge Base Used In The Experiment 94 Hyper alert Type Prerequisite Consequence IPUnknownProtocol IRDP Gateway Spoof GainOSInfo DestIP SystemAttacked DestIP ISS GainVulnerability DestIP Kerberos_User_Snarf KerberosIV DestIP GainUserName DestIP Loki SystemCompromised DestIP Mstream_Zombie SystemCompromised SrcIP AND SystemCompromised DestIP ReadyToLaunchStreamDOSAttack Netbus OSWindows DestIP GainRootAccess DestIP Nmap _Scan GainNetworkInfo DestIP GainOSInfo DestIP PingFlood SystemAttacked DestIP PmapDump OSUnix DestIP VulnerableRPCService DestIP POP Fold Overflow VulnerablePOP
17. alert Using predicates as the basic construct we introduce the notion of a hyper alert type to represent the prerequisite and the consequence of each type of alert Chapter 3 A Framework for Alert Correlation 9 Definition 1 A hyper alert type Tis a triple fact prerequisite consequence where 1 fact is a set of attribute names each with an associated domain of values 2 prerequisite is a logical combination of predicates whose free variables are all in fact and 3 consequence is a set of predicates such that all the free variables in consequence are in fact Each hyper alert type encodes the knowledge about a type of attack The component fact of a hyper alert type tells what kind of information is reported along with the alert i e detected attack prerequisite specifies what must be true in order for the attack to be successful and consequence describes what is true if the attack indeed succeeds For the sake of brevity we omit the domains associated with the attribute names when they are clear from the context Example 1 Consider the buffer overflow attack against the sadmind remote administration tool We may have a hyper alert type SadmindBufferOverflow 4 VictimIP VictimPort EristHost VictimIP AVulnerableSadmind VictimIP GainRootAccess VictimIP for such attacks Intuitively this hyper alert type says that such an attack is against the host at IP address VictimIP We expect the actual values of VictimIP ar
18. alert id else a is alerts j 1 s aggregated alert id Record this mapping in table IDMapping y j Figure 4 9 The algorithm used to do the adjustable graph reduction 4 7 Focused Analysis After correlation it is still possible that the graph is too large to understand if the dataset is huge If this happens and you have some rough knowledge of the graphs you can use this utility to facilitate your analysis The user is requested to input the focusing constraint for this utility For example there are critical services running on the computer with IP 152 1 2 3 the user wants to analyze the attacks targeted at this machine So DestIPAddress 152 1 2 3 would be the focusing constraint This focusing constraint must follow the SQL syntax and the attribute e g DestIPAddress must be a valid one in the knowledge base The tool takes input from the table GraphEdges which contains all the prepare for relationships Chapter 4 Implementation 34 and graph information applies the focusing constraint onto it and output the result into the table GraphEdgesFocus Table GraphEdgesFocus has the same attributes with table GraphEdges The implementation of this utility is kind of easy We just plug in the focusing constraint and the graph id provided by the user into the following SQL query statement Query INSERT INTO GraphEdgesFocus SELECT FROM GraphEdges WHERE graphID
19. be activated and it will search the needed parameters in the section 5 of the property file Similarly when GraphDecomposition is in the command line the graph decomposition utility will be activated and it will search the needed parameters in the section 6 of the property file For example the command line java Correlator Correlation TransitiveExclusion GraphReduction GraphDecomposition user Name userPassword will activate the correlation engine the graph reduction utility and the graph decomposition utility but not the focused analysis utility And keeps the transitive edges The user and password are used for database authentication Fhis user needs to have full rights in the database Correlation Set Correlation in the command line Set the alert related parameters in the property file following the instructions in the section property file you can correlate the alerts as you want Graph Reduction Graph reduction is to aggregate the alerts with same type in each graph To activate it you must set GraphReduction in the command line Also you must give the aggregation time interval It is in milli second unit You can set Aggregation Time_Interval to 1 which will make the aggregation engine to aggregate all the alerts with same type no matter how far in time they are Give a value to Graph_Reduction_Output will generate a DOT formatted graph file based on the aggregated prepare for relationship which can be di
20. consequence sets of hyper alerts Note that begin_time and end time are redun dant since this information can be derived from the table HyperAlert However we replicate them in both PreregSet and ConseqSet for performance reasons To simplify the correlation process we encode instantiated predicates as strings Specifically each instantiated predicate is encoded as the predicate name followed by the character followed by the sequence of arguments separated with the character and finally followed by the char acter It is assumed that predicates are uniguely identified by their names and the characters P and do not appear in predicate names and arguments Thus comparing instantiated predicates is eguivalent to comparing the encoded strings For example if a hyper alert has two instantiated predicates VulnerableSadmind 152 142 1 19 and VulnerableSadmind 152 142 1 52 in its prerequisite set then it will have two tuples in the table PreregSet with encoded predicates VulnerableSadmind 152 142 1 19 and VulnerableSadmind 152 142 1 52 respectively 4 3 Correlation Engine The basic task of the correlation engine is to find out all the prepare for relationships between hyper alerts instantiated by the alert preprocessor The correlated hyper alert information is stored in the table CorrelatedAlerts which has only two attributes PreparingHyperAlertID and PreparedHyper AlertID As suggested by th
21. fixed keyword parameters They are used to tell the column names of original alert id alert name alert begin time and alert end time in the Alert TableName The name and number of the other parameters in this section are based on knowledge base The keywords are the attribute names Appendix C User Installation amp Operation Manual 103 used in knowledge base and the values are their column names in AlertTableName In this example we have attribute name SrcIP SrcPort DestIP and DestPort in the knowledge base so we need to specify their corresponding column names in AlertTableName They have the same names here Set a file name to Original_Graph_Output will generate a DOT formatted graph file based on the original prepare for relationships which can be displayed by GraphViz Sections 4 5 and 6 contain the parameters used for three utilities graph reduction focused analysis and graph decomposition Please refer to the section Execution for detailed usages We assume that hyper alert has the same name as its original alert But to accommodate the situation that hyper alert has the different name with its original alert or several different alerts could be mapped to one hyper alert we use section 7 to address it You can write the name mapping relationship as ORIGINAL ALERT NAME HYPER_ALERT_NAME such as Sadmind Portmap request sadmind The property keyword is the original alert name and the property value is the hyper alert name
22. has the original hyper alert id while SimplifiedGraphEdges has the aggregated hyper alert id SimplifiedFocus This table keeps the results when we apply the adjustable graph reduction utility upon the focused analysis result Chapter 4 Implementation 38 SimplifiedDecomposed This table keeps the results when we apply the adjustable graph reduction utility upon the graph decomposition result Also there are three tables which contain the mapping relationships between original hyper alert ID and the aggregated hyper alert ID IDMappingA is used when the graph reduction utility is applied upon the original prepare for relationships DMappingF is used when the graph reduction utility is applied upon the focused analysis result and DMappingD is used when it is applied upon the graph decomposition So pure graph reduction utility uses the following tables GraphEdges IDMappingA and Simpli fiedGraphEdges When graph reduction is applied upon focused analysis it uses GraphEdgesFocus IDMappingF and SimplifiedFocus When graph reduction is applied upon graph decomposition it uses GraphEdgesDecomposed IDMappingD and SimplifiedDecomposed 4 10 Property File To make this tool easy to use easy to integrate with other tools and easy to upgrade we use a property file to specify the required parameters used in each functionality Basically the property file is divided into 7 sections Section 1 contains the database related parameters
23. hyper alert types in terms of the number of uncorrelated hyper alerts Among these hyper alert types uncorrelated PHalfScan counted 61 of all uncorrelated hyper alerts Windows_Access_Error counted 21 of all uncorrelated alerts According to the description provided by RealSecure a Windows_Access_Error represents an unsuccessful file sharing connection to a Windows or Samba server which usually results from an attempt to brute force a login under another account s privileges It is easy to see that the corresponding attacks could hardly prepare for any other attacks since they failed The third largest hyper alert type HTTP_Cookie counted for 3 3 of the total alerts Though such alerts have certain privacy implications we do not treat them as attacks considering the nature of the DEF Chapter 5 Experimental Results 47 Generic_Intel_Overflow31886 HTTP Machinelnfo30822 2 poti lt Generic_Intel_Overflow89044 a 3 IPHalfScan68574 ua Z ze Generic Intel Overflow89032 g i POP_QPopCommand_Overflow89027 Figure 5 5 A small hyper alert correlation discovered in initial analysis CON CTF events These three hyper alert types counted for 74 5 of all the alerts We omit the discussion of the other uncorrelated hyper alerts Figure 5 5 shows one of the small hyper alert correlation graphs The text in each node is the type followed by the ID of the hyper alert All the hyper alerts in this figure were destined to the
24. id 9 ArgName DestIPAddress gt lt Arg gt lt Predicate gt gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertTypes gt Appendix A Knowledge Base Used In The Experiment lt KnowledgeBase gt 88 Appendix A Knowledge Base Used In The Experiment 89 A 3 Knowledge Base Used for DEFCON 8 Dataset Because of the length of the XML file I present it in an alternative format Hyper alert Type Prerequisite Consequence Admind ExistService DestIP DestPort VulnerableAdmind DestIP BackOrifice OSWin95orWin98 DestIP GainRootAccess DestIP Bind_Version_Request BINDServer DestIP AND ExistService DestIP DestPort VulnerableDNS DestIP Cisco_Syslog_DoS VulnerableCiscoEquipment DestIP AND GainHardwarelnfo DestIP AND GainOSInfo DestIP SystemAttacked DestIP CyberCop Scanner GainVulnerability DestIP DNS Iguery VulnerableDNS DestIP AND ExistService DestIP DestPort GainNetworkInfo DestIP DNS Length Overflow GainOSInfo DestIP AND ExistService DestIP DestPort GainRootAccess DestIP DNS Zone High Port GainNetworkInfo DestIP Email_Almail_Overflow VulnerablePOP3Client DestIP ND ExistService DestIP DestPort GainAccess DestIP
25. in knowledge base If nothing is specified in section 7 we assume they have the same name Any line started with is a comment line C 3 3 Execution If you have configured the Correlator properties file and have a knowledge base XML file you are ready to go What you need to do is to set property parameters in the property file and turn on of turn off the corresponding switch Fhe command line would be java Correlator Correlation TransitiveExclusion GraphReduction FFocusedAnalysis GraphDecomposition user password After it executes successfully you can expect some graph files output with the name you specified in the property file Now you can use GraphViz to generate the graph with the command line dot Tps inputFileName o outFileName ps Let s explain the first command line in detail When you put Correlation in the command line the correlation engine will be activated and it will search the correlation related parameters in the section 3 of the property file When TransitiveExclusion appears in the command line the tool will delete the transitive edges in the prepare for relationship When GraphReduction is in the command line the graph reduction utility will be activated and it will search the graph reduction parameters in the section 4 of the property file Appendix C User Installation amp Operation Manual 104 When FocusedAnalysis is in the command line the focused analysis utility will
26. int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Predicate Name SMTPSupportEhlo gt lt Arg id 15 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt Appendix A Knowledge Base Used In The Experiment 77 lt Consequence gt lt Predicate Name GainSMTPInfo gt lt Arg id 28 ArgName SrcIPAddress gt lt Arg gt lt Arg id 29 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Email_Turn gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Predicate Name SMTPSupportTurn gt lt Arg id 30 ArgName SrcIPAddress gt lt Arg gt lt Arg id 31 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequi
27. n and 3 each edge e E is in a path from a node n in N to n The resulting graph PG is called the precedent graph of n w r t HG Definition 9 Given a hyper alert correlation graph HG N E and a hyper alert n in N subsequent n HG is an operation that returns the maximum sub graph SG N E of HG that satisfies the following conditions 1 n N 2 for each n N other than n there is a directed path from n to n and 3 each edge e F is in a path from n to a node n in N The resulting graph SG is called the subsequent graph of n w r t HG Definition 10 Given a hyper alert correlation graph HG N E and a hyper alert n in N correlated n HG is an operation that returns the maximal sub graph CG N E of HG that satisfies the following conditions 1 n N 2 for each n N other than n there is either a path from n to n or a path from n to n and 3 each edge e E is either in a path from a node in N to n or in a path from n to a node in N The resulting graph CG is called the correlated graph of n w r t HG Intuitively the precedent graph of n w r t HG describes all the hyper alerts in AG that prepare for n directly or indirectly the subsequent graph of n w r t HG describes all the hyper alerts in HG for which n prepares directly or indirectly and the correlated graph of n w r t HG includes all the hyper alerts in HG that are correlated to n directly
28. or indirectly It is easy to see that correlated n HG precedent n HG U subseguent n HG Assuming the black node hsaaminadBor in figure 3 1 a is the hyper alert of concern figures 3 1 b to 3 1 d display the precedent graph subsequent graph and correlated graph of hgadmindBoFr W t the hyper alert correlation graph in figure 3 1 a respectively Note that figure 3 1 d is the same as figure 3 1 a This is because all the hyper alerts in figure 3 1 a are related to hsadminaBor Vla the prepare for relation The hyper alert correlation graph is not only an intuitive representation of attack scenarios con structed through alert correlation but also reveals opportunities to improve intrusion detection First the hyper alert correlation graph can potentially reveal the intrusion strategies behind the at tacks and lead to better understanding of the attacker s intention Second assuming some attackers exhibit patterns in their strategies we can use the hyper alert correlation graph to profile previous attacks and identify on going attacks by matching to the profiles A partial match to the profile may indicate attacks possibly missed by the IDSs and lead to human investigation and improvement of the IDSs Chapter 3 A Framework for Alert Correlation 15 3 4 Utilities Correlation is effective to correlate the alerts and uncover the attack strategy However only corre lation itself is not effective enough in some cases especially i
29. replaced with the values of the corresponding attributes of t otherwise Cf evaluates to False For example consider the aforementioned focusing constraint Cf which is SrcIP 129 174 142 2 V DestIP 129 174 142 2 and a hyper alert h SrcIP 129 174 142 2 SrcPort 80 we can easily have that Cy True for h The idea of focused analysis is quite simple we only analyze the hyper alerts with which a focusing constraint evaluates to True In other words we would like to filter out irrelevant hyper alerts and concentrate on analyzing the remaining hyper alerts We are particularly interested in applying focusing constraints to atomic hyper alerts i e hyper alerts with only one tuple In our framework atomic hyper alerts correspond to the alerts reported by an IDS directly Focused analysis is particularly useful when we have certain knowledge of the alerts the systems being protected or the attacking computers For example if we are interested in the attacks against a critical server with IP address Server IP we may perform a focused analysis using DestIPAddress Server_IP However focused analysis cannot take advantage of the intrinsic relationship among the hyper alerts e g hyper alerts having the same IP address In the following we introduce the Chapter 3 A Framework for Alert Correlation 17 third utility graph decomposition to fill in this gap 3 4 3 Graph Decomposition The purpose of graph decomposition is to
30. set of predicates used to represent the consequence is essentially the conjunction of these predicates and can be represented by a single logical formula However representing the consequence as a set rather than a long formula is more convenient and will be used here The consequence of an attack is indeed the possible result of the attack In other words the attack may or may not generate the stated consequence depending on whether the attack is successful or not For example after a buffer overflow attack against a service an attacker may or may not gain the root access depending on if the service is vulnerable to the attack We use possible consequences instead of actual consequences due to the following reasons First an IDS may not have enough information to decide if an attack is effective or not For example a network based IDS can detect certain buffer overflow attacks by matching the patterns of the attacks however it cannot decide whether the attempts succeed or not without more information from the related hosts In contrast the possible consequence of a type of attack can be analyzed and made available for IDS Second even if an attack fails to prepare for the follow up attacks the follow up attacks may still occur simply because for example the attacker uses a script to launch a series of attacks Using possible consequences of attacks will lead to better opportunity to correlate such attacks 3 2 Hyper alert Type and Hyper
31. through an XML file you need it 1 Go to http xml apache org and download a Xerces Java Parser 2 Install it and make sure the package is in your classpath e GraphViz GraphViz is necessary to visualize the correlation results C 2 3 Download The software package can be downloaded at http discovery csc ncsu edu software sam ple knowledge base a sample test database and instructions to repeat our experiments are also available on the above page C 3 How to Use This Tool The core of this tool consists of a knowledge base an alert preprocessor a correlation engine a hyper alert correlation graph generator and three useful utilities adjustable graph reduction focused analysis and graph decomposition C 3 1 Knowledge Base The knowledge base contains the necessary information about hyper alert types as well as relation ships between predicates To simplify the implementation we assume that each hyper alert type is uniquely identified by its name and there is no negation in the prerequisite nor the consequence of any hyper alert type In the XML file there are basically three sections Predicates Implications and HyperAlert Types In the Predicates section the predicate name which works as the key of the predicate and the arguments of the predicate are specified In order to make the validation strict and easier a unique argument id is needed for each argument for all the predicates Here is an example lt Predica
32. to an auxiliary table TransitiveEdges It is used to keep all the possible transitive edges This table has two attributes PreparingHyperAlertID and PreparedHyperAlertID Then delete the edges which exist in both prepare for relationships and the table TransitiveEdges So A C and A D will be deleted in the above example To get all the possible transitive edges we first find out all the possible 2 hop edges A C from the prepare for relationships These edges match the condition that there exists a node B that A gt Band B Care both existed in the prepare for relationships Store this result into Transitive Edges and T2 T2 is another auxiliary table which keeps the result generated by the previous round It has the same attributes of table TransitiveEdges Then we will repeat a same process to find out all the 3 hop transitive edges 4 hop transitive edges and so on until there is no more new transitive edges Suppose we want to find all the n hop edges n 3 4 Because T2 contains all the possible n 1 hop edges all the edges A C are n hop edges if A B is existed in T2 and B gt C is existed in the prepare for relationship A B C D Figure 4 7 Transitive edges Chapter 4 Implementation 31 get all 2 hop edges using query write them into TransitiveEdges and T2 v set i 3 Y get all i hop edges using query2 write them into T2 4 Y
33. true alerts i e the alerts corresponding to actual attacks is greater than Hdetected attacks lo a tobservable attacks while the the number of detected attacks The detection rates were calculated as tS true alerts talerts Table 5 2 summarizes the results of these experiments These results show that discarding un false alert rates were computed as correlated alerts reduces the false alert rates greatly without sacrificing the detection rate too much Thus it is reasonable to treat correlated alerts more seriously than uncorrelated ones However simply discarding uncorrelated alerts is dangerous since some of them may be true alerts which correspond to individual attacks or attacks our method fails to correlate 5 3 Experiment on Defcon 8 dataset As demonstrated in the experiment with DARPA dataset the alert correlation method is effective in analyzing small amount of alerts However our experience with intrusion intensive datasets e g the DEF CON 8 CTF dataset has revealed several problems So we applied the three utilities we Chapter 5 Experimental Results 46 Table 5 3 General statistics of the initial analysis total hyper alert types 115 total hyper alerts 65054 correlated hyper alert types 95 correlated 9744 uncorrelated hyper alert types 20 uncorrelated 55310 partially correlated hyper alert types 51 correlated 15 Table 5 4 Statistics
34. unbounded gt lt xsd seguence gt lt xsd attribute name Name type xsd string use required gt lt xsd attribute gt lt xsd complexType gt lt set the Fact as the key for each hyper alert type gt lt xsd key name FactKey gt lt xsd selector xpath Fact gt lt xsd field xpath FactName gt lt xsd key gt lt xsd keyref name keyref9 refer FactKey gt lt xsd selector xpath Prerequisite Predicate Arg gt lt xsd field xpath ArgName gt lt xsd keyref gt lt xsd keyref name keyref10 refer FactKey gt lt xsd selector xpath Consequence Predicate Arg gt lt xsd field xpath ArgName gt lt xsd keyref gt Appendix A Knowledge Base Used In The Experiment lt xsd element gt lt xsd element name Fact gt lt xsd complexType gt lt xsd attribute name FactName type xsd string gt lt xsd attribute gt lt xsd attribute name FactType gt lt xsd simpleType gt lt xsd restriction base xsd string gt lt xsd enumeration value int gt lt xsd enumeration value varchar 15 gt lt xsd restriction gt lt xsd simpleType gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt xsd element name Prerequisite gt lt xsd complexType gt lt xsd sequence gt lt xsd element ref Predicate minOccurs 0 maxOccurs unbounded gt lt xsd sequence gt lt xsd complexType gt lt xsd element gt lt xsd el
35. use the inherent relationship between the attributes of hyper alerts to decompose a hyper alert correlation graph Conceptually we cluster the hyper alerts in a large correlation graph based on the common features shared by hyper alerts and then decompose the original correlation graphs into subgraphs on the basis of the clusters In other words hyper alerts should remain in the same graph only when they share certain common features We use a clustering constraint to specify the common features for clustering hyper alerts Given two sets of attribute names A and 4 a clustering constraint Ce A1 A2 is a logical combination of comparisons between constants and attribute names in A and Ag In our work we restrict logical operations to AND A OR V and NOT A clustering constraint is a constraint for two hyper alerts the attribute sets A and Ag identify the attributes from the two hyper alerts For example we may have two sets of attribute names A SrcIP DestIP and Ag SrcIP DestI P and C A1 A2 Ai SrceIP Ao SrcIP A A DestI P Az DestIP Intuitively this is to say two hyper alerts should remain in the same cluster if they have the same source and destination IP addresses A clustering constraint C A1 A2 is enforceable w r t hyper alert types T and Tz if when we represent Ce A1 A2 in a disjunctive normal form at least for one disjunct Cei all the attribute names in A appear in T and all t
36. used to generate a single graph AND PreparingHyperAlertID NOT IN SELECT FROM ProcessedNodes Query2 in figure 4 6 INSERT INTO NewlyAddedNodes SELECT DISTINCT PreparedHyperAlertID FROM GraphEdges WHERE PreparingHyperAlertID IN SELECT FROM ProcessedNodes AND PreparedHyperAlertID NOT IN SELECT FROM ProcessedNodes 29 Chapter 4 Implementation 30 4 5 Transitive Edge Exclusion In the prepare for relationship there may exist such condition that A prepares for B B prepares for C and A prepares for C also see figure 4 7 Tf we think the relationship can propagate then A prepares for C can be got from A prepares for B and B prepares for C If there exists a lot of such relationships it will make the correlation graph hard to read and understand It is better that we take these out from the prepare for relationships If we think it in the graph A prepares for C in the above example is a transitive edge So we call this process Transitive Edge Exclusion We call the edge A C is a 2 hop edge and A D is a 3 hop edge in figure 4 7 Here is the way we do the Transitive Edge Exclusion We will use the notation A B to represent that A prepares for B The basic idea is we enumerate all the possible transitive edges which may exist in this graph For example if figure 4 7 represents all the prepare for relationships then all the possible transitive edges in figure 4 7 are A C A D and B D We save this result
37. will be stored in three tables HATFact is to store the fact information HATPrereg is to store the prerequisite information and HAT Conseq is to store the consequence information Fact has two attributes FactName and FactType FactName is stored in the AttrName column of the table HAT Fact and FactType is stored in the AttrType of HATFact For example the two tuples in figure 4 2 c represent the fact information of the hyper alert type FTP_Syst defined in figure 4 5 Each Prerequisite or Conseguence may contain a set of Predicates This Predicate has the similar structure with it in the Predicates section but small difference The difference is in the argument part Instead of Pos and Attr attributes in the Predicates section it has ArgName here to specify the exact argument name Also it has an d attribute which is used to refer to the Arg defined in the Predicates section Since we assume there is no negation and the hyper alerts are reasoned using prerequisite and consequence sets we only need to keep the predicates appearing in the prerequisite and the consequence in these two tables We take the first hyper alert type FTP_Syst defined in figure 4 5 as an example Figure 4 2 d says the hyper alert type FTP Syst has one predicate ExistService in its prerequisite and this pred icate takes the fact attribute DestIPAddress as its first argument DestPort as its second argument Similarly figure 4 2 e says FTP_Syst has one predicate GainO
38. 19 Sadmind_Amslverify _Overflow66228 Sadmind_Amslverify _Overflow66221 Sadmind_Amslverify _Overflow66230 c Destination IP 172 016 112 010 d Destination IP 172 016 114 020 Sadmind_Amslverify _Overflow66207 Sadmind_Amslverify _Overflow66178 Sadmind_Amslverify _Overflow66208 Sadmind_Amslverify _Overflow66179 Sadmind_Amslverify _Overflow66210 Sadmind_Amslverify _Overflow66181 Sadmind_ Ping66048 Sadmind_Amslverify _Overflow66212 Sadmind_Amslverify _Overflow66183 Sadmind_Amslverify _Overflow66234 Sadmind_Amslverify _Overflow66200 Sadmind_Amslverify _Overflow66238 Sadmind_Amslverify _Overflow66204 e Destination IP 172 016 112 050 f Destination IP 172 016 114 030 Figure 5 2 The hyper alert correlation graphs discovered in the dmz network traffic of LLDOS1 0 Chapter 5 Experimental Results 43 Email_Almail_Overflow63896 Sadmind_Amslverify_Overflow64063 Mstream Zombie64072 ID NS a Sadmind_Amslverify_Overflow64066 SH tream Zombie64154 stream Zombi Sadmind Amslverify Overflow63967 FTP Put63997 Mstream Zombie64167 Sadmind Amslverify Overflow63963 Figure 5 3 The hyper alert correlation graph discovered in the inside network traffic of LLDOS 2 0 2 Stream DoS64163 Sadmind Amslverify Overflow65507 A a Sadmind Amslverify Overflow65511 Figure 5 4 The hyper alert correlation graph discovered in the dmz network traffic of LLDOS
39. 52 1 19 5 GainRootAccess 152 1 19 7 This hyper alert says that there are buffer overflow attacks against sadmind at IP addresses 152 1 19 5 and 152 1 19 7 and the attacker may gain root access as a result of the attacks A hyper alert may correspond to one or several related alerts If an IDS reports one alert for a certain attack and the alert has all the information needed to instantiate a hyper alert a hyper alert can be generated from the alert However some IDSs may report a series of alerts for a single attack For example EMERALD may report several alerts within the same thread related to an attack that spreads over a period of time In this case a hyper alert may correspond to the aggregation of all the related alerts Moreover several alerts may be reported for the same type of attack in a short period of time Our definition of hyper alert allows them to be treated as one hyper alert and thus provides flexibility in the reasoning about alerts Certain constraints are necessary to make sure the hyper alerts are reasonable However since our hyper alert correlation method does not depend on them directly we will discuss them after introducing our method Ideally we may correlate a set of hyper alerts with a later hyper alert together if the consequences of the former ones imply the prerequisite of the latter one However such an approach may not work in reality due to several reasons First the attacker may not always prepare for c
40. 9 gt lt ImplyingArg gt lt ImpliedArg id 7 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implication gt lt ImplyingName gt GainSMTPInfo lt ImplyingName gt lt ImpliedName gt GainInformation lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 10 gt lt ImplyingArg gt lt ImpliedArg id 7 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implication gt lt ImplyingName gt GainTerminalType lt ImplyingName gt lt ImpliedName gt GainInformation lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 11 gt lt ImplyingArg gt lt ImpliedArg id 7 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt gt lt Implication gt lt ImplyingName gt GainAccess lt ImplyingName gt lt ImpliedName gt SystemCompromised lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 4 gt lt ImplyingArg gt lt ImpliedArg id 18 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt 72 Appendix A Knowledge Base Used In The Experiment lt Implication gt lt ImplyingName gt SystemCompromised lt ImplyingName gt lt ImpliedName gt SystemAttacked lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 18 gt lt ImplyingArg gt lt ImpliedArg id 17 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt lt Implication Phantom Yes gt lt ImplyingName gt Gain0SInfo lt ImplyingName gt lt ImpliedName gt 0SSolaris lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 8 gt
41. Abstract CUI YUN A Toolkit for Intrusion Alerts Correlation Based on Prerequisites and Consequences of Attacks Under the direction of Dr Peng Ning Intrusion Detection has been studied for about twenty years Intrusion Detection Systems IDSs are usually considered the second line of defense to protect against malicious activities along with the prevention based security mechanisms such as authentication and access control However tradi tional IDSs have two major weaknesses First they usually focus on low level attacks or anomalies and raise alerts independently though there may be logical connections between them Second there are a lot of false alerts reported by traditional IDSs which are mixed with true alerts Thus the intrusion analysts or the system administrators are often overwhelmed by the volume of alerts Motivated by this observation we propose a technique to construct high level attack scenarios by correlating low level intrusion alerts using their prerequisites and consequences The prerequisite of an alert specifies what must be true in order for the corresponding attack to be successful and the consequence describes what is possibly true if the attack indeed succeeds We conjecture that the alerts being correlated together have a higher possibility to be true alerts than the uncorrelated ones If this is true through this correlation we can not only construct the high level attack scenarios but also differentiate bet
42. D ExistService DestIP DestPort GainOrderLogFile DestIP HTTP PHF s gt ulnerableCGI DestIP ND GainFileInfo DestIP ND ExistService DestIP Dest Port GainRootAccess DestIP HTTP PHP Read lt gt gt ulnerableCGI DestIP ND GainFileInfo DestIP ND ExistService DestIP DestPort gt gt GainFileInfo DestIP Appendix A Knowledge Base Used In The Experiment 93 ND GainOSInfo DestIP ND ExistService DestIP DestPort Hyper alert Type Prerequisite Consequence HTTP_RobotsTxt ExistService DestIP DestPort GainInformation DestIP HTTP SGI Wrap VulnerableCgi DestIP GainFilelnfo DestIP AND GainOSInfo DestIP AND GainFilelnfo DestIP AND ExistService DestIP DestPort HTTP Shells VulnerableCGIBin DestIP GainAccess DestIP HTTP_SiteCsc_Access lt gt gt ulnerableWebServer DestIP ND ExistService DestIP Dest Port GainDBAccess DestIP GainAccess DestIP HTTP TestCgi lt gt ulnerableWebServer DestIP ND GainFilelnfo DestIP ND ExistService DestIP Dest Port gt gt SystemAttacked DestIP GainFileInfo DestIP HTTP_Unix_Passwords td xistService DestIP DestPort ND GainOSInfo DestIP GainRootAccess DestIP HTTP WebFinger lt gt ulnerableCgi DestIP ND GainFileInfo DestIP ND ExistService DestIP DestPort HTTP Websendmail lt gt gt ulnerableCGI DestIP ND GainFilelnfo
43. Daemon DestIP ND ExistService DestIP DestPort GainAccess DestIP POP_QPopAuth _Overflow lt gt ulnerablePOPDaemon DestIP ND ExistService DestIP DestPort GainRootAccess DestIP POP_QPopCommand _Overflow lt gt ulnerablePOPDaemon DestIP ND ExistService DestIP DestPort gt GainRootAccess DestIP Port_Scan Exist Host DestIP ExistService DestIP DestPort Queso_Scan GainOSInfo DestIP GainNetworkInfo DestIP Rexec GainAccess DestIP SystemCompromised DestIP AND GainAccess SrcIP RIPAdd Rlogin_Froot VulnerableRlogin DestIP AND GainOSInfo DestIP GainRootAccess DestIP SourceRoute BypassA uthentication Sadmind_Amslverify VulnerableRPCService DestIP GainAccess DestIP Overflow AND ExistService DestIP DestPort Satan GainVulnerability DestIP ServiceScan ExistService DestIP Dest Port ExistHost DestIP Smurf Exist Host DestIP SystemAttacked DestIP Appendix A Knowledge Base Used In The Experiment 95 Hyper alert Type Prerequisite Consequence SNMP Set ExistService DestIP DestPort AND GainOSInfo DestIP SystemAttacked DestIP SNMP Suspicious Get ExistService DestIP DestPort GainTnformation DestIP SSH_Detected GainTnformation DestIP Stream_DoS Ready ToLaunchStreamDOSAttack DOSAttackLaunched Sun SNMP Backdoor E
44. NN A A ra A 30 The algorithm used to generate all the possible transitive edges 31 The algorithm used to do the adjustable graph reduction 33 The algorithm used to do the graph decompositionn 36 The only hyper alert correlation graph discovered in the inside network traffic of LEDOS Oda eve e Shah Goan tee xe ij BLA dle ee nt A a a 41 The hyper alert correlation graphs discovered in the dmz network traffic of LLDOS1 0 42 The hyper alert correlation graph discovered in the inside network traffic of LLDOS Z a A a ak E NI A da ir e dad OS A 43 The hyper alert correlation graph discovered in the dmz network traffic of LLDOS A D cis Bay Wan ha hs O RR TA 43 A small hyper alert correlation discovered in initial analysis 47 The fully reduced graph for the largest aggregated hyper alert correlation graph 48 Sizes of the reduced graphs w r t the interval threshold for the largest hyper alert correlation graph Boril o Wa AA A a ni Se S 49 A fully reduced hyper alert correlation graph resulting from graph decomposition with Cu Cluster ID 1 DestIP 010 020 001010 52 A fully reduced hyper alert correlation graph resulting from graph decomposition with C 2 Cluster ID 10 SrcIP 010 020 011 251 DestIP 010 020 001 010 53 vii Chapter 1 Introduction 1 1 Computer Security and Intrusion Detection System With the Internet having grown enormously
45. PAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name GainAdmindInfo gt lt Arg id 5 ArgName DestIPAddress gt lt Arg gt lt Arg id 6 ArgName DestPort gt lt Arg gt lt Predicate gt lt Consequence gt lt gt lt HyperAlertType gt lt HyperAlertType Name DNS_HInfo gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt Appendix A Knowledge Base Used In The Experiment 75 lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name Gain0SInfo gt lt Arg id 8 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Email_Almail_Overflow gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ExistService gt lt Arg id 22 Ar
46. ReadyToLaunchDDOSAttack gt lt Predicate gt lt Predicate Name SendMailInDebugMode gt lt Arg id 14 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name SMTPSupportEhlo gt lt Arg id 15 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt 1 lt Predicate Name SMTPSupportTurn gt lt Arg id 16 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt gt lt Predicate Name SystemAttacked gt lt Arg id 17 Pos 1 Attr lt varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name SystemCompromised gt lt Arg id 18 Pos 1 Attr lt varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name VulnerableCGIBin gt lt Arg id 19 Pos 1 Attr lt varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name VulnerableAlMailPOP3Server gt lt Arg id 20 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name VulnerableSadmind gt lt Arg id 21 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name ExistService gt lt Arg id 22 Pos 1 Attr varchar 15 gt lt Arg gt lt Arg id 23 Pos 2 Attr int gt lt Arg gt lt Predicate gt lt Predicate Name DNS_HInfo gt lt Arg id 24 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name 0SSolaris gt 70 Appendix A Knowledge Base Used In The Experiment lt Arg id 25 Pos 1 Attr
47. SInfo in its consequence and it takes Chapter 4 Implementation 26 the fact attribute DestIPAddress as its first and only argument One important part in parsing the hyper alert types is to expand the consequence predicate set based on the implications For example if a hyper alert type has only one predicate GainRootAccess DestIP in its consequence set and according to the table Implication GainRootAccess DestIP implies GainAccess DestIP then we will add GainAccess DestIP into the hyper alert type s con sequence set To take into account indirect implications this process should be repeated iteratively until no more predicates can be added 4 2 Alert Preprocessor The alert preprocessor processes the alerts to generate hyper alerts and instantiate the prerequisite and consequence sets of each hyper alert There are at least two choices in reasoning about the instantiated predicates during the correlation phase The first is to allow the correlation engine to reason about the related predicates e g GainRootAccess IP A GainAccess IP_A using the information stored in the knowledge base directly Such an approach is probably necessary for real time correlation of hyper alerts However it requires more development effort and do not take full advantage of the RDBMS s query processing capability The second approach is to instantiate the predicates specified in the prerequisite and consequence sets as well as those impl
48. YRD Dedication To my parents Liangcheng Cui Meigi Ma and my husband Deming Mao il Acknowledgments I would like to express my sincere appreciation to my advisor Dr Peng Ning for his patient guidance and constant support His careful and critical comments significantly improves the content and presentations of this thesis His knowledge and his dedication to research will be of life long benefits for me I am grateful to my committee members Dr Douglas Reeves and Dr Gregory Byrd for their valuable comments suggestions and encouragements Thanks also to the colleagues in the Intrusion Detection Research Group Pai Peng Dingbang Xu Kun Sun Yan Zhai and Donggang Liu for all the help and support Finally I am deeply grateful to my husband Deming Mao for his encouragement and support I am indebted to my parents Liangcheng Cui and Meigi Ma who have been giving me constant support all my life This work is partially supported by the U S Army Research Office under grant DAAD19 02 1 0219 and by the National Science Foundation under grant CCR 0207297 iii Table of Contents List of Tables vi List of Figures vii 1 Introduction 1 1 1 Computer Security and Intrusion Detection System 1 12 Summary of Contribution a i wanda ay a aly ty ee Di Mi ah Svi a A 3 1 3 Organization of the Thess 3 2 Related Work 4 3 A Framework for Alert Correlation 7 3 1 Prerequisite and Consequ
49. a gt lt lt i Figure 5 8 A fully reduced hyper alert correlation graph resulting from graph decomposition with Ce Cluster ID 1 DestIP 010 020 001 010 Figures 5 8 and 5 9 show a decomposed graph for C and C 2 respectively Both graphs are fully reduced to save space All the hyper alerts in Figure 5 8 are destined to 010 020 001 010 Figure 5 8 shows several possible attack strategies The most obvious ones are those that lead to the Mstream_Zoombie and TrinooDaemon However there are multiple paths that lead to these two hyper alerts Considering the fact that multiple attackers participated in the DEF CON 8 CTF event we cannot conclude which path caused the installation of these daemon programs Indeed it is possible that none of them is the actual way since the IDS may have missed some attacks Figure 5 8 involves 75 source IP addresses including IP address 216 136 173 152 which does not belong to the CTF subnet We believe that these attacks belong to different sequences of attacks since there were intensive attacks from multiple attackers who participated in the CTF event Chapter 5 Experimental Results 53 HP OpenView SNMP Backdoor gt HTTP_NphTestCgi HP OpenView SNMP Backdoor A MI ETIP she HTTP_TestCgi HTTP_WebFinger HTTP_WebSite_Uploader Kerberos_User_Snarf Sun_SNMP_Backdoor Figure 5 9 A fully reduced hyper alert correlation graph res
50. about twenty years An excellent overview of intrusion detection techniques and related issues can be found in a recent book by Bace 7 Several alert correlation methods have been proposed These methods fall into three classes The first class correlates alerts based on the similarities between alert attributes Though they are effective for correlating some alerts e g alerts with same source and destination TP addresses they cannot fully discover the causal relationships between related alerts The second class bases alert correlation on attack scenarios specified by human users or learned through training datasets This is similar to misuse detection Obviously these methods are restricted to known attack scenarios The third class is based on the preconditions and consequences of individual attacks Several alert correlation techniques have been proposed to facilitate analysis of intrusions In 33 a probabilistic method was used to correlate alerts using similarity between their features This belongs to the first category As we discussed above this method is not suitable for fully discover ing causal relationships between alerts In 30 a similar approach was applied to detect stealthy portscans along with several heuristics Though some such heuristics e g feature separation heuris tics 30 may be extended to general alert correlation problem the approach cannot fully recover the causal relationships between alerts either The te
51. ack strategies and help a user understand the overall situation of attacks As we discussed earlier the reduction of hyper alert correlation graphs can be controlled with interval constraints Figure 5 7 shows the numbers of nodes and edges of the reduced graphs for different interval sizes The shapes of the two curves in Figure 5 7 indicate that most of the hyper alerts that are of the same type occurred close to each other in time Thus the numbers of nodes and edges have a deep drop for small interval thresholds and a flat tail for large ones A reasonable Chapter 5 Experimental Results 50 guess is that some attackers tried the same type of attacks several times before they succeeded or gave up Due to space reasons we do not show these reduced graphs 5 3 3 Focused Analysis Focused analysis can help filter out the interesting parts of a large hyper alert correlation graph It is particularly useful when a user knows the systems being protected or the potential on going attacks For example a user may perform a focused analysis with focusing constraint DestIP ServerIP where Server P is the IP address of a critical server to find out attacks targeted at the server As another example he she may use SrcIP ServerIP V DestIP ServerIP to find out attacks targeted at or originated from the server suspecting that the server may have been compromised In our experiments we tried a number of focusing constraints after we learned so
52. actName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt l lt Predicate Name ExistFTPService gt lt Arg id 3 ArgName DestIPAddress gt lt Arg gt lt Predicate gt gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt Appendix A Knowledge Base Used In The Experiment 80 lt Prerequisite gt lt HyperAlertType gt lt HyperAlertType Name HTTP ActiveX gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ActiveXEnabledBrowser gt lt Arg id 2 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name SystemCompromised gt lt Arg id 18 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name HTTP_Cisco_Catalyst_Exec gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt
53. algorithm used to do the graph decomposition AND alert2 IN SELECT FROM NewlyAddedAlerts UNION SELECT DISTINCT alert2 FROM AlertPairs WHERE assigned 0 AND alert2 NOT IN SELECT FROM NewlyAddedAlerts AND alertl IN SELECT FROM NewlyAddedAlerts 36 After we set all the alerts into clusters we can assign sub graph ID to each prepare for relation ship Each cluster has a unique cluster ID we can use this cluster ID as the sub graph ID One thing we need to keep in mind is that it is possible that two alerts of a prepare for relationship belong to Chapter 4 Implementation 37 different clusters sub graphs An auxiliary table partGraphEdges is used in assigning sub graph id It has four attributes PreparingHyperAlertID PreparedHyperAlertID PreparingGraphID and Pre paredGraphID We use PreparingGraphID to represent the sub graph id of the preparing hyper alert and use PreparedGraphID to represent the sub graph id of the prepared hyper alert First we copy the prepare for relationships from table GraphEdges to table partGraphEdges We don t copy all the prepare for relationships but the prepare for relationships of one graph which is specified by the user We set both PreparingGraphID and PreparedGraphID to 0 initially Then set PreparingGraphID and PreparedGraphID separately based on which cluster that the preparing hyper alert and the prepared hyper alert belongs to respectively Only the prepare for relationships whi
54. ame DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ReadyToLaunchDDOSAttack gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name DDOSAgainst gt lt Arg id 27 ArgName DestIPAddress gt lt Arg gt Appendix A Knowledge Base Used In The Experiment 86 lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name TCP_Urgent_Data gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Consequence gt lt Predicate Name SystemAttacked gt lt Arg id 17 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name TelnetEnvaAll gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Consequence gt lt Predicate Name SystemAttacked gt lt Arg id 17 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperA
55. and globally people care more and more about the security problems Carnegie Mellon University s Computer Emergency Response Team s CERT 1 Coordination Center reported 3 734 attacks in 1998 and 52 658 attacks in 2001 Not only does the number of attacks increase quickly the attacks are also more and more sophisticated According to CERT s Internet Security Overview the sophistication of attacks is increasing and there are usually several stages involved in one attack So how to detect and respond to the attacks is becoming very important Intrusion detection has been used to protect information systems along with prevention based mechanisms such as authentication and access control Intrusion detection systems can be roughly classified as anomaly detection and misuse detection Anomaly detection is based on the normal behavior of a subject e g a user or a system Any action that significantly deviates from the normal behavior is considered intrusive Misuse detection is based on the characteristics of known attacks or system vulnerabilities which are also called signatures Any action that matches the signature is considered intrusive Both anomaly detection and misuse detection have their limitations For anomaly detection it is difficult to define what are normal behaviors and what are malicious behaviors As to misuse detection it detects attacks based on signatures of known attacks and matches the traffic pattern with these signa
56. ataset 2 that the three utilities can greatly reduce the complexity of the correlated alerts while at the same time keeping the structure of the attacks 1 2 Summary of Contribution The contribution of this thesis is twofold The first is the development of an intrusion alert correlation tool based on the framework we proposed which uses the causal relationships among the alerts to correlate them Second some experiments are performed to evaluate the effectiveness of this tool The experiments on DARPA 2000 evaluation datasets show that this method can not only uncover the attack scenario but also filter out most of the false alerts The experiments with DEFCON 8 CTF dataset further show the three utilities adjustable graph reduction focused analysis and graph decomposition are very helpful in analyzing intensive alerts 1 3 Organization of the Thesis The remainder of this thesis is organized as follows The next chapter discusses the related work on intrusion alert correlation Chapter 3 presents the framework on which this tool is based Chapter 4 describes the implementation details of the tool Chapter 5 presents the experimental results of this tool Chapter 6 concludes this thesis and points out some future work Appendix A gives the knowledge base we use in this tool Appendix B gives the summary of Java classes of the tool and Appendix C is the user manual Chapter 2 Related Work Intrusion detection has been studied for
57. attacker installed and started the mstream daemon and master programs The fourth Chapter 5 Experimental Results 41 Sadmind_Amslverify_Overflow67428 AR _zE O Sadmind_Amslverify_Overflow67430 Ss gt 3 e ZAS i z l A z NU gt 2 e Sadmind_Amslverify_Overflow67420 4 LARS Mstream_Zombie67767 ZDA E a a DIST Sadmind_Amslverify_Overflow67422 gt gt pi A x Mstream Zombie67537 gt ty Z A Po Email_Almail_Overflow67304 Ss Sadmind_Amslverify_Overflow67432 gt pe 4 Sadmind Amslverify Overflow67434 gt a gt _ gt Se Figure 5 1 The only hyper alert correlation graph discovered in the inside network traffic of LLDOS 1 0 stage consists of alerts corresponding to the communications between the DDOS master and daemon programs Finally the last stage consists of the DDOS attack We can see clearly that the hyper alert correlation graph reveals the structure as well as the high level strategy of the sequence of attacks This hyper alert correlation graph is still not perfect First the two Email_Almail_Overflow hyper alerts shown in gray in Figure 5 1 are false alerts and are mis correlated with the Rsh alerts though it is possible that an attacker uses these attacks to gain access to the victim system and then copy the DDOS program with Rsh Second the FTP_Syst hyper alert is also a false one it is correlated with one of the Sadmind_Pings b
58. ch have the same PreparingGraphID and PreparedGraphID are kept We save them into the table GraphEdgeDecomposed which has three attributes Prepar ingHyperAlertID PreparedHyperAlertID and graphID The other prepare for relationships which has different PreparingGraphID and PreparedGraphID are broken into different sub graphs They are actually some isolated nodes in the sub graphs 4 9 Important Tables Here is the summarization of the important tables generated by the tool CorrelatedAlerts It keeps the original prepare for relationships which are the results from the alert correlation engine GraphEdges Basically it has one more column based on CorrelatedAlerts which is the graph id information This table has the information that which graph does each prepare for relationship belong to GraphEdgesFocus It is the result generated by focused analysis Actually it is a subset of GraphEdges GraphEdgesDecomposed Similar with GraphEdgesFocus it is a subset of GraphEdges and is generated by graph decomposition SimplifiedGraphEdges This table keeps the results when we apply the adjustable graph re duction utility upon the original hyper alerts prepare for relationships Its structure is the same with GraphEdges The difference between them is GraphEdges is the graph information based on original prepare for relationships but SimplifiedGraphEdges is the graph information based on aggregated prepare for relationship That is GraphEdges
59. chnique in 18 uses data mining to group all the similar alarms based on their root causes Though they can reduce the false positive rate they cannot provide the attack scenario Techniques for aggregating and correlating alerts have been proposed by others 11 Tn particu lar the correlation method in 11 uses a conseguence mechanism to specify what types of alerts may follow a given alert type This belongs to the second category However the consequence mechanism only uses alert types the probes that generate the alerts the severity level and the time interval between the two alerts involved in a consequence definition which do not provide sufficient informa tion to correlate all possibly related alerts Moreover it is not easy to predict how an attacker may Chapter 2 Related Work 5 arrange a sequence of attacks In other words developing a sufficient set of consequence definitions for alert correlation is not a solved problem Another approach which also belongs to the second category has been proposed to learn alert correlation models by applying machine learning techniques to training data sets embedded with known intrusion scenarios 10 This approach can automatically build models for alert correlation however it requires training in every deployment and the resulting models may overfit the training data thereby missing attack scenarios not seen in the training data sets The alert correlation techniques that we pr
60. conference 1997 Ritchey R and Ammann P Using model checking to analyze network vulnerabilities In Proc of IEEE Sympostum on Security and Privacy pages 156 165 May 2000 Sheyner O Haines J Jha S Lippmann R and Wing J Automated generation and analysis of attack graphs In Proc of IEEE Symposium on Security and Privacy May 2002 Staniford S Hoagland J and McAlerney J Practical automated detection of stealthy portscans To appear in Journal of Computer Security 2002 Staniford Chen S Cheung S Crawford R Dilger M Frank J Hoagland J Levitt K Wee C Yip R and Zerkle D GrIDS a graph based intrusion detection system for large network In Proc of the 19th National Information System Security Conference Volume 1 pages 361 370 1996 Templeton S and Levit K A requires provides model for computer attacks In Proc of New Security Paradigms Workshop pages 31 38 September 2000 Valdes A and Skinner K Probabilistic alert correlation In Proc of the 4th Intl Symposium on Recent Advances in Intrusion Detection RAID 2001 pages 54 68 2001 Vigna G and Kemmerer R A NetSTAT A network based intrusion detection system In Journal of Computer Security 7 pages 37 71 1999 Appendix A Knowledge Base Used In The Experiment A 1 XML Schema for Knowledge Base lt xml version 1 0 encoding UTF 8 gt lt xsd schema xmlns xsd http www w3 org 2001 XMLSchema xmlns
61. ctions this difference leads to the three utilities for interactive alert analysis M Correlator 26 first translates an alert to its internal incident report format It then processes them using the vulnerability requirements of the incident type together with the knowledge of the protected network s topology It computes two parameters one is the relevance score between the alert and the incident in its fact base the other is the priority of the asset that the alert targets Based on these two parameters M Correlator keeps the alerts that will cause the greatest risk to the monitored network M2D2 21 introduces a formal information model for security information representation and correlation The model includes four types of information information system characteristics vul nerabilities security tools and events and alerts GrIDS 31 uses activity graphs to represent the causal structure of network activities and detect Chapter 2 Related Work 6 propagation of large scale attacks Our method also uses graphs to represent correlated alerts However unlike GrIDS in which nodes represent hosts or departments and edges represent network traffic between them our method uses nodes to represent alerts and edges the relationships between the alerts Several languages have been proposed to represent attacks including STAT 34 14 Colored Petri Automata CPA LAMBDA 9 and MuSig 20 and its successor 25 In particular LAMBDA us
62. e aggregation engine on the decomposed sub graphs Decomposition Aggregation Time Interval is similar as Aggregation Time Interval in section 4 Decomposition Output is used to specify the output graph C 4 Sample Execution Procedure 1 java Correlator Correlation TransitiveExclusion userName password 2 dot Tps darpa dmzl txt o outputFileName ps To generate the graph using GraphViz Here darpa dmzl txt is the file name we specified for the Original Graph Output in Correlator properties file The outputFileName is a ps formatted file which will be generated by GraphViz C 5 Trouble Shooting 1 Make sure the db Driver and dbURL in the property file is set correctly Remember the tool uses DataManager getConnection url user password to connect to the database 2 If you use the JDBC ODBC driver it may take very long time to execute the SOL statement to delete the transitive edges If this does happen either you have patience to wait or you just execute this SOL statement by hand 3 If you use Java 2 SDK v1 4 and the JDBC ODBC drvier at the same time you may have some problem to communicate with the database You can use Java 2 SDK v1 3 to get around the problem List of References http www research att com sw tools graphviz http www iss net http xml apache org Peng Ning Yun Cui Douglas S Reeves Analyzing Intensive Intrusion Alerts Via Correlation To appear in Proceedings of the 5
63. e alert pair information The attribute assigned is used as an indicator of whether this alert pair has been assigned to a sub graph We set it to 0 initially which means this alert pair hasn t been assigned into cluster yet When it is assigned we set it to 1 The algorithm in figure 4 10 is then used to cluster the alerts into different clusters The auxiliary table NewlyAddedAlerts has one attribute HyperAlertID Oueryl in figure 4 10 SELECT alertl alert2 FROM AlertPairs WHERE assigned 0 AND alert1 IN SELECT FROM NewlyAddedAlerts OR alert2 IN SELECT FROM NewlyAddedAlerts Ouery2 in figure 4 10 SELECT DISTINCT alertl FROM AlertPairs WHERE assigned 0 AND alert NOT IN SELECT FROM NewlyAddedAlerts Chapter 4 Implementation select an unassigned alert pair in AlertPairs and set assigned 1 start a new cluster a linked list in the dynamic array and nsert the two alerts of this pair h1 h2 into this cluster write hl and h2 into NewlyAddedAlerts using query 1 to find all the unassigned alert pairs in AlertPairs which has at least one alert in NewlyAddedAlerts sing query 2 to update NewlyAddedAlerts with the alerts in these pairs but they were not in the original NewlyAddedAlerts insert these alerts into cluster set pairs generated by gueryl as assigned exist unassigned edges NewlyAddedA lerts empty Figure 4 10 The
64. e attribute names each tuple in CorrelatedAlerts indicates the hyper alert with the ID PreparingHyperAlertID prepares for the one with the ID PreparedHyperAlertID With the two auxiliary tables PreregSet and Conseg et it is trivial to discover the aforementioned prepare for relations We use the following SQL query to perform this task The result of the SQL query is inserted into the CorrelatedAlerts table It is not difficult to verify that the SQL statement discovers all and only the hyper alert pairs such that the first one of the pair prepares for the second one Query used to generate all the prepare for relationships SELECT DISTINCT c HyperAlertID p HyperAlertID FROM PreregSet p ConseqSet c WHERE p EncodedPredicate c EncodedPredicate AND c end time lt p begin time 4 4 Separating Correlation Graphs After we have all the prepare for relationships we need to output them as hyper alerts correlation graphs The first thing we should do is to separate all the prepare for relationships into several Chapter 4 Implementation 28 graphs We use nodes to represent hyper alerts and edges to represent prepare for relationships All the graphs satisfy the following two conditions First in any single graph all nodes are connected with each other Second any two graphs don t have any common nodes or common edges We will refer a prepare for relationship as an edge in the following sections The table GraphEdges is the output of this
65. e discussed before graph reduction is used to reduce the complexity of a graph This utility not only can be applied on graphs generated by original prepare for relationships but also it can be applied on the results generated by focused analysis and graph decomposition In this implementation we use the interval constraint to do the graph reduction That is if the time interval between two alerts are less than the threshold user provides these two alerts are aggregated together Prepare for relationships are browsed according to their graph id For each graph it will aggre gate the same type of hyper alerts based on their time interval First the hyper alerts are clustered by different hyper alert types For each type of hyper alerts one cluster they are sorted by their timestamps Among each cluster if the interval between the two adjacent alerts is less than the threshold then these two adjacent alerts can be aggregated into one alert One auxiliary table IDMapping is used to keep the mapping relationship between the original alert id and the new aggregated alert id Once finishing aggregation the next step is to build up the aggregated prepare for relationship There will be an aggregated edge between two aggregated alerts A1 and A2 if there is an original edge between two original alerts O1 and O2 such that O1 has been aggregated into A1 and O2 has been aggregated into A2 Figure 4 9 is the algorithm we use to do the adjustable graph
66. e reported by an IDS For the attack to be successful there must exist a host at IP address VictimIP and the corresponding sadmind service must be vulnerable to buffer overflow attacks The attacker may gain root privilege as a result of the attack Given a hyper alert type a hyper alert instance can be generated if the corresponding attack is detected and reported by an IDS For example we can generate a hyper alert instance of type SadmindBufferOverflow from a corresponding alert The notion of hyper alert instance is formally defined as follows Definition 2 Given a hyper alert type T fact prerequisite consequence a hyper alert instance h of type T is a finite set of tuples on fact where each tuple is associated with an interval based timestamp begin_time end_time The hyper alert h implies that prerequisite must evaluate to True and all the predicates in conseguence might evaluate to True for each of the tuples Notation wise for each tuple t in h we use t begin time and t end_time to refer to the timestamp associated with t The fact component of a hyper alert type is essentially a relation schema as in relational databases and a hyper alert is a relation instance of this schema One may point out that an alternative way is to represent a hyper alert as a record which is equivalent to a single tuple on fact However such an alternative cannot accommodate certain alerts possibly reported by an IDS For example an IDS may r
67. ecause an attacker may use FTP Syst to gain the OS information and then launch an Sadmind_Ping attack Third the attacker used a series of telnet as a part of the sequence attacks and RealSecure detects one of them But this graph does not include the corresponding hyper alert The reason we miss the telnet alert is because we cannot tell whether the telnet is a normal user behavior or an attacker behavior Fourth because our correlator depends on the underlying IDS for alert information if the underlying IDS misses some alerts we may also miss them If the underlying IDS reports more false alerts we also have a chance to correlate more In this example RealSecure Chapter 5 Experimental Results 42 Sadmind_Amslverify _Overflow66189 Sadmind_Amslverify Sadmind_Amslverify Overflow66191 _Overflow66240 Sadmind_Amslverify _Overflow66193 Sadmind_ Ping66111 FTP_Syst 66006 Sadmind_Amslverify _Overflow66195 Sadmind_Amslverify Sadmind_Amslverify Overflow66197 _Overflow66226 Sadmind_Amslverify _Overflow66199 a Destination IP 172 016 115 020 b Destination IP 172 016 114 010 Sadmind_Amslverify _Overflow66185 Sadmind_Amslverify _Overflow66187 Sadmind_Amslverify _Overflow66215 Sadmind_Amslverify _Overflow66232 Sadmind_ Ping66063 Sadmind_Amslverify _Overflow66217 Sadmind_Amslverify _Overflow66236 Sadmind_Amslverify _Overflow662
68. ed in my thesis The experimental results showed that the developed tools were very helpful in analyzing intrusion alerts First they can be used to construct high level attack scenarios from the low level alerts reported by IDS In the experiments with DARPA 2000 intrusion detection scenario specific datasets we have successfully constructed attack scenarios from the alerts and the constructed scenarios matched the description of the data set very well Second they can be potentially used to differentiate true alerts from false alerts with a high accuracy In the experiments we reduced the false alert rate from 93 6 to 5 26 in the best case and from 98 59 to 40 even in the worst case At the same time the soundness measures of our technique that is the correctness of the alerts correlated are above 90 for all experiments The experiments with the DEFCON CTF 8 dataset also showed the three utilities could be used to reduce the complexity of the correlated alerts while keeping the structure of the attacks However the experiments also showed that we still need to improve our techniques The alerts correlated are not 100 right Some of the true alerts are missed and some false alerts are correlated although it is only a small portion compared with the truly correlated alerts 55 Chapter 6 Conclusions and Future Work 56 6 2 Future Work 6 2 1 Real Time Correlator In this thesis work I developed an offline toolkit to correlate int
69. ement name Consequence gt lt xsd complexType gt lt xsd seguence gt lt xsd element ref Predicate minOccurs 0 maxOccurs unbounded gt lt xsd sequence gt lt xsd complexType gt lt xsd element gt lt xsd element name Predicate gt Appendix A Knowledge Base Used In The Experiment 68 lt xsd complexType gt lt xsd sequence gt lt xsd element name Arg minOccurs 0 maxOccurs unbounded gt lt xsd complexType gt lt xsd attribute name id type xsd positivelnteger use required gt lt xsd attribute gt lt xsd attribute name ArgName type xsd string use required gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt xsd seguence gt lt xsd attribute name Name type xsd string use required gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt xsd schema gt A 2 Knowledge Base Used for DARPA Dataset lt xml version 1 0 encoding UTF 8 gt lt KnowledgeBase xmlns ID NCSU xmlns xsi http www w3 org 2001 XMLSchema instance xsi schemaLocation ID NCSU newKnowledgeBase xsd gt lt based on 5 gt lt add implication between ehlo and turn gt lt l Predicates gt lt Predicates gt lt Predicate Name CiscoCatalyst3500XL gt lt Arg id 1 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name ActiveXEnabledBrowser gt
70. ence of Attacks 7 3 2 Hyper alert Type and Hyper alert 8 3 2 1 Temporal Constraints for Hyper alerts 12 3 3 Hyper alert Correlation Graph L 12 3d Utilities vA ee eC Bes Y al a dar dar a IRA lt Be Z 15 3 4 1 Adjustable Graph Reduction 15 3 4 2 Focused Analysis oca a eee eS RRA Ee ee a ee 16 3 4 3 Graph Decomposition 17 4 Implementation 19 4 1 Knowledge Base ccoa E Ga ata ae e ee ee WA Ae de ea 19 41 1 Database Structure cya aise A ses SR ti BAA A ee ES 19 4 1 2 Knowledge Base XML File 21 A 2 gt Alert Preprocessor La a tude oe A ar de da dla ere dd ds 26 4 3 lt Correlatlon Engine aia a A A ad a 27 4 4 Separating Correlation Graphs 0 pe ee 27 4 5 Transitive Edge Exclusion 30 4 6 Adjustable Graph Reduction 32 A Hocused Analysis sad kPa AC AA ee AAA a 33 4 8 Graph Decomposition 2 2 2 0 0 e ee 34 4 9 important Tables ir e Gee a SN A SS AAA A ea dS 37 4 10 Property Biles or ze Za dtu a Re AAA di ne a as 38 5 Experimental Results 39 bil Experiment Setup escola a e e ada 39 5 2 Experiment on DARPA 2000 dataset 40 5 2 1 Effectiveness of Alert Correlation 40 5 2 2 Ability to Differentiate Aler
71. eport an IPSweep attack along with multiple swept IP addresses which cannot be represented as a single record In addition our current formalism allows aggregation of alerts of the same type and is flexible in reasoning about alerts Therefore we believe the current notion of a hyper alert is an appropriate choice A hyper alert instantiates its prerequisite and consequence by replacing the free variables in Chapter 3 A Framework for Alert Correlation 10 prereguisite and conseguence with its specific values Since all free variables in prerequisite and consequence must appear in fact in a hyper alert type the instantiated prerequisite and consequence will have no free variables Note that prerequisite and consequence can be instantiated multiple times if fact consists of multiple tuples In the following we treat timestamps implicitly and omit them if they are not necessary for our discussion Example 2 Consider the hyper alert type SadmindBufferOverflow in example 1 A hyper alert hsadminaBOF Of this type could be VictimIP 152 1 19 5 VictimPort 1235 VictimIP 152 1 19 7 VictimPort 1235 This implies that if the attack is successful the following two logical formulas must be True as the prerequisites of the attack ExistHost 152 1 19 5 A Vul nerableSadmind 152 1 19 5 ExistHost 152 1 19 7 A VulnerableSadmind 152 1 19 7 Moreover as possible consequences of the attack the following might be True GainRootAccess 1
72. er attack the consequence of the earlier attack should at least partly satisfy the prerequisite of the later attack Our method is to identify the prerequisites e g existence of vulnerable services and the con sequences e g discovery of vulnerable services of each type of attack These are then used to correlate alerts which are attacks detected by IDSs by matching the consequences of the attacks corresponding to some previous alerts and the prerequisites of the attacks corresponding to some later ones For example if we find a Sadmind Ping followed by a buffer overflow attack against the corresponding Sadmind service we can correlate them to be parts of the same series of attacks In other words we model the knowledge or state of attackers in terms of individual attacks and correlate alerts if they indicate the progress of attacks Note that an attacker does not have to perform early attacks to prepare for a later attack even though the later attack has certain prerequisites For example an attacker may launch an individual buffer overflow attack against a service blindly without knowing if the service exists In other words the prerequisite of an attack should not be mistaken for the necessary existence of an earlier attack However if the attacker does launch attacks with earlier ones preparing for later ones our method can correlate them provided that the attacks are detected by IDSs 3 1 Prerequisite and Consequence of A
73. ertain attacks by launching some other attacks For example the attacker may learn a vulnerable sadmind service by talking to people who work in the organization where the system is running Second the current IDSs may miss some attacks and thus affect the alert correlation if the above approach is used Third due to the combinatorial nature of the aforementioned approach it is computationally expensive to examine sets of alerts to find out whether their consequences satisfy or more precisely imply the prerequisite of an alert Having considered these issues we adopt an alternative approach Instead of examining if several Chapter 3 A Framework for Alert Correlation 11 hyper alerts satisfy the prerequisite of a later one we check if an earlier hyper alert contributes to the prerequisite of a later one Specifically we decompose the prerequisite of a hyper alert into pieces of predicates and test whether the consequence of an earlier hyper alert makes some pieces of the prerequisite True i e make the prerequisite easier to satisfy If the result is yes then we correlate the hyper alerts together This idea is specified formally through the following Definitions Definition 3 Consider a hyper alert type T fact prerequisite consequence The prerequisite set or consequence set resp of T denoted P T or C T resp is the set of all predicates that appear in prerequisite or consequence resp Given a hyper alert instance
74. es HyperAlertType Consequence Predicate gt lt xsd field xpath Name gt lt xsd keyref gt lt set the argument ID as the key gt lt xsd unigue name ArgumentKey gt lt xsd selector xpath Predicates Predicate Arg gt lt xsd field xpath id gt lt xsd unigue gt lt xsd keyref name keyref5 refer ArgumentKey gt Appendix A Knowledge Base Used In The Experiment 63 lt xsd selector xpath Implications Implication ArgMap ImplyingArg gt lt xsd field xpath id gt lt xsd keyref gt lt xsd keyref name keyref6 refer ArgumentKey gt lt xsd selector xpath Implications Implication ArgMap ImpliedArg gt lt xsd field xpath id gt lt xsd keyref gt lt xsd keyref name keyref7 refer ArgumentKey gt lt xsd selector xpath HyperAlertTypes HyperAlertType Prerequisite Predicate Arg gt lt xsd field xpath id gt lt xsd keyref gt lt xsd keyref name keyref8 refer ArgumentKey gt lt xsd selector xpath HyperAlertTypes HyperAlertType Consequence Predicate Arg gt lt xsd field xpath id gt lt xsd keyref gt lt xsd element gt lt Predicates schema gt lt xsd element name Predicates gt lt xsd complexType gt lt xsd sequence gt lt xsd element name Predicate minOccurs 0 maxOccurs unbounded gt lt xsd complexType gt lt xsd sequence gt lt xsd element name Arg minOccurs 0 maxOccurs unbounded gt lt xsd complexType gt l
75. es a logic based method to specify the precondition and postcondition of attack scenarios which is similar to our method See Chapter 3 However all these languages specify entire attack scenarios which are limited to known scenarios In contrast our method as well as JIGSAW describes prerequisites and consequences of individual attacks and correlate detected attacks i e alerts based on the relationship between these prerequisites and consequences Thus our method can potentially correlate alerts from unknown attack scenarios Alert correlation has been studied in the context of network management e g 13 27 and 12 In theory alert correlation methods for network management are applicable to intrusion alert correlation However intrusion alert correlation faces more challenges than its counterpart in network management While alert correlation for network management deals with alerts about natural faults which usually exhibit regular patterns intrusion alert correlation has to cope with less predictable malicious intruders Chapter 3 A Framework for Alert Correlation This chapter describes the foundation of the toolkit which has been proposed in 22 and 23 In a series of attacks where the attackers launch earlier attacks to prepare for later ones there are usually strong connections between the consequences of the earlier attacks and the prerequisites of the later ones If an earlier attack is to prepare for a lat
76. esent in this paper address this same problem from a novel angle overcoming the limitations of the above approaches JIGSAW 32 and our method fall into the third category Both methods try to uncover at tack scenarios based on specifications of individual attacks However our method also differs from JIGSAW First our method allows partial satisfaction of prerequisites i e required capabilities in JIGSAW 32 recognizing the possibility of undetected attacks and that of attackers gaining in formation through non intrusive ways e g talking to a friend working in the victim organization while JIGSAW requires all required capabilities be satisfied Second our method allows aggregation of alerts and thus can reduce the complexity involved in alert analysis while JIGSAW currently does not have any similar mechanisms Third we develop a set of utilities for interactive analysis of correlated alerts which is not provided by JIGSAW An alert correlation approach similar to ours was proposed recently in the MIRADOR project 8 The MIRADOR approach also correlates alerts using partial match of prerequisites pre conditions and consequences post conditions of attacks However the MIRADOR approach uses a different formalism than ours In particular the MIRADOR approach treats alert aggregation as an individual stage before alert correlation while our method allows alert aggregation during and after correlation As we will see in the later se
77. espectively Suppose hrpsweep represents an IP Sweep attack and hpposDaemon repre sents the activity of a DDOS daemon program Assume that h7pgweep prepares for hsadmindPing and hsadminaBor respectively hsadmindPing prepares for RsadminaBOF and hsadmindBOF Prepares for hpposDaemon These are intuitively shown in a hyper alert correlation graph in Figure 3 1 a The hyper alert correlation graph provides an intuitive representation of correlated hyper alerts With this notion the goal of alert correlation can be rephrased as the discovery of hyper alert correlation graphs that have maximal number of nodes from a sequence of hyper alerts In addition to getting all the correlated hyper alerts it is often desirable to discover those directly or indirectly correlated to one particular hyper alert For example if an IDS detects a DDOS daemon running on a host it would be helpful to inform the administrator how this happened that is report all the alerts that directly or indirectly prepare for the DDOS daemon Therefore we define the following operations on hyper alert correlation graphs Definition 8 Given a hyper alert correlation graph HG N E and a hyper alert n in N precedent n HG is an operation that returns the maximal sub graph PG lt N E of HG that Chapter 3 A Framework for Alert Correlation 14 satisfies the following conditions 1 n N 2 for each n N other than n there is a directed path from n to
78. estIP GainRootAccess DestIP AND GainFileInfo DestIP AND ExistService DestIP DestPort HTTP_Carbo_Server VulnerableWebServer DestIP GainFileInfo DestIP AND ExistService DestIP DestPort HTTP_Cdomain VulnerableCdomain DestIP GainAccess DestIP AND GainFileInfo DestIP AND ExistService DestIP DestPort HTTP Cold Fusion VulnerableColdFusion DestIP GainAccess DestIP ND ExistService DestIP DestPort HTTP_ColdFusion lt gt ulnerableColdFusion DestIP SystemAttacked DestIP Admin AND GainOSInfo DestIP AND ExistService DestIP DestPort HTTP ColdFusion VulnerableColdFusion DestIP GainFileInfo DestIP FileExists AND ExistService DestIP DestPort HTTP_ColdFusion VulnerableColdFusion DestIP ReadFile DestIP Source Window AND ExistService DestIP DestPort HTTP_ColdFusion VulnerableColdFusion DestIP GainAccess DestIP ViewExample AND ExistService DestIP DestPort HTTP_Cookie CookieA ccepted SrcIP GainInformation SrcIP HTTP_DotDot Vulnerable WebServer DestIP GainFileInfo DestIP AND ExistService DestIP DestPort HTTP_EZMall2000 VulnerableWebServer DestIP GainOrderLogInfo DestIP AND ExistService DestIP DestPort HTTP FaxSurvey VulnerableCGI DestIP GainAccess DestIP AND GainFileInfo DestIP AND ExistService DestIP DestPort HTTP_FormMail VulnerableCGI DestIP GainAccess DestIP AND GainFileInfo DestIP AND ExistService DestIP DestP
79. et 2000 19 the other one is DEFCON CTF 8 2 For the DARPA dataset we not only uncover the attack scenario we also reduce the false alarm rate For the DEFCON dataset there are around 65 000 alerts generated by IDS it is unhandlable by any system administrator By applying our utilities we can help the administrator to deal with the large number of alerts and discover the attack scenario behind it I will discuss these two results in detail in the following sections 5 1 Experiment Setup In our experiments we used NetPoke to replay the network traffic in an isolated network monitored by a RealSecure Network Sensor 6 0 2 In all the experiments the Network Sensor was configured to use the Maximum_Coverage policy with a slight change which forced the Network Sensor to save all the reported alerts Our alert correlator was then used to process the alerts to discover the hyper alert correlation graphs In these experiments we mapped each alert type reported by the RealSecure Network Sensor to a hyper alert type with the same name The prerequisite and consequence of each hyper alert type were specified according to the descriptions of the attack signatures provided with the RealSecure Network Sensor 6 0 The hyper alert types as well as the implication relationships between predicates can be found in the appendix 1NetPoke is a utility to replay packets to a live network that were previously captured with the tcpdump program h
80. f stage 2 include attacks that may lead to execution of arbitrary code on a target system e g HTTP_WebSite_Sample Indeed these hyper alerts directly prepare for some hyper alerts in stage 5 but GraphViz arranged them in stage 2 possibly to balance the graph Stages 3 consists of a mix of scanning attacks e g Nmap_Scan attacks that reveal system information e g HTTP_PHP_Read and attacks that may lead to execution of arbitrary code e g HTTP_Campas Stage 4 mainly consists of buffer overflow attacks e g POP_QPopCommand_Overflow detection of backdoor pro grams e g BackOrifice and attacks that may lead to execution of arbitrary code The next 3 stages are much cleaner Stage 5 consists of attacks that may be used to copy programs to target hosts stage 6 consists of detection of two types of DDOS Distributed Denial of Service daemon programs and finally stage 7 consists of the detection of an actual DDOS attack Note that the fully reduce graph in Figure 5 6 is an approximation to the strategies used by the attackers Hyper alerts for different independent sequences of attacks may be aggregated together in such a graph For example if two individual attackers use the sequence of attacks e g using the same script downloaded from a website to attack the same target the corresponding hyper alerts may be correlated and aggregated in the same fully reduced graph Nevertheless a fully reduced graph can clearly outline the att
81. gName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Predicate Name VulnerableAlMailPOP3Server gt lt Arg id 20 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt Appendix A Knowledge Base Used In The Experiment 76 lt HyperAlertType Name Email_Debug gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Predicate Name SendMailInDebugMode gt lt Arg id 14 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Email_Ehlo gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType
82. gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Sadmind_Ping gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt Appendix A Knowledge Base Used In The Experiment 85 lt Predicate Name 0SSolaris gt lt Arg id 25 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name VulnerableSadmind gt lt Arg id 21 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name SSH_Detected gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Consequence gt l lt Predicate Name GainInformation gt lt Arg id 7 ArgName DestIPAddress gt lt Arg gt lt Predicate gt gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Stream_DoS gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactN
83. h of type T the prerequisite set or consequence set resp of h denoted P h or C h resp is the set of predicates in P T or C T resp whose arguments are replaced with the corresponding attribute values of each tuple in h Each element in P h or C h resp is associated with the timestamp of the corresponding tuple in h Notation wise for each p P h or C h resp we use p begin_time and p end_time to refer to the timestamp associated with p Example 3 Consider the Sadmind Ping attack through which an attacker discovers possibly vul nerable sadmind services The corresponding alerts can be represented by a hyper alert type Sad mindPing 4 VictimIP VictimPort ExistHost VictimIP 4 VulnerableSadmind VictimIP Suppose a hyper alert instance hs dmindPing Of type SadmindPing has the following tuples VictimIP 152 1 19 5 VictimPort 1235 VictimIP 152 1 19 7 VictimPort 1235 Vic timIP 152 1 19 9 VictimPort 1235 Then P hsadminaPing EvistHost 152 1 19 5 Er istHost 152 1 19 7 ExistHost 152 1 19 9 and C hgadmindPing 4 VulnerableSadmind 152 1 19 5 VulnerableSadmind 152 1 19 7 VulnerableSadmind 152 1 19 9 Example 4 Consider hsadminaBor in example 2 We have P hsadminagor 4 ExistHost 152 1 19 5 ExistHost 152 1 19 7 VulnerableSadmind 152 1 19 5 VulnerableSadmind 152 1 19 7 and C hsadminaBoF 4 GainRootAccess 152 1 19 5 GainRootAccess 152 1 19 7 Defi
84. he attribute names in A appear in T For example the above clustering constraint is enforceable w r t T and 7 if both of them have SrcIP and DestIP in the fact component Intuitively a focusing constraint is enforceable w r t T if it can be evaluated using two hyper alerts of types T and Ta respectively If a clustering constraint Ce A1 A2 is enforceable w r t T and T2 we can evaluate it with two hyper alerts h and ha that are of type T and Ty respectively A clustering constraint C A Az evaluates to True for h and ha if there exists a tuple t h and ta he such that C A1 A2 is True with the attribute names in A and Az replaced with the values of the corresponding attributes of t and ta respectively otherwise C A1 A2 evaluates to False For example consider the clustering constraint C A1 A2 41 SrcIP Az SrcIP A A DestIP Az DestIP and hyper alerts hy SrcIP 129 174 142 2 SrcPort 1234 DestIP 152 1 14 5 DestPort 80 ha SrceIP 129 174 142 2 SrcPort 65333 DestIP 152 1 14 5 DestPort 23 we can easily have that C Ai A2 True for hi and hg For brevity we write C hi h2 True if C A A2 True for h and hz Our clustering method is very simple with a user specified clustering constraint Ce A1 A2 Two hyper alerts hi and h are in the same cluster if C A1 A2 evaluates to True for h and ha or Chapter 3 A Framework for Alert Correlation 18
85. host at 010 020 001 024 All the PHalfScan attacks were from source IP 010 020 011 240 at source port 55533 or 55534 and destined to port 110 at the victim host After these attacks all the attacks in the second stage except for 31886 were from 010 020 012 093 and targeted at port 110 of the victim host The only two hyper alerts that were not targeted at port 110 are hyper alert 30882 which was destined to port 80 of the victim host and hyper alert 31886 which was destined to port 53 Thus it is very possible that all the hyper alerts except for 30882 and 31886 were related Not all of the hyper alert correlation graphs are as small and comprehensible as Figure 5 5 In particular the largest graph in terms of the number of nodes has 2 940 nodes and 25 321 edges and on average each graph has 21 75 nodes and 310 56 edges Obviously most of the hyper alert correlation graphs are too big to understand for a human user 5 3 2 Adjustable Graph Reduction The largest hyper alert correlation graph is taken as an example to analyze the results We first applied graph reduction utility to the hyper alert correlation graphs Figure 5 6 shows the fully reduced graph Compared with the original graph which has 2 940 nodes and 25 321 edges the fully reduced graph has 77 nodes and 347 edges including transitive edges The fully reduced graph in Figure 5 6 shows 7 stages of attacks The layout of this graph was generated by GraphViz 1 which tries
86. ied by these predicates and then correlation of the hyper alerts becomes simple matching of the instantiated predicates This method requires more storage than the previous one however it is suitable for batch processing of the alerts and is able to use the RDBMS s query processing capability Since we are developing an off line alert correlation tool we choose the second method to reduce the development cost The alert preprocessing phase generates the hyper alert data as well as two auxiliary tables Each hyper alert is uniquely identified by a hyper alert ID Two tables are used to store the hyper alerts The table HyperAlert has attributes HyperAlertID HyperAlert Type begin time and end time which represent the ID the type and the interval based timestamps of the hyper alerts The table HyperAlertFact has attributes HyperAlertID and the union of the fact attributes of all known hyper alert types it keeps the fact attribute values for all hyper alerts with inapplicable attributes set to NULL The two auxiliary tables PrereqSet and ConseqSet are generated to facilitate hyper alert corre lation They are used to keep instantiated prerequisite and consequence sets of the hyper alerts re spectively Both tables have the same set of attributes HyperAlertID EncodedPredicate begin time and end time however PrereqSet saves the elements in the prerequisite sets while ConseqSet keeps Chapter 4 Implementation 27 the elements in the
87. into one host first and then fans out from it 5 2 1 Effectiveness of Alert Correlation Our first goal of these experiments is to evaluate the effectiveness of our method in constructing attack scenarios from alerts Figures 5 1 5 2 5 3 and 5 4 are the hyper alert correlation graphs we have generated for this experiment Each node in Figure 5 1 represents a hyper alert The text inside the node is the name of the hyper alert type followed by the hyper alert ID Let s take figure 5 1 as an example It shows the only hyper alert correlation graph discovered from the inside network traffic in LLDOS 1 0 There are 44 hyper alerts in this graph including 3 false alerts which are shown in gray The true hyper alerts can be divided into five stages hori zontally The first stage consists of three Sadmind_Ping alerts which the attacker used to find out the vulnerable Sadmind services The three alerts are from the source IP address 202 077 162 213 and to the destination IP addresses 172 016 112 010 172 016 115 020 and 172 016 112 050 respec tively The second stage consists of fourteen Sadmind_Amslverify_Overflow alerts According to the description of the attack scenario the attacker tried three different stack pointers and two com mands in Sadmind_Ameslverify_Overflow attacks for each victim host until one attempt succeeded All the above three hosts were successfully broken into The third stage consists of some Rsh alerts with which the
88. ion only when the resulting hyper alerts satisfy an interval con straint of a given threshold 7 Intuitively we allow hyper alerts to be aggregated only when they are close to each other The larger a threshold I is the more a hyper alert correlation graph can be reduced By adjusting the interval threshold a user can control the degree to which a hyper alert correlation graph is reduced 3 4 2 Focused Analysis Focused analysis is implemented on the basis of focusing constraints A focusing constraint is a logical combination of comparisons between attribute names and constants In our work we restrict logical operations to AND A OR V and NOT For example we may have a focusing constraint Src P 129 174 142 2 V DestIP 129 174 142 2 We say a focusing constraint Cf is enforceable w r t a hyper alert type T if when we represent Cf in a disjunctive normal form at least for one disjunct Cy all the attribute names in Cf appear in T For example the above focusing constraint is enforceable w r t T SrcIP SrcPort NULL but not w r t T VictimIP VictimPort NULL Intuitively a focusing constraint is enforceable w r t T if it can be evaluated using a hyper alert instance of type T We may evaluate a focusing constraint Cy with a hyper alert h if Cf is enforceable w r t the type of h A focusing constraint Cy evaluates to True for h if there exists a tuple t h such that Cf is True with the attribute names
89. is difficult for human users or intrusion response systems to understand the intensive alerts and take appropriate actions Therefore it is necessary to have techniques and tools to help improve the accuracy and quality of alerts A good technique should aid the intrusion detection analyst or system administrator by pulling out needles in the haystack and bringing them to attention without the noise that generally follows Motivated by the above reasons we have developed a technique 22 23 to correlate the alerts generated by IDS This technique is based on the prerequisites and consequences of attacks The prerequisite of an attack specifies what must be true in order for the attack to be successful and the consequence of the attack describes what is possibly true if the attack indeed succeeds By reasoning about the consequences of earlier attacks and the prerequisites of later attacks we can correlate the alerts together and construct attack scenarios Moreover we conjecture that the correlated alerts are more possible to be true alerts than uncorrelated ones So by correlation we can potentially differentiate the false alerts from the real ones In this thesis work I implement a set of tools based on the above technique The basic tool for alert correlation is composed of a knowledge base an alert preprocessor an alert correlation engine and a graph output component On the basis of the basic alert correlator I also implement three u
90. isite gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name SystemCompromised gt lt Arg id 18 ArgName DestIPAddress gt lt Arg gt lt Predicate gt Appendix A Knowledge Base Used In The Experiment 84 lt Predicate Name SystemCompromised gt lt Arg id 18 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name Sadmind_Amslverify_Overflow gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name VulnerableSadmind gt lt Arg id 21 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Predicate Name 0SSolaris gt lt Arg id 25 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt las lt Predicate Name GainAccess gt lt Arg id 4 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt gt lt Prerequisite gt lt Consequence gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt lt Predicate
91. k it just for the sake of clearness to users In figure 4 4 ExistService DestIPAddress im plies ExistHost DestIPAddress is a normal implication while GainOSInfo DestIPAddress implies OSUnix DestIPAddress is a phantom implication An implication is represented by the following parts one ImplyingName one ImpliedName and zero ore more ArgMap The usage of ImplyingName and ImpliedName is obvious they are the names of the implying predicate and the implied predicate respectively One ArgMap represents the mapping between one pair of arguments ImplyingArg and ImpliedArg represent the argument of implying predicate and implied predicate respectively The attribute id of the ImplyingArg and ImpliedArg is used to refer to the unique id of the predicate s argument which is defined in the Predicates section Take GainOSInfo implies OSUniz in figure 4 4 as an example We want to represent GainOSInfo DestIPAddress OSUnix DestIPAddress The argument id of GainOSInfo which is defined in the Predicates section is 4 And the argument id of OSUniz is 5 So the attribute id of the ImplyingArg and the ImpliedArg here are 4 and 5 respectively The validation check performed by XML schema is not enough for the implication part Because what XML schema can check is whether the ImplyingArg id and ImpliedArg id exist in the Predicates section But this check cannot assure that the implication mappings are valid It is very important to make sure that the Im
92. ks rate alerts rate DMZ 89 RealSecure 891 51 57 30 57 93 60 LLDOS Our method 57 50 56 18 54 5 26 1 0 Inside 60 RealSecure 922 37 61 67 44 95 23 Our method 44 36 60 41 6 82 DMZ 7 RealSecure 425 4 57 14 6 98 59 LLDOS Our method 5 3 42 86 3 40 2 0 2 Inside 15 RealSecure 489 12 80 00 16 96 73 Our method 13 10 66 67 10 23 08 To understand this issue we deliberately drop the uncorrelated alerts and then compare the resulting detection rate and false alert rate with the original ones of RealSecure We counted the number of actual attacks and false alerts according to the description included in the datasets The initial phase of the attacks involved an IP Sweep attack Though many packets were involved we counted them as a single attack Similarly the final phase had a DDOS attack which generated many packets but was also counted as one attack For the rest of the attacks we counted each action e g telnet Sadmind_Ping initiated by the attacker as one attack The numbers of attacks observable in these datasets are shown in Table 5 2 Note that some activities such as telnet are not usually considered as attacks however we counted them if the attacker used them as part of the attacks RealSecure Network Sensor 6 0 generated duplicate alerts for certain attacks For example the same rsh connection that the attacker used to access the compromised host triggered two alerts As a result the number of
93. l constraints are restrictions that make the aggregated hyper alerts meaningful 3 3 Hyper alert Correlation Graph The prepare for relation between hyper alerts provides a natural way to represent the causal rela tionship between correlated hyper alerts In the following we introduce the notion of a hyper alert correlation graph to represent attack scenarios on the basis of the prepare for relation As we will see the hyper alert correlation graph reflects the high level strategies or logical steps behind a sequence of attacks Chapter 3 A Framework for Alert Correlation 13 Nipsweep h sadmindBoF RDDOSDaemon h ipsweep h sadmindBOF O h SadmindPing O h SadmindPing a A hyper alert correlation graph HG b PG precedent hgadmindBor HG h SadmindBOF hppospaemon e o c SG subseguent hsadminaBOF HG h IPSweep h SadmindBOF h pposDaemon O gt 0 gt O SS O h SadmindPing d CG correlated hsadmindBOF HG Figure 3 1 Hyper alerts correlation graphs Definition 7 A hyper alert correlation graph HG N E is a connected DAG directed acyclic graph where the set N of nodes is a set of hyper alerts and for each pair of nodes n1 n2 N there is an edge from n to na in E if and only if n prepares for na Example 6 Suppose in a sequence of hyper alerts we have the following ones hrpsweep hSadmindPing hgsadmindBOF and RpposDaemon hsadminaBOF and hsadmindPing have been explained in examples 2 and 3 r
94. l the alerts that belong to the same cluster and use a dynamic array to keep all the linked lists Each item in the array contains the head of a linked list We record each alert s alert id in the linked list So the size of the dynamic array is the number of sub graphs after the graph decomposition and the size of each linked list is the number of alerts existed in each sub graph First we generate all the distinct hyper alerts in the graph by using the following query Chapter 4 Implementation 39 SELECT DISTINCT PreparingHyperAlertID AS HyperAlertID FROM GraphEdges WHERE graphID user input graphID UNION SELECT DISTINCT PreparedHyperAlertID AS HyperAlertID FROM GraphEdges WHERE graphID user input graphID The result of this query is saved in an auxiliary table GraphAlerts which has one attribute HyperAlertID We name two alerts an alert pair if the two alerts match the graph clustering constraint and can be put into the same cluster Then we find out all such alert pairs existed in the graph by using the following query SELECT h1 HyperAlertID h2 HyperAlertID FROM GraphAlerts a HyperAlertFact hl HyperAlertFact h2 WHERE h1 HyperAlertID IN SELECT FROM a AND h2 HyperAlertID IN SELECT FROM a AND h1 HyperAlertID NOT h2 HyperAlertID AND user input constraint An auxiliary table AlertPairs is used to keep all these pairs It has three attributes alertl alert2 and assigned The alert1 and alert2 are used to keep th
95. le in figure 4 2 a shows predicate ExistHost has one argument and this argument s data type is varchar 15 The second and the third tuple in this figure represent predicate ExistService which has two arguments The first argument s data type is varchar 15 and the second argument s data type is int All these data types and the data types we discuss in the following sections are all database data types Table Implication figure 4 2 b keeps the implication relationships between predicates as well as the mapping between their arguments It has four attributes Predicate Implied P_Arg and LArg Predicate attribute is to record the implying predicate name Implied attribute is to record the implied predicate name P_Arg is the argument position in the implying predicate 7 Arg is the argument position in the implied predicate For example the first tuple in figure 4 2 b indicates that ExistService implies ExistHost and they both take their first argument Table HATFact figure 4 2 c contains all the fact information of all hyper alert types It has Chapter 4 Implementation 21 Predicate ArgNum ArgType ExistHost 1 varchar 15 ExistService 1 varchar 15 ExistService 2 int Predicate Implied P_Arg LArg GainOSInfo 1 varchar 15 ExistService ExistHost 1 1 a Table Predicate b Table Implication HyperAlert Type Attr Name Attr Type FTP_Syst DestIPAddress varchar 15 FTP Syst De
96. le rr o a a da ARDER a 101 C33 Execution a hata e E is Ni ki A A a Le 103 C 4 Sample Execution Procedure 02 ee ee 105 Co Trouble Shooting 00 A A A o a 105 List of References 106 List of Tables Completeness and soundness of alert correlation 44 Ability to differentiate true and false alerts 45 General statistics of the initialanalysis 46 Statistics of top 10 uncorrelated hyper alert types 46 number of clusters and graphs after decomposing the largest hyper alert correlation PMA AAA dae dae Wa wy ae ARA ti oli AA sl Detailed information of each cluster after decomposing the largest hyper alert corre latiori graphi soc oon ee eis ares de gs Wak A je Je ke IA BE V ee ge ed lei eet 51 vi List of Figures 3 1 4 1 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 1 5 2 5 3 5 4 Hyper alerts correlation graphs 13 The architecture of the correlator 20 Example tables for predicates and hyper alert types in the knowledge base 21 A sample Predicates section in a knowledge base XML file 22 A sample Implications section in a knowledge base XML file 23 A sample HyperAlertTypes section in a knowledge base XML file 25 The algorithm used to generate a single graph 29 Transitive edges Mak tl AS A
97. lertType gt lt HyperAlertType Name TelnetTerminaltype gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Consequence gt lt Predicate Name GainTerminalType gt Appendix A Knowledge Base Used In The Experiment 87 lt Arg id 11 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name TelnetXdisplay gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Consequence gt lt Predicate Name SystemAttacked gt lt Arg id 17 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name UDP_Port_Scan gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Consequence gt lt lt Predicate Name GainServiceInfo gt lt Arg
98. lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name CiscoCatalyst3500XL gt lt Arg id 1 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name GainAccess gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt Appendix A Knowledge Base Used In The Experiment 81 lt HyperAlertType gt lt HyperAlertType Name HTTP_Java gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name JavaEnabledBrowser gt lt Arg id 12 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name SystemCompromised gt lt Arg id 18 ArgName SrcIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name HTTP_Shells gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt
99. lt xsd element name ImplyingArg gt lt xsd complexType gt lt xsd attribute name id type xsd positivelnteger gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt xsd element name ImpliedArg gt lt xsd complexType gt lt xsd attribute name id type xsd positivelnteger gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt xsd sequence gt lt xsd complexType gt lt xsd element gt lt xsd sequence gt lt xsd attribute name Phantom default No gt lt xsd simpleType gt lt xsd restriction base xsd string gt lt xsd enumeration value Yes gt lt xsd enumeration value No gt lt xsd restriction gt lt xsd simpleType gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt HyperAlertTypes schema gt Appendix A Knowledge Base Used In The Experiment 66 lt xsd element name HyperAlertTypes gt lt xsd complexType gt lt xsd sequence gt lt xsd element ref HyperAlertType minOccurs 1 maxOccurs unbounded gt lt xsd sequence gt lt xsd complexType gt lt xsd element gt lt xsd element name HyperAlertType gt lt xsd complexType gt lt xsd seguence gt lt xsd element ref Fact minOccurs 1 maxOccurs unbounded gt lt xsd element ref Prerequisite minOccurs 0 maxOccurs unbounded gt lt xsd element ref Consequence minOccurs 0 maxOccurs
100. may make mistakes when there is not enough information One interesting observation is that with clustering constraint C 2 there is not many hyper alert correlation graphs with more than 3 stages Considering the fact that there are many alerts about BackOrifice and NetBus which are tools to remotely manage hosts we suspect that many attackers used multiple machines during their attacks Thus their strategies cannot be reflected by the restricted hyper alert correlation graphs When relax the restriction to allow hyper alert correlation graphs involving different source IP but still with the same destination IP addresses i e with clustering constraint C we have graphs with more stages Figure 5 8 is one such fully reduced hyper alert correlation graph However due to the amount of alerts and source IP addresses involved in this graph it is difficult to conclude which hyper alerts belong to the same seguences of attacks Chapter 6 Conclusions and Future Work 6 1 Conclusions In this thesis I implemented a toolkit based on the framework discussed in Chapter 3 The basic tool consists of a knowledge base an alert preprocessor an alert correlation engine and a graph output component In order to help analyze intensive alerts I also implemented three utilities adjustable graph reduction focused analysis and graph decomposition on the basis of the basic tool I have performed a sequence of experiments to evaluate the tools develop
101. me information about the systems involved in the CTF event Among these focusing constraints are 1 Cpi DestI P 010 020 001 010 and 2 Cf2 SreIP 010 020 011 251 A DestI P 010 020 001 010 We applied both focusing constraints to the largest hyper alert correlation graph The results consist of 2154 nodes and 19423 edges for C f1 and 51 nodes and 28 edges for C f2 The corresponding fully reduced graphs are shown in Fig 5 8 and Fig 5 9 respectively Isolated nodes are shown in gray These two graphs also appear in the results of graph decomposition Section 5 3 4 We defer the discussion of these two graphs to the next subsection Focused analysis is an attempt to approximate a sequence of attacks that satisfy the focusing constraint Its success depends on the closeness of focusing constraints to the invariants of the sequences of attacks A cunning attacker would try to avoid being correlated by launching attacks from different sources or stepping stones and introducing delays in between attacks Thus this utility should be used with caution 5 3 4 Graph Decomposition We applied three clustering constraints to decompose the largest hyper alert correlation graph dis covered in Section 5 3 1 In all these clustering constraints we let Ay A SrcIP DestIP 1 Cali 42 A DestI P Az DestIP This is to cluster all hyper alerts that share the same destination IP addresses Since most of attacks are targeted at the host
102. n In Proc of Network Operations and Management Symposium NOMS 98 pages 713 722 1998 58 References 59 13 14 15 16 17 18 19 20 21 22 23 24 Gruschke B Integrated event management Event correlation using dependency graphs In Proc of the 9th IFIP IEEE International Workshop on Distributed Systems Operations amp Management 1998 Tlgun K Kemmerer R A and Porras P A State transition analysis A rule based intrusion detection approach In IEEE Transaction on Software Engineering 21 pages 181 199 1995 ISS Inc RealSecure intrusion detection system http www iss net Bace R and Mell P NIST Special Publication on Intrusion Detection System NIST National Institute of Standards and Technology Special Publication 800 31 August 2001 Jha S Sheyner O and Wing J Two formal analyses of attack graphs In Proc of the 15th Computer Security Foundation Workshop June 2002 Julisch K Mining Alarm Clusters to Improve Alarm Handling Efficiency In Proc of the 17th Annual Computer Security Application Conference December 2001 MIT Lincoln Lab 2000 DARPA intrusion detection scenario specific datasets http www 11 mit edu IST ideval data 2000 2000_data_index html 2000 Lin J Wang X S and Jajodia S Abstraction based misuse detection High level specifica tions and adaptable strategies In Proc of the 11th Computer Security Foundations Workshop
103. n dealing with intensive datasets So three utilities are proposed to help analyze the huge intrusion datasets 3 4 1 Adjustable Graph Reduction This utility is aimed to reduce the complexity i e the number of nodes and edges of hyper alert correlation graphs while keeping the structure of sequences of attacks The graph reduction is adjustable in the sense that users are allowed to control the degree of reduction Aggregation is very useful to reduce the complexity of the attack scenario analysis Especially when the dataset is very large and we need some graphic output It can dramatically reduce the number of nodes and number of edges in the graph In the experiment with the data from DEFCON Capture the Flag CTF aggregation technique shows its power A natural way to reduce the complexity of a hyper alert correlation graph is to reduce the number of nodes and edges However to make the reduced graph useful any reasonable reduction should maintain the structure of the corresponding attacks We propose to aggregate hyper alerts of the same type to reduce the number of nodes in a hyper alert correlation graph Due to the flexible definition of hyper alerts the result of hyper alert aggregation will remain valid hyper alerts For example in Figure 5 1 hyper alerts 67432 67434 67436 and 67440 are all instances of hyper alert type Sadmind_Amslverify_Overflow Thus we may aggregate them into one hyper alert As another example hyper ale
104. ncise sequence of attacks against the host at 010 020 001 013 Nmap_Scan followed by PmapDump and then ToolTalk_Overflow Ob viously they used Nmap_Scan to find the portmap service then used PmapDump to list the RPC services and finally launched a ToolTalk_Overflow attack against the ToolTalk service Indeed the sequence Nmap_Scan followed by PmapDump with the same source and destination IP address appeared many times in this dataset Chapter 5 Experimental Results 54 The attacker s at 010 020 011 074 used the same sequence of HTTP based attacks e g HTTP DotDot and HTTP TestCgi against multiple web servers e g servers at 010 020 001 014 010 020 001 015 010 020 001 019 etc Our hyper alert correlation graphs shows that HTTP DotDot prepares for the following HTTP based attacks However our further analysis of the dataset shows that this may be an incorrect correlation Though it is possible that the attacker used HTTP DotDot to collect necessary information for the later attacks the timestamps of these alerts indicate that the attacker s used a script to launch all these attacks Thus it is possible that the attacker s simply launch all the attacks hoping one of them would succeed Though these alerts are indeed related these prepare for relations reveal that our method is aggressive in correlating alerts Indeed alert correlation is to recover the relationships between the attacks behind alerts any alert correlation method
105. nition 4 Hyper alert h prepares for hyper alert ha if there exist p P h2 and C C C h1 such that for all c C c end time lt p begin time and the conjunction of all the predicates in C implies p The prepare for relation is developed to capture the causal relationships between hyper alerts Intuitively h prepares for ha if some attacks represented by h make the attacks represented by ha easier to succeed Example 5 Let us continue examples 3 and 4 Assume that all tuples in hgadminaPing have times tamps earlier than every tuple in hsadminapor By comparing C hsadmindPing and P hsadmindBOF it is clear that VulnerableSadmind 152 1 19 5 among others in P Rsadminapor is also in C hsadmindPing Thus RSadmindPing prepares for and is correlated with hgadmindBOF Chapter 3 A Framework for Alert Correlation 12 Given a sequence S of hyper alerts a hyper alert h in S is a correlated hyper alert if there exists another hyper alert h in S such that either h prepares for h or h prepares for h If no such h exists h is called an isolated hyper alert Our goal is to discover all pairs of hyper alerts h and ha in S such that h prepares for ho 3 2 1 Temporal Constraints for Hyper alerts As discussed earlier we allow multiple alerts to be aggregated into a hyper alert which gives some flexibility in reasoning about alerts However the definition of hyper alert is overly flexible in some situations it allows alert
106. ntom Yes gt lt ImplyingName gt GainOSInfo lt ImplyingName gt lt ImpliedName gt OSLinur lt ImpliedName gt lt ArgMap gt lt ImplyingArg id 23 gt lt ImplyingArg gt lt ImpliedArg id lt 39 gt lt ImpliedArg gt lt ArgMap gt lt Implication gt It represents GainOSInfo GainOSInfoArg implies OSLinuz OSLinurArg The ImplyingName and ImpliedName are obvious ArgMap represents the argument mapping relationship In this example the argument id of GainOSInfoArg defined in the Predicates section is 23 and the argument id of OSLinuxArg is 39 They should match the id which is defined in the Predicates section This part goes into the Implication table in the database The hyper alert types are defined in the HyperAlerTypes section Each HyperAlertType may consist several parts Fact Prerequisite and Consequence if it has Among them Fact is a must of a hyper alert type Prerequisite and Consequence are optional The HyperAlertTypes section will be mapped into several tables HATFact to store the fact information HAT Prereq to store the prerequisite information and HAT Conseg to store the consequence information Appendix C User Installation amp Operation Manual 101 Please refer to our papers 4 5 for detailed table structure We provide a module to parse this knowledge base XML file and put them into database C 3 2 Property File There is a property file named Correlator properties Here is an e
107. o each other via other hyper alerts Table 5 5 and table 5 6 show the statistics of the decomposed graphs C resulted in 12 clusters among which 10 clusters contain edges Cez resulted in 185 clusters among which 37 contain edges Due to space reasons we only show the first 12 clusters for C 2 Ceg in effect removes one hyper alert from the original graph This hyper alert is Stream_DoS which does not share the same IP address with any other hyper alerts This is because the source IPs of Stream_DoS are spoofed and the destination IP is the target of this attack This result shows that all the hyper alerts except for Stream_DoS share a common IP address with some others The isolated nodes in the resulting graphs are the hyper alerts that prepare for or are prepared for by those that do not satisfy the same clustering constraints Note that having isolated hyper alerts in a decomposed graph does not imply that the isolated hyper alerts are correlated incorrectly For example an attacker may hack into a host with a buffer overflow attack install a DDOS daemon and start the daemon program which then tries to contact its master program The corresponding alerts i e the detection of the buffer overflow attack and the daemon s message will certainly not have the same destination IP address though they are related Chapter 5 Experimental Results 52 e Soca HTTP_WebSite_Uploader Fe CETT PRE PA DIS Po A a y w
108. of a hyper alert type See 3 1 In the XML knowledge base file all predicates appeared in the Implications section or HyperAlert Types section must be declared in the Predicates section All the predicates defined in this section are saved in the Predicate table in the database Figure 4 3 shows an example of the Predicates section Each predicate is represented by the following parts an attribute Name and zero or more Arg elements The attribute Name is used to represent a unique name which works as the key of the predicate It is saved in the Predicate column of the Predicate table Each Arg element represents one argument of this predicate It has three attributes d Pos and Attr In order to make the validation strict and easy a unique argument id is used for each argument in all the predicates The Pos attribute is to tell the position of this argument in the predicate s argument list and it goes to the ArgNum column of the Predicate table The Attr attribute is to tell the data type of this argument and it goes to the ArgType column of the Predicate table The id attribute of each argument in the XML file is only used for validation we don t save it in database For example the first tuple in figure 4 2 a represents the predicate ExistHost defined in figure Chapter 4 Implementation 23 lt Implications gt lt Implication gt lt ImplyingName gt ExistService lt ImplyingName gt lt ImpliedName gt ExistHost lt ImpliedName gt
109. of top 10 uncorrelated hyper alert types Hyper alert uncorrelated correlated Hyper alert uncorrelated correlated type alerts alerts type alerts alerts IPHalfScan 33745 958 Windows A ccess Error 11657 0 HTTP_Cookie 2119 0 SYNFlood 1306 406 IP Duplicate 1063 0 PingFlood 1009 495 SSH Detected 731 0 Port Scan 698 725 ServiceScan 667 2156 Satan 593 280 mentioned earlier It turned out that they are very useful It would be helpful for the evaluation of our method if we could identify false alerts alerts for sequences of attacks and alerts for isolated attacks Unfortunately due to the nature of the dataset we are unable to obtain any of them Thus in these experiments we focus on the analysis of the attack strategies reflected by hyper alert correlation graphs but only discuss the uncorrelated alerts briefly 5 3 1 Initial Attempt In our initial analysis of the DEF CON 8 CTF dataset we tried to correlate the hyper alerts without reducing the complexity of any hyper alert correlation graphs The statistics of the initial analysis are shown in Table 5 3 Table 5 3 shows that only 15 alerts generated by RealSecure are correlated In addition 20 out of 115 hyper alert types that appear in this data set do not have any instances correlated Among the remaining 95 hyper alert types 51 types have both correlated and uncorrelated instances Table 5 4 shows the statistics of the top 10 uncorrelated
110. ompleteness and soundness respectively correctly correlated alerts Ro related alerts Chapter 5 Experimental Results 44 Table 5 1 Completeness and soundness of alert correlation LLDOS 1 0 LLDOS 2 0 2 DMZ Inside DMZ Inside correctly correlated alerts 54 41 5 12 related alerts 57 44 8 18 correlated alerts 57 44 5 13 completeness measure Re 94 74 93 18 62 5 66 7 soundness measure Rs 94 74 93 18 100 92 3 and _ correctly correlated alerts Rs correlated alerts Counting the numbers in R and R is easy given the description of the attacks in the DARPA datasets However RealSecure generated duplicate alerts for several attacks In our experiments we counted the duplicate alerts as different ones False alerts are counted as incorrectly correlated alerts so long as they are correlated Though non intrusive alerts e g the above Email_Ehlo and Email_Turn are not attacks if they are related activities we counted them as correctly correlated ones Table 5 1 shows the results about completeness and soundness of the alert correlation for the two datasets As shown by the values of Rs most of the hyper alerts are correlated correctly The completeness measures Re are satisfactory for LLDOS 1 0 however they are only 62 5 and 66 7 for the DMZ and inside traffic in LLDOS 2 0 2 Our further analysis reveals that all the hyper alerts missed are tho
111. on ID 9 Clustering Constraint h1 SrcI PAddress lt h2 Src PA ddress Decomposition_Aggregation true Decomposition Aggregation Time Interval Decomposition Output section 7 mapping between original alert name and hyper alert name OPTIONAL original alert name hyper_alert_name You can specify the parameter needed to communicate with database in section 1 The db Driver is used as the jdbc driver name and the dbURL is used as the database url The knowledge base parameters are specified in section 2 If you want to generate a knowledge base through an XML file please set Generate Knowledge Base to true and give the relative path of the XML file in Knowledge Base XML File If you don t want to generate the knowledge base just set Generate Knowledge Base to false We assume that all original alerts generated by IDS are stored in a single table So if there are more than one table involved please preprocessing them by merging into one table You can use the new Table property to merge it if it can be done by SQL statements If the newTable is set we will process the SOL statements you have specified here before other processes The correlation engine parameters are specified in section 3 These properties are used to specify the alert table name and the column names Alert TableName is a fixed keyword parameter to tell the tool which table stores the original alerts AlertID AlertName Begin Time and End Time are also
112. on that the hyper alert type name may be different with the original alert name or several original alert names map to one hyper alert type user can write this mapping relationship in the property file The tool gets the hyper alert type information from knowledge base and expects there could be such mappings that the keywords are the hyper alert type names their values are the respective original alert names Once these types of information are located they are inserted into the table HAT Mapping which will be used to map an original alert to a hyper alert type in the CorrelationEngine If no such kind of information is appeared in the property file we assume the hyper alert type has the same name with the original alert HyperAlert Type is the class to get the hyper alert type information from the knowledge base KnowledgeBase is a class to parse the XML file and transfer the contents in the XML file to the knowledge base tables in the database In our implementation in order to work in whatever Java version we use an outside open source XML parser Xerces SimplifiedGraphOutput is to generate the DOT formatted graph file which can be outputed using GraphViz based on the aggregated prepare for relationships The input table could be Simplified GraphEdges SimplifiedGraphFocus or SimplifiedGraphDecomposed TransitiveExclusion is to delete the transitive edges in a graph It uses the algorithm described in 4 5 Appendix C User Installation
113. ort Appendix A Knowledge Base Used In The Experiment 92 Hyper alert Type Prerequisite Consequence HTTP_Head ExistService DestIP DestPort BypassIDS HTTP IE BAT VulnerableWebServer DestIP GainAccess SrcIP ND MSIIS DestIP ND ExistService DestIP DestPort HTTP IIS DATA s gt gt ulnerableWebServer DestIP ND MSIIS DestIP ND ExistService DestIP Dest Port GainSourceCode SrcIP HTTP Info www lt gt gt ulnerableCGI DestIP ND GainFileInfo DestIP ND ExistService DestIP DestPort gt gt GainAccess DestIP HTTP_Java 2 vaEnabledBrowser SrcIP ND SystemCompromised DestIP ND ExistService DestIP Dest Port System Compromised SrcIP HTTP Machinelnfo lt gt gt ulnerableCgi DestIP GainHardwareInfo DestIP AND GainFileInfo DestIP AND ExistService DestIP DestPort HTTP_Netscape NetscapeEnterpriseServer DestIP GainFileInfo DestIP PageServices AND ExistService DestIP DestPort HTTP_Netscape NetscapeEnterpriseServer DestIP GainInformation DestIP SpaceView AND ExistService DestIP DestPort HTTP_Novell_Files VulnerableCGI DestIP GainFileInfo DestIP AND GainFileInfo DestIP AND ExistService DestIP DestPort HTTP NphTestCgi VulnerableWebServerDestIP GainFileInfo DestIP ND GainFileInfo DestIP ND ExistService DestIP DestPort HTTP_PDGSoft lt gt gt ulnerableWebStore DestIP N
114. pages 190 201 1998 Morin Benjamin Me Ludovic Debar Herve and Ducasse Mireille M2D2 A Formal Data Model for IDS Alert Correlation In Proc of the 5th Int l Symposium on Recent Advances in Intrusion Detection RAID 2002 October 2002 Ning P Cui Y and Reeves D S Analyzing intensive intrusion alerts via correlation In Proc of the 5th Int l Symposium on Recent Advances in Intrusion Detection RAID 2002 October 2002 Ning P Cui Y and Reeves D S Constructing attack scenarios through correlation of intrusion alerts To appear in the 9th ACM Conference on Computer amp Communications Security November 2002 Ning P and Xu D Adapting query optimization techniques for efficient intrusion alert correla tion Technical Report TR 2002 14 North Carolina State University Department of Computer Science September 2002 References 60 25 26 27 28 29 30 31 32 33 34 Ning P Jajodia S and Wang X S Abstraction based intrusion detection in distributed environments In ACM Transactions on Information and System Security 4 pages 407 452 2001 Porras A Phillip Fong W Martin and Valdes Alfonso A Mission Impact Based Approach to INFOSEC Alarm Correlation In Proc of the 5th Int l Symposium on Recent Advances in Intrusion Detection RAID 2002 October 2002 Ricciulli L and Shacham N Modeling correlated alarms in network management system In Western Simulation Multi
115. plyingArg and the ImpliedArg have the same data type This validation check is performed by the tool Before we write the implication mapping relationship into database we will get their data types from the Predicate table If they are the same data type this implication mapping relationship will be written into the table Implication Otherwise the tool will quit the process HyperAlertTypes The HyperAlert Types section contains a set of HyperAlert Types Figure 4 5 shows a sample Hyper AlertTypes section in the knowledge base XML file Chapter 4 Implementation 25 lt HyperAlertTypes gt lt HyperAlertType Name FTP_Syst gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt Predicate Name ExistService gt lt Arg id 2 ArgName DestIPAddress gt lt Arg gt lt Arg id 3 ArgName DestPort gt lt Arg gt lt Predicate gt lt Prerequisite gt lt Consequence gt lt Predicate Name Gain0SInfo gt lt Arg id 4 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertTypes gt Figure 4 5 A sample HyperAlertTypes section in a knowledge base XML file Each HyperAlertType is represented by the following parts one Fact element zero or one Prereq uisite element and zero or one Consequence element All these information in the HyperA lert Type
116. process which contains prepare for relationships and their graph id It has three attributes PreparingHyperAlertID PreparedHyperAlertID and graphID We use the graphID as the indicator of different graphs All the prepare for relationships with the same graph id are in the same graph Two auxiliary tables are used in the process Table ProcessedNodes is used to save all the nodes we have processed so far for this graph Table NewlyAddedNodes saves all the nodes which are added into ProcessedNodes in the previous round Both of these two tables only contain one attribute which is HyperAlertID We set 0 to graph ID for all prepare for relationships initially From the graphID we know whether this edge has been assigned a graph or not If it is 0 it hasn t been processed yet If it is greater than 0 it has already been assigned When we start a new graph clear the table ProcessedNodes first Then select any unassigned edge whose graphID 0 and assign a new graph id g g lt 1 2 3 to this edge Insert the two nodes of this edge into table ProcessedNodes We will repeat the following process to find out all the unassigned edges that connect to each other First find all the unassigned edges that their PreparingHyperAlertIDs are in the table Pro cessedNodes and set their graphID to g Also find all the unassigned edges that their PreparedHy perAlertIDs are in the table ProcessedNodes and set graphID to g Up to now we have found all the edges
117. quit N append T2 to TransitiveEdges empty T2 y i Figure 4 8 The algorithm used to generate all the possible transitive edges Replace T2 with this set of results and append it to TransitiveEdges We will stop here if T2 is null Otherwise we will continue to find all the n 1 hop edges After we have the table TransitiveEdges which contains all the transitive edges that may exist in the prepare for relationships it is very easy to delete them from the prepare for relationships Figure 4 8 is the algorithm we use to get all the possible transitive edges Queryl generate all the 2 hop transitive edges in figure 4 8 SELECT cl PreparingHyperAlertID c2 PreparedHyperAlertID FROM prepare for relationships cl prepare for relationships c2 WHERE cl PreparedHyperAlertID c2 PreparingHyperAlertID AND cl PreparingHyperAlertID c2 PreparedHyperAlertID Ouery2 generate all the n hop transitive edges in figure 4 8 where n is greater than 2 SELECT T PreparingHyperAlertID R PreparedHyperAlertID FROM T2 T perpare for relationships R WHERE T PreparedHyperAlertID R PreparingHyperAlertID AND T PreparingHyperAlertID R PreparedHyperAlertID AND NOT EXISTS SELECT FROM TransitiveEdges TE Chapter 4 Implementation 32 WHERE T PreparingHyperAlertID TE PreparingHyperAlertID AND R PreparedHyperAlertID TE PreparedHyperAlertID 4 6 Adjustable Graph Reduction As w
118. r friendly It would be much better if we have a specific component to deal with this problem It gets all the information we need from different sources and writes them into a single table in database 6 2 3 Identifying Missing Detections amp Predicating Alerts In our experiment of the DARPA dataset there is a small decrease in the detection rate compared with RealSecure Can we reduce the false alert rate without hurting the detection rate It would be even better if we can not only reduce the false alert rate but also improve the detection rate of the underlying IDS In other words our correlator can help the underlying IDS figure out what alerts are probably missed by it and what alerts are going to happen next based on the attack strategy we construct and previously seen attack scenarios Chapter 6 Conclusions and Future Work 57 6 2 4 Correlating Alerts from Different IDSs In our experiment we only used the alerts generated by one IDS As we mentioned in the introduc tion different types of IDSs have their own strength and weaknesses It would be more effective in detecting attacks if we could utilize the strength of each of them But this leads to another problem that is how to correlate the alerts generated from different IDSs Although our framework supports it in theory can our tool support it How to synchronize the timestamps from different IDSs How to map the original alerts generated by different IDSs to hyper aler
119. reduction It can have different input and output when this utility is applied in different circumstances The input of this utility could be either the table GraphEdges GraphEdgesFocus or GraphEdgesDecom posed depending on where this utility is used GraphEdges is the original prepare for relationship generated by the correlation engine GraphEdgesFocus is the result generated by the focused analysis and Graph EdgesDecomposed is the result generated by the graph decomposition The output of this utility could be either the table SimplifiedGraph Edges SimplifiedFocus or Simplified Decomposed All these three tables have the same attributes with table Graph Edges The attributes are PreparingHyperAlertID PreparedHyperAlertID and graphID The difference is that the alert id in GraphEdges is the original hyper alert id while the alert id in the other three tables is the new aggregated id Chapter 4 Implementation 33 set types of different hyper alert types in one graph V seti 0 sort all the hyper alerts whose type is the i hyper alert type according to their timestamp Put them in an array alerts its size is num Y i setj 0 v Assign a new aggregated alert id a to alertslj and record this mapping in table IDMapping i jn Y if the interval between alerts j 1 and alertslj is less than the threshold assign a as alerts j 1 s aggregated
120. retrieves all the hyper alert types from the knowledge base Then it generates hyper alerts by mapping the original alerts to the hyper alert types Finally the algorithms we propose in 4 2 and 4 3 are used to generate the prepare for relationships Table CorrelatedAlerts is the output which contains the prepare for relationships FocusedAnalysis is the class to support the focused analysis utility It requests the user has some prior knowledge of the network you protect or the attacks so that the user can input the focusing constraint It uses the algorithm in 4 7 Table GraphEdgesFocus is the output GraphDecomposition is the class to support the graph decomposition utility The algorithm in 4 8 is used It doesn t require that user has some prior knowledge Table GraphEdgesDecomposded is the output GraphOutput is to generate the DOT formatted graph file which can be displayed by GraphViz using the original prepare for relationships which are stored in GraphEdges or GraphEdgesFocus or GraphEdgesDecomposed GraphReduction is the class to support the adjustable graph reduction utility The algorithm described in 4 6 is used Either SimplifiedGraphEdges SimplifiedGraphFocus or SimplifiedGraphDe composed is the output table depends on different input table GraphEdges GraphFocus or GraphDe composed 96 Appendix B JAVA Classes 97 HATMapping is the class to map the original alert name to hyper alert type name To accommo date the situati
121. rt SystemAttacked DestIP FTP_Pass ExistService DestIP DestPort FTP_PrivilegedBounce ExistService DestIP DestPort AND GainOSInfo DestIP FTP_PrivilegedPort ExistService DestIP DestPort AND GainOSlnfo DestIP FTP_Put ExistService DestIP DestPort SystemCompromised DestIP AND GainAccess DestIP FTP_Root ExistService DestIP DestPort GainRootAccess DestIP AND VulnerableF TPService DestIP FTP Syst ExistService DestIP DestPort GainOSInformation DestIP FTP_User ExistService DestIP DestPort Generic_Intel_Overflow GainHardwarelnfo DestIP AND ExistService DestIP DestPort GainAccess DestIP HP_OpenView SNMP Backdoor VulnerableHP DestIP AND GainOSInfo DestIP AND ExistService DestIP Dest Port GainNetworkInfo DestIP HTTP ActiveX SystemCompromised DestIP SystemAttacked SrcIP HTTP AnyFormPost VulnerableCGI DestIP GainAccess DestIP ND GainFileInfo DestIP ND ExistService DestIP DestPort HTTP_BAT_Execute SWindows DestIP GainAccess DestIP ND GainFileInfo DestIP ND ExistService DestIP DestPort A A O AND VulnerableWebServer DestIP A A Appendix A Knowledge Base Used In The Experiment 91 Hyper alert Type Prerequisite Consequence HTTP_Cachemgr VulnerableCgi DestIP GainInformation DestIP AND GainFileInfo DestIP AND ExistService DestIP DestPort HTTP_Campas VulnerableCgi D
122. rts 6755 67558 67559 and 67560 are all instances of Rsh and can be aggregated into a single hyper alert Edges are reduced along with the aggregation of hyper alerts In Figure 5 1 the edges between the Rsh hyper alerts are subsumed into the aggregated hyper alert while the edges between the Sadmind_Ping hyper alert and the four Sadmind Amslverify Overflow hyper alerts are merged into a single edge Reduction of a hyper alert correlation graph may lose information contained in the original graph Indeed hyper alerts that are of the same type but belong to different sequences of attacks may be aggregated and thus provide overly simplified results Nevertheless our goal is to lose as little information of the structure of attacks as possible Depending on the actual alerts the reduction of a hyper alert correlation graph may be less simplified or over simplified We would like to give a human user more control over the graph reduction process In the following we use a simple mechanism to control this process based on the notion of an interval constraint Chapter 3 A Framework for Alert Correlation 16 Definition 11 Given a time interval 7 e g 10 seconds a hyper alert h satisfies interval constraint of I if 1 h has only one tuple or 2 for all t in h there exist another t in h such that there exist t begin time lt T lt t end_time t begin time lt T lt t end time and T T lt I We allow hyper alert aggregat
123. rusion alerts Can we use this technique to correlate the alerts in real time The most important factor for real time processing is the efficiency In the offline toolkit implementation DBMS is used to process the preprocessed data The database operations do make it easier to develop this tool but it is not an appropriate choice for real time processing because of its performance penalty For example in the experiments of DEFCON it takes me 45 minutes to preprocess 65 000 alerts if JDBC ODBC bridge is used and it drops to 5 minutes if JDBC bridge is used though It is still unbearable for real time processing One option to improve the efficiency is to adapt some existing in memory query optimization techniques such as Array Binary Search AVL Trees B Trees Chained Bucket Hashing Linear Hashing and T Trees Some initial results about this study can be found in 24 6 2 2 Input Alerts In the current implementation we assume that we can get all the information about the original alerts from a single table in database However it is not true for some IDSs e g Snort 3 An alternative way is provided in the property file to solve this problem partially If the user can use one SQL statement to write all the needed information into a table in database then he can specify this SQL statement in the property file and we will process the SQL statement before any other operations But it is not so easy sometimes Also it is not very use
124. s at the destination IP addresses this is to cluster hyper alerts in terms of the victim systems 2 C a Aj Az A SrclP Az SrcIP A A Desti P Az DestIP This is to cluster all the hyper alerts that share the same source and destination IP addresses Chapter 5 Experimental Results 51 Table 5 5 number of clusters and graphs after decomposing the largest hyper alert correlation graph clusters graphs Ca 12 10 Cez 185 27 Ce 2 1 Table 5 6 Detailed information of each cluster after decomposing the largest hyper alert correlation graph cluster ID 1 2 3 4 5 6 7 8 9 10 11 12 connected nodes 2154 244 105 227 83 11 54 28 0 23 6 0 Ce edges 19423 1966 388 2741 412 30 251 51 0 26 5 0 isolated nodes 0 0 0 0 0 0 0 110 0 4 correlated nodes 1970 17 0 12 0 0 0 3 0 29 0 0 Cez edges 2240 66 0 10 0 0 0 2 0 28 0 0 isolated nodes 3 0 21 17 35 26 15 12 4 22 13 26 connected nodes 2935 0 C 3 edges 25293 0 isolated nodes 4 1 3 C 3 Aj Ag A1 SrcIP Az SrcIP V A DestIP Ag DestIP V A SrcIP Ap DestIP V A DestIP Ag SrcIP This is to cluster all the hyper alerts that are connected via common IP addresses Note that with this constraint hyper alerts in the same cluster may not share the same IP address directly but they may connect t
125. s that occur at arbitrary points in time to be treated as a single hyper alert Although some attackers usually spread their intrusive activities over time aggregating alerts at arbitrary time points is still overly broad and may affect the effectiveness of alert correlation In the following we introduce two temporal constraints for hyper alerts The purpose of these temporal constraints is to restrict the alert aggregation to meaningful ones We are particularly interested in hyper alerts that satisfy at least one of the constraints However most of our discussion in this paper applies to general hyper alerts Thus we will not specifically indicate the constraints if it is not necessary Definition 5 Given a time duration D a hyper alert h satisfies duration constraint of D if Max t endtime Vt h Min4t begin time Yt h lt D Definition 6 Given a time interval 7 a hyper alert h satisfies interval constraint of I if 1 h has only one tuple or 2 for all t in h there exist another t in h such that there exist t begin_time lt T lt t end_time t begin_time lt T lt t end time and T T lt I The temporal constraints are introduced to prevent unreasonable aggregation of alerts However this does not imply that alerts have to be aggregated Indeed in our initial experiments we treat each alert as an individual hyper alert In other words aggregation of alerts is an option provided by our model and tempora
126. se triggered by the telnets that the attacker used to access a victim host Each telnet triggered three alerts TelnetEnvAll TelnetX Display and Telnet Terminal Type According to RealSecure s description these alerts are about attacks that are launched using environmental variables TelnetEnvAll in a telnet session including X Display TelnetX Display and TerminalType Telnet Terminal Type However according to the description of the datasets the attacker did not launch these attacks though he did telnet to one victim host after gaining access to it Nevertheless to be conservative we consider them as related alerts in our evaluation Considering these facts we can conclude that our method is effective for these datasets 5 2 2 Ability to Differentiate Alerts Our second goal of these experiments is to see how well alert correlation can be used to differentiate false alerts and true alerts As we conjectured in Chapter 3 false alerts which do not correspond to any real attacks tend to be more random than the actual alerts and are less likely to be correlated to others If this conjecture is true we can divert more resources to deal with correlated alerts and thus improve the effectiveness of intrusion response Chapter 5 Experimental Results Table 5 2 Ability to differentiate true and false alerts 45 Dataset observable Tool alerts detected Detection true False alert attacks attac
127. site gt lt Consequence gt lt Predicate Name MailLeakage gt lt Arg id 13 ArgName DestIPAddress gt lt Arg gt lt Predicate gt lt Consequence gt lt HyperAlertType gt lt HyperAlertType Name FTP_Pass gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt Appendix A Knowledge Base Used In The Experiment 78 lt Prerequisite gt Sl gt lt Predicate Name ExistFTPService gt lt Arg id 3 ArgName DestIPAddress gt lt Arg gt lt Predicate gt gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt Arg gt lt Arg id 23 ArgName DestPort gt lt Arg gt lt Predicate gt lt Prerequisite gt lt HyperAlertType gt lt HyperAlertType Name FTP_Put gt lt Fact FactName SrcIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName SrcPort FactType int gt lt Fact gt lt Fact FactName DestIPAddress FactType varchar 15 gt lt Fact gt lt Fact FactName DestPort FactType int gt lt Fact gt lt Prerequisite gt lt le lt Predicate Name ExistFTPService gt lt Arg id 3 ArgName DestIPAddress gt lt Arg gt lt Predicate gt gt lt Predicate Name ExistService gt lt Arg id 22 ArgName DestIPAddress gt lt
128. splayed by GraphViz Focused Analysis Focused analysis is implemented on the basis of focusing constraint To activate it you must set FocusedAnalysis in the command line Also please specify which graph you want to analyze and what constraint you want to use So you must have some knowledge of the graph and the alerts before you can do the focused analysis Focused Analysis GraphID is on which graph you want to do the focused analysis Focusing_Constraint is an SQL valid presentation that can be inserted into a query like select alertID from alert Table where Focusing Constraint Focused Aggregation will activate inactivate the aggregation engine on the focusd analysis Focused Aggregation Time Interval is similar to Aggregation Time Interval in section 4 Appendix C User Installation amp Operation Manual 105 Focused Output is used for the output graph Graph Decomposition Graph decomposition is to decompose a big graph into several sub graphs based on a user specified clustering constraint 4 To activate graph decomposition you must set GraphDecomposition in the command line Decomposition ID is on which graph you want to do the decomposition Clustering Constraint is an SQL valid presentation that can be inserted into an SQL query directly It must be in a relationship between h1 attribute and h2 attribute since we use h1 and h2 as two alerts in the query Decomposition_Aggregation will activate inactive th
129. st Port int c Table HATFact HyperAlertType PID Predicate ArgPos ArgName FTP Syst 1 ExistService 1 DestIPAddress FTP Syst 1 ExistService 2 DestPort d Table HATPrereq HyperAlertType PID Predicate ArgPos ArgName FTP_Syst 1 GainOSInfo 1 DestIPAddress e Table HATConseq Figure 4 2 Example tables for predicates and hyper alert types in the knowledge base three attributes HyperAlertType AttrName and AttrType They represent the name of a hyper alert type the name of a fact and the data type of a fact respectively For example the two tuples in figure 4 2 c show that there are two facts in the fact set of hyper alert type FTP_Syst One is DestIPAddress with type varchar 15 and the other is DestPort with type int Table HATPrereg figure 4 2 d stores the hyper alert type s prerequisite information It has five attributes HyperAlertType P ID Predicate ArgPos and ArgName They represent the name of a hyper alert type id of the prerequisite predicate of this hyper alert type predicate name argument position argument name respectively For example the two tuples in figure 4 2 d represent the first predicate of hyper alert type FTP_Syst s prerequisites It is ExistService and this predicate has two arguments one is DestIPAddress and the other is DestPort We can get the data type of these arguments from one of these two tables Predicate or HAT Fact Table HATConseg fig
130. t xsd attribute name id type xsd positivelnteger gt lt xsd attribute gt lt xsd attribute name Pos type xsd positivelnteger gt Appendix A Knowledge Base Used In The Experiment 64 lt xsd attribute gt lt xsd attribute name Attr gt lt xsd simpleType gt lt xsd restriction base xsd string gt lt xsd enumeration value int gt lt xsd enumeration value varchar 15 gt lt xsd restriction gt lt xsd simpleType gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt end of element Arg gt lt xsd seguence gt lt xsd attribute name Name type xsd string use required gt lt xsd attribute gt lt xsd complexType gt lt xsd element gt lt xsd sequence gt lt xsd complexType gt lt xsd element gt lt Implication schema gt lt xsd element name Implications gt lt xsd complexType gt lt xsd sequence gt lt xsd element ref Implication minOccurs 0 maxOccurs unbounded gt lt xsd sequence gt lt xsd complexType gt lt xsd element gt lt xsd element name Implication gt lt xsd complexType gt lt xsd sequence gt lt xsd element name ImplyingName type xsd string gt Appendix A Knowledge Base Used In The Experiment 65 lt xsd element name ImpliedName type xsd string gt lt xsd element name ArgMap minOccurs 0 maxOccurs unbounded gt lt xsd complexType gt lt xsd sequence gt
131. te Name lt EristService gt lt Arg id 14 Pos lt 1 Attr lt varchar 15 gt Appendix C User Installation amp Operation Manual 100 lt Arg id 15 Pos 2 Attr lt int gt lt Predicate gt In this example the predicate ExistService has two arguments one is of char the other is integer Each of them should have an unique id The Pos specifies that the char is the first argument and the integer is the second argument The whole predicate is ExistService varchar int Each predicate which appears in the Implications section or HyperAlert Types section must be declared here This part goes into the Predicate table in the database In the Implications section there are two kinds of implications normal and phantom The phan tom implications mean that the implied predicate is unclear to us but it is clear to the attacker For example the conseguence of FTP Syst is GainOSInfo Through it the attacker knows what operating system is in the target machine either OSLinuz or OSWindows etc But we the corre lator cannot get this detailed information So we call this kind of implication GainOSInfo implies OSLinuz phantom implication Phantom implications and normal implications have the same effect in the correlation process Having phantom can correlate more related alerts which may be missed otherwise however it may also increase the false correlation rate Here is an example of implication lt Implication Pha
132. th International Symposium on Recent Advances in Intrusion Detection RAID 2002 Zurich Switzerland October 2002 Peng Ning Yun Cui Douglas S Reeves Constructing Attack Scenarios through Correlation of Intrusion Alerts To appear in Proceedings of the 9th ACM Conference on Computer amp Communications Security Washington D C November 2002 106
133. that connect with the nodes in ProcessedNodes We need update table Processed Nodes and Newly AddedNodes So select the nodes whose graphID is g but the nodes themselves are not in the set ProcessedNodes That is one node of an edge isn t in ProcessedNodes but the other node is already in it Replace NewlyAddedNodes with these nodes Append the nodes in NewlyAddedNodes into ProcessedNodes Repeat the above process until that NewlyAdded Nodes is null Thus one single graph g completes Figure 4 6 is the algorithm we use to generate a single graph with graph id is g Here are two gueries used in figure 4 6 Query1 in figure 4 6 INSERT INTO NewlyAddedNodes SELECT DISTINCT PreparingHyperAlertID FROM GraphEdges WHERE PreparedHyperAlertID IN SELECT FROM ProcessedNodes Chapter 4 Implementation empty table ProcessedNodes select one unassigned edge and assign g as its groupID write the two nodes of this edge into ProcessedNodes find all edges that connect to any nodes in ProcessedNodes and assign g as their graphID Using query 1 and query 2 to find the nodes that are in these edges but not in ProcessedNodes write them into NewlyAddedNodes NewlyAddedNodes empty graph g completes quit append NewlyAddedNodes to ProcessedNodes and empty NewlyAddedNodes Figure 4 6 The algorithm
134. tilities namely adjustable graph reduction focused analysis and graph decomposition to facilitate analysis of intensive alerts The experiments in Chapter 5 show this technique is very effective First it uncovers the high level attack scenario from a potentially large set of alerts The DARPA dataset 19 has a detailed description about the attacks included in the dataset The attack scenario generated by our tool matches this description very well Second the false alert rate is significantly dropped after we discard uncorrelated alerts In one experiment we reduce the false alert rate from 95 23 to 6 82 through correlation This is significant as it filters out most of the false alerts so that the intrusion Chapter 1 Introduction 3 detection analyst or system administrator can concentrate on the real attacks To evaluate the effectiveness of our technique we define two measurements soundness and completeness Soundness evaluates how correctly the alerts are correlated and completeness assesses how well we can correlate related alerts together The values of soundness are all above 90 however the lowest value of completeness is only 62 5 But further analysis reveals that all the alerts missed are those triggered by telnet If this factor is considered then the alerts correlated are highly accurate Third the three utilities are very useful in analyzing intensive dataset It is demonstrated through the analysis of the DEFCON 8 CTF d
135. tion about hyper alert types as well as relation ships between predicates To simplify the implementation we assume that each hyper alert type is uniquely identified by its name and there is no negation in the prerequisite nor the consequence of any hyper alert type 4 1 1 Database Structure There are totally five tables in the knowledge database Two tables Predicate and Implication contain the information about predicates and the other three tables HATFact HATPrereg and HATConseq have the information about hyper alert types 19 Chapter 4 Implementation 20 Knowledge Base Alert Correlation GraphV iz formatted file Graph Generator Preprocessor Engine yper alerts auxiliary data results prepare for relationsHips Prepare for relationships Database i i Management Hyper alerts correlation graphs Utility alerts System Processors Hyper alerts correlation graphs Figure 4 1 The architecture of the correlator Figure 4 2 shows the structures of the tables and some examples of the knowledge base Table Predicate figure 4 2 a stores all the predicates that appear in the knowledge base Their names the number of arguments and arguments data types are stored in the table So the Predicate table has three attributes Predicate ArgNum and ArgType to represent the predicate name the position of an argument and the data type of the argument respectively For example the first tup
136. to reduce the number of cross edges and make the graph more balanced As a result the graph does not reflect the actual stages of attacks Nevertheless Figure 5 6 provides a much clearer outline of the attacks The hyper alerts in stage 1 and about half of those in stage 2 correspond to scanning attacks Chapter 5 Experimental Results 48 HP_OpenView _SNMP_Backdoor P P Privi gedBounce E ur se A ES _Passwords CG FTI leg Nu BackOrifice eco if NO HTTP ColdFusion K Admin IN lt IN Y Y ll N A po Vi Sa ima _Execute A 2 A A a AS sa ELVE CHTTP_DotDot DA C EP Xi i x e M MM NEA NJ HTTP Netscape AS pl 58 N _PageServices 4 AS D D WA lt T ININ a zero S NI R EAN law ji STA ia pZ Z MIM TT mre _ViewExample AA IM Z HTTP_Site Csc_Access Figure 5 6 The fully reduced graph for the largest aggregated hyper alert correlation graph Chapter 5 Experimental Results 49 30000 25000 20000 count a o o o 4k of nodes of edges 0 100 200 300 400 500 600 700 interval threshold second Figure 5 7 Sizes of the reduced graphs w r t the interval threshold for the largest hyper alert correlation graph or attacks to gain information of the target systems e g ISS Port_Scan The upper part o
137. ts 44 5 3 Experiment on Defcon 8 dataset 45 biolo Initial AGE Pb gs lr re diene eee s 46 5 3 2 Adjustable Graph Reduction 47 5 9 9 Focused ANALYSIS 424 aaa mee Soe A a a a aa 50 5 3 4 Graph Decomposition ooa a e 50 6 Conclusions and Future Work 55 6 17 Conclusions 2 2 a oroo NAVE Z RARE a Tae pe E A A A a 55 6 32 Future Work s sis rn a e e ae A AA dje e ls 56 6 2 1 Real Time Correlator 56 6 2 25 Input Alerts m a se a A eee BA ar a Pod de 56 6 2 3 Identifying Missing Detections amp Predicating Alerts 56 6 2 4 Correlating Alerts from Different IDSs 57 List of References 58 A Knowledge Base Used In The Experiment 61 A 1 XML Schema for Knowledge Base 61 A 2 Knowledge Base Used for DARPA Dataset 68 A 3 Knowledge Base Used for DEFCON 8 Dataset 89 B JAVA Classes 96 C User Installation amp Operation Manual 98 El Introductions a e e aa td 98 6 2 Installations eri ee A AA Ao ar o RAE A A 98 C 2 1 System Environment y inn O Ee AAA A Dek a a eek 98 C222 cEhe klisti icon boob adds Pee eed ee BA 98 C 2 3 Download deere be a REE BAN RZ RRR SSS TED a Rp a ee 99 G 3 How to Use This Tool sipor goes aa E EE ea 99 C 341 Knowledge Base vi o eaten e a AAR aa da eee 99 Ci82 Rropertyib
138. ts How to recognize the alerts generated by different IDSs which are actually triggered by the same event These are all the research problems that need to be addressed List of References 10 11 12 http www cert org http www shmoo org cctf http www snort org http xml apache org Anderson J P Computer security threat monitoring and surveillance Technical report James P Anderson Co Fort Washington PA 1980 AT amp T Research Labs GraphViz open source graph layout and drawing software http www research att com sw tools graphviz Bace R Intrusion Detection Macmillan Technology Publishing 2000 Cuppens F and Miege A Alert correlation in a cooperative intrusion detection framework In Proc of the 2002 IEEE Symposium on Security and Privacy May 2002 Cuppens F and Ortalo R LAMBDA A language to model a database for detection of attacks In Proc of Recent Advances in Intrusion Detection RAID 2000 pages 197 216 September 2000 Dain O and Cunningham R Fusing a heterogeneous alert stream into scenarios In Proc of the 2001 ACM Workshop on Data Mining for Security Applications pages 1 13 Nov 2001 Debar H and Wespi A Aggregation and correlation of intrusion detection alerts In Recent Advances in Intrusion Detection LNCS 2212 pages 85 103 2001 Gardner R and Harle D Pattern discovery and specification translation for alarm correlatio
139. ttacks Predicates are the basic constructs to represent prereguisites and consequences of attacks For example a scanning attack may discover UDP services vulnerable to a certain buffer overflow attack Chapter 3 A Framework for Alert Correlation 8 We can use the predicate UDP Vulnerable ToBOF VictimIP VictimPort to represent the attacker s discovery Similarly if an attack requires a UDP service vulnerable to the buffer overflow attack we can use the same predicate to represent the prerequisite Some attacks may require several conditions be satisfied at the same time in order to be successful To represent such complex conditions a logical combination of predicates is allowed in order to describe the prerequisite of an attack For example a network launched buffer overflow attack may require the target host have a vulnerable UDP service accessible to the attacker through the firewall This prerequisite can be represented by UDPVulnerableToBOF VictimIP VictimPort A UDPAccessible ViaFirewall VictimIP VictimPort To simplify the discussion we restrict the logical operators to A conjunction and V disjunction We use a set of predicates to represent the consequence of an attack For example an attack may result in compromise of the root privilege as well as modification of the rhost file Thus we may use the following to represent the corresponding consequence GainRootAccess VictimIP rhostModified VictimIP Note that the
140. ttp www 11 mit edu IST ideval tools tools _index html 39 Chapter 5 Experimental Results 40 5 2 Experiment on DARPA 2000 dataset There are two separate datasets in DARPA 2000 evaluation data LLDOS 1 0 and LLDOS 2 0 2 LLDOS 1 0 contains a series of attacks in which an attacker probes breaks in installs the components necessary to launch a Distributed Denial of Service DDOS attack and actually launches a DDOS attack against an off site server LLDOS 2 0 2 includes a similar sequence of attacks run by an attacker who is a bit more sophisticated than the first one Each dataset includes the network traffic collected from both the DMZ and the inside part of the evaluation network We have performed four sets of experiments each with either the DMZ or the inside network traffic of one dataset Let s review the scenarios briefly In both scenarios the attacker tries to use the vulnerability of Sadmind RPC service and launches buffer overflow attacks against the vulnerable hosts The attacker installs the mstream distributed DOS software after he breaks into the hosts successfully And finally the attacker launches DDOS attacks from the victims The differences between these two scenarios lay in two aspects First the attacker uses IPSweep and Sadmind_Ping to find out the vulnerable hosts in LLDOS1 0 while DNS HInfo is used in LLDOS2 0 2 second the attacker attacks each host individually in LLDOS1 0 while in LLDOS2 0 2 the attacker breaks
141. tures If a match is found then it is reported as an attack otherwise it is not So misuse detection cannot detect novel attacks Intrusion detection systems can also be classified as network based and host based according to the information source of the detection Network based IDS monitors the network traffic and looks for network based attacks while host based IDS is installed on host and monitors the host audit Chapter 1 Introduction 2 trail Network based IDS and host based IDS have their own strength and limitations Network based IDS excels at detecting network level abnormalities or abuses but it cannot understand what is going on within the host If the traffic is encrypted network based IDS can do nothing about it The encrypted traffic can only be understood by host based IDS after the traffic is decrypted on the host But host based IDS also has its weakness It is hard to manage easy to be attacked and disabled as part of the attack does not suit for detecting network scans can be disabled by denial of service attacks and inflicts a performance cost on the monitored systems 16 Traditional intrusion detection systems usually focus on low level attacks or anomalies and raise alerts independently though there may be logical connections between them In situations where there are intensive intrusions not only will actual alerts be mixed with false alerts but the amount of alerts will also become unmanageable As a result it
142. ulting from graph decomposition with C g Cluster ID 10 SrcIP 010 020 011 251 DestIP 010 020 001 010 Figure 5 9 is related to Figure 5 8 since they both are about destination IP address 010 020 001 010 Indeed Figure 5 9 is a part of Figure 5 8 though in Figure 5 8 SS prepares for HTT P Campas through HTTP_DotDot Since all the hyper alerts in Figure 5 9 have the same source and destina tion IP addresses it is very possible that the correlated ones belong to the same sequence of attacks Note that HP_OpenView_SNMP_Backdoor appears as both connected and isolated node This is because some instances are correlated while the others are isolated We analyzed the correlated hyper alerts using the three utilities and discovered several strategies used by the attackers We first restricted us to the hyper alert correlation graphs that satisfies the clustering constraint Cy One common strategy reflected by these graphs is to use scanning attacks followed by attacks that may lead to execution of arbitrary code For example the attacker s at 010 020 011 099 scanned host 010 020 001 010 with CyberCop_Scanner IPHalfScan Nmap_Scan and Port_Scan and then launched a sequence of HTTP based attacks e g HTTP_DotDot and FTP based attacks e g FTP_Root The attacker s at 010 020 011 093 and 010 020 011 227 also used a similar sequence of attacks against the host 010 020 001 008 As another strategy the attacker s at 010 020 011 240 used a co
143. ure 4 2 e is similar to HATPrereg The only difference is this table contains the hyper alert type s consequence information 4 1 2 Knowledge Base XML File An XML file is designed to provide a way to input the knowledge base and Xerces Java 3 is adopted as the XML parser There are several advantages of using XML First it is easy to read and under stand for human users Second it is easy to validate by using some existing tools In a knowledge Chapter 4 Implementation 22 lt Predicates gt lt Predicate Name ExistHost gt lt Arg id 1 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name ExistService gt lt Arg id 2 Pos 1 Attr varchar 15 gt lt Arg gt lt Arg id 3 Pos 2 Attr int gt lt Arg gt lt Predicate gt lt Predicate Name Gain0SInfo gt lt Arg id 4 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name 0SUnix gt lt Arg id 5 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicate Name VulnerableRPCService gt lt Arg id 6 Pos 1 Attr varchar 15 gt lt Arg gt lt Predicate gt lt Predicates gt Figure 4 3 A sample Predicates section in a knowledge base XML file base XML file there are basically three sections Predicates Implications and HyperAlertTypes Predicates The Predicates section contains a set of Predicates which are used to represent the prerequisites and consequences
144. ween true alerts and false alerts In this thesis work I implement an alert correlation tool based on this framework It consists of the following components a knowledge base an alert preprocessor an alert correlation engine and a graph output component To further facilitate analysis of large amounts of intrusion alerts I develop three utilities namely adjustable graph reduction focused analysis and graph decomposition I also perform a sequence of experiments to evaluate the aforementioned techniques using DARPA 2000 evaluation datasets 19 and DEFCON 8 CTF dataset 2 The experimental results show that the proposed techniques are effective First we successfully construct attack scenarios behind the low level alerts second the false alert rates are significantly reduced after the attention is focused on alerts that are correlated with others third the three utilities greatly reduce the complexity of the correlated alerts while at the same time maintaining the structure of the correlated alerts A TOOLKIT FOR INTRUSION ALERTS CORRELATION BASED ON PREREQUISITES AND CONSEQUENCES OF ATTACKS BY YUN CUI A THESIS SUBMITTED TO THE GRADUATE FACULTY OF NORTH CAROLINA STATE UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE DEPARTMENT OF COMPUTER SCIENCE RALEIGH DECEMBER 2002 APPROVED BY DR PENG NING CHAIR OF ADVISORY COMMITTEE DR DOUGLAS S REEVES DR GREGORY T B
145. xample section 1 database connection db Driver com microsoft jdbc sqlserver SQLServerDriver dbURL jdbc microsoft sqlserver balisong 1438 DatabaseName defcon8 vol1 SelectMethod cursor newTable insert into events select distinct e sid e cid e signature s sig name e timestamp 1 2p_src i ip dst t tcp_sport t tcp_dport from event e signature s iphdr i tcphdr t where e signature s sig id and e sid i sid and e cid i cid and e sid t sid and e cid t cid section 2 knowledge base Generate_Knowledge_Base true Knowledge Base XML File DARPA_2K_final xml section 3 correlation engine AlertTable events column names of RealSecure amp MSSQL the following 4 are static keywords AlertID EventID AlertName OrigEventName BeginTime EventDate EndTime EventDate the following are dynamic keywords based on knowledge base SrcIPAddress SrcIPAddress SrcPort SrcPort DestIPAddress DestIPAddress DestPort DestPort Original_Graph_Output darpa dmzl tat Below are the three utilities section 4 graph reduction Aggregation Time Interval 1 Appendix C User Installation amp Operation Manual 102 Graph Reduction Output dmz_a tat section 5 focused analysis Focused Analysis GraphID 9 Focusing Constraint SrcIPAddress 152 14 53 39 Focused Aggregation true Focused Aggregation Time Interval Focused Output section 6 graph decomposition Decompositi
146. xistService DestIP DestPort AND Solaris2 6 DestIP GainRootAccess DestIP SYNFlood ExistService DestIP DestPort System Attacked DestIP TCP_Overlap_Data TCP_Urgent_Data System Attacked DestIP TelnetEnvAll ExistService DestIP DestPort System Attacked DestIP Telnet Terminaltype ExistService DestIP DestPort GainTerminalType DestIP TelnetX display ExistService DestIP DestPort SystemAttacked DestIP Tool Talk Overflow VulnerableRPCService DestIP AND GainOSInfo DestIP GainRootAccess DestIP Trace Route GainNetworkInfo DestIP TrinooDaemon SystemCompromised SrcIP AND SystemCompromised DestIP ReadyToLaunchDOSAttack UDP_Port_Scan Exist Host DestIP GainServicelnfo DestIP Windows Access Error The fact component of all these hyper alert types is SrcIP SrcPort DestIP DestPort Appendix B JAVA Classes There are twelve Java classes in this tool AssignGraphID CorrelationEngine Correlator Focused Analysis GraphDecomposition GraphOutput GraphReduction HATMapping HyperAlertType KnowledgeBase SimplifiedGraphOutput and TransitiveExclusion Among them Correlator is the main one to call other classes AssignGraphIDis to separate the prepare for relationships into different graphs Table GraphEdges is the output CorrelationEngine is the class to preprocess the alerts and do the correlation First it

discovery.csc.ncsu.edu - Repository

Contents

Download Pdf Manuals

Related Search

Related Contents