Abstract
This paper focuses on the consistency analysis of specification rules expressing relationships between input and expected output of systems. We identified the link between Minimal Inconsistent Sets (MISes) of rules and Minimal Unsatisfiable Subsets (MUSes) of constraints. For practical consistency verification of rules, we developed a novel algorithm using SMT solvers for fast enumeration of MUSes. We evaluated the algorithm using publicly available benchmarks. Finally, we used the approach to verify the consistency of specifications rules extracted from real-world case studies.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
\(S \subset T\) means that S is a proper-subset of T.
- 2.
Available from http://smtlib.cs.uiowa.edu/benchmarks.shtml.
References
Abrial, J.-R.: Modeling in Event-B: System and Software Engineering. Cambridge University Press, New York (2010)
Abrial, J.-R., Butler, M., Hallerstede, S., Hoang, T.S., Mehta, F., Voisin, L.: Rodin: an open toolset for modelling and reasoning in Event-B. STTT 12(6), 447–466 (2010)
Bailey, J., Stuckey, P.J.: Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization. In: Hermenegildo, M.V., Cabeza, D. (eds.) PADL 2004. LNCS, vol. 3350, pp. 174–186. Springer, Heidelberg (2005)
Barrett, C.W., Sebastiani, R., Seshia, S.A., Tinelli, C.: Satisfiability modulo theories. In: Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185, pp. 825–885. IOS Press (2009)
Belov, A., Manthey, N., Marques-Silva, J.: Parallel MUS extraction. In: Järvisalo, M., Van Gelder, A. (eds.) SAT 2013. LNCS, vol. 7962, pp. 133–149. Springer, Heidelberg (2013)
Belov, A., Marques-Silva, J.: MUSer2: an efficient MUS extractor. JSAT 8(1/2), 123–128 (2012)
Berstel, B., Leconte, M.: Using constraints to verify properties of rule programs. ICST 2010, 349–354 (2010)
Christ, J., Hoenicke, J., Nutz, A.: SMTInterpol: an interpolating SMT solver. In: Donaldson, A., Parker, D. (eds.) SPIN 2012. LNCS, vol. 7385, pp. 248–254. Springer, Heidelberg (2012)
Hoang, T.S., Itoh, S., Oyama, K., Miyazaki, K., Kuruma, H., Sato, N.: Validating the consistency of specification rules. http://deploy-eprints.ecs.soton.ac.uk/465/ (2015)
Liffiton, M.H., Malik, A.: Enumerating infeasibility: finding multiple MUSes quickly. In: Gomes, C., Sellmann, M. (eds.) CPAIOR 2013. LNCS, vol. 7874, pp. 160–175. Springer, Heidelberg (2013)
Liffiton, M.H., Sakallah, K.A.: Algorithms for computing minimal unsatisfiable subsets of constraints. J. Autom. Reasoning 40(1), 1–33 (2008)
Ligeza, A.: Logical Foundations for Rule-Based Systems. Studies in Computational Intelligence, vol. 11, 2nd edn. Springer, Heidelberg (2006)
Nadel, A., Ryvchin, V., Strichman, O.: Efficient MUS extraction with resolution. In: FMCAD 2013, pp. 197–200. IEEE (2013)
Berstel-Da Silva, B.: Verification of Business Rules Programs. Springer, Heidelberg (2014)
Wieringa, S.: Understanding, improving and parallelizing MUS finding using model rotation. In: Milano, M. (ed.) CP 2012. LNCS, vol. 7514, pp. 672–687. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Hoang, T.S., Itoh, S., Oyama, K., Miyazaki, K., Kuruma, H., Sato, N. (2015). Consistency Verification of Specification Rules. In: Butler, M., Conchon, S., Zaïdi, F. (eds) Formal Methods and Software Engineering. ICFEM 2015. Lecture Notes in Computer Science(), vol 9407. Springer, Cham. https://doi.org/10.1007/978-3-319-25423-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-25423-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-25422-7
Online ISBN: 978-3-319-25423-4
eBook Packages: Computer ScienceComputer Science (R0)