ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2022-22-4-734-741ntv-217Research ArticleКОМПЬЮТЕРНЫЕ СИСТЕМЫ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИCOMPUTER SCIENCEОрганизация фаззинг-тестирования многопоточных приложений на основе метода распараллеливания независимых переходовImprovement and comparison the performance of fuzzing testing algorithms for applications in Google Thread Sanitizerhttps://orcid.org/0000-0003-4209-8440ДоронинО. В.DoroninO. V.

Доронин Олег Владимирович — аспирант

sc 57208322052

Санкт-Петербург, 197101

Oleg V. Doronin — PhD Student

sc 57208322052

Saint Petersburg, 197101

dorooleg@yandex.ruУниверситет ИТМОРоссияITMO UniversityRussian Federation202215122024224734741Copyright © Доронин О.В., 20242024Доронин О.В.Doronin O.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/217

Предмет исследования. Современные информационные системы сложно представить без использования многопоточности. Многопоточность может как повышать производительность системы в целом, так и замедлять выполнение приложений за счет возникновения ошибок многопоточного программирования. Для нахождения таких ошибок на языках С/C++ существует модуль компилятора Google Thread Sanitizer. Но порядок выполнения потоков может каждый раз меняться при запуске программы на выполнение и влиять на появление подобных ошибок. Для многократного изменения порядка выполнения потоков за время работы программы в Google Thread Sanitizer применен модуль фаззинг-тестирования, который повысил вероятность нахождения ошибок. Все алгоритмы планирования потоков в фаззинг-модуле предназначены для последовательного выполнения потоков, что приводит к значительному замедлению работы Google Thread Sanitizer. Также происходит влияние на тестирование приложений, которое зависит от асинхронных взаимодействий (ожидания сетевых событий, ограничения времени выполнения операций). Метод. Для ускорения работы фаззинг-планировщиков предложен метод распараллеливания независимых переходов. Ошибки многопоточного программирования возникают при изменении разделяемого состояния между потоками, при этом локальные вычисления не влияют на воспроизведение многопоточных ошибок. Изменение разделяемых состояний происходит в точках синхронизаций, где выполняется переключение потоков по принципу кооперативной многозадачности. Предложено осуществлять управление последовательностями выполнения потоков только при изменении разделяемых состояний в точках синхронизаций, а локальные вычисления выполнять параллельно. Данное условие позволило сократить время тестирования без снижения результативности обнаружения ошибок многопоточного программирования. Для анализа теоретической сложности алгоритма планирования применен метод комбинаторного подсчета. Основные результаты. Предложен новый подход организации фаззинг-тестирования на основе метода распараллеливания независимых переходов, реализация которого по теоретическим и практическим оценкам показывает заметное ускорение работы фаззинг-планировщиков. Результаты эксперимента показали, что для алгоритма перебора всех вариантов выполнения приложения ускорение выполнения достигает 1,25 раза для двух потоков. Представлено соотношение для оценки ускорения в случае произвольного числа потоков. Практическая значимость. Предложенный подход позволяет покрывать фаззинг-тестами многопоточные приложения, для которых важно время выполнения — приложения с привязкой к асинхронным взаимодействиям.

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.

инструменты поиска ошибокмногопоточностьфаззинг-тестированиеалгоритмы планированиякомпиляторыerror search toolsmultithreadingfuzzing testingscheduling algorithmscompilersПерсональная благодарность Дергачеву Андрею Михайловичу за оказанную поддержку и мотивацию при написании работы.Personal thanks to Andrey Mikhailovich Dergachev for the support and motivation in writing the work.ReferencesStroustrup B. The C++ Programming Language. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 2000. 1019 p.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. P. 62–71. https://doi.org/10.1145/1791194.1791203Serebryany K., Iskhodzhanov T. ThreadSanitizer — Data race detection in practice. ACM International Conference Proceeding Series, 2009, pp. 62–71. https://doi.org/10.1145/1791194.1791203Netzer R.H.B., Miller B.P. What are race conditions?: Some issues and formalizations // ACM Letters on Programming Languages and Systems (LOPLAS). 1992. V. 1. N 1. P. 74–88. https://doi.org/10.1145/130616.130623Netzer 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.130623Banerjee 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. P. 69–78. https://doi.org/10.1145/1147403.1147416Banerjee 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.1147416Dechev 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. P. 185–192. https://doi.org/10.1109/ISORC.2010.10Dechev 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.10Anderson J., Ramamurthy S., Jeffay K. Real-time computing with lock-free shared objects // ACM Transactions on Computer Systems. 1997. V. 15. N 2. P. 134–165. https://doi.org/10.1145/253145.253159Anderson 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.253159Harris 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. V. 2508. P. 265–279. https://doi.org/10.1007/3-540-36108-1_18Harris 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Саттон М., Грин А., Амини П. Fuzzing: исследование уязвимостей методом грубой силы. Москва: Символ-Плюс, 2009. 555 с.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.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. V. 29. N 7. P. 46–49.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. V. 1. P. 105–113. https://doi.org/10.1109/AERO.2002.1036832Gluck 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.1036832Garcia F., Fernandez J. Posix thread libraries // Linux Journal. 2000. V. 2000. N 70. P. 36.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. V. 2590. P. 1–8.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. V. 2344. P. 1–12.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.Дергун К.И., Доронин О.В. Фаззинг тестирование fine-grained алгоритмов // Сборник тезисов докладов VIII Конгресса молодых ученых. Электронное издание. СПб: Университет ИТМО, 2019.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)

The authors declare that there are no conflicts of interest present.