A Constrained Approximate Search Scenario for Intrusion Detection in Hosts and Networks

It is well known that most new attacks against computer systems and networks originate from the old ones. Namely, it is possible to change the old attack patterns in such a way that the modified patterns affect approximately the same targets on the victim system and pass undetected by signature-based Intrusion Detection Systems (IDS) or other detection tools. In this paper, we consider a scenario where an old attack pattern is changed by means of an automatic tool. The structure of changes must be kept under control in order for the attack to remain effective. For example, the number of changed symbols in an automatically crafted string in the attack pattern must be limited. Otherwise, this string would not affect the victim system in the same way as in the original attack. Under such an assumption, we describe the requirements for a search algorithm implemented in the detection tool (for example, an IDS) that would be capable of detecting the changes in the old attack signature. We present the basic structure of a generic search algorithm of this kind, describe some application scenarios and discuss the effectiveness of the algorithm under these scenarios.