Project Plan: Process structure extraction from ERLANG /OTP systems
- Project manager ?%
- Bengt Jonsson,
Department of Computer Systems, Department of Information
Technology, Uppsala University.
- Ph.D. student 80%
- Jan
Nyström,
Department of Computer Systems, Department of Information
Technology, Uppsala University.
- Industrial contact
- Thomas Arts,
Computer Science Laboratory, Ericsson Utveckling AB.
- Industrial contact
- Ulf Wiger,
ATM Multiservice Networks,
Ericsson Telecom AB.
ERLANG is a concurrent functional language, which
has been successfully used for the development of complex telecommunication
software within Ericsson. An ERLANG system typically creates a lanrge number
of processes. This is one of the strengths of the language, since this
allows modularisation of the code. However, it may also create problems when
analysing and debugging system.
A large ERLANG system, possibly made up of several applications,
consisting of multitude of processes is hard to overview, since processes
are dynamically created, destroyed, and may be automatically restarted after
failures.
The purpose of this project is to develop algorithms and tools that
analyse the static and the dynamic process structure of an ERLANG
system. The first goal is to develop algorithms for creating the
tree of created process in an ERLANG system. In this tree, each node
represents a process, and the processes that it may potentially create are
represented as its children. We will use some existing graph handling
tool to visualise the tree and animate it to show creation of the
processes at setup.
Apart from the apparent use in having a graphical global view the
extracted model although rudimentary is far more amenable to
analysis then the code itself. If one keeps the attributes of the
standard behaviours, such as maximal restart frequency, in the model
one can use the knowledge of these behaviours and, e.g.,
show what parts, if any, are restarted on the failure of a particular
process.
Associated with the ERLANG language is the Open Telecom Platform(OTP)
with library routines for standard behaviours of telecommunication
systems which incorporates failure handling and recovery and other
behaviours such as logging.
In our work, we will assume that applications are written using the
libraries provided in OTP.
Conversely, if you can visualise the system process architecture with
trees annotated with attributes to the node and relationships between
arcs such as ``created before'', the same means can be used to specify the
system. When the same format is used as target for abstraction and
for specification, the specification can readily be compared to
the abstraction of the implementation.
ERLANG [Armstrong,Barklund] is a simple call by value
functional language with
semi-lightweight processes that allows a high degree of
concurrency. Processes communicates asynchronously via message passing
and the distribution is non-transparent. The ERLANG runtime system
supports detection of process, as well as ERLANG node, failures. The
above, together with the code loading mechanisms support for hot-swap of
code, provides a good framework for building fault-tolerant concurrent
soft real-time systems that can be run with high availability.
Typical systems that benefit from ERLANG is telecommunication
systems[Blau,Däcker,Hinde], but ERLANG has also been used to
construct the Bluetail Mail Robustifier[Bluetail] that
handles traffic management for clusters of mail server in a robust way.
Coupled with the ERLANG programming language is Open
Telecom Platform([OTP]) which a set of
libraries originally intended to aid the construction of telecommunication
systems. The libraries encode ``design patterns'' used to construct
telecommunication systems and effectively supplies code skeletons
where the actual behaviour is realised as a call-back module.
Here we will present the state of the art in areas connected to the
work proposed in this project.
A possible approach would be to use abstract interpretation, in the
context of ERLANG this has been explored by Huch in [Huch].
In Huch work the erlang system is viewed as as a set of
expression evaluation in the context of the identity of the process
executing the expression and the message queue. The abstract consists
of truncating the terms in the expression at a predefined depth.
It is mentioned in the paper how one could tailor the interpretation
so that for selected terms the terms are either kept as they are or
truncated at a greater depth. The interpretation which can handle
small problems. The interpretation can only handle tail recursive
programs and does not handle exceptions, links, nor process termination.
Another interesting method of coming to grips with concurrent systems
is to reduce them to a finite state models by means of extracting a control
skeleton from the code.
Holzmann has extracted finite non-deterministic SPIN models for a
C with threads, by abstracting away statements and procedure not
connected to the properties under inspection, in the tools
FeaVer[Holzmanna] and AX[Holzmannb]. This method
relies on the user to define the abstractions, i.e. deciding what
procedures and variables are unimportant, and consequently is not
formally sound.
A similar but more soundly founded approach is applied by Corbet and
colleagues for JAVA in the Bandera projec[Corbet] where they use
shape analysis to determine what variables are only accessible from
one thread.
A more theoretically oriented approach is followed by Nielson et
al[Nielson], which derive finite-state control skeleton from a
program in Concurrent ML where values abstract to their types.
An important subproblem is the construction of call-graphs for the
modules in the system under inspection, notably is resent work by
Agrawal[Agrawal] where the call-graph is construct on demand
rather then constructing the entire call-graph, which has been case in
most earlier work on call-graphs.
The goal of the project is to, given an ERLANG system constructed
using the mechanisms provided for application handling and supervision
by the Open Telecom Platform, produce a annotated tree that
describes the process structure and dynamics of the system, starting
with the process structure.
The project will proceed in a number stages presented below.
- Stage1
- In a system well written system, i.e. where the
OTP System Architecture Support Libraries(SASL) have been
used, as well as the generic modules and behaviours, identify the
static processes created and in what order they will be created. By
static processes is meant the processes that are created in the
beginning of the system and exist continuously throughout the systems
lifespan. The processes should be annotated by behaviour where that is
known, i.e. where OTP standard behaviours such as ``generic server''
is used. The structure will be presented graphically
- Stage2
- A) Turn the ``unsafe'' creation tree from
prototype of Stage1 into a safe over-approximation of the
possible creation trees. Define what a safe over-approximation is in
terms of semantics with side-effects for ERLANG .
B) Add animation of start and failure behaviours to the graphical
interface.
C) Add the extended behaviours AXD301 to the extraction and evaluate the
benefits of the analyse on production code.
- Stage3
- Detect what processes can be dynamically created,
and which processes are linked. Analyse which processes
communicate with each other. Develop mechanisms for specifying systems
in the same manner that they are presented when abstracted, i.e., as
trees with annotated edges and nodes.
- Stage4
- Provide a mechanism to compare abstracted system
behaviour and specified behaviour. Trough the tracing mechanism
provided by the ERLANG runtime system check(possibly having
annotated the code with ``names'' to identify what processes are
created) that the test runs are within specified(as of Stage3) behaviour
of the system.
- 2001-05-01
- Stage1 prototype finished.
- 2001-05-15
- Submission to the Erlang Workshop in connection
with the conference: Principles,
Logics, and Implementations of high-level programming languages.
- 2001-08-28
- ASTEC Seminar presenting Stage1.
- 2001-11-30
- Stage2 A) prototype finished.
- 2001-12-15
- DoCS Technical report describing the Stage2 A)
- 2002-01-??
- ASTEC Seminar presenting Stage2.
- 2002-01-15
- Stage2 B) prototype finished.
- 2002-02-15
- Stage2 C) prototype finished.
We will organise the work as follows:
- Stage1)
- Our process structure tree is constructed using an instrumented evaluator for
Core ERLANG . Core ERLANG [Carlsson00,Carlsson01b] is an intermediate
format used in the OTP ERLANG compiler where syntactic sugar has
been removed and
a restricted set of constructs and formats are used. There are also
constructs in Core ERLANG that are not present in ERLANG , such as,
``let'' and ``letrec'' which are used to replace explicit matching and local
functions generated by list expressions.
The reason, as to why we instrumented an evaluator, rather then trying
a static program analysis, is that when starting an application and
generating the static processes the programmer has the use of, and in
many cases also need for, the full expressive power of ERLANG . Hence we
would have to deal with the full language in order to determine what
processes where generated by an application.
Our reason for writing an evaluator of Core ERLANG as
opposed to ERLANG itself (for which there already exist an evaluator
in the distribution of ERLANG ) is that it was much simpler to deal
with code where matters such as macros, files inclusion and records
had already been taken care of and it has fewer constructs.
The analysis does so far consist of evaluating a call to
application:start/1, where the result will contain the value
computed, collected ``side-effects'' and the resulting environment.
The collection of ``side-effects'', or rather processes creation and
management. The
resulting environment will contain the modules and applications loaded
during the evaluation.
For more detailed description read the PLI'01[Nyström] contribution.
- Stage2)
- A) Construct a abstracting collecting semantics of Core ERLANG based on
the denotational semantics for Core ERLANG presented in
[Carlsson01a], use this a basis for making a abstracting evaluator
that collects all the alternative result of the different executions.
B) The behaviour of the application is given by the process creation
tree and animation can easily be made of what happens on a process
failure.
- Stage3)
- Develop a technique for extracting code skeleton from ERLANG
systems. These skeletons consists of the control flow with function
calls where only functions containing primitives dealing with the
concurrency and communication constructs of the language and the OTP
concepts will remain.
Initially, we will retain only the following language primitives:
- spawn, link
- exit, kill
- !, receive
- normal function returns
- function calls.
The function calls to functions which functional skeleton is empty
will be removed until a fix-point is reached.
We will use OTP concepts to find the structure, application resource
files which defines how an application should be started and what
modules should be loaded etc. and behaviours.
- Stage4)
The use of a tool that extract the architecture, and in a manner
reverse engineer is always useful. If one can also add domain specific
extraction and analysis of the model that will prove a boon when
trying to assert that a particular convention is followed. That
particularly when the convention relies on the cooperation of several
processes.
- Agrawal
-
Agrawal, G., 2000: Demand-Driven Construction of Call
Graphs, In Proceedings of 9th International Conference in Compiler
Construction, ed. D.A. Watt , LNCS Vol.1781, pp.125-140, Springer-Verlag, 2000.
- Armstrong
-
Armstrong, J., Virding, R., Wikström, C., Williams, M., 1993:
Concurrent Programming in Erlang, 2nd ed., Prentice
Hall, 1996.
- Barklund
-
Barklund, J., Virding, R., 1999: Specification of the
Standard Erlang programming language, draft version 0.7, http://www.erlang.org/download/erl_spec47.ps.gz, June 1999.
- Blau
-
Blau, S., Rooth, J., Axell, J., Hellstrand, F., Buhrgard,
M., Westin, T., Wicklund, G., 1999:
AXD 310: A new generation ATM switching system,
Computer Networks, No.31, pp.559-582, Elsevier Science
B.V., 1999.
- Bluetail
-
Product information on Bluetail Mail Robustifier,
http://www.bluetail.com/products/bmr/.
- Carlsson00
-
Carlsson, R, Gustavsson, B., Johansson, E., Lindgren, T.,
Nyström, S.-O., Pettersson, M., Virding, R., 2000: Core Erlang
1.0 language specification, Technical Report 2000-030,
Department of Information Technology, Uppsala University, 2000.
- Carlsson01a
-
Carlsson, R., 2001: Core Erlang introduction and
formal sematics, Manuscript, Private communication, 2001.
- Carlsson01b
-
Carlsson, R., 2001: An Introduction to Core Erlang,
Proceedings of Erlang Workshop, 2001.
- Corbet
-
Corbet, J.C., 2000: Using Shape Analysis to Reduce
Finite-State Models of Concurrent Java Programs, ACM Transactions on
Software Engineering and Methodology,
Vol.9, No.1, pp.51-93, January 2000.
p
- Däcker
-
Däcker, B., 2000: Concurrent Functional Programming for
Telecommunications: A Case Study of Technology Introduction,
Licentiate thesis, Computer Communication System Laboratory,
Department Of Teleinformatics, Royal Institute of Technology, Sweden,
2000.
- Hinde
-
Hinde, S., 2000:
Use of Erlang/OTP as a Service Creation Tool for IN
Services,
Proceedings of Sixth International Erlang/OTP Users
Conference, http://www.erlang.se/euc/00/one2one.pdf,
2000.
- Holzmanna
-
Holzmann, G.J., Smith, M.H., 2000: Automating software
feature verification, Bell Labs Technical Journal, April-June 2000,
Special Issue on Software Complexity, 2000.
- Holzmannb
-
Holzmann, G.J., 2000: Logic Verification of ANSI-C Code
with SPIN, In Proceedings of 7th International SPIN
Workshop, eds. K. Havelund, J. Penix and W. Visser, LNCS Vol.1885,
pp.131-148, Springer-Verlag, 2000.
- Huch
-
Huch, F., 1999: Verification of Erlang Programs using
Abstract Interpretation and Model Checking, Proceedings of ICFP'99,
ACM SIGPLAN Notices, Vol.34, No.9, pp.261-272, ACM Press, 1999.
- Nielson
-
Nielson, H.R., Amtoft, T., Nielson, F., 1998: Behaviour
Analysis and Safety Conditions: a Case Study in CML, LNCS Vol.1382,
pp.255-269, Springer-Verlag, 1998.
- Nyström
-
Nyström, J., Jonsson, B., 2001:Extracting the Process
Structure of Erlang Applications, Proceedings of Erlang Workshop, 2001.
- OTP
-
OTP, 2000: OTP Documentation,
http://www.erlang.org/doc/current/doc/index.html.
jann@DoCS.UU.SE