CS 590D, 2004 1Temporal Sequence Learning and DataTemporal Sequence Learning and DataReduction for Anomaly DetectionReduction for Anomaly DetectionBy By TerranTerran Lane and Carla E. Lane and Carla E. BrodleyBrodleyPresented by Maja PusaraPresented by Maja PusaraECE Department ECE Department –– Purdue University Purdue UniversityFebruary 5, 2004February 5, 2004CS 590D, 2004 2Intrusion Detection ClassificationIntrusion Detection ClassificationNetwork IntrusionDetection Systems -NIDSIntrusion DetectionSystemsHost IntrusionDetection Systems -HIDSCS 590D, 2004 3Intrusion Detection ClassificationIntrusion Detection Classification(Continued)(Continued)Anomaly Detection(Behavior-Based)Intrusion DetectionSystemsSignature Matching(Knowledge-Based)CS 590D, 2004 4IDS Design ProcessIDS Design ProcessDataCollectionDataNormalizationFeatureSelectionClassificationCS 590D, 2004 5Data Sources for HIDSData Sources for HIDSSystemSystemCallsCallsDataDataSourcesSourcesCommandCommandLineLineGUIGUIEventsEventsKeystrokesKeystrokes. . .. . .MouseMouseMovementMovementCS 590D, 2004 6Data CollectionData Collection% pwd% ls% cat file1.txt file2.txt > file3.txt% rm file1.txtIntrusionDetectionSystemCommand line data:Command line data:CS 590D, 2004 7Instance-Based Anomaly DetectionInstance-Based Anomaly DetectionSystemSystemCS 590D, 2004 8Instance-Based Anomaly DetectionInstance-Based Anomaly DetectionSystemSystemCS 590D, 2004 9What is in the Data Set?What is in the Data Set?Discrete vs. ContinuousDiscrete vs. ContinuousTime dependent vs. Time independentTime dependent vs. Time independentNumerical vs. Non-numericalNumerical vs. Non-numerical% pwd% ls% cat <2> > <1>% rm <1>CS 590D, 2004 10What is in the Data Set?What is in the Data Set?DiscreteDiscrete vs. Continuous vs. ContinuousTime dependentTime dependent vs. Time independent vs. Time independentNumerical vs. Numerical vs. Non-numericalNon-numerical% pwd% ls% cat <2> > <1>% rm <1>Temporal Sequence DataTemporal Sequence DataCS 590D, 2004 11Feature ExtractionFeature ExtractionCS 590D, 2004 12Similarity FunctionSimilarity Function••Input:Input:––Data stream forming a feature vector ofData stream forming a feature vector offixed-length Lfixed-length L––UserUser’’s behavioral profile containing Ds behavioral profile containing Dsequencessequences••Output:Output:––Temporal sequence of real-valued similarityTemporal sequence of real-valued similaritymeasuresmeasuresCS 590D, 2004 13Similarity Function (Continued)Similarity Function (Continued)Given two sequences of equal length LGiven two sequences of equal length LWe compute the followingWe compute the followingCS 590D, 2004 14Similarity Function (Continued)Similarity Function (Continued)CS 590D, 2004 15Noise SuppressionNoise SuppressionCS 590D, 2004 16Noise Suppression (Continued)Noise Suppression (Continued)••Input:Input:––Results of the similarity function for eachResults of the similarity function for eachsequence over a sliding window of Wsequence over a sliding window of Wsequencessequences••Output:Output:––Temporal sequence of smoothed real-valuedTemporal sequence of smoothed real-valuedsimilarity measuressimilarity measuresCS 590D, 2004 17Noise Suppression (Continued)Noise Suppression (Continued)11stst W sequences W sequences22ndnd W sequences W sequences 2 1 3 4 W W+1•• Sliding window of W sequences: Sliding window of W sequences: •• Noise suppression function: Noise suppression function:CS 590D, 2004 18ClassificationClassificationCS 590D, 2004 19What Learning Method to Apply?What Learning Method to Apply?Supervised• Closed setting• Labeled data• Examples:• Decision trees• Neural networksSupervisedSupervised•• Closed settingClosed setting•• Labeled data Labeled data•• Examples: Examples:•• Decision trees Decision trees•• Neural networks Neural networksUnsupervised• Open setting• Non-labeled data• Examples:• Markov models• Instance-based learningUnsupervisedUnsupervised•• Open setting Open setting•• Non-labeled data Non-labeled data•• Examples: Examples:•• Markov models Markov models•• Instance-based Instance-based learning learningCS 590D, 2004 20IBL ClassificationIBL Classification••Input:Input:––Temporal sequence of smoothed real-valuedTemporal sequence of smoothed real-valuedsimilarity measuressimilarity measures••Output:Output:––Binary values:Binary values:••1 is 1 is ““normalnormal””••0 is 0 is ““abnormalabnormal””CS 590D, 2004 21Threshold SelectionThreshold SelectionCS 590D, 2004 22Threshold Selection (Continued)Threshold Selection (Continued)T-min=r/2T-min=r/2T-max=r/2T-max=r/2rr“Normal” RangeCS 590D, 2004 23Classification FunctionClassification Function•• NeymanNeyman-Pearson hypothesis test: -Pearson hypothesis test: ••Acceptance region:Acceptance region:––Between T-min and T-maxBetween T-min and T-max––Smaller r implies a wider acceptance regionSmaller r implies a wider acceptance regionCS 590D, 2004 24Concept DriftConcept DriftCS 590D, 2004 25••Real-world data sets:Real-world data sets:––8 UNIX users8 UNIX users––7,000 tokens per user7,000 tokens per user––Collected over a time period of two yearsCollected over a time period of two years••Performance criteria:Performance criteria:––AccuracyAccuracy••Acceptance rateAcceptance rate••Alarm rateAlarm rate––Time to alarm (TTA)Time to alarm (TTA)Empirical EvaluationEmpirical EvaluationTPTPFPFPTNTNFNFNAABBBBAACS 590D, 2004 26Experimental SetupExperimental Setup••Parametric values:Parametric values:––Sequence length L=10Sequence length L=10––Window length W=100Window length W=100––rr••Division of the data set:Division of the data set:CS 590D, 2004 27Experimental Results: AccuracyExperimental Results: AccuracyCS 590D, 2004 28Experimental Results: TTAExperimental Results: TTACS 590D, 2004 29Storage ReductionStorage Reduction••Instance selection:Instance selection:––RandomRandom––FIFOFIFO––LRULRU––LFULFU••ClusteringClustering––K-centersK-centers––Greedy clustering algorithmGreedy clustering algorithmCS 590D, 2004 30Instance Selection Results: AccuracyInstance Selection Results: AccuracyRandomLFUFIFOLRUCS 590D, 2004 31Instance Selection Results: TTAInstance Selection Results: TTARandomLFUFIFOLRUCS 590D, 2004 32Clustering AlgorithmsClustering Algorithms••K-centers
View Full Document
Unlocking...