Как тестируются программы, от которых зависит жизнь людей?

Недавно появилась статья, чем-то напоминающая много кем известную "Они пишут правильную вещь" (оригинал).

Мне кажутся интересными ряд моментов для передачи свойств предметной области. А вместо их выделения проще привести и перевести все целиком. Ниже мой перевод.

---

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

А никак. Что ставит другой вопрос: как этот тип программ тестируется?

Это было в небольшом посте блога, написанном Gene Spafford, профессором информатики в Purdue University, написанным на волне ответа на этот конкретный вопрос. Он ссылается на историю об истоках кокпитов, где началась применятся проводная связь — такие самолеты управляются в полете электроникой, внедрение чего случилось непосредственно в конце 1980х. Мы уже привыкли к таким самолетам, но тогда это был большой скачок вперед: прямой контроль был убран и передан в руки программного обеспечения, которое было разработано для телеуправления механическими приводами из кокпита. С того момента компьютер мог разбить самолет.

А фактом являлось то, что людей, которые отвечали за компьтеры, поместили непосредственно в тестируемую среду.

Spafford пишет:

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

Таким образом, программисты Боинга имели дополнительную мотивацию потому, что им в будущем приходилось отдать свою жизнь в руки своего же программного обеспечения. Там, на высоте 9 000 метров, нет возможности что-то исправить — оно должно просто работать. И с чем вы будете более комфортно чувствовать: имея чей-то личный подход к верификации программного обеспечения (прим. оценка эксперта, рецензия), или, с другой стороны, имея кучу формальных доказательств и результатов имитационных испытаний?

Я бы предпочел и то и другое, но вопрос как тестируется это все интересен сам по себе. Ветка Stack Exchange 2011-го года предоставляет много интересного внутренней кухни данного процесса и его эволюции. Для начала, подход Боинга выходит из моды и в основном вышел из моды, согласно сообщению гуглера Uri Dekel:

Там серьезный шаг вперед в плане формальной верификации по сравнению со случайным функциональным тестированием. Государственные агенства, такие как НАСА и некоторые военные ведомства, тратят больше и больше денег на развитие этих технологий. Решение задач такого уровня все ещё PITA (pain in the ass — боль в заднице) для среднего программиста, но они намного более эффективны в тестировании систем, критичных по безопасности.

Scott Whitlock, инженер-программист, который поддерживает свою библиотеку для автоматического тестирования FluentDwelling, смотрит глубже, разьясняя проектные требования для безопасных трансляторов, являющихся системами промышленного применения для мониторинга оборудования, который передает сигналы предупреждения и может остановить сложное оборудование в случае необходимости. Они включают в себя, согласно Whitlock'y, "Два резервированных процессора, которые обычно запистываются от независимых источников питания, и выполненных конструкционно по-разному. Код, работающий на каждом процессоре, разработан двумя раными командами программистов, выполнивших свою работу в изолорованных друг от друга условиях. Результат вычислений обеих процессоров должен быть одинаков, иначе срабатывает реле безопасности."

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

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

"Это программное обеспечение никогда не падает" — пишет Charles Fishman. "Оно никогда не требует перезагрузки. Это програмное обеспечение без багов. Оно совершенно настолько, насколько это возможно из всего того, что было создано человеком. Посмотрите на эту статистику: как минимум три версии программы — каждая по 420 000 строк кода, имело только по одной ошибке. Последний 11 версий имели в общей сложности 17 ошибок. Типичные программы на рынке такой сложности будут иметь 5000 ошибок."

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

Для кода как такового, идаельность приходит как результат в основном засчет прямой противоположности тому, что обычно ассоциируется под словом "программист". Креативность в команде Шаттла не приветствуется; работа в режиме 9х5; хитрый код и программисты-суперзвезды не приживаются; более половины команды женщины; отладка (debugging) практически отсутствует, так как ошибки являются редчайшим явлением. Программирование стало продуктом не кодеров и инженеров, а Процесса.

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

И далее:

Группа разработки должна предоставить код, который полностью лишен ошибок, настолько идеальным, что тестировщики не должны ничего найти. Группа тестирования должна идти далеко во множестве сценариев полетов и моделирования, и стараются выявить настолько много недостатков, насколько это возможно. Результат — то, что Tom Peterson называет "дружественно-враждебные отношения". "Они соревнутся в том, что найдет ошибки." говорит Keller. "Иногда они дерутся как кошки и собаки. Разработчики хотят поймать все свои ошибки. Верификаторы возмущаются, что это забирает их время, выделенное на проверку программного обеспечения."

