Concurrent Bug Detection Using Invariant Analysis

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    In concurrent programs, bug detection is a tedious job due to non-determinism and multiple thread control. The bug detection is done by checking the interleaving of threads which is not available in operational phases. So, static analysis is one of the preferred approaches for detection of concurrent bug. Invariant based testing technique is one approach of static analysis used for detecting the concurrent bugs. In this paper, we discuss an invariant based testing approach using three steps: (i) the invariants of a given concurrent program are generated using Daikon tool. (ii) The bad invariants are removed by using the static call graph of the source code, where the static call graph is generated by the javacg tool. (iii) The reduced invariant set is obtained by eliminating the bad and redundant invariants which is used for testcase generation. Using the reduced invariant set, we generate the testcases that are used to find the various concurrent bugs such as Deadlock, Atomicity violation and Bad composition. We conducted an experiment on a well-known concurrent program called the Dining Philosopher Problem. The experimental results show that, the testcases obtained from the reduced invariant set is able to detect more types and no. of concurrent bugs than the existing approach on invariant based testing.



  • Keywords

    Dynamic Invariant, Concurrent Bugs, Static Call Graph, Redundant Invariant, Invariant Analysis.

  • References

      [1] V. Kahlon and C. Wang, “Universal Causality Graphs: A precise happens-before model for detecting bugs in concurrent programs”, (2010) International Conference on Computer Aided Verification, pp. 434–449.

      [2] Wang, R., Ding, Z., Gui, N., & Liu, Y., “Detecting Bugs of Concurrent Programs with Program Invariants”, (2017) IEEE Transactions on Reliability, 66(2), pp. 425-439.

      [3] Ernst, M. D., Perkins, J. H., Guo, P. J., McCamant, S., Pacheco, C., Tschantz, M. S., & Xiao, C., “The Daikon system for dynamic detection of likely invariants”, (2007) Science of Computer Programming, 69(1-3), pp. 35-45.

      [4] Gonzalez, A., “Automatic error detection techniques based on dynamic invariants”, (2007) (Doctoral dissertation, MS thesis, Delft University of Technology, The Netherlands).

      [5] Isaratham, W., “Equivalence Partitioning as a Basis for Dynamic Conditional Invariant Detection”, (2015) (Doctoral dissertation, National University of Ireland Maynooth).

      [6] Kusano, M., Chattopadhyay, A., & Wang, C., “Dynamic generation of likely invariants for multithreaded programs”, (2015) In Software Engineering (ICSE), IEEE/ACM 37th IEEE International Conference, Vol. 1, pp. 835-846.

      [7] Zaharieva-Stojanovski, M., & Huisman, M., “Verifying class invariants in concurrent programs”, (2014) In International Conference on Fundamental Approaches to Software Engineering, Springer, pp. 230-245.

      [8] Ellsworth, D., “Improving Dynamic Invariant Saliency with Static Dataflow Analysis”, (2013).

      [9] Nimmer, J. W., & Ernst, M. D., “Invariant inference for static checking: An empirical evaluation”, (2002) ACM SIGSOFT Software Engineering Notes, Vol. 27, Issue 6, pp. 11-20.

      [10] Bianchi, F., Margara, A., & Pezze, M., “A Survey of Recent Trends in Testing Concurrent Software Systems”, (2017) IEEE Transactions on Software Engineering.

      [11] Betts, A., Chong, N., Donaldson, A., Deligiannis, P., & Ketema, J., “Implementing and evaluating candidate-based invariant generation”, (2017) IEEE Transactions on Software Engineering.


      [13] Wong, W. E., Gao, R., Li, Y., Abreu, R., & Wotawa, F., “A survey on software fault localization”, (2016) IEEE Transactions on Software Engineering, Vol. 42, Issue 8, pp. 707-740.

      [14] Hong, S., Staats, M., Ahn, J., Kim, M., & Rothermel, G., “The impact of concurrent coverage metrics on testing effectiveness”, (2013) In Software Testing, Verification and Validation (ICST), 2013 IEEE Sixth International Conference, pp. 232-241.

      [15] Chattopadhyay, Arijit., "Dynamic Invariant Generation for Concurrent Programs", (2014) PhD diss., Virginia Tech.

      [16] Park, Sangmin, Richard W. Vuduc, and Mary Jean Harrold. "Falcon: fault localization in concurrent programs", (2010) In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering, Volume 1, pp. 245-254.

      [17] Auer, A., Dingel, J., & Rudie, K., “Concurrency control generation for dynamic threads using discrete-event systems”, (2014) Science of Computer Programming, Vol. 82, pp. 22-43.

      [18] Lu, S., Tucek, J., Qin, F., & Zhou, Y., “AVIO: detecting atomicity violations via access interleaving invariants”, (2006) In ACM SIGOPS Operating Systems Review, Vol. 40, No. 5, pp. 37-48.

      [19] Zhang, W., Lim, J., Olichandran, R., Scherpelz, J., Jin, G., Lu, S., & Reps, T., “ConSeq: detecting concurrency bugs through sequential errors”, (2011) In ACM Sigplan Notices, Vol. 46, No. 3, pp. 251-264.

      [20] Farzan, A., Holzer, A., Razavi, N., & Veith, H., “Con2colic testing”, (2013) In Proceedings of the 9th Joint Meeting on Foundations of Software Engineering, pp. 37-47.





Article ID: 14666
DOI: 10.14419/ijet.v7i3.4.14666

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.