Здравствуйте, malphunction, Вы писали:

A>>Кроме того, для if (sin(x) > 3) трасс, очевидно, бесконечно много
M>Ну, sin(x) <= 1, так что конкретно этот пример не годится

А вдруг программу запустят в военное время?

Я уже поднимал эту тему здесь: http://rsdn.ru/forum/apptesting/4816033.1.aspx

Автор: malphunction
Дата: 12.07.12

, но там как-то
вяло отвечали и отфутболили сюда.

Переформулирую вопрос так: есть такая вещь, как покрытие трасс кода тестами. Код полностью покрыт,
если покрыты все трассы. Одинаковые классы входных данных дают один путь. Например, код
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. Наверное, такая программа -- это вариации на тему самоприменимости или какой-то хитрой
рекурсии, я покак ещё не разобрался...

Здравствуйте, malphunction, Вы писали:

Как показывает история IT любой IEEE floating point более или менее нестабилен вплоть до аппаратных ошибок в процессорах (привет Intel!) и ошибках в компиляторах (привет Microsoft!).
Кроме того, для if (sin(x) > 3) трасс, очевидно, бесконечно много (на практике, чудовищно много). Проблема последнего случая даже не в том, что sin(10^15) и sin(10^15 + 1) могут совпадать, а в том считать ли это ошибкой.

Здравствуйте, Erop, Вы писали:

M>>Ясно, что в общем случае покрыть произвольную программу тестами невозможно, т.к. это эквивалентно
M>>решению проблемы остановки.

E>Мне, например, это не очевидно...

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

Здравствуйте, malphunction, Вы писали:

Вот, наверное, самый простой пример -- вручную реализованное сложение двоичных чисел.

bit Add(bit *dst,const bit *src,size_t len,bit carry)
 {
  for(; len ;len--,src++,dst++)
    {
     unsigned s = (*dst)+(*src)+carry ;

     if( s>=2 ) 
       {
        *dst = bit(s-2) ;
        carry = 1 ;
       }
     else
       {
        *dst = bit(s) ;
        carry = 0 ;
       }
    } 

  return carry;
 }

Путей здесь 2^len. Т.е. "покрытие тестами" здесь невозможно. При том, что убедится в правильности кода не сложно (возможно, написав несколько тестов -- один для тестирования
шага, второй -- на общую работоспособность).

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, malphunction, Вы писали:

M>Здравствуйте, Шахтер, Вы писали:

Ш>>Сортировка. N! возможных упорядочений входа. Тестировать можно до конца существования вселенной.

M>Ну, хотя сам алгоритм может быть сложным и работать долго, сама-то сортировка состоит из нескольких
M>ветвей, их-то и надо протестировать. Так что покрыть тестами не сложно. Не забывайте, речь-то идёт
M>не о покрытии на всех возможных данных; но только о покрытии классов данных.

Классов данных N!. Путей выполнения будет не меньше, иначе вы не различите всех перестановок входной последовательности.

Ш>>Многопоточные приложения. Комбинаторный взрыв состояний.

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

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

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, 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! возможных упорядочений входа. Тестировать можно до конца существования вселенной.

Многопоточные приложения. Комбинаторный взрыв состояний.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Ш>Сортировка. 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>решению проблемы остановки.

Мне, например, это не очевидно...

Что касается проблемы остановки, то смотри. Берёшь любой генетический алгоритм оптимизации, функцию покудрявее и помногомернее и получаешь проблему остановки на практике, в полный рост. В такой версии она будет формулироваться так: "сколько особей в поколении требуется для сходимости?"...

Решай, тренируйся...

Здравствуйте, Шахтер, Вы писали:

Да, я ещё углубился в этот вопрос -- действительно, циклы не покрываются путями

Пойду учить матчасть. Вроде бы структуры Крипке как-то позволяют всё-таки покрыть циклы,
как узнаю, продолжим дискуссию.

Ш>Вот, наверное, самый простой пример -- вручную реализованное сложение двоичных чисел.

Ш>

