Power query содержит ошибки переполнения

let
    Источник = Excel.CurrentWorkbook(){[Name="СтатусПоставки"]}[Content],
    #"Повышенные заголовки" = Table.PromoteHeaders(Источник, [PromoteAllScalars=true]),
    #"Измененный тип" = Table.TransformColumnTypes(#"Повышенные заголовки",{
        {"Пп", type any}, 
   {"ОР", type any}, 
   {"Производство", type any}, 
   {"Наименование проекта", type any}, 
   {"СПП-элемент", type any}, 
   {"Комплектовщик", type any}, 
   {"Куратор", type any}, 
   {"КСП", type any}, 
   {"Часть проекта", type any}, 
   {"Материал", type any}, 
   {"Наименование материала по РВ", type any}, 
   {"Наименование материала в заявке", type any}, 
   {"Наименование ТМЦ", type any}, 
   {"Ед. изм.", type any}, 
   {"Кол-во к закупу", type any}, 
   {"Закупщик", type any}, 
   {"Стоимость", type any}, 
   {"Заявка", type any}, 
   {"Источник", type any}, 
   {"Срок начала реализации проекта", type any}, 
   {"Срок окончания реализации проекта", type any}, 
   {"Дата создания Заявки", type any}, 
   {"Дата Поставки По Заявке", type any}, 
   {"Статус поставки", type any}, 
   {"Статус корректный", type any}, 
   {"Дата статуса", type any}, 
   {"Номер контракта", type any}, 
   {"Дата Поставки Из договора", type any}, 
   {"Прогнозная дата поставки", type any}, 
   {"Договор подряда", type any}, 
   {"Дата оприходования на склад", type any}, 
   {"Учитывать", type any}, 
   {"Прогнозный срок перемещения на подрядчика ", type any}, 
   {"Перемещение на склад подрядчика", type any}, 
   {"Процент выполнения поставки", type any}, 
   {"Не вовлеченные ТМЦ", type any}, 
   {"Стоимость НВИ", type any}, 
   {"Причина возникновения НВИ", type any}, 
   {"Комментарий Планирование", type any}, 
   {"Комментарий Закупщика ", type any}, 
   {"Наличие риска", type any}})
in
    #"Измененный тип"

[Expression.Error] An error occurred while accessing table DataEntry3 because it contains overflow errors. Please fix the errors and try again.

3 ответа

Лучший ответ

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

Просматривая популярную рассылку по информационной безопасности BUGTRAQ, легко убедиться, что подавляющее большинство уязвимостей приложений и операционных систем связано с ошибками переполнения буфера. Ошибки этого типа настолько распространены, что вряд ли существует хотя бы один полностью свободный от них программный продукт. Переполнение приводит не только к некорректной работе программы, но и к возможности удаленного вторжения в систему с наследованием всех привилегий компрометированной программы. Это обстоятельство широко используется злоумышленниками. Проблема настольно серьезна, что попытки ее решения предпринимаются как на уровне самих языков программирования, так и на уровне компиляторов. К сожалению, достигнутые результаты оставляют желать лучшего, и ошибки переполнения продолжают появляться даже в современных приложениях. Вот всего несколько примеров: Microsoft Internet Information Service 5.0, Outlook Express 5.5; Netscape Directory Server 4.1x; Apple QuickTime Player 4.1; ISC BIND 8; Lotus Domino 5.0 — список этот можно было бы продолжать и продолжать. А ведь все это серьезные продукты солидных компаний, не скупящихся на тестирование. Давайте поговорим о приемах программирования, следование которым значительно уменьшает вероятность появления ошибок переполнения, в то же время не требуя от разработчика особых дополнительных усилий.

Причины и последствия ошибок переполнения

Во многих языках программирования, в том числе и в Cи/Cи++, массив одновременно является и совокупностью определенного количества объектов данных некоторого типа, и безразмерным фрагментом памяти. Программист может получить указатель на начало массива, но не имеет возможности непосредственно определить его длину. В Си/Си++ не делается особых различий между указателями на массив и указателями на ячейку памяти. Допускаются различные математические операции с указателями.

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

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

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

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

