<div>
	Организация фаззинг-тестирования многопоточных приложений на основе метода распараллеливания независимых переходов</div>

Доронин Олег Владимирович

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

2022 , ТОМ 22, НОМЕР 4 ( июль-август )

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

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

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

УДК 004.416.2

Организация фаззинг-тестирования многопоточных приложений на основе метода распараллеливания независимых переходов

Доронин О.В.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Доронин О.В. Организация фаззинг-тестирования многопоточных приложений на основе метода распараллеливания независимых переходов // Научно-технический вестник информационных технологий, механики и оптики. 2022. Т. 22, № 4. С. 734–741. doi: 10.17586/2226-1494-2022-22-4-734-741

Аннотация

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

Ключевые слова: инструменты поиска ошибок, многопоточность, фаззинг-тестирование, алгоритмы планирования, компиляторы

Благодарности. Персональная благодарность Дергачеву Андрею Михайловичу за оказанную поддержку и мотивацию при написании работы

Список литературы

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.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. V. 1. N 1. P. 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. P. 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. P. 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. V. 15. N 2. P. 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. V. 2508. P. 265–279. https://doi.org/10.1007/3-540-36108-1_18
Саттон М., Грин А., Амини П. Fuzzing: исследование уязвимостей методом грубой силы. Москва: Символ-Плюс, 2009. 555 с.
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.
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.1036832
Garcia F., Fernandez J. Posix thread libraries // Linux Journal. 2000. V. 2000. N 70. P. 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. Automatic fuzzy-scheduling of threads in Google Thread Sanitizer to detect errors in multithreaded code // CEUR Workshop Proceedings. 2019. V. 2344. P. 1–12.
Дергун К.И., Доронин О.В. Фаззинг тестированиеfine-grained алгоритмов// Сборник тезисов докладов VIII Конгресса молодых ученых. Электронное издание. СПб: Университет ИТМО, 2019.

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