Синтез и проверка драйверов устройств - Device driver synthesis and verification

Архитектура драйвера устройства.
Драйвер устройства.

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

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

Мотивация для автоматического синтеза и проверки драйверов

Драйверы устройств являются основным неисправным компонентом большинства систем. В Открытая инфраструктура Беркли для сетевых вычислений (BOINC) обнаружил, что сбои ОС в основном вызваны плохо написанным кодом драйвера устройства.[1] В Windows XP, драйверы составляют 85% зарегистрированных отказов. в Linux На код драйвера устройства ядра 2.4.1 приходится около 70% размера кода.[2] Ошибка драйвера может привести к сбою всей системы, поскольку она работает в режим ядра. Эти результаты привели к разработке различных методологий и методов проверки драйверов устройств. Альтернативой была разработка методов, которые могут надежно синтезировать драйверы устройств. Меньшее участие человека в процессе разработки и правильная спецификация устройства и операционных систем могут привести к созданию более надежных драйверов.

Другой причиной для синтеза драйверов является большое количество разновидностей операционных систем и комбинаций устройств. Каждый из них имеет свой собственный набор элементов управления вводом / выводом и технические характеристики что затрудняет поддержку аппаратных устройств в каждой из операционных систем. Таким образом, возможность использования устройства с операционной системой требует наличия соответствующей комбинации драйверов устройства. Поставщики оборудования обычно поставляют драйверы для Windows, Linux и Mac OS, но из-за высоких затрат на разработку или перенос и техническая поддержка трудности они не могут предоставить драйверы на всех платформах. Метод автоматического синтеза может помочь поставщикам в предоставлении драйверов для поддержки любых устройств в любой операционной системе.

Проверка драйверов устройств

Есть две проблемы, которые ограничивают тестирование драйверов устройств.

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

Волна проверки драйверов устройств была инициирована Microsoft через их SLAM проект еще в 2000 году. Мотивом для проекта было то, что 500 000 сбоев, о которых сообщалось в день, были вызваны одним видеодрайвером, что вызвало обеспокоенность по поводу большой уязвимости при использовании сложных драйверов устройств. Более подробную информацию можно найти здесь, в речи Билла Гейтса. С тех пор было предложено большое количество статических методов и методов времени выполнения для обнаружения и изоляции ошибок.

Статический анализ

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

Компиляторы

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

Другой подход - использовать компиляция мета-уровня (MC),.[3] Созданные для этой цели метакомпиляторы могут расширять компиляторы легковесными, специфичными для системы средствами проверки и оптимизаторами. Эти расширения должны быть написаны разработчиками системы на языке высокого уровня и динамически связаны с компиляторами для выполнения строгого статического анализа.

Проверка модели программного обеспечения

Проверка модели программного обеспечения - это алгоритмический анализ программ для подтверждения свойств их выполнения.[4] Это автоматизирует рассуждения о поведении программы относительно заданных правильных спецификаций. Проверка модели и символьное выполнение используются для проверки критически важных для безопасности свойств драйверов устройств. Входными данными для проверки модели являются программа и временные свойства безопасности. Результатом является доказательство того, что программа верна, или демонстрация того, что существует нарушение спецификации с помощью контрпримера в виде определенного пути выполнения.

Инструмент SDV (Static Driver Verifier)[5] от Microsoft использует статический анализ для драйверов устройств Windows. Механизм внутреннего анализа SLAM использовал проверку модели и символьное выполнение для статической проверки времени компиляции. Правила, которые должны соблюдаться драйверами для каждого API, указаны на языке C SLIC (язык спецификации для проверки интерфейса). Механизм анализа находит все пути, которые могут привести к нарушению правил использования API, и представляются как пути ошибок исходного уровня в исходном коде драйвера. Внутри он абстрагирует код C до логической программы и набора предикатов, которые являются правилами, которые должны соблюдаться в этой программе. Затем он использует проверку символьной модели[6] для проверки предикатов булевой программы.

В средство проверки моделей BLAST (инструмент проверки программного обеспечения Berkeley Lazy Abstraction Software)[7] используется для поиска ошибок безопасности памяти и неправильной блокировки в коде ядра Linux. Он использует алгоритм абстракции, называемый ленивой абстракцией.[8] построить модель из кода драйвера C. Он успешно проверил свойства временной безопасности программ на языке C, содержащих до 50 тыс. Строк кода. Он также используется для определения того, влияет ли изменение в исходном коде на подтверждение собственности в предыдущей версии и демонстрируется в драйвере устройства Windows.

Avinux[9] - еще один инструмент, который облегчает автоматический анализ дисков устройств Linux и построен на основе ограниченного средства проверки моделей CBMC.[10] Существуют методы локализации неисправности для поиска места ошибки, поскольку эти инструменты проверки модели возвращают длинную трассировку примера счетчика, и трудно найти точное место ошибки.[11]

