Това е накратко за изследователската статия „Използване на дезинфекция на входа за отказ на обслужване на регулярен израз“, публикувана на ICSE 2022. Тази работа беше ръководена от моите студенти Ефе Барлас и Син Ду. Пълният документ е тук. Те също написаха този бриф, който леко редактирах.

В тази статия използваме думата „regex“ като стенограма за „регулярен израз“.

Резюме

Регулярните изрази са често срещани в софтуера и са чудесни инструменти за справяне със задачи за обработка на низове. За съжаление, в много езици за програмиране машината за регулярни изрази по подразбиране може да консумира много изчислителна мощност. Някои регулярни изрази отнемат полиномиално или дори експоненциално време за обработка на низ въз основа на дължината на низа. Ако тази обработка се случи от страната на сървъра, тя може да изразходва значително количество ресурси. Това свойство създава заплаха за сигурността: ако нападателят знае регулярните изрази, използвани от страната на сървъра, тогава той може да изработи низове, за да задейства скъпоструващо съвпадение на регулярни изрази и да причини базиран на регулярен израз отказ на услуга (ReDoS). Например Cloudflare имаше прекъсване, базирано на регулярен израз през 2019 г., което засегна хиляди клиенти [1].

Въпреки че за хакерите е трудно да получат достъп до бекенд кода и да научат какви регулярни изрази се използват там, уеб услугите понякога публикуват регулярни изрази бекенд, за да помогнат на потребителите да разберат изискванията. Чудехме се дали това решение излага уеб услугите на ReDoS рискове.

  1. Проведохме проучване на черна кутия, за да измерим (етично) уязвимостите на ReDoS в живи уеб услуги. Ние прилагаме предположение, че логиката за дезинфекция от страна на клиента, включително регулярни изрази, е в съответствие с логиката за дезинфекция от страна на сървъра. Проучихме както HTML формуляри, така и спецификации на API. Нашият резултат показа, че регулярните изрази в спецификациите на API представляват по-голяма ReDoS заплаха. Открихме ReDoS уязвимости в няколко уеб домейна, включително домейни, управлявани от Microsoft и Amazon.
  2. За смекчаване на ReDoS, ние вярваме, че има по-добри решения от това изобщо да не се публикуват регулярни изрази [9]. Това оставя две възможности: измисляне как лесно да се превърнат опасните регулярни изрази в безопасни (изследователите все още не знаят как да направят това перфектно) или приемане на безопасен механизъм за регулярни изрази за дезинфекция на входа.

Смятаме, че вторият вариант е добър дългосрочен избор. За да помогнем на уеб услугите да преминат към безопасен механизъм за регулярни изрази и да елиминираме заплахата от ReDoS при дезинфекция на входа, ние предоставихме на инженерите лесен начин да използват безопасен механизъм за регулярни изрази – по този начин те могат да пишат каквито регулярни изрази искат и няма нужда да се притесняват за ReDoS. Като доказателство за концепцията, ние добавихме тази функция към Ajv [13]. Използвайки нашата функция [10], инженерите могат да използват безопасна система за регулярни изрази с един ред код.

Заден план

Регулярни изрази

Много софтуерни инженери използват регулярни изрази, за да проверят дали въведеното от потребителите отговаря на изискванията. Например регулярните изрази могат да се използват, за да се провери дали паролите имат както главни, така и малки букви. Друг случай на използване е спецификациите на API, за да помогнат на потребителите да разберат по-добре формата на данните на всеки API.

Небезопасни регулярни изрази и ReDoS

Някои регулярни изрази може да отнемат много време при обработка на определени низове. Това може да се случи, когато опасен регулярен израз се използва под опасна система за регулярни изрази. Може да сте любопитни какво прави един регулярен израз опасен. Това е следното: когато регулярен израз може да анализира низ по множество начини, машината може да пробва всеки един от тях, което води до проблематична времева сложност, варираща от полиномиална до експоненциална [11]. За по-подробно обяснение погледнете тази публикация.

Ако нападателят знае, че има опасни регулярни изрази в бекенда на уеб услугата, той може да създаде и изпрати низове за атака. Атаката е асиметрична — за атакуващия е евтино да изпрати низа, но на сървъра може да отнеме много време, за да го обработи. Все едно вашето малко дете разлива мляко навсякъде: отнема 1 секунда, за да разлее, но 5 минути, за да почисти. В резултат на това достъпът на други нормални потребители до тази уеб услуга може да бъде повлиян. Такава атака се нарича базиран на Regex отказ от услуга (ReDoS).

Но как е възможно нападателите да знаят за регулярните изрази, които използва определена уеб услуга? Следващият раздел ще обясни.

Две често срещани места за намиране на улики

