Menu
Publications
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Editor-in-Chief
Nikiforov
Vladimir O.
D.Sc., Prof.
Partners
doi: 10.17586/2226-1494-2020-20-2-243-248
TESTING OF MULTITHREADED APPLICATIONS WITH LOCKS ON NON-ATOMIC VARIABLES
Read the full article
';
Article in Russian
For citation:
Abstract
For citation:
Doronin O.V., Dergun K.I., Dergachev A.M., Ilina A.G., Gorlatch S.P. Testing of multithreaded applications with locks on non-atomic variables. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2020, vol. 20, no. 2, pp. 243–248 (in Russian). doi: 10.17586/2226-1494-2020-20-2-243-248
Abstract
Subject of Research. The paper presents the study of fuzz testing algorithm for “data race” type fault finding in multithreaded software. The algorithm is implemented in the Google TSan tool. The disadvantage of the studied algorithm is the inability to test software products which use non-atomic variables. At this, the use of such tool is excluded for testing of modern applications that implement joint access of program streams to data. We propose a new algorithm for fuzz testing of multithreaded applications and a method for its implementation in the fuzz testing module of the Google TSan tools. Method. Various combinations of the execution of program streams are the input data in the process of fuzz testing of multithreaded applications. The proposed method of fuzz testing for multithreaded software applications assumes that errors in multithreaded applications manifest themselves only at the threads switching points, also called synchronization points. The thread scheduler is implemented as simply as possible. Each thread is assigned with a status marker tracking its activity during the program running. A thread can be in an unknown state (until the first synchronization point), in a state of execution, in a state of waiting in a queue for execution, as well as in a state where the thread has spent its execution quantum but has not reached the synchronization point. Such thread state is automatically changed to the state of waiting at the synchronization point. Thread control is carried out using a separate program thread that monitors the status of all threads and exposes the corresponding marker to the threads that have spent the execution quantum. The error search mechanism is implemented in the software product at the compilation stage by specifying the appropriate options. Main Results. A new fuzz testing module has been integrated in the Google TSan tool, which finds “data race” errors in any multithreaded applications, both with synchronization of access to shared data and with shared access to data. Practical Relevance. Verification of multithreaded software with shared access to data, in particular case of applying non-atomic variables, is especially relevant for the heavily loaded scalable software systems.
Keywords: multithreading, data race, deadlock, error finding tools, fuzz testing
References
References
-
Gedich A.A., Zykov A.G., Lazdin A.V., Polyakov V.I. Search for procedure with the use of functional program transition graph to verify computational processes. Journal of Instrument Engineering, 2014, vol. 57, no. 4, pp. 64–68. (in Russian)
-
Dechev D., Pirkelbauer P., Stroustrup B. Understanding and effectively preventing the ABA problem in descriptor-based lock-free designs. Proc. 13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing (ISORC 2010), 2010, vol. 1, pp. 185–192. doi: 10.1109/ISORC.2010.10
-
Multi-Threaded Programming Terminology – 2018. Available at: https://www.bogotobogo.com/cplusplus/multithreaded.php (accessed: 18.01.2020).
-
Difficulties in concurrent programming. Available at: https://poznayka.org/s9887t1.html (accessed: 18.01.2020). (in Russian)
-
Race Condition vs. Data Race 2018. Available at: https://blog.regehr.org/archives/490 (accessed: 18.01.2020).
-
Serebryany K., Iskhodzhanov T. ThreadSanitizer - Data race detection in practice. ACM International Conference Proceeding Series, 2009, pp. 62–71. doi: 10.1145/1791194.1791203
-
Lukin M. Verification of parallel automata-based programs. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2014, vol. 14, no. 1(89), pp. 60–66. (in Russian)
-
Nikiforov V.V. Protocol for prevention of task deadlocks in real-time systems. Journal of Instrument Engineering, 2014, vol. 57, no 12, pp. 21–27. (in Russian)
-
Nikiforov V.V., Tyugashev A.A. Access to shared resources in real-time systems with varying tasks priorities. Journal of Instrument Engineering, 2016, vol. 59, no. 11, pp. 964–970. (in Russian). doi: 10.17586/0021-3454-2016-59-11-964-970
-
Triantafillou P. An approach to deadlock detection in multidatabases. Information Systems, 1997, vol. 22, no. 1, pp. 39–55. doi: 10.1016/S0306-4379(97)00003-3
-
Dergun K.I., Doronin O.V. Fuzzing testing of fine-grained algorithms. Proc. Conference of Young Scientists. Available at: https://kmu.itmo.ru/digests/article/1224 (accessed: 18.01.2020). (in Russian)
-
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.
-
ThreadSanitizer project: documentation, source code, dynamic annotations, unit tests. Available at: http://code.google.com/p/data-race-test (accessed: 18.01.2020).
-
Sutton M., Greene A., Amini P. Fuzzing: Brute Force Vulnerability Discovery. Pearson Education, 2007, 576 p.
-
Vallen A., Johansson V.Random testing with sanitizers to detect concurrency bugs in embedded avionics software. Available at: http://www.diva-portal.org/smash/record.jsf?pid=diva2%3A1269941&dswid=8217 (accessed: 18.01.2020).
