ASSESSING INVARIANT MINING TECHNIQUES FOR CLOUD-BASED UTILITY COMPUTING SYSTEMS
ABSTRACT
Likely system invariants model properties that hold in operating conditions of a computing system. Invariants may be minedoffline from training datasets, or inferred during execution. Scientific work has shown that invariants’ mining techniques support severalactivities, including capacity planning and detection of failures, anomalies and violations of Service Level Agreements. However theirpractical application by operation engineers is still a challenge. We aim to fill this gap through an empirical analysis of three majortechniques for mining invariants in cloud-based utility computing systems: clustering, association rules, and decision list. Theexperiments use independent datasets from real-world systems: a Google cluster, whose traces are publicly available, and aSoftware-as-a-Service platform used by various companies worldwide. We assess the techniques in two invariants’ applications,namely executions characterization and anomaly detection, using the metrics of coverage, recall and precision. A sensitivity analysis isperformed. Experimental results allow inferring practical usage implications, showing that relatively few invariants characterize themajority of operating conditions, that precision and recall may drop significantly when trying to achieve a large coverage, and thattechniques exhibit similar precision, though the supervised one a higher recall. Finally, we propose a general heuristic for selectinglikely invariants from a dataset.
EXISTING SYSTEM:
Program invariants were introduced by Ernst et al., who presentedtechniques for inferring likely invariants from program executiontraces. Likely program invariants are a valuable support forseveral software engineering activities, including selection oftest inputs, discovery of interface specifications, testingcompatibility of COTS components, enforcement of relationaldatabase schema constraints System invariants have been shown by several authors tobe effective for modeling system dynamics and for detectinganomalous behaviors. Jiang et al. introduced the concept offlow intensity in transactional systems, whose behavior dependson user requests. They presented an approach for modeling therelationships between the flow intensities, and demonstrated experimentallythat flow intensity invariants do exist for distributedtransaction system. In they used the technique for detectingfaults like memory leaks, missing files and null calls.Sharma et al described positive experiences in a variety ofIT systems with the SIAT product built around the flow intensitymining algorithms, used 24×7 for detecting invariants and locatingfaults as well as for capacity planning; they reported that theviolation detection can be performed in seconds, after a trainingin the order of minutes
PROPOSED SYSTEM:
We explore the use of the techniques for two typical applicationsof invariant-based analysis, namely executions characteriza-tion and anomaly detection. We assess them based on the widelyused metrics coverage, precision and recall. A sensitivity analysisis performed to carefully explore the invariants returned by eachtechnique under different settings of the mining algorithms.The key findings of the study are:_ The considered techniques provide a valuable support forcharacterizing executions and detecting anomalies in anautomated way. For the SaaS cloud platform in particular,using the mined invariants it was possible to providea valuable result to the service operation team of theIT company, spotting true anomalies for a number oftransactions out of the seven month’s of operation data,which were indeed missing and went unnoticed.
CONCLUSIONS
LIKELY SYSTEM INVARIANTS can be mined for a variety ofservice computing systems, including cloud systems, webservice infrastructures, datacenters, enterprise systems, IT servicesand utility computing systems, network services, distributed systems.They represent operational abstractions of normal systemdynamics. The identification and the analysis of their violationssupport a range of operational activities, such as runtime anomalydetection, post mortem troubleshooting, capacity planning. In thiswork we have used two real-world datasets – the publicly availableGoogle datacenter dataset and a dataset of a commercial SaaSutility computing platform – for assessing and comparing threetechniques for invariant mining. Analysis and comparison wasbased on the common metrics coverage, recall and precision.The results provide insights into advantages and limitationsof each technique, and practical suggestions to practitioners toestablish the configuration of the mining algorithms and to selectthe number of invariants. The high-level findings are the following.A relatively small number of invariants allows to reach a relativelyhigh coverage, i.e. they characterize the majority of executions.A small increase of the coverage of correct executions mayproduce a significant drop of recall and precision. The techniquesexhibit similar precision, but the decision list supervised techniqueoutperforms the unsupervised ones in recall. Finally, we presenteda general heuristic for selecting a set of likely invariants from adataset. All these results aim to fill the gap between past scientificstudies and the concrete usage of likely system invariants byoperations engineers.
REFERENCES
[1] M. D. Ernst, J. Cockrell, W. G. Griswold, and D. Notkin, “DynamicallyDiscovering Likely Program Invariants to Support Program Evolution,”IEEE Trans. on Software Engineering, vol. 27, pp. 99–123, 2001.
[2] C. Pacheco and M. D. Ernst, “Eclat: Automatic Generation and Classificationof Test Inputs,” in Proc. 19th European Conference on ObjectOrientedProgramming (ECOOP), pp. 504–527, Springer, 2005.
[3] C. Csallner and Y. Smaragdakis, “Dynamically discovering likely interfacespecifications,” in Proc. 28th Int. Conference on Software Engineering(ICSE), pp. 861–864, ACM, 2006.[4] L. Mariani, S. Papagiannakis, and M. Pezzè, “Compatibility and regressiontesting of COTS-component-based software,” in Proc. 29th Int.Conference on Software Engineering (ICSE), ACM, 2007.
[5] J. Cobb, J. A. Jones, G. M. Kapfhammer, and M. J. Harrold, “DynamicInvariant Detection for Relational Databases,” in Proc. 9th Int. Workshopon Dynamic Analysis, pp. 12–17, ACM, 2011.
[6] G. Jiang, H. Chen, and K. Yoshihira, “Discovering likely invariantsof distributed transaction systems for autonomic system management,”Cluster Computing, vol. 9, pp. 385–399, 2006.
[7] H. Chen, H. Cheng, G. Jiang, and K. Yoshihira, “Invariants Based FailureDiagnosis in Distributed Computing Systems,” in Proc. 29th IEEE Int.Symp. on Reliable Distributed System (SRDS), pp. 160–166, IEEE, 2010.
[8] A. B. Sharma, H. Chen, M. Ding, K. Yoshihira, and G. Jiang, “Faultdetection and localization in distributed systems using invariant relationships,”in Proc. 43rd IEEE/IFIP Int. Conference on Dependable Systemsand Networks (DSN), pp. 1–8, IEEE, 2013.
[9] J.-G. Lou, Q. Fu, S. Yang, Y. Xu, and J. Li, “Mining invariants fromconsole logs for system problem detection,” in Proc. USENIX ATC, 2010.
[10] X. Miao, K. Liu, Y. He, D. Papadias, Q. Ma, and Y. Liu, “Agnosticdiagnosis: Discovering silent failures in wireless sensor networks,” IEEETrans. on Wireless Communications, vol. 12, no. 12, pp. 6067–6075,2013.