Как мы можем быть уверены, что нижние компоненты компьютерного программирования, такие как компиляторы, ассемблеры, машинные инструкции и т. Д., Безупречны?

57

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

С технической точки зрения, как тестируются компиляторы и ассемблеры? (Я полагаю, это связано с проблемой остановки !!)

Судип Бхандари
источник
36
Возможно, вы захотите начать свое исследование с «Кена Томпсона Хака». См. « Размышления о доверии»
Брайан Оукли,
7
Вот пример компилятора, для которого есть доказательство корректности: compcert.inria.fr/doc/index.html
Джорджио
8
Большинство компиляторов / компоновщиков / ассемблеров тестируются наиболее глубоко, их часто используют в самых разных обстоятельствах. Для поиска ошибок нет ничего лучше, чем миллионы пользователей, использующих ваш компилятор.
Барт ван Инген Шенау
3
и добавьте операционную систему в список.
Эрик Эйдт

Ответы:

104

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

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

SQLite содержит около 73 тысяч строк кода, а набор тестов - около 91378 тысяч строк кода, что в 1250 раз больше, чем самого SQLite. Я ожидаю, что компиляторы и другие основные инструменты имеют аналогичные соотношения. Современные процессоры в основном разработаны с использованием программного обеспечения, с использованием языков описания аппаратного обеспечения, таких как Verilog или VHDL, и на них также выполняются тесты программного обеспечения, а также специализированные выводы ввода-вывода для проведения самотестирования на месте производства.

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

как зовут
источник
7
Я часто задавался вопросом о том же самом вопросе, что и ОП, но в отношении СУБД. Вы привели отличный пример, который ответил на него в контексте SQLite. Спасибо!
Брэндон
7
+1, но почему-то я сомневаюсь, что «компиляторы и другие основные инструменты имеют схожие соотношения».
Мердад
5
Обратите внимание, что (1) SQLite на самом деле имеет два набора тестов, с нетривиальной избыточностью между ними, и (2), несмотря на это, в SQLite все еще обнаруживаются ошибки.
Матье М.
7
У меня сложилось впечатление, что SQLite является одним из наиболее «тщательно протестированных» фрагментов программного обеспечения (с точки зрения строк тестирования кода / строк операционного кода), доступных для общего пользования, причем даже в большей степени, чем многие компиляторы. Если не что иное, полнофункциональный компилятор - это огромная часть программного обеспечения, и я не могу себе представить, чтобы его было в тысячу раз больше, чем тестируемого кода. (Сообщается, что в GCC содержится до 14,5 миллионов строк. Кажется маловероятным, чтобы либо коллекция компиляторов была только 14k LOC, либо что у них есть тестовая кодовая база из 14 миллиардов строк, расположенная сбоку! :-P)
David Z
2
@DavidZ: Это, конечно, единственный проект, который я знаю, который использует, например, расширенное тестирование OOM (они используют инжектор сбоя для теста и воспроизводят их снова и снова, терпя неудачу при 1-м, затем 2-м распределении ... до полного теста выполняется).
Матье М.
46

С точки зрения непрофессионала:

  1. Тебе нельзя.
  2. Компиляторы и интерпретаторы тестируются модульно, как и любое другое (профессиональное) программное обеспечение.
  3. Успешный тест не означает, что программа не содержит ошибок, это только означает, что ошибок не обнаружено.
  4. Широкая пользовательская база, использующая компилятор в течение длительного времени, является хорошим индикатором того, что в нем очень мало ошибок, потому что пользователи обычно тестируют кейсы, о которых дизайнеры не думали.
  5. Быть открытым исходным кодом также является хорошим показателем. «Учитывая достаточное количество глазных яблок, все ошибки мелкие ... Учитывая достаточно большой бета-тестер и базу со-разработчиков, почти каждая проблема будет охарактеризована быстро, и исправление будет очевидно для кого-то». , Компилятор с закрытым исходным кодом может иметь ошибки, которые возникают в очень специфические моменты времени или которые генерируют неоптимальный машинный код, и компания, стоящая за ним, может просто не раскрывать свое существование и придавать ему очень низкий приоритет в дорожной карте продукта.

Нижняя линия:

Я бы сказал, пойти на ООП ( O ld, O pen и P opular). Я только что составил эту аббревиатуру.

