Оценка количества ошибок в программе. Модель Миллса

Сколько ошибок в программе? Это вопрос, который волнует каждого программиста. Особую актуальность придает ему принцип кучкования ошибок, согласно которому нахождение в некотором модуле ошибки увеличивает вероятность того, что в этом модуле есть и другие ошибки. Точного ответа на вопрос о количестве ошибок в программе очень часто дать невозможно, а вот построить некоторую оценку — можно. Для этого существуют несколько статических моделей. Рассмотрим одну из них: Модель Миллса.

В 1972 г. суперпрограммист фирмы IBM Харлан Миллс предложил следущий способ оценки количества ошибок в программе. Пусть у нас есть программа. Предположим, что в ней N ошибок. Назовем их естественными. Внесем в нее дополнительно M искусственных ошибок. Проведём тестирование программы. Пусть в ходе тестирования было обнаружено n естественных ошибок и m искусственных. Предположим, что вероятность обнаружения для естественных и искусственных ошибок одинакова. Тогда выполняется соотношение:



Мы нашли один и тот же процент естественных и искусственных ошибок. Отсюда количество ошибок в программе:



Количество необнаруженных ошибок равно (N-n).

Например, пусть в программу внесено 20 искусственных ошибок, в ходе тестирования было обнаружено 12 искусственных и 7 естественных ошибок. Получим следущую оценку количества ошибок в программе:



Количество необнаруженных ошибок равно (N-n) = 12 — 7 = 5.

Легко заметить, что в описанном выше способе Миллса есть один существенный недостаток. Если мы найдем 100% искусственных ошибок, это будут означать, что и естественных ошибок мы нашли 100%. Но чем меньше мы внесем искусственных ошибок, тем больше вероятность того, что мы найдём их все. Внесем единственную исскуственную ошибку, найдем ее, и на этом основании объявим, что нашли все естесственные ошибки! Для решение такой проблемы Миллс добавил вторую часть модели, предназначенную для проверки гипотезы о величине N:

Предположим, что в программе N естественных ошибок. Внесём в неё M искусственных ошибок. Будем тестировать программу до тех пор, пока не найдем все искусственные ошибки. Пусть к этому моменту найдено n естественных ошибок. На основании этих чисел вычислим величину C:



Величина C выражает меру доверия к модели. Это вероятность того, что модель будет правильно отклонять ложное предположение. Например, пусть мы считаем, что естественных ошибок в программе нет (N=0). Внесем в программу 4 искусственные ошибки. Будем тестировать программу, пока не обнаружим все искусственные ошибки. Пусть при это мы не обнаружим ни одной естественной ошибки. В этом случае мера доверия нашему предположению (об отсутствии ошибок в программе) будет равна 80% (4 / (4+0+1)). Для того чтобы довести ее до 90% количество искусственных ошибок придется поднять до 9. Следущие 5% уверенности в отсутствии естественных ошибок обойдутся нам в 10 дополнительных искусственных ошибок. M придется довести до 19.

Если мы предположим, что в программе не более 3-х естественных ошибок (N=3), внесем в нее 6 искусственных (M=6), найдем все искусственные и одну, две или три (но не больше!) естественных, то мера доверия к модели будет 60% (6 / (6+3+1)).

Значения функции С для различных значений N и M, в процентах:
Таблица 1 — с шагом 1;
Таблица 2 — с шагом 5;

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



Количество исскуственных ошибок, которые необходимо внести в программу, для достижения нужной меры доверия, для различных значений N:
Таблица 3 — с шагом 1;
Таблица 4 — с шагом 5;