Анализ времени выполнения

Динамический анализ программы выполняется путем запуска программы с достаточным количеством тестовых входных данных для получения интересного поведения. Безопасное вождение[12] это система с низкими накладными расходами для обнаружения и восстановления нарушений безопасности типов в драйверах устройств. Всего лишь на 4% изменений в исходном коде сетевых драйверов Linux они смогли реализовать SafeDrive и обеспечить лучшую защиту и восстановление ядра Linux. Похожий проект, использующий оборудование для изоляции драйверов устройств от основного ядра, - это Nook.[13] Они помещают драйверы устройств в отдельный домен защиты оборудования, называемый «укромными уголками», и имеют отдельные настройки разрешений для каждой страницы, гарантируя, что драйвер не изменяет страницы, которые не находятся в его домене, но может читать все данные ядра, поскольку они используют одно и то же адресное пространство .

Еще одна аналогичная работа в этой области - автоматическое восстановление операционных систем из-за сбоев драйверов. МИНИКС 3[14] это операционная система, которая может локализовать основные неисправности, обнаруживать дефекты и оперативно заменять неисправные компоненты.

Синтез драйверов устройств

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

Языки спецификации интерфейса

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

Дьявол[15] обеспечивает высокую четкость связи с устройством. Компоненты оборудования представлены портами ввода-вывода и отображенными в память регистрами. Затем эти спецификации преобразуются в набор макросов C, которые можно вызывать из кода драйвера, что устраняет ошибку, вызванную программистом при написании функций низкого уровня. NDL[16] представляет собой расширение Devil, описывающее драйвер с точки зрения его рабочего интерфейса. Он использует синтаксис определения интерфейса Devil и включает набор определений регистров, протоколы для доступа к этим регистрам и набор функций устройства. Затем функции устройства преобразуются в серию операций на этом интерфейсе. Для генерации драйвера устройства необходимо сначала написать функции драйвера на этих языках спецификации интерфейса, а затем использовать компилятор, который сгенерирует код драйвера низкого уровня.

HAIL (язык интерфейса аппаратного доступа)[17] - еще один предметно-ориентированный язык спецификации драйверов устройств. Разработчик драйвера должен написать следующее.

  1. Описание карты регистров, которое описывает различные регистры устройства и битовые поля из таблицы данных устройства.
  2. Описание адресного пространства для доступа к шине.
  3. Реализация устройства в конкретной системе.
  4. Инвариантная спецификация, ограничивающая доступ к устройству.

Компилятор HAIL принимает эти входные данные и переводит спецификацию в код C.

Совместная разработка аппаратного и программного обеспечения

При совместном проектировании аппаратного программного обеспечения разработчик определяет структуру и поведение системы с помощью конечных автоматов, которые взаимодействуют между собой. Затем на этих конечных автоматах выполняется серия испытаний, моделирования и формальной проверки, прежде чем будет принято решение, какие компоненты входят в аппаратное обеспечение, а какие - в программное обеспечение. Аппаратное обеспечение обычно выполняется в виде программируемых вентильных матриц (FPGA) или специализированных интегральных схем (ASIC), тогда как программная часть переводится на язык программирования низкого уровня. Этот подход в основном применяется во встроенных системах, которые определяются как набор программируемых частей, которые непрерывно взаимодействуют с окружающей средой через датчики. Существующие методы[18] предназначены для генерации простых микроконтроллеров и их драйверов.

Автономный синтез драйверов

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

Инструмент Термит[19] требуется три спецификации для создания драйвера.

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

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

Еще одна очень интересная попытка взлома была предпринята RevNIC,[20] который генерирует конечный автомат драйвера путем обратного проектирования существующего драйвера для создания переносимых и безопасных драйверов для новых платформ. Чтобы реконструировать драйвер, он перехватывает аппаратные операции ввода-вывода, выполняя драйвер с использованием символьных и конкретных исполнений. Выходные данные прослушки поступают на синтезатор, который восстанавливает граф потока управления исходного драйвера из этих нескольких трассировок вместе с стандартным шаблоном для соответствующего класса устройств. Используя эти методы, исследователи портировали некоторые драйверы Windows для сетевых интерфейсов на другие Linux и встроенные операционные системы.

Критика

Хотя многие инструменты статического анализа широко используются, многие из Водитель Инструменты синтеза и проверки не получили широкого распространения на практике. Одна из причин в том, что водители имеют тенденцию поддерживать несколько устройств, и работа по синтезу драйверов обычно генерирует один драйвер на каждое поддерживаемое устройство, что потенциально может привести к большому количеству драйверов. Другая причина заключается в том, что драйверы также выполняют некоторую обработку, а модель драйверов конечного автомата не может отображать обработку.[21]

Вывод

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

