Brief Announcement: Graph-Based and Probabilistic Discrete Models Used in Detection of Malicious Attacks

Design of program secure systems is connected with choice of mathematical models of the systems. A widely-used approach to malware detection (or classification as “benign-malicious”) is based on the system calls traces similarity measurement. Presently both the set-theoretical metrics (for example, Jaccard similarity, the Edit (Levenshtein) distance (ED) [1]) between the traces of system calls and the Markov chain based models of attack effect are used. Jaccard similarity is used when the traces are considered as a non-ordering set. The Edit Distance, namely, the minimal number of edit operations (delete, insert and substitute of a single symbol) required to convert one sequence to the other, is used as it reflects the traces ordering and semantics. However, the time and space complexity of the edit distance between two strings requires quadratic (in symbol numbers) complexity [1]. The traces can also be represented as a system calls graphs [2], the nodes of which are the system calls (or the items of the q-grams [1]). That is, we can consider the traces description by the ordered string as a partial case of the graph representation, for which it is possible to use the same similarity metrics with the same computational complexity.

This work demonstrates a framework for combining both graph-based and probabilistic models enabling both the analysis of the system robustness to malicious attacks and malicious codes recognition and detection.