Stony Brook University Logo Department of Computer Science Stony Brook Search Button
Secure Systems Lab

Efficient Algorithms for Security Applications

Although we don't pursue purely algorithmic research, we work on a number of problems where efficient algorithms are required for addressing security problems. For instance, our work on specification-based intrusion detection was based on algorithms for constructing efficient automata for matching regular expressions over events  [19]. Our work on anomaly detection relies on automata-based models of program behavior. We have relied on efficient string-matching algorithms for efficiently learning dataflow relationships between system call events that represent the transitions in this automata  [16].

Our network anomaly detection work develops linear-time algorithms for computing several statistical measures on network packets so as to scale to high-speed networks  [17, 18]. More recently, we have developed efficient algorithms for network packet classification, a central problem in the context of signature-based network intrusion detection systems  [14, 15].

Recently, we have started investigating the use of approximate string matching algorithms in the context of taint analysis, and reasoning about privacy leaks  [13].

Related Publications

[1]  A New Tag-Based Approach for Real-Time Detection of Advanced Cyber Attacks
Md Nahid Hossain
PhD Dissertation (Stony Brook University) January, 2022.
[2]  On the Effectiveness of Cyber-Attack Campaign Investigation with Reduced Audit Logs
Maggie Zhou
Undergraduate (Honors) Thesis (Stony Brook University) January, 2021.
[3]  Combating Dependence Explosion in Forensic Analysis Using Alternative Tag Propagation Semantics
Md Nahid Hossain, Sanaz Sheikhi and R. Sekar
IEEE Symposium on Security and Privacy (IEEE S&P) May, 2020.
(A 2-minute demo and the conference presentation are also available.).
[4]  HOLMES: Real-time APT Detection through Correlation of Suspicious Information Flows
Sadegh Milajerdi, Rigel Gjomemo, Birhanu Eshete, R. Sekar and V.N. Venkatakrishnan
IEEE Symposium on Security and Privacy (IEEE S&P) May, 2019.
[5]  Dependence-Preserving Data Compaction for Scalable Forensic Analysis
Md Nahid Hossain, Junao Wang, R. Sekar and Scott D. Stoller
USENIX Security Symposium (USENIX Security) August, 2018. (Talk).
[6]  SLEUTH: Real-time Attack Scenario Reconstruction from COTS Audit Data
Md Nahid Hossain, Sadegh Milajerdi, Junao Wang, Birhanu Eshete, Rigel Gjomemo, R. Sekar, Scott D. Stoller and V.N. Venkatakrishnan
USENIX Security Symposium (USENIX Security) August, 2017. (Talk).
[7]  Lifting Assembly to Intermediate Representation: A Novel Approach Leveraging Compilers
Niranjan Hasabnis and R. Sekar
ACM Architectural Support for Programming Languages and Operating Systems (ASPLOS) April, 2016.
[8]  Condition Factorization: A Technique for Building Fast and Compact Packet Matching Automata
Alok Tongaonkar and R. Sekar
IEEE Transactions on Information Forensics and Security (IEEE TIFS) March, 2016.
[9]  Automatic Synthesis of Instruction Set Semantics
Niranjan Hasabnis
PhD Dissertation (Stony Brook University) July, 2015.
[10]  Protection, Usability and Improvements in Reflected XSS Filters
Riccardo Pelizzi and R. Sekar
ACM Symposium on Information, Computer and Communications Security (ASIACCS) May, 2012.
[11]  Efficient Techniques for Fast Packet Classification
Alok Tongaonkar
PhD Dissertation (Stony Brook University) August, 2009.
[12]  Fast Packet Classification using Condition Factorization
Alok Tongaonkar, R. Sekar and Sreenaath Vasudevan
Applied Cryptography and Network Security (ACNS) June, 2009.
[13]  An Efficient Black-box Technique for Defeating Web Application Attacks
R. Sekar
ISOC Network and Distributed Systems Symposium (NDSS) February, 2009.
[14]  Fast Packet Classification for Snort
Alok Tongaonkar, Sreenaath Vasudevan and R. Sekar
USENIX Large Installation System Administration Conference (LISA) November, 2008.
[15]  Inferring Higher Level Policies from Firewall Rules
Alok Tongaonkar, Niranjan Inamdar and R. Sekar
USENIX Large Installation System Administration Conference (LISA) November, 2007.
[16]  Dataflow Anomaly Detection
Sandeep Bhatkar, Abhishek Chaturvedi and R. Sekar
IEEE Symposium on Security and Privacy (IEEE S&P) May, 2006. (Supercedes Technical Report SECLAB-05-03 Improving Attack Detection in Host-Based IDS by Learning Properties of System Call Arguments, July 2005.).
[17]  Specification-based anomaly detection: a new approach for detecting network intrusions
R. Sekar, Ajay Gupta, James Frullo, Tushar Shanbhag, Abhishek Tiwari, Henglin Yang and Sheng Zhou
ACM Conference on Computer and Communications Security (CCS) October, 2002.
[18]  A High-Performance Network Intrusion Detection System
R. Sekar, Guang Yang, Shobhit Verma and Tushar Shanbhag
ACM Conference on Computer and Communications Security (CCS) November, 1999.
[19]  Synthesizing Fast Intrusion Detection/Prevention Systems from High-Level Specifications
R. Sekar and Prem Uppuluri
USENIX Security Symposium (USENIX Security) August, 1999.
Overview

Research Areas

Source-code analysis/transformation
Binary analysis/rewriting
Policy/Specification Languages
OS and Virtualization Techniques
Algorithms
Learning/anomaly detection
Formal methods/Foundations


Research Problems

Randomization/Memory Errors
Information flow analysis
Automated Exploit Defenses
Virtual Network Lab
Safe execution/attack recovery
Automated signature generation
Malware/Untrusted code defense
Intrusion/Anomaly detection
Fast packet matching
Policy generation tools


Local Search



Home Contact NSI Computer Science Stony Brook University

Copyright © 1999-2013 Secure Systems Laboratory, Stony Brook University. All rights reserved.