Несанкционированное чтение не принадлежащих к массиву данных может привести к утере конфиденциальности, а их модификация в лучшем случае заканчивается некорректной работой приложения (чаще всего «зависанием»), а в худшем — выполнением действий, никак не предусмотренных разработчиком (например, отключением защиты). Еще опаснее, если непосредственно за концом массива следуют адрес возврата из функции; в этом случае уязвимое приложение потенциально способно выполнить от своего имени любой код, переданный ему злоумышленником. И, если это приложение исполняется с наивысшими привилегиями (что типично для сетевых служб), взломщик сможет как угодно манипулировать системой.

Предотвращение возникновения ошибок переполнения

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

Переход на другой язык

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

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

Если в критических областях применения (атомной энергетике, космонавтике и т.п.) выбор между производительностью и защищенностью автоматически делается в пользу последней, в офисных и уж тем более в бытовых приложениях ситуация обратная. В лучшем случае речь может идти только о разумном компромиссе. Покупать дополнительные мегабайты и мегагерцы ради одного лишь достижения надлежащего уровня безопасности и без всяких гарантий на отсутствие ошибок других типов рядовой клиент не будет, как бы его ни убеждали. Тем более, что ни Ада, ни Perl, ни Java (языки, не отягощенные проблемами переполнения) принципиально не способны заменить Си/Cи++, не говоря уже об ассемблере. Разработчики оказываются зажатыми между несовершенством используемого ими языка программирования и невозможностью перехода на другой язык. Даже если бы и появился язык, удовлетворяющий всем мыслимым требованиям, совокупная стоимость его изучения и переписывания с нуля созданного программного обеспечения многократно бы превысила убытки от отсутствия в старом языке продвинутых средств контроля за ошибками: производители вообще несут очень мало издержек за «ляпы» в своих продуктах и не особо одержимы идей их тотального устранения.

Использование «кучи» для создания массивов

От использования статических массивов рекомендуется вообще отказаться (за исключением тех случаев, когда их переполнение заведомо невозможно). Вместо этого следует выделять память из кучи (Heap), преобразуя указатель, возвращенный функцией malloc к указателю на соответствующий тип данных (char, int), после чего с ним можно обращаться точно так же, как с указателем на обычный массив. Вернее, почти «точно так» — за двумя небольшими исключениями. Во-первых, получившая такой указатель функция может с помощью вызова msize узнать истинный размер буфера, не требуя от программиста явного указания данной величины. А, во-вторых, если в ходе работы выяснится, что этого размера недостаточно, она может динамически увеличить длину буфера, обращаясь к realloc всякий раз, как только в этом возникнет потребность. В этом случае, передавая функции, читающей строку с клавиатуры, указатель на буфер, не придется мучительно соображать: какой именно величиной следует ограничить его размер, — об этом позаботится сама вызываемая функция. Программисту же не придется добавлять еще одну константу в свою программу.

Отказ от индикатора завершения

По возможности не используйте какой бы то ни было индикатор завершения для распознания конца данных (например, нуль для задания конца строки). Во-первых, это приводит к неопределенности в длине самих данных и количества памяти, необходимой для их размещения, в результате чего возникают ошибки типа buff = malloc(strlen(Str)), которые с первого взгляда не всегда удается обнаружить (правильный код должен выглядеть так: buff = malloc(strlen(Str)+1), поскольку, в длину строки, возвращаемой функцией srtlen, не входит завершающий ее нуль).

Во-вторых, если по каким-то причинам индикатор конца будет уничтожен, функция, работающая с этими данными, «забредет» совсем не в свой «лес».

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

Значительно лучше явным образом указывать размер данных в отдельном поле (так, например, задается длина строк в компиляторах Turbo Pascal и Delphi). Однако такое решение не устраняет несоответствия размера данных и количества занимаемой ими памяти. Поэтому надежнее вообще отказаться от какого бы то ни было задания длины данных и всегда помещать их в буфер строго соответствующего размера.

