Что означает ситуация гонок каким образом ее можно протестировать

Race condition и D ata Race

Продолжаем серию статей о проблемах многопоточности, параллелизме, concurrency и других интересных штуках.

Race condition и data race — две разные проблемы многопоточности, которые часто путают. Попробуем разобраться.

Race condition

Существует много формулировок определения:

Race condition представляет собой класс проблем, в которых корректное поведение системы зависит от двух независимых событий, происходящих в правильном порядке, однако отсутствует механизм, для того чтобы гарантировать фактическое возникновение этих событий.

Race condition — ошибка проектирования многопоточной системы или приложения, при которой работа системы или приложения зависит от того, в каком порядке выполняются части кода.

Race condition — это нежелательная ситуация, которая возникает, когда устройство или система пытается выполнить две или более операций одновременно, но из-за природы устройства или системы, операции должны выполняться в правильной последовательности, чтобы быть выполненными правильно.

Race condition — это недостаток, связанный с синхронизацией или упорядочением событий, что приводит к ошибочному поведению программы.

Но мне нравиться наиболее короткое и простое:

Race condition — это недостаток, возникающий, когда время или порядок событий влияют на правильность программы.

Важно, что Race condition — это семантическая ошибка.

В проектирование электронных схем есть похожая проблема:

Состязание сигналов — явление в цифровых устройствах несоответствия работы данного устройства с заданным алгоритмом работы по причине возникновения переходных процессов в реальной аппаратуре.

Рассмотрим пример, где результат не определен:

Если запустить такой код много раз, то можно увидеть примерно такое:

Результат выполнения кода зависит от порядка выполнения горутин. Это типичная ошибка race condition. Ситуации могут быть гораздо сложней и не очевидней.

Учитывая, что race condition семантическая ошибка, нет общего способа который может отличить правильное и неправильное поведение программы в общем случае.

Помочь могут хорошие практики и проверенные паттерны.

В результате на консоле получим четные и нечетные числа, а расчитывали увидеть только четные.

Проблемы с доступом к общим ресурсам проще обнаружить автоматически и решаются они обычно с помощью синхронизации:

или локальной копией:

Data Race

Data race это состояние когда разные потоки обращаются к одной ячейке памяти без какой-либо синхронизации и как минимум один из потоков осуществляет запись.

Пример с балансом на счету:

Запускаем в разных горутинах:

Изначально баланс равен 0, депозитим 1000 раз по 1. Ожидаем баланс равный 1000, но результат другой:

Потеряли много денег.

Причина в том, что операция acc.balance += amount не атомарная. Она может разложиться на 3:

Пока мы меняем временную переменную в одном потоке, в других уже изменен основной balance. Таким образом теряется часть изменений.

Например, у нас 2 параллельных потока выполнения, каждый должен прибавить к балансу по 1:

Ожидали получить баланс=102, а получили = 101.

У Data Race есть точное определение, которое не обязательно связано с корректностью, и поэтому их можно обнаружить. Существует множество разновидностей детекторов гонки данных (статическое/динамическое обнаружение, обнаружение на основе блокировок, обнаружение основанное на предшествующих событий, обнаружение гибридного data race).

У Go есть хороший Data Race Detector с помощью которого такие ошибки можно обнаружить.

Решается проблема с помощью синхронизации:

Race Condition и Data Race

Функция для перевода средств с одного счета на другой:

На одном счету у нас будет 1000, а на другом 0. Переводим по 1 в 1000 горутинах и ожидаем, что все деньги из одного счета перетекут в другой:

Но результат может быть таким:

Если запустить цикл на большее кол-во операций, то можно получить еще интересней:

При вызове из нескольких потоков без внешней синхронизации эта функция допускает как dara race (несколько потоков могут одновременно пытаться обновить баланс счета), так и race condition (в параллельном контексте это приведет к потере денег).

Для решения можно применить синхронизацию и локальную копию. Общая логика может быть не такой линейной и в итоге код может выглядит например так:

У нас синхронизированы все участки с записью и чтением, у нас есть локальная копия, Race Detector больше не ругается на код. Запускаем 1000 операций и получаем верный результат:

Но что если горутин будет 10к:

Мы решили проблему data race, но race condition остался. В данном случае можно сделать блокировку на всю логику перевода средств, но это не всегда возможно.

Решив Data Race через синхронизацию доступа к памяти (блокировки) не всегда решается race condition и logical correctness.

Источник

Почему стоит проверять приложения на устойчивость к race condition

Если ваше приложение или сервис работает с внутренней валютой, следует проверить его на уязвимости типа race condition («состояние гонки» или, если точнее, — «неопределенность параллелизма»). Race condition — это «плавающая ошибка», которую могут эксплуатировать злоумышленники. Суть в том, что благодаря параллельному выполнению кода можно получить доступ к внутренней валюте приложения, манипулировать ею и, при желании, нанести ощутимый финансовый ущерб владельцу сервиса. Недавно мы обнаружили такую проблему у одного из наших клиентов и помогли ее решить.

Что такое race condition

Так как разработчики часто забывают, что код может выполняться несколькими потоками одновременно, они не тестируют продукт на уязвимость типа race condition, хотя эта ошибка довольно распространена.

С точки зрения бэкэнда это выглядит так: несколько потоков одновременно обращаются к одному общему ресурсу: переменным или файлам, для которых не предусмотрена блокировка или синхронизация. Это приводит к несогласованности вывода данных.

Вот конкретный пример такой уязвимости. Допустим, у нас есть приложение, которое позволяет переводить бонусы между платежными кошельками. У злоумышленника есть два кошелька — A и B, и на каждом из них есть 1000 бонусов. На схеме показано, как манипулируя временем отправки запроса на транзакцию, злоумышленник может увеличивать сумму перевода на свой счет и сделать из 10 бонусов — 20.

Существуют автоматические инструменты для поиска таких уязвимостей. Например, RacePWN который за минимальное время отправляет множество HTTP-запросов на сервер и принимает на вход json-конфигурацию, облегчая процесс атаки для злоумышленников. Вручную же это делается с помощью отправки POST-запросов.

Смертельная race condition

В США с июня 1985 года по январь 1987 года ошибка race condition в аппарате лучевой терапии Therac-25, созданном канадской государственной организацией Atomic Energy of Canada Limited (AECL) стала причиной шести передозировок радиацией. Жертвы получили дозы в десятки тысяч рад. Смертельным считается уровень в 1000 рад. После полученных ожогов пострадавшие умерли в течение нескольких недель. Выжить удалось только одной пациентке.

Предыдущие модели Therac имели аппаратные механизмы защиты: независимые цепи блокировки, контролирующие электронный луч; механические блокираторы; аппаратные автоматические выключатели; отключающие предохранители. В Therac-25 аппаратную защиту убрали. За безопасность отвечало программное обеспечение. Аппарат имел несколько режимов работы, и из-за ошибки race condition врач иногда не понимал, в каком режиме аппарат работает на самом деле. В ходе судебных разбирательств выяснилось, что ПО Therac-25 было разработано одним программистом, но у AECL не было данных, кем конкретно.

По итогам процесса правительство США серьезно ужесточило требования к проектированию и работе систем, чья безопасность критична для людей.

Как защититься

Проще и дешевле всего решить проблему race condition — правильно спроектировать архитектуру приложения. Вот что для этого следует предусмотреть.

Как мы нашли уязвимость

Наш клиент — интернет-магазин доставки продуктов, который поддерживает функцию предоставления скидок с помощью купонов. В процессе тестирования мы обнаружили уязвимость — при отправке POST-запроса со значением купона. Отправляя запрос с различными временными задержками, удавалось получить скидку дважды. Судя по всему, разработчики допустили грубую ошибку, связанную с разделяемым доступом к объекту, который отождествлялся с покупкой.

Решение