Рекомендации

  1. ^ Арчана Ганапати, Виджи Ганапати и Дэвид Паттерсон. "Анализ сбоев ядра Windows XP ". В материалах конференции по администрированию больших систем, 2006 г., 2006 г.
  2. ^ А. Чоу, Дж. Ян, Б. Шельф, С. Халлем и Д. Энглер. Эмпирическое исследование ошибок операционных систем. В СОСП, 2001 г.
  3. ^ Энглер, Доусон и Чельф, Бенджамин и Чоу, Энди и Халлем, Сет. "Проверка системных правил с помощью системных расширений компилятора, написанных программистом ". В материалах 4-й конференции симпозиума по разработке и внедрению операционных систем, 2000 г.
  4. ^ Джхала, Ранджит и Маджумдар, Рупак. «Проверка модели программного обеспечения». В обзоре вычислений ACM. 2009 г.
  5. ^ Томас Болл, Элла Бунимова, Байрон Кук, Владимир Левин, Якоб Лихтенберг, Кон МакГарви, Бохус Ондрусек, Шрирам Раджамани. и Абдулла Устунер. "Тщательный статический анализ драйверов устройств ", В SIGOPS Oper. Syst. Rev, Vol. 40, 2006.
  6. ^ Макмиллан, Кеннет Л. «Проверка символической модели». Kluwer Academic Publishers, 1993.
  7. ^ Томас А. Хензингер, Ранджит Джала, Рупак Маджумдар и Грегуар Сутре. "Проверка программного обеспечения с помощью BLAST ". В СПИН, 2003.
  8. ^ Томас А. Хензингер, Ранджит Джала, Рупак Маджумдар и Грегуар Сутре. «Ленивая абстракция», на конференции ACM SIGPLAN-SIGACT по принципам языков программирования, 2002.
  9. ^ Х. Пост, В. Кюхлин. «Интеграция статического анализа для проверки драйверов устройств linux». В 6-м Междунар. Конф. по интегрированным формальным методам, 2007.
  10. ^ Эдмунд Кларк, Даниэль Кренинг и Флавио Лерда. «Инструмент для проверки программ ANSI-C». В TACAS, 2004 г.
  11. ^ Томас Болл, Маюр Найк и Шрирам К. Раджамани. «От симптома к причине: локализация ошибок в следах контрпримера». Уведомления ACM SIGPLAN, 2003 г.
  12. ^ Фэн Чжоу, Джереми Кондит, Захари Андерсон, Илья Баграк, Роб Энналс, Мэтью Харрен, Джордж Некула и Эрик Брюэр. "SafeDrive: безопасные и восстанавливаемые расширения с использованием языковых методов ". В 7-м OSDI, 2006.
  13. ^ Майкл М. Свифт, Стивен Мартин, Генри М. Леви и Сьюзен Дж. Эггерс. "Nooks: архитектура для надежных драйверов устройств ". В 10-м ACM SIGOPS, 2002.
  14. ^ Йоррит Н. Гердер, Герберт Бос, Бен Гра, Филип Хомбург и Эндрю С. Таненбаум. "MINIX 3: высоконадежная операционная система с самовосстановлением ". В SIGOPS Oper. Syst. Rev.40, 2006.
  15. ^ Фабрис Мерильон, Лоран Ревельер, Шарль Консель, Рено Марле и Жиль Мюллер. " Дьявол: IDL для программирования оборудования ". В материалах 4-й конференции симпозиума по разработке и внедрению операционных систем, том 4, 2000 г.
  16. ^ Кристофер Л. Конвей и Стивен А. Эдвардс. "NDL: предметно-ориентированный язык для драйверов устройств ". Уведомления ACM SIGPLAN 39, 2004 г."
  17. ^ Дж. Сун, В. Юань, М. Каллахалла и Н. Ислам. "HAIL: язык для простого и правильного доступа к устройствам ". В материалах конференции ACM по встроенному программному обеспечению, 2005 г.
  18. ^ Феличе Баларин и др. "Аппаратно-программное совместное проектирование встроенных систем. Подход ПОЛИС. "Kluwer Academic Publishers, 1997.
  19. ^ Леонид Рыжик, Питер Чубб, Игорь Куз, Этьен Ле Сюер и Гернот Хейзер. "Автоматическое устройство Водитель синтез с Termite ». В материалах 22-го симпозиума ACM по принципам операционных систем, 2009 г.
  20. ^ Виталий Чипунов и Джордж Кандеа. "Обратный инжиниринг драйверов двоичных устройств с RevNIC ". 5-я выставка ACM SIGOPS / EuroSys, 2010 г.
  21. ^ Асим Кадав и Майкл М. Свифт «Понимание современных драйверов устройств» в материалах 17-й конференции ACM по архитектурной поддержке языков программирования и операционных систем

внешняя ссылка