Избавиться от накладных расходов, связанных с необходимостью частых вызовов достаточно медленной функции realloc можно введением специального ключевого значения, обозначающего отсутствие данных. В частности, для этой цели подойдет тот же нуль, однако, теперь он будет иметь другое значение — обозначать не конец строки, а отсутствие символа в данной позиции. Конец же строки определяется размером выделенного под нее буфера данных. Выделив буфер «про запас» и забив его «хвост» нулями, можно значительно сократить количество вызовов realloc. (Правда, в этом случае за эффективное использование ресурсов процессора приходится расплачиваться существенным перерасходом памяти. — Прим. ред.)

Обработка структурных исключений

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

Однако следует помнить, что описанные подходы сами по себе не защищают от ошибок переполнения, а только уменьшают вероятность их появления. Они исправно работают только в том случае, когда разработчик всегда помнит о необходимости постоянного контроля за границами массивов. Гарантировать выполнение такого требования невозможно в любой «полновесной» программе, состоящей из десятков или сотен тысяч строк. К тому же, чем больше проверок делает программа, тем «тяжелее» и медлительнее получается код и тем вероятнее, что хотя бы одна из проверок реализована неправильно или по забывчивости не реализована вообще. Можно ли, избежав нудных проверок, в то же время получить высокопроизводительный код, гарантированно защищенный от ошибок переполнения?

Несмотря на смелость вопроса, на него есть основания дать положительный ответ. И помогает в этом обработка структурных исключений. В общих чертах идея состоит в следующем: выделяется некий буфер, с обеих сторон «окольцованный» несуществующими страницами памяти и устанавливается обработчик исключений, «отлавливающий» прерывания, вызываемые при попытке доступа к несуществующей странице (вне зависимости от того, был ли это запрос на запись или чтение). Необходимость постоянного контроля границ массива при каждом к нему обращении отпадает. Точнее, теперь она «перекладывается» на процессор, а от программиста требуется всего лишь написать несколько строк кода, возвращающего ошибку или увеличивающего размер буфера при его переполнении. Единственным незакрытым лазом останется возможность прыгнуть далеко-далеко за конец буфера и случайно попасть на не имеющую к нему никакого отношения, но все-таки существующую страницу. В этом случае прерывания не произойдет и обработчик исключений ничего не узнает о факте нарушения. Однако такая ситуация достаточно маловероятна (чаще всего буферы читаются и записываются последовательно, а не в разброс), поэтому ею можно полностью пренебречь.

Преимущества технологии обработки структурных исключений заключаются в надежности, компактности и ясности использующего ее программного кода, не отягощенного беспорядочно разбросанными проверками, затрудняющими его понимание. Основной недостаток — плохая переносимость и системная зависимость. Не всякие операционные системы позволяют прикладному коду манипулировать на низком уровне со страницами памяти, а те, что позволяют, реализуют это каждая по-своему. В Windows, к счастью, такая возможность есть.

Функция VirtualAlloc обеспечивает выделение сегмента виртуальной памяти, с которым можно обращаться в точности как и с обычным динамическим буфером, а вызов VirtualProtect позволят изменить его атрибуты защиты. Можно задавать любой требуемый тип доступа, например, разрешить только чтение памяти, но не запись или исполнение. Это позволяет защищать критически важные структуры данных от разрушения некорректно работающими функциями. А запрет на исполнение кода в буфере даже при наличии ошибок переполнения не дает злоумышленнику никаких шансов запустить собственноручно переданный им код.

Использование функций, непосредственно работающих с виртуальной памятью, позволяет творить настоящие чудеса, на которые не способны функции стандартной библиотеки Си/Cи++. Единственный их недостаток заключается в непереносимости. Однако эту проблему можно решить, собственноручно реализовав функции VirtualAlloc, VirtualProtect и некоторые другие (правда, в некоторых случаях это придется делать на уровне компонентов ядра; обработка же структурных исключений изначально заложена в Си++).

Таким образом, усилия, направленные на защиту от ошибок переполнения буфера не настолько чрезмерны, чтобы не окупить полученный результат.

