На гитхабе код открыт тыща строк как этот бит

Wzsound — Podvoram

По дворам
По дворам гуляю в хлам
Инстаграм, телеграм — не сейчас
По району в ночи час
Рассекаю бормоча
Мне луна свет несла
Ебнул боттл пополам
Моросил звон по рукам
Раздробилась по кускам
Не связать стог из слов
Сто столбов, тень рябит
Я ей всё толкую час
Это наша часть
Не придет месть для нас
Не уйдет шиш на нас
Не зайдет этот бит
Для всех вас
На репит
Ставлю фит
Скоро meet
Собрал shit
Двинул на taxi
Прямо к точке “Си”
Блант ты загаси
На айфон насоси

Как создать безопасную авторизацию пользователей с помощью UUID

Всем привет, я Никита, Node.js-разработчик в компании OBRIO, которая входит в экосистему бизнесов Genesis. Компания существует с мая и сейчас команда развивает четыре продуктовых направления: Mobile, Web, GameDev, SaaS.

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

Тема авторизации будет актуальна для большинства приложений. В статье мы сравним существующие подходы, разберем, с какими подводными камнями сталкиваются при создании модуля авторизации, и напишем авторизацию в приложении с нуля на примере Node.js.

Когда мы начали разработку нового приложения, одной из первых задач, конечно, было построение правильной системы аутентификации и авторизации пользователей в системе. Недолго думая, мы взяли самый распространенный способ и его готовую реализацию на нашей платформе. Мы использовали JWT-токены, взяв в качестве библиотеки-поставщика Passport.js. Тем более, что есть готовый модуль Passport.js для фреймворка Nest.js, который используется на проекте. Однако вскоре я пожалел об этом решении.

С каждым новым бизнес-запросом мне становилось все сложнее решать, как его удовлетворить в текущей архитектуре. И проблема была в нашей системе авторизации. Она накладывала несколько ограничений, кроме того, Passport.js добавлял слишком много «магии» в код, что осложняло дебаг. Потому было принято решение отказаться от Passport.js, а потом и от использования JWT-токенов.

С Passport.js все было предельно просто: я довольно быстро написал собственную реализацию авторизации через JWT-токены, которая делала то же самое, что и стратегия от Passport.js, но более прозрачно и понятно для восприятия. Но, что делать с заменой JWT-токенов, было не совсем понятно. И тут встал вопрос: как создать систему авторизации, которую потом не придется переписывать, которая не будет накладывать функциональных ограничений на систему и которой мы будем удовлетворены с точки зрения безопасности.

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

Про авторизацию в целом

Если вы хорошо знакомы с процессом авторизации и аутентификации в целом, смело переходите к следующему разделу. Этот — для тех, кто только знакомится с этими понятиями.

Итак, что такое аутентификация и авторизация пользователей? В целом, это два процесса, которые происходят при каждом запросе на какой-то ресурс, чтобы определить:

• кто делает этот запрос;
• есть ли у него на это право.

Предположим, вам скинули ссылку на папку в Google Drive. Вы по ней переходите. Чтобы сервер Google понял, что у вас есть к ней доступ, ему нужно сначала определить, кто вы. Этот процесс называется аутентификацией. Самый простой способ — перенаправить вас на страницу с вводом логина и пароля, дождаться, пока вы введете данные, и продолжить начатое. Однако вы ведь не вводите логин/пароль каждый раз, когда хотите войти в Drive? Это возможно, так как при первом входе Google отправляет вам в cookies сгенерированный токен доступа. Это просто строка, которую ваш браузер сохраняет в сторедж и при каждом следующем запросе автоматически отправляет все cookies, которые ранее были получены от Google. И в таком случае Google уже аутентифицирует вас не по логину и паролю, а по токену доступа. Как и связка логин+пароль, так и токен доступа однозначно дают понять серверу, какой пользователь делает запрос.

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

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

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

Токены доступа

Итак, в прошлом разделе мы сказали, что после ввода учетных данных сервер отправляет пользователю токен в файле cookie, чтобы ему не приходилось вводить данные при каждом запросе и авторизация происходила автоматически. Что это за токен? Самое простое решение, которое приходит в голову, — отправлять в качестве токена идентификатор пользователя в системе, тогда при каждом запросе на сервере нам нужно просто запросить пользователя из базы данных по идентификатору из cookie. Но тогда, если пользователь узнает идентификатор другого человека, например зайдет на его профиль и увидит в URL-параметрах (сложно представить, что кто-то создаст такую «безопасную» систему, но все же), тогда первый пользователь сможет выдать себя за второго и авторизоваться от его имени. Кроме того, мы не сможем отозвать токен на сервере, если нам станет известно, что он был скомпрометирован, поскольку токен — это идентификатор самого пользователя. Чтобы деактиваровать токен, нам придется удалить пользователя из системы, а нам бы этого явно не хотелось. Тут нам приходит на помощь первое возможное решение — JWT-токены, те же идентификаторы пользователя, но проапгрейденные.

JWT-токены

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

JWT-токен — это строка символов, состоящая из трех частей, разделенных точкой:

• заголовок;
• полезная нагрузка;
• подпись.

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

Итак, как это работает на практике: пользователь авторизуется на сайте с использованием учетных данных. Мы создаем для него объект (полезную нагрузку). Этот объект хешируется некоторой хеш-функцией, таким образом получается подпись. И это все мы отправляем клиенту. При получении запроса от клиента, мы также получаем в cookie сгенерированный ранее токен, который теперь нам нужно проверить на подлинность. Для этого мы возьмем вторую часть из полученного токена (полезную нагрузку) и заново ее захешируем, используя ту же хеш-функцию и тот же секретный ключ. Если на выходе мы получаем хеш, идентичный подписи в полученном токене, значит аутентификация прошла успешно. Запрос действительно отправил пользователь, чьи данные были получены в полезной нагрузке.

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

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

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

А теперь о грустном. С какими проблемами мы столкнулись при использовании JWT-токенов и почему впоследствии вообще решили от них отказаться.

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

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

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

2. Несколько сессий для одного аккаунта. Однажды в нашем приложении появилась необходимость запретить одновременный доступ к одному аккаунту с нескольких устройств. Это стандартная практика для b2b-приложений. Но хотелось сделать это без лишней боли и эксцентричных манипуляций в коде, так как к авторизации уже и так были вопросы. Оказалось, что сделать это не так просто. Одним из решений было сохранять access- и refresh-токены в базе данных для каждого пользователя и перезатирать их в случае нового логина. Но тогда теряется смысл самих JWT-токенов. Зачем мне какая-то логика по конструированию payload (полезной нагрузки), подписыванию, кодированию, повторного хеширования для проверки подлинности (а это ресурсозатратная операция), если я просто могу сгенерировать криптографически стойкую случайную последовательность, сохранить ее в базу данных и по ней проверять пользователей?

На этом моменте пришло ощущение, что это начало конца использования JWT в нашем продукте. В качестве временного решения я решил сохранять только refresh-токен в БД, таким образом давать возможность существования нескольких одновременных сессий в системе для одного аккаунта на время жизни access-токена. Это тоже не очень хорошо сказывается на впечатлении о сайте, так как если бы пользователю кидало ошибку UNAUTHORIZED сразу после создания сессии, ему было бы намного проще отследить причину. А так получилось, что его выбивает из системы через В любом случае это стало причиной обсуждений в команде и поиска новых решений.

3. Logout. Еще одна проблема заключается в том, что после выхода из системы, когда пользователь считает, что окончил свою сессию, его токены доступа и обновления продолжают жить, пока не закончится их время жизни. Чтобы решить эту проблему, мы бы могли записывать токены в списки из первого пункта. Но тогда эти списки быстро начали бы раздуваться до нежелательных размеров, чего бы тоже не хотелось.

