Concurrent Bug Detection Using Invariant Analysis

  • Authors

    • Bidush Kumar Sahoo
    • Mitrabinda Ray
    https://doi.org/10.14419/ijet.v7i3.4.14666

    Received date: June 26, 2018

    Accepted date: June 26, 2018

    Published date: June 25, 2018

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

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

  • 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 Con-current Programs with Program Invariants”, (2017) IEEE Transac-tions 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 de-tection of likely invariants”, (2007) Science of Computer Program-ming, 69(1-3), pp. 35-45.
    4. Gonzalez, A., “Automatic error detection techniques based on dy-namic 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, Na-tional 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 Confer-ence, Vol. 1, pp. 835-846.
    7. Zaharieva-Stojanovski, M., & Huisman, M., “Verifying class invari-ants 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 Soft-ware 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 Transac-tions on Software Engineering.
    11. Betts, A., Chong, N., Donaldson, A., Deligiannis, P., & Ketema, J., “Implementing and evaluating candidate-based invariant genera-tion”, (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 Soft-ware Engineering, Vol. 42, Issue 8, pp. 707-740.
    14. Hong, S., Staats, M., Ahn, J., Kim, M., & Rothermel, G., “The im-pact 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 Concur-rent Programs", (2014) PhD diss., Virginia Tech.
    16. Park, Sangmin, Richard W. Vuduc, and Mary Jean Harrold. "Fal-con: fault localization in concurrent programs", (2010) In Proceed-ings 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 SI-GOPS 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 and Technology, 7(3.4), 6-12. https://doi.org/10.14419/ijet.v7i3.4.14666