Ка­залось бы, что может быть слож­ного в иден­тифика­ции строк? Если то, на что ссы­лает­ся ука­затель, выг­лядит как стро­ка, это и есть стро­ка! Более того, в подав­ляющем боль­шинс­тве слу­чаев стро­ки обна­ружи­вают­ся и иден­тифици­руют­ся три­виаль­ным прос­мотром дам­па прог­раммы (при усло­вии, конеч­но, что они не зашиф­рованы, но шиф­рование — тема отдель­ного раз­говора). Так‑то оно так, да не все столь прос­то!

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

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

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

Ес­ли N име­ет малое зна­чение, поряд­ка трех‑четырех бай­тов, то мы получим очень боль­шое количес­тво лож­ных сра­баты­ваний. Нап­ротив, ког­да N велико, поряд­ка шес­ти‑вось­ми бай­тов, чис­ло лож­ных сра­баты­ваний близ­ко к нулю и ими мож­но пре­неб­речь, но все корот­кие стро­ки, нап­ример OK, YES, NO, ока­жут­ся не рас­позна­ны! Дру­гая проб­лема: помимо зна­ко‑циф­ровых сим­волов, в стро­ках встре­чают­ся и эле­мен­ты псев­догра­фики (осо­бен­но час­ты они в кон­соль­ных при­ложе­ниях) и вся­кие там «мор­дашки», «стрел­ки», «карапу­зики» — сло­вом, поч­ти вся таб­лица ASCII. Чем же тог­да стро­ка отли­чает­ся от слу­чай­ной пос­ледова­тель­нос­ти бай­тов? Час­тотный ана­лиз здесь бес­силен: ему для нор­маль­ной работы тре­бует­ся как минимум сот­ня бай­тов тек­ста, а мы говорим о стро­ках из двух‑трех сим­волов!

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

Прос­то, да не сов­сем! Рас­смот­рим сле­дующий при­мер (writeln_d):

От­компи­лиру­ем этот при­мер. Хотелось бы ска­зать, любым Pascal-ком­пилято­ром, толь­ко любой нам не подой­дет, пос­коль­ку нам нужен бинар­ный код под архи­тек­туру x86-64. Это авто­мати­чес­ки сужа­ет круг под­ходящих ком­пилято­ров. Даже популяр­ный Free Pascal все еще не уме­ет бил­дить прог­раммы для Windows x64. Но не уби­рай его далеко, он нам еще при­годит­ся.

В таком слу­чае нам при­дет­ся вос­поль­зовать­ся Embarcadero Delphi 10.4. Нас­трой ком­пилятор для пос­тро­ения 64-бит­ных при­ложе­ний и заг­рузи откомпи­лиро­ван­ный файл в дизас­сем­блер:

IDA опре­дели­ла, что перед вызовом фун­кции _ZN6System14_Write0UStringERNS_8TTextRecENS_13UnicodeStringE в регистр RDX заг­ружа­ется ука­затель на сме­щение aHelloSailor. Пос­мотрим, куда оно ука­зыва­ет (дваж­ды щел­кнем по нему):

Ага! Текст в кодиров­ке UTF-16LE. Что такое UTF-16, думаю, всем понят­но. Два конеч­ных сим­вола обоз­нача­ют порядок бай­тов. В дан­ном слу­чае, пос­коль­ку при­ложе­ние ском­пилиро­вано для архи­тек­туры x86-64, в которой исполь­зует­ся порядок бай­тов «от млад­шего к стар­шему» — little endian, упо­мяну­тые сим­волы говорят имен­но об этом. В про­тиво­полож­ном слу­чае, нап­ример на компь­юте­ре с про­цес­сором SPARC, кодиров­ка име­ла бы наз­вание UTF-16BE от big endian.

Из это­го сле­дует, что Delphi кодиру­ет каж­дый сим­вол перемен­ным количес­твом бай­тов: 2 или 4. Пос­мотрим, как себя поведет Visual C++ 2019 с ана­логич­ным кодом:

Ре­зуль­тат дизас­сем­бли­рова­ния:

По­инте­ресу­емся, что находит­ся в сег­менте дан­ных толь­ко для чте­ния (rdata) по сме­щению aHelloSailor:

Ни­каких допол­нитель­ных све­дений о раз­мере сим­волов. Из это­го мож­но сде­лать вывод, что исполь­зует­ся стан­дар­тная 8-бит­ная кодиров­ка ASCII, в которой под каж­дый сим­вол отво­дит­ся толь­ко 1 байт.