4. Использование стандарта. Еще одна проблема более абстрактного характера, но о которой нельзя не сказать — из тех, кто использует JWT-токены, мало кто знает этот стандарт целиком. С каждой добавленной возможностью или пунктом настройки в какой-то стандарт потенциально растет количество людей, которые могут сделать ошибку в том или ином месте. Даже у Auth0 в прошлом году нашли критическую уязвимость с использованием JWT. Потому, мне кажется, этот стандарт недостаточно прост, чтобы его можно повсеместно использовать всем и не бояться, что что-то может пойти не так.

UUID

Наконец, перейдем к решению, которое оказалось на удивление удачным.

Что такое UUID (Universally Unique Identifiers)? Как и JWT-токен, это просто набор символов, но, в отличие от JWT, фиксированной длины.

M — версия UUID (на момент написания статьи всего 5).

N — вариант UUID. Не буду заострять на этом внимание. Подробнее можно почитать на вики.

Как его применить и безопасно ли это для авторизации? Итак, UUID — это просто случайный набор символов. В силу того, какое необъятное количество вариантов UUID существует, принято считать, что практически невозможно получить в одной системе два одинаковых идентификатора, потому их даже используют, как первичные ключи в сущностях БД.

Что если в нашей системе авторизации мы заменим JWT-токен на UUID? То есть на первом входе пользователя в систему будем генерировать для него два обычных UUID, сохранять их в базу данных и отдавать ему. Один — как токен доступа, второй — как токен обновления. И затем при каждом запросе пользователя на сервер, мы будем получать в cookie его токен доступа, проверять, соответствует ли он хоть одному токену, сохраненному на текущий момент в БД, если да — аутентифицировать его как пользователя, для которого в базе сохранен этот токен. Аналогично с обновлением: пользователь отправляет на сервер токен обновления на специальный эндпоинт, мы проверяем, имеется ли у нас в базе такой токен обновления, и если да, какому пользователю он соответствует.

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

Усложненная логика отзыва токенов

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

Несколько сессий для одного аккаунта

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

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

Logout

Если пользователь хочет выйти из системы, мы просто удаляем его токены из БД. Они больше не будут валидными и не смогут использоваться кем-то для входа/обновления. Profit.

Использование стандарта

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

Все проблемы, как по мне, решены в полном объеме. Получили ли мы какие-то дополнительные проблемы? За полгода, которые мы используем этот подход, я не увидел ни соринки, ни задоринки в UUID. Кроме одного.

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

UUID — secure or not secure?

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

1. Самая страшная из них — возможность с некоторой вероятностью, большей чем чистый рандом, угадывать токены, которые будут сгенерированы следующими, зная один из токенов. На практике это даст злоумышленнику возможность провернуть такой сценарий: он авторизуется в нашем приложении, получает свой токен доступа, и, зная свой токен доступа, каким-то образом угадывает токены, которые будут сгенерированы сервером клиентам сразу после него. И затем, подождав некоторое время, за которое потенциально кто-то из пользователей авторизуется в приложении, он берет предполагаемый им сгенерированный токен доступа и пытается зайти с его использованием. Если он угадает, то сможет войти в систему от имени другого пользователя. А дальше уже делать все, что душа пожелает.
2. Возможность брутфорса токенов. То есть перебора возможных вариантов сгенерированных токенов и попытки войти в систему с каждым из них.

Разберемся с первой уязвимостью и тем, опасна ли она для нас.

Всего есть пять версий UUID. Четыре из них используют неподходящие для нас варианты генерации: на основе текущего таймстемпа, MAC-адреса сервера и так далее. То есть способы генерации, при котором по одному идентификатору можно предугадать следующий с большой вероятностью.

Остановимся подробнее на версии № 4.

Почти весь идентификатор генерируется случайным образом. Только два символа установлены в определенное значение. Это первый символ третьей группы, отвечающий за версию и первый символ четвертой группы, отвечающий за тип. Он, как правило, будет иметь значение «a». Таким образом, алгоритм генерации UUID делает следующее:

1. Генерирует 30 случайных символов.
2. Превращает их в правильную форму, добавляет версию с типом и возвращает сериализированное значение.

Второй пункт довольно тривиален, самое интересное кроется в первом пункте. Генерация 30 случайных символов для UUID является процессом, при ошибке в котором вся безопасность системы накроется медным тазом. По сути, этот процесс ничем не отличается от генерации обычной последовательности случайных чисел. Так как мы можем сгенерировать случайные числа?

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

Для генерации первого числа используется начальное значение, которое передается генератору, так называемый seed. Для безопасного использования генератора критически важно, чтобы этот seed был абсолютно случайным. Даже случайная строка, предоставленная разработчиками в конфиге приложения типа lkO#93pfo)/apasdfl, не является подходящим вариантом. Считается, что человек в принципе не может сгенерировать действительно случайную последовательность. Например, random.org для генерации случайных чисел использует атмосферный шум, то есть нечто, что крайне трудно предсказать.

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

Потому источник этого seed-а и функция, генерирующая новые значения, будут определять безопасность генератора и его устойчивость к разным видам атак. Именно так работает функция Math.random, отдающая каждый раз новое случайное число. Но можем ли мы ее использовать для генерации нашего UUID?

Увы, ответ — не можем. Нам мало обычного генератора случайных чисел (pseudorandom number generator, PRNG) в криптографических целях. Чтобы препятствовать потенциальному злоумышленнику, мы должны использовать криптографически стойкий генератор случайных чисел (Cryptographically secure pseudorandom number generator, CSPRNG). Обычный PRNG не обладает особыми требованиями к безопасности, есть лишь рекомендации, в соответствии с которыми он должен делать хорошую видимость генерации равномерно распределенных случайных чисел. В свою очередь CSPRNG имеет жесткие требования, среди которых:

• проходить статистические тесты на равномерное распределение полученных значений;
• проходить тест на следующий бит, который заключается в том, что не существует алгоритма, который за адекватное время, зная первые n битов, сгенерированных генератором, позволит предсказать n+1 бит с вероятностью > 50%;
• если n подряд идущих битов, сгенерированных генератором, оказались известны злоумышленнику, у него не должно быть возможности за адекватное время вычислить предыдущие значения.

В нашем случае Math.random не соответствует ни одному из этих свойств.

Чтобы в этом убедиться, я рекомендую почитать отличную статью, которая описывает тонкости подкапотной жизни Math.random. Тут доступно объясняется, почему функция, которую используют для получения новых случайных чисел из предыдущих чисел в Math.random, совершенно непригодна для любых целей, когда нужна криптографическая стойкость. Я лишь добавлю, что seed эта функция генерирует сама, и он тоже является небезопасным. Если злоумышленник узнает seed, с которым был запущен генератор случайных чисел на сервере, это его значительно приблизит к возможности полного контроля над состоянием генератора и определения всех последующих чисел, которые будут в нем сгенерированы. Так вот, Math.random в качестве сида использует преобразованное локальное время на сервере. Таким образом достаточно узнать время, когда сервер был запущен и сделав всего несколько тысяч попыток, можно угадать сид. Посмотреть своими глазами исходники генератора, который используется для Math.random, можно тут.

Итак, мы определили, что нам нужен CSPRNG для генерации случайных UUID. Но не писать же его самим?

В Node.js есть целый встроенный модуль crypto, в котором есть необходимая функция randomUUID(). Эта функция генерирует нужный нам UUID четвертой версии. Исходники функции здесь. Сама функция ничего интересного не делает: получает набор случайных чисел из более низкоуровневой функции на С++ и представляет их в необходимом формате, осуществляя несколько проверок.

Потому, чтобы убедиться в безопасности данной функции для наших целей, нужно спуститься на несколько слоев абстракции вниз. Проанализировав исходники, становится понятно, что Node.js использует OpenSSL для получения случайных чисел для модуля crypto. OpenSSL — это большая криптографическая библиотека, которая предоставляет много криптографических примитивов. Это хорошая практика, когда такие критически важные с точки зрения безопасности функции реализовывает один поставщик, который следит за актуальностью их реализации и оперативно их обновляет в случае обнаружения какой-то уязвимости. А все остальные, например поставщики стандартных библиотек языков программирования, просто используют готовые функции OpenSSL через API.

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

Чтобы убедиться в безопасности, изучим эту функцию. Она реализует один из методов, описанных в этом документе центра стандартизации США. Если вы намерены глубже разобраться в теме, этот документ — одно из лучших руководств. В нем даны рекомендации по построению генераторов. Реализация OpenSSL следует этому документу.

Всего есть два метода построения генераторов. Это использование хеш-функций и использование блочных шифров. Оба метода применяются в разных условиях, и это тема для отдельной статьи. В OpenSSL же используется первый метод, называемый HMAC_DRBG, который использует некоторую хеш-функцию. Эта хеш-функция (в коде md — message digest) может быть предоставлена клиентом (в нашем случае Node.js). Если клиент ее не предоставляет, берется дефолтное значение. В текущей версии OpenSSL дефолтным является SHA256. Node ничего не передает в OpenSSL, потому библиотека будет использовать именно SHA256.

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

Но, поскольку их имеется ограниченное количество, OpenSSL на основе этих данных начинает генерировать псевдослучайные числа, используя HMAK_SHA256 (обратите внимание, в названии алгоритма сначала пишется сам алгоритм, а потом хеш-функция, которая используется. Точно также это мог бы быть HMAK_RIPEMD-160, HMAK_MD5 или любая другая реализация, если бы, к примеру, Node.js ее предоставила OpenSSL). Итак, OpenSSL берет сид и хеширует его, используя HMAK_SHA256, таким образом получая первую порцию псевдослучайных данных. Затем отдает ее вызывающему процессу, а также обновляет свое состояние:

• сохраняет полученное значение хеша как текущее значение генератора;
• обновляет счетчик энтропии. Когда этот счетчик достигнет граничного значения (через n запросов на псевдослучайные числа), OpenSSL запросит у ОС новые значения энтропии для минимизации вероятности деградации процесса генерации.

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

Да, SHA256 считается безопасной с точки зрения криптографии. Об этом детальнее можно почитать, например, в этой статье. Мы в эти детали вдаваться не будем.

Подытоживая, можно сказать, что UUID, которые генерирует нам модуль crypto, являются безопасными к разным интерполяционным атакам. Если же вы пишите не на Node.js, вам нужно найти в документации к вашему языку, какую хеш-функцию использует его генератор случайных чисел. И затем загуглить статус этой функции. Если это, например, xorshift128+, как в случае с Math.random в стандарте JS, то вы довольно быстро найдете информацию о том, что данный алгоритм не является криптографически стойким, значит, он не может использоваться. Если это что-то вроде SHA256 — это то, что вам нужно. Как же быть со второй уязвимостью?

Тут все намного проще. Просто представим, сколько возможных значений UUID 4 версии существует. Их 16^30 ~ 2^120. Это число мало с чем можно сравнить, настолько оно огромно. Если предположить, что у нас в системе 100 тысяч пользователей, которые одновременно взаимодействуют с системой и имеют токены доступа, то если сгенерировать миллион токенов и попробовать с каждым из них авторизоваться, то вероятность угадать хотя бы один токен будет (1.3e+25)%, то есть практически равна нулю. Кроме того, на уровне инфраструктуры мы должны ограничивать количество возможных запросов за единицу времени. А если учесть, что все токены должны быть проверены в ограниченный промежуток времени, так как потом токены, которые злоумышленник уже проверял, могут задействоваться, а те, которые он только собирается проверить — заэкспайрятся. Кроме того, их генерация — тоже не быстрая операция (HMAK_SHA256 требует вычислительных ресурсов для работы), поэтому вероятность угадать за адекватное время хотя бы один токен практически равна 0.

Подытоживая все вышесказанное, хочу также отметить, что хоть UUID и выглядит теоретически безопасным способом, есть случаи, когда не стоит его применять на практике. Это в первую очередь касается приложений, которые во время своего жизненного цикла будут проходить разные аудиты безопасности, информационные аудиты и так далее. Аудитор может просто не одобрить подобный способ авторизации, сославшись на то, что он раньше такого не видел, потому он не уверен в безопасности. И пока вы будете его уверять в обратном, он уже оформит вам негативную оценку.

Реализация

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

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

Для начала создадим базовое приложение Nest.js и удалим все ненужные файлы.

Так выглядит наш проект на старте. Для демонстрационных целей упростим способ хранения данных и вместо БД просто будем писать в объект. В файле permission.ts перечислим доступные права в нашей системе:

export enum Permission

Опишем две сущности: для пользователя и продукта. Тут все тривиально. Покажу пример для пользователя:

import < Permission >from '../permission'; export class User < constructor( public userId: string, public username: string, public password: string, public permissions: Permission[], ) <>>

Теперь опишем сервис для хранения наших данных:

import < User >from ‘./entities/user’; import < Product >from ‘./entities/product’; export class StorageService

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

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

import < SetMetadata >from '@nestjs/common'; export const Public = () => SetMetadata('isPublic', true); export const Permissions = (. permissions: Permission[]) => SetMetadata('permissions', permissions);

И теперь опишем контроллер, который будет обрабатывать клиентские запросы:

import < Body, Controller, Get, Post >from '@nestjs/common'; import < StorageService >from './data-storage/storage.service'; import < Product >from './data-storage/entities/product'; import < Permission >from './data-storage/permission'; import < Permissions >from './auth/authorization/permissions.decorator'; @Controller() export class AppController < constructor(private storageService: StorageService) <>@Get() @Permissions(Permission.READ) getProducts() < return this.storageService.products; >@Post() @Permissions(Permission.WRITE) updateProduct(@Body() product: Partial) < const oldProduct = this.storageService.products.find( (< productId >) => productId === product.productId, ); oldProduct.productTitle = product.productTitle ?? oldProduct.productTitle; oldProduct.price = product.price ?? oldProduct.price; oldProduct.amount = product.amount ?? oldProduct.amount; return < success: true >; > >

Пришло время делать авторизацию. Общая схема такая:

Сразу нужно сказать о том, что у нас будет три возможных варианта аутентифицировать пользователя:

• через username + password;
• через accessToken;
• через refreshToken.

Давайте сначала создадим аутентификацию через username + password. Мы будем использовать гварды. Это специальные мидлвары, которые предназначены для авторизации пользователей и запрета выполнения действий, на которые у них нет разрешений.

import < CanActivate, ExecutionContext, Injectable, UnauthorizedException, >from '@nestjs/common'; import < StorageService >from '../../storage.service'; @Injectable() export class CredentialsAuthenticateGuard implements CanActivate < constructor(private readonly storageService: StorageService) <>async canActivate(context: ExecutionContext): Promise  < const request = context.switchToHttp().getRequest(); const < username, password >= request.body; const user = await this.storageService.users.find( (< username: savedUsername >) => savedUsername === username, ); if (!user || user.password !== password) throw new UnauthorizedException(); request.user = user; return true; > >

Все, что делает этот гвард — получает учетные данные из тела запроса, проверяет их на соответствие одной из записей в хранилище юзеров и, если все правильно, записывает полученного пользователя в поле user в запросе (так делать очень плохо, это «привет» из эпохи мидлваров express, лучше как минимум использовать поле с символьным ключом, а как максимум — что-то вроде промежуточного хранилища на WeakRef, но мы так делаем для упрощения, чтобы потом была возможность быстро получить пользователя в контроллере). В противном случае кидаем ошибку.

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

