Statistical Models of Network Traffic

Model-based approaches have been applied successfully to a wide range of tasks such as specification, simulation, testing, and diagnosis. But one bottleneck often prevents the introduction of these ideas: Manual modeling is a non-trivial, time-consuming task. Automatically deriving models by observing and analyzing running systems is one possible way to amend this bottleneck. To derive a model automatically, some a-priori knowledge about the model structure–i.e. about the system–must exist. Such a model formalism would be used as follows: (i) By observing the network traffic, a model of the long-term system behavior could be generated automatically, (ii) Test vectors can be generated from the model, (iii) While the system is running, the model could be used to diagnose non-normal system behavior. The main contribution of this paper is the introduction of a model formalism called 'probabilistic regression automaton' suitable for the tasks mentioned above.

Authors:

• Barath Kumar
• Oliver Niggemann
• Juergen Jasperneite

Keywords:

• Model-based approach
• Probabilistic regression automata
• Statistical models and Timed automata.

References:

[1] R. Alur, C. Courcoubetis, and D. Dill. Model-checking in dense realtime.
Information and Computation, 104:2-34, 1993.
[2] R. Alur, C. Courcoubetis, N. Halbwachs, T. A. Henzinger, P. h. Ho,
X. Nicollin, A. Olivero, J. Sifakis, and S. Yovine. The algorithmic
analysis of hybrid systems. Theoretical Computer Science, 138:3-34,
1995.
[3] R. Alur and D. Dill. A theory of timed automata. Theoretical Computer
Science, vol. 126:183-235, 1994.
[4] M. M. F. Bugalho and A. L. Oliveira. Inference of regular languages
using state merging algorithms with search. Pattern Recognition,
38(9):1457-1467, 2005.
[5] S. Burmester. Generierung von java real-time code f¨ur zeitbehaftete
uml modelle. Master-s thesis, University of Paderborn, Department of
Computer Science, Paderborn, Germany, September 2002.
[6] S. Burmester and H. Giese. The fujaba real-time statechart plugin. In
H. Giese and A. Z¨undorf, editors, Proc. of the first International Fujaba
Days 2003, Kassel, Germany, pages 1-8. University of Paderborn,
October 2003.
[7] S. Burmester, H. Giese, M. Hirsch, D. Schilling, and M. Tichy. The
fujaba real-time tool suite: Model-driven development of safety-critical,
real-time systems. In Proc. of the 27th International Conference on
Software Engineering (ICSE), St. Louis, Missouri, USA, pages 670-671.
ACM Press, May 2005.
[8] A. David and M. O. M¨oller. From huppaal to uppaal: A translation from
hierarchical timed automata toflat timed automata. Technical report,
BRICS, BRICS Report Series RS-01-11, March 2001.
[9] A. David and W. Yi. Hierarchical timed automata. Contacts:
[email protected], [email protected], 2000.
[10] C. Daws and S. Yovine. Reducing the number of clock variables of
timed automata. In RTSS -96: Proceedings of the 17th IEEE Real-Time
Systems Symposium, pages 73-81, Washington, DC, USA, 1996. IEEE
Computer Society.
[11] C. Dima. Real-time automata. Journal of Automata, Languages and
Combinatorics, Vol. 6, Issue 1:3 - 23, January 2001.
[12] J. S. Dong, P. Hao, and et.al. Timed automata patterns. IEEE
Transactions on Software Engineering, Vol 34(No. 6), December 2008.
[13] M. Gehrke, P. Nawratil, O. Niggemann, and W. S. M. Hirsch.
Scenario-based verification of automotive software systems. In
H. Giese, B. Rumpe, and B. Sch¨atz, editors, Proc. of the Dagstuhl-
Workshop: Model-Based Development of Embedded Systems(MBEES),
9.-13.1.2005, Schloss Dagstuhl, Germany, pages 35-42, 2006.
[14] H. Giese and S. Burmester. Real-time statechart semantics. Technical
Report tr-ri-03-239, Lehrstuhl f¨ur Softwaretechnik, Universit¨at Paderborn,
Paderborn, Germany, June 2003.
[15] H. Giese, M. Tichy, S. Burmester, W. Sch¨afer, and S. Flake. Towards
the compositional verification of real-time uml designs. In Proc. of the
9th European software engineering conference held jointly with 11th
ACM SIGSOFT international symposium on Foundations of software
engineering (ESEC/FSE-11), pages 38-47. ACM Press, September 2003.
[16] B. Kumar, J. Imtiaz, and J. Jasperneite. Applicability of uml marte-s
schedulability sub-package for engineering industrial real-time protocols.
In 2nd Junior Researcher Workshop on Real-Time Computing
(JRWRTC 2008) (in conjunction with the 16th International Conference
on Real-Time and Network Systems (RTNS 2008)), Rennes, France, Oct
2008.
[17] B. Kumar and J. Jasperneite. Industrial communication protocol engineering
using uml 2.0: a case study. In 7th International Workshop
on Factory Communication Systems (WFCS 2008), Dresden, Germany,
May 2008.
[18] B. Kumar, O. Niggemann, and J. Jasperneite. Timed automata for modeling
network traffic. In Machine Learning in Real-Time Applications
(MLRTA 09) (in conjunction with 32nd Annual Conference on Artificial
Intelligence (KI 2009)), Paderborn, Germany, September 2009.
[19] M. Kwiatkowska, G. Norman, R. Segala, and J. Sproston. Automatic
verification of real-time systems with discrete probability distributions.
Theoretical Computer Science, 282:101-150, 2002.
[20] P. Mosterman, J. Ghidella, and E. O-Brien. Model coverage as a
quality measure and teaching tool for embedded control system design.
In Frontiers in education conference - global engineering: knowledge
without borders, opportunities without passports, 2007. FIE -07. 37th
annual, pages T3J-1-T3J-6, Oct. 2007.
[21] J. R. Norris. Markov Chains. Cambridge University Press, 1997.
[22] P. Bremaud. Markov Chains - Gibbs Fields, Monte Carlo Simulation,
and Queues. Springer Verlag, 1999.
[23] PNO. Profinet specification iec 61158-5-10 (v2.1), 2007.
[24] PNO. Profinet specification iec 61158-6-10 (v2.1), 2007.
[25] A. Pretschner, W. Prenninger, S. Wagner, C. K¨uhnel, M. Baumgartner,
B. Sostawa, R. Z¨olch, and T. Stauner. One evaluation of model-based
testing and its automation. In ICSE -05: Proceedings of the 27th
international conference on Software engineering, pages 392-401, New
York, NY, USA, 2005. ACM.
[26] J. Sproston. Decidable model checking of probabilistic hybrid automata.
In FTRTFT, pages 31-45, 2000.
[27] S. Verwer, M. de Weerdt, and C. Witteveen. An algorithm for learning
real-time automata. In M. van Someren, S. Katrenko, and P. Adriaans,
editors, Proc. of the Sixteenth Annual Machine Learning Conference of
Belgium andthe Netherlands (Benelearn), pages 128-135, 2007.
[28] S. E. Verwer, M. M. de Weerdt, and C. Witteveen. Efficiently learning
simple timed automata. In W. Bridewell, T. Calders, A. K. de Medeiros,
S. Kramer, M. Pechenizkiy, and L. Todorovski, editors, Induction of
Process Models, pages 61-68. University of Antwerp, 2008. Workshop
at ECML PKDD.