Towards adaptive anomaly detection systems using boolean combination of hidden Markov models

Khreich, Wael (2011). Towards adaptive anomaly detection systems using boolean combination of hidden Markov models. Thèse de doctorat électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (1MB) | Prévisualisation

Résumé

Anomaly detection monitors for significant deviations from normal system behavior. Hidden Markov Models (HMMs) have been successfully applied in many intrusion detection applications, including anomaly detection from sequences of operating system calls. In practice, anomaly detection systems (ADSs) based on HMMs typically generate false alarms because they are designed using limited representative training data and prior knowledge. However, since new data may become available over time, an important feature of an ADS is the ability to accommodate newly-acquired data incrementally, after it has originally been trained and deployed for operations. Incremental re-estimation of HMM parameters raises several challenges. HMM parameters should be updated from new data without requiring access to the previously-learned training data, and without corrupting previously-learned models of normal behavior. Standard techniques for training HMM parameters involve iterative batch learning, and hence must observe the entire training data prior to updating HMM parameters. Given new training data, these techniques must restart the training procedure using all (new and previously-accumulated) data. Moreover, a single HMM system for incremental learning may not adequately approximate the underlying data distribution of the normal process, due to the many local maxima in the solution space. Ensemble methods have been shown to alleviate knowledge corruption, by combining the outputs of classifiers trained independently on successive blocks of data.

This thesis makes contributions at the HMM and decision levels towards improved accuracy, efficiency and adaptability of HMM-based ADSs. It first presents a survey of techniques found in literature that may be suitable for incremental learning of HMM parameters, and assesses the challenges faced when these techniques are applied to incremental learning scenarios in which the new training data is limited and abundant. Consequently, An efficient alternative to the Forward-Backward algorithm is first proposed to reduce the memory complexity without increasing the computational overhead of HMM parameters estimation from fixed-size abundant data. Improved techniques for incremental learning of HMM parameters are then proposed to accommodate new data over time, while maintaining a high level of performance. However, knowledge corruption caused by a single HMM with a fixed number of states remains an issue. To overcome such limitations, this thesis presents an efficient system to accommodate new data using a learn-and-combine approach at the decision level. When a new block of training data becomes available, a new pool of base HMMs is generated from the data using a different number of HMM states and random initializations. The responses from the newly-trained HMMs are then combined to those of the previously-trained HMMs in receiver operating characteristic (ROC) space using novel Boolean combination (BC) techniques. The learn-and-combine approach allows to select a diversified ensemble of HMMs (EoHMMs) from the pool, and adapts the Boolean fusion functions and thresholds for improved performance, while it prunes redundant base HMMs. The proposed system is capable of changing its desired operating point during operations, and this point can be adjusted to changes in prior probabilities and costs of errors.

During simulations conducted for incremental learning from successive data blocks using both synthetic and real-world system call data sets, the proposed learn-and-combine approach has been shown to achieve the highest level of accuracy than all related techniques. In particular, it can sustain a significantly higher level of accuracy than when the parameters of a single best HMM are re-estimated for each new block of data, using the reference batch learning and the proposed incremental learning techniques. It also outperforms static fusion techniques such as majority voting for combining the responses of new and previously-generated pools of HMMs. Ensemble selection techniques have been shown to form compact EoHMMs for operations, by selecting diverse and accurate base HMMs from the pool while maintaining or improving the overall system accuracy. Pruning has been shown to prevents pool sizes from increasing indefinitely with the number of data blocks acquired over time. Therefore, the storage space for accommodating HMMs parameters and the computational costs of the selection techniques are reduced, without negatively affecting the overall system performance. The proposed techniques are general in that they can be employed to adapt HMM-based systems to new data, within a wide range of application domains. More importantly, the proposed Boolean combination techniques can be employed to combine diverse responses from any set of crisp or soft one- or two-class classifiers trained on different data or features or trained according to different parameters, or from different detectors trained on the same data. In particular, they can be effectively applied when training data is limited and test data is imbalanced.

Titre traduit

Vers des systèmes adaptatifs de détection d'anomalies utilisant des combinaisons booléennes de modèles de Markov cachés

Résumé traduit

La détection d’anomalies permet de surveiller les déviations significatives du comportement normal d’un système. Les modèles de Markov cachés (MMCs) ont été utilisés avec succès dans différentes applications de détection d’intrusions, en particulier la détection d’anomalies à partir de séquences d’appels système. Dans la pratique, les systèmes de détection d’anomalies (SDAs) basés sur les MMCs génèrent typiquement de fausses alertes étant donné qu’ils ont été conçu en utilisant des données d’apprentissage et des connaissances préalables limitées. Mais puisque de nouvelles données peuvent être acquises avec le temps, les SDAs doivent s’adapter aux nouvelles données une fois qu’ils ont été entraînés et mis en opération. La ré-estimation incrémentale des paramètres des MMCs présente plusieurs défis à relever. Ces paramètres devront être ajustés selon l’information fournie par les nouvelles données, sans réutiliser les données d’apprentissage antérieures et sans compromettre les informations déjà acquises dans les modèles de comportement normal.

