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

Что такое «слепые» SQL-инъекции

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

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

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

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

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

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

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

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

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

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

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

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

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

Факторы, влияющие на скорость эксплуатации

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

• При экс­плу­ата­ции Blind SQL-инъ­екции ата­кующий отправ­ляет зап­росы на один и тот же эндпо­инт. Один такой зап­рос обра­баты­вает­ся веб‑сер­вером некото­рое вре­мя. Обоз­начим сред­нее вре­мя выпол­нения зап­роса — $t_0$. Раз­брос вре­мени выпол­нения зап­росов обыч­но невелик.

• Веб‑сер­вер может обра­баты­вать некото­рое количес­тво зап­росов парал­лель­но. Оно зависит от количес­тва физичес­ких веб‑сер­веров за балан­сиров­щиком, потоков веб‑при­ложе­ния, ядер на сер­вере СУБД и т.д. Его мож­но выяс­нить экспе­римен­таль­но. Обоз­начим количес­тво зап­росов к веб‑сер­веру — $n_0$.

• Со­ответс­твен­но, при­ложе­ние не будет обра­баты­вать боль­ше чем $F_0 = \frac{n_0}{t_0}$ зап­росов в секун­ду. Мы можем отпра­вить и боль­ше зап­росов в секун­ду, но они будут попадать в оче­редь и ждать обра­бот­ки, поэто­му общая ско­рость обра­бот­ки зап­росов не пре­высит $F_0$. Дан­ный параметр может менять­ся в зависи­мос­ти от текущей наг­рузки на при­ложе­ние и быть непос­тоян­ным, но не суть.

Вы­вод: cко­рость, с которой мы можем вынимать дан­ные, сос­тавля­ет ~=$F_0$ бит в секун­ду. Это основное огра­ниче­ние по ско­рос­ти экс­плу­ата­ции сле­пых SQL-инъ­екций.

Общие идеи повышения производительности

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

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

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

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

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

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

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

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

При баналь­ной реали­зации «в лоб» рас­парал­лелива­ние дела­ется толь­ко на треть­ем эта­пе. На пер­вом и вто­ром эта­пе идет под­бор в 1 поток, это озна­чает, что ско­рость сос­тавля­ет $\frac{1}{t_0}$ зап­росов в секун­ду вмес­то дос­тупных $\frac{n_0}{t_0}$.

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

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

По мере завер­шения поис­ка сим­волов мы запус­каем новые потоки для сле­дующих сим­волов той же стро­ки. Но так как ско­рость выпол­нения зап­росов при­мер­но оди­нако­ва, новые $n_0$ потоков мы запус­тим при­мер­но тог­да, ког­да пер­вые $n_0$ потоков завер­шатся, а имен­но через $7 * t_0$ секунд (если ищем в диапа­зоне 0x00-0x7f).

Ес­ли дли­на стро­ки крат­на $n_0$, то все хорошо и все потоки будут работать на мак­сималь­ной ско­рос­ти. Если же нет, то пос­ледняя груп­па пос­ле крат­ности $n_0$ будет работать в $X\ mod\ (n_0)$ потоков. Осталь­ные потоки будут прос­таивать. Наконец, если дли­на стро­ки слу­чай­ная, то оче­вид­но, что в сред­нем пос­ледняя груп­па будет работать толь­ко на 50% от мак­сималь­ной ско­рос­ти.

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

Для уве­личе­ния ско­рос­ти мож­но луч­ше исполь­зовать парал­лель­ность: запус­тить пер­вый поток для решения задачи 1, а оставши­еся $n_0 - 1$ сво­бод­ных потоков сра­зу запус­тить на опре­деле­ние длин строк для пер­вых $\frac{n_0 - 1}{c}$ строк, где $c$ — количес­тво колонок. Если ока­жет­ся, что строк нуж­но зап­росить мень­ше, чем мы опре­дели­ли, то часть потоков отра­бота­ла бес­смыс­ленно. Но ина­че они бы прос­то прос­таива­ли, так что ско­рость ата­ки не упа­дет, но может уве­личить­ся.

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

Основные задачи эксплуатации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Бу­дем счи­тать, что раз­мер чис­ла огра­ничен 64 битами. При этом чис­ло не отри­цатель­ное — unsigned. Для signed-чисел мож­но при­менить те же рас­сужде­ния, оцен­ка не изме­нит­ся.

2. Мак­сималь­ное 64-бит­ное чис­ло пред­став­ляет­ся стро­кой в 20 сим­волов. Таким обра­зом, на опре­деле­ние дли­ны стро­ки нуж­но 5 зап­росов, т.к. $2^5 = 32$ — бли­жай­шая свер­ху точ­ная сте­пень двой­ки (на самом деле нем­ного мень­ше, как будет показа­но ниже, но пока округлим в боль­шую сто­рону).

3. Даль­ше в зависи­мос­ти от дли­ны стро­ки нуж­но пот­ратить 3-4 зап­роса на каж­дую циф­ру (почему так — смот­ри ниже в раз­деле «Сужение диапа­зона поис­ка»). Дли­на стро­ки рав­на $ceil(log_{10}(N))$, где $N$ — иско­мое чис­ло.

