Гарантирует ли покрытие пути поиск всех ошибок?

64

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

Если нет, то почему? Как вы могли бы пройти через все возможные комбинации программных потоков и не найти проблему, если таковая существует?

Я стесняюсь предположить, что «все ошибки» могут быть найдены, но, может быть, это потому, что охват пути не практичен (так как он комбинаторный), поэтому он никогда не испытывался?

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


источник
33
Это эквивалентно проблеме остановки .
31
Что если код, который должен был быть там, не так ли?
RemcoGerlich
6
@ Снеговик: Нет, это не так. Невозможно решить проблему остановки для всех программ, но для многих конкретных программ это решаемо. Для этих программ все пути кода могут быть перечислены за конечное (хотя, возможно, длительное) время.
Йорген Фог
3
@ JørgenFogh Но при попытке найти ошибки в любой программе, априори неизвестно, останавливается ли программа или нет? Разве этот вопрос не относится к общему методу «нахождения всех ошибок в любой программе через покрытие пути»? В таком случае, разве это не похоже на «поиск остановки любой программы»?
Андрес Ф.
1
@AndresF. неизвестно, останавливается ли программа, если подмножество языка, на котором она написана, способно выразить программу без остановки. Если ваша программа написана на C без использования неограниченных циклов / рекурсии / setjmp и т. Д., Или на Coq, или на ESSL, то она должна быть остановлена ​​и все пути могут быть прослежены. (Тьюринг-полнота серьезно переоценена)
Леушенко

Ответы:

128

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

нет

Если нет, то почему? Как вы могли бы пройти через все возможные комбинации программных потоков и не найти проблему, если таковая существует?

Потому что даже если вы тестируете все возможные пути , вы все равно не проверили их со всеми возможными значениями или всеми возможными комбинациями значений . Например (псевдокод):

def Add(x as Int32, y as Int32) as Int32:
   return x + y

Test.Assert(Add(2, 2) == 4) //100% test coverage
Add(MAXINT, 5) //Throws an exception, despite 100% test coverage

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

- EW Dijkstra (выделение добавлено. Написано в 1988 году. Прошло уже более двух десятилетий.)

Мейсон Уилер
источник
7
@digitgopher: Полагаю, но если программа не имеет ввода, что она делает?
Мейсон Уилер
34
Существует также возможность пропустить интеграционные тесты, ошибки в тестах, ошибки в зависимостях, ошибки в системе сборки / развертывания или ошибки в исходной спецификации / требованиях. Вы никогда не сможете гарантировать, что найдете все ошибки.
Ixrec
11
@Ixrec: SQLite прилагает довольно смелые усилия! Но посмотрите, какое это огромное усилие! Это не подходит для больших кодовых баз.
Мейсон Уилер
13
Мало того, что вы не проверили все возможные значения или их комбинации, вы не проверили все относительные тайминги, некоторые из которых могли бы выставить условия гонки или даже сделать ваш тест зашедшим в тупик, из-за которого он не мог ничего сообщить . Это даже не будет неудачей!
Ивилнотексист Идонотексист
14
Мое воспоминание (подкрепленное такими записями ) состоит в том, что Дейкстра считал, что в хороших практиках программирования, прежде всего, доказательство правильности программы (при любых условиях) должно быть неотъемлемой частью разработки программы. Если смотреть с этой точки зрения, тестирование является как алхимия. Вместо гиперболы, я думаю, это было очень сильное мнение, выраженное очень сильным языком.
Дэвид К
71

В дополнение к ответу Мэйсона , есть еще одна проблема: покрытие не говорит вам, какой код был протестирован, оно говорит вам, какой код был выполнен .

Представьте, что у вас есть тестовый набор со 100% охватом пути. Теперь удалите все утверждения и снова запустите тестовый набор. Вуаля, тестовый пакет по-прежнему имеет 100% охват пути, но он абсолютно ничего не тестирует.