Ако се преструваме на хакер, който се интересува какви регулярни изрази се използват в бекенда, има две общи места, където можем да намерим улики.

Първият е HTML формуляри, където могат да се използват регулярни изрази за проверка на входа, преди да бъде изпратен до бекенда на уеб услугата. В рамките на HTML формуляри има два начина за включване на проверки на регулярни изрази. Единият е да използвате атрибутите на шаблона за входен таг. Това е вградена функция на HTML [6]. Другият начин е да включите персонализиран JavaScript, който след това използва регулярни изрази за проверка на входа. Този JavaScript кодов фрагмент обикновено се задейства, когато потребителите въвеждат текстове или натискат бутона за изпращане. Уеб програмистите често използват JavaScript, за да извършват проверка на формата, защото им позволява да правят много повече от това, което позволяват вградените в HTML функции. И двата начина са показани от лявата страна на фигурата.

Второто често срещано място са спецификациите на API. Много уеб услуги имат API, към които потребителите могат да се свързват програмно. За да се уточни изискването за въвеждане, като път, формат на данните и върната стойност, на тези API, уеб услугите описват своите API в различни форми. Някои са по-небрежни, а други следват определен формат. Често използван формат се нарича OpenAPI спецификация [7]. Пример за спецификация на OpenAPI е показан от дясната страна на фигурата.

Приближаване

Нашият подход се основава на предположение: че логиката за дезинфекция от страната на клиента, включително регулярните изрази, е в съответствие с логиката за дезинфекция от страната на сървъра. Това е обичайна практика сред програмистите и също така се препоръчва от популярния уебсайт за уеб програмиране Mozilla [8]. Поради това предположение, ако можем да намерим регулярни изрази, които се използват от страната на клиента, регулярните изрази, които се използват от страната на сървъра, може да са същите. След това можем да генерираме низове, които задействат време за суперлинейно съвпадение на регулярния израз и да го изпратим на страната на сървъра. Въз основа на разликата между времената за отговор можем да определим дали регулярният израз от страна на сървъра действително е уязвим. Взехме мерки нашите експерименти да не повлияят на наличността на уеб услугата.

Намиране на регулярни изрази

Тъй като има две общи места (HTML формуляри и API спецификации) за намиране на улики, имаме два различни начина за намиране на регулярни изрази от тях. За HTML формуляри първо произволно избрахме 1000 уеб услуги от списъка Tranco Top 1M [2]. След това използвахме уеб робот, наречен Apify [3], за да обходим тези 1000 уеб услуги и да намерим уеб страници, които можем да анализираме. За тези уеб страници, които имат HTML формуляри върху тях, управлявахме автоматизиран браузър чрез OpenWPM [4]. Използвахме OpenWPM, за да попълним полетата на формуляра със стойности. Ние също така добавихме нашия маймунски код за корекция към тези свързани с регулярни изрази JavaScript функции в средата на браузъра. По време на процеса, ако се задействат някакви JavaScript функции, свързани с регулярни изрази, нашият маймунски код за корекция ще уведоми нашата база данни, която записва използвания регулярен израз и низ. Регулярните изрази, използвани в атрибутите на шаблони, се намират по-лесно. Просто анализирахме HTML кода.

За API събрахме API спецификации от онлайн директория, наречена apis.guru [12]. Анализирахме всяка спецификация и идентифицирахме регулярните изрази, които ограничават всички входни низове, посочени от поне една схема на заявка.

Откриване на суперлинейни регулярни изрази

След като намерихме всички регулярни изрази на двете места, след това ги изследвахме, за да видим колко от тях всъщност са суперлинейни (така че всъщност представляват заплаха). Използвахме най-съвременен детектор на уязвими регулярни изрази [5]. Ние определяме регулярен израз като суперлинеен, ако той показва повече от линейно увеличение на времето за съвпадение, тъй като дължината на низа за атака става по-дълга.

Опасно използване на Regex с отпечатъци

За онези уеб страници и крайни точки на API, за които беше установено, че потенциално имат суперлинейни регулярни изрази, ние ги изследвахме етично с внимателно проектиран вход. След това наблюдавахме разликата между времената за реакция и определихме дали те действително са уязвими към ReDoS или не.

Резултати и дискусия

Анализирахме спецификациите на OpenAPI на 475 домейна и HTML формуляри и JavaScript файлове на 696 домейна. 17% от домейните на API и 39% от домейните на HTML форми са използвали регулярни изрази. Интересното е, че повторната употреба на регулярни изрази е много по-често срещана в HTML формуляри, отколкото в спецификациите на API: открихме само 33 уникални регулярни израза в 4,9k атрибута на HTML модел, в сравнение с 1841 уникални регулярни израза в 2681 употреби на регулярни изрази в домейни на API.

