Распуши пингвина! Разбираем способы фаззинга ядра Linux

Ког­да я говорю об ата­ках на USB, мно­гие сра­зу вспо­мина­ют Evil HID — одну из атак типа BadUSB. Это ког­да под­клю­чаемое устрой­ство выг­лядит безобид­но, как флеш­ка, а на самом деле ока­зыва­ется кла­виату­рой, которая авто­мати­чес­ки откры­вает кон­соль и дела­ет что‑нибудь нехоро­шее.

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

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

Что такое фаззинг

Фаз­зинг — это спо­соб искать ошиб­ки в прог­раммах.

Как он работа­ет? Мы генери­руем слу­чай­ные дан­ные, переда­ем их на вход прог­рамме и про­веря­ем, не сло­малась ли она. Если не сло­малась — генери­руем новый ввод. Если сло­малась — прек­расно, мы наш­ли баг. Пред­полага­ется, что прог­рамма не дол­жна падать от неожи­дан­ного вво­да, она дол­жна этот ввод кор­рек­тно обра­баты­вать.

Кон­крет­ный при­мер: мы берем XML-пар­сер и скар­мли­ваем ему слу­чай­но сге­нери­рован­ные XML-фай­лы. Если он упал — мы наш­ли баг в пар­сере.

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

Ког­да мы начина­ем работать над фаз­зером для оче­ред­ной прог­раммы, нам нуж­но разоб­рать­ся со сле­дующи­ми воп­росами:

1. Как прог­рамму запус­кать? В слу­чае при­ложе­ния в юзер­спей­се — запус­тить бинар­ник. А вот запус­тить ядро или час­ти про­шив­ки так прос­то не вый­дет.
2. Что слу­жит вход­ными дан­ными? Для XML-пар­сера вход­ные дан­ные — XML-фай­лы. А, нап­ример, бра­узер и обра­баты­вает HTML, и исполня­ет JavaScript.
3. Как вход­ные дан­ные прог­рамме переда­вать? В прос­тей­шем слу­чае дан­ные переда­ются на стан­дар­тный ввод или в виде фай­ла. Но прог­раммы могут получать дан­ные и через дру­гие каналы. Нап­ример, про­шив­ка может получать их от физичес­ких устрой­ств.
4. Как генери­ровать вво­ды? «Вво­дом» будем называть набор дан­ных, передан­ный прог­рамме на вход. В качес­тве вво­да мож­но соз­давать мас­сивы ран­домных бай­тов, а мож­но делать что‑нибудь более умное.
5. Как опре­делять факт ошиб­ки? Если прог­рамма упа­ла — это баг. Но сущес­тву­ют ошиб­ки, которые не при­водят к падению. При­мер: утеч­ка информа­ции. Такие ошиб­ки тоже хочет­ся находить.
6. Как авто­мати­зиро­вать про­цесс? Мож­но запус­кать прог­рамму с новыми вво­дами вруч­ную и смот­реть, не упа­ла ли она. А мож­но написать скрипт, который будет делать это авто­мати­чес­ки.

Се­год­ня мы говорим о ядре Linux, так что в каж­дом из воп­росов мы можем мыс­ленно заменить сло­во «прог­рамма» на «ядро Linux». А теперь давай поп­робу­ем най­ти отве­ты.

Простой способ

Для начала при­дума­ем отве­ты поп­роще и раз­работа­ем пер­вую вер­сию нашего фаз­зера.

Запускаем ядро

Нач­нем с того, как ядро запус­кать. Здесь есть два спо­соба: исполь­зовать железо (компь­юте­ры, телефо­ны или одноплат­ники) или исполь­зовать вир­туаль­ные машины (нап­ример, QEMU). У каж­дого свои плю­сы и минусы.

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

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

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

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

Разбираемся со вводами

Что явля­ется вход­ными дан­ными для ядра? Ядро обра­баты­вает сис­темные вызовы — сис­колы (syscall). Как передать их в ядро? Давай напишем прог­рамму, которая дела­ет пос­ледова­тель­ность вызовов, ском­пилиру­ем ее в бинарь и запус­тим. Всё: ядро будет интер­пре­тиро­вать наши вызовы.

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

Са­мый прос­той спо­соб генери­ровать дан­ные — брать слу­чай­ные бай­ты. Этот спо­соб работа­ет пло­хо: обыч­но прог­раммы, вклю­чая то же ядро, ожи­дают дан­ные в более‑менее кор­рек­тном виде. Если передать им сов­сем мусор, даже эле­мен­тарные про­вер­ки на кор­рек­тность не прой­дут, и прог­рамма отка­жет­ся обра­баты­вать ввод даль­ше.