Тулаинс Кордова
источник
19
+1 За изобретение еще одного TLA (трехбуквенного аббревиатуры) - в мире их пока недостаточно.
s1lv3r
34
Кроме того, ООП еще не имел никакого значения в компьютерном программировании. Так что KTT (слава тебе)!
Пьер Арло,
15
Комментарий Пьера - шутка @Dannnno.
Яннис
19
В качестве альтернативы это может быть P opular, O ld и O pen. ;) На самом деле, вот как бы я оценил их в порядке важности.
jpmc26
23
@ jpmc26 Я бы выбрал Практические, Старые, Открытые и Популярные. Что касается аббревиатуры ...
StupidOne
24

Это черепахи все время вниз.

Нет ничего определенного У вас нет выбора, кроме как рассчитывать на рейтинг доверия.

Вы можете думать об этом как о стеке: Math> Physics> Hardware> Firmware> Operating System> Assembler / Compiler / etc

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

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

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

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

voutasaurus
источник
17

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

За 25 с лишним лет программирования на C, C ++ и Java я обнаружил:

  • две ошибки из-за ошибки компилятора (gcc и SunOS C)
  • примерно раз в год или два ошибка из-за проблемы Java JVM (обычно связанной с потреблением памяти / сборкой мусора)
  • примерно раз в месяц или два ошибка в библиотеке, которая часто исправляется с помощью последней версии или возвращается к предыдущей версии библиотеки

Все остальные ошибки напрямую связаны с ошибкой или, чаще, с отсутствием понимания того, как работает библиотека. Иногда то, что кажется ошибкой, происходит из-за несовместимости, например, как изменилась структура класса Java, что сломало некоторые библиотеки AOP.

Эд Грибель
источник
Мне любопытно - какие годы для каких языков? Еще в дни EGCS, прежде чем C ++ был должным образом стандартизирован, ошибки компилятора не было так трудно найти ...
Чарльз Даффи
3
Чем больше неясен компилятор, процессор или язык, тем легче найти ошибку в компиляторах (перед кем-то еще), поэтому найти 2 в GCC C приятно :)
Surt
1
Так получилось, что я потратил около месяца впустую, предполагая, что проблема, с которой я столкнулся, была в моих сценариях GDB, или мое понимание того, что я изучал. В конце концов я стал подозрительным, упростил свой тестовый пример и обнаружил недостаток проекта в библиотеке (libkvm), из-за которого отладчик ядра не смог получить доступ к определенным адресам из дампа ядра. Т.е. YMMV - и я счастлив, когда обнаружил новую ошибку в коде передо мной, особенно то, что я использую, а не разрабатываю.
Арли Стивенс
Конечно, это была не ошибка компилятора или даже одна из наиболее часто используемых библиотек. И по правде говоря, я не нахожу ошибок в тех с любой частотой вообще.
Арли Стивенс
@ArlieStephens Там есть урок: упрощение тестового примера - это то, что вы должны делать на раннем этапе, когда не удается найти проблему. Независимо от того, является ли проблема вашей или другой код, это поможет вам сузить ее. Часто, если проблема в другом коде, это приводит к «доказательству и модульным тестам, демонстрирующим» это.
jpmc26
8

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

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПРЕДОСТАВЛЯЕТСЯ «КАК ЕСТЬ», БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ, ЯВНЫХ ИЛИ ПОДРАЗУМЕВАЕМЫХ, ВКЛЮЧАЯ, НО НЕ ОГРАНИЧИВАЯСЯ ГАРАНТИИ ТОВАРНОГО ОБЕСПЕЧЕНИЯ, ПРИГОДНОСТИ ДЛЯ ОСОБЫХ ЦЕЛЕЙ И НЕЗАКРЕПЛЕНИЙ.

Из лицензионного соглашения Microsoft Word

, За исключением ограниченной гарантии и в максимальной степени, разрешенной применимым законодательством, Microsoft и ее поставщики предоставляют Программное обеспечение и услуги поддержки (если таковые имеются) КАК ЕСТЬ И СО ВСЕМИ НЕИСПРАВНОСТЯМИ, и настоящим отказываются от всех других гарантий и условий, явных, подразумеваемых или законодательно, включая, но не ограничиваясь, любые (если таковые имеются) подразумеваемые гарантии, обязанности или условия товарной пригодности, пригодности для конкретной цели, надежности или доступности, точности или полноты ответов, результатов, работы, подобной работе, отсутствие вирусов и небрежность, все в отношении Программного обеспечения, а также предоставление или неспособность предоставлять поддержку или другие услуги, информацию, программное обеспечение и связанный контент через Программное обеспечение или иным образом возникающие в результате использования Программного обеспечения. ,

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

Программное обеспечение похоже на научную теорию, и считается, что оно работает так, как указано, пока оно не работает.