Йорг Миттаг
источник
2
Он может убедиться, что нет исключения при вызове тестируемого кода (с параметрами в тесте). Это немного больше, чем ничего.
Паŭло Эберманн
7
@ PaŭloEbermann Согласен, чуть больше, чем ничего. Тем не менее, это значительно меньше, чем «найти все ошибки»;)
Андрес Ф.
1
@ PaŭloEbermann: Исключением является путь к коду. Если код может выдать, но с определенными тестовыми данными не выдает, тест не достигает 100% покрытия пути. Это не относится к исключениям как к механизму обработки ошибок. Visual Basic - ON ERROR GOTOэто тоже путь, как и Си if(errno).
MSalters
1
@MSalters Я говорю о коде, который (по спецификации) не должен выдавать никаких исключений, независимо от ввода. Если он выбрасывает, это будет ошибка. Конечно, если у вас есть код, который указан для создания исключения, это следует проверить. (И, конечно, как сказал Йорг, просто проверки того, что код не генерирует исключение, обычно недостаточно для того, чтобы убедиться, что он работает правильно, даже для кода без смещения.) И некоторые исключения могут быть сгенерированы не -видимый путь кода, как для разыменования нулевого указателя или деления на ноль. Ваш инструмент покрытия пути поймает их?
Пауло Эберманн
2
Этот ответ прибивает это. Я бы пошел дальше и сказал, что благодаря этому покрытие пути никогда не гарантирует обнаружение даже одной ошибки. Однако существуют метрики, которые могут гарантировать, что, по крайней мере, будут обнаружены изменения - тестирование мутаций может фактически гарантировать, что (некоторые) модификации кода будут обнаружены.
EIS
34

Вот более простой пример для округления. Рассмотрим следующий алгоритм сортировки (на Java):

int[] sort(int[] x) { return new int[] { x[0] }; }

Теперь давайте проверим:

sort(new int[] { 0xCAFEBABE });

Теперь предположим, что (A) этот конкретный вызов sortвозвращает правильный результат, (B) все пути кода были покрыты этим тестом.

Но, очевидно, программа на самом деле не сортирует.

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

Atsby
источник
12

Рассмотрим absфункцию, которая возвращает абсолютное значение числа. Вот тест (Python, представьте себе тестовый фреймворк):

def test_abs_of_neg_number_returns_positive():
    assert abs(-3) == 3

Эта реализация верна, но она покрывает только 60% кода:

def abs(x):
    if x < 0:
        return -x
    else:
        return x

Эта реализация неверна, но она получает 100% покрытие кода:

def abs(x):
    return -x
RemcoGerlich
источник
2
Вот еще одна реализация, которая проходит тест (прошу прощения за не сломанный Python): def abs(x): if x == -3: return 3 else: return 0Вы могли бы исключить else: return 0часть и получить 100% покрытие, но функция была бы по существу бесполезной, даже если она проходит модульный тест.
CVn
7

Еще одно дополнение к ответу Мейсона , поведение программы может зависеть от среды выполнения.

Следующий код содержит Use-After-Free:

int main(void)
{
    int* a = malloc(sizeof(a));
    int* b = a;
    *a = 0;
    free(a);
    *b = 12; /* UAF */
    return 0;
}

Этот код является неопределенным поведением, в зависимости от конфигурации (выпуск | отладка), ОС и компилятора, он будет приводить к различным поведениям. Не только покрытие пути не гарантирует, что вы найдете UAF, но и ваш набор тестов, как правило, не охватывает различные возможные варианты поведения UAF, которые зависят от конфигурации.

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

int main(int a, int b)
{
    if (a != b) {
        if (cryptohash(a) == cryptohash(b)) {
            return ERROR;
        }
    }
    return 0;
} 

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

dureuill
источник
Легко для достаточно маленьких целых чисел :)
CodesInChaos
Не зная ничего cryptohash, трудно сказать, что такое «достаточно маленький». Может быть, это займет два дня, чтобы завершить на суперкалькулятор. Но да, intможет оказаться немного short.
Dureuill
С 32-битными целыми числами и типичными криптографическими хэшами (SHA2, SHA3 и т. Д.) Вычисления должны быть достаточно дешевыми. Пару секунд или около того.
CodesInChaos
7

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

Другой способ ответить на этот вопрос один из практики:

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

В связи с этим возникает вопрос:

В чем смысл инструментов покрытия кода?

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

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

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

С охватом кода может быть соблазнительно, особенно если у вас почти идеальный 98%, заполнить дела, чтобы найти оставшиеся пути.

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

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

Джон Ханна
источник
+1 Мне нравится этот ответ, потому что он конструктивный и упоминает некоторые преимущества покрытия.
Андрес Ф.
4

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

