Вероятностное Unit-тестирование. (Chaos driven Unit Testing.)

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

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

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

    Например, вы пишите код для работы на Intel и PPC, разрабатываете его на Intel, но учитываете порядок байтов. Потом прогоняете свои Unit-тесты, чтобы сравнить выходные данные с эталоном и обнаруживаете расхождения — понятно, где-то забыли байты перевернуть — исправляете — всё в порядке.

    Однако, любой пользователь всегда несёт в себе элемент случайности.

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

    Если программа делает больше чем печать «Hello World!», то скрытые ошибки в любом случае остаются.
    Это могут быть ошибки и в логике в том числе.

    Программа компилируется, все Warning'и устранены… но иногда что-то идёт не так… у пользователя (который живёт далеко в домике на островке в тихом океане — приехать к нему и пощупать нет возможности). Программист прокликал и протестировал со своей стороны всё что мог, но ошибки не нашёл. Что же делать?

    Любое приложение можно рассматривать как массив взаимосвязанных компонентов C объеденённых в логическую сеть.
    Каждый компонент принимает на вход аргументы I, а на выходе даёт результаты O.
    Мы составляем генераторы для получения случайных аргументов I, подаём их на вход компонентам C и проверяем выходы O, а также проверяем дополнительными тестами целостность состояния компонента C.

    Так мы тестируем каждый компонент случайным набором данных. Метод можно распространить и на полную сеть составленную из компонентов или на избранные подсети.

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

    Мы прогоняем тысячи итераций всё новые и новые случайные данные, выбираем и запрашиваем у компонентов случайные (допустимые) операции над этими данными.

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

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

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

    • Добавить слово
    • Установить существующему слову значение
    • Удалить слово
    • Проверить целостность


    Каркас тестирующего кода (фрагмент на Objective-C):

    srand(time(0));
    
    NSMutableString * log = [NSMutableString string];// for commands
    int prev = -1;
    unsigned i;
    #define ST_COUNT 2000
    
    id model = [SomeModelFactory createModelObject];
    
    for (i = 0; !status && i < ST_COUNT; i++)
    {
        int todo;
        do
        {
            todo = rand() % 4;
        }
         while (3 == todo && todo == prev);
        prev = todo;
    
        if (i + 1 == ST_COUNT)// last iter.
            todo = 3;// force int. check
    
        switch (todo)
         {
            case 0:// add new word to the model
            {
                …
            }
            case 1:// set existing word
            {
                …
            }
            case 2:// remove word
            {
                …
            }
            case 3:// pint. check
            {
                if (i + 1 == ST_COUNT || rand() % 2)
                {
                    …
                    status = 3;// set some error code if fail
                }
            }
        }
    }
    
    if (status)
    {
        [log writeToFile:@"/tmp/commands.log" atomically:YES encoding:NSUTF8StringEncoding error:NULL];
        exit(status);
    }
    


    Генератор аргументов:

    char genChar()
    {
        // allowed chars
        static char allowed[] = "ABCDEFGHIJKLMNOPQRSTUVWXUZabcdefghijklmnopqrstuvwxyz1234567890/";
        return allowed[rand() % (sizeof(allowed)-1)];
    }
    
    NSString* genWord(int min, int max)
    {
        NSMutableString * res = [NSMutableString string];
    
        if (max < min)
            max = min;
    
        int toGen = min + rand() % (max - min + 1); 
    
        int i;
        for (i = 0; i < toGen; i++)
             [res appendFormat:@"%c",genChar()];
    
        return res;
    }
    


    Все журналы с ошибками можете переложить из /tmp, например, в папочку issues, по папочкам case-1, case-2, …
    Чтобы по номеру case прогнать любую проверку в будущем.

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

    Для влияния на систему проверки, можно менять выход генераторов аргументов — форсируя больше пересечений… и тем самым сдвигая вероятность наступления тех или иных событий.
    Для примера выше, мы можем генерировать слова от 1 до 10 букв и статьи от 1 до 100 символов.
    Мы можем поменять условия и генерировать слова в 1-3 буквы а статьи от 1 до 10 символов, соответственно мы можем оказаться в вероятностном поле иных ошибок.
    Мы можем также влиять на вероятности выбора доступных операций и либо заставить словарь резко расти, либо резко худеть.
    Мы можем даже менять политику вероятностей выбора также случайным образом, подобно ветру, который меняет своё направление…

    Фактически, только благодаря методу вероятностного тестирования мы в своём проекте отловили 5 скрытых и весьма изощрённых ошибок в уже протестированном движке в котором не было видимых намёков на неисправности!

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

    Подробнее
    Реклама

    Комментарии 18

      +3
      Жалко, что на хабре нет некого механизма разделения топиков по уровню пользователя, для которого пишется та или иная статья. Можно было бы выставлять: для начинающих, для продвинутых и т.д.
        +1
        Концепт хороший. Но у вас пример довольно легкий, и больше похож на функциональное тестирование. Т.е. те подсистемы, которые лежат внутри словаря (хранилище данных, какие-то другие самостоятельные объекты) не экранированы. Точно хорошо подойдет для тех мест, где получаются какие-то данные извне.
        А что насчет сложности проверки самой целостности? Есть подозрения, что это может быть весьма и весьма нетривиальной задачей в более сложных случаях.
        Вообще любопытно, хоть chaos-mockup делай :)
          0
          Согалсен, по-моему менее затратно будет доверить такую работу опытному тестировщику.
          А подход интересный…
            0
            Все-таки движение от искусства, которое под силу только опытным тестировщикам, к технологии, которой можно обучить — правильное. Тогда завтра затраты будут меньше.
          +5
          При подобном стресс-тестировании, случайные данные обязательно нащупают определённые скрытые пограничные точки, и протестируют те ветки ваших условий, до которых ваши выдуманные тесты при обычных обстоятельствах не доходили.

          Ну это только в том случае, если «скрытые пограничные точки» не мельче острова Гренландия. Если пограничные множества маленькие, а размерность входных данных велика, то вероятность сгенерировать множество входны аргументов такое, что оно затронет эту пограничную ошибку, ничтожно мала.
            +1
            Идея интересная. Чем-то напоминает фаззинг (fuzz testing).
              +1
              Я работаю как раз в компании, которая пишет софт для тестирования чипов на этапе разработки (пока они в софте).
              В качестве методологии мы предлагаем клиентам MDV — Metric Driven Verification.
              Т.е. гоняются случайные тесты (вернее тесты не случайные, но со случайным инпутом) и по метрикам таким как Code coverage, Assert coverage, functional coverage и другим (метрик много) принимается решение о готовности продукта.
                +1
                Задача неправильно поставлена.

                > Мы составляем генераторы для получения случайных аргументов I, подаём их на вход компонентам C
                > и проверяем выходы O, а также проверяем дополнительными тестами целостность состояния компонента C.

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

                Сгенерировать I само по себе может быть достаточно сложно (один из предельных примеров — транслятор, для которого надо генерировать корректные входные программы), но ещё и сам компонент надо загнать во все возможные состояния. То есть, тест — это не просто цикл, а обход графа состояний компонента.

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

                Мы эту собаку не первый год грызем: citforum.ru/SE/testing/unitesk/
                www.unitesk.ru

                  0
                  спасибо, ссылка интересная, анализ приведён подробный
                    0
                    именно за проверку изменённого внутреннего состояния и отвечает проверка целостности:
                    "… а также проверяем дополнительными тестами целостность состояния компонента C..."
                      0
                      Проверить — это ползадачи. Вторая половина — подавать на вход компонента значения надо в разных состояниях компонента. То есть тестами являются цепочки вызовов. Нереально покрыть все классы состояний компонента цепочками случайных вызовов.

                      А что за дополнительные тесты, откуда они берутся? У вас это черезчур кратко.
                        0
                        Да, в примере разобранном выше состояние объекта было одно — он хранит определённый набор слов и важные операции для доступа дают совпадения с эталоном.

                        Дополнительные тесты пишутся для каждого компонента:
                        "… Разумеется на 1-м этапе придётся настроить подсистему контроля целостности, но потом всё пойдёт как по маслу..."

                        Для частного примера из статьи тест целостности был следующим:

                        if ([std count] != [sd wordsCount])
                        {   
                         NSLog(@"Words count mismatch %u vs %u",(unsigned)[std count],[sd wordsCount]);
                         status = 4;
                        }   
                        else
                        {   
                         for (NSString * w in [std allKeys])
                         {   
                          NSString * entry = [sd lookupWord:w];
                          NSString * stdEntry = [std objectForKey:w];
                          if (![entry isEqualToString:stdEntry])
                          {   
                           NSLog(@"Entry mismatch for word '%@', expected '%@'",w,stdEntry);
                           status = 5;
                           break;
                          }   
                          unsigned wi = [sd indexForWord:w];
                          if (wi == TIDNotFound)
                          {   
                           NSLog(@"Index-word error '%@'",w);
                           status = 6;
                           break;
                          }   
                          NSString * iw = [sd wordByIndex:wi];
                          if (!iw)
                          {   
                           NSLog(@"Word-index error for index %u",wi);
                           status = 7;
                           break;
                          }   
                          if (![iw isEqualToString:w])
                          {   
                           NSLog(@"Mismatch '%@' vs '%@' at index %u",w,iw,wi);
                           status = 8;
                           break;
                          }   
                         }   
                        }
                        


                        Пример конечно не сложный, для произвольного случая можно дать лишь общие рекомендации — как Вы и говорите — постараться пройтись по всем состояниям и произвести проверки. И постараться подобрать генераторы, которые прогонят систему по всем состояниям… Но это палка о двух концах — в погоне за всем и при излишней детерминированности входных параметров могут появиться случайные ограничения и мы попадём в иной класс ошибок. Вероятностная система очень чувствительна к входным параметрам. Оставляя место полному хаусу мы можем получить неожиданные результаты, а при попытке что-то фиксировать — мы теряем потеряем возможность что-то измерить — аналогия с принципом неопределённости Гейзенберга.
                    0
                    А на Хаскеле вот такая штука имеется:
                    en.wikipedia.org/wiki/QuickCheck
                      0
                      Chaos-driven? Тзинч уже потирает руки.
                        0
                        логика простая — если Хаос породил ошибки
                        то сам же Хаос и поможет их обнаружить.
                        клин клином.
                        0
                        Как говорится: пользователь — это периферийное устройство хаотичного ввода.

                        А вы фактически пытаетесь реализовать эмулятор этого самого устройства. Такое в принципе оправдано для достаточно узкого круга задач, т.к., как было сказано выше, на большой области допустимых значений достаточно тяжело выявить рандомом все возможные пограничные состояния. Сам иногда похожим методом пользуюсь, но в основном от лени. Компьютер, хаотично перебирая входные значения, зачастую находит ошибку дольше, чем человек, внимательно изучающий код. Хороший тест должен знать где копать.
                          0
                          Полностью согласен.
                          Вертоятностный метод лишь дополняет существующие тесты.

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

                          Точно установить причину не удалось, а вероятностный тест помог не только найти проблему, но и минимизировать путь к воспроизводству ошибки. И устранить 4 наведённые проблемы, после исправления 1-й логической ошибки. Таким образом удалось исправить одну корневую и 4 наведённых ошибки во вспомогательных методах, в результате устранения 1-й. И причём весьма чёткие траектории получились.
                          Например выпадает ошибка на 1000-м проходе, сохраняем, прогоняем стресс тест ещё раз — выпадает на 249-м, не успокаеваемся и снова — 128, ну где-то в среднем от 100 итераций получается в этом случае.
                          Начинаем упрощать — выкидывать операции пока ошибка воспроизводится по журналу операций.
                          Удавалось сократить журнал до 10-20 операций.
                          Дальше в ход шёл двоичный анализ дампов с подтверждением целостности после каждой операции согласно документированному двоичному формату.
                          Удавалось найти артефакт и точку программы, которая воспроизвела на его.
                          0
                          Ну это в тему, что лишние тесты никогда не бывают лишними.
                          (это утверждение тоже не бесспорно, т.к. порой роль играет и время прогона тестов и трудозатраты на их поддержку).

                          А можно ли для этого подхода определить критерии достаточности? Достаточное количество итераций, например.

                          Просто без подобных критериев, данный метод напоминает тыканье пальцем в небо «авось упадет».

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

                          А с данным подходом, когда и как Вы решаете, что код протестирован достаточно хорошо?

                          И правильно ли я понимаю, что Вы предлагаете использовать данный подход для тестирования системы в целом? Т.е. что то вроде интеграционных тестов черного ящика?

                          PS
                          В тексте есть опечатка — слово «длинны».

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

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