Что такое race condition

Борьба с гонками (race conditions) в JavaScript на примере работы с кешем

Рассмотрим следующую задачу. Нам необходимо делать вызовы стороннего API, которые считаются дорогими, и, следовательно, их необходимо кешировать в Redis. Мы используем современный NodeJS (версии 14+), а значит и конструкции async / await.

Напишем сначала класс обертку над вызовом API, где сам вызов будем эмулировать 2-секундным таймаутом.

Теперь добавим к коду кеширование в Redis. Для этого будем использовать пакет redis@next.

Код с кеширующим методом cachedApiCall

Несмотря на то, что мы вызываем cachedApiCall, наш счетчик вызовов API всё равно показывает цифру 4. Это происходит из-за особенностей работы async / await.

Давайте детальней рассмотрим кеширующий метод. Я его написал так, как если бы я работал с синхронным кодом.

В коде, при обращении к асинхронным методам, я использовал await. Следовательно, как только исполнение первого вызова cachedApiCall дойдет до этой строки оно прервется, и начнет работать следующий параллельный вызов (а у нас их 4). Так будет происходить на каждом вызове await. Если бы наше обращение к cachedApiCall не вызывалось параллельно, то проблемы бы в таком коде не было. Но при параллельном вызове мы нарвались на состояние гонки. Все 4 вызова соревнуются внутри метода, и в итоге мы имеем 4 запроса на получения значения кеша, 4 вызова API, и 4 вызова на установку значения кеша.

Как можно решить такую проблему? Нужно куда-то спрятать await, например во вложенной фукнции, а сам вызов вложенной функции кешировать в памяти на время работы основой функции.

Выглядеть это будет вот так:

Теперь, при параллельном вызове cachedApiCall все получат один и тот же промис, а значит вызовы к Redis и к нашему API произойдут всего 1 раз.

Боролись ли вы в своих JavaScript проектах с состоянием гонки и какие подходы вы применяли?

Источник

Почему стоит проверять приложения на устойчивость к 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 не следует недооценивать. Лучше потратить время и ресурсы на поиск уязвимости, чтобы избежать непредвиденных последствий, в том числе для бюджета компании.

Источник

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 в веб-приложениях

TL;DR В статье описываются непопулярные трюки с race condition, которые обычно не используют в атаках такого типа. По итогу исследований мы сделали свой фреймворк для атак racepwn.

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

А теперь представим, что наш алгоритм срабатывает одновременно 3 раза.

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

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

Типичная эксплуатация race condition

Заходит хакер в кальянную, квест и бар, а ему — у вас race condition! Омар Ганиев

В большинстве случаев для проверки/эксплуатации состояния гонки используют многопоточное программное обеспечение в качестве клиента. Например, Burp Suite и его инструмент Intruder. Ставят один HTTP-запрос на повторение, устанавливают много потоков и включают флуд. Как например, в этой статье. Или в этой. Это достаточно рабочий способ, если сервер допускает использование множества потоков на свой ресурс и как пишут в статьях выше — если не получилось, попробуйте ещё раз. Но дело в том, что в некоторых ситуациях, это может быть не эффективно. Особенно если вспомнить, как подобные приложения обращаются к серверу.

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

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

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

Можно вспомнить о HTTP-Pipelining, в котором можно отправлять данные с помощью одного сокета. Ты можешь сам посмотреть как это работает, использовав утилиту netcat (у тебя же есть GNU/Linux, ведь так?).

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

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

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

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

Веб-сервер получит запросы последовательно (ключевое слово), и обработает ответы в порядке очереди. Эту особенность можно использовать для атаки в несколько шагов (когда необходимо последовательно выполнить два действия в минимальное количество времени) или, например, для замедления работы сервера в первом запросе, чтобы увеличить успешность атаки.
Трюк — ты можешь мешать серверу обработать твой запрос нагружая его СУБД, особенно эффективно если будет использован INSERT/UPDATE. Более тяжелые запросы могут “затормозить” твою нагрузку, тем самым, будет большая вероятность, что ты выиграешь эту гонку.

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

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

Дальше идут заголовки до переноса строки:

Host: google.com
Cookie: a=1
Но как веб-сервер узнает, что HTTP-запрос закончился?

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

То есть, чтобы веб-сервер принял HTTP-запрос, необходимо два перевода строки. А корректный запрос выглядит так:

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

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

POST / HTTP/1.1
Host: google.com
Content-Length: 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подводя черту

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

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

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

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

Источник

Разбор основных концепций параллелизма

Завтра у нас плавненько стартует практически юбилейный поток курс «Разработчик Java» — уже шестой по счёту начиная с апреля прошлого года. А это значит, что мы снова подобрали, перевели интереснейший материал, которым делимся с вами.

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

С момента своего создания Java поддерживает ключевые концепции параллелизма, такие как потоки и блокировки. Эта памятка поможет Java-разработчикам, работающим с многопоточными программами, понять основные концепции параллелизма и способы их применения.

