Самый быстрый укол. Оптимизируем Blind SQL-инъекцию

В сво­ей прак­тике работы в BI.ZONE я регуляр­но стал­кива­юсь с необ­ходимостью экс­плу­ата­ции сле­пых SQL-инъ­екций. Пожалуй, Blind-слу­чаи встре­чались мне даже чаще, чем Union или Error-based. Поэто­му я решил подумать об эффектив­ности. Эта статья — обзор под­ходов к экс­плу­ата­ции сле­пых SQL-инъ­екций и тех­ник, поз­воля­ющих уско­рить экс­плу­ата­цию.

ЧТО ТАКОЕ «СЛЕПЫЕ» SQL-ИНЪЕКЦИИ

Здесь мы раз­берем слу­чаи, при которых воз­ника­ют Blind SQL-инъ­екции, а так­же опи­сана базовая тех­ника их экс­плу­ата­ции. Если ты уже c ними зна­ком и понима­ешь, что такое бинар­ный поиск, — сме­ло перехо­ди к сле­дующе­му раз­делу.

Blind SQL-инъ­екции воз­ника­ют, ког­да мы не можем нап­рямую дос­тать дан­ные из при­ложе­ния, но можем раз­личить два раз­ных сос­тояния веб‑при­ложе­ния в зависи­мос­ти от усло­вия, которое мы опре­деля­ем в SQL-зап­росе.

Как работает Blind SQL-инъекция

Пред­ста­вим сле­дующую инъ­екцию (для прос­тоты исполь­зуем язык PHP, а в качес­тве СУБД возь­мем MySQL):

$query = "SELECT id,name FROM products ORDER BY ".$_GET['order'];

Здесь мы можем ука­зать в парамет­ре order не толь­ко имя колон­ки, но и некото­рое усло­вие, нап­ример:

order=(if( (select 1=1),id,name))

order=(if( (select 1=0),id,name))

В зависи­мос­ти от истиннос­ти логичес­кого выраже­ния (1=1) или (1=0) резуль­тат будет отсорти­рован СУБД либо по колон­ке id, либо по колон­ке name. В отве­те веб‑при­ложе­ния мы уви­дим, по какой колон­ке отсорти­рова­ны products, и смо­жем отли­чить истинное усло­вие от лож­ного. Это поз­воля­ет нам «задавать воп­росы» СУБД, на которые мы будем получать отве­ты «да» или «нет».

Нап­ример, «спро­сим» у СУБД — в таб­лице information_schema.tables боль­ше 50 строк или нет?

