Здравствуйте, malphunction, Вы писали:
A>>Кроме того, для if (sin(x) > 3) трасс, очевидно, бесконечно много M>Ну, sin(x) <= 1, так что конкретно этот пример не годится
Переформулирую вопрос так: есть такая вещь, как покрытие трасс кода тестами. Код полностью покрыт,
если покрыты все трассы. Одинаковые классы входных данных дают один путь. Например, код
if (a > 10) x(); else y(); не нужно тестировать со всеми значениями переменной a, достаточно
двух тестов, где a > 10 и где a <= 10 (например, две трассы, в которых a = 15 и a = 2 -- подойдут).
Ясно, что в общем случае покрыть произвольную программу тестами невозможно, т.к. это эквивалентно
решению проблемы остановки.
Но как часто такие "невозможные для покрытия" программы встречаются на практике?
Ясно, что бывают запутанные программы, для покрытия которых требуется астрономическое число
вариантов. Но недавние успехи в автоматическом тестировании показывают, что и это
уже почти не проблема. Вот тут http://habrahabr.ru/post/128503/ описывается пример системы
KLEE, при помощью которой было достигнуто 94% покрытия кода Coreutils, при котором было
сгенерировано 3321 тестов и найдено 10 новых ошибок.
Итак, вопросы: Можете ли вы привести пример программы, не поддающейся покрытию тестами?
Можете ли привести примеры кода из реальных проектов?
P.S. Наверное, такая программа -- это вариации на тему самоприменимости или какой-то хитрой
рекурсии, я покак ещё не разобрался...
Как показывает история IT любой IEEE floating point более или менее нестабилен вплоть до аппаратных ошибок в процессорах (привет Intel!) и ошибках в компиляторах (привет Microsoft!).
Кроме того, для if (sin(x) > 3) трасс, очевидно, бесконечно много (на практике, чудовищно много). Проблема последнего случая даже не в том, что sin(10^15) и sin(10^15 + 1) могут совпадать, а в том считать ли это ошибкой.
Здравствуйте, Erop, Вы писали:
M>>Ясно, что в общем случае покрыть произвольную программу тестами невозможно, т.к. это эквивалентно M>>решению проблемы остановки.
E>Мне, например, это не очевидно...
Если программа программа полностью покрыта путями, значит, она останавливается.
Если есть останавливающийся алгоритм, выдающий либо покрытия, либо признак невозможности покрытия, то этот алгоритм может
использоваться для проверки остановки.
Путей здесь 2^len. Т.е. "покрытие тестами" здесь невозможно. При том, что убедится в правильности кода не сложно (возможно, написав несколько тестов -- один для тестирования
шага, второй -- на общую работоспособность).
Здравствуйте, malphunction, Вы писали:
M>Здравствуйте, Шахтер, Вы писали:
Ш>>Сортировка. N! возможных упорядочений входа. Тестировать можно до конца существования вселенной.
M>Ну, хотя сам алгоритм может быть сложным и работать долго, сама-то сортировка состоит из нескольких M>ветвей, их-то и надо протестировать. Так что покрыть тестами не сложно. Не забывайте, речь-то идёт M>не о покрытии на всех возможных данных; но только о покрытии классов данных.
Классов данных N!. Путей выполнения будет не меньше, иначе вы не различите всех перестановок входной последовательности.
Ш>>Многопоточные приложения. Комбинаторный взрыв состояний.
M>Комбинаторный взрыв бывает в тех прогах, которые плохо спроектированы и отлажены. M>Средства синхронизации -- мьютексы там всякие -- как раз и нужны, чтобы этот взрыв потушить.
Не потушить, а редуцировать. Кстати, мьютексы сами по себе не решают -- ими можно легко создать дедлок, если бездумно пользоваться.
Причем ещё и мадловероятный дедлок -- ищи его потом.
Верификация многопоточных программ невозможна тестами в принципе. Только логическими расуждениями, подкреплёнными тестами.
Но это верно и для многих других приложений. Возмите, например, lock-free style алгоритмы. Там возникают те же проблемы, что и в многопоточных приложениях.
Здравствуйте, adontz, Вы писали:
A>Здравствуйте, malphunction, Вы писали:
A>Как показывает история IT любой IEEE floating point более или менее нестабилен вплоть до аппаратных ошибок в процессорах (привет Intel!) и ошибках в компиляторах (привет Microsoft!).
Их поведение всё же детерминировано, хоть и не совпадает с документацией. Так что этот довод не принимается.
Кроме того, процессоры сейчас тоже проходят верификацию (особенно после случаев с Pentium FDIV), да и компилятор можно взять получше.
A>Кроме того, для if (sin(x) > 3) трасс, очевидно, бесконечно много (на практике, чудовищно много). Проблема последнего случая даже не в том, что sin(10^15) и sin(10^15 + 1) могут совпадать, а в том считать ли это ошибкой.
Ну, sin(x) <= 1, так что конкретно этот пример не годится, но мысль понятна: периодические функции могут порождать бесконечное число трасс.
Что ж, надо будет подумать над этим...
Здравствуйте, malphunction, Вы писали:
M>Итак, вопросы: Можете ли вы привести пример программы, не поддающейся покрытию тестами? M>Можете ли привести примеры кода из реальных проектов?
Сортировка. N! возможных упорядочений входа. Тестировать можно до конца существования вселенной.
это понятно, тем не менее, покрытие кода в обычном понимании у сортировки может быть достигнуто 100% -- там же только code path считается, а не полное состояние.
Здравствуйте, Шахтер, Вы писали:
Ш>Сортировка. N! возможных упорядочений входа. Тестировать можно до конца существования вселенной.
Ну, хотя сам алгоритм может быть сложным и работать долго, сама-то сортировка состоит из нескольких
ветвей, их-то и надо протестировать. Так что покрыть тестами не сложно. Не забывайте, речь-то идёт
не о покрытии на всех возможных данных; но только о покрытии классов данных.
Ш>Многопоточные приложения. Комбинаторный взрыв состояний.
Комбинаторный взрыв бывает в тех прогах, которые плохо спроектированы и отлажены.
Средства синхронизации -- мьютексы там всякие -- как раз и нужны, чтобы этот взрыв потушить.
Иначе код будет слабопредсказуемым, и программист в нём сам потеряется.
Я понимаю, что плохой код можно написать, он и пишется таким. Ну давайте тогда, для определенности,
не будем рассматривать многопоточные приложения.
Тогда вопрос -- а для однопоточных можно привести пример такой не-тестируемой программы?
Здравствуйте, adontz, Вы писали:
A>Кроме того, для if (sin(x) > 3) трасс, очевидно, бесконечно много (на практике, чудовищно много). Проблема последнего случая даже не в том, что sin(10^15) и sin(10^15 + 1) могут совпадать, а в том считать ли это ошибкой.
Пусть наш тестировщик будет поумнее, и знает что-то про синус и его периодичность. Вот он видит выражение if (sin(x) > 0.5) ..., тогда, учитывая свойства sin(x), он "догадывается"
разбить значения x на два класса, "где sin(x) больше 0.5" и "sin(x) меньше или равен 0.5", что соответствует двум покрытиям.
Соответственно, первый тест -- это какое-нибудь значение из первого интервала (напр., x = 1.6), а второй тест -- со значением x из второго интервала, напр., x = 0.001. После этого углубляться в ветки этого if'а с учётом разбиения x (внутри тоже могут быть вызовы каких-то функций, что снова приведет к разбиению интервала x).
Я, кажется, придумал более-менее сложный пример на основе вашего. Суть-то в чём? В том, что нужно обратить функцию внутри if (). Ну так возьмем какую-нить криптографическую!
Например, if (md5(x) > 123) ... . Тогда "реверсор", который внутри тестера, явно споткнётся об эту функцию. В случае md5 он не сможет разбить область значений x.
Правда, и этот пример не очень-то хорош. Крипто-функции всё-ж таки обратимы, хотя их вычисление может быть весьма трудоёмким. Но не невозможным же!
А судя по теореме о проблеме остановки это именно невозможно (а не сложно).
Здравствуйте, malphunction, Вы писали:
M>разбить значения x на два класса, "где sin(x) больше 0.5" и "sin(x) меньше или равен 0.5", что соответствует двум покрытиям.
равен 0.5 — это уже ошибка. Вообще, загнать в процессор ровное вещественное число, например 1/3 — теоретически невозможно. Отсюда невозможность точного сравнения.
Пути — это хорошо. Но если у тебя в входных значениях от -бесконечность до +бесконечность, то абсолютно доказать верность путем эксперимента невозможно.
Здравствуйте, GlebZ, Вы писали:
GZ>Здравствуйте, malphunction, Вы писали:
M>>разбить значения x на два класса, "где sin(x) больше 0.5" и "sin(x) меньше или равен 0.5", что соответствует двум покрытиям. GZ>равен 0.5 — это уже ошибка. Вообще, загнать в процессор ровное вещественное число, например 1/3 — теоретически невозможно. Отсюда невозможность точного сравнения.
GZ>Пути — это хорошо. Но если у тебя в входных значениях от -бесконечность до +бесконечность, то абсолютно доказать верность путем эксперимента невозможно.
Не совсем понятно, что такое "абсолютно доказать", да и зачем это нужно, если достаточно классов путей?
Во-вторых, "значения от -бесконечность до +бесконечность" просто не представимы в современных компах.
Здравствуйте, GlebZ, Вы писали:
M>>разбить значения x на два класса, "где sin(x) больше 0.5" и "sin(x) меньше или равен 0.5", что соответствует двум покрытиям. GZ>равен 0.5 — это уже ошибка. Вообще, загнать в процессор ровное вещественное число, например 1/3 — теоретически невозможно. Отсюда невозможность точного сравнения.
Для таких случаев разбиваем на открытые интервалы, делов-то.
Здравствуйте, GlebZ, Вы писали:
M>>разбить значения x на два класса, "где sin(x) больше 0.5" и "sin(x) меньше или равен 0.5", что соответствует двум покрытиям. GZ>равен 0.5 — это уже ошибка. Вообще, загнать в процессор ровное вещественное число, например 1/3 — теоретически невозможно. Отсюда невозможность точного сравнения.
Упс, я немного ошибся с интервалами в предыдущем ответе.
Когда компилятор видит выражение вида 1.0/3.0, то он разворачивает его в соответствующую константу (типа double, например).
При этом вполне можно сравнить другое значение с этой константой, какие проблемы?
Другое дело, программист, который написал "1.0/3.0", может не знать о поведении компилятора и способе обработки чисел с плавающей точкой, и удивляться,
почему это 10.0 / 30.0 не равно 1.0 / 3.0. Ну так это его, программиста, проблемы.
Здравствуйте, malphunction, Вы писали:
M>Ясно, что в общем случае покрыть произвольную программу тестами невозможно, т.к. это эквивалентно M>решению проблемы остановки.
Мне, например, это не очевидно...
Что касается проблемы остановки, то смотри. Берёшь любой генетический алгоритм оптимизации, функцию покудрявее и помногомернее и получаешь проблему остановки на практике, в полный рост. В такой версии она будет формулироваться так: "сколько особей в поколении требуется для сходимости?"...
Решай, тренируйся...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Да, я ещё углубился в этот вопрос -- действительно, циклы не покрываются путями
Пойду учить матчасть. Вроде бы структуры Крипке как-то позволяют всё-таки покрыть циклы,
как узнаю, продолжим дискуссию.
Ш>Вот, наверное, самый простой пример -- вручную реализованное сложение двоичных чисел.
Ш>
Ш>Путей здесь 2^len. Т.е. "покрытие тестами" здесь невозможно. При том, что убедится в правильности кода не сложно (возможно, написав несколько тестов -- один для тестирования Ш>шага, второй -- на общую работоспособность).
Здравствуйте, malphunction, Вы писали:
M>Если программа программа полностью покрыта путями, значит, она останавливается.
докажи...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, malphunction, Вы писали:
M>>Если программа программа полностью покрыта путями, значит, она останавливается.
E>докажи...
Здравствуйте, malphunction, Вы писали:
M>>>Если программа программа полностью покрыта путями, значит, она останавливается.
E>>докажи...
M>Лениво, сам доказывай...
Я приводил контрпример...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, malphunction, Вы писали:
M>>>>Если программа программа полностью покрыта путями, значит, она останавливается.
E>>>докажи...
M>>Лениво, сам доказывай...
E>Я приводил контрпример...
Контрпример? Программу, покрытую тестами, которые приводят к прохождению всех путей, но не останавливающуюся?
M>Контрпример? Программу, покрытую тестами, которые приводят к прохождению всех путей, но не останавливающуюся?
Возможно, я как-то не так понимаю термин "прохождение всех путей", но есть куча практически нужных даже примеров, а не то, что бы синтетических...
Я приводил в пример итерационные оптимизирующие алгоритмы, сходимость которых плохо исследована. Например генетические...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Возможно, я как-то не так понимаю термин "прохождение всех путей",
Ну так разберись, прежде чем спорить. Инфы по тестированию путей в гугле/википедии полно.
E>Я приводил в пример итерационные оптимизирующие алгоритмы, сходимость которых плохо исследована. Например генетические...
Для чего приводил?
Как пример непокрываемых программ? Я выше уже писал, что если программа содержит цикл, она непокрываема.
Или как контрпример для моего утверждения "покрываемые программы" останавливаются? Ну так как контрпример это не работает, потому что путь --
это последовательность операторов от начала программы до конца. Если программа полностью покрываема путями, то она не может "зависнуть",
т.к. все пути приводят к концу.
M>Как пример непокрываемых программ? Я выше уже писал, что если программа содержит цикл, она непокрываема.
ERGO: Коммерческих покрываемых программ не существует.
M>Или как контрпример для моего утверждения "покрываемые программы" останавливаются? Ну так как контрпример это не работает, потому что путь -- M>это последовательность операторов от начала программы до конца. Если программа полностью покрываема путями, то она не может "зависнуть", M>т.к. все пути приводят к концу.
Что значит "покрываема"? Что есть такой набор путей, что для любого оператора в программе можно указать хотя бы один путь из набора, в который, этот оператор входит, или, что можно перебрать все возможные пути?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
M>>Или как контрпример для моего утверждения "покрываемые программы" останавливаются? Ну так как контрпример это не работает, потому что путь -- M>>это последовательность операторов от начала программы до конца. Если программа полностью покрываема путями, то она не может "зависнуть", M>>т.к. все пути приводят к концу.
E>Что значит "покрываема"? Что есть такой набор путей, что для любого оператора в программе можно указать хотя бы один путь из набора, в который, этот оператор входит, или, что можно перебрать все возможные пути?
См. начало топика; ещё тут: https://ru.wikipedia.org/wiki/Покрытие_кода. Я писал про тестирование покрытием путей (т.е. перебор всех возможных путей), а не операторов.
Здравствуйте, malphunction, Вы писали:
M>Здравствуйте, Erop, Вы писали:
E>>Что значит "покрываема"? Что есть такой набор путей, что для любого оператора в программе можно указать хотя бы один путь из набора, в который, этот оператор входит, или, что можно перебрать все возможные пути?
M>См. начало топика; ещё тут: https://ru.wikipedia.org/wiki/Покрытие_кода. Я писал про тестирование покрытием путей (т.е. перебор всех возможных путей), а не операторов.
Походу вы пишете про покрытие путей (Path coverage — Has every possible route through a given part of the code been executed?) а подразумеваете "Full path coverage", по поводу которого в английской вики написано что "is usually impractical or impossible", который же связан с halting problem.
Т.е. вы с коллегой разговариваете о разных критериях покрытия.
Здравствуйте, malphunction, Вы писали:
M>См. начало топика; ещё тут: https://ru.wikipedia.org/wiki/Покрытие_кода. Я писал про тестирование покрытием путей (т.е. перебор всех возможных путей), а не операторов.
Можно пример коммерческой программы, где такое покрытие достигалось?..
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском