Improvement and comparison the performance of fuzzing testing algorithms for applications in Google Thread Sanitizer

It is difficult to imagine modern information systems without the use of multithreading. The use of multithreading can both improve the performance of the system as in whole so as slow down the execution of multithreaded applications due to the occurrence of multithreaded programming errors. To find such errors in C/C++ languages, there exists a Google Thread Sanitizer compiler module. The order of execution of threads can change every time the program is started for execution and can affect the appearance of such errors. To repeatedly change the order of execution of threads during the execution of the program, Google Thread Sanitizer has a fuzzing testing module that allows you to increase the probability of finding errors. But all the thread scheduling algorithms in this module are presented in the form of sequential execution of threads which can lead to a significant slowdown in Google Thread Sanitizer as well as can affect the testing of applications that depends on timers (waiting for network events, deadline for operations, ...). To speed up the work of fuzzing schedulers, a method for parallelizing independent transitions is proposed. From the point of view of multithreaded programming errors, it is only important to change the shared state between threads, and local calculations do not affect the reproduction of multithreaded errors. The changes of shared states themselves occur at synchronization points (places in the code where threads are switched according to the principle of cooperative multitasking). The method suggests ordering only the change of shared states at synchronization points, and performing local calculations in parallel, due to which parallelization is achieved. For the analysis of theoretical complexity of the algorithm, the method of combinatorial counting is used. A new approach to the organization of fuzzing testing based on the method of parallelization of independent transitions is proposed the implementation of which, according to theoretical and practical estimates, shows a noticeable acceleration of the work of fuzzing schedulers. According to the results of the experiment, it was revealed that for the algorithm of iterating through all execution variants, the acceleration of execution reaches 1.25 times for two threads. For an arbitrary number of threads, an estimate is presented in the form of a formula. The proposed approach allows fuzzing tests to cover multithreaded applications for which execution time is important — applications with reference to timers which improve the quality of the software.

1. Stroustrup B. The C++ Programming Language. Boston, MA, USA, Addison-Wesley Longman Publishing Co., Inc., 2000, 1019 p.

2. Serebryany K., Iskhodzhanov T. ThreadSanitizer — Data race detection in practice. ACM International Conference Proceeding Series, 2009, pp. 62–71. https://doi.org/10.1145/1791194.1791203

3. Netzer R.H.B., Miller B.P. What are race conditions?: Some issues and formalizations. ACM Letters on Programming Languages and Systems (LOPLAS), 1992, vol. 1, no. 1, pp. 74–88. https://doi.org/10.1145/130616.130623

4. Banerjee U., Bliss B., Ma Z., Petersen P. A theory of data race detection. Proc. of the 2006 Workshop on Parallel and Distributed Systems: Testing and Debugging (PADTAD), 2006, pp. 69–78. https://doi.org/10.1145/1147403.1147416

5. Dechev D., Pirkelbauer P., Stroustrup B. Understanding and effectively preventing the ABA problem in descriptor-based lock-free designs. Proc. of the 13th IEEE International Symposium on Object/ Component/Service-Oriented Real-Time Distributed Computing (ISORC). V. 1, 2010, pp. 185–192. https://doi.org/10.1109/ISORC.2010.10

6. Anderson J., Ramamurthy S., Jeffay K. Real-time computing with lock-free shared objects. ACM Transactions on Computer Systems, 1997, vol. 15 , no. 2, pp. 134–165. https://doi.org/10.1145/253145.253159

7. Harris T.L., Fraser K., Pratt I.A. A practical multi-word compare-and-swap operation. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2002, vol. 2508, pp. 265–279. https://doi.org/10.1007/3-540-36108-1_18

8. Sutton M., Greene A., Armini P. Fuzzing: Brute Force Vulnerability Discovery. Pearson Education, 2007, 576 p.

9. Clarke E., Grumberg O., Peled D. Model Checking. MIT Press, 1999, 314 p.

10. Meyers S., Alexandrescu A. C++ and the Perils of Double-Checked Locking: Part I. Dr. Dobb’s Journal, 2004, vol. 29, no. 7, pp. 46–49.

11. Gluck P., Holzmann G. Using SPIN model checking for flight software verification. IEEE Aerospace Conference Proceedings, 2002, vol. 1, pp. 105–113. https://doi.org/10.1109/AERO.2002.1036832

12. Garcia F., Fernandez J. Posix thread libraries. Linux Journal, 2000, vol. 2000, no. 70, pp. 36.

13. Doronin O., Dergun K., Dergachev A., Ilina A. Fuzz testing of multithreaded applications based on waiting. CEUR Workshop Proceedings, 2020, vol. 2590, pp. 1–8.

14. Doronin O., Dergun K., Dergachev A. Automatic fuzzy-scheduling of threads in Google Thread Sanitizer to detect errors in multithreaded code. CEUR Workshop Proceedings, 2019, vol. 2344, pp. 1–12.

15. Dergun K.I., Doronin O.V. Fuzzing testing of fine-grained algorithms. Abstracts collection of VIII Young Scientists Congress. St. Petersburg, ITMO University, 2019. (in Russian)