Таблица 1: Концепции параллелизма

Состояние гонки (Race condition)

Гонка данных (Data race)

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

Модель памяти Java: отношение happens-before

Модель памяти Java определяется с точки зрения таких действий, как чтение/запись полей и синхронизация в мониторе. Действия упорядочены с помощью отношения happens-before (выполняется прежде), которое может быть использовано для объяснения того, когда поток видит результат действий другого потока, и что представляет собой правильно синхронизированная программа.

ОТНОШЕНИЯ HAPPENS-BEFORE ИМЕЮТ СЛЕДУЮЩИЕ СВОЙСТВА:

Изображение 1: Пример happens-before

Стандартные функции синхронизации

Ключевое слово synchronized

Ключевое слово synchronized используется для предотвращения одновременного выполнения разными потоками одного и того же блока кода. Оно гарантирует, что, если вы получили блокировку (войдя в синхронизированный блок), данные, на которые наложена эта блокировка, обрабатываются в эксклюзивном режиме, поэтому операция может считаться атомарной. Кроме того, оно гарантирует, что другие потоки увидят результат операции после того, как получат такую же блокировку.

Ключевое слово synchronized можно также раскрыть на уровне методов.

Таблица 2: Мониторы, которые используются, когда весь метод синхронизирован

Блокировка реентерабельна (reentrant), поэтому, если поток уже содержит блокировку, он может успешно получить ее снова.

Уровень соперничества влияет на способ захвата монитора:

Таблица 3: Состояния мониторов

volatile решает проблему видимости и делает изменение значения атомарным, потому что здесь есть отношение happens-before: запись в volatile-переменную происходит до любого последующего считывания volatile-переменной. Таким образом, оно гарантирует, что при последующем считывании поля будет видно значение, которое было задано самой последней записью.

Используя классы AtomicXXX, можно реализовать атомарную операцию check-then-act :

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

Убедитесь, что this-ссылка не испарилась во время создания.

Одним из самых замечательных свойств неизменяемых объектов является потокобезопасность, поэтому синхронизация для них не нужна. Требования к неизменному объекту:

Класс java.lang.Thread используется для представления приложения или потока JVM. Код всегда выполняется в контексте некоторого класса Thread (чтобы получить текущий поток вы можете использовать Thread#currentThread()).

Таблица 4: Состояния потоков

Таблица 5: Thread coordination methods Методы координации потоков

Как обрабатывать InterruptedException?

Пример потенциального дэдлока:

Взаимная блокировка происходит, если в одно и то же время:

JVM способен обнаруживать взаимные блокировки мониторов и выводить информацию о них в дампах потоков.

Livelock и потоковое голодание

Livelock возникает, когда потоки тратят все свое время на переговоры о доступе к ресурсу или обнаруживают и избегают тупиковой ситуации так, что поток фактически не продвигается вперед. Голодание возникает, когда потоки сохраняют блокировку в течение длительных периодов, так что некоторые потоки «голодают» без прогресса.

Основным интерфейсом для пулов потоков является ExecutorService.java.util.concurrent также предоставляет статическую фабрику Executors, которая содержит фабричные методы для создания пула потоков с наиболее распространенными конфигурациями.

Таблица 6: Методы статической фабрики

Таблица 7: Реализации пула потоков

Таблица 8: Функциональные интерфейсы задач

Future — это абстракция для асинхронного вычисления. Она представляет результат вычисления, который может быть доступен в какой-либо момент: либо вычисленное значение, либо исключение. Большинство методов ExecutorService используют Future как возвращаемый тип. Он предоставляет методы для изучения текущего состояния future или блокирует до тех пор, пока не будет доступен результат.

Пакет java.util.concurrent.locks также содержит интерфейс ReadWriteLock (и реализацию ReentrantReadWriteLock), который определяется парой блокировок для чтения и записи, обычно позволяя считывать одновременно нескольким читателям, но допуская только одного писателя.

CompletableFuture является абстракцией для произведения асинхронных вычислений. В отличие от простого Future, где единственная возможность получить результат — блокировать, рекомендуется регистрировать обратные вызовы для создания конвейера задач, которые должны выполняться, когда доступен результат или исключение. Либо во время создания (через CompletableFuture#supplyAsync/runAsync ), либо во время добавления обратных вызовов (методы семейства *async ) может быть указан исполнитель, где должно выполняться вычисление (если он не указан стандартным глобальным ForkJoinPool#commonPool ).

Учтите, что если CompletableFuture уже завершен, обратные вызовы, зарегистрированные с помощью не *async методов, будут выполняться в вызывающем потоке.

Таблица 9: Списки в java.util.concurrent

Таблица 10: Ассоциативные массивы в java.util.concurrent

Таблица 11: Множества в java.util.concurrent

Другим подходом к созданию параллельного множества является обертка параллельного Map:

Источник