Каковы некоторые стратегии тестирования больших конечных автоматов?

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

Грубая сила: Напишите что-нибудь, что декларативно сгенерирует все 4320 тестовых примеров с в основном неверными данными. Я бы порекомендовал поместить это в файл CSV, а затем использовать что-то вроде параметрического тестирования NUnits для загрузки всех тестовых примеров. Теперь большинство из этих тестовых примеров завершатся ошибкой, поэтому вам придется обновить декларативный файл вручную, чтобы он был правильным. и случайным образом возьмите лишь несколько тестовых примеров для исправления.

Техника машинного обучения: Вы можете использовать некоторые векторные машины или алгоритмы / эвристики MDA, чтобы попытаться изучить образец, взятый из того, что мы упомянули выше, и научить вашу программу машинного обучения вашему конечному автомату. Затем запустите алгоритм на всех 4320 входах и посмотрите, где они не согласны.

Я вижу проблему, но я определенно попробую разделить логику.

На мой взгляд, большая проблемная область:

• Он имеет 31 возможное состояние, в котором можно находиться.
• Он имеет следующие входные данные:
  • Enum: Current State (так 0 -> 30)
  • Enum: источник (в настоящее время только 2 записи)
  • Boolean: Request
  • Boolean: type
  • Enum: Status (3 состояния)
  • Enum: Handling (3 состояния) )
  • Boolean: Completed

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

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

Проверка устаревшего кода

Ознакомьтесь с Pex . Вы утверждаете, что унаследовали этот код, поэтому на самом деле это не разработка, основанная на тестировании.Вы просто хотите, чтобы модульные тесты охватывали каждый аспект. Это хорошо, так как любая дальнейшая работа будет подтверждена. Я лично еще не использовал Pex должным образом, однако я был поражен увиденным видео. По сути, он будет генерировать модульные тесты на основе входных данных, которыми в данном случае будет сам конечный автомат. Он сгенерирует тестовые примеры, о которых вы еще не задумывались. Конечно, это не TDD, но в этом сценарии тестирования устаревшего кода он должен быть идеальным.

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

Как вы думаете, сколько тестов необходимо, чтобы «полностью» проверить сумму функции (int a, int b)? В С # это будет что-то вроде 18446744056529682436 тестов ... Намного хуже, чем в вашем случае.

Я бы посоветовал следующее:

1. Проверить наиболее возможные ситуации, граничные условия.
2. Протестируйте некоторые важные части вашей SUT отдельно.
3. Добавьте тестовые примеры, когда ошибки обнаружены QA или в производственной среде.

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

Start
  .UploadDocument("name1")
  .SendDocumentOnReviewTo("user1")
  .Review()
  .RejectWithComment("Not enough details")
  .AssertIsCompleted()

Пример создания простых тестов для потоков находится здесь: http://slmoloch.blogspot.com/2009/12/design-of-selenium-tests-for-aspnet_09.html

Используйте SpecExplorer или NModel .

Я сконструировал конечный автомат для медицинского оборудования. Конечный автомат можно было настроить с помощью формата XML, который я определил.

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

. Вы должны использовать то, что я называю картой перехода магистрали. На Восточном побережье США большинство автомагистралей называют магистралями. Власти магистралей выпускают карту цен на платные дороги. Если бы в платном участке было 50 выходов, карта ценообразования имела бы таблицу 50 строк x 50 колец, в которой выходы были бы исчерпывающе перечислены как в строках, так и в столбцах. Чтобы узнать плату за въезд на выезд 20 и выезд из выезда 30, вы просто ищите пересечение строки 20 и столбца 30.

Для конечного автомата с 30 состояниями карта перехода магистрали была бы матрицей 30 x 30 перечисление всех 30 возможных состояний по строкам и столбцам. Давайте решим, что строки должны быть ТЕКУЩИМИ состояниями, а столбцы - СЛЕДУЮЩИМИ состояниями.

В каждой пересекающейся ячейке будет указана «цена» перехода из ТЕКУЩЕГО состояния (строка) в состояние СЛЕДУЮЩИЙ (столбец). Однако вместо одного значения $ ячейка будет ссылаться на строку в таблице Inputs, которую мы могли бы назвать идентификатором перехода.

В медицинском оборудовании FSM, который я разработал, были входы String, enums, int и т. Д. В таблице Inputs эти входные стимулы перечислены по столбцам.

Чтобы построить таблицу входных данных, вы должны написать простую процедуру для перечисления всех возможных комбинаций входных данных. Но стол был бы огромным. В вашем случае таблица будет иметь 4320 строк и, следовательно, 4320 идентификаторов перехода.Но это не утомительная таблица, потому что вы создали ее программно. В моем случае я написал простой JSP, чтобы перечислить входную таблицу переходов (и таблицу магистрали) в браузере или загрузить как csv для отображения в MS Excel.

Есть два направления построения этих двух таблиц.

1. направление проектирования, при котором вы создаете на магистрали все возможные переходы, скрывая недоступные переходы серым цветом. Затем создайте таблицу Inputs для всех ожидаемых входов только для каждого достижимого перехода с номером строки в качестве идентификатора перехода. Каждый идентификатор перехода записывается в соответствующую ячейку карты перехода магистрали. Однако, поскольку конечный автомат представляет собой разреженную матрицу, не все идентификаторы перехода будут использоваться в ячейках карты перехода магистрали. Кроме того, идентификатор перехода можно использовать много раз, потому что одни и те же условия перехода могут применяться к более чем одной паре изменений состояния.

2. направление теста обратное, где вы создаете таблицу Inputs. Вы должны написать общую процедуру для исчерпывающего теста перехода.
   Процедура сначала считывает таблицу последовательности переходов, чтобы перевести конечный автомат в состояние точки входа для запуска цикла тестирования. В каждом состоянии CURRENT он готов пройти через все 4320 идентификаторов перехода. В каждой строке ТЕКУЩИХ состояний на карте перехода Магистрали будет ограниченное количество столбцов, допустимых для СЛЕДУЮЩИХ состояний.

Вы бы хотели, чтобы подпрограмма циклически перебирала все 4320 строк входных данных, которые она считывала из таблицы Inputs, чтобы гарантировать, что неиспользуемые идентификаторы перехода не влияют на текущее состояние.Вы хотите проверить, что все действующие идентификаторы переходов являются действительными переходами.

Но вы не можете - потому что, как только будет введен эффективный переход, он изменит состояние машины на СЛЕДУЮЩИЙ и помешает вам завершить тестирование остальных идентификаторов перехода в этом предыдущем ТЕКУЩЕМ состоянии. Как только машина изменит состояние, вы должны снова начать тестирование с идентификатора перехода 0.

Пути перехода могут быть циклическими или необратимыми или иметь комбинацию циклических и необратимых участков вдоль пути.

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

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

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

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

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

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

Для java-листинга контроллера конечного автомата http://code.google.com/p/synthfuljava/source/browse/#svn/trunk/xml/org/synthful . Процедуры тестирования не включены.

Тест на основе требований. Если определенное состояние требуется для перехода в определенное другое состояние всякий раз, когда Завершено истинно, тогда напишите тест, который автоматически циклически перебирает все комбинации других входов (это должна быть просто пара циклов), чтобы доказать, что другие входы являются правильно игнорируется. У вас должно получиться по одному тесту для каждой переходной дуги, что, по моим оценкам, составит порядка 100 или 150 тестов, а не 4000.

Вы можете рассмотреть вариант Тестирование на основе моделей . Есть несколько инструментов, которые помогут с генерацией тестов в подобных ситуациях. Я обычно рекомендую MBT .

Грубая сила с тестами на покрытие, похоже, только начало.

Тестирование всех пар

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

причина тестирования всех пар такова: простейшие ошибки в программе обычно вызываются одним входным параметром . Следующая простейшая категория ошибок состоит из ошибок, зависящих от взаимодействий между парами параметров, которые могут быть обнаружены с помощью тестирования всех пар1 {{ 1}} Ошибки, связанные с взаимодействием между тремя или более параметрами, все реже встречаются2, в то время как в то же время становятся все более дорогостоящими для поиска исчерпывающим { {1}} тестирование, которое ограничено исчерпывающим тестированием всех возможных входных данных.

Также взгляните на предыдущий ответ здесь (бесстыдный плагин) для получения дополнительной информации и ссылок как на all-pair, так и на pict as tool.

Пример файла модели Pict

Данная модель генерирует 93 тестовых сценария, охватывающих все пары входных параметров.

#
# This is a PICT  model for testing a complex state machine at work 
#

CurrentState  :0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30
Source        :1,2
Request       :True, False
Type          :True, False
Status        :State1, State2, State3
Handling      :State1, State2, State3
Completed     :True,False

#
# One can add constraints to the model to exclude impossible 
# combinations if needed.
#
# For example:
# IF [Completed]="True" THEN CurrentState>15;
#

#
# This is the PICT output of "pict ComplexStateMachine.pict /s /r1"
#
# Combinations:    515
# Generated tests: 93