Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this paper, we evaluate the performance of ten well-known evolutionary and non-evolutionary rule learning algorithms. The comparative study is performed on a real-world classification problem of detecting malicious executables. The executable dataset, used in this study, consists of 189 attributes which are statically extracted from the executables of Microsoft Windows operating system. In our study, we compare the performance of rule learning algorithms with respect to four metrics: (1) classification accuracy, (2) the number of rules in the developed rule set, (3) the comprehensibility of the generated rules, and (4) the processing overhead of the rule learning process. The results of our comparative study suggest that evolutionary rule learning classifiers cannot be deployed in real-world malware detection systems.

REFERENCES

• 1: John H. Holland , Lashon B. Booker , Marco Colombetti , Marco Dorigo , David E. Goldberg , Stephanie Forrest , Rick L. Riolo , Robert E. Smith , Pier Luca Lanzi , Wolfgang Stolzmann , Stewart W. Wilson, What Is a Learning Classifier System?, Learning Classifier Systems, From Foundations to Applications, p.3-32, January 2000
• 2: Stewart W. Wilson, Classifier fitness based on accuracy, Evolutionary Computation, v.3 n.2, p.149-175, Summer 1995 [doi>10.1162/evco.1995.3.2.149]
• 3: Ester Bernadó-Mansilla , Josep M. Garrell-Guiu, Accuracy-based learning classifier systems: models, analysis and applications to classification tasks, Evolutionary Computation, v.11 n.3, p.209-238, Fall 2003 [doi>10.1162/106365603322365289]
• 4: J. Bacardit, J.M. Garrell, "Evolving Multiple Discretizations with Adaptive Intervals for a Pittsburgh Rule-Based Learning Classifier System", Genetic and Evolutionary Computation Conference (GECCO), Volume 2724 of Lecture Notes in Computer Science, pp. 1818--1831, Springer, USA, 2003.
• 5: J. Bacardit, J.M. Garrell, "Bloat control and generalization pressure using the minimum description length principle for a Pittsburgh approach Learning Classifier System", International Workshop on Learning Classifier Systems (IWLCS), Volume 4399 of Lecture Notes in Artificial Intelligence, pp. 59--79, Springer, UK, 2007.
• 6: A. Gonzalez, R. Perez, "SLAVE: A genetic learning system based on an iterative approach", IEEE Transactions on Fuzzy Systems, 7(2), pp. 176--191, 1999.
• 7: W.W. Cohen, "Fast Effective Rule Induction", 12th International Conference on Machine Learning (ICML), pp. 115--123, Morgan Kaufmann, USA, 1995.
• 8: William W. Cohen , Yoram Singer, A simple, fast, and effective rule learner, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.335-342, July 18-22, 1999, Orlando, Florida, United States
• 9: Eibe Frank , Ian H. Witten, Generating Accurate Rule Sets Without Global Optimization, Proceedings of the Fifteenth International Conference on Machine Learning, p.144-151, July 24-27, 1998
• 10: J.R. Quinlan, "MDL and Categorical Theories (Continued)", 12th International Conference on Machine Learning (ICML), pp. 464--470, Morgan Kaufmann, USA, 1995.
• 11: Grzegorz Góra , Arkadiusz Wojna, RIONA: A New Classification System Combining Rule Induction and Instance-Based Learning, Fundamenta Informaticae, v.51 n.4, p.369-390, March 2002
• 12: A.O. Puig, J. Casillas, E.B. Mansilla, "Genetic-based machine learning systems are competitive for pattern recognition", Evolutioanry Intelligence, 1(3), pp. 209--232, Springer, 2008.
• 13: J. Bacardit, M.V. Butz, "Data Mining in Learning Classifier Systems: Comparing XCS with GAssist", International Workshop on Learning Classifier Systems (IWLCS), Volume 4399 of Lecture Notes in Artificial Intelligence, pp. 282--290, Springer, UK, 2007.
• 14: Ester Bernadó i Mansilla , Xavier Llorà , Josep Maria Garrell i Guiu, XCS and GALE: A Comparative Study of Two Learning Classifier Systems on Data Mining, Revised Papers from the 4th International Workshop on Advances in Learning Classifier Systems, p.115-132, July 07-08, 2001
• 15: Faten Kharbat , Larry Bull , Mohammed Odeh, Mining breast cancer data with XCS, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277362]
• 16: Albert Orriols-Puig , Ester Bernadó-Mansilla, Evolutionary rule-based systems for imbalanced data sets, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.13 n.3, p.213-225, October 2008 [doi>10.1007/s00500-008-0319-7]
• 17: Kamran Shafi , Tim Kovacs , Hussein A. Abbass , Weiping Zhu, Intrusion detection with evolutionary learning classifier systems, Natural Computing: an international journal, v.8 n.1, p.3-27, March 2009 [doi>10.1007/s11047-007-9053-9]
• 18: K.C. Tan, Q. Yu, C.M. Heng, T.H. Lee, "Evolutionary computing for knowledge discovery in medical diagnosis", Artificial Intelligence in Medicine, 27(2), pp. 129--154, Elsevier, 2003.
• 19: Y. Gao, J.Z. Huang, H. Rong, D.Q. Gu, "LCSE: Learning Classifier System Ensemble for Incremental Medical Instances", International Workshop on Learning Classifier Systems (IWLCS), Volume 4399 of Lecture Notes in Computer Science, pp. 93--103, Springer, UK, 2007.
• 20: J. Alcalá-Fdez , L. Sánchez , S. García , M. J. del Jesus , S. Ventura , J. M. Garrell , J. Otero , C. Romero , J. Bacardit , V. M. Rivas , J. C. Fernández , F. Herrera, KEEL: a software tool to assess evolutionary algorithms for data mining problems, Soft Computing - A Fusion of Foundations, Methodologies and Applications, v.13 n.3, p.307-318, October 2008 [doi>10.1007/s00500-008-0323-y]
• 21: C. Blake, E. Keogh, C. Merz, "UCI repository of machine learning databases", 1998, available at www.ics.uci.edu/mlearn/MLRepository.html.
• 22: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• 23: Stewart W. Wilson, Compact Rulesets from XCSI, Revised Papers from the 4th International Workshop on Advances in Learning Classifier Systems, p.197-210, July 07-08, 2001
• 24: P.W. Dixon, D.W. Corne, M.J. Oates, "A ruleset reduction algorithm for the XCSI Learning Classifier System", Volume 2661 of Lecture Notes in Computer Science, pp. 20--29, Springer, 2004.
• 25: Chunsheng Fu , Lawrence Davis, A Modified Classifier System Compaction Algorithm, Proceedings of the Genetic and Evolutionary Computation Conference, p.920-925, July 09-13, 2002
• 26: A.O. Puig, E.B. Mansilla, "Analysis of reduction algorithms for XCS classifier system", Recent Advances in Artificial Intelligence Research and Development, pp. 383--390, IOS Press, 2004.
• 27: Microsoft Portable Executable and Common Object File Format Specification, Windows Hardware Developer Central, Updated March 2008.
• 28: F-Secure Virus Description Database, available at http://www.f-secure.com/v-descs/.
• 29: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 30: VX Heavens Virus Collection, VX Heavens website, available at http://vx.netlux.org.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Invasive software (e.g., viruses, worms, Trojan horses)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction; Concept learning

General Terms:
Algorithms, Experimentation, Security

Keywords:
genetics based machine learning, learning classifier systems, malware detection