Что такое состояние гонки в java

Русские Блоги

Многопоточность JAVA (два), состояние гонки, взаимоблокировка и механизм синхронизации

4 Многопоточные проблемы безопасности и решения

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

Что такое безопасность потоков? Проще говоря, Если ваш код всегда будет получать один и тот же результат при выполнении в нескольких потоках и в одном потоке, тогда ваш код является поточно-ориентированным.

4.1 Состояние гонки (условия гонки) и многопоточный механизм синхронизации

4.1.1 Понятие условий гонки

Thread-0:0
Thread-0:2
Thread-1:1
Thread-0:3
Thread-0:5
Thread-0:6
Thread-0:7
Thread-0:8
Thread-0:9
Thread-0:10
Thread-0:11
Thread-1:4
Thread-1:12
Thread-1:13
Thread-1:14
Thread-1:15
Thread-1:16
Thread-1:17
Thread-1:18
Thread-1:19
В этом примере оба потока получат доступ к индексу статической переменной. Время получения системного временного интервала является неопределенным, поэтому их доступ и изменение индекса всегда чередуются.

4.1.2 Многопоточная синхронизация

Есть три способа добиться синхронизации:

4.1.3 synchronized

Структура синхронизированного блока:

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

Результаты этого прогона:
Thread-1:0
Thread-1:1
Thread-1:2
Thread-1:3
Thread-1:4
Thread-1:5
Thread-1:6
Thread-1:7
Thread-1:8
Thread-1:9
Thread-0:10
Thread-0:11
Thread-0:12
Thread-0:13
Thread-0:14
Thread-0:15
Thread-0:16
Thread-0:17
Thread-0:18
Thread-0:19
Можно видеть, что после использования синхронизации потоки будут обращаться к статическим переменным в том порядке, то есть механизм синхронизации решает условие гонки путем «блокировки».

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

4.1.4 Lock vs synchronized

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

Вот пример использования Lock:

Результат выполнения программы:
interrupted.

4.2 тупик (тупик)

Тупик относится к Два или более процессов В процессе исполнения, феномен ожидания друг друга, вызванный конкуренцией за ресурсы, если нет внешней силы, они всегда будут ждать друг друга и не могут продвигаться вперед. Другими словами, тупик заставит вашу программу зависнуть и не сможет завершить задачу.

При каких обстоятельствах возникнет тупик? Одновременно Следующие условия

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

Здесь мы даем пример, чтобы проиллюстрировать тупик и избежать тупика (программа цитируетсяHow to avoid deadlock). Следующая программа вызовет взаимоблокировку, потому что, если поток 1 получает блокировку объекта String при выполнении method1 (), а поток 2 получает блокировку объекта Integer при выполнении method2 (), обе стороны будут входить в бесконечное взаимное Состояние ожидания, поскольку обе стороны хотят получить блокировку объекта, полученную другой стороной. к

Согласно сказанному выше, вы можете избежать тупиковых ситуаций, внеся следующие изменения в программу. Когда поток 1 получает блокировку объекта Integer, поток 2 будет ожидать, пока поток 1 не снимет блокировку, прежде чем выполнить, и наоборот. к

Источник

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. Часть 2

Jul 9, 2020 · 5 min read

Состояние гонки

Вновь приветствую вас в теме “Синхронизация в Java”! Надеюсь, что вы прочли мою предыдущую статью.

Давайте разберёмся, что же такое состояние гонки. Это состояние проявляется, когда нам нужно обратиться к данным параллельно. Хорошо, тогда что же значит параллельное обращение к данным? Проще говоря, это означает, что два разных потока могут считывать одну и ту же переменную, поле, или даже массив, определённые внутри класса Java. Давайте возьмём популярный шаблон проектирования “Singleton” и посмотрим, как в нём проявляется такое состояние гонки.

Два потока пытают с я выполнить этот блок кода. Представьте себе ситуацию, где поток 1 (T1) задерживается в блоке if, в это время в процесс включается T2 и в итоге завершает блок if созданием “статического экземпляра Singleton”, после чего опять запускается T1 и уничтожает только что созданный T2 экземпляр.

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

Значит синхронизация решит проблему? Да, именно так. Теперь давайте посмотрим её в действии на примере образов. В них мы увидим, как ключевое слово synchronized защищает методы.

Для большей наглядности я подготовил серию рисунков. Образ человека будет представлять собой поток. Взгляните на то, как этот человек просит ключ и попадает с его помощью в метод, а затем, покидая этот метод, возвращает ключ обратно. Поэтому другой человек (поток 2) должен дождаться, чтобы также получить ключ. Достаточно простой принцип, не так ли?

