Publications
[ArnoldHPS14]
Time-Dependent Analysis of Attacks.
In Principles of Security and Trust (POST), Springer, Lecture Notes in Computer Science , 2014.
Downloads: pdf, bibAbstract. The success of a security attack crucially depends on time: the more time available to the attacker, the higher the probability of a successful attack; when given enough time, any system can be compromised. Insight in time-dependent behaviors of attacks and the evolution of the attacker’s success as time progresses is therefore a key for effective countermeasures in securing systems.
This paper presents an efficient technique to analyze attack times for an extension of the prominent formalism of attack trees. If each basic attack step, i.e., each leaf in an attack tree, is annotated with a probability distribution of the time needed for this step to be successful, we show how this information can be propagated to an analysis of the entire tree. In this way, we obtain the probability distribution for the entire system to be attacked successfully as time progresses. For our approach to be effective, we take great care to always work with the best possible compression of the representations of the probability distributions arising. This is achieved by an elegant calculus of acyclic phase type distributions, together with an effective compositional compression technique. We demonstrate the effectiveness of this approach on three case studies, exhibiting orders of magnitude of compression.
[Bungert13]
Android App for Minimization of Acyclic Phase-Type Distributions.
Master's Thesis, Universität des Saarlandes, Saarbrücken, Germany, 2013.
Downloads: pdf, bibAbstract. Acyclic phase-type distributions are probability distributions that mainly consist of combinations of exponential distributions and can be represented by continuous-time Markov chains. The computation time when analyzing these distributions strongly depends on the size of their representations. However, because their representations aren’t unique, an algorithm was developed by Reza Pulungan and Holger Hermanns to minimize their state space [5]. They also developed a calculus which is able to construct these distributions.
In this thesis, an Android application to build and display these distributions according to this calculus is developed. It uses an already implemented web service to compute their minimal representations and makes this service reachable from any Android device.
[PulunganH13]
A construction and minimization service for continuous probability distributions.
In International Journal on Software Tools for Technology Transfer: 1-14, 2013.
Downloads: pdf, bibURL: http://dx.doi.org/10.1007/s10009-013-0296-8
Abstract. The universe of acyclic continuous-time Markov chains can provide
arbitrarily close approximations of any continuous probability distribution.
We span this universe by a compositional construction calculus for acyclic
phase-type distributions. The calculus draws its expressiveness from a single
operator, yet the calculus is equipped with further convenient operators,
namely convolution, maximum, and minimum. However, the size of the chains
constructed in this way can grow rapidly. We therefore link our calculus
to a compositional minimization algorithm that whenever applied almost
surely yields a chain with the least possible size. The entire approach
is available in the form of an easy-to-use web service. The paper describes
the architecture of this service in detail and reports on experimental
evidence demonstrating its usefulness.
[PulunganH09]
Acyclic Minimality by Construction---Almost.
In QEST 2009, Sixth International Conference on the Quantitative
Evaluation of Systems, Budapest, Hungary, 13-16 September
2009, pages 63-72, IEEE Computer Society, 2009.
Downloads: bibURL: http://doi.ieeecomputersociety.org/10.1109/QEST.2009.45
Abstract. Acyclic phase-type distributions are phase-type distributions with
triangular matrix representations. They constitute a versatile
modelling tool in many circumstances. The size of their matrix
representation has a strong influence on computational efforts
needed when analyzing these distributions. This representation,
however, is not unique, and two representations of the same distribution
can differ drastically in size.
This paper explores an effective algorithm to reduce the size of
the matrix representation without altering the distribution. This
proceeds via a symbolic representation of the Laplace-Stieltjes
transform of the phase-type distribution. The algorithm is of
cubic complexity in the size of the given representation. We
clarify the circumstances under which the algorithm returns a
minimal representation, and discuss in how far it can keep
representations minimal when they are constructed via any of
three operations---convolution, minimum, and maximum. A case study
modelling delay propagation in railway networks demonstrates the
practicality of the approach.
[PulunganH08]
The Minimal Representation of the Maximum of Erlang Distributions.
In Proceedings 14th GI/ITG Conference on Measurement, Modelling
and Evaluation of Computer and Communication Systems (MMB
2008), March 31 - April 2, 2008, Dortmund, Germany, pages 207-222, VDE Verlag, 2008.
Downloads: bibURL: http://www.vde-verlag.de/proceedings-en/563090015.html
Abstract. Analysis of models comprising concurrent stochastic processes
leads to state space explosion, just like in many other areas of formal validation.
The number of states grows exponentially in the number of involved processes.
One of the principal constituents of many such processes is the so-called Erlang
distribution, which is particularly well-suited as approximations for fixed
delays---with adjustable accuracy. The concurrent execution of Erlang distributions
corresponds to their maximum. In this paper, we show that an exponential growth of
the Markov chain representation of the maximum of Erlang distributions is inevitable.
This is because even its minimal representations grow exponentially.
