Early Failure Prediction in Software Programs: Dimensionality Reduction Kernel

Abstract

The aim of this paper is to build an online failure prediction classifier for monitoring the behavior of programs. The classifier predicts the termination state of the program execution paths as failing or passing. This could be achieved by mapping each execution path as a vector into a feature space whose dimensions represent common sub-paths amongst failing and passing execution paths. The main contribution of this paper is to treat the failure prediction problem as a classification task of execution paths in a customized feature space. The main dilemma is the size and the number of space dimensions, affecting the speed of the classifier. The size of the dimensions could be reduced by shortening the length of the common sub-paths, used as the space dimensions. The length of common sub-paths is affected by repeated patterns in program executions. Replacing the consecutively repeated patterns with only a single iteration in execution paths, reduces the size of the common sub-paths. The number of dimensions could be reduced by removing dimensions which have projection onto others. This paper proposes two kernels which measure similarity amongst execution paths in an implicit feature space with reduced dimensionality. Our experiments demonstrate a significant reduction in time overhead of the failure prediction classifier while preserving accuracy.