import < Controller,Post, UseGuards >from '@nestjs/common'; import < CredentialsAuthenticateGuard >from './authentication/credentials.authenticate.guard'; @Controller('auth') export class AuthController < @Post('login') @Public() @UseGuards(CredentialsAuthenticateGuard) login() <>@Post('logout') logout() <> @Post('refresh-token') refreshToken() <> >

Как видите, с помощью декоратора @UseGuards (CredentialsAuthenticateGuard) мы применили к эндпоинту на логин созданный ранее гвард. Теперь nest будет вызывать метод нашего гварда перед тем, как начать обработку запроса. Обратите внимание, что метод обозначается декоратором Public, так как к нему имеет доступ любой пользователь.

После того как пользователь будет аутентифицирован, нам нужно отдать ему в cookie две пары токенов: access и refresh. Перед этим мы их сгенерируем и сохраним на сервере.

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

• в реляционной базе данных, прямо рядом с данными пользователей;
• в памяти, в объект;
• в in-memory БД типа redis.

Давайте подумаем, какой вариант выбрать. Если мы будем хранить токены в реляционной БД, то получим слишком большие временные издержки, так как нам при каждом запросе в систему нужно будет сделать FULL SCAN таблицы с пользователями, чтобы проверить наличие полученного токена доступа в запросе. Сразу отпадает.

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

Остается третий вариант. Хорошо ли? Все хранится в памяти, потому времени на запросы потребуется в разы меньше, чем с реляционной БД. При этом токены отвязаны от приложения. Потому система будет масштабируемой, и нам не придется разлогинивать пользователей при редеплое приложения (хорошо бы настроить blue-green deploy, но если его нет, то проблема будет очень заметной). Выбор очевиден. Выбираем in-memory БД. В качестве примера возьмем redis. Кроме того, redis позволяет удобно установить TTL, что позволит работать с недолговечными токенами.

Теперь нужно продумать, как мы будем хранить токены в redis.

Конечно, нам нужно сохранить пары:

• accessToken → userId;
• refreshToken → userId.

чтобы понять, какому пользователю отвечает полученный токен в запросе. Достаточно ли этого? Не совсем, так как для обеспечения логаута пользователей нам нужно уметь по идентификатору пользователя получить оба токена, чтобы удалить их из redis, потому дополнительно мы будем хранить пару:

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

import < Injectable >from '@nestjs/common'; import < RedisService >from 'nestjs-redis'; import < Redis >from 'ioredis'; @Injectable() export class AuthCacheService < public readonly redisClient: Redis; constructor(redisService: RedisService) < this.redisClient = redisService.getClient(); >async setTokens( userId: string, accessToken: string, refreshToken: string, accessTokenExpire: number, refreshTokenExpire: number, ) < await this.redisClient.set(`access-token:$`, userId); await this.redisClient.set(`refresh-token:$`, userId); await this.redisClient.hset(`usr:$`, < refreshToken, accessToken >); await this.redisClient.expire( `access-token:$`, accessTokenExpire, ); await this.redisClient.expire( `refresh-token:$`, refreshTokenExpire, ); await this.redisClient.expire(`usr:$`, refreshTokenExpire); > async getUserIdByAccessToken(accessToken) < return this.redisClient.get(`access-token:$`); > async getUserIdByRefreshToken(refreshToken) < return this.redisClient.get(`refresh-token:$`); > async deleteCache(userId: string) < const < accessToken, refreshToken >= await this.redisClient.hgetall( `usr:$`, ); await this.redisClient.unlink( `access-token:$`, `refresh-token:$`, `usr:$`, ); > >

Теперь опишем сервис, который будет делать всю работу по генерации, сохранении токенов и оформлении их в виде cookies (для простоты будем создавать cookies в виде plain строк. Для импрува это можно вынести в отдельный сервис, там типизировать ответ и отдавать не строки, а сконструированные объекты. И затем их обрабатывать где нужно):

import < Injectable >from '@nestjs/common'; import < randomUUID >from 'crypto'; import < ConfigService >from '../system/config/config.service'; import < AuthCookiesService >from './auth.cookies.service'; import < AuthCacheService >from './auth.cashe.service'; @Injectable() export class AuthService < constructor( private readonly configService: ConfigService, private cookiesService: AuthCookiesService, private authCacheService: AuthCacheService, ) <>private static getExpireDate(seconds: number): Date < return newDate(newDate(Date.now() + seconds * 1000).toUTCString()); >async createAndSaveTokenPair(userId: string) < const accessToken = randomUUID(); const accessTokenExpire = this.configService.tokens.accessTokenExpire; const accessTokenExpireDate = AuthService.getExpireDate(accessTokenExpire); const accessTokenCookie = `Authentication=$; Path=/; Expires=$; HttpOnly` this.cookiesService.getAccessTokenCookie( accessToken, accessTokenExpireDate, ); const refreshToken = randomUUID(); const refreshTokenExpire = this.configService.tokens.refreshTokenExpire; const refreshTokenExpireDate = AuthService.getExpireDate(refreshTokenExpireDate); const refreshTokenCookie = `Refresh=$; Path=/api/auth/refresh-token; Expires=$; HttpOnly` await this.authCacheService.deleteCache(userId); await this.authCacheService.setTokens( userId, accessToken, refreshToken, accessTokenExpire, refreshTokenExpire, ); return < accessTokenCookie, refreshTokenCookie, accessTokenExpireDate >; > >

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

На что тут важно обратить внимание:

• мы обязательно ставим флаг httpOnly, который обеспечивает нам защиту токенов в браузере, не давая читать их js-коду. Это важно в случае использования third-party библиотек на клиенте;
• ограничиваем область действия refreshToken только на эндпоинт по рефрешу. Если мы этого не сделаем, он будет отправляться при запросах на все эндпоинты. И тогда в нем не будет смысла, так как его можно будет украсть с той же вероятностью, что и токен доступа;
• ставим время жизни токена, чтобы у клиента исчезли cookies тогда же, когда они исчезнут на сервере.

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