Ш>bit Add(bit *dst,const bit *src,size_t len,bit carry)
Ш> {
Ш>  for(; len ;len--,src++,dst++)
Ш>    {
Ш>     unsigned s = (*dst)+(*src)+carry ;

Ш>     if( s>=2 ) 
Ш>       {
Ш>        *dst = bit(s-2) ;
Ш>        carry = 1 ;
Ш>       }
Ш>     else
Ш>       {
Ш>        *dst = bit(s) ;
Ш>        carry = 0 ;
Ш>       }
Ш>    } 

Ш>  return carry;
Ш> }
Ш>

Ш>Путей здесь 2^len. Т.е. "покрытие тестами" здесь невозможно. При том, что убедится в правильности кода не сложно (возможно, написав несколько тестов -- один для тестирования
Ш>шага, второй -- на общую работоспособность).

Здравствуйте, malphunction, Вы писали:

M>Если программа программа полностью покрыта путями, значит, она останавливается.

докажи...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, malphunction, Вы писали:

M>>Если программа программа полностью покрыта путями, значит, она останавливается.

E>докажи...

Лениво, сам доказывай...

Здравствуйте, malphunction, Вы писали:

M>>>Если программа программа полностью покрыта путями, значит, она останавливается.

E>>докажи...

M>Лениво, сам доказывай...

Я приводил контрпример...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, malphunction, Вы писали:

M>>>>Если программа программа полностью покрыта путями, значит, она останавливается.

E>>>докажи...

M>>Лениво, сам доказывай...

E>Я приводил контрпример...

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

Здравствуйте, malphunction, Вы писали:


M>Контрпример? Программу, покрытую тестами, которые приводят к прохождению всех путей, но не останавливающуюся?
Возможно, я как-то не так понимаю термин "прохождение всех путей", но есть куча практически нужных даже примеров, а не то, что бы синтетических...
Я приводил в пример итерационные оптимизирующие алгоритмы, сходимость которых плохо исследована. Например генетические...

Здравствуйте, Erop, Вы писали:

E>Возможно, я как-то не так понимаю термин "прохождение всех путей",

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

E>Я приводил в пример итерационные оптимизирующие алгоритмы, сходимость которых плохо исследована. Например генетические...

Для чего приводил?

Как пример непокрываемых программ? Я выше уже писал, что если программа содержит цикл, она непокрываема.

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

Здравствуйте, malphunction, Вы писали:


M>Как пример непокрываемых программ? Я выше уже писал, что если программа содержит цикл, она непокрываема.

ERGO: Коммерческих покрываемых программ не существует.

M>Или как контрпример для моего утверждения "покрываемые программы" останавливаются? Ну так как контрпример это не работает, потому что путь --
M>это последовательность операторов от начала программы до конца. Если программа полностью покрываема путями, то она не может "зависнуть",
M>т.к. все пути приводят к концу.

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

Здравствуйте, Erop, Вы писали:

M>>Или как контрпример для моего утверждения "покрываемые программы" останавливаются? Ну так как контрпример это не работает, потому что путь --
M>>это последовательность операторов от начала программы до конца. Если программа полностью покрываема путями, то она не может "зависнуть",
M>>т.к. все пути приводят к концу.

E>Что значит "покрываема"? Что есть такой набор путей, что для любого оператора в программе можно указать хотя бы один путь из набора, в который, этот оператор входит, или, что можно перебрать все возможные пути?

См. начало топика; ещё тут: https://ru.wikipedia.org/wiki/Покрытие_кода. Я писал про тестирование покрытием путей (т.е. перебор всех возможных путей), а не операторов.

M>Как пример непокрываемых программ? Я выше уже писал, что если программа содержит цикл, она непокрываема.

ну и кому нужно такое определение покрытия, хоть на практике, хоть в теории?

Покрытие кода измеряется тупо -- смотрим в каких инструкциях мы бывали, а в каких нет. А вовсе не смотрятся все возможные пути.

Здравствуйте, 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/Покрытие_кода. Я писал про тестирование покрытием путей (т.е. перебор всех возможных путей), а не операторов.

Можно пример коммерческой программы, где такое покрытие достигалось?..