All software developers dream of the times when computers will write programs for them, or, if it is not possible, that computers will at least help them in this hard task. A large variety of software projects, from assemblers, compilers and interpreters to UML-based executable code generators are aimed at reaching this goal.

Search-based software engineering (SBSE) is a collection of techniques for solving problems that arise in the process of software development by translating them to optimization problems and, consequently, solving these problems. SBSE uses optimization methods such as genetic and evolutionary algorithms, ant colony optimization and other stochastic search algorithms.

The goal in the “Programming technologies” research direction of the Computer Technologies Laboratory is to create SBSE methods that would allow to automate the processes of design, development and testing of software.

Constructing control programs from their specification

Control software systems have complex behavior – they can produce different control actions in response to the same input events depending on the history of interaction. Research being conducted in a number of universities in the world (e.g., in Standford University) shows that it is advisable to use state-based models for design and analysis of such systems. The most well-known deterministic state-based model is a finite-state machine. The programming paradigm in which control program logic is expressed in the form of interacting finite-state machines is known as automata-based programming.

Designing control software systems, including systems based on finite-state machines, is an extremely complex and time-consuming process. Therefore, development of automated methods for finite-state machine construction is a task of current importance. Input data for finite-state machine construction may include a set of tests that the target system should pass or a specification expressed in the form of temporal properties that the system should satisfy.

Given a way to evaluate how well a finite-state machine based system solves a given problem, automated finite-state machine construction can be viewed as an optimization problem. Furthermore, in most cases such a problem cannot be solved with traditional optimization methods since the search space, which is the set of all possible finite-state machines, is not a continuous one. Stochastic search algorithms such as evolutionary algorithms and ant colony optimization can be used to solve such optimization problems.