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  [8]. 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  [5].

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  [6, 7]. More recently, we have developed efficient algorithms for network packet classification, a central problem in the context of signature-based network intrusion detection systems  [3, 4].

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

Related Publications

[1]  Fast Packet Classification using Condition Factorization

Alok Tongaonkar, R. Sekar and Sreenaath Vasudevan
Applied Cryptography and Network Security (ACNS) June, 2009.

[2]  An Efficient Black-box Technique for Defeating Web Application Attacks

R. Sekar
ISOC Network and Distributed Systems Symposium (NDSS) February, 2009.

[3]  Fast Packet Classification for Snort

Alok Tongaonkar, Sreenaath Vasudevan and R. Sekar
USENIX Large Installation System Administration Conference (LISA) November, 2008.

[4]  Inferring Higher Level Policies from Firewall Rules

Alok Tongaonkar, Niranjan Inamdar and R. Sekar
USENIX Large Installation System Administration Conference (LISA) November, 2007.

[5]  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.).

[6]  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.

[7]  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.

[8]  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