Традиции против надежности

Здравый смысл подсказывает: «Если все очень хорошо, то что-то тут не так». Если описанные приемы программирования столь хороши, почему же они не получили массового распространения? Видимо, на практике не все так складно, как на бумаге.

Пожалуй, основной камень преткновения — «верность традициям». В сложившейся культуре программирования признаком хорошего тона считается использование везде, где только возможно, стандартных функций самого языка, а не специфических возможностей операционной системы, «привязывающих» программу к одной платформе. Вряд ли этот подход бесспорен, но многие разработчики ему следуют. Но что лучше — мобильный, но нестабильно работающий и небезопасный код или плохо переносимое (в худшем случае вообще не переносимое), зато устойчивое и безопасное приложение? Если отказ от использования стандартных библиотек позволит уменьшить количество ошибок в приложении и многократно повысить его безопасность, стоит ли этим пренебрегать? Удивительно, но существует и такое мнение, что непереносимость — более тяжкий грех, чем ошибки, от которых, как водится, никто не застрахован. Аргументы: дескать, ошибки — явление временное и теоретически устранимое, а непереносимость — это навсегда. Однако, использование в своей программе функций, специфичных для какой-то одной операционной системы, не является непреодолимым препятствием для ее переноса на платформы, где этих функций нет. Достаточно лишь реализовать эти функции самостоятельно.

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

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

Как с ними борются?

Было бы по меньшей мере удивительно, если бы с ошибками переполнения никто не пытался бы бороться. Такие попытки предпринимались неоднократно, но результат во всех случаях оставлял желать лучшего. Очевидное «лобовое» решение проблемы состоит в синтаксической проверке выхода за границы массива при каждом обращении к нему. Такие проверки реализованы в некоторых компиляторах Си, например, в Compaq C для Tru64 Unix и Alpha Linux. Они не предотвращают возможности переполнения вообще и обеспечивают лишь контроль непосредственных ссылок на элементы массивов, но бессильны предсказать значение указателей.

Проверка корректности указателей вообще не может быть реализована синтаксически, а осуществима только на машинном уровне. Bounds Checker — специальное дополнение для компилятора gcc — именно так и поступает, гарантированно исключая всякую возможность переполнения. Платой за надежность становится значительное, измеряемое десятками раз падение производительности программы. В большинстве случаев это не приемлемо, поэтому такой подход не стал популярен и практически никем не применяется. Bounds Checker хорошо подходит для облегчения отладки приложений, но вовсе не факт, что все допущенные ошибки проявят себя еще на стадии отладки и будут замечены тестировщиками. В рамках проекта Synthetix удалось найти несколько простых и надежных решений, не спасающих от ошибок переполнения, но затрудняющих их использование злоумышленниками для несанкционированного вторжения в систему. StackGuard, еще одно расширение к компилятору gcc, дополняет пролог и эпилог каждой функции особым кодом, контролирующим целостность адреса возврата.

Алгоритм в общих чертах таков: в стек вместе с адресом возврата заносится так называемое Canary Word, расположенный до адреса возврата. Искажение адреса обычно сопровождается и искажением Canary Word, что легко проконтролировать. Соль в том, что Canary Word содержит символы «», CR, LF, EOF, которые могут быть обычным путем введены с клавиатуры. А для усиления защиты добавляется случайная привязка, генерируемая при каждом запуске программы. Компилятор MS Visual C++ также способен контролировать сбалансированность стека на выходе из функции: сразу после входа в функцию он копирует содержимое регистра-указателя вершины стека в один из регистров общего назначения, а затем сверяет их перед выходом из функции. Недостаток: впустую расходуется один из семи регистров и совсем не проверяется целостность стека, а лишь его сбалансированность.

Bounds Checker для Windows 9x/NT, выпущенный компанией NuMega, неплохо отлавливает ошибки переполнения, но, поскольку он выполнен не в виде расширения к какому-нибудь компилятору, а представляет собой отдельное приложение, к тому же требующее для своей работы исходных текстов «подопытной» программы, может использоваться лишь для отладки.

