This work was supported in part by the National Science Foundation under grant CCR-93-02739.
Department of Computer Science
University of Colorado
Boulder, CO 80309 USA
{jcook,alw}@cs.colorado.edu
Until now, most of the software process research has focussed mainly on modelling and execution of processes. But for this work to be successfully applied, true process engineering in the form of applying the analysis of data must take place. The variety of data that can be collected makes building general analysis tools very difficult, however, and to date most efforts have seen the ad hoc creation of data collection methods and tools. In this paper we present BALBOA , a framework for the collection of event-based process data and the application of tools to the data. This framework serves to unite the variety of collection mechanisms and a variety of tools with consistent data manipulation, management, and access services, and assistance in tool construction.
Process engineering, or re-engineering as some might have it, is an important activity if one wants to consistently produce a quality product in a reasonable, and estimatable, amount of time. People have long sought to define and control how things are done; yet, definitions often don't reflect how things are really done, and the control is a will-o'-wisp. Collecting and analysing process data would be useful in helping understand and control the process, yet people are hesitant to put too much effort into this, because it takes away that much direct effort from the product, without guarantees of payback.
Software process engineering has an advantage over other disciplines in that much of its activity takes place on computers; thus, it is more amenable to reducing the effort needed for process tracking and analyses. Indeed, in the past several years, there have been efforts to collect process data and analyse it to improve the process.
This work, so far, has seen the creation of single tools that access process data in an ad hoc manner. Several methods for collecting process data have been proposed and constructed (e.g., [6,1,2,7]); however, there has not been a significant effort to propose a coherent framework for tools and methods with which to do process analysis from process data.
Such a framework would be useful in many ways. From the data access perspective, a framework that isolated the tools from the variety of data formats and provided a consistent access manner to all of the data would reduce the effort needed to make a tool widely-usable with multiple data formats. Indeed, by providing access methods in libraries, tools could be constructed quite easily. From the data management perspective, a framework that provided for the management of data would eliminate the need to provide such (redundant) facilities in each and every tool, and for each and every data formats.
This paper describes such a framework, BALBOA , that supports the analysis of process executions and process models through the use of event-based data. We concentrate on event data because it supports a wide variety of behavioral and temporal analyses. Balboa supports the use of event data in two ways. The first is support for the managing and interpreting data that has been collected. The second is support for the building of tools that fit into the BALBOA framework.
This paper has the following organization. Section 2 gives a motivating scenario for the usefullness of BALBOA .
Then Section 
describes the nature of event data,
its strengths and weaknesses, and how it is used.
Section 3 follows with a presentation of the
architecture of the BALBOA
framework.
The implementation of BALBOA
is then described in detail in
Section 4.
Section 5 then describes two tools that have
been successfully constructed using the Balboa framework. Finally,
Section 6 concludes with some insights and ideas
for future work.
As a motivating example for the use of Balboa, consider a development group building a large piece of software. The system is far enough along so that they do an integration build once a week, including all the additions and changes completed up to that point. The group feels that they are getting too many errors in the system at each integration build, and, looking at the errors, cannot point to something in the product (specification, design, etc.) that is causing this. They decide that a more detailed look at their process is in order. Up to this point, they have relied on an informal textual document that described their process. The group decides to use Balboa to help them with this examination, and appoints a process engineer (p.e.) to coordinate and perform the examination.
The first step the p.e. makes is to instrument their site for data collection. The p.e. uses Yeast ([5]) to watch a directory structure for file modifications, and output these as events. The p.e. wraps the basic commands in shell scripts to first record the command as an event and then execute the command. The p.e. adds an email repository account for everyone to cc when communicating about the project, and adds a simple utility program to allow people to record phone or other communication events, and events such as meetings, inspections, and reviews.
With this infrastructure in place, the p.e. then collects data through a week's cycle of the process. At this point the p.e. will begin to use that data, while still collecting another week's worth of data. After that, the p.e. will continue collecting the automatically generated data, but will not ask the group to record other events. This way they know that the intrusiveness of the data collection will only last a short time.
With a little processing, the event data the p.e. has collected is put into a single event stream with a common format, having fields of event type, time, date, generating user, receiving user(s), and products (files) involved.
Since the p.e. knows that each developer works relatively independently, the first discovery experiments the p.e. tries involve discovering individual processes. For this, the p.e. extracts from the event stream just those events that are generated by a single person. The p.e. does this for each person.
For each of these extracted event streams, then, BALBOA/DISCOVERY is used to discover a model of that person's process. In doing this, it is found that some people are making last-minute changes during the regression testing of the piece they are working on, but do not re-start the regression testing. It is felt that this could be causing some of the integration problems.
As a second view to the process, the p.e. also extracts from the event stream just the events pertaining to a single product. The p.e. does this for several products that the p.e. feels are central and give a good experimental mix. BALBOA/DISCOVERY is used here to see the process that a product goes through, including being checked out, modified, read, and checked in. In this analysis, it is seen that some products are being checked out in read-only while it is also checked out to be modified. The read version does not have the changes being made on the ``locked'' version. Although the group thought that the rules for using RCS specified a strict lock when modifying files, in reading their informal process specification they now see an ambiguity in it.
With these two problems identified, that of lax regression testing on components, and the non-strict use of RCS, the p.e. now goes about fixing the process. From the pieces that BALBOA/DISCOVERY has created, the p.e. refines the state machines into complete models that BALBOA/VALIDATION can use to validate their process. The p.e. also publishes a report to the project group detailing their findings and recommendations. The group agrees that these changes should be enforced.
With the changes in the process being followed, the p.e. continues to collect the automatic data, since the extra off-computer events are not central to the problems the p.e. is trying to fix at the moment.
With this new data from a week-long cycle of the process, the p.e. uses BALBOA/VALIDATION to compare the new process execution with the model the p.e. now has of the desired process. The p.e. finds a good correspondence, and in a detailed look at the regression testing finds a much stricter testing process than what the the group did have. And indeed, in that integration build, and subsequent ones, the number of errors has decreased dramatically.
In the area of real-time, concurrent systems analysis, tools have had complete control over the environment, from the compiler and linker used to instrument the system to the tools that are used to analyze the data. Thus, they have not needed a general framework. [what about PICL?] Tools in the software process arena, on the other hand, must deal with event data from multiple, heterogeneous sources, and also with varied formats of the events. In this climate a framework such as BALBOA is needed.
BALBOA , then, is a framework in which tools fit into and are insulated from the heterogeneous nature of process data, and in which services dealing with the management of data are provided. This section describes the architecture of BALBOA in terms of its high-level components and their requirements. This architecture is shown in Figure 1.
Figure 1: Balboa Framework Architecture.
The components of BALBOA are:
In the BALBOA framework, we do not address the issue of providing mechanisms for collecting the event data, for two reasons. One is that there already exists a variety of mechanisms for collecting such data already. Basili and Weiss describe a method for manual, forms-based collection of data for use in evaluating and comparing software development methods [1]. Amadeus is a system for automated collection and analysis of process metrics [6]. Wolf and Rosenblum use a hybrid of manual and automated collection methods [7]. Bradac, et. al., provided the user with a menu-based tool that collects sampled task and state information [2].
The second is that the mechanisms for collecting such data can be site-specific, so that it is more flexible to allow event data to be sent to BALBOA from various sources. It also may be the case that a single project will have to use several different collection mechanisms; for example, a combination of automated and manual collection. It is because of this variety that a framework such as BALBOA is needed to allow tools consistent access to all kinds of data.
We also do not address the issue of data integrity; we assume that the data are correct (i.e., the events that are collected have actually occurred) and consistent (e.g., all ``begin'' events for an activity have a corresponding ``end'' event). If needed, tools could be built to help clean up raw event data.
Note that event data should be able to be both pushed through BALBOA to a tool or pulled through by a tool. A tool that provides real-time statistics of a process would want event data as it occurs; so BALBOA would push this data through as it was made available. Tools that operated in more of a post-mortem style on an already-gathered collection of events would want data as they needed it, so they would issue requests to pull the data from BALBOA . Both styles of data access need to be supported in this framework.
The preceding section described the abstract architecture of BALBOA . In this section we describe its implementation and how it instantiates the services described in the architecture.
BALBOA is built on the Unix/X platform using C++ and Tcl/Tk as the development languages. BALBOA provides support for tools in both of these languages, thus allowing both the construction of robust, ``polished'' tools and the fast exploration of ideas using an interpreted prototyping language. The BALBOA system currently consists of source C++ lines (non-commented), and 2700 lines of source Tcl/Tk lines (non-commented). This includes tools associated with BALBOA , and generic routines developed in the course of BALBOA 's implementation.
BALBOA collects and serves event data through two mechanisms--sockets and files. In many instances, data that a user is going to be accessing is local and stored in simple files directly under the user's control. In these cases, tools may want to access the data through a simple file-based interface. BALBOA provides the ability to serve data through this simple interface. On the other hand, there can be situations where the owners of the data would like stricter control over how, when, and where the data is used; for this, BALBOA provides a socket-based client-server mechanism, where the tools are clients and request interpreted event data from a BALBOA server. This mechanism provides the possibilities of remote data access, authenticating clients, massaging data to sanitize it for public use, and for restricting access to the data. Additionally, a file-based interface doesn't handle the case of a continuous, real-time, stream of process events.
For the file-based interface, BALBOA 's server is executed as a batch command that reads the raw data and the meta-data, and produces a file of the appropriate format for the tool(s). BALBOA 's managerial tools also recognize this mode and read and write the corresponding meta-data locally into files. As a server, BALBOA is run as a daemon to which tools connect dynamically by specifying the machine name (or address) and port number that BALBOA is using.
For the implementer of the tools, however, the distinction between a file-based and socket-based usage pattern is a minor one. The FACILITATOR part of BALBOA provides routines to the tools that blur this distinction, and only a minor initialization difference can be seen in the implementation.
Each of the architectural pieces of BALBOA are described next.
There are two basic styles of data that can be gathered into to BALBOA . One is a stream of data from an active software process. A stream has no specific ending point---it continues as long as events are produced and a connection remains between BALBOA and the source. Tools that monitor resource usage or the progress of the process in a real-time setting would make use of this style of data. The other style is a static event source, one that has a beginning and an end. Post-mortem and other analysis tools would make use of this style of events.
For both styles, BALBOA can either store them in an event collection or just let them pass through to a tool. Since a stream continues and cannot ``back up'', one might want to store it as it is produced in order to use it later in other analyses. A static event source might take considerable effort to extract the event, so that once extracted it may be useful for BALBOA to store them. In both styles, space limitations or other considerations may influence one to not store the gathered data into event collections.
To the other parts of BALBOA , then, the gatherer appears as a fixed interface that allows event data to be served. Internally, the gatherer is split into two parts---a fixed front end that serves events to the other pieces, and a variable, data-type-specific back end that understands the type of data and the source of the data.
For the file based collection, which already exists and the data owner wants to make accessible through Balboa, the collection manager has the ability to import a data file when the specification of the data collection is made. In this case, the data is copied and stored in a collection that is control under Balboa.
For the socket based interface, [who knows?].
[specify how to gather data; how do collection mechanisms hook up;]
As described in Section ,
events collected in an event stream are
complex data that have attributes.
Tools will more generally want to understand event types and the
attribute values.
Thus, to make use of the event data, one must specify mapping criteria to map the events to specific event types, and to handle attribute matching. These mapping specifications are then used by the interpreter to understand the raw event data and extract event type and attribute values from it.
We do not assume that event streams are homogeneous, but rather that it is likely that they are non-homogeneous, coming from a variety of sources. The mechanism to interpret events, i.e. map them into event types and set attribute values is a two-tiered one based on regular expressions and attribute values.
For a given event stream, a set of regular expressions are specified for describing the events in that event stream. Each event is expected to match one regular expression. If it matches more than one, the first one it matches is used; if it matches none, then that event cannot be interpreted, which is an error.
The regular expression is bracketed by curly braces into pieces that represent event attributes. Each piece of the regular expression inside curly braces represents one attribute, and each part of the regular expression outside braces represents the white space between the attributes. The attributes then are named rather than referring to them positionally. To specify a unique event type, then, a set of attributes of that regular expression are flagged as defining the event type. The unique values of the cross product of those flagged attribute types determine the event types in the event stream.
For example, suppose we have an event stream that has the event FILE-WRITE code io.c jcook 15:34:21 09/11/93
in it. This event can be mapped by providing the regular expression
which specifies a simple pattern of four attributes separated by spaces, and ignoring all of the rest (the time and date). These attributes are named sys-op, doc-type, doc, and user. The attributes sys-op, doc-type are then flagged as those that define the event type. Thus, an event with sys-op== FILE-WRITE and doc-type== design would be a different event type from the one shown. The attributes doc and user are variable within an event type, however. The event type is the spaced concatenation of the flagged attributes; thus, the first event above would have an event type of FILE-WRITE code.
A tool can also ask for an encoded version of the event type, called a token. A token is a single character or integer encoding of the event type. This reduces a large event stream to a simple, small stream of characters (integers). This is useful because, for tools that might do pattern matching or something similar, the need to look at large amounts of data in a simple form is paramount. Rather than have the tool do the mapping, the interpreter provides the mapping for the tool, and also remembers the reverse mapping from token to event type, so that user I/O can be accomplished using the understandable event type, and not the (externally) meaningless token.
The interpreter, then, accepts raw event data from the gatherer, maps that event into an event type and attribute values, and then sends this data on to the provider.
The provider in BALBOA is the mechanism that communicate the interpreted event data to the tools that request it. Recall above that BALBOA can serve data to tools by both files and sockets. For the file method, BALBOA just produces the file of interpreted event types and attributes (if needed), so there is no direct connection between the tools and BALBOA . With the socket interface, tools connect directly to BALBOA , and communicate with it to establish an interpreted event stream flow of data.
When a tool connects to BALBOA , an initial authorization takes place, where the server can either accept or reject the connection. [this doesn't exist - can put a simple mechanism in]. This is important if the owner of the data wants to maintain control of who gets what data and in what form. For example, a company may agree to make some data available outside the company, but only in some sanitized form. Tools inside the company, however, would be given access to all the data.
There are three main methods of serving events: tokens or event types, event attributes, and raw events. Some tools may just be interested in the structure of the event stream, and in this case the event type alone is enough. This is provided in the form of either the textual event type name or a single token (character or number).
Other tools will be interested in the values of attributes on the event types, to validate that the correct operations are happening to the correct artifacts, for example. BALBOA allows tools to access any or all of the attribute values for the last event that was provided to the tool. Lastly, if a tool needs access to the raw events, a null interpreter can be used to provide the tools with this. Note that if raw events are accessed, then attribute values are not available, since the event was never interpreted. [This should be changed?]
In order to make use of the event data, tools and users have to be able to manage and describe the data. BALBOA provides several mechanisms and user tools to perform these functions:
Figure 2 shows a snapshot of BALBOA/LAUNCHPAD .
Figure: The BALBOA/LAUNCHPAD
tool.
As can be seen in the figure, this tool is a simple interface to start up the various pieces of BALBOA . In addition, tools can be installed onto the BALBOA/LAUNCHPAD ; thus BALBOA helps to manage the tools that use it as well as the data. A collection site (file or a BALBOA server) can be specified here, which is then inherited by all the tools as they are started up. This makes the interaction with one collection site transparent across all tools.
Figure 3 shows the BALBOA/COLLECTIONMANAGER .
Figure: The BALBOA/COLLECTIONMANAGER
tool.
This tool provides a mechanism for the user to view, create, and modify the descriptions of collections of events. It provides a direct-manipulation list of event collections. The lower part of the screen is a field-oriented form for modifying or creating specifications. To modify a collection, clicking on it in the list will bring its data into the fields, which can then be individually modified and finally written back with the modify button. To create a new specification, the fields are filled out and the create button is pressed. Note that an existing collection description can be used as a template simply by selecting it in the list, thus bringing in its data to the fields.
When a new specification is created, if it is a file-based stored collection, the data can be immediately imported into BALBOA . A dialog box appears after the create button, allowing the user to specify a file to import the data from. This file is imported into BALBOA as the raw event data.
[How to specify real-time data?]
Figure 4 shows a snapshot of BALBOA/COLLECTIONVIEWER .
Figure: The BALBOA/COLLECTIONVIEWER
tool.
This tool provides a simple browser for event collections. Whether constructing an event mapping specification or simply wanting to see the raw data, there are times when a browser is indispensable.
Figure 5 shows a snapshot of BALBOA/EVENTMAPPER .
Figure: The BALBOA/EVENTMAPPER
tool.
This tool is used to create and modify the event mapping specifications used in BALBOA . As described in Section 4.2, event mapping is done using regular expressions, braced to specify event attributes, and a flagged subset of the event attributes to specify event types. BALBOA/EVENTMAPPER , then, provides the user with a two-list view of an even mapping specification. The upper list is the set of regular expressions specified in the mapping, and the lower list is the set of attributes for the currently selected regular expression.
For integrating tools, BALBOA provides library routines that make it easy for tools to connect to the provider end of BALBOA . These mechanisms are supported in both C++ and Tcl.
In C++, these interfaces are are just subclasses of a standard interface class, so the tool's code does not see a difference. Initialization routines for each of the interface types are provided. [Show the class interface]
In Tcl/Tk, the underlying socket mechanism is an addition to the Tcl interpreter, and then on top of this some basic Tcl routines are provided in a library module for the application's use. These routines, in general, hide the fact that the tool is communicating with a server or accessing a local file. These routines provide high-level services such as a dialog box to select event collections to low level services such as sending data over a socket.
To demonstrate the validity, usefulness, and flexibility of the BALBOA system, we describe here two tools that use BALBOA in quite different ways, yet both successfully. These tools are:
Because the creation of new process models can be an expensive and daunting task, we are exploring methods for automatically deriving a formal model of a process from basic data collected on the process. We term this form of data analysis process discovery, because inherent in every project is a process (whether known or unknown, whether good or bad, and whether stable or erratic) and for every process there is some model that can be devised to describe it. Process discovery can be used as an entry point into applying the many process technologies that use formal process models. A full description of our process discovery work can be found in [4].
BALBOA/DISCOVERY is the process discovery tool of BALBOA . It allows one to specify event streams and discovery method parameters, and run the methods to produce discovered process models. BALBOA/DISCOVERY writes out the discovered process models in a format compatible with the dot graph layout program [cite dot]. Figure 6 shows a snapshot of BALBOA/DISCOVERY .
Figure: The BALBOA/DISCOVERY
tool.
With BALBOA/DISCOVERY , one just specifies the source event collection (with its mapping specification), the discovery method, and the parameters for that discovery method. BALBOA/DISCOVERY then spawns off a discovery process, and in turn spawns a BALBOA/DOTVIEWER window to display the results. Each time a discovery process is run a new BALBOA/DOTVIEWER window is used. Thus multiple methods and/or parameter variations can be run and compared side-by-side on a large enough display. Once the BALBOA/DOTVIEWER display window is spawned off, it is completely independent of BALBOA/DISCOVERY .
BALBOA/DOTVIEWER is a tool that allows one to layout a graph specified in dot format, and then view and edit the graph. It has several features that are directly specific to dealing with process models from BALBOA/DISCOVERY . BALBOA/DOTVIEWER is a graphical editor of state machines, but it uses dot to lay out the graph automatically. Thus, there are no commands for moving nodes and edges. The I/O that BALBOA/DOTVIEWER uses is compatible with the dot program.
Previously, we said that we intended BALBOA/DISCOVERY to produce process models that need completing by human beings. To this end, the BALBOA/DOTVIEWER tool not only presents the discovered process models visually, but allows for the modification of the discovered process model. The operations that it supports are: merging nodes, creating/deleting nodes, creating/deleting edges, naming/renaming nodes, and splitting nodes.
In this work we are developing techniques for detecting and characterizing the differences between a formal model of a process and the actual execution of the process. We refer to the detection and characterization of differences as process validation. Process validation serves several purposes. For one, confidence in a formal process model is raised when it can be shown that the process execution is consistent with the behavior predicted by the model. This, in turn, raises confidence in the results of any analyses performed on the formal model. For another, process validation can be used as a process enforcement tool, uncovering differences between intended behavior and actual behavior. A full description of our work in process validation can be found in [3].
BALBOA/VALIDATION is the process validation tool of BALBOA . It lets one quantitatively and qualitatively compare an execution (collected) event stream to a process model and see how many and where deviations occur between the execution stream and what the model expects. Figure 7 shows a snapshot of BALBOA/VALIDATION .
Figure: The BALBOA/VALIDATION
tool.
As can be seen in the figure, BALBOA/VALIDATION gives the user both the quantitative metrics view of the validation, and also a detailed view in the scrolling areas showing each event stream. In the metrics view, the upper portion of the window, there are three levels of detail: the count of the individual insertions and deletions (in the upper middle); the count of the blocks of insertions and deletions (in the lower middle); and finally the calculated distance measurements (on the left side). BALBOA/VALIDATION also makes available the parameters used in the distance calculations (on the right side of the window), so that the user can interactively change the parameters and see the change in the calculations. The lower portion of the tool shows the detailed differences between the execution and what the process model expects. The execution stream is displayed on the left and the generated model event stream on the right. Events that are needed to be inserted into the execution stream to have it correspond to the model are colored blue (light grey bars), and those that need to be deleted are colored red (dark grey bars).
In order to do the validation, BALBOA/VALIDATION is given an event stream from BALBOA , and a process model specified by the user. BALBOA/VALIDATION then spawns a validation process that analyzes the model using the event stream, and produces a model stream that corresponds to the validated event stream. Additionally, BALBOA/VALIDATION can spawn a BALBOA/DOTVIEWER window for the convenience of viewing a process model during the validation exercise.
We have presented BALBOA , a framework for consistently managing, interpreting, and serving process event data to analysis tools. The advantages it gives are that both the data collection and the tool construction are decoupled from having to worry about the format and access method of the data, how to interpret the data, and the managerial aspects of handling the data. This facilitates the construction of tools and allows them to access data from a wider variety of sources.
While event data supports many varieties of analyses, certainly there are other forms of valid data to be used. A major direction to take BALBOA in the future would be to incorporate other types of process, and perhaps product, data into it.
We have shown two example tools that fit into the BALBOA
framework, BALBOA/DISCOVERY
and BALBOA/VALIDATION
. We are
interested in building more tools, including performance monitoring
tools such as resource usage statistics, real-time verification tools
that apply temporal logic specifications (e.g., TRIO ),
and others.
This document was generated using the LaTeX2HTML translator Version 95.1 (Fri Jan 20 1995) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 -t Balboa: A Framework for Process Data Analysis main.tex.
The translation was initiated by Jonathan Cook on Mon Jan 8 10:31:46 MST 1996