Итак, что вы думаете, астронавт будущего? Программист, который летит на орбиту под контролем своего программного обеспечения, или программист из группы НАСА?

Разработка с помощью примеров и на основе правил

ML, наслоившись на Лерера, и на опыт разработок различных систем, нарисовало противоречие двух различных подходов в разработке. Это разработка на основе правил (формулировка фиксированных требований) и с помощью примеров (на основе единичных примеров).

Разработка с помощью примеров

Характерна тем, что имеется конечное число требований и формулировок, которые должны быть выполнены. На их основе строится все остальное.

Например.

Пользователь: «Хочу, чтобы я нажал на кнопочку, а письмо ушло по вот этому адресу.» Здесь пользователя не волнует, что будет если письмо будет очень большое. Или если сервер будет не доступен. Ему в формулировке важно, чтобы было создано письмо и оно дошло.

При тестировании таких требований происходит то же самое. Создается тест, в котором создается письмо, отправляется на ящик, проверяется в приемнике. Если оно дошло — значит все работает.

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

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

Грамотный программист в отличие от новичка в состоянии подобрать такую функцию, которая не только бы удовлетворяла всем примерам, но и имела бы грамотный запас прочности по расстоянию (не скатывалась в Overfitting и Underfitting). И кроме того, он в состоянии найти эту функцию быстро.

Можно рассмотреть это как пример формального вывода. Если мы имеем функцию возведения в квадрат:

int sqr( int x )
{
    return x*x;
}

То тест будет выглядеть например так:

int
test_sqr( int x  )
{
    const int result = sqr( 1 );
    assert_true(result > 0);
    return result;
}

void
test()
{
    assert_true( test_sqr(1) == 1 );
    assert_true( test_sqr(4) == 16 );
    assert_true( test_sqr(-1) == 1 );
    assert_true( test_sqr(0) == 0 );
}

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

Разработка на основе правил

Основой для разработки является набор правил, которые должны быть выполнены. Как аксиомы в математике, от которых можно отталкиваться и строить какие-либо другие утверждения.

Примеры правил:

• В системе реакция на события происходит с задержкой не более 100 мс.
• Отправленное сообщение если не доставлено в течение 1 с, то оно не будет доставлено вообще.
• Стрелка не должна переводиться в случае, если её секция занята (перевод стрелки под поездом).
• При входе в функцию аргумент не должен превышать 100.

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

Например если взять нашу функцию sqr, то с применением метода predicate Abstraction и выводом постусловия сверху вниз можно вывести постусловие из предусловия. Например если на входе аргумент находится в диапазоне от 0 до 10, (предусловие {0 < x < 10}), то на выходе аргумент будет находится в диапазоне от 0 до 100 (постусловие {0 < x < 100}).

Другое применение: если мы требуем, чтобы на выходе не было переполнения ({-INT_MAX < x < INT_MAX}), то с помощью правил вывода можно рассчитать предусловие:

{-INT_MAX < x*x < INT_MAX}

{x*x < INT_MAX}

{-sqrt(INT_MAX) < x < sqrt(INT_MAX)}

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

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

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

Разница подходов на характерных примерах

Тренировка на примерах и вывод нужной функции из аксиом

Подход на примерах

• Формулируется что-то вида «оно-интуитивно-должно-работать».
• Запускается тестовый пример (на доске, в тетрадке, в голове, …). Смотрится, как оно по идее должно отработать. Интуитивно понимается, что скорее всего вот здесь проблема, а здесь возможно долго кодить, а здесь наверное надо-ещё-подумать.
• Если обнаружены проблемы на предыдущем шаге, то начинается размышление чего-исправить-чтобы-заработало.
• Добавляется ещё много-много-примеров. Пока не появится уверенность, что все должно работать.
• Если ничего не получается, то идет переход к первому шагу с попыткой переписать все с нуля. Или берется таймаут до новых идей.

Переходы по шагам напоминают работу напильником. Вот грубое решение. Давайте его забрасаем примерами, а где надо, допилим.

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

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

Подход на системе правил

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

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

В синтезе с подходом на примерах получается приблизительно следующее:

• Исследование предметной области (ТЗ, железо, библиотеки, …) и установка правил (трафик не превышает 100 транзакций в секунду; таблица не должна содержать более 1М записей; введение индекса по такому-то полю позволит выполнить select со сложностью log N).
• Формулировка варианта решения с учетом всех правил. Если правила невыполнимы, то задача в таком ключе не решается и надо их пересмотреть.
• Формулировка дополнительных правил исходя из варианта решения.
• Прогон на тестовых примерах (не важно где, в уме или на стенде).

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

