Application of SA algorithm in intrusion detection based on model reasoning

In view of the fact that the model-based intrusion detection method needs to search for the optimal value in a huge number of attack script subsets in a huge audit record space, the simulated annealing algorithm is proposed for this NP-complete problem. The optimization problem model of attack detection is established, the solution space, objective function, generation and acceptance criteria of new solutions in the attack detection experiment are given, a reasonable cooling schedule is obtained, and the simulated annealing algorithm in the experiment is studied in parallel. The experiment proves that compared with the traditional greedy algorithm, the application of the simulated annealing algorithm improves the evolution speed and global optimization ability, and solves the search efficiency problem better. Keywords Simulated annealing algorithm; model reasoning; intrusion detection; network security 1 Intrusion detection method based on model reasoning Intrusion refers to any behavior that attempts to endanger the integrity, confidentiality or availability of resources. Intrusion detection is the identification of these behaviors. Due to the diversity of intrusion patterns, intrusion detection strategies and models also have many different types [1,2]. The intrusion detection method based on model reasoning establishes a specific model for the intrusion behavior and infers whether the intrusion behavior occurs in combination with the attack script. A large part of the information used in intrusion detection comes from the system log and audit information. Intruders often leave their traces in the system log, so making full use of the system\'s log files and audit information is a necessary means to detect intrusions. The log contains evidence of unusual and unexpected activities occurring on the system and network. By analyzing the log files and audit information, successful intrusions or intrusion attempts can be discovered. There are many audit mechanisms in the Unix operating system, and audit tools can be reconfigured, so a large amount of audit data can be generated. In order to extract security-related information from the huge amount of information to generate attack scripts, the historical audit files are first preprocessed to generate user session vectors. User sessions include all events between login and logout. The session vector A= describes the number of various events performed by the user during a single session. The session starts at login and ends at logout, and the number of logins and logouts is also part of the session vector. More than 20 events can be monitored, such as: login time, number of login failures, number of files written, number of files read, etc. The generated user session vector is then submitted to the analysis module, which can use statistics, expert systems and other methods to establish attack scripts for intrusion detection and store them in the attack script library. The script library is an m×n dimensional event matrix, and a column vector represents the session vector corresponding to an attack. During detection, a subset of these attack scripts is first assumed to be the attack that the system is facing. Then, through a predictor program module, a subset of attack scripts that needs to be verified is generated according to the current behavior pattern and passed to the decision maker. After receiving the information, the decision maker translates these assumed attack behaviors into an audit record format that matches the specific system according to the possible appearance of these assumed attack behaviors in the audit records, and finds the corresponding information in the audit records to determine whether the attack has occurred. The essence of intrusion detection based on model reasoning is to search for possible attack subsets in the audit records. In practical applications, it is found that the audit record data volume of the general system is huge: a typical C2-level audit mechanism will generate 1 GB of data in less than 1 hour in a multi-user system; a 4CPU SPARC SUN system needs to use two CPUs and all disk channels to record the activities of the other two CPUs; in a network environment, the data volume will be even larger. At the same time, the number of attack script subsets is also huge. Assuming that there are n metrics potentially related to intrusion in the attack script, the number of subsets composed of these n metrics reaches 2n. The problem of finding corresponding information in audit records to confirm or deny these attacks can be regarded as similar to a non-deterministic polynomial (NP) complete problem, that is, finding the optimal solution or quasi-optimal solution in a complex and huge search space. When solving such problems, if the inherent knowledge of the problem cannot be used to narrow the search space, a combinatorial explosion of the search will occur. Therefore, based on the existing achievements of model reasoning methods, this paper proposes to apply the simulated annealing (SA) algorithm to intrusion detection based on model reasoning. The four elements of the simulated annealing algorithm: solution space, objective function, generation of new solutions, and selection of acceptance criteria in attack detection are discussed, the main SA algorithm code of the experiment is given, and the SA algorithm for attack detection is parallelized. 2 SA algorithm There are many methods to find the optimal solution of NP-complete problems, such as linear programming, greedy algorithm, etc., but these algorithms are often not feasible due to the limitation of computing time. An important feature of intrusion detection is to be real-time, so the above algorithms are not suitable for intrusion detection based on model reasoning [3,4]. The simulated annealing algorithm is an effective approximate algorithm for solving large-scale combinatorial optimization problems [5], especially NP-complete problems. It is derived from the simulation of solid annealing process, adopts Metropolis acceptance criterion, and uses a set of parameters called cooling schedule to control the algorithm process, so that the algorithm can give an approximate optimal solution in polynomial time. The main features of the simulated annealing algorithm are high efficiency, robustness, generality and flexibility. Although there are still many problems to be further studied in theory and application methods of the algorithm itself, practice has proved that the simulated annealing algorithm is very effective for NP-complete problems in combinatorial optimization. 3 SA Application Research 3.1 Description of the Problem The goal of this paper is to determine which of all possible attack subsets is the most threatening to the system based on the events in the audit trail records, that is, for a specific attack subset, count the number of each type of events generated by all attacks. If this number is less than or equal to the number of recorded events, the assumption that \"the attack subset exists\" is valid. In order to describe the problem more accurately in mathematical form.