Pull to refresh

Самая дорогая однобайтовая ошибка

Programming
Translation
Original author: Poul-Henning Kamp
Предлагаю вашему вниманию перевод недавнего поста в электронном журнале Queue авторства Poul-Henning Kamp.

Ошиблись ли Кен, Деннис и Брайан при выборе использовать NUL-завершенные текстовые строки?

ИТ стимулирует и реализует современную западную экономику. Соответственно мы часто видим заголовки про ошеломляюще огромные суммы денег, связанные с ошибками в ИТ. Какое же решение, связанное с ИТ или КН [компьютерными науками], является наиболее дорогим?

Недавно достаточное количество экспертов разводили руками при упоминании финансовых последствий для Sony от проблем, связанных с их PlayStation Network, но такое событие незначительно в данном контексте. Когда я учился в школе, мне довелось пообщаться с инспектором из Книги рекордов Гиннеса, который объяснил, что что-то не может просто случайно стать настоящим рекордом, должна быть причинная связь, начинающаяся с человеческого намерения (например, мы загнали 26 учеников старшей школы в Volkswagen Beetle нашего учителя музыки и закрыли двери).

Sony (вероятно) не хотели выяснять, какой же беспорядок случится, если уделять безопасности мало внимания, поэтому этот и другие примеры ложной экономии не проходят отбор. Другим бы кандидатом мог быть выбор IBM Билла Гейтса, а не Гари Килдалла [Gary Kildall], в качестве поставщика операционной системы для их персонального компьютера. Ущерб от этого решения по-прежнему накапливается с головокружительной скоростью: Stuxnet [прим. пер. сетевой червь] и искажение процесса ISO стандартизации OOXML наглядно демонстрируют, как далеко и широко может распространиться ущерб. Но это не было решением, связанным с ИТ или КН. Как на данный момент известно, это было бизнес решение, основанное на отказе Килдала принимать требования IBM о неразглашении.

Более подходящим примером было бы решение изобрести собственный разделитель имени каталога/файла для MS-DOS: была выбрана обратная косая черта (\), а не прямая косая черта (/), которая использовалась в Unix или точка, которая использовала DEC в своих операционных системах. Хоть фактический ущерб сравнительно умеренный, это решение тоже не подходит как хороший пример, поскольку это не было настоящим решением, это было истинным предпочтением. В IBM выбрали использовать косую черту для флагов команд, игнорируя Unix, а точка была использована как разделитель имени файла и расширения, что сделало невозможным следовать примеру DEC.

История исследования космоса предлагает целый набор раскрученных и дорогих ошибок, но, что интересно, я не смог найти ни одного подходящего кандидата. Ошибки синтаксиса Fortran и ошибки синхронизации бортового компьютера шаттла не подходят по причине отсутствия намерения. Ведение части проекта в имперских единицах измерения, а другой части в метрических является «случайным актом управления» и никак не относится к КН или ИТ.

Наилучшим примером, который я смог найти, является использование NUL-завершенных текстовых строк в C/Unix/Posix. Стоял очень простой выбор: должен ли язык C представлять строки как кортеж адрес + длина или просто как адрес и некий магический символ (NUL), отмечающий конец строки? Именно это решение приняло динамическое трио Кен Томпсон, Деннис Ритчи и Брайан Керниган в начале 70-х, и они были вольны выбрать любой способ. Я не смог найти ни одной записи о решении, которое я признаю слабым кандидатом: у меня нет никаких доказательств, что это решение было осознанным.

Тем не менее, насколько я могу определить из моего исследования, формат адрес + длина был предпочтительным для большинства языков программирования того времени, тогда как адрес + магический маркер использовался в основном в программах, написанных на ассемблере. Поскольку язык C вырос из ассемблера, как более переносимый и высокоуровневый язык, мне сложно поверить, что Кен, Деннис и Брайан об этом даже не думали.

Использование формата адрес + длина стоило бы одного накладного байта в сравнении с адрес + магический маркер, а их PDP компьютер имел ограниченную основную память. Другими словами, этот пример мог бы стать идеально типичным и рациональным решением, связанным с ИТ или КН, как и множество подобных решений принимаемых нами каждый день. Но именно это решение имеет атипичные экономические последствия.

Затраты на разработку аппаратного обеспечения



Изначально Unix слабо влиял на разработку аппаратного обеспечения и набора команд [прим. пер. процессора]. Процессоры, предоставлявшие инструкции для манипуляции строками, например, Z-80 и DEC VAX, осуществляли это, используя гораздо более распространенную модель адрес + смещение. Как только Unix и C получили поддержку, NUL-завершенные строки стали целью для оптимизаций. Разработчики ЦПУ начали добавлять инструкции для работы с ними. Примером служит инструкции Logical String Assist добавленные IBM в 1992 году в процессоры, основанные на ES/9000 520.

Добавление инструкций в ЦПУ не является дешевым и происходит только тогда, когда существуют ощутимые и исчислимые денежные причины.

Затраты на производительность



IBM добавила инструкции для работы с NUL-завершенными строками потому, что ее покупатели тратили дорогие циклы ЦПУ на обработку таких строк. Однако, это нам не говорит о том, что циклов ЦПУ потребовалось бы меньше, если бы формат адрес + длина был использован.

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

Одним примером служит библиотека libc во FreeBSD, где реализация bcopy(3)/memcpy(3) перемещает как можно больше информации фрагментами по «беззнаковое целое»: обычно 32 или 64 бита, а затем «очищает любые замыкающие байты» используя побайтовое копирование, как описано в комментариях.

При использовании NUL-завершенной строки, попытка работы с ней частями, превышающими один байт, может привести к обращению к символам за символом NUL. Если NUL символ является последним байтом страницы виртуальной памяти и следующая страница не определена, это может привести к крушению процесса с ошибкой «страница не найдена» [«page not present»].

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

Если мы заранее знаем длину строки — все по-другому.

Затраты на разработку компилятора



Часто компилятор знает одну вещь о строках — их длину, особенно, когда строки константны. Это позволяет компилятору выполнять вызов к более быстрой memcpy(3) даже, если программист использовал strcpy(3) в исходном коде.

Более глубокая инспекция кода позволяет компилятору осуществлять более продвинутые оптимизации, некоторые из них очень умелые, но только в том случае, если кто-то реализовал это в компиляторе. Разработка оптимизирующих компиляторов никогда не была простой или дешевой, однако очевидно, что Apple надеется, что это изменится с использованием LLVM (Low-level Virtual Machine), где оптимизаторов навалом.

Обратной стороной глубоких оптимизаций, проводимых компилятором, являются оптимизации, которые проводят целостный обзор исходного кода и переупорядочивают его в больших объемах. Они требуют, чтобы программист тщательно следил за тем, что исходный код точно описывает то, что необходимо. Программист, работавший с компилятором для суперкомпьютеров серии Convex C3800, обозначил это как «необходимо программировать так, как будто компилятор твоя бывшая жена».

Затраты на безопасность



Даже если ваш компилятор не имеет вражеских намерений, исходный код должен писаться таким образом, чтобы он мог противостоять атакам и NUL-завершенная строка имеет мрачное досье в этом отношении. Полным бедствием, с точки зрения безопасности, является gets(3), которая «полагает, что буфер будет достаточно большим», и эта проблема «относительно под нашим контролем».

Взятие под контроль, однако, означает, что компилятор будет дополнительно жаловаться, если gets(3) где-либо вызывается. Несмотря на 15 лет внимания, переполнение и недогрузка [under-running] строковых буферов являются предпочтительным вектором атаки для злоумышленников и слишком часто это окупается.

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

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

Предотвращая Slashdot-сенсации



Мы учимся на своих ошибках и не стоит придумывать «желтые» заголовки для этой статьи. Кен, Деннис и Брайан никак не могли предвидеть все последствия своего выбора, сделанного 30 лет назад, и тогда они ничего не гарантировали. На сколько мне известно, понадобилось 15 лет, чтобы понять, что это тонкое решение является плохой идеей. Наверное, ни одно из моих решений не продержалось столь же долго.

Другими словами, Кен, Деннис и Брайан сделали все правильно.

Но это не решает проблему



Для множества людей C умер, и ${lang} является языком будущего, для постоянно меняющегося кратковременного значения ${lang}. В реальности же, все другие языки напрямую или опосредствованно сидят на вершине Posix API и NUL-завершенных строк языка C.

Когда ваша Java, Python, Ruby или Haskell программа открывает файл, среда выполнения передает имя файла как NUL-завершенную строку в open(3); или когда она преобразует queue.acm.org в IP адрес, она передает имя хоста как NUL-завершенную строку в getaddrinfo(3). До тех пор, как вы будете продолжать так делать, вы сохраните все преимущества при работе вашей программы на PDP/11, и все недостатки при запуске на чем-либо другом.

Вы можете здесь написать свое предложение об API в борьбе с воображаемым противником, предложить способ задания функций, операций и стратегии обработки ошибок, но я уверен, это будет полной растратой прекрасного вечера. Опыт показывает, что такие предложения идут в никуда, поскольку обратная совместимость с PDP/11 и конечное количество написанных программ куда важнее, чем потенциальная возможность написать бесконечное количество программ в будущем более эффективным и безопасным способом.

Таким образом, затраты на решение Кена, Денниса и Брайана будут продолжать накапливаться, как пыль почти похоронившая Древний Рим на протяжении столетий.

Ссылки


1. Computer Business Review. 1992. Partitioning and Escon enhancements for top-end ES/9000s; http://www.cbronline.com/news/ibm_announcements_71.
2. ViewVC. 2007. Contents of /head/lib/libc/string/bcopy.c; http://svnweb.freebsd.org/base/head/lib/libc/string/bcopy.c?view=markup.
3. Wikipedia. 2011. Lifeboat sketch; http://en.wikipedia.org/wiki/Lifeboat_sketch.
Tags:CКен ТомпсонДеннис РитчиБрайан Керниганnull-terminated stringPosix
Hubs: Programming
Total votes 141: ↑115 and ↓26+89
Views5.1K

Popular right now

Top of the last 24 hours