Особенность железной дороги в том, что разрабатываемый софт нижнего уровня работает на одном и том же железе. С минимумом привлечения сторонних библиотек. При конкретных и не меняющихся требованиях заказчика. Все намного более жестко детерминировано. В банковских системах эти моменты теряют смысл. Требования к проекту могут измениться через неделю после старта разработки при проведенном проектировании. Исследовать свойства предметной области чаще не удается, чем удается. Перед внедрением внезапно заказчику хочется прикрутить какую-нибудь рюшечку. В документации написано, что на запрос должен прийти ответ «Пиво», а на самом деле приходит «Жопа». В договоре темп 100 транзакций в секунду, но почему-то раз в сутки в зависимости от фазы Луны происходит всплеск в 200 шт в секунду. Когда показываешь логи с фактом, то оказывается, что лучше допилить приложение. И т.д. и т.п.. В таких условиях сформулированные когда-то правила летят кувырком. Аксиомы, на которых строилась теорема, перестают быть аксиомами. И лишенное фундамента здание начинает рушиться.

Полюса применения

Известность области

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

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

Изменение требований ТЗ

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

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

Использование библиотек

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

Ковариантность и контравиантность

Понятия достаточно широкие, и соответственно могут использоваться как в математике, так и в физике, так и в computer science, так и при математическом доказательстве правильности программ (см. вики и wiki).

Обозначение

Если A ковариантен B, то это будем записывать как A cov B.

Если A контравариантен B, то это будем записывать как A contrav B.

Если A инвариантен B, то это будем записывать как A inv B.

Общее определение

A cov B тогда true, когда все что есть в B есть в A. Или более точно: условие A всегда захватывает B.

A contrav B тогда true, когда все что есть в A есть в B. Или более точно: условие B всегда захватывает A.

A inv B тогда true, когда все что есть в А есть в В, а также все что есть в B есть в A; или A cov B и при этом B cov A.

Примеры

Множества

{x,y,z} cov {x, y} = true

{x,y,z} cov {x, y, z} = true

{x,z} cov {x, y} = false

{x} cov {x, y} = false

{x} cov {} = true

{x} cov {x, y} = false

Типы

Пусть имеется иерархия наследования:

Здесь:

{инструмент} cov {отвертка} = true

{инструмент} cov {крестовая отвертка} = true

{инструмент} cov {отвертка; молоток} = true

{отвертка} cov {молоток} = false

{отвертка} cov {инструмент} = false

{отвертка;молоток} cov {инструмент} = false

Условия

{x > 0} cov {x > 1} = true

{x > 0} cov {false} = true

{x > 0} cov {true} = false

{x > 0} cov {x > 0 and y > 0} = true

{x > 0} cov {x > 0 or y > 0} = false

{x > 0 and y > 0} cov {x > 0} = false

{x > 0 and y > 0} cov {x > 1} = false

Применение

LSP

См. LSP

Пусть имеется базовый тип A и его подтип B.

Для них необходимо, чтобы для любой функции

type1
func( type2 value );

выполнялось:

A::type1 cov B::type1

A::type2 contrav B::type2

Т.е. например можно так:

class A {
    float
    func( double x );
};
 
class B: public A {
    double
    func( float x );
};

Но нельзя так:

class A {
    float
    func( double x );
};
 
class B: public A {
    double
    func( float x );
};

Если для функции существует любое предусловие pred и любое постусловие post, то необходимо, чтобы выполнялось 

A::pred contrav B::pred

A::post cov B::post

Например:

1. Имеется предусловие перед созданием объекта A о необходимости открытого файла f. Тогда в предусловии создания объекта B этот файл может быть как открыт, так и нет.
2. Имеется постусловие после выхода из полиморфной функции объекта A - внутренняя функция Release() должна быть вызвана. Соответственно, в этой же функции в объекте B внутренняя функция Release() также должна быть вызвана.

Изменение условий вывода при доказательстве правильности

Если рассматривается программа в виде троек Хоара

{P} C {Q}

то при движении в прямом направлении можно усиливать условия. Т.е. должно выполнятся Q_old cov Q_new.

Соответственно при движении в обратном направлении должно выполняться  P_old contrav P_new.

Например имеем программу и предусловие:

{x > 0}
x = x + 1;

Для неё постусловие есть {x > 1}. Но чтобы сказать, что {x > 0} возможно будет достаточно доказательства что {x > 2}.

И для постусловия:

x = x + 1;
{x > 0}

Здесь предусловием будет {x > -1}. Но данное предусловие можно усилить. Т.е. если мы докажем, что {x > 0}, то это также будет доказывать, что {x > 0} после инкремента.

Рафинирование