Race condition не следует недооценивать. Лучше потратить время и ресурсы на поиск уязвимости, чтобы избежать непредвиденных последствий, в том числе для бюджета компании.

Источник

20.5. Ситуация гонок

20.5. Ситуация гонок

Ситуация гонок (race condition) обычно возникает, когда множество процессов получают доступ к общим для них данным, но корректность результата зависит от порядка выполнения процессов. Поскольку порядок выполнения процессов в типичных системах Unix зависит от множества факторов, которые могут меняться от запуска к запуску, иногда результат корректен, а иногда — нет. Наиболее сложным для отладки типом гонок является такой, когда результат получается некорректным только изредка. Более подробно о ситуациях гонок мы поговорим в главе 26, когда будем обсуждать взаимные исключения (mutex) и условные переменные (condition variables). При программировании потоков всегда возникают проблемы с ситуациями гонок, поскольку значительное количество данных является общим для всех потоков (например, все глобальные переменные).

Ситуации гонок другого типа часто возникают при работе с сигналами. Проблемы возникают, потому что сигнал, как правило, может быть доставлен в любой момент во время выполнения нашей программы. POSIX позволяет нам блокировать доставку сигнала, но при выполнении операций ввода-вывода это часто не дает эффекта.

Чтобы понять эту проблему, рассмотрим пример. Ситуация гонок возникает при выполнении программы из листинга 20.1. Потратьте несколько минут и посмотрите, сможете ли вы ее обнаружить. (Подсказка: в каком месте программы мы можем находиться, когда доставляется сигнал?) Вы можете также инициировать ситуацию гонок следующим образом: изменить аргумент функции alarm с 5 на 1 и добавить вызов sleep(1) сразу же после printf.

Когда мы после внесения этих изменений наберем первую строку ввода, эта строка будет отправлена как широковещательное сообщение, а мы установим аргумент функции alarm равным 1 с. Мы блокируемся в вызове функции recvfrom, а затем для нашего сокета приходит первый ответ, вероятно, в течение нескольких миллисекунд. Ответ возвращается функцией recvfrom, но затем мы входим в спящее состояние на одну секунду. Принимаются остальные ответы и помещаются в приемный буфер сокета. Но пока мы находимся в спящем состоянии, время таймера alarm истекает и генерируется сигнал SIGALRM. При этом вызывается наш обработчик сигнала, затем он возвращает управление и прерывает функцию sleep, в которой мы блокированы. Далее мы повторяем цикл и читаем установленные в очередь ответы с паузой в одну секунду каждый раз, когда выводится ответ. Прочитав все ответы, мы снова блокируемся в вызове функции recvfrom, однако таймер уже не работает. Мы окажемся навсегда заблокированы в вызове функции recvfrom. Фундаментальная проблема здесь в том, что наша цель — обеспечить прерывание блокирования в функции recvfrom обработчиком сигнала, однако сигнал может быть доставлен в любое время, и наша программа в момент доставки сигнала может находиться в любом месте бесконечного цикла for.

Теперь мы проанализируем четыре различных варианта решения этой проблемы: одно некорректное и три различных корректных решения.

Блокирование и разблокирование сигнала

Наше первое (некорректное) решение снижает вероятность появления ошибки, блокируя сигнал и предотвращая его доставку, пока наша программа выполняет оставшуюся часть цикла for. Эта версия представлена в листинге 20.2.

Листинг 20.2. Блокирование сигналов при выполнении в цикле for (некорректное решение)

2 static void recvfrom_alarm(int);

4 dg_cli(FILE *fp, int sockfd, const SA *pservaddr, socklen_t servlen)

8 char sendline[MAXLINE], recvline[MAXLINE + 1];

9 sigset_t sigset_alrm;

11 struct sockaddr *preply_addr;

12 preply_addr = Malloc(servlen);

13 Setsockopt(sockfd, SOL_SOCKET, SO_BROADCAST, &on, sizeof(on));

16 Signal(SIGALRM, recvfrom_alarm);

