Using fault screeners for software error detection. (English) Zbl 1211.68105

Abreu, Rui; González, Alberto; Zoeteweij, Peter; Van Gemund, Arjan J. C.

Maciaszek, Leszek A. (ed.) et al., Evaluation of novel approaches to software engineering. 3rd and 4th international conference, ENASE 2008/2009, Funchal, Madeira, Portugal, May 4–7, 2008, Milan, Italy, May 9–10, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-14818-7/pbk). Communications in Computer and Information Science 69, 60-74 (2010).

Summary: Fault screeners are simple software (or hardware) constructs that detect variable value errors based on unary invariant checking. In this paper, we evaluate and compare the performance of three low-cost screeners (Bloom filter, bitmask, and range screener) that can be automatically integrated within a program, and trained during the testing phase. While the Bloom filter has the capacity of retaining virtually all variable values associated with proper program execution, this property comes with a much higher false positive rate per unit of training effort, compared to the more simple range and bitmask screeners, that compresses all value information in terms of a single lower and upper bound or a bitmask, respectively. We present a novel analytic model that predicts the false positive and false negative rate for ideal (i.e., screeners that store each individual value during training) and simple (e.g., range and bitmask) screeners. We show that the model agrees with our empirical findings. Furthermore, we describe an application of all screeners, where the screener’s error detection output is used as input to a fault localization process that provides automatic feedback on the location of residual program defects during deployment in the field.
For the entire collection see [Zbl 1201.68007].

MSC:

68N99

Theory of software

Keywords:

error detection; program invariants; analytic model; fault localization; program spectra

Software:

LLVM; Daikon; IODINE

References:

[1]	Abreu, R., González, A., Zoeteweij, P., van Gemund, A.J.C.: Automatic software fault localization using generic program invariants. In: Proc. SAC 2008. ACM Press, New York (2008)
[2]	Abreu, R., Zoeteweij, P., van Gemund, A.J.C.: An evaluation of similarity coefficients for software fault localization. In: Proc. PRDC 2006. IEEE CS, Los Alamitos (2006)
[3]	Abreu, R., Zoeteweij, P., van Gemund, A.J.C.: On the accuracy of spectrum-based fault localization. In: Proc. TAIC PART 2007. IEEE CS, Los Alamitos (2007)
[4]	Bloom, B.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970) · Zbl 0195.47003
[5]	Cleve, H., Zeller, A.: Locating causes of program failures. In: Proc. ICSE 2005. IEEE CS, Los Alamitos (2005)
[6]	Dallmeier, V., Lindig, C., Zeller, A.: Lightweight defect localization for Java. In: Black, A.P. (ed.) ECOOP 2005. LNCS, vol. 3586, pp. 528–550. Springer, Heidelberg (2005)
[7]	David, H.A.: Order Statistics. John Wiley & Sons, Chichester (1970) · Zbl 0223.62057
[8]	Ernst, M., Cockrell, J., Griswold, W., Notkin, D.: Dynamically discovering likely program invariants to support program evolution. In: Proc. ICSE 1999. IEEE CS, Los Alamitos (1999)
[9]	Ernst, M., Perkins, J., Guo, P., McCamant, S., Pacheco, C., Tschantz, M., Xiao, C.: The Daikon system for dynamic detection of likely invariants. In: Science of Computer Programming (2007) · Zbl 1161.68390
[10]	Gautama, H., van Gemund, A.: Low-cost static performance prediction of parallel stochastic task compositions. IEEE Trans. Parallel Distrib. Syst. 17(1), 78–91 (2006) · Zbl 05106480
[11]	González, A.: Automatic error detection techniques based on dynamic invariants. Master’s thesis, Delft University of Technology and Universidad de Valladolid, Delft (2007)
[12]	Gumbel, E.: Statistical theory of extreme values (main results). In: Sarhan, A., Greenberg, B. (eds.) Contributions to Order Statistics. John Wiley & Sons, Chichester (1962)
[13]	Hangal, S., Chandra, N., Narayanan, S., Chakravorty, S.: IODINE: A tool to automatically infer dynamic invariants for hardware designs. In: Proc. DAC 2005. ACM Press, New York (2005)
[14]	Hangal, S., Lam, M.: Tracking down software bugs using automatic anomaly detection. In: Proc. ICSE 2002. IEEE CS, Los Alamitos (2002)
[15]	Harrold, M., Rothermel, G., Wu, R., Yi, L.: An empirical investigation of program spectra. ACM SIGPLAN Notices 33(7) (1998)
[16]	Hutchins, M., Foster, H., Goradia, T., Ostrand, T.: Experiments of the effectiveness of dataflow- and controlflow-based test adequacy criteria. In: Proc. ICSE 1994. IEEE CS, Los Alamitos (1994)
[17]	Jain, A., Dubes, R.: Algorithms for clustering data. Prentice-Hall, Inc., Englewood Cliffs (1988) · Zbl 0665.62061
[18]	Jones, J., Harrold, M.: Empirical evaluation of the tarantula automatic fault-localization technique. In: Proc. ASE 2005. ACM Press, New York (2005)
[19]	Kephart, J., Chess, D.: The vision of autonomic computing. Computer 36 (2003) · Zbl 05087044
[20]	Lattner, C., Adve, V.: LLVM: A compilation framework for lifelong program analysis & transformation. In: Proc. CGO 2004. ACM Press, New York (2004)
[21]	Liu, C., Fei, L., Yan, X., Han, J., Midkiff, S.: Statistical debugging: A hypothesis testing-based approach. IEEE TSE 32(10), 831–848 (2006)
[22]	Lorenzoli, D., Mariani, L., Pezzè, M.: Automatic generation of software behavioral models. In: ICSE 2008. ACM Press, New York (2008)
[23]	Menzies, T., Owen, D., Richardson, J.: The strangest thing about software. Computer 40(1), 54–60 (2007) · Zbl 05331422
[24]	Pattabiraman, K., Kalbarczyk, Z., Iyer, R.K.: Application-based metrics for strategic placement of detectors. In: Proc. PRDC 2005. IEEE CS, Los Alamitos (2005)
[25]	Patterson, D., Brown, A., Broadwell, P., Candea, G., Chen, M., Cutler, J., Enriquez, P., Fox, A., Kiciman, E., Merzbacher, M., Oppenheimer, D., Sastry, N., Tetzlaff, W., Traupman, J., Treuhaft, N.: Recovery Oriented Computing (ROC): Motivation, definition, techniques, and case studies. Technical Report UCB/CSD-02-1175, U.C. Berkeley (2002)
[26]	Pytlik, B., Renieris, M., Krishnamurthi, S., Reiss, S.: Automated fault localization using potential invariants. In: Proc. AADEBUG 2003. ACM Press, New York (2003)
[27]	Racunas, P., Constantinides, K., Manne, S., Mukherjee, S.: Perturbation-based fault screening. In: Proc. HPCA 2007. IEEE CS, Los Alamitos (2007)
[28]	Renieris, M., Reiss, S.: Fault localization with nearest neighbor queries. In: Proc. ASE 2003, Montreal, Canada. IEEE CS, Los Alamitos (2003)
[29]	Yang, J., Evans, D.: Automatically inferring temporal properties for program evolution. In: Proc. ISSRE 2004. IEEE CS, Los Alamitos (2004)
[30]	Zhang, X., He, H., Gupta, N., Gupta, R.: Experimental evaluation of using dynamic slices for fault location. In: Proc. AADEBUG 2005. ACM Press, New York (2005)