Итак, готовых «волшебных» решений проблемы переполнения не существует и сомнительно, чтобы они появились в обозримом будущем. Да и так ли они необходимы при наличии поддержки структурных исключений со стороны операционной системы и современных компиляторов?

Поиск уязвимых программ

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

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

int file(char *buff)
{	char *p; int a=0; char
 proto[10];
p=strchr(&buff[0],?:?);
if (p) {
for (;a!=(p-&buff[0]);a++)
 proto[a]=buff[a];
proto[a]=0;
if (strcmp(&proto[0],»file»))
 return 0; else
WinExec(p+3,SW_SHOW);
}
else WinExec(&buff[0],SW_SHOW);
return 1;
}

main(int argc,char **argv)
{if (argc>1) file(&argv[1][0]);}

Программа запускает файл, имя которого указано в командной строке. Попытка вызвать переполнение вводом цепочек различной длины, скорее всего, ни к чему не приведет. Но даже беглый анализ исходного кода позволит обнаружить ошибку, допущенную разработчиком. Если в имени файла присутствует символ «:», программа полагает, что имя записано в формате «протокол://путь к файлу/имя файла» и пытается выяснить, какой именно протокол указан. При этом она копирует название протокола в буфер фиксированного размера, полагая, что при нормальном ходе вещей его хватит для вмещения имени любого протокола. Но если ввести цепочку наподобие «ZZZZZZZZZZZZZZZZZZZZZZ:», произойдет переполнение буфера со всеми вытекающими последствиями.

Приведенный пример — один из самых простых. На практике нередко встречаются и более коварные ошибки, проявляющиеся лишь при стечении множества маловероятных самих по себе обстоятельств. Обнаружить подобные уязвимости только лишь перебором входных данных невозможно (тем не менее, даже такой поиск позволяет выявить огромное число ошибок в существующих приложениях). Значительно лучший результат дает анализ исходных текстов программы. Чаще всего ошибки переполнения возникают вследствие путаницы между длинами и индексами массивов, выполнения операций сравнения до модификации переменной, небрежного обращения с условиями выхода из цикла, злоупотребления операторами «++» и «—», молчаливого ожидания символа завершения и т.д. Например, конструкция «buff[strlen(str)-1]=0», удаляющая заключительный символ возврата каретки, будет «спотыкаться» на цепочках нулевой длины, затирая при этом байт, предшествующий началу буфера.

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

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

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

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

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

Заключение

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

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

Крис Касперски (kpnc@aport.ru) — независимый автор

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

Целочисленное переполнение может быть продемонстрировано с помощью одометр переполнение, механическая версия явления. Все цифры устанавливаются на максимум 9, и следующее приращение белой цифры вызывает каскад переходящих добавлений, устанавливающих все цифры на 0, но нет более высокой цифры (цифра 100000), которая могла бы измениться на 1, поэтому счетчик сбрасывается в ноль. Это обертывание в отличие от насыщения.

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

Наиболее частым результатом переполнения является сохранение наименее значимых представимых цифр результата; считается, что результат оборачивается вокруг максимума (т.е. по модулю степень системы счисления, обычно два в современных компьютерах, но иногда десять или другое основание).

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

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

На некоторых процессорах, таких как графические процессоры (графические процессоры) и процессоры цифровых сигналов (DSP), которые поддерживают арифметику насыщения, результаты переполнения будут «ограничены», т. е. установлены на минимум или максимум значение в представляемом диапазоне, а не обертывается.

Содержание

• 1 Источник
• 2 Флаги
• 3 Варианты определения и неоднозначность
• 4 Методы решения проблем целочисленного переполнения
  • 4.1 Обнаружение
  • 4.2 Предотвращение
  • 4.3 Обработка
  • 4.4 Явное распространение
  • 4.5 Поддержка языка программирования
  • 4.6 Насыщенная арифметика
• 5 Примеры
• 6 См. Также
• 7 Ссылки
• 8 Внешние ссылки