Яд­ро Windows NT изна­чаль­но исполь­зовало для работы со стро­ковы­ми сим­волами кодиров­ку UTF-16, одна­ко до Windows 10 в поль­зователь­ском режиме при­меня­лись две кодиров­ки: UTF-16 и ASCII (ниж­ние 128 сим­волов для англий­ско­го язы­ка, вер­хняя полови­на — для рус­ско­го). Начиная с Windows 10, в user mode исполь­зует­ся толь­ко UTF-16. Меж­ду тем сим­волы могут хра­нить­ся и в ASCII, что мы видели в при­мере выше.

В C/C++ char явля­ется исходным типом сим­вола и поз­воля­ет хра­нить любой сим­вол ниж­ней и вер­хней час­тей кодиров­ки ASCII раз­мером 8 бит. Хотя реали­зация типа wchar_t пол­ностью лежит на совес­ти раз­работ­чика ком­пилято­ра, в Visual C++ он пред­став­ляет собой пол­ный ана­лог сим­вола кодиров­ки UTF-16LE, то есть поз­воля­ет хра­нить любой сим­вол Юни­кода.

Для демонс­тра­ции двух основных сим­воль­ных типов в Visual C++ напишем эле­мен­тарный при­мер:

Ре­зуль­тат его выпол­нения пред­став­лен ниже.

Ду­маю, все понят­но без под­робных пояс­нений: char — 1 байт, wchar_t — 2 бай­та. Стро­ка "Hello, Sailor!" сос­тоит из 14 сим­волов, плюс конеч­ный 0. Это так­же отра­жено в выводе прог­раммы.

info

В стан­дарте C++ есть типы сим­волов: char8_t, char16_t, char32_t. Пер­вый из них был добав­лен с вве­дени­ем стан­дарта C++20, два дру­гих добав­лены в C++11. Их раз­мер отра­жает­ся в их наз­вани­ях: char16_t исполь­зует­ся для сим­волов кодиров­ки UTF-16, char32_t — для UTF-32. При этом char8_t не то же самое, что «унас­ледован­ный» char, хотя поз­воля­ет работать с сим­волами пос­ледне­го, глав­ным обра­зом он пред­назна­чен для литера­лов кодиров­ки UTF-8.

Раз­меры сим­волов важ­ны для обна­руже­ния гра­ниц строк при ана­лизе дизас­сем­блер­ных лис­тингов прог­рамм.

Мож­но сде­лать вывод, что сов­ремен­ные Visual C++ и Delphi опе­риру­ют оди­нако­выми типами строк, неваж­но какого раз­мера, но окан­чива­ющиеся сим­волом 0. Но так было не всег­да. В качес­тве исто­ричес­кого экскур­са откомпи­лиру­ем при­мер writeln_d ком­пилято­ром Free Pascal.

Заг­рузим резуль­тат в IDA.

Так‑так‑так… какой инте­рес­ный код для нас при­гото­вил Free Pascal! Сра­зу же бро­сает­ся в гла­за сме­щение

ад­рес которо­го помеща­ется в регистр ECX перед вызовом про­цеду­ры FPC_WRITE_TEXT_SHORTSTR, сво­им наз­вани­ем намека­ющей на вывод тек­ста. Пос­той, ведь это же 32-раз­рядная прог­рамма, где переда­ча парамет­ров в регис­трах ско­рее исклю­чение, чем пра­вило, и исполь­зует­ся толь­ко при сог­лашении fastcall, в осталь­ных же слу­чаях парамет­ры переда­ются через стек!

Заг­лянем‑ка в докумен­тацию по ком­пилято­ру… Есть кон­такт! По умол­чанию в коде механиз­ма вызова про­цедур для про­цес­соров i386 исполь­зует­ся сог­лашение register. У нор­маль­ных людей оно называ­ется fastcall. И, пос­коль­ку для плат­формы x86 оно не стан­дарти­зиро­вано, в отли­чие от x64, для переда­чи парамет­ров исполь­зуют­ся все сво­бод­ные регис­тры! Поэто­му в том, что исполь­зует­ся регистр ECX, нет ничего сверхъ­естес­твен­ного.

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

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

Ага! Сле­дующая инс­трук­ция копиру­ет ука­затель, пре­обра­зуя его в 32-раз­рядное зна­чение без уче­та зна­ка (ука­затель не может быть отри­цатель­ным). Затем с помощью коман­ды cmp срав­нива­ются зна­чения двух регис­тров: EAX и EBX. И если EAX боль­ше или равен EBX, выпол­няет­ся переход на мет­ку loc_40665C...

