Concurrent Bug Detection Using Invariant Analysis

  • Authors

    • Bidush Kumar Sahoo
    • Mitrabinda Ray
    2018-06-25
    https://doi.org/10.14419/ijet.v7i3.4.14666
  • Dynamic Invariant, Concurrent Bugs, Static Call Graph, Redundant Invariant, Invariant Analysis.

  • 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.

     

     

  • References

    1. [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.

      [12] http://my.oschina.net/sharkbobo/blog/270238.

      [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.

      [21] https://github.com/gousiosg/java-callgraph

  • Downloads

  • How to Cite

    Kumar Sahoo, B., & Ray, M. (2018). Concurrent Bug Detection Using Invariant Analysis. International Journal of Engineering & Technology, 7(3.4), 6-12. https://doi.org/10.14419/ijet.v7i3.4.14666