18 Sendto(sockfd, sendline, strlen(sendline), 0, pservaddr, servlen);

23 n = recvfrom(sockfd, recvline, MAXLINE, 0, preply_addr, &len);

25 if (n Продолжение на ЛитРес

Читайте также

10.4.5. Состояния гонок и sig_atomic_t (ISO C)

10.4.5. Состояния гонок и sig_atomic_t (ISO C) Пока обработка одного сигнала за раз выглядит просто: установка обработчика сигнала в main() и (не обязательная) переустановка самого себя обработчиком сигнала (или установка действия SIG_IGN) в качестве первого действия обработчика.Но что

Реальная ситуация

Реальная ситуация Рис. 5.7. Диаграмма загрузки (неизмененного) сайта

Ситуация 4. Авария загрузочного диска

Ситуация 4. Авария загрузочного диска Технический бандит. Чинит диск. Обычно ему удается восстановить файловую систему прямо из приглашения загрузки. Если это не помогает, запускает микроядро, которое запускает на соседнем компьютере скрипт, копирующий на аварийную

Ситуация 5. Слабая производительность сети

Ситуация 5. Слабая производительность сети Технический бандит. Пишет скрипт для мониторинга сети, переписывает программное обеспечение, чем повышает производительность на 2%. Пожимает плечами, говорит: «Я сделал все, что мог», и отправляется в поход в

Ситуация 7. Установка новой версии операционной системы

Ситуация 7. Установка новой версии операционной системы Технический бандит. Изучает исходные тексты новой версии и выбирает из них только то, что ему нравится.Администратор-фашист. В первую очередь изучает законодательные акты против производителя, поставляющего

3. Проблемная ситуация, которую вы преодолели

3. Проблемная ситуация, которую вы преодолели Наверняка у каждого в жизни были ситуации, когда вы чего-то боялись или испытывали дискомфорт. Например, во время публичных выступлений или при общении с противоположным полом, на работе. У вас были проблемы, но вы их

Бизнес-ситуация 1.2: проектирование таблиц и отношений

Бизнес-ситуация 1.2: проектирование таблиц и отношений Брэд Джонс понял, что компании Jones Novelties Incorporated необходим способ сохранения информации о клиентах. Он совершенно уверен в том, что большинство его деловых контактов не будут однократными, и поэтому хочет иметь

АНАЛИЗЫ: Патовая патентная ситуация

АНАЛИЗЫ: Патовая патентная ситуация 6 июля сего года Европарламент 648 голосами против 14 во втором чтении отклонил направленный на утверждение Евросоветом проект «Директивы о патентовании компьютерно-реализованных изобретений», ставшей за последний год более известной

Нереволюционная ситуация

Нереволюционная ситуация В этом году самое главное игровое мероприятие осени, Tokyo Game Show, посетило рекордное количество любителей игр и интерактивных развлечений — более 176 тысяч человек. По данным организатора выставки, ассоциации Computer Entertainment Supplier’s Association, прежний

Источник

Race conditon в веб-приложениях

Многие недооценивают такую уязвимость, как race condition. А также неправильно ее эксплуатируют. Автор расскажет как и с чем ее готовить.

При написании программ человек берет простейшие алгоритмы, которые он объединяет в единый сюжет, что и будет являться сценарием программы. Предположим, задача программиста — написать логику переводов денег (баллов, кредитов) от одного человека к другому в веб-приложении. Руководствуясь логикой можно составить алгоритм, состоящий из нескольких проверок.

Вася хочет перевести 100 долларов, которые есть у него на счету, Пете. Он переходит на вкладку переводов, вбивает Петин ник и в поле с количеством средств, которые необходимо перевести — цифру 100. Далее, нажимает на кнопку перевода. Данные кому и сколько отправляются на веб-приложение. Что может происходить внутри? Что необходимо сделать программисту, чтобы все работало корректно?

● Убедиться, что у Васи достаточно денег на счету

Нужно убедиться, что сумма доступна Васе для перевода. Необходимо получить значение текущего баланса пользователя, если оно меньше чем сумма, которую он хочет перевести — сказать ему об этом. С учетом того, что на нашем сайте не предусмотрены кредиты и в минус баланс уйти не должен.

● Вычесть сумму, которую необходимо перевести из баланса пользователя

Необходимо записать в значение баланса текущего пользователя его баланс с вычетом переводимой суммы. Было 100, стало 100-100=0.

● Добавить к балансу пользователя Петя сумму которую перевели.

Пете наоборот, было 0, стало 0+100=100.

● Вывести сообщение пользователю, что он молодец!

У нас получается примерно такой псевдокод:

Если (Вася.баланс >= сумма_перевода) То

Но всё бы ничего, если бы все происходило в одном потоке. Тогда бы все запросы выполнялись друг за другом. Но так как сайт может обслуживать одновременно множество пользователей, это все происходит не в одном потоке, потому что современные веб-приложения используют многопроцессорность и многопоточность для параллельной обработки данных. С появлением многопоточности у программ появилась забавная архитектурная уязвимость — состояние гонки (или race condition). А теперь представим, что наш алгоритм срабатывает одновременно 3 раза.

У Васи все так же 100 баксов на балансе, только вот каким-то образом он обратился к веб-приложению тремя потоками одновременно (с минимальным количеством времени между запросами). Все три потока проверяют, существует ли пользователь Петя, и проверяют, достаточно ли баланса у Васи для перевода. В тот момент времени, когда алгоритм проверяет баланс, он всё еще равен 100. Как только проверка пройдена, из текущего баланса 3 раза вычитается 100, и добавляется Пете.

Также race condition применяется, например, для повышения привилегий в операционных системах.

Типичная гонка

Что там на сервере

Каждый поток устанавливает TCP соединение, отправляет данные, ждет ответа, закрывает соединение, открывает снова, отправляет данные и так далее. На первый взгляд, все данные отправляются одновременно, но сами HTTP-запросы могут приходить не синхронно и в разнобой из-за особенностей транспортного уровня, необходимости устанавливать защищенное соединение (HTTPS) и резолвить DNS (не в случае с burp’ом) и множества слоёв абстракций, которые проходят данные до отправки в сетевое устройство. Когда речь идет о миллисекундах, это может сыграть ключевую роль.

Конвейерная обработка HTTP

На самом деле использовать linux необходимо по многим причинам, ведь там более современный стек TCP/IP, который поддерживается ядрами операционной системы. Сервер скорее всего тоже на нем.

Например, выполни команду nc google.com 80 и вставь туда строки

Таким образом, в рамках одного соединения будет отправлено три HTTP-запроса, и ты получишь три HTTP ответа. Эту особенность можно использовать для минимизации времени между запросами.

Что там на сервере

Веб-сервер получит запросы последовательно (ключевое слово), и обработает ответы в порядке очереди. Эту особенность можно использовать для атаки в несколько шагов (когда необходимо последовательно выполнить два действия в минимальное количество времени) или, например, для замедления работы сервера в первом запросе, чтобы увеличить успешность атаки*.

Разбиение HTTP-запроса на две части

Для начала вспомни как формируется HTTP-запрос.

Ну как ты знаешь, первая строка это метод, путь и версия протокола:

Второй и последующий это заголовки и их содержимое

Но как веб-сервер узнает, что HTTP-запрос закончился?

Давай рассмотрим на примере, введи nc google.com 80, а там

после того, как нажмешь ENTER, ничего не произойдет. Нажмешь еще раз — увидишь ответ.

GET / HTTP/1.1\r\nHost: google.com\r\n\r\n

Если бы это был метод POST (не забываем про Content-Length), то корректный HTTP-запрос был бы таким:

Или POST / HTTP/1.1\r\nHost: google.com\r\nContent-Length: 3\r\na=1\r\n\r\n

Попробуй отправить подобный запрос из командной строки:

В итоге ты получишь ответ, так как наш HTTP-запрос полноценный. Но если ты уберешь последний символ \n, то ответа не получишь.

На самом деле многим веб-серверам достаточно использовать в качестве переноса \n, поэтому важно не менять местами \r и \n, иначе дальнейшие трюки могут не получиться.

Что это дает? Ты можешь одновременно открыть множество соединений на ресурс, отправить 99% своего HTTP-запроса и оставив неотправленным последний байт. Сервер будет ждать пока ты не дошлёшь последний символ перевода строки. После того, как будет ясно, что основная часть данных отправлена — дослать последний байт (или несколько).

Это особенно важно, если речь идет о большом POST-запросе, например, когда необходима заливка файла. Но и даже в небольшом запросе это имеет смысл, так как доставить несколько байт намного быстрее, чем одновременно килобайты информации.

Задержка перед отправкой второй части запроса

Что там на сервере

Например nginx при получении заголовков HTTP-запроса начнет их парсить, складывая неполноценный запрос в кэш. Когда придет последний байт — веб-сервер возьмет частично обработанный запрос и отправит его уже непосредственно приложению, тем самым сокращается время обработки запросов, что повышает вероятность атаки.

Кстати, как с этим бороться

В первую очередь это конечно же архитектурная проблема, если правильно спроектировать веб-приложение, можно избежать подобных гонок.

Обычно, применяют следующие методы борьбы с атакой:

Операция блокирует в СУБД обращения к заблокированному объекту, пока его не разблокируют. Другие стоят и ждут в сторонке. Необходимо правильно работать с блокировками, не блокировать ничего лишнего.

Берут какую-нибудь штуку (например etcd). В момент вызова функций создают запись с ключем, если не получилось создать запись, значит она уже есть и тогда запрос прерывается. По окончании обработки запроса запись удаляется.

И вообще мне понравилось видео выступления Ивана Работяги про блокировки и транзакции, очень познавательно.

Особенности сессий в race condition

Одна из особенностей сессий может быть то, что она сама по-себе мешает эксплуатировать гонку. Например, в языке PHP после session_start() происходит блокировка сессионного файла, и его разблокировка наступит только по окончанию работы сценария (если не было вызова session_write_close ). Если в этот момент вызван другой сценарий который использует сессию, он будет ждать.

Для обхода этой особенности можно использовать простой трюк — выполнить аутентификацию нужное количество раз. Если веб-приложение разрешает создавать множество сессий для одного пользователя, просто собираем все PHPSESSID и делаем каждому запросу свой идентификатор.

Близость к серверу

Если сайт, на котором необходимо эксплуатировать race condition хостится в AWS — возьми тачку в AWS. Если в DigitalOcean — бери там.

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

Ведь есть разница, когда ping к серверу 200 и 10 мс. А если повезет, вы вообще можете оказаться на одном физическом сервере, тогда зарейсить будет немного проще 🙂

Для успешного race condition можно применять различные трюки для увеличения вероятности успеха. Отправлять несколько запросов (keep-alive) в одном, замедляя веб-сервер. Разбивать запрос на несколько частей и создавать задержку перед отправкой. Уменьшать расстояние до сервера и количество абстракций до сетевого интерфейса.

В результате этого анализа мы вместе с Michail Badin разработали инструмент RacePWN

Он состоит из двух компонентов:

Библиотеки librace на языке C, которая за минимальное время и используя большинство фишек из статьи отправляет множество HTTP-запросов на сервер

Утилиты racepwn, которая принимает на вход json-конфигурацию и вообще рулит этой библиотекой

RacePWN можно интегрировать в другие утилиты (например в Burp Suite), или создать веб-интерфейс для управления рейсами (все никак руки не доходят). Enjoy!

Но на самом деле ещё есть куда расти и можно вспомнить о HTTP/2 и его перспективы для атаки. Но в данный момент HTTP/2 у большинство ресурсов лишь фронт, проксирующий запросы в старый-добрый HTTP/1.1.

Источник