Towards Generating High Coverage Vulnerability-based Signatures with Protocol-level Constraint-guided Exploration (CMU-CyLab-08-009)

Signature-based input filtering is an important and widely deployed defense. But current signature generation methods have limited coverage and the generated signatures can be easily evaded by an attacker with small variations of the exploit message. In this paper, we propose protocol-level constraint-guided exploration, a new approach towards generating high coverage vulnerability-based signatures. In particular, our approach generates high coverage, yet compact, vulnerability point reachability predicates, which capture many paths to the vulnerability point. We have implemented Endeavour, a system that implements our approach. Our results show that our signatures have high coverage (optimal or close to optimal in our experiments) and are small (often human-readable), offering dramatic improvements over previous approaches.