Int. J. Accounting, Auditing and Performance Evaluation, Vol. x, No. x, xxxx 1Software Fault Tree and Colored PetriNet Based Specification, Design andImplementation of Agent-Based IntrusionDetection SystemsGuy Helmer∗, Johnny Wong†∗∗,Mark Slagell†, Vasant Honavar†,Les Miller†, Yanxin Wang,Xia Wang, Natalia StakhanovaDepartment of Computer Science,Iowa State University,Atanasoff Hall, Ames, Iowa 50011E-mail: {ghelmer,wong,slagell,honavar,lmiller}@cs.iastate.eduE-mail: {wangyx,jxiawang,ndubrov}@cs.iastate.edu∗G. Helmer is with Palisade Systems, Inc. His r e search was fundedin part by the Department of Defense, the Boeing Company in theform of the Boeing Dissertation Fellowship, and the Graduate Col-lege of Iowa State University.∗∗Corresponding author†Funded in part by the Department of Defense.Abstract: The integration of Software Fault Tree (SFT) which de-scribes intrusions and Colored Petri Nets (CPNs) which specifies design,is examined for an Intrusion Detection System (IDS). The IDS underdevelopment is a collection of mobile agents that detect, classify, andcorrelate system and network activities. Software Fault Trees ( SFTs),augmented with nodes that describe trust, temporal, and contextualrelationships, are used to describe intrusions. CPNs for intrusion detec-tion are built using CPN templates created from the augmented SFTs.Hierarchical CPNs are created to detect critical stages of intrusions.The agent-based implementation of the IDS is then constructed fromthe CPNs. Examples of intrusions and descriptions of the prototype im-plementation are used to demonstrate how the CPN approach has beenused in development of the IDS.The main contribution of this paper is an approach to systematicspecification, design, and implementation of an IDS. I nnovations include(1) using stages of intrusions to structure the specification and design ofthe IDS, (2) augmentation of SFT with trust, temporal, and contextualnodes to model intrusions, (3) algorithmic construction of CPNs fromaugmented SFT, and (4) generation of mobile agents from CPNs.Keywords: Intrusion detection system, mobile agents, software faulttree analysis, colored Petri netsCopyrightc 200x Inderscience Enterprises Ltd.2 G. Helmer, J. Wong, M. Slagell, V. Honavar, L. Miller et al.Reference to th is paper should be made as follows: Guy Helmer,Johnny Wong, Mark Slagell, Vasant Honavar, Les Miller, Yanxin Wang,Xia Wang, Natalia Stakhanova (xxxx) ‘Software Fault Tree and ColoredPetri Net Based Specification, Design and Implementation of Agent-Based Intrusion Detection Systems’, Int. Journal of Information andComputer Security, Vol. x, No. x, pp.xxx–xxx.Biographical Notes: Guy Helmer, received his Ph.D. in ComputerScience at Iowa State University and is the Chief Principal Architect atPalisade, Inc..Johnny Wong, Professor & Associate Chair in Computer Science De-partment at I owa S tate University.Mark Slagell, received his M.S. in Computer Science at I owa StateUniversity and is a system administrator at Vet. Med. College at IowaState University.Vasant Honavar, Professor in Computer Science and Bioinformatics& Computational Biology at Iowa State University.Les Miller, Professor in Computer Science Department at Iowa StateUniversity.Yanxin Wang, received his Ph.D. in Computer Science at Iowa StateUniversity and is a software engineer at Microsoft.Xia Wang is currently a PhD candidate in Computer Science at IowaState University, Ames, Iowa.Natalia Stakhanova is currently a Ph.D candidate in Computer Sci-ence at Iowa State University, Ames, Iowa.1 IntroductionA secure computer system provides guarantees regarding the confidentiality, in-tegrity, and availability of its objects (such as data, processe s, or se rvices). However,systems genera lly contain design and implementatio n flaws that result in securityvulnerabilities. An intrusion takes pla c e when an attacker or group of attack-ers exploit security vulnerabilities and thus violate the confidentiality, integrity,or availability guarantees of a system or a network. Intrusion detection systems(IDSs) detect some set of intrusions and exe c ute some predetermined action whenan intrusion is detected.IDSs use audit information obtained from host systems and network s to de-termine whether violations of a system’s security policy are occurring or have oc-curred (Amoroso, 1999). Our Multi-Agents Intrusion Detection System (MAIDS)(Helmer, 2000; Helmer et al., 2002b, 20 03) uses mobile agents (Bradshaw, 1997) ina distributed system to obtain audit data, correlate e vents, and discover intrusions.Design and Implementation of Agent -Based Intrusion Detection Systems 3The MAIDS system co ns ists of (1) statio nary data cleaning agents that obtain in-formation from system logs, audit data, and operational statistics and convert theinformation into a common format, (2) low level a gents that monitor and classifyongoing activities, classify events, and pass on their information to mediators , and(3) data mining (Cabena et al., 1998) agents that use machine learning to acquirepredictive rules for intrusion detection from system logs and audit data.One of the challenges in designing an IDS involves defining exactly what dataelements s hould be c orrelated to determine whether an intrusion is taking place ina distributed environment. It is also difficult to determine what data elements arenecessary to discover intrusions. A model of intrusion detection is e ssentia l to de-scribe how the data sho uld flow through the s ystem, determine whether the systemwould b e able to detect intrusions, and suggest points at which countermeasurescould be implemented.Against this background, the paper presents a theoretical framework for model-ing the operation of intrusion detection systems such as MAIDS. We use SoftwareFault Trees (SFTs) to define intrusions and develop the requirements model for theIDS. The SFT models of intrusions are used to create Colored Petri Net (CPN)designs for the detectors in the IDS. The CPN detection model is then mappedinto a set of software mobile a gents that form the distributed intrusion detectionsystem. Finally, the SFT models provide test cases for the implementation.The SFT analysis (SFTA) approach applies safety engineering techniques tothe intrusion detection domain for developing IDS requirements. Each part ofthese development processes — SFTA, CPNs, and software agent implementation— is distinct, and each stage in the development