Тоби аллен
источник
+1 за указание на то, что в самой лицензии указано, что ни одно программное обеспечение не является идеальным.
Тулаинс Кордова
3
Я был рад отметить отклонение от этой практики в IBM ViaVoice для Mac. Вместо обычного «если это не работает, слишком плохо», они фактически сказали что-то вроде «Программное обеспечение гарантированно работает так, как указано».
WGroleau
1
Простым переводом этой конкретной части формулировки гарантии является: «Это может быть часть программного обеспечения, или это может быть кусок дерьма. Это может сработать. Это может не сработать. Даже если это работает, это может не сработать делай, что хочешь. Кстати, мы могли бы украсть кое-что у кого-то еще. Очень плохо. Мы получили твои деньги и использовали их, чтобы нанять множество адвокатов. ИГРА! НА! Ня-ня -nyah-Nyah-nyaaah-Неее!». :-)
Боб Джарвис
2
@BobJarvis: мое любимое гарантийное заявление, используемое в некоторых программах с открытым исходным кодом (например, nmap IIRC), звучит так: «Если он сломается, вы сохраните обе части».
Питер Кордес
Это утверждение вездесуще в программном обеспечении с открытым исходным кодом и множестве бесплатных программ с закрытым исходным кодом. Он не присутствует в большинстве коммерческих платных лицензий на программное обеспечение.
JWG
2

Как автор компилятора для математического языка *, из моего опыта я могу сказать, что теоретически вы не можете. И некоторые из ошибок просто дают неправильные результаты, такие как (из моего списка позора), вычисление 6/3*2справа 6/(3*2)и вывод 1 без сбоев или бессмысленные ошибки компиляции.

Но IMHO, многие компиляторы не имеют столько ошибок, как другие программы, потому что:

  • Написание юнит-тестов легко. Каждое утверждение представляет собой единицу, и вы можете написать тесты так просто, как:test_unit("2+(-2)*(-2+1)*3+1",9);
  • Программа представляет собой комбинацию операторов, и для любой программы для вывода правильного результата каждый отдельный оператор должен давать правильный результат (в основном). Поэтому очень маловероятно, что будут какие-либо ошибки, пока программа дает правильный результат.
  • По мере увеличения размера и количества написанных программ вероятность обнаружения ошибок резко возрастает.

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

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

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

Мой скромный математический язык *

Gorkem
источник
Intel чертовски тестирует свои процессоры, выполняя последовательности произвольных инструкций и сравнивая, в частности, с программной моделью: tweakers.net/reviews/740/4/… . Вот почему вы часто видите действительно малоизвестные опечатки из-за очень маловероятного сочетания инструкций в необычном режиме.
Питер Кордес
0

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

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

Но безупречно, нет. Хотя вы также можете увидеть, как люди в Stack Exchange получают впечатляющее представление о деталях производительности, о соответствии стандартам и их причудах, всегда есть недостатки и недостатки, особенно когда разные люди по-разному оценивают недостатки.

Dronz
источник
-1

Чтобы показать, что основные системы безупречны, вы либо

а) Нужно доказать, что они безупречны

  1. Математическое доказательство
  2. Реально возможно только для тривиальных программ

б) сделать исчерпывающий тест

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

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

Пример: вы хотите протестировать 8-символьный ввод utf-8 в какое-то поле, вы делаете выбор, чтобы обрезать ввод в 8 раз по сравнению с максимальной длиной 6 utf-8 в байтах, что дает 8 * 6 = 48 байтов, чтобы фактически иметь конечное количество возможностей.

Теперь вы можете подумать, что вам нужно только протестировать 1,112,064 действительных кодовых точек каждого из 8 символов, т.е. 1,112,064 ^ 8 (скажем, 10 ^ 48) тестов (что уже вряд ли возможно), но на самом деле вы должны проверить каждое значение каждого из 48 байтов или 256 ^ 48, что составляет около 10 ^ 120, что является такой же сложностью, что и шахматы по сравнению с общим числом атомов во вселенной примерно 10 ^ 80.

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

а) проверить хороший и плохой образец.

б) покрытие кода, т.е. Попробуйте проверить каждую строку кода, которая относительно проста для большинства кода. Теперь вы можете задаться вопросом, что там за последний 1% кода, который вы не можете протестировать ... ошибки, мертвый код, аппаратные исключения и т. Д.

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

d) проверка данных, проверка числа образцов с граничным значением, общими проблемными значениями и магическими числами, ноль, -1, 1, мин +/- 1, макс +/- 1, 42, rnd значения. Если это не дает вам покрытия пути, вы знаете, что вы не уловили все значения в своем анализе.

Если вы уже делаете это, вы должны быть готовы к экзамену ISTQB Foundation.

Surt
источник