Установихме, че използването на суперлинейни регулярни изрази е малко вероятно, тъй като само 15 домейна на API и 6 домейна на HTML форми използват суперлинейни регулярни изрази. В нашите експерименти обаче установихме отклонения във времето за реакция за 6 от 15 API домейна, 2 от които бяха големи технологични компании. Не открихме отклонения във времето за отговор в нито един от HTML домейните. Изглежда, че уеб услугите вероятно са ReDoS-уязвими, ако използват супер-линейни регулярни изрази в техните API спецификации, но размерът на извадката (N=15) е твърде малък, за да се направи убедително твърдение.

Смятаме, че по-високият риск от ReDoS за API спецификации може да бъде причинен от:

  • Генератори на кодове, базирани на API спецификация. API спецификациите са важна стъпка към проектирането на уеб услуга. Въпреки че безопасността на регулярните изрази не е основна грижа по време на фазата на спецификация, когато тази спецификация се използва за генериране на код, софтуерните инженери могат неволно да въведат ReDoS уязвимости в своята уеб услуга.
  • Инструменти, които съставят API спецификации чрез анализиране на код. Софтуерните инженери, използващи тези инструменти, може неволно да публикуват регулярните изрази, които използват в бекенда.

Лесно е да се каже на софтуерните инженери да „разработват безопасни регулярни изрази“, но за софтуерните инженери е трудно да използват този съвет на практика (защото „регексите са трудни“). В повечето случаи за инженера е много по-лесно да използва безопасен инструмент - превключване към използване на безопасна машина за регулярни изрази за прости регулярни изрази. Затова решихме да направим заявка за изтегляне към популярен инструмент за проверка на въвеждане, наречен Ajv. Ajv [13] се използва от популярния междинен софтуер, базиран на спецификация на API (генератори на кодове и валидатори) за валидиране на заявки. Нашата заявка за изтегляне, сега обединена и пусната, позволява на инженерите да изберат механизма за регулярни изрази, който желаят да използват. Тази корекция позволява на милионите зависими лица на Ajv да елиминират риска от ReDoS при дезинфекция на входа.

Заключение

ReDoS получи много внимание напоследък. Поради този интерес, ние направихме първото проучване за измерване на черна кутия на уязвимостите на ReDoS в реални уеб услуги. Нашият метод се основава на наблюдението, че санирането на входа от страна на сървъра може да бъде огледално от страна на клиента. Проверихме степента, в която суперлинейните регулярни изрази от страна на клиента могат да бъдат използвани като ReDoS уязвимости от страната на сървъра. Сравнихме два често срещани типа интерфейс: HTML формуляри (𝑁 =1000 домейна) и API (𝑁 = 475 домейна).

Резултатите за двата типа интерфейс се оказаха различни. Въпреки че регулярните изрази са често срещани и в двата типа интерфейси, регулярните изрази, които биха могли да причинят най-много проблеми, които са супер-линейни регулярни изрази, са често срещани само в API. Открихме ReDoS уязвимости в API на 6 домейна (15 поддомейна), два от които бяха големи технологични компании.

Нашите открития добавят тежест към опасенията относно рисковете от ReDoS на практика. Надяваме се, че нашите констатации мотивират компаниите да намалят своите ReDoS рискове и че нашата корекция към Ajv им дава лесен начин да го направят.

Препратки

[1] Греъм-Къминг, 2019 г. Подробности за прекъсването на Cloudflare на 2 юли 2019 г. https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

[2] Tranco Топ 1M списък. https://tranco-list.eu/

[3] Apify Web Crawler. https://apify.com/

[4] OpenWPM. https://github.com/openwpm/OpenWPM

[5] vuln-regex-детектор. https://github.com/davisjam/vuln-regex-detector

[6] HTML таг за въвеждане. https://developer.mozilla.org/en-US/docs/Web/HTML/Element/input

[7] Спецификация на OpenAPI. https://swagger.io/specification/

[8] Проверка на ограниченията на Mozilla. https://developer.mozilla.org/en-US/docs/Web/API/Constraint_validation

[9] Сигурност чрез неизвестност. https://en.wikipedia.org/wiki/Security_through_obscurity

[10] Ajv документация. https://ajv.js.org/security.html#redos-attack

[11] Николас Вайдеман, Бринк ван дер Мерве, Мартин Берглунд и Брус Уотсън. 2016. Анализиране на поведението на съпоставянето във времето на съпоставящите регулярни изрази за обратно проследяване чрез използване на неяснотата на NFA. В Международна конференция за внедряване и приложение на автомати. Спрингър, 322–334.

[12] apis.guru.

[13] Прил. https://ajv.js.org/