검색 기반 소프트웨어 엔지니어링

Search-based software engineering

검색 기반 소프트웨어 엔지니어링(SBSE)은 소프트웨어 엔지니어링 문제에 유전자 알고리즘, 시뮬레이션 어닐링, 타부 검색과 같은 메타휴리스틱 검색 기술을 적용한다. 소프트웨어 공학에서의 많은 활동은 최적화 문제로 언급될 수 있다. 선형 프로그래밍이나 동적 프로그래밍과 같은 운영 연구의 최적화 기법은 계산상의 복잡성이나 문제 구조에 대한 가정 때문에 대규모 소프트웨어 엔지니어링 문제에 대해서는 종종 비실용적이다. 연구자들과 실무자들은 문제 구조에 거의 가정을 하지 않는 메타휴리스틱 검색 기술을 사용하여 거의 최적이나 "완벽한" 해결책을 찾는다.

SBSE 문제는 두 가지 유형으로 나눌 수 있다.

  • 예를 들어, 블랙박스 최적화 문제(예: 사람을 작업에 할당하는 것)(일반적인 조합 최적화 문제.
  • 소스 코드의 작동을 고려해야 하는 화이트 박스 문제.[1]

정의

SBSE는 소프트웨어 엔지니어링 문제를 메타휴리스틱으로 해결할 수 있는 컴퓨터 검색 문제로 변환한다. 여기에는 검색 공간 또는 가능한 해결책의 집합 정의가 포함된다. 이 공간은 일반적으로 너무 커서 완전히 탐구할 수 없으며 메타휴리스틱 접근법을 제안한다. 그런 다음 잠재적인 솔루션의 품질을 측정하기 위해 메트릭(체력 함수, 비용 함수, 객관적 함수 또는 품질 측정이라고도 함)을 사용한다. 많은 소프트웨어 공학 문제들은 컴퓨터 검색 문제로 재조정될 수 있다.[3]

이와는 대조적으로 "검색 기반 응용"이라는 용어는 검색 기법이 아닌 검색 엔진 기술을 다른 산업 응용 분야에 사용하는 것을 말한다.

간략한 역사

소프트웨어 엔지니어링 문제에 최적화를 적용하려는 가장 초기 시도 중 하나는 1976년 소프트웨어 테스트 분야에서 Webb Miller와 David Super에 의해 보고되었다.[4] 1992년 S. 크산타키스와 그의 동료들은 처음으로 소프트웨어 공학 문제에 검색 기술을 적용했다.[5] SBSE라는 용어는 2001년 하만과 존스에 의해 처음 사용되었다.[6] 연구계는 2013년까지 40개국의 약 270개 기관에 걸쳐 800명 이상의 저자를 포함하도록 성장했다.[7]

응용 영역

검색 기반 소프트웨어 엔지니어링은 소프트웨어 개발 프로세스의 거의 모든 단계에 적용할 수 있다. 소프트웨어 테스트는 주요 애플리케이션 중 하나이다.[8] 검색 기법은 요건 분석,[9][10] 설계,[11][12] 리팩터링,[13] 개발 [14]및 유지보수와 같은 기타 소프트웨어 엔지니어링 활동에 적용되었다.[15]

요구사항공학

요구사항 엔지니어링은 소프트웨어 사용자 및 환경의 요구를 결정하고 관리하는 프로세스다. 검색 기반 방법은 제한된 자원 및 요건 간의 상호의존성과 같은 제약조건 속에서 사용자 요청에 부합하는 최선의 가능한 요구사항의 하위 집합을 찾는 것을 목표로 요구사항 선택 및 최적화에 사용되어 왔다. 이 문제는 종종 다중 기준 의사결정 문제로 다루어지고 일반적으로 요구사항 위험뿐만 아니라 비용 및 사용자 만족도 사이에서 일련의 훌륭한 타협안을 의사결정자에게 제시하는 것을 포함한다.[16][17] [18][19]

디버깅 및 유지 관리

소프트웨어 버그(또는 코드 냄새)를 식별한 다음 소프트웨어를 디버깅(또는 리팩터링)하는 것은 프로세스가 도구 지원을 받기는 하지만 대체로 수동적이고 노동 집약적인 노력이다. SBSE의 한 가지 목표는 (예를 들어 돌연변이 테스트를 통해) 버그를 자동으로 식별하고 수정하는 것이다.

크로스오버와 돌연변이를 통해 프로그램을 진화시키는 생물학적으로 영감을 받은 기법인 유전자 프로그래밍은 소스코드 몇 줄을 변경해 프로그램 수리를 검색하는 데 이용됐다. GenProg Evolution Program Repair 소프트웨어는 105개 버그 중 55개를 한 번의 테스트에서 각각 약 8달러에 수리했다.[20]

공진화는 프로그램 집합과 단위 테스트 집합이 함께 진화하여 서로 영향을 미치는 "프레데이터와 먹잇감" 은유를 채택한다.[21]

테스트

소프트웨어 테스트에는 테스트 케이스(테스트 데이터)의 자동 생성, 테스트 케이스 최소화, 테스트 케이스 우선순위 지정 등 검색 기반 소프트웨어 엔지니어링이 적용됐다.[22] 회귀 테스트도 어느 정도 주목을 받았다.

소프트웨어 최적화

SBSE를 프로그램 최적화에 사용하거나, 속도나 자원 사용 측면에서 보다 효율적으로 만들기 위해 소프트웨어를 수정하는 것은 성공적인 연구의 대상이 되어 왔다.[23] 한 예로, 5만개의 라인 프로그램이 유전적으로 개선되어 평균적으로 프로그램이 70배 빨라졌다.[24] Basios 등의 최근 연구는 구글 과바가 데이터 구조를 최적화함으로써 실행 시간이 9%, 메모리 소비량이 13%, CPU 사용량이 4% 각각 개선되었음을 발견했다.[25]

프로젝트 관리

프로젝트 관리자가 일반적으로 내리는 여러 가지 결정(예: 프로젝트 스케줄링)은 자동으로 이루어질 수 있다.[26]

도구들

SBSE에 사용할 수 있는 도구로는 Python의[29] 코드 범위 측정 도구인 OpenPAT, EvoSuite[28] 및 Coverage 등이 있다.[27]

방법 및 기술

다음과 같은 다양한 방법과 기법을 사용할 수 있다.

산업합격

비교적 새로운 연구 분야로서 SBSE는 아직 폭넓은 산업 수용을 경험하지 못하고 있다.

업계에서 SBSE의 성공적인 애플리케이션은 대부분 소프트웨어 테스트에서 찾을 수 있는데, 대규모의 버그 발견을 위해 무작위 테스트 입력을 자동으로 생성할 수 있는 기능이 기업에게 매력적이다. 페이스북은 2017년 검색 기반 버그 찾기 앱인 사피엔즈를 개발한 소프트웨어 스타트업 '마지키 리미티드'[31]를 인수했다.

다른 애플리케이션 시나리오에서 소프트웨어 엔지니어는 제어 능력이 거의 없거나 인간이 생산하는 것과 다른 솔루션을 생성하는 도구를 채택하는 것을 꺼릴 수 있다.[32] SBSE가 프로그램을 수정 또는 개선하는 데 사용하는 맥락에서, 개발자들은 자동 생성된 수정이 시스템의 요구사항과 시험 환경의 범위 밖에서 예기치 않은 동작을 일으키지 않는다고 확신할 필요가 있다. 완전히 자동화된 프로그래밍이 아직 달성되지 않았다는 점을 고려하면, 이러한 변경의 바람직한 특성은 정비 활동을 지원하기 위해 인간이 쉽게 이해할 필요가 있다는 것이다.[33]

또 다른 우려는 SBSE가 소프트웨어 엔지니어를 중복으로 만들 수 있다는 것이다. 지지자들은 SBSE의 동기가 엔지니어와 프로그램 간의 관계를 강화하기 위한 것이라고 주장한다.[34]

참고 항목

참조

  1. ^ Harman, Mark (2010). "Why Source Code Analysis and Manipulation Will Always be Important". 10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010). 10th IEEE Working Conference on Source Code Analysis and Manipulation (SCAM 2010). pp. 7–19. doi:10.1109/SCAM.2010.28.
  2. ^ Harman, Mark; John A. Clark (2004). "Metrics are fitness functions too". Proceedings of the 10th International Symposium on Software Metrics, 2004. 10th International Symposium on Software Metrics, 2004. pp. 58–69. doi:10.1109/METRIC.2004.1357891.
  3. ^ Clark, John A.; Dolado, José Javier; Harman, Mark; Hierons, Robert M.; Jones, Bryan F.; Lumkin, M.; Mitchell, Brian S.; Mancoridis, Spiros; Rees, K.; Roper, Marc; Shepperd, Martin J. (2003). "Reformulating software engineering as a search problem". IEE Proceedings - Software. 150 (3): 161–175. CiteSeerX 10.1.1.144.3059. doi:10.1049/ip-sen:20030559. ISSN 1462-5970.
  4. ^ Miller, Webb; Spooner, David L. (1976). "Automatic Generation of Floating-Point Test Data". IEEE Transactions on Software Engineering. SE-2 (3): 223–226. doi:10.1109/TSE.1976.233818. ISSN 0098-5589. S2CID 18875300.
  5. ^ S. 크산타키스, C. 엘리스, C. 스쿠를라스, A. 1992년 프랑스 툴루즈에서 열린 제5차 소프트웨어 엔지니어링 및 그 응용에 관한 국제 회의의 절차에서 Le Gall, S. Katsikas 및 K. Karapoulios, "소프트웨어 테스트에 유전자 알고리즘의 적용"
  6. ^ Harman, Mark; Jones, Bryan F. (15 December 2001). "Search-based software engineering". Information and Software Technology. 43 (14): 833–839. CiteSeerX 10.1.1.143.9716. doi:10.1016/S0950-5849(01)00189-6. ISSN 0950-5849.
  7. ^ Harman, Mark; Mansouri, S. Afshin; Zhang, Yuanyuan (1 November 2012). "Search-based software engineering: Trends, techniques and applications". ACM Computing Surveys. 45 (1): 1–61. doi:10.1145/2379776.2379787. S2CID 207198163.
  8. ^ McMinn, Phil (2004). "Search-based software test data generation: a survey". Software Testing, Verification and Reliability. 14 (2): 105–156. CiteSeerX 10.1.1.122.33. doi:10.1002/stvr.294. ISSN 1099-1689.
  9. ^ Greer, Des; Ruhe, Guenther (15 March 2004). "Software release planning: an evolutionary and iterative approach". Information and Software Technology. 46 (4): 243–253. CiteSeerX 10.1.1.195.321. doi:10.1016/j.infsof.2003.07.002. ISSN 0950-5849.
  10. ^ Colares, Felipe; Souza, Jerffeson; Carmo, Raphael; Pádua, Clarindo; Mateus, Geraldo R. (2009). "A New Approach to the Software Release Planning". XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09. XXIII Brazilian Symposium on Software Engineering, 2009. SBES '09. pp. 207–215. doi:10.1109/SBES.2009.23.
  11. ^ Clark, John A.; Jacob, Jeremy L. (15 December 2001). "Protocols are programs too: the meta-heuristic search for security protocols". Information and Software Technology. 43 (14): 891–904. CiteSeerX 10.1.1.102.6016. doi:10.1016/S0950-5849(01)00195-1. ISSN 0950-5849.
  12. ^ Räihä, Outi (1 November 2010). "A survey on search-based software design" (PDF). Computer Science Review. 4 (4): 203–249. CiteSeerX 10.1.1.188.9036. doi:10.1016/j.cosrev.2010.06.001. ISSN 1574-0137.
  13. ^ Mariani, Thainá; Vergilio, Silvia Regina (1 March 2017). "A systematic review on search-based refactoring". Information and Software Technology. 83: 14–34. doi:10.1016/j.infsof.2016.11.009. ISSN 0950-5849.
  14. ^ Alba, Enrique; Chicano, J. Francisco (1 June 2007). "Software project management with GAs". Information Sciences. 177 (11): 2380–2401. doi:10.1016/j.ins.2006.12.020. hdl:10630/8145. ISSN 0020-0255.
  15. ^ Antoniol, Giuliano; Di Penta, Massimiliano; Harman, Mark (2005). "Search-based techniques applied to optimization of project planning for a massive maintenance project". Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05. Proceedings of the 21st IEEE International Conference on Software Maintenance, 2005. ICSM'05. pp. 240–249. CiteSeerX 10.1.1.63.8069. doi:10.1109/ICSM.2005.79.
  16. ^ Zhang, Yuanyuan (February 2010). Multi-Objective Search-based Requirements Selection and Optimisation (PhD). Strand, London, UK: University of London.
  17. ^ Y. 장과 M. Harman과 S. L. L. Lim, "Search Based Optimization of Requirements Interaction Management," University College London, Research Note RN/11/12, 2011년.
  18. ^ Li, Lingbo; Harman, Mark; Letier, Emmanuel; Zhang, Yuanyuan (2014). Robust Next Release Problem: Handling Uncertainty During Optimization. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. Gecco '14. pp. 1247–1254. doi:10.1145/2576768.2598334. ISBN 9781450326629. S2CID 8423690.
  19. ^ Li, L.; Harman, M.; Wu, F.; Zhang, Y. (2017). "The Value of Exact Analysis in Requirements Selection" (PDF). IEEE Transactions on Software Engineering. 43 (6): 580–596. doi:10.1109/TSE.2016.2615100. ISSN 0098-5589. S2CID 8398275.
  20. ^ Le Goues, Claire; Dewey-Vogt, Michael; Forrest, Stephanie; Weimer, Westley (2012). "A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each". 2012 34th International Conference on Software Engineering (ICSE). 2012 34th International Conference on Software Engineering (ICSE). pp. 3–13. doi:10.1109/ICSE.2012.6227211.
  21. ^ Arcuri, Andrea; Yao, Xin (2008). "A novel co-evolutionary approach to automatic software bug fixing". IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). pp. 162–168. doi:10.1109/CEC.2008.4630793.
  22. ^ Harman, Mark; Jia, Yue; Zhang, Yuanyuan (April 2015). "Achievements, Open Problems and Challenges for Search Based Software Testing". 2015 IEEE 8th International Conference on Software Testing, Verification and Validation (ICST). Graz, Austria: IEEE: 1–12. CiteSeerX 10.1.1.686.7418. doi:10.1109/ICST.2015.7102580. ISBN 978-1-4799-7125-1. S2CID 15272060.
  23. ^ Memeti, Suejb; Pllana, Sabri; Binotto, Alecio; Kolodziej, Joanna; Brandic, Ivona (2018). "Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review". Computing. 101 (8): 893–936. arXiv:1801.09444. Bibcode:2018arXiv180109444M. doi:10.1007/s00607-018-0614-9. S2CID 13868111.
  24. ^ Langdon, William B.; Harman, Mark. "Optimising Existing Software with Genetic Programming" (PDF). IEEE Transactions on Evolutionary Computation.
  25. ^ Basios, Michail; Li, Lingbo; Wu, Fan; Kanthan, Leslie; Barr, Earl T. (9 September 2017). Optimising Darwinian Data Structures on Google Guava (PDF). Search Based Software Engineering. Lecture Notes in Computer Science. Vol. 10452. pp. 161–167. doi:10.1007/978-3-319-66299-2_14. ISBN 978-3-319-66298-5.
  26. ^ Minku, Leandro L.; Sudholt, Dirk; Yao, Xin (2012). "Evolutionary algorithms for the project scheduling problem: runtime analysis and improved design". Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference. GECCO '12. New York, NY, USA: ACM. pp. 1221–1228. doi:10.1145/2330163.2330332. ISBN 978-1-4503-1177-9.
  27. ^ Mayo, M.; Spacey, S. (2013). Predicting Regression Test Failures Using Genetic Algorithm-Selected Dynamic Performance Analysis Metrics (PDF). Proceedings of the 5th International Symposium on Search-Based Software Engineering (SSBSE). Vol. 8084. pp. 158–171. doi:10.1007/978-3-642-39742-4_13. hdl:10289/7763.
  28. ^ (http://www.evosuite.org/)
  29. ^ others, Ned Batchelder and 100, coverage: Code coverage measurement for Python, retrieved 14 March 2018
  30. ^ "Open Source Profilers in Java".
  31. ^ "Sapienz: Facebook's push to automate software testing". VentureBeat. 30 December 2018. Retrieved 29 September 2020.
  32. ^ Jones, Derek (18 October 2013). "Programming using genetic algorithms: isn't that what humans already do ;-)". The Shape of Code. Retrieved 31 October 2013.
  33. ^ Le Goues, Claire; Forrest, Stephanie; Weimer, Westley (1 September 2013). "Current challenges in automatic software repair". Software Quality Journal. 21 (3): 421–443. CiteSeerX 10.1.1.371.5784. doi:10.1007/s11219-013-9208-0. ISSN 1573-1367. S2CID 16435531.
  34. ^ Simons, Christopher L. (May 2013). Whither (away) software engineers in SBSE?. First International Workshop on Combining Modelling with Search-Based Software Engineering, First International Workshop on Combining Modelling with Search-Based Software Engineering. San Francisco, USA: IEEE Press. pp. 49–50. Retrieved 31 October 2013.

외부 링크