<div>
	Improvement and comparison the performance of fuzzing testing algorithms for applications in Google Thread Sanitizer</div>

Oleg V. Doronin

2022 , VOLUME 22, NUMBER 4 ( July-August )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

doi: 10.17586/2226-1494-2022-22-4-734-741

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

O. V. Doronin

Read the full article

Article in English

For citation:

Doronin O.V. Improvement and comparison the performance of fuzzing testing algorithms for applications in Google Thread Sanitizer. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2022, vol. 22, no. 4, pp. 734–741 (in Russian). doi: 10.17586/2226-1494-2022-22-4-734-741

Abstract

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.

Keywords: error search tools, multithreading, fuzzing testing, scheduling algorithms, compilers

Acknowledgements. Personal thanks to Andrey Mikhailovich Dergachev for the support and motivation in writing the work

References

Stroustrup B. The C++ Programming Language. Boston, MA, USA, Addison-Wesley Longman Publishing Co., Inc., 2000, 1019 p.
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
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
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
Dechev D., Pirkelbauer P., Stroustrup B. Understanding and effectively preventing the ABA problem in descriptor-based lock-free designs. Proc. of the 13^th 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
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
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
Sutton M., Greene A., Armini P. Fuzzing: Brute Force Vulnerability Discovery. Pearson Education, 2007, 576 p.
Clarke E., Grumberg O., Peled D. Model Checking. MIT Press, 1999, 314 p.
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.
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
Garcia F., Fernandez J. Posix thread libraries. Linux Journal, 2000, vol. 2000, no. 70, pp. 36.
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.
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.
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)

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License