Источник

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

• 4 бита: максимальное представимое значение 2-1 = 15
• 8 битов: максимальное представимое значение 2-1 = 255
• 16 бит: максимальное представляемое значение 2-1 = 65 535
• 32 бита: максимальное представляемое значение 2-1 = 4294967 295 (наиболее распространенная ширина для персональных компьютеров с 2005 года),
• 64 биты: максимальное представляемое значение 2-1 = 18,446,744,073,709,551,615 (наиболее распространенная ширина для персональных компьютеров процессоров, по состоянию на 2017 год),
• 128 бит: максимальное представляемое значение 2-1 = 340,282,366,920,938,463,463,374,607,431,768,211,455

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

В частности, умножение или сложение двух целых чисел может привести к неожиданно маленькому значению, а вычитание из маленького целого числа может вызвать перенос на большое положительное значение (например, сложение 8-битных целых чисел 255 + 2 дает 1, что составляет 257 по модулю 2, и аналогичным образом вычитание 0 — 1 дает 255, дополнение до двух представление -1).

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

Если переменная имеет тип целое число со знаком, программа может сделать предположение, что переменная всегда содержит положительное значение. Целочисленное переполнение может привести к переносу значения и стать отрицательным, что нарушает предположение программы и может привести к неожиданному поведению (например, сложение 8-битного целого числа 127 + 1 дает -128, дополнение до двух до 128). (Решением этой конкретной проблемы является использование целочисленных типов без знака для значений, которые программа ожидает и предполагает, что они никогда не будут отрицательными.)

Флаги

Большинство компьютеров имеют два выделенных флага процессора для проверки условия переполнения.

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

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

Варианты определения и неоднозначность

Для беззнакового типа, когда идеальный результат операции выходит за пределы представимого диапазона типа, а возвращаемый результат получается путем упаковки, это событие обычно определяется как переполнение. Напротив, стандарт C11 определяет, что это событие не является переполнением, и заявляет, что «вычисление с участием беззнаковых операндов никогда не может переполниться».

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

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

Когда идеальный результат операции не является точным целым числом, значение переполнения может быть неоднозначным в крайних случаях. Рассмотрим случай, когда идеальный результат имеет значение 127,25, а максимальное представимое значение типа вывода — 127. Если переполнение определено как идеальное значение, выходящее за пределы представимого диапазона типа вывода, то этот случай будет классифицирован как переполнение. Для операций, которые имеют четко определенное поведение округления, может потребоваться отложить классификацию переполнения до тех пор, пока не будет применено округление. Стандарт C11 определяет, что преобразования из числа с плавающей запятой в целое число должны округляться до нуля. Если C используется для преобразования значения 127,25 с плавающей запятой в целое число, то сначала следует применить округление, чтобы получить идеальное целое число на выходе 127. Поскольку округленное целое число находится в диапазоне выходных значений, стандарт C не классифицирует это преобразование как переполнение..

Методы решения проблем целочисленного переполнения

Обработка целочисленного переполнения в различных языках программирования

Обнаружение

Реализация обнаружения переполнения во время выполнения UBSanдоступна для Компиляторы C.

В Java 8 есть перегруженные методы, например, такие как Math.addExact (int, int) , которые выбрасывают ArithmeticException в случае переполнения.

Группа реагирования на компьютерные чрезвычайные ситуации (CERT) разработала целочисленную модель с неограниченным диапазоном значений (AIR), в значительной степени автоматизированный механизм устранения переполнения и усечения целых чисел в C / C ++ с использованием обработки ошибок времени выполнения.

Предотвращение

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

Обработка

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

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

Явное распространение

, если значение слишком велико для сохранения, ему может быть присвоено специальное значение, указывающее, что произошло переполнение, а затем все последующие операции возвращают это значение флага. Такие значения иногда обозначаются как NaN, что означает «не число». Это полезно для того, чтобы можно было проверить проблему один раз в конце длинных вычислений, а не после каждого шага. Это часто поддерживается оборудованием с плавающей запятой, называемым FPU.