По факту из сказанного следует, что нам нужен объект, который будет содержать ключ, делая подобную синхронизацию возможной. В случае, приведённом выше, мы поместили ключевое слово synchronized в public static method. А что же для преодоления блокировки в таком случае использует JVM? Объект Singleton.class. Т.е. схожим образом в случае синхронизации в нестатических методах JVM использует в качестве объекта синхронизации конкретный экземпляр, в котором Singleton.class находится.

Давайте используем для синхронизации явный объект

Мы можем использовать для выполнения синхронизации явный объект, как это показано в блоке кода ниже. Да, достаточно только самого класса объекта. Я думаю, что вы уже знаете почему. Вместо синхронизирования метода getName() мы можем использовать синхронизированный блок внутри этого метода и передать объект key в качестве параметра ключевого слова synchronized. Помните, что это всегда будет удачным решением.

Синхронизация более чем одного метода

Предположим, что у нас есть класс Student с двумя синхронизированными методами getName() и getMarks(). Объект блокировки, используемый JVM, находится в самом объекте Student. Когда конкретный поток захочет выполнить getName(), он возьмёт этот объект блокировки, тем самым лишая другой поток возможности выполнить этот же метод одновременно с ним. Поскольку мы не объявляли явный объект в синхронизации наших методов, будет использован тот же объект key. Итак, теперь становится понятно, что для независимого выполнения этих двух методов в одно и то же время нам нужно создать в классе Student два объекта блокировки и синхронизировать эти два блока кода из 2 блокировок (2 разных объектов).

Теперь предположим, что у нас есть два экземпляра класса Student: Student1 и Student2. Синхронизирование более одного метода заблокирует объекты двумя ключами.

Источник

Что такое состояние гонки?

При написании многопоточных приложений одной из наиболее распространенных проблем является состояние гонки.

Мои вопросы к сообществу:

Каково состояние гонки?
Как вы их обнаруживаете?
Как вы справляетесь с ними?
Наконец, как вы предотвращаете их появление?

Состояние гонки возникает, когда два или более потоков могут получить доступ к общим данным, и они пытаются изменить их одновременно. Поскольку алгоритм планирования потоков может переключаться между потоками в любое время, вы не знаете порядок, в котором потоки будут пытаться получить доступ к общим данным. Следовательно, результат изменения данных зависит от алгоритма планирования потоков, то есть оба потока «участвуют в гонке», чтобы получить доступ / изменить данные.

Проблемы часто возникают, когда один поток выполняет «check-then-act» (например, «check», если значение равно X, затем «act», чтобы сделать что-то, зависящее от значения, являющегося X), а другой поток делает что-то со значением в между «чеком» и «актом». Например:

Дело в том, что у может быть 10 или может быть любым, в зависимости от того, изменился ли другой поток х между проверкой и действием. У вас нет реального способа узнать.

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

«Условие гонки» существует, когда многопоточный (или другой параллельный) код, который будет обращаться к общему ресурсу, может сделать это таким образом, чтобы вызвать неожиданные результаты.

Возьмите этот пример:

Если у вас было 5 потоков, выполняющих этот код одновременно, значение x НЕ БЫЛО 50 000 000. Это на самом деле будет меняться с каждым прогоном.

Это связано с тем, что для того, чтобы каждый поток увеличивал значение x, они должны сделать следующее: (очевидно, упрощенно)

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

Допустим, поток извлекает значение x, но еще не сохранил его. Другой поток может также получить то же значение x (потому что ни один поток еще не изменил его), и тогда они оба сохранят одно и то же значение (x + 1) обратно в x!

Гоночных условий можно избежать, используя какой-то механизм блокировки перед кодом, который обращается к общему ресурсу:

Здесь каждый раз получается 50 000 000 ответов.

Подробнее о блокировке ищите: мьютекс, семафор, критический раздел, общий ресурс.

Религиозный кодекс, многопоточные юнит-тесты. Там нет ярлыка. Существует несколько плагинов Eclipse, но пока нет ничего стабильного.

Как вы справляетесь и предотвращаете их?

Лучше всего было бы создавать функции без побочных эффектов и без сохранения состояния, как можно больше использовать неизменяемые. Но это не всегда возможно. Таким образом, использование java.util.concurrent.atomic, параллельные структуры данных, правильная синхронизация и параллелизм на основе акторов помогут.

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

Многие гонки могут быть (и фактически) вызваны гонками данных, но это не обязательно. Фактически, гонки данных и условия гонки не являются ни необходимым, ни достаточным условием друг для друга. Этот пост в блоге также очень хорошо объясняет разницу на простом примере банковской транзакции. Вот еще один простой пример, который объясняет разницу.

Теперь, когда мы прибегли к терминологии, давайте попробуем ответить на первоначальный вопрос.

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

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

Источник

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.

Источник