A Behavioral Programming Approach to Search Based Software Engineering
Authors: Moshe Weinstock
Year: 2015

We present a model based approach to Search Based Software Engineering (SBSE). The approach is based on the Behavioral Programming (BP) paradigm where independent aspects of behavior are woven at run time using a simple interaction protocol. We propose to extend the behavioral programming execution mechanism with on-line heuristic search in program state space that allows programmers to develop non-deterministic programs while relying on a “smart” event selection mechanism to resolve non-determinism in a way that maximizes a specified heuristic function. The paper presents a new library that we have developed in Java and in JavaScript, using Rhino, to facilitate the proposed modeling approach and programming style. We give examples, in the context of a StarCraft game bot built with the library, that demonstrate how the proposed programming idioms can simplify the code and help build robust reactive systems. I. MOTIVATION AND BACKGROUND Search Based Software Engineering (SBSE) is an emerging field of research which aims to cope with the increased demand for functionality, scalability, and robustness of computer programs (and of reactive robotic systems in particular) using heuristic search mechanisms [1]. SBSE consists of automatic resolution (using search algorithms) of complex decisions that programmers model as optimization problems. There are many published papers in this area that describe various approaches within the software engineering research community [2], [3]. There are also reports that describe how SBSE has been successfully applied to solve problems in nearly all software development life cycle phases [4], [5]. The main challenge in SBSE is, of course, finding a good modeling technique that facilitates the search [6]. Despite the research activity in the area, search methods are practically used only in specific domains. Harman [2] reports, for example, that 54% of SBSE tools are used for testing purposes, an additional 11% for maintenance, and another 10% for project management. It seems that the main barrier that delays further adaptation of the technique is shortage in models for online search [6]. The goal of this this paper is to explore how SBSE can be made accessible to modelers and programmers of reactive systems, such as robotic applications and interactive game bots, as idioms that integrate with standard constructs in common modeling and programming languages. This allows for natural, powerful derivation from modeling languages (such as LSC [7], [8]) to code. Specifically, we aim at tools that facilitate the following software development methodology: 1) Code and/or derive from models the high-level specification of the system’s behavior, using non-determinism to specify free choices in execution. 2) Run the system using an engine that resolves non determinism heuristically or synthesize deterministic code. 3) If unsatisfied with the execution’s choices, extend the model by formalizing more refined requirements. 4) Repeat steps 2 and 3 until the behavior is satisfactory. The behavioral programming (BP) paradigm that we focus on in this paper is described in detail in Section II. BP extends and generalizes scenario-based programming which was introduced with the language of live sequence charts (LSC) [7], [8]. In addition to the refinement idioms that already exist in BP, which allow programmers to incrementally shape their software by adding modules that can both widen and narrow the set of possible behaviors of the system [9], we propose in this paper to allow BP based models to also contain specification of fitness criteria for the heuristic search function that can also be refined along the above development process. The idea of “smart” execution of scenario based specifications started in [10] and in [11] with proposals to apply, respectively, model-checking and planning algorithms for running a single super-step (the part of the run that spans between two consecutive external events) in LSC. We apply a similar mechanism in the context of a behavioral programming library embedded in an imperative programming language. Beyond running in a different setting, the main addition of our library, when compared to these earlier contributions, is that it runs the “smart” event selection mechanism at run-time, on real program code rather than on a model or specification, and that it can consider a horizon beyond a single super-step. II. BEHAVIORAL PROGRAMMING PRINCIPLES As presented in [12], a behavioral model consists of a set of independent behavior threads (b-threads for short). Each b-thread is a specification of a reactive machine that can be modeled, e.g., as a procedure in an imperative programming language. Together, the b-threads control the behavior of flow of the application via a synchronization protocol, as follows. When a b-thread reaches a point that requires synchronization, it waits until all other b-threads reach such synchronization points in their own flow. At synchronization points, each bthread specifies three sets of events: (1) requested events the thread proposes that these events be considered for triggering, and asks to be notified when any of them occurs; (2) waitedfor events the thread does not request these events, but only asks to be notified when any of them is triggered. The platform will not consider these events for triggering, unless given as external input to the system; and (3) blocked events the thread currently forbids triggering of these events. As shown in Figure 1, when all b-threads are at a synchronization point, a legal event (an event that is requested by at least one b-thread and is not blocked by any b-thread) is chosen. This chosen event is then triggered by resuming all the