Поддержка языков программирования

В языках программирования реализованы различные методы предотвращения случайного переполнения: Ada, Seed7 (и некоторые варианты функциональных языков) запускают условие исключения при переполнении, тогда как Python (начиная с версии 2.4) легко преобразует внутреннее представление числа в соответствии с его ростом, в конечном итоге представляя его как long— чьи возможности ограничены только доступной памятью.

В языках с собственной поддержкой арифметики произвольной точности и безопасности типов (например, Python или Common Lisp ), числа автоматически увеличиваются до большего размера, когда происходят переполнения, или генерируются исключения (условия сигнализируются), когда существует ограничение диапазона. Таким образом, использование таких языков может помочь смягчить эту проблему. Однако в некоторых таких языках все еще возможны ситуации, когда может произойти целочисленное переполнение. Примером является явная оптимизация пути кода, который профилировщик считает узким местом. В случае Common Lisp это возможно с помощью явного объявления для обозначения типа переменной слова машинного размера (fixnum) и понижения уровня безопасности типа до нуля для конкретного блока кода.

Насыщенная арифметика

В компьютерной графике или обработке сигналов обычно работают с данными в диапазоне от 0 до 1 или от -1 на 1. Например, возьмите изображение в оттенках серого , где 0 представляет черный цвет, 1 представляет белый цвет, а значения между ними представляют оттенки серого. Одна операция, которую можно поддерживать, — это увеличение яркости изображения путем умножения каждого пикселя на константу. Насыщенная арифметика позволяет просто слепо умножать каждый пиксель на эту константу, не беспокоясь о переполнении, просто придерживаясь разумного результата, что все эти пиксели больше 1 (т. Е. «ярче белого» ) просто становятся белыми, а все значения «темнее черного» просто становятся черными.

Примеры

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

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

Необработанное арифметическое переполнение в программном обеспечении управления двигателем было основной причиной крушения в 1996 году первого полета ракеты Ariane 5. Считалось, что программное обеспечение не содержит ошибок, так как оно использовалось во многих предыдущих полетах, но в них использовались ракеты меньшего размера, которые генерировали меньшее ускорение, чем Ariane 5. К сожалению, часть программного обеспечения, в которой произошла ошибка переполнения, даже не требовалась. запускался для Ariane 5 в то время, когда он привел к отказу ракеты — это был процесс режима запуска для меньшего предшественника Ariane 5, который остался в программном обеспечении, когда он был адаптирован для новой ракеты. Кроме того, фактической причиной сбоя был недостаток в технической спецификации того, как программное обеспечение справлялось с переполнением, когда оно было обнаружено: оно выполнило диагностический дамп на свою шину, которая должна была быть подключена к испытательному оборудованию во время тестирования программного обеспечения во время разработки. но был связан с двигателями рулевого управления ракеты во время полета; из-за сброса данных сопло двигателя сильно отклонилось в сторону, что вывело ракету из-под контроля аэродинамики и ускорило ее быстрое разрушение в воздухе.

30 апреля 2015 года Федеральное управление гражданской авиации США объявил, что прикажет операторам Boeing 787 периодически перезагружать его электрическую систему, чтобы избежать целочисленного переполнения, которое может привести к потере электроэнергии и развертыванию воздушной турбины, и Boeing развернул обновление ПО в четвертом квартале. Европейское агентство по авиационной безопасности последовало 4 мая 2015 года. Ошибка возникает через 2 центсекунды (248,55134814815 дней), указывая на 32-битное подписанное целое число.