4. Та­ким обра­зом, общее количес­тво зап­росов — $5 + 3,4 * (ceil(log_{10}(N)))$.

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

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

1. Оп­ределить, сколь­ко в чис­ле битов ($ln_2(N)$). Воз­можные зна­чения — от 1 до 64, то есть нам пот­ребу­ется 6 зап­росов ($2^6 = 64$).

2. Даль­ше в зависи­мос­ти от количес­тва битов еще нуж­но столь­ко зап­росов, сколь­ко в чис­ле битов. Битов в чис­ле — $ceil(log_2(N))$, то есть в сум­ме получа­ется $6 + ceil(log_2(N))$.

3. Для срав­нения двух вари­антов убе­рем округле­ние и при­ведем фор­мулу оцен­ки обще­го количес­тва зап­росов к логариф­му по осно­ванию 2:

   $5 + 3,4 * log_{10}(N) = 5 + 3,4*\frac{log_2(N)}{log_2(10)} = 5 + \frac{3,4}{3,33}*log_2(N)$.

Вид­но, что раз­ница фор­мул в основном опи­сыва­ется дробью $\frac{3,4}{3,33}$, которая не силь­но отли­чает­ся от $1$, то есть при­веден­ные алго­рит­мы име­ют при­мер­но оди­нако­вую эффектив­ность. Пер­вый алго­ритм удоб­но исполь­зовать, ког­да мы не зна­ем заранее тип колон­ки, — мы можем всег­да все колон­ки кон­верти­ровать в тек­сто­вый тип и получать работа­ющую ата­ку (прав­да, ценой неболь­шого удли­нения зап­роса).

Работа с диапазонами поиска

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

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

До это­го мы говори­ли о том, что для опре­деле­ния одно­го сим­вола тре­бует­ся 7 зап­росов, за которые мы можем опре­делить зна­чение из диапа­зона 0x00-0x7f (алфа­вит объ­ема $2^7$), что соот­ветс­тву­ет ниж­ней (англий­ской) полови­не таб­лицы ASCII. Идея уско­рения сос­тоит в том, что мы можем искать сим­волы не сре­ди всей ниж­ней полови­ны ASCII-таб­лицы, а сре­ди какого‑то ее под­мно­жес­тва.

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

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

1. Пер­вый зап­рос покажет, вхо­дит сим­вол в мно­жес­тво [0,1,2,3,4] или в [5,6,7,8,9].

2. Вто­рой зап­рос разобь­ет получен­ную груп­пу из 5 эле­мен­тов на груп­пы из 2 и 3 эле­мен­тов:

   • [0,1] и [2,3,4] для пер­вого слу­чая;
   • [5,6] и [7,8,9] для вто­рого слу­чая.

3. Тре­тий зап­рос най­дет зна­чение в слу­чае, если целевой сим­вол был в диапа­зонах [0,1] и [5,6].

4. Для диапа­зонов [2,3,4] и [7,8,9] одним зап­росом мы можем сде­лать раз­деление на под­диапа­зоны из одно­го и двух сим­волов:

   • [2,3,4] разобь­ем на [2] и [3,4];
   • [7,8,9] разобь­ем на [7] и [8,9].

5. Та­ким обра­зом сим­волы [2] и [7] будут най­дены треть­им зап­росом.

6. Ес­ли целевой сим­вол находит­ся в [3,4] или [8,9], то понадо­бит­ся еще один (чет­вертый) зап­рос.

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

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

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

$q = ((N - N_2) * 2 * (log_2(N_2) + 1) + (N_2 * 2-N) * log_2(N_2) ) / N$

где $N_2$ — бли­жай­шая сни­зу к N пол­ная сте­пень чис­ла 2: $N_2 = 2^{floor(ln_2(N))}$.

Фун­кцию $q$ мож­но апрокси­миро­вать как $log_2(N)$, но реаль­ное $q$ будет всег­да чуть боль­ше, чем $log_2(N)$ для N, не явля­ющих­ся точ­ной сте­пенью двой­ки.

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

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

1. Бу­дем искать зна­чение соот­ветс­тву­юще­го ASCII-кода в диапа­зоне чисел 97-122. Середи­ной диапа­зона явля­ется чис­ло 109,5.

2. Оп­ределим, боль­ше ASCII-код целево­го сим­вола, чем 109,5, или мень­ше:

   (ascii(substr(target_col,5,1)) from target_table limit 2,1)>109

   Ес­ли ASCII-код мень­ше, то целевой диапа­зон умень­шит­ся до 97-109, если боль­ше — до 110-122.

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

Та­ким обра­зом, сред­нее количес­тво зап­росов получа­ется $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) * \frac{97}{102} + q(5) * \frac{5}{102} + 4,86 = 11,33$, что нам­ного боль­ше изна­чаль­ных 7 зап­росов. То есть пред­положе­ние о диапа­зоне дол­жно иметь дос­таточ­но высокую веро­ятность, ина­че попыт­ка уско­рения может обер­нуть­ся потерей про­изво­дитель­нос­ти.

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

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

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