CSAIL Research Abstracts - 2005 link to http://publications.csail.mit.edu/abstracts/abstracts05/index.html link to http://www.csail.mit.edu
bullet Introduction bullet Architecture, Systems
& Networks
bullet Language, Learning,
Vision & Graphics
bullet Physical, Biological
& Social Systems
bullet Theory bullet

horizontal line

A Model-Based System Supporting Automatic Self-Regeneration of Critical Software

Paul. Robertson & Brian C. Williams


In complex, concurrent critical systems, every component is a potential point of failure.  Typical attempts to make such systems more robust and secure are both brittle and incomplete.  That is, the security is easily broken, and there are many possible failure modes that are not handled.  Techniques that expand to handling component level failures are very expensive to apply, yet are still quite brittle and incomplete. This is not because engineers are lazy – the sheer size and complexity of modern information systems overwhelms the attempts of engineers, and myriad methodologies, to systematically investigate, identify, and specify a response to all possible failures of a system. 

Adding dynamic intelligent fault awareness and recovery to running systems enables the identification of unanticipated failures and the construction of novel workarounds to these failures.  Our approach is pervasive and incremental.  It is pervasive in that it applies to all components of a large, complex system – not just the “firewall” services.  It is incremental in that it coexists with existing faulty, unsafe systems, and it is possible to incrementally increase the safety and reliability of large systems. The approach aims to minimize the cost, in terms of hand-coded specifications with respect to how to isolate and recover from failures.


At the heart of our system is a model-based programming language called RMPL that provides a language for specifying correct and faulty behavior of the systems software components. The novel ideas in our approach include method deprecation and method regeneration in tandem with an intelligent runtime model-based executive that performs automated fault management from engineering models, and that utilizes decision-theoretic method dispatch.  Once a system has been enhanced by abstract models of the nominal and faulty behavior of its components, the model-based executive monitors the state of the individual components according to the models.  If faults in a system render some methods (procedures for accomplishing individual goals) inapplicable, method deprecation removes the methods from consideration by the decision-theoretic dispatch.  Method regeneration involves repairing or reconfiguring the underlying services that are causing some method to be inapplicable.  This regeneration is achieved by reasoning about the consequences of actions using the component models, and by exploiting functional redundancies in the specified methods.  In addition, decision-theoretic dispatch continually monitors method performance and dynamically selects the applicable method that accomplishes the intended goals with maximum safety, timeliness, and accuracy.

Beyond simply modeling existing software and hardware components, we allow the specification of high-level methods.  A method defines the intended state evolution of a system in terms of goals and fundamental control constructs, such as iteration, parallelism, and conditionals.  Over time, the more that a system’s behavior is specified in terms of model-based methods, the more that the system will be able to take full advantage of the benefits of model-based programming and the runtime model-based executive.  Implementing functionality in terms of methods enables method prognosis, which involves proactive method deprecation and regeneration, by looking ahead in time through a temporal plan for future method invocations.

Our approach provides a well-grounded technology for incrementally increasing the robustness of complex, concurrent, critical applications.  When applied pervasively, model-based execution will dramatically increase the security and reliability of these systems, as well as improve overall performance, especially when the system is under stress.

Self Deprecation and Regeneration Through Predictive Method Dispatc

In model-based programming, the execution of a method will fail if one of the service components it relies upon irreparably fails.  This in turn can cause the failure of any method that relies upon it, potentially cascading to a catastrophic and irrecoverable system-wide malfunction.  The control sequencer enhances robustness by continuously searching for and deprecating any requisite method whose successful execution relies upon a component that is deemed faulty by mode estimation, and deemed irreparable by mode reconfiguration. 

Without additional action, a deprecated method will cause the deprecation of any method that relies upon it, potentially cascading to catastrophic system-level malfunction.  Model-based programmers specify redundant methods for achieving each desired function.  When a requisite method is deprecated, the control sequencer attempts to regenerate the lost function proactively, by selecting an applicable alternative method, while verifying overall safety of execution. 

Comparison with Current Technology

The reactive model-based programming language (RMPL) is similar to reactive embedded synchronous programming languages like Esterel. 

RMPL supports nondeterministic or decision theoretic choice, plus flexible timing constraints.  Robotic execution languages, such as RAPS, [2], ESL[4] and TDL[3], offer a form of decision theoretic choice between methods and timing constraints.  The set of timing constraints of an RMPL program constitutes a Simple Temporal Network (STN).  Dechter and Meiri showed that, whether or not a consistent execution exists, can be determined by converting the STN to a directed graph, called a distance graph, and by solving two single source shortest path problems on the graph.  RMPL execution is unique in that it predictively selects a set of future methods whose execution are temporally feasible.


[1] D. Bernard, G. Dorais, E. Gamble, B. Kanefsky, J. Kurien, G. Man, W. Millar, N. Muscettola, P. Nayak, K. Rajan, N. Rouquette, B. Smith, W. Taylor, Y. Tung, Spacecraft Autonomy Flight Experience: The DS1 Remote Agent Experiment, Proceedings of the AIAA Space Technology Conference & Exposition, Albuquerque, NM, Sept. 28-30, 1999. AIAA-99-4512.

[2] R. Firby, “The RAP language manual,” Working Note AAP-6.  University of Chicago, 1995.

[3] R. Simmons, “Structured Control for Autonomous Robots,” IEEE Transactions on Robotics and Automation, 10(1), 94.

[4] E Gat, “ESL: A Language for Supporting Robust Plan Execution in Embedded Autonomous Agents,” In Proceedings of the AAAI Fall Symposium on Plan Execution, 1996.

[5] B. Williams and P. Nayak. A Reactive Planner for a Model-based Execution. In Proceedings 15th International Joint Conference AI, Nagoya, Japan, August 1997. IJCAI-97.

horizontal line

MIT logo Computer Science and Artificial Intelligence Laboratory (CSAIL)
The Stata Center, Building 32 - 32 Vassar Street - Cambridge, MA 02139 - USA
tel:+1-617-253-0073 - publications@csail.mit.edu
(Note: On July 1, 2003, the AI Lab and LCS merged to form CSAIL.)