Paper Info
Title
Dynamic behavior matching: a complexity analysis and new approximation algorithms
Abstract
A number of advances in software security over the past decade have foundations in the behavior matching problem: given a specification of software behavior and a concrete execution trace, determine whether the behavior is exhibited by the execution trace. Despite the importance of this problem, precise descriptions of algorithms for its solution, and rigorous analyses of their complexity, are missing in the literature. In this paper, we formalize the notion of behavior matching used by the software security community, study the complexity of the problem, and give several algorithms for its solution, both exact and approximate. We find that the problem is in general not efficiently solvable, i.e. behavior matching is NP-Complete. We demonstrate empirically that our approximation algorithms can be used to efficiently find accurate solutions to real instances.
Year
DOI
Venue
2011
10.1007/978-3-642-22438-6_20
CADE
Keywords
Field
DocType
past decade,behavior matching,concrete execution trace,software security,software security community,approximation algorithm,precise description,dynamic behavior matching,complexity analysis,accurate solution,execution trace,new approximation algorithm,software behavior
Approximation algorithm,Discrete mathematics,Software behavior,Exact algorithm,Computer science,Software security assurance,Algorithm,Theoretical computer science,Tree automaton,3-dimensional matching
Conference
Volume
ISSN
Citations 
6803
0302-9743
6
PageRank 
References 
Authors
0.45
16
3
Name
Order
Citations
PageRank
Matt Fredrikson197248.56
Mihai Christodorescu2116385.97
S. Jha37921539.19