Спо­соб луч­ше: генери­ровать дан­ные на осно­ве грам­матики. На при­мере XML-пар­сера: мы можем за­ложить в грам­матику зна­ние о том, что XML-файл сос­тоит из XML-тегов. Таким обра­зом мы обой­дем эле­мен­тарные про­вер­ки и про­ник­нем глуб­же внутрь кода пар­сера.

Од­нако для ядра такой под­ход надо адап­тировать: ядро при­нима­ет пос­ледова­тель­ность сис­колов с аргу­мен­тами, а это не прос­то мас­сив бай­тов, даже сге­нери­рован­ных по опре­делен­ной грам­матике.

Пред­ставь прог­рамму из трех сис­колов: open, который откры­вает файл, ioctl, который совер­шает опе­рацию над этим фай­лом, и close, который файл зак­рыва­ет. Для open пер­вый аргу­мент — это стро­ка, то есть прос­тая струк­тура с единс­твен­ным фик­сирован­ным полем. Для ioctl, в свою оче­редь, пер­вый аргу­мент — зна­чение, которое вер­нул open, а тре­тий — слож­ная струк­тура с нес­коль­кими полями. Наконец, в close переда­ется все тот же резуль­тат open.

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

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

По­луча­ется, что, ког­да мы фаз­зим сис­колы, мы фаз­зим API, который пре­дос­тавля­ет ядро. Я такой под­ход называю API-aware-фаз­зинг.

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

Так и сде­лаем: выберем нес­коль­ко сис­колов и раз­работа­ем алго­ритм генери­рова­ния их пос­ледова­тель­нос­тей. Нап­ример, заложим в него, что в ioctl дол­жен переда­вать­ся резуль­тат open и струк­тура пра­виль­ного типа со слу­чай­ными полями.

[Не] автоматизируем

С авто­мати­заци­ей пока не будем замора­чивать­ся: наш фаз­зер в цик­ле будет генери­ровать вво­ды и переда­вать их ядру. А мы будем вруч­ную монито­рить лог ядра на пред­мет оши­бок типа kernel panic.

Готово

Всё! Мы отве­тили на все воп­росы и раз­работа­ли прос­той спо­соб фаз­зинга ядра.

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

Ход рас­сужде­ний был прос­тым, но сам под­ход работа­ет прек­расно. Если спе­циалис­та по фаз­зингу ядра Linux спро­сить: «Какой фаз­зер работа­ет опи­сан­ным спо­собом?», то он сра­зу ска­жет: Trinity! Да, фаз­зер с таким алго­рит­мом работы уже сущес­тву­ет. Одно из его пре­иму­ществ — он лег­ко перено­симый. Закинул бинарь в сис­тему, запус­тил — и все, ты уже ищешь баги в ядре.

Способ получше

Фаз­зер Trinity сде­лали дав­но, и с тех пор мысль в области фаз­зинга ушла даль­ше. Давай поп­робу­ем улуч­шить при­думан­ный спо­соб, исполь­зовав более сов­ремен­ные идеи.

Собираем покрытие

Идея пер­вая: для генера­ции вво­дов исполь­зовать под­ход coverage-guided — на осно­ве сбор­ки пок­рытия кода.

Как он работа­ет? Помимо генери­рова­ния слу­чай­ных вво­дов с нуля, мы под­держи­ваем набор ранее сге­нери­рован­ных «инте­рес­ных» вво­дов — кор­пус. И иног­да, вмес­то слу­чай­ного вво­да, мы берем один ввод из кор­пуса и его слег­ка модифи­циру­ем. Пос­ле чего мы исполня­ем прог­рамму с новым вво­дом и про­веря­ем, инте­ресен ли он. А инте­ресен ввод в том слу­чае, если он поз­воля­ет пок­рыть учас­ток кода, который ни один из пре­дыду­щих исполнен­ных вво­дов не пок­рыва­ет. Если новый ввод поз­волил прой­ти даль­ше вглубь прог­раммы, то мы добав­ляем его в кор­пус. Таким обра­зом, мы пос­тепен­но про­ника­ем все глуб­же и глуб­же, а в кор­пусе собира­ются все более и более инте­рес­ные прог­раммы.

