Многие команды используют так называемый fuzzing (генерация случайных наборов данных) для тестирования и некоторые — вполне успешно. Я же попробую рассказать о попытке применения fuzzing-техник для создания/оптимизации кода приложения. Сфера применения таких приложений, разумеется, ограничена — только задачи, где точное и полное решение отсутствует в принципе, а для любых решений есть некоторый критерий качества. Мы используем технику для оптимизации приложения для распознаванию рукописного ввода, но этим применение метода не заканчивается, а задуматься о нем можно, когда у себя в исходном коде вы видите нечто похожее:
|
Введение
Нет, я не предлагаю вовсе избавляться от констант/параметров методов, ибо даже в случае очень гибких и адаптивных систем ограничивающие параметры нужны, чтобы обеспечивать некоторую сходимость внутренних методов, и в целом, стабильность приложения. То есть, написать хороший распознаватель текста вообще без констант нельзя, а, значит нужно эти константы каким-то образом выбирать. И варианта у нас по сути два:
- Ручное определение (оно же «здравый смысл»)
- Автоматическая генерация (подстройка)
Первый способ хорош, но при условии достаточного количества времени, прекрасного представления о логике работы каждой части программы и наличии этого «здравого смысла»; человеку очень легко угадать нужный порядок константы, и там где должно быть 0.001, он не напишет 1000 (как правило). Но какая, в сущности, разница между 0.1 и 0.15? Особенно, если не знать, зачем эта константа нужна, а человек, который ввел ее, уже несколько лет как не работает с вами. И ручное определение никогда не даст «замечательных» результатов ни в общем случае, ни на какой-либо тестовой коллекции.
И мы должны понимать, что изменение некоторой части кода может существенным образом повлиять на все последующие методы, и их параметры в том числе.
Для обеспечения автоматической генерации нам потребуется организовать окружение разработки, позволяющее подгадывать параметры методов «на лету». В идеале, этим должен заниматься build-server в свободное от основной работы время.
Окружение разработки
Конечно, весьма желательно вынести все константы в отдельные файлы, тогда с ними будет удобнее работать. Но мы живем не в идеальном мире, и если это кто-то не сделал за вас, то работа вам достанется нелегкая. Особенно тем — что константы нужно как-то называть, а по контексту это сделать не всегда возможно. И некоторые константы являются действительно точными значениями, которые модификации не подлежат.
int grayscale = round(0.30 * R + 0.59 * G + 0.11 * B);
А другие же, напротив, только этого и ждут:
if (width/height > 0.25 && width/height < 1.25 && width > 10) ...
Если менять и те и другие, то с вероятностью, близкой к 1 мы получим нерабочую программу, соответственно необходимо их как-то разделять. Для этого можно использовать специальные маркеры, например:
#define FUZZ
int grayscale = round(0.30 * R + 0.59 * G + 0.11 * B);
...
FUZZ if (width/height > 0.25 && width/height < 1.25 && width > 10)
В общем вся работа сводится к проставлению маркеров, для тех объектов, значение которых следует менять. Чтобы найти константы в проекте помогут регулярные выражения, а вот чтобы понять какие «ждут» маркера — .
Далее, пишется простейшая программка (ConstFuzzer), для случайной модификации этих констант, которая находит помеченные маркером строчки и модифицирует значения в них на определенную случайную величину. Привет, Entropy! Возможно, если разрешат, чуть позже ее выложу.
Запускаем: ConstFuzzer src/*.cpp fuzzed_output_dir/ 0.1 и получаем «перепорченные исходники».
Пока мы не знаем, есть ли от новых исходников какой-то прок, или нет, и чтобы это выяснить — нужно их скомпилировать. Под gcc у вас, наверняка есть Makefile, а под Visual Studio, при наличии solution сделать это нетрудно:
%VS_CPP_COMPILER% %OUR_SLN% /Build Release /Out log-cpp.txt
Теперь, если приложение собралось, результат его работы следует проверить. Для этого, собранное приложение прогоняется по тестовому набору данных (в нашем случае картинки) и его выход сопоставляется с эталонным (распознанные тексты). Считается процент правильно распознанных и среднее время выполнения.
Кстати, не всегда полученное приложение будет работать правильно, оно может и зависнуть (зациклиться где-то из-за «неправильных» констант). Для того чтобы весь процесс Fuzzing'а на этом не рухнул — приложение вызывается через TimeLimit (утилита, ограничивающая время исполнения). Не прошло порог времени — считаем, что получило «0» в качестве результата.
Если грамотно расставлять маркеры, то такое случается редко, и константы при которых это происходит интересны для исправления потенциальных багов приложения.
Процесс «обучения»
Вышеописанный процесс по сути мало чем отличается от любой системы машинного обучения. И здесь можно смело применять большинство известных схем.
1. примитивный подход: max (случайные_изменения(начальные_значения) -> результат)
2. итеративный подход: while(iteration) {случайные_изменения(текущие_лучшие_значения) -> результат}
3. деление отрезка пополам: новые_значения = (max(случайные_изменения(начальные_значения) -> результат)) + начальные_значения) / 2
4. симплекс-метод.
Используемый метод определяет только скорость сходимости (то есть получения локальных лучших результатов), качество же результирующей программы — качеством тестовой коллекции.
Однако, чтобы получить глобальный максимум (то есть оптимально работающую программу) необходимо научиться делить входные данные на кластера, и использовать лучший набор констант (теперь уже переменных) для этого кластера. Если это интересно, то чуть позже расскажу, как это можно технически реализовать, без особых усложнений процесса разработки.
Подводные камни
Конечно, обучить «константы» в программе, так чтобы она давала наилучший результат на одной тестовой коллекции — дело не хитрое, но это вовсе не будет гарантировать оптимального поведения в целом. Для того чтобы ослабить влияние этого фактора мы берем более объемлющую коллекцию для вывода итоговых результатов работы. То есть «тренируются» константы на одной коллекции, а итоговый результат считается на другой.
Но тестовую коллекцию все равно нужно постоянно расширять, и ручной контроль результатов — более чем желателен (ну да, все-таки пока еще программа сама себя не напишет).
Однако, наличие пусть и субоптимальных результатов на определенной коллекции и представление их в удобной форме — некоторый шаг вперед относительно вечных «TODO».
Итоги:
+ меньше времени тратится на изменение констант, неявно зависящих от других частей кода;
+ возможно получение более близких к оптимальным результатов, практически «просто так», даже если вы не находитесь за рабочим местом;
+ возможность протестировать изменения (вы добавили новый код, но если с ним пока нет улучшений, то можно постоянно тестировать версии, как с ним, так и без него — FUZZ if (true), и может когда-нибудь он «поможет»);
— некоторое время придется потратить на автоматизацию процесса.
Автор: sic