Модель Миллса достаточно проста. Ее слабое место — предположение о равновероятности нахождения ошибок. Чтобы это предположение оправдалось, процедура внесения искусственных ошибок должна обладать определенной степенью «интеллекта». Ещё одно слабое место — это требование второй части миллсовой модели отыскать непременно все искусственные ошибки. А этого может не произойти долго, может быть, и никогда.
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 18
    +8
    Сколько программистов нужно, чтобы отладить программу? Один чтобы искать ошибки и второй — чтобы ему мешать.
      +4
      Предположим, что вероятность обнаружения для естественных и искусственных ошибок одинакова. Тогда выполняется соотношение ...


      Из первого, увы, не следует второе. См. тервер :).
      0
      Конечно не следует, но зачем усложнять модель. Да если расписывать «адекватность» модели, то это будет достаточно сложно и возможно статья вообще не появится :) А из первого только следует, что функция распределения одинаковы, то есть вероятность P_m,n (найти m ошибок из n) P_m,n=P_k,l при условии что m/n=k/l. Ну а сами числа зависят конечно от тестировщика, именно от него как раз и зависит адекватность этой модели.
        +2
        Даже если предельно упростить, то ключевую фразу «для значений M и N достаточно больших, чтобы...» вырезать, увы, не удасться. Для выборки в десять или даже сто особей статистика и тервер, увы, не работают :)
          0
          Почему усложнять-то? Просто надо аккуратней выражаться. «Из чего сделаем допущение, что для программ с достаточно большим количеством ошибок выполняется соотношение» смотрелось бы гораздо лучше, чем категоричное «Тогда выполняется соотношение».

          А то это просто дезинформация неосведомленного читателя, который вряд ли придет в восторг от теории, увидев, что она не работает. Откуда ему знать-то, что просто автор не потрудился указать рамки ее применимости?
          +3
          Метод сам по себе интересный, другое дело, что применить на практике его довольно сложно. Возмем сценарий: один программист расставляет в коде случайные ошибки, а второй их ищет. Возникают вопросы:

          1. Чем должен руководствоваться перый программист при создании ошибок. Он может расставить кое-где в методах throw new RuntimeException, или, например, поменять рандомно арифметические и логические операторы, или поудалять кое-какие условия. На мой взгляд, все эти внесенные ошибки будут весьма неглубокими и легко локализуемыми. Чего, к сожалению, нельзя сказать о настоящих ошибках. Может быть есть какой-то другой способ?

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

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

          Плюсы в этом, конечно, есть — можно оценить общий объем предстоящей работы, но и о временных затратах забывать нельзя.
            +2
            Как я себе вижу, данная модель скорее оценивает качество тестов, и, косвенно, качество кода. Т.е. у Вас есть набор тестов. Вы вносите в тестируемый код некоторое количество ошибок, после прогоняете тесты. Получаете некоторое количество ошибок. По количеству пойманных искусственных ошибок рассчитывается число пропущенных естественных.
            Я так понял применение данной модели.
              0
              Для оценки количества тестов существует другая модель. Даже не модель, а некоторая абстрактная формула. Однако, под неё нужен отдельный топик, так просто в комментарие её не напишешь, а в интернете эту информацию найти не могу.
                0
                У меня «качество тестов», у вас «количество тестов». Вы очепятались или говорите о другом?
                  0
                  Да, я неверно прочитал.
              0
              Он может расставить кое-где в методах throw new RuntimeException, или, например, поменять рандомно арифметические и логические операторы, или поудалять кое-какие условия.

              Учитывая, что эта методика 72 года, вполне возможно, она ориентированна именно на такие ошибки и опечатки. Ведь тогда не было навороченных IDE и утилит анализа кода, что бы находить их. А в проектах использовалось меньше различных компонент и библиотек, которые могут породить сложные ошибки взаимодействия.
              0
              Только вчера читал про эту модель. Доверия конечно не внушает да и реализовать сложновато, но более адекватного способа, к сожалению, мне найти не удалось:(
                0
                Существует модель «Парная» оценка. На мой взгляд, она намного адекватнее миллсовой модели. Также есть способ «Исторический опыт», но он слишком специфичен.
                +4
                Для 1972 года — вполне себе отличная работающая идея.

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

                расстановка таких рэндомов
                if(someCondition || random*1000 == 42)
                не в счёт)

                +Ошибки многопоточности — остаются совсем в стороне

                  +2
                  Очень смущает гипотеза о том что вероятность найти естественные и искусственные ошибки одинаковая. Методика их создания и процесс совершенно разные и потому вероятности тоже.
                    0
                    А существуют ли другие подобные модели для оценки количества ошибок?
                      0
                      Скажите, а зачем вообще нужно знать число N?
                      За всё моё время работы в тестировании мне ни разу не понадобилось это знать.

                      Более того, смотря в любой дефект-трэкер можно увидеть, что из числа найденных багов n, чинится только некоторое кол-во F. И на мой взгляд отношение F/n намного более интересно, чем абстрактная величина N или даже N-n.

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

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

                      Самое читаемое