Этот под­ход исполь­зует­ся в двух основных инс­тру­мен­тах для фаз­зинга при­ложе­ний в юзер­спей­се: AFL и libFuzzer.

Coverage-guided-под­ход мож­но ском­биниро­вать с исполь­зовани­ем грам­матики. Если мы модифи­циру­ем струк­туру, можем делать это в соот­ветс­твии с ее грам­матикой, а не прос­то слу­чай­но выкиды­вать бай­ты. А если вво­дом явля­ется пос­ледова­тель­ность сис­колов, то изме­нять ее мож­но, добав­ляя или уда­ляя вызовы, перес­тавляя их мес­тами или меняя их аргу­мен­ты.

Для coverage-guided-фаз­зинга ядра нам нужен спо­соб собирать информа­цию о пок­рытии кода. Для этой цели был раз­работан инс­тру­мент KCOV. Он тре­бует дос­тупа к исходни­кам, но для ядра у нас они есть. Что­бы вклю­чить KCOV, нуж­но пересоб­рать ядро с вклю­чен­ной опци­ей CONFIG_KCOV, пос­ле чего пок­рытие кода ядра мож­но собирать через /sys/kernel/debug/kcov.

Ловим баги

Те­перь давай при­дума­ем что‑нибудь получ­ше для обна­руже­ния багов, чем выпаде­ние в kernel panic.

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

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

Для ядра таких детек­торов нес­коль­ко. Самый кру­той из них — KASAN. Крут он не потому, что я над ним работал, а потому, что он находит глав­ные типы пов­режде­ний памяти: выходы за гра­ницы мас­сива и use-after-free. Для его исполь­зования дос­таточ­но вклю­чить опцию CONFIG_KASAN, и KASAN будет работать в фоне, записы­вая репор­ты об ошиб­ках в лог ядра при обна­руже­нии.

Автоматизируем

Что каса­ется авто­мати­зации, то тут мож­но при­думать мно­го все­го инте­рес­ного. Авто­мати­чес­ки мож­но:

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

Как это все сде­лать? Написать код и вклю­чить его в наш фаз­зер. Исклю­читель­но инже­нер­ная задача.

Все вместе

Возь­мем эти три идеи — coverage-guided-под­ход, исполь­зование динами­чес­ких детек­торов и авто­мати­зацию про­цес­са фаз­зинга — и вклю­чим в наш фаз­зер. У нас получит­ся сле­дующая кар­тина.

Ес­ли опять‑таки спро­сить зна­юще­го челове­ка, какой фаз­зер ядра исполь­зует эти под­ходы, тебе сра­зу отве­тят: syzkaller. Сей­час syzkaller — это передо­вой фаз­зер ядра Linux. Он нашел ты­сячи оши­бок, вклю­чая экс­плу­ати­руемые уяз­вимос­ти. Прак­тичес­ки любой, кто занимал­ся фаз­зингом ядра, имел дело с этим фаз­зером.

Навороченные идеи

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

Вытаскиваем код в юзерспейс

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

Для некото­рых под­систем это сде­лать нес­ложно. Если под­систе­ма прос­то выделя­ет память с помощью kmalloc и осво­бож­дает ее через kfree и на этом при­вяз­ка к ядер­ным фун­кци­ям закан­чива­ется, тог­да мы можем заменить kmalloc на malloc и kfree на free. Даль­ше мы ком­пилиру­ем код как биб­лиоте­ку и фаз­зим с помощью того же libFuzzer.

Для боль­шинс­тва под­систем с этим под­ходом воз­никнут слож­ности. Тре­буемая под­систе­ма может исполь­зовать API, которые в юзер­спей­се поп­росту недос­тупны. Нап­ример, RCU.

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

Этот под­ход исполь­зовал­ся для фаз­зинга eBPF, ASN.1-пар­серов и се­тевой под­систе­мы ядра XNU.

Фаззим внешние интерфейсы

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

Дру­гими сло­вами, ядро обра­баты­вает дан­ные, при­ходя­щие через Ethernet, USB, Bluetooth, NFC, мобиль­ные сети и про­чие железяч­ные про­токо­лы.

Нап­ример, мы пос­лали на сис­тему TCP-пакет. Ядро дол­жно его рас­парсить, что­бы понять, на какой порт он при­шел и какому при­ложе­нию его дос­тавить. Отправ­ляя слу­чай­но сге­нери­рован­ные TCP-пакеты, мы можем фаз­зить сетевую под­систе­му с внеш­ней сто­роны.