export const GetUser = createParamDecorator((_, request) =>

Этот декоратор просто отдает пользователя из полученного объекта запроса.

Теперь обновим метод login в контроллере:

@Post('login') @UseGuards(CredentialsAuthenticateGuard) async login(@GetUser() < userId >, @Res() response: any) < const < accessTokenCookie, refreshTokenCookie, accessTokenExpireDate >= await this.authService.createAndSaveTokenPair(userId); response.header('Set-Cookie', [accessTokenCookie, refreshTokenCookie]); return response.send(< accessTokenExpireDate >); >

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

Итак, логин пользователей через пароль мы закончили. Дело за малым.
Опишем наш основной гвард. Сначала он аутентифицирует пользователя по токенам из cookies, потом проверит наличие необходимых прав для выполнения желаемого действия. Для прозрачности кода это должно быть два разнесенных гварда. Затем объединенных третьим гвардом. Однако для простоты, мы все напишем в одном:

import < CanActivate, ExecutionContext, ForbiddenException, Injectable, UnauthorizedException, >from '@nestjs/common'; import < Reflector >from '@nestjs/core'; import < AuthCacheService >from './auth.cashe.service'; import < StorageService >from '../../storage.service'; @Injectable() export class AuthGuard implements CanActivate < constructor( private reflector: Reflector, private authCacheService: AuthCacheService, private storageService: StorageService, ) <>async canActivate(context: ExecutionContext): Promise < if (this.reflector.get('isPublic', context.getHandler())) return true; const request = context.switchToHttp().getRequest(); const userId = await this.authCacheService.getUserIdByAccessToken( request?.cookies?.Authentication, ); const user = await this.storageService.users.find( (< userId: savedUserId >) => savedUserId === userId, ); if (!user) throw new UnauthorizedException(); const expectedPermissions = request.user.permissions; const needed = this.reflector.get('permissions', context.getHandler()); needed.forEach(needed => < if (!expectedPermissions.includes(needed)) throw new ForbiddenException(); >); return true; > >

Наш гвард будет проверять наличие специального флага Public у вызываемого эндпоинта. Если он имеется, то будет пропускать юзеров дальше без проверок, иначе сначала запустит процесс аутентификации через UUID-токен, потом проверит наличие прав и вернет результат. Если у нас что-то пойдет не так, будет выкинута ошибка, которую Nest.js вернет пользователю.

Для того чтобы этот гвард стал глобальным гвардом, то есть запускался при каждом запросе на сервер, кроме тех эндпоинтов, на которых установлены другие гварды, нужно в любом модуле, например app.module, определить гвард с использованием APP_GUARD константы, импортированной из @nestjs/core.

Теперь сделаем возможность обновлять токен доступа. По сути, все, что нам нужно — это чуть подправить гвард (доставать cookie из другого поля и вызывать другой метод для получения идентификатора пользователя из кеш-сервиса). Для самого процессинга обновления у нас уже есть метод createAndSaveTokenPair. Прелесть заключается в том, что он полностью покрывает функциональность обновления. Удаляет старые токены, генерирует новые, сохраняет их в redis и отдает токены в виде cookies.

Гвард для рефреша:

import < CanActivate, ExecutionContext, Injectable, UnauthorizedException, >from '@nestjs/common'; import < AuthCacheService >from '../auth.cashe.service'; import < StorageService >from '../../storage.service'; @Injectable() export class RefreshTokenGuard implements CanActivate < constructor( private authCacheService: AuthCacheService, private storageService: StorageService, ) <>async canActivate(context: ExecutionContext): Promise < const request = context.switchToHttp().getRequest(); const userId = await this.authCacheService.getUserIdByRefreshToken( request?.cookies.Refresh, ); const user = await this.storageService.users.find( (< userId: savedUserId >) => savedUserId === userId, ); if (!user) throw new UnauthorizedException(); request.user = user; return true; > >

Для большей переиспользуемости кода, мы могли бы добавить опциональный аргумент в метод canActivate глобального гварда — isRefresh, который по умолчанию будет false. И все, что бы делал RefreshTokenGuard — вызывал бы canActivate в UuidAuthenticateGuard со значением isRefresh в true.

Сам метод refreshToken в контроллере аналогичный login-y.

И теперь сделаем логаут. Для этого опишем необходимый метод в auth сервисе:

async logout(userId: string) < await this.authCacheService.deleteCache(userId); const accessTokenCookie = `Authentication=; Path=/; Expires=$`; const refreshTokenCookie = `Refresh=; Path=/api/v1/auth/refresh-token; Expires=$` return < accessTokenCookie, refreshTokenCookie >; >

Он удаляет необходимые записи из redis и очищает cookies у пользователя: устанавливает их время жизни в 0 (они сразу окажутся заекспайреными и перезатирает их пустой строкой).

На этом реализация логики с UUID-авторизацией окончена.

Всем спасибо за внимание.

Пожалуй, самое лучшее, что каждый из нас может вынести из этой статьи это мнение коллег по теме.

Поэтому обязательно включайтесь в дискуссию в комментариях, особенно если вам есть что сказать.

Буду рад вопросам и замечаниям ��

�� Подобається Сподобалось 9

До обраного В обраному 9

Я — айтишник, я не хочу много знать

За последнее время мне довелось провести немало технических собеседований на позицию DevOps инженера, в связи с чем появилась идея формализовать полученные выводы в этой статье. Хочу поделиться своими наблюдениями, субъективным мнением, и задать самому себе вопросы, ответы на которые, возможно, мне помогут получить читатели данной статьи.

Я понимаю, что под определение так называемого DevOps инженера от компании к компании подпадает очень разный набор навыков, следовательно, требования также будут заметно варьироваться. Поэтому попробую описать что такое DevOps инженер, или SRE (как мне привычнее) для меня в рамках нынешней организации: специалист, поддерживающий инфраструктуру проекта на всех уровнях, реализующий автоматизацию инфраструктуры, процессов разработки и тестирования, в некоторой степени DBA, конечно SRE и евангелист DevOps культуры. Так как цель статьи в другом, то не хотелось бы тут размышлять на тему того, кто такой DevOps инженер, существует ли он, маркетинговый ли это термин и вот это вот всё, оставим этот холивар. Я думаю, что в основном понятно, о каких специалистах я говорю.

Я являюсь тимлидом команды именно таких инженеров. Мы не профилируемся внутри команды по направлениям, каждый занимается бóльшей частью из перечисленного.

Пару слов о кандидатах

Встречают по одежке. Одежкой в нашем случае является резюме соискателя.

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

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

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

В рамках технического интервью, проводимых для поиска новых специалистов, я общаюсь с кандидатами, разделяя разговор на два больших блока: фундаментальные темы (операционные системы, сети, базы данных, методологии, точечно прочие компьютерные науки) и инструментарий (здесь может быть всё что угодно, Ansible, Terraform, Helm, Kubernetes, контейнеры, скриптинг, реализация конкретной небольшой задачи в определенных условиях и так далее). В среднем, общаемся в районе полутора часов, за которые я прихожу всё чаще к тем выводам, о которых буду рассказывать далее, и которые подчеркивают тему данной статьи.

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

Зачем мне что-то знать про память, всё же в кубере

Это та мысль, которую в разных формулировках я слышу очень часто от соискателей. Приходим мы к этому умозаключению после того, как я задаю свой первый вопрос про то, сколько памяти занимает процесс с указанным PID (кандидату демонстрируется скриншот или экран с выводом top). 80% соискателей с опытом администрирования nix систем не знают ответ, теряются или говорят очень странные вещи, 10% без объяснения выбора способны указать на колонку RES, и оставшиеся с разным успехом могут поговорить и порассуждать про виртуальное адресное пространство, разделяемую память, OOM, оверкоммиты, стэки, кучи и так далее.

Приведенный вопрос, как и любой другой в рамках собеседования, может получить множественное развитие как в глубину, так и в ширину, но происходит это крайне редко. Не совсем понятно, каким образом такой инженер выставляет адекватные реквесты/лимиты приложению в кубере, каким образом задаёт max-old-space-size для V8 (и делает ли это вообще). Может быть вопрос действительно лишний (пусть не всё, но большинство приложений же в кубере) и морально устарел?

Сети. Это всегда было не моё, а в облаках оно вообще не актуально

Следующая частая формулировка, которая появляется после вопросов про понимание, например, маски подсети или TCP-сессии. То есть инженер работает с кластерными системами, с кубером, наливает ансиблом большие группы узлов, а сети, получается, это что-то лишнее, недосягаемое? Видимо, во всем многообразии «сетевых» процессов вряд ли что-то может пойти не так, а в случае чего, лучше, наверное, нанять отдельного специалиста, который умеет запускать ping, traceroute и dig, да ещё и понимать их выхлоп.

Вряд ли же придётся заниматься дебагом NAT в облаках при множественных подключениях изнутри (при наличии единственного IP адреса на облачном маршрутизаторе), вряд ли нужно будет разбираться, почему пакетики из одного региона страны не доходят в облако до приложения, вряд ли понадобится VPN до API облачного кубера. И ведь действительно, вопросы сетевого взаимодействия в 2023-ем уже могли изжить себя?

HTTP GET используется только для получения информации

Это 90% ответов на просьбу сравнить GET и POST методы. Мы говорим тут про GET и POST как таковые, не привязываясь, например, к CRUD для REST. Возможно, понимать суть и отличие данных методов сегодня действительно не нужно, ведь всегда есть документация к API, а разработчик никогда не реализует метод против стандартов?

Почему у вас нет Argo CD?

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

Другим ярчайшим и популярным примером про неразрывность инструментов и методологий, как мне кажется, является разговор про CI/CD. Зачастую, CI/CD — это Gitlab CI, Teamcity или Jenkins, а не методологии, решающие конкретный список проблем/задач в процессах разработки, для удобной реализации которых есть готовые, ранее перечисленные инструменты. Кажется, пришло время внедрять Argo CD, мы же GitOps делаем?

Приведенные примеры подчеркивают нежелание большого количества нынешних специалистов погружаться в вопрос и разбираться в теме, что не может радовать. Бывали случаи, когда кандидаты не просто показывали незнание по тому или иному вопросу, а вступали в конфликт о том, что не должно быть таких, как мы задаём, глубоких вопросов на собеседовании DevOps инженеров, не должно быть бóльшей части затронутых тем. И всё бы ничего, но расстраивает факт отстранения работников интеллектуального труда от своей непосредственной деятельности, не желая о ней думать. Такое происходит конечно же не только в рамках DevOps инженеров, а распространяется и на другие направления, что я могу наблюдать, общаясь с соискателями на позиции бэкенд разработчиков и тестировщиков.

По описанным выше вопросам становится понятно, что ничего из ряда вон мы не требуем, нормальные инженерные вопросы, которые с разных сторон пытаются раскрыть кандидата. Мы не гоняем по алгоритмам, не просим спроектировать нагруженный онлайн видео сервис в масштабах планеты (хотя, системный дизайн был бы классным модулем), да и не просим тонко под задачу затюнить СУБД, но как ни крути, только лишь опыт использования облачного K8s вместе с Ansible на несколько узлов и деплой всего через Gitlab CI, не является для нас достаточным, как уже должно быть понятно из описания в начале статьи.

Я понимаю, что далеко не везде желаемые мной запросы к кандидатам. На рынке немало мест, на которых поверхностное понимание инструментария является достаточным, а какие-то более глубокие проблемы решают местные гуру. Может ли это говорить о том, что ИТ как сфера приходит к более четкому квалификационному разделению? Может ли это говорить о том, что насыщения рынка соискателями, владеющих лишь инструментарием, станет со временем трендом и стоит ли переживать на этот счет? И да, ни в коем случае не хочу сказать, что я тут один тут стою в пальто белом, я всего лишь рассуждаю “вслух” о сложившейся вокруг меня ситуации.

Выводы

• Резюме не имеет ничего общего с реальными знаниями и навыками соискателя.
• Многих интересуют только зарплаты, без реального увлечения технологиями.
• Фундаментальные, нетленные знания пугают соискателей, всерьёз не воспринимаются как необходимые, иногда вызывают улыбки.
• Большинство соискателей видят роль DevOps инженера следующим образом: YAML, какая-нибудь технология контейнеризации (на уровне пользователя), какая-нибудь система оркестрации (на уровне пользователя), Terraform, Ansible.
• Эти же соискатели не согласны с тем, что DevOps инженер это: основы операционных систем, основы баз данных, основы сетей, основы распределенных систем, любые другие основы, не связанные с верхнеуровневым инструментарием и перекладыванием конфигов, для получения очередной абстракции.

В чем я могу ошибаться

• Я считаю себя энтузиастом в ИТ, для меня это не только работа, но и одно из увлечений, в связи с чем могут проявляться завышенные ожидания к соискателям.
• Субъективное ощущение реальности и рынка, выстраивают неверный набор запросов и уровень ожидаемых ответов. Мой личный и сторонний (коллеги, статьи и т. п.) опыт собеседований в крупные и небольшие ИТ компании, склоняет меня в сторону тех примеров, в которых присутствовал более жесткий отбор с более высокими требованиями.
• Наличие слишком малой, нерепрезентативной выборки, приводящей к ошибочным умозаключениям о соискателях.

Вопросы без ответа

• Не слишком ли широкий спектр обязанностей падает на каждого инженера в нашей команде, может быть нужно делиться по профилям?
• Может быть я неправильно (или крайне неудачно) подобрал блоки вопросов для собеседования?
• Что мы можем улучшить, как ужесточить фильтр на этапе отбора резюме и первичного общения с HR для обеспечения наиболее продуктивного общения на всех последующих этапах, но при этом не отпугнуть кандидата?

Логика сознания. Часть 12. Поиск закономерностей. Комбинаторное пространство

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

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

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

Задача контекстного сдвига текстовой строки

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

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

Фрагмент текста. Числами обозначен циклический идентификатор позиции. Период идентификатора K=10. Вертикальными линиями выделено одно из положений скользящего окна. Размер окна N=6

Основная идея такого представления в том, что если размер окна N меньше периода идентификатора K, то набор пар «буква — идентификатор позиции» позволяет однозначно записать строку внутри скользящего окна. Ранее похожий метод записи мы упоминали, когда говорили о том, как можно закодировать звуковую информацию. Подставьте вместо букв коды неких условных фонем, и вы получите запись звукового фрагмента.

Введем систему понятий, позволяющую описать все, что появляется в скользящем окне. Для простоты не будем делать разницы между заглавными и строчными буквами и не будем учитывать знаки препинания. Так как потенциально любая буква может встретиться нам в любой позиции, то нам понадобятся все возможные сочетания букв и позиций, то есть 26 x K понятий. Условно эти понятия можно обозначить как

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

Сопоставим каждому понятию некий разреженный бинарный код. Например, если взять длину кода в 256 бит и отвести 8 бит для кодирования одного понятия, то кодирование буквы «a» в различных позициях будет выглядеть как показано на рисунке ниже. Напомню, что коды выбираются случайным образом, и биты у них могут повторяться, то есть одни и те же биты могут быть общими для нескольких кодов.

Пример кодов буквы a в позициях от 0 до 9. Бинарные вектора показаны вертикально, единицы выделены горизонтальными светлыми линиями

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

На рисунке ниже приведен пример того, как будут выглядеть коды понятий и суммарный код фрагмента для предыдущего примера.

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

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

Изменение кодировки текста при разном начальном смещении

Первому случаю будет соответствовать описание

Второй случай будет записан, как

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

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

Чтобы иметь возможность сравнивать фрагменты текста инвариантно к их смещению, надо ввести пространство контекстов смещений. Для этого понадобится K контекстов. Каждый контекст будет соответствовать одному из вариантов возможного начального смещения.

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

Контекстными преобразованиями в случае с текстом будут правила изменения понятий при переходе к соответствующему контексту смещению. Так, например, для контекста с нулевым смещением правила переходов будут переходами сами в себя

Для контекста со смещением на 8 позиций при длине кольцевого идентификатора K=10, что соответствует нижней строке примера с рисунка выше, правила будут иметь вид
a0→a8, a1→a9, a2→a0⋯z9→z7

При таких правилах в контексте со смещением 8 описание окна из первой строки примера перейдет в описание окна из второй строки, что, собственно, вполне очевидно и без долгих пояснений

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

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

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

Код исходной строки и ее смещения

Так как у нас есть алгоритм пересчета описаний, мы без труда можем для любой строки получить ее исходный бинарный код (в нулевом контексте) и код в смещении на одну позицию (в контексте «1»). Взяв длинный текст, мы можем создать сколь угодно много таких примеров, относящихся к одному смещению.

А теперь возьмем сгенерированные примеры и представим, что перед нами черный ящик. Есть бинарное описание на входе, есть бинарное описание на выходе, но нам ничего не известно ни про природу входного описания, ни про правила, по которым происходит преобразование. Можем ли мы воспроизвести работу этого черного ящика?

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

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

В чем сложность?

Когда я учился в институте, у нас была очень популярна игра «Быки и коровы». Один игрок загадывает четырехзначное число без повторов, другой пытается его угадать. Тот, кто пытается, называет некие числа, а загадавший сообщает, сколько в них быков, то есть угаданных цифр, стоящих на своем месте, и сколько коров, цифр, которые есть в загаданном числе, но стоят не там, где им положено. Вся соль игры в том, что ответы загадавшего не дают однозначной информации, а создают множество допустимых вариантов. Каждая попытка порождает такую неоднозначную информацию. Однако совокупность попыток позволяет найти единственно верный ответ.

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

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

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

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

Для борьбы с комбинаторным взрывом требуется «комбинаторный лом». Есть два инструмента, позволяющие на практике решать сложные комбинаторные задачи. Первый – это массовое распараллеливание вычислений. И тут важно не только иметь большое количество параллельных процессоров, но и подобрать такой алгоритм, который позволяет распараллелить задачу и загрузить все доступные вычислительные мощности.

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

Комбинируя эти два принципа, можно построить решение и нашей задачи.

Комбинаторное пространство

Возьмем входной битовый вектор и пронумеруем его биты. Создадим комбинаторные «точки». В каждую точку сведем несколько случайных битов входного вектора (рисунок ниже). Наблюдая за входом, каждая из этих точек будет видеть не всю картину, а только ее малую часть, определяемую тем, какие биты сошлись в выбранной точке. Так на рисунке ниже крайняя слева точка с индексом 0 следит только за битами 1, 6, 10 и 21 исходного входного сигнала. Создадим таких точек достаточно много и назовем их набор комбинаторным пространством.

Комбинаторное пространство

В чем смысл этого пространства? Мы предполагаем, что входной сигнал не случаен, а содержит определенные закономерности. Закономерности могут быть двух основных типов. Что-то во входном описании может появляться несколько чаще чем другое. Например, в нашем случае отдельные буквы появляются чаще чем их сочетания. При битовом кодировании это означает, что определенные комбинации битов встречаются, чаще чем другие.

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

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

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

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

Конечно, если делать размеры точек слишком узкими, то есть количество битов в точках выбирать приблизительно равным тому, сколько битов ожидается в закономерности, то размеры комбинаторного пространства начнут стремиться к количеству вариантов полного перебора возможных гипотез, что возвращает нас к комбинаторному взрыву. Но, к счастью, можно увеличивать обзор точек, снижая их общее количество. Это снижение не дается бесплатно, комбинаторика «переносится в точки», но до определенного момента это не смертельно.

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

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

Кластеры рецепторов

Как искать закономерности в комбинаторном пространстве? Каждая точка видит свой фрагмент входного вектора. Если в том, что она видит, оказывается достаточно много активных битов, то можно предположить, что то, что она видит, и есть какая-либо закономерность. То есть, набор активных битов, попадающий в точку, можно назвать гипотезой о наличии закономерности. Запомним такую гипотезу, то есть зафиксируем набор активных битов, видимых в точке. В ситуации, показанной на рисунке ниже, видно, что в точке 0 надо зафиксировать биты 1, 6 и 21.

Фиксация битов в кластере

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

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

• длина входного вектора — 256 бит;
• длина выходного вектора – 256 бит;
• отдельная буква кодируется 8 битами;
• длина строки — 5 символов;
• количество контекстов смещения — 10;
• размер комбинаторного пространства – 60000;
• количество битов, пересекающихся в точке – 32;
• порог создания кластера – 6;
• порог частичной активации кластера — 4.

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

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

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

Обучение. Консолидация памяти

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

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

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

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

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

Хроника частичного срабатывания кластера рецепторов

Что нас должно интересовать в этой статистике? Нам важно, какие биты чаще других срабатывают совместно. Не спутайте это с самыми частыми битами. Если посчитать для каждого бита частоту его появления и взять самые распространенные биты, то это будет усреднение, которое совсем не то, что нам надо. Если в точке сошлись несколько устойчивых закономерностей, то при усреднении получится средняя между ними «не закономерность». В нашем примере, видно, что 1,2 и 4 строки похожи между собой, также похожи 3,4 и 6 строки. Нам надо выбрать одну из этих закономерностей, желательно самую сильную, и очистить ее от лишних битов.

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

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

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

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

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

Кроме подрезки кластера надо следить за тем, чтобы была поймана именно нужная закономерность. В исходной строке смешаны коды нескольких букв, каждый из них является закономерностью. Любой из этих кодов может быть «пойман» кластером. Но нас интересует код только той буквы, которая влияет на формирование выходного бита. По этой причине большинство гипотез будут ложными и их необходимо отвергнуть. Это можно сделать по тем критериям, что частичное или даже полное срабатывание кластера слишком часто будет не совпадать с активностью нужного выходного бита. Такие кластеры подлежат удалению. Процесс такого контроля и удаления лишних кластеров вместе с их «подрезкой» можно назвать консолидацией памяти.

Процесс накопления новых кластеров достаточно быстрый, каждый новый опыт формирует несколько тысяч новых кластеров-гипотез. Обучение целесообразно проводить этапами с перерывом на «сон». Когда кластеров создается критически много, требуется перейти в режим «холостой» работы. В этом режиме прокручивается ранее запомненный опыт. Но при этом не создается новых гипотез, а только идет проверка старых. В результате «сна» удается удалить огромный процент ложных гипотез и оставить только гипотезы, прошедшие проверку. После «сна» комбинаторное пространство не только оказывается очищено и готово к приему новой информации, но и гораздо увереннее ориентируется в том, что было выучено «вчера».

Выход комбинаторного пространства

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

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

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

Пример работы комбинаторного пространства в процессе обучения (порядка 200 шагов). Сверху исходный код, в середине требуемый код, снизу код, предсказанный комбинаторным пространством

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

Пример работы обученного комбинаторного пространства. Сверху исходный код, в середине требуемый код, снизу код, предсказанный комбинаторным пространством

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

Усиление правил

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

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

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

Случайный лес

Описанный механизм позволяет найти закономерности, которые в Data Mining принято называть правилами типа «if-then». Соответственно, можно найти что-то общее между нашей моделью и всеми теми методами, что традиционно используются для решения таких задач. Пожалуй, наиболее близок к нам «random forest».

Этот метод начинается с идеи «случайных подпространств». Если в исходных данных слишком много переменных и эти переменные слабо, но коррелированы, то на полном объеме данных становится трудно вычленить отдельные закономерности. В таком случае можно создать подпространства, в которых будут ограничены как используемые переменные, так и обучающие примеры. То есть каждое подпространство будет содержать только часть входных данных, и эти данные будут представлены не всеми переменными, а их случайным ограниченным набором. Для некоторых из этих подпространств шансы обнаружить закономерность, плохо видимую на полном объеме данных, значительно повышаются.

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

Пример дерева принятия решений

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

На завершающем этапе применяется идея бустинга. Решающие деревья формируют комитет для голосования. На основании коллективного мнения создается наиболее правдоподобный ответ. Главное достоинство бустинга – это возможность при объединении множества «плохих» алгоритмов (результат которых лишь немного лучше случайного) получить сколь угодно «хороший» итоговый результат.

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

Биология обучения

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

На мембране нейрона располагается множество различных рецепторов. Большинство этих рецепторов находится в «свободном плавании». Мембрана создает для рецепторов среду, в которой они могут свободно перемещаться, легко меняя свое положение на поверхности нейрона (Sheng, M., Nakagawa, T., 2002) (Tovar K. R.,Westbrook G. L., 2002).

Мембрана и рецепторы

В классическом подходе на причинах такой «свободы» рецепторов обычно акцент не делается. Когда синапс усиливает свою чувствительность, это сопровождается перемещением рецепторов из внесинаптического пространства в синаптическую щель (Malenka R.C., Nicoll R.A., 1999). Этот факт негласно воспринимается как оправдание подвижности рецепторов.

В нашей модели можно предположить, что основная причина подвижности рецепторов – это необходимость «на лету» формировать из них кластеры. То есть картина выглядит следующим образом. По мембране свободно дрейфуют самые разные рецепторы, чувствительные к различным нейромедиаторам. Информационный сигнал, возникший в миниколонке, вызывает выброс нейромедиаторов аксонными окончаниями нейронов и астроцитами. В каждом синапсе, где испускаются нейромедиаторы, кроме основного нейромедиатора присутствует своя уникальная добавка, которая идентифицирует именно этот синапс. Нейромедиаторы выплескиваются из синаптических щелей в окружающее пространство, за счет чего в каждом месте дендрита (точках комбинаторного пространства) возникает специфический коктейль нейромедиаторов (ингредиенты коктейля указывают на биты, попадающие в точку). Те свободно блуждающие рецепторы, которые находят в этот момент свой нейромедиатор в этом коктейле (рецепторы конкретных битов входного сигнала), переходят в новое состояние – состояние поиска. В этом состоянии у них есть небольшое время (до того момента, пока не наступит следующий такт), за которое они могут встретить другие «активные» рецепторы и создать общий кластер (кластер рецепторов, чувствительных к определенному сочетанию битов).

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

Одиночный метаботропный рецептор

После объединения начинается совместная жизнь рецепторов в кластере. Можно предположить, что положение рецепторов относительно друг друга может меняться в широких пределах и кластер может принимать причудливые формы. Если допустить, что рецепторы, срабатывающие совместно, будут стремиться занять место ближе друг к другу, например, за счет электростатических сил, то получится интересное следствие. Чем ближе будут оказываться такие «совместные» рецепторы, тем сильнее будет их совместное притяжение. Сблизившись они начнут усиливать влияние друг друга. Такое поведение воспроизводит поведение фильтра Хебба, который выделяет первую главную компоненту. Чем точнее фильтр настраивается на главную компоненту, тем сильнее оказывается его реакция, когда она появляется в примере. Таким образом, если после ряда итераций совместно срабатывающие рецепторы окажутся вместе в условном «центре» кластера, а «лишние» рецепторы на удалении, на его краях, то, в принципе, такие «лишние» рецепторы могут в какой-то момент самоликвидироваться, то есть просто оторваться от кластера. И тогда мы получим поведение кластера, аналогичное тому, что описано выше в нашей вычислительной модели.

Кластеры, которые прошли консолидацию, могут переместиться куда-нибудь «в тихую гавань», например, в синаптическую щель. Там существует постсинаптическое уплотнение, за которое кластеры рецепторов могут якориться, теряя уже ненужную им подвижность. Поблизости от них будут находиться ионные каналы, которыми они смогут управлять через G-белки. Теперь эти рецепторы начнут влиять на формирование локального постсинаптического потенциала (потенциала точки).

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

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

Объединение сигналов с разных синапсов одного дендритного дерева может быть не простым логическим сложением, а быть сложнее и реализовывать какой-нибудь алгоритм хитрого бустинга.

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

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

Сон

У здорового человека сон начинается с первой стадии медленного сна, которая длится 5-10 минут. Затем наступает вторая стадия, которая продолжается около 20 минут. Еще 30-45 минут приходится на периоды третей и четвертой стадий. После этого спящий снова возвращается во вторую стадию медленного сна, после которой возникает первый эпизод быстрого сна, который имеет короткую продолжительность — около 5 минут. Во время быстрого сна глазные яблоки очень часто и периодически совершают быстрые движения под сомкнутыми веками. Если в это время разбудить спящего, то в 90% случаев можно услышать рассказ о ярком сновидении. Вся эта последовательность называется циклом. Первый цикл имеет длительность 90-100 минут. Затем циклы повторяются, при этом уменьшается доля медленного сна и постепенно нарастает доля быстрого сна, последний эпизод которого в отдельных случаях может достигать 1 часа. В среднем при полноценном здоровом сне отмечается пять полных циклов.

Можно предположить, что во сне происходит основная работа по расчистке кластеров рецепторов, накопившихся за день. В вычислительной модели мы описали процедуру «холостого» обучения. Старый опыт предъявляется мозгу, не вызывая формирования новых кластеров. Цель – проверка уже существующих гипотез. Такая проверка состоит из двух этапов. Первый — вычисление главной компоненты закономерности и проверка того, что количество битов, отвечающих за нее, достаточно для четкой идентификации. Второй – проверка истинности гипотезы, то есть того, что закономерность оказалась в нужной точке, связанной с нужным выходным битом. Можно предположить, что часть стадий ночного сна связана с такими процедурами.

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

Увидеть и оценить концентрацию белков можно через окрашивание среза мозговой ткани красителем, избирательно реагирующим на требуемый белок. Подобные наблюдения показали, что наиболее масштабные изменения для белков, связанных с памятью, происходят именно во время сна (Chiara Cirelli, Giulio Tononi, 1998) (Cirelli, 2002) (рисунки ниже).

Распределение белка Arc в теменной коре крысы после трех часов сна (S) и после трех часов спонтанного бодрствования (W) (Cirelli, 2002)

Распределение транскрипционного фактора P-CREB в корональных участках теменной коры крысы после трех часов сна (S) и в случае лишения сна на три часа (SD) (Cirelli, 2002)

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

При моделировании было видно, что количество ложных гипотез во многие тысячи раз превышает количество истинных. Так как отличить одни от других можно только временем и опытом, то мозгу не остается ничего другого, кроме как копить всю эту информационную руду в надежде найти в ней со временем граммы радия. При получении нового опыта количество кластеров с гипотезами, требующими проверки, постоянно растет. Количество кластеров, формирующихся за день и содержащих руду, которую еще предстоит обработать, может превышать количество кластеров, отвечающих за кодирование накопленного за всю предыдущую жизнь проверенного опыта. Ресурс мозга по хранению сырых гипотез, требующих проверки должен быть ограничен. Похоже, что за 16 часов дневного бодрствования кластерами рецепторов практически полностью забивается все доступное пространство. Когда наступает этот момент, мозг начинает принуждать нас перейти в режим сна, чтобы позволить ему выполнить консолидацию и расчистить свободное место. Видимо, процесс полной расчистки занимает около 8 часов. Если разбудить нас раньше, то часть кластеров останется необработанной. Отсюда происходит феномен того, что усталость накапливается. Если несколько дней недосыпать, то потом придется наверстывать упущенный сон. В противном случае мозг начинает «аварийно» удалять кластеры, что ни к чему хорошему не приводит, так как лишает нас возможности почерпнуть знания из полученного опыта. Событийная память скорее всего сохранится, но закономерности останутся невыявленными.
Кстати, мой личный совет: не пренебрегайте качественным сном, особенно если вы учитесь. Не пытайтесь сэкономить на сне, чтобы больше успеть. Сон не менее важен в обучении, чем посещение лекций и повтор материала на практических занятиях. Недаром дети в те периоды развития, когда накопление и обобщение информации идет наиболее активно, большую часть времени проводят во сне.

Быстродействие мозга

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

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

Текст приведенной программы доступен на GitHub. В коде оставлено достаточно много отладочных фрагментов, я не стал их удалять, а только закомментировал на случай, если кому-то захочется самостоятельно поэкспериментировать.

• искусственный интеллект
• машинное обучение
• биология
• смысл
• нейронные сети
• нейрон
• сознание