Разработка программного обеспечения на основе поиска - Search-based software engineering

Разработка программного обеспечения на основе поиска (SBSE) применяется метаэвристический методы поиска, такие как генетические алгоритмы, имитация отжига и табу поиск к программная инженерия проблемы. Многие мероприятия в программная инженерия можно сформулировать как оптимизация проблемы. Оптимизация методы исследование операций Такие как линейное программирование или же динамическое программирование часто непрактичны для крупномасштабных программная инженерия проблемы из-за их вычислительная сложность или их предположения о структуре проблемы. Исследователи и практики используют метаэвристический методы поиска, которые налагают небольшие предположения на структуру проблемы, чтобы найти почти оптимальные или "достаточно хорошие" решения.

Проблемы SBSE можно разделить на два типа:

  • проблемы оптимизации черного ящика, например, распределение людей по задачам (типичный комбинаторная оптимизация проблема).
  • проблемы белого ящика, когда необходимо учитывать операции с исходным кодом.[1]

Определение

SBSE превращает проблему разработки программного обеспечения в задачу вычислительного поиска, которую можно решить с помощью метаэвристический. Это включает определение области поиска или набора возможных решений. Это пространство, как правило, слишком велико, чтобы его можно было исследовать исчерпывающе. метаэвристический подход. Метрика [2] (также называемая функцией пригодности, функцией стоимости, целевой функцией или мерой качества) затем используется для измерения качества потенциальных решений. Многие проблемы программной инженерии можно переформулировать как задачу вычислительного поиска.[3]

Период, термин "поисковое приложение ", напротив, означает использование технология поисковых систем вместо методов поиска в другом промышленном приложении.

Краткая история

Одна из самых ранних попыток подать заявку оптимизация к программная инженерия о проблеме сообщил Уэбб Миллер и Дэвид Спунер в 1976 году в районе тестирование программного обеспечения.[4] В 1992 г. С. Ксантакис и его коллеги применили поисковую технику к программная инженерия проблема впервые.[5] Термин SBSE впервые был использован в 2001 г. Харман и Джонс.[6] К 2013 году исследовательское сообщество выросло до более 800 авторов, охватывающих около 270 учреждений в 40 странах.[7]

Области применения

Разработка программного обеспечения на основе поиска применима практически ко всем этапам процесс разработки программного обеспечения. Тестирование программного обеспечения был одним из основных приложений.[8] Методы поиска были применены к другим программная инженерия деятельности, например, анализ требований,[9][10] дизайн,[11][12] рефакторинг,[13] разработка,[14] и поддержание.[15]

Разработка требований

Разработка требований это процесс определения и управления потребностями пользователей программного обеспечения и среды. Методы на основе поиска использовались для выбора и оптимизации требований с целью поиска наилучшего возможного подмножества требований, которое соответствует запросам пользователей в условиях ограничений, таких как ограниченные ресурсы и взаимозависимости между требованиями. Эта проблема часто решается как многокритериальное принятие решений проблема и, как правило, включает в себя предоставление лицу, принимающему решения, набора хороших компромиссов между стоимостью и удовлетворенностью пользователей, а также риском требований.[16][17][18][19]

Отладка и обслуживание

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

Генетическое программирование, биологически вдохновленный метод, который включает в себя развитие программ за счет использования кроссовера и мутации, был использован для поиска исправлений программ путем изменения нескольких строк исходного кода. В Ремонт GenProg Evolutionary Program программное обеспечение исправило 55 из 105 ошибок примерно по 8 долларов каждая за один тест.[20]

Коэволюция принимает "хищника и добычу" метафора в котором набор программ и набор модульные тесты вместе развиваться и влиять друг на друга.[21]

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

Программная инженерия на основе поиска применялась для тестирования программного обеспечения, включая автоматическое создание тестовых примеров (тестовых данных), минимизацию тестовых примеров и приоритизацию тестовых примеров.[22] Регрессионное тестирование также получил некоторое внимание.

Оптимизация программного обеспечения

Использование SBSE в оптимизация программы или изменение программного обеспечения, чтобы сделать его более эффективным с точки зрения скорости и использования ресурсов, были предметом успешных исследований.[23] В одном случае программа на 50 000 строк была генетически улучшена, что привело к ее ускорению в среднем в 70 раз.[24]Недавняя работа Basios et al. показывает, что при оптимизации структуры данных Google Guava обнаружил улучшение времени выполнения на 9%, потребление памяти на 13% и улучшение использования ЦП по отдельности на 4%.[25]

Управление проектом

Ряд решений, которые обычно принимаются менеджером проекта, могут выполняться автоматически, например, планирование проекта.[26]

инструменты

Инструменты, доступные для SBSE, включают OpenPAT.[27] и EvoSuite [28] и Покрытие, инструмент измерения покрытия кода для Python[29]

Методы и приемы

Доступен ряд методов и техник, в том числе:

Принятие в отрасли

SBSE как относительно новая область исследований еще не получила широкого признания в отрасли.

Успешные применения SBSE в отрасли в основном можно найти в тестировании программного обеспечения, где возможность автоматически генерировать случайные тестовые входные данные для обнаружения ошибок в большом масштабе привлекательна для компаний. В 2017 г. Facebook приобрела программный стартап Majicke Limited, который разработал Sapienz, поисковое приложение для поиска ошибок.[31]

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

Другая проблема заключается в том, что SBSE может лишить разработчика программного обеспечения. Сторонники утверждают, что мотивация SBSE состоит в том, чтобы улучшить отношения между инженером и программой.[34]

Смотрите также

Рекомендации

  1. ^ Харман, Марк (2010). «Почему анализ исходного кода и манипуляции с ним всегда будут важны». 10-я рабочая конференция IEEE по анализу и обработке исходного кода (SCAM 2010). 10-я рабочая конференция IEEE по анализу и обработке исходного кода (SCAM 2010). С. 7–19. Дои:10.1109 / SCAM.2010.28.
  2. ^ Харман, Марк; Джон А. Кларк (2004). «Метрики - тоже фитнес-функции». Материалы 10-го Международного симпозиума по метрикам программного обеспечения, 2004 г.. 10-й Международный симпозиум по метрикам программного обеспечения, 2004 г., стр. 58–69. Дои:10.1109 / METRIC.2004.1357891.
  3. ^ Кларк, Джон А .; Доладо, Хосе Хавьер; Харман, Марк; Hierons, Роберт М .; Джонс, Брайан Ф .; Лумкин, М .; Митчелл, Брайан С .; Манкоридис, Спирос; Rees, K .; Ропер, Марк; Шепперд, Мартин Дж. (2003). «Переформулирование программной инженерии как поисковой задачи». IEE Proceedings - Программное обеспечение. 150 (3): 161–175. CiteSeerX  10.1.1.144.3059. Дои:10.1049 / ip-sen: 20030559. ISSN  1462-5970.
  4. ^ Миллер, Уэбб; Спунер, Дэвид Л. (1976). «Автоматическое создание тестовых данных с плавающей запятой». IEEE Transactions по разработке программного обеспечения. SE-2 (3): 223–226. Дои:10.1109 / TSE.1976.233818. ISSN  0098-5589. S2CID  18875300.
  5. ^ С. Ксантакис, К. Эллис, К. Скурлас, А. Ле Галл, С. Кацикас и К. Карапулиос, «Применение генетических алгоритмов для тестирования программного обеспечения», в Труды 5-й Международной конференции по программной инженерии и ее приложениям, Тулуза, Франция, 1992, стр. 625–636.
  6. ^ Харман, Марк; Джонс, Брайан Ф. (15 декабря 2001 г.). «Поисковая инженерия». Информационные и программные технологии. 43 (14): 833–839. CiteSeerX  10.1.1.143.9716. Дои:10.1016 / S0950-5849 (01) 00189-6. ISSN  0950-5849.
  7. ^ Харман, Марк; Мансури, С. Афшин; Чжан, Юаньюань (1 ноября 2012 г.). «Разработка программного обеспечения на основе поиска: тенденции, методы и приложения». Опросы ACM Computing. 45 (1): 1–61. Дои:10.1145/2379776.2379787. S2CID  207198163.
  8. ^ Макминн, Фил (2004). «Генерация тестовых данных программного обеспечения на основе поиска: обзор». Тестирование, проверка и надежность программного обеспечения. 14 (2): 105–156. CiteSeerX  10.1.1.122.33. Дои:10.1002 / stvr.294. ISSN  1099-1689.
  9. ^ Грир, Дес; Руэ, Гюнтер (15 марта 2004 г.). «Планирование выпуска программного обеспечения: эволюционный и итеративный подход». Информационные и программные технологии. 46 (4): 243–253. CiteSeerX  10.1.1.195.321. Дои:10.1016 / j.infsof.2003.07.002. ISSN  0950-5849.
  10. ^ Коларес, Фелипе; Соуза, Джеффесон; Кармо, Рафаэль; Падуа, Клариндо; Матеус, Джеральдо Р. (2009). «Новый подход к планированию выпуска программного обеспечения». XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09. XXIII Бразильский симпозиум по разработке программного обеспечения, 2009 г. SBES '09. С. 207–215. Дои:10.1109 / SBES.2009.23.
  11. ^ Кларк, Джон А .; Джейкоб, Джереми Л. (15 декабря 2001 г.). «Протоколы - это тоже программы: метаэвристический поиск протоколов безопасности». Информационные и программные технологии. 43 (14): 891–904. CiteSeerX  10.1.1.102.6016. Дои:10.1016 / S0950-5849 (01) 00195-1. ISSN  0950-5849.
  12. ^ Ряйха, Оути (1 ноября 2010 г.). «Исследование по разработке программного обеспечения на основе поиска» (PDF). Обзор компьютерных наук. 4 (4): 203–249. Дои:10.1016 / j.cosrev.2010.06.001. ISSN  1574-0137.
  13. ^ Мариани, Тайна; Вергилио, Сильвия Регина (1 марта 2017 г.). «Систематический обзор рефакторинга на основе поиска». Информационные и программные технологии. 83: 14–34. Дои:10.1016 / j.infsof.2016.11.009. ISSN  0950-5849.
  14. ^ Альба, Энрике; Чикано, Дж. Франциско (1 июня 2007 г.). «Управление программными проектами с помощью GA». Информационные науки. 177 (11): 2380–2401. Дои:10.1016 / j.ins.2006.12.020. HDL:10630/8145. ISSN  0020-0255.
  15. ^ Антониол, Джулиано; Ди Пента, Массимилиано; Харман, Марк (2005). «Поисковые методы, применяемые для оптимизации планирования проекта массового технического обслуживания». Материалы 21-й Международной конференции IEEE по сопровождению программного обеспечения, 2005 г. ICSM'05. Материалы 21-й Международной конференции IEEE по сопровождению программного обеспечения, 2005. ICSM'05. С. 240–249. CiteSeerX  10.1.1.63.8069. Дои:10.1109 / ICSM.2005.79.
  16. ^ Чжан, Юаньюань (февраль 2010 г.). Выбор и оптимизация требований на основе многоцелевого поиска (Кандидат наук.). Стрэнд, Лондон, Великобритания: Лондонский университет.
  17. ^ Ю. Чжан, М. Харман и С. Л. Лим "Поисковая оптимизация управления взаимодействием требований, "Департамент компьютерных наук, Университетский колледж Лондона, Research Note RN / 11/12, 2011.
  18. ^ Ли, Лингбо; Харман, Марк; Летье, Эммануэль; Чжан, Юаньюань (2014). Проблема надежной следующей версии: устранение неопределенности во время оптимизации. Труды Ежегодной конференции по генетическим и эволюционным вычислениям 2014 г.. Gecco '14. С. 1247–1254. Дои:10.1145/2576768.2598334. ISBN  9781450326629. S2CID  8423690.
  19. ^ Li, L .; Harman, M .; Wu, F .; Чжан, Ю. (2017). «Значение точного анализа при выборе требований» (PDF). IEEE Transactions по разработке программного обеспечения. 43 (6): 580–596. Дои:10.1109 / TSE.2016.2615100. ISSN  0098-5589. S2CID  8398275.
  20. ^ Ле Гуэ, Клэр; Дьюи-Фогт, Майкл; Форрест, Стефани; Веймер, Уэстли (2012). «Систематическое исследование автоматического восстановления программ: исправление 55 из 105 ошибок по 8 долларов каждая». 2012 34-я Международная конференция по программной инженерии (ICSE). 2012 34-я Международная конференция по программной инженерии (ICSE). С. 3–13. Дои:10.1109 / ICSE.2012.6227211.
  21. ^ Аркури, Андреа; Яо, Синь (2008). «Новый коэволюционный подход к автоматическому исправлению ошибок программного обеспечения». Конгресс IEEE по эволюционным вычислениям, 2008 г. CEC 2008 г. (Всемирный конгресс IEEE по вычислительному интеллекту). Конгресс IEEE по эволюционным вычислениям, 2008 г. CEC 2008 г. (Всемирный конгресс IEEE по вычислительному интеллекту). С. 162–168. Дои:10.1109 / CEC.2008.4630793.
  22. ^ Харман, Марк; Цзя, Юэ; Чжан, Юаньюань (апрель 2015 г.). «Достижения, открытые проблемы и вызовы для тестирования программного обеспечения на основе поиска». 2015 IEEE 8-я Международная конференция по тестированию, верификации и валидации программного обеспечения (ICST). Грац, Австрия: IEEE: 1–12. CiteSeerX  10.1.1.686.7418. Дои:10.1109 / ICST.2015.7102580. ISBN  978-1-4799-7125-1. S2CID  15272060.
  23. ^ Мемети, Суэйб; Пллана, Сабри; Бинотто, Алецио; Колодзей, Иоанна; Брандич, Ивона (2018). «Использование метаэвристики и машинного обучения для оптимизации программного обеспечения параллельных вычислительных систем: систематический обзор литературы». Вычисление. 101 (8): 893–936. arXiv:1801.09444. Bibcode:2018arXiv180109444M. Дои:10.1007 / s00607-018-0614-9. S2CID  13868111.
  24. ^ Лэнгдон, Уильям Б.; Харман, Марк. «Оптимизация существующего программного обеспечения с помощью генетического программирования» (PDF). IEEE Transactions по эволюционным вычислениям.
  25. ^ Басиос, Михаил; Ли, Лингбо; Ву, Фань; Кантан, Лесли; Барр, Эрл Т. (9 сентября 2017 г.). Оптимизация дарвиновских структур данных в Google Guava (PDF). Разработка программного обеспечения на основе поиска. Конспект лекций по информатике. 10452. С. 161–167. Дои:10.1007/978-3-319-66299-2_14. ISBN  978-3-319-66298-5.
  26. ^ Минку, Леандро Л .; Судхольт, Дирк; Яо, Синь (2012). «Эволюционные алгоритмы для задачи планирования проекта: анализ времени выполнения и улучшенный дизайн». Материалы четырнадцатой международной конференции по генетическим и эволюционным вычислениям.. GECCO '12. Нью-Йорк, Нью-Йорк, США: ACM. С. 1221–1228. Дои:10.1145/2330163.2330332. ISBN  978-1-4503-1177-9.
  27. ^ Mayo, M .; Спейси, С. (2013). Прогнозирование сбоев регрессионных тестов с помощью выбранных генетическим алгоритмом показателей динамического анализа производительности (PDF). Материалы 5-го Международного симпозиума по разработке программного обеспечения на основе поиска (SSBSE). 8084. С. 158–171. Дои:10.1007/978-3-642-39742-4_13.CS1 maint: ref = harv (ссылка на сайт)
  28. ^ (http://www.evosuite.org/ )
  29. ^ другие, Нед Батчелдер и 100, охват: измерение покрытия кода для Python, получено 14 марта 2018
  30. ^ «Профилировщики с открытым исходным кодом на Java».
  31. ^ «Сапиенц: толчок Facebook к автоматизации тестирования программного обеспечения». VentureBeat. 30 декабря 2018 г.. Получено 29 сентября 2020.
  32. ^ Джонс, Дерек (18 октября 2013 г.). «Программирование с использованием генетических алгоритмов: разве это не то, чем люди уже занимаются ;-)». Форма кода. Получено 31 октября 2013.
  33. ^ Ле Гуэ, Клэр; Форрест, Стефани; Веймер, Уэстли (1 сентября 2013 г.). «Актуальные проблемы автоматического восстановления программного обеспечения». Журнал качества программного обеспечения. 21 (3): 421–443. CiteSeerX  10.1.1.371.5784. Дои:10.1007 / s11219-013-9208-0. ISSN  1573-1367. S2CID  16435531.
  34. ^ Саймонс, Кристофер Л. (май 2013 г.). Куда (подальше) программисты в SBSE?. Первый международный семинар по объединению моделирования с разработкой программного обеспечения на основе поиска, Первый международный семинар по объединению моделирования с разработкой программного обеспечения на основе поиска. Сан-Франциско, США: IEEE Press. стр. 49–50. Получено 31 октября 2013.

внешняя ссылка