An automated approach to monitoring and diagnosing requirements

ABSTRACT

Monitoring the satisfaction of software requirements and diagnosing what went wrong in case of failure is a hard problem that has received little attention in the Software and Requirement Engineering literature. To address this problem, we propose a framework adapted from artificial intelligence theories of action and diagnosis. Specifically, the framework monitors the satisfaction of software requirements and generates log data at a level of granularity that can be tuned adaptively at runtime depending on monitored feedback. When errors are found, the framework diagnoses the denial of the requirements and identifies problematic components. To support diagnostic reasoning, we transform the diagnostic problem into apropositional satisfiability (SAT) problem that can be solved by existing SAT solvers. We preprocess log data into a compact propositional encoding that better scales with problem size. The proposed theoretical framework has been implemented as a diagnosing component that will return sound and complete diagnoses accounting for observed aberrant system behaviors. Our solution is illustrated with two medium-sized publicly available case studies: a Web-based email client and an ATM simulation. Our experimental results demonstrate the feasibility of scaling our approach to medium-size software systems

REFERENCES

• 1: R. Bjork. An ATM simulation. http://www.cs.gordon.edu/courses/cs211/atmexample.
• 2: R. Castello. Squirrel mail, http://www.squirrelmail.org/.
• 3: Martin Davis , George Logemann , Donald Loveland, A machine program for theorem-proving, Communications of the ACM, v.5 n.7, p.394-397, July 1962 [doi>10.1145/368273.368557]
• 4: Johan de Kleer , Alan K. Mackworth , Raymond Reiter, Characterizing diagnoses and systems, Artificial Intelligence, v.56 n.2-3, p.197-222, Aug. 1992 [doi>10.1016/0004-3702(92)90027-U]
• 5: M. S. Feather , S. Fickas , A. Van Lamsweerde , C. Ponsard, Reconciling System Requirements and Runtime Behavior, Proceedings of the 9th international workshop on Software specification and design, p.50, April 16-18, 1998
• 6: S. Fickas , M. S. Feather, Requirements monitoring in dynamic environments, Proceedings of the Second IEEE International Symposium on Requirements Engineering, p.140, March 27-29, 1995
• 7: Paolo Giorgini , John Mylopoulos , Eleonora Nicchiarelli , Roberto Sebastiani, Reasoning with Goal Models, Proceedings of the 21st International Conference on Conceptual Modeling, p.167-181, October 07-11, 2002
• 8: E. Goldberg , Y. Novikov, BerkMin: A Fast and Robust Sat-Solver, Proceedings of the conference on Design, automation and test in Europe, p.142, March 04-08, 2002
• 9: Gero Iwan, History-based diagnosis templates in the framework of the situation calculus, AI Communications, v.15 n.1, p.31-45, January 2002
• 10: Axel van Lamsweerde , Emmanuel Letier, Handling Obstacles in Goal-Oriented Requirements Engineering, IEEE Transactions on Software Engineering, v.26 n.10, p.978-1005, October 2000 [doi>10.1109/32.879820]
• 11: D. Le Berre. A satisfiability library for java. http://www.sat4j.org/.
• 12: S. McIlraith. Explanatory diagnosis: Conjecturing actions to explain observations. In KR'98, pages 167--179, 1998.
• 13: Matthew W. Moskewicz , Conor F. Madigan , Ying Zhao , Lintao Zhang , Sharad Malik, Chaff: engineering an efficient SAT solver, Proceedings of the 38th conference on Design automation, p.530-535, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379017]
• 14: J. Mylopoulos , L. Chung , B. Nixon, Representing and Using Nonfunctional Requirements: A Process-Oriented Approach, IEEE Transactions on Software Engineering, v.18 n.6, p.483-497, June 1992 [doi>10.1109/32.142871]
• 15: R Reiter, A theory of diagnosis from first principles, Artificial Intelligence, v.32 n.1, p.57-95, April 1987 [doi>10.1016/0004-3702(87)90062-2]
• 16: Raymond Reiter, The frame problem in situation the calculus: a simple solution (sometimes) and a completeness result for goal regression, Artificial intelligence and mathematical theory of computation: papers in honor of John McCarthy, Academic Press Professional, Inc., San Diego, CA, 1991
• 17: William N. Robinson, Implementing Rule-Based Monitors within a Framework for Continuous Requirements Monitoring, Proceedings of the Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS'05) - Track 7, p.188.1, January 03-06, 2005 [doi>10.1109/HICSS.2005.306]
• 18: L. Ryan. Efficient algorithms for clause-learning SAT solvers. Master's thesis, Simon Fraser University, 2004.
• 19: R. Sebastiani, P. Giorgini, and J. Mylopoulos. Simple and minimum-cost satisfiability for goal models. In CAiSE'04, volume 4, pages 20--33. Springer, 2004.
• 20: A. Van Lamsweerde , R. Darimont , P. Massonet, Goal-directed elaboration of requirements for a meeting scheduler: problems and lessons learnt, Proceedings of the Second IEEE International Symposium on Requirements Engineering, p.194, March 27-29, 1995
• 21: Y. Wang, Y. Yu, and J. Mylopoulos. Monitoring and diagnosing requirements. Technical report, University of Toronto, 2007. CSRG-555.
• 22: Kristina Winbladh , Thomas A. Alspaugh , Hadar Ziv , Debra J. Richardson, An Automated Approach for Goal-driven, Specification-based Testing, Proceedings of the 21st IEEE/ACM International Conference on Automated Software Engineering, p.289-292, September 18-22, 2006 [doi>10.1109/ASE.2006.11]
• 23: Yijun Yu , Yiqiao Wang , John Mylopoulos , Sotirios Liaskos , Alexei Lapouchnian , Julio Cesar Sampaio do Prado Leite, Reverse Engineering Goal Models from Legacy Code, Proceedings of the 13th IEEE International Conference on Requirements Engineering, p.363-372, August 29-September 02, 2005 [doi>10.1109/RE.2005.61]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Diagnostics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Monitors

General Terms:
Design, Theory, Verification

Keywords:
diagnostics, requirements monitoring