. очевидно в некоторых компьютерных играх. В аркадной игре Donkey Kong, невозможно продвинуться дальше 22 уровня из-за целочисленного переполнения его времени / бонуса. Игра берет номер уровня, на котором находится пользователь, умножает его на 10 и добавляет 40. Когда они достигают уровня 22, количество времени / бонуса равно 260, что слишком велико для его 8-битного регистра значений 256, поэтому он сбрасывается. до 0 и дает оставшиеся 4 как время / бонус — слишком мало для завершения уровня. В Donkey Kong Jr. Math при попытке вычислить число, превышающее 10 000, отображаются только первые 4 цифры. Переполнение является причиной знаменитого уровня «разделенного экрана» в Pac-Man и «Ядерного Ганди» в Civilization. Это также привело к появлению «Дальних земель» в Minecraft, которые существовали с периода разработки Infdev до Beta 1.7.3; однако позже это было исправлено в Beta 1.8, но все еще существует в версиях Minecraft Pocket Edition и Windows 10 Edition. В игре Super Nintendo Lamborghini American Challenge игрок может заставить свою сумму денег упасть ниже 0 долларов во время гонки, будучи оштрафованным сверх лимита оставшихся денег после уплаты сбора за гонка, в которой происходит сбой целого числа, и игрок получает на 65 535 000 долларов больше, чем он получил бы после отрицательного результата. Подобный сбой происходит в S.T.A.L.K.E.R.: Clear Sky, где игрок может упасть до отрицательной суммы, быстро путешествуя без достаточных средств, а затем перейти к событию, где игрока ограбят и у него заберут всю валюту. После того, как игра попытается забрать деньги игрока на сумму в 0 долларов, игроку выдается 2147482963 игровой валюты.

В структуре данных Покемон в играх с покемонами число полученных очков опыта хранится в виде 3-байтового целого числа. Однако в первом и втором поколениях группа опыта со средней медленной скоростью, которой требуется 1 059 860 очков опыта для достижения 100 уровня, по расчетам имеет -54 очка опыта на уровне 1. Поскольку целое число не имеет знака, значение превращается в 16 777 162. Если покемон набирает менее 54 очков опыта в битве, то покемон мгновенно перескакивает на 100-й уровень. Кроме того, если эти покемоны на уровне 1 помещаются на ПК, и игрок пытается их вывести, игра вылетает., из-за чего эти покемоны навсегда застревают на ПК. В тех же играх игрок, используя Редкие Конфеты, может повысить уровень своего Покемона выше 100 уровня. Если он достигает уровня 255 и используется другая Редкая Конфета, то уровень переполняется до 0 (из-за того, что уровень кодируется в один байт, например, 64 16 соответствует уровню 100).

Ошибка целочисленной подписи в коде настройки стека, выпущенная компилятором Pascal, помешала Microsoft / IBM MACRO Assembler Version 1.00 (MASM), DOS программа 1981 года и многие другие программы, скомпилированные с помощью того же компилятора, для работы в некоторых конфигурациях с объемом памяти более 512 КБ.

Microsoft / IBM MACRO Assembler (MASM) версии 1.00 и, вероятно, все другие программы, созданные с помощью того же Компилятор Паскаля имел ошибку переполнения целого числа и подписи в коде настройки стека, что не позволяло им работать на новых машинах DOS или эмуляторах в некоторых распространенных конфигурациях с более чем 512 КБ памяти. Программа либо зависает, либо отображает сообщение об ошибке и выходит в DOS.

В августе 2016 года автомат казино в Resorts World Casino распечатал призовой билет на 42 949 672,76 долларов в результате ошибки переполнения. Казино отказалось выплатить эту сумму, назвав это неисправностью, используя в свою защиту то, что в автомате четко указано, что максимальная выплата составляет 10 000 долларов, поэтому любой превышающий эту сумму приз должен быть результатом ошибки программирования. Верховный суд штата Айова вынес решение в пользу казино.

См. Также

• Переполнение буфера
• Переполнение кучи
• Переключение указателя
• Тестирование программного обеспечения
• буфер стека переполнение
• Статический анализ программы
• Сигнал Unix

Ссылки

Внешние ссылки

• Фракция № 60, Базовое целочисленное переполнение
• Фракция № 60, Целочисленная защита большого цикла
• Эффективная и Точное обнаружение целочисленных атак
• Классификация угроз WASC — Целочисленные переполнения
• Общие сведения о целочисленном переполнении в C / C ++
• Двоичное переполнение — двоичная арифметика
• Стандарт ISO C11