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.

Research Areas

Research Problems

Local Search