Les techniques standards pour l’entraînement des paramètres des MMCs utilisent l’apprentissage itératif en mode « batch » et doivent ainsi observer la totalité de la base de données d’apprentissage avant d’ajuster les paramètres des MMCs. À l’acquisition de nouvelles données, ces techniques devraient recommencer la procédure de l’apprentissage en utilisant toutes les données accumulées. En outre, un système d’apprentissage incrémental basé sur un seul MMC n’a pas la capacité de fournir une bonne approximation de la distribution sous-jacente du comportement normal du processus à cause du grand nombre des maximums locaux. Les ensembles de classificateurs permettent de réduire la corruption des connaissances acquises, en combinant les sorties des classificateurs indépendamment entraînés sur des blocs de données successives.

Cette thèse apporte des contributions au niveau des MMCs ainsi qu’en regard de la décision des classificateurs dans le but d’améliorer la précision, l’efficacité et l’adaptabilité des SDAs basés sur les MMCs. Elle présente en premier lieu une étude d’ensemble des techniques qui peuvent être utilisées pour l’apprentissage incrémental des paramètres des MMCs et évalue les défis rencontrés par ces techniques lors d’un apprentissage incrémental avec des données limitées ou abondantes. Par conséquent, une alternative efficace à « l’algorithme avant-arrière » est proposée pour réduire la complexité de la mémoire sans augmenter le coût computationnel de l’estimation des paramètres des MMCs, faite à partir de données fixes. D’autre part, elle propose des améliorations aux techniques d’apprentissage incrémental des paramètres des MMCs pour qu’elles s’adaptent à des nouvelles données, tout en conservant un niveau de performance élevé. Cependant, le problème de la corruption des connaissances acquises causée par l’utilisation d’un système basé sur un seul MMC n’est toujours pas complètement résolu. Pour surmonter ces problèmes, cette thèse présente un système efficace qui s’adapte aux nouvelles données, en utilisant une approche apprentissage-combinaison au niveau décision. À l’arrivée d’un nouveau bloc de données d’apprentissage, un ensemble de MMCs est généré en variant le nombre d’états et l’initialisation aléatoire des paramètres. Les réponses des MMCs entraînés sur les nouvelles données sont combinées avec celles des MMCs déjà entraînés sur les données antérieures dans l’espace ROC (caractéristique de fonctionnement du récepteur, receiver operating characteristic), en utilisant les techniques de combinaison booléenne. L’approche apprentissage-combinaison proposée permet de sélectionner un ensemble diversifié de MMCs et d’ajuster les fonctions booléennes et les seuils de décision, tout en éliminant les MMCs redondants. Pendant la phase d’opération, le système proposé est capable de changer le point d’opération et celui-ci peut s’adapter au changement des probabilités a priori et des coûts des erreurs.

Les résultats des simulations obtenus sur des bases de données réelles et synthétiques montrent que l’approche apprentissage-combinaison proposée a atteint le taux le plus élevé de précision en comparaison avec d’autres techniques d’apprentissage incrémental à partir de blocs de données successives. En particulier, le système a démontré qu’il pouvait maintenir un plus haut taux de précision que celui d’un système basé sur un seul MMC entraîné selon le mode batch (utilisant tous les blocs de données cumulatifs) ou qui adapte les paramètres du MMC selon la méthode incrémentale proposée (utilisant des blocs de données successifs). De même, la précision du système proposé a surpassé celle des techniques basées sur les fonctions de fusion classiques tel que le vote majoritaire combinant les décisions des MMCs entraînés sur les anciens et les nouveaux blocs de données. Les techniques de sélection d’ensembles du système proposé sont capables de choisir un ensemble compact, en sélectionnant les MMCs générés, les plus précis et les plus diversifiés, tout en conservant ou en améliorant la précision du système. La technique d’élimination des modèles empêche l’augmentation de la taille du pool avec le temps. Ceci permet de réduire l’espace de stockage des MMCs et le coût computationnel des techniques de sélection, sans compromettre la performance globale du système. Les techniques proposées sont générales et peuvent être utilisées dans diverses applications pratiques qui nécessitent l’adaptation aux nouvelles données des systèmes basés sur les MMCs. Qui plus est, les techniques de combinaison booléennes proposées sont capables de combiner les réponses des classificateurs binaires ou probabilistes pour des problèmes à une ou deux classes. Ceci inclut la combinaison du même type de classificateurs entraînés sur différentes données ou caractéristiques ou selon différents paramètres, et la combinaison de différents classificateurs entraînés sur la même de données. En particulier, ces techniques peuvent être efficaces dans des applications où les données d’apprentissage sont limitées et les données de test sont non équilibrées.

Type de document:	Mémoire ou thèse (Thèse de doctorat électronique)
Renseignements supplémentaires:	"Manuscript-based thesis presented to École de technologie supérieure in partial fulfillment of the requirements for the degree of doctor of philosophy". Bibliogr. : f. [291]-312.
Mots-clés libres:	Systèmes de détection d'intrusion (Sécurité informatique). Systèmes adaptatifs. Apprentissage sur le Web. Modèles de Markov cachés. Courbes ROC. Anomalie, Apprentissage, Booléen, Classificateur, Combinaison, Ensemble, Fusion, Incrémental, Information, Caractéristique de fonctionnement du récepteur.
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Granger, Éric
Codirecteur:	Codirecteur Sabourin, Robert
Programme:	Doctorat en génie > Génie
Date de dépôt:	23 sept. 2011 20:07
Dernière modification:	23 févr. 2017 21:34
URI:	https://espace.etsmtl.ca/id/eprint/910

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt