From Requirements to Source Code: Evolution of Behavioral Programs
Source abstract
Abstract
Automatically generating executable code has a long history of arguably modest success, mostly limited to the generation of small programs of up to 200 lines of code, and genetic improvement of existing code. We present the use of genetic programming (GP) in conjunction with context-oriented behavioral programming (COBP), the latter being a programming paradigm with unique characteristics that facilitate automatic coding. COBP models a program as a set of behavioral threads (b-threads), each aligned to a single behavior or requirement of the system. To evolve behavioral programs we design viable and effective genetic operators, a genetic representation, and evaluation methods. The simplicity of the COBP paradigm, its straightforward syntax, the ability to use verification and formal-method techniques to validate program correctness, and a program comprising small independent chunks all allow us to effectively generate behavioral programs using GP. To demonstrate our approach we evolve complete programs from scratch of a highly competent O player for the game of tic-tac-toe. The evolved programs are well structured, consisting of multiple, explainable modules that specify the different behavioral aspects of the program and are similar to our handcrafted program. To validate the correctness of our individuals, we utilize the mathematical characteristics of COBP to analyze program behavior under all possible execution paths. Our analysis of an evolved program proved that it plays as expected more than 99% of the times.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Evolutionary Algorithms and Applications · Artificial Intelligence in Games · Advanced Malware Detection Techniques
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Software and Information Systems Engineering, Ben-Gurion University, Beer-Sheva 8410501, Israel
Department of Computer Science, Ben-Gurion University, Beer-Sheva 8410501, Israel
References (26)
Show source-provided references
1. Context-Oriented Behavioral Programming10.1016/j.infsof.2020.106504 ↗
2. Cramer, N.L. (1985, January 24–26). A representation for the adaptive generation of simple sequential programs. Proceedings of the International Conference on Genetic Algorithms and the Applications, Pittsburgh, PA, USA.
3. Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection, The MIT Press.
4. Orlov, M., and Sipper, M. (2009, January 8–12). Genetic programming in the wild: Evolving unrestricted bytecode. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, Montreal, QC, Canada.10.1145/1569901.1570042 ↗
5. Flight of the FINCH through the Java wilderness10.1109/TEVC.2010.2052622 ↗
6. On the cruelty of really teaching computing science
7. Genetic improvement of software: A comprehensive survey10.1109/TEVC.2017.2693219 ↗
8. Gabel, M., and Su, Z. (2010, January 7–11). A study of the uniqueness of source code. Proceedings of the Eighteenth ACM SIGSOFT International Symposium on Foundations of Software Engineering, Santa Fe, NM, USA.10.1145/1882291.1882315 ↗
9. Barr, E.T., Brun, Y., Devanbu, P., Harman, M., and Sarro, F. (2014, January 16–21). The plastic surgery hypothesis. Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, Hong Kong, China.10.1145/2635868.2635898 ↗
10. Forrest, S., Nguyen, T., Weimer, W., and Le Goues, C. (2009, January 8–12). A genetic programming approach to automated software repair. Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, Montreal, QC, Canada.10.1145/1569901.1570031 ↗
11. Weimer, W., Nguyen, T., Le Goues, C., and Forrest, S. (2009, January 16–24). Automatically finding patches using genetic programming. Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, Vancouver, BC, Canada.10.1109/ICSE.2009.5070536 ↗
12. Ackling, T., Alexander, B., and Grunert, I. (2011, January 12–16). Evolving patches for software repair. Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, Dublin, Ireland.10.1145/2001576.2001768 ↗
13. Le Goues, C., Dewey-Vogt, M., Forrest, S., and Weimer, W. (2012, January 2–9). A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. Proceedings of the 2012 34th International Conference on Software Engineering (ICSE), Zurich, Switzerland.10.1109/ICSE.2012.6227211 ↗
14. Automated repair of binary and assembly programs for cooperating embedded devices10.1145/2490301.2451151 ↗
15. Schulte, E., Forrest, S., and Weimer, W. (2010, January 20–24). Automated program repair through the evolution of assembly code. Proceedings of the IEEE/ACM international conference on Automated Software Engineering, Antwerp, Belgium.10.1145/1858996.1859059 ↗
16. Harel, D., Marron, A., and Weiss, G. (2010, January 21–25). Programming coordinated behavior in java. Proceedings of the European Conference on Object-Oriented Programming, Maribor, Slovenia.10.1007/978-3-642-14107-2_12 ↗
17. Shimony, B., and Nikolaidis, I. (2011, January 22). On coordination tools in the PicOS tuples system. Proceedings of the 2nd Workshop on Software Engineering for Sensor Network Applications, Honolulu, HI, USA.10.1145/1988051.1988056 ↗
18. A Context-Based Behavioral Language for IoT
19. D’Hollander, E.H., Joubert, G.R., Peters, F.J., and Trystram, D. (1995). Automatic Conversion of Programs from Serial to Parallel using Genetic Programming-The Paragen System. Parallel Computing: State-of-the-Art and Perspectives, Proceedings of the Conference ParCo 1995, Gent, Belgium, 4–15 September 1995, Elsevier. Advances in Parallel Computing.
20. Walsh, P., and Ryan, C. (1996, January 28–31). Paragen: A novel technique for the autoparallelisation of sequential programs using gp. Proceedings of the 1st Annual Conference on Genetic Programming, Stanford, CA, USA.
21. Barr, E.T., Harman, M., Jia, Y., Marginean, A., and Petke, J. (2015, January 13–17). Automated software transplantation. Proceedings of the 2015 International Symposium on Software Testing and Analysis, Baltimore, MD, USA.10.1145/2771783.2771796 ↗
22. Marginean, A., Barr, E.T., Harman, M., and Jia, Y. (2015, January 5–7). Automated transplantation of call graph and layout features into Kate. Proceedings of the International Symposium on Search Based Software Engineering, Bergamo, Italy.10.1007/978-3-319-22183-0_21 ↗
23. Le Goues, C. (2013). Automatic Program Repair Using Genetic Programming. [Ph.D. Thesis, School of Engineering and Applied Science, University of Virginia].
24. Arcuri, A., and Yao, X. (2008, January 1–6). A novel co-evolutionary approach to automatic software bug fixing. Proceedings of the 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), Hong Kong, China.10.1109/CEC.2008.4630793 ↗
25. Flexible strategy use in young children’s tic-tac-toe
26. Simani, S., Fantuzzi, C., and Patton, R.J. (2003). Model-based fault diagnosis techniques. Model-Based Fault Diagnosis in Dynamic Systems Using Identification Techniques, Springer.10.1007/978-1-4471-3829-7 ↗