...где про­исхо­дит похожая на манипу­ляцию со стро­кой деятель­ность.

Те­перь мы смог­ли убе­дить­ся в пра­виль­нос­ти нашего пред­положе­ния! Вер­немся к основно­му иссле­дова­нию и пос­мотрим, что же скры­вает­ся под подоз­ритель­ным сме­щени­ем:

Сог­ласись, не это мы ожи­дали уви­деть. Одна­ко пос­ледова­тель­ное рас­положе­ние сим­волов стро­ки «в стол­бик» дела не меня­ет. Инте­ресен дру­гой момент: в начале стро­ки сто­ит чис­ло, показы­вающее количес­тво сим­волов в стро­ке, — 0xE (14 в десятич­ной сис­теме).

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

Типы строк

На­ибо­лее популяр­ны сле­дующие типы строк: С‑стро­ки, которые завер­шают­ся нулем; DOS-стро­ки, завер­шают­ся сим­волом $ (такие стро­ки исполь­зуют­ся не толь­ко в MS-DOS); Pascal-стро­ки, которые пред­варя­ет одно-, двух- или четырех­бай­товое поле, содер­жащее дли­ну стро­ки. Рас­смот­рим каж­дый из этих типов под­робнее.

С‑стро­ки, так­же име­нуемые ASCIIZ-стро­ками (от Zero — ноль на кон­це) или нуль‑тер­миниро­ван­ными, — весь­ма рас­простра­нен­ный тип строк, широко исполь­зующий­ся в опе­раци­онных сис­темах семей­ств Windows и UNIX. Сим­вол 0 (не путать с 0) име­ет спе­циаль­ное пред­назна­чение и трак­тует­ся по‑осо­бому, как приз­нак завер­шения стро­ки. Дли­на ASCIIZ-строк прак­тичес­ки ничем не огра­ниче­на, ну раз­ве что раз­мером адресно­го прос­транс­тва, выделен­ного про­цес­су. Поэто­му теоре­тичес­ки в Windows NT х64 мак­сималь­ный раз­мер ASCIIZ-стро­ки лишь нем­ногим менее 16 Тбайт.

Фак­тичес­кая дли­на ASCIIZ-строк лишь на байт длин­нее исходной ASCII-стро­ки. Нес­мотря на перечис­ленные выше дос­тоинс­тва, С‑стро­кам при­сущи и некото­рые недос­татки. Во‑пер­вых, ASCIIZ-стро­ка не может содер­жать нулевых бай­тов, поэто­му она неп­ригод­на для обра­бот­ки бинар­ных дан­ных. Во‑вто­рых, опе­рации копиро­вания, срав­нения и кон­катена­ции С‑строк соп­ряжены со зна­читель­ными нак­ладны­ми рас­ходами — сов­ремен­ным про­цес­сорам невыгод­но работать с отдель­ными бай­тами, им желатель­но иметь дело с чет­верны­ми сло­вами.

Но, увы, дли­на ASCIIZ-строк наперед неиз­вес­тна, и ее при­ходит­ся вычис­лять на лету, про­веряя каж­дый байт на сим­вол завер­шения. Прав­да, раз­работ­чики некото­рых ком­пилято­ров идут на хит­рость: они завер­шают стро­ку семью нулями, что поз­воля­ет работать с двой­ными сло­вами, а это на порядок быс­трее. Почему семью, а не четырь­мя, ведь в двой­ном сло­ве бай­тов четыре? Да, вер­но, четыре, но подумай, что про­изой­дет, если пос­ледний зна­чимый сим­вол стро­ки при­дет­ся на пер­вый байт двой­ного сло­ва? Вер­но, его конец запол­нят три нулевых бай­та, но двой­ное сло­во из‑за вме­шатель­ства пер­вого сим­вола уже не будет рав­но нулю! Вот поэто­му сле­дующе­му двой­ному сло­ву надо пре­дос­тавить еще четыре нулевых бай­та, тог­да оно гаран­тирован­но будет рав­но нулю. Впро­чем, семь слу­жеб­ных бай­тов на каж­дую стро­ку — это уже перебор!

В MS-DOS (и не толь­ко в ней) фун­кция вывода стро­ки вос­при­нима­ет знак $ как сим­вол завер­шения, поэто­му в прог­раммист­ских кулу­арах такие стро­ки называ­ют DOS-стро­ками. Тер­мин не сов­сем кор­ректен: все осталь­ные фун­кции MS-DOS работа­ют исклю­читель­но с ASCIIZ-стро­ками!

Теги: CSS