Пит Беккер
источник
1
Я думаю, что это зависит от определения ошибки. Я не думаю, что отсутствующие функции или функциональность должны рассматриваться как ошибки.
EIS
@eis - вы не видите проблемы с продуктом, в документации которого написано, что он делает X, а на самом деле это не так? Это довольно узкое определение «ошибка». Когда я руководил QA для линейки продуктов Borland C ++, мы не были такими щедрыми.
Пит Беккер
Я не понимаю, почему документация говорит, что это делает X, если это никогда не было реализовано
eis
@eis - если исходный дизайн требовал использования функции X, документация может закончиться описанием функции X. Если никто не реализовал ее, это ошибка, и покрытие пути (или любой другой вид тестирования черного ящика) не найдет ее.
Пит Беккер
К сожалению, охват пути - тестирование белого ящика , а не черного ящика . Тестирование белого ящика не может выявить отсутствующие функции.
Пит Беккер
4

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

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

Дерек W
источник
Согласились, что это является частью проблемы, но реальная проблема является более фундаментальной, чем эта. Даже с теоретическим компьютером с бесконечной памятью и отсутствием параллелизма, 100% тестовое покрытие не означает отсутствие ошибок. Тривиальные примеры этого изобилуют ответами здесь, но вот другое: если моя программа times_two(x) = x + 2, это будет полностью покрыто набором тестов assert(times_two(2) == 4), но это все еще очевидно глючный код! Нет необходимости в утечках памяти :)
Андрес Ф.
2
Это замечательный момент, и я признаю, что это более крупный / более фундаментальный гвоздь в гробу возможности приложений без ошибок, но, как вы говорите, он уже был добавлен здесь, и я хотел добавить что-то, что не было полностью охвачено существующие ответы. Я слышал о приложениях, которые зависали, потому что соединения с базой данных не были возвращены обратно в пул соединений, когда они больше не были нужны. Утечка памяти - это просто канонический пример неправильного управления ресурсами. Я хотел добавить, что правильное управление ресурсами в целом не может быть полностью проверено.
Дерек Вт
Хорошая точка зрения. Согласовано.
Андрес Ф.
3

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

Как уже было сказано, ответ НЕТ.

Если нет, то почему?

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

  • ошибки, обнаруженные в интеграционных тестах (модульные тесты не должны использовать реальные ресурсы)
  • ошибки в требованиях
  • ошибки в дизайне и архитектуре
BЈовић
источник
2

Что это значит для каждого пути, который будет проверен?

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

Рассмотрим этот метод:

def add(num1, num2)
  foo = "bar"  # useless statement
  $global += 1 # side effect
  num1 + num2  # actual work
end

Если вы напишите тест, который утверждает add(1, 2) == 3, инструмент покрытия кода скажет вам, что каждая строка выполняется. Но вы на самом деле ничего не утверждали о глобальном побочном эффекте или бесполезном назначении. Эти строки выполнены, но на самом деле не были проверены.

Тестирование мутаций поможет найти такие проблемы. Инструмент тестирования мутаций будет иметь список предопределенных способов «изменить» код и посмотреть, пройдут ли еще тесты. Например:

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

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

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

Натан Лонг
источник
0

Ну ... да, на самом деле, если каждый путь «через» программу проверен. Но это означает, что каждый возможный путь через все пространство всех возможных состояний, которые может иметь программа, включая все переменные. Даже для очень простой статически скомпилированной программы, скажем, старого средства вычисления чисел Фортрана, это невозможно, хотя, по крайней мере, это можно себе представить: если у вас есть только две целочисленные переменные, вы в основном имеете дело со всеми возможными способами соединения точек на двумерная сетка; это на самом деле очень похоже на коммивояжера. Для n таких переменных вы имеете дело с n- мерным пространством, поэтому для любой реальной программы задача совершенно невыполнима.

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


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

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

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

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

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

leftaroundabout
источник
Я не согласен с вашим первым предложением. Прохождение каждого состояния программы само по себе не обнаруживает никаких ошибок. Даже если вы проверяете наличие сбоев и явных ошибок, вы все равно не проверяли действительную функциональность, поэтому вы охватили лишь небольшую часть пространства ошибок.
Мэтью Прочитал
@MatthewRead: если вы примените это последовательно, то «пространство ошибок» будет правильным подпространством пространства всех состояний. Конечно, это гипотетически, потому что даже «правильные» состояния составляют слишком большое пространство, чтобы проводить какие-либо исчерпывающие тесты.
оставлено около