Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Dynamic Behavior Matching: A Complexity Analysis and New Approximation Algorithms
verfasst von : Matthew Fredrikson, Mihai Christodorescu, Somesh Jha
Erschienen in: Automated Deduction – CADE-23
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.