order=(if( (select count(*)>50 from information_schema.tables),id,name))`

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

order=(if( (select substring(password,1,1)='a' from users where username='admin'),id,name))

order=(if( (select substring(password,1,1)='b' from users where username='admin'),id,name))

order=(if( (select substring(password,1,1)='c' from users where username='admin'),id,name))

...

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

Как выполнить бинарный поиск

Пе­реве­дем сим­вол иско­мой стро­ки в его ASCII-код и сде­лаем некото­рое пред­положе­ние о воз­можных зна­чени­ях это­го сим­вола. Нап­ример, мож­но пред­положить, что он лежит в ниж­ней полови­не ASCII-таб­лицы, то есть име­ет код в диапа­зоне от 0x00 до 0x7f. Раз­делим этот диапа­зон пополам и спро­сим у БД — в какой полови­не диапа­зона находит­ся сим­вол?

order=(if( (select ascii(substring(password,1,1))>0x3f from users where username='admin'),id,name))

Ес­ли сим­вол ока­жет­ся боль­ше 0x3f, зна­чит, целевой диапа­зон сужа­ется до 0x40-0x7f, если мень­ше — до 0x00-0x3f. Далее находим середи­ну диапа­зона и сно­ва спра­шива­ем у БД: целевой сим­вол боль­ше середи­ны или мень­ше? Потом сно­ва сужа­ем диапа­зон и про­дол­жаем до тех пор, пока в диапа­зоне не оста­нет­ся ров­но одно зна­чение. Это зна­чение и будет отве­том.

В дан­ном слу­чае для поис­ка точ­ного зна­чения сим­вола нам пот­ребу­ется ров­но log2(128)=7

зап­росов.

ФАКТОРЫ, ВЛИЯЮЩИЕ НА СКОРОСТЬ ЭКСПЛУАТАЦИИ

Те­перь раз­берем­ся, что ог­раничи­вает ско­рость экс­плу­ата­ции инъ­екции:

• При экс­плу­ата­ции Blind SQL-инъ­екции ата­кующий отправ­ляет зап­росы на один и тот же эндпо­инт. Один такой зап­рос обра­баты­вает­ся веб‑сер­вером некото­рое вре­мя. Обоз­начим сред­нее вре­мя выпол­нения зап­роса — t0
• . Раз­брос вре­мени выпол­нения зап­росов обыч­но невелик.
• Веб‑сер­вер может обра­баты­вать некото­рое количес­тво зап­росов парал­лель­но. Оно зависит от количес­тва физичес­ких веб‑сер­веров за балан­сиров­щиком, потоков веб‑при­ложе­ния, ядер на сер­вере СУБД и т.д. Его мож­но выяс­нить экспе­ремен­таль­но. Обоз­начим количес­тво зап­росов к веб‑сер­веру — n0.
• Со­ответс­твен­но, при­ложе­ние не будет обра­баты­вать боль­ше чем
• F0=n0t0
• зап­росов в секун­ду. Мы можем отпра­вить и боль­ше зап­росов в секун­ду, но они будут попадать в оче­редь и ждать обра­бот­ки, поэто­му общая ско­рость обра­бот­вки зап­росов не пре­высит F0
• . Дан­ный параметр может менять­ся в зависи­мос­ти от текущей наг­рузки на при­ложе­ние и быть непос­тоян­ным, но не суть.

Вы­вод: cко­рость, с которой мы можем вынимать дан­ные, сос­тавля­ет ~=F0

бит в секун­ду. Это основное огра­ниче­ние по ско­рос­ти экс­плу­ата­ции сле­пых SQL-инъ­екций.

ОБЩИЕ ИДЕИ ПОВЫШЕНИЯ ПРОИЗВОДИТЕЛЬНОСТИ

Работа с сессиями

Веб‑при­ложе­ние может не выпол­нять паралель­ные зап­росы в рам­ках одной сес­сии (нап­ример, так работа­ет PHP). Если мы видим, что под­бор идет в один поток, то нуж­но соз­дать по сес­сии для каж­дого потока под­бора.

Так­же, если веб‑при­ложе­ние выпол­няет­ся на нес­коль­ких сер­верах и исполь­зует балан­сиров­ку на осно­ве Sticky Sessions, все зап­росы в рам­ках сес­сии отправ­ляют­ся на один и тот же сер­вер. Мы можем соз­дать нес­коль­ко сес­сий на раз­ных сер­верах и рас­пре­делить зап­росы рав­номер­но по ним. В обра­бот­ку зап­росов будет вов­лечено боль­шее количес­тво сер­веров — сле­дова­тель­но, n0

повысить­ся, а вмес­те с ним и общая ско­рость ата­ки.

Многопоточность

По­лучить боль­ше чем F0

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

Как пра­вило, наша задача — вытащить нес­коль­ко колонок из одной таб­лицы (воз­можно, с при­мене­нием филь­тра WHERE). Реали­зация такой ата­ки «в лоб» сос­тоит из сле­дующих задач:

1. Оп­ределить количес­тво строк, которое надо вер­нуть.
2. Для каж­дой стро­ки и колон­ки, которые надо вер­нуть, опре­делить дли­ну стро­ки.
3. Вы­пол­нить поиск каж­дого сим­вола целевой стро­ки. Если мы счи­таем что нам нуж­ны толь­ко стан­дар­тные сим­волы из ниж­ней полови­ны ASCII-таб­лицы (0x00-0x7f), то это 7 зап­росов на один сим­вол.

Банальная реализация

При баналь­ной реали­зации «в лоб» рас­парал­лелива­ние дела­ется толь­ко на треть­ем эта­пе. На пер­вом и вто­ром эта­пе идет под­бор в 1 поток, это озна­чает, что ско­рость сос­тавля­ет

1t0

зап­росов в секун­ду вмес­то дос­тупных

n0t0.

На треть­ем эта­пе рас­парал­лелива­ние дела­ется таким обра­зом. Допус­тим, веб‑при­ложе­ние обра­баты­вает n0

одновре­мен­ных зап­росов, а дли­на стро­ки сос­тавля­ет X

. Таким обра­зом мы можем выпол­нять n0

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

Сна­чала опре­деля­ем пер­вые n0

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

По мере завер­шения поис­ка сим­волов мы запус­каем новые потоки для сле­дующих сим­волов той же стро­ки. Но так как ско­рость выпол­нения зап­росов при­мер­но оди­нако­ва, новые n0

потоков мы запус­тим при­мер­но тог­да, ког­да пер­вые n0

потоков завер­шать­ся, а имен­но через 7∗t0

секунд (если ищем в диапа­зоне 0x00-0x7f).

Ес­ли дли­на стро­ки крат­на n0

, то все хорошо и все потоки будут работать на мак­сималь­ной ско­рос­ти. Если же нет, то пос­ледняя груп­па пос­ле крат­ности n0

будет работать в X mod (n0)

потоков. Осталь­ные потоки будут прос­таивать. Наконец, если дли­на стро­ки слу­чай­ная, то оче­вид­но, что в сред­нем пос­ледняя груп­па будет работать толь­ко на 50% от мак­сималь­ной ско­рос­ти.

Более производительный вариант

Для уве­личе­ния ско­рос­ти мож­но луч­ше исполь­зовать парал­лель­ность: запус­тить пер­вый поток для решения задачи 1, а оставши­еся n0−1

сво­бод­ных потоков сра­зу запус­тить на опре­деле­ние длин строк для пер­вых

n0−1c

строк, где c

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

Мож­но пой­ти и еще даль­ше, сде­лав веро­ятное допуще­ние о том, что целевые стро­ки име­ют дли­ну не мень­ше, нап­ример, 3-х сим­волов. Не завер­шив ни задачу 1, ни задачу 2, начать выпол­нять задачу 3, начать опре­делять пер­вые 3 сим­вола пер­вых целевых строк. Пос­ле такого стар­та, если гра­мот­но рас­порядить­ся потока­ми (нап­ример, иметь уже опре­делен­ные дли­ны для нес­коль­ких сле­дующих строк заранее), мож­но под­держи­вать общую ско­рость ~=F0.

ОСНОВНЫЕ ЗАДАЧИ ЭКСПЛУАТАЦИИ

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

Определение количества записей и длины строк

Оп­ределе­ние количес­тва воз­вра­щаемых записей (row) и дли­ны строк — схо­жие задачи, но они не так три­виаль­ны, как могут изна­чаль­но показать­ся.

Би­нар­ный поиск может искать зна­чение в рам­ках какого‑то диапа­зона, у которо­го есть минималь­ное и мак­сималь­ное зна­чение. Так, при опре­деле­нии сим­волов мы зна­ем, что они, ско­рее все­го, лежат в диапа­зоне 0x00-0x7f и точ­но попада­ют в 0x00-0xff (Unicode пока опус­тим, хотя и для него тоже мож­но задать мак­сималь­ную гра­ницу диапа­зона).

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

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

Определяем длину строки (банальный способ)

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

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

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

Ал­горитм получа­ется сле­дующий:

1. Срав­нива­ем дли­ну стро­ки с 256.
2. Ес­ли дли­на мень­ше, то запус­каем бинар­ный поиск, который будет тре­бовать ln2(256)=8
3. зап­росов.
4. Ес­ли дли­на боль­ше, то нам нуж­но уве­личить мак­сималь­ный диапа­зон. Нап­ример, мож­но умно­жить ста­рую вер­хнюю гра­ницу на 24
5. и срав­нить с ней. Если ока­жет­ся мень­ше, то запус­каем бинар­ный поиск, если боль­ше, то умно­жаем на 24
6. еще раз и так далее.

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

Так­же сто­ит учи­тывать обыч­ные прак­тичес­кие задачи. Экс­плу­ата­ция сле­пых SQL-инъ­екций — дело небыс­трое. Ско­рее все­го, если мы наш­ли стро­ку, дли­на которой сос­тавля­ет 10 000 сим­волов, нам не будет инте­рес­но вынимать ее целиком. Воз­можно, мы заходим пос­мотреть на пер­вые 100 сим­волов, что­бы понять, что вооб­ще в ней содер­жится.

Та­ким обра­зом, если дли­на стро­ки боль­ше, чем, нап­ример, 128 сим­волов, то нас и не инте­ресу­ет ее точ­ная дли­на — мож­но в выводе прос­то ука­зать, что дли­на боль­ше 128 сим­волов, и при этом най­ти толь­ко эти самые пер­вые 128 сим­волов. В ито­ге получа­ем, что на опре­деле­ние дли­ны стро­ки мы тра­тим 7 зап­росов, как на 1 сим­вол. На мой взгляд — впол­не при­емле­мо.

Определяем длину строки (небанальный способ)

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

При опре­деле­нии сим­волов, как пра­вило, исполь­зует­ся конс­трук­ция

ASCII(substring(target_col,n,1))

Ес­ли n боль­ше, чем дли­на стро­ки, то фун­кция substring вер­нет пус­тую стро­ку, а фун­кция ASCII от пус­той стро­ки вер­нет 0x00 (это вер­но для MySQL и PostgreSQL). Соот­ветс­твен­но, как толь­ко мы обна­ружи­ли нулевой сим­вол, мы счи­таем, что мы обна­ружи­ли пос­ледний сим­вол и даль­ше искать не надо.

В дан­ном под­ходе мы осу­щест­вля­ем поиск сим­вола за пос­ледним, что дает лиш­них 7 зап­росов. Тра­ты ана­логич­ны тра­там на опре­деле­ние дли­ны стро­ки. Так­же учтем, что в MSSQL и SQLite фун­кция substring вер­нет не пус­тую стро­ку, а NULL, как и фун­кция ASCII/Unicode. Мож­но соз­давать осо­бые конс­трук­ции, при­водя­щие NULL в 0, одна­ко это тре­бует уве­личе­ния дли­ны зап­роса. Кро­ме того, мы дол­жны акку­рат­но выс­тра­ивать парал­лель­ность: под­бор нес­коль­ких сим­волов одновре­мен­но может при­вес­ти к бес­полез­ному поис­ку за кон­цом стро­ки и лиш­нему рас­ходу зап­росов.

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

Поиск целых чисел

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

1. Бу­дем счи­тать, что раз­мер чис­ла огра­ничен 64 битами. При этом чис­ло не отри­цатель­ное — unsigned. Для signed-чисел мож­но при­менить те же рас­сужде­ния, оцен­ка не изме­нит­ся.
2. Мак­сималь­ное 64-бит­ное чис­ло пред­став­ляет­ся стро­кой в 20 сим­волов. Таким обра­зом, на опре­деле­ние дли­ны стро­ки нуж­но 5 зап­росов, т.к. 25=32
3. — бли­жай­шая свер­ху точ­ная сте­пень двой­ки (на самом деле нем­ного мень­ше, как будет показа­но ниже, но пока округлим в боль­шую сто­рону).
4. Даль­ше в зависи­мос­ти от дли­ны стро­ки нуж­но пот­ратить 3-4 зап­роса на каж­дую циф­ру (почему так — смот­ри ниже в раз­деле «Сужение диапа­зона поис­ка»). Дли­на стро­ки рав­на ceil(log10(N))
5. , где N
6. — иско­мое чис­ло.
7. Та­ким обра­зом, общее количес­тво зап­росов — 5+3,4∗(ceil(log10(N))).

Мак­сималь­ное количес­тво зап­росов для мак­сималь­ной дли­ны — 73. Баналь­ный бинар­ный поиск на все 64 бита тре­бует 64 зап­роса вне зависи­мос­ти от раз­мера чис­ла.

Для улуч­шения алго­рит­ма мы можем:

1. Оп­ределить, сколь­ко в чис­ле битов (ln2(N)
2. ). Воз­можные зна­чения — от 1 до 64, то есть нам пот­ребу­ется 6 зап­росов (26=64
3. ).
4. Даль­ше в зависи­мос­ти от количес­тва битов еще нуж­но столь­ко зап­росов, сколь­ко в чис­ле битов. Битов в чис­ле — ceil(log2(N))
5. , то есть в сум­ме получа­ется 6+ceil(log2(N)).
6. Для срав­нения двух вари­антов убе­рем округле­ние и при­ведем фор­мулу оцен­ки обще­го количес­тва зап­росов к логариф­му по осно­ванию 2:
7. 5+3,4∗log10(N)=5+3,4∗log2(N)log2(10)=5+3,43,33∗log2(N)

Вид­но, что раз­ница фор­мул в основном опи­сыва­ется дробью

3,43,33

, которая не силь­но отли­чает­ся от 1

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

РАБОТА С ДИАПАЗОНАМИ ПОИСКА

В дан­ном раз­деле рас­смот­рены раз­личные под­ходы к экс­плу­ата­ции сле­пых SQL-инъ­екций при исполь­зовании раз­ных диапа­зонов поис­ка.

Сужение диапазона поиска

До это­го мы говори­ли о том, что для опре­деле­ния одно­го сим­вола тре­бует­ся 7 зап­росов, за которые мы можем опре­делить зна­чение из диапа­зона 0x00-0x7f (алфа­вит объ­ема 27

), что соот­ветс­тву­ет ниж­ней (англий­ской) полови­не таб­лицы ASCII. Идея уско­рения сос­тоит в том, что мы можем искать сим­волы не сре­ди всей ниж­ней полови­ны ASCII-таб­лицы, а сре­ди какого‑то ее под­мно­жес­тва.

Да­вай­те раз­берем при­мер, ког­да нам извес­тно, что целевая стро­ка сос­тоит исклю­читель­но из цифр, и оце­ним ско­рость под­бора.

Ал­фавит под­бора име­ет мощ­ность 10. Для точ­ных сте­пеней 2 мы мог­ли бы взять прос­то логарифм по осно­ванию 2 от мощ­ности алфа­вита. Одна­ко 10 не явля­ется сте­пенью 2, а зна­чит, опре­делить количес­тво зап­росов для опре­деле­ния сим­вола чуть слож­нее:

1. Пер­вый зап­рос покажет, вхо­дит сим­вол в мно­жес­тво [0,1,2,3,4] или в [5,6,7,8,9].
2. Вто­рой зап­рос разобь­ет получен­ную груп­пу из 5 эле­мен­тов на груп­пы из 2 и 3 эле­мен­тов:
3. [0,1] и [2,3,4] для пер­вого слу­чая;
4. [5,6] и [7,8,9] для вто­рого слу­чая.
5. Тре­тий зап­рос най­дет зна­чение в слу­чае, если целевой сим­вол был в диапа­зонах [0,1] и [5,6].
6. Для диапа­зонов [2,3,4] и [7,8,9] одним зап­росом мы можем сде­лать раз­деление на под­диапа­зоны из одно­го и двух сим­волов:
7. [2,3,4] разобь­ем на [2] и [3,4];
8. [7,8,9] разобь­ем на [7] и [8,9].
9. Та­ким обра­зом сим­волы [2] и [7] будут най­дены треть­им зап­росом.
10. Ес­ли целевой сим­вол находит­ся в [3,4] или [8,9], то понадо­бит­ся еще один (чет­вертый) зап­рос.

По­луча­ется, для 6 воз­можных зна­чений мы дела­ем 3 зап­роса, а для оставших­ся 4 зна­чений — 4 зап­роса. Ито­го в сред­нем мы дела­ем 3-4 зап­роса на один сим­вол. Это более чем в 2 раза луч­ше, чем пол­ный бинар­ный поиск в диапа­зоне из воз­можных 128 зна­чений.

Математическая оценка

Оп­ределить сред­нее количес­тво зап­росов для сим­вола из алфа­вита мощ­ностью N мож­но по фор­муле

q=((N−N2)∗2∗(log2(N2)+1)+(N2∗2−N)∗log2(N2))/N

где N2

— бли­жай­шая сни­зу к N пол­ная сте­пень чис­ла 2: N2=2floor(ln2(N))

.

from math import log,floor

def questions(N):

pow2 = 2**floor(ln2(N))

return ((N-pow2)*2*(ln2(pow2)+1) + (pow2*2-N)*ln2(pow2))/N

def ln2(x):

return log(x)/log(2)

Фун­кцию q

мож­но апрокси­миро­вать как log2(N)

, но реаль­ное q

будет всег­да чуть боль­ше, чем log2(N)

для N, не явля­ющих­ся точ­ной сте­пенью двой­ки.

Определение ошибок

Для даль­нейших рас­сужде­ний раз­берем при­мер, в котором мы пред­полага­ем, что целевой сим­вол явля­ется малень­кой англий­ской бук­вой из диапа­зона a-z:

1. Бу­дем искать зна­чение соот­ветс­тву­юще­го ASCII-кода в диапа­зоне чисел 97-122. Середи­ной диапа­зона явля­ется чис­ло 109,5.
2. Оп­ределим, боль­ше ASCII-код целево­го сим­вола, чем 109,5, или мень­ше:
3. (ascii(substr(target_col,5,1)) from target_table limit 2,1)>109
4. Ес­ли ASCII-код мень­ше, то целевой диапа­зон умень­шит­ся до 97-109, если боль­ше — до 110-122.
5. Да­лее новый дипазон так­же бьет­ся на две час­ти и так далее, пока сим­вол не будет опре­делен.

Та­ким обра­зом, сред­нее количес­тво зап­росов получа­ется q(26)=4,77.

Канареечные символы

Ес­ли наше изна­чаль­ное пред­положе­ние «целевым сим­волом явля­ется малень­кая англий­ская бук­ва» — невер­ное, то мы получим в резуль­тате бинар­ного поис­ка одно из гра­нич­ных зна­чений — a или z. Отли­чить такой слу­чай от нас­тоящих букв «a» или «z» без допол­нитель­ных зап­росов мы не смо­жем. Для решения этой проб­лемы мы можем добавить на обе­их гра­ницах диапа­зона по сим­волу‑канарей­ке — то есть искать целевое зна­чение мы будем не в диапа­зоне 97-122, как в при­мере выше, а в диапа­зоне 96-123. Если в резуль­тате поис­ка будет получе­но канаре­ечное зна­чение 96 или 123, мы смо­жем понять, что изна­чаль­ное пред­положе­ние невер­но.

Та­кая тех­ника поз­воля­ет исполь­зовать диапа­зон­ный поиск в слу­чае, ког­да мы с хорошей долей веро­ятности можем пред­положить об алфа­вите кон­крет­ного сим­вола, но не уве­рены на 100%. При этом сто­ит пом­нить, что рас­ширение диапа­зона канаре­ечны­ми сим­волами при­водит к уве­личе­нию сред­него количес­тво зап­росов на один сим­вол: с q(26)=4,77

до q(28)=4,86.

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

• q(97)
• , если зна­чение мень­ше 97;
• q(5)
• , если боль­ше 122.

Ес­ли счи­тать, что сим­волы рас­пре­деле­ны рав­номер­но, то в сум­ме получа­ется

q(97)∗97102+q(5)∗5102+4,86=11,33

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

Поиск в диапазонах с разрывами

Те­перь рас­смот­рим поиск в наборе воз­можных зна­чений, которые не обра­зуют неп­рерыв­ного диапа­зона в ASCII-таб­лице. Нап­ример, наша цель — шес­тнад­цатерич­ная стро­ка, набор зна­чений [0-9A-F]. Для решения дан­ной задачи мож­но пред­ложить две тех­ники:

• инъ­екция с помощью опе­рато­ров IN и NOT IN;
• по­иск с игно­риро­вани­ем раз­рывов.

Инъекция с помощью операторов IN и NOT IN

Спи­сок допус­тимых ASCII-кодов в рас­смат­рива­емом слу­чае: [48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 97, 98, 99, 100, 101, 102]. Мы можем раз­делить этот перечень пополам и спра­шивать у СУБД, попада­ет ли иско­мый сим­вол в под­спи­сок. Усло­вие тог­да будет выг­лядеть при­мер­но так:

(ascii(substr(target_col,5,1)) from target_table limit 2,1) in (48, 49, 50, 51, 52, 53, 54, 55)

Ес­ли усло­вие выпол­нится, то целевое зна­чение будет находит­ся в наборе [48, 49, 50, 51, 52, 53, 54, 55]. Если нет — то в наборе [56, 57, 97, 98, 99, 100, 101, 102]. Далее, шаг за шагом раз­деляя получен­ные диапа­зоны пополам, мы получим целевое зна­чение. На опре­деле­ние одно­го сим­вола будет пот­рачено q(16)=4

зап­роса.

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

• до­бавить к алфа­виту одно псев­дозна­чение, которое будет соот­ветс­тво­вать сра­зу всем сим­волам, не вошед­шим в алфа­вит;
• для поис­ка исполь­зовать исклю­читель­но конс­трук­цию NOT IN.

При­мер:

1. Рас­смот­рим слу­чай, ког­да алфа­вит поис­ка сос­тоит из трех зна­чений [1, 3, 5].
2. До­бавим к зна­чени­ям [1, 3, 5] псев­дозна­чение N — получим [1, 3, 5, N].
3. Сде­лаем зап­рос (ascii(substr(target_col,5,1)) from target_table limit 2,1) NOT IN (1,3). Если получим False, то целевой сим­вол либо 1, либо 3, и сле­дующим зап­росом мы получим точ­ный ответ. Если же мы получи­ли True, то ответ либо равен 5, либо мы ошиб­лись с диапа­зоном.
4. Сде­лаем точ­ное срав­нение с 5: (ascii(substr(target_col,5,1)) from target_table limit 2,1) NOT IN (5). Если получи­ли True, зна­чит, мы ошиб­лись в нашем изна­чаль­ном пред­положе­нии об алфа­вите.

Эта тех­ника луч­ше, чем пред­ложен­ные выше канаре­ечные сим­волы на кра­ях диапа­зона, так как c исполь­зовани­ем опе­рато­ра NOT IN мы можем осу­щест­влять бинар­ный поиск в диапа­зонах с раз­рывами, при этом для обна­руже­ния ошиб­ки нам при­дет­ся уве­личить раз­мер алфа­вита все­го на 1. К недос­таткам этой тех­ники мож­но отнести удли­нение зап­роса в силу перечис­ления полови­ны алфа­вита в парамет­ре опе­рато­ров IN и NOT IN.

Поиск с игнорированием разрывов

Еще одна воз­можность решить задачу поис­ка в диапа­зоне с раз­рывом [0-9A-F] — выпол­нить поиск с игно­риро­вани­ем раз­рывов в диапа­зоне:

1. Раз­делим пополам диапа­зон [48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 97, 98, 99, 100, 101, 102]. Гра­ница диапа­зона будет про­ходить меж­ду сим­волами 55 и 56.
2. Сде­лаем зап­рос с помощью опе­рато­ра срав­нения: (ascii(substr(target_col,5,1)) from target_table limit 2,1) > 55. Ответ поз­воля­ет выб­рать одну из половин изна­чаль­ного диапа­зона.

Эту тех­нику нуж­но при­менять, пока в диапа­зоне не оста­нет­ся ров­но 1 сим­вол. В резуль­тате нам так­же пот­ребу­ется q(16)=4

зап­роса.

Дан­ная тех­ника может быть допол­нена для выпол­нения поис­ка оши­бок с помощью канаре­ечных сим­волов.

1. До­бавим к переч­ню зна­чений, которые мы ищем, канаре­ечные зна­чения:
2. од­но мень­ше самого малень­кого — 47;
3. од­но боль­ше самого боль­шого — 103;
4. од­но в про­пус­ке, нап­ример 58.
5. Вы­пол­ним поиск так же, как ука­зано выше. Cпи­сок воз­можных зна­чений — [47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 97, 98, 99, 100, 101, 102, 103].
6. Най­дем середи­ну диапа­зона (56) и выпол­ним срав­нение: (ascii(substr(target_col,5,1)) from target_table limit 2,1) > 56.
7. В резуль­тате выпол­нения зап­роса мы получим информа­цию о том, что целевое зна­чение лежит в одном из двух наборов:
8. [47, 48, 49, 50, 51, 52, 53, 54, 55, 56];
9. [57, 58, 97, 98, 99, 100, 101, 102, 103].
10. Вы­берем середи­ну диапа­зона, отпра­вим зап­рос, раз­делим набор на две час­ти и так далее.
11. В ито­ге мы либо получим зна­чение из изна­чаль­ного диапа­зона поис­ка (оно и будет отве­том), либо канаре­ечные зна­чения 47, 103 или 58 (любое из этих зна­чений покажет, что целево­го сим­вола в диапа­зоне не было). Так­же мы получим информа­цию о том, целевой сим­вол боль­ше 102, мень­ше 48 или лежит на отрезке 59-96.

Ес­ли пред­полага­емый диапа­зон име­ет более одно­го раз­рыва (пусть их r

), то количес­тво канаре­ечных сим­волов воз­раста­ет: нуж­но исполь­зовать гра­ницы 2+r.

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

Подстройка диапазона поиска

По­мимо жес­тко задан­ных диапа­зонов, мы можем модифи­циро­вать диапа­зон в про­цес­се про­веде­ния ата­ки, то есть «на лету».

Идеи оптимизации

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

Не­кото­рые колон­ки могут иметь жес­тко задан­ные сим­волы в опре­делен­ных позици­ях. Нап­ример, GUID (при­мер — 6F9619FF-8B86-D011-B42D-00CF4FC964FF) име­ет сим­вол - (минус) на позици­ях [8, 13, 18, 23]. Мы можем про­верить, что все сим­волы на соот­ветс­тву­ющей позиции сре­ди уже соб­ранных записей име­ют оди­нако­вое зна­чение и вмес­то бинар­ного поис­ка отпра­вить один зап­рос для про­вер­ки это­го сим­вола.

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

Дей­стви­тель­но, задача сжа­тия ана­логич­на нашей задаче: мы хотим находить час­то встре­чающиеся сим­волы за мень­шее количес­тво зап­росов (то есть пот­ратить на них мень­ше битов), а алго­ритм сжа­тия — пред­став­лять такие сим­волы наимень­шим количес­твом битов. Пос­тро­ение такого дерева тре­бует однократ­ного про­хож­дения по всей соб­ранной информа­ции для сбо­ра ста­тис­тики. Само пос­тро­ение име­ет слож­ность O(n∗log(n))

(где n

— раз­мер алфа­вита), что не так уж мно­го для алфа­витов в нашей задаче.

Пусть мы соб­рали нес­коль­ко строк и в них име­ется сле­дующая ста­тис­тика рас­пре­деле­ния сим­волов:

СИМ­ВОЛСКОЛЬ­КО РАЗ ВСТРЕ­ТИЛ­СЯВЕ­РОЯТ­НОСТЬa3447,2%b79,7%c57%d1216,7%e45,5%f1013,9%Для такой ста­тис­тики мож­но пос­тро­ить сле­дующее опти­маль­ное H-дерево:

Для раз­личных сим­волов пот­ребу­ется раз­личное количес­тво зап­росов:

• для сим­вола a — один зап­рос;
• для d, f и b — два зап­роса;
• для c и e — три зап­роса.

Ма­тожи­дание чис­ла зап­росов на один сим­вол:

1∗(0,472)+2∗(0,167+0,139+0,097)+3∗(0,07+0,055)=1,653

При обыч­ном поис­ке по диапа­зону оно сос­тавило бы q(6)=2,67.

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

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

ДРУГИЕ ИДЕИ ОПТИМИЗАЦИИ

Соединение строк

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

Идея алго­рит­ма

• Для соеди­нения колонок мы можем исполь­зовать опе­рацию кон­катена­ции соот­ветс­тву­ющей СУБД, ста­вя меж­ду ними ред­ко исполь­зуемый раз­делитель (нап­ример, 0x01). Стро­ки (rows) мы так­же можем объ­еди­нить с исполь­зовани­ем спе­циаль­ных фун­кции (group_concat для MySQL, string_agg для PostgreSQL). В качес­тве раз­делите­ля строк будем исполь­зовать тот же самый раз­делитель 0x01.
• Ана­лизи­руя получен­ный ответ, мы смо­жем отли­чить начало новой стро­ки (row), под­счи­тывая количес­тво колонок. На опре­деле­ние дли­ны стро­ки мы пот­ратим чуть боль­ше зап­росов. Одна­ко количес­тво зап­росов при­мер­но рав­но логариф­му дли­ны стро­ки и, соот­ветс­твен­но, рас­тет мед­леннее, чем сум­ма зап­росов, которые мы пот­ратили бы на опре­деле­ние длин каж­дой стро­ки в отдель­нос­ти.
• Так­же в дан­ном слу­чае мы можем не опре­делять дли­ну стро­ки вов­се, а прос­то обна­ружи­вать сим­волы, пока они не кон­чатся, как опи­сано в раз­деле «Опре­деле­ние количес­тва row и дли­ны строк». Одна­ко тог­да мы не смо­жем оце­нить, сколь­ко вре­мени зай­мет получе­ние дан­ных, что, ско­рее все­го, неп­рием­лемо на прак­тике.
• Ко­личес­тво зап­росов, которые будут пот­рачены на опре­деле­ние раз­делите­лей, зависит от исполь­зуемо­го диапа­зона под­бора. Раз­делитель сам по себе добав­ляет­ся как один сим­вол в диапа­зон. Сум­марное количес­тво раз­делите­лей рав­но количес­тву воз­вра­щаемых строк минус 1. Таким обра­зом, мож­но ска­зать, что мы заменя­ем зат­раты на опре­деле­ние длин строк на зат­раты на опре­деле­ние раз­делите­лей.
• Ес­ли счи­тать, что на опре­деле­ние дли­ны стро­ки в сред­нем тра­тит­ся 7 зап­росов, как ука­зано в раз­деле «Опре­деле­ние количес­тва записей и дли­ны строк», то это поз­воля­ет сэконо­мить 7−q(len(D))
• зап­росов на каж­дую стро­ку (где D
• — диапа­зон поис­ка). Так­же мы теря­ем q(len(D))−q(len(D)−1)
• зап­росов на каж­дый сим­вол, т.к. добав­ляем раз­делитель в диапа­зон.
• Ис­поль­зовать раз­ные диапа­зоны для поис­ка в раз­ных колон­ках мы можем лишь огра­ничен­но — так как мы исполь­зуем мно­гопо­точ­ность и не можем заранее знать — перева­лим мы через раз­делитель при под­боре оче­ред­ного сим­вола и, соот­ветс­твен­но, попадем в дру­гую колон­ку или нет. Поэто­му либо мы дол­жны исполь­зовать широкие диапа­зоны, что уве­личи­вает q(len(D))
• и сни­жает выиг­рыш от отсутс­твия необ­ходимос­ти опре­деле­ния длин строк, либо мы можем исполь­зовать соот­ветс­тву­ющие текущей колон­ке диапа­зоны и получать допол­нитель­ное количес­тво оши­бок — попада­ний в канаре­ечные сим­волы с пос­леду­ющим пов­торным поис­ком.

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

Работа с UNICODE

В слу­чае, ког­да в иско­мом тек­сте встре­чают­ся сим­волы, отсутс­тву­ющие в стан­дар­тной англий­ской ASCII-таб­лице, СУБД при­меня­ют для хра­нения Unicode. При­чем в некото­рых СУБД (нап­ример, MySQL) по умол­чанию при­меня­ется UTF-8, а в дру­гих (нап­ример, PostgreSQL) — UTF-16. В обо­их слу­чаях пре­обра­зова­ние сим­вола с помощью фун­кции ASCII/UNICODE при­ведет к получе­нию зна­чения боль­ше 128. Получе­ние зна­чения боль­ше 128 и будет для нас триг­гером того, что в стро­ке встре­чают­ся Unicode-сим­волы.

Unicode-сим­волы име­ют харак­терный вид для раз­личных язы­ков. Нап­ример, рус­ские бук­вы в UTF-8 в качес­тве пер­вого бай­та име­ют 0xDO или 0xD1. Если мы работа­ем с UTF-8, то мы можем пред­положить, что пос­ле одно­го UTF-8 сим­вола с рус­ской бук­вой будет идти еще один. Тог­да пер­вый байт это­го сим­вола мы можем эффектив­но обна­ружить, исполь­зуя алфа­вит из двух зна­чений [0xD0,0xD1], а для вто­рого бай­та мы можем огра­ничить поиск толь­ко зна­чени­ями, которые соот­ветс­тву­ют рус­ским бук­вам.

Од­нако такой под­ход не очень хорошо сов­местим с мно­гопо­точ­ным поис­ком: веро­ятность того, что сим­вол, иду­щий через N

сим­волов пос­ле текуще­го, так­же явля­ется рус­ским сим­волом UTF-8, пада­ет с рос­том N.

В сло­ве на рус­ском язы­ке в UTF-8 каж­дый вто­рой сим­вол будет 0xD0 или 0xD1, но пос­ле кон­ца сло­ва, ско­рее все­го, будет сто­ять одно­бай­товый сим­вол про­бела или зна­ка пре­пина­ния. Это сни­жает веро­ятность того, что через чет­ное чис­ло сим­волов пос­ле встре­чен­ного 0xD0 так­же будет 0xD0 или 0xD1.

Вы­вод: при работе с Unicode воз­можным решени­ем явля­ется исполь­зование одно­го потока на каж­дую стро­ку.

Сжатие данных

Ряд СУБД под­держи­вают встро­енные фун­кции сжа­тия (нап­ример, COMPRESS для MySQL и UTL_COMPRESS.LZ_COMPRESS для Oracle). Соот­ветс­твен­но, их при­мене­ние поз­воля­ет умень­шить количес­тво сим­волов, которые нам тре­бует­ся получить. При этом нам не нуж­но делать пред­положе­ния об исполь­зуемом алфа­вите: резуль­тат сжа­тия — BLOB. Мы будем исполь­зовать пол­ный диапа­зон из 256 зна­чений.

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

SELECT LENGTH(COMPRESS('123'))

>> 15

Вы­вод: подоб­ную тех­нику име­ет смысл при­менять сов­мес­тно с тех­никой соеди­нения строк. Объ­еди­нен­ная стро­ка будет длин­ной, и алго­рит­мы сжа­тия смо­гут сжать ее дос­таточ­но эффектив­но. Одна­ко мы будем зас­тавлять СУБД выпол­нять про­цеду­ру сжа­тия длин­ной стро­ки при каж­дом зап­росе, чем можем уве­личить вре­мя выпол­нения каж­дого зап­роса.

А ЧТО ТАМ SQLMAP?

Работа с потоками

Sqlmap не исполь­зует мно­гопо­точ­ность при опре­деле­нии количес­тва записей или длин строк. Одновре­мен­но он ищет толь­ко сим­волы одной стро­ки.

Определение длины строки

Sqlmap ищет дли­ну стро­ки, если исполь­зует­ся нес­коль­ко потоков. Если исполь­зует­ся один поток, то он счи­тает, что стро­ка закон­чилась, как толь­ко обна­ружен пер­вый сим­вол 0x00.

Поиск символов

При поис­ке сим­волов sqlmap исполь­зует сле­дующую тех­нику:

1. Пер­вый сим­вол ищет­ся пол­ным перебо­ром из 128 сим­волов (7 зап­росов).
2. Да­лее выбира­ется сим­вол, с которо­го нач­нется сле­дующий поиск на осно­вании пре­дыду­щего обна­ружен­ного сим­вола:
3. ес­ли это циф­ра, то sqlmap выбира­ет 48 (ASCII-код минималь­ного сим­вола, циф­ры 0);
4. ес­ли строч­ная бук­ва, то он выбира­ет 96 (код a);
5. ес­ли заг­лавная бук­ва, то 64 (код A).
6. Да­лее про­исхо­дит срав­нение с этим опре­делен­ным чис­лом и исполь­зует­ся обыч­ный бинар­ный поиск в оставшем­ся диапа­зоне. То есть если пре­дыду­щий сим­вол — бук­ва, то дела­ется сна­чала срав­нение с 48, а затем, если иско­мое зна­чение боль­ше, дела­ется поиск в диапа­зоне 48-127.

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

К плю­сам дан­ного под­хода мож­но отнести эффектив­ное обна­руже­ние кон­ца стро­ки, осо­бен­но если пос­ледний сим­вол стро­ки — чис­ло. Тог­да конец стро­ки будет опре­делен все­го за 3 зап­роса. Но эта тех­ника име­ет и не­дос­таток — низ­кая эффектив­ность поис­ка в час­ти слу­чаев.

Пред­положим, что пре­дыду­щий сим­вол был циф­рой. Тог­да пер­вое срав­нение дела­ется с 48, и если сле­дующий сим­вол сущес­тву­ет и боль­ше 48 (а это наибо­лее веро­ятная ситу­ация), то на его опре­деле­ние будет исполь­зован диапа­зон из 128−48=80

сим­волов, то есть q(80)=6,4

зап­росов. При этом один зап­рос уже будет сде­лан для срав­нения с 48, так что сум­марно sqlmap пот­ратит 7,4 зап­роса (дру­гими сло­вами, появ­ляет­ся веро­ятность, что он пот­ратит 8 зап­росов). При этом, если бы sqlmap делал пол­ный бинар­ный поиск, то пот­ратил бы ров­но 7 и никак не боль­ше.

Выбор диапазона символов

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

Unicode

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

Дру­гие рас­смот­ренные вари­анты опти­миза­ции в sqlmap не реали­зова­ны (по край­ней мере, я их не обна­ружил).

ВЫВОДЫ

В этой статье я при­вел теоре­тичес­кий обзор основных спо­собов опти­миза­ции экс­плу­ата­ции Blind SQL-инъ­екций. Какие‑то из них более эффектив­ны, какие‑то менее, но я попытал­ся при­вес­ти наибо­лее пол­ный перечень. Если у тебя есть дру­гие идеи и тех­ники опти­миза­ции — пиши мне в телег­рам @sorokinpf, обсу­дим!

Пос­тепен­но я пла­нирую реали­зовать некото­рые из опи­сан­ных спо­собов в сво­ем фрей­мвор­ке для экс­плу­ата­ции Blind SQL-инъ­екций — sqli_blinder (да, с фан­тази­ей у меня так себе). На дан­ный момент фрей­мворк реали­зует баналь­ный бинар­ный поиск, под­держи­вает работу с SQLite, MSSQL, Oracle, MySQL и PostgreSQL. Для работы с ним необ­ходимо написать одну фун­кцию на python, которая опре­делит, куда фрей­мвор­ку под­став­лять зап­росы и как ана­лизи­ровать отве­ты.