Воз­ника­ет воп­рос: как дос­тавлять в ядро дан­ные со сто­роны внеш­них интерфей­сов? Сис­колы мы прос­то зва­ли из бинар­ника, а если мы хотим общать­ся с ядром по USB, то такой под­ход не прой­дет.

Дос­тавлять дан­ные мож­но через реаль­ное железо: нап­ример, отправ­лять сетевые пакеты по сетево­му кабелю или исполь­зовать Facedancer для USB. Но такой под­ход пло­хо мас­шта­биру­ется: хочет­ся иметь воз­можность фаз­зить внут­ри вир­туал­ки.

Здесь есть два решения.

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

Нап­ример, сеть я фаз­зил через TUN/TAP. Этот интерфейс поз­воля­ет отправ­лять в ядро сетевые пакеты так, что пакет про­ходит через те же самые пути пар­синга, как если бы он при­шел извне. В свою оче­редь, для фаз­зинга USB мне приш­лось написать свой драй­вер.

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

Та­кой под­ход при­меня­ется в фаз­зере vUSBf. В нем исполь­зовали QEMU и про­токол usbredir, который поз­воля­ет с хос­та под­клю­чать USB-устрой­ства внутрь вир­туал­ки.

За пределами API-aware-фаззинга

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

При­мер: clone и sigaction. Да, они тоже при­нима­ют аргу­мен­ты, тоже могут вер­нуть резуль­тат, но при этом они порож­дают еще один поток исполне­ния. clone соз­дает новый про­цесс, а sigaction поз­воля­ет нас­тро­ить обра­бот­чик сиг­нала, которо­му передас­тся управле­ние, ког­да этот сиг­нал при­дет.

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

Структурируем внешние вводы

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

При­мер: пусть мы фаз­зим TCP и у нас на хос­те есть сокет, с которым мы хотим уста­новить соеди­нение извне. Казалось бы, мы посыла­ем SYN, хост отве­чает SYN/ACK, мы посыла­ем ACK — все, соеди­нение уста­нов­лено. Но в получен­ном нами пакете SYN/ACK содер­жится но­мер под­твержде­ния, который мы дол­жны вста­вить в пакет ACK. В каком‑то смыс­ле это воз­врат зна­чения из ядра, но с внеш­ней сто­роны.

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

Помимо KCOV

Как еще мож­но собирать пок­рытие кода, кро­ме как с помощью KCOV?

Во‑пер­вых, мож­но исполь­зовать эму­лято­ры. Пред­ставь, что вир­туал­ка эму­лиру­ет ядро инс­трук­ция за инс­трук­цией. Мы можем внед­рить­ся в цикл эму­ляции и собирать отту­да адре­са инс­трук­ций. Этот под­ход хорош тем, что, в отли­чие от KCOV, тут не нуж­ны исходни­ки ядра. Как следс­твие, этот спо­соб мож­но исполь­зовать для зак­рытых модулей, которые дос­тупны в виде бинар­ников. Так дела­ют фаз­зеры TriforceAFL и UnicoreFuzz.

Еще один спо­соб собирать пок­рытие — исполь­зовать аппа­рат­ные фичи про­цес­сора. Нап­ример, kAFL исполь­зует Intel PT.

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

Собираем релевантное покрытие

Для coverage-guided-фаз­зинга нам нуж­но собирать пок­рытие с кода под­систе­мы, которую мы фаз­зим.

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

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

За пределами сбора покрытия кода

Нап­равлять про­цесс фаз­зинга мож­но не толь­ко с помощью пок­рытия кода.

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

Чем в более слож­ное сос­тояние мы заведем ядро во вре­мя фаз­зинга, тем боль­ше шанс, что мы нат­кнем­ся на ситу­ацию, которую оно не смо­жет кор­рек­тно обра­ботать.

Собираем корпус вводов

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

Я видел такой под­ход в про­екте Moonshine: авто­ры запус­кали сис­темные ути­литы под strace, собира­ли с них лог и исполь­зовали получен­ную пос­ледова­тель­ность сис­колов как ввод для фаз­зинга с помощью syzkaller.

Ловим больше багов

Су­щес­тву­ющие динами­чес­кие детек­торы неидеаль­ны и могут не замечать некото­рые ошиб­ки. Как находить такие ошиб­ки? Улуч­шать детек­торы.

