Bluemoon: Home

Bluemoon es una herramienta prototípica para la simulación eficiente de eventos raros a través de técnicas de importance splitting. Sus usuarios pueden estudiar comportamientos poco frecuentes de su sistema (raros) sobre un modelo del mismo, por ejemplo la aparición de bugs en un software de alta confiabilidad o tolerante a fallas.

Bluemoon puede trabajar con cualquier tipo de sistema modelado como una cadena markoviana de tiempo discreto o continuo. Está preparada para estudiar comportamientos transitorios (e.g. cual es la probabilidad de perder un paquete antes de haber enviado todo el bache) y de estado estacionario (e.g. con qué frecuencia pierde paquetes mi red). La herramienta realiza un cómputo estadístico de la probabilidad de observar la anomalía de interés, construyendo un intervalo de confianza según los requerimientos del usuario. Ha logrado estimar correcta y eficientemente probabilidades del orden de 10-15, para niveles de confianza entre 90% y 95% y precisiones de hasta ± 10-16.

Bluemoon fue implementado como un módulo del model-checker probabilístico PRISM desarrollado principalmente por Dave Parker. Los modelos a analizar son descriptos con la sintaxis de PRISM en un archivo de texto plano, interpretado por éste y luego alimentados a Bluemoon, donde se realizan las simulaciones y el análisis de probabilidades. Por el momento sólo corre sobre sistemas operativos Linux.

Bluemoon es software gratuito, libre y de código abierto, disponible con la licencia Pública General de GNU (GPL).

Fundamentos teóricos

La división por importancia o importance splitting es una técnica de simulación de eventos raros que reduce la varianza de los estimadores Montecarlo estándares. Dado un presupuesto de cómputo permite lograr mejores estimaciones de la propiedad bajo estudio, o equivalentemente alcanza los criterios de confianza requeridos usando menos recursos computacionales.

A diferencia de otras técnicas como importance sampling, la división por importancia no requiere un análisis probabilístico de las distribuciones del modelo estudiado. Esto permite aplicarla de forma menos restrictiva en descripciones generales de sistemas, por ejemplo DTMCs y CTMCs. Importance splitting depende sin embargo de una función de importancia, normalmente definida por el usuario, para lograr la mejora prometida en la estimación.

Bluemoon implementa RESTART, un método particular de divisón por importancia de bajo costo en memoria y probada efectividad. A su vez utiliza las técnicas de Adaptive Multilevel Splitting para la definición del entorno de simulación. Su mayor contribución sin embargo es la posibilidad de construir automáticamente la función de importancia, que guiará al proceso de simulación otorgándole la eficiencia al método.

Bibliografía

  1. C.E. Budde, P.R. D'Argenio, and H. Hermanns, "Rare Event Simulation with Fully Automated Importance Splitting", in Computer Performance Engineering - 12th European Workshop, EPEW 2015, Madrid, Spain, August 31 - September 1, 2015, Proceedings, vol. 9272, M. Beltrán, W.J. Knottenbelt, and J.T. Bradley. Springer, 2015, pp. 275-290. DOI
Powered by Drupal