Мож­но, к при­меру, взять KASAN (напом­ню, он ищет пов­режде­ния памяти) и до­бавить анно­тации для какого‑нибудь нового алло­като­ра. По умол­чанию KASAN под­держи­вает стан­дар­тные алло­като­ры ядра, такие как slab и page_alloc. Но некото­рые драй­веры выделя­ют здо­ровен­ный кусок памяти и потом самос­тоятель­но его нареза­ют на бло­ки помель­че (при­вет, Android!). KASAN в таком слу­чае не смо­жет най­ти перепол­нение из одно­го бло­ка в дру­гой. Нуж­но добав­лять анно­тации вруч­ную.

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

Мож­но делать свои баг‑детек­торы с нуля. Самый прос­той спо­соб — добавить в исходни­ки ядра ассерты. Если мы зна­ем, что в опре­делен­ном мес­те всег­да дол­жно выпол­нять­ся опре­делен­ное усло­вие, — добав­ляем BUG_ON и начина­ем фаз­зить. Если BUG_ON сра­ботал — баг най­ден. А мы сде­лали эле­мен­тарный детек­тор логичес­кой ошиб­ки. Такие детек­торы осо­бен­но инте­рес­ны в кон­тек­сте фаз­зинга eBPF, потому что ошиб­ка в eBPF обыч­но не при­водит к пов­режде­нию памяти и оста­ется незаме­чен­ной.

Итоги и советы

Да­вай под­ведем ито­ги.

Гло­баль­но под­ходов к фаз­зингу ядра Linux три:

• Ис­поль­зовать юзер­спей­сный фаз­зер. Либо берешь фаз­зер типа AFL или libFuzzer и его переде­лыва­ешь, что­бы он звал сис­колы вмес­то фун­кций юзер­спей­сной прог­раммы. Либо вытас­кива­ешь ядер­ный код в юзер­спейс и фаз­зишь его там. Эти спо­собы прек­расно работа­ют для под­систем, обра­баты­вающих струк­туры, потому что в основном юзер­спей­сные фаз­зеры ори­енти­рова­ны на мутацию мас­сива бай­тов. При­меры: фаз­зинг фай­ловых сис­тем и Netlink. Для coverage-guided-фаз­зинга тебе при­дет­ся под­клю­чить сбор­ку пок­рытия с ядра к алго­рит­му фаз­зера.
• Ис­поль­зовать syzkaller. Он иде­аль­но под­ходит для API-aware-фаз­зинга. Для опи­сания сис­колов и их воз­вра­щаемых зна­чений и аргу­мен­тов он исполь­зует спе­циаль­ный язык — syzlang.
• На­писать свой фаз­зер с нуля. Это отличный спо­соб ра­зоб­рать­ся, как работа­ет фаз­зинг изнутри. А еще с помощью это­го под­хода мож­но фаз­зить под­систе­мы с не­обыч­ными ин­терфей­сами.

Как понять, что твой фаз­зер работа­ет хорошо? Оче­вид­но, что если он находит новые баги, то все отлично. Но вот что делать, если не находит?

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

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

И еще пара советов:

• Пи­ши фаз­зер на осно­ве кода, а не докумен­тации. Докумен­тация может быть неточ­на. Источни­ком исти­ны всег­да будет код. Я на это натол­кнул­ся, ког­да делал фаз­зер USB: ядро обра­баты­вало дру­гое под­мно­жес­тво про­токо­лов, чем опи­сан­ное в докумен­тации.

• В пер­вую оче­редь делай фаз­зер умным, а уже потом делай его быс­трым. «Умный» озна­чает генери­ровать более точ­ные вво­ды, луч­ше собирать пок­рытие или что‑нибудь еще в таком роде, а «быс­трый» — иметь боль­ше исполне­ний в секун­ду. Нас­чет «умный» или «быс­трый» пос­мотри статью и дис­куссию.

Выводы

Соз­дание фаз­зеров — инже­нер­ная работа. И осно­вана она на инже­нер­ных уме­ниях: про­екти­рова­нии, прог­рамми­рова­нии, тес­тирова­нии, дебаг­гинге и бен­чмар­кинге.

От­сюда два вывода. Пер­вый: что­бы написать прос­той фаз­зер — дос­таточ­но прос­то уметь прог­рамми­ровать. Вто­рой: что­бы написать кру­той фаз­зер — нуж­но быть хорошим инже­нером. При­чина, по которой syzkaller име­ет такой успех, — в него было вло­жено мно­го инже­нер­ного опы­та и вре­мени.

На­деюсь, я ско­ро уви­жу новый необыч­ный фаз­зер, который напишешь имен­но ты!